LLVM API Documentation
00001 //===- Reassociate.cpp - Reassociate binary expressions -------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass reassociates commutative expressions in an order that is designed 00011 // to promote better constant propagation, GCSE, LICM, PRE... 00012 // 00013 // For example: 4 + (x + 5) -> x + (4 + 5) 00014 // 00015 // Note that this pass works best if left shifts have been promoted to explicit 00016 // multiplies before this pass executes. 00017 // 00018 // In the implementation of this algorithm, constants are assigned rank = 0, 00019 // function arguments are rank = 1, and other values are assigned ranks 00020 // corresponding to the reverse post order traversal of current function 00021 // (starting at 2), which effectively gives values in deep loops higher rank 00022 // than values not in loops. 00023 // 00024 //===----------------------------------------------------------------------===// 00025 00026 #include "llvm/Transforms/Scalar.h" 00027 #include "llvm/Function.h" 00028 #include "llvm/Instructions.h" 00029 #include "llvm/Type.h" 00030 #include "llvm/Pass.h" 00031 #include "llvm/Constant.h" 00032 #include "llvm/Support/CFG.h" 00033 #include "llvm/Support/Debug.h" 00034 #include "llvm/ADT/PostOrderIterator.h" 00035 #include "llvm/ADT/Statistic.h" 00036 using namespace llvm; 00037 00038 namespace { 00039 Statistic<> NumLinear ("reassociate","Number of insts linearized"); 00040 Statistic<> NumChanged("reassociate","Number of insts reassociated"); 00041 Statistic<> NumSwapped("reassociate","Number of insts with operands swapped"); 00042 00043 class Reassociate : public FunctionPass { 00044 std::map<BasicBlock*, unsigned> RankMap; 00045 std::map<Value*, unsigned> ValueRankMap; 00046 public: 00047 bool runOnFunction(Function &F); 00048 00049 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00050 AU.setPreservesCFG(); 00051 } 00052 private: 00053 void BuildRankMap(Function &F); 00054 unsigned getRank(Value *V); 00055 bool ReassociateExpr(BinaryOperator *I); 00056 bool ReassociateBB(BasicBlock *BB); 00057 }; 00058 00059 RegisterOpt<Reassociate> X("reassociate", "Reassociate expressions"); 00060 } 00061 00062 // Public interface to the Reassociate pass 00063 FunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 00064 00065 void Reassociate::BuildRankMap(Function &F) { 00066 unsigned i = 2; 00067 00068 // Assign distinct ranks to function arguments 00069 for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) 00070 ValueRankMap[I] = ++i; 00071 00072 ReversePostOrderTraversal<Function*> RPOT(&F); 00073 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 00074 E = RPOT.end(); I != E; ++I) 00075 RankMap[*I] = ++i << 16; 00076 } 00077 00078 unsigned Reassociate::getRank(Value *V) { 00079 if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument... 00080 00081 if (Instruction *I = dyn_cast<Instruction>(V)) { 00082 // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 00083 // we can reassociate expressions for code motion! Since we do not recurse 00084 // for PHI nodes, we cannot have infinite recursion here, because there 00085 // cannot be loops in the value graph that do not go through PHI nodes. 00086 // 00087 if (I->getOpcode() == Instruction::PHI || 00088 I->getOpcode() == Instruction::Alloca || 00089 I->getOpcode() == Instruction::Malloc || isa<TerminatorInst>(I) || 00090 I->mayWriteToMemory()) // Cannot move inst if it writes to memory! 00091 return RankMap[I->getParent()]; 00092 00093 unsigned &CachedRank = ValueRankMap[I]; 00094 if (CachedRank) return CachedRank; // Rank already known? 00095 00096 // If not, compute it! 00097 unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 00098 for (unsigned i = 0, e = I->getNumOperands(); 00099 i != e && Rank != MaxRank; ++i) 00100 Rank = std::max(Rank, getRank(I->getOperand(i))); 00101 00102 DEBUG(std::cerr << "Calculated Rank[" << V->getName() << "] = " 00103 << Rank+1 << "\n"); 00104 00105 return CachedRank = Rank+1; 00106 } 00107 00108 // Otherwise it's a global or constant, rank 0. 00109 return 0; 00110 } 00111 00112 00113 bool Reassociate::ReassociateExpr(BinaryOperator *I) { 00114 Value *LHS = I->getOperand(0); 00115 Value *RHS = I->getOperand(1); 00116 unsigned LHSRank = getRank(LHS); 00117 unsigned RHSRank = getRank(RHS); 00118 00119 bool Changed = false; 00120 00121 // Make sure the LHS of the operand always has the greater rank... 00122 if (LHSRank < RHSRank) { 00123 bool Success = !I->swapOperands(); 00124 assert(Success && "swapOperands failed"); 00125 00126 std::swap(LHS, RHS); 00127 std::swap(LHSRank, RHSRank); 00128 Changed = true; 00129 ++NumSwapped; 00130 DEBUG(std::cerr << "Transposed: " << *I 00131 /* << " Result BB: " << I->getParent()*/); 00132 } 00133 00134 // If the LHS is the same operator as the current one is, and if we are the 00135 // only expression using it... 00136 // 00137 if (BinaryOperator *LHSI = dyn_cast<BinaryOperator>(LHS)) 00138 if (LHSI->getOpcode() == I->getOpcode() && LHSI->hasOneUse()) { 00139 // If the rank of our current RHS is less than the rank of the LHS's LHS, 00140 // then we reassociate the two instructions... 00141 00142 unsigned TakeOp = 0; 00143 if (BinaryOperator *IOp = dyn_cast<BinaryOperator>(LHSI->getOperand(0))) 00144 if (IOp->getOpcode() == LHSI->getOpcode()) 00145 TakeOp = 1; // Hoist out non-tree portion 00146 00147 if (RHSRank < getRank(LHSI->getOperand(TakeOp))) { 00148 // Convert ((a + 12) + 10) into (a + (12 + 10)) 00149 I->setOperand(0, LHSI->getOperand(TakeOp)); 00150 LHSI->setOperand(TakeOp, RHS); 00151 I->setOperand(1, LHSI); 00152 00153 // Move the LHS expression forward, to ensure that it is dominated by 00154 // its operands. 00155 LHSI->getParent()->getInstList().remove(LHSI); 00156 I->getParent()->getInstList().insert(I, LHSI); 00157 00158 ++NumChanged; 00159 DEBUG(std::cerr << "Reassociated: " << *I/* << " Result BB: " 00160 << I->getParent()*/); 00161 00162 // Since we modified the RHS instruction, make sure that we recheck it. 00163 ReassociateExpr(LHSI); 00164 ReassociateExpr(I); 00165 return true; 00166 } 00167 } 00168 00169 return Changed; 00170 } 00171 00172 00173 // NegateValue - Insert instructions before the instruction pointed to by BI, 00174 // that computes the negative version of the value specified. The negative 00175 // version of the value is returned, and BI is left pointing at the instruction 00176 // that should be processed next by the reassociation pass. 00177 // 00178 static Value *NegateValue(Value *V, BasicBlock::iterator &BI) { 00179 // We are trying to expose opportunity for reassociation. One of the things 00180 // that we want to do to achieve this is to push a negation as deep into an 00181 // expression chain as possible, to expose the add instructions. In practice, 00182 // this means that we turn this: 00183 // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 00184 // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 00185 // the constants. We assume that instcombine will clean up the mess later if 00186 // we introduce tons of unnecessary negation instructions... 00187 // 00188 if (Instruction *I = dyn_cast<Instruction>(V)) 00189 if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 00190 Value *RHS = NegateValue(I->getOperand(1), BI); 00191 Value *LHS = NegateValue(I->getOperand(0), BI); 00192 00193 // We must actually insert a new add instruction here, because the neg 00194 // instructions do not dominate the old add instruction in general. By 00195 // adding it now, we are assured that the neg instructions we just 00196 // inserted dominate the instruction we are about to insert after them. 00197 // 00198 return BinaryOperator::create(Instruction::Add, LHS, RHS, 00199 I->getName()+".neg", 00200 cast<Instruction>(RHS)->getNext()); 00201 } 00202 00203 // Insert a 'neg' instruction that subtracts the value from zero to get the 00204 // negation. 00205 // 00206 return BI = BinaryOperator::createNeg(V, V->getName() + ".neg", BI); 00207 } 00208 00209 00210 bool Reassociate::ReassociateBB(BasicBlock *BB) { 00211 bool Changed = false; 00212 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) { 00213 00214 DEBUG(std::cerr << "Reassociating: " << *BI); 00215 if (BI->getOpcode() == Instruction::Sub && !BinaryOperator::isNeg(BI)) { 00216 // Convert a subtract into an add and a neg instruction... so that sub 00217 // instructions can be commuted with other add instructions... 00218 // 00219 // Calculate the negative value of Operand 1 of the sub instruction... 00220 // and set it as the RHS of the add instruction we just made... 00221 // 00222 std::string Name = BI->getName(); 00223 BI->setName(""); 00224 Instruction *New = 00225 BinaryOperator::create(Instruction::Add, BI->getOperand(0), 00226 BI->getOperand(1), Name, BI); 00227 00228 // Everyone now refers to the add instruction... 00229 BI->replaceAllUsesWith(New); 00230 00231 // Put the new add in the place of the subtract... deleting the subtract 00232 BB->getInstList().erase(BI); 00233 00234 BI = New; 00235 New->setOperand(1, NegateValue(New->getOperand(1), BI)); 00236 00237 Changed = true; 00238 DEBUG(std::cerr << "Negated: " << *New /*<< " Result BB: " << BB*/); 00239 } 00240 00241 // If this instruction is a commutative binary operator, and the ranks of 00242 // the two operands are sorted incorrectly, fix it now. 00243 // 00244 if (BI->isAssociative()) { 00245 BinaryOperator *I = cast<BinaryOperator>(BI); 00246 if (!I->use_empty()) { 00247 // Make sure that we don't have a tree-shaped computation. If we do, 00248 // linearize it. Convert (A+B)+(C+D) into ((A+B)+C)+D 00249 // 00250 Instruction *LHSI = dyn_cast<Instruction>(I->getOperand(0)); 00251 Instruction *RHSI = dyn_cast<Instruction>(I->getOperand(1)); 00252 if (LHSI && (int)LHSI->getOpcode() == I->getOpcode() && 00253 RHSI && (int)RHSI->getOpcode() == I->getOpcode() && 00254 RHSI->hasOneUse()) { 00255 // Insert a new temporary instruction... (A+B)+C 00256 BinaryOperator *Tmp = BinaryOperator::create(I->getOpcode(), LHSI, 00257 RHSI->getOperand(0), 00258 RHSI->getName()+".ra", 00259 BI); 00260 BI = Tmp; 00261 I->setOperand(0, Tmp); 00262 I->setOperand(1, RHSI->getOperand(1)); 00263 00264 // Process the temporary instruction for reassociation now. 00265 I = Tmp; 00266 ++NumLinear; 00267 Changed = true; 00268 DEBUG(std::cerr << "Linearized: " << *I/* << " Result BB: " << BB*/); 00269 } 00270 00271 // Make sure that this expression is correctly reassociated with respect 00272 // to it's used values... 00273 // 00274 Changed |= ReassociateExpr(I); 00275 } 00276 } 00277 } 00278 00279 return Changed; 00280 } 00281 00282 00283 bool Reassociate::runOnFunction(Function &F) { 00284 // Recalculate the rank map for F 00285 BuildRankMap(F); 00286 00287 bool Changed = false; 00288 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 00289 Changed |= ReassociateBB(FI); 00290 00291 // We are done with the rank map... 00292 RankMap.clear(); 00293 ValueRankMap.clear(); 00294 return Changed; 00295 } 00296