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/MachineFunctionAnalysis.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineModuleInfo.h"
  23 #include "llvm/CodeGen/Passes.h"
  24 #include "llvm/CodeGen/RegAllocRegistry.h"
  25 #include "llvm/Target/TargetLowering.h"
  26 #include "llvm/Target/TargetLoweringObjectFile.h"
  27 #include "llvm/Target/TargetOptions.h"
  28 #include "llvm/Target/TargetRegisterInfo.h"
  29 #include "llvm/MC/MCAsmInfo.h"
  30 #include "llvm/Assembly/PrintModulePass.h"
  31 #include "llvm/Support/CommandLine.h"
  32 #include "llvm/Support/Debug.h"
  33 #include "llvm/Support/ErrorHandling.h"
  34
  35 using namespace llvm;
  36
  37 static cl::opt<bool> DisablePostRA("disable-post-ra", cl::Hidden,
  38     cl::desc("Disable Post Regalloc"));
  39 static cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden,
  40     cl::desc("Disable branch folding"));
  41 static cl::opt<bool> DisableTailDuplicate("disable-tail-duplicate", cl::Hidden,
  42     cl::desc("Disable tail duplication"));
  43 static cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden,
  44     cl::desc("Disable pre-register allocation tail duplication"));
  45 static cl::opt<bool> EnableBlockPlacement("enable-block-placement",
  46     cl::Hidden, cl::desc("Enable probability-driven block placement"));
  47 static cl::opt<bool> EnableBlockPlacementStats("enable-block-placement-stats",
  48     cl::Hidden, cl::desc("Collect probability-driven block placement stats"));
  49 static cl::opt<bool> DisableCodePlace("disable-code-place", cl::Hidden,
  50     cl::desc("Disable code placement"));
  51 static cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden,
  52     cl::desc("Disable Stack Slot Coloring"));
  53 static cl::opt<bool> DisableMachineDCE("disable-machine-dce", cl::Hidden,
  54     cl::desc("Disable Machine Dead Code Elimination"));
  55 static cl::opt<bool> DisableMachineLICM("disable-machine-licm", cl::Hidden,
  56     cl::desc("Disable Machine LICM"));
  57 static cl::opt<bool> DisableMachineCSE("disable-machine-cse", cl::Hidden,
  58     cl::desc("Disable Machine Common Subexpression Elimination"));
  59 static cl::opt<bool> DisablePostRAMachineLICM("disable-postra-machine-licm",
  60     cl::Hidden,
  61     cl::desc("Disable Machine LICM"));
  62 static cl::opt<bool> DisableMachineSink("disable-machine-sink", cl::Hidden,
  63     cl::desc("Disable Machine Sinking"));
  64 static cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden,
  65     cl::desc("Disable Loop Strength Reduction Pass"));
  66 static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
  67     cl::desc("Disable Codegen Prepare"));
  68 static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
  69     cl::desc("Disable Copy Propagation pass"));
  70 static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
  71     cl::desc("Print LLVM IR produced by the loop-reduce pass"));
  72 static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
  73     cl::desc("Print LLVM IR input to isel pass"));
  74 static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden,
  75     cl::desc("Dump garbage collector data"));
  76 static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden,
  77     cl::desc("Verify generated machine code"),
  78     cl::init(getenv("LLVM_VERIFY_MACHINEINSTRS")!=NULL));
  79
  80 // Enable or disable FastISel. Both options are needed, because
  81 // FastISel is enabled by default with -fast, and we wish to be
  82 // able to enable or disable fast-isel independently from -O0.
  83 static cl::opt<cl::boolOrDefault>
  84 EnableFastISelOption("fast-isel", cl::Hidden,
  85   cl::desc("Enable the \"fast\" instruction selector"));
  86
  87 //===---------------------------------------------------------------------===//
  88 /// TargetPassConfig
  89 //===---------------------------------------------------------------------===//
  90
  91 INITIALIZE_PASS(TargetPassConfig, "targetpassconfig",
  92                 "Target Pass Configuration", false, false)
  93 char TargetPassConfig::ID = 0;
  94
  95 // Out of line virtual method.
  96 TargetPassConfig::~TargetPassConfig() {}
  97
  98 TargetPassConfig::TargetPassConfig(TargetMachine *tm, PassManagerBase &pm,
  99                                    bool DisableVerifyFlag)
 100   : ImmutablePass(ID), TM(tm), PM(pm), DisableVerify(DisableVerifyFlag) {
 101   // Register all target independent codegen passes to activate their PassIDs,
 102   // including this pass itself.
 103   initializeCodeGen(*PassRegistry::getPassRegistry());
 104 }
 105
 106 /// createPassConfig - Create a pass configuration object to be used by
 107 /// addPassToEmitX methods for generating a pipeline of CodeGen passes.
 108 ///
 109 /// Targets may override this to extend TargetPassConfig.
 110 TargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM,
 111                                                       bool DisableVerify) {
 112   return new TargetPassConfig(this, PM, DisableVerify);
 113 }
 114
 115 TargetPassConfig::TargetPassConfig()
 116   : ImmutablePass(ID), PM(*(PassManagerBase*)0) {
 117   llvm_unreachable("TargetPassConfig should not be constructed on-the-fly");
 118 }
 119
 120
 121 void TargetPassConfig::printNoVerify(const char *Banner) const {
 122   if (TM->shouldPrintMachineCode())
 123     PM.add(createMachineFunctionPrinterPass(dbgs(), Banner));
 124 }
 125
 126 void TargetPassConfig::printAndVerify(const char *Banner) const {
 127   if (TM->shouldPrintMachineCode())
 128     PM.add(createMachineFunctionPrinterPass(dbgs(), Banner));
 129
 130   if (VerifyMachineCode)
 131     PM.add(createMachineVerifierPass(Banner));
 132 }
 133
 134 /// addCodeGenPasses - Add standard LLVM codegen passes used for both
 135 /// emitting to assembly files or machine code output.
 136 ///
 137 bool TargetPassConfig::addCodeGenPasses(MCContext *&OutContext) {
 138   // Standard LLVM-Level Passes.
 139
 140   // Basic AliasAnalysis support.
 141   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
 142   // BasicAliasAnalysis wins if they disagree. This is intended to help
 143   // support "obvious" type-punning idioms.
 144   PM.add(createTypeBasedAliasAnalysisPass());
 145   PM.add(createBasicAliasAnalysisPass());
 146
 147   // Before running any passes, run the verifier to determine if the input
 148   // coming from the front-end and/or optimizer is valid.
 149   if (!DisableVerify)
 150     PM.add(createVerifierPass());
 151
 152   // Run loop strength reduction before anything else.
 153   if (getOptLevel() != CodeGenOpt::None && !DisableLSR) {
 154     PM.add(createLoopStrengthReducePass(getTargetLowering()));
 155     if (PrintLSR)
 156       PM.add(createPrintFunctionPass("\n\n*** Code after LSR ***\n", &dbgs()));
 157   }
 158
 159   PM.add(createGCLoweringPass());
 160
 161   // Make sure that no unreachable blocks are instruction selected.
 162   PM.add(createUnreachableBlockEliminationPass());
 163
 164   // Turn exception handling constructs into something the code generators can
 165   // handle.
 166   switch (TM->getMCAsmInfo()->getExceptionHandlingType()) {
 167   case ExceptionHandling::SjLj:
 168     // SjLj piggy-backs on dwarf for this bit. The cleanups done apply to both
 169     // Dwarf EH prepare needs to be run after SjLj prepare. Otherwise,
 170     // catch info can get misplaced when a selector ends up more than one block
 171     // removed from the parent invoke(s). This could happen when a landing
 172     // pad is shared by multiple invokes and is also a target of a normal
 173     // edge from elsewhere.
 174     PM.add(createSjLjEHPass(getTargetLowering()));
 175     // FALLTHROUGH
 176   case ExceptionHandling::DwarfCFI:
 177   case ExceptionHandling::ARM:
 178   case ExceptionHandling::Win64:
 179     PM.add(createDwarfEHPass(TM));
 180     break;
 181   case ExceptionHandling::None:
 182     PM.add(createLowerInvokePass(getTargetLowering()));
 183
 184     // The lower invoke pass may create unreachable code. Remove it.
 185     PM.add(createUnreachableBlockEliminationPass());
 186     break;
 187   }
 188
 189   if (getOptLevel() != CodeGenOpt::None && !DisableCGP)
 190     PM.add(createCodeGenPreparePass(getTargetLowering()));
 191
 192   PM.add(createStackProtectorPass(getTargetLowering()));
 193
 194   addPreISel();
 195
 196   if (PrintISelInput)
 197     PM.add(createPrintFunctionPass("\n\n"
 198                                    "*** Final LLVM Code input to ISel ***\n",
 199                                    &dbgs()));
 200
 201   // All passes which modify the LLVM IR are now complete; run the verifier
 202   // to ensure that the IR is valid.
 203   if (!DisableVerify)
 204     PM.add(createVerifierPass());
 205
 206   // Standard Lower-Level Passes.
 207
 208   // Install a MachineModuleInfo class, which is an immutable pass that holds
 209   // all the per-module stuff we're generating, including MCContext.
 210   MachineModuleInfo *MMI =
 211     new MachineModuleInfo(*TM->getMCAsmInfo(), *TM->getRegisterInfo(),
 212                           &getTargetLowering()->getObjFileLowering());
 213   PM.add(MMI);
 214   OutContext = &MMI->getContext(); // Return the MCContext specifically by-ref.
 215
 216   // Set up a MachineFunction for the rest of CodeGen to work on.
 217   PM.add(new MachineFunctionAnalysis(*TM));
 218
 219   // Enable FastISel with -fast, but allow that to be overridden.
 220   if (EnableFastISelOption == cl::BOU_TRUE ||
 221       (getOptLevel() == CodeGenOpt::None &&
 222        EnableFastISelOption != cl::BOU_FALSE))
 223     TM->setFastISel(true);
 224
 225   // Ask the target for an isel.
 226   if (addInstSelector())
 227     return true;
 228
 229   // Print the instruction selected machine code...
 230   printAndVerify("After Instruction Selection");
 231
 232   // Expand pseudo-instructions emitted by ISel.
 233   PM.add(createExpandISelPseudosPass());
 234
 235   // Pre-ra tail duplication.
 236   if (getOptLevel() != CodeGenOpt::None && !DisableEarlyTailDup) {
 237     PM.add(createTailDuplicatePass(true));
 238     printAndVerify("After Pre-RegAlloc TailDuplicate");
 239   }
 240
 241   // Optimize PHIs before DCE: removing dead PHI cycles may make more
 242   // instructions dead.
 243   if (getOptLevel() != CodeGenOpt::None)
 244     PM.add(createOptimizePHIsPass());
 245
 246   // If the target requests it, assign local variables to stack slots relative
 247   // to one another and simplify frame index references where possible.
 248   PM.add(createLocalStackSlotAllocationPass());
 249
 250   if (getOptLevel() != CodeGenOpt::None) {
 251     // With optimization, dead code should already be eliminated. However
 252     // there is one known exception: lowered code for arguments that are only
 253     // used by tail calls, where the tail calls reuse the incoming stack
 254     // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll).
 255     if (!DisableMachineDCE)
 256       PM.add(createDeadMachineInstructionElimPass());
 257     printAndVerify("After codegen DCE pass");
 258
 259     if (!DisableMachineLICM)
 260       PM.add(createMachineLICMPass());
 261     if (!DisableMachineCSE)
 262       PM.add(createMachineCSEPass());
 263     if (!DisableMachineSink)
 264       PM.add(createMachineSinkingPass());
 265     printAndVerify("After Machine LICM, CSE and Sinking passes");
 266
 267     PM.add(createPeepholeOptimizerPass());
 268     printAndVerify("After codegen peephole optimization pass");
 269   }
 270
 271   // Run pre-ra passes.
 272   if (addPreRegAlloc())
 273     printAndVerify("After PreRegAlloc passes");
 274
 275   // Perform register allocation.
 276   PM.add(createRegisterAllocator(getOptLevel()));
 277   printAndVerify("After Register Allocation");
 278
 279   // Perform stack slot coloring and post-ra machine LICM.
 280   if (getOptLevel() != CodeGenOpt::None) {
 281     // FIXME: Re-enable coloring with register when it's capable of adding
 282     // kill markers.
 283     if (!DisableSSC)
 284       PM.add(createStackSlotColoringPass(false));
 285
 286     // Run post-ra machine LICM to hoist reloads / remats.
 287     if (!DisablePostRAMachineLICM)
 288       PM.add(createMachineLICMPass(false));
 289
 290     printAndVerify("After StackSlotColoring and postra Machine LICM");
 291   }
 292
 293   // Run post-ra passes.
 294   if (addPostRegAlloc())
 295     printAndVerify("After PostRegAlloc passes");
 296
 297   // Insert prolog/epilog code.  Eliminate abstract frame index references...
 298   PM.add(createPrologEpilogCodeInserter());
 299   printAndVerify("After PrologEpilogCodeInserter");
 300
 301   // Branch folding must be run after regalloc and prolog/epilog insertion.
 302   if (getOptLevel() != CodeGenOpt::None && !DisableBranchFold) {
 303     PM.add(createBranchFoldingPass(getEnableTailMergeDefault()));
 304     printNoVerify("After BranchFolding");
 305   }
 306
 307   // Tail duplication.
 308   if (getOptLevel() != CodeGenOpt::None && !DisableTailDuplicate) {
 309     PM.add(createTailDuplicatePass(false));
 310     printNoVerify("After TailDuplicate");
 311   }
 312
 313   // Copy propagation.
 314   if (getOptLevel() != CodeGenOpt::None && !DisableCopyProp) {
 315     PM.add(createMachineCopyPropagationPass());
 316     printNoVerify("After copy propagation pass");
 317   }
 318
 319   // Expand pseudo instructions before second scheduling pass.
 320   PM.add(createExpandPostRAPseudosPass());
 321   printNoVerify("After ExpandPostRAPseudos");
 322
 323   // Run pre-sched2 passes.
 324   if (addPreSched2())
 325     printNoVerify("After PreSched2 passes");
 326
 327   // Second pass scheduler.
 328   if (getOptLevel() != CodeGenOpt::None && !DisablePostRA) {
 329     PM.add(createPostRAScheduler(getOptLevel()));
 330     printNoVerify("After PostRAScheduler");
 331   }
 332
 333   PM.add(createGCMachineCodeAnalysisPass());
 334
 335   if (PrintGCInfo)
 336     PM.add(createGCInfoPrinter(dbgs()));
 337
 338   if (getOptLevel() != CodeGenOpt::None && !DisableCodePlace) {
 339     if (EnableBlockPlacement) {
 340       // MachineBlockPlacement is an experimental pass which is disabled by
 341       // default currently. Eventually it should subsume CodePlacementOpt, so
 342       // when enabled, the other is disabled.
 343       PM.add(createMachineBlockPlacementPass());
 344       printNoVerify("After MachineBlockPlacement");
 345     } else {
 346       PM.add(createCodePlacementOptPass());
 347       printNoVerify("After CodePlacementOpt");
 348     }
 349
 350     // Run a separate pass to collect block placement statistics.
 351     if (EnableBlockPlacementStats) {
 352       PM.add(createMachineBlockPlacementStatsPass());
 353       printNoVerify("After MachineBlockPlacementStats");
 354     }
 355   }
 356
 357   if (addPreEmitPass())
 358     printNoVerify("After PreEmit passes");
 359
 360   return false;
 361 }
 362
 363 //===---------------------------------------------------------------------===//
 364 ///
 365 /// RegisterRegAlloc class - Track the registration of register allocators.
 366 ///
 367 //===---------------------------------------------------------------------===//
 368 MachinePassRegistry RegisterRegAlloc::Registry;
 369
 370 static FunctionPass *createDefaultRegisterAllocator() { return 0; }
 371 static RegisterRegAlloc
 372 defaultRegAlloc("default",
 373                 "pick register allocator based on -O option",
 374                 createDefaultRegisterAllocator);
 375
 376 //===---------------------------------------------------------------------===//
 377 ///
 378 /// RegAlloc command line options.
 379 ///
 380 //===---------------------------------------------------------------------===//
 381 static cl::opt<RegisterRegAlloc::FunctionPassCtor, false,
 382                RegisterPassParser<RegisterRegAlloc> >
 383 RegAlloc("regalloc",
 384          cl::init(&createDefaultRegisterAllocator),
 385          cl::desc("Register allocator to use"));
 386
 387
 388 //===---------------------------------------------------------------------===//
 389 ///
 390 /// createRegisterAllocator - choose the appropriate register allocator.
 391 ///
 392 //===---------------------------------------------------------------------===//
 393 FunctionPass *llvm::createRegisterAllocator(CodeGenOpt::Level OptLevel) {
 394   RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault();
 395
 396   if (!Ctor) {
 397     Ctor = RegAlloc;
 398     RegisterRegAlloc::setDefault(RegAlloc);
 399   }
 400
 401   if (Ctor != createDefaultRegisterAllocator)
 402     return Ctor();
 403
 404   // When the 'default' allocator is requested, pick one based on OptLevel.
 405   switch (OptLevel) {
 406   case CodeGenOpt::None:
 407     return createFastRegisterAllocator();
 408   default:
 409     return createGreedyRegisterAllocator();
 410   }
 411 }