LLVM API Documentation

Reassociate.cpp

Go to the documentation of this file.
00001 //===- Reassociate.cpp - Reassociate binary expressions -------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass reassociates commutative expressions in an order that is designed
00011 // to promote better constant propagation, GCSE, LICM, PRE...
00012 //
00013 // For example: 4 + (x + 5) -> x + (4 + 5)
00014 //
00015 // In the implementation of this algorithm, constants are assigned rank = 0,
00016 // function arguments are rank = 1, and other values are assigned ranks
00017 // corresponding to the reverse post order traversal of current function
00018 // (starting at 2), which effectively gives values in deep loops higher rank
00019 // than values not in loops.
00020 //
00021 //===----------------------------------------------------------------------===//
00022 
00023 #define DEBUG_TYPE "reassociate"
00024 #include "llvm/Transforms/Scalar.h"
00025 #include "llvm/Constants.h"
00026 #include "llvm/DerivedTypes.h"
00027 #include "llvm/Function.h"
00028 #include "llvm/Instructions.h"
00029 #include "llvm/IntrinsicInst.h"
00030 #include "llvm/LLVMContext.h"
00031 #include "llvm/Pass.h"
00032 #include "llvm/Assembly/Writer.h"
00033 #include "llvm/Support/CFG.h"
00034 #include "llvm/Support/Compiler.h"
00035 #include "llvm/Support/Debug.h"
00036 #include "llvm/Support/ValueHandle.h"
00037 #include "llvm/ADT/PostOrderIterator.h"
00038 #include "llvm/ADT/Statistic.h"
00039 #include <algorithm>
00040 #include <map>
00041 using namespace llvm;
00042 
00043 STATISTIC(NumLinear , "Number of insts linearized");
00044 STATISTIC(NumChanged, "Number of insts reassociated");
00045 STATISTIC(NumAnnihil, "Number of expr tree annihilated");
00046 STATISTIC(NumFactor , "Number of multiplies factored");
00047 
00048 namespace {
00049   struct VISIBILITY_HIDDEN ValueEntry {
00050     unsigned Rank;
00051     Value *Op;
00052     ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
00053   };
00054   inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
00055     return LHS.Rank > RHS.Rank;   // Sort so that highest rank goes to start.
00056   }
00057 }
00058 
00059 #ifndef NDEBUG
00060 /// PrintOps - Print out the expression identified in the Ops list.
00061 ///
00062 static void PrintOps(Instruction *I, const std::vector<ValueEntry> &Ops) {
00063   Module *M = I->getParent()->getParent()->getParent();
00064   cerr << Instruction::getOpcodeName(I->getOpcode()) << " "
00065        << *Ops[0].Op->getType();
00066   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
00067     WriteAsOperand(*cerr.stream() << " ", Ops[i].Op, false, M);
00068     cerr << "," << Ops[i].Rank;
00069   }
00070 }
00071 #endif
00072   
00073 namespace {
00074   class VISIBILITY_HIDDEN Reassociate : public FunctionPass {
00075     std::map<BasicBlock*, unsigned> RankMap;
00076     std::map<AssertingVH<>, unsigned> ValueRankMap;
00077     bool MadeChange;
00078   public:
00079     static char ID; // Pass identification, replacement for typeid
00080     Reassociate() : FunctionPass(&ID) {}
00081 
00082     bool runOnFunction(Function &F);
00083 
00084     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00085       AU.setPreservesCFG();
00086     }
00087   private:
00088     void BuildRankMap(Function &F);
00089     unsigned getRank(Value *V);
00090     void ReassociateExpression(BinaryOperator *I);
00091     void RewriteExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops,
00092                          unsigned Idx = 0);
00093     Value *OptimizeExpression(BinaryOperator *I, std::vector<ValueEntry> &Ops);
00094     void LinearizeExprTree(BinaryOperator *I, std::vector<ValueEntry> &Ops);
00095     void LinearizeExpr(BinaryOperator *I);
00096     Value *RemoveFactorFromExpression(Value *V, Value *Factor);
00097     void ReassociateBB(BasicBlock *BB);
00098     
00099     void RemoveDeadBinaryOp(Value *V);
00100   };
00101 }
00102 
00103 char Reassociate::ID = 0;
00104 static RegisterPass<Reassociate> X("reassociate", "Reassociate expressions");
00105 
00106 // Public interface to the Reassociate pass
00107 FunctionPass *llvm::createReassociatePass() { return new Reassociate(); }
00108 
00109 void Reassociate::RemoveDeadBinaryOp(Value *V) {
00110   Instruction *Op = dyn_cast<Instruction>(V);
00111   if (!Op || !isa<BinaryOperator>(Op) || !isa<CmpInst>(Op) || !Op->use_empty())
00112     return;
00113   
00114   Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1);
00115   RemoveDeadBinaryOp(LHS);
00116   RemoveDeadBinaryOp(RHS);
00117 }
00118 
00119 
00120 static bool isUnmovableInstruction(Instruction *I) {
00121   if (I->getOpcode() == Instruction::PHI ||
00122       I->getOpcode() == Instruction::Alloca ||
00123       I->getOpcode() == Instruction::Load ||
00124       I->getOpcode() == Instruction::Malloc ||
00125       I->getOpcode() == Instruction::Invoke ||
00126       (I->getOpcode() == Instruction::Call &&
00127        !isa<DbgInfoIntrinsic>(I)) ||
00128       I->getOpcode() == Instruction::UDiv || 
00129       I->getOpcode() == Instruction::SDiv ||
00130       I->getOpcode() == Instruction::FDiv ||
00131       I->getOpcode() == Instruction::URem ||
00132       I->getOpcode() == Instruction::SRem ||
00133       I->getOpcode() == Instruction::FRem)
00134     return true;
00135   return false;
00136 }
00137 
00138 void Reassociate::BuildRankMap(Function &F) {
00139   unsigned i = 2;
00140 
00141   // Assign distinct ranks to function arguments
00142   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
00143     ValueRankMap[&*I] = ++i;
00144 
00145   ReversePostOrderTraversal<Function*> RPOT(&F);
00146   for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
00147          E = RPOT.end(); I != E; ++I) {
00148     BasicBlock *BB = *I;
00149     unsigned BBRank = RankMap[BB] = ++i << 16;
00150 
00151     // Walk the basic block, adding precomputed ranks for any instructions that
00152     // we cannot move.  This ensures that the ranks for these instructions are
00153     // all different in the block.
00154     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
00155       if (isUnmovableInstruction(I))
00156         ValueRankMap[&*I] = ++BBRank;
00157   }
00158 }
00159 
00160 unsigned Reassociate::getRank(Value *V) {
00161   if (isa<Argument>(V)) return ValueRankMap[V];   // Function argument...
00162 
00163   Instruction *I = dyn_cast<Instruction>(V);
00164   if (I == 0) return 0;  // Otherwise it's a global or constant, rank 0.
00165 
00166   unsigned &CachedRank = ValueRankMap[I];
00167   if (CachedRank) return CachedRank;    // Rank already known?
00168 
00169   // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that
00170   // we can reassociate expressions for code motion!  Since we do not recurse
00171   // for PHI nodes, we cannot have infinite recursion here, because there
00172   // cannot be loops in the value graph that do not go through PHI nodes.
00173   unsigned Rank = 0, MaxRank = RankMap[I->getParent()];
00174   for (unsigned i = 0, e = I->getNumOperands();
00175        i != e && Rank != MaxRank; ++i)
00176     Rank = std::max(Rank, getRank(I->getOperand(i)));
00177 
00178   // If this is a not or neg instruction, do not count it for rank.  This
00179   // assures us that X and ~X will have the same rank.
00180   if (!I->getType()->isInteger() ||
00181       (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I)))
00182     ++Rank;
00183 
00184   //DOUT << "Calculated Rank[" << V->getName() << "] = "
00185   //     << Rank << "\n";
00186 
00187   return CachedRank = Rank;
00188 }
00189 
00190 /// isReassociableOp - Return true if V is an instruction of the specified
00191 /// opcode and if it only has one use.
00192 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) {
00193   if ((V->hasOneUse() || V->use_empty()) && isa<Instruction>(V) &&
00194       cast<Instruction>(V)->getOpcode() == Opcode)
00195     return cast<BinaryOperator>(V);
00196   return 0;
00197 }
00198 
00199 /// LowerNegateToMultiply - Replace 0-X with X*-1.
00200 ///
00201 static Instruction *LowerNegateToMultiply(Instruction *Neg,
00202                               std::map<AssertingVH<>, unsigned> &ValueRankMap,
00203                               LLVMContext &Context) {
00204   Constant *Cst = Constant::getAllOnesValue(Neg->getType());
00205 
00206   Instruction *Res = BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg);
00207   ValueRankMap.erase(Neg);
00208   Res->takeName(Neg);
00209   Neg->replaceAllUsesWith(Res);
00210   Neg->eraseFromParent();
00211   return Res;
00212 }
00213 
00214 // Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'.
00215 // Note that if D is also part of the expression tree that we recurse to
00216 // linearize it as well.  Besides that case, this does not recurse into A,B, or
00217 // C.
00218 void Reassociate::LinearizeExpr(BinaryOperator *I) {
00219   BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0));
00220   BinaryOperator *RHS = cast<BinaryOperator>(I->getOperand(1));
00221   assert(isReassociableOp(LHS, I->getOpcode()) &&
00222          isReassociableOp(RHS, I->getOpcode()) &&
00223          "Not an expression that needs linearization?");
00224 
00225   DOUT << "Linear" << *LHS << '\n' << *RHS << '\n' << *I << '\n';
00226 
00227   // Move the RHS instruction to live immediately before I, avoiding breaking
00228   // dominator properties.
00229   RHS->moveBefore(I);
00230 
00231   // Move operands around to do the linearization.
00232   I->setOperand(1, RHS->getOperand(0));
00233   RHS->setOperand(0, LHS);
00234   I->setOperand(0, RHS);
00235 
00236   ++NumLinear;
00237   MadeChange = true;
00238   DOUT << "Linearized: " << *I << '\n';
00239 
00240   // If D is part of this expression tree, tail recurse.
00241   if (isReassociableOp(I->getOperand(1), I->getOpcode()))
00242     LinearizeExpr(I);
00243 }
00244 
00245 
00246 /// LinearizeExprTree - Given an associative binary expression tree, traverse
00247 /// all of the uses putting it into canonical form.  This forces a left-linear
00248 /// form of the the expression (((a+b)+c)+d), and collects information about the
00249 /// rank of the non-tree operands.
00250 ///
00251 /// NOTE: These intentionally destroys the expression tree operands (turning
00252 /// them into undef values) to reduce #uses of the values.  This means that the
00253 /// caller MUST use something like RewriteExprTree to put the values back in.
00254 ///
00255 void Reassociate::LinearizeExprTree(BinaryOperator *I,
00256                                     std::vector<ValueEntry> &Ops) {
00257   Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
00258   unsigned Opcode = I->getOpcode();
00259   LLVMContext &Context = I->getContext();
00260 
00261   // First step, linearize the expression if it is in ((A+B)+(C+D)) form.
00262   BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode);
00263   BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode);
00264 
00265   // If this is a multiply expression tree and it contains internal negations,
00266   // transform them into multiplies by -1 so they can be reassociated.
00267   if (I->getOpcode() == Instruction::Mul) {
00268     if (!LHSBO && LHS->hasOneUse() && BinaryOperator::isNeg(LHS)) {
00269       LHS = LowerNegateToMultiply(cast<Instruction>(LHS),
00270                                   ValueRankMap, Context);
00271       LHSBO = isReassociableOp(LHS, Opcode);
00272     }
00273     if (!RHSBO && RHS->hasOneUse() && BinaryOperator::isNeg(RHS)) {
00274       RHS = LowerNegateToMultiply(cast<Instruction>(RHS),
00275                                   ValueRankMap, Context);
00276       RHSBO = isReassociableOp(RHS, Opcode);
00277     }
00278   }
00279 
00280   if (!LHSBO) {
00281     if (!RHSBO) {
00282       // Neither the LHS or RHS as part of the tree, thus this is a leaf.  As
00283       // such, just remember these operands and their rank.
00284       Ops.push_back(ValueEntry(getRank(LHS), LHS));
00285       Ops.push_back(ValueEntry(getRank(RHS), RHS));
00286       
00287       // Clear the leaves out.
00288       I->setOperand(0, UndefValue::get(I->getType()));
00289       I->setOperand(1, UndefValue::get(I->getType()));
00290       return;
00291     } else {
00292       // Turn X+(Y+Z) -> (Y+Z)+X
00293       std::swap(LHSBO, RHSBO);
00294       std::swap(LHS, RHS);
00295       bool Success = !I->swapOperands();
00296       assert(Success && "swapOperands failed");
00297       Success = false;
00298       MadeChange = true;
00299     }
00300   } else if (RHSBO) {
00301     // Turn (A+B)+(C+D) -> (((A+B)+C)+D).  This guarantees the the RHS is not
00302     // part of the expression tree.
00303     LinearizeExpr(I);
00304     LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0));
00305     RHS = I->getOperand(1);
00306     RHSBO = 0;
00307   }
00308 
00309   // Okay, now we know that the LHS is a nested expression and that the RHS is
00310   // not.  Perform reassociation.
00311   assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!");
00312 
00313   // Move LHS right before I to make sure that the tree expression dominates all
00314   // values.
00315   LHSBO->moveBefore(I);
00316 
00317   // Linearize the expression tree on the LHS.
00318   LinearizeExprTree(LHSBO, Ops);
00319 
00320   // Remember the RHS operand and its rank.
00321   Ops.push_back(ValueEntry(getRank(RHS), RHS));
00322   
00323   // Clear the RHS leaf out.
00324   I->setOperand(1, UndefValue::get(I->getType()));
00325 }
00326 
00327 // RewriteExprTree - Now that the operands for this expression tree are
00328 // linearized and optimized, emit them in-order.  This function is written to be
00329 // tail recursive.
00330 void Reassociate::RewriteExprTree(BinaryOperator *I,
00331                                   std::vector<ValueEntry> &Ops,
00332                                   unsigned i) {
00333   if (i+2 == Ops.size()) {
00334     if (I->getOperand(0) != Ops[i].Op ||
00335         I->getOperand(1) != Ops[i+1].Op) {
00336       Value *OldLHS = I->getOperand(0);
00337       DOUT << "RA: " << *I << '\n';
00338       I->setOperand(0, Ops[i].Op);
00339       I->setOperand(1, Ops[i+1].Op);
00340       DOUT << "TO: " << *I << '\n';
00341       MadeChange = true;
00342       ++NumChanged;
00343       
00344       // If we reassociated a tree to fewer operands (e.g. (1+a+2) -> (a+3)
00345       // delete the extra, now dead, nodes.
00346       RemoveDeadBinaryOp(OldLHS);
00347     }
00348     return;
00349   }
00350   assert(i+2 < Ops.size() && "Ops index out of range!");
00351 
00352   if (I->getOperand(1) != Ops[i].Op) {
00353     DOUT << "RA: " << *I << '\n';
00354     I->setOperand(1, Ops[i].Op);
00355     DOUT << "TO: " << *I << '\n';
00356     MadeChange = true;
00357     ++NumChanged;
00358   }
00359   
00360   BinaryOperator *LHS = cast<BinaryOperator>(I->getOperand(0));
00361   assert(LHS->getOpcode() == I->getOpcode() &&
00362          "Improper expression tree!");
00363   
00364   // Compactify the tree instructions together with each other to guarantee
00365   // that the expression tree is dominated by all of Ops.
00366   LHS->moveBefore(I);
00367   RewriteExprTree(LHS, Ops, i+1);
00368 }
00369 
00370 
00371 
00372 // NegateValue - Insert instructions before the instruction pointed to by BI,
00373 // that computes the negative version of the value specified.  The negative
00374 // version of the value is returned, and BI is left pointing at the instruction
00375 // that should be processed next by the reassociation pass.
00376 //
00377 static Value *NegateValue(LLVMContext &Context, Value *V, Instruction *BI) {
00378   // We are trying to expose opportunity for reassociation.  One of the things
00379   // that we want to do to achieve this is to push a negation as deep into an
00380   // expression chain as possible, to expose the add instructions.  In practice,
00381   // this means that we turn this:
00382   //   X = -(A+12+C+D)   into    X = -A + -12 + -C + -D = -12 + -A + -C + -D
00383   // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate
00384   // the constants.  We assume that instcombine will clean up the mess later if
00385   // we introduce tons of unnecessary negation instructions...
00386   //
00387   if (Instruction *I = dyn_cast<Instruction>(V))
00388     if (I->getOpcode() == Instruction::Add && I->hasOneUse()) {
00389       // Push the negates through the add.
00390       I->setOperand(0, NegateValue(Context, I->getOperand(0), BI));
00391       I->setOperand(1, NegateValue(Context, I->getOperand(1), BI));
00392 
00393       // We must move the add instruction here, because the neg instructions do
00394       // not dominate the old add instruction in general.  By moving it, we are
00395       // assured that the neg instructions we just inserted dominate the 
00396       // instruction we are about to insert after them.
00397       //
00398       I->moveBefore(BI);
00399       I->setName(I->getName()+".neg");
00400       return I;
00401     }
00402 
00403   // Insert a 'neg' instruction that subtracts the value from zero to get the
00404   // negation.
00405   //
00406   return BinaryOperator::CreateNeg(V, V->getName() + ".neg", BI);
00407 }
00408 
00409 /// ShouldBreakUpSubtract - Return true if we should break up this subtract of
00410 /// X-Y into (X + -Y).
00411 static bool ShouldBreakUpSubtract(LLVMContext &Context, Instruction *Sub) {
00412   // If this is a negation, we can't split it up!
00413   if (BinaryOperator::isNeg(Sub))
00414     return false;
00415   
00416   // Don't bother to break this up unless either the LHS is an associable add or
00417   // subtract or if this is only used by one.
00418   if (isReassociableOp(Sub->getOperand(0), Instruction::Add) ||
00419       isReassociableOp(Sub->getOperand(0), Instruction::Sub))
00420     return true;
00421   if (isReassociableOp(Sub->getOperand(1), Instruction::Add) ||
00422       isReassociableOp(Sub->getOperand(1), Instruction::Sub))
00423     return true;
00424   if (Sub->hasOneUse() && 
00425       (isReassociableOp(Sub->use_back(), Instruction::Add) ||
00426        isReassociableOp(Sub->use_back(), Instruction::Sub)))
00427     return true;
00428     
00429   return false;
00430 }
00431 
00432 /// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is
00433 /// only used by an add, transform this into (X+(0-Y)) to promote better
00434 /// reassociation.
00435 static Instruction *BreakUpSubtract(LLVMContext &Context, Instruction *Sub,
00436                               std::map<AssertingVH<>, unsigned> &ValueRankMap) {
00437   // Convert a subtract into an add and a neg instruction... so that sub
00438   // instructions can be commuted with other add instructions...
00439   //
00440   // Calculate the negative value of Operand 1 of the sub instruction...
00441   // and set it as the RHS of the add instruction we just made...
00442   //
00443   Value *NegVal = NegateValue(Context, Sub->getOperand(1), Sub);
00444   Instruction *New =
00445     BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub);
00446   New->takeName(Sub);
00447 
00448   // Everyone now refers to the add instruction.
00449   ValueRankMap.erase(Sub);
00450   Sub->replaceAllUsesWith(New);
00451   Sub->eraseFromParent();
00452 
00453   DOUT << "Negated: " << *New << '\n';
00454   return New;
00455 }
00456 
00457 /// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used
00458 /// by one, change this into a multiply by a constant to assist with further
00459 /// reassociation.
00460 static Instruction *ConvertShiftToMul(Instruction *Shl, 
00461                               std::map<AssertingVH<>, unsigned> &ValueRankMap,
00462                               LLVMContext &Context) {
00463   // If an operand of this shift is a reassociable multiply, or if the shift
00464   // is used by a reassociable multiply or add, turn into a multiply.
00465   if (isReassociableOp(Shl->getOperand(0), Instruction::Mul) ||
00466       (Shl->hasOneUse() && 
00467        (isReassociableOp(Shl->use_back(), Instruction::Mul) ||
00468         isReassociableOp(Shl->use_back(), Instruction::Add)))) {
00469     Constant *MulCst = ConstantInt::get(Shl->getType(), 1);
00470     MulCst =
00471         ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1)));
00472     
00473     Instruction *Mul = BinaryOperator::CreateMul(Shl->getOperand(0), MulCst,
00474                                                  "", Shl);
00475     ValueRankMap.erase(Shl);
00476     Mul->takeName(Shl);
00477     Shl->replaceAllUsesWith(Mul);
00478     Shl->eraseFromParent();
00479     return Mul;
00480   }
00481   return 0;
00482 }
00483 
00484 // Scan backwards and forwards among values with the same rank as element i to
00485 // see if X exists.  If X does not exist, return i.
00486 static unsigned FindInOperandList(std::vector<ValueEntry> &Ops, unsigned i,
00487                                   Value *X) {
00488   unsigned XRank = Ops[i].Rank;
00489   unsigned e = Ops.size();
00490   for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j)
00491     if (Ops[j].Op == X)
00492       return j;
00493   // Scan backwards
00494   for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j)
00495     if (Ops[j].Op == X)
00496       return j;
00497   return i;
00498 }
00499 
00500 /// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together
00501 /// and returning the result.  Insert the tree before I.
00502 static Value *EmitAddTreeOfValues(Instruction *I, std::vector<Value*> &Ops) {
00503   if (Ops.size() == 1) return Ops.back();
00504   
00505   Value *V1 = Ops.back();
00506   Ops.pop_back();
00507   Value *V2 = EmitAddTreeOfValues(I, Ops);
00508   return BinaryOperator::CreateAdd(V2, V1, "tmp", I);
00509 }
00510 
00511 /// RemoveFactorFromExpression - If V is an expression tree that is a 
00512 /// multiplication sequence, and if this sequence contains a multiply by Factor,
00513 /// remove Factor from the tree and return the new tree.
00514 Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) {
00515   BinaryOperator *BO = isReassociableOp(V, Instruction::Mul);
00516   if (!BO) return 0;
00517   
00518   std::vector<ValueEntry> Factors;
00519   LinearizeExprTree(BO, Factors);
00520 
00521   bool FoundFactor = false;
00522   for (unsigned i = 0, e = Factors.size(); i != e; ++i)
00523     if (Factors[i].Op == Factor) {
00524       FoundFactor = true;
00525       Factors.erase(Factors.begin()+i);
00526       break;
00527     }
00528   if (!FoundFactor) {
00529     // Make sure to restore the operands to the expression tree.
00530     RewriteExprTree(BO, Factors);
00531     return 0;
00532   }
00533   
00534   if (Factors.size() == 1) return Factors[0].Op;
00535   
00536   RewriteExprTree(BO, Factors);
00537   return BO;
00538 }
00539 
00540 /// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively
00541 /// add its operands as factors, otherwise add V to the list of factors.
00542 static void FindSingleUseMultiplyFactors(Value *V,
00543                                          std::vector<Value*> &Factors) {
00544   BinaryOperator *BO;
00545   if ((!V->hasOneUse() && !V->use_empty()) ||
00546       !(BO = dyn_cast<BinaryOperator>(V)) ||
00547       BO->getOpcode() != Instruction::Mul) {
00548     Factors.push_back(V);
00549     return;
00550   }
00551   
00552   // Otherwise, add the LHS and RHS to the list of factors.
00553   FindSingleUseMultiplyFactors(BO->getOperand(1), Factors);
00554   FindSingleUseMultiplyFactors(BO->getOperand(0), Factors);
00555 }
00556 
00557 
00558 
00559 Value *Reassociate::OptimizeExpression(BinaryOperator *I,
00560                                        std::vector<ValueEntry> &Ops) {
00561   // Now that we have the linearized expression tree, try to optimize it.
00562   // Start by folding any constants that we found.
00563   bool IterateOptimization = false;
00564   if (Ops.size() == 1) return Ops[0].Op;
00565 
00566   unsigned Opcode = I->getOpcode();
00567   
00568   if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op))
00569     if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) {
00570       Ops.pop_back();
00571       Ops.back().Op = ConstantExpr::get(Opcode, V1, V2);
00572       return OptimizeExpression(I, Ops);
00573     }
00574 
00575   // Check for destructive annihilation due to a constant being used.
00576   if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op))
00577     switch (Opcode) {
00578     default: break;
00579     case Instruction::And:
00580       if (CstVal->isZero()) {                // ... & 0 -> 0
00581         ++NumAnnihil;
00582         return CstVal;
00583       } else if (CstVal->isAllOnesValue()) { // ... & -1 -> ...
00584         Ops.pop_back();
00585       }
00586       break;
00587     case Instruction::Mul:
00588       if (CstVal->isZero()) {                // ... * 0 -> 0
00589         ++NumAnnihil;
00590         return CstVal;
00591       } else if (cast<ConstantInt>(CstVal)->isOne()) {
00592         Ops.pop_back();                      // ... * 1 -> ...
00593       }
00594       break;
00595     case Instruction::Or:
00596       if (CstVal->isAllOnesValue()) {        // ... | -1 -> -1
00597         ++NumAnnihil;
00598         return CstVal;
00599       }
00600       // FALLTHROUGH!
00601     case Instruction::Add:
00602     case Instruction::Xor:
00603       if (CstVal->isZero())                  // ... [|^+] 0 -> ...
00604         Ops.pop_back();
00605       break;
00606     }
00607   if (Ops.size() == 1) return Ops[0].Op;
00608 
00609   // Handle destructive annihilation do to identities between elements in the
00610   // argument list here.
00611   switch (Opcode) {
00612   default: break;
00613   case Instruction::And:
00614   case Instruction::Or:
00615   case Instruction::Xor:
00616     // Scan the operand lists looking for X and ~X pairs, along with X,X pairs.
00617     // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1.
00618     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
00619       // First, check for X and ~X in the operand list.
00620       assert(i < Ops.size());
00621       if (BinaryOperator::isNot(Ops[i].Op)) {    // Cannot occur for ^.
00622         Value *X = BinaryOperator::getNotArgument(Ops[i].Op);
00623         unsigned FoundX = FindInOperandList(Ops, i, X);
00624         if (FoundX != i) {
00625           if (Opcode == Instruction::And) {   // ...&X&~X = 0
00626             ++NumAnnihil;
00627             return Constant::getNullValue(X->getType());
00628           } else if (Opcode == Instruction::Or) {   // ...|X|~X = -1
00629             ++NumAnnihil;
00630             return Constant::getAllOnesValue(X->getType());
00631           }
00632         }
00633       }
00634 
00635       // Next, check for duplicate pairs of values, which we assume are next to
00636       // each other, due to our sorting criteria.
00637       assert(i < Ops.size());
00638       if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) {
00639         if (Opcode == Instruction::And || Opcode == Instruction::Or) {
00640           // Drop duplicate values.
00641           Ops.erase(Ops.begin()+i);
00642           --i; --e;
00643           IterateOptimization = true;
00644           ++NumAnnihil;
00645         } else {
00646           assert(Opcode == Instruction::Xor);
00647           if (e == 2) {
00648             ++NumAnnihil;
00649             return Constant::getNullValue(Ops[0].Op->getType());
00650           }
00651           // ... X^X -> ...
00652           Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
00653           i -= 1; e -= 2;
00654           IterateOptimization = true;
00655           ++NumAnnihil;
00656         }
00657       }
00658     }
00659     break;
00660 
00661   case Instruction::Add:
00662     // Scan the operand lists looking for X and -X pairs.  If we find any, we
00663     // can simplify the expression. X+-X == 0.
00664     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
00665       assert(i < Ops.size());
00666       // Check for X and -X in the operand list.
00667       if (BinaryOperator::isNeg(Ops[i].Op)) {
00668         Value *X = BinaryOperator::getNegArgument(Ops[i].Op);
00669         unsigned FoundX = FindInOperandList(Ops, i, X);
00670         if (FoundX != i) {
00671           // Remove X and -X from the operand list.
00672           if (Ops.size() == 2) {
00673             ++NumAnnihil;
00674             return Constant::getNullValue(X->getType());
00675           } else {
00676             Ops.erase(Ops.begin()+i);
00677             if (i < FoundX)
00678               --FoundX;
00679             else
00680               --i;   // Need to back up an extra one.
00681             Ops.erase(Ops.begin()+FoundX);
00682             IterateOptimization = true;
00683             ++NumAnnihil;
00684             --i;     // Revisit element.
00685             e -= 2;  // Removed two elements.
00686           }
00687         }
00688       }
00689     }
00690     
00691 
00692     // Scan the operand list, checking to see if there are any common factors
00693     // between operands.  Consider something like A*A+A*B*C+D.  We would like to
00694     // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies.
00695     // To efficiently find this, we count the number of times a factor occurs
00696     // for any ADD operands that are MULs.
00697     std::map<Value*, unsigned> FactorOccurrences;
00698     unsigned MaxOcc = 0;
00699     Value *MaxOccVal = 0;
00700     for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
00701       if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op)) {
00702         if (BOp->getOpcode() == Instruction::Mul && BOp->use_empty()) {
00703           // Compute all of the factors of this added value.
00704           std::vector<Value*> Factors;
00705           FindSingleUseMultiplyFactors(BOp, Factors);
00706           assert(Factors.size() > 1 && "Bad linearize!");
00707 
00708           // Add one to FactorOccurrences for each unique factor in this op.
00709           if (Factors.size() == 2) {
00710             unsigned Occ = ++FactorOccurrences[Factors[0]];
00711             if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[0]; }
00712             if (Factors[0] != Factors[1]) {   // Don't double count A*A.
00713               Occ = ++FactorOccurrences[Factors[1]];
00714               if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[1]; }
00715             }
00716           } else {
00717             std::set<Value*> Duplicates;
00718             for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
00719               if (Duplicates.insert(Factors[i]).second) {
00720                 unsigned Occ = ++FactorOccurrences[Factors[i]];
00721                 if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factors[i]; }
00722               }
00723             }
00724           }
00725         }
00726       }
00727     }
00728 
00729     // If any factor occurred more than one time, we can pull it out.
00730     if (MaxOcc > 1) {
00731       DOUT << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << "\n";
00732       
00733       // Create a new instruction that uses the MaxOccVal twice.  If we don't do
00734       // this, we could otherwise run into situations where removing a factor
00735       // from an expression will drop a use of maxocc, and this can cause 
00736       // RemoveFactorFromExpression on successive values to behave differently.
00737       Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal);
00738       std::vector<Value*> NewMulOps;
00739       for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
00740         if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) {
00741           NewMulOps.push_back(V);
00742           Ops.erase(Ops.begin()+i);
00743           --i; --e;
00744         }
00745       }
00746       
00747       // No need for extra uses anymore.
00748       delete DummyInst;
00749 
00750       unsigned NumAddedValues = NewMulOps.size();
00751       Value *V = EmitAddTreeOfValues(I, NewMulOps);
00752       Value *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I);
00753 
00754       // Now that we have inserted V and its sole use, optimize it. This allows
00755       // us to handle cases that require multiple factoring steps, such as this:
00756       // A*A*B + A*A*C   -->   A*(A*B+A*C)   -->   A*(A*(B+C))
00757       if (NumAddedValues > 1)
00758         ReassociateExpression(cast<BinaryOperator>(V));
00759       
00760       ++NumFactor;
00761       
00762       if (Ops.empty())
00763         return V2;
00764 
00765       // Add the new value to the list of things being added.
00766       Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2));
00767       
00768       // Rewrite the tree so that there is now a use of V.
00769       RewriteExprTree(I, Ops);
00770       return OptimizeExpression(I, Ops);
00771     }
00772     break;
00773   //case Instruction::Mul:
00774   }
00775 
00776   if (IterateOptimization)
00777     return OptimizeExpression(I, Ops);
00778   return 0;
00779 }
00780 
00781 
00782 /// ReassociateBB - Inspect all of the instructions in this basic block,
00783 /// reassociating them as we go.
00784 void Reassociate::ReassociateBB(BasicBlock *BB) {
00785   LLVMContext &Context = BB->getContext();
00786   
00787   for (BasicBlock::iterator BBI = BB->begin(); BBI != BB->end(); ) {
00788     Instruction *BI = BBI++;
00789     if (BI->getOpcode() == Instruction::Shl &&
00790         isa<ConstantInt>(BI->getOperand(1)))
00791       if (Instruction *NI = ConvertShiftToMul(BI, ValueRankMap, Context)) {
00792         MadeChange = true;
00793         BI = NI;
00794       }
00795 
00796     // Reject cases where it is pointless to do this.
00797     if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPoint() || 
00798         isa<VectorType>(BI->getType()))
00799       continue;  // Floating point ops are not associative.
00800 
00801     // If this is a subtract instruction which is not already in negate form,
00802     // see if we can convert it to X+-Y.
00803     if (BI->getOpcode() == Instruction::Sub) {
00804       if (ShouldBreakUpSubtract(Context, BI)) {
00805         BI = BreakUpSubtract(Context, BI, ValueRankMap);
00806         MadeChange = true;
00807       } else if (BinaryOperator::isNeg(BI)) {
00808         // Otherwise, this is a negation.  See if the operand is a multiply tree
00809         // and if this is not an inner node of a multiply tree.
00810         if (isReassociableOp(BI->getOperand(1), Instruction::Mul) &&
00811             (!BI->hasOneUse() ||
00812              !isReassociableOp(BI->use_back(), Instruction::Mul))) {
00813           BI = LowerNegateToMultiply(BI, ValueRankMap, Context);
00814           MadeChange = true;
00815         }
00816       }
00817     }
00818 
00819     // If this instruction is a commutative binary operator, process it.
00820     if (!BI->isAssociative()) continue;
00821     BinaryOperator *I = cast<BinaryOperator>(BI);
00822 
00823     // If this is an interior node of a reassociable tree, ignore it until we
00824     // get to the root of the tree, to avoid N^2 analysis.
00825     if (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode()))
00826       continue;
00827 
00828     // If this is an add tree that is used by a sub instruction, ignore it 
00829     // until we process the subtract.
00830     if (I->hasOneUse() && I->getOpcode() == Instruction::Add &&
00831         cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub)
00832       continue;
00833 
00834     ReassociateExpression(I);
00835   }
00836 }
00837 
00838 void Reassociate::ReassociateExpression(BinaryOperator *I) {
00839   
00840   // First, walk the expression tree, linearizing the tree, collecting
00841   std::vector<ValueEntry> Ops;
00842   LinearizeExprTree(I, Ops);
00843   
00844   DOUT << "RAIn:\t"; DEBUG(PrintOps(I, Ops)); DOUT << "\n";
00845   
00846   // Now that we have linearized the tree to a list and have gathered all of
00847   // the operands and their ranks, sort the operands by their rank.  Use a
00848   // stable_sort so that values with equal ranks will have their relative
00849   // positions maintained (and so the compiler is deterministic).  Note that
00850   // this sorts so that the highest ranking values end up at the beginning of
00851   // the vector.
00852   std::stable_sort(Ops.begin(), Ops.end());
00853   
00854   // OptimizeExpression - Now that we have the expression tree in a convenient
00855   // sorted form, optimize it globally if possible.
00856   if (Value *V = OptimizeExpression(I, Ops)) {
00857     // This expression tree simplified to something that isn't a tree,
00858     // eliminate it.
00859     DOUT << "Reassoc to scalar: " << *V << "\n";
00860     I->replaceAllUsesWith(V);
00861     RemoveDeadBinaryOp(I);
00862     return;
00863   }
00864   
00865   // We want to sink immediates as deeply as possible except in the case where
00866   // this is a multiply tree used only by an add, and the immediate is a -1.
00867   // In this case we reassociate to put the negation on the outside so that we
00868   // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y
00869   if (I->getOpcode() == Instruction::Mul && I->hasOneUse() &&
00870       cast<Instruction>(I->use_back())->getOpcode() == Instruction::Add &&
00871       isa<ConstantInt>(Ops.back().Op) &&
00872       cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) {
00873     Ops.insert(Ops.begin(), Ops.back());
00874     Ops.pop_back();
00875   }
00876   
00877   DOUT << "RAOut:\t"; DEBUG(PrintOps(I, Ops)); DOUT << "\n";
00878   
00879   if (Ops.size() == 1) {
00880     // This expression tree simplified to something that isn't a tree,
00881     // eliminate it.
00882     I->replaceAllUsesWith(Ops[0].Op);
00883     RemoveDeadBinaryOp(I);
00884   } else {
00885     // Now that we ordered and optimized the expressions, splat them back into
00886     // the expression tree, removing any unneeded nodes.
00887     RewriteExprTree(I, Ops);
00888   }
00889 }
00890 
00891 
00892 bool Reassociate::runOnFunction(Function &F) {
00893   // Recalculate the rank map for F
00894   BuildRankMap(F);
00895 
00896   MadeChange = false;
00897   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
00898     ReassociateBB(FI);
00899 
00900   // We are done with the rank map...
00901   RankMap.clear();
00902   ValueRankMap.clear();
00903   return MadeChange;
00904 }
00905