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/CodeGen/Passes.h" 16#include "llvm/Analysis/Passes.h" 17#include "llvm/Analysis/Verifier.h" 18#include "llvm/Assembly/PrintModulePass.h" 19#include "llvm/CodeGen/GCStrategy.h" 20#include "llvm/CodeGen/MachineFunctionPass.h" 21#include "llvm/CodeGen/RegAllocRegistry.h" 22#include "llvm/MC/MCAsmInfo.h" 23#include "llvm/PassManager.h" 24#include "llvm/Support/CommandLine.h" 25#include "llvm/Support/Debug.h" 26#include "llvm/Support/ErrorHandling.h" 27#include "llvm/Target/TargetLowering.h" 28#include "llvm/Target/TargetSubtargetInfo.h" 29#include "llvm/Transforms/Scalar.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> DisableEarlyIfConversion("disable-early-ifcvt", cl::Hidden, 53 cl::desc("Disable 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 interval 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, DisableEarlyIfConversion); 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 // Temporarily disable experimental passes. 241 const TargetSubtargetInfo &ST = TM->getSubtarget<TargetSubtargetInfo>(); 242 if (!ST.enableMachineScheduler()) 243 disablePass(&MachineSchedulerID); 244} 245 246/// Insert InsertedPassID pass after TargetPassID. 247void TargetPassConfig::insertPass(AnalysisID TargetPassID, 248 AnalysisID InsertedPassID) { 249 assert(TargetPassID != InsertedPassID && "Insert a pass after itself!"); 250 std::pair<AnalysisID, AnalysisID> P(TargetPassID, InsertedPassID); 251 Impl->InsertedPasses.push_back(P); 252} 253 254/// createPassConfig - Create a pass configuration object to be used by 255/// addPassToEmitX methods for generating a pipeline of CodeGen passes. 256/// 257/// Targets may override this to extend TargetPassConfig. 258TargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM) { 259 return new TargetPassConfig(this, PM); 260} 261 262TargetPassConfig::TargetPassConfig() 263 : ImmutablePass(ID), PM(0) { 264 llvm_unreachable("TargetPassConfig should not be constructed on-the-fly"); 265} 266 267// Helper to verify the analysis is really immutable. 268void TargetPassConfig::setOpt(bool &Opt, bool Val) { 269 assert(!Initialized && "PassConfig is immutable"); 270 Opt = Val; 271} 272 273void TargetPassConfig::substitutePass(AnalysisID StandardID, 274 AnalysisID TargetID) { 275 Impl->TargetPasses[StandardID] = TargetID; 276} 277 278AnalysisID TargetPassConfig::getPassSubstitution(AnalysisID ID) const { 279 DenseMap<AnalysisID, AnalysisID>::const_iterator 280 I = Impl->TargetPasses.find(ID); 281 if (I == Impl->TargetPasses.end()) 282 return ID; 283 return I->second; 284} 285 286/// Add a pass to the PassManager if that pass is supposed to be run. If the 287/// Started/Stopped flags indicate either that the compilation should start at 288/// a later pass or that it should stop after an earlier pass, then do not add 289/// the pass. Finally, compare the current pass against the StartAfter 290/// and StopAfter options and change the Started/Stopped flags accordingly. 291void TargetPassConfig::addPass(Pass *P) { 292 assert(!Initialized && "PassConfig is immutable"); 293 294 // Cache the Pass ID here in case the pass manager finds this pass is 295 // redundant with ones already scheduled / available, and deletes it. 296 // Fundamentally, once we add the pass to the manager, we no longer own it 297 // and shouldn't reference it. 298 AnalysisID PassID = P->getPassID(); 299 300 if (Started && !Stopped) 301 PM->add(P); 302 if (StopAfter == PassID) 303 Stopped = true; 304 if (StartAfter == PassID) 305 Started = true; 306 if (Stopped && !Started) 307 report_fatal_error("Cannot stop compilation after pass that is not run"); 308} 309 310/// Add a CodeGen pass at this point in the pipeline after checking for target 311/// and command line overrides. 312AnalysisID TargetPassConfig::addPass(AnalysisID PassID) { 313 AnalysisID TargetID = getPassSubstitution(PassID); 314 AnalysisID FinalID = overridePass(PassID, TargetID); 315 if (FinalID == 0) 316 return FinalID; 317 318 Pass *P = Pass::createPass(FinalID); 319 if (!P) 320 llvm_unreachable("Pass ID not registered"); 321 addPass(P); 322 // Add the passes after the pass P if there is any. 323 for (SmallVector<std::pair<AnalysisID, AnalysisID>, 4>::iterator 324 I = Impl->InsertedPasses.begin(), E = Impl->InsertedPasses.end(); 325 I != E; ++I) { 326 if ((*I).first == PassID) { 327 assert((*I).second && "Illegal Pass ID!"); 328 Pass *NP = Pass::createPass((*I).second); 329 assert(NP && "Pass ID not registered"); 330 addPass(NP); 331 } 332 } 333 return FinalID; 334} 335 336void TargetPassConfig::printAndVerify(const char *Banner) { 337 if (TM->shouldPrintMachineCode()) 338 addPass(createMachineFunctionPrinterPass(dbgs(), Banner)); 339 340 if (VerifyMachineCode) 341 addPass(createMachineVerifierPass(Banner)); 342} 343 344/// Add common target configurable passes that perform LLVM IR to IR transforms 345/// following machine independent optimization. 346void TargetPassConfig::addIRPasses() { 347 // Basic AliasAnalysis support. 348 // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that 349 // BasicAliasAnalysis wins if they disagree. This is intended to help 350 // support "obvious" type-punning idioms. 351 addPass(createTypeBasedAliasAnalysisPass()); 352 addPass(createBasicAliasAnalysisPass()); 353 354 // Before running any passes, run the verifier to determine if the input 355 // coming from the front-end and/or optimizer is valid. 356 if (!DisableVerify) 357 addPass(createVerifierPass()); 358 359 // Run loop strength reduction before anything else. 360 if (getOptLevel() != CodeGenOpt::None && !DisableLSR) { 361 addPass(createLoopStrengthReducePass()); 362 if (PrintLSR) 363 addPass(createPrintFunctionPass("\n\n*** Code after LSR ***\n", &dbgs())); 364 } 365 366 addPass(createGCLoweringPass()); 367 368 // Make sure that no unreachable blocks are instruction selected. 369 addPass(createUnreachableBlockEliminationPass()); 370} 371 372/// Turn exception handling constructs into something the code generators can 373/// handle. 374void TargetPassConfig::addPassesToHandleExceptions() { 375 switch (TM->getMCAsmInfo()->getExceptionHandlingType()) { 376 case ExceptionHandling::SjLj: 377 // SjLj piggy-backs on dwarf for this bit. The cleanups done apply to both 378 // Dwarf EH prepare needs to be run after SjLj prepare. Otherwise, 379 // catch info can get misplaced when a selector ends up more than one block 380 // removed from the parent invoke(s). This could happen when a landing 381 // pad is shared by multiple invokes and is also a target of a normal 382 // edge from elsewhere. 383 addPass(createSjLjEHPreparePass(TM->getTargetLowering())); 384 // FALLTHROUGH 385 case ExceptionHandling::DwarfCFI: 386 case ExceptionHandling::ARM: 387 case ExceptionHandling::Win64: 388 addPass(createDwarfEHPass(TM)); 389 break; 390 case ExceptionHandling::None: 391 addPass(createLowerInvokePass(TM->getTargetLowering())); 392 393 // The lower invoke pass may create unreachable code. Remove it. 394 addPass(createUnreachableBlockEliminationPass()); 395 break; 396 } 397} 398 399/// Add pass to prepare the LLVM IR for code generation. This should be done 400/// before exception handling preparation passes. 401void TargetPassConfig::addCodeGenPrepare() { 402 if (getOptLevel() != CodeGenOpt::None && !DisableCGP) 403 addPass(createCodeGenPreparePass(getTargetLowering())); 404} 405 406/// Add common passes that perform LLVM IR to IR transforms in preparation for 407/// instruction selection. 408void TargetPassConfig::addISelPrepare() { 409 addPass(createStackProtectorPass(getTargetLowering())); 410 411 addPreISel(); 412 413 if (PrintISelInput) 414 addPass(createPrintFunctionPass("\n\n" 415 "*** Final LLVM Code input to ISel ***\n", 416 &dbgs())); 417 418 // All passes which modify the LLVM IR are now complete; run the verifier 419 // to ensure that the IR is valid. 420 if (!DisableVerify) 421 addPass(createVerifierPass()); 422} 423 424/// Add the complete set of target-independent postISel code generator passes. 425/// 426/// This can be read as the standard order of major LLVM CodeGen stages. Stages 427/// with nontrivial configuration or multiple passes are broken out below in 428/// add%Stage routines. 429/// 430/// Any TargetPassConfig::addXX routine may be overriden by the Target. The 431/// addPre/Post methods with empty header implementations allow injecting 432/// target-specific fixups just before or after major stages. Additionally, 433/// targets have the flexibility to change pass order within a stage by 434/// overriding default implementation of add%Stage routines below. Each 435/// technique has maintainability tradeoffs because alternate pass orders are 436/// not well supported. addPre/Post works better if the target pass is easily 437/// tied to a common pass. But if it has subtle dependencies on multiple passes, 438/// the target should override the stage instead. 439/// 440/// TODO: We could use a single addPre/Post(ID) hook to allow pass injection 441/// before/after any target-independent pass. But it's currently overkill. 442void TargetPassConfig::addMachinePasses() { 443 // Insert a machine instr printer pass after the specified pass. 444 // If -print-machineinstrs specified, print machineinstrs after all passes. 445 if (StringRef(PrintMachineInstrs.getValue()).equals("")) 446 TM->Options.PrintMachineCode = true; 447 else if (!StringRef(PrintMachineInstrs.getValue()) 448 .equals("option-unspecified")) { 449 const PassRegistry *PR = PassRegistry::getPassRegistry(); 450 const PassInfo *TPI = PR->getPassInfo(PrintMachineInstrs.getValue()); 451 const PassInfo *IPI = PR->getPassInfo(StringRef("print-machineinstrs")); 452 assert (TPI && IPI && "Pass ID not registered!"); 453 const char *TID = (const char *)(TPI->getTypeInfo()); 454 const char *IID = (const char *)(IPI->getTypeInfo()); 455 insertPass(TID, IID); 456 } 457 458 // Print the instruction selected machine code... 459 printAndVerify("After Instruction Selection"); 460 461 // Expand pseudo-instructions emitted by ISel. 462 if (addPass(&ExpandISelPseudosID)) 463 printAndVerify("After ExpandISelPseudos"); 464 465 // Add passes that optimize machine instructions in SSA form. 466 if (getOptLevel() != CodeGenOpt::None) { 467 addMachineSSAOptimization(); 468 } else { 469 // If the target requests it, assign local variables to stack slots relative 470 // to one another and simplify frame index references where possible. 471 addPass(&LocalStackSlotAllocationID); 472 } 473 474 // Run pre-ra passes. 475 if (addPreRegAlloc()) 476 printAndVerify("After PreRegAlloc passes"); 477 478 // Run register allocation and passes that are tightly coupled with it, 479 // including phi elimination and scheduling. 480 if (getOptimizeRegAlloc()) 481 addOptimizedRegAlloc(createRegAllocPass(true)); 482 else 483 addFastRegAlloc(createRegAllocPass(false)); 484 485 // Run post-ra passes. 486 if (addPostRegAlloc()) 487 printAndVerify("After PostRegAlloc passes"); 488 489 // Insert prolog/epilog code. Eliminate abstract frame index references... 490 addPass(&PrologEpilogCodeInserterID); 491 printAndVerify("After PrologEpilogCodeInserter"); 492 493 /// Add passes that optimize machine instructions after register allocation. 494 if (getOptLevel() != CodeGenOpt::None) 495 addMachineLateOptimization(); 496 497 // Expand pseudo instructions before second scheduling pass. 498 addPass(&ExpandPostRAPseudosID); 499 printAndVerify("After ExpandPostRAPseudos"); 500 501 // Run pre-sched2 passes. 502 if (addPreSched2()) 503 printAndVerify("After PreSched2 passes"); 504 505 // Second pass scheduler. 506 if (getOptLevel() != CodeGenOpt::None) { 507 addPass(&PostRASchedulerID); 508 printAndVerify("After PostRAScheduler"); 509 } 510 511 // GC 512 if (addGCPasses()) { 513 if (PrintGCInfo) 514 addPass(createGCInfoPrinter(dbgs())); 515 } 516 517 // Basic block placement. 518 if (getOptLevel() != CodeGenOpt::None) 519 addBlockPlacement(); 520 521 if (addPreEmitPass()) 522 printAndVerify("After PreEmit passes"); 523} 524 525/// Add passes that optimize machine instructions in SSA form. 526void TargetPassConfig::addMachineSSAOptimization() { 527 // Pre-ra tail duplication. 528 if (addPass(&EarlyTailDuplicateID)) 529 printAndVerify("After Pre-RegAlloc TailDuplicate"); 530 531 // Optimize PHIs before DCE: removing dead PHI cycles may make more 532 // instructions dead. 533 addPass(&OptimizePHIsID); 534 535 // This pass merges large allocas. StackSlotColoring is a different pass 536 // which merges spill slots. 537 addPass(&StackColoringID); 538 539 // If the target requests it, assign local variables to stack slots relative 540 // to one another and simplify frame index references where possible. 541 addPass(&LocalStackSlotAllocationID); 542 543 // With optimization, dead code should already be eliminated. However 544 // there is one known exception: lowered code for arguments that are only 545 // used by tail calls, where the tail calls reuse the incoming stack 546 // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll). 547 addPass(&DeadMachineInstructionElimID); 548 printAndVerify("After codegen DCE pass"); 549 550 // Allow targets to insert passes that improve instruction level parallelism, 551 // like if-conversion. Such passes will typically need dominator trees and 552 // loop info, just like LICM and CSE below. 553 if (addILPOpts()) 554 printAndVerify("After ILP optimizations"); 555 556 addPass(&MachineLICMID); 557 addPass(&MachineCSEID); 558 addPass(&MachineSinkingID); 559 printAndVerify("After Machine LICM, CSE and Sinking passes"); 560 561 addPass(&PeepholeOptimizerID); 562 printAndVerify("After codegen peephole optimization pass"); 563} 564 565//===---------------------------------------------------------------------===// 566/// Register Allocation Pass Configuration 567//===---------------------------------------------------------------------===// 568 569bool TargetPassConfig::getOptimizeRegAlloc() const { 570 switch (OptimizeRegAlloc) { 571 case cl::BOU_UNSET: return getOptLevel() != CodeGenOpt::None; 572 case cl::BOU_TRUE: return true; 573 case cl::BOU_FALSE: return false; 574 } 575 llvm_unreachable("Invalid optimize-regalloc state"); 576} 577 578/// RegisterRegAlloc's global Registry tracks allocator registration. 579MachinePassRegistry RegisterRegAlloc::Registry; 580 581/// A dummy default pass factory indicates whether the register allocator is 582/// overridden on the command line. 583static FunctionPass *useDefaultRegisterAllocator() { return 0; } 584static RegisterRegAlloc 585defaultRegAlloc("default", 586 "pick register allocator based on -O option", 587 useDefaultRegisterAllocator); 588 589/// -regalloc=... command line option. 590static cl::opt<RegisterRegAlloc::FunctionPassCtor, false, 591 RegisterPassParser<RegisterRegAlloc> > 592RegAlloc("regalloc", 593 cl::init(&useDefaultRegisterAllocator), 594 cl::desc("Register allocator to use")); 595 596 597/// Instantiate the default register allocator pass for this target for either 598/// the optimized or unoptimized allocation path. This will be added to the pass 599/// manager by addFastRegAlloc in the unoptimized case or addOptimizedRegAlloc 600/// in the optimized case. 601/// 602/// A target that uses the standard regalloc pass order for fast or optimized 603/// allocation may still override this for per-target regalloc 604/// selection. But -regalloc=... always takes precedence. 605FunctionPass *TargetPassConfig::createTargetRegisterAllocator(bool Optimized) { 606 if (Optimized) 607 return createGreedyRegisterAllocator(); 608 else 609 return createFastRegisterAllocator(); 610} 611 612/// Find and instantiate the register allocation pass requested by this target 613/// at the current optimization level. Different register allocators are 614/// defined as separate passes because they may require different analysis. 615/// 616/// This helper ensures that the regalloc= option is always available, 617/// even for targets that override the default allocator. 618/// 619/// FIXME: When MachinePassRegistry register pass IDs instead of function ptrs, 620/// this can be folded into addPass. 621FunctionPass *TargetPassConfig::createRegAllocPass(bool Optimized) { 622 RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault(); 623 624 // Initialize the global default. 625 if (!Ctor) { 626 Ctor = RegAlloc; 627 RegisterRegAlloc::setDefault(RegAlloc); 628 } 629 if (Ctor != useDefaultRegisterAllocator) 630 return Ctor(); 631 632 // With no -regalloc= override, ask the target for a regalloc pass. 633 return createTargetRegisterAllocator(Optimized); 634} 635 636/// Add the minimum set of target-independent passes that are required for 637/// register allocation. No coalescing or scheduling. 638void TargetPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) { 639 addPass(&PHIEliminationID); 640 addPass(&TwoAddressInstructionPassID); 641 642 addPass(RegAllocPass); 643 printAndVerify("After Register Allocation"); 644} 645 646/// Add standard target-independent passes that are tightly coupled with 647/// optimized register allocation, including coalescing, machine instruction 648/// scheduling, and register allocation itself. 649void TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) { 650 addPass(&ProcessImplicitDefsID); 651 652 // LiveVariables currently requires pure SSA form. 653 // 654 // FIXME: Once TwoAddressInstruction pass no longer uses kill flags, 655 // LiveVariables can be removed completely, and LiveIntervals can be directly 656 // computed. (We still either need to regenerate kill flags after regalloc, or 657 // preferably fix the scavenger to not depend on them). 658 addPass(&LiveVariablesID); 659 660 // Add passes that move from transformed SSA into conventional SSA. This is a 661 // "copy coalescing" problem. 662 // 663 if (!EnableStrongPHIElim) { 664 // Edge splitting is smarter with machine loop info. 665 addPass(&MachineLoopInfoID); 666 addPass(&PHIEliminationID); 667 } 668 669 // Eventually, we want to run LiveIntervals before PHI elimination. 670 if (EarlyLiveIntervals) 671 addPass(&LiveIntervalsID); 672 673 addPass(&TwoAddressInstructionPassID); 674 675 if (EnableStrongPHIElim) 676 addPass(&StrongPHIEliminationID); 677 678 addPass(&RegisterCoalescerID); 679 680 // PreRA instruction scheduling. 681 if (addPass(&MachineSchedulerID)) 682 printAndVerify("After Machine Scheduling"); 683 684 // Add the selected register allocation pass. 685 addPass(RegAllocPass); 686 printAndVerify("After Register Allocation, before rewriter"); 687 688 // Allow targets to change the register assignments before rewriting. 689 if (addPreRewrite()) 690 printAndVerify("After pre-rewrite passes"); 691 692 // Finally rewrite virtual registers. 693 addPass(&VirtRegRewriterID); 694 printAndVerify("After Virtual Register Rewriter"); 695 696 // FinalizeRegAlloc is convenient until MachineInstrBundles is more mature, 697 // but eventually, all users of it should probably be moved to addPostRA and 698 // it can go away. Currently, it's the intended place for targets to run 699 // FinalizeMachineBundles, because passes other than MachineScheduling an 700 // RegAlloc itself may not be aware of bundles. 701 if (addFinalizeRegAlloc()) 702 printAndVerify("After RegAlloc finalization"); 703 704 // Perform stack slot coloring and post-ra machine LICM. 705 // 706 // FIXME: Re-enable coloring with register when it's capable of adding 707 // kill markers. 708 addPass(&StackSlotColoringID); 709 710 // Run post-ra machine LICM to hoist reloads / remats. 711 // 712 // FIXME: can this move into MachineLateOptimization? 713 addPass(&PostRAMachineLICMID); 714 715 printAndVerify("After StackSlotColoring and postra Machine LICM"); 716} 717 718//===---------------------------------------------------------------------===// 719/// Post RegAlloc Pass Configuration 720//===---------------------------------------------------------------------===// 721 722/// Add passes that optimize machine instructions after register allocation. 723void TargetPassConfig::addMachineLateOptimization() { 724 // Branch folding must be run after regalloc and prolog/epilog insertion. 725 if (addPass(&BranchFolderPassID)) 726 printAndVerify("After BranchFolding"); 727 728 // Tail duplication. 729 if (addPass(&TailDuplicateID)) 730 printAndVerify("After TailDuplicate"); 731 732 // Copy propagation. 733 if (addPass(&MachineCopyPropagationID)) 734 printAndVerify("After copy propagation pass"); 735} 736 737/// Add standard GC passes. 738bool TargetPassConfig::addGCPasses() { 739 addPass(&GCMachineCodeAnalysisID); 740 return true; 741} 742 743/// Add standard basic block placement passes. 744void TargetPassConfig::addBlockPlacement() { 745 AnalysisID PassID = 0; 746 if (!DisableBlockPlacement) { 747 // MachineBlockPlacement is a new pass which subsumes the functionality of 748 // CodPlacementOpt. The old code placement pass can be restored by 749 // disabling block placement, but eventually it will be removed. 750 PassID = addPass(&MachineBlockPlacementID); 751 } else { 752 PassID = addPass(&CodePlacementOptID); 753 } 754 if (PassID) { 755 // Run a separate pass to collect block placement statistics. 756 if (EnableBlockPlacementStats) 757 addPass(&MachineBlockPlacementStatsID); 758 759 printAndVerify("After machine block placement."); 760 } 761} 762