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