lib/CodeGen/Passes.cpp

   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
  30 using namespace llvm;
  31
  32 static cl::opt<bool> DisablePostRA("disable-post-ra", cl::Hidden,
  33     cl::desc("Disable Post Regalloc"));
  34 static cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden,
  35     cl::desc("Disable branch folding"));
  36 static cl::opt<bool> DisableTailDuplicate("disable-tail-duplicate", cl::Hidden,
  37     cl::desc("Disable tail duplication"));
  38 static cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden,
  39     cl::desc("Disable pre-register allocation tail duplication"));
  40 static cl::opt<bool> EnableBlockPlacement("enable-block-placement",
  41     cl::Hidden, cl::desc("Enable probability-driven block placement"));
  42 static cl::opt<bool> EnableBlockPlacementStats("enable-block-placement-stats",
  43     cl::Hidden, cl::desc("Collect probability-driven block placement stats"));
  44 static cl::opt<bool> DisableCodePlace("disable-code-place", cl::Hidden,
  45     cl::desc("Disable code placement"));
  46 static cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden,
  47     cl::desc("Disable Stack Slot Coloring"));
  48 static cl::opt<bool> DisableMachineDCE("disable-machine-dce", cl::Hidden,
  49     cl::desc("Disable Machine Dead Code Elimination"));
  50 static cl::opt<bool> DisableMachineLICM("disable-machine-licm", cl::Hidden,
  51     cl::desc("Disable Machine LICM"));
  52 static cl::opt<bool> DisableMachineCSE("disable-machine-cse", cl::Hidden,
  53     cl::desc("Disable Machine Common Subexpression Elimination"));
  54 static cl::opt<bool> DisablePostRAMachineLICM("disable-postra-machine-licm",
  55     cl::Hidden,
  56     cl::desc("Disable Machine LICM"));
  57 static cl::opt<bool> DisableMachineSink("disable-machine-sink", cl::Hidden,
  58     cl::desc("Disable Machine Sinking"));
  59 static cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden,
  60     cl::desc("Disable Loop Strength Reduction Pass"));
  61 static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
  62     cl::desc("Disable Codegen Prepare"));
  63 static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
  64     cl::desc("Disable Copy Propagation pass"));
  65 static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
  66     cl::desc("Print LLVM IR produced by the loop-reduce pass"));
  67 static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
  68     cl::desc("Print LLVM IR input to isel pass"));
  69 static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden,
  70     cl::desc("Dump garbage collector data"));
  71 static 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
  79 INITIALIZE_PASS(TargetPassConfig, "targetpassconfig",
  80                 "Target Pass Configuration", false, false)
  81 char TargetPassConfig::ID = 0;
  82
  83 // Out of line virtual method.
  84 TargetPassConfig::~TargetPassConfig() {}
  85
  86 // Out of line constructor provides default values for pass options and
  87 // registers all common codegen passes.
  88 TargetPassConfig::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.
 102 TargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM) {
 103   return new TargetPassConfig(this, PM);
 104 }
 105
 106 TargetPassConfig::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.
 112 void TargetPassConfig::setOpt(bool &Opt, bool Val) {
 113   assert(!Initialized && "PassConfig is immutable");
 114   Opt = Val;
 115 }
 116
 117 void 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
 125 void TargetPassConfig::printNoVerify(const char *Banner) const {
 126   if (TM->shouldPrintMachineCode())
 127     PM.add(createMachineFunctionPrinterPass(dbgs(), Banner));
 128 }
 129
 130 void 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.
 140 void 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.
 168 void 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
 187 void 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 //===---------------------------------------------------------------------===//
 325 MachinePassRegistry RegisterRegAlloc::Registry;
 326
 327 static FunctionPass *createDefaultRegisterAllocator() { return 0; }
 328 static RegisterRegAlloc
 329 defaultRegAlloc("default",
 330                 "pick register allocator based on -O option",
 331                 createDefaultRegisterAllocator);
 332
 333 //===---------------------------------------------------------------------===//
 334 ///
 335 /// RegAlloc command line options.
 336 ///
 337 //===---------------------------------------------------------------------===//
 338 static cl::opt<RegisterRegAlloc::FunctionPassCtor, false,
 339                RegisterPassParser<RegisterRegAlloc> >
 340 RegAlloc("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 //===---------------------------------------------------------------------===//
 350 FunctionPass *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 }