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