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