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 50First, configure and build LLVM. Next, you need to create a new directory 51somewhere in the LLVM source base. For this example, we'll assume that you 52made ``lib/Transforms/Hello``. Finally, you must set up a build script 53that will compile the source code for the new pass. To do this, 54copy the following into ``CMakeLists.txt``: 55 56.. code-block:: cmake 57 58 add_llvm_loadable_module( LLVMHello 59 Hello.cpp 60 61 PLUGIN_TOOL 62 opt 63 ) 64 65and the following line into ``lib/Transforms/CMakeLists.txt``: 66 67.. code-block:: cmake 68 69 add_subdirectory(Hello) 70 71(Note that there is already a directory named ``Hello`` with a sample "Hello" 72pass; you may play with it -- in which case you don't need to modify any 73``CMakeLists.txt`` files -- or, if you want to create everything from scratch, 74use another name.) 75 76This build script specifies that ``Hello.cpp`` file in the current directory 77is to be compiled and linked into a shared object ``$(LEVEL)/lib/LLVMHello.so`` that 78can be dynamically loaded by the :program:`opt` tool via its :option:`-load` 79option. If your operating system uses a suffix other than ``.so`` (such as 80Windows or Mac OS X), the appropriate extension will be used. 81 82Now that we have the build scripts set up, we just need to write the code for 83the pass itself. 84 85.. _writing-an-llvm-pass-basiccode: 86 87Basic code required 88------------------- 89 90Now that we have a way to compile our new pass, we just have to write it. 91Start out with: 92 93.. code-block:: c++ 94 95 #include "llvm/Pass.h" 96 #include "llvm/IR/Function.h" 97 #include "llvm/Support/raw_ostream.h" 98 99Which are needed because we are writing a `Pass 100<http://llvm.org/doxygen/classllvm_1_1Pass.html>`_, we are operating on 101`Function <http://llvm.org/doxygen/classllvm_1_1Function.html>`_\ s, and we will 102be doing some printing. 103 104Next we have: 105 106.. code-block:: c++ 107 108 using namespace llvm; 109 110... which is required because the functions from the include files live in the 111llvm namespace. 112 113Next we have: 114 115.. code-block:: c++ 116 117 namespace { 118 119... which starts out an anonymous namespace. Anonymous namespaces are to C++ 120what the "``static``" keyword is to C (at global scope). It makes the things 121declared inside of the anonymous namespace visible only to the current file. 122If you're not familiar with them, consult a decent C++ book for more 123information. 124 125Next, we declare our pass itself: 126 127.. code-block:: c++ 128 129 struct Hello : public FunctionPass { 130 131This declares a "``Hello``" class that is a subclass of :ref:`FunctionPass 132<writing-an-llvm-pass-FunctionPass>`. The different builtin pass subclasses 133are described in detail :ref:`later <writing-an-llvm-pass-pass-classes>`, but 134for now, know that ``FunctionPass`` operates on a function at a time. 135 136.. code-block:: c++ 137 138 static char ID; 139 Hello() : FunctionPass(ID) {} 140 141This declares pass identifier used by LLVM to identify pass. This allows LLVM 142to avoid using expensive C++ runtime information. 143 144.. code-block:: c++ 145 146 bool runOnFunction(Function &F) override { 147 errs() << "Hello: "; 148 errs().write_escaped(F.getName()) << '\n'; 149 return false; 150 } 151 }; // end of struct Hello 152 } // end of anonymous namespace 153 154We declare a :ref:`runOnFunction <writing-an-llvm-pass-runOnFunction>` method, 155which overrides an abstract virtual method inherited from :ref:`FunctionPass 156<writing-an-llvm-pass-FunctionPass>`. This is where we are supposed to do our 157thing, so we just print out our message with the name of each function. 158 159.. code-block:: c++ 160 161 char Hello::ID = 0; 162 163We initialize pass ID here. LLVM uses ID's address to identify a pass, so 164initialization value is not important. 165 166.. code-block:: c++ 167 168 static RegisterPass<Hello> X("hello", "Hello World Pass", 169 false /* Only looks at CFG */, 170 false /* Analysis Pass */); 171 172Lastly, we :ref:`register our class <writing-an-llvm-pass-registration>` 173``Hello``, giving it a command line argument "``hello``", and a name "Hello 174World Pass". The last two arguments describe its behavior: if a pass walks CFG 175without modifying it then the third argument is set to ``true``; if a pass is 176an analysis pass, for example dominator tree pass, then ``true`` is supplied as 177the fourth argument. 178 179As a whole, the ``.cpp`` file looks like: 180 181.. code-block:: c++ 182 183 #include "llvm/Pass.h" 184 #include "llvm/IR/Function.h" 185 #include "llvm/Support/raw_ostream.h" 186 187 using namespace llvm; 188 189 namespace { 190 struct Hello : public FunctionPass { 191 static char ID; 192 Hello() : FunctionPass(ID) {} 193 194 bool runOnFunction(Function &F) override { 195 errs() << "Hello: "; 196 errs().write_escaped(F.getName()) << '\n'; 197 return false; 198 } 199 }; // end of struct Hello 200 } // end of anonymous namespace 201 202 char Hello::ID = 0; 203 static RegisterPass<Hello> X("hello", "Hello World Pass", 204 false /* Only looks at CFG */, 205 false /* Analysis Pass */); 206 207Now that it's all together, compile the file with a simple "``gmake``" command 208from the top level of your build directory and you should get a new file 209"``lib/LLVMHello.so``". Note that everything in this file is 210contained in an anonymous namespace --- this reflects the fact that passes 211are self contained units that do not need external interfaces (although they 212can have them) to be useful. 213 214Running a pass with ``opt`` 215--------------------------- 216 217Now that you have a brand new shiny shared object file, we can use the 218:program:`opt` command to run an LLVM program through your pass. Because you 219registered your pass with ``RegisterPass``, you will be able to use the 220:program:`opt` tool to access it, once loaded. 221 222To test it, follow the example at the end of the :doc:`GettingStarted` to 223compile "Hello World" to LLVM. We can now run the bitcode file (hello.bc) for 224the program through our transformation like this (or course, any bitcode file 225will work): 226 227.. code-block:: console 228 229 $ opt -load lib/LLVMHello.so -hello < hello.bc > /dev/null 230 Hello: __main 231 Hello: puts 232 Hello: main 233 234The :option:`-load` option specifies that :program:`opt` should load your pass 235as a shared object, which makes "``-hello``" a valid command line argument 236(which is one reason you need to :ref:`register your pass 237<writing-an-llvm-pass-registration>`). Because the Hello pass does not modify 238the program in any interesting way, we just throw away the result of 239:program:`opt` (sending it to ``/dev/null``). 240 241To see what happened to the other string you registered, try running 242:program:`opt` with the :option:`-help` option: 243 244.. code-block:: console 245 246 $ opt -load lib/LLVMHello.so -help 247 OVERVIEW: llvm .bc -> .bc modular optimizer and analysis printer 248 249 USAGE: opt [subcommand] [options] <input bitcode file> 250 251 OPTIONS: 252 Optimizations available: 253 ... 254 -guard-widening - Widen guards 255 -gvn - Global Value Numbering 256 -gvn-hoist - Early GVN Hoisting of Expressions 257 -hello - Hello World Pass 258 -indvars - Induction Variable Simplification 259 -inferattrs - Infer set function attributes 260 ... 261 262The pass name gets added as the information string for your pass, giving some 263documentation to users of :program:`opt`. Now that you have a working pass, 264you would go ahead and make it do the cool transformations you want. Once you 265get it all working and tested, it may become useful to find out how fast your 266pass is. The :ref:`PassManager <writing-an-llvm-pass-passmanager>` provides a 267nice command line option (:option:`--time-passes`) that allows you to get 268information about the execution time of your pass along with the other passes 269you queue up. For example: 270 271.. code-block:: console 272 273 $ opt -load lib/LLVMHello.so -hello -time-passes < hello.bc > /dev/null 274 Hello: __main 275 Hello: puts 276 Hello: main 277 ===-------------------------------------------------------------------------=== 278 ... Pass execution timing report ... 279 ===-------------------------------------------------------------------------=== 280 Total Execution Time: 0.0007 seconds (0.0005 wall clock) 281 282 ---User Time--- --User+System-- ---Wall Time--- --- Name --- 283 0.0004 ( 55.3%) 0.0004 ( 55.3%) 0.0004 ( 75.7%) Bitcode Writer 284 0.0003 ( 44.7%) 0.0003 ( 44.7%) 0.0001 ( 13.6%) Hello World Pass 285 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0001 ( 10.7%) Module Verifier 286 0.0007 (100.0%) 0.0007 (100.0%) 0.0005 (100.0%) Total 287 288As you can see, our implementation above is pretty fast. The additional 289passes listed are automatically inserted by the :program:`opt` tool to verify 290that the LLVM emitted by your pass is still valid and well formed LLVM, which 291hasn't been broken somehow. 292 293Now that you have seen the basics of the mechanics behind passes, we can talk 294about some more details of how they work and how to use them. 295 296.. _writing-an-llvm-pass-pass-classes: 297 298Pass classes and requirements 299============================= 300 301One of the first things that you should do when designing a new pass is to 302decide what class you should subclass for your pass. The :ref:`Hello World 303<writing-an-llvm-pass-basiccode>` example uses the :ref:`FunctionPass 304<writing-an-llvm-pass-FunctionPass>` class for its implementation, but we did 305not discuss why or when this should occur. Here we talk about the classes 306available, from the most general to the most specific. 307 308When choosing a superclass for your ``Pass``, you should choose the **most 309specific** class possible, while still being able to meet the requirements 310listed. This gives the LLVM Pass Infrastructure information necessary to 311optimize how passes are run, so that the resultant compiler isn't unnecessarily 312slow. 313 314The ``ImmutablePass`` class 315--------------------------- 316 317The most plain and boring type of pass is the "`ImmutablePass 318<http://llvm.org/doxygen/classllvm_1_1ImmutablePass.html>`_" class. This pass 319type is used for passes that do not have to be run, do not change state, and 320never need to be updated. This is not a normal type of transformation or 321analysis, but can provide information about the current compiler configuration. 322 323Although this pass class is very infrequently used, it is important for 324providing information about the current target machine being compiled for, and 325other static information that can affect the various transformations. 326 327``ImmutablePass``\ es never invalidate other transformations, are never 328invalidated, and are never "run". 329 330.. _writing-an-llvm-pass-ModulePass: 331 332The ``ModulePass`` class 333------------------------ 334 335The `ModulePass <http://llvm.org/doxygen/classllvm_1_1ModulePass.html>`_ class 336is the most general of all superclasses that you can use. Deriving from 337``ModulePass`` indicates that your pass uses the entire program as a unit, 338referring to function bodies in no predictable order, or adding and removing 339functions. Because nothing is known about the behavior of ``ModulePass`` 340subclasses, no optimization can be done for their execution. 341 342A module pass can use function level passes (e.g. dominators) using the 343``getAnalysis`` interface ``getAnalysis<DominatorTree>(llvm::Function *)`` to 344provide the function to retrieve analysis result for, if the function pass does 345not require any module or immutable passes. Note that this can only be done 346for functions for which the analysis ran, e.g. in the case of dominators you 347should only ask for the ``DominatorTree`` for function definitions, not 348declarations. 349 350To write a correct ``ModulePass`` subclass, derive from ``ModulePass`` and 351overload the ``runOnModule`` method with the following signature: 352 353The ``runOnModule`` method 354^^^^^^^^^^^^^^^^^^^^^^^^^^ 355 356.. code-block:: c++ 357 358 virtual bool runOnModule(Module &M) = 0; 359 360The ``runOnModule`` method performs the interesting work of the pass. It 361should return ``true`` if the module was modified by the transformation and 362``false`` otherwise. 363 364.. _writing-an-llvm-pass-CallGraphSCCPass: 365 366The ``CallGraphSCCPass`` class 367------------------------------ 368 369The `CallGraphSCCPass 370<http://llvm.org/doxygen/classllvm_1_1CallGraphSCCPass.html>`_ is used by 371passes that need to traverse the program bottom-up on the call graph (callees 372before callers). Deriving from ``CallGraphSCCPass`` provides some mechanics 373for building and traversing the ``CallGraph``, but also allows the system to 374optimize execution of ``CallGraphSCCPass``\ es. If your pass meets the 375requirements outlined below, and doesn't meet the requirements of a 376:ref:`FunctionPass <writing-an-llvm-pass-FunctionPass>` or :ref:`BasicBlockPass 377<writing-an-llvm-pass-BasicBlockPass>`, you should derive from 378``CallGraphSCCPass``. 379 380``TODO``: explain briefly what SCC, Tarjan's algo, and B-U mean. 381 382To be explicit, CallGraphSCCPass subclasses are: 383 384#. ... *not allowed* to inspect or modify any ``Function``\ s other than those 385 in the current SCC and the direct callers and direct callees of the SCC. 386#. ... *required* to preserve the current ``CallGraph`` object, updating it to 387 reflect any changes made to the program. 388#. ... *not allowed* to add or remove SCC's from the current Module, though 389 they may change the contents of an SCC. 390#. ... *allowed* to add or remove global variables from the current Module. 391#. ... *allowed* to maintain state across invocations of :ref:`runOnSCC 392 <writing-an-llvm-pass-runOnSCC>` (including global data). 393 394Implementing a ``CallGraphSCCPass`` is slightly tricky in some cases because it 395has to handle SCCs with more than one node in it. All of the virtual methods 396described below should return ``true`` if they modified the program, or 397``false`` if they didn't. 398 399The ``doInitialization(CallGraph &)`` method 400^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 401 402.. code-block:: c++ 403 404 virtual bool doInitialization(CallGraph &CG); 405 406The ``doInitialization`` method is allowed to do most of the things that 407``CallGraphSCCPass``\ es are not allowed to do. They can add and remove 408functions, get pointers to functions, etc. The ``doInitialization`` method is 409designed to do simple initialization type of stuff that does not depend on the 410SCCs being processed. The ``doInitialization`` method call is not scheduled to 411overlap with any other pass executions (thus it should be very fast). 412 413.. _writing-an-llvm-pass-runOnSCC: 414 415The ``runOnSCC`` method 416^^^^^^^^^^^^^^^^^^^^^^^ 417 418.. code-block:: c++ 419 420 virtual bool runOnSCC(CallGraphSCC &SCC) = 0; 421 422The ``runOnSCC`` method performs the interesting work of the pass, and should 423return ``true`` if the module was modified by the transformation, ``false`` 424otherwise. 425 426The ``doFinalization(CallGraph &)`` method 427^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 428 429.. code-block:: c++ 430 431 virtual bool doFinalization(CallGraph &CG); 432 433The ``doFinalization`` method is an infrequently used method that is called 434when the pass framework has finished calling :ref:`runOnSCC 435<writing-an-llvm-pass-runOnSCC>` for every SCC in the program being compiled. 436 437.. _writing-an-llvm-pass-FunctionPass: 438 439The ``FunctionPass`` class 440-------------------------- 441 442In contrast to ``ModulePass`` subclasses, `FunctionPass 443<http://llvm.org/doxygen/classllvm_1_1Pass.html>`_ subclasses do have a 444predictable, local behavior that can be expected by the system. All 445``FunctionPass`` execute on each function in the program independent of all of 446the other functions in the program. ``FunctionPass``\ es do not require that 447they are executed in a particular order, and ``FunctionPass``\ es do not modify 448external functions. 449 450To be explicit, ``FunctionPass`` subclasses are not allowed to: 451 452#. Inspect or modify a ``Function`` other than the one currently being processed. 453#. Add or remove ``Function``\ s from the current ``Module``. 454#. Add or remove global variables from the current ``Module``. 455#. Maintain state across invocations of :ref:`runOnFunction 456 <writing-an-llvm-pass-runOnFunction>` (including global data). 457 458Implementing a ``FunctionPass`` is usually straightforward (See the :ref:`Hello 459World <writing-an-llvm-pass-basiccode>` pass for example). 460``FunctionPass``\ es may overload three virtual methods to do their work. All 461of these methods should return ``true`` if they modified the program, or 462``false`` if they didn't. 463 464.. _writing-an-llvm-pass-doInitialization-mod: 465 466The ``doInitialization(Module &)`` method 467^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 468 469.. code-block:: c++ 470 471 virtual bool doInitialization(Module &M); 472 473The ``doInitialization`` method is allowed to do most of the things that 474``FunctionPass``\ es are not allowed to do. They can add and remove functions, 475get pointers to functions, etc. The ``doInitialization`` method is designed to 476do simple initialization type of stuff that does not depend on the functions 477being processed. The ``doInitialization`` method call is not scheduled to 478overlap with any other pass executions (thus it should be very fast). 479 480A good example of how this method should be used is the `LowerAllocations 481<http://llvm.org/doxygen/LowerAllocations_8cpp-source.html>`_ pass. This pass 482converts ``malloc`` and ``free`` instructions into platform dependent 483``malloc()`` and ``free()`` function calls. It uses the ``doInitialization`` 484method to get a reference to the ``malloc`` and ``free`` functions that it 485needs, adding prototypes to the module if necessary. 486 487.. _writing-an-llvm-pass-runOnFunction: 488 489The ``runOnFunction`` method 490^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 491 492.. code-block:: c++ 493 494 virtual bool runOnFunction(Function &F) = 0; 495 496The ``runOnFunction`` method must be implemented by your subclass to do the 497transformation or analysis work of your pass. As usual, a ``true`` value 498should be returned if the function is modified. 499 500.. _writing-an-llvm-pass-doFinalization-mod: 501 502The ``doFinalization(Module &)`` method 503^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 504 505.. code-block:: c++ 506 507 virtual bool doFinalization(Module &M); 508 509The ``doFinalization`` method is an infrequently used method that is called 510when the pass framework has finished calling :ref:`runOnFunction 511<writing-an-llvm-pass-runOnFunction>` for every function in the program being 512compiled. 513 514.. _writing-an-llvm-pass-LoopPass: 515 516The ``LoopPass`` class 517---------------------- 518 519All ``LoopPass`` execute on each loop in the function independent of all of the 520other loops in the function. ``LoopPass`` processes loops in loop nest order 521such that outer most loop is processed last. 522 523``LoopPass`` subclasses are allowed to update loop nest using ``LPPassManager`` 524interface. Implementing a loop pass is usually straightforward. 525``LoopPass``\ es may overload three virtual methods to do their work. All 526these methods should return ``true`` if they modified the program, or ``false`` 527if they didn't. 528 529A ``LoopPass`` subclass which is intended to run as part of the main loop pass 530pipeline needs to preserve all of the same *function* analyses that the other 531loop passes in its pipeline require. To make that easier, 532a ``getLoopAnalysisUsage`` function is provided by ``LoopUtils.h``. It can be 533called within the subclass's ``getAnalysisUsage`` override to get consistent 534and correct behavior. Analogously, ``INITIALIZE_PASS_DEPENDENCY(LoopPass)`` 535will initialize this set of function analyses. 536 537The ``doInitialization(Loop *, LPPassManager &)`` method 538^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 539 540.. code-block:: c++ 541 542 virtual bool doInitialization(Loop *, LPPassManager &LPM); 543 544The ``doInitialization`` method is designed to do simple initialization type of 545stuff that does not depend on the functions being processed. The 546``doInitialization`` method call is not scheduled to overlap with any other 547pass executions (thus it should be very fast). ``LPPassManager`` interface 548should be used to access ``Function`` or ``Module`` level analysis information. 549 550.. _writing-an-llvm-pass-runOnLoop: 551 552The ``runOnLoop`` method 553^^^^^^^^^^^^^^^^^^^^^^^^ 554 555.. code-block:: c++ 556 557 virtual bool runOnLoop(Loop *, LPPassManager &LPM) = 0; 558 559The ``runOnLoop`` method must be implemented by your subclass to do the 560transformation or analysis work of your pass. As usual, a ``true`` value 561should be returned if the function is modified. ``LPPassManager`` interface 562should be used to update loop nest. 563 564The ``doFinalization()`` method 565^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 566 567.. code-block:: c++ 568 569 virtual bool doFinalization(); 570 571The ``doFinalization`` method is an infrequently used method that is called 572when the pass framework has finished calling :ref:`runOnLoop 573<writing-an-llvm-pass-runOnLoop>` for every loop in the program being compiled. 574 575.. _writing-an-llvm-pass-RegionPass: 576 577The ``RegionPass`` class 578------------------------ 579 580``RegionPass`` is similar to :ref:`LoopPass <writing-an-llvm-pass-LoopPass>`, 581but executes on each single entry single exit region in the function. 582``RegionPass`` processes regions in nested order such that the outer most 583region is processed last. 584 585``RegionPass`` subclasses are allowed to update the region tree by using the 586``RGPassManager`` interface. You may overload three virtual methods of 587``RegionPass`` to implement your own region pass. All these methods should 588return ``true`` if they modified the program, or ``false`` if they did not. 589 590The ``doInitialization(Region *, RGPassManager &)`` method 591^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 592 593.. code-block:: c++ 594 595 virtual bool doInitialization(Region *, RGPassManager &RGM); 596 597The ``doInitialization`` method is designed to do simple initialization type of 598stuff that does not depend on the functions being processed. The 599``doInitialization`` method call is not scheduled to overlap with any other 600pass executions (thus it should be very fast). ``RPPassManager`` interface 601should be used to access ``Function`` or ``Module`` level analysis information. 602 603.. _writing-an-llvm-pass-runOnRegion: 604 605The ``runOnRegion`` method 606^^^^^^^^^^^^^^^^^^^^^^^^^^ 607 608.. code-block:: c++ 609 610 virtual bool runOnRegion(Region *, RGPassManager &RGM) = 0; 611 612The ``runOnRegion`` method must be implemented by your subclass to do the 613transformation or analysis work of your pass. As usual, a true value should be 614returned if the region is modified. ``RGPassManager`` interface should be used to 615update region tree. 616 617The ``doFinalization()`` method 618^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 619 620.. code-block:: c++ 621 622 virtual bool doFinalization(); 623 624The ``doFinalization`` method is an infrequently used method that is called 625when the pass framework has finished calling :ref:`runOnRegion 626<writing-an-llvm-pass-runOnRegion>` for every region in the program being 627compiled. 628 629.. _writing-an-llvm-pass-BasicBlockPass: 630 631The ``BasicBlockPass`` class 632---------------------------- 633 634``BasicBlockPass``\ es are just like :ref:`FunctionPass's 635<writing-an-llvm-pass-FunctionPass>` , except that they must limit their scope 636of inspection and modification to a single basic block at a time. As such, 637they are **not** allowed to do any of the following: 638 639#. Modify or inspect any basic blocks outside of the current one. 640#. Maintain state across invocations of :ref:`runOnBasicBlock 641 <writing-an-llvm-pass-runOnBasicBlock>`. 642#. Modify the control flow graph (by altering terminator instructions) 643#. Any of the things forbidden for :ref:`FunctionPasses 644 <writing-an-llvm-pass-FunctionPass>`. 645 646``BasicBlockPass``\ es are useful for traditional local and "peephole" 647optimizations. They may override the same :ref:`doInitialization(Module &) 648<writing-an-llvm-pass-doInitialization-mod>` and :ref:`doFinalization(Module &) 649<writing-an-llvm-pass-doFinalization-mod>` methods that :ref:`FunctionPass's 650<writing-an-llvm-pass-FunctionPass>` have, but also have the following virtual 651methods that may also be implemented: 652 653The ``doInitialization(Function &)`` method 654^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 655 656.. code-block:: c++ 657 658 virtual bool doInitialization(Function &F); 659 660The ``doInitialization`` method is allowed to do most of the things that 661``BasicBlockPass``\ es are not allowed to do, but that ``FunctionPass``\ es 662can. The ``doInitialization`` method is designed to do simple initialization 663that does not depend on the ``BasicBlock``\ s being processed. The 664``doInitialization`` method call is not scheduled to overlap with any other 665pass executions (thus it should be very fast). 666 667.. _writing-an-llvm-pass-runOnBasicBlock: 668 669The ``runOnBasicBlock`` method 670^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 671 672.. code-block:: c++ 673 674 virtual bool runOnBasicBlock(BasicBlock &BB) = 0; 675 676Override this function to do the work of the ``BasicBlockPass``. This function 677is not allowed to inspect or modify basic blocks other than the parameter, and 678are not allowed to modify the CFG. A ``true`` value must be returned if the 679basic block is modified. 680 681The ``doFinalization(Function &)`` method 682^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 683 684.. code-block:: c++ 685 686 virtual bool doFinalization(Function &F); 687 688The ``doFinalization`` method is an infrequently used method that is called 689when the pass framework has finished calling :ref:`runOnBasicBlock 690<writing-an-llvm-pass-runOnBasicBlock>` for every ``BasicBlock`` in the program 691being compiled. This can be used to perform per-function finalization. 692 693The ``MachineFunctionPass`` class 694--------------------------------- 695 696A ``MachineFunctionPass`` is a part of the LLVM code generator that executes on 697the machine-dependent representation of each LLVM function in the program. 698 699Code generator passes are registered and initialized specially by 700``TargetMachine::addPassesToEmitFile`` and similar routines, so they cannot 701generally be run from the :program:`opt` or :program:`bugpoint` commands. 702 703A ``MachineFunctionPass`` is also a ``FunctionPass``, so all the restrictions 704that apply to a ``FunctionPass`` also apply to it. ``MachineFunctionPass``\ es 705also have additional restrictions. In particular, ``MachineFunctionPass``\ es 706are not allowed to do any of the following: 707 708#. Modify or create any LLVM IR ``Instruction``\ s, ``BasicBlock``\ s, 709 ``Argument``\ s, ``Function``\ s, ``GlobalVariable``\ s, 710 ``GlobalAlias``\ es, or ``Module``\ s. 711#. Modify a ``MachineFunction`` other than the one currently being processed. 712#. Maintain state across invocations of :ref:`runOnMachineFunction 713 <writing-an-llvm-pass-runOnMachineFunction>` (including global data). 714 715.. _writing-an-llvm-pass-runOnMachineFunction: 716 717The ``runOnMachineFunction(MachineFunction &MF)`` method 718^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 719 720.. code-block:: c++ 721 722 virtual bool runOnMachineFunction(MachineFunction &MF) = 0; 723 724``runOnMachineFunction`` can be considered the main entry point of a 725``MachineFunctionPass``; that is, you should override this method to do the 726work of your ``MachineFunctionPass``. 727 728The ``runOnMachineFunction`` method is called on every ``MachineFunction`` in a 729``Module``, so that the ``MachineFunctionPass`` may perform optimizations on 730the machine-dependent representation of the function. If you want to get at 731the LLVM ``Function`` for the ``MachineFunction`` you're working on, use 732``MachineFunction``'s ``getFunction()`` accessor method --- but remember, you 733may not modify the LLVM ``Function`` or its contents from a 734``MachineFunctionPass``. 735 736.. _writing-an-llvm-pass-registration: 737 738Pass registration 739----------------- 740 741In the :ref:`Hello World <writing-an-llvm-pass-basiccode>` example pass we 742illustrated how pass registration works, and discussed some of the reasons that 743it is used and what it does. Here we discuss how and why passes are 744registered. 745 746As we saw above, passes are registered with the ``RegisterPass`` template. The 747template parameter is the name of the pass that is to be used on the command 748line to specify that the pass should be added to a program (for example, with 749:program:`opt` or :program:`bugpoint`). The first argument is the name of the 750pass, which is to be used for the :option:`-help` output of programs, as well 751as for debug output generated by the `--debug-pass` option. 752 753If you want your pass to be easily dumpable, you should implement the virtual 754print method: 755 756The ``print`` method 757^^^^^^^^^^^^^^^^^^^^ 758 759.. code-block:: c++ 760 761 virtual void print(llvm::raw_ostream &O, const Module *M) const; 762 763The ``print`` method must be implemented by "analyses" in order to print a 764human readable version of the analysis results. This is useful for debugging 765an analysis itself, as well as for other people to figure out how an analysis 766works. Use the opt ``-analyze`` argument to invoke this method. 767 768The ``llvm::raw_ostream`` parameter specifies the stream to write the results 769on, and the ``Module`` parameter gives a pointer to the top level module of the 770program that has been analyzed. Note however that this pointer may be ``NULL`` 771in certain circumstances (such as calling the ``Pass::dump()`` from a 772debugger), so it should only be used to enhance debug output, it should not be 773depended on. 774 775.. _writing-an-llvm-pass-interaction: 776 777Specifying interactions between passes 778-------------------------------------- 779 780One of the main responsibilities of the ``PassManager`` is to make sure that 781passes interact with each other correctly. Because ``PassManager`` tries to 782:ref:`optimize the execution of passes <writing-an-llvm-pass-passmanager>` it 783must know how the passes interact with each other and what dependencies exist 784between the various passes. To track this, each pass can declare the set of 785passes that are required to be executed before the current pass, and the passes 786which are invalidated by the current pass. 787 788Typically this functionality is used to require that analysis results are 789computed before your pass is run. Running arbitrary transformation passes can 790invalidate the computed analysis results, which is what the invalidation set 791specifies. If a pass does not implement the :ref:`getAnalysisUsage 792<writing-an-llvm-pass-getAnalysisUsage>` method, it defaults to not having any 793prerequisite passes, and invalidating **all** other passes. 794 795.. _writing-an-llvm-pass-getAnalysisUsage: 796 797The ``getAnalysisUsage`` method 798^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 799 800.. code-block:: c++ 801 802 virtual void getAnalysisUsage(AnalysisUsage &Info) const; 803 804By implementing the ``getAnalysisUsage`` method, the required and invalidated 805sets may be specified for your transformation. The implementation should fill 806in the `AnalysisUsage 807<http://llvm.org/doxygen/classllvm_1_1AnalysisUsage.html>`_ object with 808information about which passes are required and not invalidated. To do this, a 809pass may call any of the following methods on the ``AnalysisUsage`` object: 810 811The ``AnalysisUsage::addRequired<>`` and ``AnalysisUsage::addRequiredTransitive<>`` methods 812^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 813 814If your pass requires a previous pass to be executed (an analysis for example), 815it can use one of these methods to arrange for it to be run before your pass. 816LLVM has many different types of analyses and passes that can be required, 817spanning the range from ``DominatorSet`` to ``BreakCriticalEdges``. Requiring 818``BreakCriticalEdges``, for example, guarantees that there will be no critical 819edges in the CFG when your pass has been run. 820 821Some analyses chain to other analyses to do their job. For example, an 822`AliasAnalysis <AliasAnalysis>` implementation is required to :ref:`chain 823<aliasanalysis-chaining>` to other alias analysis passes. In cases where 824analyses chain, the ``addRequiredTransitive`` method should be used instead of 825the ``addRequired`` method. This informs the ``PassManager`` that the 826transitively required pass should be alive as long as the requiring pass is. 827 828The ``AnalysisUsage::addPreserved<>`` method 829^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 830 831One of the jobs of the ``PassManager`` is to optimize how and when analyses are 832run. In particular, it attempts to avoid recomputing data unless it needs to. 833For this reason, passes are allowed to declare that they preserve (i.e., they 834don't invalidate) an existing analysis if it's available. For example, a 835simple constant folding pass would not modify the CFG, so it can't possibly 836affect the results of dominator analysis. By default, all passes are assumed 837to invalidate all others. 838 839The ``AnalysisUsage`` class provides several methods which are useful in 840certain circumstances that are related to ``addPreserved``. In particular, the 841``setPreservesAll`` method can be called to indicate that the pass does not 842modify the LLVM program at all (which is true for analyses), and the 843``setPreservesCFG`` method can be used by transformations that change 844instructions in the program but do not modify the CFG or terminator 845instructions (note that this property is implicitly set for 846:ref:`BasicBlockPass <writing-an-llvm-pass-BasicBlockPass>`\ es). 847 848``addPreserved`` is particularly useful for transformations like 849``BreakCriticalEdges``. This pass knows how to update a small set of loop and 850dominator related analyses if they exist, so it can preserve them, despite the 851fact that it hacks on the CFG. 852 853Example implementations of ``getAnalysisUsage`` 854^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 855 856.. code-block:: c++ 857 858 // This example modifies the program, but does not modify the CFG 859 void LICM::getAnalysisUsage(AnalysisUsage &AU) const { 860 AU.setPreservesCFG(); 861 AU.addRequired<LoopInfoWrapperPass>(); 862 } 863 864.. _writing-an-llvm-pass-getAnalysis: 865 866The ``getAnalysis<>`` and ``getAnalysisIfAvailable<>`` methods 867^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 868 869The ``Pass::getAnalysis<>`` method is automatically inherited by your class, 870providing you with access to the passes that you declared that you required 871with the :ref:`getAnalysisUsage <writing-an-llvm-pass-getAnalysisUsage>` 872method. It takes a single template argument that specifies which pass class 873you want, and returns a reference to that pass. For example: 874 875.. code-block:: c++ 876 877 bool LICM::runOnFunction(Function &F) { 878 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 879 //... 880 } 881 882This method call returns a reference to the pass desired. You may get a 883runtime assertion failure if you attempt to get an analysis that you did not 884declare as required in your :ref:`getAnalysisUsage 885<writing-an-llvm-pass-getAnalysisUsage>` implementation. This method can be 886called by your ``run*`` method implementation, or by any other local method 887invoked by your ``run*`` method. 888 889A module level pass can use function level analysis info using this interface. 890For example: 891 892.. code-block:: c++ 893 894 bool ModuleLevelPass::runOnModule(Module &M) { 895 //... 896 DominatorTree &DT = getAnalysis<DominatorTree>(Func); 897 //... 898 } 899 900In above example, ``runOnFunction`` for ``DominatorTree`` is called by pass 901manager before returning a reference to the desired pass. 902 903If your pass is capable of updating analyses if they exist (e.g., 904``BreakCriticalEdges``, as described above), you can use the 905``getAnalysisIfAvailable`` method, which returns a pointer to the analysis if 906it is active. For example: 907 908.. code-block:: c++ 909 910 if (DominatorSet *DS = getAnalysisIfAvailable<DominatorSet>()) { 911 // A DominatorSet is active. This code will update it. 912 } 913 914Implementing Analysis Groups 915---------------------------- 916 917Now that we understand the basics of how passes are defined, how they are used, 918and how they are required from other passes, it's time to get a little bit 919fancier. All of the pass relationships that we have seen so far are very 920simple: one pass depends on one other specific pass to be run before it can 921run. For many applications, this is great, for others, more flexibility is 922required. 923 924In particular, some analyses are defined such that there is a single simple 925interface to the analysis results, but multiple ways of calculating them. 926Consider alias analysis for example. The most trivial alias analysis returns 927"may alias" for any alias query. The most sophisticated analysis a 928flow-sensitive, context-sensitive interprocedural analysis that can take a 929significant amount of time to execute (and obviously, there is a lot of room 930between these two extremes for other implementations). To cleanly support 931situations like this, the LLVM Pass Infrastructure supports the notion of 932Analysis Groups. 933 934Analysis Group Concepts 935^^^^^^^^^^^^^^^^^^^^^^^ 936 937An Analysis Group is a single simple interface that may be implemented by 938multiple different passes. Analysis Groups can be given human readable names 939just like passes, but unlike passes, they need not derive from the ``Pass`` 940class. An analysis group may have one or more implementations, one of which is 941the "default" implementation. 942 943Analysis groups are used by client passes just like other passes are: the 944``AnalysisUsage::addRequired()`` and ``Pass::getAnalysis()`` methods. In order 945to resolve this requirement, the :ref:`PassManager 946<writing-an-llvm-pass-passmanager>` scans the available passes to see if any 947implementations of the analysis group are available. If none is available, the 948default implementation is created for the pass to use. All standard rules for 949:ref:`interaction between passes <writing-an-llvm-pass-interaction>` still 950apply. 951 952Although :ref:`Pass Registration <writing-an-llvm-pass-registration>` is 953optional for normal passes, all analysis group implementations must be 954registered, and must use the :ref:`INITIALIZE_AG_PASS 955<writing-an-llvm-pass-RegisterAnalysisGroup>` template to join the 956implementation pool. Also, a default implementation of the interface **must** 957be registered with :ref:`RegisterAnalysisGroup 958<writing-an-llvm-pass-RegisterAnalysisGroup>`. 959 960As a concrete example of an Analysis Group in action, consider the 961`AliasAnalysis <http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html>`_ 962analysis group. The default implementation of the alias analysis interface 963(the `basicaa <http://llvm.org/doxygen/structBasicAliasAnalysis.html>`_ pass) 964just does a few simple checks that don't require significant analysis to 965compute (such as: two different globals can never alias each other, etc). 966Passes that use the `AliasAnalysis 967<http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html>`_ interface (for 968example the `gvn <http://llvm.org/doxygen/classllvm_1_1GVN.html>`_ pass), do not 969care which implementation of alias analysis is actually provided, they just use 970the designated interface. 971 972From the user's perspective, commands work just like normal. Issuing the 973command ``opt -gvn ...`` will cause the ``basicaa`` class to be instantiated 974and added to the pass sequence. Issuing the command ``opt -somefancyaa -gvn 975...`` will cause the ``gvn`` pass to use the ``somefancyaa`` alias analysis 976(which doesn't actually exist, it's just a hypothetical example) instead. 977 978.. _writing-an-llvm-pass-RegisterAnalysisGroup: 979 980Using ``RegisterAnalysisGroup`` 981^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 982 983The ``RegisterAnalysisGroup`` template is used to register the analysis group 984itself, while the ``INITIALIZE_AG_PASS`` is used to add pass implementations to 985the analysis group. First, an analysis group should be registered, with a 986human readable name provided for it. Unlike registration of passes, there is 987no command line argument to be specified for the Analysis Group Interface 988itself, because it is "abstract": 989 990.. code-block:: c++ 991 992 static RegisterAnalysisGroup<AliasAnalysis> A("Alias Analysis"); 993 994Once the analysis is registered, passes can declare that they are valid 995implementations of the interface by using the following code: 996 997.. code-block:: c++ 998 999 namespace { 1000 // Declare that we implement the AliasAnalysis interface 1001 INITIALIZE_AG_PASS(FancyAA, AliasAnalysis , "somefancyaa", 1002 "A more complex alias analysis implementation", 1003 false, // Is CFG Only? 1004 true, // Is Analysis? 1005 false); // Is default Analysis Group implementation? 1006 } 1007 1008This just shows a class ``FancyAA`` that uses the ``INITIALIZE_AG_PASS`` macro 1009both to register and to "join" the `AliasAnalysis 1010<http://llvm.org/doxygen/classllvm_1_1AliasAnalysis.html>`_ analysis group. 1011Every implementation of an analysis group should join using this macro. 1012 1013.. code-block:: c++ 1014 1015 namespace { 1016 // Declare that we implement the AliasAnalysis interface 1017 INITIALIZE_AG_PASS(BasicAA, AliasAnalysis, "basicaa", 1018 "Basic Alias Analysis (default AA impl)", 1019 false, // Is CFG Only? 1020 true, // Is Analysis? 1021 true); // Is default Analysis Group implementation? 1022 } 1023 1024Here we show how the default implementation is specified (using the final 1025argument to the ``INITIALIZE_AG_PASS`` template). There must be exactly one 1026default implementation available at all times for an Analysis Group to be used. 1027Only default implementation can derive from ``ImmutablePass``. Here we declare 1028that the `BasicAliasAnalysis 1029<http://llvm.org/doxygen/structBasicAliasAnalysis.html>`_ pass is the default 1030implementation for the interface. 1031 1032Pass Statistics 1033=============== 1034 1035The `Statistic <http://llvm.org/doxygen/Statistic_8h_source.html>`_ class is 1036designed to be an easy way to expose various success metrics from passes. 1037These statistics are printed at the end of a run, when the :option:`-stats` 1038command line option is enabled on the command line. See the :ref:`Statistics 1039section <Statistic>` in the Programmer's Manual for details. 1040 1041.. _writing-an-llvm-pass-passmanager: 1042 1043What PassManager does 1044--------------------- 1045 1046The `PassManager <http://llvm.org/doxygen/PassManager_8h_source.html>`_ `class 1047<http://llvm.org/doxygen/classllvm_1_1PassManager.html>`_ takes a list of 1048passes, ensures their :ref:`prerequisites <writing-an-llvm-pass-interaction>` 1049are set up correctly, and then schedules passes to run efficiently. All of the 1050LLVM tools that run passes use the PassManager for execution of these passes. 1051 1052The PassManager does two main things to try to reduce the execution time of a 1053series of passes: 1054 1055#. **Share analysis results.** The ``PassManager`` attempts to avoid 1056 recomputing analysis results as much as possible. This means keeping track 1057 of which analyses are available already, which analyses get invalidated, and 1058 which analyses are needed to be run for a pass. An important part of work 1059 is that the ``PassManager`` tracks the exact lifetime of all analysis 1060 results, allowing it to :ref:`free memory 1061 <writing-an-llvm-pass-releaseMemory>` allocated to holding analysis results 1062 as soon as they are no longer needed. 1063 1064#. **Pipeline the execution of passes on the program.** The ``PassManager`` 1065 attempts to get better cache and memory usage behavior out of a series of 1066 passes by pipelining the passes together. This means that, given a series 1067 of consecutive :ref:`FunctionPass <writing-an-llvm-pass-FunctionPass>`, it 1068 will execute all of the :ref:`FunctionPass 1069 <writing-an-llvm-pass-FunctionPass>` on the first function, then all of the 1070 :ref:`FunctionPasses <writing-an-llvm-pass-FunctionPass>` on the second 1071 function, etc... until the entire program has been run through the passes. 1072 1073 This improves the cache behavior of the compiler, because it is only 1074 touching the LLVM program representation for a single function at a time, 1075 instead of traversing the entire program. It reduces the memory consumption 1076 of compiler, because, for example, only one `DominatorSet 1077 <http://llvm.org/doxygen/classllvm_1_1DominatorSet.html>`_ needs to be 1078 calculated at a time. This also makes it possible to implement some 1079 :ref:`interesting enhancements <writing-an-llvm-pass-SMP>` in the future. 1080 1081The effectiveness of the ``PassManager`` is influenced directly by how much 1082information it has about the behaviors of the passes it is scheduling. For 1083example, the "preserved" set is intentionally conservative in the face of an 1084unimplemented :ref:`getAnalysisUsage <writing-an-llvm-pass-getAnalysisUsage>` 1085method. Not implementing when it should be implemented will have the effect of 1086not allowing any analysis results to live across the execution of your pass. 1087 1088The ``PassManager`` class exposes a ``--debug-pass`` command line options that 1089is useful for debugging pass execution, seeing how things work, and diagnosing 1090when you should be preserving more analyses than you currently are. (To get 1091information about all of the variants of the ``--debug-pass`` option, just type 1092"``opt -help-hidden``"). 1093 1094By using the --debug-pass=Structure option, for example, we can see how our 1095:ref:`Hello World <writing-an-llvm-pass-basiccode>` pass interacts with other 1096passes. Lets try it out with the gvn and licm passes: 1097 1098.. code-block:: console 1099 1100 $ opt -load lib/LLVMHello.so -gvn -licm --debug-pass=Structure < hello.bc > /dev/null 1101 ModulePass Manager 1102 FunctionPass Manager 1103 Dominator Tree Construction 1104 Basic Alias Analysis (stateless AA impl) 1105 Function Alias Analysis Results 1106 Memory Dependence Analysis 1107 Global Value Numbering 1108 Natural Loop Information 1109 Canonicalize natural loops 1110 Loop-Closed SSA Form Pass 1111 Basic Alias Analysis (stateless AA impl) 1112 Function Alias Analysis Results 1113 Scalar Evolution Analysis 1114 Loop Pass Manager 1115 Loop Invariant Code Motion 1116 Module Verifier 1117 Bitcode Writer 1118 1119This output shows us when passes are constructed. 1120Here we see that GVN uses dominator tree information to do its job. The LICM pass 1121uses natural loop information, which uses dominator tree as well. 1122 1123After the LICM pass, the module verifier runs (which is automatically added by 1124the :program:`opt` tool), which uses the dominator tree to check that the 1125resultant LLVM code is well formed. Note that the dominator tree is computed 1126once, and shared by three passes. 1127 1128Lets see how this changes when we run the :ref:`Hello World 1129<writing-an-llvm-pass-basiccode>` pass in between the two passes: 1130 1131.. code-block:: console 1132 1133 $ opt -load lib/LLVMHello.so -gvn -hello -licm --debug-pass=Structure < hello.bc > /dev/null 1134 ModulePass Manager 1135 FunctionPass Manager 1136 Dominator Tree Construction 1137 Basic Alias Analysis (stateless AA impl) 1138 Function Alias Analysis Results 1139 Memory Dependence Analysis 1140 Global Value Numbering 1141 Hello World Pass 1142 Dominator Tree Construction 1143 Natural Loop Information 1144 Canonicalize natural loops 1145 Loop-Closed SSA Form Pass 1146 Basic Alias Analysis (stateless AA impl) 1147 Function Alias Analysis Results 1148 Scalar Evolution Analysis 1149 Loop Pass Manager 1150 Loop Invariant Code Motion 1151 Module Verifier 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 Tree 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 lib/LLVMHello.so -gvn -hello -licm --debug-pass=Structure < hello.bc > /dev/null 1174 Pass Arguments: -gvn -hello -licm 1175 ModulePass Manager 1176 FunctionPass Manager 1177 Dominator Tree Construction 1178 Basic Alias Analysis (stateless AA impl) 1179 Function Alias Analysis Results 1180 Memory Dependence Analysis 1181 Global Value Numbering 1182 Hello World Pass 1183 Natural Loop Information 1184 Canonicalize natural loops 1185 Loop-Closed SSA Form Pass 1186 Basic Alias Analysis (stateless AA impl) 1187 Function Alias Analysis Results 1188 Scalar Evolution Analysis 1189 Loop Pass Manager 1190 Loop Invariant Code Motion 1191 Module Verifier 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 Next 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