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