Passes.cpp revision 239462
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/MC/MCAsmInfo.h" 26#include "llvm/Assembly/PrintModulePass.h" 27#include "llvm/Support/CommandLine.h" 28#include "llvm/Support/Debug.h" 29#include "llvm/Support/ErrorHandling.h" 30 31using namespace llvm; 32 33static cl::opt<bool> DisablePostRA("disable-post-ra", cl::Hidden, 34 cl::desc("Disable Post Regalloc")); 35static cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden, 36 cl::desc("Disable branch folding")); 37static cl::opt<bool> DisableTailDuplicate("disable-tail-duplicate", cl::Hidden, 38 cl::desc("Disable tail duplication")); 39static cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden, 40 cl::desc("Disable pre-register allocation tail duplication")); 41static cl::opt<bool> DisableBlockPlacement("disable-block-placement", 42 cl::Hidden, cl::desc("Disable the probability-driven block placement, and " 43 "re-enable the old code placement pass")); 44static cl::opt<bool> EnableBlockPlacementStats("enable-block-placement-stats", 45 cl::Hidden, cl::desc("Collect probability-driven block placement stats")); 46static cl::opt<bool> DisableCodePlace("disable-code-place", cl::Hidden, 47 cl::desc("Disable code placement")); 48static cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden, 49 cl::desc("Disable Stack Slot Coloring")); 50static cl::opt<bool> DisableMachineDCE("disable-machine-dce", cl::Hidden, 51 cl::desc("Disable Machine Dead Code Elimination")); 52static cl::opt<bool> EnableEarlyIfConversion("enable-early-ifcvt", cl::Hidden, 53 cl::desc("Enable Early If-conversion")); 54static cl::opt<bool> DisableMachineLICM("disable-machine-licm", cl::Hidden, 55 cl::desc("Disable Machine LICM")); 56static cl::opt<bool> DisableMachineCSE("disable-machine-cse", cl::Hidden, 57 cl::desc("Disable Machine Common Subexpression Elimination")); 58static cl::opt<cl::boolOrDefault> 59OptimizeRegAlloc("optimize-regalloc", cl::Hidden, 60 cl::desc("Enable optimized register allocation compilation path.")); 61static cl::opt<cl::boolOrDefault> 62EnableMachineSched("enable-misched", cl::Hidden, 63 cl::desc("Enable the machine instruction scheduling pass.")); 64static cl::opt<bool> EnableStrongPHIElim("strong-phi-elim", cl::Hidden, 65 cl::desc("Use strong PHI elimination.")); 66static cl::opt<bool> DisablePostRAMachineLICM("disable-postra-machine-licm", 67 cl::Hidden, 68 cl::desc("Disable Machine LICM")); 69static cl::opt<bool> DisableMachineSink("disable-machine-sink", cl::Hidden, 70 cl::desc("Disable Machine Sinking")); 71static cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden, 72 cl::desc("Disable Loop Strength Reduction Pass")); 73static cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden, 74 cl::desc("Disable Codegen Prepare")); 75static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden, 76 cl::desc("Disable Copy Propagation pass")); 77static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden, 78 cl::desc("Print LLVM IR produced by the loop-reduce pass")); 79static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden, 80 cl::desc("Print LLVM IR input to isel pass")); 81static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden, 82 cl::desc("Dump garbage collector data")); 83static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden, 84 cl::desc("Verify generated machine code"), 85 cl::init(getenv("LLVM_VERIFY_MACHINEINSTRS")!=NULL)); 86static cl::opt<std::string> 87PrintMachineInstrs("print-machineinstrs", cl::ValueOptional, 88 cl::desc("Print machine instrs"), 89 cl::value_desc("pass-name"), cl::init("option-unspecified")); 90 91// Experimental option to run live inteerval analysis early. 92static cl::opt<bool> EarlyLiveIntervals("early-live-intervals", cl::Hidden, 93 cl::desc("Run live interval analysis earlier in the pipeline")); 94 95/// Allow standard passes to be disabled by command line options. This supports 96/// simple binary flags that either suppress the pass or do nothing. 97/// i.e. -disable-mypass=false has no effect. 98/// These should be converted to boolOrDefault in order to use applyOverride. 99static AnalysisID applyDisable(AnalysisID PassID, bool Override) { 100 if (Override) 101 return 0; 102 return PassID; 103} 104 105/// Allow Pass selection to be overriden by command line options. This supports 106/// flags with ternary conditions. TargetID is passed through by default. The 107/// pass is suppressed when the option is false. When the option is true, the 108/// StandardID is selected if the target provides no default. 109static AnalysisID applyOverride(AnalysisID TargetID, cl::boolOrDefault Override, 110 AnalysisID StandardID) { 111 switch (Override) { 112 case cl::BOU_UNSET: 113 return TargetID; 114 case cl::BOU_TRUE: 115 if (TargetID) 116 return TargetID; 117 if (StandardID == 0) 118 report_fatal_error("Target cannot enable pass"); 119 return StandardID; 120 case cl::BOU_FALSE: 121 return 0; 122 } 123 llvm_unreachable("Invalid command line option state"); 124} 125 126/// Allow standard passes to be disabled by the command line, regardless of who 127/// is adding the pass. 128/// 129/// StandardID is the pass identified in the standard pass pipeline and provided 130/// to addPass(). It may be a target-specific ID in the case that the target 131/// directly adds its own pass, but in that case we harmlessly fall through. 132/// 133/// TargetID is the pass that the target has configured to override StandardID. 134/// 135/// StandardID may be a pseudo ID. In that case TargetID is the name of the real 136/// pass to run. This allows multiple options to control a single pass depending 137/// on where in the pipeline that pass is added. 138static AnalysisID overridePass(AnalysisID StandardID, AnalysisID TargetID) { 139 if (StandardID == &PostRASchedulerID) 140 return applyDisable(TargetID, DisablePostRA); 141 142 if (StandardID == &BranchFolderPassID) 143 return applyDisable(TargetID, DisableBranchFold); 144 145 if (StandardID == &TailDuplicateID) 146 return applyDisable(TargetID, DisableTailDuplicate); 147 148 if (StandardID == &TargetPassConfig::EarlyTailDuplicateID) 149 return applyDisable(TargetID, DisableEarlyTailDup); 150 151 if (StandardID == &MachineBlockPlacementID) 152 return applyDisable(TargetID, DisableCodePlace); 153 154 if (StandardID == &CodePlacementOptID) 155 return applyDisable(TargetID, DisableCodePlace); 156 157 if (StandardID == &StackSlotColoringID) 158 return applyDisable(TargetID, DisableSSC); 159 160 if (StandardID == &DeadMachineInstructionElimID) 161 return applyDisable(TargetID, DisableMachineDCE); 162 163 if (StandardID == &EarlyIfConverterID) 164 return applyDisable(TargetID, !EnableEarlyIfConversion); 165 166 if (StandardID == &MachineLICMID) 167 return applyDisable(TargetID, DisableMachineLICM); 168 169 if (StandardID == &MachineCSEID) 170 return applyDisable(TargetID, DisableMachineCSE); 171 172 if (StandardID == &MachineSchedulerID) 173 return applyOverride(TargetID, EnableMachineSched, StandardID); 174 175 if (StandardID == &TargetPassConfig::PostRAMachineLICMID) 176 return applyDisable(TargetID, DisablePostRAMachineLICM); 177 178 if (StandardID == &MachineSinkingID) 179 return applyDisable(TargetID, DisableMachineSink); 180 181 if (StandardID == &MachineCopyPropagationID) 182 return applyDisable(TargetID, DisableCopyProp); 183 184 return TargetID; 185} 186 187//===---------------------------------------------------------------------===// 188/// TargetPassConfig 189//===---------------------------------------------------------------------===// 190 191INITIALIZE_PASS(TargetPassConfig, "targetpassconfig", 192 "Target Pass Configuration", false, false) 193char TargetPassConfig::ID = 0; 194 195// Pseudo Pass IDs. 196char TargetPassConfig::EarlyTailDuplicateID = 0; 197char TargetPassConfig::PostRAMachineLICMID = 0; 198 199namespace llvm { 200class PassConfigImpl { 201public: 202 // List of passes explicitly substituted by this target. Normally this is 203 // empty, but it is a convenient way to suppress or replace specific passes 204 // that are part of a standard pass pipeline without overridding the entire 205 // pipeline. This mechanism allows target options to inherit a standard pass's 206 // user interface. For example, a target may disable a standard pass by 207 // default by substituting a pass ID of zero, and the user may still enable 208 // that standard pass with an explicit command line option. 209 DenseMap<AnalysisID,AnalysisID> TargetPasses; 210 211 /// Store the pairs of <AnalysisID, AnalysisID> of which the second pass 212 /// is inserted after each instance of the first one. 213 SmallVector<std::pair<AnalysisID, AnalysisID>, 4> InsertedPasses; 214}; 215} // namespace llvm 216 217// Out of line virtual method. 218TargetPassConfig::~TargetPassConfig() { 219 delete Impl; 220} 221 222// Out of line constructor provides default values for pass options and 223// registers all common codegen passes. 224TargetPassConfig::TargetPassConfig(TargetMachine *tm, PassManagerBase &pm) 225 : ImmutablePass(ID), PM(&pm), StartAfter(0), StopAfter(0), 226 Started(true), Stopped(false), TM(tm), Impl(0), Initialized(false), 227 DisableVerify(false), 228 EnableTailMerge(true) { 229 230 Impl = new PassConfigImpl(); 231 232 // Register all target independent codegen passes to activate their PassIDs, 233 // including this pass itself. 234 initializeCodeGen(*PassRegistry::getPassRegistry()); 235 236 // Substitute Pseudo Pass IDs for real ones. 237 substitutePass(&EarlyTailDuplicateID, &TailDuplicateID); 238 substitutePass(&PostRAMachineLICMID, &MachineLICMID); 239 240 // Disable early if-conversion. Targets that are ready can enable it. 241 disablePass(&EarlyIfConverterID); 242 243 // Temporarily disable experimental passes. 244 substitutePass(&MachineSchedulerID, 0); 245} 246 247/// Insert InsertedPassID pass after TargetPassID. 248void TargetPassConfig::insertPass(AnalysisID TargetPassID, 249 AnalysisID InsertedPassID) { 250 assert(TargetPassID != InsertedPassID && "Insert a pass after itself!"); 251 std::pair<AnalysisID, AnalysisID> P(TargetPassID, InsertedPassID); 252 Impl->InsertedPasses.push_back(P); 253} 254 255/// createPassConfig - Create a pass configuration object to be used by 256/// addPassToEmitX methods for generating a pipeline of CodeGen passes. 257/// 258/// Targets may override this to extend TargetPassConfig. 259TargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM) { 260 return new TargetPassConfig(this, PM); 261} 262 263TargetPassConfig::TargetPassConfig() 264 : ImmutablePass(ID), PM(0) { 265 llvm_unreachable("TargetPassConfig should not be constructed on-the-fly"); 266} 267 268// Helper to verify the analysis is really immutable. 269void TargetPassConfig::setOpt(bool &Opt, bool Val) { 270 assert(!Initialized && "PassConfig is immutable"); 271 Opt = Val; 272} 273 274void TargetPassConfig::substitutePass(AnalysisID StandardID, 275 AnalysisID TargetID) { 276 Impl->TargetPasses[StandardID] = TargetID; 277} 278 279AnalysisID TargetPassConfig::getPassSubstitution(AnalysisID ID) const { 280 DenseMap<AnalysisID, AnalysisID>::const_iterator 281 I = Impl->TargetPasses.find(ID); 282 if (I == Impl->TargetPasses.end()) 283 return ID; 284 return I->second; 285} 286 287/// Add a pass to the PassManager if that pass is supposed to be run. If the 288/// Started/Stopped flags indicate either that the compilation should start at 289/// a later pass or that it should stop after an earlier pass, then do not add 290/// the pass. Finally, compare the current pass against the StartAfter 291/// and StopAfter options and change the Started/Stopped flags accordingly. 292void TargetPassConfig::addPass(Pass *P) { 293 assert(!Initialized && "PassConfig is immutable"); 294 295 // Cache the Pass ID here in case the pass manager finds this pass is 296 // redundant with ones already scheduled / available, and deletes it. 297 // Fundamentally, once we add the pass to the manager, we no longer own it 298 // and shouldn't reference it. 299 AnalysisID PassID = P->getPassID(); 300 301 if (Started && !Stopped) 302 PM->add(P); 303 if (StopAfter == PassID) 304 Stopped = true; 305 if (StartAfter == PassID) 306 Started = true; 307 if (Stopped && !Started) 308 report_fatal_error("Cannot stop compilation after pass that is not run"); 309} 310 311/// Add a CodeGen pass at this point in the pipeline after checking for target 312/// and command line overrides. 313AnalysisID TargetPassConfig::addPass(AnalysisID PassID) { 314 AnalysisID TargetID = getPassSubstitution(PassID); 315 AnalysisID FinalID = overridePass(PassID, TargetID); 316 if (FinalID == 0) 317 return FinalID; 318 319 Pass *P = Pass::createPass(FinalID); 320 if (!P) 321 llvm_unreachable("Pass ID not registered"); 322 addPass(P); 323 // Add the passes after the pass P if there is any. 324 for (SmallVector<std::pair<AnalysisID, AnalysisID>, 4>::iterator 325 I = Impl->InsertedPasses.begin(), E = Impl->InsertedPasses.end(); 326 I != E; ++I) { 327 if ((*I).first == PassID) { 328 assert((*I).second && "Illegal Pass ID!"); 329 Pass *NP = Pass::createPass((*I).second); 330 assert(NP && "Pass ID not registered"); 331 addPass(NP); 332 } 333 } 334 return FinalID; 335} 336 337void TargetPassConfig::printAndVerify(const char *Banner) { 338 if (TM->shouldPrintMachineCode()) 339 addPass(createMachineFunctionPrinterPass(dbgs(), Banner)); 340 341 if (VerifyMachineCode) 342 addPass(createMachineVerifierPass(Banner)); 343} 344 345/// Add common target configurable passes that perform LLVM IR to IR transforms 346/// following machine independent optimization. 347void TargetPassConfig::addIRPasses() { 348 // Basic AliasAnalysis support. 349 // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that 350 // BasicAliasAnalysis wins if they disagree. This is intended to help 351 // support "obvious" type-punning idioms. 352 addPass(createTypeBasedAliasAnalysisPass()); 353 addPass(createBasicAliasAnalysisPass()); 354 355 // Before running any passes, run the verifier to determine if the input 356 // coming from the front-end and/or optimizer is valid. 357 if (!DisableVerify) 358 addPass(createVerifierPass()); 359 360 // Run loop strength reduction before anything else. 361 if (getOptLevel() != CodeGenOpt::None && !DisableLSR) { 362 addPass(createLoopStrengthReducePass(getTargetLowering())); 363 if (PrintLSR) 364 addPass(createPrintFunctionPass("\n\n*** Code after LSR ***\n", &dbgs())); 365 } 366 367 addPass(createGCLoweringPass()); 368 369 // Make sure that no unreachable blocks are instruction selected. 370 addPass(createUnreachableBlockEliminationPass()); 371} 372 373/// Turn exception handling constructs into something the code generators can 374/// handle. 375void TargetPassConfig::addPassesToHandleExceptions() { 376 switch (TM->getMCAsmInfo()->getExceptionHandlingType()) { 377 case ExceptionHandling::SjLj: 378 // SjLj piggy-backs on dwarf for this bit. The cleanups done apply to both 379 // Dwarf EH prepare needs to be run after SjLj prepare. Otherwise, 380 // catch info can get misplaced when a selector ends up more than one block 381 // removed from the parent invoke(s). This could happen when a landing 382 // pad is shared by multiple invokes and is also a target of a normal 383 // edge from elsewhere. 384 addPass(createSjLjEHPreparePass(TM->getTargetLowering())); 385 // FALLTHROUGH 386 case ExceptionHandling::DwarfCFI: 387 case ExceptionHandling::ARM: 388 case ExceptionHandling::Win64: 389 addPass(createDwarfEHPass(TM)); 390 break; 391 case ExceptionHandling::None: 392 addPass(createLowerInvokePass(TM->getTargetLowering())); 393 394 // The lower invoke pass may create unreachable code. Remove it. 395 addPass(createUnreachableBlockEliminationPass()); 396 break; 397 } 398} 399 400/// Add common passes that perform LLVM IR to IR transforms in preparation for 401/// instruction selection. 402void TargetPassConfig::addISelPrepare() { 403 if (getOptLevel() != CodeGenOpt::None && !DisableCGP) 404 addPass(createCodeGenPreparePass(getTargetLowering())); 405 406 addPass(createStackProtectorPass(getTargetLowering())); 407 408 addPreISel(); 409 410 if (PrintISelInput) 411 addPass(createPrintFunctionPass("\n\n" 412 "*** Final LLVM Code input to ISel ***\n", 413 &dbgs())); 414 415 // All passes which modify the LLVM IR are now complete; run the verifier 416 // to ensure that the IR is valid. 417 if (!DisableVerify) 418 addPass(createVerifierPass()); 419} 420 421/// Add the complete set of target-independent postISel code generator passes. 422/// 423/// This can be read as the standard order of major LLVM CodeGen stages. Stages 424/// with nontrivial configuration or multiple passes are broken out below in 425/// add%Stage routines. 426/// 427/// Any TargetPassConfig::addXX routine may be overriden by the Target. The 428/// addPre/Post methods with empty header implementations allow injecting 429/// target-specific fixups just before or after major stages. Additionally, 430/// targets have the flexibility to change pass order within a stage by 431/// overriding default implementation of add%Stage routines below. Each 432/// technique has maintainability tradeoffs because alternate pass orders are 433/// not well supported. addPre/Post works better if the target pass is easily 434/// tied to a common pass. But if it has subtle dependencies on multiple passes, 435/// the target should override the stage instead. 436/// 437/// TODO: We could use a single addPre/Post(ID) hook to allow pass injection 438/// before/after any target-independent pass. But it's currently overkill. 439void TargetPassConfig::addMachinePasses() { 440 // Insert a machine instr printer pass after the specified pass. 441 // If -print-machineinstrs specified, print machineinstrs after all passes. 442 if (StringRef(PrintMachineInstrs.getValue()).equals("")) 443 TM->Options.PrintMachineCode = true; 444 else if (!StringRef(PrintMachineInstrs.getValue()) 445 .equals("option-unspecified")) { 446 const PassRegistry *PR = PassRegistry::getPassRegistry(); 447 const PassInfo *TPI = PR->getPassInfo(PrintMachineInstrs.getValue()); 448 const PassInfo *IPI = PR->getPassInfo(StringRef("print-machineinstrs")); 449 assert (TPI && IPI && "Pass ID not registered!"); 450 const char *TID = (char *)(TPI->getTypeInfo()); 451 const char *IID = (char *)(IPI->getTypeInfo()); 452 insertPass(TID, IID); 453 } 454 455 // Print the instruction selected machine code... 456 printAndVerify("After Instruction Selection"); 457 458 // Expand pseudo-instructions emitted by ISel. 459 addPass(&ExpandISelPseudosID); 460 461 // Add passes that optimize machine instructions in SSA form. 462 if (getOptLevel() != CodeGenOpt::None) { 463 addMachineSSAOptimization(); 464 } 465 else { 466 // If the target requests it, assign local variables to stack slots relative 467 // to one another and simplify frame index references where possible. 468 addPass(&LocalStackSlotAllocationID); 469 } 470 471 // Run pre-ra passes. 472 if (addPreRegAlloc()) 473 printAndVerify("After PreRegAlloc passes"); 474 475 // Run register allocation and passes that are tightly coupled with it, 476 // including phi elimination and scheduling. 477 if (getOptimizeRegAlloc()) 478 addOptimizedRegAlloc(createRegAllocPass(true)); 479 else 480 addFastRegAlloc(createRegAllocPass(false)); 481 482 // Run post-ra passes. 483 if (addPostRegAlloc()) 484 printAndVerify("After PostRegAlloc passes"); 485 486 // Insert prolog/epilog code. Eliminate abstract frame index references... 487 addPass(&PrologEpilogCodeInserterID); 488 printAndVerify("After PrologEpilogCodeInserter"); 489 490 /// Add passes that optimize machine instructions after register allocation. 491 if (getOptLevel() != CodeGenOpt::None) 492 addMachineLateOptimization(); 493 494 // Expand pseudo instructions before second scheduling pass. 495 addPass(&ExpandPostRAPseudosID); 496 printAndVerify("After ExpandPostRAPseudos"); 497 498 // Run pre-sched2 passes. 499 if (addPreSched2()) 500 printAndVerify("After PreSched2 passes"); 501 502 // Second pass scheduler. 503 if (getOptLevel() != CodeGenOpt::None) { 504 addPass(&PostRASchedulerID); 505 printAndVerify("After PostRAScheduler"); 506 } 507 508 // GC 509 addPass(&GCMachineCodeAnalysisID); 510 if (PrintGCInfo) 511 addPass(createGCInfoPrinter(dbgs())); 512 513 // Basic block placement. 514 if (getOptLevel() != CodeGenOpt::None) 515 addBlockPlacement(); 516 517 if (addPreEmitPass()) 518 printAndVerify("After PreEmit passes"); 519} 520 521/// Add passes that optimize machine instructions in SSA form. 522void TargetPassConfig::addMachineSSAOptimization() { 523 // Pre-ra tail duplication. 524 if (addPass(&EarlyTailDuplicateID)) 525 printAndVerify("After Pre-RegAlloc TailDuplicate"); 526 527 // Optimize PHIs before DCE: removing dead PHI cycles may make more 528 // instructions dead. 529 addPass(&OptimizePHIsID); 530 531 // If the target requests it, assign local variables to stack slots relative 532 // to one another and simplify frame index references where possible. 533 addPass(&LocalStackSlotAllocationID); 534 535 // With optimization, dead code should already be eliminated. However 536 // there is one known exception: lowered code for arguments that are only 537 // used by tail calls, where the tail calls reuse the incoming stack 538 // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll). 539 addPass(&DeadMachineInstructionElimID); 540 printAndVerify("After codegen DCE pass"); 541 542 addPass(&EarlyIfConverterID); 543 addPass(&MachineLICMID); 544 addPass(&MachineCSEID); 545 addPass(&MachineSinkingID); 546 printAndVerify("After Machine LICM, CSE and Sinking passes"); 547 548 addPass(&PeepholeOptimizerID); 549 printAndVerify("After codegen peephole optimization pass"); 550} 551 552//===---------------------------------------------------------------------===// 553/// Register Allocation Pass Configuration 554//===---------------------------------------------------------------------===// 555 556bool TargetPassConfig::getOptimizeRegAlloc() const { 557 switch (OptimizeRegAlloc) { 558 case cl::BOU_UNSET: return getOptLevel() != CodeGenOpt::None; 559 case cl::BOU_TRUE: return true; 560 case cl::BOU_FALSE: return false; 561 } 562 llvm_unreachable("Invalid optimize-regalloc state"); 563} 564 565/// RegisterRegAlloc's global Registry tracks allocator registration. 566MachinePassRegistry RegisterRegAlloc::Registry; 567 568/// A dummy default pass factory indicates whether the register allocator is 569/// overridden on the command line. 570static FunctionPass *useDefaultRegisterAllocator() { return 0; } 571static RegisterRegAlloc 572defaultRegAlloc("default", 573 "pick register allocator based on -O option", 574 useDefaultRegisterAllocator); 575 576/// -regalloc=... command line option. 577static cl::opt<RegisterRegAlloc::FunctionPassCtor, false, 578 RegisterPassParser<RegisterRegAlloc> > 579RegAlloc("regalloc", 580 cl::init(&useDefaultRegisterAllocator), 581 cl::desc("Register allocator to use")); 582 583 584/// Instantiate the default register allocator pass for this target for either 585/// the optimized or unoptimized allocation path. This will be added to the pass 586/// manager by addFastRegAlloc in the unoptimized case or addOptimizedRegAlloc 587/// in the optimized case. 588/// 589/// A target that uses the standard regalloc pass order for fast or optimized 590/// allocation may still override this for per-target regalloc 591/// selection. But -regalloc=... always takes precedence. 592FunctionPass *TargetPassConfig::createTargetRegisterAllocator(bool Optimized) { 593 if (Optimized) 594 return createGreedyRegisterAllocator(); 595 else 596 return createFastRegisterAllocator(); 597} 598 599/// Find and instantiate the register allocation pass requested by this target 600/// at the current optimization level. Different register allocators are 601/// defined as separate passes because they may require different analysis. 602/// 603/// This helper ensures that the regalloc= option is always available, 604/// even for targets that override the default allocator. 605/// 606/// FIXME: When MachinePassRegistry register pass IDs instead of function ptrs, 607/// this can be folded into addPass. 608FunctionPass *TargetPassConfig::createRegAllocPass(bool Optimized) { 609 RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault(); 610 611 // Initialize the global default. 612 if (!Ctor) { 613 Ctor = RegAlloc; 614 RegisterRegAlloc::setDefault(RegAlloc); 615 } 616 if (Ctor != useDefaultRegisterAllocator) 617 return Ctor(); 618 619 // With no -regalloc= override, ask the target for a regalloc pass. 620 return createTargetRegisterAllocator(Optimized); 621} 622 623/// Add the minimum set of target-independent passes that are required for 624/// register allocation. No coalescing or scheduling. 625void TargetPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) { 626 addPass(&PHIEliminationID); 627 addPass(&TwoAddressInstructionPassID); 628 629 addPass(RegAllocPass); 630 printAndVerify("After Register Allocation"); 631} 632 633/// Add standard target-independent passes that are tightly coupled with 634/// optimized register allocation, including coalescing, machine instruction 635/// scheduling, and register allocation itself. 636void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) { 637 addPass(&ProcessImplicitDefsID); 638 639 // LiveVariables currently requires pure SSA form. 640 // 641 // FIXME: Once TwoAddressInstruction pass no longer uses kill flags, 642 // LiveVariables can be removed completely, and LiveIntervals can be directly 643 // computed. (We still either need to regenerate kill flags after regalloc, or 644 // preferably fix the scavenger to not depend on them). 645 addPass(&LiveVariablesID); 646 647 // Add passes that move from transformed SSA into conventional SSA. This is a 648 // "copy coalescing" problem. 649 // 650 if (!EnableStrongPHIElim) { 651 // Edge splitting is smarter with machine loop info. 652 addPass(&MachineLoopInfoID); 653 addPass(&PHIEliminationID); 654 } 655 656 // Eventually, we want to run LiveIntervals before PHI elimination. 657 if (EarlyLiveIntervals) 658 addPass(&LiveIntervalsID); 659 660 addPass(&TwoAddressInstructionPassID); 661 662 if (EnableStrongPHIElim) 663 addPass(&StrongPHIEliminationID); 664 665 addPass(&RegisterCoalescerID); 666 667 // PreRA instruction scheduling. 668 if (addPass(&MachineSchedulerID)) 669 printAndVerify("After Machine Scheduling"); 670 671 // Add the selected register allocation pass. 672 addPass(RegAllocPass); 673 printAndVerify("After Register Allocation, before rewriter"); 674 675 // Allow targets to change the register assignments before rewriting. 676 if (addPreRewrite()) 677 printAndVerify("After pre-rewrite passes"); 678 679 // Finally rewrite virtual registers. 680 addPass(&VirtRegRewriterID); 681 printAndVerify("After Virtual Register Rewriter"); 682 683 // FinalizeRegAlloc is convenient until MachineInstrBundles is more mature, 684 // but eventually, all users of it should probably be moved to addPostRA and 685 // it can go away. Currently, it's the intended place for targets to run 686 // FinalizeMachineBundles, because passes other than MachineScheduling an 687 // RegAlloc itself may not be aware of bundles. 688 if (addFinalizeRegAlloc()) 689 printAndVerify("After RegAlloc finalization"); 690 691 // Perform stack slot coloring and post-ra machine LICM. 692 // 693 // FIXME: Re-enable coloring with register when it's capable of adding 694 // kill markers. 695 addPass(&StackSlotColoringID); 696 697 // Run post-ra machine LICM to hoist reloads / remats. 698 // 699 // FIXME: can this move into MachineLateOptimization? 700 addPass(&PostRAMachineLICMID); 701 702 printAndVerify("After StackSlotColoring and postra Machine LICM"); 703} 704 705//===---------------------------------------------------------------------===// 706/// Post RegAlloc Pass Configuration 707//===---------------------------------------------------------------------===// 708 709/// Add passes that optimize machine instructions after register allocation. 710void TargetPassConfig::addMachineLateOptimization() { 711 // Branch folding must be run after regalloc and prolog/epilog insertion. 712 if (addPass(&BranchFolderPassID)) 713 printAndVerify("After BranchFolding"); 714 715 // Tail duplication. 716 if (addPass(&TailDuplicateID)) 717 printAndVerify("After TailDuplicate"); 718 719 // Copy propagation. 720 if (addPass(&MachineCopyPropagationID)) 721 printAndVerify("After copy propagation pass"); 722} 723 724/// Add standard basic block placement passes. 725void TargetPassConfig::addBlockPlacement() { 726 AnalysisID PassID = 0; 727 if (!DisableBlockPlacement) { 728 // MachineBlockPlacement is a new pass which subsumes the functionality of 729 // CodPlacementOpt. The old code placement pass can be restored by 730 // disabling block placement, but eventually it will be removed. 731 PassID = addPass(&MachineBlockPlacementID); 732 } else { 733 PassID = addPass(&CodePlacementOptID); 734 } 735 if (PassID) { 736 // Run a separate pass to collect block placement statistics. 737 if (EnableBlockPlacementStats) 738 addPass(&MachineBlockPlacementStatsID); 739 740 printAndVerify("After machine block placement."); 741 } 742} 743