897 lines · plain
1========================================2Writing an LLVM Pass (legacy PM version)3========================================4 5.. program:: opt6 7.. contents::8 :local:9 10Introduction --- What is a pass?11================================12 13.. warning::14 This document deals with the legacy pass manager. LLVM uses the new pass15 manager for the optimization pipeline (the codegen pipeline16 still uses the legacy pass manager), which has its own way of defining17 passes. For more details, see :doc:`WritingAnLLVMNewPMPass` and18 :doc:`NewPassManager`.19 20The LLVM Pass Framework is an important part of the LLVM system, because LLVM21passes are where most of the interesting parts of the compiler exist. Passes22perform the transformations and optimizations that make up the compiler, they23build the analysis results that are used by these transformations, and they24are, above all, a structuring technique for compiler code.25 26All LLVM passes are subclasses of the `Pass27<https://llvm.org/doxygen/classllvm_1_1Pass.html>`_ class, which implement28functionality by overriding virtual methods inherited from ``Pass``. Depending29on how your pass works, you should inherit from the :ref:`ModulePass30<writing-an-llvm-pass-ModulePass>` , :ref:`CallGraphSCCPass31<writing-an-llvm-pass-CallGraphSCCPass>`, :ref:`FunctionPass32<writing-an-llvm-pass-FunctionPass>` , or :ref:`LoopPass33<writing-an-llvm-pass-LoopPass>`, or :ref:`RegionPass34<writing-an-llvm-pass-RegionPass>` classes, which gives the system more35information about what your pass does, and how it can be combined with other36passes. One of the main features of the LLVM Pass Framework is that it37schedules passes to run in an efficient way based on the constraints that your38pass meets (which are indicated by which class they derive from).39 40.. _writing-an-llvm-pass-pass-classes:41 42Pass classes and requirements43=============================44 45One of the first things that you should do when designing a new pass is to46decide what class you should subclass for your pass. Here we talk about the47classes available, from the most general to the most specific.48 49When choosing a superclass for your ``Pass``, you should choose the **most50specific** class possible, while still being able to meet the requirements51listed. This gives the LLVM Pass Infrastructure information necessary to52optimize how passes are run, so that the resultant compiler isn't unnecessarily53slow.54 55The ``ImmutablePass`` class56---------------------------57 58The most plain and boring type of pass is the "`ImmutablePass59<https://llvm.org/doxygen/classllvm_1_1ImmutablePass.html>`_" class. This pass60type is used for passes that do not have to be run, do not change state, and61never need to be updated. This is not a normal type of transformation or62analysis, but can provide information about the current compiler configuration.63 64Although this pass class is very infrequently used, it is important for65providing information about the current target machine being compiled for, and66other static information that can affect the various transformations.67 68``ImmutablePass``\ es never invalidate other transformations, are never69invalidated, and are never "run".70 71.. _writing-an-llvm-pass-ModulePass:72 73The ``ModulePass`` class74------------------------75 76The `ModulePass <https://llvm.org/doxygen/classllvm_1_1ModulePass.html>`_ class77is the most general of all superclasses that you can use. Deriving from78``ModulePass`` indicates that your pass uses the entire program as a unit,79referring to function bodies in no predictable order, or adding and removing80functions. Because nothing is known about the behavior of ``ModulePass``81subclasses, no optimization can be done for their execution.82 83A module pass can use function level passes (e.g. dominators) using the84``getAnalysis`` interface ``getAnalysis<DominatorTree>(llvm::Function *)`` to85provide the function to retrieve analysis result for, if the function pass does86not require any module or immutable passes. Note that this can only be done87for functions for which the analysis ran, e.g. in the case of dominators you88should only ask for the ``DominatorTree`` for function definitions, not89declarations.90 91To write a correct ``ModulePass`` subclass, derive from ``ModulePass`` and92override the ``runOnModule`` method with the following signature:93 94The ``runOnModule`` method95^^^^^^^^^^^^^^^^^^^^^^^^^^96 97.. code-block:: c++98 99 virtual bool runOnModule(Module &M) = 0;100 101The ``runOnModule`` method performs the interesting work of the pass. It102should return ``true`` if the module was modified by the transformation and103``false`` otherwise.104 105.. _writing-an-llvm-pass-CallGraphSCCPass:106 107The ``CallGraphSCCPass`` class108------------------------------109 110The `CallGraphSCCPass111<https://llvm.org/doxygen/classllvm_1_1CallGraphSCCPass.html>`_ is used by112passes that need to traverse the program bottom-up on the call graph (callees113before callers). Deriving from ``CallGraphSCCPass`` provides some mechanics114for building and traversing the ``CallGraph``, but also allows the system to115optimize execution of ``CallGraphSCCPass``\ es. If your pass meets the116requirements outlined below, and doesn't meet the requirements of a117:ref:`FunctionPass <writing-an-llvm-pass-FunctionPass>`, you should derive from118``CallGraphSCCPass``.119 120``TODO``: explain briefly what SCC, Tarjan's algo, and B-U mean.121 122To be explicit, CallGraphSCCPass subclasses are:123 124#. ... *not allowed* to inspect or modify any ``Function``\ s other than those125 in the current SCC and the direct callers and direct callees of the SCC.126#. ... *required* to preserve the current ``CallGraph`` object, updating it to127 reflect any changes made to the program.128#. ... *not allowed* to add or remove SCC's from the current Module, though129 they may change the contents of an SCC.130#. ... *allowed* to add or remove global variables from the current Module.131#. ... *allowed* to maintain state across invocations of :ref:`runOnSCC132 <writing-an-llvm-pass-runOnSCC>` (including global data).133 134Implementing a ``CallGraphSCCPass`` is slightly tricky in some cases because it135has to handle SCCs with more than one node in it. All of the virtual methods136described below should return ``true`` if they modified the program, or137``false`` if they didn't.138 139The ``doInitialization(CallGraph &)`` method140^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^141 142.. code-block:: c++143 144 virtual bool doInitialization(CallGraph &CG);145 146The ``doInitialization`` method is allowed to do most of the things that147``CallGraphSCCPass``\ es are not allowed to do. They can add and remove148functions, get pointers to functions, etc. The ``doInitialization`` method is149designed to do simple initialization type of stuff that does not depend on the150SCCs being processed. The ``doInitialization`` method call is not scheduled to151overlap with any other pass executions (thus it should be very fast).152 153.. _writing-an-llvm-pass-runOnSCC:154 155The ``runOnSCC`` method156^^^^^^^^^^^^^^^^^^^^^^^157 158.. code-block:: c++159 160 virtual bool runOnSCC(CallGraphSCC &SCC) = 0;161 162The ``runOnSCC`` method performs the interesting work of the pass, and should163return ``true`` if the module was modified by the transformation, ``false``164otherwise.165 166The ``doFinalization(CallGraph &)`` method167^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^168 169.. code-block:: c++170 171 virtual bool doFinalization(CallGraph &CG);172 173The ``doFinalization`` method is an infrequently used method that is called174when the pass framework has finished calling :ref:`runOnSCC175<writing-an-llvm-pass-runOnSCC>` for every SCC in the program being compiled.176 177.. _writing-an-llvm-pass-FunctionPass:178 179The ``FunctionPass`` class180--------------------------181 182In contrast to ``ModulePass`` subclasses, `FunctionPass183<https://llvm.org/doxygen/classllvm_1_1Pass.html>`_ subclasses do have a184predictable, local behavior that can be expected by the system. All185``FunctionPass`` execute on each function in the program independent of all of186the other functions in the program. ``FunctionPass``\ es do not require that187they are executed in a particular order, and ``FunctionPass``\ es do not modify188external functions.189 190To be explicit, ``FunctionPass`` subclasses are not allowed to:191 192#. Inspect or modify a ``Function`` other than the one currently being processed.193#. Add or remove ``Function``\ s from the current ``Module``.194#. Add or remove global variables from the current ``Module``.195#. Maintain state across invocations of :ref:`runOnFunction196 <writing-an-llvm-pass-runOnFunction>` (including global data).197 198Implementing a ``FunctionPass`` is usually straightforward. ``FunctionPass``\199es may override three virtual methods to do their work. All of these methods200should return ``true`` if they modified the program, or ``false`` if they201didn't.202 203.. _writing-an-llvm-pass-doInitialization-mod:204 205The ``doInitialization(Module &)`` method206^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^207 208.. code-block:: c++209 210 virtual bool doInitialization(Module &M);211 212The ``doInitialization`` method is allowed to do most of the things that213``FunctionPass``\ es are not allowed to do. They can add and remove functions,214get pointers to functions, etc. The ``doInitialization`` method is designed to215do simple initialization type of stuff that does not depend on the functions216being processed. The ``doInitialization`` method call is not scheduled to217overlap with any other pass executions (thus it should be very fast).218 219A good example of how this method should be used is the `LowerAllocations220<https://llvm.org/doxygen/LowerAllocations_8cpp-source.html>`_ pass. This pass221converts ``malloc`` and ``free`` instructions into platform dependent222``malloc()`` and ``free()`` function calls. It uses the ``doInitialization``223method to get a reference to the ``malloc`` and ``free`` functions that it224needs, adding prototypes to the module if necessary.225 226.. _writing-an-llvm-pass-runOnFunction:227 228The ``runOnFunction`` method229^^^^^^^^^^^^^^^^^^^^^^^^^^^^230 231.. code-block:: c++232 233 virtual bool runOnFunction(Function &F) = 0;234 235The ``runOnFunction`` method must be implemented by your subclass to do the236transformation or analysis work of your pass. As usual, a ``true`` value237should be returned if the function is modified.238 239.. _writing-an-llvm-pass-doFinalization-mod:240 241The ``doFinalization(Module &)`` method242^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^243 244.. code-block:: c++245 246 virtual bool doFinalization(Module &M);247 248The ``doFinalization`` method is an infrequently used method that is called249when the pass framework has finished calling :ref:`runOnFunction250<writing-an-llvm-pass-runOnFunction>` for every function in the program being251compiled.252 253.. _writing-an-llvm-pass-LoopPass:254 255The ``LoopPass`` class256----------------------257 258All ``LoopPass`` execute on each :ref:`loop <loop-terminology>` in the function259independent of all of the other loops in the function. ``LoopPass`` processes260loops in loop nest order such that outer most loop is processed last.261 262``LoopPass`` subclasses are allowed to update loop nest using ``LPPassManager``263interface. Implementing a loop pass is usually straightforward.264``LoopPass``\ es may override three virtual methods to do their work. All265these methods should return ``true`` if they modified the program, or ``false``266if they didn't.267 268A ``LoopPass`` subclass which is intended to run as part of the main loop pass269pipeline needs to preserve all of the same *function* analyses that the other270loop passes in its pipeline require. To make that easier,271a ``getLoopAnalysisUsage`` function is provided by ``LoopUtils.h``. It can be272called within the subclass's ``getAnalysisUsage`` override to get consistent273and correct behavior. Analogously, ``INITIALIZE_PASS_DEPENDENCY(LoopPass)``274will initialize this set of function analyses.275 276The ``doInitialization(Loop *, LPPassManager &)`` method277^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^278 279.. code-block:: c++280 281 virtual bool doInitialization(Loop *, LPPassManager &LPM);282 283The ``doInitialization`` method is designed to do simple initialization type of284stuff that does not depend on the functions being processed. The285``doInitialization`` method call is not scheduled to overlap with any other286pass executions (thus it should be very fast). ``LPPassManager`` interface287should be used to access ``Function`` or ``Module`` level analysis information.288 289.. _writing-an-llvm-pass-runOnLoop:290 291The ``runOnLoop`` method292^^^^^^^^^^^^^^^^^^^^^^^^293 294.. code-block:: c++295 296 virtual bool runOnLoop(Loop *, LPPassManager &LPM) = 0;297 298The ``runOnLoop`` method must be implemented by your subclass to do the299transformation or analysis work of your pass. As usual, a ``true`` value300should be returned if the function is modified. ``LPPassManager`` interface301should be used to update loop nest.302 303The ``doFinalization()`` method304^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^305 306.. code-block:: c++307 308 virtual bool doFinalization();309 310The ``doFinalization`` method is an infrequently used method that is called311when the pass framework has finished calling :ref:`runOnLoop312<writing-an-llvm-pass-runOnLoop>` for every loop in the program being compiled.313 314.. _writing-an-llvm-pass-RegionPass:315 316The ``RegionPass`` class317------------------------318 319``RegionPass`` is similar to :ref:`LoopPass <writing-an-llvm-pass-LoopPass>`,320but executes on each single entry single exit region in the function.321``RegionPass`` processes regions in nested order such that the outer most322region is processed last.323 324``RegionPass`` subclasses are allowed to update the region tree by using the325``RGPassManager`` interface. You may override three virtual methods of326``RegionPass`` to implement your own region pass. All these methods should327return ``true`` if they modified the program, or ``false`` if they did not.328 329The ``doInitialization(Region *, RGPassManager &)`` method330^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^331 332.. code-block:: c++333 334 virtual bool doInitialization(Region *, RGPassManager &RGM);335 336The ``doInitialization`` method is designed to do simple initialization type of337stuff that does not depend on the functions being processed. The338``doInitialization`` method call is not scheduled to overlap with any other339pass executions (thus it should be very fast). ``RPPassManager`` interface340should be used to access ``Function`` or ``Module`` level analysis information.341 342.. _writing-an-llvm-pass-runOnRegion:343 344The ``runOnRegion`` method345^^^^^^^^^^^^^^^^^^^^^^^^^^346 347.. code-block:: c++348 349 virtual bool runOnRegion(Region *, RGPassManager &RGM) = 0;350 351The ``runOnRegion`` method must be implemented by your subclass to do the352transformation or analysis work of your pass. As usual, a true value should be353returned if the region is modified. ``RGPassManager`` interface should be used to354update region tree.355 356The ``doFinalization()`` method357^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^358 359.. code-block:: c++360 361 virtual bool doFinalization();362 363The ``doFinalization`` method is an infrequently used method that is called364when the pass framework has finished calling :ref:`runOnRegion365<writing-an-llvm-pass-runOnRegion>` for every region in the program being366compiled.367 368 369The ``MachineFunctionPass`` class370---------------------------------371 372A ``MachineFunctionPass`` is a part of the LLVM code generator that executes on373the machine-dependent representation of each LLVM function in the program.374 375Code generator passes are registered and initialized specially by376``TargetMachine::addPassesToEmitFile`` and similar routines, so they cannot377generally be run from the :program:`opt` or :program:`bugpoint` commands.378 379A ``MachineFunctionPass`` is also a ``FunctionPass``, so all the restrictions380that apply to a ``FunctionPass`` also apply to it. ``MachineFunctionPass``\ es381also have additional restrictions. In particular, ``MachineFunctionPass``\ es382are not allowed to do any of the following:383 384#. Modify or create any LLVM IR ``Instruction``\ s, ``BasicBlock``\ s,385 ``Argument``\ s, ``Function``\ s, ``GlobalVariable``\ s,386 ``GlobalAlias``\ es, or ``Module``\ s.387#. Modify a ``MachineFunction`` other than the one currently being processed.388#. Maintain state across invocations of :ref:`runOnMachineFunction389 <writing-an-llvm-pass-runOnMachineFunction>` (including global data).390 391.. _writing-an-llvm-pass-runOnMachineFunction:392 393The ``runOnMachineFunction(MachineFunction &MF)`` method394^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^395 396.. code-block:: c++397 398 virtual bool runOnMachineFunction(MachineFunction &MF) = 0;399 400``runOnMachineFunction`` can be considered the main entry point of a401``MachineFunctionPass``; that is, you should override this method to do the402work of your ``MachineFunctionPass``.403 404The ``runOnMachineFunction`` method is called on every ``MachineFunction`` in a405``Module``, so that the ``MachineFunctionPass`` may perform optimizations on406the machine-dependent representation of the function. If you want to get at407the LLVM ``Function`` for the ``MachineFunction`` you're working on, use408``MachineFunction``'s ``getFunction()`` accessor method --- but remember, you409may not modify the LLVM ``Function`` or its contents from a410``MachineFunctionPass``.411 412.. _writing-an-llvm-pass-registration:413 414Pass registration415-----------------416 417Passes are registered with the ``RegisterPass`` template. The template418parameter is the name of the pass that is to be used on the command line to419specify that the pass should be added to a program. The first argument is the420name of the pass, which is to be used for the :option:`-help` output of421programs, as well as for debug output generated by the `--debug-pass` option.422 423If you want your pass to be easily dumpable, you should implement the virtual424print method:425 426The ``print`` method427^^^^^^^^^^^^^^^^^^^^428 429.. code-block:: c++430 431 virtual void print(llvm::raw_ostream &O, const Module *M) const;432 433The ``print`` method must be implemented by "analyses" in order to print a434human-readable version of the analysis results. This is useful for debugging435an analysis itself, as well as for other people to figure out how an analysis436works. Use the opt ``-analyze`` argument to invoke this method.437 438The ``llvm::raw_ostream`` parameter specifies the stream to write the results439on, and the ``Module`` parameter gives a pointer to the top level module of the440program that has been analyzed. Note however that this pointer may be ``NULL``441in certain circumstances (such as calling the ``Pass::dump()`` from a442debugger), so it should only be used to enhance debug output, it should not be443depended on.444 445Scheduling a MachineFunctionPass446^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^447 448Backends create a ``TargetPassConfig`` and use ``addPass`` to schedule449``MachineFunctionPass``\ es. External plugins can register a callback to modify450and insert additional passes:451 452.. code-block:: c++453 454 RegisterTargetPassConfigCallback X{[](auto &TM, auto &PM, auto *TPC) {455 TPC->insertPass(/* ... */);456 TPC->substitutePass(/* ... */);457 }};458 459Note that passes still have to be registered:460 461.. code-block:: c++462 463 __attribute__((constructor)) static void initCodeGenPlugin() {464 initializeExamplePass(*PassRegistry::getPassRegistry());465 }466 467.. _writing-an-llvm-pass-interaction:468 469Specifying interactions between passes470--------------------------------------471 472One of the main responsibilities of the ``PassManager`` is to make sure that473passes interact with each other correctly. Because ``PassManager`` tries to474:ref:`optimize the execution of passes <writing-an-llvm-pass-passmanager>` it475must know how the passes interact with each other and what dependencies exist476between the various passes. To track this, each pass can declare the set of477passes that are required to be executed before the current pass, and the passes478which are invalidated by the current pass.479 480Typically this functionality is used to require that analysis results are481computed before your pass is run. Running arbitrary transformation passes can482invalidate the computed analysis results, which is what the invalidation set483specifies. If a pass does not implement the :ref:`getAnalysisUsage484<writing-an-llvm-pass-getAnalysisUsage>` method, it defaults to not having any485prerequisite passes, and invalidating **all** other passes.486 487.. _writing-an-llvm-pass-getAnalysisUsage:488 489The ``getAnalysisUsage`` method490^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^491 492.. code-block:: c++493 494 virtual void getAnalysisUsage(AnalysisUsage &Info) const;495 496By implementing the ``getAnalysisUsage`` method, the required and invalidated497sets may be specified for your transformation. The implementation should fill498in the `AnalysisUsage499<https://llvm.org/doxygen/classllvm_1_1AnalysisUsage.html>`_ object with500information about which passes are required and not invalidated. To do this, a501pass may call any of the following methods on the ``AnalysisUsage`` object:502 503The ``AnalysisUsage::addRequired<>`` and ``AnalysisUsage::addRequiredTransitive<>`` methods504^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^505 506If your pass requires a previous pass to be executed (an analysis for example),507it can use one of these methods to arrange for it to be run before your pass.508LLVM has many different types of analyses and passes that can be required,509spanning the range from ``DominatorSet`` to ``BreakCriticalEdges``. Requiring510``BreakCriticalEdges``, for example, guarantees that there will be no critical511edges in the CFG when your pass has been run.512 513Some analyses chain to other analyses to do their job. For example, an514`AliasAnalysis <AliasAnalysis.html>`_ implementation is required to :ref:`chain515<aliasanalysis-chaining>` to other alias analysis passes. In cases where516analyses chain, the ``addRequiredTransitive`` method should be used instead of517the ``addRequired`` method. This informs the ``PassManager`` that the518transitively required pass should be alive as long as the requiring pass is.519 520The ``AnalysisUsage::addPreserved<>`` method521^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^522 523One of the jobs of the ``PassManager`` is to optimize how and when analyses are524run. In particular, it attempts to avoid recomputing data unless it needs to.525For this reason, passes are allowed to declare that they preserve (i.e., they526don't invalidate) an existing analysis if it's available. For example, a527simple constant folding pass would not modify the CFG, so it can't possibly528affect the results of dominator analysis. By default, all passes are assumed529to invalidate all others.530 531The ``AnalysisUsage`` class provides several methods which are useful in532certain circumstances that are related to ``addPreserved``. In particular, the533``setPreservesAll`` method can be called to indicate that the pass does not534modify the LLVM program at all (which is true for analyses), and the535``setPreservesCFG`` method can be used by transformations that change536instructions in the program but do not modify the CFG or terminator537instructions.538 539``addPreserved`` is particularly useful for transformations like540``BreakCriticalEdges``. This pass knows how to update a small set of loop and541dominator related analyses if they exist, so it can preserve them, despite the542fact that it hacks on the CFG.543 544Example implementations of ``getAnalysisUsage``545^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^546 547.. code-block:: c++548 549 // This example modifies the program, but does not modify the CFG550 void LICM::getAnalysisUsage(AnalysisUsage &AU) const {551 AU.setPreservesCFG();552 AU.addRequired<LoopInfoWrapperPass>();553 }554 555.. _writing-an-llvm-pass-getAnalysis:556 557The ``getAnalysis<>`` and ``getAnalysisIfAvailable<>`` methods558^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^559 560The ``Pass::getAnalysis<>`` method is automatically inherited by your class,561providing you with access to the passes that you declared that you required562with the :ref:`getAnalysisUsage <writing-an-llvm-pass-getAnalysisUsage>`563method. It takes a single template argument that specifies which pass class564you want, and returns a reference to that pass. For example:565 566.. code-block:: c++567 568 bool LICM::runOnFunction(Function &F) {569 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();570 //...571 }572 573This method call returns a reference to the pass desired. You may get a574runtime assertion failure if you attempt to get an analysis that you did not575declare as required in your :ref:`getAnalysisUsage576<writing-an-llvm-pass-getAnalysisUsage>` implementation. This method can be577called by your ``run*`` method implementation, or by any other local method578invoked by your ``run*`` method.579 580A module level pass can use function level analysis info using this interface.581For example:582 583.. code-block:: c++584 585 bool ModuleLevelPass::runOnModule(Module &M) {586 //...587 DominatorTree &DT = getAnalysis<DominatorTree>(Func);588 //...589 }590 591In above example, ``runOnFunction`` for ``DominatorTree`` is called by pass592manager before returning a reference to the desired pass.593 594If your pass is capable of updating analyses if they exist (e.g.,595``BreakCriticalEdges``, as described above), you can use the596``getAnalysisIfAvailable`` method, which returns a pointer to the analysis if597it is active. For example:598 599.. code-block:: c++600 601 if (DominatorSet *DS = getAnalysisIfAvailable<DominatorSet>()) {602 // A DominatorSet is active. This code will update it.603 }604 605Pass Statistics606===============607 608The `Statistic <https://llvm.org/doxygen/Statistic_8h_source.html>`_ class is609designed to be an easy way to expose various success metrics from passes.610These statistics are printed at the end of a run, when the :option:`-stats`611command line option is enabled on the command line. See the :ref:`Statistics612section <Statistic>` in the Programmer's Manual for details.613 614.. _writing-an-llvm-pass-passmanager:615 616What PassManager does617---------------------618 619The `PassManager <https://llvm.org/doxygen/PassManager_8h_source.html>`_ `class620<https://llvm.org/doxygen/classllvm_1_1PassManager.html>`_ takes a list of621passes, ensures their :ref:`prerequisites <writing-an-llvm-pass-interaction>`622are set up correctly, and then schedules passes to run efficiently. All of the623LLVM tools that run passes use the PassManager for execution of these passes.624 625The PassManager does two main things to try to reduce the execution time of a626series of passes:627 628#. **Share analysis results.** The ``PassManager`` attempts to avoid629 recomputing analysis results as much as possible. This means keeping track630 of which analyses are available already, which analyses get invalidated, and631 which analyses are needed to be run for a pass. An important part of work632 is that the ``PassManager`` tracks the exact lifetime of all analysis633 results, allowing it to :ref:`free memory634 <writing-an-llvm-pass-releaseMemory>` allocated to holding analysis results635 as soon as they are no longer needed.636 637#. **Pipeline the execution of passes on the program.** The ``PassManager``638 attempts to get better cache and memory usage behavior out of a series of639 passes by pipelining the passes together. This means that, given a series640 of consecutive :ref:`FunctionPass <writing-an-llvm-pass-FunctionPass>`, it641 will execute all of the :ref:`FunctionPass642 <writing-an-llvm-pass-FunctionPass>` on the first function, then all of the643 :ref:`FunctionPasses <writing-an-llvm-pass-FunctionPass>` on the second644 function, etc... until the entire program has been run through the passes.645 646 This improves the cache behavior of the compiler, because it is only647 touching the LLVM program representation for a single function at a time,648 instead of traversing the entire program. It reduces the memory consumption649 of compiler, because, for example, only one `DominatorSet650 <https://llvm.org/doxygen/classllvm_1_1DominatorSet.html>`_ needs to be651 calculated at a time.652 653The effectiveness of the ``PassManager`` is influenced directly by how much654information it has about the behaviors of the passes it is scheduling. For655example, the "preserved" set is intentionally conservative in the face of an656unimplemented :ref:`getAnalysisUsage <writing-an-llvm-pass-getAnalysisUsage>`657method. Not implementing when it should be implemented will have the effect of658not allowing any analysis results to live across the execution of your pass.659 660The ``PassManager`` class exposes a ``--debug-pass`` command line options that661is useful for debugging pass execution, seeing how things work, and diagnosing662when you should be preserving more analyses than you currently are. (To get663information about all of the variants of the ``--debug-pass`` option, just type664"``llc -help-hidden``").665 666By using the --debug-pass=Structure option, for example, we can see inspect the667default optimization pipelines, e.g. (the output has been trimmed):668 669.. code-block:: console670 671 $ llc -mtriple=arm64-- -O3 -debug-pass=Structure file.ll > /dev/null672 (...)673 ModulePass Manager674 Pre-ISel Intrinsic Lowering675 FunctionPass Manager676 Expand large div/rem677 Expand fp678 Expand Atomic instructions679 SVE intrinsics optimizations680 FunctionPass Manager681 Dominator Tree Construction682 FunctionPass Manager683 Simplify the CFG684 Dominator Tree Construction685 Natural Loop Information686 Canonicalize natural loops687 (...)688 689.. _writing-an-llvm-pass-releaseMemory:690 691The ``releaseMemory`` method692^^^^^^^^^^^^^^^^^^^^^^^^^^^^693 694.. code-block:: c++695 696 virtual void releaseMemory();697 698The ``PassManager`` automatically determines when to compute analysis results,699and how long to keep them around for. Because the lifetime of the pass object700itself is effectively the entire duration of the compilation process, we need701some way to free analysis results when they are no longer useful. The702``releaseMemory`` virtual method is the way to do this.703 704If you are writing an analysis or any other pass that retains a significant705amount of state (for use by another pass which "requires" your pass and uses706the :ref:`getAnalysis <writing-an-llvm-pass-getAnalysis>` method) you should707implement ``releaseMemory`` to, well, release the memory allocated to maintain708this internal state. This method is called after the ``run*`` method for the709class, before the next call of ``run*`` in your pass.710 711Registering dynamically loaded passes712=====================================713 714*Size matters* when constructing production quality tools using LLVM, both for715the purposes of distribution, and for regulating the resident code size when716running on the target system. Therefore, it becomes desirable to selectively717use some passes, while omitting others and maintain the flexibility to change718configurations later on. You want to be able to do all this, and, provide719feedback to the user. This is where pass registration comes into play.720 721The fundamental mechanisms for pass registration are the722``MachinePassRegistry`` class and subclasses of ``MachinePassRegistryNode``.723 724An instance of ``MachinePassRegistry`` is used to maintain a list of725``MachinePassRegistryNode`` objects. This instance maintains the list and726communicates additions and deletions to the command line interface.727 728An instance of ``MachinePassRegistryNode`` subclass is used to maintain729information provided about a particular pass. This information includes the730command line name, the command help string and the address of the function used731to create an instance of the pass. A global static constructor of one of these732instances *registers* with a corresponding ``MachinePassRegistry``, the static733destructor *unregisters*. Thus a pass that is statically linked in the tool734will be registered at start up. A dynamically loaded pass will register on735load and unregister at unload.736 737Using existing registries738-------------------------739 740There are predefined registries to track instruction scheduling741(``RegisterScheduler``) and register allocation (``RegisterRegAlloc``) machine742passes. Here we will describe how to *register* a register allocator machine743pass.744 745Implement your register allocator machine pass. In your register allocator746``.cpp`` file add the following include:747 748.. code-block:: c++749 750 #include "llvm/CodeGen/RegAllocRegistry.h"751 752Also in your register allocator ``.cpp`` file, define a creator function in the753form:754 755.. code-block:: c++756 757 FunctionPass *createMyRegisterAllocator() {758 return new MyRegisterAllocator();759 }760 761Note that the signature of this function should match the type of762``RegisterRegAlloc::FunctionPassCtor``. In the same file add the "installing"763declaration, in the form:764 765.. code-block:: c++766 767 static RegisterRegAlloc myRegAlloc("myregalloc",768 "my register allocator help string",769 createMyRegisterAllocator);770 771Note the two spaces prior to the help string produces a tidy result on the772:option:`-help` query.773 774.. code-block:: console775 776 $ llc -help777 ...778 -regalloc - Register allocator to use (default=linearscan)779 =linearscan - linear scan register allocator780 =local - local register allocator781 =simple - simple register allocator782 =myregalloc - my register allocator help string783 ...784 785And that's it. The user is now free to use ``-regalloc=myregalloc`` as an786option. Registering instruction schedulers is similar except use the787``RegisterScheduler`` class. Note that the788``RegisterScheduler::FunctionPassCtor`` is significantly different from789``RegisterRegAlloc::FunctionPassCtor``.790 791To force the load/linking of your register allocator into the792:program:`llc`/:program:`lli` tools, add your creator function's global793declaration to ``Passes.h`` and add a "pseudo" call line to794``llvm/Codegen/LinkAllCodegenComponents.h``.795 796Creating new registries797-----------------------798 799The easiest way to get started is to clone one of the existing registries; we800recommend ``llvm/CodeGen/RegAllocRegistry.h``. The key things to modify are801the class name and the ``FunctionPassCtor`` type.802 803Then you need to declare the registry. Example: if your pass registry is804``RegisterMyPasses`` then define:805 806.. code-block:: c++807 808 MachinePassRegistry<RegisterMyPasses::FunctionPassCtor> RegisterMyPasses::Registry;809 810And finally, declare the command line option for your passes. Example:811 812.. code-block:: c++813 814 cl::opt<RegisterMyPasses::FunctionPassCtor, false,815 RegisterPassParser<RegisterMyPasses> >816 MyPassOpt("mypass",817 cl::init(&createDefaultMyPass),818 cl::desc("my pass option help"));819 820Here the command option is "``mypass``", with ``createDefaultMyPass`` as the821default creator.822 823Using GDB with dynamically loaded passes824----------------------------------------825 826Unfortunately, using GDB with dynamically loaded passes is not as easy as it827should be. First of all, you can't set a breakpoint in a shared object that828has not been loaded yet, and second of all there are problems with inlined829functions in shared objects. Here are some suggestions to debugging your pass830with GDB.831 832For sake of discussion, I'm going to assume that you are debugging a833transformation invoked by :program:`opt`, although nothing described here834depends on that.835 836Setting a breakpoint in your pass837^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^838 839First thing you do is start gdb on the opt process:840 841.. code-block:: console842 843 $ gdb opt844 GNU gdb 5.0845 Copyright 2000 Free Software Foundation, Inc.846 GDB is free software, covered by the GNU General Public License, and you are847 welcome to change it and/or distribute copies of it under certain conditions.848 Type "show copying" to see the conditions.849 There is absolutely no warranty for GDB. Type "show warranty" for details.850 This GDB was configured as "sparc-sun-solaris2.6"...851 (gdb)852 853Note that :program:`opt` has a lot of debugging information in it, so it takes854time to load. Be patient. Since we cannot set a breakpoint in our pass yet855(the shared object isn't loaded until runtime), we must execute the process,856and have it stop before it invokes our pass, but after it has loaded the shared857object. The most foolproof way of doing this is to set a breakpoint in858``PassManager::run`` and then run the process with the arguments you want:859 860.. code-block:: console861 862 $ (gdb) break llvm::PassManager::run863 Breakpoint 1 at 0x2413bc: file Pass.cpp, line 70.864 (gdb) run test.bc -load $(LLVMTOP)/llvm/Debug+Asserts/lib/[libname].so -[passoption]865 Starting program: opt test.bc -load $(LLVMTOP)/llvm/Debug+Asserts/lib/[libname].so -[passoption]866 Breakpoint 1, PassManager::run (this=0xffbef174, M=@0x70b298) at Pass.cpp:70867 70 bool PassManager::run(Module &M) { return PM->run(M); }868 (gdb)869 870Once the :program:`opt` stops in the ``PassManager::run`` method you are now871free to set breakpoints in your pass so that you can trace through execution or872do other standard debugging stuff.873 874Miscellaneous Problems875^^^^^^^^^^^^^^^^^^^^^^876 877Once you have the basics down, there are a couple of problems that GDB has,878some with solutions, some without.879 880* Inline functions have bogus stack information. In general, GDB does a pretty881 good job getting stack traces and stepping through inline functions. When a882 pass is dynamically loaded however, it somehow completely loses this883 capability. The only solution I know of is to de-inline a function (move it884 from the body of a class to a ``.cpp`` file).885 886* Restarting the program breaks breakpoints. After following the information887 above, you have succeeded in getting some breakpoints planted in your pass.888 Next thing you know, you restart the program (i.e., you type "``run``" again),889 and you start getting errors about breakpoints being unsettable. The only890 way I have found to "fix" this problem is to delete the breakpoints that are891 already set in your pass, run the program, and re-set the breakpoints once892 execution stops in ``PassManager::run``.893 894Hopefully these tips will help with common case debugging situations. If you'd895like to contribute some tips of your own, just contact `Chris896<mailto:sabre@nondot.org>`_.897