Scalar.h revision 82c89b9f3a9b88bb63ce13b09b4f27fbb72f66fc
1//===-- Scalar.h - Scalar Transformations ------------------------*- C++ -*-==// 2// 3// This header file defines prototypes for accessor functions that expose passes 4// in the Scalar transformations library. 5// 6//===----------------------------------------------------------------------===// 7 8#ifndef LLVM_TRANSFORMS_SCALAR_H 9#define LLVM_TRANSFORMS_SCALAR_H 10 11class Pass; 12class GetElementPtrInst; 13class PassInfo; 14class TerminatorInst; 15 16//===----------------------------------------------------------------------===// 17// 18// Constant Propagation Pass - A worklist driven constant propagation pass 19// 20Pass *createConstantPropagationPass(); 21 22 23//===----------------------------------------------------------------------===// 24// 25// Sparse Conditional Constant Propagation Pass 26// 27Pass *createSCCPPass(); 28 29 30//===----------------------------------------------------------------------===// 31// 32// DeadInstElimination - This pass quickly removes trivially dead instructions 33// without modifying the CFG of the function. It is a BasicBlockPass, so it 34// runs efficiently when queued next to other BasicBlockPass's. 35// 36Pass *createDeadInstEliminationPass(); 37 38 39//===----------------------------------------------------------------------===// 40// 41// DeadCodeElimination - This pass is more powerful than DeadInstElimination, 42// because it is worklist driven that can potentially revisit instructions when 43// their other instructions become dead, to eliminate chains of dead 44// computations. 45// 46Pass *createDeadCodeEliminationPass(); 47 48 49//===----------------------------------------------------------------------===// 50// 51// AggressiveDCE - This pass uses the SSA based Aggressive DCE algorithm. This 52// algorithm assumes instructions are dead until proven otherwise, which makes 53// it more successful are removing non-obviously dead instructions. 54// 55Pass *createAggressiveDCEPass(); 56 57 58//===----------------------------------------------------------------------===// 59// 60// DecomposeMultiDimRefs - Convert multi-dimensional references consisting of 61// any combination of 2 or more array and structure indices into a sequence of 62// instructions (using getelementpr and cast) so that each instruction has at 63// most one index (except structure references, which need an extra leading 64// index of [0]). 65 66// This pass decomposes all multi-dimensional references in a function. 67Pass *createDecomposeMultiDimRefsPass(); 68 69// This function decomposes a single instance of such a reference. 70// Return value: true if the instruction was replaced; false otherwise. 71// 72bool DecomposeArrayRef(GetElementPtrInst* GEP); 73 74//===----------------------------------------------------------------------===// 75// 76// GCSE - This pass is designed to be a very quick global transformation that 77// eliminates global common subexpressions from a function. It does this by 78// examining the SSA value graph of the function, instead of doing slow 79// bit-vector computations. 80// 81Pass *createGCSEPass(); 82 83 84//===----------------------------------------------------------------------===// 85// 86// InductionVariableSimplify - Transform induction variables in a program to all 87// use a single cannonical induction variable per loop. 88// 89Pass *createIndVarSimplifyPass(); 90 91 92//===----------------------------------------------------------------------===// 93// 94// InstructionCombining - Combine instructions to form fewer, simple 95// instructions. This pass does not modify the CFG, and has a tendancy to 96// make instructions dead, so a subsequent DCE pass is useful. 97// 98// This pass combines things like: 99// %Y = add int 1, %X 100// %Z = add int 1, %Y 101// into: 102// %Z = add int 2, %X 103// 104Pass *createInstructionCombiningPass(); 105 106 107//===----------------------------------------------------------------------===// 108// 109// LICM - This pass is a simple natural loop based loop invariant code motion 110// pass. 111// 112Pass *createLICMPass(); 113 114 115//===----------------------------------------------------------------------===// 116// 117// PiNodeInsertion - This pass inserts single entry Phi nodes into basic blocks 118// that are preceeded by a conditional branch, where the branch gives 119// information about the operands of the condition. For example, this C code: 120// if (x == 0) { ... = x + 4; 121// becomes: 122// if (x == 0) { 123// x2 = phi(x); // Node that can hold data flow information about X 124// ... = x2 + 4; 125// 126// Since the direction of the condition branch gives information about X itself 127// (whether or not it is zero), some passes (like value numbering or ABCD) can 128// use the inserted Phi/Pi nodes as a place to attach information, in this case 129// saying that X has a value of 0 in this scope. The power of this analysis 130// information is that "in the scope" translates to "for all uses of x2". 131// 132// This special form of Phi node is refered to as a Pi node, following the 133// terminology defined in the "Array Bounds Checks on Demand" paper. 134// 135Pass *createPiNodeInsertionPass(); 136 137 138//===----------------------------------------------------------------------===// 139// 140// This pass is used to promote memory references to be register references. A 141// simple example of the transformation performed by this pass is: 142// 143// FROM CODE TO CODE 144// %X = alloca int, uint 1 ret int 42 145// store int 42, int *%X 146// %Y = load int* %X 147// ret int %Y 148// 149Pass *createPromoteMemoryToRegister(); 150 151 152//===----------------------------------------------------------------------===// 153// 154// This pass reassociates commutative expressions in an order that is designed 155// to promote better constant propagation, GCSE, LICM, PRE... 156// 157// For example: 4 + (x + 5) -> x + (4 + 5) 158// 159Pass *createReassociatePass(); 160 161//===----------------------------------------------------------------------===// 162// 163// This pass eliminates correlated conditions, such as these: 164// if (X == 0) 165// if (X > 2) ; // Known false 166// else 167// Y = X * Z; // = 0 168// 169Pass *createCorrelatedExpressionEliminationPass(); 170 171//===----------------------------------------------------------------------===// 172// 173// CFG Simplification - Merge basic blocks, eliminate unreachable blocks, 174// simplify terminator instructions, etc... 175// 176Pass *createCFGSimplificationPass(); 177 178//===----------------------------------------------------------------------===// 179// 180// BreakCriticalEdges pass - Break all of the critical edges in the CFG by 181// inserting a dummy basic block. This pass may be "required" by passes that 182// cannot deal with critical edges. For this usage, a pass must call: 183// 184// AU.addRequiredID(BreakCriticalEdgesID); 185// 186// This pass obviously invalidates the CFG, but can update forward dominator 187// (set, immediate dominators, and tree) information. 188// 189Pass *createBreakCriticalEdgesPass(); 190extern const PassInfo *BreakCriticalEdgesID; 191 192// The BreakCriticalEdges pass also exposes some low-level functionality that 193// may be used by other passes. 194 195/// isCriticalEdge - Return true if the specified edge is a critical edge. 196/// Critical edges are edges from a block with multiple successors to a block 197/// with multiple predecessors. 198/// 199bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum); 200 201/// SplitCriticalEdge - Insert a new node node to split the critical edge. This 202/// will update DominatorSet, ImmediateDominator and DominatorTree information 203/// if a pass is specified, thus calling this pass will not invalidate these 204/// analyses. 205/// 206void SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P = 0); 207 208//===----------------------------------------------------------------------===// 209// 210// LoopPreheaders pass - Insert Pre-header blocks into the CFG for every 211// function in the module. This pass updates dominator information, loop 212// information, and does not add critical edges to the CFG. 213// 214// AU.addRequiredID(LoopPreheadersID); 215// 216Pass *createLoopPreheaderInsertionPass(); 217extern const PassInfo *LoopPreheadersID; 218 219 220//===----------------------------------------------------------------------===// 221// These two passes convert malloc and free instructions to and from %malloc & 222// %free function calls. 223// 224Pass *createLowerAllocationsPass(); 225Pass *createRaiseAllocationsPass(); 226 227//===----------------------------------------------------------------------===// 228// This pass converts SwitchInst instructions into a sequence of chained binary 229// branch instructions. 230// 231Pass *createLowerSwitchPass(); 232 233//===----------------------------------------------------------------------===// 234// 235// These functions removes symbols from functions and modules. 236// 237Pass *createSymbolStrippingPass(); 238Pass *createFullSymbolStrippingPass(); 239 240#endif 241