1 //===-- Passes.h - Target independent code generation passes ----*- C++ -*-===// 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 generation 11 // passes provided by the LLVM backend. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_CODEGEN_PASSES_H 16 #define LLVM_CODEGEN_PASSES_H 17 18 #include "llvm/Pass.h" 19 #include "llvm/Target/TargetMachine.h" 20 #include <string> 21 22 namespace llvm { 23 24 class FunctionPass; 25 class MachineFunctionPass; 26 class PassConfigImpl; 27 class PassInfo; 28 class ScheduleDAGInstrs; 29 class TargetLowering; 30 class TargetLoweringBase; 31 class TargetRegisterClass; 32 class raw_ostream; 33 struct MachineSchedContext; 34 35 // The old pass manager infrastructure is hidden in a legacy namespace now. 36 namespace legacy { 37 class PassManagerBase; 38 } 39 using legacy::PassManagerBase; 40 41 /// Discriminated union of Pass ID types. 42 /// 43 /// The PassConfig API prefers dealing with IDs because they are safer and more 44 /// efficient. IDs decouple configuration from instantiation. This way, when a 45 /// pass is overriden, it isn't unnecessarily instantiated. It is also unsafe to 46 /// refer to a Pass pointer after adding it to a pass manager, which deletes 47 /// redundant pass instances. 48 /// 49 /// However, it is convient to directly instantiate target passes with 50 /// non-default ctors. These often don't have a registered PassInfo. Rather than 51 /// force all target passes to implement the pass registry boilerplate, allow 52 /// the PassConfig API to handle either type. 53 /// 54 /// AnalysisID is sadly char*, so PointerIntPair won't work. 55 class IdentifyingPassPtr { 56 union { 57 AnalysisID ID; 58 Pass *P; 59 }; 60 bool IsInstance; 61 public: 62 IdentifyingPassPtr() : P(nullptr), IsInstance(false) {} 63 IdentifyingPassPtr(AnalysisID IDPtr) : ID(IDPtr), IsInstance(false) {} 64 IdentifyingPassPtr(Pass *InstancePtr) : P(InstancePtr), IsInstance(true) {} 65 66 bool isValid() const { return P; } 67 bool isInstance() const { return IsInstance; } 68 69 AnalysisID getID() const { 70 assert(!IsInstance && "Not a Pass ID"); 71 return ID; 72 } 73 Pass *getInstance() const { 74 assert(IsInstance && "Not a Pass Instance"); 75 return P; 76 } 77 }; 78 79 template <> struct isPodLike<IdentifyingPassPtr> { 80 static const bool value = true; 81 }; 82 83 /// Target-Independent Code Generator Pass Configuration Options. 84 /// 85 /// This is an ImmutablePass solely for the purpose of exposing CodeGen options 86 /// to the internals of other CodeGen passes. 87 class TargetPassConfig : public ImmutablePass { 88 public: 89 /// Pseudo Pass IDs. These are defined within TargetPassConfig because they 90 /// are unregistered pass IDs. They are only useful for use with 91 /// TargetPassConfig APIs to identify multiple occurrences of the same pass. 92 /// 93 94 /// EarlyTailDuplicate - A clone of the TailDuplicate pass that runs early 95 /// during codegen, on SSA form. 96 static char EarlyTailDuplicateID; 97 98 /// PostRAMachineLICM - A clone of the LICM pass that runs during late machine 99 /// optimization after regalloc. 100 static char PostRAMachineLICMID; 101 102 private: 103 PassManagerBase *PM; 104 AnalysisID StartAfter; 105 AnalysisID StopAfter; 106 bool Started; 107 bool Stopped; 108 109 protected: 110 TargetMachine *TM; 111 PassConfigImpl *Impl; // Internal data structures 112 bool Initialized; // Flagged after all passes are configured. 113 114 // Target Pass Options 115 // Targets provide a default setting, user flags override. 116 // 117 bool DisableVerify; 118 119 /// Default setting for -enable-tail-merge on this target. 120 bool EnableTailMerge; 121 122 public: 123 TargetPassConfig(TargetMachine *tm, PassManagerBase &pm); 124 // Dummy constructor. 125 TargetPassConfig(); 126 127 virtual ~TargetPassConfig(); 128 129 static char ID; 130 131 /// Get the right type of TargetMachine for this target. 132 template<typename TMC> TMC &getTM() const { 133 return *static_cast<TMC*>(TM); 134 } 135 136 // 137 void setInitialized() { Initialized = true; } 138 139 CodeGenOpt::Level getOptLevel() const { return TM->getOptLevel(); } 140 141 /// setStartStopPasses - Set the StartAfter and StopAfter passes to allow 142 /// running only a portion of the normal code-gen pass sequence. If the 143 /// Start pass ID is zero, then compilation will begin at the normal point; 144 /// otherwise, clear the Started flag to indicate that passes should not be 145 /// added until the starting pass is seen. If the Stop pass ID is zero, 146 /// then compilation will continue to the end. 147 void setStartStopPasses(AnalysisID Start, AnalysisID Stop) { 148 StartAfter = Start; 149 StopAfter = Stop; 150 Started = (StartAfter == nullptr); 151 } 152 153 void setDisableVerify(bool Disable) { setOpt(DisableVerify, Disable); } 154 155 bool getEnableTailMerge() const { return EnableTailMerge; } 156 void setEnableTailMerge(bool Enable) { setOpt(EnableTailMerge, Enable); } 157 158 /// Allow the target to override a specific pass without overriding the pass 159 /// pipeline. When passes are added to the standard pipeline at the 160 /// point where StandardID is expected, add TargetID in its place. 161 void substitutePass(AnalysisID StandardID, IdentifyingPassPtr TargetID); 162 163 /// Insert InsertedPassID pass after TargetPassID pass. 164 void insertPass(AnalysisID TargetPassID, IdentifyingPassPtr InsertedPassID); 165 166 /// Allow the target to enable a specific standard pass by default. 167 void enablePass(AnalysisID PassID) { substitutePass(PassID, PassID); } 168 169 /// Allow the target to disable a specific standard pass by default. 170 void disablePass(AnalysisID PassID) { 171 substitutePass(PassID, IdentifyingPassPtr()); 172 } 173 174 /// Return the pass substituted for StandardID by the target. 175 /// If no substitution exists, return StandardID. 176 IdentifyingPassPtr getPassSubstitution(AnalysisID StandardID) const; 177 178 /// Return true if the optimized regalloc pipeline is enabled. 179 bool getOptimizeRegAlloc() const; 180 181 /// Add common target configurable passes that perform LLVM IR to IR 182 /// transforms following machine independent optimization. 183 virtual void addIRPasses(); 184 185 /// Add passes to lower exception handling for the code generator. 186 void addPassesToHandleExceptions(); 187 188 /// Add pass to prepare the LLVM IR for code generation. This should be done 189 /// before exception handling preparation passes. 190 virtual void addCodeGenPrepare(); 191 192 /// Add common passes that perform LLVM IR to IR transforms in preparation for 193 /// instruction selection. 194 virtual void addISelPrepare(); 195 196 /// addInstSelector - This method should install an instruction selector pass, 197 /// which converts from LLVM code to machine instructions. 198 virtual bool addInstSelector() { 199 return true; 200 } 201 202 /// Add the complete, standard set of LLVM CodeGen passes. 203 /// Fully developed targets will not generally override this. 204 virtual void addMachinePasses(); 205 206 /// Create an instance of ScheduleDAGInstrs to be run within the standard 207 /// MachineScheduler pass for this function and target at the current 208 /// optimization level. 209 /// 210 /// This can also be used to plug a new MachineSchedStrategy into an instance 211 /// of the standard ScheduleDAGMI: 212 /// return new ScheduleDAGMI(C, new MyStrategy(C)) 213 /// 214 /// Return NULL to select the default (generic) machine scheduler. 215 virtual ScheduleDAGInstrs * 216 createMachineScheduler(MachineSchedContext *C) const { 217 return nullptr; 218 } 219 220 /// Similar to createMachineScheduler but used when postRA machine scheduling 221 /// is enabled. 222 virtual ScheduleDAGInstrs * 223 createPostMachineScheduler(MachineSchedContext *C) const { 224 return nullptr; 225 } 226 227 protected: 228 // Helper to verify the analysis is really immutable. 229 void setOpt(bool &Opt, bool Val); 230 231 /// Methods with trivial inline returns are convenient points in the common 232 /// codegen pass pipeline where targets may insert passes. Methods with 233 /// out-of-line standard implementations are major CodeGen stages called by 234 /// addMachinePasses. Some targets may override major stages when inserting 235 /// passes is insufficient, but maintaining overriden stages is more work. 236 /// 237 238 /// addPreISelPasses - This method should add any "last minute" LLVM->LLVM 239 /// passes (which are run just before instruction selector). 240 virtual bool addPreISel() { 241 return true; 242 } 243 244 /// addMachineSSAOptimization - Add standard passes that optimize machine 245 /// instructions in SSA form. 246 virtual void addMachineSSAOptimization(); 247 248 /// Add passes that optimize instruction level parallelism for out-of-order 249 /// targets. These passes are run while the machine code is still in SSA 250 /// form, so they can use MachineTraceMetrics to control their heuristics. 251 /// 252 /// All passes added here should preserve the MachineDominatorTree, 253 /// MachineLoopInfo, and MachineTraceMetrics analyses. 254 virtual bool addILPOpts() { 255 return false; 256 } 257 258 /// addPreRegAlloc - This method may be implemented by targets that want to 259 /// run passes immediately before register allocation. This should return 260 /// true if -print-machineinstrs should print after these passes. 261 virtual bool addPreRegAlloc() { 262 return false; 263 } 264 265 /// createTargetRegisterAllocator - Create the register allocator pass for 266 /// this target at the current optimization level. 267 virtual FunctionPass *createTargetRegisterAllocator(bool Optimized); 268 269 /// addFastRegAlloc - Add the minimum set of target-independent passes that 270 /// are required for fast register allocation. 271 virtual void addFastRegAlloc(FunctionPass *RegAllocPass); 272 273 /// addOptimizedRegAlloc - Add passes related to register allocation. 274 /// LLVMTargetMachine provides standard regalloc passes for most targets. 275 virtual void addOptimizedRegAlloc(FunctionPass *RegAllocPass); 276 277 /// addPreRewrite - Add passes to the optimized register allocation pipeline 278 /// after register allocation is complete, but before virtual registers are 279 /// rewritten to physical registers. 280 /// 281 /// These passes must preserve VirtRegMap and LiveIntervals, and when running 282 /// after RABasic or RAGreedy, they should take advantage of LiveRegMatrix. 283 /// When these passes run, VirtRegMap contains legal physreg assignments for 284 /// all virtual registers. 285 virtual bool addPreRewrite() { 286 return false; 287 } 288 289 /// addPostRegAlloc - This method may be implemented by targets that want to 290 /// run passes after register allocation pass pipeline but before 291 /// prolog-epilog insertion. This should return true if -print-machineinstrs 292 /// should print after these passes. 293 virtual bool addPostRegAlloc() { 294 return false; 295 } 296 297 /// Add passes that optimize machine instructions after register allocation. 298 virtual void addMachineLateOptimization(); 299 300 /// addPreSched2 - This method may be implemented by targets that want to 301 /// run passes after prolog-epilog insertion and before the second instruction 302 /// scheduling pass. This should return true if -print-machineinstrs should 303 /// print after these passes. 304 virtual bool addPreSched2() { 305 return false; 306 } 307 308 /// addGCPasses - Add late codegen passes that analyze code for garbage 309 /// collection. This should return true if GC info should be printed after 310 /// these passes. 311 virtual bool addGCPasses(); 312 313 /// Add standard basic block placement passes. 314 virtual void addBlockPlacement(); 315 316 /// addPreEmitPass - This pass may be implemented by targets that want to run 317 /// passes immediately before machine code is emitted. This should return 318 /// true if -print-machineinstrs should print out the code after the passes. 319 virtual bool addPreEmitPass() { 320 return false; 321 } 322 323 /// Utilities for targets to add passes to the pass manager. 324 /// 325 326 /// Add a CodeGen pass at this point in the pipeline after checking overrides. 327 /// Return the pass that was added, or zero if no pass was added. 328 AnalysisID addPass(AnalysisID PassID); 329 330 /// Add a pass to the PassManager if that pass is supposed to be run, as 331 /// determined by the StartAfter and StopAfter options. Takes ownership of the 332 /// pass. 333 void addPass(Pass *P); 334 335 /// addMachinePasses helper to create the target-selected or overriden 336 /// regalloc pass. 337 FunctionPass *createRegAllocPass(bool Optimized); 338 339 /// printAndVerify - Add a pass to dump then verify the machine function, if 340 /// those steps are enabled. 341 /// 342 void printAndVerify(const char *Banner); 343 }; 344 } // namespace llvm 345 346 /// List of target independent CodeGen pass IDs. 347 namespace llvm { 348 FunctionPass *createAtomicExpandLoadLinkedPass(const TargetMachine *TM); 349 350 /// \brief Create a basic TargetTransformInfo analysis pass. 351 /// 352 /// This pass implements the target transform info analysis using the target 353 /// independent information available to the LLVM code generator. 354 ImmutablePass * 355 createBasicTargetTransformInfoPass(const TargetMachine *TM); 356 357 /// createUnreachableBlockEliminationPass - The LLVM code generator does not 358 /// work well with unreachable basic blocks (what live ranges make sense for a 359 /// block that cannot be reached?). As such, a code generator should either 360 /// not instruction select unreachable blocks, or run this pass as its 361 /// last LLVM modifying pass to clean up blocks that are not reachable from 362 /// the entry block. 363 FunctionPass *createUnreachableBlockEliminationPass(); 364 365 /// MachineFunctionPrinter pass - This pass prints out the machine function to 366 /// the given stream as a debugging tool. 367 MachineFunctionPass * 368 createMachineFunctionPrinterPass(raw_ostream &OS, 369 const std::string &Banner =""); 370 371 /// createCodeGenPreparePass - Transform the code to expose more pattern 372 /// matching during instruction selection. 373 FunctionPass *createCodeGenPreparePass(const TargetMachine *TM = nullptr); 374 375 /// AtomicExpandLoadLinkedID -- FIXME 376 extern char &AtomicExpandLoadLinkedID; 377 378 /// MachineLoopInfo - This pass is a loop analysis pass. 379 extern char &MachineLoopInfoID; 380 381 /// MachineDominators - This pass is a machine dominators analysis pass. 382 extern char &MachineDominatorsID; 383 384 /// EdgeBundles analysis - Bundle machine CFG edges. 385 extern char &EdgeBundlesID; 386 387 /// LiveVariables pass - This pass computes the set of blocks in which each 388 /// variable is life and sets machine operand kill flags. 389 extern char &LiveVariablesID; 390 391 /// PHIElimination - This pass eliminates machine instruction PHI nodes 392 /// by inserting copy instructions. This destroys SSA information, but is the 393 /// desired input for some register allocators. This pass is "required" by 394 /// these register allocator like this: AU.addRequiredID(PHIEliminationID); 395 extern char &PHIEliminationID; 396 397 /// LiveIntervals - This analysis keeps track of the live ranges of virtual 398 /// and physical registers. 399 extern char &LiveIntervalsID; 400 401 /// LiveStacks pass. An analysis keeping track of the liveness of stack slots. 402 extern char &LiveStacksID; 403 404 /// TwoAddressInstruction - This pass reduces two-address instructions to 405 /// use two operands. This destroys SSA information but it is desired by 406 /// register allocators. 407 extern char &TwoAddressInstructionPassID; 408 409 /// ProcessImpicitDefs pass - This pass removes IMPLICIT_DEFs. 410 extern char &ProcessImplicitDefsID; 411 412 /// RegisterCoalescer - This pass merges live ranges to eliminate copies. 413 extern char &RegisterCoalescerID; 414 415 /// MachineScheduler - This pass schedules machine instructions. 416 extern char &MachineSchedulerID; 417 418 /// PostMachineScheduler - This pass schedules machine instructions postRA. 419 extern char &PostMachineSchedulerID; 420 421 /// SpillPlacement analysis. Suggest optimal placement of spill code between 422 /// basic blocks. 423 extern char &SpillPlacementID; 424 425 /// VirtRegRewriter pass. Rewrite virtual registers to physical registers as 426 /// assigned in VirtRegMap. 427 extern char &VirtRegRewriterID; 428 429 /// UnreachableMachineBlockElimination - This pass removes unreachable 430 /// machine basic blocks. 431 extern char &UnreachableMachineBlockElimID; 432 433 /// DeadMachineInstructionElim - This pass removes dead machine instructions. 434 extern char &DeadMachineInstructionElimID; 435 436 /// FastRegisterAllocation Pass - This pass register allocates as fast as 437 /// possible. It is best suited for debug code where live ranges are short. 438 /// 439 FunctionPass *createFastRegisterAllocator(); 440 441 /// BasicRegisterAllocation Pass - This pass implements a degenerate global 442 /// register allocator using the basic regalloc framework. 443 /// 444 FunctionPass *createBasicRegisterAllocator(); 445 446 /// Greedy register allocation pass - This pass implements a global register 447 /// allocator for optimized builds. 448 /// 449 FunctionPass *createGreedyRegisterAllocator(); 450 451 /// PBQPRegisterAllocation Pass - This pass implements the Partitioned Boolean 452 /// Quadratic Prograaming (PBQP) based register allocator. 453 /// 454 FunctionPass *createDefaultPBQPRegisterAllocator(); 455 456 /// PrologEpilogCodeInserter - This pass inserts prolog and epilog code, 457 /// and eliminates abstract frame references. 458 extern char &PrologEpilogCodeInserterID; 459 460 /// ExpandPostRAPseudos - This pass expands pseudo instructions after 461 /// register allocation. 462 extern char &ExpandPostRAPseudosID; 463 464 /// createPostRAScheduler - This pass performs post register allocation 465 /// scheduling. 466 extern char &PostRASchedulerID; 467 468 /// BranchFolding - This pass performs machine code CFG based 469 /// optimizations to delete branches to branches, eliminate branches to 470 /// successor blocks (creating fall throughs), and eliminating branches over 471 /// branches. 472 extern char &BranchFolderPassID; 473 474 /// MachineFunctionPrinterPass - This pass prints out MachineInstr's. 475 extern char &MachineFunctionPrinterPassID; 476 477 /// TailDuplicate - Duplicate blocks with unconditional branches 478 /// into tails of their predecessors. 479 extern char &TailDuplicateID; 480 481 /// MachineTraceMetrics - This pass computes critical path and CPU resource 482 /// usage in an ensemble of traces. 483 extern char &MachineTraceMetricsID; 484 485 /// EarlyIfConverter - This pass performs if-conversion on SSA form by 486 /// inserting cmov instructions. 487 extern char &EarlyIfConverterID; 488 489 /// StackSlotColoring - This pass performs stack coloring and merging. 490 /// It merges disjoint allocas to reduce the stack size. 491 extern char &StackColoringID; 492 493 /// IfConverter - This pass performs machine code if conversion. 494 extern char &IfConverterID; 495 496 /// MachineBlockPlacement - This pass places basic blocks based on branch 497 /// probabilities. 498 extern char &MachineBlockPlacementID; 499 500 /// MachineBlockPlacementStats - This pass collects statistics about the 501 /// basic block placement using branch probabilities and block frequency 502 /// information. 503 extern char &MachineBlockPlacementStatsID; 504 505 /// GCLowering Pass - Performs target-independent LLVM IR transformations for 506 /// highly portable strategies. 507 /// 508 FunctionPass *createGCLoweringPass(); 509 510 /// GCMachineCodeAnalysis - Target-independent pass to mark safe points 511 /// in machine code. Must be added very late during code generation, just 512 /// prior to output, and importantly after all CFG transformations (such as 513 /// branch folding). 514 extern char &GCMachineCodeAnalysisID; 515 516 /// Creates a pass to print GC metadata. 517 /// 518 FunctionPass *createGCInfoPrinter(raw_ostream &OS); 519 520 /// MachineCSE - This pass performs global CSE on machine instructions. 521 extern char &MachineCSEID; 522 523 /// MachineLICM - This pass performs LICM on machine instructions. 524 extern char &MachineLICMID; 525 526 /// MachineSinking - This pass performs sinking on machine instructions. 527 extern char &MachineSinkingID; 528 529 /// MachineCopyPropagation - This pass performs copy propagation on 530 /// machine instructions. 531 extern char &MachineCopyPropagationID; 532 533 /// PeepholeOptimizer - This pass performs peephole optimizations - 534 /// like extension and comparison eliminations. 535 extern char &PeepholeOptimizerID; 536 537 /// OptimizePHIs - This pass optimizes machine instruction PHIs 538 /// to take advantage of opportunities created during DAG legalization. 539 extern char &OptimizePHIsID; 540 541 /// StackSlotColoring - This pass performs stack slot coloring. 542 extern char &StackSlotColoringID; 543 544 /// createStackProtectorPass - This pass adds stack protectors to functions. 545 /// 546 FunctionPass *createStackProtectorPass(const TargetMachine *TM); 547 548 /// createMachineVerifierPass - This pass verifies cenerated machine code 549 /// instructions for correctness. 550 /// 551 FunctionPass *createMachineVerifierPass(const char *Banner = nullptr); 552 553 /// createDwarfEHPass - This pass mulches exception handling code into a form 554 /// adapted to code generation. Required if using dwarf exception handling. 555 FunctionPass *createDwarfEHPass(const TargetMachine *TM); 556 557 /// createSjLjEHPreparePass - This pass adapts exception handling code to use 558 /// the GCC-style builtin setjmp/longjmp (sjlj) to handling EH control flow. 559 /// 560 FunctionPass *createSjLjEHPreparePass(const TargetMachine *TM); 561 562 /// LocalStackSlotAllocation - This pass assigns local frame indices to stack 563 /// slots relative to one another and allocates base registers to access them 564 /// when it is estimated by the target to be out of range of normal frame 565 /// pointer or stack pointer index addressing. 566 extern char &LocalStackSlotAllocationID; 567 568 /// ExpandISelPseudos - This pass expands pseudo-instructions. 569 extern char &ExpandISelPseudosID; 570 571 /// createExecutionDependencyFixPass - This pass fixes execution time 572 /// problems with dependent instructions, such as switching execution 573 /// domains to match. 574 /// 575 /// The pass will examine instructions using and defining registers in RC. 576 /// 577 FunctionPass *createExecutionDependencyFixPass(const TargetRegisterClass *RC); 578 579 /// UnpackMachineBundles - This pass unpack machine instruction bundles. 580 extern char &UnpackMachineBundlesID; 581 582 /// FinalizeMachineBundles - This pass finalize machine instruction 583 /// bundles (created earlier, e.g. during pre-RA scheduling). 584 extern char &FinalizeMachineBundlesID; 585 586 /// StackMapLiveness - This pass analyses the register live-out set of 587 /// stackmap/patchpoint intrinsics and attaches the calculated information to 588 /// the intrinsic for later emission to the StackMap. 589 extern char &StackMapLivenessID; 590 591 /// createJumpInstrTables - This pass creates jump-instruction tables. 592 ModulePass *createJumpInstrTablesPass(); 593 } // End llvm namespace 594 595 /// This initializer registers TargetMachine constructor, so the pass being 596 /// initialized can use target dependent interfaces. Please do not move this 597 /// macro to be together with INITIALIZE_PASS, which is a complete target 598 /// independent initializer, and we don't want to make libScalarOpts depend 599 /// on libCodeGen. 600 #define INITIALIZE_TM_PASS(passName, arg, name, cfg, analysis) \ 601 static void* initialize##passName##PassOnce(PassRegistry &Registry) { \ 602 PassInfo *PI = new PassInfo(name, arg, & passName ::ID, \ 603 PassInfo::NormalCtor_t(callDefaultCtor< passName >), cfg, analysis, \ 604 PassInfo::TargetMachineCtor_t(callTargetMachineCtor< passName >)); \ 605 Registry.registerPass(*PI, true); \ 606 return PI; \ 607 } \ 608 void llvm::initialize##passName##Pass(PassRegistry &Registry) { \ 609 CALL_ONCE_INITIALIZATION(initialize##passName##PassOnce) \ 610 } 611 612 #endif 613