klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Optimize.cpp
Go to the documentation of this file.
1 // FIXME: This file is a bastard child of opt.cpp and llvm-ld's
2 // Optimize.cpp. This stuff should live in common code.
3 
4 
5 //===- Optimize.cpp - Optimize a complete program -------------------------===//
6 //
7 // The LLVM Compiler Infrastructure
8 //
9 // This file is distributed under the University of Illinois Open Source
10 // License. See LICENSE.TXT for details.
11 //
12 //===----------------------------------------------------------------------===//
13 //
14 // This file implements all optimization of the linked module for llvm-ld.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "klee/Config/Version.h"
19 #include "llvm/PassManager.h"
20 #include "llvm/Analysis/Passes.h"
21 #include "llvm/Analysis/LoopPass.h"
22 #include "llvm/Analysis/Verifier.h"
23 #include "llvm/Support/CommandLine.h"
24 #include "llvm/Support/DynamicLibrary.h"
25 
26 #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 3)
27 #include "llvm/IR/Module.h"
28 #include "llvm/IR/DataLayout.h"
29 #else
30 #include "llvm/Module.h"
31 #if LLVM_VERSION_CODE <= LLVM_VERSION(3, 1)
32 #include "llvm/Target/TargetData.h"
33 #else
34 #include "llvm/DataLayout.h"
35 #endif
36 #endif
37 
38 #include "llvm/Target/TargetMachine.h"
39 #include "llvm/Transforms/IPO.h"
40 #include "llvm/Transforms/Scalar.h"
41 #include "llvm/Support/PassNameParser.h"
42 #include "llvm/Support/PluginLoader.h"
43 using namespace llvm;
44 
45 #if 0
46 // Pass Name Options as generated by the PassNameParser
47 static cl::list<const PassInfo*, bool, PassNameParser>
48  OptimizationList(cl::desc("Optimizations available:"));
49 #endif
50 
51 // Don't verify at the end
52 static cl::opt<bool> DontVerify("disable-verify", cl::ReallyHidden);
53 
54 static cl::opt<bool> DisableInline("disable-inlining",
55  cl::desc("Do not run the inliner pass"));
56 
57 static cl::opt<bool>
58 DisableOptimizations("disable-opt",
59  cl::desc("Do not run any optimization passes"));
60 
61 static cl::opt<bool> DisableInternalize("disable-internalize",
62  cl::desc("Do not mark all symbols as internal"));
63 
64 static cl::opt<bool> VerifyEach("verify-each",
65  cl::desc("Verify intermediate results of all passes"));
66 
67 static cl::alias ExportDynamic("export-dynamic",
68  cl::aliasopt(DisableInternalize),
69  cl::desc("Alias for -disable-internalize"));
70 
71 static cl::opt<bool> Strip("strip-all",
72  cl::desc("Strip all symbol info from executable"));
73 
74 static cl::alias A0("s", cl::desc("Alias for --strip-all"),
75  cl::aliasopt(Strip));
76 
77 static cl::opt<bool> StripDebug("strip-debug",
78  cl::desc("Strip debugger symbol info from executable"));
79 
80 static cl::alias A1("S", cl::desc("Alias for --strip-debug"),
81  cl::aliasopt(StripDebug));
82 
83 // A utility function that adds a pass to the pass manager but will also add
84 // a verifier pass after if we're supposed to verify.
85 static inline void addPass(PassManager &PM, Pass *P) {
86  // Add the pass to the pass manager...
87  PM.add(P);
88 
89  // If we are verifying all of the intermediate steps, add the verifier...
90  if (VerifyEach)
91  PM.add(createVerifierPass());
92 }
93 
94 namespace llvm {
95 
96 
97 static void AddStandardCompilePasses(PassManager &PM) {
98  PM.add(createVerifierPass()); // Verify that input is correct
99 
100 #if LLVM_VERSION_CODE < LLVM_VERSION(3, 0)
101  addPass(PM, createLowerSetJmpPass()); // Lower llvm.setjmp/.longjmp
102 #endif
103 
104  // If the -strip-debug command line option was specified, do it.
105  if (StripDebug)
106  addPass(PM, createStripSymbolsPass(true));
107 
108  if (DisableOptimizations) return;
109 
110  addPass(PM, createCFGSimplificationPass()); // Clean up disgusting code
111  addPass(PM, createPromoteMemoryToRegisterPass());// Kill useless allocas
112  addPass(PM, createGlobalOptimizerPass()); // Optimize out global vars
113  addPass(PM, createGlobalDCEPass()); // Remove unused fns and globs
114  addPass(PM, createIPConstantPropagationPass());// IP Constant Propagation
115  addPass(PM, createDeadArgEliminationPass()); // Dead argument elimination
116  addPass(PM, createInstructionCombiningPass()); // Clean up after IPCP & DAE
117  addPass(PM, createCFGSimplificationPass()); // Clean up after IPCP & DAE
118 
119  addPass(PM, createPruneEHPass()); // Remove dead EH info
120  addPass(PM, createFunctionAttrsPass()); // Deduce function attrs
121 
122  if (!DisableInline)
123  addPass(PM, createFunctionInliningPass()); // Inline small functions
124  addPass(PM, createArgumentPromotionPass()); // Scalarize uninlined fn args
125 
126 #if LLVM_VERSION_CODE < LLVM_VERSION(3, 4)
127  addPass(PM, createSimplifyLibCallsPass()); // Library Call Optimizations
128 #endif
129  addPass(PM, createInstructionCombiningPass()); // Cleanup for scalarrepl.
130  addPass(PM, createJumpThreadingPass()); // Thread jumps.
131  addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs
132  addPass(PM, createScalarReplAggregatesPass()); // Break up aggregate allocas
133  addPass(PM, createInstructionCombiningPass()); // Combine silly seq's
134 
135  addPass(PM, createTailCallEliminationPass()); // Eliminate tail calls
136  addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs
137  addPass(PM, createReassociatePass()); // Reassociate expressions
138  addPass(PM, createLoopRotatePass());
139  addPass(PM, createLICMPass()); // Hoist loop invariants
140  addPass(PM, createLoopUnswitchPass()); // Unswitch loops.
141  // FIXME : Removing instcombine causes nestedloop regression.
142  addPass(PM, createInstructionCombiningPass());
143  addPass(PM, createIndVarSimplifyPass()); // Canonicalize indvars
144  addPass(PM, createLoopDeletionPass()); // Delete dead loops
145  addPass(PM, createLoopUnrollPass()); // Unroll small loops
146  addPass(PM, createInstructionCombiningPass()); // Clean up after the unroller
147  addPass(PM, createGVNPass()); // Remove redundancies
148  addPass(PM, createMemCpyOptPass()); // Remove memcpy / form memset
149  addPass(PM, createSCCPPass()); // Constant prop with SCCP
150 
151  // Run instcombine after redundancy elimination to exploit opportunities
152  // opened up by them.
153  addPass(PM, createInstructionCombiningPass());
154 
155  addPass(PM, createDeadStoreEliminationPass()); // Delete dead stores
156  addPass(PM, createAggressiveDCEPass()); // Delete dead instructions
157  addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs
158  addPass(PM, createStripDeadPrototypesPass()); // Get rid of dead prototypes
159 #if LLVM_VERSION_CODE < LLVM_VERSION(3, 0)
160  addPass(PM, createDeadTypeEliminationPass()); // Eliminate dead types
161 #endif
162  addPass(PM, createConstantMergePass()); // Merge dup global constants
163 }
164 
168 void Optimize(Module* M) {
169 
170  // Instantiate the pass manager to organize the passes.
171  PassManager Passes;
172 
173  // If we're verifying, start off with a verification pass.
174  if (VerifyEach)
175  Passes.add(createVerifierPass());
176 
177 #if LLVM_VERSION_CODE <= LLVM_VERSION(3, 1)
178  // Add an appropriate TargetData instance for this module...
179  addPass(Passes, new TargetData(M));
180 #else
181  // Add an appropriate DataLayout instance for this module...
182  addPass(Passes, new DataLayout(M));
183 #endif
184 
185  // DWD - Run the opt standard pass list as well.
186  AddStandardCompilePasses(Passes);
187 
188  if (!DisableOptimizations) {
189  // Now that composite has been compiled, scan through the module, looking
190  // for a main function. If main is defined, mark all other functions
191  // internal.
192  if (!DisableInternalize) {
193 #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 2)
194  ModulePass *pass = createInternalizePass(std::vector<const char *>(1, "main"));
195 #else
196  ModulePass *pass = createInternalizePass(true);
197 #endif
198  addPass(Passes, pass);
199  }
200 
201  // Propagate constants at call sites into the functions they call. This
202  // opens opportunities for globalopt (and inlining) by substituting function
203  // pointers passed as arguments to direct uses of functions.
204  addPass(Passes, createIPSCCPPass());
205 
206  // Now that we internalized some globals, see if we can hack on them!
207  addPass(Passes, createGlobalOptimizerPass());
208 
209  // Linking modules together can lead to duplicated global constants, only
210  // keep one copy of each constant...
211  addPass(Passes, createConstantMergePass());
212 
213  // Remove unused arguments from functions...
214  addPass(Passes, createDeadArgEliminationPass());
215 
216  // Reduce the code after globalopt and ipsccp. Both can open up significant
217  // simplification opportunities, and both can propagate functions through
218  // function pointers. When this happens, we often have to resolve varargs
219  // calls, etc, so let instcombine do this.
220  addPass(Passes, createInstructionCombiningPass());
221 
222  if (!DisableInline)
223  addPass(Passes, createFunctionInliningPass()); // Inline small functions
224 
225  addPass(Passes, createPruneEHPass()); // Remove dead EH info
226  addPass(Passes, createGlobalOptimizerPass()); // Optimize globals again.
227  addPass(Passes, createGlobalDCEPass()); // Remove dead functions
228 
229  // If we didn't decide to inline a function, check to see if we can
230  // transform it to pass arguments by value instead of by reference.
231  addPass(Passes, createArgumentPromotionPass());
232 
233  // The IPO passes may leave cruft around. Clean up after them.
234  addPass(Passes, createInstructionCombiningPass());
235  addPass(Passes, createJumpThreadingPass()); // Thread jumps.
236  addPass(Passes, createScalarReplAggregatesPass()); // Break up allocas
237 
238  // Run a few AA driven optimizations here and now, to cleanup the code.
239  addPass(Passes, createFunctionAttrsPass()); // Add nocapture
240  addPass(Passes, createGlobalsModRefPass()); // IP alias analysis
241 
242  addPass(Passes, createLICMPass()); // Hoist loop invariants
243  addPass(Passes, createGVNPass()); // Remove redundancies
244  addPass(Passes, createMemCpyOptPass()); // Remove dead memcpy's
245  addPass(Passes, createDeadStoreEliminationPass()); // Nuke dead stores
246 
247  // Cleanup and simplify the code after the scalar optimizations.
248  addPass(Passes, createInstructionCombiningPass());
249 
250  addPass(Passes, createJumpThreadingPass()); // Thread jumps.
251  addPass(Passes, createPromoteMemoryToRegisterPass()); // Cleanup jumpthread.
252 
253  // Delete basic blocks, which optimization passes may have killed...
254  addPass(Passes, createCFGSimplificationPass());
255 
256  // Now that we have optimized the program, discard unreachable functions...
257  addPass(Passes, createGlobalDCEPass());
258  }
259 
260  // If the -s or -S command line options were specified, strip the symbols out
261  // of the resulting program to make it smaller. -s and -S are GNU ld options
262  // that we are supporting; they alias -strip-all and -strip-debug.
263  if (Strip || StripDebug)
264  addPass(Passes, createStripSymbolsPass(StripDebug && !Strip));
265 
266 #if 0
267  // Create a new optimization pass for each one specified on the command line
268  std::auto_ptr<TargetMachine> target;
269  for (unsigned i = 0; i < OptimizationList.size(); ++i) {
270  const PassInfo *Opt = OptimizationList[i];
271  if (Opt->getNormalCtor())
272  addPass(Passes, Opt->getNormalCtor()());
273  else
274  llvm::errs() << "llvm-ld: cannot create pass: " << Opt->getPassName()
275  << "\n";
276  }
277 #endif
278 
279  // The user's passes may leave cruft around. Clean up after them them but
280  // only if we haven't got DisableOptimizations set
281  if (!DisableOptimizations) {
282  addPass(Passes, createInstructionCombiningPass());
283  addPass(Passes, createCFGSimplificationPass());
284  addPass(Passes, createAggressiveDCEPass());
285  addPass(Passes, createGlobalDCEPass());
286  }
287 
288  // Make sure everything is still good.
289  if (!DontVerify)
290  Passes.add(createVerifierPass());
291 
292  // Run our queue of passes all at once now, efficiently.
293  Passes.run(*M);
294 }
295 
296 }
static cl::opt< bool > DisableOptimizations("disable-opt", cl::desc("Do not run any optimization passes"))
static void AddStandardCompilePasses(PassManager &PM)
Definition: Optimize.cpp:97
static cl::opt< bool > StripDebug("strip-debug", cl::desc("Strip debugger symbol info from executable"))
static cl::alias A1("S", cl::desc("Alias for --strip-debug"), cl::aliasopt(StripDebug))
static cl::alias ExportDynamic("export-dynamic", cl::aliasopt(DisableInternalize), cl::desc("Alias for -disable-internalize"))
static cl::opt< bool > DisableInline("disable-inlining", cl::desc("Do not run the inliner pass"))
static cl::opt< bool > DontVerify("disable-verify", cl::ReallyHidden)
static void addPass(PassManager &PM, Pass *P)
Definition: Optimize.cpp:85
static cl::opt< bool > DisableInternalize("disable-internalize", cl::desc("Do not mark all symbols as internal"))
void Optimize(Module *)
Definition: Optimize.cpp:168
static cl::opt< bool > VerifyEach("verify-each", cl::desc("Verify intermediate results of all passes"))
static cl::opt< bool > Strip("strip-all", cl::desc("Strip all symbol info from executable"))
static cl::alias A0("s", cl::desc("Alias for --strip-all"), cl::aliasopt(Strip))