Reassociate.cpp revision e408e25132b8de8c757db1e3ddcd70432dfeb24d
14fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 24fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 34fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// This pass reassociates commutative expressions in an order that is designed 44fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// to promote better constant propogation, GCSE, LICM, PRE... 54fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 64fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// For example: 4 + (x + 5) -> x + (4 + 5) 74fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 84fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// Note that this pass works best if left shifts have been promoted to explicit 94fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// multiplies before this pass executes. 104fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 114fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// In the implementation of this algorithm, constants are assigned rank = 0, 124fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// function arguments are rank = 1, and other values are assigned ranks 134fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// corresponding to the reverse post order traversal of current function 144fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// (starting at 2), which effectively gives values in deep loops higher rank 154fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// than values not in loops. 164fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner// 17e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner// This code was originally written by Chris Lattner, and was then cleaned up 18e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner// and perfected by Casey Carter. 19e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner// 204fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner//===----------------------------------------------------------------------===// 214fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 224fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Transforms/Scalar.h" 234fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Function.h" 244fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/iOperators.h" 254fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Type.h" 264fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Pass.h" 274fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Constant.h" 284fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "llvm/Support/CFG.h" 294fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner#include "Support/PostOrderIterator.h" 30a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner#include "Support/Statistic.h" 314fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 324fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnernamespace { 33a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumLinear ("reassociate","Number of insts linearized"); 34a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumChanged("reassociate","Number of insts reassociated"); 35a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner Statistic<> NumSwapped("reassociate","Number of insts with operands swapped"); 36a92f696b74a99325026ebbdbffd2a44317e0c10bChris Lattner 374fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner class Reassociate : public FunctionPass { 380c0edf8afc35a42b15a24ebb5fa5f3fc674290aeChris Lattner std::map<BasicBlock*, unsigned> RankMap; 394d0a82da2daab7bd4eb3b3cd7ea28ba15d0db144Chris Lattner std::map<Instruction*, unsigned> InstRankMap; 404fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner public: 417e70829632f82de15db187845666aaca6e04b792Chris Lattner bool runOnFunction(Function &F); 424fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 434fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 44cb2610ea037a17115ef3a01a6bdaab4e3cfdca27Chris Lattner AU.setPreservesCFG(); 454fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 464fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner private: 477e70829632f82de15db187845666aaca6e04b792Chris Lattner void BuildRankMap(Function &F); 484fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned getRank(Value *V); 494fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner bool ReassociateExpr(BinaryOperator *I); 504fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner bool ReassociateBB(BasicBlock *BB); 514fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner }; 52f629309f74cf1a64aa7fd1cd5784fd7db9a8f59eChris Lattner 53a6275ccdf5e1aa208afde56c498e2b13e16442f0Chris Lattner RegisterOpt<Reassociate> X("reassociate", "Reassociate expressions"); 544fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 554fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 564fd56003ab29e3662c909bb10e47daa97ceb55abChris LattnerPass *createReassociatePass() { return new Reassociate(); } 574fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 587e70829632f82de15db187845666aaca6e04b792Chris Lattnervoid Reassociate::BuildRankMap(Function &F) { 594fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned i = 1; 607e70829632f82de15db187845666aaca6e04b792Chris Lattner ReversePostOrderTraversal<Function*> RPOT(&F); 614fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 624fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner E = RPOT.end(); I != E; ++I) 634fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner RankMap[*I] = ++i; 644fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 654fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 664fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnerunsigned Reassociate::getRank(Value *V) { 674fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (isa<Argument>(V)) return 1; // Function argument... 684fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) { 694fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // If this is an expression, return the MAX(rank(LHS), rank(RHS)) so that we 704fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // can reassociate expressions for code motion! Since we do not recurse for 714fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // PHI nodes, we cannot have infinite recursion here, because there cannot 72680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner // be loops in the value graph that do not go through PHI nodes. 734fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // 744fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (I->getOpcode() == Instruction::PHINode || 754fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner I->getOpcode() == Instruction::Alloca || 764fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner I->getOpcode() == Instruction::Malloc || isa<TerminatorInst>(I) || 77f0a93ed9c59d706494496c6fe4e8354864d24aa7Chris Lattner I->mayWriteToMemory()) // Cannot move inst if it writes to memory! 784fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner return RankMap[I->getParent()]; 794fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 804d0a82da2daab7bd4eb3b3cd7ea28ba15d0db144Chris Lattner unsigned &CachedRank = InstRankMap[I]; 814d0a82da2daab7bd4eb3b3cd7ea28ba15d0db144Chris Lattner if (CachedRank) return CachedRank; // Rank already known? 824d0a82da2daab7bd4eb3b3cd7ea28ba15d0db144Chris Lattner 834d0a82da2daab7bd4eb3b3cd7ea28ba15d0db144Chris Lattner // If not, compute it! 84a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 85a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); 86a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner i != e && Rank != MaxRank; ++i) 874fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner Rank = std::max(Rank, getRank(I->getOperand(i))); 884fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 894d0a82da2daab7bd4eb3b3cd7ea28ba15d0db144Chris Lattner return CachedRank = Rank; 904fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 914fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 924fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Otherwise it's a global or constant, rank 0. 934fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner return 0; 944fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 954fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 964fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 974fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnerbool Reassociate::ReassociateExpr(BinaryOperator *I) { 984fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner Value *LHS = I->getOperand(0); 994fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner Value *RHS = I->getOperand(1); 1004fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned LHSRank = getRank(LHS); 1014fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned RHSRank = getRank(RHS); 1024fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1034fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner bool Changed = false; 1044fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1054fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Make sure the LHS of the operand always has the greater rank... 1064fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (LHSRank < RHSRank) { 107e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner bool Success = !I->swapOperands(); 108e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner assert(Success && "swapOperands failed"); 109e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 1104fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner std::swap(LHS, RHS); 1114fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner std::swap(LHSRank, RHSRank); 1124fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner Changed = true; 1133dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner ++NumSwapped; 114680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner DEBUG(std::cerr << "Transposed: " << I 115680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner /* << " Result BB: " << I->getParent()*/); 1164fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 1174fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1184fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // If the LHS is the same operator as the current one is, and if we are the 1194fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // only expression using it... 1204fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // 1214fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (BinaryOperator *LHSI = dyn_cast<BinaryOperator>(LHS)) 1224fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (LHSI->getOpcode() == I->getOpcode() && LHSI->use_size() == 1) { 1234fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // If the rank of our current RHS is less than the rank of the LHS's LHS, 1244fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // then we reassociate the two instructions... 1254fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (RHSRank < getRank(LHSI->getOperand(0))) { 1264fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner unsigned TakeOp = 0; 1274fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (BinaryOperator *IOp = dyn_cast<BinaryOperator>(LHSI->getOperand(0))) 1284fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner if (IOp->getOpcode() == LHSI->getOpcode()) 1294fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner TakeOp = 1; // Hoist out non-tree portion 1304fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1314fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Convert ((a + 12) + 10) into (a + (12 + 10)) 1324fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner I->setOperand(0, LHSI->getOperand(TakeOp)); 133680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner LHSI->setOperand(TakeOp, RHS); 134680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner I->setOperand(1, LHSI); 135e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 136e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // Move the LHS expression forward, to ensure that it is dominated by 137e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // its operands. 138680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner LHSI->getParent()->getInstList().remove(LHSI); 139680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner I->getParent()->getInstList().insert(I, LHSI); 1404fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1413dec1f272219ee1f8e1499929cdf53f5bc3c2272Chris Lattner ++NumChanged; 142680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner DEBUG(std::cerr << "Reassociated: " << I/* << " Result BB: " 143680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner << I->getParent()*/); 1444fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1454fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Since we modified the RHS instruction, make sure that we recheck it. 146680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner ReassociateExpr(LHSI); 1474fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner return true; 1484fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 1494fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 1504fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1514fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner return Changed; 1524fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 1534fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 1544fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 155a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// NegateValue - Insert instructions before the instruction pointed to by BI, 156a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that computes the negative version of the value specified. The negative 157a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// version of the value is returned, and BI is left pointing at the instruction 158a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// that should be processed next by the reassociation pass. 159a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner// 160e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattnerstatic Value *NegateValue(Value *V, BasicBlock::iterator &BI) { 161a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // We are trying to expose opportunity for reassociation. One of the things 162a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // that we want to do to achieve this is to push a negation as deep into an 163a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // expression chain as possible, to expose the add instructions. In practice, 164a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // this means that we turn this: 165a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 166a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 167a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // the constants. We assume that instcombine will clean up the mess later if 168a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // we introduce tons of unneccesary negation instructions... 169a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 170a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner if (Instruction *I = dyn_cast<Instruction>(V)) 171a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner if (I->getOpcode() == Instruction::Add && I->use_size() == 1) { 172e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner Value *RHS = NegateValue(I->getOperand(1), BI); 173e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner Value *LHS = NegateValue(I->getOperand(0), BI); 174a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 175a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // We must actually insert a new add instruction here, because the neg 176a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // instructions do not dominate the old add instruction in general. By 177a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // adding it now, we are assured that the neg instructions we just 178a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // inserted dominate the instruction we are about to insert after them. 179a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 1802a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner return BinaryOperator::create(Instruction::Add, LHS, RHS, 1812a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner I->getName()+".neg", 1822a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner cast<Instruction>(RHS)->getNext()); 183a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner } 184a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 185a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Insert a 'neg' instruction that subtracts the value from zero to get the 186a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // negation. 187a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 188e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner return BI = BinaryOperator::createNeg(V, V->getName() + ".neg", BI); 189a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner} 190a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 191a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 1924fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattnerbool Reassociate::ReassociateBB(BasicBlock *BB) { 1934fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner bool Changed = false; 1944fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) { 1954fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 196680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner DEBUG(std::cerr << "Processing: " << *BI); 197e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner if (BI->getOpcode() == Instruction::Sub && !BinaryOperator::isNeg(BI)) { 198e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // Convert a subtract into an add and a neg instruction... so that sub 199e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // instructions can be commuted with other add instructions... 200e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // 201e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // Calculate the negative value of Operand 1 of the sub instruction... 202e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // and set it as the RHS of the add instruction we just made... 203e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // 204e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner std::string Name = BI->getName(); 205e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner BI->setName(""); 206e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner Instruction *New = 207e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner BinaryOperator::create(Instruction::Add, BI->getOperand(0), 208e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner BI->getOperand(1), Name, BI); 209e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 210e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // Everyone now refers to the add instruction... 211e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner BI->replaceAllUsesWith(New); 212e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 213e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner // Put the new add in the place of the subtract... deleting the subtract 214e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner BB->getInstList().erase(BI); 215e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 216e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner BI = New; 217e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner New->setOperand(1, NegateValue(New->getOperand(1), BI)); 218e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 219e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner Changed = true; 220680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner DEBUG(std::cerr << "Negated: " << New /*<< " Result BB: " << BB*/); 221e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner } 222e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner 2234fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // If this instruction is a commutative binary operator, and the ranks of 2244fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // the two operands are sorted incorrectly, fix it now. 2254fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // 226e4b730441dab4aff9a69aeddbdea98990e7703c4Chris Lattner if (BI->isAssociative()) { 227e408e25132b8de8c757db1e3ddcd70432dfeb24dChris Lattner BinaryOperator *I = cast<BinaryOperator>(BI); 228a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner if (!I->use_empty()) { 229a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Make sure that we don't have a tree-shaped computation. If we do, 230a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // linearize it. Convert (A+B)+(C+D) into ((A+B)+C)+D 231a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 232a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner Instruction *LHSI = dyn_cast<Instruction>(I->getOperand(0)); 233a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner Instruction *RHSI = dyn_cast<Instruction>(I->getOperand(1)); 234a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner if (LHSI && (int)LHSI->getOpcode() == I->getOpcode() && 235a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner RHSI && (int)RHSI->getOpcode() == I->getOpcode() && 236a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner RHSI->use_size() == 1) { 237a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Insert a new temporary instruction... (A+B)+C 238a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner BinaryOperator *Tmp = BinaryOperator::create(I->getOpcode(), LHSI, 239a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner RHSI->getOperand(0), 2402a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner RHSI->getName()+".ra", 2412a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner BI); 2422a7c23ef9156a97f426a3fe8d1f5935b75d076d1Chris Lattner BI = Tmp; 243a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner I->setOperand(0, Tmp); 244a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner I->setOperand(1, RHSI->getOperand(1)); 245a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 246a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Process the temporary instruction for reassociation now. 247a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner I = Tmp; 248a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner ++NumLinear; 249a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner Changed = true; 250680f0c283d6faf15113687a6eb68482d231d1d91Chris Lattner DEBUG(std::cerr << "Linearized: " << I/* << " Result BB: " << BB*/); 251a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner } 252a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner 253a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // Make sure that this expression is correctly reassociated with respect 254a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // to it's used values... 255a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner // 256a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner Changed |= ReassociateExpr(I); 257a36e6c8cd58c2876decd2d0402064ac349bbec71Chris Lattner } 2584fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 2594fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner } 2604fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 2614fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner return Changed; 2624fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 2634fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 2644fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 2657e70829632f82de15db187845666aaca6e04b792Chris Lattnerbool Reassociate::runOnFunction(Function &F) { 2664fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // Recalculate the rank map for F 2674fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner BuildRankMap(F); 2684fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 2694fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner bool Changed = false; 2707e70829632f82de15db187845666aaca6e04b792Chris Lattner for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 2717e70829632f82de15db187845666aaca6e04b792Chris Lattner Changed |= ReassociateBB(FI); 2724fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner 2734fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner // We are done with the rank map... 2744fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner RankMap.clear(); 2754d0a82da2daab7bd4eb3b3cd7ea28ba15d0db144Chris Lattner InstRankMap.clear(); 2764fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner return Changed; 2774fd56003ab29e3662c909bb10e47daa97ceb55abChris Lattner} 278