Passes.cpp revision 1dd8c8560d45d36a8e507cd014352f1d313f9f9e 
1//===-- Passes.cpp - Target independent code generation passes ------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file defines interfaces to access the target independent code
11// generation passes provided by the LLVM backend.
12//
13//===---------------------------------------------------------------------===//
14
15#include "llvm/Analysis/Passes.h"
16#include "llvm/Analysis/Verifier.h"
17#include "llvm/Transforms/Scalar.h"
18#include "llvm/PassManager.h"
19#include "llvm/CodeGen/GCStrategy.h"
20#include "llvm/CodeGen/MachineFunctionPass.h"
21#include "llvm/CodeGen/Passes.h"
22#include "llvm/CodeGen/RegAllocRegistry.h"
23#include "llvm/Target/TargetLowering.h"
24#include "llvm/Target/TargetOptions.h"
25#include "llvm/Assembly/PrintModulePass.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/ErrorHandling.h"
29
30using namespace llvm;
31
32static cl::opt<bool> DisablePostRA("disable-post-ra", cl::Hidden,
33    cl::desc("Disable Post Regalloc"));
34static cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden,
35    cl::desc("Disable branch folding"));
36static cl::opt<bool> DisableTailDuplicate("disable-tail-duplicate", cl::Hidden,
37    cl::desc("Disable tail duplication"));
38static cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden,
39    cl::desc("Disable pre-register allocation tail duplication"));
40static cl::opt<bool> EnableBlockPlacement("enable-block-placement",
41    cl::Hidden, cl::desc("Enable probability-driven block placement"));
42static cl::opt<bool> EnableBlockPlacementStats("enable-block-placement-stats",
43    cl::Hidden, cl::desc("Collect probability-driven block placement stats"));
44static cl::opt<bool> DisableCodePlace("disable-code-place", cl::Hidden,
45    cl::desc("Disable code placement"));
46static cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden,
47    cl::desc("Disable Stack Slot Coloring"));
48static cl::opt<bool> DisableMachineDCE("disable-machine-dce", cl::Hidden,
49    cl::desc("Disable Machine Dead Code Elimination"));
50static cl::opt<bool> DisableMachineLICM("disable-machine-licm", cl::Hidden,
51    cl::desc("Disable Machine LICM"));
52static cl::opt<bool> DisableMachineCSE("disable-machine-cse", cl::Hidden,
53    cl::desc("Disable Machine Common Subexpression Elimination"));
54static cl::opt<bool> DisablePostRAMachineLICM("disable-postra-machine-licm",
55    cl::Hidden,
56    cl::desc("Disable Machine LICM"));
57static cl::opt<bool> DisableMachineSink("disable-machine-sink", cl::Hidden,
58    cl::desc("Disable Machine Sinking"));
59static cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden,
60    cl::desc("Disable Loop Strength Reduction Pass"));
61static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
62    cl::desc("Disable Codegen Prepare"));
63static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
64    cl::desc("Disable Copy Propagation pass"));
65static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
66    cl::desc("Print LLVM IR produced by the loop-reduce pass"));
67static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
68    cl::desc("Print LLVM IR input to isel pass"));
69static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden,
70    cl::desc("Dump garbage collector data"));
71static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden,
72    cl::desc("Verify generated machine code"),
73    cl::init(getenv("LLVM_VERIFY_MACHINEINSTRS")!=NULL));
74
75//===---------------------------------------------------------------------===//
76/// TargetPassConfig
77//===---------------------------------------------------------------------===//
78
79INITIALIZE_PASS(TargetPassConfig, "targetpassconfig",
80                "Target Pass Configuration", false, false)
81char TargetPassConfig::ID = 0;
82
83// Out of line virtual method.
84TargetPassConfig::~TargetPassConfig() {}
85
86// Out of line constructor provides default values for pass options and
87// registers all common codegen passes.
88TargetPassConfig::TargetPassConfig(TargetMachine *tm, PassManagerBase &pm)
89  : ImmutablePass(ID), TM(tm), PM(pm), Initialized(false),
90    DisableVerify(false),
91    EnableTailMerge(true) {
92
93  // Register all target independent codegen passes to activate their PassIDs,
94  // including this pass itself.
95  initializeCodeGen(*PassRegistry::getPassRegistry());
96}
97
98/// createPassConfig - Create a pass configuration object to be used by
99/// addPassToEmitX methods for generating a pipeline of CodeGen passes.
100///
101/// Targets may override this to extend TargetPassConfig.
102TargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM) {
103  return new TargetPassConfig(this, PM);
104}
105
106TargetPassConfig::TargetPassConfig()
107  : ImmutablePass(ID), PM(*(PassManagerBase*)0) {
108  llvm_unreachable("TargetPassConfig should not be constructed on-the-fly");
109}
110
111// Helper to verify the analysis is really immutable.
112void TargetPassConfig::setOpt(bool &Opt, bool Val) {
113  assert(!Initialized && "PassConfig is immutable");
114  Opt = Val;
115}
116
117void TargetPassConfig::addPass(char &ID) {
118  // FIXME: check user overrides
119  Pass *P = Pass::createPass(ID);
120  if (!P)
121    llvm_unreachable("Pass ID not registered");
122  PM.add(P);
123}
124
125void TargetPassConfig::printNoVerify(const char *Banner) const {
126  if (TM->shouldPrintMachineCode())
127    PM.add(createMachineFunctionPrinterPass(dbgs(), Banner));
128}
129
130void TargetPassConfig::printAndVerify(const char *Banner) const {
131  if (TM->shouldPrintMachineCode())
132    PM.add(createMachineFunctionPrinterPass(dbgs(), Banner));
133
134  if (VerifyMachineCode)
135    PM.add(createMachineVerifierPass(Banner));
136}
137
138/// Add common target configurable passes that perform LLVM IR to IR transforms
139/// following machine independent optimization.
140void TargetPassConfig::addIRPasses() {
141  // Basic AliasAnalysis support.
142  // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
143  // BasicAliasAnalysis wins if they disagree. This is intended to help
144  // support "obvious" type-punning idioms.
145  PM.add(createTypeBasedAliasAnalysisPass());
146  PM.add(createBasicAliasAnalysisPass());
147
148  // Before running any passes, run the verifier to determine if the input
149  // coming from the front-end and/or optimizer is valid.
150  if (!DisableVerify)
151    PM.add(createVerifierPass());
152
153  // Run loop strength reduction before anything else.
154  if (getOptLevel() != CodeGenOpt::None && !DisableLSR) {
155    PM.add(createLoopStrengthReducePass(getTargetLowering()));
156    if (PrintLSR)
157      PM.add(createPrintFunctionPass("\n\n*** Code after LSR ***\n", &dbgs()));
158  }
159
160  PM.add(createGCLoweringPass());
161
162  // Make sure that no unreachable blocks are instruction selected.
163  PM.add(createUnreachableBlockEliminationPass());
164}
165
166/// Add common passes that perform LLVM IR to IR transforms in preparation for
167/// instruction selection.
168void TargetPassConfig::addISelPrepare() {
169  if (getOptLevel() != CodeGenOpt::None && !DisableCGP)
170    PM.add(createCodeGenPreparePass(getTargetLowering()));
171
172  PM.add(createStackProtectorPass(getTargetLowering()));
173
174  addPreISel();
175
176  if (PrintISelInput)
177    PM.add(createPrintFunctionPass("\n\n"
178                                   "*** Final LLVM Code input to ISel ***\n",
179                                   &dbgs()));
180
181  // All passes which modify the LLVM IR are now complete; run the verifier
182  // to ensure that the IR is valid.
183  if (!DisableVerify)
184    PM.add(createVerifierPass());
185}
186
187void TargetPassConfig::addMachinePasses() {
188  // Print the instruction selected machine code...
189  printAndVerify("After Instruction Selection");
190
191  // Expand pseudo-instructions emitted by ISel.
192  addPass(ExpandISelPseudosID);
193
194  // Pre-ra tail duplication.
195  if (getOptLevel() != CodeGenOpt::None && !DisableEarlyTailDup) {
196    addPass(TailDuplicateID);
197    printAndVerify("After Pre-RegAlloc TailDuplicate");
198  }
199
200  // Optimize PHIs before DCE: removing dead PHI cycles may make more
201  // instructions dead.
202  if (getOptLevel() != CodeGenOpt::None)
203    addPass(OptimizePHIsID);
204
205  // If the target requests it, assign local variables to stack slots relative
206  // to one another and simplify frame index references where possible.
207  addPass(LocalStackSlotAllocationID);
208
209  if (getOptLevel() != CodeGenOpt::None) {
210    // With optimization, dead code should already be eliminated. However
211    // there is one known exception: lowered code for arguments that are only
212    // used by tail calls, where the tail calls reuse the incoming stack
213    // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll).
214    if (!DisableMachineDCE)
215      addPass(DeadMachineInstructionElimID);
216    printAndVerify("After codegen DCE pass");
217
218    if (!DisableMachineLICM)
219      addPass(MachineLICMID);
220    if (!DisableMachineCSE)
221      addPass(MachineCSEID);
222    if (!DisableMachineSink)
223      addPass(MachineSinkingID);
224    printAndVerify("After Machine LICM, CSE and Sinking passes");
225
226    addPass(PeepholeOptimizerID);
227    printAndVerify("After codegen peephole optimization pass");
228  }
229
230  // Run pre-ra passes.
231  if (addPreRegAlloc())
232    printAndVerify("After PreRegAlloc passes");
233
234  // Perform register allocation.
235  PM.add(createRegisterAllocator(getOptLevel()));
236  printAndVerify("After Register Allocation");
237
238  // Perform stack slot coloring and post-ra machine LICM.
239  if (getOptLevel() != CodeGenOpt::None) {
240    // FIXME: Re-enable coloring with register when it's capable of adding
241    // kill markers.
242    if (!DisableSSC)
243      addPass(StackSlotColoringID);
244
245    // Run post-ra machine LICM to hoist reloads / remats.
246    if (!DisablePostRAMachineLICM)
247      addPass(MachineLICMID);
248
249    printAndVerify("After StackSlotColoring and postra Machine LICM");
250  }
251
252  // Run post-ra passes.
253  if (addPostRegAlloc())
254    printAndVerify("After PostRegAlloc passes");
255
256  // Insert prolog/epilog code.  Eliminate abstract frame index references...
257  addPass(PrologEpilogCodeInserterID);
258  printAndVerify("After PrologEpilogCodeInserter");
259
260  // Branch folding must be run after regalloc and prolog/epilog insertion.
261  if (getOptLevel() != CodeGenOpt::None && !DisableBranchFold) {
262    addPass(BranchFolderPassID);
263    printNoVerify("After BranchFolding");
264  }
265
266  // Tail duplication.
267  if (getOptLevel() != CodeGenOpt::None && !DisableTailDuplicate) {
268    addPass(TailDuplicateID);
269    printNoVerify("After TailDuplicate");
270  }
271
272  // Copy propagation.
273  if (getOptLevel() != CodeGenOpt::None && !DisableCopyProp) {
274    addPass(MachineCopyPropagationID);
275    printNoVerify("After copy propagation pass");
276  }
277
278  // Expand pseudo instructions before second scheduling pass.
279  addPass(ExpandPostRAPseudosID);
280  printNoVerify("After ExpandPostRAPseudos");
281
282  // Run pre-sched2 passes.
283  if (addPreSched2())
284    printNoVerify("After PreSched2 passes");
285
286  // Second pass scheduler.
287  if (getOptLevel() != CodeGenOpt::None && !DisablePostRA) {
288    addPass(PostRASchedulerID);
289    printNoVerify("After PostRAScheduler");
290  }
291
292  addPass(GCMachineCodeAnalysisID);
293
294  if (PrintGCInfo)
295    PM.add(createGCInfoPrinter(dbgs()));
296
297  if (getOptLevel() != CodeGenOpt::None && !DisableCodePlace) {
298    if (EnableBlockPlacement) {
299      // MachineBlockPlacement is an experimental pass which is disabled by
300      // default currently. Eventually it should subsume CodePlacementOpt, so
301      // when enabled, the other is disabled.
302      addPass(MachineBlockPlacementID);
303      printNoVerify("After MachineBlockPlacement");
304    } else {
305      addPass(CodePlacementOptID);
306      printNoVerify("After CodePlacementOpt");
307    }
308
309    // Run a separate pass to collect block placement statistics.
310    if (EnableBlockPlacementStats) {
311      addPass(MachineBlockPlacementStatsID);
312      printNoVerify("After MachineBlockPlacementStats");
313    }
314  }
315
316  if (addPreEmitPass())
317    printNoVerify("After PreEmit passes");
318}
319
320//===---------------------------------------------------------------------===//
321///
322/// RegisterRegAlloc class - Track the registration of register allocators.
323///
324//===---------------------------------------------------------------------===//
325MachinePassRegistry RegisterRegAlloc::Registry;
326
327static FunctionPass *createDefaultRegisterAllocator() { return 0; }
328static RegisterRegAlloc
329defaultRegAlloc("default",
330                "pick register allocator based on -O option",
331                createDefaultRegisterAllocator);
332
333//===---------------------------------------------------------------------===//
334///
335/// RegAlloc command line options.
336///
337//===---------------------------------------------------------------------===//
338static cl::opt<RegisterRegAlloc::FunctionPassCtor, false,
339               RegisterPassParser<RegisterRegAlloc> >
340RegAlloc("regalloc",
341         cl::init(&createDefaultRegisterAllocator),
342         cl::desc("Register allocator to use"));
343
344
345//===---------------------------------------------------------------------===//
346///
347/// createRegisterAllocator - choose the appropriate register allocator.
348///
349//===---------------------------------------------------------------------===//
350FunctionPass *llvm::createRegisterAllocator(CodeGenOpt::Level OptLevel) {
351  RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault();
352
353  if (!Ctor) {
354    Ctor = RegAlloc;
355    RegisterRegAlloc::setDefault(RegAlloc);
356  }
357
358  if (Ctor != createDefaultRegisterAllocator)
359    return Ctor();
360
361  // When the 'default' allocator is requested, pick one based on OptLevel.
362  switch (OptLevel) {
363  case CodeGenOpt::None:
364    return createFastRegisterAllocator();
365  default:
366    return createGreedyRegisterAllocator();
367  }
368}
369