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<cl::boolOrDefault>
  55 OptimizeRegAlloc("optimize-regalloc", cl::Hidden,
  56     cl::desc("Enable optimized register allocation compilation path."));
  57 static cl::opt<cl::boolOrDefault>
  58 EnableMachineSched("enable-misched", cl::Hidden,
  59     cl::desc("Enable the machine instruction scheduling pass."));
  60 static cl::opt<bool> EnableStrongPHIElim("strong-phi-elim", cl::Hidden,
  61     cl::desc("Use strong PHI elimination."));
  62 static cl::opt<bool> DisablePostRAMachineLICM("disable-postra-machine-licm",
  63     cl::Hidden,
  64     cl::desc("Disable Machine LICM"));
  65 static cl::opt<bool> DisableMachineSink("disable-machine-sink", cl::Hidden,
  66     cl::desc("Disable Machine Sinking"));
  67 static cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden,
  68     cl::desc("Disable Loop Strength Reduction Pass"));
  69 static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden,
  70     cl::desc("Disable Codegen Prepare"));
  71 static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
  72     cl::desc("Disable Copy Propagation pass"));
  73 static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
  74     cl::desc("Print LLVM IR produced by the loop-reduce pass"));
  75 static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
  76     cl::desc("Print LLVM IR input to isel pass"));
  77 static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden,
  78     cl::desc("Dump garbage collector data"));
  79 static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden,
  80     cl::desc("Verify generated machine code"),
  81     cl::init(getenv("LLVM_VERIFY_MACHINEINSTRS")!=NULL));
  82
  83 // Allow Pass selection to be overriden by command line options.
  84 //
  85 // DefaultID is the default pass to run which may be NoPassID, or may be
  86 // overriden by the target.
  87 //
  88 // OptionalID is a pass that may be forcibly enabled by the user when the
  89 // default is NoPassID.
  90 char &enablePass(char &DefaultID, cl::boolOrDefault Override,
  91                  char *OptionalIDPtr = &NoPassID) {
  92   switch (Override) {
  93   case cl::BOU_UNSET:
  94     return DefaultID;
  95   case cl::BOU_TRUE:
  96     if (&DefaultID != &NoPassID)
  97       return DefaultID;
  98     if (OptionalIDPtr == &NoPassID)
  99       report_fatal_error("Target cannot enable pass");
 100     return *OptionalIDPtr;
 101   case cl::BOU_FALSE:
 102     return NoPassID;
 103   }
 104   llvm_unreachable("Invalid command line option state");
 105 }
 106
 107 //===---------------------------------------------------------------------===//
 108 /// TargetPassConfig
 109 //===---------------------------------------------------------------------===//
 110
 111 INITIALIZE_PASS(TargetPassConfig, "targetpassconfig",
 112                 "Target Pass Configuration", false, false)
 113 char TargetPassConfig::ID = 0;
 114
 115 static char NoPassIDAnchor = 0;
 116 char &llvm::NoPassID = NoPassIDAnchor;
 117
 118 // Out of line virtual method.
 119 TargetPassConfig::~TargetPassConfig() {}
 120
 121 // Out of line constructor provides default values for pass options and
 122 // registers all common codegen passes.
 123 TargetPassConfig::TargetPassConfig(TargetMachine *tm, PassManagerBase &pm)
 124   : ImmutablePass(ID), TM(tm), PM(pm), Initialized(false),
 125     DisableVerify(false),
 126     EnableTailMerge(true) {
 127
 128   // Register all target independent codegen passes to activate their PassIDs,
 129   // including this pass itself.
 130   initializeCodeGen(*PassRegistry::getPassRegistry());
 131 }
 132
 133 /// createPassConfig - Create a pass configuration object to be used by
 134 /// addPassToEmitX methods for generating a pipeline of CodeGen passes.
 135 ///
 136 /// Targets may override this to extend TargetPassConfig.
 137 TargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM) {
 138   return new TargetPassConfig(this, PM);
 139 }
 140
 141 TargetPassConfig::TargetPassConfig()
 142   : ImmutablePass(ID), PM(*(PassManagerBase*)0) {
 143   llvm_unreachable("TargetPassConfig should not be constructed on-the-fly");
 144 }
 145
 146 // Helper to verify the analysis is really immutable.
 147 void TargetPassConfig::setOpt(bool &Opt, bool Val) {
 148   assert(!Initialized && "PassConfig is immutable");
 149   Opt = Val;
 150 }
 151
 152 void TargetPassConfig::addPass(char &ID) {
 153   if (&ID == &NoPassID)
 154     return;
 155
 156   // FIXME: check user overrides
 157   Pass *P = Pass::createPass(ID);
 158   if (!P)
 159     llvm_unreachable("Pass ID not registered");
 160   PM.add(P);
 161 }
 162
 163 void TargetPassConfig::printNoVerify(const char *Banner) const {
 164   if (TM->shouldPrintMachineCode())
 165     PM.add(createMachineFunctionPrinterPass(dbgs(), Banner));
 166 }
 167
 168 void TargetPassConfig::printAndVerify(const char *Banner) const {
 169   if (TM->shouldPrintMachineCode())
 170     PM.add(createMachineFunctionPrinterPass(dbgs(), Banner));
 171
 172   if (VerifyMachineCode)
 173     PM.add(createMachineVerifierPass(Banner));
 174 }
 175
 176 /// Add common target configurable passes that perform LLVM IR to IR transforms
 177 /// following machine independent optimization.
 178 void TargetPassConfig::addIRPasses() {
 179   // Basic AliasAnalysis support.
 180   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
 181   // BasicAliasAnalysis wins if they disagree. This is intended to help
 182   // support "obvious" type-punning idioms.
 183   PM.add(createTypeBasedAliasAnalysisPass());
 184   PM.add(createBasicAliasAnalysisPass());
 185
 186   // Before running any passes, run the verifier to determine if the input
 187   // coming from the front-end and/or optimizer is valid.
 188   if (!DisableVerify)
 189     PM.add(createVerifierPass());
 190
 191   // Run loop strength reduction before anything else.
 192   if (getOptLevel() != CodeGenOpt::None && !DisableLSR) {
 193     PM.add(createLoopStrengthReducePass(getTargetLowering()));
 194     if (PrintLSR)
 195       PM.add(createPrintFunctionPass("\n\n*** Code after LSR ***\n", &dbgs()));
 196   }
 197
 198   PM.add(createGCLoweringPass());
 199
 200   // Make sure that no unreachable blocks are instruction selected.
 201   PM.add(createUnreachableBlockEliminationPass());
 202 }
 203
 204 /// Add common passes that perform LLVM IR to IR transforms in preparation for
 205 /// instruction selection.
 206 void TargetPassConfig::addISelPrepare() {
 207   if (getOptLevel() != CodeGenOpt::None && !DisableCGP)
 208     PM.add(createCodeGenPreparePass(getTargetLowering()));
 209
 210   PM.add(createStackProtectorPass(getTargetLowering()));
 211
 212   addPreISel();
 213
 214   if (PrintISelInput)
 215     PM.add(createPrintFunctionPass("\n\n"
 216                                    "*** Final LLVM Code input to ISel ***\n",
 217                                    &dbgs()));
 218
 219   // All passes which modify the LLVM IR are now complete; run the verifier
 220   // to ensure that the IR is valid.
 221   if (!DisableVerify)
 222     PM.add(createVerifierPass());
 223 }
 224
 225 /// Add the complete set of target-independent postISel code generator passes.
 226 ///
 227 /// This can be read as the standard order of major LLVM CodeGen stages. Stages
 228 /// with nontrivial configuration or multiple passes are broken out below in
 229 /// add%Stage routines.
 230 ///
 231 /// Any TargetPassConfig::addXX routine may be overriden by the Target. The
 232 /// addPre/Post methods with empty header implementations allow injecting
 233 /// target-specific fixups just before or after major stages. Additionally,
 234 /// targets have the flexibility to change pass order within a stage by
 235 /// overriding default implementation of add%Stage routines below. Each
 236 /// technique has maintainability tradeoffs because alternate pass orders are
 237 /// not well supported. addPre/Post works better if the target pass is easily
 238 /// tied to a common pass. But if it has subtle dependencies on multiple passes,
 239 /// the target should override the stage instead.
 240 ///
 241 /// TODO: We could use a single addPre/Post(ID) hook to allow pass injection
 242 /// before/after any target-independent pass. But it's currently overkill.
 243 void TargetPassConfig::addMachinePasses() {
 244   // Print the instruction selected machine code...
 245   printAndVerify("After Instruction Selection");
 246
 247   // Expand pseudo-instructions emitted by ISel.
 248   addPass(ExpandISelPseudosID);
 249
 250   // Add passes that optimize machine instructions in SSA form.
 251   if (getOptLevel() != CodeGenOpt::None) {
 252     addMachineSSAOptimization();
 253   }
 254   else {
 255     // If the target requests it, assign local variables to stack slots relative
 256     // to one another and simplify frame index references where possible.
 257     addPass(LocalStackSlotAllocationID);
 258   }
 259
 260   // Run pre-ra passes.
 261   if (addPreRegAlloc())
 262     printAndVerify("After PreRegAlloc passes");
 263
 264   // Run register allocation and passes that are tightly coupled with it,
 265   // including phi elimination and scheduling.
 266   if (getOptimizeRegAlloc())
 267     addOptimizedRegAlloc(createRegAllocPass(true));
 268   else
 269     addFastRegAlloc(createRegAllocPass(false));
 270
 271   // Run post-ra passes.
 272   if (addPostRegAlloc())
 273     printAndVerify("After PostRegAlloc passes");
 274
 275   // Insert prolog/epilog code.  Eliminate abstract frame index references...
 276   addPass(PrologEpilogCodeInserterID);
 277   printAndVerify("After PrologEpilogCodeInserter");
 278
 279   /// Add passes that optimize machine instructions after register allocation.
 280   if (getOptLevel() != CodeGenOpt::None)
 281     addMachineLateOptimization();
 282
 283   // Expand pseudo instructions before second scheduling pass.
 284   addPass(ExpandPostRAPseudosID);
 285   printNoVerify("After ExpandPostRAPseudos");
 286
 287   // Run pre-sched2 passes.
 288   if (addPreSched2())
 289     printNoVerify("After PreSched2 passes");
 290
 291   // Second pass scheduler.
 292   if (getOptLevel() != CodeGenOpt::None && !DisablePostRA) {
 293     addPass(PostRASchedulerID);
 294     printNoVerify("After PostRAScheduler");
 295   }
 296
 297   // GC
 298   addPass(GCMachineCodeAnalysisID);
 299   if (PrintGCInfo)
 300     PM.add(createGCInfoPrinter(dbgs()));
 301
 302   // Basic block placement.
 303   if (getOptLevel() != CodeGenOpt::None && !DisableCodePlace)
 304     addBlockPlacement();
 305
 306   if (addPreEmitPass())
 307     printNoVerify("After PreEmit passes");
 308 }
 309
 310 /// Add passes that optimize machine instructions in SSA form.
 311 void TargetPassConfig::addMachineSSAOptimization() {
 312   // Pre-ra tail duplication.
 313   if (!DisableEarlyTailDup) {
 314     addPass(TailDuplicateID);
 315     printAndVerify("After Pre-RegAlloc TailDuplicate");
 316   }
 317
 318   // Optimize PHIs before DCE: removing dead PHI cycles may make more
 319   // instructions dead.
 320   addPass(OptimizePHIsID);
 321
 322   // If the target requests it, assign local variables to stack slots relative
 323   // to one another and simplify frame index references where possible.
 324   addPass(LocalStackSlotAllocationID);
 325
 326   // With optimization, dead code should already be eliminated. However
 327   // there is one known exception: lowered code for arguments that are only
 328   // used by tail calls, where the tail calls reuse the incoming stack
 329   // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll).
 330   if (!DisableMachineDCE)
 331     addPass(DeadMachineInstructionElimID);
 332   printAndVerify("After codegen DCE pass");
 333
 334   if (!DisableMachineLICM)
 335     addPass(MachineLICMID);
 336   if (!DisableMachineCSE)
 337     addPass(MachineCSEID);
 338   if (!DisableMachineSink)
 339     addPass(MachineSinkingID);
 340   printAndVerify("After Machine LICM, CSE and Sinking passes");
 341
 342   addPass(PeepholeOptimizerID);
 343   printAndVerify("After codegen peephole optimization pass");
 344 }
 345
 346 //===---------------------------------------------------------------------===//
 347 /// Register Allocation Pass Configuration
 348 //===---------------------------------------------------------------------===//
 349
 350 bool TargetPassConfig::getOptimizeRegAlloc() const {
 351   switch (OptimizeRegAlloc) {
 352   case cl::BOU_UNSET: return getOptLevel() != CodeGenOpt::None;
 353   case cl::BOU_TRUE:  return true;
 354   case cl::BOU_FALSE: return false;
 355   }
 356   llvm_unreachable("Invalid optimize-regalloc state");
 357 }
 358
 359 /// RegisterRegAlloc's global Registry tracks allocator registration.
 360 MachinePassRegistry RegisterRegAlloc::Registry;
 361
 362 /// A dummy default pass factory indicates whether the register allocator is
 363 /// overridden on the command line.
 364 static FunctionPass *useDefaultRegisterAllocator() { return 0; }
 365 static RegisterRegAlloc
 366 defaultRegAlloc("default",
 367                 "pick register allocator based on -O option",
 368                 useDefaultRegisterAllocator);
 369
 370 /// -regalloc=... command line option.
 371 static cl::opt<RegisterRegAlloc::FunctionPassCtor, false,
 372                RegisterPassParser<RegisterRegAlloc> >
 373 RegAlloc("regalloc",
 374          cl::init(&useDefaultRegisterAllocator),
 375          cl::desc("Register allocator to use"));
 376
 377
 378 /// Instantiate the default register allocator pass for this target for either
 379 /// the optimized or unoptimized allocation path. This will be added to the pass
 380 /// manager by addFastRegAlloc in the unoptimized case or addOptimizedRegAlloc
 381 /// in the optimized case.
 382 ///
 383 /// A target that uses the standard regalloc pass order for fast or optimized
 384 /// allocation may still override this for per-target regalloc
 385 /// selection. But -regalloc=... always takes precedence.
 386 FunctionPass *TargetPassConfig::createTargetRegisterAllocator(bool Optimized) {
 387   if (Optimized)
 388     return createGreedyRegisterAllocator();
 389   else
 390     return createFastRegisterAllocator();
 391 }
 392
 393 /// Find and instantiate the register allocation pass requested by this target
 394 /// at the current optimization level.  Different register allocators are
 395 /// defined as separate passes because they may require different analysis.
 396 ///
 397 /// This helper ensures that the regalloc= option is always available,
 398 /// even for targets that override the default allocator.
 399 ///
 400 /// FIXME: When MachinePassRegistry register pass IDs instead of function ptrs,
 401 /// this can be folded into addPass.
 402 FunctionPass *TargetPassConfig::createRegAllocPass(bool Optimized) {
 403   RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault();
 404
 405   // Initialize the global default.
 406   if (!Ctor) {
 407     Ctor = RegAlloc;
 408     RegisterRegAlloc::setDefault(RegAlloc);
 409   }
 410   if (Ctor != useDefaultRegisterAllocator)
 411     return Ctor();
 412
 413   // With no -regalloc= override, ask the target for a regalloc pass.
 414   return createTargetRegisterAllocator(Optimized);
 415 }
 416
 417 /// Add the minimum set of target-independent passes that are required for
 418 /// register allocation. No coalescing or scheduling.
 419 void TargetPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) {
 420   addPass(PHIEliminationID);
 421   addPass(TwoAddressInstructionPassID);
 422
 423   PM.add(RegAllocPass);
 424   printAndVerify("After Register Allocation");
 425 }
 426
 427 /// Add standard target-independent passes that are tightly coupled with
 428 /// optimized register allocation, including coalescing, machine instruction
 429 /// scheduling, and register allocation itself.
 430 void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) {
 431   // LiveVariables currently requires pure SSA form.
 432   //
 433   // FIXME: Once TwoAddressInstruction pass no longer uses kill flags,
 434   // LiveVariables can be removed completely, and LiveIntervals can be directly
 435   // computed. (We still either need to regenerate kill flags after regalloc, or
 436   // preferably fix the scavenger to not depend on them).
 437   addPass(LiveVariablesID);
 438
 439   // Add passes that move from transformed SSA into conventional SSA. This is a
 440   // "copy coalescing" problem.
 441   //
 442   if (!EnableStrongPHIElim) {
 443     // Edge splitting is smarter with machine loop info.
 444     addPass(MachineLoopInfoID);
 445     addPass(PHIEliminationID);
 446   }
 447   addPass(TwoAddressInstructionPassID);
 448
 449   // FIXME: Either remove this pass completely, or fix it so that it works on
 450   // SSA form. We could modify LiveIntervals to be independent of this pass, But
 451   // it would be even better to simply eliminate *all* IMPLICIT_DEFs before
 452   // leaving SSA.
 453   addPass(ProcessImplicitDefsID);
 454
 455   if (EnableStrongPHIElim)
 456     addPass(StrongPHIEliminationID);
 457
 458   addPass(RegisterCoalescerID);
 459
 460   // PreRA instruction scheduling.
 461   addPass(enablePass(getSchedPass(), EnableMachineSched, &MachineSchedulerID));
 462
 463   // Add the selected register allocation pass.
 464   PM.add(RegAllocPass);
 465   printAndVerify("After Register Allocation");
 466
 467   // FinalizeRegAlloc is convenient until MachineInstrBundles is more mature,
 468   // but eventually, all users of it should probably be moved to addPostRA and
 469   // it can go away.  Currently, it's the intended place for targets to run
 470   // FinalizeMachineBundles, because passes other than MachineScheduling an
 471   // RegAlloc itself may not be aware of bundles.
 472   if (addFinalizeRegAlloc())
 473     printAndVerify("After RegAlloc finalization");
 474
 475   // Perform stack slot coloring and post-ra machine LICM.
 476   //
 477   // FIXME: Re-enable coloring with register when it's capable of adding
 478   // kill markers.
 479   if (!DisableSSC)
 480     addPass(StackSlotColoringID);
 481
 482   // Run post-ra machine LICM to hoist reloads / remats.
 483   //
 484   // FIXME: can this move into MachineLateOptimization?
 485   if (!DisablePostRAMachineLICM)
 486     addPass(MachineLICMID);
 487
 488   printAndVerify("After StackSlotColoring and postra Machine LICM");
 489 }
 490
 491 //===---------------------------------------------------------------------===//
 492 /// Post RegAlloc Pass Configuration
 493 //===---------------------------------------------------------------------===//
 494
 495 /// Add passes that optimize machine instructions after register allocation.
 496 void TargetPassConfig::addMachineLateOptimization() {
 497   // Branch folding must be run after regalloc and prolog/epilog insertion.
 498   if (!DisableBranchFold) {
 499     addPass(BranchFolderPassID);
 500     printNoVerify("After BranchFolding");
 501   }
 502
 503   // Tail duplication.
 504   if (!DisableTailDuplicate) {
 505     addPass(TailDuplicateID);
 506     printNoVerify("After TailDuplicate");
 507   }
 508
 509   // Copy propagation.
 510   if (!DisableCopyProp) {
 511     addPass(MachineCopyPropagationID);
 512     printNoVerify("After copy propagation pass");
 513   }
 514 }
 515
 516 /// Add standard basic block placement passes.
 517 void TargetPassConfig::addBlockPlacement() {
 518   if (EnableBlockPlacement) {
 519     // MachineBlockPlacement is an experimental pass which is disabled by
 520     // default currently. Eventually it should subsume CodePlacementOpt, so
 521     // when enabled, the other is disabled.
 522     addPass(MachineBlockPlacementID);
 523     printNoVerify("After MachineBlockPlacement");
 524   } else {
 525     addPass(CodePlacementOptID);
 526     printNoVerify("After CodePlacementOpt");
 527   }
 528
 529   // Run a separate pass to collect block placement statistics.
 530   if (EnableBlockPlacementStats) {
 531     addPass(MachineBlockPlacementStatsID);
 532     printNoVerify("After MachineBlockPlacementStats");
 533   }
 534 }