Andrew Kaylor | 3aeda4f | 2016-08-26 23:11:48 +0000 | [diff] [blame] | 1 | ==================================================== |
| 2 | Using -opt-bisect-limit to debug optimization errors |
| 3 | ==================================================== |
| 4 | .. contents:: |
| 5 | :local: |
| 6 | :depth: 1 |
| 7 | |
| 8 | Introduction |
| 9 | ============ |
| 10 | |
| 11 | The -opt-bisect-limit option provides a way to disable all optimization passes |
| 12 | above a specified limit without modifying the way in which the Pass Managers |
| 13 | are populated. The intention of this option is to assist in tracking down |
| 14 | problems where incorrect transformations during optimization result in incorrect |
| 15 | run-time behavior. |
| 16 | |
| 17 | This feature is implemented on an opt-in basis. Passes which can be safely |
| 18 | skipped while still allowing correct code generation call a function to |
| 19 | check the opt-bisect limit before performing optimizations. Passes which |
| 20 | either must be run or do not modify the IR do not perform this check and are |
| 21 | therefore never skipped. Generally, this means analysis passes, passes |
| 22 | that are run at CodeGenOpt::None and passes which are required for register |
| 23 | allocation. |
| 24 | |
| 25 | The -opt-bisect-limit option can be used with any tool, including front ends |
| 26 | such as clang, that uses the core LLVM library for optimization and code |
| 27 | generation. The exact syntax for invoking the option is discussed below. |
| 28 | |
| 29 | This feature is not intended to replace other debugging tools such as bugpoint. |
| 30 | Rather it provides an alternate course of action when reproducing the problem |
| 31 | requires a complex build infrastructure that would make using bugpoint |
| 32 | impractical or when reproducing the failure requires a sequence of |
| 33 | transformations that is difficult to replicate with tools like opt and llc. |
| 34 | |
| 35 | |
| 36 | Getting Started |
| 37 | =============== |
| 38 | |
| 39 | The -opt-bisect-limit command line option can be passed directly to tools such |
| 40 | as opt, llc and lli. The syntax is as follows: |
| 41 | |
| 42 | :: |
| 43 | |
| 44 | <tool name> [other options] -opt-bisect-limit=<limit> |
| 45 | |
| 46 | If a value of -1 is used the tool will perform all optimizations but a message |
| 47 | will be printed to stderr for each optimization that could be skipped |
| 48 | indicating the index value that is associated with that optimization. To skip |
| 49 | optimizations, pass the value of the last optimization to be performed as the |
| 50 | opt-bisect-limit. All optimizations with a higher index value will be skipped. |
| 51 | |
| 52 | In order to use the -opt-bisect-limit option with a driver that provides a |
| 53 | wrapper around the LLVM core library, an additional prefix option may be |
| 54 | required, as defined by the driver. For example, to use this option with |
| 55 | clang, the "-mllvm" prefix must be used. A typical clang invocation would look |
| 56 | like this: |
| 57 | |
| 58 | :: |
| 59 | |
| 60 | clang -O2 -mllvm -opt-bisect-limit=256 my_file.c |
| 61 | |
| 62 | The -opt-bisect-limit option may also be applied to link-time optimizations by |
Mehdi Amini | a826244 | 2017-02-10 07:21:06 +0000 | [diff] [blame] | 63 | using a prefix to indicate that this is a plug-in option for the linker. The |
Andrew Kaylor | 3aeda4f | 2016-08-26 23:11:48 +0000 | [diff] [blame] | 64 | following syntax will set a bisect limit for LTO transformations: |
| 65 | |
| 66 | :: |
| 67 | |
Mehdi Amini | f1423e8 | 2017-02-10 17:16:00 +0000 | [diff] [blame] | 68 | # When using lld, or ld64 (macOS) |
Mehdi Amini | a826244 | 2017-02-10 07:21:06 +0000 | [diff] [blame] | 69 | clang -flto -Wl,-mllvm,-opt-bisect-limit=256 my_file.o my_other_file.o |
Mehdi Amini | f1423e8 | 2017-02-10 17:16:00 +0000 | [diff] [blame] | 70 | # When using Gold |
| 71 | clang -flto -Wl,-plugin-opt,-opt-bisect-limit=256 my_file.o my_other_file.o |
Andrew Kaylor | 3aeda4f | 2016-08-26 23:11:48 +0000 | [diff] [blame] | 72 | |
| 73 | LTO passes are run by a library instance invoked by the linker. Therefore any |
| 74 | passes run in the primary driver compilation phase are not affected by options |
| 75 | passed via '-Wl,-plugin-opt' and LTO passes are not affected by options |
| 76 | passed to the driver-invoked LLVM invocation via '-mllvm'. |
| 77 | |
| 78 | |
| 79 | Bisection Index Values |
| 80 | ====================== |
| 81 | |
| 82 | The granularity of the optimizations associated with a single index value is |
| 83 | variable. Depending on how the optimization pass has been instrumented the |
| 84 | value may be associated with as much as all transformations that would have |
| 85 | been performed by an optimization pass on an IR unit for which it is invoked |
| 86 | (for instance, during a single call of runOnFunction for a FunctionPass) or as |
| 87 | little as a single transformation. The index values may also be nested so that |
| 88 | if an invocation of the pass is not skipped individual transformations within |
| 89 | that invocation may still be skipped. |
| 90 | |
| 91 | The order of the values assigned is guaranteed to remain stable and consistent |
| 92 | from one run to the next up to and including the value specified as the limit. |
| 93 | Above the limit value skipping of optimizations can cause a change in the |
| 94 | numbering, but because all optimizations above the limit are skipped this |
| 95 | is not a problem. |
| 96 | |
| 97 | When an opt-bisect index value refers to an entire invocation of the run |
| 98 | function for a pass, the pass will query whether or not it should be skipped |
| 99 | each time it is invoked and each invocation will be assigned a unique value. |
| 100 | For example, if a FunctionPass is used with a module containing three functions |
| 101 | a different index value will be assigned to the pass for each of the functions |
| 102 | as the pass is run. The pass may be run on two functions but skipped for the |
| 103 | third. |
| 104 | |
| 105 | If the pass internally performs operations on a smaller IR unit the pass must be |
| 106 | specifically instrumented to enable bisection at this finer level of granularity |
| 107 | (see below for details). |
| 108 | |
| 109 | |
| 110 | Example Usage |
| 111 | ============= |
| 112 | |
| 113 | .. code-block:: console |
| 114 | |
| 115 | $ opt -O2 -o test-opt.bc -opt-bisect-limit=16 test.ll |
| 116 | |
| 117 | BISECT: running pass (1) Simplify the CFG on function (g) |
| 118 | BISECT: running pass (2) SROA on function (g) |
| 119 | BISECT: running pass (3) Early CSE on function (g) |
| 120 | BISECT: running pass (4) Infer set function attributes on module (test.ll) |
| 121 | BISECT: running pass (5) Interprocedural Sparse Conditional Constant Propagation on module (test.ll) |
| 122 | BISECT: running pass (6) Global Variable Optimizer on module (test.ll) |
| 123 | BISECT: running pass (7) Promote Memory to Register on function (g) |
| 124 | BISECT: running pass (8) Dead Argument Elimination on module (test.ll) |
| 125 | BISECT: running pass (9) Combine redundant instructions on function (g) |
| 126 | BISECT: running pass (10) Simplify the CFG on function (g) |
| 127 | BISECT: running pass (11) Remove unused exception handling info on SCC (<<null function>>) |
| 128 | BISECT: running pass (12) Function Integration/Inlining on SCC (<<null function>>) |
| 129 | BISECT: running pass (13) Deduce function attributes on SCC (<<null function>>) |
| 130 | BISECT: running pass (14) Remove unused exception handling info on SCC (f) |
| 131 | BISECT: running pass (15) Function Integration/Inlining on SCC (f) |
| 132 | BISECT: running pass (16) Deduce function attributes on SCC (f) |
| 133 | BISECT: NOT running pass (17) Remove unused exception handling info on SCC (g) |
| 134 | BISECT: NOT running pass (18) Function Integration/Inlining on SCC (g) |
| 135 | BISECT: NOT running pass (19) Deduce function attributes on SCC (g) |
| 136 | BISECT: NOT running pass (20) SROA on function (g) |
| 137 | BISECT: NOT running pass (21) Early CSE on function (g) |
| 138 | BISECT: NOT running pass (22) Speculatively execute instructions if target has divergent branches on function (g) |
| 139 | ... etc. ... |
| 140 | |
| 141 | |
| 142 | Pass Skipping Implementation |
| 143 | ============================ |
| 144 | |
| 145 | The -opt-bisect-limit implementation depends on individual passes opting in to |
| 146 | the opt-bisect process. The OptBisect object that manages the process is |
| 147 | entirely passive and has no knowledge of how any pass is implemented. When a |
| 148 | pass is run if the pass may be skipped, it should call the OptBisect object to |
| 149 | see if it should be skipped. |
| 150 | |
| 151 | The OptBisect object is intended to be accessed through LLVMContext and each |
| 152 | Pass base class contains a helper function that abstracts the details in order |
| 153 | to make this check uniform across all passes. These helper functions are: |
| 154 | |
| 155 | .. code-block:: c++ |
| 156 | |
| 157 | bool ModulePass::skipModule(Module &M); |
| 158 | bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC); |
| 159 | bool FunctionPass::skipFunction(const Function &F); |
Andrew Kaylor | 3aeda4f | 2016-08-26 23:11:48 +0000 | [diff] [blame] | 160 | bool LoopPass::skipLoop(const Loop *L); |
| 161 | |
| 162 | A MachineFunctionPass should use FunctionPass::skipFunction() as such: |
| 163 | |
| 164 | .. code-block:: c++ |
| 165 | |
| 166 | bool MyMachineFunctionPass::runOnMachineFunction(Function &MF) { |
| 167 | if (skipFunction(*MF.getFunction()) |
Craig Topper | 0527717 | 2018-07-27 06:54:13 +0000 | [diff] [blame] | 168 | return false; |
Andrew Kaylor | 3aeda4f | 2016-08-26 23:11:48 +0000 | [diff] [blame] | 169 | // Otherwise, run the pass normally. |
| 170 | } |
| 171 | |
| 172 | In addition to checking with the OptBisect class to see if the pass should be |
| 173 | skipped, the skipFunction(), skipLoop() and skipBasicBlock() helper functions |
| 174 | also look for the presence of the "optnone" function attribute. The calling |
| 175 | pass will be unable to determine whether it is being skipped because the |
| 176 | "optnone" attribute is present or because the opt-bisect-limit has been |
| 177 | reached. This is desirable because the behavior should be the same in either |
| 178 | case. |
| 179 | |
| 180 | The majority of LLVM passes which can be skipped have already been instrumented |
| 181 | in the manner described above. If you are adding a new pass or believe you |
| 182 | have found a pass which is not being included in the opt-bisect process but |
| 183 | should be, you can add it as described above. |
| 184 | |
| 185 | |
| 186 | Adding Finer Granularity |
| 187 | ======================== |
| 188 | |
| 189 | Once the pass in which an incorrect transformation is performed has been |
| 190 | determined, it may be useful to perform further analysis in order to determine |
Daniel Berlin | 14f5c47 | 2017-03-11 01:41:03 +0000 | [diff] [blame] | 191 | which specific transformation is causing the problem. Debug counters |
| 192 | can be used for this purpose. |