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 = (const char *)(TPI->getTypeInfo()); 451 const char *IID = (const 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 if (addPass(&ExpandISelPseudosID)) 460 printAndVerify("After ExpandISelPseudos"); 461 462 // Add passes that optimize machine instructions in SSA form. 463 if (getOptLevel() != CodeGenOpt::None) { 464 addMachineSSAOptimization(); 465 } 466 else { 467 // If the target requests it, assign local variables to stack slots relative 468 // to one another and simplify frame index references where possible. 469 addPass(&LocalStackSlotAllocationID); 470 } 471 472 // Run pre-ra passes. 473 if (addPreRegAlloc()) 474 printAndVerify("After PreRegAlloc passes"); 475 476 // Run register allocation and passes that are tightly coupled with it, 477 // including phi elimination and scheduling. 478 if (getOptimizeRegAlloc()) 479 addOptimizedRegAlloc(createRegAllocPass(true)); 480 else 481 addFastRegAlloc(createRegAllocPass(false)); 482 483 // Run post-ra passes. 484 if (addPostRegAlloc()) 485 printAndVerify("After PostRegAlloc passes"); 486 487 // Insert prolog/epilog code. Eliminate abstract frame index references... 488 addPass(&PrologEpilogCodeInserterID); 489 printAndVerify("After PrologEpilogCodeInserter"); 490 491 /// Add passes that optimize machine instructions after register allocation. 492 if (getOptLevel() != CodeGenOpt::None) 493 addMachineLateOptimization(); 494 495 // Expand pseudo instructions before second scheduling pass. 496 addPass(&ExpandPostRAPseudosID); 497 printAndVerify("After ExpandPostRAPseudos"); 498 499 // Run pre-sched2 passes. 500 if (addPreSched2()) 501 printAndVerify("After PreSched2 passes"); 502 503 // Second pass scheduler. 504 if (getOptLevel() != CodeGenOpt::None) { 505 addPass(&PostRASchedulerID); 506 printAndVerify("After PostRAScheduler"); 507 } 508 509 // GC 510 addPass(&GCMachineCodeAnalysisID); 511 if (PrintGCInfo) 512 addPass(createGCInfoPrinter(dbgs())); 513 514 // Basic block placement. 515 if (getOptLevel() != CodeGenOpt::None) 516 addBlockPlacement(); 517 518 if (addPreEmitPass()) 519 printAndVerify("After PreEmit passes"); 520} 521 522/// Add passes that optimize machine instructions in SSA form. 523void TargetPassConfig::addMachineSSAOptimization() { 524 // Pre-ra tail duplication. 525 if (addPass(&EarlyTailDuplicateID)) 526 printAndVerify("After Pre-RegAlloc TailDuplicate"); 527 528 // Optimize PHIs before DCE: removing dead PHI cycles may make more 529 // instructions dead. 530 addPass(&OptimizePHIsID); 531 532 // This pass merges large allocas. StackSlotColoring is a different pass 533 // which merges spill slots. 534 addPass(&StackColoringID); 535 536 // If the target requests it, assign local variables to stack slots relative 537 // to one another and simplify frame index references where possible. 538 addPass(&LocalStackSlotAllocationID); 539 540 // With optimization, dead code should already be eliminated. However 541 // there is one known exception: lowered code for arguments that are only 542 // used by tail calls, where the tail calls reuse the incoming stack 543 // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll). 544 addPass(&DeadMachineInstructionElimID); 545 printAndVerify("After codegen DCE pass"); 546 547 addPass(&EarlyIfConverterID); 548 addPass(&MachineLICMID); 549 addPass(&MachineCSEID); 550 addPass(&MachineSinkingID); 551 printAndVerify("After Machine LICM, CSE and Sinking passes"); 552 553 addPass(&PeepholeOptimizerID); 554 printAndVerify("After codegen peephole optimization pass"); 555} 556 557//===---------------------------------------------------------------------===// 558/// Register Allocation Pass Configuration 559//===---------------------------------------------------------------------===// 560 561bool TargetPassConfig::getOptimizeRegAlloc() const { 562 switch (OptimizeRegAlloc) { 563 case cl::BOU_UNSET: return getOptLevel() != CodeGenOpt::None; 564 case cl::BOU_TRUE: return true; 565 case cl::BOU_FALSE: return false; 566 } 567 llvm_unreachable("Invalid optimize-regalloc state"); 568} 569 570/// RegisterRegAlloc's global Registry tracks allocator registration. 571MachinePassRegistry RegisterRegAlloc::Registry; 572 573/// A dummy default pass factory indicates whether the register allocator is 574/// overridden on the command line. 575static FunctionPass *useDefaultRegisterAllocator() { return 0; } 576static RegisterRegAlloc 577defaultRegAlloc("default", 578 "pick register allocator based on -O option", 579 useDefaultRegisterAllocator); 580 581/// -regalloc=... command line option. 582static cl::opt<RegisterRegAlloc::FunctionPassCtor, false, 583 RegisterPassParser<RegisterRegAlloc> > 584RegAlloc("regalloc", 585 cl::init(&useDefaultRegisterAllocator), 586 cl::desc("Register allocator to use")); 587 588 589/// Instantiate the default register allocator pass for this target for either 590/// the optimized or unoptimized allocation path. This will be added to the pass 591/// manager by addFastRegAlloc in the unoptimized case or addOptimizedRegAlloc 592/// in the optimized case. 593/// 594/// A target that uses the standard regalloc pass order for fast or optimized 595/// allocation may still override this for per-target regalloc 596/// selection. But -regalloc=... always takes precedence. 597FunctionPass *TargetPassConfig::createTargetRegisterAllocator(bool Optimized) { 598 if (Optimized) 599 return createGreedyRegisterAllocator(); 600 else 601 return createFastRegisterAllocator(); 602} 603 604/// Find and instantiate the register allocation pass requested by this target 605/// at the current optimization level. Different register allocators are 606/// defined as separate passes because they may require different analysis. 607/// 608/// This helper ensures that the regalloc= option is always available, 609/// even for targets that override the default allocator. 610/// 611/// FIXME: When MachinePassRegistry register pass IDs instead of function ptrs, 612/// this can be folded into addPass. 613FunctionPass *TargetPassConfig::createRegAllocPass(bool Optimized) { 614 RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault(); 615 616 // Initialize the global default. 617 if (!Ctor) { 618 Ctor = RegAlloc; 619 RegisterRegAlloc::setDefault(RegAlloc); 620 } 621 if (Ctor != useDefaultRegisterAllocator) 622 return Ctor(); 623 624 // With no -regalloc= override, ask the target for a regalloc pass. 625 return createTargetRegisterAllocator(Optimized); 626} 627 628/// Add the minimum set of target-independent passes that are required for 629/// register allocation. No coalescing or scheduling. 630void TargetPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) { 631 addPass(&PHIEliminationID); 632 addPass(&TwoAddressInstructionPassID); 633 634 addPass(RegAllocPass); 635 printAndVerify("After Register Allocation"); 636} 637 638/// Add standard target-independent passes that are tightly coupled with 639/// optimized register allocation, including coalescing, machine instruction 640/// scheduling, and register allocation itself. 641void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) { 642 addPass(&ProcessImplicitDefsID); 643 644 // LiveVariables currently requires pure SSA form. 645 // 646 // FIXME: Once TwoAddressInstruction pass no longer uses kill flags, 647 // LiveVariables can be removed completely, and LiveIntervals can be directly 648 // computed. (We still either need to regenerate kill flags after regalloc, or 649 // preferably fix the scavenger to not depend on them). 650 addPass(&LiveVariablesID); 651 652 // Add passes that move from transformed SSA into conventional SSA. This is a 653 // "copy coalescing" problem. 654 // 655 if (!EnableStrongPHIElim) { 656 // Edge splitting is smarter with machine loop info. 657 addPass(&MachineLoopInfoID); 658 addPass(&PHIEliminationID); 659 } 660 661 // Eventually, we want to run LiveIntervals before PHI elimination. 662 if (EarlyLiveIntervals) 663 addPass(&LiveIntervalsID); 664 665 addPass(&TwoAddressInstructionPassID); 666 667 if (EnableStrongPHIElim) 668 addPass(&StrongPHIEliminationID); 669 670 addPass(&RegisterCoalescerID); 671 672 // PreRA instruction scheduling. 673 if (addPass(&MachineSchedulerID)) 674 printAndVerify("After Machine Scheduling"); 675 676 // Add the selected register allocation pass. 677 addPass(RegAllocPass); 678 printAndVerify("After Register Allocation, before rewriter"); 679 680 // Allow targets to change the register assignments before rewriting. 681 if (addPreRewrite()) 682 printAndVerify("After pre-rewrite passes"); 683 684 // Finally rewrite virtual registers. 685 addPass(&VirtRegRewriterID); 686 printAndVerify("After Virtual Register Rewriter"); 687 688 // FinalizeRegAlloc is convenient until MachineInstrBundles is more mature, 689 // but eventually, all users of it should probably be moved to addPostRA and 690 // it can go away. Currently, it's the intended place for targets to run 691 // FinalizeMachineBundles, because passes other than MachineScheduling an 692 // RegAlloc itself may not be aware of bundles. 693 if (addFinalizeRegAlloc()) 694 printAndVerify("After RegAlloc finalization"); 695 696 // Perform stack slot coloring and post-ra machine LICM. 697 // 698 // FIXME: Re-enable coloring with register when it's capable of adding 699 // kill markers. 700 addPass(&StackSlotColoringID); 701 702 // Run post-ra machine LICM to hoist reloads / remats. 703 // 704 // FIXME: can this move into MachineLateOptimization? 705 addPass(&PostRAMachineLICMID); 706 707 printAndVerify("After StackSlotColoring and postra Machine LICM"); 708} 709 710//===---------------------------------------------------------------------===// 711/// Post RegAlloc Pass Configuration 712//===---------------------------------------------------------------------===// 713 714/// Add passes that optimize machine instructions after register allocation. 715void TargetPassConfig::addMachineLateOptimization() { 716 // Branch folding must be run after regalloc and prolog/epilog insertion. 717 if (addPass(&BranchFolderPassID)) 718 printAndVerify("After BranchFolding"); 719 720 // Tail duplication. 721 if (addPass(&TailDuplicateID)) 722 printAndVerify("After TailDuplicate"); 723 724 // Copy propagation. 725 if (addPass(&MachineCopyPropagationID)) 726 printAndVerify("After copy propagation pass"); 727} 728 729/// Add standard basic block placement passes. 730void TargetPassConfig::addBlockPlacement() { 731 AnalysisID PassID = 0; 732 if (!DisableBlockPlacement) { 733 // MachineBlockPlacement is a new pass which subsumes the functionality of 734 // CodPlacementOpt. The old code placement pass can be restored by 735 // disabling block placement, but eventually it will be removed. 736 PassID = addPass(&MachineBlockPlacementID); 737 } else { 738 PassID = addPass(&CodePlacementOptID); 739 } 740 if (PassID) { 741 // Run a separate pass to collect block placement statistics. 742 if (EnableBlockPlacementStats) 743 addPass(&MachineBlockPlacementStatsID); 744 745 printAndVerify("After machine block placement."); 746 } 747} 748