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, etc.
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 #include "llvm/Transforms/Scalar.h"
00024 #include "llvm/ADT/DenseMap.h"
00025 #include "llvm/ADT/PostOrderIterator.h"
00026 #include "llvm/ADT/STLExtras.h"
00027 #include "llvm/ADT/SetVector.h"
00028 #include "llvm/ADT/Statistic.h"
00029 #include "llvm/IR/CFG.h"
00030 #include "llvm/IR/Constants.h"
00031 #include "llvm/IR/DerivedTypes.h"
00032 #include "llvm/IR/Function.h"
00033 #include "llvm/IR/IRBuilder.h"
00034 #include "llvm/IR/Instructions.h"
00035 #include "llvm/IR/IntrinsicInst.h"
00036 #include "llvm/IR/ValueHandle.h"
00037 #include "llvm/Pass.h"
00038 #include "llvm/Support/Debug.h"
00039 #include "llvm/Support/raw_ostream.h"
00040 #include "llvm/Transforms/Utils/Local.h"
00041 #include <algorithm>
00042 using namespace llvm;
00043 
00044 #define DEBUG_TYPE "reassociate"
00045 
00046 STATISTIC(NumChanged, "Number of insts reassociated");
00047 STATISTIC(NumAnnihil, "Number of expr tree annihilated");
00048 STATISTIC(NumFactor , "Number of multiplies factored");
00049 
00050 namespace {
00051   struct ValueEntry {
00052     unsigned Rank;
00053     Value *Op;
00054     ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
00055   };
00056   inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
00057     return LHS.Rank > RHS.Rank;   // Sort so that highest rank goes to start.
00058   }
00059 }
00060 
00061 #ifndef NDEBUG
00062 /// PrintOps - Print out the expression identified in the Ops list.
00063 ///
00064 static void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) {
00065   Module *M = I->getParent()->getParent()->getParent();
00066   dbgs() << Instruction::getOpcodeName(I->getOpcode()) << " "
00067        << *Ops[0].Op->getType() << '\t';
00068   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
00069     dbgs() << "[ ";
00070     Ops[i].Op->printAsOperand(dbgs(), false, M);
00071     dbgs() << ", #" << Ops[i].Rank << "] ";
00072   }
00073 }
00074 #endif
00075 
00076 namespace {
00077   /// \brief Utility class representing a base and exponent pair which form one
00078   /// factor of some product.
00079   struct Factor {
00080     Value *Base;
00081     unsigned Power;
00082 
00083     Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {}
00084 
00085     /// \brief Sort factors by their Base.
00086     struct BaseSorter {
00087       bool operator()(const Factor &LHS, const Factor &RHS) {
00088         return LHS.Base < RHS.Base;
00089       }
00090     };
00091 
00092     /// \brief Compare factors for equal bases.
00093     struct BaseEqual {
00094       bool operator()(const Factor &LHS, const Factor &RHS) {
00095         return LHS.Base == RHS.Base;
00096       }
00097     };
00098 
00099     /// \brief Sort factors in descending order by their power.
00100     struct PowerDescendingSorter {
00101       bool operator()(const Factor &LHS, const Factor &RHS) {
00102         return LHS.Power > RHS.Power;
00103       }
00104     };
00105 
00106     /// \brief Compare factors for equal powers.
00107     struct PowerEqual {
00108       bool operator()(const Factor &LHS, const Factor &RHS) {
00109         return LHS.Power == RHS.Power;
00110       }
00111     };
00112   };
00113   
00114   /// Utility class representing a non-constant Xor-operand. We classify
00115   /// non-constant Xor-Operands into two categories:
00116   ///  C1) The operand is in the form "X & C", where C is a constant and C != ~0
00117   ///  C2)
00118   ///    C2.1) The operand is in the form of "X | C", where C is a non-zero
00119   ///          constant.
00120   ///    C2.2) Any operand E which doesn't fall into C1 and C2.1, we view this
00121   ///          operand as "E | 0"
00122   class XorOpnd {
00123   public:
00124     XorOpnd(Value *V);
00125 
00126     bool isInvalid() const { return SymbolicPart == nullptr; }
00127     bool isOrExpr() const { return isOr; }
00128     Value *getValue() const { return OrigVal; }
00129     Value *getSymbolicPart() const { return SymbolicPart; }
00130     unsigned getSymbolicRank() const { return SymbolicRank; }
00131     const APInt &getConstPart() const { return ConstPart; }
00132 
00133     void Invalidate() { SymbolicPart = OrigVal = nullptr; }
00134     void setSymbolicRank(unsigned R) { SymbolicRank = R; }
00135 
00136     // Sort the XorOpnd-Pointer in ascending order of symbolic-value-rank.
00137     // The purpose is twofold:
00138     // 1) Cluster together the operands sharing the same symbolic-value.
00139     // 2) Operand having smaller symbolic-value-rank is permuted earlier, which 
00140     //   could potentially shorten crital path, and expose more loop-invariants.
00141     //   Note that values' rank are basically defined in RPO order (FIXME). 
00142     //   So, if Rank(X) < Rank(Y) < Rank(Z), it means X is defined earlier 
00143     //   than Y which is defined earlier than Z. Permute "x | 1", "Y & 2",
00144     //   "z" in the order of X-Y-Z is better than any other orders.
00145     struct PtrSortFunctor {
00146       bool operator()(XorOpnd * const &LHS, XorOpnd * const &RHS) {
00147         return LHS->getSymbolicRank() < RHS->getSymbolicRank();
00148       }
00149     };
00150   private:
00151     Value *OrigVal;
00152     Value *SymbolicPart;
00153     APInt ConstPart;
00154     unsigned SymbolicRank;
00155     bool isOr;
00156   };
00157 }
00158 
00159 namespace {
00160   class Reassociate : public FunctionPass {
00161     DenseMap<BasicBlock*, unsigned> RankMap;
00162     DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
00163     SetVector<AssertingVH<Instruction> > RedoInsts;
00164     bool MadeChange;
00165   public:
00166     static char ID; // Pass identification, replacement for typeid
00167     Reassociate() : FunctionPass(ID) {
00168       initializeReassociatePass(*PassRegistry::getPassRegistry());
00169     }
00170 
00171     bool runOnFunction(Function &F) override;
00172 
00173     void getAnalysisUsage(AnalysisUsage &AU) const override {
00174       AU.setPreservesCFG();
00175     }
00176   private:
00177     void BuildRankMap(Function &F);
00178     unsigned getRank(Value *V);
00179     void ReassociateExpression(BinaryOperator *I);
00180     void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
00181     Value *OptimizeExpression(BinaryOperator *I,
00182                               SmallVectorImpl<ValueEntry> &Ops);
00183     Value *OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops);
00184     Value *OptimizeXor(Instruction *I, SmallVectorImpl<ValueEntry> &Ops);
00185     bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, APInt &ConstOpnd,
00186                         Value *&Res);
00187     bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2,
00188                         APInt &ConstOpnd, Value *&Res);
00189     bool collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops,
00190                                 SmallVectorImpl<Factor> &Factors);
00191     Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
00192                                    SmallVectorImpl<Factor> &Factors);
00193     Value *OptimizeMul(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
00194     Value *RemoveFactorFromExpression(Value *V, Value *Factor);
00195     void EraseInst(Instruction *I);
00196     void optimizeFAddNegExpr(ConstantFP *ConstOperand, Instruction *I,
00197                              int OperandNr);
00198     void OptimizeInst(Instruction *I);
00199   };
00200 }
00201 
00202 XorOpnd::XorOpnd(Value *V) {
00203   assert(!isa<ConstantInt>(V) && "No ConstantInt");
00204   OrigVal = V;
00205   Instruction *I = dyn_cast<Instruction>(V);
00206   SymbolicRank = 0;
00207 
00208   if (I && (I->getOpcode() == Instruction::Or ||
00209             I->getOpcode() == Instruction::And)) {
00210     Value *V0 = I->getOperand(0);
00211     Value *V1 = I->getOperand(1);
00212     if (isa<ConstantInt>(V0))
00213       std::swap(V0, V1);
00214 
00215     if (ConstantInt *C = dyn_cast<ConstantInt>(V1)) {
00216       ConstPart = C->getValue();
00217       SymbolicPart = V0;
00218       isOr = (I->getOpcode() == Instruction::Or);
00219       return;
00220     }
00221   }
00222 
00223   // view the operand as "V | 0"
00224   SymbolicPart = V;
00225   ConstPart = APInt::getNullValue(V->getType()->getIntegerBitWidth());
00226   isOr = true;
00227 }
00228 
00229 char Reassociate::ID = 0;
00230 INITIALIZE_PASS(Reassociate, "reassociate",
00231                 "Reassociate expressions", false, false)
00232 
00233 // Public interface to the Reassociate pass
00234 FunctionPass *llvm::createReassociatePass() { return new Reassociate(); }
00235 
00236 /// isReassociableOp - Return true if V is an instruction of the specified
00237 /// opcode and if it only has one use.
00238 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) {
00239   if (V->hasOneUse() && isa<Instruction>(V) &&
00240       cast<Instruction>(V)->getOpcode() == Opcode)
00241     return cast<BinaryOperator>(V);
00242   return nullptr;
00243 }
00244 
00245 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode1,
00246                                         unsigned Opcode2) {
00247   if (V->hasOneUse() && isa<Instruction>(V) &&
00248       (cast<Instruction>(V)->getOpcode() == Opcode1 ||
00249        cast<Instruction>(V)->getOpcode() == Opcode2))
00250     return cast<BinaryOperator>(V);
00251   return nullptr;
00252 }
00253 
00254 static bool isUnmovableInstruction(Instruction *I) {
00255   switch (I->getOpcode()) {
00256   case Instruction::PHI:
00257   case Instruction::LandingPad:
00258   case Instruction::Alloca:
00259   case Instruction::Load:
00260   case Instruction::Invoke:
00261   case Instruction::UDiv:
00262   case Instruction::SDiv:
00263   case Instruction::FDiv:
00264   case Instruction::URem:
00265   case Instruction::SRem:
00266   case Instruction::FRem:
00267     return true;
00268   case Instruction::Call:
00269     return !isa<DbgInfoIntrinsic>(I);
00270   default:
00271     return false;
00272   }
00273 }
00274 
00275 void Reassociate::BuildRankMap(Function &F) {
00276   unsigned i = 2;
00277 
00278   // Assign distinct ranks to function arguments
00279   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
00280     ValueRankMap[&*I] = ++i;
00281 
00282   ReversePostOrderTraversal<Function*> RPOT(&F);
00283   for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
00284          E = RPOT.end(); I != E; ++I) {
00285     BasicBlock *BB = *I;
00286     unsigned BBRank = RankMap[BB] = ++i << 16;
00287 
00288     // Walk the basic block, adding precomputed ranks for any instructions that
00289     // we cannot move.  This ensures that the ranks for these instructions are
00290     // all different in the block.
00291     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
00292       if (isUnmovableInstruction(I))
00293         ValueRankMap[&*I] = ++BBRank;
00294   }
00295 }
00296 
00297 unsigned Reassociate::getRank(Value *V) {
00298   Instruction *I = dyn_cast<Instruction>(V);
00299   if (!I) {
00300     if (isa<Argument>(V)) return ValueRankMap[V];   // Function argument.
00301     return 0;  // Otherwise it's a global or constant, rank 0.
00302   }
00303 
00304   if (unsigned Rank = ValueRankMap[I])
00305     return Rank;    // Rank already known?
00306 
00307   // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that
00308   // we can reassociate expressions for code motion!  Since we do not recurse
00309   // for PHI nodes, we cannot have infinite recursion here, because there
00310   // cannot be loops in the value graph that do not go through PHI nodes.
00311   unsigned Rank = 0, MaxRank = RankMap[I->getParent()];
00312   for (unsigned i = 0, e = I->getNumOperands();
00313        i != e && Rank != MaxRank; ++i)
00314     Rank = std::max(Rank, getRank(I->getOperand(i)));
00315 
00316   // If this is a not or neg instruction, do not count it for rank.  This
00317   // assures us that X and ~X will have the same rank.
00318   Type *Ty = V->getType();
00319   if ((!Ty->isIntegerTy() && !Ty->isFloatingPointTy()) ||
00320       (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I) &&
00321        !BinaryOperator::isFNeg(I)))
00322     ++Rank;
00323 
00324   //DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = "
00325   //     << Rank << "\n");
00326 
00327   return ValueRankMap[I] = Rank;
00328 }
00329 
00330 static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name,
00331                                  Instruction *InsertBefore, Value *FlagsOp) {
00332   if (S1->getType()->isIntegerTy())
00333     return BinaryOperator::CreateAdd(S1, S2, Name, InsertBefore);
00334   else {
00335     BinaryOperator *Res =
00336         BinaryOperator::CreateFAdd(S1, S2, Name, InsertBefore);
00337     Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags());
00338     return Res;
00339   }
00340 }
00341 
00342 static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name,
00343                                  Instruction *InsertBefore, Value *FlagsOp) {
00344   if (S1->getType()->isIntegerTy())
00345     return BinaryOperator::CreateMul(S1, S2, Name, InsertBefore);
00346   else {
00347     BinaryOperator *Res =
00348       BinaryOperator::CreateFMul(S1, S2, Name, InsertBefore);
00349     Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags());
00350     return Res;
00351   }
00352 }
00353 
00354 static BinaryOperator *CreateNeg(Value *S1, const Twine &Name,
00355                                  Instruction *InsertBefore, Value *FlagsOp) {
00356   if (S1->getType()->isIntegerTy())
00357     return BinaryOperator::CreateNeg(S1, Name, InsertBefore);
00358   else {
00359     BinaryOperator *Res = BinaryOperator::CreateFNeg(S1, Name, InsertBefore);
00360     Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags());
00361     return Res;
00362   }
00363 }
00364 
00365 /// LowerNegateToMultiply - Replace 0-X with X*-1.
00366 ///
00367 static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) {
00368   Type *Ty = Neg->getType();
00369   Constant *NegOne = Ty->isIntegerTy() ? ConstantInt::getAllOnesValue(Ty)
00370                                        : ConstantFP::get(Ty, -1.0);
00371 
00372   BinaryOperator *Res = CreateMul(Neg->getOperand(1), NegOne, "", Neg, Neg);
00373   Neg->setOperand(1, Constant::getNullValue(Ty)); // Drop use of op.
00374   Res->takeName(Neg);
00375   Neg->replaceAllUsesWith(Res);
00376   Res->setDebugLoc(Neg->getDebugLoc());
00377   return Res;
00378 }
00379 
00380 /// CarmichaelShift - Returns k such that lambda(2^Bitwidth) = 2^k, where lambda
00381 /// is the Carmichael function. This means that x^(2^k) === 1 mod 2^Bitwidth for
00382 /// every odd x, i.e. x^(2^k) = 1 for every odd x in Bitwidth-bit arithmetic.
00383 /// Note that 0 <= k < Bitwidth, and if Bitwidth > 3 then x^(2^k) = 0 for every
00384 /// even x in Bitwidth-bit arithmetic.
00385 static unsigned CarmichaelShift(unsigned Bitwidth) {
00386   if (Bitwidth < 3)
00387     return Bitwidth - 1;
00388   return Bitwidth - 2;
00389 }
00390 
00391 /// IncorporateWeight - Add the extra weight 'RHS' to the existing weight 'LHS',
00392 /// reducing the combined weight using any special properties of the operation.
00393 /// The existing weight LHS represents the computation X op X op ... op X where
00394 /// X occurs LHS times.  The combined weight represents  X op X op ... op X with
00395 /// X occurring LHS + RHS times.  If op is "Xor" for example then the combined
00396 /// operation is equivalent to X if LHS + RHS is odd, or 0 if LHS + RHS is even;
00397 /// the routine returns 1 in LHS in the first case, and 0 in LHS in the second.
00398 static void IncorporateWeight(APInt &LHS, const APInt &RHS, unsigned Opcode) {
00399   // If we were working with infinite precision arithmetic then the combined
00400   // weight would be LHS + RHS.  But we are using finite precision arithmetic,
00401   // and the APInt sum LHS + RHS may not be correct if it wraps (it is correct
00402   // for nilpotent operations and addition, but not for idempotent operations
00403   // and multiplication), so it is important to correctly reduce the combined
00404   // weight back into range if wrapping would be wrong.
00405 
00406   // If RHS is zero then the weight didn't change.
00407   if (RHS.isMinValue())
00408     return;
00409   // If LHS is zero then the combined weight is RHS.
00410   if (LHS.isMinValue()) {
00411     LHS = RHS;
00412     return;
00413   }
00414   // From this point on we know that neither LHS nor RHS is zero.
00415 
00416   if (Instruction::isIdempotent(Opcode)) {
00417     // Idempotent means X op X === X, so any non-zero weight is equivalent to a
00418     // weight of 1.  Keeping weights at zero or one also means that wrapping is
00419     // not a problem.
00420     assert(LHS == 1 && RHS == 1 && "Weights not reduced!");
00421     return; // Return a weight of 1.
00422   }
00423   if (Instruction::isNilpotent(Opcode)) {
00424     // Nilpotent means X op X === 0, so reduce weights modulo 2.
00425     assert(LHS == 1 && RHS == 1 && "Weights not reduced!");
00426     LHS = 0; // 1 + 1 === 0 modulo 2.
00427     return;
00428   }
00429   if (Opcode == Instruction::Add || Opcode == Instruction::FAdd) {
00430     // TODO: Reduce the weight by exploiting nsw/nuw?
00431     LHS += RHS;
00432     return;
00433   }
00434 
00435   assert((Opcode == Instruction::Mul || Opcode == Instruction::FMul) &&
00436          "Unknown associative operation!");
00437   unsigned Bitwidth = LHS.getBitWidth();
00438   // If CM is the Carmichael number then a weight W satisfying W >= CM+Bitwidth
00439   // can be replaced with W-CM.  That's because x^W=x^(W-CM) for every Bitwidth
00440   // bit number x, since either x is odd in which case x^CM = 1, or x is even in
00441   // which case both x^W and x^(W - CM) are zero.  By subtracting off multiples
00442   // of CM like this weights can always be reduced to the range [0, CM+Bitwidth)
00443   // which by a happy accident means that they can always be represented using
00444   // Bitwidth bits.
00445   // TODO: Reduce the weight by exploiting nsw/nuw?  (Could do much better than
00446   // the Carmichael number).
00447   if (Bitwidth > 3) {
00448     /// CM - The value of Carmichael's lambda function.
00449     APInt CM = APInt::getOneBitSet(Bitwidth, CarmichaelShift(Bitwidth));
00450     // Any weight W >= Threshold can be replaced with W - CM.
00451     APInt Threshold = CM + Bitwidth;
00452     assert(LHS.ult(Threshold) && RHS.ult(Threshold) && "Weights not reduced!");
00453     // For Bitwidth 4 or more the following sum does not overflow.
00454     LHS += RHS;
00455     while (LHS.uge(Threshold))
00456       LHS -= CM;
00457   } else {
00458     // To avoid problems with overflow do everything the same as above but using
00459     // a larger type.
00460     unsigned CM = 1U << CarmichaelShift(Bitwidth);
00461     unsigned Threshold = CM + Bitwidth;
00462     assert(LHS.getZExtValue() < Threshold && RHS.getZExtValue() < Threshold &&
00463            "Weights not reduced!");
00464     unsigned Total = LHS.getZExtValue() + RHS.getZExtValue();
00465     while (Total >= Threshold)
00466       Total -= CM;
00467     LHS = Total;
00468   }
00469 }
00470 
00471 typedef std::pair<Value*, APInt> RepeatedValue;
00472 
00473 /// LinearizeExprTree - Given an associative binary expression, return the leaf
00474 /// nodes in Ops along with their weights (how many times the leaf occurs).  The
00475 /// original expression is the same as
00476 ///   (Ops[0].first op Ops[0].first op ... Ops[0].first)  <- Ops[0].second times
00477 /// op
00478 ///   (Ops[1].first op Ops[1].first op ... Ops[1].first)  <- Ops[1].second times
00479 /// op
00480 ///   ...
00481 /// op
00482 ///   (Ops[N].first op Ops[N].first op ... Ops[N].first)  <- Ops[N].second times
00483 ///
00484 /// Note that the values Ops[0].first, ..., Ops[N].first are all distinct.
00485 ///
00486 /// This routine may modify the function, in which case it returns 'true'.  The
00487 /// changes it makes may well be destructive, changing the value computed by 'I'
00488 /// to something completely different.  Thus if the routine returns 'true' then
00489 /// you MUST either replace I with a new expression computed from the Ops array,
00490 /// or use RewriteExprTree to put the values back in.
00491 ///
00492 /// A leaf node is either not a binary operation of the same kind as the root
00493 /// node 'I' (i.e. is not a binary operator at all, or is, but with a different
00494 /// opcode), or is the same kind of binary operator but has a use which either
00495 /// does not belong to the expression, or does belong to the expression but is
00496 /// a leaf node.  Every leaf node has at least one use that is a non-leaf node
00497 /// of the expression, while for non-leaf nodes (except for the root 'I') every
00498 /// use is a non-leaf node of the expression.
00499 ///
00500 /// For example:
00501 ///           expression graph        node names
00502 ///
00503 ///                     +        |        I
00504 ///                    / \       |
00505 ///                   +   +      |      A,  B
00506 ///                  / \ / \     |
00507 ///                 *   +   *    |    C,  D,  E
00508 ///                / \ / \ / \   |
00509 ///                   +   *      |      F,  G
00510 ///
00511 /// The leaf nodes are C, E, F and G.  The Ops array will contain (maybe not in
00512 /// that order) (C, 1), (E, 1), (F, 2), (G, 2).
00513 ///
00514 /// The expression is maximal: if some instruction is a binary operator of the
00515 /// same kind as 'I', and all of its uses are non-leaf nodes of the expression,
00516 /// then the instruction also belongs to the expression, is not a leaf node of
00517 /// it, and its operands also belong to the expression (but may be leaf nodes).
00518 ///
00519 /// NOTE: This routine will set operands of non-leaf non-root nodes to undef in
00520 /// order to ensure that every non-root node in the expression has *exactly one*
00521 /// use by a non-leaf node of the expression.  This destruction means that the
00522 /// caller MUST either replace 'I' with a new expression or use something like
00523 /// RewriteExprTree to put the values back in if the routine indicates that it
00524 /// made a change by returning 'true'.
00525 ///
00526 /// In the above example either the right operand of A or the left operand of B
00527 /// will be replaced by undef.  If it is B's operand then this gives:
00528 ///
00529 ///                     +        |        I
00530 ///                    / \       |
00531 ///                   +   +      |      A,  B - operand of B replaced with undef
00532 ///                  / \   \     |
00533 ///                 *   +   *    |    C,  D,  E
00534 ///                / \ / \ / \   |
00535 ///                   +   *      |      F,  G
00536 ///
00537 /// Note that such undef operands can only be reached by passing through 'I'.
00538 /// For example, if you visit operands recursively starting from a leaf node
00539 /// then you will never see such an undef operand unless you get back to 'I',
00540 /// which requires passing through a phi node.
00541 ///
00542 /// Note that this routine may also mutate binary operators of the wrong type
00543 /// that have all uses inside the expression (i.e. only used by non-leaf nodes
00544 /// of the expression) if it can turn them into binary operators of the right
00545 /// type and thus make the expression bigger.
00546 
00547 static bool LinearizeExprTree(BinaryOperator *I,
00548                               SmallVectorImpl<RepeatedValue> &Ops) {
00549   DEBUG(dbgs() << "LINEARIZE: " << *I << '\n');
00550   unsigned Bitwidth = I->getType()->getScalarType()->getPrimitiveSizeInBits();
00551   unsigned Opcode = I->getOpcode();
00552   assert(I->isAssociative() && I->isCommutative() &&
00553          "Expected an associative and commutative operation!");
00554 
00555   // Visit all operands of the expression, keeping track of their weight (the
00556   // number of paths from the expression root to the operand, or if you like
00557   // the number of times that operand occurs in the linearized expression).
00558   // For example, if I = X + A, where X = A + B, then I, X and B have weight 1
00559   // while A has weight two.
00560 
00561   // Worklist of non-leaf nodes (their operands are in the expression too) along
00562   // with their weights, representing a certain number of paths to the operator.
00563   // If an operator occurs in the worklist multiple times then we found multiple
00564   // ways to get to it.
00565   SmallVector<std::pair<BinaryOperator*, APInt>, 8> Worklist; // (Op, Weight)
00566   Worklist.push_back(std::make_pair(I, APInt(Bitwidth, 1)));
00567   bool MadeChange = false;
00568 
00569   // Leaves of the expression are values that either aren't the right kind of
00570   // operation (eg: a constant, or a multiply in an add tree), or are, but have
00571   // some uses that are not inside the expression.  For example, in I = X + X,
00572   // X = A + B, the value X has two uses (by I) that are in the expression.  If
00573   // X has any other uses, for example in a return instruction, then we consider
00574   // X to be a leaf, and won't analyze it further.  When we first visit a value,
00575   // if it has more than one use then at first we conservatively consider it to
00576   // be a leaf.  Later, as the expression is explored, we may discover some more
00577   // uses of the value from inside the expression.  If all uses turn out to be
00578   // from within the expression (and the value is a binary operator of the right
00579   // kind) then the value is no longer considered to be a leaf, and its operands
00580   // are explored.
00581 
00582   // Leaves - Keeps track of the set of putative leaves as well as the number of
00583   // paths to each leaf seen so far.
00584   typedef DenseMap<Value*, APInt> LeafMap;
00585   LeafMap Leaves; // Leaf -> Total weight so far.
00586   SmallVector<Value*, 8> LeafOrder; // Ensure deterministic leaf output order.
00587 
00588 #ifndef NDEBUG
00589   SmallPtrSet<Value*, 8> Visited; // For sanity checking the iteration scheme.
00590 #endif
00591   while (!Worklist.empty()) {
00592     std::pair<BinaryOperator*, APInt> P = Worklist.pop_back_val();
00593     I = P.first; // We examine the operands of this binary operator.
00594 
00595     for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) { // Visit operands.
00596       Value *Op = I->getOperand(OpIdx);
00597       APInt Weight = P.second; // Number of paths to this operand.
00598       DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n");
00599       assert(!Op->use_empty() && "No uses, so how did we get to it?!");
00600 
00601       // If this is a binary operation of the right kind with only one use then
00602       // add its operands to the expression.
00603       if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
00604         assert(Visited.insert(Op) && "Not first visit!");
00605         DEBUG(dbgs() << "DIRECT ADD: " << *Op << " (" << Weight << ")\n");
00606         Worklist.push_back(std::make_pair(BO, Weight));
00607         continue;
00608       }
00609 
00610       // Appears to be a leaf.  Is the operand already in the set of leaves?
00611       LeafMap::iterator It = Leaves.find(Op);
00612       if (It == Leaves.end()) {
00613         // Not in the leaf map.  Must be the first time we saw this operand.
00614         assert(Visited.insert(Op) && "Not first visit!");
00615         if (!Op->hasOneUse()) {
00616           // This value has uses not accounted for by the expression, so it is
00617           // not safe to modify.  Mark it as being a leaf.
00618           DEBUG(dbgs() << "ADD USES LEAF: " << *Op << " (" << Weight << ")\n");
00619           LeafOrder.push_back(Op);
00620           Leaves[Op] = Weight;
00621           continue;
00622         }
00623         // No uses outside the expression, try morphing it.
00624       } else if (It != Leaves.end()) {
00625         // Already in the leaf map.
00626         assert(Visited.count(Op) && "In leaf map but not visited!");
00627 
00628         // Update the number of paths to the leaf.
00629         IncorporateWeight(It->second, Weight, Opcode);
00630 
00631 #if 0   // TODO: Re-enable once PR13021 is fixed.
00632         // The leaf already has one use from inside the expression.  As we want
00633         // exactly one such use, drop this new use of the leaf.
00634         assert(!Op->hasOneUse() && "Only one use, but we got here twice!");
00635         I->setOperand(OpIdx, UndefValue::get(I->getType()));
00636         MadeChange = true;
00637 
00638         // If the leaf is a binary operation of the right kind and we now see
00639         // that its multiple original uses were in fact all by nodes belonging
00640         // to the expression, then no longer consider it to be a leaf and add
00641         // its operands to the expression.
00642         if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
00643           DEBUG(dbgs() << "UNLEAF: " << *Op << " (" << It->second << ")\n");
00644           Worklist.push_back(std::make_pair(BO, It->second));
00645           Leaves.erase(It);
00646           continue;
00647         }
00648 #endif
00649 
00650         // If we still have uses that are not accounted for by the expression
00651         // then it is not safe to modify the value.
00652         if (!Op->hasOneUse())
00653           continue;
00654 
00655         // No uses outside the expression, try morphing it.
00656         Weight = It->second;
00657         Leaves.erase(It); // Since the value may be morphed below.
00658       }
00659 
00660       // At this point we have a value which, first of all, is not a binary
00661       // expression of the right kind, and secondly, is only used inside the
00662       // expression.  This means that it can safely be modified.  See if we
00663       // can usefully morph it into an expression of the right kind.
00664       assert((!isa<Instruction>(Op) ||
00665               cast<Instruction>(Op)->getOpcode() != Opcode) &&
00666              "Should have been handled above!");
00667       assert(Op->hasOneUse() && "Has uses outside the expression tree!");
00668 
00669       // If this is a multiply expression, turn any internal negations into
00670       // multiplies by -1 so they can be reassociated.
00671       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op))
00672         if ((Opcode == Instruction::Mul && BinaryOperator::isNeg(BO)) ||
00673             (Opcode == Instruction::FMul && BinaryOperator::isFNeg(BO))) {
00674           DEBUG(dbgs() << "MORPH LEAF: " << *Op << " (" << Weight << ") TO ");
00675           BO = LowerNegateToMultiply(BO);
00676           DEBUG(dbgs() << *BO << '\n');
00677           Worklist.push_back(std::make_pair(BO, Weight));
00678           MadeChange = true;
00679           continue;
00680         }
00681 
00682       // Failed to morph into an expression of the right type.  This really is
00683       // a leaf.
00684       DEBUG(dbgs() << "ADD LEAF: " << *Op << " (" << Weight << ")\n");
00685       assert(!isReassociableOp(Op, Opcode) && "Value was morphed?");
00686       LeafOrder.push_back(Op);
00687       Leaves[Op] = Weight;
00688     }
00689   }
00690 
00691   // The leaves, repeated according to their weights, represent the linearized
00692   // form of the expression.
00693   for (unsigned i = 0, e = LeafOrder.size(); i != e; ++i) {
00694     Value *V = LeafOrder[i];
00695     LeafMap::iterator It = Leaves.find(V);
00696     if (It == Leaves.end())
00697       // Node initially thought to be a leaf wasn't.
00698       continue;
00699     assert(!isReassociableOp(V, Opcode) && "Shouldn't be a leaf!");
00700     APInt Weight = It->second;
00701     if (Weight.isMinValue())
00702       // Leaf already output or weight reduction eliminated it.
00703       continue;
00704     // Ensure the leaf is only output once.
00705     It->second = 0;
00706     Ops.push_back(std::make_pair(V, Weight));
00707   }
00708 
00709   // For nilpotent operations or addition there may be no operands, for example
00710   // because the expression was "X xor X" or consisted of 2^Bitwidth additions:
00711   // in both cases the weight reduces to 0 causing the value to be skipped.
00712   if (Ops.empty()) {
00713     Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, I->getType());
00714     assert(Identity && "Associative operation without identity!");
00715     Ops.push_back(std::make_pair(Identity, APInt(Bitwidth, 1)));
00716   }
00717 
00718   return MadeChange;
00719 }
00720 
00721 // RewriteExprTree - Now that the operands for this expression tree are
00722 // linearized and optimized, emit them in-order.
00723 void Reassociate::RewriteExprTree(BinaryOperator *I,
00724                                   SmallVectorImpl<ValueEntry> &Ops) {
00725   assert(Ops.size() > 1 && "Single values should be used directly!");
00726 
00727   // Since our optimizations should never increase the number of operations, the
00728   // new expression can usually be written reusing the existing binary operators
00729   // from the original expression tree, without creating any new instructions,
00730   // though the rewritten expression may have a completely different topology.
00731   // We take care to not change anything if the new expression will be the same
00732   // as the original.  If more than trivial changes (like commuting operands)
00733   // were made then we are obliged to clear out any optional subclass data like
00734   // nsw flags.
00735 
00736   /// NodesToRewrite - Nodes from the original expression available for writing
00737   /// the new expression into.
00738   SmallVector<BinaryOperator*, 8> NodesToRewrite;
00739   unsigned Opcode = I->getOpcode();
00740   BinaryOperator *Op = I;
00741 
00742   /// NotRewritable - The operands being written will be the leaves of the new
00743   /// expression and must not be used as inner nodes (via NodesToRewrite) by
00744   /// mistake.  Inner nodes are always reassociable, and usually leaves are not
00745   /// (if they were they would have been incorporated into the expression and so
00746   /// would not be leaves), so most of the time there is no danger of this.  But
00747   /// in rare cases a leaf may become reassociable if an optimization kills uses
00748   /// of it, or it may momentarily become reassociable during rewriting (below)
00749   /// due it being removed as an operand of one of its uses.  Ensure that misuse
00750   /// of leaf nodes as inner nodes cannot occur by remembering all of the future
00751   /// leaves and refusing to reuse any of them as inner nodes.
00752   SmallPtrSet<Value*, 8> NotRewritable;
00753   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
00754     NotRewritable.insert(Ops[i].Op);
00755 
00756   // ExpressionChanged - Non-null if the rewritten expression differs from the
00757   // original in some non-trivial way, requiring the clearing of optional flags.
00758   // Flags are cleared from the operator in ExpressionChanged up to I inclusive.
00759   BinaryOperator *ExpressionChanged = nullptr;
00760   for (unsigned i = 0; ; ++i) {
00761     // The last operation (which comes earliest in the IR) is special as both
00762     // operands will come from Ops, rather than just one with the other being
00763     // a subexpression.
00764     if (i+2 == Ops.size()) {
00765       Value *NewLHS = Ops[i].Op;
00766       Value *NewRHS = Ops[i+1].Op;
00767       Value *OldLHS = Op->getOperand(0);
00768       Value *OldRHS = Op->getOperand(1);
00769 
00770       if (NewLHS == OldLHS && NewRHS == OldRHS)
00771         // Nothing changed, leave it alone.
00772         break;
00773 
00774       if (NewLHS == OldRHS && NewRHS == OldLHS) {
00775         // The order of the operands was reversed.  Swap them.
00776         DEBUG(dbgs() << "RA: " << *Op << '\n');
00777         Op->swapOperands();
00778         DEBUG(dbgs() << "TO: " << *Op << '\n');
00779         MadeChange = true;
00780         ++NumChanged;
00781         break;
00782       }
00783 
00784       // The new operation differs non-trivially from the original. Overwrite
00785       // the old operands with the new ones.
00786       DEBUG(dbgs() << "RA: " << *Op << '\n');
00787       if (NewLHS != OldLHS) {
00788         BinaryOperator *BO = isReassociableOp(OldLHS, Opcode);
00789         if (BO && !NotRewritable.count(BO))
00790           NodesToRewrite.push_back(BO);
00791         Op->setOperand(0, NewLHS);
00792       }
00793       if (NewRHS != OldRHS) {
00794         BinaryOperator *BO = isReassociableOp(OldRHS, Opcode);
00795         if (BO && !NotRewritable.count(BO))
00796           NodesToRewrite.push_back(BO);
00797         Op->setOperand(1, NewRHS);
00798       }
00799       DEBUG(dbgs() << "TO: " << *Op << '\n');
00800 
00801       ExpressionChanged = Op;
00802       MadeChange = true;
00803       ++NumChanged;
00804 
00805       break;
00806     }
00807 
00808     // Not the last operation.  The left-hand side will be a sub-expression
00809     // while the right-hand side will be the current element of Ops.
00810     Value *NewRHS = Ops[i].Op;
00811     if (NewRHS != Op->getOperand(1)) {
00812       DEBUG(dbgs() << "RA: " << *Op << '\n');
00813       if (NewRHS == Op->getOperand(0)) {
00814         // The new right-hand side was already present as the left operand.  If
00815         // we are lucky then swapping the operands will sort out both of them.
00816         Op->swapOperands();
00817       } else {
00818         // Overwrite with the new right-hand side.
00819         BinaryOperator *BO = isReassociableOp(Op->getOperand(1), Opcode);
00820         if (BO && !NotRewritable.count(BO))
00821           NodesToRewrite.push_back(BO);
00822         Op->setOperand(1, NewRHS);
00823         ExpressionChanged = Op;
00824       }
00825       DEBUG(dbgs() << "TO: " << *Op << '\n');
00826       MadeChange = true;
00827       ++NumChanged;
00828     }
00829 
00830     // Now deal with the left-hand side.  If this is already an operation node
00831     // from the original expression then just rewrite the rest of the expression
00832     // into it.
00833     BinaryOperator *BO = isReassociableOp(Op->getOperand(0), Opcode);
00834     if (BO && !NotRewritable.count(BO)) {
00835       Op = BO;
00836       continue;
00837     }
00838 
00839     // Otherwise, grab a spare node from the original expression and use that as
00840     // the left-hand side.  If there are no nodes left then the optimizers made
00841     // an expression with more nodes than the original!  This usually means that
00842     // they did something stupid but it might mean that the problem was just too
00843     // hard (finding the mimimal number of multiplications needed to realize a
00844     // multiplication expression is NP-complete).  Whatever the reason, smart or
00845     // stupid, create a new node if there are none left.
00846     BinaryOperator *NewOp;
00847     if (NodesToRewrite.empty()) {
00848       Constant *Undef = UndefValue::get(I->getType());
00849       NewOp = BinaryOperator::Create(Instruction::BinaryOps(Opcode),
00850                                      Undef, Undef, "", I);
00851       if (NewOp->getType()->isFloatingPointTy())
00852         NewOp->setFastMathFlags(I->getFastMathFlags());
00853     } else {
00854       NewOp = NodesToRewrite.pop_back_val();
00855     }
00856 
00857     DEBUG(dbgs() << "RA: " << *Op << '\n');
00858     Op->setOperand(0, NewOp);
00859     DEBUG(dbgs() << "TO: " << *Op << '\n');
00860     ExpressionChanged = Op;
00861     MadeChange = true;
00862     ++NumChanged;
00863     Op = NewOp;
00864   }
00865 
00866   // If the expression changed non-trivially then clear out all subclass data
00867   // starting from the operator specified in ExpressionChanged, and compactify
00868   // the operators to just before the expression root to guarantee that the
00869   // expression tree is dominated by all of Ops.
00870   if (ExpressionChanged)
00871     do {
00872       // Preserve FastMathFlags.
00873       if (isa<FPMathOperator>(I)) {
00874         FastMathFlags Flags = I->getFastMathFlags();
00875         ExpressionChanged->clearSubclassOptionalData();
00876         ExpressionChanged->setFastMathFlags(Flags);
00877       } else
00878         ExpressionChanged->clearSubclassOptionalData();
00879 
00880       if (ExpressionChanged == I)
00881         break;
00882       ExpressionChanged->moveBefore(I);
00883       ExpressionChanged = cast<BinaryOperator>(*ExpressionChanged->user_begin());
00884     } while (1);
00885 
00886   // Throw away any left over nodes from the original expression.
00887   for (unsigned i = 0, e = NodesToRewrite.size(); i != e; ++i)
00888     RedoInsts.insert(NodesToRewrite[i]);
00889 }
00890 
00891 /// NegateValue - Insert instructions before the instruction pointed to by BI,
00892 /// that computes the negative version of the value specified.  The negative
00893 /// version of the value is returned, and BI is left pointing at the instruction
00894 /// that should be processed next by the reassociation pass.
00895 static Value *NegateValue(Value *V, Instruction *BI) {
00896   if (ConstantFP *C = dyn_cast<ConstantFP>(V))
00897     return ConstantExpr::getFNeg(C);
00898   if (Constant *C = dyn_cast<Constant>(V))
00899     return ConstantExpr::getNeg(C);
00900 
00901   // We are trying to expose opportunity for reassociation.  One of the things
00902   // that we want to do to achieve this is to push a negation as deep into an
00903   // expression chain as possible, to expose the add instructions.  In practice,
00904   // this means that we turn this:
00905   //   X = -(A+12+C+D)   into    X = -A + -12 + -C + -D = -12 + -A + -C + -D
00906   // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate
00907   // the constants.  We assume that instcombine will clean up the mess later if
00908   // we introduce tons of unnecessary negation instructions.
00909   //
00910   if (BinaryOperator *I =
00911           isReassociableOp(V, Instruction::Add, Instruction::FAdd)) {
00912     // Push the negates through the add.
00913     I->setOperand(0, NegateValue(I->getOperand(0), BI));
00914     I->setOperand(1, NegateValue(I->getOperand(1), BI));
00915 
00916     // We must move the add instruction here, because the neg instructions do
00917     // not dominate the old add instruction in general.  By moving it, we are
00918     // assured that the neg instructions we just inserted dominate the
00919     // instruction we are about to insert after them.
00920     //
00921     I->moveBefore(BI);
00922     I->setName(I->getName()+".neg");
00923     return I;
00924   }
00925 
00926   // Okay, we need to materialize a negated version of V with an instruction.
00927   // Scan the use lists of V to see if we have one already.
00928   for (User *U : V->users()) {
00929     if (!BinaryOperator::isNeg(U) && !BinaryOperator::isFNeg(U))
00930       continue;
00931 
00932     // We found one!  Now we have to make sure that the definition dominates
00933     // this use.  We do this by moving it to the entry block (if it is a
00934     // non-instruction value) or right after the definition.  These negates will
00935     // be zapped by reassociate later, so we don't need much finesse here.
00936     BinaryOperator *TheNeg = cast<BinaryOperator>(U);
00937 
00938     // Verify that the negate is in this function, V might be a constant expr.
00939     if (TheNeg->getParent()->getParent() != BI->getParent()->getParent())
00940       continue;
00941 
00942     BasicBlock::iterator InsertPt;
00943     if (Instruction *InstInput = dyn_cast<Instruction>(V)) {
00944       if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) {
00945         InsertPt = II->getNormalDest()->begin();
00946       } else {
00947         InsertPt = InstInput;
00948         ++InsertPt;
00949       }
00950       while (isa<PHINode>(InsertPt)) ++InsertPt;
00951     } else {
00952       InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin();
00953     }
00954     TheNeg->moveBefore(InsertPt);
00955     return TheNeg;
00956   }
00957 
00958   // Insert a 'neg' instruction that subtracts the value from zero to get the
00959   // negation.
00960   return CreateNeg(V, V->getName() + ".neg", BI, BI);
00961 }
00962 
00963 /// ShouldBreakUpSubtract - Return true if we should break up this subtract of
00964 /// X-Y into (X + -Y).
00965 static bool ShouldBreakUpSubtract(Instruction *Sub) {
00966   // If this is a negation, we can't split it up!
00967   if (BinaryOperator::isNeg(Sub) || BinaryOperator::isFNeg(Sub))
00968     return false;
00969 
00970   // Don't breakup X - undef.
00971   if (isa<UndefValue>(Sub->getOperand(1)))
00972     return false;
00973 
00974   // Don't bother to break this up unless either the LHS is an associable add or
00975   // subtract or if this is only used by one.
00976   Value *V0 = Sub->getOperand(0);
00977   if (isReassociableOp(V0, Instruction::Add, Instruction::FAdd) ||
00978       isReassociableOp(V0, Instruction::Sub, Instruction::FSub))
00979     return true;
00980   Value *V1 = Sub->getOperand(1);
00981   if (isReassociableOp(V1, Instruction::Add, Instruction::FAdd) ||
00982       isReassociableOp(V1, Instruction::Sub, Instruction::FSub))
00983     return true;
00984   Value *VB = Sub->user_back();
00985   if (Sub->hasOneUse() &&
00986       (isReassociableOp(VB, Instruction::Add, Instruction::FAdd) ||
00987        isReassociableOp(VB, Instruction::Sub, Instruction::FSub)))
00988     return true;
00989 
00990   return false;
00991 }
00992 
00993 /// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is
00994 /// only used by an add, transform this into (X+(0-Y)) to promote better
00995 /// reassociation.
00996 static BinaryOperator *BreakUpSubtract(Instruction *Sub) {
00997   // Convert a subtract into an add and a neg instruction. This allows sub
00998   // instructions to be commuted with other add instructions.
00999   //
01000   // Calculate the negative value of Operand 1 of the sub instruction,
01001   // and set it as the RHS of the add instruction we just made.
01002   //
01003   Value *NegVal = NegateValue(Sub->getOperand(1), Sub);
01004   BinaryOperator *New = CreateAdd(Sub->getOperand(0), NegVal, "", Sub, Sub);
01005   Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op.
01006   Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op.
01007   New->takeName(Sub);
01008 
01009   // Everyone now refers to the add instruction.
01010   Sub->replaceAllUsesWith(New);
01011   New->setDebugLoc(Sub->getDebugLoc());
01012 
01013   DEBUG(dbgs() << "Negated: " << *New << '\n');
01014   return New;
01015 }
01016 
01017 /// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used
01018 /// by one, change this into a multiply by a constant to assist with further
01019 /// reassociation.
01020 static BinaryOperator *ConvertShiftToMul(Instruction *Shl) {
01021   Constant *MulCst = ConstantInt::get(Shl->getType(), 1);
01022   MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1)));
01023 
01024   BinaryOperator *Mul =
01025     BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl);
01026   Shl->setOperand(0, UndefValue::get(Shl->getType())); // Drop use of op.
01027   Mul->takeName(Shl);
01028   Shl->replaceAllUsesWith(Mul);
01029   Mul->setDebugLoc(Shl->getDebugLoc());
01030   return Mul;
01031 }
01032 
01033 /// FindInOperandList - Scan backwards and forwards among values with the same
01034 /// rank as element i to see if X exists.  If X does not exist, return i.  This
01035 /// is useful when scanning for 'x' when we see '-x' because they both get the
01036 /// same rank.
01037 static unsigned FindInOperandList(SmallVectorImpl<ValueEntry> &Ops, unsigned i,
01038                                   Value *X) {
01039   unsigned XRank = Ops[i].Rank;
01040   unsigned e = Ops.size();
01041   for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {
01042     if (Ops[j].Op == X)
01043       return j;
01044     if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
01045       if (Instruction *I2 = dyn_cast<Instruction>(X))
01046         if (I1->isIdenticalTo(I2))
01047           return j;
01048   }
01049   // Scan backwards.
01050   for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {
01051     if (Ops[j].Op == X)
01052       return j;
01053     if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
01054       if (Instruction *I2 = dyn_cast<Instruction>(X))
01055         if (I1->isIdenticalTo(I2))
01056           return j;
01057   }
01058   return i;
01059 }
01060 
01061 /// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together
01062 /// and returning the result.  Insert the tree before I.
01063 static Value *EmitAddTreeOfValues(Instruction *I,
01064                                   SmallVectorImpl<WeakVH> &Ops){
01065   if (Ops.size() == 1) return Ops.back();
01066 
01067   Value *V1 = Ops.back();
01068   Ops.pop_back();
01069   Value *V2 = EmitAddTreeOfValues(I, Ops);
01070   return CreateAdd(V2, V1, "tmp", I, I);
01071 }
01072 
01073 /// RemoveFactorFromExpression - If V is an expression tree that is a
01074 /// multiplication sequence, and if this sequence contains a multiply by Factor,
01075 /// remove Factor from the tree and return the new tree.
01076 Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) {
01077   BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul);
01078   if (!BO)
01079     return nullptr;
01080 
01081   SmallVector<RepeatedValue, 8> Tree;
01082   MadeChange |= LinearizeExprTree(BO, Tree);
01083   SmallVector<ValueEntry, 8> Factors;
01084   Factors.reserve(Tree.size());
01085   for (unsigned i = 0, e = Tree.size(); i != e; ++i) {
01086     RepeatedValue E = Tree[i];
01087     Factors.append(E.second.getZExtValue(),
01088                    ValueEntry(getRank(E.first), E.first));
01089   }
01090 
01091   bool FoundFactor = false;
01092   bool NeedsNegate = false;
01093   for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
01094     if (Factors[i].Op == Factor) {
01095       FoundFactor = true;
01096       Factors.erase(Factors.begin()+i);
01097       break;
01098     }
01099 
01100     // If this is a negative version of this factor, remove it.
01101     if (ConstantInt *FC1 = dyn_cast<ConstantInt>(Factor)) {
01102       if (ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op))
01103         if (FC1->getValue() == -FC2->getValue()) {
01104           FoundFactor = NeedsNegate = true;
01105           Factors.erase(Factors.begin()+i);
01106           break;
01107         }
01108     } else if (ConstantFP *FC1 = dyn_cast<ConstantFP>(Factor)) {
01109       if (ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[i].Op)) {
01110         APFloat F1(FC1->getValueAPF());
01111         APFloat F2(FC2->getValueAPF());
01112         F2.changeSign();
01113         if (F1.compare(F2) == APFloat::cmpEqual) {
01114           FoundFactor = NeedsNegate = true;
01115           Factors.erase(Factors.begin() + i);
01116           break;
01117         }
01118       }
01119     }
01120   }
01121 
01122   if (!FoundFactor) {
01123     // Make sure to restore the operands to the expression tree.
01124     RewriteExprTree(BO, Factors);
01125     return nullptr;
01126   }
01127 
01128   BasicBlock::iterator InsertPt = BO; ++InsertPt;
01129 
01130   // If this was just a single multiply, remove the multiply and return the only
01131   // remaining operand.
01132   if (Factors.size() == 1) {
01133     RedoInsts.insert(BO);
01134     V = Factors[0].Op;
01135   } else {
01136     RewriteExprTree(BO, Factors);
01137     V = BO;
01138   }
01139 
01140   if (NeedsNegate)
01141     V = CreateNeg(V, "neg", InsertPt, BO);
01142 
01143   return V;
01144 }
01145 
01146 /// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively
01147 /// add its operands as factors, otherwise add V to the list of factors.
01148 ///
01149 /// Ops is the top-level list of add operands we're trying to factor.
01150 static void FindSingleUseMultiplyFactors(Value *V,
01151                                          SmallVectorImpl<Value*> &Factors,
01152                                        const SmallVectorImpl<ValueEntry> &Ops) {
01153   BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul);
01154   if (!BO) {
01155     Factors.push_back(V);
01156     return;
01157   }
01158 
01159   // Otherwise, add the LHS and RHS to the list of factors.
01160   FindSingleUseMultiplyFactors(BO->getOperand(1), Factors, Ops);
01161   FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops);
01162 }
01163 
01164 /// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor'
01165 /// instruction.  This optimizes based on identities.  If it can be reduced to
01166 /// a single Value, it is returned, otherwise the Ops list is mutated as
01167 /// necessary.
01168 static Value *OptimizeAndOrXor(unsigned Opcode,
01169                                SmallVectorImpl<ValueEntry> &Ops) {
01170   // Scan the operand lists looking for X and ~X pairs, along with X,X pairs.
01171   // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1.
01172   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
01173     // First, check for X and ~X in the operand list.
01174     assert(i < Ops.size());
01175     if (BinaryOperator::isNot(Ops[i].Op)) {    // Cannot occur for ^.
01176       Value *X = BinaryOperator::getNotArgument(Ops[i].Op);
01177       unsigned FoundX = FindInOperandList(Ops, i, X);
01178       if (FoundX != i) {
01179         if (Opcode == Instruction::And)   // ...&X&~X = 0
01180           return Constant::getNullValue(X->getType());
01181 
01182         if (Opcode == Instruction::Or)    // ...|X|~X = -1
01183           return Constant::getAllOnesValue(X->getType());
01184       }
01185     }
01186 
01187     // Next, check for duplicate pairs of values, which we assume are next to
01188     // each other, due to our sorting criteria.
01189     assert(i < Ops.size());
01190     if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) {
01191       if (Opcode == Instruction::And || Opcode == Instruction::Or) {
01192         // Drop duplicate values for And and Or.
01193         Ops.erase(Ops.begin()+i);
01194         --i; --e;
01195         ++NumAnnihil;
01196         continue;
01197       }
01198 
01199       // Drop pairs of values for Xor.
01200       assert(Opcode == Instruction::Xor);
01201       if (e == 2)
01202         return Constant::getNullValue(Ops[0].Op->getType());
01203 
01204       // Y ^ X^X -> Y
01205       Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
01206       i -= 1; e -= 2;
01207       ++NumAnnihil;
01208     }
01209   }
01210   return nullptr;
01211 }
01212 
01213 /// Helper funciton of CombineXorOpnd(). It creates a bitwise-and
01214 /// instruction with the given two operands, and return the resulting
01215 /// instruction. There are two special cases: 1) if the constant operand is 0,
01216 /// it will return NULL. 2) if the constant is ~0, the symbolic operand will
01217 /// be returned.
01218 static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd, 
01219                              const APInt &ConstOpnd) {
01220   if (ConstOpnd != 0) {
01221     if (!ConstOpnd.isAllOnesValue()) {
01222       LLVMContext &Ctx = Opnd->getType()->getContext();
01223       Instruction *I;
01224       I = BinaryOperator::CreateAnd(Opnd, ConstantInt::get(Ctx, ConstOpnd),
01225                                     "and.ra", InsertBefore);
01226       I->setDebugLoc(InsertBefore->getDebugLoc());
01227       return I;
01228     }
01229     return Opnd;
01230   }
01231   return nullptr;
01232 }
01233 
01234 // Helper function of OptimizeXor(). It tries to simplify "Opnd1 ^ ConstOpnd"
01235 // into "R ^ C", where C would be 0, and R is a symbolic value.
01236 //
01237 // If it was successful, true is returned, and the "R" and "C" is returned
01238 // via "Res" and "ConstOpnd", respectively; otherwise, false is returned,
01239 // and both "Res" and "ConstOpnd" remain unchanged.
01240 //  
01241 bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
01242                                  APInt &ConstOpnd, Value *&Res) {
01243   // Xor-Rule 1: (x | c1) ^ c2 = (x | c1) ^ (c1 ^ c1) ^ c2 
01244   //                       = ((x | c1) ^ c1) ^ (c1 ^ c2)
01245   //                       = (x & ~c1) ^ (c1 ^ c2)
01246   // It is useful only when c1 == c2.
01247   if (Opnd1->isOrExpr() && Opnd1->getConstPart() != 0) {
01248     if (!Opnd1->getValue()->hasOneUse())
01249       return false;
01250 
01251     const APInt &C1 = Opnd1->getConstPart();
01252     if (C1 != ConstOpnd)
01253       return false;
01254 
01255     Value *X = Opnd1->getSymbolicPart();
01256     Res = createAndInstr(I, X, ~C1);
01257     // ConstOpnd was C2, now C1 ^ C2.
01258     ConstOpnd ^= C1;
01259 
01260     if (Instruction *T = dyn_cast<Instruction>(Opnd1->getValue()))
01261       RedoInsts.insert(T);
01262     return true;
01263   }
01264   return false;
01265 }
01266 
01267                            
01268 // Helper function of OptimizeXor(). It tries to simplify
01269 // "Opnd1 ^ Opnd2 ^ ConstOpnd" into "R ^ C", where C would be 0, and R is a
01270 // symbolic value. 
01271 // 
01272 // If it was successful, true is returned, and the "R" and "C" is returned 
01273 // via "Res" and "ConstOpnd", respectively (If the entire expression is
01274 // evaluated to a constant, the Res is set to NULL); otherwise, false is
01275 // returned, and both "Res" and "ConstOpnd" remain unchanged.
01276 bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2,
01277                                  APInt &ConstOpnd, Value *&Res) {
01278   Value *X = Opnd1->getSymbolicPart();
01279   if (X != Opnd2->getSymbolicPart())
01280     return false;
01281 
01282   // This many instruction become dead.(At least "Opnd1 ^ Opnd2" will die.)
01283   int DeadInstNum = 1;
01284   if (Opnd1->getValue()->hasOneUse())
01285     DeadInstNum++;
01286   if (Opnd2->getValue()->hasOneUse())
01287     DeadInstNum++;
01288 
01289   // Xor-Rule 2:
01290   //  (x | c1) ^ (x & c2)
01291   //   = (x|c1) ^ (x&c2) ^ (c1 ^ c1) = ((x|c1) ^ c1) ^ (x & c2) ^ c1
01292   //   = (x & ~c1) ^ (x & c2) ^ c1               // Xor-Rule 1
01293   //   = (x & c3) ^ c1, where c3 = ~c1 ^ c2      // Xor-rule 3
01294   //
01295   if (Opnd1->isOrExpr() != Opnd2->isOrExpr()) {
01296     if (Opnd2->isOrExpr())
01297       std::swap(Opnd1, Opnd2);
01298 
01299     const APInt &C1 = Opnd1->getConstPart();
01300     const APInt &C2 = Opnd2->getConstPart();
01301     APInt C3((~C1) ^ C2);
01302 
01303     // Do not increase code size!
01304     if (C3 != 0 && !C3.isAllOnesValue()) {
01305       int NewInstNum = ConstOpnd != 0 ? 1 : 2;
01306       if (NewInstNum > DeadInstNum)
01307         return false;
01308     }
01309 
01310     Res = createAndInstr(I, X, C3);
01311     ConstOpnd ^= C1;
01312 
01313   } else if (Opnd1->isOrExpr()) {
01314     // Xor-Rule 3: (x | c1) ^ (x | c2) = (x & c3) ^ c3 where c3 = c1 ^ c2
01315     //
01316     const APInt &C1 = Opnd1->getConstPart();
01317     const APInt &C2 = Opnd2->getConstPart();
01318     APInt C3 = C1 ^ C2;
01319     
01320     // Do not increase code size
01321     if (C3 != 0 && !C3.isAllOnesValue()) {
01322       int NewInstNum = ConstOpnd != 0 ? 1 : 2;
01323       if (NewInstNum > DeadInstNum)
01324         return false;
01325     }
01326 
01327     Res = createAndInstr(I, X, C3);
01328     ConstOpnd ^= C3;
01329   } else {
01330     // Xor-Rule 4: (x & c1) ^ (x & c2) = (x & (c1^c2))
01331     //
01332     const APInt &C1 = Opnd1->getConstPart();
01333     const APInt &C2 = Opnd2->getConstPart();
01334     APInt C3 = C1 ^ C2;
01335     Res = createAndInstr(I, X, C3);
01336   }
01337 
01338   // Put the original operands in the Redo list; hope they will be deleted
01339   // as dead code.
01340   if (Instruction *T = dyn_cast<Instruction>(Opnd1->getValue()))
01341     RedoInsts.insert(T);
01342   if (Instruction *T = dyn_cast<Instruction>(Opnd2->getValue()))
01343     RedoInsts.insert(T);
01344 
01345   return true;
01346 }
01347 
01348 /// Optimize a series of operands to an 'xor' instruction. If it can be reduced
01349 /// to a single Value, it is returned, otherwise the Ops list is mutated as
01350 /// necessary.
01351 Value *Reassociate::OptimizeXor(Instruction *I,
01352                                 SmallVectorImpl<ValueEntry> &Ops) {
01353   if (Value *V = OptimizeAndOrXor(Instruction::Xor, Ops))
01354     return V;
01355       
01356   if (Ops.size() == 1)
01357     return nullptr;
01358 
01359   SmallVector<XorOpnd, 8> Opnds;
01360   SmallVector<XorOpnd*, 8> OpndPtrs;
01361   Type *Ty = Ops[0].Op->getType();
01362   APInt ConstOpnd(Ty->getIntegerBitWidth(), 0);
01363 
01364   // Step 1: Convert ValueEntry to XorOpnd
01365   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
01366     Value *V = Ops[i].Op;
01367     if (!isa<ConstantInt>(V)) {
01368       XorOpnd O(V);
01369       O.setSymbolicRank(getRank(O.getSymbolicPart()));
01370       Opnds.push_back(O);
01371     } else
01372       ConstOpnd ^= cast<ConstantInt>(V)->getValue();
01373   }
01374 
01375   // NOTE: From this point on, do *NOT* add/delete element to/from "Opnds".
01376   //  It would otherwise invalidate the "Opnds"'s iterator, and hence invalidate
01377   //  the "OpndPtrs" as well. For the similar reason, do not fuse this loop
01378   //  with the previous loop --- the iterator of the "Opnds" may be invalidated
01379   //  when new elements are added to the vector.
01380   for (unsigned i = 0, e = Opnds.size(); i != e; ++i)
01381     OpndPtrs.push_back(&Opnds[i]);
01382 
01383   // Step 2: Sort the Xor-Operands in a way such that the operands containing
01384   //  the same symbolic value cluster together. For instance, the input operand
01385   //  sequence ("x | 123", "y & 456", "x & 789") will be sorted into:
01386   //  ("x | 123", "x & 789", "y & 456").
01387   std::stable_sort(OpndPtrs.begin(), OpndPtrs.end(), XorOpnd::PtrSortFunctor());
01388 
01389   // Step 3: Combine adjacent operands
01390   XorOpnd *PrevOpnd = nullptr;
01391   bool Changed = false;
01392   for (unsigned i = 0, e = Opnds.size(); i < e; i++) {
01393     XorOpnd *CurrOpnd = OpndPtrs[i];
01394     // The combined value
01395     Value *CV;
01396 
01397     // Step 3.1: Try simplifying "CurrOpnd ^ ConstOpnd"
01398     if (ConstOpnd != 0 && CombineXorOpnd(I, CurrOpnd, ConstOpnd, CV)) {
01399       Changed = true;
01400       if (CV)
01401         *CurrOpnd = XorOpnd(CV);
01402       else {
01403         CurrOpnd->Invalidate();
01404         continue;
01405       }
01406     }
01407 
01408     if (!PrevOpnd || CurrOpnd->getSymbolicPart() != PrevOpnd->getSymbolicPart()) {
01409       PrevOpnd = CurrOpnd;
01410       continue;
01411     }
01412 
01413     // step 3.2: When previous and current operands share the same symbolic
01414     //  value, try to simplify "PrevOpnd ^ CurrOpnd ^ ConstOpnd" 
01415     //    
01416     if (CombineXorOpnd(I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
01417       // Remove previous operand
01418       PrevOpnd->Invalidate();
01419       if (CV) {
01420         *CurrOpnd = XorOpnd(CV);
01421         PrevOpnd = CurrOpnd;
01422       } else {
01423         CurrOpnd->Invalidate();
01424         PrevOpnd = nullptr;
01425       }
01426       Changed = true;
01427     }
01428   }
01429 
01430   // Step 4: Reassemble the Ops
01431   if (Changed) {
01432     Ops.clear();
01433     for (unsigned int i = 0, e = Opnds.size(); i < e; i++) {
01434       XorOpnd &O = Opnds[i];
01435       if (O.isInvalid())
01436         continue;
01437       ValueEntry VE(getRank(O.getValue()), O.getValue());
01438       Ops.push_back(VE);
01439     }
01440     if (ConstOpnd != 0) {
01441       Value *C = ConstantInt::get(Ty->getContext(), ConstOpnd);
01442       ValueEntry VE(getRank(C), C);
01443       Ops.push_back(VE);
01444     }
01445     int Sz = Ops.size();
01446     if (Sz == 1)
01447       return Ops.back().Op;
01448     else if (Sz == 0) {
01449       assert(ConstOpnd == 0);
01450       return ConstantInt::get(Ty->getContext(), ConstOpnd);
01451     }
01452   }
01453 
01454   return nullptr;
01455 }
01456 
01457 /// OptimizeAdd - Optimize a series of operands to an 'add' instruction.  This
01458 /// optimizes based on identities.  If it can be reduced to a single Value, it
01459 /// is returned, otherwise the Ops list is mutated as necessary.
01460 Value *Reassociate::OptimizeAdd(Instruction *I,
01461                                 SmallVectorImpl<ValueEntry> &Ops) {
01462   // Scan the operand lists looking for X and -X pairs.  If we find any, we
01463   // can simplify expressions like X+-X == 0 and X+~X ==-1.  While we're at it,
01464   // scan for any
01465   // duplicates.  We want to canonicalize Y+Y+Y+Z -> 3*Y+Z.
01466 
01467   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
01468     Value *TheOp = Ops[i].Op;
01469     // Check to see if we've seen this operand before.  If so, we factor all
01470     // instances of the operand together.  Due to our sorting criteria, we know
01471     // that these need to be next to each other in the vector.
01472     if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) {
01473       // Rescan the list, remove all instances of this operand from the expr.
01474       unsigned NumFound = 0;
01475       do {
01476         Ops.erase(Ops.begin()+i);
01477         ++NumFound;
01478       } while (i != Ops.size() && Ops[i].Op == TheOp);
01479 
01480       DEBUG(errs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n');
01481       ++NumFactor;
01482 
01483       // Insert a new multiply.
01484       Type *Ty = TheOp->getType();
01485       Constant *C = Ty->isIntegerTy() ? ConstantInt::get(Ty, NumFound)
01486                                       : ConstantFP::get(Ty, NumFound);
01487       Instruction *Mul = CreateMul(TheOp, C, "factor", I, I);
01488 
01489       // Now that we have inserted a multiply, optimize it. This allows us to
01490       // handle cases that require multiple factoring steps, such as this:
01491       // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6
01492       RedoInsts.insert(Mul);
01493 
01494       // If every add operand was a duplicate, return the multiply.
01495       if (Ops.empty())
01496         return Mul;
01497 
01498       // Otherwise, we had some input that didn't have the dupe, such as
01499       // "A + A + B" -> "A*2 + B".  Add the new multiply to the list of
01500       // things being added by this operation.
01501       Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul));
01502 
01503       --i;
01504       e = Ops.size();
01505       continue;
01506     }
01507 
01508     // Check for X and -X or X and ~X in the operand list.
01509     if (!BinaryOperator::isNeg(TheOp) && !BinaryOperator::isFNeg(TheOp) &&
01510         !BinaryOperator::isNot(TheOp))
01511       continue;
01512 
01513     Value *X = nullptr;
01514     if (BinaryOperator::isNeg(TheOp) || BinaryOperator::isFNeg(TheOp))
01515       X = BinaryOperator::getNegArgument(TheOp);
01516     else if (BinaryOperator::isNot(TheOp))
01517       X = BinaryOperator::getNotArgument(TheOp);
01518 
01519     unsigned FoundX = FindInOperandList(Ops, i, X);
01520     if (FoundX == i)
01521       continue;
01522 
01523     // Remove X and -X from the operand list.
01524     if (Ops.size() == 2 &&
01525         (BinaryOperator::isNeg(TheOp) || BinaryOperator::isFNeg(TheOp)))
01526       return Constant::getNullValue(X->getType());
01527 
01528     // Remove X and ~X from the operand list.
01529     if (Ops.size() == 2 && BinaryOperator::isNot(TheOp))
01530       return Constant::getAllOnesValue(X->getType());
01531 
01532     Ops.erase(Ops.begin()+i);
01533     if (i < FoundX)
01534       --FoundX;
01535     else
01536       --i;   // Need to back up an extra one.
01537     Ops.erase(Ops.begin()+FoundX);
01538     ++NumAnnihil;
01539     --i;     // Revisit element.
01540     e -= 2;  // Removed two elements.
01541 
01542     // if X and ~X we append -1 to the operand list.
01543     if (BinaryOperator::isNot(TheOp)) {
01544       Value *V = Constant::getAllOnesValue(X->getType());
01545       Ops.insert(Ops.end(), ValueEntry(getRank(V), V));
01546       e += 1;
01547     }
01548   }
01549 
01550   // Scan the operand list, checking to see if there are any common factors
01551   // between operands.  Consider something like A*A+A*B*C+D.  We would like to
01552   // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies.
01553   // To efficiently find this, we count the number of times a factor occurs
01554   // for any ADD operands that are MULs.
01555   DenseMap<Value*, unsigned> FactorOccurrences;
01556 
01557   // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4)
01558   // where they are actually the same multiply.
01559   unsigned MaxOcc = 0;
01560   Value *MaxOccVal = nullptr;
01561   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
01562     BinaryOperator *BOp =
01563         isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul);
01564     if (!BOp)
01565       continue;
01566 
01567     // Compute all of the factors of this added value.
01568     SmallVector<Value*, 8> Factors;
01569     FindSingleUseMultiplyFactors(BOp, Factors, Ops);
01570     assert(Factors.size() > 1 && "Bad linearize!");
01571 
01572     // Add one to FactorOccurrences for each unique factor in this op.
01573     SmallPtrSet<Value*, 8> Duplicates;
01574     for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
01575       Value *Factor = Factors[i];
01576       if (!Duplicates.insert(Factor))
01577         continue;
01578 
01579       unsigned Occ = ++FactorOccurrences[Factor];
01580       if (Occ > MaxOcc) {
01581         MaxOcc = Occ;
01582         MaxOccVal = Factor;
01583       }
01584 
01585       // If Factor is a negative constant, add the negated value as a factor
01586       // because we can percolate the negate out.  Watch for minint, which
01587       // cannot be positivified.
01588       if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) {
01589         if (CI->isNegative() && !CI->isMinValue(true)) {
01590           Factor = ConstantInt::get(CI->getContext(), -CI->getValue());
01591           assert(!Duplicates.count(Factor) &&
01592                  "Shouldn't have two constant factors, missed a canonicalize");
01593           unsigned Occ = ++FactorOccurrences[Factor];
01594           if (Occ > MaxOcc) {
01595             MaxOcc = Occ;
01596             MaxOccVal = Factor;
01597           }
01598         }
01599       } else if (ConstantFP *CF = dyn_cast<ConstantFP>(Factor)) {
01600         if (CF->isNegative()) {
01601           APFloat F(CF->getValueAPF());
01602           F.changeSign();
01603           Factor = ConstantFP::get(CF->getContext(), F);
01604           assert(!Duplicates.count(Factor) &&
01605                  "Shouldn't have two constant factors, missed a canonicalize");
01606           unsigned Occ = ++FactorOccurrences[Factor];
01607           if (Occ > MaxOcc) {
01608             MaxOcc = Occ;
01609             MaxOccVal = Factor;
01610           }
01611         }
01612       }
01613     }
01614   }
01615 
01616   // If any factor occurred more than one time, we can pull it out.
01617   if (MaxOcc > 1) {
01618     DEBUG(errs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n');
01619     ++NumFactor;
01620 
01621     // Create a new instruction that uses the MaxOccVal twice.  If we don't do
01622     // this, we could otherwise run into situations where removing a factor
01623     // from an expression will drop a use of maxocc, and this can cause
01624     // RemoveFactorFromExpression on successive values to behave differently.
01625     Instruction *DummyInst =
01626         I->getType()->isIntegerTy()
01627             ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal)
01628             : BinaryOperator::CreateFAdd(MaxOccVal, MaxOccVal);
01629 
01630     SmallVector<WeakVH, 4> NewMulOps;
01631     for (unsigned i = 0; i != Ops.size(); ++i) {
01632       // Only try to remove factors from expressions we're allowed to.
01633       BinaryOperator *BOp =
01634           isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul);
01635       if (!BOp)
01636         continue;
01637 
01638       if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) {
01639         // The factorized operand may occur several times.  Convert them all in
01640         // one fell swoop.
01641         for (unsigned j = Ops.size(); j != i;) {
01642           --j;
01643           if (Ops[j].Op == Ops[i].Op) {
01644             NewMulOps.push_back(V);
01645             Ops.erase(Ops.begin()+j);
01646           }
01647         }
01648         --i;
01649       }
01650     }
01651 
01652     // No need for extra uses anymore.
01653     delete DummyInst;
01654 
01655     unsigned NumAddedValues = NewMulOps.size();
01656     Value *V = EmitAddTreeOfValues(I, NewMulOps);
01657 
01658     // Now that we have inserted the add tree, optimize it. This allows us to
01659     // handle cases that require multiple factoring steps, such as this:
01660     // A*A*B + A*A*C   -->   A*(A*B+A*C)   -->   A*(A*(B+C))
01661     assert(NumAddedValues > 1 && "Each occurrence should contribute a value");
01662     (void)NumAddedValues;
01663     if (Instruction *VI = dyn_cast<Instruction>(V))
01664       RedoInsts.insert(VI);
01665 
01666     // Create the multiply.
01667     Instruction *V2 = CreateMul(V, MaxOccVal, "tmp", I, I);
01668 
01669     // Rerun associate on the multiply in case the inner expression turned into
01670     // a multiply.  We want to make sure that we keep things in canonical form.
01671     RedoInsts.insert(V2);
01672 
01673     // If every add operand included the factor (e.g. "A*B + A*C"), then the
01674     // entire result expression is just the multiply "A*(B+C)".
01675     if (Ops.empty())
01676       return V2;
01677 
01678     // Otherwise, we had some input that didn't have the factor, such as
01679     // "A*B + A*C + D" -> "A*(B+C) + D".  Add the new multiply to the list of
01680     // things being added by this operation.
01681     Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2));
01682   }
01683 
01684   return nullptr;
01685 }
01686 
01687 /// \brief Build up a vector of value/power pairs factoring a product.
01688 ///
01689 /// Given a series of multiplication operands, build a vector of factors and
01690 /// the powers each is raised to when forming the final product. Sort them in
01691 /// the order of descending power.
01692 ///
01693 ///      (x*x)          -> [(x, 2)]
01694 ///     ((x*x)*x)       -> [(x, 3)]
01695 ///   ((((x*y)*x)*y)*x) -> [(x, 3), (y, 2)]
01696 ///
01697 /// \returns Whether any factors have a power greater than one.
01698 bool Reassociate::collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops,
01699                                          SmallVectorImpl<Factor> &Factors) {
01700   // FIXME: Have Ops be (ValueEntry, Multiplicity) pairs, simplifying this.
01701   // Compute the sum of powers of simplifiable factors.
01702   unsigned FactorPowerSum = 0;
01703   for (unsigned Idx = 1, Size = Ops.size(); Idx < Size; ++Idx) {
01704     Value *Op = Ops[Idx-1].Op;
01705 
01706     // Count the number of occurrences of this value.
01707     unsigned Count = 1;
01708     for (; Idx < Size && Ops[Idx].Op == Op; ++Idx)
01709       ++Count;
01710     // Track for simplification all factors which occur 2 or more times.
01711     if (Count > 1)
01712       FactorPowerSum += Count;
01713   }
01714 
01715   // We can only simplify factors if the sum of the powers of our simplifiable
01716   // factors is 4 or higher. When that is the case, we will *always* have
01717   // a simplification. This is an important invariant to prevent cyclicly
01718   // trying to simplify already minimal formations.
01719   if (FactorPowerSum < 4)
01720     return false;
01721 
01722   // Now gather the simplifiable factors, removing them from Ops.
01723   FactorPowerSum = 0;
01724   for (unsigned Idx = 1; Idx < Ops.size(); ++Idx) {
01725     Value *Op = Ops[Idx-1].Op;
01726 
01727     // Count the number of occurrences of this value.
01728     unsigned Count = 1;
01729     for (; Idx < Ops.size() && Ops[Idx].Op == Op; ++Idx)
01730       ++Count;
01731     if (Count == 1)
01732       continue;
01733     // Move an even number of occurrences to Factors.
01734     Count &= ~1U;
01735     Idx -= Count;
01736     FactorPowerSum += Count;
01737     Factors.push_back(Factor(Op, Count));
01738     Ops.erase(Ops.begin()+Idx, Ops.begin()+Idx+Count);
01739   }
01740 
01741   // None of the adjustments above should have reduced the sum of factor powers
01742   // below our mininum of '4'.
01743   assert(FactorPowerSum >= 4);
01744 
01745   std::stable_sort(Factors.begin(), Factors.end(), Factor::PowerDescendingSorter());
01746   return true;
01747 }
01748 
01749 /// \brief Build a tree of multiplies, computing the product of Ops.
01750 static Value *buildMultiplyTree(IRBuilder<> &Builder,
01751                                 SmallVectorImpl<Value*> &Ops) {
01752   if (Ops.size() == 1)
01753     return Ops.back();
01754 
01755   Value *LHS = Ops.pop_back_val();
01756   do {
01757     if (LHS->getType()->isIntegerTy())
01758       LHS = Builder.CreateMul(LHS, Ops.pop_back_val());
01759     else
01760       LHS = Builder.CreateFMul(LHS, Ops.pop_back_val());
01761   } while (!Ops.empty());
01762 
01763   return LHS;
01764 }
01765 
01766 /// \brief Build a minimal multiplication DAG for (a^x)*(b^y)*(c^z)*...
01767 ///
01768 /// Given a vector of values raised to various powers, where no two values are
01769 /// equal and the powers are sorted in decreasing order, compute the minimal
01770 /// DAG of multiplies to compute the final product, and return that product
01771 /// value.
01772 Value *Reassociate::buildMinimalMultiplyDAG(IRBuilder<> &Builder,
01773                                             SmallVectorImpl<Factor> &Factors) {
01774   assert(Factors[0].Power);
01775   SmallVector<Value *, 4> OuterProduct;
01776   for (unsigned LastIdx = 0, Idx = 1, Size = Factors.size();
01777        Idx < Size && Factors[Idx].Power > 0; ++Idx) {
01778     if (Factors[Idx].Power != Factors[LastIdx].Power) {
01779       LastIdx = Idx;
01780       continue;
01781     }
01782 
01783     // We want to multiply across all the factors with the same power so that
01784     // we can raise them to that power as a single entity. Build a mini tree
01785     // for that.
01786     SmallVector<Value *, 4> InnerProduct;
01787     InnerProduct.push_back(Factors[LastIdx].Base);
01788     do {
01789       InnerProduct.push_back(Factors[Idx].Base);
01790       ++Idx;
01791     } while (Idx < Size && Factors[Idx].Power == Factors[LastIdx].Power);
01792 
01793     // Reset the base value of the first factor to the new expression tree.
01794     // We'll remove all the factors with the same power in a second pass.
01795     Value *M = Factors[LastIdx].Base = buildMultiplyTree(Builder, InnerProduct);
01796     if (Instruction *MI = dyn_cast<Instruction>(M))
01797       RedoInsts.insert(MI);
01798 
01799     LastIdx = Idx;
01800   }
01801   // Unique factors with equal powers -- we've folded them into the first one's
01802   // base.
01803   Factors.erase(std::unique(Factors.begin(), Factors.end(),
01804                             Factor::PowerEqual()),
01805                 Factors.end());
01806 
01807   // Iteratively collect the base of each factor with an add power into the
01808   // outer product, and halve each power in preparation for squaring the
01809   // expression.
01810   for (unsigned Idx = 0, Size = Factors.size(); Idx != Size; ++Idx) {
01811     if (Factors[Idx].Power & 1)
01812       OuterProduct.push_back(Factors[Idx].Base);
01813     Factors[Idx].Power >>= 1;
01814   }
01815   if (Factors[0].Power) {
01816     Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors);
01817     OuterProduct.push_back(SquareRoot);
01818     OuterProduct.push_back(SquareRoot);
01819   }
01820   if (OuterProduct.size() == 1)
01821     return OuterProduct.front();
01822 
01823   Value *V = buildMultiplyTree(Builder, OuterProduct);
01824   return V;
01825 }
01826 
01827 Value *Reassociate::OptimizeMul(BinaryOperator *I,
01828                                 SmallVectorImpl<ValueEntry> &Ops) {
01829   // We can only optimize the multiplies when there is a chain of more than
01830   // three, such that a balanced tree might require fewer total multiplies.
01831   if (Ops.size() < 4)
01832     return nullptr;
01833 
01834   // Try to turn linear trees of multiplies without other uses of the
01835   // intermediate stages into minimal multiply DAGs with perfect sub-expression
01836   // re-use.
01837   SmallVector<Factor, 4> Factors;
01838   if (!collectMultiplyFactors(Ops, Factors))
01839     return nullptr; // All distinct factors, so nothing left for us to do.
01840 
01841   IRBuilder<> Builder(I);
01842   Value *V = buildMinimalMultiplyDAG(Builder, Factors);
01843   if (Ops.empty())
01844     return V;
01845 
01846   ValueEntry NewEntry = ValueEntry(getRank(V), V);
01847   Ops.insert(std::lower_bound(Ops.begin(), Ops.end(), NewEntry), NewEntry);
01848   return nullptr;
01849 }
01850 
01851 Value *Reassociate::OptimizeExpression(BinaryOperator *I,
01852                                        SmallVectorImpl<ValueEntry> &Ops) {
01853   // Now that we have the linearized expression tree, try to optimize it.
01854   // Start by folding any constants that we found.
01855   Constant *Cst = nullptr;
01856   unsigned Opcode = I->getOpcode();
01857   while (!Ops.empty() && isa<Constant>(Ops.back().Op)) {
01858     Constant *C = cast<Constant>(Ops.pop_back_val().Op);
01859     Cst = Cst ? ConstantExpr::get(Opcode, C, Cst) : C;
01860   }
01861   // If there was nothing but constants then we are done.
01862   if (Ops.empty())
01863     return Cst;
01864 
01865   // Put the combined constant back at the end of the operand list, except if
01866   // there is no point.  For example, an add of 0 gets dropped here, while a
01867   // multiplication by zero turns the whole expression into zero.
01868   if (Cst && Cst != ConstantExpr::getBinOpIdentity(Opcode, I->getType())) {
01869     if (Cst == ConstantExpr::getBinOpAbsorber(Opcode, I->getType()))
01870       return Cst;
01871     Ops.push_back(ValueEntry(0, Cst));
01872   }
01873 
01874   if (Ops.size() == 1) return Ops[0].Op;
01875 
01876   // Handle destructive annihilation due to identities between elements in the
01877   // argument list here.
01878   unsigned NumOps = Ops.size();
01879   switch (Opcode) {
01880   default: break;
01881   case Instruction::And:
01882   case Instruction::Or:
01883     if (Value *Result = OptimizeAndOrXor(Opcode, Ops))
01884       return Result;
01885     break;
01886 
01887   case Instruction::Xor:
01888     if (Value *Result = OptimizeXor(I, Ops))
01889       return Result;
01890     break;
01891 
01892   case Instruction::Add:
01893   case Instruction::FAdd:
01894     if (Value *Result = OptimizeAdd(I, Ops))
01895       return Result;
01896     break;
01897 
01898   case Instruction::Mul:
01899   case Instruction::FMul:
01900     if (Value *Result = OptimizeMul(I, Ops))
01901       return Result;
01902     break;
01903   }
01904 
01905   if (Ops.size() != NumOps)
01906     return OptimizeExpression(I, Ops);
01907   return nullptr;
01908 }
01909 
01910 /// EraseInst - Zap the given instruction, adding interesting operands to the
01911 /// work list.
01912 void Reassociate::EraseInst(Instruction *I) {
01913   assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
01914   SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
01915   // Erase the dead instruction.
01916   ValueRankMap.erase(I);
01917   RedoInsts.remove(I);
01918   I->eraseFromParent();
01919   // Optimize its operands.
01920   SmallPtrSet<Instruction *, 8> Visited; // Detect self-referential nodes.
01921   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
01922     if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
01923       // If this is a node in an expression tree, climb to the expression root
01924       // and add that since that's where optimization actually happens.
01925       unsigned Opcode = Op->getOpcode();
01926       while (Op->hasOneUse() && Op->user_back()->getOpcode() == Opcode &&
01927              Visited.insert(Op))
01928         Op = Op->user_back();
01929       RedoInsts.insert(Op);
01930     }
01931 }
01932 
01933 void Reassociate::optimizeFAddNegExpr(ConstantFP *ConstOperand, Instruction *I,
01934                                       int OperandNr) {
01935   // Change the sign of the constant.
01936   APFloat Val = ConstOperand->getValueAPF();
01937   Val.changeSign();
01938   I->setOperand(0, ConstantFP::get(ConstOperand->getContext(), Val));
01939 
01940   assert(I->hasOneUse() && "Only a single use can be replaced.");
01941   Instruction *Parent = I->user_back();
01942 
01943   Value *OtherOperand = Parent->getOperand(1 - OperandNr);
01944 
01945   unsigned Opcode = Parent->getOpcode();
01946   assert(Opcode == Instruction::FAdd ||
01947          (Opcode == Instruction::FSub && Parent->getOperand(1) == I));
01948 
01949   BinaryOperator *NI = Opcode == Instruction::FAdd
01950                            ? BinaryOperator::CreateFSub(OtherOperand, I)
01951                            : BinaryOperator::CreateFAdd(OtherOperand, I);
01952   NI->setFastMathFlags(cast<FPMathOperator>(Parent)->getFastMathFlags());
01953   NI->insertBefore(Parent);
01954   NI->setName(Parent->getName() + ".repl");
01955   Parent->replaceAllUsesWith(NI);
01956   NI->setDebugLoc(I->getDebugLoc());
01957   MadeChange = true;
01958 }
01959 
01960 /// OptimizeInst - Inspect and optimize the given instruction. Note that erasing
01961 /// instructions is not allowed.
01962 void Reassociate::OptimizeInst(Instruction *I) {
01963   // Only consider operations that we understand.
01964   if (!isa<BinaryOperator>(I))
01965     return;
01966 
01967   if (I->getOpcode() == Instruction::Shl && isa<ConstantInt>(I->getOperand(1)))
01968     // If an operand of this shift is a reassociable multiply, or if the shift
01969     // is used by a reassociable multiply or add, turn into a multiply.
01970     if (isReassociableOp(I->getOperand(0), Instruction::Mul) ||
01971         (I->hasOneUse() &&
01972          (isReassociableOp(I->user_back(), Instruction::Mul) ||
01973           isReassociableOp(I->user_back(), Instruction::Add)))) {
01974       Instruction *NI = ConvertShiftToMul(I);
01975       RedoInsts.insert(I);
01976       MadeChange = true;
01977       I = NI;
01978     }
01979 
01980   // Commute floating point binary operators, to canonicalize the order of their
01981   // operands.  This can potentially expose more CSE opportunities, and makes
01982   // writing other transformations simpler.
01983   if (I->getType()->isFloatingPointTy() || I->getType()->isVectorTy()) {
01984 
01985     // FAdd and FMul can be commuted.
01986     unsigned Opcode = I->getOpcode();
01987     if (Opcode == Instruction::FMul || Opcode == Instruction::FAdd) {
01988       Value *LHS = I->getOperand(0);
01989       Value *RHS = I->getOperand(1);
01990       unsigned LHSRank = getRank(LHS);
01991       unsigned RHSRank = getRank(RHS);
01992 
01993       // Sort the operands by rank.
01994       if (RHSRank < LHSRank) {
01995         I->setOperand(0, RHS);
01996         I->setOperand(1, LHS);
01997       }
01998     }
01999 
02000     // Reassociate: x + -ConstantFP * y -> x - ConstantFP * y
02001     // The FMul can also be an FDiv, and FAdd can be a FSub.
02002     if (Opcode == Instruction::FMul || Opcode == Instruction::FDiv) {
02003       if (ConstantFP *LHSConst = dyn_cast<ConstantFP>(I->getOperand(0))) {
02004         if (LHSConst->isNegative() && I->hasOneUse()) {
02005           Instruction *Parent = I->user_back();
02006           if (Parent->getOpcode() == Instruction::FAdd) {
02007             if (Parent->getOperand(0) == I)
02008               optimizeFAddNegExpr(LHSConst, I, 0);
02009             else if (Parent->getOperand(1) == I)
02010               optimizeFAddNegExpr(LHSConst, I, 1);
02011           } else if (Parent->getOpcode() == Instruction::FSub)
02012             if (Parent->getOperand(1) == I)
02013               optimizeFAddNegExpr(LHSConst, I, 1);
02014         }
02015       }
02016     }
02017 
02018     // FIXME: We should commute vector instructions as well.  However, this 
02019     // requires further analysis to determine the effect on later passes.
02020 
02021     // Don't try to optimize vector instructions or anything that doesn't have
02022     // unsafe algebra.
02023     if (I->getType()->isVectorTy() || !I->hasUnsafeAlgebra())
02024       return;
02025   }
02026 
02027   // Do not reassociate boolean (i1) expressions.  We want to preserve the
02028   // original order of evaluation for short-circuited comparisons that
02029   // SimplifyCFG has folded to AND/OR expressions.  If the expression
02030   // is not further optimized, it is likely to be transformed back to a
02031   // short-circuited form for code gen, and the source order may have been
02032   // optimized for the most likely conditions.
02033   if (I->getType()->isIntegerTy(1))
02034     return;
02035 
02036   // If this is a subtract instruction which is not already in negate form,
02037   // see if we can convert it to X+-Y.
02038   if (I->getOpcode() == Instruction::Sub) {
02039     if (ShouldBreakUpSubtract(I)) {
02040       Instruction *NI = BreakUpSubtract(I);
02041       RedoInsts.insert(I);
02042       MadeChange = true;
02043       I = NI;
02044     } else if (BinaryOperator::isNeg(I)) {
02045       // Otherwise, this is a negation.  See if the operand is a multiply tree
02046       // and if this is not an inner node of a multiply tree.
02047       if (isReassociableOp(I->getOperand(1), Instruction::Mul) &&
02048           (!I->hasOneUse() ||
02049            !isReassociableOp(I->user_back(), Instruction::Mul))) {
02050         Instruction *NI = LowerNegateToMultiply(I);
02051         RedoInsts.insert(I);
02052         MadeChange = true;
02053         I = NI;
02054       }
02055     }
02056   } else if (I->getOpcode() == Instruction::FSub) {
02057     if (ShouldBreakUpSubtract(I)) {
02058       Instruction *NI = BreakUpSubtract(I);
02059       RedoInsts.insert(I);
02060       MadeChange = true;
02061       I = NI;
02062     } else if (BinaryOperator::isFNeg(I)) {
02063       // Otherwise, this is a negation.  See if the operand is a multiply tree
02064       // and if this is not an inner node of a multiply tree.
02065       if (isReassociableOp(I->getOperand(1), Instruction::FMul) &&
02066           (!I->hasOneUse() ||
02067            !isReassociableOp(I->user_back(), Instruction::FMul))) {
02068         Instruction *NI = LowerNegateToMultiply(I);
02069         RedoInsts.insert(I);
02070         MadeChange = true;
02071         I = NI;
02072       }
02073     }
02074   }
02075 
02076   // If this instruction is an associative binary operator, process it.
02077   if (!I->isAssociative()) return;
02078   BinaryOperator *BO = cast<BinaryOperator>(I);
02079 
02080   // If this is an interior node of a reassociable tree, ignore it until we
02081   // get to the root of the tree, to avoid N^2 analysis.
02082   unsigned Opcode = BO->getOpcode();
02083   if (BO->hasOneUse() && BO->user_back()->getOpcode() == Opcode)
02084     return;
02085 
02086   // If this is an add tree that is used by a sub instruction, ignore it
02087   // until we process the subtract.
02088   if (BO->hasOneUse() && BO->getOpcode() == Instruction::Add &&
02089       cast<Instruction>(BO->user_back())->getOpcode() == Instruction::Sub)
02090     return;
02091   if (BO->hasOneUse() && BO->getOpcode() == Instruction::FAdd &&
02092       cast<Instruction>(BO->user_back())->getOpcode() == Instruction::FSub)
02093     return;
02094 
02095   ReassociateExpression(BO);
02096 }
02097 
02098 void Reassociate::ReassociateExpression(BinaryOperator *I) {
02099   assert(!I->getType()->isVectorTy() &&
02100          "Reassociation of vector instructions is not supported.");
02101 
02102   // First, walk the expression tree, linearizing the tree, collecting the
02103   // operand information.
02104   SmallVector<RepeatedValue, 8> Tree;
02105   MadeChange |= LinearizeExprTree(I, Tree);
02106   SmallVector<ValueEntry, 8> Ops;
02107   Ops.reserve(Tree.size());
02108   for (unsigned i = 0, e = Tree.size(); i != e; ++i) {
02109     RepeatedValue E = Tree[i];
02110     Ops.append(E.second.getZExtValue(),
02111                ValueEntry(getRank(E.first), E.first));
02112   }
02113 
02114   DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n');
02115 
02116   // Now that we have linearized the tree to a list and have gathered all of
02117   // the operands and their ranks, sort the operands by their rank.  Use a
02118   // stable_sort so that values with equal ranks will have their relative
02119   // positions maintained (and so the compiler is deterministic).  Note that
02120   // this sorts so that the highest ranking values end up at the beginning of
02121   // the vector.
02122   std::stable_sort(Ops.begin(), Ops.end());
02123 
02124   // OptimizeExpression - Now that we have the expression tree in a convenient
02125   // sorted form, optimize it globally if possible.
02126   if (Value *V = OptimizeExpression(I, Ops)) {
02127     if (V == I)
02128       // Self-referential expression in unreachable code.
02129       return;
02130     // This expression tree simplified to something that isn't a tree,
02131     // eliminate it.
02132     DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n');
02133     I->replaceAllUsesWith(V);
02134     if (Instruction *VI = dyn_cast<Instruction>(V))
02135       VI->setDebugLoc(I->getDebugLoc());
02136     RedoInsts.insert(I);
02137     ++NumAnnihil;
02138     return;
02139   }
02140 
02141   // We want to sink immediates as deeply as possible except in the case where
02142   // this is a multiply tree used only by an add, and the immediate is a -1.
02143   // In this case we reassociate to put the negation on the outside so that we
02144   // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y
02145   if (I->hasOneUse()) {
02146     if (I->getOpcode() == Instruction::Mul &&
02147         cast<Instruction>(I->user_back())->getOpcode() == Instruction::Add &&
02148         isa<ConstantInt>(Ops.back().Op) &&
02149         cast<ConstantInt>(Ops.back().Op)->isAllOnesValue()) {
02150       ValueEntry Tmp = Ops.pop_back_val();
02151       Ops.insert(Ops.begin(), Tmp);
02152     } else if (I->getOpcode() == Instruction::FMul &&
02153                cast<Instruction>(I->user_back())->getOpcode() ==
02154                    Instruction::FAdd &&
02155                isa<ConstantFP>(Ops.back().Op) &&
02156                cast<ConstantFP>(Ops.back().Op)->isExactlyValue(-1.0)) {
02157       ValueEntry Tmp = Ops.pop_back_val();
02158       Ops.insert(Ops.begin(), Tmp);
02159     }
02160   }
02161 
02162   DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n');
02163 
02164   if (Ops.size() == 1) {
02165     if (Ops[0].Op == I)
02166       // Self-referential expression in unreachable code.
02167       return;
02168 
02169     // This expression tree simplified to something that isn't a tree,
02170     // eliminate it.
02171     I->replaceAllUsesWith(Ops[0].Op);
02172     if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op))
02173       OI->setDebugLoc(I->getDebugLoc());
02174     RedoInsts.insert(I);
02175     return;
02176   }
02177 
02178   // Now that we ordered and optimized the expressions, splat them back into
02179   // the expression tree, removing any unneeded nodes.
02180   RewriteExprTree(I, Ops);
02181 }
02182 
02183 bool Reassociate::runOnFunction(Function &F) {
02184   if (skipOptnoneFunction(F))
02185     return false;
02186 
02187   // Calculate the rank map for F
02188   BuildRankMap(F);
02189 
02190   MadeChange = false;
02191   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
02192     // Optimize every instruction in the basic block.
02193     for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; )
02194       if (isInstructionTriviallyDead(II)) {
02195         EraseInst(II++);
02196       } else {
02197         OptimizeInst(II);
02198         assert(II->getParent() == BI && "Moved to a different block!");
02199         ++II;
02200       }
02201 
02202     // If this produced extra instructions to optimize, handle them now.
02203     while (!RedoInsts.empty()) {
02204       Instruction *I = RedoInsts.pop_back_val();
02205       if (isInstructionTriviallyDead(I))
02206         EraseInst(I);
02207       else
02208         OptimizeInst(I);
02209     }
02210   }
02211 
02212   // We are done with the rank map.
02213   RankMap.clear();
02214   ValueRankMap.clear();
02215 
02216   return MadeChange;
02217 }