Reassociate.cpp revision 201360
142660Smarkm//===- Reassociate.cpp - Reassociate binary expressions -------------------===// 242660Smarkm// 321495Sjmacd// The LLVM Compiler Infrastructure 442660Smarkm// 521495Sjmacd// This file is distributed under the University of Illinois Open Source 621495Sjmacd// License. See LICENSE.TXT for details. 721495Sjmacd// 821495Sjmacd//===----------------------------------------------------------------------===// 921495Sjmacd// 1021495Sjmacd// This pass reassociates commutative expressions in an order that is designed 1121495Sjmacd// to promote better constant propagation, GCSE, LICM, PRE, etc. 1221495Sjmacd// 1321495Sjmacd// For example: 4 + (x + 5) -> x + (4 + 5) 1421495Sjmacd// 1521495Sjmacd// In the implementation of this algorithm, constants are assigned rank = 0, 1621495Sjmacd// function arguments are rank = 1, and other values are assigned ranks 1721495Sjmacd// corresponding to the reverse post order traversal of current function 1821495Sjmacd// (starting at 2), which effectively gives values in deep loops higher rank 1921495Sjmacd// than values not in loops. 2021495Sjmacd// 2121495Sjmacd//===----------------------------------------------------------------------===// 2242660Smarkm 2342660Smarkm#define DEBUG_TYPE "reassociate" 2421495Sjmacd#include "llvm/Transforms/Scalar.h" 2521495Sjmacd#include "llvm/Constants.h" 2621495Sjmacd#include "llvm/DerivedTypes.h" 2721495Sjmacd#include "llvm/Function.h" 2821495Sjmacd#include "llvm/Instructions.h" 2921495Sjmacd#include "llvm/IntrinsicInst.h" 3021495Sjmacd#include "llvm/Pass.h" 3142660Smarkm#include "llvm/Assembly/Writer.h" 3242660Smarkm#include "llvm/Support/CFG.h" 3321495Sjmacd#include "llvm/Support/Debug.h" 3421495Sjmacd#include "llvm/Support/ValueHandle.h" 3521495Sjmacd#include "llvm/Support/raw_ostream.h" 3621495Sjmacd#include "llvm/ADT/PostOrderIterator.h" 3721495Sjmacd#include "llvm/ADT/Statistic.h" 3821495Sjmacd#include "llvm/ADT/DenseMap.h" 3921495Sjmacd#include <algorithm> 4021495Sjmacdusing namespace llvm; 4142660Smarkm 4221495SjmacdSTATISTIC(NumLinear , "Number of insts linearized"); 4321495SjmacdSTATISTIC(NumChanged, "Number of insts reassociated"); 4421495SjmacdSTATISTIC(NumAnnihil, "Number of expr tree annihilated"); 4521495SjmacdSTATISTIC(NumFactor , "Number of multiplies factored"); 4621495Sjmacd 4721495Sjmacdnamespace { 4821495Sjmacd struct ValueEntry { 4921495Sjmacd unsigned Rank; 5021495Sjmacd Value *Op; 5121495Sjmacd ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 5221495Sjmacd }; 5321495Sjmacd inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 5421495Sjmacd return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 5521495Sjmacd } 5621495Sjmacd} 5721495Sjmacd 5821495Sjmacd#ifndef NDEBUG 5921495Sjmacd/// PrintOps - Print out the expression identified in the Ops list. 6021495Sjmacd/// 6121495Sjmacdstatic void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) { 6221495Sjmacd Module *M = I->getParent()->getParent()->getParent(); 6321495Sjmacd errs() << Instruction::getOpcodeName(I->getOpcode()) << " " 6421495Sjmacd << *Ops[0].Op->getType() << '\t'; 6521495Sjmacd for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 6621495Sjmacd errs() << "[ "; 6721495Sjmacd WriteAsOperand(errs(), Ops[i].Op, false, M); 6821495Sjmacd errs() << ", #" << Ops[i].Rank << "] "; 6921495Sjmacd } 7021495Sjmacd} 7121495Sjmacd#endif 7221495Sjmacd 7321495Sjmacdnamespace { 7421495Sjmacd class Reassociate : public FunctionPass { 7521495Sjmacd DenseMap<BasicBlock*, unsigned> RankMap; 7621495Sjmacd DenseMap<AssertingVH<>, unsigned> ValueRankMap; 7721495Sjmacd bool MadeChange; 7821495Sjmacd public: 7921495Sjmacd static char ID; // Pass identification, replacement for typeid 8021495Sjmacd Reassociate() : FunctionPass(&ID) {} 8121495Sjmacd 8221495Sjmacd bool runOnFunction(Function &F); 8321495Sjmacd 8442660Smarkm virtual void getAnalysisUsage(AnalysisUsage &AU) const { 8521495Sjmacd AU.setPreservesCFG(); 8621495Sjmacd } 8742660Smarkm private: 8842660Smarkm void BuildRankMap(Function &F); 8921495Sjmacd unsigned getRank(Value *V); 9042660Smarkm Value *ReassociateExpression(BinaryOperator *I); 9121495Sjmacd void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops, 9242660Smarkm unsigned Idx = 0); 9342660Smarkm Value *OptimizeExpression(BinaryOperator *I, 9442660Smarkm SmallVectorImpl<ValueEntry> &Ops); 9542660Smarkm Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops); 9642660Smarkm void LinearizeExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops); 9742660Smarkm void LinearizeExpr(BinaryOperator *I); 9842660Smarkm Value *RemoveFactorFromExpression(Value *V, Value *Factor); 9942660Smarkm void ReassociateBB(BasicBlock *BB); 10042660Smarkm 10142660Smarkm void RemoveDeadBinaryOp(Value *V); 10221495Sjmacd }; 10342660Smarkm} 10442660Smarkm 10542660Smarkmchar Reassociate::ID = 0; 10642660Smarkmstatic RegisterPass<Reassociate> X("reassociate", "Reassociate expressions"); 10742660Smarkm 10821495Sjmacd// Public interface to the Reassociate pass 10942660SmarkmFunctionPass *llvm::createReassociatePass() { return new Reassociate(); } 11021495Sjmacd 11142660Smarkmvoid Reassociate::RemoveDeadBinaryOp(Value *V) { 11221495Sjmacd Instruction *Op = dyn_cast<Instruction>(V); 11342660Smarkm if (!Op || !isa<BinaryOperator>(Op) || !Op->use_empty()) 11442660Smarkm return; 11542660Smarkm 11642660Smarkm Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1); 11721495Sjmacd 11842660Smarkm ValueRankMap.erase(Op); 11942660Smarkm Op->eraseFromParent(); 12042660Smarkm RemoveDeadBinaryOp(LHS); 12142660Smarkm RemoveDeadBinaryOp(RHS); 12221495Sjmacd} 12342660Smarkm 12421495Sjmacd 12521495Sjmacdstatic bool isUnmovableInstruction(Instruction *I) { 12642660Smarkm if (I->getOpcode() == Instruction::PHI || 12742660Smarkm I->getOpcode() == Instruction::Alloca || 12842660Smarkm I->getOpcode() == Instruction::Load || 12942660Smarkm I->getOpcode() == Instruction::Invoke || 13042660Smarkm (I->getOpcode() == Instruction::Call && 13142660Smarkm !isa<DbgInfoIntrinsic>(I)) || 13242660Smarkm I->getOpcode() == Instruction::UDiv || 13342660Smarkm I->getOpcode() == Instruction::SDiv || 13442660Smarkm I->getOpcode() == Instruction::FDiv || 13542660Smarkm I->getOpcode() == Instruction::URem || 13621495Sjmacd I->getOpcode() == Instruction::SRem || 13721495Sjmacd I->getOpcode() == Instruction::FRem) 13821495Sjmacd return true; 13921495Sjmacd return false; 14021495Sjmacd} 14121495Sjmacd 14221495Sjmacdvoid Reassociate::BuildRankMap(Function &F) { 14321495Sjmacd unsigned i = 2; 14421495Sjmacd 14521495Sjmacd // Assign distinct ranks to function arguments 14621495Sjmacd for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) 14721495Sjmacd ValueRankMap[&*I] = ++i; 14821495Sjmacd 14921495Sjmacd ReversePostOrderTraversal<Function*> RPOT(&F); 15021495Sjmacd for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(), 15121495Sjmacd E = RPOT.end(); I != E; ++I) { 15221495Sjmacd BasicBlock *BB = *I; 15342660Smarkm unsigned BBRank = RankMap[BB] = ++i << 16; 15421495Sjmacd 15521495Sjmacd // Walk the basic block, adding precomputed ranks for any instructions that 15621495Sjmacd // we cannot move. This ensures that the ranks for these instructions are 15721495Sjmacd // all different in the block. 15821495Sjmacd for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 15921495Sjmacd if (isUnmovableInstruction(I)) 16042660Smarkm ValueRankMap[&*I] = ++BBRank; 16142660Smarkm } 16221495Sjmacd} 16342660Smarkm 16442660Smarkmunsigned Reassociate::getRank(Value *V) { 16542660Smarkm Instruction *I = dyn_cast<Instruction>(V); 16642660Smarkm if (I == 0) { 16721495Sjmacd if (isa<Argument>(V)) return ValueRankMap[V]; // Function argument. 16821495Sjmacd return 0; // Otherwise it's a global or constant, rank 0. 16921495Sjmacd } 17021495Sjmacd 17142660Smarkm if (unsigned Rank = ValueRankMap[I]) 17221495Sjmacd return Rank; // Rank already known? 17321495Sjmacd 17421495Sjmacd // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that 17521495Sjmacd // we can reassociate expressions for code motion! Since we do not recurse 17621495Sjmacd // for PHI nodes, we cannot have infinite recursion here, because there 17721495Sjmacd // cannot be loops in the value graph that do not go through PHI nodes. 17821495Sjmacd unsigned Rank = 0, MaxRank = RankMap[I->getParent()]; 17942660Smarkm for (unsigned i = 0, e = I->getNumOperands(); 18042660Smarkm i != e && Rank != MaxRank; ++i) 18121495Sjmacd Rank = std::max(Rank, getRank(I->getOperand(i))); 18242660Smarkm 18321495Sjmacd // If this is a not or neg instruction, do not count it for rank. This 18442660Smarkm // assures us that X and ~X will have the same rank. 18542660Smarkm if (!I->getType()->isInteger() || 18642660Smarkm (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I))) 18742660Smarkm ++Rank; 18842660Smarkm 18942660Smarkm //DEBUG(errs() << "Calculated Rank[" << V->getName() << "] = " 19042660Smarkm // << Rank << "\n"); 19142660Smarkm 19242660Smarkm return ValueRankMap[I] = Rank; 19342660Smarkm} 19442660Smarkm 19521495Sjmacd/// isReassociableOp - Return true if V is an instruction of the specified 19642660Smarkm/// opcode and if it only has one use. 19742660Smarkmstatic BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { 19842660Smarkm if ((V->hasOneUse() || V->use_empty()) && isa<Instruction>(V) && 19921495Sjmacd cast<Instruction>(V)->getOpcode() == Opcode) 20042660Smarkm return cast<BinaryOperator>(V); 20142660Smarkm return 0; 20242660Smarkm} 20342660Smarkm 20442660Smarkm/// LowerNegateToMultiply - Replace 0-X with X*-1. 20542660Smarkm/// 20642660Smarkmstatic Instruction *LowerNegateToMultiply(Instruction *Neg, 20742660Smarkm DenseMap<AssertingVH<>, unsigned> &ValueRankMap) { 20842660Smarkm Constant *Cst = Constant::getAllOnesValue(Neg->getType()); 20942660Smarkm 21042660Smarkm Instruction *Res = BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg); 21142660Smarkm ValueRankMap.erase(Neg); 21242660Smarkm Res->takeName(Neg); 21321495Sjmacd Neg->replaceAllUsesWith(Res); 21442660Smarkm Neg->eraseFromParent(); 21521495Sjmacd return Res; 21642660Smarkm} 21742660Smarkm 21842660Smarkm// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. 21942660Smarkm// Note that if D is also part of the expression tree that we recurse to 22021495Sjmacd// linearize it as well. Besides that case, this does not recurse into A,B, or 22142660Smarkm// C. 22242660Smarkmvoid Reassociate::LinearizeExpr(BinaryOperator *I) { 22342660Smarkm BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 22442660Smarkm BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1)); 22542660Smarkm assert(isReassociableOp(LHS, I->getOpcode()) && 22642660Smarkm isReassociableOp(RHS, I->getOpcode()) && 22721495Sjmacd "Not an expression that needs linearization?"); 22821495Sjmacd 22921495Sjmacd DEBUG(errs() << "Linear" << *LHS << '\n' << *RHS << '\n' << *I << '\n'); 23021495Sjmacd 23121495Sjmacd // Move the RHS instruction to live immediately before I, avoiding breaking 23221495Sjmacd // dominator properties. 23321495Sjmacd RHS->moveBefore(I); 23421495Sjmacd 23521495Sjmacd // Move operands around to do the linearization. 23621495Sjmacd I->setOperand(1, RHS->getOperand(0)); 23721495Sjmacd RHS->setOperand(0, LHS); 23821495Sjmacd I->setOperand(0, RHS); 23921495Sjmacd 24021495Sjmacd ++NumLinear; 24121495Sjmacd MadeChange = true; 24221495Sjmacd DEBUG(errs() << "Linearized: " << *I << '\n'); 24321495Sjmacd 24421495Sjmacd // If D is part of this expression tree, tail recurse. 24521495Sjmacd if (isReassociableOp(I->getOperand(1), I->getOpcode())) 24621495Sjmacd LinearizeExpr(I); 24721495Sjmacd} 24821495Sjmacd 24921495Sjmacd 25021495Sjmacd/// LinearizeExprTree - Given an associative binary expression tree, traverse 25121495Sjmacd/// all of the uses putting it into canonical form. This forces a left-linear 25221495Sjmacd/// form of the the expression (((a+b)+c)+d), and collects information about the 25321495Sjmacd/// rank of the non-tree operands. 25421495Sjmacd/// 25521495Sjmacd/// NOTE: These intentionally destroys the expression tree operands (turning 25621495Sjmacd/// them into undef values) to reduce #uses of the values. This means that the 25721495Sjmacd/// caller MUST use something like RewriteExprTree to put the values back in. 25821495Sjmacd/// 25921495Sjmacdvoid Reassociate::LinearizeExprTree(BinaryOperator *I, 26042660Smarkm SmallVectorImpl<ValueEntry> &Ops) { 26121495Sjmacd Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); 26221495Sjmacd unsigned Opcode = I->getOpcode(); 26321495Sjmacd 26421495Sjmacd // First step, linearize the expression if it is in ((A+B)+(C+D)) form. 26521495Sjmacd BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); 26621495Sjmacd BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); 26721495Sjmacd 26821495Sjmacd // If this is a multiply expression tree and it contains internal negations, 26921495Sjmacd // transform them into multiplies by -1 so they can be reassociated. 27021495Sjmacd if (I->getOpcode() == Instruction::Mul) { 27121495Sjmacd if (!LHSBO && LHS->hasOneUse() && BinaryOperator::isNeg(LHS)) { 27221495Sjmacd LHS = LowerNegateToMultiply(cast<Instruction>(LHS), ValueRankMap); 27321495Sjmacd LHSBO = isReassociableOp(LHS, Opcode); 27421495Sjmacd } 27521495Sjmacd if (!RHSBO && RHS->hasOneUse() && BinaryOperator::isNeg(RHS)) { 27621495Sjmacd RHS = LowerNegateToMultiply(cast<Instruction>(RHS), ValueRankMap); 27721495Sjmacd RHSBO = isReassociableOp(RHS, Opcode); 27821495Sjmacd } 27921495Sjmacd } 28021495Sjmacd 28121495Sjmacd if (!LHSBO) { 28221495Sjmacd if (!RHSBO) { 28321495Sjmacd // Neither the LHS or RHS as part of the tree, thus this is a leaf. As 28421495Sjmacd // such, just remember these operands and their rank. 28521495Sjmacd Ops.push_back(ValueEntry(getRank(LHS), LHS)); 28621495Sjmacd Ops.push_back(ValueEntry(getRank(RHS), RHS)); 28742660Smarkm 28842660Smarkm // Clear the leaves out. 28942660Smarkm I->setOperand(0, UndefValue::get(I->getType())); 29042660Smarkm I->setOperand(1, UndefValue::get(I->getType())); 29121495Sjmacd return; 29221495Sjmacd } 29321495Sjmacd 29421495Sjmacd // Turn X+(Y+Z) -> (Y+Z)+X 29521495Sjmacd std::swap(LHSBO, RHSBO); 29621495Sjmacd std::swap(LHS, RHS); 29721495Sjmacd bool Success = !I->swapOperands(); 29821495Sjmacd assert(Success && "swapOperands failed"); 29921495Sjmacd Success = false; 30021495Sjmacd MadeChange = true; 30121495Sjmacd } else if (RHSBO) { 30221495Sjmacd // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the the RHS is not 30321495Sjmacd // part of the expression tree. 30421495Sjmacd LinearizeExpr(I); 30521495Sjmacd LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0)); 30621495Sjmacd RHS = I->getOperand(1); 30721495Sjmacd RHSBO = 0; 30821495Sjmacd } 30921495Sjmacd 31042660Smarkm // Okay, now we know that the LHS is a nested expression and that the RHS is 31121495Sjmacd // not. Perform reassociation. 31221495Sjmacd assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); 31321495Sjmacd 31442660Smarkm // Move LHS right before I to make sure that the tree expression dominates all 31542660Smarkm // values. 31621495Sjmacd LHSBO->moveBefore(I); 31721495Sjmacd 31821495Sjmacd // Linearize the expression tree on the LHS. 31921495Sjmacd LinearizeExprTree(LHSBO, Ops); 32021495Sjmacd 32121495Sjmacd // Remember the RHS operand and its rank. 32221495Sjmacd Ops.push_back(ValueEntry(getRank(RHS), RHS)); 32321495Sjmacd 32421495Sjmacd // Clear the RHS leaf out. 32521495Sjmacd I->setOperand(1, UndefValue::get(I->getType())); 32621495Sjmacd} 32742660Smarkm 32821495Sjmacd// RewriteExprTree - Now that the operands for this expression tree are 32921495Sjmacd// linearized and optimized, emit them in-order. This function is written to be 33021495Sjmacd// tail recursive. 33121495Sjmacdvoid Reassociate::RewriteExprTree(BinaryOperator *I, 33221495Sjmacd SmallVectorImpl<ValueEntry> &Ops, 33321495Sjmacd unsigned i) { 33421495Sjmacd if (i+2 == Ops.size()) { 33521495Sjmacd if (I->getOperand(0) != Ops[i].Op || 33621495Sjmacd I->getOperand(1) != Ops[i+1].Op) { 33721495Sjmacd Value *OldLHS = I->getOperand(0); 33821495Sjmacd DEBUG(errs() << "RA: " << *I << '\n'); 33921495Sjmacd I->setOperand(0, Ops[i].Op); 34021495Sjmacd I->setOperand(1, Ops[i+1].Op); 34121495Sjmacd DEBUG(errs() << "TO: " << *I << '\n'); 34221495Sjmacd MadeChange = true; 34321495Sjmacd ++NumChanged; 34421495Sjmacd 34521495Sjmacd // If we reassociated a tree to fewer operands (e.g. (1+a+2) -> (a+3) 34621495Sjmacd // delete the extra, now dead, nodes. 34721495Sjmacd RemoveDeadBinaryOp(OldLHS); 34821495Sjmacd } 34921495Sjmacd return; 35021495Sjmacd } 35121495Sjmacd assert(i+2 < Ops.size() && "Ops index out of range!"); 35221495Sjmacd 35321495Sjmacd if (I->getOperand(1) != Ops[i].Op) { 35421495Sjmacd DEBUG(errs() << "RA: " << *I << '\n'); 35521495Sjmacd I->setOperand(1, Ops[i].Op); 35621495Sjmacd DEBUG(errs() << "TO: " << *I << '\n'); 35721495Sjmacd MadeChange = true; 35821495Sjmacd ++NumChanged; 35921495Sjmacd } 36021495Sjmacd 36121495Sjmacd BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0)); 36242660Smarkm assert(LHS->getOpcode() == I->getOpcode() && 36321495Sjmacd "Improper expression tree!"); 36421495Sjmacd 36521495Sjmacd // Compactify the tree instructions together with each other to guarantee 36621495Sjmacd // that the expression tree is dominated by all of Ops. 36721495Sjmacd LHS->moveBefore(I); 36821495Sjmacd RewriteExprTree(LHS, Ops, i+1); 36921495Sjmacd} 37021495Sjmacd 37121495Sjmacd 37221495Sjmacd 37321495Sjmacd// NegateValue - Insert instructions before the instruction pointed to by BI, 37421495Sjmacd// that computes the negative version of the value specified. The negative 37521495Sjmacd// version of the value is returned, and BI is left pointing at the instruction 37621495Sjmacd// that should be processed next by the reassociation pass. 37721495Sjmacd// 37821495Sjmacdstatic Value *NegateValue(Value *V, Instruction *BI) { 37921495Sjmacd if (Constant *C = dyn_cast<Constant>(V)) 38021495Sjmacd return ConstantExpr::getNeg(C); 38121495Sjmacd 38221495Sjmacd // We are trying to expose opportunity for reassociation. One of the things 38321495Sjmacd // that we want to do to achieve this is to push a negation as deep into an 38421495Sjmacd // expression chain as possible, to expose the add instructions. In practice, 38521495Sjmacd // this means that we turn this: 38621495Sjmacd // X = -(A+12+C+D) into X = -A + -12 + -C + -D = -12 + -A + -C + -D 38721495Sjmacd // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate 38821495Sjmacd // the constants. We assume that instcombine will clean up the mess later if 38921495Sjmacd // we introduce tons of unnecessary negation instructions. 39021495Sjmacd // 39121495Sjmacd if (Instruction *I = dyn_cast<Instruction>(V)) 39221495Sjmacd if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { 39321495Sjmacd // Push the negates through the add. 39421495Sjmacd I->setOperand(0, NegateValue(I->getOperand(0), BI)); 39521495Sjmacd I->setOperand(1, NegateValue(I->getOperand(1), BI)); 39621495Sjmacd 39721495Sjmacd // We must move the add instruction here, because the neg instructions do 39821495Sjmacd // not dominate the old add instruction in general. By moving it, we are 39921495Sjmacd // assured that the neg instructions we just inserted dominate the 40021495Sjmacd // instruction we are about to insert after them. 40121495Sjmacd // 40221495Sjmacd I->moveBefore(BI); 40321495Sjmacd I->setName(I->getName()+".neg"); 40421495Sjmacd return I; 40521495Sjmacd } 40642660Smarkm 40742660Smarkm // Okay, we need to materialize a negated version of V with an instruction. 40842660Smarkm // Scan the use lists of V to see if we have one already. 40942660Smarkm for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){ 41021495Sjmacd if (!BinaryOperator::isNeg(*UI)) continue; 41121495Sjmacd 41221495Sjmacd // We found one! Now we have to make sure that the definition dominates 41321495Sjmacd // this use. We do this by moving it to the entry block (if it is a 41421495Sjmacd // non-instruction value) or right after the definition. These negates will 41542660Smarkm // be zapped by reassociate later, so we don't need much finesse here. 41642660Smarkm BinaryOperator *TheNeg = cast<BinaryOperator>(*UI); 41742660Smarkm 41842660Smarkm BasicBlock::iterator InsertPt; 41942660Smarkm if (Instruction *InstInput = dyn_cast<Instruction>(V)) { 42042660Smarkm if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) { 42121495Sjmacd InsertPt = II->getNormalDest()->begin(); 42221495Sjmacd } else { 42321495Sjmacd InsertPt = InstInput; 42421495Sjmacd ++InsertPt; 42521495Sjmacd } 42621495Sjmacd while (isa<PHINode>(InsertPt)) ++InsertPt; 42721495Sjmacd } else { 42821495Sjmacd InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin(); 42921495Sjmacd } 43021495Sjmacd TheNeg->moveBefore(InsertPt); 43121495Sjmacd return TheNeg; 43221495Sjmacd } 43321495Sjmacd 43421495Sjmacd // Insert a 'neg' instruction that subtracts the value from zero to get the 43521495Sjmacd // negation. 43621495Sjmacd return BinaryOperator::CreateNeg(V, V->getName() + ".neg", BI); 43721495Sjmacd} 43821495Sjmacd 43921495Sjmacd/// ShouldBreakUpSubtract - Return true if we should break up this subtract of 44021495Sjmacd/// X-Y into (X + -Y). 44121495Sjmacdstatic bool ShouldBreakUpSubtract(Instruction *Sub) { 44221495Sjmacd // If this is a negation, we can't split it up! 44321495Sjmacd if (BinaryOperator::isNeg(Sub)) 44421495Sjmacd return false; 44521495Sjmacd 44621495Sjmacd // Don't bother to break this up unless either the LHS is an associable add or 44721495Sjmacd // subtract or if this is only used by one. 44821495Sjmacd if (isReassociableOp(Sub->getOperand(0), Instruction::Add) || 44921495Sjmacd isReassociableOp(Sub->getOperand(0), Instruction::Sub)) 45021495Sjmacd return true; 45121495Sjmacd if (isReassociableOp(Sub->getOperand(1), Instruction::Add) || 45221495Sjmacd isReassociableOp(Sub->getOperand(1), Instruction::Sub)) 45321495Sjmacd return true; 45421495Sjmacd if (Sub->hasOneUse() && 45521495Sjmacd (isReassociableOp(Sub->use_back(), Instruction::Add) || 45621495Sjmacd isReassociableOp(Sub->use_back(), Instruction::Sub))) 45721495Sjmacd return true; 45821495Sjmacd 45921495Sjmacd return false; 46021495Sjmacd} 46121495Sjmacd 46221495Sjmacd/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is 46321495Sjmacd/// only used by an add, transform this into (X+(0-Y)) to promote better 46421495Sjmacd/// reassociation. 46521495Sjmacdstatic Instruction *BreakUpSubtract(Instruction *Sub, 46621495Sjmacd DenseMap<AssertingVH<>, unsigned> &ValueRankMap) { 46721495Sjmacd // Convert a subtract into an add and a neg instruction. This allows sub 46821495Sjmacd // instructions to be commuted with other add instructions. 46921495Sjmacd // 47021495Sjmacd // Calculate the negative value of Operand 1 of the sub instruction, 47121495Sjmacd // and set it as the RHS of the add instruction we just made. 47221495Sjmacd // 47321495Sjmacd Value *NegVal = NegateValue(Sub->getOperand(1), Sub); 47421495Sjmacd Instruction *New = 47521495Sjmacd BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub); 47621495Sjmacd New->takeName(Sub); 47721495Sjmacd 47821495Sjmacd // Everyone now refers to the add instruction. 47921495Sjmacd ValueRankMap.erase(Sub); 48042660Smarkm Sub->replaceAllUsesWith(New); 48142660Smarkm Sub->eraseFromParent(); 48221495Sjmacd 48342660Smarkm DEBUG(errs() << "Negated: " << *New << '\n'); 48421495Sjmacd return New; 48542660Smarkm} 48642660Smarkm 48742660Smarkm/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used 48821495Sjmacd/// by one, change this into a multiply by a constant to assist with further 48942660Smarkm/// reassociation. 49042660Smarkmstatic Instruction *ConvertShiftToMul(Instruction *Shl, 49142660Smarkm DenseMap<AssertingVH<>, unsigned> &ValueRankMap) { 49242660Smarkm // If an operand of this shift is a reassociable multiply, or if the shift 49342660Smarkm // is used by a reassociable multiply or add, turn into a multiply. 49421495Sjmacd if (isReassociableOp(Shl->getOperand(0), Instruction::Mul) || 49521495Sjmacd (Shl->hasOneUse() && 49621495Sjmacd (isReassociableOp(Shl->use_back(), Instruction::Mul) || 49721495Sjmacd isReassociableOp(Shl->use_back(), Instruction::Add)))) { 49821495Sjmacd Constant *MulCst = ConstantInt::get(Shl->getType(), 1); 49921495Sjmacd MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1))); 50021495Sjmacd 50121495Sjmacd Instruction *Mul = 50221495Sjmacd BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl); 50321495Sjmacd ValueRankMap.erase(Shl); 50421495Sjmacd Mul->takeName(Shl); 50521495Sjmacd Shl->replaceAllUsesWith(Mul); 50621495Sjmacd Shl->eraseFromParent(); 50721495Sjmacd return Mul; 50821495Sjmacd } 50921495Sjmacd return 0; 51021495Sjmacd} 51121495Sjmacd 51221495Sjmacd// Scan backwards and forwards among values with the same rank as element i to 51321495Sjmacd// see if X exists. If X does not exist, return i. This is useful when 51421495Sjmacd// scanning for 'x' when we see '-x' because they both get the same rank. 51521495Sjmacdstatic unsigned FindInOperandList(SmallVectorImpl<ValueEntry> &Ops, unsigned i, 51621495Sjmacd Value *X) { 51721495Sjmacd unsigned XRank = Ops[i].Rank; 51821495Sjmacd unsigned e = Ops.size(); 51921495Sjmacd for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) 52021495Sjmacd if (Ops[j].Op == X) 52121495Sjmacd return j; 52221495Sjmacd // Scan backwards. 52321495Sjmacd for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) 52421495Sjmacd if (Ops[j].Op == X) 52521495Sjmacd return j; 52621495Sjmacd return i; 52721495Sjmacd} 52821495Sjmacd 52921495Sjmacd/// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together 53021495Sjmacd/// and returning the result. Insert the tree before I. 53121495Sjmacdstatic Value *EmitAddTreeOfValues(Instruction *I, SmallVectorImpl<Value*> &Ops){ 53221495Sjmacd if (Ops.size() == 1) return Ops.back(); 53321495Sjmacd 53421495Sjmacd Value *V1 = Ops.back(); 53521495Sjmacd Ops.pop_back(); 53621495Sjmacd Value *V2 = EmitAddTreeOfValues(I, Ops); 53721495Sjmacd return BinaryOperator::CreateAdd(V2, V1, "tmp", I); 53821495Sjmacd} 53921495Sjmacd 54021495Sjmacd/// RemoveFactorFromExpression - If V is an expression tree that is a 54121495Sjmacd/// multiplication sequence, and if this sequence contains a multiply by Factor, 54242660Smarkm/// remove Factor from the tree and return the new tree. 54342660SmarkmValue *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { 54421495Sjmacd BinaryOperator *BO = isReassociableOp(V, Instruction::Mul); 54521495Sjmacd if (!BO) return 0; 54621495Sjmacd 54721495Sjmacd SmallVector<ValueEntry, 8> Factors; 54821495Sjmacd LinearizeExprTree(BO, Factors); 54921495Sjmacd 55021495Sjmacd bool FoundFactor = false; 55121495Sjmacd bool NeedsNegate = false; 55221495Sjmacd for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 55321495Sjmacd if (Factors[i].Op == Factor) { 55421495Sjmacd FoundFactor = true; 55521495Sjmacd Factors.erase(Factors.begin()+i); 55621495Sjmacd break; 55721495Sjmacd } 55821495Sjmacd 55921495Sjmacd // If this is a negative version of this factor, remove it. 56021495Sjmacd if (ConstantInt *FC1 = dyn_cast<ConstantInt>(Factor)) 56121495Sjmacd if (ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op)) 56221495Sjmacd if (FC1->getValue() == -FC2->getValue()) { 56321495Sjmacd FoundFactor = NeedsNegate = true; 56421495Sjmacd Factors.erase(Factors.begin()+i); 56521495Sjmacd break; 56621495Sjmacd } 56721495Sjmacd } 56821495Sjmacd 56921495Sjmacd if (!FoundFactor) { 57021495Sjmacd // Make sure to restore the operands to the expression tree. 57121495Sjmacd RewriteExprTree(BO, Factors); 57221495Sjmacd return 0; 57321495Sjmacd } 57421495Sjmacd 57521495Sjmacd BasicBlock::iterator InsertPt = BO; ++InsertPt; 57621495Sjmacd 57721495Sjmacd // If this was just a single multiply, remove the multiply and return the only 57821495Sjmacd // remaining operand. 57921495Sjmacd if (Factors.size() == 1) { 58021495Sjmacd ValueRankMap.erase(BO); 58121495Sjmacd BO->eraseFromParent(); 58221495Sjmacd V = Factors[0].Op; 58321495Sjmacd } else { 58421495Sjmacd RewriteExprTree(BO, Factors); 585 V = BO; 586 } 587 588 if (NeedsNegate) 589 V = BinaryOperator::CreateNeg(V, "neg", InsertPt); 590 591 return V; 592} 593 594/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively 595/// add its operands as factors, otherwise add V to the list of factors. 596static void FindSingleUseMultiplyFactors(Value *V, 597 SmallVectorImpl<Value*> &Factors) { 598 BinaryOperator *BO; 599 if ((!V->hasOneUse() && !V->use_empty()) || 600 !(BO = dyn_cast<BinaryOperator>(V)) || 601 BO->getOpcode() != Instruction::Mul) { 602 Factors.push_back(V); 603 return; 604 } 605 606 // Otherwise, add the LHS and RHS to the list of factors. 607 FindSingleUseMultiplyFactors(BO->getOperand(1), Factors); 608 FindSingleUseMultiplyFactors(BO->getOperand(0), Factors); 609} 610 611/// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor' 612/// instruction. This optimizes based on identities. If it can be reduced to 613/// a single Value, it is returned, otherwise the Ops list is mutated as 614/// necessary. 615static Value *OptimizeAndOrXor(unsigned Opcode, 616 SmallVectorImpl<ValueEntry> &Ops) { 617 // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. 618 // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1. 619 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 620 // First, check for X and ~X in the operand list. 621 assert(i < Ops.size()); 622 if (BinaryOperator::isNot(Ops[i].Op)) { // Cannot occur for ^. 623 Value *X = BinaryOperator::getNotArgument(Ops[i].Op); 624 unsigned FoundX = FindInOperandList(Ops, i, X); 625 if (FoundX != i) { 626 if (Opcode == Instruction::And) // ...&X&~X = 0 627 return Constant::getNullValue(X->getType()); 628 629 if (Opcode == Instruction::Or) // ...|X|~X = -1 630 return Constant::getAllOnesValue(X->getType()); 631 } 632 } 633 634 // Next, check for duplicate pairs of values, which we assume are next to 635 // each other, due to our sorting criteria. 636 assert(i < Ops.size()); 637 if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) { 638 if (Opcode == Instruction::And || Opcode == Instruction::Or) { 639 // Drop duplicate values for And and Or. 640 Ops.erase(Ops.begin()+i); 641 --i; --e; 642 ++NumAnnihil; 643 continue; 644 } 645 646 // Drop pairs of values for Xor. 647 assert(Opcode == Instruction::Xor); 648 if (e == 2) 649 return Constant::getNullValue(Ops[0].Op->getType()); 650 651 // Y ^ X^X -> Y 652 Ops.erase(Ops.begin()+i, Ops.begin()+i+2); 653 i -= 1; e -= 2; 654 ++NumAnnihil; 655 } 656 } 657 return 0; 658} 659 660/// OptimizeAdd - Optimize a series of operands to an 'add' instruction. This 661/// optimizes based on identities. If it can be reduced to a single Value, it 662/// is returned, otherwise the Ops list is mutated as necessary. 663Value *Reassociate::OptimizeAdd(Instruction *I, 664 SmallVectorImpl<ValueEntry> &Ops) { 665 // Scan the operand lists looking for X and -X pairs. If we find any, we 666 // can simplify the expression. X+-X == 0. While we're at it, scan for any 667 // duplicates. We want to canonicalize Y+Y+Y+Z -> 3*Y+Z. 668 // 669 // TODO: We could handle "X + ~X" -> "-1" if we wanted, since "-X = ~X+1". 670 // 671 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 672 Value *TheOp = Ops[i].Op; 673 // Check to see if we've seen this operand before. If so, we factor all 674 // instances of the operand together. Due to our sorting criteria, we know 675 // that these need to be next to each other in the vector. 676 if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) { 677 // Rescan the list, remove all instances of this operand from the expr. 678 unsigned NumFound = 0; 679 do { 680 Ops.erase(Ops.begin()+i); 681 ++NumFound; 682 } while (i != Ops.size() && Ops[i].Op == TheOp); 683 684 DEBUG(errs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n'); 685 ++NumFactor; 686 687 // Insert a new multiply. 688 Value *Mul = ConstantInt::get(cast<IntegerType>(I->getType()), NumFound); 689 Mul = BinaryOperator::CreateMul(TheOp, Mul, "factor", I); 690 691 // Now that we have inserted a multiply, optimize it. This allows us to 692 // handle cases that require multiple factoring steps, such as this: 693 // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6 694 Mul = ReassociateExpression(cast<BinaryOperator>(Mul)); 695 696 // If every add operand was a duplicate, return the multiply. 697 if (Ops.empty()) 698 return Mul; 699 700 // Otherwise, we had some input that didn't have the dupe, such as 701 // "A + A + B" -> "A*2 + B". Add the new multiply to the list of 702 // things being added by this operation. 703 Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul)); 704 705 --i; 706 e = Ops.size(); 707 continue; 708 } 709 710 // Check for X and -X in the operand list. 711 if (!BinaryOperator::isNeg(TheOp)) 712 continue; 713 714 Value *X = BinaryOperator::getNegArgument(TheOp); 715 unsigned FoundX = FindInOperandList(Ops, i, X); 716 if (FoundX == i) 717 continue; 718 719 // Remove X and -X from the operand list. 720 if (Ops.size() == 2) 721 return Constant::getNullValue(X->getType()); 722 723 Ops.erase(Ops.begin()+i); 724 if (i < FoundX) 725 --FoundX; 726 else 727 --i; // Need to back up an extra one. 728 Ops.erase(Ops.begin()+FoundX); 729 ++NumAnnihil; 730 --i; // Revisit element. 731 e -= 2; // Removed two elements. 732 } 733 734 // Scan the operand list, checking to see if there are any common factors 735 // between operands. Consider something like A*A+A*B*C+D. We would like to 736 // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies. 737 // To efficiently find this, we count the number of times a factor occurs 738 // for any ADD operands that are MULs. 739 DenseMap<Value*, unsigned> FactorOccurrences; 740 741 // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4) 742 // where they are actually the same multiply. 743 unsigned MaxOcc = 0; 744 Value *MaxOccVal = 0; 745 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 746 BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op); 747 if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty()) 748 continue; 749 750 // Compute all of the factors of this added value. 751 SmallVector<Value*, 8> Factors; 752 FindSingleUseMultiplyFactors(BOp, Factors); 753 assert(Factors.size() > 1 && "Bad linearize!"); 754 755 // Add one to FactorOccurrences for each unique factor in this op. 756 SmallPtrSet<Value*, 8> Duplicates; 757 for (unsigned i = 0, e = Factors.size(); i != e; ++i) { 758 Value *Factor = Factors[i]; 759 if (!Duplicates.insert(Factor)) continue; 760 761 unsigned Occ = ++FactorOccurrences[Factor]; 762 if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } 763 764 // If Factor is a negative constant, add the negated value as a factor 765 // because we can percolate the negate out. Watch for minint, which 766 // cannot be positivified. 767 if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) 768 if (CI->getValue().isNegative() && !CI->getValue().isMinSignedValue()) { 769 Factor = ConstantInt::get(CI->getContext(), -CI->getValue()); 770 assert(!Duplicates.count(Factor) && 771 "Shouldn't have two constant factors, missed a canonicalize"); 772 773 unsigned Occ = ++FactorOccurrences[Factor]; 774 if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } 775 } 776 } 777 } 778 779 // If any factor occurred more than one time, we can pull it out. 780 if (MaxOcc > 1) { 781 DEBUG(errs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n'); 782 ++NumFactor; 783 784 // Create a new instruction that uses the MaxOccVal twice. If we don't do 785 // this, we could otherwise run into situations where removing a factor 786 // from an expression will drop a use of maxocc, and this can cause 787 // RemoveFactorFromExpression on successive values to behave differently. 788 Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal); 789 SmallVector<Value*, 4> NewMulOps; 790 for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 791 if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { 792 NewMulOps.push_back(V); 793 Ops.erase(Ops.begin()+i); 794 --i; --e; 795 } 796 } 797 798 // No need for extra uses anymore. 799 delete DummyInst; 800 801 unsigned NumAddedValues = NewMulOps.size(); 802 Value *V = EmitAddTreeOfValues(I, NewMulOps); 803 804 // Now that we have inserted the add tree, optimize it. This allows us to 805 // handle cases that require multiple factoring steps, such as this: 806 // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C)) 807 assert(NumAddedValues > 1 && "Each occurrence should contribute a value"); 808 V = ReassociateExpression(cast<BinaryOperator>(V)); 809 810 // Create the multiply. 811 Value *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I); 812 813 // Rerun associate on the multiply in case the inner expression turned into 814 // a multiply. We want to make sure that we keep things in canonical form. 815 V2 = ReassociateExpression(cast<BinaryOperator>(V2)); 816 817 // If every add operand included the factor (e.g. "A*B + A*C"), then the 818 // entire result expression is just the multiply "A*(B+C)". 819 if (Ops.empty()) 820 return V2; 821 822 // Otherwise, we had some input that didn't have the factor, such as 823 // "A*B + A*C + D" -> "A*(B+C) + D". Add the new multiply to the list of 824 // things being added by this operation. 825 Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); 826 } 827 828 return 0; 829} 830 831Value *Reassociate::OptimizeExpression(BinaryOperator *I, 832 SmallVectorImpl<ValueEntry> &Ops) { 833 // Now that we have the linearized expression tree, try to optimize it. 834 // Start by folding any constants that we found. 835 bool IterateOptimization = false; 836 if (Ops.size() == 1) return Ops[0].Op; 837 838 unsigned Opcode = I->getOpcode(); 839 840 if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op)) 841 if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) { 842 Ops.pop_back(); 843 Ops.back().Op = ConstantExpr::get(Opcode, V1, V2); 844 return OptimizeExpression(I, Ops); 845 } 846 847 // Check for destructive annihilation due to a constant being used. 848 if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op)) 849 switch (Opcode) { 850 default: break; 851 case Instruction::And: 852 if (CstVal->isZero()) // X & 0 -> 0 853 return CstVal; 854 if (CstVal->isAllOnesValue()) // X & -1 -> X 855 Ops.pop_back(); 856 break; 857 case Instruction::Mul: 858 if (CstVal->isZero()) { // X * 0 -> 0 859 ++NumAnnihil; 860 return CstVal; 861 } 862 863 if (cast<ConstantInt>(CstVal)->isOne()) 864 Ops.pop_back(); // X * 1 -> X 865 break; 866 case Instruction::Or: 867 if (CstVal->isAllOnesValue()) // X | -1 -> -1 868 return CstVal; 869 // FALLTHROUGH! 870 case Instruction::Add: 871 case Instruction::Xor: 872 if (CstVal->isZero()) // X [|^+] 0 -> X 873 Ops.pop_back(); 874 break; 875 } 876 if (Ops.size() == 1) return Ops[0].Op; 877 878 // Handle destructive annihilation due to identities between elements in the 879 // argument list here. 880 switch (Opcode) { 881 default: break; 882 case Instruction::And: 883 case Instruction::Or: 884 case Instruction::Xor: { 885 unsigned NumOps = Ops.size(); 886 if (Value *Result = OptimizeAndOrXor(Opcode, Ops)) 887 return Result; 888 IterateOptimization |= Ops.size() != NumOps; 889 break; 890 } 891 892 case Instruction::Add: { 893 unsigned NumOps = Ops.size(); 894 if (Value *Result = OptimizeAdd(I, Ops)) 895 return Result; 896 IterateOptimization |= Ops.size() != NumOps; 897 } 898 899 break; 900 //case Instruction::Mul: 901 } 902 903 if (IterateOptimization) 904 return OptimizeExpression(I, Ops); 905 return 0; 906} 907 908 909/// ReassociateBB - Inspect all of the instructions in this basic block, 910/// reassociating them as we go. 911void Reassociate::ReassociateBB(BasicBlock *BB) { 912 for (BasicBlock::iterator BBI = BB->begin(); BBI != BB->end(); ) { 913 Instruction *BI = BBI++; 914 if (BI->getOpcode() == Instruction::Shl && 915 isa<ConstantInt>(BI->getOperand(1))) 916 if (Instruction *NI = ConvertShiftToMul(BI, ValueRankMap)) { 917 MadeChange = true; 918 BI = NI; 919 } 920 921 // Reject cases where it is pointless to do this. 922 if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPoint() || 923 isa<VectorType>(BI->getType())) 924 continue; // Floating point ops are not associative. 925 926 // If this is a subtract instruction which is not already in negate form, 927 // see if we can convert it to X+-Y. 928 if (BI->getOpcode() == Instruction::Sub) { 929 if (ShouldBreakUpSubtract(BI)) { 930 BI = BreakUpSubtract(BI, ValueRankMap); 931 MadeChange = true; 932 } else if (BinaryOperator::isNeg(BI)) { 933 // Otherwise, this is a negation. See if the operand is a multiply tree 934 // and if this is not an inner node of a multiply tree. 935 if (isReassociableOp(BI->getOperand(1), Instruction::Mul) && 936 (!BI->hasOneUse() || 937 !isReassociableOp(BI->use_back(), Instruction::Mul))) { 938 BI = LowerNegateToMultiply(BI, ValueRankMap); 939 MadeChange = true; 940 } 941 } 942 } 943 944 // If this instruction is a commutative binary operator, process it. 945 if (!BI->isAssociative()) continue; 946 BinaryOperator *I = cast<BinaryOperator>(BI); 947 948 // If this is an interior node of a reassociable tree, ignore it until we 949 // get to the root of the tree, to avoid N^2 analysis. 950 if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode())) 951 continue; 952 953 // If this is an add tree that is used by a sub instruction, ignore it 954 // until we process the subtract. 955 if (I->hasOneUse() && I->getOpcode() == Instruction::Add && 956 cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub) 957 continue; 958 959 ReassociateExpression(I); 960 } 961} 962 963Value *Reassociate::ReassociateExpression(BinaryOperator *I) { 964 965 // First, walk the expression tree, linearizing the tree, collecting the 966 // operand information. 967 SmallVector<ValueEntry, 8> Ops; 968 LinearizeExprTree(I, Ops); 969 970 DEBUG(errs() << "RAIn:\t"; PrintOps(I, Ops); errs() << '\n'); 971 972 // Now that we have linearized the tree to a list and have gathered all of 973 // the operands and their ranks, sort the operands by their rank. Use a 974 // stable_sort so that values with equal ranks will have their relative 975 // positions maintained (and so the compiler is deterministic). Note that 976 // this sorts so that the highest ranking values end up at the beginning of 977 // the vector. 978 std::stable_sort(Ops.begin(), Ops.end()); 979 980 // OptimizeExpression - Now that we have the expression tree in a convenient 981 // sorted form, optimize it globally if possible. 982 if (Value *V = OptimizeExpression(I, Ops)) { 983 // This expression tree simplified to something that isn't a tree, 984 // eliminate it. 985 DEBUG(errs() << "Reassoc to scalar: " << *V << '\n'); 986 I->replaceAllUsesWith(V); 987 RemoveDeadBinaryOp(I); 988 ++NumAnnihil; 989 return V; 990 } 991 992 // We want to sink immediates as deeply as possible except in the case where 993 // this is a multiply tree used only by an add, and the immediate is a -1. 994 // In this case we reassociate to put the negation on the outside so that we 995 // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y 996 if (I->getOpcode() == Instruction::Mul && I->hasOneUse() && 997 cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add && 998 isa<ConstantInt>(Ops.back().Op) && 999 cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) { 1000 ValueEntry Tmp = Ops.pop_back_val(); 1001 Ops.insert(Ops.begin(), Tmp); 1002 } 1003 1004 DEBUG(errs() << "RAOut:\t"; PrintOps(I, Ops); errs() << '\n'); 1005 1006 if (Ops.size() == 1) { 1007 // This expression tree simplified to something that isn't a tree, 1008 // eliminate it. 1009 I->replaceAllUsesWith(Ops[0].Op); 1010 RemoveDeadBinaryOp(I); 1011 return Ops[0].Op; 1012 } 1013 1014 // Now that we ordered and optimized the expressions, splat them back into 1015 // the expression tree, removing any unneeded nodes. 1016 RewriteExprTree(I, Ops); 1017 return I; 1018} 1019 1020 1021bool Reassociate::runOnFunction(Function &F) { 1022 // Recalculate the rank map for F 1023 BuildRankMap(F); 1024 1025 MadeChange = false; 1026 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) 1027 ReassociateBB(FI); 1028 1029 // We are done with the rank map. 1030 RankMap.clear(); 1031 ValueRankMap.clear(); 1032 return MadeChange; 1033} 1034 1035