1==================== 2Writing an LLVM Pass 3==================== 4 5.. contents:: 6 :local: 7 8Introduction --- What is a pass? 9================================ 10 11The LLVM Pass Framework is an important part of the LLVM system, because LLVM 12passes are where most of the interesting parts of the compiler exist. Passes 13perform the transformations and optimizations that make up the compiler, they 14build the analysis results that are used by these transformations, and they 15are, above all, a structuring technique for compiler code. 16 17All LLVM passes are subclasses of the `Pass 18<http://llvm.org/doxygen/classllvm_1_1Pass.html>`_ class, which implement 19functionality by overriding virtual methods inherited from ``Pass``. Depending 20on how your pass works, you should inherit from the :ref:`ModulePass 21<writing-an-llvm-pass-ModulePass>` , :ref:`CallGraphSCCPass 22<writing-an-llvm-pass-CallGraphSCCPass>`, :ref:`FunctionPass 23<writing-an-llvm-pass-FunctionPass>` , or :ref:`LoopPass 24<writing-an-llvm-pass-LoopPass>`, or :ref:`RegionPass 25<writing-an-llvm-pass-RegionPass>`, or :ref:`BasicBlockPass 26<writing-an-llvm-pass-BasicBlockPass>` classes, which gives the system more 27information about what your pass does, and how it can be combined with other 28passes. One of the main features of the LLVM Pass Framework is that it 29schedules passes to run in an efficient way based on the constraints that your 30pass meets (which are indicated by which class they derive from). 31 32We start by showing you how to construct a pass, everything from setting up the 33code, to compiling, loading, and executing it. After the basics are down, more 34advanced features are discussed. 35 36Quick Start --- Writing hello world 37=================================== 38 39Here we describe how to write the "hello world" of passes. The "Hello" pass is 40designed to simply print out the name of non-external functions that exist in 41the program being compiled. It does not modify the program at all, it just 42inspects it. The source code and files for this pass are available in the LLVM 43source tree in the ``lib/Transforms/Hello`` directory. 44 45.. _writing-an-llvm-pass-makefile: 46 47Setting up the build environment 48-------------------------------- 49 50.. FIXME: Why does this recommend to build in-tree? 51 52First, configure and build LLVM. This needs to be done directly inside the 53LLVM source tree rather than in a separate objects directory. Next, you need 54to create a new directory somewhere in the LLVM source base. For this example, 55we'll assume that you made ``lib/Transforms/Hello``. Finally, you must set up 56a build script (``Makefile``) that will compile the source code for the new 57pass. To do this, copy the following into ``Makefile``: 58 59.. code-block:: make 60 61 # Makefile for hello pass 62 63 # Path to top level of LLVM hierarchy 64 LEVEL = ../../.. 65 66 # Name of the library to build 67 LIBRARYNAME = Hello 68 69 # Make the shared library become a loadable module so the tools can 70 # dlopen/dlsym on the resulting library. 71 LOADABLE_MODULE = 1 72 73 # Include the makefile implementation stuff 74 include $(LEVEL)/Makefile.common 75 76This makefile specifies that all of the ``.cpp`` files in the current directory 77are to be compiled and linked together into a shared object 78``$(LEVEL)/Debug+Asserts/lib/Hello.so`` that can be dynamically loaded by the 79:program:`opt` or :program:`bugpoint` tools via their :option:`-load` options. 80If your operating system uses a suffix other than ``.so`` (such as Windows or Mac 81OS X), the appropriate extension will be used. 82 83If you are used CMake to build LLVM, see :ref:`cmake-out-of-source-pass`. 84 85Now that we have the build scripts set up, we just need to write the code for 86the pass itself. 87 88.. _writing-an-llvm-pass-basiccode: 89 90Basic code required 91------------------- 92 93Now that we have a way to compile our new pass, we just have to write it. 94Start out with: 95 96.. code-block:: c++ 97 98 #include "llvm/Pass.h" 99 #include "llvm/IR/Function.h" 100 #include "llvm/Support/raw_ostream.h" 101 102Which are needed because we are writing a `Pass 103<http://llvm.org/doxygen/classllvm_1_1Pass.html>`_, we are operating on 104`Function <http://llvm.org/doxygen/classllvm_1_1Function.html>`_\ s, and we will 105be doing some printing. 106 107Next we have: 108 109.. code-block:: c++ 110 111 using namespace llvm; 112 113... which is required because the functions from the include files live in the 114llvm namespace. 115 116Next we have: 117 118.. code-block:: c++ 119 120 namespace { 121 122... which starts out an anonymous namespace. Anonymous namespaces are to C++ 123what the "``static``" keyword is to C (at global scope). It makes the things 124declared inside of the anonymous namespace visible only to the current file. 125If you're not familiar with them, consult a decent C++ book for more 126information. 127 128Next, we declare our pass itself: 129 130.. code-block:: c++ 131 132 struct Hello : public FunctionPass { 133 134This declares a "``Hello``" class that is a subclass of :ref:`FunctionPass 135<writing-an-llvm-pass-FunctionPass>`. The different builtin pass subclasses 136are described in detail :ref:`later <writing-an-llvm-pass-pass-classes>`, but 137for now, know that ``FunctionPass`` operates on a function at a time. 138 139.. code-block:: c++ 140 141 static char ID; 142 Hello() : FunctionPass(ID) {} 143 144This declares pass identifier used by LLVM to identify pass. This allows LLVM 145to avoid using expensive C++ runtime information. 146 147.. code-block:: c++ 148 149 bool runOnFunction(Function &F) override { 150 errs() << "Hello: "; 151 errs().write_escaped(F.getName()) << "\n"; 152 return false; 153 } 154 }; // end of struct Hello 155 } // end of anonymous namespace 156 157We declare a :ref:`runOnFunction <writing-an-llvm-pass-runOnFunction>` method, 158which overrides an abstract virtual method inherited from :ref:`FunctionPass 159<writing-an-llvm-pass-FunctionPass>`. This is where we are supposed to do our 160thing, so we just print out our message with the name of each function. 161 162.. code-block:: c++ 163 164 char Hello::ID = 0; 165 166We initialize pass ID here. LLVM uses ID's address to identify a pass, so 167initialization value is not important. 168 169.. code-block:: c++ 170 171 static RegisterPass<Hello> X("hello", "Hello World Pass", 172 false /* Only looks at CFG */, 173 false /* Analysis Pass */); 174 175Lastly, we :ref:`register our class <writing-an-llvm-pass-registration>` 176``Hello``, giving it a command line argument "``hello``", and a name "Hello 177World Pass". The last two arguments describe its behavior: if a pass walks CFG 178without modifying it then the third argument is set to ``true``; if a pass is 179an analysis pass, for example dominator tree pass, then ``true`` is supplied as 180the fourth argument. 181 182As a whole, the ``.cpp`` file looks like: 183 184.. code-block:: c++ 185 186 #include "llvm/Pass.h" 187 #include "llvm/IR/Function.h" 188 #include "llvm/Support/raw_ostream.h" 189 190 using namespace llvm; 191 192 namespace { 193 struct Hello : public FunctionPass { 194 static char ID; 195 Hello() : FunctionPass(ID) {} 196 197 bool runOnFunction(Function &F) override { 198 errs() << "Hello: "; 199 errs().write_escaped(F.getName()) << '\n'; 200 return false; 201 } 202 }; 203 } 204 205 char Hello::ID = 0; 206 static RegisterPass<Hello> X("hello", "Hello World Pass", false, false); 207 208Now that it's all together, compile the file with a simple "``gmake``" command 209in the local directory and you should get a new file 210"``Debug+Asserts/lib/Hello.so``" under the top level directory of the LLVM 211source tree (not in the local directory). Note that everything in this file is 212contained in an anonymous namespace --- this reflects the fact that passes 213are self contained units that do not need external interfaces (although they 214can have them) to be useful. 215 216Running a pass with ``opt`` 217--------------------------- 218 219Now that you have a brand new shiny shared object file, we can use the 220:program:`opt` command to run an LLVM program through your pass. Because you 221registered your pass with ``RegisterPass``, you will be able to use the 222:program:`opt` tool to access it, once loaded. 223 224To test it, follow the example at the end of the :doc:`GettingStarted` to 225compile "Hello World" to LLVM. We can now run the bitcode file (hello.bc) for 226the program through our transformation like this (or course, any bitcode file 227will work): 228 229.. code-block:: console 230 231 $ opt -load ../../../Debug+Asserts/lib/Hello.so -hello < hello.bc > /dev/null 232 Hello: __main 233 Hello: puts 234 Hello: main 235 236The :option:`-load` option specifies that :program:`opt` should load your pass 237as a shared object, which makes "``-hello``" a valid command line argument 238(which is one reason you need to :ref:`register your pass 239<writing-an-llvm-pass-registration>`). Because the Hello pass does not modify 240the program in any interesting way, we just throw away the result of 241:program:`opt` (sending it to ``/dev/null``). 242 243To see what happened to the other string you registered, try running 244:program:`opt` with the :option:`-help` option: 245 246.. code-block:: console 247 248 $ opt -load ../../../Debug+Asserts/lib/Hello.so -help 249 OVERVIEW: llvm .bc -> .bc modular optimizer 250 251 USAGE: opt [options] <input bitcode> 252 253 OPTIONS: 254 Optimizations available: 255 ... 256 -globalopt - Global Variable Optimizer 257 -globalsmodref-aa - Simple mod/ref analysis for globals 258 -gvn - Global Value Numbering 259 -hello - Hello World Pass 260 -indvars - Induction Variable Simplification 261 -inline - Function Integration/Inlining 262 ... 263 264The pass name gets added as the information string for your pass, giving some 265documentation to users of :program:`opt`. Now that you have a working pass, 266you would go ahead and make it do the cool transformations you want. Once you 267get it all working and tested, it may become useful to find out how fast your 268pass is. The :ref:`PassManager <writing-an-llvm-pass-passmanager>` provides a 269nice command line option (:option:`--time-passes`) that allows you to get 270information about the execution time of your pass along with the other passes 271you queue up. For example: 272 273.. code-block:: console 274 275 $ opt -load ../../../Debug+Asserts/lib/Hello.so -hello -time-passes < hello.bc > /dev/null 276 Hello: __main 277 Hello: puts 278 Hello: main 279 =============================================================================== 280 ... Pass execution timing report ... 281 =============================================================================== 282 Total Execution Time: 0.02 seconds (0.0479059 wall clock) 283 284 ---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Pass Name --- 285 0.0100 (100.0%) 0.0000 ( 0.0%) 0.0100 ( 50.0%) 0.0402 ( 84.0%) Bitcode Writer 286 0.0000 ( 0.0%) 0.0100 (100.0%) 0.0100 ( 50.0%) 0.0031 ( 6.4%) Dominator Set Construction 287 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0013 ( 2.7%) Module Verifier 288 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0033 ( 6.9%) Hello World Pass 289 0.0100 (100.0%) 0.0100 (100.0%) 0.0200 (100.0%) 0.0479 (100.0%) TOTAL 290 291As you can see, our implementation above is pretty fast. The additional 292passes listed are automatically inserted by the :program:`opt` tool to verify 293that the LLVM emitted by your pass is still valid and well formed LLVM, which 294hasn't been broken somehow. 295 296Now that you have seen the basics of the mechanics behind passes, we can talk 297about some more details of how they work and how to use them. 298 299.. _writing-an-llvm-pass-pass-classes: 300 301Pass classes and requirements 302============================= 303 304One of the first things that you should do when designing a new pass is to 305decide what class you should subclass for your pass. The :ref:`Hello World 306<writing-an-llvm-pass-basiccode>` example uses the :ref:`FunctionPass 307<writing-an-llvm-pass-FunctionPass>` class for its implementation, but we did 308not discuss why or when this should occur. Here we talk about the classes 309available, from the most general to the most specific. 310 311When choosing a superclass for your ``Pass``, you should choose the **most 312specific** class possible, while still being able to meet the requirements 313listed. This gives the LLVM Pass Infrastructure information necessary to 314optimize how passes are run, so that the resultant compiler isn't unnecessarily 315slow. 316 317The ``ImmutablePass`` class 318--------------------------- 319 320The most plain and boring type of pass is the "`ImmutablePass 321<http://llvm.org/doxygen/classllvm_1_1ImmutablePass.html>`_" class. This pass 322type is used for passes that do not have to be run, do not change state, and 323never need to be updated. This is not a normal type of transformation or 324analysis, but can provide information about the current compiler configuration. 325 326Although this pass class is very infrequently used, it is important for 327providing information about the current target machine being compiled for, and 328other static information that can affect the various transformations. 329 330``ImmutablePass``\ es never invalidate other transformations, are never 331invalidated, and are never "run". 332 333.. _writing-an-llvm-pass-ModulePass: 334 335The ``ModulePass`` class 336------------------------ 337 338The `ModulePass <http://llvm.org/doxygen/classllvm_1_1ModulePass.html>`_ class 339is the most general of all superclasses that you can use. Deriving from 340``ModulePass`` indicates that your pass uses the entire program as a unit, 341referring to function bodies in no predictable order, or adding and removing 342functions. Because nothing is known about the behavior of ``ModulePass`` 343subclasses, no optimization can be done for their execution. 344 345A module pass can use function level passes (e.g. dominators) using the 346``getAnalysis`` interface ``getAnalysis<DominatorTree>(llvm::Function *)`` to 347provide the function to retrieve analysis result for, if the function pass does 348not require any module or immutable passes. Note that this can only be done 349for functions for which the analysis ran, e.g. in the case of dominators you 350should only ask for the ``DominatorTree`` for function definitions, not 351declarations. 352 353To write a correct ``ModulePass`` subclass, derive from ``ModulePass`` and 354overload the ``runOnModule`` method with the following signature: 355 356The ``runOnModule`` method 357^^^^^^^^^^^^^^^^^^^^^^^^^^ 358 359.. code-block:: c++ 360 361 virtual bool runOnModule(Module &M) = 0; 362 363The ``runOnModule`` method performs the interesting work of the pass. It 364should return ``true`` if the module was modified by the transformation and 365``false`` otherwise. 366 367.. _writing-an-llvm-pass-CallGraphSCCPass: 368 369The ``CallGraphSCCPass`` class 370------------------------------ 371 372The `CallGraphSCCPass 373<http://llvm.org/doxygen/classllvm_1_1CallGraphSCCPass.html>`_ is used by 374passes that need to traverse the program bottom-up on the call graph (callees 375before callers). Deriving from ``CallGraphSCCPass`` provides some mechanics 376for building and traversing the ``CallGraph``, but also allows the system to 377optimize execution of ``CallGraphSCCPass``\ es. If your pass meets the 378requirements outlined below, and doesn't meet the requirements of a 379:ref:`FunctionPass <writing-an-llvm-pass-FunctionPass>` or :ref:`BasicBlockPass 380<writing-an-llvm-pass-BasicBlockPass>`, you should derive from 381``CallGraphSCCPass``. 382 383``TODO``: explain briefly what SCC, Tarjan's algo, and B-U mean. 384 385To be explicit, CallGraphSCCPass subclasses are: 386 387#. ... *not allowed* to inspect or modify any ``Function``\ s other than those 388 in the current SCC and the direct callers and direct callees of the SCC. 389#. ... *required* to preserve the current ``CallGraph`` object, updating it to 390 reflect any changes made to the program. 391#. ... *not allowed* to add or remove SCC's from the current Module, though 392 they may change the contents of an SCC. 393#. ... *allowed* to add or remove global variables from the current Module. 394#. ... *allowed* to maintain state across invocations of :ref:`runOnSCC 395 <writing-an-llvm-pass-runOnSCC>` (including global data). 396 397Implementing a ``CallGraphSCCPass`` is slightly tricky in some cases because it 398has to handle SCCs with more than one node in it. All of the virtual methods 399described below should return ``true`` if they modified the program, or 400``false`` if they didn't. 401 402The ``doInitialization(CallGraph &)`` method 403^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 404 405.. code-block:: c++ 406 407 virtual bool doInitialization(CallGraph &CG); 408 409The ``doInitialization`` method is allowed to do most of the things that 410``CallGraphSCCPass``\ es are not allowed to do. They can add and remove 411functions, get pointers to functions, etc. The ``doInitialization`` method is 412designed to do simple initialization type of stuff that does not depend on the 413SCCs being processed. The ``doInitialization`` method call is not scheduled to 414overlap with any other pass executions (thus it should be very fast). 415 416.. _writing-an-llvm-pass-runOnSCC: 417 418The ``runOnSCC`` method 419^^^^^^^^^^^^^^^^^^^^^^^ 420 421.. code-block:: c++ 422 423 virtual bool runOnSCC(CallGraphSCC &SCC) = 0; 424 425The ``runOnSCC`` method performs the interesting work of the pass, and should 426return ``true`` if the module was modified by the transformation, ``false`` 427otherwise. 428 429The ``doFinalization(CallGraph &)`` method 430^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 431 432.. code-block:: c++ 433 434 virtual bool doFinalization(CallGraph &CG); 435 436The ``doFinalization`` method is an infrequently used method that is called 437when the pass framework has finished calling :ref:`runOnSCC 438<writing-an-llvm-pass-runOnSCC>` for every SCC in the program being compiled. 439 440.. _writing-an-llvm-pass-FunctionPass: 441 442The ``FunctionPass`` class 443-------------------------- 444 445In contrast to ``ModulePass`` subclasses, `FunctionPass 446<http://llvm.org/doxygen/classllvm_1_1Pass.html>`_ subclasses do have a 447predictable, local behavior that can be expected by the system. All 448``FunctionPass`` execute on each function in the program independent of all of 449the other functions in the program. ``FunctionPass``\ es do not require that 450they are executed in a particular order, and ``FunctionPass``\ es do not modify 451external functions. 452 453To be explicit, ``FunctionPass`` subclasses are not allowed to: 454 455#. Inspect or modify a ``Function`` other than the one currently being processed. 456#. Add or remove ``Function``\ s from the current ``Module``. 457#. Add or remove global variables from the current ``Module``. 458#. Maintain state across invocations of :ref:`runOnFunction 459 <writing-an-llvm-pass-runOnFunction>` (including global data). 460 461Implementing a ``FunctionPass`` is usually straightforward (See the :ref:`Hello 462World <writing-an-llvm-pass-basiccode>` pass for example). 463``FunctionPass``\ es may overload three virtual methods to do their work. All 464of these methods should return ``true`` if they modified the program, or 465``false`` if they didn't. 466 467.. _writing-an-llvm-pass-doInitialization-mod: 468 469The ``doInitialization(Module &)`` method 470^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 471 472.. code-block:: c++ 473 474 virtual bool doInitialization(Module &M); 475 476The ``doInitialization`` method is allowed to do most of the things that 477``FunctionPass``\ es are not allowed to do. They can add and remove functions, 478get pointers to functions, etc. The ``doInitialization`` method is designed to 479do simple initialization type of stuff that does not depend on the functions 480being processed. The ``doInitialization`` method call is not scheduled to 481overlap with any other pass executions (thus it should be very fast). 482 483A good example of how this method should be used is the `LowerAllocations 484<http://llvm.org/doxygen/LowerAllocations_8cpp-source.html>`_ pass. This pass 485converts ``malloc`` and ``free`` instructions into platform dependent 486``malloc()`` and ``free()`` function calls. It uses the ``doInitialization`` 487method to get a reference to the ``malloc`` and ``free`` functions that it 488needs, adding prototypes to the module if necessary. 489 490.. _writing-an-llvm-pass-runOnFunction: 491 492The ``runOnFunction`` method 493^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 494 495.. code-block:: c++ 496 497 virtual bool runOnFunction(Function &F) = 0; 498 499The ``runOnFunction`` method must be implemented by your subclass to do the 500transformation or analysis work of your pass. As usual, a ``true`` value 501should be returned if the function is modified. 502 503.. _writing-an-llvm-pass-doFinalization-mod: 504 505The ``doFinalization(Module &)`` method 506^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 507 508.. code-block:: c++ 509 510 virtual bool doFinalization(Module &M); 511 512The ``doFinalization`` method is an infrequently used method that is called 513when the pass framework has finished calling :ref:`runOnFunction 514<writing-an-llvm-pass-runOnFunction>` for every function in the program being 515compiled. 516 517.. _writing-an-llvm-pass-LoopPass: 518 519The ``LoopPass`` class 520---------------------- 521 522All ``LoopPass`` execute on each loop in the function independent of all of the 523other loops in the function. ``LoopPass`` processes loops in loop nest order 524such that outer most loop is processed last. 525 526``LoopPass`` subclasses are allowed to update loop nest using ``LPPassManager`` 527interface. Implementing a loop pass is usually straightforward. 528``LoopPass``\ es may overload three virtual methods to do their work. All 529these methods should return ``true`` if they modified the program, or ``false`` 530if they didn't. 531 532The ``doInitialization(Loop *, LPPassManager &)`` method 533^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 534 535.. code-block:: c++ 536 537 virtual bool doInitialization(Loop *, LPPassManager &LPM); 538 539The ``doInitialization`` method is designed to do simple initialization type of 540stuff that does not depend on the functions being processed. The 541``doInitialization`` method call is not scheduled to overlap with any other 542pass executions (thus it should be very fast). ``LPPassManager`` interface 543should be used to access ``Function`` or ``Module`` level analysis information. 544 545.. _writing-an-llvm-pass-runOnLoop: 546 547The ``runOnLoop`` method 548^^^^^^^^^^^^^^^^^^^^^^^^ 549 550.. code-block:: c++ 551 552 virtual bool runOnLoop(Loop *, LPPassManager &LPM) = 0; 553 554The ``runOnLoop`` method must be implemented by your subclass to do the 555transformation or analysis work of your pass. As usual, a ``true`` value 556should be returned if the function is modified. ``LPPassManager`` interface 557should be used to update loop nest. 558 559The ``doFinalization()`` method 560^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 561 562.. code-block:: c++ 563 564 virtual bool doFinalization(); 565 566The ``doFinalization`` method is an infrequently used method that is called 567when the pass framework has finished calling :ref:`runOnLoop 568<writing-an-llvm-pass-runOnLoop>` for every loop in the program being compiled. 569 570.. _writing-an-llvm-pass-RegionPass: 571 572The ``RegionPass`` class 573------------------------ 574 575``RegionPass`` is similar to :ref:`LoopPass <writing-an-llvm-pass-LoopPass>`, 576but executes on each single entry single exit region in the function. 577``RegionPass`` processes regions in nested order such that the outer most 578region is processed last. 579 580``RegionPass`` subclasses are allowed to update the region tree by using the 581``RGPassManager`` interface. You may overload three virtual methods of 582``RegionPass`` to implement your own region pass. All these methods should 583return ``true`` if they modified the program, or ``false`` if they did not. 584 585The ``doInitialization(Region *, RGPassManager &)`` method 586^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 587 588.. code-block:: c++ 589 590 virtual bool doInitialization(Region *, RGPassManager &RGM); 591 592The ``doInitialization`` method is designed to do simple initialization type of 593stuff that does not depend on the functions being processed. The 594``doInitialization`` method call is not scheduled to overlap with any other 595pass executions (thus it should be very fast). ``RPPassManager`` interface 596should be used to access ``Function`` or ``Module`` level analysis information. 597 598.. _writing-an-llvm-pass-runOnRegion: 599 600The ``runOnRegion`` method 601^^^^^^^^^^^^^^^^^^^^^^^^^^ 602 603.. code-block:: c++ 604 605 virtual bool runOnRegion(Region *, RGPassManager &RGM) = 0; 606 607The ``runOnRegion`` method must be implemented by your subclass to do the 608transformation or analysis work of your pass. As usual, a true value should be 609returned if the region is modified. ``RGPassManager`` interface should be used to 610update region tree. 611 612The ``doFinalization()`` method 613^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 614 615.. code-block:: c++ 616 617 virtual bool doFinalization(); 618 619The ``doFinalization`` method is an infrequently used method that is called 620when the pass framework has finished calling :ref:`runOnRegion 621<writing-an-llvm-pass-runOnRegion>` for every region in the program being 622compiled. 623 624.. _writing-an-llvm-pass-BasicBlockPass: 625 626The ``BasicBlockPass`` class 627---------------------------- 628 629``BasicBlockPass``\ es are just like :ref:`FunctionPass's 630<writing-an-llvm-pass-FunctionPass>` , except that they must limit their scope 631of inspection and modification to a single basic block at a time. As such, 632they are **not** allowed to do any of the following: 633 634#. Modify or inspect any basic blocks outside of the current one. 635#. Maintain state across invocations of :ref:`runOnBasicBlock 636 <writing-an-llvm-pass-runOnBasicBlock>`. 637#. Modify the control flow graph (by altering terminator instructions) 638#. Any of the things forbidden for :ref:`FunctionPasses 639 <writing-an-llvm-pass-FunctionPass>`. 640 641``BasicBlockPass``\ es are useful for traditional local and "peephole" 642optimizations. They may override the same :ref:`doInitialization(Module &) 643<writing-an-llvm-pass-doInitialization-mod>` and :ref:`doFinalization(Module &) 644<writing-an-llvm-pass-doFinalization-mod>` methods that :ref:`FunctionPass's 645<writing-an-llvm-pass-FunctionPass>` have, but also have the following virtual 646methods that may also be implemented: 647 648The ``doInitialization(Function &)`` method 649^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 650 651.. code-block:: c++ 652 653 virtual bool doInitialization(Function &F); 654 655The ``doInitialization`` method is allowed to do most of the things that 656``BasicBlockPass``\ es are not allowed to do, but that ``FunctionPass``\ es 657can. The ``doInitialization`` method is designed to do simple initialization 658that does not depend on the ``BasicBlock``\ s being processed. The 659``doInitialization`` method call is not scheduled to overlap with any other 660pass executions (thus it should be very fast). 661 662.. _writing-an-llvm-pass-runOnBasicBlock: 663 664The ``runOnBasicBlock`` method 665^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 666 667.. code-block:: c++ 668 669 virtual bool runOnBasicBlock(BasicBlock &BB) = 0; 670 671Override this function to do the work of the ``BasicBlockPass``. This function 672is not allowed to inspect or modify basic blocks other than the parameter, and 673are not allowed to modify the CFG. A ``true`` value must be returned if the 674basic block is modified. 675 676The ``doFinalization(Function &)`` method 677^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 678 679.. code-block:: c++ 680 681 virtual bool doFinalization(Function &F); 682 683The ``doFinalization`` method is an infrequently used method that is called 684when the pass framework has finished calling :ref:`runOnBasicBlock 685<writing-an-llvm-pass-runOnBasicBlock>` for every ``BasicBlock`` in the program 686being compiled. This can be used to perform per-function finalization. 687 688The ``MachineFunctionPass`` class 689--------------------------------- 690 691A ``MachineFunctionPass`` is a part of the LLVM code generator that executes on 692the machine-dependent representation of each LLVM function in the program. 693 694Code generator passes are registered and initialized specially by 695``TargetMachine::addPassesToEmitFile`` and similar routines, so they cannot 696generally be run from the :program:`opt` or :program:`bugpoint` commands. 697 698A ``MachineFunctionPass`` is also a ``FunctionPass``, so all the restrictions 699that apply to a ``FunctionPass`` also apply to it. ``MachineFunctionPass``\ es 700also have additional restrictions. In particular, ``MachineFunctionPass``\ es 701are not allowed to do any of the following: 702 703#. Modify or create any LLVM IR ``Instruction``\ s, ``BasicBlock``\ s, 704 ``Argument``\ s, ``Function``\ s, ``GlobalVariable``\ s, 705 ``GlobalAlias``\ es, or ``Module``\ s. 706#. Modify a ``MachineFunction`` other than the one currently being processed. 707#. Maintain state across invocations of :ref:`runOnMachineFunction 708 <writing-an-llvm-pass-runOnMachineFunction>` (including global data). 709 710.. _writing-an-llvm-pass-runOnMachineFunction: 711 712The ``runOnMachineFunction(MachineFunction &MF)`` method 713^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 714 715.. code-block:: c++ 716 717 virtual bool runOnMachineFunction(MachineFunction &MF) = 0; 718 719``runOnMachineFunction`` can be considered the main entry point of a 720``MachineFunctionPass``; that is, you should override this method to do the 721work of your ``MachineFunctionPass``. 722 723The ``runOnMachineFunction`` method is called on every ``MachineFunction`` in a 724``Module``, so that the ``MachineFunctionPass`` may perform optimizations on 725the machine-dependent representation of the function. If you want to get at 726the LLVM ``Function`` for the ``MachineFunction`` you're working on, use 727``MachineFunction``'s ``getFunction()`` accessor method --- but remember, you 728may not modify the LLVM ``Function`` or its contents from a 729``MachineFunctionPass``. 730 731.. _writing-an-llvm-pass-registration: 732 733Pass registration 734----------------- 735 736In the :ref:`Hello World <writing-an-llvm-pass-basiccode>` example pass we 737illustrated how pass registration works, and discussed some of the reasons that 738it is used and what it does. Here we discuss how and why passes are 739registered. 740 741As we saw above, passes are registered with the ``RegisterPass`` template. The 742template parameter is the name of the pass that is to be used on the command 743line to specify that the pass should be added to a program (for example, with 744:program:`opt` or :program:`bugpoint`). The first argument is the name of the 745pass, which is to be used for the :option:`-help` output of programs, as well 746as for debug output generated by the :option:`--debug-pass` option. 747 748If you want your pass to be easily dumpable, you should implement the virtual 749print method: 750 751The ``print`` method 752^^^^^^^^^^^^^^^^^^^^ 753 754.. code-block:: c++ 755 756 virtual void print(llvm::raw_ostream &O, const Module *M) const; 757 758The ``print`` method must be implemented by "analyses" in order to print a 759human readable version of the analysis results. This is useful for debugging 760an analysis itself, as well as for other people to figure out how an analysis 761works. Use the opt ``-analyze`` argument to invoke this method. 762 763The ``llvm::raw_ostream`` parameter specifies the stream to write the results 764on, and the ``Module`` parameter gives a pointer to the top level module of the 765program that has been analyzed. Note however that this pointer may be ``NULL`` 766in certain circumstances (such as calling the ``Pass::dump()`` from a 767debugger), so it should only be used to enhance debug output, it should not be 768depended on. 769 770.. _writing-an-llvm-pass-interaction: 771 772Specifying interactions between passes 773-------------------------------------- 774 775One of the main responsibilities of the ``PassManager`` is to make sure that 776passes interact with each other correctly. Because ``PassManager`` tries to 777:ref:`optimize the execution of passes <writing-an-llvm-pass-passmanager>` it 778must know how the passes interact with each other and what dependencies exist 779between the various passes. To track this, each pass can declare the set of 780passes that are required to be executed before the current pass, and the passes 781which are invalidated by the current pass. 782 783Typically this functionality is used to require that analysis results are 784computed before your pass is run. Running arbitrary transformation passes can 785invalidate the computed analysis results, which is what the invalidation set 786specifies. If a pass does not implement the :ref:`getAnalysisUsage 787<writing-an-llvm-pass-getAnalysisUsage>` method, it defaults to not having any 788prerequisite passes, and invalidating **all** other passes. 789 790.. _writing-an-llvm-pass-getAnalysisUsage: 791 792The ``getAnalysisUsage`` method 793^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 794 795.. code-block:: c++ 796 797 virtual void getAnalysisUsage(AnalysisUsage &Info) const; 798 799By implementing the ``getAnalysisUsage`` method, the required and invalidated 800sets may be specified for your transformation. The implementation should fill 801in the `AnalysisUsage 802<http://llvm.org/doxygen/classllvm_1_1AnalysisUsage.html>`_ object with 803information about which passes are required and not invalidated. To do this, a 804pass may call any of the following methods on the ``AnalysisUsage`` object: 805 806The ``AnalysisUsage::addRequired<>`` and ``AnalysisUsage::addRequiredTransitive<>`` methods 807^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 808 809If your pass requires a previous pass to be executed (an analysis for example), 810it can use one of these methods to arrange for it to be run before your pass. 811LLVM has many different types of analyses and passes that can be required, 812spanning the range from ``DominatorSet`` to ``BreakCriticalEdges``. Requiring 813``BreakCriticalEdges``, for example, guarantees that there will be no critical 814edges in the CFG when your pass has been run. 815 816Some analyses chain to other analyses to do their job. For example, an 817`AliasAnalysis <AliasAnalysis>` implementation is required to :ref:`chain 818<aliasanalysis-chaining>` to other alias analysis passes. In cases where 819analyses chain, the ``addRequiredTransitive`` method should be used instead of 820the ``addRequired`` method. This informs the ``PassManager`` that the 821transitively required pass should be alive as long as the requiring pass is. 822 823The ``AnalysisUsage::addPreserved<>`` method 824^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 825 826One of the jobs of the ``PassManager`` is to optimize how and when analyses are 827run. In particular, it attempts to avoid recomputing data unless it needs to. 828For this reason, passes are allowed to declare that they preserve (i.e., they 829don't invalidate) an existing analysis if it's available. For example, a 830simple constant folding pass would not modify the CFG, so it can't possibly 831affect the results of dominator analysis. By default, all passes are assumed 832to invalidate all others. 833 834The ``AnalysisUsage`` class provides several methods which are useful in 835certain circumstances that are related to ``addPreserved``. In particular, the 836``setPreservesAll`` method can be called to indicate that the pass does not 837modify the LLVM program at all (which is true for analyses), and the 838``setPreservesCFG`` method can be used by transformations that change 839instructions in the program but do not modify the CFG or terminator 840instructions (note that this property is implicitly set for 841:ref:`BasicBlockPass <writing-an-llvm-pass-BasicBlockPass>`\ es). 842 843``addPreserved`` is particularly useful for transformations like 844``BreakCriticalEdges``. This pass knows how to update a small set of loop and 845dominator related analyses if they exist, so it can preserve them, despite the 846fact that it hacks on the CFG. 847 848Example implementations of ``getAnalysisUsage`` 849^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 850 851.. code-block:: c++ 852 853 // This example modifies the program, but does not modify the CFG 854 void LICM::getAnalysisUsage(AnalysisUsage &AU) const { 855 AU.setPreservesCFG(); 856 AU.addRequired<LoopInfo>(); 857 } 858 859.. _writing-an-llvm-pass-getAnalysis: 860 861The ``getAnalysis<>`` and ``getAnalysisIfAvailable<>`` methods 862^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 863 864The ``Pass::getAnalysis<>`` method is automatically inherited by your class, 865providing you with access to the passes that you declared that you required 866with the :ref:`getAnalysisUsage <writing-an-llvm-pass-getAnalysisUsage>` 867method. It takes a single template argument that specifies which pass class 868you want, and returns a reference to that pass. For example: 869 870.. code-block:: c++ 871 872 bool LICM::runOnFunction(Function &F) { 873 LoopInfo &LI = getAnalysis<LoopInfo>(); 874 //... 875 } 876 877This method call returns a reference to the pass desired. You may get a 878runtime assertion failure if you attempt to get an analysis that you did not 879declare as required in your :ref:`getAnalysisUsage 880<writing-an-llvm-pass-getAnalysisUsage>` implementation. This method can be 881called by your ``run*`` method implementation, or by any other local method 882invoked by your ``run*`` method. 883 884A module level pass can use function level analysis info using this interface. 885For example: 886 887.. code-block:: c++ 888 889 bool ModuleLevelPass::runOnModule(Module &M) { 890 //... 891 DominatorTree &DT = getAnalysis<DominatorTree>(Func); 892 //... 893 } 894 895In above example, ``runOnFunction`` for ``DominatorTree`` is called by pass 896manager before returning a reference to the desired pass. 897 898If your pass is capable of updating analyses if they exist (e.g., 899``BreakCriticalEdges``, as described above), you can use the 900``getAnalysisIfAvailable`` method, which returns a pointer to the analysis if 901it is active. For example: 902 903.. code-block:: c++ 904 905 if (DominatorSet *DS = getAnalysisIfAvailable<DominatorSet>()) { 906 // A DominatorSet is active. This code will update it. 907 } 908 909Implementing Analysis Groups 910---------------------------- 911 912Now that we understand the basics of how passes are defined, how they are used, 913and how they are required from other passes, it's time to get a little bit 914fancier. All of the pass relationships that we have seen so far are very 915simple: one pass depends on one other specific pass to be run before it can 916run. For many applications, this is great, for others, more flexibility is 917required. 918 919In particular, some analyses are defined such that there is a single simple 920interface to the analysis results, but multiple ways of calculating them. 921Consider alias analysis for example. The most trivial alias analysis returns 922"may alias" for any alias query. The most sophisticated analysis a 923flow-sensitive, context-sensitive interprocedural analysis that can take a 924significant amount of time to execute (and obviously, there is a lot of room 925between these two extremes for other implementations). To cleanly support 926situations like this, the LLVM Pass Infrastructure supports the notion of 927Analysis Groups. 928 929Analysis Group Concepts 930^^^^^^^^^^^^^^^^^^^^^^^ 931 932An Analysis Group is a single simple interface that may be implemented by 933multiple different passes. Analysis Groups can be given human readable names 934just like passes, but unlike passes, they need not derive from the ``Pass`` 935class. An analysis group may have one or more implementations, one of which is 936the "default" implementation. 937 938Analysis groups are used by client passes just like other passes are: the 939``AnalysisUsage::addRequired()`` and ``Pass::getAnalysis()`` methods. In order 940to resolve this requirement, the :ref:`PassManager 941<writing-an-llvm-pass-passmanager>` scans the available passes to see if any 942implementations of the analysis group are available. If none is available, the 943default implementation is created for the pass to use. All standard rules for 944:ref:`interaction between passes <writing-an-llvm-pass-interaction>` still 945apply. 946 947Although :ref:`Pass Registration <writing-an-llvm-pass-registration>` is 948optional for normal passes, all analysis group implementations must be 949registered, and must use the :ref:`INITIALIZE_AG_PASS 950<writing-an-llvm-pass-RegisterAnalysisGroup>` template to join the 951implementation pool. Also, a default implementation of the interface **must** 952be registered with :ref:`RegisterAnalysisGroup 953<writing-an-llvm-pass-RegisterAnalysisGroup>`. 954 955As a concrete example of an Analysis Group in action, consider the 956`AliasAnalysis <http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html>`_ 957analysis group. The default implementation of the alias analysis interface 958(the `basicaa <http://llvm.org/doxygen/structBasicAliasAnalysis.html>`_ pass) 959just does a few simple checks that don't require significant analysis to 960compute (such as: two different globals can never alias each other, etc). 961Passes that use the `AliasAnalysis 962<http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html>`_ interface (for 963example the `gcse <http://llvm.org/doxygen/structGCSE.html>`_ pass), do not 964care which implementation of alias analysis is actually provided, they just use 965the designated interface. 966 967From the user's perspective, commands work just like normal. Issuing the 968command ``opt -gcse ...`` will cause the ``basicaa`` class to be instantiated 969and added to the pass sequence. Issuing the command ``opt -somefancyaa -gcse 970...`` will cause the ``gcse`` pass to use the ``somefancyaa`` alias analysis 971(which doesn't actually exist, it's just a hypothetical example) instead. 972 973.. _writing-an-llvm-pass-RegisterAnalysisGroup: 974 975Using ``RegisterAnalysisGroup`` 976^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 977 978The ``RegisterAnalysisGroup`` template is used to register the analysis group 979itself, while the ``INITIALIZE_AG_PASS`` is used to add pass implementations to 980the analysis group. First, an analysis group should be registered, with a 981human readable name provided for it. Unlike registration of passes, there is 982no command line argument to be specified for the Analysis Group Interface 983itself, because it is "abstract": 984 985.. code-block:: c++ 986 987 static RegisterAnalysisGroup<AliasAnalysis> A("Alias Analysis"); 988 989Once the analysis is registered, passes can declare that they are valid 990implementations of the interface by using the following code: 991 992.. code-block:: c++ 993 994 namespace { 995 // Declare that we implement the AliasAnalysis interface 996 INITIALIZE_AG_PASS(FancyAA, AliasAnalysis , "somefancyaa", 997 "A more complex alias analysis implementation", 998 false, // Is CFG Only? 999 true, // Is Analysis? 1000 false); // Is default Analysis Group implementation? 1001 } 1002 1003This just shows a class ``FancyAA`` that uses the ``INITIALIZE_AG_PASS`` macro 1004both to register and to "join" the `AliasAnalysis 1005<http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html>`_ analysis group. 1006Every implementation of an analysis group should join using this macro. 1007 1008.. code-block:: c++ 1009 1010 namespace { 1011 // Declare that we implement the AliasAnalysis interface 1012 INITIALIZE_AG_PASS(BasicAA, AliasAnalysis, "basicaa", 1013 "Basic Alias Analysis (default AA impl)", 1014 false, // Is CFG Only? 1015 true, // Is Analysis? 1016 true); // Is default Analysis Group implementation? 1017 } 1018 1019Here we show how the default implementation is specified (using the final 1020argument to the ``INITIALIZE_AG_PASS`` template). There must be exactly one 1021default implementation available at all times for an Analysis Group to be used. 1022Only default implementation can derive from ``ImmutablePass``. Here we declare 1023that the `BasicAliasAnalysis 1024<http://llvm.org/doxygen/structBasicAliasAnalysis.html>`_ pass is the default 1025implementation for the interface. 1026 1027Pass Statistics 1028=============== 1029 1030The `Statistic <http://llvm.org/doxygen/Statistic_8h-source.html>`_ class is 1031designed to be an easy way to expose various success metrics from passes. 1032These statistics are printed at the end of a run, when the :option:`-stats` 1033command line option is enabled on the command line. See the :ref:`Statistics 1034section <Statistic>` in the Programmer's Manual for details. 1035 1036.. _writing-an-llvm-pass-passmanager: 1037 1038What PassManager does 1039--------------------- 1040 1041The `PassManager <http://llvm.org/doxygen/PassManager_8h-source.html>`_ `class 1042<http://llvm.org/doxygen/classllvm_1_1PassManager.html>`_ takes a list of 1043passes, ensures their :ref:`prerequisites <writing-an-llvm-pass-interaction>` 1044are set up correctly, and then schedules passes to run efficiently. All of the 1045LLVM tools that run passes use the PassManager for execution of these passes. 1046 1047The PassManager does two main things to try to reduce the execution time of a 1048series of passes: 1049 1050#. **Share analysis results.** The ``PassManager`` attempts to avoid 1051 recomputing analysis results as much as possible. This means keeping track 1052 of which analyses are available already, which analyses get invalidated, and 1053 which analyses are needed to be run for a pass. An important part of work 1054 is that the ``PassManager`` tracks the exact lifetime of all analysis 1055 results, allowing it to :ref:`free memory 1056 <writing-an-llvm-pass-releaseMemory>` allocated to holding analysis results 1057 as soon as they are no longer needed. 1058 1059#. **Pipeline the execution of passes on the program.** The ``PassManager`` 1060 attempts to get better cache and memory usage behavior out of a series of 1061 passes by pipelining the passes together. This means that, given a series 1062 of consecutive :ref:`FunctionPass <writing-an-llvm-pass-FunctionPass>`, it 1063 will execute all of the :ref:`FunctionPass 1064 <writing-an-llvm-pass-FunctionPass>` on the first function, then all of the 1065 :ref:`FunctionPasses <writing-an-llvm-pass-FunctionPass>` on the second 1066 function, etc... until the entire program has been run through the passes. 1067 1068 This improves the cache behavior of the compiler, because it is only 1069 touching the LLVM program representation for a single function at a time, 1070 instead of traversing the entire program. It reduces the memory consumption 1071 of compiler, because, for example, only one `DominatorSet 1072 <http://llvm.org/doxygen/classllvm_1_1DominatorSet.html>`_ needs to be 1073 calculated at a time. This also makes it possible to implement some 1074 :ref:`interesting enhancements <writing-an-llvm-pass-SMP>` in the future. 1075 1076The effectiveness of the ``PassManager`` is influenced directly by how much 1077information it has about the behaviors of the passes it is scheduling. For 1078example, the "preserved" set is intentionally conservative in the face of an 1079unimplemented :ref:`getAnalysisUsage <writing-an-llvm-pass-getAnalysisUsage>` 1080method. Not implementing when it should be implemented will have the effect of 1081not allowing any analysis results to live across the execution of your pass. 1082 1083The ``PassManager`` class exposes a ``--debug-pass`` command line options that 1084is useful for debugging pass execution, seeing how things work, and diagnosing 1085when you should be preserving more analyses than you currently are. (To get 1086information about all of the variants of the ``--debug-pass`` option, just type 1087"``opt -help-hidden``"). 1088 1089By using the --debug-pass=Structure option, for example, we can see how our 1090:ref:`Hello World <writing-an-llvm-pass-basiccode>` pass interacts with other 1091passes. Lets try it out with the gcse and licm passes: 1092 1093.. code-block:: console 1094 1095 $ opt -load ../../../Debug+Asserts/lib/Hello.so -gcse -licm --debug-pass=Structure < hello.bc > /dev/null 1096 Module Pass Manager 1097 Function Pass Manager 1098 Dominator Set Construction 1099 Immediate Dominators Construction 1100 Global Common Subexpression Elimination 1101 -- Immediate Dominators Construction 1102 -- Global Common Subexpression Elimination 1103 Natural Loop Construction 1104 Loop Invariant Code Motion 1105 -- Natural Loop Construction 1106 -- Loop Invariant Code Motion 1107 Module Verifier 1108 -- Dominator Set Construction 1109 -- Module Verifier 1110 Bitcode Writer 1111 --Bitcode Writer 1112 1113This output shows us when passes are constructed and when the analysis results 1114are known to be dead (prefixed with "``--``"). Here we see that GCSE uses 1115dominator and immediate dominator information to do its job. The LICM pass 1116uses natural loop information, which uses dominator sets, but not immediate 1117dominators. Because immediate dominators are no longer useful after the GCSE 1118pass, it is immediately destroyed. The dominator sets are then reused to 1119compute natural loop information, which is then used by the LICM pass. 1120 1121After the LICM pass, the module verifier runs (which is automatically added by 1122the :program:`opt` tool), which uses the dominator set to check that the 1123resultant LLVM code is well formed. After it finishes, the dominator set 1124information is destroyed, after being computed once, and shared by three 1125passes. 1126 1127Lets see how this changes when we run the :ref:`Hello World 1128<writing-an-llvm-pass-basiccode>` pass in between the two passes: 1129 1130.. code-block:: console 1131 1132 $ opt -load ../../../Debug+Asserts/lib/Hello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null 1133 Module Pass Manager 1134 Function Pass Manager 1135 Dominator Set Construction 1136 Immediate Dominators Construction 1137 Global Common Subexpression Elimination 1138 -- Dominator Set Construction 1139 -- Immediate Dominators Construction 1140 -- Global Common Subexpression Elimination 1141 Hello World Pass 1142 -- Hello World Pass 1143 Dominator Set Construction 1144 Natural Loop Construction 1145 Loop Invariant Code Motion 1146 -- Natural Loop Construction 1147 -- Loop Invariant Code Motion 1148 Module Verifier 1149 -- Dominator Set Construction 1150 -- Module Verifier 1151 Bitcode Writer 1152 --Bitcode Writer 1153 Hello: __main 1154 Hello: puts 1155 Hello: main 1156 1157Here we see that the :ref:`Hello World <writing-an-llvm-pass-basiccode>` pass 1158has killed the Dominator Set pass, even though it doesn't modify the code at 1159all! To fix this, we need to add the following :ref:`getAnalysisUsage 1160<writing-an-llvm-pass-getAnalysisUsage>` method to our pass: 1161 1162.. code-block:: c++ 1163 1164 // We don't modify the program, so we preserve all analyses 1165 void getAnalysisUsage(AnalysisUsage &AU) const override { 1166 AU.setPreservesAll(); 1167 } 1168 1169Now when we run our pass, we get this output: 1170 1171.. code-block:: console 1172 1173 $ opt -load ../../../Debug+Asserts/lib/Hello.so -gcse -hello -licm --debug-pass=Structure < hello.bc > /dev/null 1174 Pass Arguments: -gcse -hello -licm 1175 Module Pass Manager 1176 Function Pass Manager 1177 Dominator Set Construction 1178 Immediate Dominators Construction 1179 Global Common Subexpression Elimination 1180 -- Immediate Dominators Construction 1181 -- Global Common Subexpression Elimination 1182 Hello World Pass 1183 -- Hello World Pass 1184 Natural Loop Construction 1185 Loop Invariant Code Motion 1186 -- Loop Invariant Code Motion 1187 -- Natural Loop Construction 1188 Module Verifier 1189 -- Dominator Set Construction 1190 -- Module Verifier 1191 Bitcode Writer 1192 --Bitcode Writer 1193 Hello: __main 1194 Hello: puts 1195 Hello: main 1196 1197Which shows that we don't accidentally invalidate dominator information 1198anymore, and therefore do not have to compute it twice. 1199 1200.. _writing-an-llvm-pass-releaseMemory: 1201 1202The ``releaseMemory`` method 1203^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1204 1205.. code-block:: c++ 1206 1207 virtual void releaseMemory(); 1208 1209The ``PassManager`` automatically determines when to compute analysis results, 1210and how long to keep them around for. Because the lifetime of the pass object 1211itself is effectively the entire duration of the compilation process, we need 1212some way to free analysis results when they are no longer useful. The 1213``releaseMemory`` virtual method is the way to do this. 1214 1215If you are writing an analysis or any other pass that retains a significant 1216amount of state (for use by another pass which "requires" your pass and uses 1217the :ref:`getAnalysis <writing-an-llvm-pass-getAnalysis>` method) you should 1218implement ``releaseMemory`` to, well, release the memory allocated to maintain 1219this internal state. This method is called after the ``run*`` method for the 1220class, before the next call of ``run*`` in your pass. 1221 1222Registering dynamically loaded passes 1223===================================== 1224 1225*Size matters* when constructing production quality tools using LLVM, both for 1226the purposes of distribution, and for regulating the resident code size when 1227running on the target system. Therefore, it becomes desirable to selectively 1228use some passes, while omitting others and maintain the flexibility to change 1229configurations later on. You want to be able to do all this, and, provide 1230feedback to the user. This is where pass registration comes into play. 1231 1232The fundamental mechanisms for pass registration are the 1233``MachinePassRegistry`` class and subclasses of ``MachinePassRegistryNode``. 1234 1235An instance of ``MachinePassRegistry`` is used to maintain a list of 1236``MachinePassRegistryNode`` objects. This instance maintains the list and 1237communicates additions and deletions to the command line interface. 1238 1239An instance of ``MachinePassRegistryNode`` subclass is used to maintain 1240information provided about a particular pass. This information includes the 1241command line name, the command help string and the address of the function used 1242to create an instance of the pass. A global static constructor of one of these 1243instances *registers* with a corresponding ``MachinePassRegistry``, the static 1244destructor *unregisters*. Thus a pass that is statically linked in the tool 1245will be registered at start up. A dynamically loaded pass will register on 1246load and unregister at unload. 1247 1248Using existing registries 1249------------------------- 1250 1251There are predefined registries to track instruction scheduling 1252(``RegisterScheduler``) and register allocation (``RegisterRegAlloc``) machine 1253passes. Here we will describe how to *register* a register allocator machine 1254pass. 1255 1256Implement your register allocator machine pass. In your register allocator 1257``.cpp`` file add the following include: 1258 1259.. code-block:: c++ 1260 1261 #include "llvm/CodeGen/RegAllocRegistry.h" 1262 1263Also in your register allocator ``.cpp`` file, define a creator function in the 1264form: 1265 1266.. code-block:: c++ 1267 1268 FunctionPass *createMyRegisterAllocator() { 1269 return new MyRegisterAllocator(); 1270 } 1271 1272Note that the signature of this function should match the type of 1273``RegisterRegAlloc::FunctionPassCtor``. In the same file add the "installing" 1274declaration, in the form: 1275 1276.. code-block:: c++ 1277 1278 static RegisterRegAlloc myRegAlloc("myregalloc", 1279 "my register allocator help string", 1280 createMyRegisterAllocator); 1281 1282Note the two spaces prior to the help string produces a tidy result on the 1283:option:`-help` query. 1284 1285.. code-block:: console 1286 1287 $ llc -help 1288 ... 1289 -regalloc - Register allocator to use (default=linearscan) 1290 =linearscan - linear scan register allocator 1291 =local - local register allocator 1292 =simple - simple register allocator 1293 =myregalloc - my register allocator help string 1294 ... 1295 1296And that's it. The user is now free to use ``-regalloc=myregalloc`` as an 1297option. Registering instruction schedulers is similar except use the 1298``RegisterScheduler`` class. Note that the 1299``RegisterScheduler::FunctionPassCtor`` is significantly different from 1300``RegisterRegAlloc::FunctionPassCtor``. 1301 1302To force the load/linking of your register allocator into the 1303:program:`llc`/:program:`lli` tools, add your creator function's global 1304declaration to ``Passes.h`` and add a "pseudo" call line to 1305``llvm/Codegen/LinkAllCodegenComponents.h``. 1306 1307Creating new registries 1308----------------------- 1309 1310The easiest way to get started is to clone one of the existing registries; we 1311recommend ``llvm/CodeGen/RegAllocRegistry.h``. The key things to modify are 1312the class name and the ``FunctionPassCtor`` type. 1313 1314Then you need to declare the registry. Example: if your pass registry is 1315``RegisterMyPasses`` then define: 1316 1317.. code-block:: c++ 1318 1319 MachinePassRegistry RegisterMyPasses::Registry; 1320 1321And finally, declare the command line option for your passes. Example: 1322 1323.. code-block:: c++ 1324 1325 cl::opt<RegisterMyPasses::FunctionPassCtor, false, 1326 RegisterPassParser<RegisterMyPasses> > 1327 MyPassOpt("mypass", 1328 cl::init(&createDefaultMyPass), 1329 cl::desc("my pass option help")); 1330 1331Here the command option is "``mypass``", with ``createDefaultMyPass`` as the 1332default creator. 1333 1334Using GDB with dynamically loaded passes 1335---------------------------------------- 1336 1337Unfortunately, using GDB with dynamically loaded passes is not as easy as it 1338should be. First of all, you can't set a breakpoint in a shared object that 1339has not been loaded yet, and second of all there are problems with inlined 1340functions in shared objects. Here are some suggestions to debugging your pass 1341with GDB. 1342 1343For sake of discussion, I'm going to assume that you are debugging a 1344transformation invoked by :program:`opt`, although nothing described here 1345depends on that. 1346 1347Setting a breakpoint in your pass 1348^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1349 1350First thing you do is start gdb on the opt process: 1351 1352.. code-block:: console 1353 1354 $ gdb opt 1355 GNU gdb 5.0 1356 Copyright 2000 Free Software Foundation, Inc. 1357 GDB is free software, covered by the GNU General Public License, and you are 1358 welcome to change it and/or distribute copies of it under certain conditions. 1359 Type "show copying" to see the conditions. 1360 There is absolutely no warranty for GDB. Type "show warranty" for details. 1361 This GDB was configured as "sparc-sun-solaris2.6"... 1362 (gdb) 1363 1364Note that :program:`opt` has a lot of debugging information in it, so it takes 1365time to load. Be patient. Since we cannot set a breakpoint in our pass yet 1366(the shared object isn't loaded until runtime), we must execute the process, 1367and have it stop before it invokes our pass, but after it has loaded the shared 1368object. The most foolproof way of doing this is to set a breakpoint in 1369``PassManager::run`` and then run the process with the arguments you want: 1370 1371.. code-block:: console 1372 1373 $ (gdb) break llvm::PassManager::run 1374 Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70. 1375 (gdb) run test.bc -load $(LLVMTOP)/llvm/Debug+Asserts/lib/[libname].so -[passoption] 1376 Starting program: opt test.bc -load $(LLVMTOP)/llvm/Debug+Asserts/lib/[libname].so -[passoption] 1377 Breakpoint 1, PassManager::run (this=0xffbef174, M=@0x70b298) at Pass.cpp:70 1378 70 bool PassManager::run(Module &M) { return PM->run(M); } 1379 (gdb) 1380 1381Once the :program:`opt` stops in the ``PassManager::run`` method you are now 1382free to set breakpoints in your pass so that you can trace through execution or 1383do other standard debugging stuff. 1384 1385Miscellaneous Problems 1386^^^^^^^^^^^^^^^^^^^^^^ 1387 1388Once you have the basics down, there are a couple of problems that GDB has, 1389some with solutions, some without. 1390 1391* Inline functions have bogus stack information. In general, GDB does a pretty 1392 good job getting stack traces and stepping through inline functions. When a 1393 pass is dynamically loaded however, it somehow completely loses this 1394 capability. The only solution I know of is to de-inline a function (move it 1395 from the body of a class to a ``.cpp`` file). 1396 1397* Restarting the program breaks breakpoints. After following the information 1398 above, you have succeeded in getting some breakpoints planted in your pass. 1399 Nex thing you know, you restart the program (i.e., you type "``run``" again), 1400 and you start getting errors about breakpoints being unsettable. The only 1401 way I have found to "fix" this problem is to delete the breakpoints that are 1402 already set in your pass, run the program, and re-set the breakpoints once 1403 execution stops in ``PassManager::run``. 1404 1405Hopefully these tips will help with common case debugging situations. If you'd 1406like to contribute some tips of your own, just contact `Chris 1407<mailto:sabre@nondot.org>`_. 1408 1409Future extensions planned 1410------------------------- 1411 1412Although the LLVM Pass Infrastructure is very capable as it stands, and does 1413some nifty stuff, there are things we'd like to add in the future. Here is 1414where we are going: 1415 1416.. _writing-an-llvm-pass-SMP: 1417 1418Multithreaded LLVM 1419^^^^^^^^^^^^^^^^^^ 1420 1421Multiple CPU machines are becoming more common and compilation can never be 1422fast enough: obviously we should allow for a multithreaded compiler. Because 1423of the semantics defined for passes above (specifically they cannot maintain 1424state across invocations of their ``run*`` methods), a nice clean way to 1425implement a multithreaded compiler would be for the ``PassManager`` class to 1426create multiple instances of each pass object, and allow the separate instances 1427to be hacking on different parts of the program at the same time. 1428 1429This implementation would prevent each of the passes from having to implement 1430multithreaded constructs, requiring only the LLVM core to have locking in a few 1431places (for global resources). Although this is a simple extension, we simply 1432haven't had time (or multiprocessor machines, thus a reason) to implement this. 1433Despite that, we have kept the LLVM passes SMP ready, and you should too. 1434 1435