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