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