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