xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp (revision 38a52bd3b5cac3da6f7f6eef3dd050e6aa08ebb3)
1 //===- Reassociate.cpp - Reassociate binary expressions -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass reassociates commutative expressions in an order that is designed
10 // to promote better constant propagation, GCSE, LICM, PRE, etc.
11 //
12 // For example: 4 + (x + 5) -> x + (4 + 5)
13 //
14 // In the implementation of this algorithm, constants are assigned rank = 0,
15 // function arguments are rank = 1, and other values are assigned ranks
16 // corresponding to the reverse post order traversal of current function
17 // (starting at 2), which effectively gives values in deep loops higher rank
18 // than values not in loops.
19 //
20 //===----------------------------------------------------------------------===//
21 
22 #include "llvm/Transforms/Scalar/Reassociate.h"
23 #include "llvm/ADT/APFloat.h"
24 #include "llvm/ADT/APInt.h"
25 #include "llvm/ADT/DenseMap.h"
26 #include "llvm/ADT/PostOrderIterator.h"
27 #include "llvm/ADT/SetVector.h"
28 #include "llvm/ADT/SmallPtrSet.h"
29 #include "llvm/ADT/SmallSet.h"
30 #include "llvm/ADT/SmallVector.h"
31 #include "llvm/ADT/Statistic.h"
32 #include "llvm/Analysis/BasicAliasAnalysis.h"
33 #include "llvm/Analysis/GlobalsModRef.h"
34 #include "llvm/Analysis/ValueTracking.h"
35 #include "llvm/IR/Argument.h"
36 #include "llvm/IR/BasicBlock.h"
37 #include "llvm/IR/CFG.h"
38 #include "llvm/IR/Constant.h"
39 #include "llvm/IR/Constants.h"
40 #include "llvm/IR/Function.h"
41 #include "llvm/IR/IRBuilder.h"
42 #include "llvm/IR/InstrTypes.h"
43 #include "llvm/IR/Instruction.h"
44 #include "llvm/IR/Instructions.h"
45 #include "llvm/IR/IntrinsicInst.h"
46 #include "llvm/IR/Operator.h"
47 #include "llvm/IR/PassManager.h"
48 #include "llvm/IR/PatternMatch.h"
49 #include "llvm/IR/Type.h"
50 #include "llvm/IR/User.h"
51 #include "llvm/IR/Value.h"
52 #include "llvm/IR/ValueHandle.h"
53 #include "llvm/InitializePasses.h"
54 #include "llvm/Pass.h"
55 #include "llvm/Support/Casting.h"
56 #include "llvm/Support/Debug.h"
57 #include "llvm/Support/ErrorHandling.h"
58 #include "llvm/Support/raw_ostream.h"
59 #include "llvm/Transforms/Scalar.h"
60 #include "llvm/Transforms/Utils/Local.h"
61 #include <algorithm>
62 #include <cassert>
63 #include <utility>
64 
65 using namespace llvm;
66 using namespace reassociate;
67 using namespace PatternMatch;
68 
69 #define DEBUG_TYPE "reassociate"
70 
71 STATISTIC(NumChanged, "Number of insts reassociated");
72 STATISTIC(NumAnnihil, "Number of expr tree annihilated");
73 STATISTIC(NumFactor , "Number of multiplies factored");
74 
75 #ifndef NDEBUG
76 /// Print out the expression identified in the Ops list.
77 static void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) {
78   Module *M = I->getModule();
79   dbgs() << Instruction::getOpcodeName(I->getOpcode()) << " "
80        << *Ops[0].Op->getType() << '\t';
81   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
82     dbgs() << "[ ";
83     Ops[i].Op->printAsOperand(dbgs(), false, M);
84     dbgs() << ", #" << Ops[i].Rank << "] ";
85   }
86 }
87 #endif
88 
89 /// Utility class representing a non-constant Xor-operand. We classify
90 /// non-constant Xor-Operands into two categories:
91 ///  C1) The operand is in the form "X & C", where C is a constant and C != ~0
92 ///  C2)
93 ///    C2.1) The operand is in the form of "X | C", where C is a non-zero
94 ///          constant.
95 ///    C2.2) Any operand E which doesn't fall into C1 and C2.1, we view this
96 ///          operand as "E | 0"
97 class llvm::reassociate::XorOpnd {
98 public:
99   XorOpnd(Value *V);
100 
101   bool isInvalid() const { return SymbolicPart == nullptr; }
102   bool isOrExpr() const { return isOr; }
103   Value *getValue() const { return OrigVal; }
104   Value *getSymbolicPart() const { return SymbolicPart; }
105   unsigned getSymbolicRank() const { return SymbolicRank; }
106   const APInt &getConstPart() const { return ConstPart; }
107 
108   void Invalidate() { SymbolicPart = OrigVal = nullptr; }
109   void setSymbolicRank(unsigned R) { SymbolicRank = R; }
110 
111 private:
112   Value *OrigVal;
113   Value *SymbolicPart;
114   APInt ConstPart;
115   unsigned SymbolicRank;
116   bool isOr;
117 };
118 
119 XorOpnd::XorOpnd(Value *V) {
120   assert(!isa<ConstantInt>(V) && "No ConstantInt");
121   OrigVal = V;
122   Instruction *I = dyn_cast<Instruction>(V);
123   SymbolicRank = 0;
124 
125   if (I && (I->getOpcode() == Instruction::Or ||
126             I->getOpcode() == Instruction::And)) {
127     Value *V0 = I->getOperand(0);
128     Value *V1 = I->getOperand(1);
129     const APInt *C;
130     if (match(V0, m_APInt(C)))
131       std::swap(V0, V1);
132 
133     if (match(V1, m_APInt(C))) {
134       ConstPart = *C;
135       SymbolicPart = V0;
136       isOr = (I->getOpcode() == Instruction::Or);
137       return;
138     }
139   }
140 
141   // view the operand as "V | 0"
142   SymbolicPart = V;
143   ConstPart = APInt::getZero(V->getType()->getScalarSizeInBits());
144   isOr = true;
145 }
146 
147 /// Return true if V is an instruction of the specified opcode and if it
148 /// only has one use.
149 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) {
150   auto *I = dyn_cast<Instruction>(V);
151   if (I && I->hasOneUse() && I->getOpcode() == Opcode)
152     if (!isa<FPMathOperator>(I) || I->isFast())
153       return cast<BinaryOperator>(I);
154   return nullptr;
155 }
156 
157 static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode1,
158                                         unsigned Opcode2) {
159   auto *I = dyn_cast<Instruction>(V);
160   if (I && I->hasOneUse() &&
161       (I->getOpcode() == Opcode1 || I->getOpcode() == Opcode2))
162     if (!isa<FPMathOperator>(I) || I->isFast())
163       return cast<BinaryOperator>(I);
164   return nullptr;
165 }
166 
167 void ReassociatePass::BuildRankMap(Function &F,
168                                    ReversePostOrderTraversal<Function*> &RPOT) {
169   unsigned Rank = 2;
170 
171   // Assign distinct ranks to function arguments.
172   for (auto &Arg : F.args()) {
173     ValueRankMap[&Arg] = ++Rank;
174     LLVM_DEBUG(dbgs() << "Calculated Rank[" << Arg.getName() << "] = " << Rank
175                       << "\n");
176   }
177 
178   // Traverse basic blocks in ReversePostOrder.
179   for (BasicBlock *BB : RPOT) {
180     unsigned BBRank = RankMap[BB] = ++Rank << 16;
181 
182     // Walk the basic block, adding precomputed ranks for any instructions that
183     // we cannot move.  This ensures that the ranks for these instructions are
184     // all different in the block.
185     for (Instruction &I : *BB)
186       if (mayBeMemoryDependent(I))
187         ValueRankMap[&I] = ++BBRank;
188   }
189 }
190 
191 unsigned ReassociatePass::getRank(Value *V) {
192   Instruction *I = dyn_cast<Instruction>(V);
193   if (!I) {
194     if (isa<Argument>(V)) return ValueRankMap[V];   // Function argument.
195     return 0;  // Otherwise it's a global or constant, rank 0.
196   }
197 
198   if (unsigned Rank = ValueRankMap[I])
199     return Rank;    // Rank already known?
200 
201   // If this is an expression, return the 1+MAX(rank(LHS), rank(RHS)) so that
202   // we can reassociate expressions for code motion!  Since we do not recurse
203   // for PHI nodes, we cannot have infinite recursion here, because there
204   // cannot be loops in the value graph that do not go through PHI nodes.
205   unsigned Rank = 0, MaxRank = RankMap[I->getParent()];
206   for (unsigned i = 0, e = I->getNumOperands(); i != e && Rank != MaxRank; ++i)
207     Rank = std::max(Rank, getRank(I->getOperand(i)));
208 
209   // If this is a 'not' or 'neg' instruction, do not count it for rank. This
210   // assures us that X and ~X will have the same rank.
211   if (!match(I, m_Not(m_Value())) && !match(I, m_Neg(m_Value())) &&
212       !match(I, m_FNeg(m_Value())))
213     ++Rank;
214 
215   LLVM_DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = " << Rank
216                     << "\n");
217 
218   return ValueRankMap[I] = Rank;
219 }
220 
221 // Canonicalize constants to RHS.  Otherwise, sort the operands by rank.
222 void ReassociatePass::canonicalizeOperands(Instruction *I) {
223   assert(isa<BinaryOperator>(I) && "Expected binary operator.");
224   assert(I->isCommutative() && "Expected commutative operator.");
225 
226   Value *LHS = I->getOperand(0);
227   Value *RHS = I->getOperand(1);
228   if (LHS == RHS || isa<Constant>(RHS))
229     return;
230   if (isa<Constant>(LHS) || getRank(RHS) < getRank(LHS))
231     cast<BinaryOperator>(I)->swapOperands();
232 }
233 
234 static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name,
235                                  Instruction *InsertBefore, Value *FlagsOp) {
236   if (S1->getType()->isIntOrIntVectorTy())
237     return BinaryOperator::CreateAdd(S1, S2, Name, InsertBefore);
238   else {
239     BinaryOperator *Res =
240         BinaryOperator::CreateFAdd(S1, S2, Name, InsertBefore);
241     Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags());
242     return Res;
243   }
244 }
245 
246 static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name,
247                                  Instruction *InsertBefore, Value *FlagsOp) {
248   if (S1->getType()->isIntOrIntVectorTy())
249     return BinaryOperator::CreateMul(S1, S2, Name, InsertBefore);
250   else {
251     BinaryOperator *Res =
252       BinaryOperator::CreateFMul(S1, S2, Name, InsertBefore);
253     Res->setFastMathFlags(cast<FPMathOperator>(FlagsOp)->getFastMathFlags());
254     return Res;
255   }
256 }
257 
258 static Instruction *CreateNeg(Value *S1, const Twine &Name,
259                               Instruction *InsertBefore, Value *FlagsOp) {
260   if (S1->getType()->isIntOrIntVectorTy())
261     return BinaryOperator::CreateNeg(S1, Name, InsertBefore);
262 
263   if (auto *FMFSource = dyn_cast<Instruction>(FlagsOp))
264     return UnaryOperator::CreateFNegFMF(S1, FMFSource, Name, InsertBefore);
265 
266   return UnaryOperator::CreateFNeg(S1, Name, InsertBefore);
267 }
268 
269 /// Replace 0-X with X*-1.
270 static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) {
271   assert((isa<UnaryOperator>(Neg) || isa<BinaryOperator>(Neg)) &&
272          "Expected a Negate!");
273   // FIXME: It's not safe to lower a unary FNeg into a FMul by -1.0.
274   unsigned OpNo = isa<BinaryOperator>(Neg) ? 1 : 0;
275   Type *Ty = Neg->getType();
276   Constant *NegOne = Ty->isIntOrIntVectorTy() ?
277     ConstantInt::getAllOnesValue(Ty) : ConstantFP::get(Ty, -1.0);
278 
279   BinaryOperator *Res = CreateMul(Neg->getOperand(OpNo), NegOne, "", Neg, Neg);
280   Neg->setOperand(OpNo, Constant::getNullValue(Ty)); // Drop use of op.
281   Res->takeName(Neg);
282   Neg->replaceAllUsesWith(Res);
283   Res->setDebugLoc(Neg->getDebugLoc());
284   return Res;
285 }
286 
287 /// Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael
288 /// function. This means that x^(2^k) === 1 mod 2^Bitwidth for
289 /// every odd x, i.e. x^(2^k) = 1 for every odd x in Bitwidth-bit arithmetic.
290 /// Note that 0 <= k < Bitwidth, and if Bitwidth > 3 then x^(2^k) = 0 for every
291 /// even x in Bitwidth-bit arithmetic.
292 static unsigned CarmichaelShift(unsigned Bitwidth) {
293   if (Bitwidth < 3)
294     return Bitwidth - 1;
295   return Bitwidth - 2;
296 }
297 
298 /// Add the extra weight 'RHS' to the existing weight 'LHS',
299 /// reducing the combined weight using any special properties of the operation.
300 /// The existing weight LHS represents the computation X op X op ... op X where
301 /// X occurs LHS times.  The combined weight represents  X op X op ... op X with
302 /// X occurring LHS + RHS times.  If op is "Xor" for example then the combined
303 /// operation is equivalent to X if LHS + RHS is odd, or 0 if LHS + RHS is even;
304 /// the routine returns 1 in LHS in the first case, and 0 in LHS in the second.
305 static void IncorporateWeight(APInt &LHS, const APInt &RHS, unsigned Opcode) {
306   // If we were working with infinite precision arithmetic then the combined
307   // weight would be LHS + RHS.  But we are using finite precision arithmetic,
308   // and the APInt sum LHS + RHS may not be correct if it wraps (it is correct
309   // for nilpotent operations and addition, but not for idempotent operations
310   // and multiplication), so it is important to correctly reduce the combined
311   // weight back into range if wrapping would be wrong.
312 
313   // If RHS is zero then the weight didn't change.
314   if (RHS.isMinValue())
315     return;
316   // If LHS is zero then the combined weight is RHS.
317   if (LHS.isMinValue()) {
318     LHS = RHS;
319     return;
320   }
321   // From this point on we know that neither LHS nor RHS is zero.
322 
323   if (Instruction::isIdempotent(Opcode)) {
324     // Idempotent means X op X === X, so any non-zero weight is equivalent to a
325     // weight of 1.  Keeping weights at zero or one also means that wrapping is
326     // not a problem.
327     assert(LHS == 1 && RHS == 1 && "Weights not reduced!");
328     return; // Return a weight of 1.
329   }
330   if (Instruction::isNilpotent(Opcode)) {
331     // Nilpotent means X op X === 0, so reduce weights modulo 2.
332     assert(LHS == 1 && RHS == 1 && "Weights not reduced!");
333     LHS = 0; // 1 + 1 === 0 modulo 2.
334     return;
335   }
336   if (Opcode == Instruction::Add || Opcode == Instruction::FAdd) {
337     // TODO: Reduce the weight by exploiting nsw/nuw?
338     LHS += RHS;
339     return;
340   }
341 
342   assert((Opcode == Instruction::Mul || Opcode == Instruction::FMul) &&
343          "Unknown associative operation!");
344   unsigned Bitwidth = LHS.getBitWidth();
345   // If CM is the Carmichael number then a weight W satisfying W >= CM+Bitwidth
346   // can be replaced with W-CM.  That's because x^W=x^(W-CM) for every Bitwidth
347   // bit number x, since either x is odd in which case x^CM = 1, or x is even in
348   // which case both x^W and x^(W - CM) are zero.  By subtracting off multiples
349   // of CM like this weights can always be reduced to the range [0, CM+Bitwidth)
350   // which by a happy accident means that they can always be represented using
351   // Bitwidth bits.
352   // TODO: Reduce the weight by exploiting nsw/nuw?  (Could do much better than
353   // the Carmichael number).
354   if (Bitwidth > 3) {
355     /// CM - The value of Carmichael's lambda function.
356     APInt CM = APInt::getOneBitSet(Bitwidth, CarmichaelShift(Bitwidth));
357     // Any weight W >= Threshold can be replaced with W - CM.
358     APInt Threshold = CM + Bitwidth;
359     assert(LHS.ult(Threshold) && RHS.ult(Threshold) && "Weights not reduced!");
360     // For Bitwidth 4 or more the following sum does not overflow.
361     LHS += RHS;
362     while (LHS.uge(Threshold))
363       LHS -= CM;
364   } else {
365     // To avoid problems with overflow do everything the same as above but using
366     // a larger type.
367     unsigned CM = 1U << CarmichaelShift(Bitwidth);
368     unsigned Threshold = CM + Bitwidth;
369     assert(LHS.getZExtValue() < Threshold && RHS.getZExtValue() < Threshold &&
370            "Weights not reduced!");
371     unsigned Total = LHS.getZExtValue() + RHS.getZExtValue();
372     while (Total >= Threshold)
373       Total -= CM;
374     LHS = Total;
375   }
376 }
377 
378 using RepeatedValue = std::pair<Value*, APInt>;
379 
380 /// Given an associative binary expression, return the leaf
381 /// nodes in Ops along with their weights (how many times the leaf occurs).  The
382 /// original expression is the same as
383 ///   (Ops[0].first op Ops[0].first op ... Ops[0].first)  <- Ops[0].second times
384 /// op
385 ///   (Ops[1].first op Ops[1].first op ... Ops[1].first)  <- Ops[1].second times
386 /// op
387 ///   ...
388 /// op
389 ///   (Ops[N].first op Ops[N].first op ... Ops[N].first)  <- Ops[N].second times
390 ///
391 /// Note that the values Ops[0].first, ..., Ops[N].first are all distinct.
392 ///
393 /// This routine may modify the function, in which case it returns 'true'.  The
394 /// changes it makes may well be destructive, changing the value computed by 'I'
395 /// to something completely different.  Thus if the routine returns 'true' then
396 /// you MUST either replace I with a new expression computed from the Ops array,
397 /// or use RewriteExprTree to put the values back in.
398 ///
399 /// A leaf node is either not a binary operation of the same kind as the root
400 /// node 'I' (i.e. is not a binary operator at all, or is, but with a different
401 /// opcode), or is the same kind of binary operator but has a use which either
402 /// does not belong to the expression, or does belong to the expression but is
403 /// a leaf node.  Every leaf node has at least one use that is a non-leaf node
404 /// of the expression, while for non-leaf nodes (except for the root 'I') every
405 /// use is a non-leaf node of the expression.
406 ///
407 /// For example:
408 ///           expression graph        node names
409 ///
410 ///                     +        |        I
411 ///                    / \       |
412 ///                   +   +      |      A,  B
413 ///                  / \ / \     |
414 ///                 *   +   *    |    C,  D,  E
415 ///                / \ / \ / \   |
416 ///                   +   *      |      F,  G
417 ///
418 /// The leaf nodes are C, E, F and G.  The Ops array will contain (maybe not in
419 /// that order) (C, 1), (E, 1), (F, 2), (G, 2).
420 ///
421 /// The expression is maximal: if some instruction is a binary operator of the
422 /// same kind as 'I', and all of its uses are non-leaf nodes of the expression,
423 /// then the instruction also belongs to the expression, is not a leaf node of
424 /// it, and its operands also belong to the expression (but may be leaf nodes).
425 ///
426 /// NOTE: This routine will set operands of non-leaf non-root nodes to undef in
427 /// order to ensure that every non-root node in the expression has *exactly one*
428 /// use by a non-leaf node of the expression.  This destruction means that the
429 /// caller MUST either replace 'I' with a new expression or use something like
430 /// RewriteExprTree to put the values back in if the routine indicates that it
431 /// made a change by returning 'true'.
432 ///
433 /// In the above example either the right operand of A or the left operand of B
434 /// will be replaced by undef.  If it is B's operand then this gives:
435 ///
436 ///                     +        |        I
437 ///                    / \       |
438 ///                   +   +      |      A,  B - operand of B replaced with undef
439 ///                  / \   \     |
440 ///                 *   +   *    |    C,  D,  E
441 ///                / \ / \ / \   |
442 ///                   +   *      |      F,  G
443 ///
444 /// Note that such undef operands can only be reached by passing through 'I'.
445 /// For example, if you visit operands recursively starting from a leaf node
446 /// then you will never see such an undef operand unless you get back to 'I',
447 /// which requires passing through a phi node.
448 ///
449 /// Note that this routine may also mutate binary operators of the wrong type
450 /// that have all uses inside the expression (i.e. only used by non-leaf nodes
451 /// of the expression) if it can turn them into binary operators of the right
452 /// type and thus make the expression bigger.
453 static bool LinearizeExprTree(Instruction *I,
454                               SmallVectorImpl<RepeatedValue> &Ops) {
455   assert((isa<UnaryOperator>(I) || isa<BinaryOperator>(I)) &&
456          "Expected a UnaryOperator or BinaryOperator!");
457   LLVM_DEBUG(dbgs() << "LINEARIZE: " << *I << '\n');
458   unsigned Bitwidth = I->getType()->getScalarType()->getPrimitiveSizeInBits();
459   unsigned Opcode = I->getOpcode();
460   assert(I->isAssociative() && I->isCommutative() &&
461          "Expected an associative and commutative operation!");
462 
463   // Visit all operands of the expression, keeping track of their weight (the
464   // number of paths from the expression root to the operand, or if you like
465   // the number of times that operand occurs in the linearized expression).
466   // For example, if I = X + A, where X = A + B, then I, X and B have weight 1
467   // while A has weight two.
468 
469   // Worklist of non-leaf nodes (their operands are in the expression too) along
470   // with their weights, representing a certain number of paths to the operator.
471   // If an operator occurs in the worklist multiple times then we found multiple
472   // ways to get to it.
473   SmallVector<std::pair<Instruction*, APInt>, 8> Worklist; // (Op, Weight)
474   Worklist.push_back(std::make_pair(I, APInt(Bitwidth, 1)));
475   bool Changed = false;
476 
477   // Leaves of the expression are values that either aren't the right kind of
478   // operation (eg: a constant, or a multiply in an add tree), or are, but have
479   // some uses that are not inside the expression.  For example, in I = X + X,
480   // X = A + B, the value X has two uses (by I) that are in the expression.  If
481   // X has any other uses, for example in a return instruction, then we consider
482   // X to be a leaf, and won't analyze it further.  When we first visit a value,
483   // if it has more than one use then at first we conservatively consider it to
484   // be a leaf.  Later, as the expression is explored, we may discover some more
485   // uses of the value from inside the expression.  If all uses turn out to be
486   // from within the expression (and the value is a binary operator of the right
487   // kind) then the value is no longer considered to be a leaf, and its operands
488   // are explored.
489 
490   // Leaves - Keeps track of the set of putative leaves as well as the number of
491   // paths to each leaf seen so far.
492   using LeafMap = DenseMap<Value *, APInt>;
493   LeafMap Leaves; // Leaf -> Total weight so far.
494   SmallVector<Value *, 8> LeafOrder; // Ensure deterministic leaf output order.
495 
496 #ifndef NDEBUG
497   SmallPtrSet<Value *, 8> Visited; // For checking the iteration scheme.
498 #endif
499   while (!Worklist.empty()) {
500     std::pair<Instruction*, APInt> P = Worklist.pop_back_val();
501     I = P.first; // We examine the operands of this binary operator.
502 
503     for (unsigned OpIdx = 0; OpIdx < I->getNumOperands(); ++OpIdx) { // Visit operands.
504       Value *Op = I->getOperand(OpIdx);
505       APInt Weight = P.second; // Number of paths to this operand.
506       LLVM_DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n");
507       assert(!Op->use_empty() && "No uses, so how did we get to it?!");
508 
509       // If this is a binary operation of the right kind with only one use then
510       // add its operands to the expression.
511       if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
512         assert(Visited.insert(Op).second && "Not first visit!");
513         LLVM_DEBUG(dbgs() << "DIRECT ADD: " << *Op << " (" << Weight << ")\n");
514         Worklist.push_back(std::make_pair(BO, Weight));
515         continue;
516       }
517 
518       // Appears to be a leaf.  Is the operand already in the set of leaves?
519       LeafMap::iterator It = Leaves.find(Op);
520       if (It == Leaves.end()) {
521         // Not in the leaf map.  Must be the first time we saw this operand.
522         assert(Visited.insert(Op).second && "Not first visit!");
523         if (!Op->hasOneUse()) {
524           // This value has uses not accounted for by the expression, so it is
525           // not safe to modify.  Mark it as being a leaf.
526           LLVM_DEBUG(dbgs()
527                      << "ADD USES LEAF: " << *Op << " (" << Weight << ")\n");
528           LeafOrder.push_back(Op);
529           Leaves[Op] = Weight;
530           continue;
531         }
532         // No uses outside the expression, try morphing it.
533       } else {
534         // Already in the leaf map.
535         assert(It != Leaves.end() && Visited.count(Op) &&
536                "In leaf map but not visited!");
537 
538         // Update the number of paths to the leaf.
539         IncorporateWeight(It->second, Weight, Opcode);
540 
541 #if 0   // TODO: Re-enable once PR13021 is fixed.
542         // The leaf already has one use from inside the expression.  As we want
543         // exactly one such use, drop this new use of the leaf.
544         assert(!Op->hasOneUse() && "Only one use, but we got here twice!");
545         I->setOperand(OpIdx, UndefValue::get(I->getType()));
546         Changed = true;
547 
548         // If the leaf is a binary operation of the right kind and we now see
549         // that its multiple original uses were in fact all by nodes belonging
550         // to the expression, then no longer consider it to be a leaf and add
551         // its operands to the expression.
552         if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
553           LLVM_DEBUG(dbgs() << "UNLEAF: " << *Op << " (" << It->second << ")\n");
554           Worklist.push_back(std::make_pair(BO, It->second));
555           Leaves.erase(It);
556           continue;
557         }
558 #endif
559 
560         // If we still have uses that are not accounted for by the expression
561         // then it is not safe to modify the value.
562         if (!Op->hasOneUse())
563           continue;
564 
565         // No uses outside the expression, try morphing it.
566         Weight = It->second;
567         Leaves.erase(It); // Since the value may be morphed below.
568       }
569 
570       // At this point we have a value which, first of all, is not a binary
571       // expression of the right kind, and secondly, is only used inside the
572       // expression.  This means that it can safely be modified.  See if we
573       // can usefully morph it into an expression of the right kind.
574       assert((!isa<Instruction>(Op) ||
575               cast<Instruction>(Op)->getOpcode() != Opcode
576               || (isa<FPMathOperator>(Op) &&
577                   !cast<Instruction>(Op)->isFast())) &&
578              "Should have been handled above!");
579       assert(Op->hasOneUse() && "Has uses outside the expression tree!");
580 
581       // If this is a multiply expression, turn any internal negations into
582       // multiplies by -1 so they can be reassociated.
583       if (Instruction *Tmp = dyn_cast<Instruction>(Op))
584         if ((Opcode == Instruction::Mul && match(Tmp, m_Neg(m_Value()))) ||
585             (Opcode == Instruction::FMul && match(Tmp, m_FNeg(m_Value())))) {
586           LLVM_DEBUG(dbgs()
587                      << "MORPH LEAF: " << *Op << " (" << Weight << ") TO ");
588           Tmp = LowerNegateToMultiply(Tmp);
589           LLVM_DEBUG(dbgs() << *Tmp << '\n');
590           Worklist.push_back(std::make_pair(Tmp, Weight));
591           Changed = true;
592           continue;
593         }
594 
595       // Failed to morph into an expression of the right type.  This really is
596       // a leaf.
597       LLVM_DEBUG(dbgs() << "ADD LEAF: " << *Op << " (" << Weight << ")\n");
598       assert(!isReassociableOp(Op, Opcode) && "Value was morphed?");
599       LeafOrder.push_back(Op);
600       Leaves[Op] = Weight;
601     }
602   }
603 
604   // The leaves, repeated according to their weights, represent the linearized
605   // form of the expression.
606   for (unsigned i = 0, e = LeafOrder.size(); i != e; ++i) {
607     Value *V = LeafOrder[i];
608     LeafMap::iterator It = Leaves.find(V);
609     if (It == Leaves.end())
610       // Node initially thought to be a leaf wasn't.
611       continue;
612     assert(!isReassociableOp(V, Opcode) && "Shouldn't be a leaf!");
613     APInt Weight = It->second;
614     if (Weight.isMinValue())
615       // Leaf already output or weight reduction eliminated it.
616       continue;
617     // Ensure the leaf is only output once.
618     It->second = 0;
619     Ops.push_back(std::make_pair(V, Weight));
620   }
621 
622   // For nilpotent operations or addition there may be no operands, for example
623   // because the expression was "X xor X" or consisted of 2^Bitwidth additions:
624   // in both cases the weight reduces to 0 causing the value to be skipped.
625   if (Ops.empty()) {
626     Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, I->getType());
627     assert(Identity && "Associative operation without identity!");
628     Ops.emplace_back(Identity, APInt(Bitwidth, 1));
629   }
630 
631   return Changed;
632 }
633 
634 /// Now that the operands for this expression tree are
635 /// linearized and optimized, emit them in-order.
636 void ReassociatePass::RewriteExprTree(BinaryOperator *I,
637                                       SmallVectorImpl<ValueEntry> &Ops) {
638   assert(Ops.size() > 1 && "Single values should be used directly!");
639 
640   // Since our optimizations should never increase the number of operations, the
641   // new expression can usually be written reusing the existing binary operators
642   // from the original expression tree, without creating any new instructions,
643   // though the rewritten expression may have a completely different topology.
644   // We take care to not change anything if the new expression will be the same
645   // as the original.  If more than trivial changes (like commuting operands)
646   // were made then we are obliged to clear out any optional subclass data like
647   // nsw flags.
648 
649   /// NodesToRewrite - Nodes from the original expression available for writing
650   /// the new expression into.
651   SmallVector<BinaryOperator*, 8> NodesToRewrite;
652   unsigned Opcode = I->getOpcode();
653   BinaryOperator *Op = I;
654 
655   /// NotRewritable - The operands being written will be the leaves of the new
656   /// expression and must not be used as inner nodes (via NodesToRewrite) by
657   /// mistake.  Inner nodes are always reassociable, and usually leaves are not
658   /// (if they were they would have been incorporated into the expression and so
659   /// would not be leaves), so most of the time there is no danger of this.  But
660   /// in rare cases a leaf may become reassociable if an optimization kills uses
661   /// of it, or it may momentarily become reassociable during rewriting (below)
662   /// due it being removed as an operand of one of its uses.  Ensure that misuse
663   /// of leaf nodes as inner nodes cannot occur by remembering all of the future
664   /// leaves and refusing to reuse any of them as inner nodes.
665   SmallPtrSet<Value*, 8> NotRewritable;
666   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
667     NotRewritable.insert(Ops[i].Op);
668 
669   // ExpressionChanged - Non-null if the rewritten expression differs from the
670   // original in some non-trivial way, requiring the clearing of optional flags.
671   // Flags are cleared from the operator in ExpressionChanged up to I inclusive.
672   BinaryOperator *ExpressionChanged = nullptr;
673   for (unsigned i = 0; ; ++i) {
674     // The last operation (which comes earliest in the IR) is special as both
675     // operands will come from Ops, rather than just one with the other being
676     // a subexpression.
677     if (i+2 == Ops.size()) {
678       Value *NewLHS = Ops[i].Op;
679       Value *NewRHS = Ops[i+1].Op;
680       Value *OldLHS = Op->getOperand(0);
681       Value *OldRHS = Op->getOperand(1);
682 
683       if (NewLHS == OldLHS && NewRHS == OldRHS)
684         // Nothing changed, leave it alone.
685         break;
686 
687       if (NewLHS == OldRHS && NewRHS == OldLHS) {
688         // The order of the operands was reversed.  Swap them.
689         LLVM_DEBUG(dbgs() << "RA: " << *Op << '\n');
690         Op->swapOperands();
691         LLVM_DEBUG(dbgs() << "TO: " << *Op << '\n');
692         MadeChange = true;
693         ++NumChanged;
694         break;
695       }
696 
697       // The new operation differs non-trivially from the original. Overwrite
698       // the old operands with the new ones.
699       LLVM_DEBUG(dbgs() << "RA: " << *Op << '\n');
700       if (NewLHS != OldLHS) {
701         BinaryOperator *BO = isReassociableOp(OldLHS, Opcode);
702         if (BO && !NotRewritable.count(BO))
703           NodesToRewrite.push_back(BO);
704         Op->setOperand(0, NewLHS);
705       }
706       if (NewRHS != OldRHS) {
707         BinaryOperator *BO = isReassociableOp(OldRHS, Opcode);
708         if (BO && !NotRewritable.count(BO))
709           NodesToRewrite.push_back(BO);
710         Op->setOperand(1, NewRHS);
711       }
712       LLVM_DEBUG(dbgs() << "TO: " << *Op << '\n');
713 
714       ExpressionChanged = Op;
715       MadeChange = true;
716       ++NumChanged;
717 
718       break;
719     }
720 
721     // Not the last operation.  The left-hand side will be a sub-expression
722     // while the right-hand side will be the current element of Ops.
723     Value *NewRHS = Ops[i].Op;
724     if (NewRHS != Op->getOperand(1)) {
725       LLVM_DEBUG(dbgs() << "RA: " << *Op << '\n');
726       if (NewRHS == Op->getOperand(0)) {
727         // The new right-hand side was already present as the left operand.  If
728         // we are lucky then swapping the operands will sort out both of them.
729         Op->swapOperands();
730       } else {
731         // Overwrite with the new right-hand side.
732         BinaryOperator *BO = isReassociableOp(Op->getOperand(1), Opcode);
733         if (BO && !NotRewritable.count(BO))
734           NodesToRewrite.push_back(BO);
735         Op->setOperand(1, NewRHS);
736         ExpressionChanged = Op;
737       }
738       LLVM_DEBUG(dbgs() << "TO: " << *Op << '\n');
739       MadeChange = true;
740       ++NumChanged;
741     }
742 
743     // Now deal with the left-hand side.  If this is already an operation node
744     // from the original expression then just rewrite the rest of the expression
745     // into it.
746     BinaryOperator *BO = isReassociableOp(Op->getOperand(0), Opcode);
747     if (BO && !NotRewritable.count(BO)) {
748       Op = BO;
749       continue;
750     }
751 
752     // Otherwise, grab a spare node from the original expression and use that as
753     // the left-hand side.  If there are no nodes left then the optimizers made
754     // an expression with more nodes than the original!  This usually means that
755     // they did something stupid but it might mean that the problem was just too
756     // hard (finding the mimimal number of multiplications needed to realize a
757     // multiplication expression is NP-complete).  Whatever the reason, smart or
758     // stupid, create a new node if there are none left.
759     BinaryOperator *NewOp;
760     if (NodesToRewrite.empty()) {
761       Constant *Undef = UndefValue::get(I->getType());
762       NewOp = BinaryOperator::Create(Instruction::BinaryOps(Opcode),
763                                      Undef, Undef, "", I);
764       if (NewOp->getType()->isFPOrFPVectorTy())
765         NewOp->setFastMathFlags(I->getFastMathFlags());
766     } else {
767       NewOp = NodesToRewrite.pop_back_val();
768     }
769 
770     LLVM_DEBUG(dbgs() << "RA: " << *Op << '\n');
771     Op->setOperand(0, NewOp);
772     LLVM_DEBUG(dbgs() << "TO: " << *Op << '\n');
773     ExpressionChanged = Op;
774     MadeChange = true;
775     ++NumChanged;
776     Op = NewOp;
777   }
778 
779   // If the expression changed non-trivially then clear out all subclass data
780   // starting from the operator specified in ExpressionChanged, and compactify
781   // the operators to just before the expression root to guarantee that the
782   // expression tree is dominated by all of Ops.
783   if (ExpressionChanged)
784     do {
785       // Preserve FastMathFlags.
786       if (isa<FPMathOperator>(I)) {
787         FastMathFlags Flags = I->getFastMathFlags();
788         ExpressionChanged->clearSubclassOptionalData();
789         ExpressionChanged->setFastMathFlags(Flags);
790       } else
791         ExpressionChanged->clearSubclassOptionalData();
792 
793       if (ExpressionChanged == I)
794         break;
795 
796       // Discard any debug info related to the expressions that has changed (we
797       // can leave debug infor related to the root, since the result of the
798       // expression tree should be the same even after reassociation).
799       replaceDbgUsesWithUndef(ExpressionChanged);
800 
801       ExpressionChanged->moveBefore(I);
802       ExpressionChanged = cast<BinaryOperator>(*ExpressionChanged->user_begin());
803     } while (true);
804 
805   // Throw away any left over nodes from the original expression.
806   for (unsigned i = 0, e = NodesToRewrite.size(); i != e; ++i)
807     RedoInsts.insert(NodesToRewrite[i]);
808 }
809 
810 /// Insert instructions before the instruction pointed to by BI,
811 /// that computes the negative version of the value specified.  The negative
812 /// version of the value is returned, and BI is left pointing at the instruction
813 /// that should be processed next by the reassociation pass.
814 /// Also add intermediate instructions to the redo list that are modified while
815 /// pushing the negates through adds.  These will be revisited to see if
816 /// additional opportunities have been exposed.
817 static Value *NegateValue(Value *V, Instruction *BI,
818                           ReassociatePass::OrderedSet &ToRedo) {
819   if (auto *C = dyn_cast<Constant>(V))
820     return C->getType()->isFPOrFPVectorTy() ? ConstantExpr::getFNeg(C) :
821                                               ConstantExpr::getNeg(C);
822 
823   // We are trying to expose opportunity for reassociation.  One of the things
824   // that we want to do to achieve this is to push a negation as deep into an
825   // expression chain as possible, to expose the add instructions.  In practice,
826   // this means that we turn this:
827   //   X = -(A+12+C+D)   into    X = -A + -12 + -C + -D = -12 + -A + -C + -D
828   // so that later, a: Y = 12+X could get reassociated with the -12 to eliminate
829   // the constants.  We assume that instcombine will clean up the mess later if
830   // we introduce tons of unnecessary negation instructions.
831   //
832   if (BinaryOperator *I =
833           isReassociableOp(V, Instruction::Add, Instruction::FAdd)) {
834     // Push the negates through the add.
835     I->setOperand(0, NegateValue(I->getOperand(0), BI, ToRedo));
836     I->setOperand(1, NegateValue(I->getOperand(1), BI, ToRedo));
837     if (I->getOpcode() == Instruction::Add) {
838       I->setHasNoUnsignedWrap(false);
839       I->setHasNoSignedWrap(false);
840     }
841 
842     // We must move the add instruction here, because the neg instructions do
843     // not dominate the old add instruction in general.  By moving it, we are
844     // assured that the neg instructions we just inserted dominate the
845     // instruction we are about to insert after them.
846     //
847     I->moveBefore(BI);
848     I->setName(I->getName()+".neg");
849 
850     // Add the intermediate negates to the redo list as processing them later
851     // could expose more reassociating opportunities.
852     ToRedo.insert(I);
853     return I;
854   }
855 
856   // Okay, we need to materialize a negated version of V with an instruction.
857   // Scan the use lists of V to see if we have one already.
858   for (User *U : V->users()) {
859     if (!match(U, m_Neg(m_Value())) && !match(U, m_FNeg(m_Value())))
860       continue;
861 
862     // We found one!  Now we have to make sure that the definition dominates
863     // this use.  We do this by moving it to the entry block (if it is a
864     // non-instruction value) or right after the definition.  These negates will
865     // be zapped by reassociate later, so we don't need much finesse here.
866     Instruction *TheNeg = cast<Instruction>(U);
867 
868     // Verify that the negate is in this function, V might be a constant expr.
869     if (TheNeg->getParent()->getParent() != BI->getParent()->getParent())
870       continue;
871 
872     bool FoundCatchSwitch = false;
873 
874     BasicBlock::iterator InsertPt;
875     if (Instruction *InstInput = dyn_cast<Instruction>(V)) {
876       if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) {
877         InsertPt = II->getNormalDest()->begin();
878       } else {
879         InsertPt = ++InstInput->getIterator();
880       }
881 
882       const BasicBlock *BB = InsertPt->getParent();
883 
884       // Make sure we don't move anything before PHIs or exception
885       // handling pads.
886       while (InsertPt != BB->end() && (isa<PHINode>(InsertPt) ||
887                                        InsertPt->isEHPad())) {
888         if (isa<CatchSwitchInst>(InsertPt))
889           // A catchswitch cannot have anything in the block except
890           // itself and PHIs.  We'll bail out below.
891           FoundCatchSwitch = true;
892         ++InsertPt;
893       }
894     } else {
895       InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin();
896     }
897 
898     // We found a catchswitch in the block where we want to move the
899     // neg.  We cannot move anything into that block.  Bail and just
900     // create the neg before BI, as if we hadn't found an existing
901     // neg.
902     if (FoundCatchSwitch)
903       break;
904 
905     TheNeg->moveBefore(&*InsertPt);
906     if (TheNeg->getOpcode() == Instruction::Sub) {
907       TheNeg->setHasNoUnsignedWrap(false);
908       TheNeg->setHasNoSignedWrap(false);
909     } else {
910       TheNeg->andIRFlags(BI);
911     }
912     ToRedo.insert(TheNeg);
913     return TheNeg;
914   }
915 
916   // Insert a 'neg' instruction that subtracts the value from zero to get the
917   // negation.
918   Instruction *NewNeg = CreateNeg(V, V->getName() + ".neg", BI, BI);
919   ToRedo.insert(NewNeg);
920   return NewNeg;
921 }
922 
923 // See if this `or` looks like an load widening reduction, i.e. that it
924 // consists of an `or`/`shl`/`zext`/`load` nodes only. Note that we don't
925 // ensure that the pattern is *really* a load widening reduction,
926 // we do not ensure that it can really be replaced with a widened load,
927 // only that it mostly looks like one.
928 static bool isLoadCombineCandidate(Instruction *Or) {
929   SmallVector<Instruction *, 8> Worklist;
930   SmallSet<Instruction *, 8> Visited;
931 
932   auto Enqueue = [&](Value *V) {
933     auto *I = dyn_cast<Instruction>(V);
934     // Each node of an `or` reduction must be an instruction,
935     if (!I)
936       return false; // Node is certainly not part of an `or` load reduction.
937     // Only process instructions we have never processed before.
938     if (Visited.insert(I).second)
939       Worklist.emplace_back(I);
940     return true; // Will need to look at parent nodes.
941   };
942 
943   if (!Enqueue(Or))
944     return false; // Not an `or` reduction pattern.
945 
946   while (!Worklist.empty()) {
947     auto *I = Worklist.pop_back_val();
948 
949     // Okay, which instruction is this node?
950     switch (I->getOpcode()) {
951     case Instruction::Or:
952       // Got an `or` node. That's fine, just recurse into it's operands.
953       for (Value *Op : I->operands())
954         if (!Enqueue(Op))
955           return false; // Not an `or` reduction pattern.
956       continue;
957 
958     case Instruction::Shl:
959     case Instruction::ZExt:
960       // `shl`/`zext` nodes are fine, just recurse into their base operand.
961       if (!Enqueue(I->getOperand(0)))
962         return false; // Not an `or` reduction pattern.
963       continue;
964 
965     case Instruction::Load:
966       // Perfect, `load` node means we've reached an edge of the graph.
967       continue;
968 
969     default:        // Unknown node.
970       return false; // Not an `or` reduction pattern.
971     }
972   }
973 
974   return true;
975 }
976 
977 /// Return true if it may be profitable to convert this (X|Y) into (X+Y).
978 static bool shouldConvertOrWithNoCommonBitsToAdd(Instruction *Or) {
979   // Don't bother to convert this up unless either the LHS is an associable add
980   // or subtract or mul or if this is only used by one of the above.
981   // This is only a compile-time improvement, it is not needed for correctness!
982   auto isInteresting = [](Value *V) {
983     for (auto Op : {Instruction::Add, Instruction::Sub, Instruction::Mul,
984                     Instruction::Shl})
985       if (isReassociableOp(V, Op))
986         return true;
987     return false;
988   };
989 
990   if (any_of(Or->operands(), isInteresting))
991     return true;
992 
993   Value *VB = Or->user_back();
994   if (Or->hasOneUse() && isInteresting(VB))
995     return true;
996 
997   return false;
998 }
999 
1000 /// If we have (X|Y), and iff X and Y have no common bits set,
1001 /// transform this into (X+Y) to allow arithmetics reassociation.
1002 static BinaryOperator *convertOrWithNoCommonBitsToAdd(Instruction *Or) {
1003   // Convert an or into an add.
1004   BinaryOperator *New =
1005       CreateAdd(Or->getOperand(0), Or->getOperand(1), "", Or, Or);
1006   New->setHasNoSignedWrap();
1007   New->setHasNoUnsignedWrap();
1008   New->takeName(Or);
1009 
1010   // Everyone now refers to the add instruction.
1011   Or->replaceAllUsesWith(New);
1012   New->setDebugLoc(Or->getDebugLoc());
1013 
1014   LLVM_DEBUG(dbgs() << "Converted or into an add: " << *New << '\n');
1015   return New;
1016 }
1017 
1018 /// Return true if we should break up this subtract of X-Y into (X + -Y).
1019 static bool ShouldBreakUpSubtract(Instruction *Sub) {
1020   // If this is a negation, we can't split it up!
1021   if (match(Sub, m_Neg(m_Value())) || match(Sub, m_FNeg(m_Value())))
1022     return false;
1023 
1024   // Don't breakup X - undef.
1025   if (isa<UndefValue>(Sub->getOperand(1)))
1026     return false;
1027 
1028   // Don't bother to break this up unless either the LHS is an associable add or
1029   // subtract or if this is only used by one.
1030   Value *V0 = Sub->getOperand(0);
1031   if (isReassociableOp(V0, Instruction::Add, Instruction::FAdd) ||
1032       isReassociableOp(V0, Instruction::Sub, Instruction::FSub))
1033     return true;
1034   Value *V1 = Sub->getOperand(1);
1035   if (isReassociableOp(V1, Instruction::Add, Instruction::FAdd) ||
1036       isReassociableOp(V1, Instruction::Sub, Instruction::FSub))
1037     return true;
1038   Value *VB = Sub->user_back();
1039   if (Sub->hasOneUse() &&
1040       (isReassociableOp(VB, Instruction::Add, Instruction::FAdd) ||
1041        isReassociableOp(VB, Instruction::Sub, Instruction::FSub)))
1042     return true;
1043 
1044   return false;
1045 }
1046 
1047 /// If we have (X-Y), and if either X is an add, or if this is only used by an
1048 /// add, transform this into (X+(0-Y)) to promote better reassociation.
1049 static BinaryOperator *BreakUpSubtract(Instruction *Sub,
1050                                        ReassociatePass::OrderedSet &ToRedo) {
1051   // Convert a subtract into an add and a neg instruction. This allows sub
1052   // instructions to be commuted with other add instructions.
1053   //
1054   // Calculate the negative value of Operand 1 of the sub instruction,
1055   // and set it as the RHS of the add instruction we just made.
1056   Value *NegVal = NegateValue(Sub->getOperand(1), Sub, ToRedo);
1057   BinaryOperator *New = CreateAdd(Sub->getOperand(0), NegVal, "", Sub, Sub);
1058   Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op.
1059   Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op.
1060   New->takeName(Sub);
1061 
1062   // Everyone now refers to the add instruction.
1063   Sub->replaceAllUsesWith(New);
1064   New->setDebugLoc(Sub->getDebugLoc());
1065 
1066   LLVM_DEBUG(dbgs() << "Negated: " << *New << '\n');
1067   return New;
1068 }
1069 
1070 /// If this is a shift of a reassociable multiply or is used by one, change
1071 /// this into a multiply by a constant to assist with further reassociation.
1072 static BinaryOperator *ConvertShiftToMul(Instruction *Shl) {
1073   Constant *MulCst = ConstantInt::get(Shl->getType(), 1);
1074   auto *SA = cast<ConstantInt>(Shl->getOperand(1));
1075   MulCst = ConstantExpr::getShl(MulCst, SA);
1076 
1077   BinaryOperator *Mul =
1078     BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl);
1079   Shl->setOperand(0, UndefValue::get(Shl->getType())); // Drop use of op.
1080   Mul->takeName(Shl);
1081 
1082   // Everyone now refers to the mul instruction.
1083   Shl->replaceAllUsesWith(Mul);
1084   Mul->setDebugLoc(Shl->getDebugLoc());
1085 
1086   // We can safely preserve the nuw flag in all cases.  It's also safe to turn a
1087   // nuw nsw shl into a nuw nsw mul.  However, nsw in isolation requires special
1088   // handling.  It can be preserved as long as we're not left shifting by
1089   // bitwidth - 1.
1090   bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
1091   bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
1092   unsigned BitWidth = Shl->getType()->getIntegerBitWidth();
1093   if (NSW && (NUW || SA->getValue().ult(BitWidth - 1)))
1094     Mul->setHasNoSignedWrap(true);
1095   Mul->setHasNoUnsignedWrap(NUW);
1096   return Mul;
1097 }
1098 
1099 /// Scan backwards and forwards among values with the same rank as element i
1100 /// to see if X exists.  If X does not exist, return i.  This is useful when
1101 /// scanning for 'x' when we see '-x' because they both get the same rank.
1102 static unsigned FindInOperandList(const SmallVectorImpl<ValueEntry> &Ops,
1103                                   unsigned i, Value *X) {
1104   unsigned XRank = Ops[i].Rank;
1105   unsigned e = Ops.size();
1106   for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {
1107     if (Ops[j].Op == X)
1108       return j;
1109     if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
1110       if (Instruction *I2 = dyn_cast<Instruction>(X))
1111         if (I1->isIdenticalTo(I2))
1112           return j;
1113   }
1114   // Scan backwards.
1115   for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {
1116     if (Ops[j].Op == X)
1117       return j;
1118     if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
1119       if (Instruction *I2 = dyn_cast<Instruction>(X))
1120         if (I1->isIdenticalTo(I2))
1121           return j;
1122   }
1123   return i;
1124 }
1125 
1126 /// Emit a tree of add instructions, summing Ops together
1127 /// and returning the result.  Insert the tree before I.
1128 static Value *EmitAddTreeOfValues(Instruction *I,
1129                                   SmallVectorImpl<WeakTrackingVH> &Ops) {
1130   if (Ops.size() == 1) return Ops.back();
1131 
1132   Value *V1 = Ops.pop_back_val();
1133   Value *V2 = EmitAddTreeOfValues(I, Ops);
1134   return CreateAdd(V2, V1, "reass.add", I, I);
1135 }
1136 
1137 /// If V is an expression tree that is a multiplication sequence,
1138 /// and if this sequence contains a multiply by Factor,
1139 /// remove Factor from the tree and return the new tree.
1140 Value *ReassociatePass::RemoveFactorFromExpression(Value *V, Value *Factor) {
1141   BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul);
1142   if (!BO)
1143     return nullptr;
1144 
1145   SmallVector<RepeatedValue, 8> Tree;
1146   MadeChange |= LinearizeExprTree(BO, Tree);
1147   SmallVector<ValueEntry, 8> Factors;
1148   Factors.reserve(Tree.size());
1149   for (unsigned i = 0, e = Tree.size(); i != e; ++i) {
1150     RepeatedValue E = Tree[i];
1151     Factors.append(E.second.getZExtValue(),
1152                    ValueEntry(getRank(E.first), E.first));
1153   }
1154 
1155   bool FoundFactor = false;
1156   bool NeedsNegate = false;
1157   for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
1158     if (Factors[i].Op == Factor) {
1159       FoundFactor = true;
1160       Factors.erase(Factors.begin()+i);
1161       break;
1162     }
1163 
1164     // If this is a negative version of this factor, remove it.
1165     if (ConstantInt *FC1 = dyn_cast<ConstantInt>(Factor)) {
1166       if (ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op))
1167         if (FC1->getValue() == -FC2->getValue()) {
1168           FoundFactor = NeedsNegate = true;
1169           Factors.erase(Factors.begin()+i);
1170           break;
1171         }
1172     } else if (ConstantFP *FC1 = dyn_cast<ConstantFP>(Factor)) {
1173       if (ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[i].Op)) {
1174         const APFloat &F1 = FC1->getValueAPF();
1175         APFloat F2(FC2->getValueAPF());
1176         F2.changeSign();
1177         if (F1 == F2) {
1178           FoundFactor = NeedsNegate = true;
1179           Factors.erase(Factors.begin() + i);
1180           break;
1181         }
1182       }
1183     }
1184   }
1185 
1186   if (!FoundFactor) {
1187     // Make sure to restore the operands to the expression tree.
1188     RewriteExprTree(BO, Factors);
1189     return nullptr;
1190   }
1191 
1192   BasicBlock::iterator InsertPt = ++BO->getIterator();
1193 
1194   // If this was just a single multiply, remove the multiply and return the only
1195   // remaining operand.
1196   if (Factors.size() == 1) {
1197     RedoInsts.insert(BO);
1198     V = Factors[0].Op;
1199   } else {
1200     RewriteExprTree(BO, Factors);
1201     V = BO;
1202   }
1203 
1204   if (NeedsNegate)
1205     V = CreateNeg(V, "neg", &*InsertPt, BO);
1206 
1207   return V;
1208 }
1209 
1210 /// If V is a single-use multiply, recursively add its operands as factors,
1211 /// otherwise add V to the list of factors.
1212 ///
1213 /// Ops is the top-level list of add operands we're trying to factor.
1214 static void FindSingleUseMultiplyFactors(Value *V,
1215                                          SmallVectorImpl<Value*> &Factors) {
1216   BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul);
1217   if (!BO) {
1218     Factors.push_back(V);
1219     return;
1220   }
1221 
1222   // Otherwise, add the LHS and RHS to the list of factors.
1223   FindSingleUseMultiplyFactors(BO->getOperand(1), Factors);
1224   FindSingleUseMultiplyFactors(BO->getOperand(0), Factors);
1225 }
1226 
1227 /// Optimize a series of operands to an 'and', 'or', or 'xor' instruction.
1228 /// This optimizes based on identities.  If it can be reduced to a single Value,
1229 /// it is returned, otherwise the Ops list is mutated as necessary.
1230 static Value *OptimizeAndOrXor(unsigned Opcode,
1231                                SmallVectorImpl<ValueEntry> &Ops) {
1232   // Scan the operand lists looking for X and ~X pairs, along with X,X pairs.
1233   // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1.
1234   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1235     // First, check for X and ~X in the operand list.
1236     assert(i < Ops.size());
1237     Value *X;
1238     if (match(Ops[i].Op, m_Not(m_Value(X)))) {    // Cannot occur for ^.
1239       unsigned FoundX = FindInOperandList(Ops, i, X);
1240       if (FoundX != i) {
1241         if (Opcode == Instruction::And)   // ...&X&~X = 0
1242           return Constant::getNullValue(X->getType());
1243 
1244         if (Opcode == Instruction::Or)    // ...|X|~X = -1
1245           return Constant::getAllOnesValue(X->getType());
1246       }
1247     }
1248 
1249     // Next, check for duplicate pairs of values, which we assume are next to
1250     // each other, due to our sorting criteria.
1251     assert(i < Ops.size());
1252     if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) {
1253       if (Opcode == Instruction::And || Opcode == Instruction::Or) {
1254         // Drop duplicate values for And and Or.
1255         Ops.erase(Ops.begin()+i);
1256         --i; --e;
1257         ++NumAnnihil;
1258         continue;
1259       }
1260 
1261       // Drop pairs of values for Xor.
1262       assert(Opcode == Instruction::Xor);
1263       if (e == 2)
1264         return Constant::getNullValue(Ops[0].Op->getType());
1265 
1266       // Y ^ X^X -> Y
1267       Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
1268       i -= 1; e -= 2;
1269       ++NumAnnihil;
1270     }
1271   }
1272   return nullptr;
1273 }
1274 
1275 /// Helper function of CombineXorOpnd(). It creates a bitwise-and
1276 /// instruction with the given two operands, and return the resulting
1277 /// instruction. There are two special cases: 1) if the constant operand is 0,
1278 /// it will return NULL. 2) if the constant is ~0, the symbolic operand will
1279 /// be returned.
1280 static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd,
1281                              const APInt &ConstOpnd) {
1282   if (ConstOpnd.isZero())
1283     return nullptr;
1284 
1285   if (ConstOpnd.isAllOnes())
1286     return Opnd;
1287 
1288   Instruction *I = BinaryOperator::CreateAnd(
1289       Opnd, ConstantInt::get(Opnd->getType(), ConstOpnd), "and.ra",
1290       InsertBefore);
1291   I->setDebugLoc(InsertBefore->getDebugLoc());
1292   return I;
1293 }
1294 
1295 // Helper function of OptimizeXor(). It tries to simplify "Opnd1 ^ ConstOpnd"
1296 // into "R ^ C", where C would be 0, and R is a symbolic value.
1297 //
1298 // If it was successful, true is returned, and the "R" and "C" is returned
1299 // via "Res" and "ConstOpnd", respectively; otherwise, false is returned,
1300 // and both "Res" and "ConstOpnd" remain unchanged.
1301 bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
1302                                      APInt &ConstOpnd, Value *&Res) {
1303   // Xor-Rule 1: (x | c1) ^ c2 = (x | c1) ^ (c1 ^ c1) ^ c2
1304   //                       = ((x | c1) ^ c1) ^ (c1 ^ c2)
1305   //                       = (x & ~c1) ^ (c1 ^ c2)
1306   // It is useful only when c1 == c2.
1307   if (!Opnd1->isOrExpr() || Opnd1->getConstPart().isZero())
1308     return false;
1309 
1310   if (!Opnd1->getValue()->hasOneUse())
1311     return false;
1312 
1313   const APInt &C1 = Opnd1->getConstPart();
1314   if (C1 != ConstOpnd)
1315     return false;
1316 
1317   Value *X = Opnd1->getSymbolicPart();
1318   Res = createAndInstr(I, X, ~C1);
1319   // ConstOpnd was C2, now C1 ^ C2.
1320   ConstOpnd ^= C1;
1321 
1322   if (Instruction *T = dyn_cast<Instruction>(Opnd1->getValue()))
1323     RedoInsts.insert(T);
1324   return true;
1325 }
1326 
1327 // Helper function of OptimizeXor(). It tries to simplify
1328 // "Opnd1 ^ Opnd2 ^ ConstOpnd" into "R ^ C", where C would be 0, and R is a
1329 // symbolic value.
1330 //
1331 // If it was successful, true is returned, and the "R" and "C" is returned
1332 // via "Res" and "ConstOpnd", respectively (If the entire expression is
1333 // evaluated to a constant, the Res is set to NULL); otherwise, false is
1334 // returned, and both "Res" and "ConstOpnd" remain unchanged.
1335 bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
1336                                      XorOpnd *Opnd2, APInt &ConstOpnd,
1337                                      Value *&Res) {
1338   Value *X = Opnd1->getSymbolicPart();
1339   if (X != Opnd2->getSymbolicPart())
1340     return false;
1341 
1342   // This many instruction become dead.(At least "Opnd1 ^ Opnd2" will die.)
1343   int DeadInstNum = 1;
1344   if (Opnd1->getValue()->hasOneUse())
1345     DeadInstNum++;
1346   if (Opnd2->getValue()->hasOneUse())
1347     DeadInstNum++;
1348 
1349   // Xor-Rule 2:
1350   //  (x | c1) ^ (x & c2)
1351   //   = (x|c1) ^ (x&c2) ^ (c1 ^ c1) = ((x|c1) ^ c1) ^ (x & c2) ^ c1
1352   //   = (x & ~c1) ^ (x & c2) ^ c1               // Xor-Rule 1
1353   //   = (x & c3) ^ c1, where c3 = ~c1 ^ c2      // Xor-rule 3
1354   //
1355   if (Opnd1->isOrExpr() != Opnd2->isOrExpr()) {
1356     if (Opnd2->isOrExpr())
1357       std::swap(Opnd1, Opnd2);
1358 
1359     const APInt &C1 = Opnd1->getConstPart();
1360     const APInt &C2 = Opnd2->getConstPart();
1361     APInt C3((~C1) ^ C2);
1362 
1363     // Do not increase code size!
1364     if (!C3.isZero() && !C3.isAllOnes()) {
1365       int NewInstNum = ConstOpnd.getBoolValue() ? 1 : 2;
1366       if (NewInstNum > DeadInstNum)
1367         return false;
1368     }
1369 
1370     Res = createAndInstr(I, X, C3);
1371     ConstOpnd ^= C1;
1372   } else if (Opnd1->isOrExpr()) {
1373     // Xor-Rule 3: (x | c1) ^ (x | c2) = (x & c3) ^ c3 where c3 = c1 ^ c2
1374     //
1375     const APInt &C1 = Opnd1->getConstPart();
1376     const APInt &C2 = Opnd2->getConstPart();
1377     APInt C3 = C1 ^ C2;
1378 
1379     // Do not increase code size
1380     if (!C3.isZero() && !C3.isAllOnes()) {
1381       int NewInstNum = ConstOpnd.getBoolValue() ? 1 : 2;
1382       if (NewInstNum > DeadInstNum)
1383         return false;
1384     }
1385 
1386     Res = createAndInstr(I, X, C3);
1387     ConstOpnd ^= C3;
1388   } else {
1389     // Xor-Rule 4: (x & c1) ^ (x & c2) = (x & (c1^c2))
1390     //
1391     const APInt &C1 = Opnd1->getConstPart();
1392     const APInt &C2 = Opnd2->getConstPart();
1393     APInt C3 = C1 ^ C2;
1394     Res = createAndInstr(I, X, C3);
1395   }
1396 
1397   // Put the original operands in the Redo list; hope they will be deleted
1398   // as dead code.
1399   if (Instruction *T = dyn_cast<Instruction>(Opnd1->getValue()))
1400     RedoInsts.insert(T);
1401   if (Instruction *T = dyn_cast<Instruction>(Opnd2->getValue()))
1402     RedoInsts.insert(T);
1403 
1404   return true;
1405 }
1406 
1407 /// Optimize a series of operands to an 'xor' instruction. If it can be reduced
1408 /// to a single Value, it is returned, otherwise the Ops list is mutated as
1409 /// necessary.
1410 Value *ReassociatePass::OptimizeXor(Instruction *I,
1411                                     SmallVectorImpl<ValueEntry> &Ops) {
1412   if (Value *V = OptimizeAndOrXor(Instruction::Xor, Ops))
1413     return V;
1414 
1415   if (Ops.size() == 1)
1416     return nullptr;
1417 
1418   SmallVector<XorOpnd, 8> Opnds;
1419   SmallVector<XorOpnd*, 8> OpndPtrs;
1420   Type *Ty = Ops[0].Op->getType();
1421   APInt ConstOpnd(Ty->getScalarSizeInBits(), 0);
1422 
1423   // Step 1: Convert ValueEntry to XorOpnd
1424   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1425     Value *V = Ops[i].Op;
1426     const APInt *C;
1427     // TODO: Support non-splat vectors.
1428     if (match(V, m_APInt(C))) {
1429       ConstOpnd ^= *C;
1430     } else {
1431       XorOpnd O(V);
1432       O.setSymbolicRank(getRank(O.getSymbolicPart()));
1433       Opnds.push_back(O);
1434     }
1435   }
1436 
1437   // NOTE: From this point on, do *NOT* add/delete element to/from "Opnds".
1438   //  It would otherwise invalidate the "Opnds"'s iterator, and hence invalidate
1439   //  the "OpndPtrs" as well. For the similar reason, do not fuse this loop
1440   //  with the previous loop --- the iterator of the "Opnds" may be invalidated
1441   //  when new elements are added to the vector.
1442   for (unsigned i = 0, e = Opnds.size(); i != e; ++i)
1443     OpndPtrs.push_back(&Opnds[i]);
1444 
1445   // Step 2: Sort the Xor-Operands in a way such that the operands containing
1446   //  the same symbolic value cluster together. For instance, the input operand
1447   //  sequence ("x | 123", "y & 456", "x & 789") will be sorted into:
1448   //  ("x | 123", "x & 789", "y & 456").
1449   //
1450   //  The purpose is twofold:
1451   //  1) Cluster together the operands sharing the same symbolic-value.
1452   //  2) Operand having smaller symbolic-value-rank is permuted earlier, which
1453   //     could potentially shorten crital path, and expose more loop-invariants.
1454   //     Note that values' rank are basically defined in RPO order (FIXME).
1455   //     So, if Rank(X) < Rank(Y) < Rank(Z), it means X is defined earlier
1456   //     than Y which is defined earlier than Z. Permute "x | 1", "Y & 2",
1457   //     "z" in the order of X-Y-Z is better than any other orders.
1458   llvm::stable_sort(OpndPtrs, [](XorOpnd *LHS, XorOpnd *RHS) {
1459     return LHS->getSymbolicRank() < RHS->getSymbolicRank();
1460   });
1461 
1462   // Step 3: Combine adjacent operands
1463   XorOpnd *PrevOpnd = nullptr;
1464   bool Changed = false;
1465   for (unsigned i = 0, e = Opnds.size(); i < e; i++) {
1466     XorOpnd *CurrOpnd = OpndPtrs[i];
1467     // The combined value
1468     Value *CV;
1469 
1470     // Step 3.1: Try simplifying "CurrOpnd ^ ConstOpnd"
1471     if (!ConstOpnd.isZero() && CombineXorOpnd(I, CurrOpnd, ConstOpnd, CV)) {
1472       Changed = true;
1473       if (CV)
1474         *CurrOpnd = XorOpnd(CV);
1475       else {
1476         CurrOpnd->Invalidate();
1477         continue;
1478       }
1479     }
1480 
1481     if (!PrevOpnd || CurrOpnd->getSymbolicPart() != PrevOpnd->getSymbolicPart()) {
1482       PrevOpnd = CurrOpnd;
1483       continue;
1484     }
1485 
1486     // step 3.2: When previous and current operands share the same symbolic
1487     //  value, try to simplify "PrevOpnd ^ CurrOpnd ^ ConstOpnd"
1488     if (CombineXorOpnd(I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
1489       // Remove previous operand
1490       PrevOpnd->Invalidate();
1491       if (CV) {
1492         *CurrOpnd = XorOpnd(CV);
1493         PrevOpnd = CurrOpnd;
1494       } else {
1495         CurrOpnd->Invalidate();
1496         PrevOpnd = nullptr;
1497       }
1498       Changed = true;
1499     }
1500   }
1501 
1502   // Step 4: Reassemble the Ops
1503   if (Changed) {
1504     Ops.clear();
1505     for (unsigned int i = 0, e = Opnds.size(); i < e; i++) {
1506       XorOpnd &O = Opnds[i];
1507       if (O.isInvalid())
1508         continue;
1509       ValueEntry VE(getRank(O.getValue()), O.getValue());
1510       Ops.push_back(VE);
1511     }
1512     if (!ConstOpnd.isZero()) {
1513       Value *C = ConstantInt::get(Ty, ConstOpnd);
1514       ValueEntry VE(getRank(C), C);
1515       Ops.push_back(VE);
1516     }
1517     unsigned Sz = Ops.size();
1518     if (Sz == 1)
1519       return Ops.back().Op;
1520     if (Sz == 0) {
1521       assert(ConstOpnd.isZero());
1522       return ConstantInt::get(Ty, ConstOpnd);
1523     }
1524   }
1525 
1526   return nullptr;
1527 }
1528 
1529 /// Optimize a series of operands to an 'add' instruction.  This
1530 /// optimizes based on identities.  If it can be reduced to a single Value, it
1531 /// is returned, otherwise the Ops list is mutated as necessary.
1532 Value *ReassociatePass::OptimizeAdd(Instruction *I,
1533                                     SmallVectorImpl<ValueEntry> &Ops) {
1534   // Scan the operand lists looking for X and -X pairs.  If we find any, we
1535   // can simplify expressions like X+-X == 0 and X+~X ==-1.  While we're at it,
1536   // scan for any
1537   // duplicates.  We want to canonicalize Y+Y+Y+Z -> 3*Y+Z.
1538 
1539   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1540     Value *TheOp = Ops[i].Op;
1541     // Check to see if we've seen this operand before.  If so, we factor all
1542     // instances of the operand together.  Due to our sorting criteria, we know
1543     // that these need to be next to each other in the vector.
1544     if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) {
1545       // Rescan the list, remove all instances of this operand from the expr.
1546       unsigned NumFound = 0;
1547       do {
1548         Ops.erase(Ops.begin()+i);
1549         ++NumFound;
1550       } while (i != Ops.size() && Ops[i].Op == TheOp);
1551 
1552       LLVM_DEBUG(dbgs() << "\nFACTORING [" << NumFound << "]: " << *TheOp
1553                         << '\n');
1554       ++NumFactor;
1555 
1556       // Insert a new multiply.
1557       Type *Ty = TheOp->getType();
1558       Constant *C = Ty->isIntOrIntVectorTy() ?
1559         ConstantInt::get(Ty, NumFound) : ConstantFP::get(Ty, NumFound);
1560       Instruction *Mul = CreateMul(TheOp, C, "factor", I, I);
1561 
1562       // Now that we have inserted a multiply, optimize it. This allows us to
1563       // handle cases that require multiple factoring steps, such as this:
1564       // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6
1565       RedoInsts.insert(Mul);
1566 
1567       // If every add operand was a duplicate, return the multiply.
1568       if (Ops.empty())
1569         return Mul;
1570 
1571       // Otherwise, we had some input that didn't have the dupe, such as
1572       // "A + A + B" -> "A*2 + B".  Add the new multiply to the list of
1573       // things being added by this operation.
1574       Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul));
1575 
1576       --i;
1577       e = Ops.size();
1578       continue;
1579     }
1580 
1581     // Check for X and -X or X and ~X in the operand list.
1582     Value *X;
1583     if (!match(TheOp, m_Neg(m_Value(X))) && !match(TheOp, m_Not(m_Value(X))) &&
1584         !match(TheOp, m_FNeg(m_Value(X))))
1585       continue;
1586 
1587     unsigned FoundX = FindInOperandList(Ops, i, X);
1588     if (FoundX == i)
1589       continue;
1590 
1591     // Remove X and -X from the operand list.
1592     if (Ops.size() == 2 &&
1593         (match(TheOp, m_Neg(m_Value())) || match(TheOp, m_FNeg(m_Value()))))
1594       return Constant::getNullValue(X->getType());
1595 
1596     // Remove X and ~X from the operand list.
1597     if (Ops.size() == 2 && match(TheOp, m_Not(m_Value())))
1598       return Constant::getAllOnesValue(X->getType());
1599 
1600     Ops.erase(Ops.begin()+i);
1601     if (i < FoundX)
1602       --FoundX;
1603     else
1604       --i;   // Need to back up an extra one.
1605     Ops.erase(Ops.begin()+FoundX);
1606     ++NumAnnihil;
1607     --i;     // Revisit element.
1608     e -= 2;  // Removed two elements.
1609 
1610     // if X and ~X we append -1 to the operand list.
1611     if (match(TheOp, m_Not(m_Value()))) {
1612       Value *V = Constant::getAllOnesValue(X->getType());
1613       Ops.insert(Ops.end(), ValueEntry(getRank(V), V));
1614       e += 1;
1615     }
1616   }
1617 
1618   // Scan the operand list, checking to see if there are any common factors
1619   // between operands.  Consider something like A*A+A*B*C+D.  We would like to
1620   // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies.
1621   // To efficiently find this, we count the number of times a factor occurs
1622   // for any ADD operands that are MULs.
1623   DenseMap<Value*, unsigned> FactorOccurrences;
1624 
1625   // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4)
1626   // where they are actually the same multiply.
1627   unsigned MaxOcc = 0;
1628   Value *MaxOccVal = nullptr;
1629   for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1630     BinaryOperator *BOp =
1631         isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul);
1632     if (!BOp)
1633       continue;
1634 
1635     // Compute all of the factors of this added value.
1636     SmallVector<Value*, 8> Factors;
1637     FindSingleUseMultiplyFactors(BOp, Factors);
1638     assert(Factors.size() > 1 && "Bad linearize!");
1639 
1640     // Add one to FactorOccurrences for each unique factor in this op.
1641     SmallPtrSet<Value*, 8> Duplicates;
1642     for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
1643       Value *Factor = Factors[i];
1644       if (!Duplicates.insert(Factor).second)
1645         continue;
1646 
1647       unsigned Occ = ++FactorOccurrences[Factor];
1648       if (Occ > MaxOcc) {
1649         MaxOcc = Occ;
1650         MaxOccVal = Factor;
1651       }
1652 
1653       // If Factor is a negative constant, add the negated value as a factor
1654       // because we can percolate the negate out.  Watch for minint, which
1655       // cannot be positivified.
1656       if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) {
1657         if (CI->isNegative() && !CI->isMinValue(true)) {
1658           Factor = ConstantInt::get(CI->getContext(), -CI->getValue());
1659           if (!Duplicates.insert(Factor).second)
1660             continue;
1661           unsigned Occ = ++FactorOccurrences[Factor];
1662           if (Occ > MaxOcc) {
1663             MaxOcc = Occ;
1664             MaxOccVal = Factor;
1665           }
1666         }
1667       } else if (ConstantFP *CF = dyn_cast<ConstantFP>(Factor)) {
1668         if (CF->isNegative()) {
1669           APFloat F(CF->getValueAPF());
1670           F.changeSign();
1671           Factor = ConstantFP::get(CF->getContext(), F);
1672           if (!Duplicates.insert(Factor).second)
1673             continue;
1674           unsigned Occ = ++FactorOccurrences[Factor];
1675           if (Occ > MaxOcc) {
1676             MaxOcc = Occ;
1677             MaxOccVal = Factor;
1678           }
1679         }
1680       }
1681     }
1682   }
1683 
1684   // If any factor occurred more than one time, we can pull it out.
1685   if (MaxOcc > 1) {
1686     LLVM_DEBUG(dbgs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal
1687                       << '\n');
1688     ++NumFactor;
1689 
1690     // Create a new instruction that uses the MaxOccVal twice.  If we don't do
1691     // this, we could otherwise run into situations where removing a factor
1692     // from an expression will drop a use of maxocc, and this can cause
1693     // RemoveFactorFromExpression on successive values to behave differently.
1694     Instruction *DummyInst =
1695         I->getType()->isIntOrIntVectorTy()
1696             ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal)
1697             : BinaryOperator::CreateFAdd(MaxOccVal, MaxOccVal);
1698 
1699     SmallVector<WeakTrackingVH, 4> NewMulOps;
1700     for (unsigned i = 0; i != Ops.size(); ++i) {
1701       // Only try to remove factors from expressions we're allowed to.
1702       BinaryOperator *BOp =
1703           isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul);
1704       if (!BOp)
1705         continue;
1706 
1707       if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) {
1708         // The factorized operand may occur several times.  Convert them all in
1709         // one fell swoop.
1710         for (unsigned j = Ops.size(); j != i;) {
1711           --j;
1712           if (Ops[j].Op == Ops[i].Op) {
1713             NewMulOps.push_back(V);
1714             Ops.erase(Ops.begin()+j);
1715           }
1716         }
1717         --i;
1718       }
1719     }
1720 
1721     // No need for extra uses anymore.
1722     DummyInst->deleteValue();
1723 
1724     unsigned NumAddedValues = NewMulOps.size();
1725     Value *V = EmitAddTreeOfValues(I, NewMulOps);
1726 
1727     // Now that we have inserted the add tree, optimize it. This allows us to
1728     // handle cases that require multiple factoring steps, such as this:
1729     // A*A*B + A*A*C   -->   A*(A*B+A*C)   -->   A*(A*(B+C))
1730     assert(NumAddedValues > 1 && "Each occurrence should contribute a value");
1731     (void)NumAddedValues;
1732     if (Instruction *VI = dyn_cast<Instruction>(V))
1733       RedoInsts.insert(VI);
1734 
1735     // Create the multiply.
1736     Instruction *V2 = CreateMul(V, MaxOccVal, "reass.mul", I, I);
1737 
1738     // Rerun associate on the multiply in case the inner expression turned into
1739     // a multiply.  We want to make sure that we keep things in canonical form.
1740     RedoInsts.insert(V2);
1741 
1742     // If every add operand included the factor (e.g. "A*B + A*C"), then the
1743     // entire result expression is just the multiply "A*(B+C)".
1744     if (Ops.empty())
1745       return V2;
1746 
1747     // Otherwise, we had some input that didn't have the factor, such as
1748     // "A*B + A*C + D" -> "A*(B+C) + D".  Add the new multiply to the list of
1749     // things being added by this operation.
1750     Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2));
1751   }
1752 
1753   return nullptr;
1754 }
1755 
1756 /// Build up a vector of value/power pairs factoring a product.
1757 ///
1758 /// Given a series of multiplication operands, build a vector of factors and
1759 /// the powers each is raised to when forming the final product. Sort them in
1760 /// the order of descending power.
1761 ///
1762 ///      (x*x)          -> [(x, 2)]
1763 ///     ((x*x)*x)       -> [(x, 3)]
1764 ///   ((((x*y)*x)*y)*x) -> [(x, 3), (y, 2)]
1765 ///
1766 /// \returns Whether any factors have a power greater than one.
1767 static bool collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops,
1768                                    SmallVectorImpl<Factor> &Factors) {
1769   // FIXME: Have Ops be (ValueEntry, Multiplicity) pairs, simplifying this.
1770   // Compute the sum of powers of simplifiable factors.
1771   unsigned FactorPowerSum = 0;
1772   for (unsigned Idx = 1, Size = Ops.size(); Idx < Size; ++Idx) {
1773     Value *Op = Ops[Idx-1].Op;
1774 
1775     // Count the number of occurrences of this value.
1776     unsigned Count = 1;
1777     for (; Idx < Size && Ops[Idx].Op == Op; ++Idx)
1778       ++Count;
1779     // Track for simplification all factors which occur 2 or more times.
1780     if (Count > 1)
1781       FactorPowerSum += Count;
1782   }
1783 
1784   // We can only simplify factors if the sum of the powers of our simplifiable
1785   // factors is 4 or higher. When that is the case, we will *always* have
1786   // a simplification. This is an important invariant to prevent cyclicly
1787   // trying to simplify already minimal formations.
1788   if (FactorPowerSum < 4)
1789     return false;
1790 
1791   // Now gather the simplifiable factors, removing them from Ops.
1792   FactorPowerSum = 0;
1793   for (unsigned Idx = 1; Idx < Ops.size(); ++Idx) {
1794     Value *Op = Ops[Idx-1].Op;
1795 
1796     // Count the number of occurrences of this value.
1797     unsigned Count = 1;
1798     for (; Idx < Ops.size() && Ops[Idx].Op == Op; ++Idx)
1799       ++Count;
1800     if (Count == 1)
1801       continue;
1802     // Move an even number of occurrences to Factors.
1803     Count &= ~1U;
1804     Idx -= Count;
1805     FactorPowerSum += Count;
1806     Factors.push_back(Factor(Op, Count));
1807     Ops.erase(Ops.begin()+Idx, Ops.begin()+Idx+Count);
1808   }
1809 
1810   // None of the adjustments above should have reduced the sum of factor powers
1811   // below our mininum of '4'.
1812   assert(FactorPowerSum >= 4);
1813 
1814   llvm::stable_sort(Factors, [](const Factor &LHS, const Factor &RHS) {
1815     return LHS.Power > RHS.Power;
1816   });
1817   return true;
1818 }
1819 
1820 /// Build a tree of multiplies, computing the product of Ops.
1821 static Value *buildMultiplyTree(IRBuilderBase &Builder,
1822                                 SmallVectorImpl<Value*> &Ops) {
1823   if (Ops.size() == 1)
1824     return Ops.back();
1825 
1826   Value *LHS = Ops.pop_back_val();
1827   do {
1828     if (LHS->getType()->isIntOrIntVectorTy())
1829       LHS = Builder.CreateMul(LHS, Ops.pop_back_val());
1830     else
1831       LHS = Builder.CreateFMul(LHS, Ops.pop_back_val());
1832   } while (!Ops.empty());
1833 
1834   return LHS;
1835 }
1836 
1837 /// Build a minimal multiplication DAG for (a^x)*(b^y)*(c^z)*...
1838 ///
1839 /// Given a vector of values raised to various powers, where no two values are
1840 /// equal and the powers are sorted in decreasing order, compute the minimal
1841 /// DAG of multiplies to compute the final product, and return that product
1842 /// value.
1843 Value *
1844 ReassociatePass::buildMinimalMultiplyDAG(IRBuilderBase &Builder,
1845                                          SmallVectorImpl<Factor> &Factors) {
1846   assert(Factors[0].Power);
1847   SmallVector<Value *, 4> OuterProduct;
1848   for (unsigned LastIdx = 0, Idx = 1, Size = Factors.size();
1849        Idx < Size && Factors[Idx].Power > 0; ++Idx) {
1850     if (Factors[Idx].Power != Factors[LastIdx].Power) {
1851       LastIdx = Idx;
1852       continue;
1853     }
1854 
1855     // We want to multiply across all the factors with the same power so that
1856     // we can raise them to that power as a single entity. Build a mini tree
1857     // for that.
1858     SmallVector<Value *, 4> InnerProduct;
1859     InnerProduct.push_back(Factors[LastIdx].Base);
1860     do {
1861       InnerProduct.push_back(Factors[Idx].Base);
1862       ++Idx;
1863     } while (Idx < Size && Factors[Idx].Power == Factors[LastIdx].Power);
1864 
1865     // Reset the base value of the first factor to the new expression tree.
1866     // We'll remove all the factors with the same power in a second pass.
1867     Value *M = Factors[LastIdx].Base = buildMultiplyTree(Builder, InnerProduct);
1868     if (Instruction *MI = dyn_cast<Instruction>(M))
1869       RedoInsts.insert(MI);
1870 
1871     LastIdx = Idx;
1872   }
1873   // Unique factors with equal powers -- we've folded them into the first one's
1874   // base.
1875   Factors.erase(std::unique(Factors.begin(), Factors.end(),
1876                             [](const Factor &LHS, const Factor &RHS) {
1877                               return LHS.Power == RHS.Power;
1878                             }),
1879                 Factors.end());
1880 
1881   // Iteratively collect the base of each factor with an add power into the
1882   // outer product, and halve each power in preparation for squaring the
1883   // expression.
1884   for (unsigned Idx = 0, Size = Factors.size(); Idx != Size; ++Idx) {
1885     if (Factors[Idx].Power & 1)
1886       OuterProduct.push_back(Factors[Idx].Base);
1887     Factors[Idx].Power >>= 1;
1888   }
1889   if (Factors[0].Power) {
1890     Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors);
1891     OuterProduct.push_back(SquareRoot);
1892     OuterProduct.push_back(SquareRoot);
1893   }
1894   if (OuterProduct.size() == 1)
1895     return OuterProduct.front();
1896 
1897   Value *V = buildMultiplyTree(Builder, OuterProduct);
1898   return V;
1899 }
1900 
1901 Value *ReassociatePass::OptimizeMul(BinaryOperator *I,
1902                                     SmallVectorImpl<ValueEntry> &Ops) {
1903   // We can only optimize the multiplies when there is a chain of more than
1904   // three, such that a balanced tree might require fewer total multiplies.
1905   if (Ops.size() < 4)
1906     return nullptr;
1907 
1908   // Try to turn linear trees of multiplies without other uses of the
1909   // intermediate stages into minimal multiply DAGs with perfect sub-expression
1910   // re-use.
1911   SmallVector<Factor, 4> Factors;
1912   if (!collectMultiplyFactors(Ops, Factors))
1913     return nullptr; // All distinct factors, so nothing left for us to do.
1914 
1915   IRBuilder<> Builder(I);
1916   // The reassociate transformation for FP operations is performed only
1917   // if unsafe algebra is permitted by FastMathFlags. Propagate those flags
1918   // to the newly generated operations.
1919   if (auto FPI = dyn_cast<FPMathOperator>(I))
1920     Builder.setFastMathFlags(FPI->getFastMathFlags());
1921 
1922   Value *V = buildMinimalMultiplyDAG(Builder, Factors);
1923   if (Ops.empty())
1924     return V;
1925 
1926   ValueEntry NewEntry = ValueEntry(getRank(V), V);
1927   Ops.insert(llvm::lower_bound(Ops, NewEntry), NewEntry);
1928   return nullptr;
1929 }
1930 
1931 Value *ReassociatePass::OptimizeExpression(BinaryOperator *I,
1932                                            SmallVectorImpl<ValueEntry> &Ops) {
1933   // Now that we have the linearized expression tree, try to optimize it.
1934   // Start by folding any constants that we found.
1935   Constant *Cst = nullptr;
1936   unsigned Opcode = I->getOpcode();
1937   while (!Ops.empty() && isa<Constant>(Ops.back().Op)) {
1938     Constant *C = cast<Constant>(Ops.pop_back_val().Op);
1939     Cst = Cst ? ConstantExpr::get(Opcode, C, Cst) : C;
1940   }
1941   // If there was nothing but constants then we are done.
1942   if (Ops.empty())
1943     return Cst;
1944 
1945   // Put the combined constant back at the end of the operand list, except if
1946   // there is no point.  For example, an add of 0 gets dropped here, while a
1947   // multiplication by zero turns the whole expression into zero.
1948   if (Cst && Cst != ConstantExpr::getBinOpIdentity(Opcode, I->getType())) {
1949     if (Cst == ConstantExpr::getBinOpAbsorber(Opcode, I->getType()))
1950       return Cst;
1951     Ops.push_back(ValueEntry(0, Cst));
1952   }
1953 
1954   if (Ops.size() == 1) return Ops[0].Op;
1955 
1956   // Handle destructive annihilation due to identities between elements in the
1957   // argument list here.
1958   unsigned NumOps = Ops.size();
1959   switch (Opcode) {
1960   default: break;
1961   case Instruction::And:
1962   case Instruction::Or:
1963     if (Value *Result = OptimizeAndOrXor(Opcode, Ops))
1964       return Result;
1965     break;
1966 
1967   case Instruction::Xor:
1968     if (Value *Result = OptimizeXor(I, Ops))
1969       return Result;
1970     break;
1971 
1972   case Instruction::Add:
1973   case Instruction::FAdd:
1974     if (Value *Result = OptimizeAdd(I, Ops))
1975       return Result;
1976     break;
1977 
1978   case Instruction::Mul:
1979   case Instruction::FMul:
1980     if (Value *Result = OptimizeMul(I, Ops))
1981       return Result;
1982     break;
1983   }
1984 
1985   if (Ops.size() != NumOps)
1986     return OptimizeExpression(I, Ops);
1987   return nullptr;
1988 }
1989 
1990 // Remove dead instructions and if any operands are trivially dead add them to
1991 // Insts so they will be removed as well.
1992 void ReassociatePass::RecursivelyEraseDeadInsts(Instruction *I,
1993                                                 OrderedSet &Insts) {
1994   assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
1995   SmallVector<Value *, 4> Ops(I->operands());
1996   ValueRankMap.erase(I);
1997   Insts.remove(I);
1998   RedoInsts.remove(I);
1999   llvm::salvageDebugInfo(*I);
2000   I->eraseFromParent();
2001   for (auto Op : Ops)
2002     if (Instruction *OpInst = dyn_cast<Instruction>(Op))
2003       if (OpInst->use_empty())
2004         Insts.insert(OpInst);
2005 }
2006 
2007 /// Zap the given instruction, adding interesting operands to the work list.
2008 void ReassociatePass::EraseInst(Instruction *I) {
2009   assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
2010   LLVM_DEBUG(dbgs() << "Erasing dead inst: "; I->dump());
2011 
2012   SmallVector<Value *, 8> Ops(I->operands());
2013   // Erase the dead instruction.
2014   ValueRankMap.erase(I);
2015   RedoInsts.remove(I);
2016   llvm::salvageDebugInfo(*I);
2017   I->eraseFromParent();
2018   // Optimize its operands.
2019   SmallPtrSet<Instruction *, 8> Visited; // Detect self-referential nodes.
2020   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
2021     if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
2022       // If this is a node in an expression tree, climb to the expression root
2023       // and add that since that's where optimization actually happens.
2024       unsigned Opcode = Op->getOpcode();
2025       while (Op->hasOneUse() && Op->user_back()->getOpcode() == Opcode &&
2026              Visited.insert(Op).second)
2027         Op = Op->user_back();
2028 
2029       // The instruction we're going to push may be coming from a
2030       // dead block, and Reassociate skips the processing of unreachable
2031       // blocks because it's a waste of time and also because it can
2032       // lead to infinite loop due to LLVM's non-standard definition
2033       // of dominance.
2034       if (ValueRankMap.find(Op) != ValueRankMap.end())
2035         RedoInsts.insert(Op);
2036     }
2037 
2038   MadeChange = true;
2039 }
2040 
2041 /// Recursively analyze an expression to build a list of instructions that have
2042 /// negative floating-point constant operands. The caller can then transform
2043 /// the list to create positive constants for better reassociation and CSE.
2044 static void getNegatibleInsts(Value *V,
2045                               SmallVectorImpl<Instruction *> &Candidates) {
2046   // Handle only one-use instructions. Combining negations does not justify
2047   // replicating instructions.
2048   Instruction *I;
2049   if (!match(V, m_OneUse(m_Instruction(I))))
2050     return;
2051 
2052   // Handle expressions of multiplications and divisions.
2053   // TODO: This could look through floating-point casts.
2054   const APFloat *C;
2055   switch (I->getOpcode()) {
2056     case Instruction::FMul:
2057       // Not expecting non-canonical code here. Bail out and wait.
2058       if (match(I->getOperand(0), m_Constant()))
2059         break;
2060 
2061       if (match(I->getOperand(1), m_APFloat(C)) && C->isNegative()) {
2062         Candidates.push_back(I);
2063         LLVM_DEBUG(dbgs() << "FMul with negative constant: " << *I << '\n');
2064       }
2065       getNegatibleInsts(I->getOperand(0), Candidates);
2066       getNegatibleInsts(I->getOperand(1), Candidates);
2067       break;
2068     case Instruction::FDiv:
2069       // Not expecting non-canonical code here. Bail out and wait.
2070       if (match(I->getOperand(0), m_Constant()) &&
2071           match(I->getOperand(1), m_Constant()))
2072         break;
2073 
2074       if ((match(I->getOperand(0), m_APFloat(C)) && C->isNegative()) ||
2075           (match(I->getOperand(1), m_APFloat(C)) && C->isNegative())) {
2076         Candidates.push_back(I);
2077         LLVM_DEBUG(dbgs() << "FDiv with negative constant: " << *I << '\n');
2078       }
2079       getNegatibleInsts(I->getOperand(0), Candidates);
2080       getNegatibleInsts(I->getOperand(1), Candidates);
2081       break;
2082     default:
2083       break;
2084   }
2085 }
2086 
2087 /// Given an fadd/fsub with an operand that is a one-use instruction
2088 /// (the fadd/fsub), try to change negative floating-point constants into
2089 /// positive constants to increase potential for reassociation and CSE.
2090 Instruction *ReassociatePass::canonicalizeNegFPConstantsForOp(Instruction *I,
2091                                                               Instruction *Op,
2092                                                               Value *OtherOp) {
2093   assert((I->getOpcode() == Instruction::FAdd ||
2094           I->getOpcode() == Instruction::FSub) && "Expected fadd/fsub");
2095 
2096   // Collect instructions with negative FP constants from the subtree that ends
2097   // in Op.
2098   SmallVector<Instruction *, 4> Candidates;
2099   getNegatibleInsts(Op, Candidates);
2100   if (Candidates.empty())
2101     return nullptr;
2102 
2103   // Don't canonicalize x + (-Constant * y) -> x - (Constant * y), if the
2104   // resulting subtract will be broken up later.  This can get us into an
2105   // infinite loop during reassociation.
2106   bool IsFSub = I->getOpcode() == Instruction::FSub;
2107   bool NeedsSubtract = !IsFSub && Candidates.size() % 2 == 1;
2108   if (NeedsSubtract && ShouldBreakUpSubtract(I))
2109     return nullptr;
2110 
2111   for (Instruction *Negatible : Candidates) {
2112     const APFloat *C;
2113     if (match(Negatible->getOperand(0), m_APFloat(C))) {
2114       assert(!match(Negatible->getOperand(1), m_Constant()) &&
2115              "Expecting only 1 constant operand");
2116       assert(C->isNegative() && "Expected negative FP constant");
2117       Negatible->setOperand(0, ConstantFP::get(Negatible->getType(), abs(*C)));
2118       MadeChange = true;
2119     }
2120     if (match(Negatible->getOperand(1), m_APFloat(C))) {
2121       assert(!match(Negatible->getOperand(0), m_Constant()) &&
2122              "Expecting only 1 constant operand");
2123       assert(C->isNegative() && "Expected negative FP constant");
2124       Negatible->setOperand(1, ConstantFP::get(Negatible->getType(), abs(*C)));
2125       MadeChange = true;
2126     }
2127   }
2128   assert(MadeChange == true && "Negative constant candidate was not changed");
2129 
2130   // Negations cancelled out.
2131   if (Candidates.size() % 2 == 0)
2132     return I;
2133 
2134   // Negate the final operand in the expression by flipping the opcode of this
2135   // fadd/fsub.
2136   assert(Candidates.size() % 2 == 1 && "Expected odd number");
2137   IRBuilder<> Builder(I);
2138   Value *NewInst = IsFSub ? Builder.CreateFAddFMF(OtherOp, Op, I)
2139                           : Builder.CreateFSubFMF(OtherOp, Op, I);
2140   I->replaceAllUsesWith(NewInst);
2141   RedoInsts.insert(I);
2142   return dyn_cast<Instruction>(NewInst);
2143 }
2144 
2145 /// Canonicalize expressions that contain a negative floating-point constant
2146 /// of the following form:
2147 ///   OtherOp + (subtree) -> OtherOp {+/-} (canonical subtree)
2148 ///   (subtree) + OtherOp -> OtherOp {+/-} (canonical subtree)
2149 ///   OtherOp - (subtree) -> OtherOp {+/-} (canonical subtree)
2150 ///
2151 /// The fadd/fsub opcode may be switched to allow folding a negation into the
2152 /// input instruction.
2153 Instruction *ReassociatePass::canonicalizeNegFPConstants(Instruction *I) {
2154   LLVM_DEBUG(dbgs() << "Combine negations for: " << *I << '\n');
2155   Value *X;
2156   Instruction *Op;
2157   if (match(I, m_FAdd(m_Value(X), m_OneUse(m_Instruction(Op)))))
2158     if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))
2159       I = R;
2160   if (match(I, m_FAdd(m_OneUse(m_Instruction(Op)), m_Value(X))))
2161     if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))
2162       I = R;
2163   if (match(I, m_FSub(m_Value(X), m_OneUse(m_Instruction(Op)))))
2164     if (Instruction *R = canonicalizeNegFPConstantsForOp(I, Op, X))
2165       I = R;
2166   return I;
2167 }
2168 
2169 /// Inspect and optimize the given instruction. Note that erasing
2170 /// instructions is not allowed.
2171 void ReassociatePass::OptimizeInst(Instruction *I) {
2172   // Only consider operations that we understand.
2173   if (!isa<UnaryOperator>(I) && !isa<BinaryOperator>(I))
2174     return;
2175 
2176   if (I->getOpcode() == Instruction::Shl && isa<ConstantInt>(I->getOperand(1)))
2177     // If an operand of this shift is a reassociable multiply, or if the shift
2178     // is used by a reassociable multiply or add, turn into a multiply.
2179     if (isReassociableOp(I->getOperand(0), Instruction::Mul) ||
2180         (I->hasOneUse() &&
2181          (isReassociableOp(I->user_back(), Instruction::Mul) ||
2182           isReassociableOp(I->user_back(), Instruction::Add)))) {
2183       Instruction *NI = ConvertShiftToMul(I);
2184       RedoInsts.insert(I);
2185       MadeChange = true;
2186       I = NI;
2187     }
2188 
2189   // Commute binary operators, to canonicalize the order of their operands.
2190   // This can potentially expose more CSE opportunities, and makes writing other
2191   // transformations simpler.
2192   if (I->isCommutative())
2193     canonicalizeOperands(I);
2194 
2195   // Canonicalize negative constants out of expressions.
2196   if (Instruction *Res = canonicalizeNegFPConstants(I))
2197     I = Res;
2198 
2199   // Don't optimize floating-point instructions unless they are 'fast'.
2200   if (I->getType()->isFPOrFPVectorTy() && !I->isFast())
2201     return;
2202 
2203   // Do not reassociate boolean (i1) expressions.  We want to preserve the
2204   // original order of evaluation for short-circuited comparisons that
2205   // SimplifyCFG has folded to AND/OR expressions.  If the expression
2206   // is not further optimized, it is likely to be transformed back to a
2207   // short-circuited form for code gen, and the source order may have been
2208   // optimized for the most likely conditions.
2209   if (I->getType()->isIntegerTy(1))
2210     return;
2211 
2212   // If this is a bitwise or instruction of operands
2213   // with no common bits set, convert it to X+Y.
2214   if (I->getOpcode() == Instruction::Or &&
2215       shouldConvertOrWithNoCommonBitsToAdd(I) && !isLoadCombineCandidate(I) &&
2216       haveNoCommonBitsSet(I->getOperand(0), I->getOperand(1),
2217                           I->getModule()->getDataLayout(), /*AC=*/nullptr, I,
2218                           /*DT=*/nullptr)) {
2219     Instruction *NI = convertOrWithNoCommonBitsToAdd(I);
2220     RedoInsts.insert(I);
2221     MadeChange = true;
2222     I = NI;
2223   }
2224 
2225   // If this is a subtract instruction which is not already in negate form,
2226   // see if we can convert it to X+-Y.
2227   if (I->getOpcode() == Instruction::Sub) {
2228     if (ShouldBreakUpSubtract(I)) {
2229       Instruction *NI = BreakUpSubtract(I, RedoInsts);
2230       RedoInsts.insert(I);
2231       MadeChange = true;
2232       I = NI;
2233     } else if (match(I, m_Neg(m_Value()))) {
2234       // Otherwise, this is a negation.  See if the operand is a multiply tree
2235       // and if this is not an inner node of a multiply tree.
2236       if (isReassociableOp(I->getOperand(1), Instruction::Mul) &&
2237           (!I->hasOneUse() ||
2238            !isReassociableOp(I->user_back(), Instruction::Mul))) {
2239         Instruction *NI = LowerNegateToMultiply(I);
2240         // If the negate was simplified, revisit the users to see if we can
2241         // reassociate further.
2242         for (User *U : NI->users()) {
2243           if (BinaryOperator *Tmp = dyn_cast<BinaryOperator>(U))
2244             RedoInsts.insert(Tmp);
2245         }
2246         RedoInsts.insert(I);
2247         MadeChange = true;
2248         I = NI;
2249       }
2250     }
2251   } else if (I->getOpcode() == Instruction::FNeg ||
2252              I->getOpcode() == Instruction::FSub) {
2253     if (ShouldBreakUpSubtract(I)) {
2254       Instruction *NI = BreakUpSubtract(I, RedoInsts);
2255       RedoInsts.insert(I);
2256       MadeChange = true;
2257       I = NI;
2258     } else if (match(I, m_FNeg(m_Value()))) {
2259       // Otherwise, this is a negation.  See if the operand is a multiply tree
2260       // and if this is not an inner node of a multiply tree.
2261       Value *Op = isa<BinaryOperator>(I) ? I->getOperand(1) :
2262                                            I->getOperand(0);
2263       if (isReassociableOp(Op, Instruction::FMul) &&
2264           (!I->hasOneUse() ||
2265            !isReassociableOp(I->user_back(), Instruction::FMul))) {
2266         // If the negate was simplified, revisit the users to see if we can
2267         // reassociate further.
2268         Instruction *NI = LowerNegateToMultiply(I);
2269         for (User *U : NI->users()) {
2270           if (BinaryOperator *Tmp = dyn_cast<BinaryOperator>(U))
2271             RedoInsts.insert(Tmp);
2272         }
2273         RedoInsts.insert(I);
2274         MadeChange = true;
2275         I = NI;
2276       }
2277     }
2278   }
2279 
2280   // If this instruction is an associative binary operator, process it.
2281   if (!I->isAssociative()) return;
2282   BinaryOperator *BO = cast<BinaryOperator>(I);
2283 
2284   // If this is an interior node of a reassociable tree, ignore it until we
2285   // get to the root of the tree, to avoid N^2 analysis.
2286   unsigned Opcode = BO->getOpcode();
2287   if (BO->hasOneUse() && BO->user_back()->getOpcode() == Opcode) {
2288     // During the initial run we will get to the root of the tree.
2289     // But if we get here while we are redoing instructions, there is no
2290     // guarantee that the root will be visited. So Redo later
2291     if (BO->user_back() != BO &&
2292         BO->getParent() == BO->user_back()->getParent())
2293       RedoInsts.insert(BO->user_back());
2294     return;
2295   }
2296 
2297   // If this is an add tree that is used by a sub instruction, ignore it
2298   // until we process the subtract.
2299   if (BO->hasOneUse() && BO->getOpcode() == Instruction::Add &&
2300       cast<Instruction>(BO->user_back())->getOpcode() == Instruction::Sub)
2301     return;
2302   if (BO->hasOneUse() && BO->getOpcode() == Instruction::FAdd &&
2303       cast<Instruction>(BO->user_back())->getOpcode() == Instruction::FSub)
2304     return;
2305 
2306   ReassociateExpression(BO);
2307 }
2308 
2309 void ReassociatePass::ReassociateExpression(BinaryOperator *I) {
2310   // First, walk the expression tree, linearizing the tree, collecting the
2311   // operand information.
2312   SmallVector<RepeatedValue, 8> Tree;
2313   MadeChange |= LinearizeExprTree(I, Tree);
2314   SmallVector<ValueEntry, 8> Ops;
2315   Ops.reserve(Tree.size());
2316   for (const RepeatedValue &E : Tree)
2317     Ops.append(E.second.getZExtValue(), ValueEntry(getRank(E.first), E.first));
2318 
2319   LLVM_DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n');
2320 
2321   // Now that we have linearized the tree to a list and have gathered all of
2322   // the operands and their ranks, sort the operands by their rank.  Use a
2323   // stable_sort so that values with equal ranks will have their relative
2324   // positions maintained (and so the compiler is deterministic).  Note that
2325   // this sorts so that the highest ranking values end up at the beginning of
2326   // the vector.
2327   llvm::stable_sort(Ops);
2328 
2329   // Now that we have the expression tree in a convenient
2330   // sorted form, optimize it globally if possible.
2331   if (Value *V = OptimizeExpression(I, Ops)) {
2332     if (V == I)
2333       // Self-referential expression in unreachable code.
2334       return;
2335     // This expression tree simplified to something that isn't a tree,
2336     // eliminate it.
2337     LLVM_DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n');
2338     I->replaceAllUsesWith(V);
2339     if (Instruction *VI = dyn_cast<Instruction>(V))
2340       if (I->getDebugLoc())
2341         VI->setDebugLoc(I->getDebugLoc());
2342     RedoInsts.insert(I);
2343     ++NumAnnihil;
2344     return;
2345   }
2346 
2347   // We want to sink immediates as deeply as possible except in the case where
2348   // this is a multiply tree used only by an add, and the immediate is a -1.
2349   // In this case we reassociate to put the negation on the outside so that we
2350   // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y
2351   if (I->hasOneUse()) {
2352     if (I->getOpcode() == Instruction::Mul &&
2353         cast<Instruction>(I->user_back())->getOpcode() == Instruction::Add &&
2354         isa<ConstantInt>(Ops.back().Op) &&
2355         cast<ConstantInt>(Ops.back().Op)->isMinusOne()) {
2356       ValueEntry Tmp = Ops.pop_back_val();
2357       Ops.insert(Ops.begin(), Tmp);
2358     } else if (I->getOpcode() == Instruction::FMul &&
2359                cast<Instruction>(I->user_back())->getOpcode() ==
2360                    Instruction::FAdd &&
2361                isa<ConstantFP>(Ops.back().Op) &&
2362                cast<ConstantFP>(Ops.back().Op)->isExactlyValue(-1.0)) {
2363       ValueEntry Tmp = Ops.pop_back_val();
2364       Ops.insert(Ops.begin(), Tmp);
2365     }
2366   }
2367 
2368   LLVM_DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n');
2369 
2370   if (Ops.size() == 1) {
2371     if (Ops[0].Op == I)
2372       // Self-referential expression in unreachable code.
2373       return;
2374 
2375     // This expression tree simplified to something that isn't a tree,
2376     // eliminate it.
2377     I->replaceAllUsesWith(Ops[0].Op);
2378     if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op))
2379       OI->setDebugLoc(I->getDebugLoc());
2380     RedoInsts.insert(I);
2381     return;
2382   }
2383 
2384   if (Ops.size() > 2 && Ops.size() <= GlobalReassociateLimit) {
2385     // Find the pair with the highest count in the pairmap and move it to the
2386     // back of the list so that it can later be CSE'd.
2387     // example:
2388     //   a*b*c*d*e
2389     // if c*e is the most "popular" pair, we can express this as
2390     //   (((c*e)*d)*b)*a
2391     unsigned Max = 1;
2392     unsigned BestRank = 0;
2393     std::pair<unsigned, unsigned> BestPair;
2394     unsigned Idx = I->getOpcode() - Instruction::BinaryOpsBegin;
2395     for (unsigned i = 0; i < Ops.size() - 1; ++i)
2396       for (unsigned j = i + 1; j < Ops.size(); ++j) {
2397         unsigned Score = 0;
2398         Value *Op0 = Ops[i].Op;
2399         Value *Op1 = Ops[j].Op;
2400         if (std::less<Value *>()(Op1, Op0))
2401           std::swap(Op0, Op1);
2402         auto it = PairMap[Idx].find({Op0, Op1});
2403         if (it != PairMap[Idx].end()) {
2404           // Functions like BreakUpSubtract() can erase the Values we're using
2405           // as keys and create new Values after we built the PairMap. There's a
2406           // small chance that the new nodes can have the same address as
2407           // something already in the table. We shouldn't accumulate the stored
2408           // score in that case as it refers to the wrong Value.
2409           if (it->second.isValid())
2410             Score += it->second.Score;
2411         }
2412 
2413         unsigned MaxRank = std::max(Ops[i].Rank, Ops[j].Rank);
2414         if (Score > Max || (Score == Max && MaxRank < BestRank)) {
2415           BestPair = {i, j};
2416           Max = Score;
2417           BestRank = MaxRank;
2418         }
2419       }
2420     if (Max > 1) {
2421       auto Op0 = Ops[BestPair.first];
2422       auto Op1 = Ops[BestPair.second];
2423       Ops.erase(&Ops[BestPair.second]);
2424       Ops.erase(&Ops[BestPair.first]);
2425       Ops.push_back(Op0);
2426       Ops.push_back(Op1);
2427     }
2428   }
2429   // Now that we ordered and optimized the expressions, splat them back into
2430   // the expression tree, removing any unneeded nodes.
2431   RewriteExprTree(I, Ops);
2432 }
2433 
2434 void
2435 ReassociatePass::BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT) {
2436   // Make a "pairmap" of how often each operand pair occurs.
2437   for (BasicBlock *BI : RPOT) {
2438     for (Instruction &I : *BI) {
2439       if (!I.isAssociative())
2440         continue;
2441 
2442       // Ignore nodes that aren't at the root of trees.
2443       if (I.hasOneUse() && I.user_back()->getOpcode() == I.getOpcode())
2444         continue;
2445 
2446       // Collect all operands in a single reassociable expression.
2447       // Since Reassociate has already been run once, we can assume things
2448       // are already canonical according to Reassociation's regime.
2449       SmallVector<Value *, 8> Worklist = { I.getOperand(0), I.getOperand(1) };
2450       SmallVector<Value *, 8> Ops;
2451       while (!Worklist.empty() && Ops.size() <= GlobalReassociateLimit) {
2452         Value *Op = Worklist.pop_back_val();
2453         Instruction *OpI = dyn_cast<Instruction>(Op);
2454         if (!OpI || OpI->getOpcode() != I.getOpcode() || !OpI->hasOneUse()) {
2455           Ops.push_back(Op);
2456           continue;
2457         }
2458         // Be paranoid about self-referencing expressions in unreachable code.
2459         if (OpI->getOperand(0) != OpI)
2460           Worklist.push_back(OpI->getOperand(0));
2461         if (OpI->getOperand(1) != OpI)
2462           Worklist.push_back(OpI->getOperand(1));
2463       }
2464       // Skip extremely long expressions.
2465       if (Ops.size() > GlobalReassociateLimit)
2466         continue;
2467 
2468       // Add all pairwise combinations of operands to the pair map.
2469       unsigned BinaryIdx = I.getOpcode() - Instruction::BinaryOpsBegin;
2470       SmallSet<std::pair<Value *, Value*>, 32> Visited;
2471       for (unsigned i = 0; i < Ops.size() - 1; ++i) {
2472         for (unsigned j = i + 1; j < Ops.size(); ++j) {
2473           // Canonicalize operand orderings.
2474           Value *Op0 = Ops[i];
2475           Value *Op1 = Ops[j];
2476           if (std::less<Value *>()(Op1, Op0))
2477             std::swap(Op0, Op1);
2478           if (!Visited.insert({Op0, Op1}).second)
2479             continue;
2480           auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, {Op0, Op1, 1}});
2481           if (!res.second) {
2482             // If either key value has been erased then we've got the same
2483             // address by coincidence. That can't happen here because nothing is
2484             // erasing values but it can happen by the time we're querying the
2485             // map.
2486             assert(res.first->second.isValid() && "WeakVH invalidated");
2487             ++res.first->second.Score;
2488           }
2489         }
2490       }
2491     }
2492   }
2493 }
2494 
2495 PreservedAnalyses ReassociatePass::run(Function &F, FunctionAnalysisManager &) {
2496   // Get the functions basic blocks in Reverse Post Order. This order is used by
2497   // BuildRankMap to pre calculate ranks correctly. It also excludes dead basic
2498   // blocks (it has been seen that the analysis in this pass could hang when
2499   // analysing dead basic blocks).
2500   ReversePostOrderTraversal<Function *> RPOT(&F);
2501 
2502   // Calculate the rank map for F.
2503   BuildRankMap(F, RPOT);
2504 
2505   // Build the pair map before running reassociate.
2506   // Technically this would be more accurate if we did it after one round
2507   // of reassociation, but in practice it doesn't seem to help much on
2508   // real-world code, so don't waste the compile time running reassociate
2509   // twice.
2510   // If a user wants, they could expicitly run reassociate twice in their
2511   // pass pipeline for further potential gains.
2512   // It might also be possible to update the pair map during runtime, but the
2513   // overhead of that may be large if there's many reassociable chains.
2514   BuildPairMap(RPOT);
2515 
2516   MadeChange = false;
2517 
2518   // Traverse the same blocks that were analysed by BuildRankMap.
2519   for (BasicBlock *BI : RPOT) {
2520     assert(RankMap.count(&*BI) && "BB should be ranked.");
2521     // Optimize every instruction in the basic block.
2522     for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;)
2523       if (isInstructionTriviallyDead(&*II)) {
2524         EraseInst(&*II++);
2525       } else {
2526         OptimizeInst(&*II);
2527         assert(II->getParent() == &*BI && "Moved to a different block!");
2528         ++II;
2529       }
2530 
2531     // Make a copy of all the instructions to be redone so we can remove dead
2532     // instructions.
2533     OrderedSet ToRedo(RedoInsts);
2534     // Iterate over all instructions to be reevaluated and remove trivially dead
2535     // instructions. If any operand of the trivially dead instruction becomes
2536     // dead mark it for deletion as well. Continue this process until all
2537     // trivially dead instructions have been removed.
2538     while (!ToRedo.empty()) {
2539       Instruction *I = ToRedo.pop_back_val();
2540       if (isInstructionTriviallyDead(I)) {
2541         RecursivelyEraseDeadInsts(I, ToRedo);
2542         MadeChange = true;
2543       }
2544     }
2545 
2546     // Now that we have removed dead instructions, we can reoptimize the
2547     // remaining instructions.
2548     while (!RedoInsts.empty()) {
2549       Instruction *I = RedoInsts.front();
2550       RedoInsts.erase(RedoInsts.begin());
2551       if (isInstructionTriviallyDead(I))
2552         EraseInst(I);
2553       else
2554         OptimizeInst(I);
2555     }
2556   }
2557 
2558   // We are done with the rank map and pair map.
2559   RankMap.clear();
2560   ValueRankMap.clear();
2561   for (auto &Entry : PairMap)
2562     Entry.clear();
2563 
2564   if (MadeChange) {
2565     PreservedAnalyses PA;
2566     PA.preserveSet<CFGAnalyses>();
2567     return PA;
2568   }
2569 
2570   return PreservedAnalyses::all();
2571 }
2572 
2573 namespace {
2574 
2575   class ReassociateLegacyPass : public FunctionPass {
2576     ReassociatePass Impl;
2577 
2578   public:
2579     static char ID; // Pass identification, replacement for typeid
2580 
2581     ReassociateLegacyPass() : FunctionPass(ID) {
2582       initializeReassociateLegacyPassPass(*PassRegistry::getPassRegistry());
2583     }
2584 
2585     bool runOnFunction(Function &F) override {
2586       if (skipFunction(F))
2587         return false;
2588 
2589       FunctionAnalysisManager DummyFAM;
2590       auto PA = Impl.run(F, DummyFAM);
2591       return !PA.areAllPreserved();
2592     }
2593 
2594     void getAnalysisUsage(AnalysisUsage &AU) const override {
2595       AU.setPreservesCFG();
2596       AU.addPreserved<AAResultsWrapperPass>();
2597       AU.addPreserved<BasicAAWrapperPass>();
2598       AU.addPreserved<GlobalsAAWrapperPass>();
2599     }
2600   };
2601 
2602 } // end anonymous namespace
2603 
2604 char ReassociateLegacyPass::ID = 0;
2605 
2606 INITIALIZE_PASS(ReassociateLegacyPass, "reassociate",
2607                 "Reassociate expressions", false, false)
2608 
2609 // Public interface to the Reassociate pass
2610 FunctionPass *llvm::createReassociatePass() {
2611   return new ReassociateLegacyPass();
2612 }
2613