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