1 //===- NaryReassociate.h - Reassociate n-ary expressions --------*- 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 pass reassociates n-ary add expressions and eliminates the redundancy 11 // exposed by the reassociation. 12 // 13 // A motivating example: 14 // 15 // void foo(int a, int b) { 16 // bar(a + b); 17 // bar((a + 2) + b); 18 // } 19 // 20 // An ideal compiler should reassociate (a + 2) + b to (a + b) + 2 and simplify 21 // the above code to 22 // 23 // int t = a + b; 24 // bar(t); 25 // bar(t + 2); 26 // 27 // However, the Reassociate pass is unable to do that because it processes each 28 // instruction individually and believes (a + 2) + b is the best form according 29 // to its rank system. 30 // 31 // To address this limitation, NaryReassociate reassociates an expression in a 32 // form that reuses existing instructions. As a result, NaryReassociate can 33 // reassociate (a + 2) + b in the example to (a + b) + 2 because it detects that 34 // (a + b) is computed before. 35 // 36 // NaryReassociate works as follows. For every instruction in the form of (a + 37 // b) + c, it checks whether a + c or b + c is already computed by a dominating 38 // instruction. If so, it then reassociates (a + b) + c into (a + c) + b or (b + 39 // c) + a and removes the redundancy accordingly. To efficiently look up whether 40 // an expression is computed before, we store each instruction seen and its SCEV 41 // into an SCEV-to-instruction map. 42 // 43 // Although the algorithm pattern-matches only ternary additions, it 44 // automatically handles many >3-ary expressions by walking through the function 45 // in the depth-first order. For example, given 46 // 47 // (a + c) + d 48 // ((a + b) + c) + d 49 // 50 // NaryReassociate first rewrites (a + b) + c to (a + c) + b, and then rewrites 51 // ((a + c) + b) + d into ((a + c) + d) + b. 52 // 53 // Finally, the above dominator-based algorithm may need to be run multiple 54 // iterations before emitting optimal code. One source of this need is that we 55 // only split an operand when it is used only once. The above algorithm can 56 // eliminate an instruction and decrease the usage count of its operands. As a 57 // result, an instruction that previously had multiple uses may become a 58 // single-use instruction and thus eligible for split consideration. For 59 // example, 60 // 61 // ac = a + c 62 // ab = a + b 63 // abc = ab + c 64 // ab2 = ab + b 65 // ab2c = ab2 + c 66 // 67 // In the first iteration, we cannot reassociate abc to ac+b because ab is used 68 // twice. However, we can reassociate ab2c to abc+b in the first iteration. As a 69 // result, ab2 becomes dead and ab will be used only once in the second 70 // iteration. 71 // 72 // Limitations and TODO items: 73 // 74 // 1) We only considers n-ary adds and muls for now. This should be extended 75 // and generalized. 76 // 77 //===----------------------------------------------------------------------===// 78 79 #ifndef LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H 80 #define LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H 81 82 #include "llvm/ADT/DenseMap.h" 83 #include "llvm/ADT/SmallVector.h" 84 #include "llvm/IR/PassManager.h" 85 #include "llvm/IR/ValueHandle.h" 86 87 namespace llvm { 88 89 class AssumptionCache; 90 class BinaryOperator; 91 class DataLayout; 92 class DominatorTree; 93 class Function; 94 class GetElementPtrInst; 95 class Instruction; 96 class ScalarEvolution; 97 class SCEV; 98 class TargetLibraryInfo; 99 class TargetTransformInfo; 100 class Type; 101 class Value; 102 103 class NaryReassociatePass : public PassInfoMixin<NaryReassociatePass> { 104 public: 105 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 106 107 // Glue for old PM. 108 bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_, 109 ScalarEvolution *SE_, TargetLibraryInfo *TLI_, 110 TargetTransformInfo *TTI_); 111 112 private: 113 // Runs only one iteration of the dominator-based algorithm. See the header 114 // comments for why we need multiple iterations. 115 bool doOneIteration(Function &F); 116 117 // Reassociates I for better CSE. 118 Instruction *tryReassociate(Instruction *I); 119 120 // Reassociate GEP for better CSE. 121 Instruction *tryReassociateGEP(GetElementPtrInst *GEP); 122 123 // Try splitting GEP at the I-th index and see whether either part can be 124 // CSE'ed. This is a helper function for tryReassociateGEP. 125 // 126 // \p IndexedType The element type indexed by GEP's I-th index. This is 127 // equivalent to 128 // GEP->getIndexedType(GEP->getPointerOperand(), 0-th index, 129 // ..., i-th index). 130 GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP, 131 unsigned I, Type *IndexedType); 132 133 // Given GEP's I-th index = LHS + RHS, see whether &Base[..][LHS][..] or 134 // &Base[..][RHS][..] can be CSE'ed and rewrite GEP accordingly. 135 GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP, 136 unsigned I, Value *LHS, 137 Value *RHS, Type *IndexedType); 138 139 // Reassociate binary operators for better CSE. 140 Instruction *tryReassociateBinaryOp(BinaryOperator *I); 141 142 // A helper function for tryReassociateBinaryOp. LHS and RHS are explicitly 143 // passed. 144 Instruction *tryReassociateBinaryOp(Value *LHS, Value *RHS, 145 BinaryOperator *I); 146 // Rewrites I to (LHS op RHS) if LHS is computed already. 147 Instruction *tryReassociatedBinaryOp(const SCEV *LHS, Value *RHS, 148 BinaryOperator *I); 149 150 // Tries to match Op1 and Op2 by using V. 151 bool matchTernaryOp(BinaryOperator *I, Value *V, Value *&Op1, Value *&Op2); 152 153 // Gets SCEV for (LHS op RHS). 154 const SCEV *getBinarySCEV(BinaryOperator *I, const SCEV *LHS, 155 const SCEV *RHS); 156 157 // Returns the closest dominator of \c Dominatee that computes 158 // \c CandidateExpr. Returns null if not found. 159 Instruction *findClosestMatchingDominator(const SCEV *CandidateExpr, 160 Instruction *Dominatee); 161 162 // GetElementPtrInst implicitly sign-extends an index if the index is shorter 163 // than the pointer size. This function returns whether Index is shorter than 164 // GEP's pointer size, i.e., whether Index needs to be sign-extended in order 165 // to be an index of GEP. 166 bool requiresSignExtension(Value *Index, GetElementPtrInst *GEP); 167 168 AssumptionCache *AC; 169 const DataLayout *DL; 170 DominatorTree *DT; 171 ScalarEvolution *SE; 172 TargetLibraryInfo *TLI; 173 TargetTransformInfo *TTI; 174 175 // A lookup table quickly telling which instructions compute the given SCEV. 176 // Note that there can be multiple instructions at different locations 177 // computing to the same SCEV, so we map a SCEV to an instruction list. For 178 // example, 179 // 180 // if (p1) 181 // foo(a + b); 182 // if (p2) 183 // bar(a + b); 184 DenseMap<const SCEV *, SmallVector<WeakTrackingVH, 2>> SeenExprs; 185 }; 186 187 } // end namespace llvm 188 189 #endif // LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H 190
