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