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