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