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