Reassociate.cpp revision 3b237fcd385a734b49bb54893ce256ba181e36f9
1//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 2// 3// This pass reassociates commutative expressions in an order that is designed 4// to promote better constant propagation, GCSE, LICM, PRE... 5// 6// For example: 4 + (x + 5) -> x + (4 + 5) 7// 8// Note that this pass works best if left shifts have been promoted to explicit 9// multiplies before this pass executes. 10// 11// In the implementation of this algorithm, constants are assigned rank = 0, 12// function arguments are rank = 1, and other values are assigned ranks 13// corresponding to the reverse post order traversal of current function 14// (starting at 2), which effectively gives values in deep loops higher rank 15// than values not in loops. 16// 17//===----------------------------------------------------------------------===// 18 19#include "llvm/Transforms/Scalar.h" 20#include "llvm/Function.h" 21#include "llvm/iOperators.h" 22#include "llvm/Type.h" 23#include "llvm/Pass.h" 24#include "llvm/Constant.h" 25#include "llvm/Support/CFG.h" 26#include "Support/Debug.h" 27#include "Support/PostOrderIterator.h" 28#include "Support/Statistic.h" 29 30namespace { 31 Statistic<> NumLinear ("reassociate","Number of insts linearized"); 32 Statistic<> NumChanged("reassociate","Number of insts reassociated"); 33 Statistic<> NumSwapped("reassociate","Number of insts with operands swapped"); 34 35 class Reassociate : public FunctionPass { 36 std::map<BasicBlock*, unsigned> RankMap; 37 std::map<Value*, unsigned> ValueRankMap; 38 public: 39 bool runOnFunction(Function &F); 40 41 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 42 AU.setPreservesCFG(); 43 } 44 private: 45 void BuildRankMap(Function &F); 46 unsigned getRank(Value *V); 47 bool ReassociateExpr(BinaryOperator *I); 48 bool ReassociateBB(BasicBlock *BB); 49 }; 50 51 RegisterOpt<Reassociate> X("reassociate", "Reassociate expressions"); 52} 53 54Pass *createReassociatePass() { return new Reassociate(); } 55 56void Reassociate::BuildRankMap(Function &F) { 57 unsigned i = 2; 58 59 // Assign distinct ranks to function arguments 60 for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) 61 ValueRankMap[I] = ++i; 62 63 ReversePostOrderTraversal<Function*> RPOT(&F); 64 for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 65 E = RPOT.end(); I != E; ++I) 66 RankMap[*I] = ++i << 16; 67} 68 69unsigned Reassociate::getRank(Value *V) { 70 if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument... 71 72 if (Instruction *I = dyn_cast<Instruction>(V)) { 73 // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 74 // we can reassociate expressions for code motion! Since we do not recurse 75 // for PHI nodes, we cannot have infinite recursion here, because there 76 // cannot be loops in the value graph that do not go through PHI nodes. 77 // 78 if (I->getOpcode() == Instruction::PHI || 79 I->getOpcode() == Instruction::Alloca || 80 I->getOpcode() == Instruction::Malloc || isa<TerminatorInst>(I) || 81 I->mayWriteToMemory()) // Cannot move inst if it writes to memory! 82 return RankMap[I->getParent()]; 83 84 unsigned &CachedRank = ValueRankMap[I]; 85 if (CachedRank) return CachedRank; // Rank already known? 86 87 // If not, compute it! 88 unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 89 for (unsigned i = 0, e = I->getNumOperands(); 90 i != e && Rank != MaxRank; ++i) 91 Rank = std::max(Rank, getRank(I->getOperand(i))); 92 93 DEBUG(std::cerr << "Calculated Rank[" << V->getName() << "] = " 94 << Rank+1 << "\n"); 95 96 return CachedRank = Rank+1; 97 } 98 99 // Otherwise it's a global or constant, rank 0. 100 return 0; 101} 102 103 104bool Reassociate::ReassociateExpr(BinaryOperator *I) { 105 Value *LHS = I->getOperand(0); 106 Value *RHS = I->getOperand(1); 107 unsigned LHSRank = getRank(LHS); 108 unsigned RHSRank = getRank(RHS); 109 110 bool Changed = false; 111 112 // Make sure the LHS of the operand always has the greater rank... 113 if (LHSRank < RHSRank) { 114 bool Success = !I->swapOperands(); 115 assert(Success && "swapOperands failed"); 116 117 std::swap(LHS, RHS); 118 std::swap(LHSRank, RHSRank); 119 Changed = true; 120 ++NumSwapped; 121 DEBUG(std::cerr << "Transposed: " << I 122 /* << " Result BB: " << I->getParent()*/); 123 } 124 125 // If the LHS is the same operator as the current one is, and if we are the 126 // only expression using it... 127 // 128 if (BinaryOperator *LHSI = dyn_cast<BinaryOperator>(LHS)) 129 if (LHSI->getOpcode() == I->getOpcode() && LHSI->hasOneUse()) { 130 // If the rank of our current RHS is less than the rank of the LHS's LHS, 131 // then we reassociate the two instructions... 132 133 unsigned TakeOp = 0; 134 if (BinaryOperator *IOp = dyn_cast<BinaryOperator>(LHSI->getOperand(0))) 135 if (IOp->getOpcode() == LHSI->getOpcode()) 136 TakeOp = 1; // Hoist out non-tree portion 137 138 if (RHSRank < getRank(LHSI->getOperand(TakeOp))) { 139 // Convert ((a + 12) + 10) into (a + (12 + 10)) 140 I->setOperand(0, LHSI->getOperand(TakeOp)); 141 LHSI->setOperand(TakeOp, RHS); 142 I->setOperand(1, LHSI); 143 144 // Move the LHS expression forward, to ensure that it is dominated by 145 // its operands. 146 LHSI->getParent()->getInstList().remove(LHSI); 147 I->getParent()->getInstList().insert(I, LHSI); 148 149 ++NumChanged; 150 DEBUG(std::cerr << "Reassociated: " << I/* << " Result BB: " 151 << I->getParent()*/); 152 153 // Since we modified the RHS instruction, make sure that we recheck it. 154 ReassociateExpr(LHSI); 155 ReassociateExpr(I); 156 return true; 157 } 158 } 159 160 return Changed; 161} 162 163 164// NegateValue - Insert instructions before the instruction pointed to by BI, 165// that computes the negative version of the value specified. The negative 166// version of the value is returned, and BI is left pointing at the instruction 167// that should be processed next by the reassociation pass. 168// 169static Value *NegateValue(Value *V, BasicBlock::iterator &BI) { 170 // We are trying to expose opportunity for reassociation. One of the things 171 // that we want to do to achieve this is to push a negation as deep into an 172 // expression chain as possible, to expose the add instructions. In practice, 173 // this means that we turn this: 174 // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 175 // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 176 // the constants. We assume that instcombine will clean up the mess later if 177 // we introduce tons of unnecessary negation instructions... 178 // 179 if (Instruction *I = dyn_cast<Instruction>(V)) 180 if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 181 Value *RHS = NegateValue(I->getOperand(1), BI); 182 Value *LHS = NegateValue(I->getOperand(0), BI); 183 184 // We must actually insert a new add instruction here, because the neg 185 // instructions do not dominate the old add instruction in general. By 186 // adding it now, we are assured that the neg instructions we just 187 // inserted dominate the instruction we are about to insert after them. 188 // 189 return BinaryOperator::create(Instruction::Add, LHS, RHS, 190 I->getName()+".neg", 191 cast<Instruction>(RHS)->getNext()); 192 } 193 194 // Insert a 'neg' instruction that subtracts the value from zero to get the 195 // negation. 196 // 197 return BI = BinaryOperator::createNeg(V, V->getName() + ".neg", BI); 198} 199 200 201bool Reassociate::ReassociateBB(BasicBlock *BB) { 202 bool Changed = false; 203 for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) { 204 205 DEBUG(std::cerr << "Processing: " << *BI); 206 if (BI->getOpcode() == Instruction::Sub && !BinaryOperator::isNeg(BI)) { 207 // Convert a subtract into an add and a neg instruction... so that sub 208 // instructions can be commuted with other add instructions... 209 // 210 // Calculate the negative value of Operand 1 of the sub instruction... 211 // and set it as the RHS of the add instruction we just made... 212 // 213 std::string Name = BI->getName(); 214 BI->setName(""); 215 Instruction *New = 216 BinaryOperator::create(Instruction::Add, BI->getOperand(0), 217 BI->getOperand(1), Name, BI); 218 219 // Everyone now refers to the add instruction... 220 BI->replaceAllUsesWith(New); 221 222 // Put the new add in the place of the subtract... deleting the subtract 223 BB->getInstList().erase(BI); 224 225 BI = New; 226 New->setOperand(1, NegateValue(New->getOperand(1), BI)); 227 228 Changed = true; 229 DEBUG(std::cerr << "Negated: " << New /*<< " Result BB: " << BB*/); 230 } 231 232 // If this instruction is a commutative binary operator, and the ranks of 233 // the two operands are sorted incorrectly, fix it now. 234 // 235 if (BI->isAssociative()) { 236 BinaryOperator *I = cast<BinaryOperator>(BI); 237 if (!I->use_empty()) { 238 // Make sure that we don't have a tree-shaped computation. If we do, 239 // linearize it. Convert (A+B)+(C+D) into ((A+B)+C)+D 240 // 241 Instruction *LHSI = dyn_cast<Instruction>(I->getOperand(0)); 242 Instruction *RHSI = dyn_cast<Instruction>(I->getOperand(1)); 243 if (LHSI && (int)LHSI->getOpcode() == I->getOpcode() && 244 RHSI && (int)RHSI->getOpcode() == I->getOpcode() && 245 RHSI->hasOneUse()) { 246 // Insert a new temporary instruction... (A+B)+C 247 BinaryOperator *Tmp = BinaryOperator::create(I->getOpcode(), LHSI, 248 RHSI->getOperand(0), 249 RHSI->getName()+".ra", 250 BI); 251 BI = Tmp; 252 I->setOperand(0, Tmp); 253 I->setOperand(1, RHSI->getOperand(1)); 254 255 // Process the temporary instruction for reassociation now. 256 I = Tmp; 257 ++NumLinear; 258 Changed = true; 259 DEBUG(std::cerr << "Linearized: " << I/* << " Result BB: " << BB*/); 260 } 261 262 // Make sure that this expression is correctly reassociated with respect 263 // to it's used values... 264 // 265 Changed |= ReassociateExpr(I); 266 } 267 } 268 } 269 270 return Changed; 271} 272 273 274bool Reassociate::runOnFunction(Function &F) { 275 // Recalculate the rank map for F 276 BuildRankMap(F); 277 278 bool Changed = false; 279 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 280 Changed |= ReassociateBB(FI); 281 282 // We are done with the rank map... 283 RankMap.clear(); 284 ValueRankMap.clear(); 285 return Changed; 286} 287