Reassociate.cpp revision fd05924946ebfcfb3409b21996cfd0836e4ddb31
1f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 2f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// 3f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// This pass reassociates commutative expressions in an order that is designed 4f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// to promote better constant propagation, GCSE, LICM, PRE... 5f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// 6f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// For example: 4 + (x + 5) -> x + (4 + 5) 7f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// 8f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// Note that this pass works best if left shifts have been promoted to explicit 9f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// multiplies before this pass executes. 10f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// 11f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// In the implementation of this algorithm, constants are assigned rank = 0, 12f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// function arguments are rank = 1, and other values are assigned ranks 13f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// corresponding to the reverse post order traversal of current function 14f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// (starting at 2), which effectively gives values in deep loops higher rank 15f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// than values not in loops. 16f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn// 17f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn//===----------------------------------------------------------------------===// 18f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 19f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn#include "llvm/Transforms/Scalar.h" 2021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn#include "llvm/Function.h" 21f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn#include "llvm/iOperators.h" 22f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn#include "llvm/Type.h" 23f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn#include "llvm/Pass.h" 24f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn#include "llvm/Constant.h" 2521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn#include "llvm/Support/CFG.h" 26f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn#include "Support/Debug.h" 27f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn#include "Support/PostOrderIterator.h" 28f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn#include "Support/Statistic.h" 29f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 30f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornnamespace { 31f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Statistic<> NumLinear ("reassociate","Number of insts linearized"); 32f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Statistic<> NumChanged("reassociate","Number of insts reassociated"); 33f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Statistic<> NumSwapped("reassociate","Number of insts with operands swapped"); 34f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 35f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn class Reassociate : public FunctionPass { 36f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn std::map<BasicBlock*, unsigned> RankMap; 37f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn std::map<Value*, unsigned> ValueRankMap; 38f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn public: 39f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn bool runOnFunction(Function &F); 40f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 41f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn virtual void getAnalysisUsage(AnalysisUsage &AU) const { 42f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn AU.setPreservesCFG(); 43f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 44f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn private: 45f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn void BuildRankMap(Function &F); 46f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn unsigned getRank(Value *V); 47f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn bool ReassociateExpr(BinaryOperator *I); 48f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn bool ReassociateBB(BasicBlock *BB); 49f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn }; 50f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 5162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn RegisterOpt<Reassociate> X("reassociate", "Reassociate expressions"); 52f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 5362d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 54f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne HackbornPass *createReassociatePass() { return new Reassociate(); } 55f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 56f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornvoid Reassociate::BuildRankMap(Function &F) { 57f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn unsigned i = 2; 58f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 5962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn // Assign distinct ranks to function arguments 60f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I) 6162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn ValueRankMap[I] = ++i; 62f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 63f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ReversePostOrderTraversal<Function*> RPOT(&F); 64f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 65f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn E = RPOT.end(); I != E; ++I) 66f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn RankMap[*I] = ++i << 16; 67f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 68f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 69f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornunsigned Reassociate::getRank(Value *V) { 70f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument... 71f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 72f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (Instruction *I = dyn_cast<Instruction>(V)) { 73f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 74f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // we can reassociate expressions for code motion! Since we do not recurse 75f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // for PHI nodes, we cannot have infinite recursion here, because there 76f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // cannot be loops in the value graph that do not go through PHI nodes. 77f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // 78f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (I->getOpcode() == Instruction::PHINode || 7962d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn I->getOpcode() == Instruction::Alloca || 80f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn I->getOpcode() == Instruction::Malloc || isa<TerminatorInst>(I) || 8162d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn I->mayWriteToMemory()) // Cannot move inst if it writes to memory! 82f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return RankMap[I->getParent()]; 83f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 84f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn unsigned &CachedRank = ValueRankMap[I]; 85f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (CachedRank) return CachedRank; // Rank already known? 86f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 87f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If not, compute it! 88f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 89f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (unsigned i = 0, e = I->getNumOperands(); 90f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn i != e && Rank != MaxRank; ++i) 91f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Rank = std::max(Rank, getRank(I->getOperand(i))); 92f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 93f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn DEBUG(std::cerr << "Calculated Rank[" << V->getName() << "] = " 9462d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn << Rank+1 << "\n"); 9562d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn 9662d708f4dd8e2a8554df4967837df9896efeff7cDianne Hackborn return CachedRank = Rank+1; 97f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 98f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 99f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Otherwise it's a global or constant, rank 0. 100f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return 0; 101f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 102f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 103f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 104f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornbool Reassociate::ReassociateExpr(BinaryOperator *I) { 105f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Value *LHS = I->getOperand(0); 106f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Value *RHS = I->getOperand(1); 107f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn unsigned LHSRank = getRank(LHS); 108f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn unsigned RHSRank = getRank(RHS); 109f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 110f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn bool Changed = false; 111f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 112f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Make sure the LHS of the operand always has the greater rank... 113f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (LHSRank < RHSRank) { 114f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn bool Success = !I->swapOperands(); 115f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn assert(Success && "swapOperands failed"); 116f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 117f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn std::swap(LHS, RHS); 118f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn std::swap(LHSRank, RHSRank); 119f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Changed = true; 120f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ++NumSwapped; 121f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn DEBUG(std::cerr << "Transposed: " << I 122f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn /* << " Result BB: " << I->getParent()*/); 123f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 124f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 125f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If the LHS is the same operator as the current one is, and if we are the 126f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // only expression using it... 127f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // 128f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (BinaryOperator *LHSI = dyn_cast<BinaryOperator>(LHS)) 129f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (LHSI->getOpcode() == I->getOpcode() && LHSI->hasOneUse()) { 130f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // If the rank of our current RHS is less than the rank of the LHS's LHS, 131f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // then we reassociate the two instructions... 132f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 133f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn unsigned TakeOp = 0; 134f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (BinaryOperator *IOp = dyn_cast<BinaryOperator>(LHSI->getOperand(0))) 135f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (IOp->getOpcode() == LHSI->getOpcode()) 136f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn TakeOp = 1; // Hoist out non-tree portion 137f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 138f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (RHSRank < getRank(LHSI->getOperand(TakeOp))) { 139f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Convert ((a + 12) + 10) into (a + (12 + 10)) 140f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn I->setOperand(0, LHSI->getOperand(TakeOp)); 141f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn LHSI->setOperand(TakeOp, RHS); 142f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn I->setOperand(1, LHSI); 143f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 144f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Move the LHS expression forward, to ensure that it is dominated by 145f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // its operands. 146f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn LHSI->getParent()->getInstList().remove(LHSI); 147f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn I->getParent()->getInstList().insert(I, LHSI); 148f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 1498b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn ++NumChanged; 1508b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn DEBUG(std::cerr << "Reassociated: " << I/* << " Result BB: " 1518b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn << I->getParent()*/); 1528b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 1538b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // Since we modified the RHS instruction, make sure that we recheck it. 1548b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn ReassociateExpr(LHSI); 1558b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn ReassociateExpr(I); 1568b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn return true; 1578b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn } 1588b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn } 1598b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 1608b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn return Changed; 1618b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn} 1628b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 1638b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 1648b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn// NegateValue - Insert instructions before the instruction pointed to by BI, 1658b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn// that computes the negative version of the value specified. The negative 1668b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn// version of the value is returned, and BI is left pointing at the instruction 1678b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn// that should be processed next by the reassociation pass. 1688b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn// 1698b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackbornstatic Value *NegateValue(Value *V, BasicBlock::iterator &BI) { 1708b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // We are trying to expose opportunity for reassociation. One of the things 1718b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // that we want to do to achieve this is to push a negation as deep into an 1728b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // expression chain as possible, to expose the add instructions. In practice, 1738b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // this means that we turn this: 1748b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 1758b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 1768b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // the constants. We assume that instcombine will clean up the mess later if 1778b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // we introduce tons of unnecessary negation instructions... 1788b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // 1798b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn if (Instruction *I = dyn_cast<Instruction>(V)) 1808b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 1818b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn Value *RHS = NegateValue(I->getOperand(1), BI); 1828b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn Value *LHS = NegateValue(I->getOperand(0), BI); 1838b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 1848b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // We must actually insert a new add instruction here, because the neg 1858b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // instructions do not dominate the old add instruction in general. By 1868b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // adding it now, we are assured that the neg instructions we just 1878b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // inserted dominate the instruction we are about to insert after them. 1888b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // 1898b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn return BinaryOperator::create(Instruction::Add, LHS, RHS, 1908b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn I->getName()+".neg", 1918b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn cast<Instruction>(RHS)->getNext()); 1928b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn } 1938b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 1948b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // Insert a 'neg' instruction that subtracts the value from zero to get the 1958b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // negation. 1968b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // 1978b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn return BI = BinaryOperator::createNeg(V, V->getName() + ".neg", BI); 1988b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn} 1998b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 2008b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 2018b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackbornbool Reassociate::ReassociateBB(BasicBlock *BB) { 2028b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn bool Changed = false; 2038b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn for (BasicBlock::iterator BI = BB->begin(); BI != BB->end(); ++BI) { 2048b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn 2058b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn DEBUG(std::cerr << "Processing: " << *BI); 2068b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn if (BI->getOpcode() == Instruction::Sub && !BinaryOperator::isNeg(BI)) { 2078b7bc13e217034e0ddd00f9033463190f50dce88Dianne Hackborn // Convert a subtract into an add and a neg instruction... so that sub 20821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // instructions can be commuted with other add instructions... 20921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // 21021ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Calculate the negative value of Operand 1 of the sub instruction... 21121ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // and set it as the RHS of the add instruction we just made... 21221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // 21321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn std::string Name = BI->getName(); 21421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn BI->setName(""); 21521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn Instruction *New = 21621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn BinaryOperator::create(Instruction::Add, BI->getOperand(0), 21721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn BI->getOperand(1), Name, BI); 21821ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 21921ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Everyone now refers to the add instruction... 220f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn BI->replaceAllUsesWith(New); 221f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 222f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Put the new add in the place of the subtract... deleting the subtract 223f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn BB->getInstList().erase(BI); 22421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 22521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn BI = New; 22621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn New->setOperand(1, NegateValue(New->getOperand(1), BI)); 22721ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn 228f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Changed = true; 229f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn DEBUG(std::cerr << "Negated: " << New /*<< " Result BB: " << BB*/); 230f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 231f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 23221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // If this instruction is a commutative binary operator, and the ranks of 23321ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // the two operands are sorted incorrectly, fix it now. 23421ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // 23521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn if (BI->isAssociative()) { 23621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn BinaryOperator *I = cast<BinaryOperator>(BI); 237f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (!I->use_empty()) { 238f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Make sure that we don't have a tree-shaped computation. If we do, 239f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // linearize it. Convert (A+B)+(C+D) into ((A+B)+C)+D 240f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // 241f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Instruction *LHSI = dyn_cast<Instruction>(I->getOperand(0)); 242f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Instruction *RHSI = dyn_cast<Instruction>(I->getOperand(1)); 243f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn if (LHSI && (int)LHSI->getOpcode() == I->getOpcode() && 244f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn RHSI && (int)RHSI->getOpcode() == I->getOpcode() && 245f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn RHSI->hasOneUse()) { 246f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Insert a new temporary instruction... (A+B)+C 247f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn BinaryOperator *Tmp = BinaryOperator::create(I->getOpcode(), LHSI, 248f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn RHSI->getOperand(0), 249f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn RHSI->getName()+".ra", 250f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn BI); 251f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn BI = Tmp; 252f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn I->setOperand(0, Tmp); 253f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn I->setOperand(1, RHSI->getOperand(1)); 254f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 25521ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Process the temporary instruction for reassociation now. 256f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn I = Tmp; 257f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ++NumLinear; 258f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Changed = true; 259f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn DEBUG(std::cerr << "Linearized: " << I/* << " Result BB: " << BB*/); 260f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 261f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 26221ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn // Make sure that this expression is correctly reassociated with respect 263f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // to it's used values... 264f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // 265f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Changed |= ReassociateExpr(I); 266f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 267f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 268f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn } 269f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 270f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return Changed; 271f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 272f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 273f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 274f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackbornbool Reassociate::runOnFunction(Function &F) { 275f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // Recalculate the rank map for F 27621ab6f49910a6f319bc7b9d3964086cb1ffe09d0Dianne Hackborn BuildRankMap(F); 277f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 278f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn bool Changed = false; 279f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 280f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn Changed |= ReassociateBB(FI); 281f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn 282f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn // We are done with the rank map... 283f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn RankMap.clear(); 284f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn ValueRankMap.clear(); 285f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn return Changed; 286f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn} 287f4bf0ae2a7c2d9d92c5c8abdb82baa53b4c9ccdaDianne Hackborn