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 22namespace llvm { 23 24class FunctionPass; 25class MachineFunctionPass; 26class PassConfigImpl; 27class PassInfo; 28class ScheduleDAGInstrs; 29class TargetLowering; 30class TargetLoweringBase; 31class TargetRegisterClass; 32class raw_ostream; 33struct MachineSchedContext; 34 35// The old pass manager infrastructure is hidden in a legacy namespace now. 36namespace legacy { 37class PassManagerBase; 38} 39using 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. 55class IdentifyingPassPtr { 56 union { 57 AnalysisID ID; 58 Pass *P; 59 }; 60 bool IsInstance; 61public: 62 IdentifyingPassPtr() : P(0), 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 79template <> 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. 87class TargetPassConfig : public ImmutablePass { 88public: 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 102private: 103 PassManagerBase *PM; 104 AnalysisID StartAfter; 105 AnalysisID StopAfter; 106 bool Started; 107 bool Stopped; 108 109protected: 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 122public: 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 const TargetLowering *getTargetLowering() const { 137 return TM->getTargetLowering(); 138 } 139 140 // 141 void setInitialized() { Initialized = true; } 142 143 CodeGenOpt::Level getOptLevel() const { return TM->getOptLevel(); } 144 145 /// setStartStopPasses - Set the StartAfter and StopAfter passes to allow 146 /// running only a portion of the normal code-gen pass sequence. If the 147 /// Start pass ID is zero, then compilation will begin at the normal point; 148 /// otherwise, clear the Started flag to indicate that passes should not be 149 /// added until the starting pass is seen. If the Stop pass ID is zero, 150 /// then compilation will continue to the end. 151 void setStartStopPasses(AnalysisID Start, AnalysisID Stop) { 152 StartAfter = Start; 153 StopAfter = Stop; 154 Started = (StartAfter == 0); 155 } 156 157 void setDisableVerify(bool Disable) { setOpt(DisableVerify, Disable); } 158 159 bool getEnableTailMerge() const { return EnableTailMerge; } 160 void setEnableTailMerge(bool Enable) { setOpt(EnableTailMerge, Enable); } 161 162 /// Allow the target to override a specific pass without overriding the pass 163 /// pipeline. When passes are added to the standard pipeline at the 164 /// point where StandardID is expected, add TargetID in its place. 165 void substitutePass(AnalysisID StandardID, IdentifyingPassPtr TargetID); 166 167 /// Insert InsertedPassID pass after TargetPassID pass. 168 void insertPass(AnalysisID TargetPassID, IdentifyingPassPtr InsertedPassID); 169 170 /// Allow the target to enable a specific standard pass by default. 171 void enablePass(AnalysisID PassID) { substitutePass(PassID, PassID); } 172 173 /// Allow the target to disable a specific standard pass by default. 174 void disablePass(AnalysisID PassID) { 175 substitutePass(PassID, IdentifyingPassPtr()); 176 } 177 178 /// Return the pass substituted for StandardID by the target. 179 /// If no substitution exists, return StandardID. 180 IdentifyingPassPtr getPassSubstitution(AnalysisID StandardID) const; 181 182 /// Return true if the optimized regalloc pipeline is enabled. 183 bool getOptimizeRegAlloc() const; 184 185 /// Add common target configurable passes that perform LLVM IR to IR 186 /// transforms following machine independent optimization. 187 virtual void addIRPasses(); 188 189 /// Add passes to lower exception handling for the code generator. 190 void addPassesToHandleExceptions(); 191 192 /// Add pass to prepare the LLVM IR for code generation. This should be done 193 /// before exception handling preparation passes. 194 virtual void addCodeGenPrepare(); 195 196 /// Add common passes that perform LLVM IR to IR transforms in preparation for 197 /// instruction selection. 198 virtual void addISelPrepare(); 199 200 /// addInstSelector - This method should install an instruction selector pass, 201 /// which converts from LLVM code to machine instructions. 202 virtual bool addInstSelector() { 203 return true; 204 } 205 206 /// Add the complete, standard set of LLVM CodeGen passes. 207 /// Fully developed targets will not generally override this. 208 virtual void addMachinePasses(); 209 210 /// createTargetScheduler - Create an instance of ScheduleDAGInstrs to be run 211 /// within the standard MachineScheduler pass for this function and target at 212 /// the current optimization level. 213 /// 214 /// This can also be used to plug a new MachineSchedStrategy into an instance 215 /// of the standard ScheduleDAGMI: 216 /// return new ScheduleDAGMI(C, new MyStrategy(C)) 217 /// 218 /// Return NULL to select the default (generic) machine scheduler. 219 virtual ScheduleDAGInstrs * 220 createMachineScheduler(MachineSchedContext *C) const { 221 return 0; 222 } 223 224protected: 225 // Helper to verify the analysis is really immutable. 226 void setOpt(bool &Opt, bool Val); 227 228 /// Methods with trivial inline returns are convenient points in the common 229 /// codegen pass pipeline where targets may insert passes. Methods with 230 /// out-of-line standard implementations are major CodeGen stages called by 231 /// addMachinePasses. Some targets may override major stages when inserting 232 /// passes is insufficient, but maintaining overriden stages is more work. 233 /// 234 235 /// addPreISelPasses - This method should add any "last minute" LLVM->LLVM 236 /// passes (which are run just before instruction selector). 237 virtual bool addPreISel() { 238 return true; 239 } 240 241 /// addMachineSSAOptimization - Add standard passes that optimize machine 242 /// instructions in SSA form. 243 virtual void addMachineSSAOptimization(); 244 245 /// Add passes that optimize instruction level parallelism for out-of-order 246 /// targets. These passes are run while the machine code is still in SSA 247 /// form, so they can use MachineTraceMetrics to control their heuristics. 248 /// 249 /// All passes added here should preserve the MachineDominatorTree, 250 /// MachineLoopInfo, and MachineTraceMetrics analyses. 251 virtual bool addILPOpts() { 252 return false; 253 } 254 255 /// addPreRegAlloc - This method may be implemented by targets that want to 256 /// run passes immediately before register allocation. This should return 257 /// true if -print-machineinstrs should print after these passes. 258 virtual bool addPreRegAlloc() { 259 return false; 260 } 261 262 /// createTargetRegisterAllocator - Create the register allocator pass for 263 /// this target at the current optimization level. 264 virtual FunctionPass *createTargetRegisterAllocator(bool Optimized); 265 266 /// addFastRegAlloc - Add the minimum set of target-independent passes that 267 /// are required for fast register allocation. 268 virtual void addFastRegAlloc(FunctionPass *RegAllocPass); 269 270 /// addOptimizedRegAlloc - Add passes related to register allocation. 271 /// LLVMTargetMachine provides standard regalloc passes for most targets. 272 virtual void addOptimizedRegAlloc(FunctionPass *RegAllocPass); 273 274 /// addPreRewrite - Add passes to the optimized register allocation pipeline 275 /// after register allocation is complete, but before virtual registers are 276 /// rewritten to physical registers. 277 /// 278 /// These passes must preserve VirtRegMap and LiveIntervals, and when running 279 /// after RABasic or RAGreedy, they should take advantage of LiveRegMatrix. 280 /// When these passes run, VirtRegMap contains legal physreg assignments for 281 /// all virtual registers. 282 virtual bool addPreRewrite() { 283 return false; 284 } 285 286 /// addPostRegAlloc - This method may be implemented by targets that want to 287 /// run passes after register allocation pass pipeline but before 288 /// prolog-epilog insertion. This should return true if -print-machineinstrs 289 /// should print after these passes. 290 virtual bool addPostRegAlloc() { 291 return false; 292 } 293 294 /// Add passes that optimize machine instructions after register allocation. 295 virtual void addMachineLateOptimization(); 296 297 /// addPreSched2 - This method may be implemented by targets that want to 298 /// run passes after prolog-epilog insertion and before the second instruction 299 /// scheduling pass. This should return true if -print-machineinstrs should 300 /// print after these passes. 301 virtual bool addPreSched2() { 302 return false; 303 } 304 305 /// addGCPasses - Add late codegen passes that analyze code for garbage 306 /// collection. This should return true if GC info should be printed after 307 /// these passes. 308 virtual bool addGCPasses(); 309 310 /// Add standard basic block placement passes. 311 virtual void addBlockPlacement(); 312 313 /// addPreEmitPass - This pass may be implemented by targets that want to run 314 /// passes immediately before machine code is emitted. This should return 315 /// true if -print-machineinstrs should print out the code after the passes. 316 virtual bool addPreEmitPass() { 317 return false; 318 } 319 320 /// Utilities for targets to add passes to the pass manager. 321 /// 322 323 /// Add a CodeGen pass at this point in the pipeline after checking overrides. 324 /// Return the pass that was added, or zero if no pass was added. 325 AnalysisID addPass(AnalysisID PassID); 326 327 /// Add a pass to the PassManager if that pass is supposed to be run, as 328 /// determined by the StartAfter and StopAfter options. Takes ownership of the 329 /// pass. 330 void addPass(Pass *P); 331 332 /// addMachinePasses helper to create the target-selected or overriden 333 /// regalloc pass. 334 FunctionPass *createRegAllocPass(bool Optimized); 335 336 /// printAndVerify - Add a pass to dump then verify the machine function, if 337 /// those steps are enabled. 338 /// 339 void printAndVerify(const char *Banner); 340}; 341} // namespace llvm 342 343/// List of target independent CodeGen pass IDs. 344namespace llvm { 345 /// \brief Create a basic TargetTransformInfo analysis pass. 346 /// 347 /// This pass implements the target transform info analysis using the target 348 /// independent information available to the LLVM code generator. 349 ImmutablePass * 350 createBasicTargetTransformInfoPass(const TargetMachine *TM); 351 352 /// createUnreachableBlockEliminationPass - The LLVM code generator does not 353 /// work well with unreachable basic blocks (what live ranges make sense for a 354 /// block that cannot be reached?). As such, a code generator should either 355 /// not instruction select unreachable blocks, or run this pass as its 356 /// last LLVM modifying pass to clean up blocks that are not reachable from 357 /// the entry block. 358 FunctionPass *createUnreachableBlockEliminationPass(); 359 360 /// MachineFunctionPrinter pass - This pass prints out the machine function to 361 /// the given stream as a debugging tool. 362 MachineFunctionPass * 363 createMachineFunctionPrinterPass(raw_ostream &OS, 364 const std::string &Banner =""); 365 366 /// MachineLoopInfo - This pass is a loop analysis pass. 367 extern char &MachineLoopInfoID; 368 369 /// MachineDominators - This pass is a machine dominators analysis pass. 370 extern char &MachineDominatorsID; 371 372 /// EdgeBundles analysis - Bundle machine CFG edges. 373 extern char &EdgeBundlesID; 374 375 /// LiveVariables pass - This pass computes the set of blocks in which each 376 /// variable is life and sets machine operand kill flags. 377 extern char &LiveVariablesID; 378 379 /// PHIElimination - This pass eliminates machine instruction PHI nodes 380 /// by inserting copy instructions. This destroys SSA information, but is the 381 /// desired input for some register allocators. This pass is "required" by 382 /// these register allocator like this: AU.addRequiredID(PHIEliminationID); 383 extern char &PHIEliminationID; 384 385 /// LiveIntervals - This analysis keeps track of the live ranges of virtual 386 /// and physical registers. 387 extern char &LiveIntervalsID; 388 389 /// LiveStacks pass. An analysis keeping track of the liveness of stack slots. 390 extern char &LiveStacksID; 391 392 /// TwoAddressInstruction - This pass reduces two-address instructions to 393 /// use two operands. This destroys SSA information but it is desired by 394 /// register allocators. 395 extern char &TwoAddressInstructionPassID; 396 397 /// ProcessImpicitDefs pass - This pass removes IMPLICIT_DEFs. 398 extern char &ProcessImplicitDefsID; 399 400 /// RegisterCoalescer - This pass merges live ranges to eliminate copies. 401 extern char &RegisterCoalescerID; 402 403 /// MachineScheduler - This pass schedules machine instructions. 404 extern char &MachineSchedulerID; 405 406 /// SpillPlacement analysis. Suggest optimal placement of spill code between 407 /// basic blocks. 408 extern char &SpillPlacementID; 409 410 /// VirtRegRewriter pass. Rewrite virtual registers to physical registers as 411 /// assigned in VirtRegMap. 412 extern char &VirtRegRewriterID; 413 414 /// UnreachableMachineBlockElimination - This pass removes unreachable 415 /// machine basic blocks. 416 extern char &UnreachableMachineBlockElimID; 417 418 /// DeadMachineInstructionElim - This pass removes dead machine instructions. 419 extern char &DeadMachineInstructionElimID; 420 421 /// FastRegisterAllocation Pass - This pass register allocates as fast as 422 /// possible. It is best suited for debug code where live ranges are short. 423 /// 424 FunctionPass *createFastRegisterAllocator(); 425 426 /// BasicRegisterAllocation Pass - This pass implements a degenerate global 427 /// register allocator using the basic regalloc framework. 428 /// 429 FunctionPass *createBasicRegisterAllocator(); 430 431 /// Greedy register allocation pass - This pass implements a global register 432 /// allocator for optimized builds. 433 /// 434 FunctionPass *createGreedyRegisterAllocator(); 435 436 /// PBQPRegisterAllocation Pass - This pass implements the Partitioned Boolean 437 /// Quadratic Prograaming (PBQP) based register allocator. 438 /// 439 FunctionPass *createDefaultPBQPRegisterAllocator(); 440 441 /// PrologEpilogCodeInserter - This pass inserts prolog and epilog code, 442 /// and eliminates abstract frame references. 443 extern char &PrologEpilogCodeInserterID; 444 445 /// ExpandPostRAPseudos - This pass expands pseudo instructions after 446 /// register allocation. 447 extern char &ExpandPostRAPseudosID; 448 449 /// createPostRAScheduler - This pass performs post register allocation 450 /// scheduling. 451 extern char &PostRASchedulerID; 452 453 /// BranchFolding - This pass performs machine code CFG based 454 /// optimizations to delete branches to branches, eliminate branches to 455 /// successor blocks (creating fall throughs), and eliminating branches over 456 /// branches. 457 extern char &BranchFolderPassID; 458 459 /// MachineFunctionPrinterPass - This pass prints out MachineInstr's. 460 extern char &MachineFunctionPrinterPassID; 461 462 /// TailDuplicate - Duplicate blocks with unconditional branches 463 /// into tails of their predecessors. 464 extern char &TailDuplicateID; 465 466 /// MachineTraceMetrics - This pass computes critical path and CPU resource 467 /// usage in an ensemble of traces. 468 extern char &MachineTraceMetricsID; 469 470 /// EarlyIfConverter - This pass performs if-conversion on SSA form by 471 /// inserting cmov instructions. 472 extern char &EarlyIfConverterID; 473 474 /// StackSlotColoring - This pass performs stack coloring and merging. 475 /// It merges disjoint allocas to reduce the stack size. 476 extern char &StackColoringID; 477 478 /// IfConverter - This pass performs machine code if conversion. 479 extern char &IfConverterID; 480 481 /// MachineBlockPlacement - This pass places basic blocks based on branch 482 /// probabilities. 483 extern char &MachineBlockPlacementID; 484 485 /// MachineBlockPlacementStats - This pass collects statistics about the 486 /// basic block placement using branch probabilities and block frequency 487 /// information. 488 extern char &MachineBlockPlacementStatsID; 489 490 /// GCLowering Pass - Performs target-independent LLVM IR transformations for 491 /// highly portable strategies. 492 /// 493 FunctionPass *createGCLoweringPass(); 494 495 /// GCMachineCodeAnalysis - Target-independent pass to mark safe points 496 /// in machine code. Must be added very late during code generation, just 497 /// prior to output, and importantly after all CFG transformations (such as 498 /// branch folding). 499 extern char &GCMachineCodeAnalysisID; 500 501 /// Creates a pass to print GC metadata. 502 /// 503 FunctionPass *createGCInfoPrinter(raw_ostream &OS); 504 505 /// MachineCSE - This pass performs global CSE on machine instructions. 506 extern char &MachineCSEID; 507 508 /// MachineLICM - This pass performs LICM on machine instructions. 509 extern char &MachineLICMID; 510 511 /// MachineSinking - This pass performs sinking on machine instructions. 512 extern char &MachineSinkingID; 513 514 /// MachineCopyPropagation - This pass performs copy propagation on 515 /// machine instructions. 516 extern char &MachineCopyPropagationID; 517 518 /// PeepholeOptimizer - This pass performs peephole optimizations - 519 /// like extension and comparison eliminations. 520 extern char &PeepholeOptimizerID; 521 522 /// OptimizePHIs - This pass optimizes machine instruction PHIs 523 /// to take advantage of opportunities created during DAG legalization. 524 extern char &OptimizePHIsID; 525 526 /// StackSlotColoring - This pass performs stack slot coloring. 527 extern char &StackSlotColoringID; 528 529 /// createStackProtectorPass - This pass adds stack protectors to functions. 530 /// 531 FunctionPass *createStackProtectorPass(const TargetMachine *TM); 532 533 /// createMachineVerifierPass - This pass verifies cenerated machine code 534 /// instructions for correctness. 535 /// 536 FunctionPass *createMachineVerifierPass(const char *Banner = 0); 537 538 /// createDwarfEHPass - This pass mulches exception handling code into a form 539 /// adapted to code generation. Required if using dwarf exception handling. 540 FunctionPass *createDwarfEHPass(const TargetMachine *TM); 541 542 /// createSjLjEHPreparePass - This pass adapts exception handling code to use 543 /// the GCC-style builtin setjmp/longjmp (sjlj) to handling EH control flow. 544 /// 545 FunctionPass *createSjLjEHPreparePass(const TargetMachine *TM); 546 547 /// LocalStackSlotAllocation - This pass assigns local frame indices to stack 548 /// slots relative to one another and allocates base registers to access them 549 /// when it is estimated by the target to be out of range of normal frame 550 /// pointer or stack pointer index addressing. 551 extern char &LocalStackSlotAllocationID; 552 553 /// ExpandISelPseudos - This pass expands pseudo-instructions. 554 extern char &ExpandISelPseudosID; 555 556 /// createExecutionDependencyFixPass - This pass fixes execution time 557 /// problems with dependent instructions, such as switching execution 558 /// domains to match. 559 /// 560 /// The pass will examine instructions using and defining registers in RC. 561 /// 562 FunctionPass *createExecutionDependencyFixPass(const TargetRegisterClass *RC); 563 564 /// UnpackMachineBundles - This pass unpack machine instruction bundles. 565 extern char &UnpackMachineBundlesID; 566 567 /// FinalizeMachineBundles - This pass finalize machine instruction 568 /// bundles (created earlier, e.g. during pre-RA scheduling). 569 extern char &FinalizeMachineBundlesID; 570 571} // End llvm namespace 572 573#endif 574