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