1193323Sed//===-- Passes.cpp - Target independent code generation passes ------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines interfaces to access the target independent code 11193323Sed// generation passes provided by the LLVM backend. 12193323Sed// 13193323Sed//===---------------------------------------------------------------------===// 14193323Sed 15249423Sdim#include "llvm/CodeGen/Passes.h" 16234353Sdim#include "llvm/Analysis/Passes.h" 17234353Sdim#include "llvm/Analysis/Verifier.h" 18249423Sdim#include "llvm/Assembly/PrintModulePass.h" 19234353Sdim#include "llvm/CodeGen/GCStrategy.h" 20234353Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 21193323Sed#include "llvm/CodeGen/RegAllocRegistry.h" 22239462Sdim#include "llvm/MC/MCAsmInfo.h" 23249423Sdim#include "llvm/PassManager.h" 24234353Sdim#include "llvm/Support/CommandLine.h" 25234353Sdim#include "llvm/Support/Debug.h" 26234353Sdim#include "llvm/Support/ErrorHandling.h" 27249423Sdim#include "llvm/Target/TargetLowering.h" 28249423Sdim#include "llvm/Target/TargetSubtargetInfo.h" 29249423Sdim#include "llvm/Transforms/Scalar.h" 30193323Sed 31193323Sedusing namespace llvm; 32193323Sed 33234353Sdimstatic cl::opt<bool> DisablePostRA("disable-post-ra", cl::Hidden, 34234353Sdim cl::desc("Disable Post Regalloc")); 35234353Sdimstatic cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden, 36234353Sdim cl::desc("Disable branch folding")); 37234353Sdimstatic cl::opt<bool> DisableTailDuplicate("disable-tail-duplicate", cl::Hidden, 38234353Sdim cl::desc("Disable tail duplication")); 39234353Sdimstatic cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden, 40234353Sdim cl::desc("Disable pre-register allocation tail duplication")); 41234982Sdimstatic cl::opt<bool> DisableBlockPlacement("disable-block-placement", 42249423Sdim cl::Hidden, cl::desc("Disable probability-driven block placement")); 43234353Sdimstatic cl::opt<bool> EnableBlockPlacementStats("enable-block-placement-stats", 44234353Sdim cl::Hidden, cl::desc("Collect probability-driven block placement stats")); 45234353Sdimstatic cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden, 46234353Sdim cl::desc("Disable Stack Slot Coloring")); 47234353Sdimstatic cl::opt<bool> DisableMachineDCE("disable-machine-dce", cl::Hidden, 48234353Sdim cl::desc("Disable Machine Dead Code Elimination")); 49243830Sdimstatic cl::opt<bool> DisableEarlyIfConversion("disable-early-ifcvt", cl::Hidden, 50243830Sdim cl::desc("Disable Early If-conversion")); 51234353Sdimstatic cl::opt<bool> DisableMachineLICM("disable-machine-licm", cl::Hidden, 52234353Sdim cl::desc("Disable Machine LICM")); 53234353Sdimstatic cl::opt<bool> DisableMachineCSE("disable-machine-cse", cl::Hidden, 54234353Sdim cl::desc("Disable Machine Common Subexpression Elimination")); 55234353Sdimstatic cl::opt<cl::boolOrDefault> 56234353SdimOptimizeRegAlloc("optimize-regalloc", cl::Hidden, 57234353Sdim cl::desc("Enable optimized register allocation compilation path.")); 58234353Sdimstatic cl::opt<cl::boolOrDefault> 59234353SdimEnableMachineSched("enable-misched", cl::Hidden, 60234353Sdim cl::desc("Enable the machine instruction scheduling pass.")); 61234353Sdimstatic cl::opt<bool> EnableStrongPHIElim("strong-phi-elim", cl::Hidden, 62234353Sdim cl::desc("Use strong PHI elimination.")); 63234353Sdimstatic cl::opt<bool> DisablePostRAMachineLICM("disable-postra-machine-licm", 64234353Sdim cl::Hidden, 65234353Sdim cl::desc("Disable Machine LICM")); 66234353Sdimstatic cl::opt<bool> DisableMachineSink("disable-machine-sink", cl::Hidden, 67234353Sdim cl::desc("Disable Machine Sinking")); 68234353Sdimstatic cl::opt<bool> DisableLSR("disable-lsr", cl::Hidden, 69234353Sdim cl::desc("Disable Loop Strength Reduction Pass")); 70234353Sdimstatic cl::opt<bool> DisableCGP("disable-cgp", cl::Hidden, 71234353Sdim cl::desc("Disable Codegen Prepare")); 72234353Sdimstatic cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden, 73234353Sdim cl::desc("Disable Copy Propagation pass")); 74234353Sdimstatic cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden, 75234353Sdim cl::desc("Print LLVM IR produced by the loop-reduce pass")); 76234353Sdimstatic cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden, 77234353Sdim cl::desc("Print LLVM IR input to isel pass")); 78234353Sdimstatic cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden, 79234353Sdim cl::desc("Dump garbage collector data")); 80234353Sdimstatic cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden, 81234353Sdim cl::desc("Verify generated machine code"), 82234353Sdim cl::init(getenv("LLVM_VERIFY_MACHINEINSTRS")!=NULL)); 83239462Sdimstatic cl::opt<std::string> 84239462SdimPrintMachineInstrs("print-machineinstrs", cl::ValueOptional, 85239462Sdim cl::desc("Print machine instrs"), 86239462Sdim cl::value_desc("pass-name"), cl::init("option-unspecified")); 87234353Sdim 88249423Sdim// Experimental option to run live interval analysis early. 89239462Sdimstatic cl::opt<bool> EarlyLiveIntervals("early-live-intervals", cl::Hidden, 90239462Sdim cl::desc("Run live interval analysis earlier in the pipeline")); 91239462Sdim 92234353Sdim/// Allow standard passes to be disabled by command line options. This supports 93234353Sdim/// simple binary flags that either suppress the pass or do nothing. 94234353Sdim/// i.e. -disable-mypass=false has no effect. 95234353Sdim/// These should be converted to boolOrDefault in order to use applyOverride. 96251662Sdimstatic IdentifyingPassPtr applyDisable(IdentifyingPassPtr PassID, 97251662Sdim bool Override) { 98234353Sdim if (Override) 99251662Sdim return IdentifyingPassPtr(); 100239462Sdim return PassID; 101234353Sdim} 102234353Sdim 103234353Sdim/// Allow Pass selection to be overriden by command line options. This supports 104234353Sdim/// flags with ternary conditions. TargetID is passed through by default. The 105234353Sdim/// pass is suppressed when the option is false. When the option is true, the 106234353Sdim/// StandardID is selected if the target provides no default. 107251662Sdimstatic IdentifyingPassPtr applyOverride(IdentifyingPassPtr TargetID, 108251662Sdim cl::boolOrDefault Override, 109251662Sdim AnalysisID StandardID) { 110234353Sdim switch (Override) { 111234353Sdim case cl::BOU_UNSET: 112234353Sdim return TargetID; 113234353Sdim case cl::BOU_TRUE: 114251662Sdim if (TargetID.isValid()) 115234353Sdim return TargetID; 116239462Sdim if (StandardID == 0) 117234353Sdim report_fatal_error("Target cannot enable pass"); 118234353Sdim return StandardID; 119234353Sdim case cl::BOU_FALSE: 120251662Sdim return IdentifyingPassPtr(); 121234353Sdim } 122234353Sdim llvm_unreachable("Invalid command line option state"); 123234353Sdim} 124234353Sdim 125234353Sdim/// Allow standard passes to be disabled by the command line, regardless of who 126234353Sdim/// is adding the pass. 127234353Sdim/// 128234353Sdim/// StandardID is the pass identified in the standard pass pipeline and provided 129234353Sdim/// to addPass(). It may be a target-specific ID in the case that the target 130234353Sdim/// directly adds its own pass, but in that case we harmlessly fall through. 131234353Sdim/// 132234353Sdim/// TargetID is the pass that the target has configured to override StandardID. 133234353Sdim/// 134234353Sdim/// StandardID may be a pseudo ID. In that case TargetID is the name of the real 135234353Sdim/// pass to run. This allows multiple options to control a single pass depending 136234353Sdim/// on where in the pipeline that pass is added. 137251662Sdimstatic IdentifyingPassPtr overridePass(AnalysisID StandardID, 138251662Sdim IdentifyingPassPtr TargetID) { 139234353Sdim if (StandardID == &PostRASchedulerID) 140234353Sdim return applyDisable(TargetID, DisablePostRA); 141234353Sdim 142234353Sdim if (StandardID == &BranchFolderPassID) 143234353Sdim return applyDisable(TargetID, DisableBranchFold); 144234353Sdim 145234353Sdim if (StandardID == &TailDuplicateID) 146234353Sdim return applyDisable(TargetID, DisableTailDuplicate); 147234353Sdim 148234353Sdim if (StandardID == &TargetPassConfig::EarlyTailDuplicateID) 149234353Sdim return applyDisable(TargetID, DisableEarlyTailDup); 150234353Sdim 151234353Sdim if (StandardID == &MachineBlockPlacementID) 152249423Sdim return applyDisable(TargetID, DisableBlockPlacement); 153234353Sdim 154234353Sdim if (StandardID == &StackSlotColoringID) 155234353Sdim return applyDisable(TargetID, DisableSSC); 156234353Sdim 157234353Sdim if (StandardID == &DeadMachineInstructionElimID) 158234353Sdim return applyDisable(TargetID, DisableMachineDCE); 159234353Sdim 160239462Sdim if (StandardID == &EarlyIfConverterID) 161243830Sdim return applyDisable(TargetID, DisableEarlyIfConversion); 162239462Sdim 163234353Sdim if (StandardID == &MachineLICMID) 164234353Sdim return applyDisable(TargetID, DisableMachineLICM); 165234353Sdim 166234353Sdim if (StandardID == &MachineCSEID) 167234353Sdim return applyDisable(TargetID, DisableMachineCSE); 168234353Sdim 169234353Sdim if (StandardID == &MachineSchedulerID) 170234353Sdim return applyOverride(TargetID, EnableMachineSched, StandardID); 171234353Sdim 172234353Sdim if (StandardID == &TargetPassConfig::PostRAMachineLICMID) 173234353Sdim return applyDisable(TargetID, DisablePostRAMachineLICM); 174234353Sdim 175234353Sdim if (StandardID == &MachineSinkingID) 176234353Sdim return applyDisable(TargetID, DisableMachineSink); 177234353Sdim 178234353Sdim if (StandardID == &MachineCopyPropagationID) 179234353Sdim return applyDisable(TargetID, DisableCopyProp); 180234353Sdim 181234353Sdim return TargetID; 182234353Sdim} 183234353Sdim 184193323Sed//===---------------------------------------------------------------------===// 185234353Sdim/// TargetPassConfig 186234353Sdim//===---------------------------------------------------------------------===// 187234353Sdim 188234353SdimINITIALIZE_PASS(TargetPassConfig, "targetpassconfig", 189234353Sdim "Target Pass Configuration", false, false) 190234353Sdimchar TargetPassConfig::ID = 0; 191234353Sdim 192234353Sdim// Pseudo Pass IDs. 193234353Sdimchar TargetPassConfig::EarlyTailDuplicateID = 0; 194234353Sdimchar TargetPassConfig::PostRAMachineLICMID = 0; 195234353Sdim 196234353Sdimnamespace llvm { 197234353Sdimclass PassConfigImpl { 198234353Sdimpublic: 199234353Sdim // List of passes explicitly substituted by this target. Normally this is 200234353Sdim // empty, but it is a convenient way to suppress or replace specific passes 201234353Sdim // that are part of a standard pass pipeline without overridding the entire 202234353Sdim // pipeline. This mechanism allows target options to inherit a standard pass's 203234353Sdim // user interface. For example, a target may disable a standard pass by 204239462Sdim // default by substituting a pass ID of zero, and the user may still enable 205239462Sdim // that standard pass with an explicit command line option. 206251662Sdim DenseMap<AnalysisID,IdentifyingPassPtr> TargetPasses; 207239462Sdim 208239462Sdim /// Store the pairs of <AnalysisID, AnalysisID> of which the second pass 209239462Sdim /// is inserted after each instance of the first one. 210251662Sdim SmallVector<std::pair<AnalysisID, IdentifyingPassPtr>, 4> InsertedPasses; 211234353Sdim}; 212234353Sdim} // namespace llvm 213234353Sdim 214234353Sdim// Out of line virtual method. 215234353SdimTargetPassConfig::~TargetPassConfig() { 216234353Sdim delete Impl; 217234353Sdim} 218234353Sdim 219234353Sdim// Out of line constructor provides default values for pass options and 220234353Sdim// registers all common codegen passes. 221234353SdimTargetPassConfig::TargetPassConfig(TargetMachine *tm, PassManagerBase &pm) 222239462Sdim : ImmutablePass(ID), PM(&pm), StartAfter(0), StopAfter(0), 223239462Sdim Started(true), Stopped(false), TM(tm), Impl(0), Initialized(false), 224234353Sdim DisableVerify(false), 225234353Sdim EnableTailMerge(true) { 226234353Sdim 227234353Sdim Impl = new PassConfigImpl(); 228234353Sdim 229234353Sdim // Register all target independent codegen passes to activate their PassIDs, 230234353Sdim // including this pass itself. 231234353Sdim initializeCodeGen(*PassRegistry::getPassRegistry()); 232234353Sdim 233234353Sdim // Substitute Pseudo Pass IDs for real ones. 234239462Sdim substitutePass(&EarlyTailDuplicateID, &TailDuplicateID); 235239462Sdim substitutePass(&PostRAMachineLICMID, &MachineLICMID); 236234353Sdim 237234353Sdim // Temporarily disable experimental passes. 238249423Sdim const TargetSubtargetInfo &ST = TM->getSubtarget<TargetSubtargetInfo>(); 239249423Sdim if (!ST.enableMachineScheduler()) 240249423Sdim disablePass(&MachineSchedulerID); 241234353Sdim} 242234353Sdim 243239462Sdim/// Insert InsertedPassID pass after TargetPassID. 244239462Sdimvoid TargetPassConfig::insertPass(AnalysisID TargetPassID, 245251662Sdim IdentifyingPassPtr InsertedPassID) { 246251662Sdim assert(((!InsertedPassID.isInstance() && 247251662Sdim TargetPassID != InsertedPassID.getID()) || 248251662Sdim (InsertedPassID.isInstance() && 249251662Sdim TargetPassID != InsertedPassID.getInstance()->getPassID())) && 250251662Sdim "Insert a pass after itself!"); 251251662Sdim std::pair<AnalysisID, IdentifyingPassPtr> P(TargetPassID, InsertedPassID); 252239462Sdim Impl->InsertedPasses.push_back(P); 253239462Sdim} 254239462Sdim 255234353Sdim/// createPassConfig - Create a pass configuration object to be used by 256234353Sdim/// addPassToEmitX methods for generating a pipeline of CodeGen passes. 257193323Sed/// 258234353Sdim/// Targets may override this to extend TargetPassConfig. 259234353SdimTargetPassConfig *LLVMTargetMachine::createPassConfig(PassManagerBase &PM) { 260234353Sdim return new TargetPassConfig(this, PM); 261234353Sdim} 262234353Sdim 263234353SdimTargetPassConfig::TargetPassConfig() 264234982Sdim : ImmutablePass(ID), PM(0) { 265234353Sdim llvm_unreachable("TargetPassConfig should not be constructed on-the-fly"); 266234353Sdim} 267234353Sdim 268234353Sdim// Helper to verify the analysis is really immutable. 269234353Sdimvoid TargetPassConfig::setOpt(bool &Opt, bool Val) { 270234353Sdim assert(!Initialized && "PassConfig is immutable"); 271234353Sdim Opt = Val; 272234353Sdim} 273234353Sdim 274239462Sdimvoid TargetPassConfig::substitutePass(AnalysisID StandardID, 275251662Sdim IdentifyingPassPtr TargetID) { 276239462Sdim Impl->TargetPasses[StandardID] = TargetID; 277234353Sdim} 278234353Sdim 279251662SdimIdentifyingPassPtr TargetPassConfig::getPassSubstitution(AnalysisID ID) const { 280251662Sdim DenseMap<AnalysisID, IdentifyingPassPtr>::const_iterator 281234353Sdim I = Impl->TargetPasses.find(ID); 282234353Sdim if (I == Impl->TargetPasses.end()) 283234353Sdim return ID; 284234353Sdim return I->second; 285234353Sdim} 286234353Sdim 287239462Sdim/// Add a pass to the PassManager if that pass is supposed to be run. If the 288239462Sdim/// Started/Stopped flags indicate either that the compilation should start at 289239462Sdim/// a later pass or that it should stop after an earlier pass, then do not add 290239462Sdim/// the pass. Finally, compare the current pass against the StartAfter 291239462Sdim/// and StopAfter options and change the Started/Stopped flags accordingly. 292239462Sdimvoid TargetPassConfig::addPass(Pass *P) { 293239462Sdim assert(!Initialized && "PassConfig is immutable"); 294239462Sdim 295239462Sdim // Cache the Pass ID here in case the pass manager finds this pass is 296239462Sdim // redundant with ones already scheduled / available, and deletes it. 297239462Sdim // Fundamentally, once we add the pass to the manager, we no longer own it 298239462Sdim // and shouldn't reference it. 299239462Sdim AnalysisID PassID = P->getPassID(); 300239462Sdim 301239462Sdim if (Started && !Stopped) 302239462Sdim PM->add(P); 303239462Sdim if (StopAfter == PassID) 304239462Sdim Stopped = true; 305239462Sdim if (StartAfter == PassID) 306239462Sdim Started = true; 307239462Sdim if (Stopped && !Started) 308239462Sdim report_fatal_error("Cannot stop compilation after pass that is not run"); 309239462Sdim} 310239462Sdim 311234353Sdim/// Add a CodeGen pass at this point in the pipeline after checking for target 312234353Sdim/// and command line overrides. 313251662Sdim/// 314251662Sdim/// addPass cannot return a pointer to the pass instance because is internal the 315251662Sdim/// PassManager and the instance we create here may already be freed. 316239462SdimAnalysisID TargetPassConfig::addPass(AnalysisID PassID) { 317251662Sdim IdentifyingPassPtr TargetID = getPassSubstitution(PassID); 318251662Sdim IdentifyingPassPtr FinalPtr = overridePass(PassID, TargetID); 319251662Sdim if (!FinalPtr.isValid()) 320251662Sdim return 0; 321234353Sdim 322251662Sdim Pass *P; 323251662Sdim if (FinalPtr.isInstance()) 324251662Sdim P = FinalPtr.getInstance(); 325251662Sdim else { 326251662Sdim P = Pass::createPass(FinalPtr.getID()); 327251662Sdim if (!P) 328251662Sdim llvm_unreachable("Pass ID not registered"); 329251662Sdim } 330251662Sdim AnalysisID FinalID = P->getPassID(); 331251662Sdim addPass(P); // Ends the lifetime of P. 332251662Sdim 333239462Sdim // Add the passes after the pass P if there is any. 334251662Sdim for (SmallVector<std::pair<AnalysisID, IdentifyingPassPtr>, 4>::iterator 335239462Sdim I = Impl->InsertedPasses.begin(), E = Impl->InsertedPasses.end(); 336239462Sdim I != E; ++I) { 337239462Sdim if ((*I).first == PassID) { 338251662Sdim assert((*I).second.isValid() && "Illegal Pass ID!"); 339251662Sdim Pass *NP; 340251662Sdim if ((*I).second.isInstance()) 341251662Sdim NP = (*I).second.getInstance(); 342251662Sdim else { 343251662Sdim NP = Pass::createPass((*I).second.getID()); 344251662Sdim assert(NP && "Pass ID not registered"); 345251662Sdim } 346239462Sdim addPass(NP); 347239462Sdim } 348239462Sdim } 349234353Sdim return FinalID; 350234353Sdim} 351234353Sdim 352239462Sdimvoid TargetPassConfig::printAndVerify(const char *Banner) { 353234353Sdim if (TM->shouldPrintMachineCode()) 354239462Sdim addPass(createMachineFunctionPrinterPass(dbgs(), Banner)); 355234353Sdim 356234353Sdim if (VerifyMachineCode) 357239462Sdim addPass(createMachineVerifierPass(Banner)); 358234353Sdim} 359234353Sdim 360234353Sdim/// Add common target configurable passes that perform LLVM IR to IR transforms 361234353Sdim/// following machine independent optimization. 362234353Sdimvoid TargetPassConfig::addIRPasses() { 363234353Sdim // Basic AliasAnalysis support. 364234353Sdim // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that 365234353Sdim // BasicAliasAnalysis wins if they disagree. This is intended to help 366234353Sdim // support "obvious" type-punning idioms. 367239462Sdim addPass(createTypeBasedAliasAnalysisPass()); 368239462Sdim addPass(createBasicAliasAnalysisPass()); 369234353Sdim 370234353Sdim // Before running any passes, run the verifier to determine if the input 371234353Sdim // coming from the front-end and/or optimizer is valid. 372234353Sdim if (!DisableVerify) 373239462Sdim addPass(createVerifierPass()); 374234353Sdim 375234353Sdim // Run loop strength reduction before anything else. 376234353Sdim if (getOptLevel() != CodeGenOpt::None && !DisableLSR) { 377249423Sdim addPass(createLoopStrengthReducePass()); 378234353Sdim if (PrintLSR) 379239462Sdim addPass(createPrintFunctionPass("\n\n*** Code after LSR ***\n", &dbgs())); 380234353Sdim } 381234353Sdim 382239462Sdim addPass(createGCLoweringPass()); 383234353Sdim 384234353Sdim // Make sure that no unreachable blocks are instruction selected. 385239462Sdim addPass(createUnreachableBlockEliminationPass()); 386234353Sdim} 387234353Sdim 388239462Sdim/// Turn exception handling constructs into something the code generators can 389239462Sdim/// handle. 390239462Sdimvoid TargetPassConfig::addPassesToHandleExceptions() { 391239462Sdim switch (TM->getMCAsmInfo()->getExceptionHandlingType()) { 392239462Sdim case ExceptionHandling::SjLj: 393239462Sdim // SjLj piggy-backs on dwarf for this bit. The cleanups done apply to both 394239462Sdim // Dwarf EH prepare needs to be run after SjLj prepare. Otherwise, 395239462Sdim // catch info can get misplaced when a selector ends up more than one block 396239462Sdim // removed from the parent invoke(s). This could happen when a landing 397239462Sdim // pad is shared by multiple invokes and is also a target of a normal 398239462Sdim // edge from elsewhere. 399239462Sdim addPass(createSjLjEHPreparePass(TM->getTargetLowering())); 400239462Sdim // FALLTHROUGH 401239462Sdim case ExceptionHandling::DwarfCFI: 402239462Sdim case ExceptionHandling::ARM: 403239462Sdim case ExceptionHandling::Win64: 404239462Sdim addPass(createDwarfEHPass(TM)); 405239462Sdim break; 406239462Sdim case ExceptionHandling::None: 407239462Sdim addPass(createLowerInvokePass(TM->getTargetLowering())); 408239462Sdim 409239462Sdim // The lower invoke pass may create unreachable code. Remove it. 410239462Sdim addPass(createUnreachableBlockEliminationPass()); 411239462Sdim break; 412239462Sdim } 413239462Sdim} 414239462Sdim 415249423Sdim/// Add pass to prepare the LLVM IR for code generation. This should be done 416249423Sdim/// before exception handling preparation passes. 417249423Sdimvoid TargetPassConfig::addCodeGenPrepare() { 418249423Sdim if (getOptLevel() != CodeGenOpt::None && !DisableCGP) 419249423Sdim addPass(createCodeGenPreparePass(getTargetLowering())); 420249423Sdim} 421249423Sdim 422234353Sdim/// Add common passes that perform LLVM IR to IR transforms in preparation for 423234353Sdim/// instruction selection. 424234353Sdimvoid TargetPassConfig::addISelPrepare() { 425239462Sdim addPass(createStackProtectorPass(getTargetLowering())); 426234353Sdim 427234353Sdim addPreISel(); 428234353Sdim 429234353Sdim if (PrintISelInput) 430239462Sdim addPass(createPrintFunctionPass("\n\n" 431234982Sdim "*** Final LLVM Code input to ISel ***\n", 432234982Sdim &dbgs())); 433234353Sdim 434234353Sdim // All passes which modify the LLVM IR are now complete; run the verifier 435234353Sdim // to ensure that the IR is valid. 436234353Sdim if (!DisableVerify) 437239462Sdim addPass(createVerifierPass()); 438234353Sdim} 439234353Sdim 440234353Sdim/// Add the complete set of target-independent postISel code generator passes. 441193323Sed/// 442234353Sdim/// This can be read as the standard order of major LLVM CodeGen stages. Stages 443234353Sdim/// with nontrivial configuration or multiple passes are broken out below in 444234353Sdim/// add%Stage routines. 445234353Sdim/// 446234353Sdim/// Any TargetPassConfig::addXX routine may be overriden by the Target. The 447234353Sdim/// addPre/Post methods with empty header implementations allow injecting 448234353Sdim/// target-specific fixups just before or after major stages. Additionally, 449234353Sdim/// targets have the flexibility to change pass order within a stage by 450234353Sdim/// overriding default implementation of add%Stage routines below. Each 451234353Sdim/// technique has maintainability tradeoffs because alternate pass orders are 452234353Sdim/// not well supported. addPre/Post works better if the target pass is easily 453234353Sdim/// tied to a common pass. But if it has subtle dependencies on multiple passes, 454234353Sdim/// the target should override the stage instead. 455234353Sdim/// 456234353Sdim/// TODO: We could use a single addPre/Post(ID) hook to allow pass injection 457234353Sdim/// before/after any target-independent pass. But it's currently overkill. 458234353Sdimvoid TargetPassConfig::addMachinePasses() { 459239462Sdim // Insert a machine instr printer pass after the specified pass. 460239462Sdim // If -print-machineinstrs specified, print machineinstrs after all passes. 461239462Sdim if (StringRef(PrintMachineInstrs.getValue()).equals("")) 462239462Sdim TM->Options.PrintMachineCode = true; 463239462Sdim else if (!StringRef(PrintMachineInstrs.getValue()) 464239462Sdim .equals("option-unspecified")) { 465239462Sdim const PassRegistry *PR = PassRegistry::getPassRegistry(); 466239462Sdim const PassInfo *TPI = PR->getPassInfo(PrintMachineInstrs.getValue()); 467239462Sdim const PassInfo *IPI = PR->getPassInfo(StringRef("print-machineinstrs")); 468239462Sdim assert (TPI && IPI && "Pass ID not registered!"); 469243830Sdim const char *TID = (const char *)(TPI->getTypeInfo()); 470243830Sdim const char *IID = (const char *)(IPI->getTypeInfo()); 471239462Sdim insertPass(TID, IID); 472239462Sdim } 473239462Sdim 474234353Sdim // Print the instruction selected machine code... 475234353Sdim printAndVerify("After Instruction Selection"); 476234353Sdim 477234353Sdim // Expand pseudo-instructions emitted by ISel. 478243830Sdim if (addPass(&ExpandISelPseudosID)) 479243830Sdim printAndVerify("After ExpandISelPseudos"); 480234353Sdim 481234353Sdim // Add passes that optimize machine instructions in SSA form. 482234353Sdim if (getOptLevel() != CodeGenOpt::None) { 483234353Sdim addMachineSSAOptimization(); 484249423Sdim } else { 485234353Sdim // If the target requests it, assign local variables to stack slots relative 486234353Sdim // to one another and simplify frame index references where possible. 487239462Sdim addPass(&LocalStackSlotAllocationID); 488234353Sdim } 489234353Sdim 490234353Sdim // Run pre-ra passes. 491234353Sdim if (addPreRegAlloc()) 492234353Sdim printAndVerify("After PreRegAlloc passes"); 493234353Sdim 494234353Sdim // Run register allocation and passes that are tightly coupled with it, 495234353Sdim // including phi elimination and scheduling. 496234353Sdim if (getOptimizeRegAlloc()) 497234353Sdim addOptimizedRegAlloc(createRegAllocPass(true)); 498234353Sdim else 499234353Sdim addFastRegAlloc(createRegAllocPass(false)); 500234353Sdim 501234353Sdim // Run post-ra passes. 502234353Sdim if (addPostRegAlloc()) 503234353Sdim printAndVerify("After PostRegAlloc passes"); 504234353Sdim 505234353Sdim // Insert prolog/epilog code. Eliminate abstract frame index references... 506239462Sdim addPass(&PrologEpilogCodeInserterID); 507234353Sdim printAndVerify("After PrologEpilogCodeInserter"); 508234353Sdim 509234353Sdim /// Add passes that optimize machine instructions after register allocation. 510234353Sdim if (getOptLevel() != CodeGenOpt::None) 511234353Sdim addMachineLateOptimization(); 512234353Sdim 513234353Sdim // Expand pseudo instructions before second scheduling pass. 514239462Sdim addPass(&ExpandPostRAPseudosID); 515234353Sdim printAndVerify("After ExpandPostRAPseudos"); 516234353Sdim 517234353Sdim // Run pre-sched2 passes. 518234353Sdim if (addPreSched2()) 519234353Sdim printAndVerify("After PreSched2 passes"); 520234353Sdim 521234353Sdim // Second pass scheduler. 522234353Sdim if (getOptLevel() != CodeGenOpt::None) { 523239462Sdim addPass(&PostRASchedulerID); 524234353Sdim printAndVerify("After PostRAScheduler"); 525234353Sdim } 526234353Sdim 527234353Sdim // GC 528249423Sdim if (addGCPasses()) { 529249423Sdim if (PrintGCInfo) 530249423Sdim addPass(createGCInfoPrinter(dbgs())); 531249423Sdim } 532234353Sdim 533234353Sdim // Basic block placement. 534234353Sdim if (getOptLevel() != CodeGenOpt::None) 535234353Sdim addBlockPlacement(); 536234353Sdim 537234353Sdim if (addPreEmitPass()) 538234353Sdim printAndVerify("After PreEmit passes"); 539234353Sdim} 540234353Sdim 541234353Sdim/// Add passes that optimize machine instructions in SSA form. 542234353Sdimvoid TargetPassConfig::addMachineSSAOptimization() { 543234353Sdim // Pre-ra tail duplication. 544239462Sdim if (addPass(&EarlyTailDuplicateID)) 545234353Sdim printAndVerify("After Pre-RegAlloc TailDuplicate"); 546234353Sdim 547234353Sdim // Optimize PHIs before DCE: removing dead PHI cycles may make more 548234353Sdim // instructions dead. 549239462Sdim addPass(&OptimizePHIsID); 550234353Sdim 551243830Sdim // This pass merges large allocas. StackSlotColoring is a different pass 552243830Sdim // which merges spill slots. 553243830Sdim addPass(&StackColoringID); 554243830Sdim 555234353Sdim // If the target requests it, assign local variables to stack slots relative 556234353Sdim // to one another and simplify frame index references where possible. 557239462Sdim addPass(&LocalStackSlotAllocationID); 558234353Sdim 559234353Sdim // With optimization, dead code should already be eliminated. However 560234353Sdim // there is one known exception: lowered code for arguments that are only 561234353Sdim // used by tail calls, where the tail calls reuse the incoming stack 562234353Sdim // arguments directly (see t11 in test/CodeGen/X86/sibcall.ll). 563239462Sdim addPass(&DeadMachineInstructionElimID); 564234353Sdim printAndVerify("After codegen DCE pass"); 565234353Sdim 566249423Sdim // Allow targets to insert passes that improve instruction level parallelism, 567249423Sdim // like if-conversion. Such passes will typically need dominator trees and 568249423Sdim // loop info, just like LICM and CSE below. 569249423Sdim if (addILPOpts()) 570249423Sdim printAndVerify("After ILP optimizations"); 571249423Sdim 572239462Sdim addPass(&MachineLICMID); 573239462Sdim addPass(&MachineCSEID); 574239462Sdim addPass(&MachineSinkingID); 575234353Sdim printAndVerify("After Machine LICM, CSE and Sinking passes"); 576234353Sdim 577239462Sdim addPass(&PeepholeOptimizerID); 578234353Sdim printAndVerify("After codegen peephole optimization pass"); 579234353Sdim} 580234353Sdim 581193323Sed//===---------------------------------------------------------------------===// 582234353Sdim/// Register Allocation Pass Configuration 583234353Sdim//===---------------------------------------------------------------------===// 584234353Sdim 585234353Sdimbool TargetPassConfig::getOptimizeRegAlloc() const { 586234353Sdim switch (OptimizeRegAlloc) { 587234353Sdim case cl::BOU_UNSET: return getOptLevel() != CodeGenOpt::None; 588234353Sdim case cl::BOU_TRUE: return true; 589234353Sdim case cl::BOU_FALSE: return false; 590234353Sdim } 591234353Sdim llvm_unreachable("Invalid optimize-regalloc state"); 592234353Sdim} 593234353Sdim 594234353Sdim/// RegisterRegAlloc's global Registry tracks allocator registration. 595193323SedMachinePassRegistry RegisterRegAlloc::Registry; 596193323Sed 597234353Sdim/// A dummy default pass factory indicates whether the register allocator is 598234353Sdim/// overridden on the command line. 599234353Sdimstatic FunctionPass *useDefaultRegisterAllocator() { return 0; } 600210299Sedstatic RegisterRegAlloc 601210299SeddefaultRegAlloc("default", 602210299Sed "pick register allocator based on -O option", 603234353Sdim useDefaultRegisterAllocator); 604193323Sed 605234353Sdim/// -regalloc=... command line option. 606193323Sedstatic cl::opt<RegisterRegAlloc::FunctionPassCtor, false, 607193323Sed RegisterPassParser<RegisterRegAlloc> > 608193323SedRegAlloc("regalloc", 609234353Sdim cl::init(&useDefaultRegisterAllocator), 610210299Sed cl::desc("Register allocator to use")); 611193323Sed 612193323Sed 613234353Sdim/// Instantiate the default register allocator pass for this target for either 614234353Sdim/// the optimized or unoptimized allocation path. This will be added to the pass 615234353Sdim/// manager by addFastRegAlloc in the unoptimized case or addOptimizedRegAlloc 616234353Sdim/// in the optimized case. 617193323Sed/// 618234353Sdim/// A target that uses the standard regalloc pass order for fast or optimized 619234353Sdim/// allocation may still override this for per-target regalloc 620234353Sdim/// selection. But -regalloc=... always takes precedence. 621234353SdimFunctionPass *TargetPassConfig::createTargetRegisterAllocator(bool Optimized) { 622234353Sdim if (Optimized) 623234353Sdim return createGreedyRegisterAllocator(); 624234353Sdim else 625234353Sdim return createFastRegisterAllocator(); 626234353Sdim} 627234353Sdim 628234353Sdim/// Find and instantiate the register allocation pass requested by this target 629234353Sdim/// at the current optimization level. Different register allocators are 630234353Sdim/// defined as separate passes because they may require different analysis. 631193323Sed/// 632234353Sdim/// This helper ensures that the regalloc= option is always available, 633234353Sdim/// even for targets that override the default allocator. 634234353Sdim/// 635234353Sdim/// FIXME: When MachinePassRegistry register pass IDs instead of function ptrs, 636234353Sdim/// this can be folded into addPass. 637234353SdimFunctionPass *TargetPassConfig::createRegAllocPass(bool Optimized) { 638193323Sed RegisterRegAlloc::FunctionPassCtor Ctor = RegisterRegAlloc::getDefault(); 639210299Sed 640234353Sdim // Initialize the global default. 641193323Sed if (!Ctor) { 642193323Sed Ctor = RegAlloc; 643193323Sed RegisterRegAlloc::setDefault(RegAlloc); 644193323Sed } 645234353Sdim if (Ctor != useDefaultRegisterAllocator) 646234353Sdim return Ctor(); 647210299Sed 648234353Sdim // With no -regalloc= override, ask the target for a regalloc pass. 649234353Sdim return createTargetRegisterAllocator(Optimized); 650234353Sdim} 651221345Sdim 652234353Sdim/// Add the minimum set of target-independent passes that are required for 653234353Sdim/// register allocation. No coalescing or scheduling. 654234353Sdimvoid TargetPassConfig::addFastRegAlloc(FunctionPass *RegAllocPass) { 655239462Sdim addPass(&PHIEliminationID); 656239462Sdim addPass(&TwoAddressInstructionPassID); 657210299Sed 658239462Sdim addPass(RegAllocPass); 659234353Sdim printAndVerify("After Register Allocation"); 660234353Sdim} 661234353Sdim 662234353Sdim/// Add standard target-independent passes that are tightly coupled with 663234353Sdim/// optimized register allocation, including coalescing, machine instruction 664234353Sdim/// scheduling, and register allocation itself. 665234353Sdimvoid TargetPassConfig::addOptimizedRegAlloc(FunctionPass *RegAllocPass) { 666239462Sdim addPass(&ProcessImplicitDefsID); 667239462Sdim 668234353Sdim // LiveVariables currently requires pure SSA form. 669234353Sdim // 670234353Sdim // FIXME: Once TwoAddressInstruction pass no longer uses kill flags, 671234353Sdim // LiveVariables can be removed completely, and LiveIntervals can be directly 672234353Sdim // computed. (We still either need to regenerate kill flags after regalloc, or 673234353Sdim // preferably fix the scavenger to not depend on them). 674239462Sdim addPass(&LiveVariablesID); 675234353Sdim 676234353Sdim // Add passes that move from transformed SSA into conventional SSA. This is a 677234353Sdim // "copy coalescing" problem. 678234353Sdim // 679234353Sdim if (!EnableStrongPHIElim) { 680234353Sdim // Edge splitting is smarter with machine loop info. 681239462Sdim addPass(&MachineLoopInfoID); 682239462Sdim addPass(&PHIEliminationID); 683210299Sed } 684234353Sdim 685239462Sdim // Eventually, we want to run LiveIntervals before PHI elimination. 686239462Sdim if (EarlyLiveIntervals) 687239462Sdim addPass(&LiveIntervalsID); 688234353Sdim 689239462Sdim addPass(&TwoAddressInstructionPassID); 690239462Sdim 691234353Sdim if (EnableStrongPHIElim) 692239462Sdim addPass(&StrongPHIEliminationID); 693234353Sdim 694239462Sdim addPass(&RegisterCoalescerID); 695234353Sdim 696234353Sdim // PreRA instruction scheduling. 697239462Sdim if (addPass(&MachineSchedulerID)) 698234353Sdim printAndVerify("After Machine Scheduling"); 699234353Sdim 700234353Sdim // Add the selected register allocation pass. 701239462Sdim addPass(RegAllocPass); 702239462Sdim printAndVerify("After Register Allocation, before rewriter"); 703234353Sdim 704239462Sdim // Allow targets to change the register assignments before rewriting. 705239462Sdim if (addPreRewrite()) 706239462Sdim printAndVerify("After pre-rewrite passes"); 707239462Sdim 708239462Sdim // Finally rewrite virtual registers. 709239462Sdim addPass(&VirtRegRewriterID); 710239462Sdim printAndVerify("After Virtual Register Rewriter"); 711239462Sdim 712234353Sdim // Perform stack slot coloring and post-ra machine LICM. 713234353Sdim // 714234353Sdim // FIXME: Re-enable coloring with register when it's capable of adding 715234353Sdim // kill markers. 716239462Sdim addPass(&StackSlotColoringID); 717234353Sdim 718234353Sdim // Run post-ra machine LICM to hoist reloads / remats. 719234353Sdim // 720234353Sdim // FIXME: can this move into MachineLateOptimization? 721239462Sdim addPass(&PostRAMachineLICMID); 722234353Sdim 723234353Sdim printAndVerify("After StackSlotColoring and postra Machine LICM"); 724193323Sed} 725234353Sdim 726234353Sdim//===---------------------------------------------------------------------===// 727234353Sdim/// Post RegAlloc Pass Configuration 728234353Sdim//===---------------------------------------------------------------------===// 729234353Sdim 730234353Sdim/// Add passes that optimize machine instructions after register allocation. 731234353Sdimvoid TargetPassConfig::addMachineLateOptimization() { 732234353Sdim // Branch folding must be run after regalloc and prolog/epilog insertion. 733239462Sdim if (addPass(&BranchFolderPassID)) 734234353Sdim printAndVerify("After BranchFolding"); 735234353Sdim 736234353Sdim // Tail duplication. 737239462Sdim if (addPass(&TailDuplicateID)) 738234353Sdim printAndVerify("After TailDuplicate"); 739234353Sdim 740234353Sdim // Copy propagation. 741239462Sdim if (addPass(&MachineCopyPropagationID)) 742234353Sdim printAndVerify("After copy propagation pass"); 743234353Sdim} 744234353Sdim 745249423Sdim/// Add standard GC passes. 746249423Sdimbool TargetPassConfig::addGCPasses() { 747249423Sdim addPass(&GCMachineCodeAnalysisID); 748249423Sdim return true; 749249423Sdim} 750249423Sdim 751234353Sdim/// Add standard basic block placement passes. 752234353Sdimvoid TargetPassConfig::addBlockPlacement() { 753249423Sdim if (addPass(&MachineBlockPlacementID)) { 754234353Sdim // Run a separate pass to collect block placement statistics. 755234353Sdim if (EnableBlockPlacementStats) 756239462Sdim addPass(&MachineBlockPlacementStatsID); 757234353Sdim 758234353Sdim printAndVerify("After machine block placement."); 759234353Sdim } 760234353Sdim} 761