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  BasicBlock::iterator InsertPt;
865  if (Instruction *InstInput = dyn_cast<Instruction>(V)) {
866  if (InvokeInst *II = dyn_cast<InvokeInst>(InstInput)) {
867  InsertPt = II->getNormalDest()->begin();
868  } else {
869  InsertPt = ++InstInput->getIterator();
870  }
871  while (isa<PHINode>(InsertPt)) ++InsertPt;
872  } else {
873  InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin();
874  }
875  TheNeg->moveBefore(&*InsertPt);
876  if (TheNeg->getOpcode() == Instruction::Sub) {
877  TheNeg->setHasNoUnsignedWrap(false);
878  TheNeg->setHasNoSignedWrap(false);
879  } else {
880  TheNeg->andIRFlags(BI);
881  }
882  ToRedo.insert(TheNeg);
883  return TheNeg;
884  }
885 
886  // Insert a 'neg' instruction that subtracts the value from zero to get the
887  // negation.
888  BinaryOperator *NewNeg = CreateNeg(V, V->getName() + ".neg", BI, BI);
889  ToRedo.insert(NewNeg);
890  return NewNeg;
891 }
892 
893 /// Return true if we should break up this subtract of X-Y into (X + -Y).
895  // If this is a negation, we can't split it up!
896  if (match(Sub, m_Neg(m_Value())) || match(Sub, m_FNeg(m_Value())))
897  return false;
898 
899  // Don't breakup X - undef.
900  if (isa<UndefValue>(Sub->getOperand(1)))
901  return false;
902 
903  // Don't bother to break this up unless either the LHS is an associable add or
904  // subtract or if this is only used by one.
905  Value *V0 = Sub->getOperand(0);
906  if (isReassociableOp(V0, Instruction::Add, Instruction::FAdd) ||
907  isReassociableOp(V0, Instruction::Sub, Instruction::FSub))
908  return true;
909  Value *V1 = Sub->getOperand(1);
910  if (isReassociableOp(V1, Instruction::Add, Instruction::FAdd) ||
911  isReassociableOp(V1, Instruction::Sub, Instruction::FSub))
912  return true;
913  Value *VB = Sub->user_back();
914  if (Sub->hasOneUse() &&
915  (isReassociableOp(VB, Instruction::Add, Instruction::FAdd) ||
916  isReassociableOp(VB, Instruction::Sub, Instruction::FSub)))
917  return true;
918 
919  return false;
920 }
921 
922 /// If we have (X-Y), and if either X is an add, or if this is only used by an
923 /// add, transform this into (X+(0-Y)) to promote better reassociation.
925  ReassociatePass::OrderedSet &ToRedo) {
926  // Convert a subtract into an add and a neg instruction. This allows sub
927  // instructions to be commuted with other add instructions.
928  //
929  // Calculate the negative value of Operand 1 of the sub instruction,
930  // and set it as the RHS of the add instruction we just made.
931  Value *NegVal = NegateValue(Sub->getOperand(1), Sub, ToRedo);
932  BinaryOperator *New = CreateAdd(Sub->getOperand(0), NegVal, "", Sub, Sub);
933  Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op.
934  Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op.
935  New->takeName(Sub);
936 
937  // Everyone now refers to the add instruction.
938  Sub->replaceAllUsesWith(New);
939  New->setDebugLoc(Sub->getDebugLoc());
940 
941  LLVM_DEBUG(dbgs() << "Negated: " << *New << '\n');
942  return New;
943 }
944 
945 /// If this is a shift of a reassociable multiply or is used by one, change
946 /// this into a multiply by a constant to assist with further reassociation.
948  Constant *MulCst = ConstantInt::get(Shl->getType(), 1);
949  MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1)));
950 
951  BinaryOperator *Mul =
952  BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl);
953  Shl->setOperand(0, UndefValue::get(Shl->getType())); // Drop use of op.
954  Mul->takeName(Shl);
955 
956  // Everyone now refers to the mul instruction.
957  Shl->replaceAllUsesWith(Mul);
958  Mul->setDebugLoc(Shl->getDebugLoc());
959 
960  // We can safely preserve the nuw flag in all cases. It's also safe to turn a
961  // nuw nsw shl into a nuw nsw mul. However, nsw in isolation requires special
962  // handling.
963  bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
964  bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
965  if (NSW && NUW)
966  Mul->setHasNoSignedWrap(true);
967  Mul->setHasNoUnsignedWrap(NUW);
968  return Mul;
969 }
970 
971 /// Scan backwards and forwards among values with the same rank as element i
972 /// to see if X exists. If X does not exist, return i. This is useful when
973 /// scanning for 'x' when we see '-x' because they both get the same rank.
975  unsigned i, Value *X) {
976  unsigned XRank = Ops[i].Rank;
977  unsigned e = Ops.size();
978  for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {
979  if (Ops[j].Op == X)
980  return j;
981  if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
982  if (Instruction *I2 = dyn_cast<Instruction>(X))
983  if (I1->isIdenticalTo(I2))
984  return j;
985  }
986  // Scan backwards.
987  for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {
988  if (Ops[j].Op == X)
989  return j;
990  if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
991  if (Instruction *I2 = dyn_cast<Instruction>(X))
992  if (I1->isIdenticalTo(I2))
993  return j;
994  }
995  return i;
996 }
997 
998 /// Emit a tree of add instructions, summing Ops together
999 /// and returning the result. Insert the tree before I.
1002  if (Ops.size() == 1) return Ops.back();
1003 
1004  Value *V1 = Ops.back();
1005  Ops.pop_back();
1006  Value *V2 = EmitAddTreeOfValues(I, Ops);
1007  return CreateAdd(V2, V1, "reass.add", I, I);
1008 }
1009 
1010 /// If V is an expression tree that is a multiplication sequence,
1011 /// and if this sequence contains a multiply by Factor,
1012 /// remove Factor from the tree and return the new tree.
1013 Value *ReassociatePass::RemoveFactorFromExpression(Value *V, Value *Factor) {
1014  BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul);
1015  if (!BO)
1016  return nullptr;
1017 
1019  MadeChange |= LinearizeExprTree(BO, Tree);
1021  Factors.reserve(Tree.size());
1022  for (unsigned i = 0, e = Tree.size(); i != e; ++i) {
1023  RepeatedValue E = Tree[i];
1024  Factors.append(E.second.getZExtValue(),
1025  ValueEntry(getRank(E.first), E.first));
1026  }
1027 
1028  bool FoundFactor = false;
1029  bool NeedsNegate = false;
1030  for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
1031  if (Factors[i].Op == Factor) {
1032  FoundFactor = true;
1033  Factors.erase(Factors.begin()+i);
1034  break;
1035  }
1036 
1037  // If this is a negative version of this factor, remove it.
1038  if (ConstantInt *FC1 = dyn_cast<ConstantInt>(Factor)) {
1039  if (ConstantInt *FC2 = dyn_cast<ConstantInt>(Factors[i].Op))
1040  if (FC1->getValue() == -FC2->getValue()) {
1041  FoundFactor = NeedsNegate = true;
1042  Factors.erase(Factors.begin()+i);
1043  break;
1044  }
1045  } else if (ConstantFP *FC1 = dyn_cast<ConstantFP>(Factor)) {
1046  if (ConstantFP *FC2 = dyn_cast<ConstantFP>(Factors[i].Op)) {
1047  const APFloat &F1 = FC1->getValueAPF();
1048  APFloat F2(FC2->getValueAPF());
1049  F2.changeSign();
1050  if (F1.compare(F2) == APFloat::cmpEqual) {
1051  FoundFactor = NeedsNegate = true;
1052  Factors.erase(Factors.begin() + i);
1053  break;
1054  }
1055  }
1056  }
1057  }
1058 
1059  if (!FoundFactor) {
1060  // Make sure to restore the operands to the expression tree.
1061  RewriteExprTree(BO, Factors);
1062  return nullptr;
1063  }
1064 
1065  BasicBlock::iterator InsertPt = ++BO->getIterator();
1066 
1067  // If this was just a single multiply, remove the multiply and return the only
1068  // remaining operand.
1069  if (Factors.size() == 1) {
1070  RedoInsts.insert(BO);
1071  V = Factors[0].Op;
1072  } else {
1073  RewriteExprTree(BO, Factors);
1074  V = BO;
1075  }
1076 
1077  if (NeedsNegate)
1078  V = CreateNeg(V, "neg", &*InsertPt, BO);
1079 
1080  return V;
1081 }
1082 
1083 /// If V is a single-use multiply, recursively add its operands as factors,
1084 /// otherwise add V to the list of factors.
1085 ///
1086 /// Ops is the top-level list of add operands we're trying to factor.
1088  SmallVectorImpl<Value*> &Factors) {
1089  BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul);
1090  if (!BO) {
1091  Factors.push_back(V);
1092  return;
1093  }
1094 
1095  // Otherwise, add the LHS and RHS to the list of factors.
1096  FindSingleUseMultiplyFactors(BO->getOperand(1), Factors);
1097  FindSingleUseMultiplyFactors(BO->getOperand(0), Factors);
1098 }
1099 
1100 /// Optimize a series of operands to an 'and', 'or', or 'xor' instruction.
1101 /// This optimizes based on identities. If it can be reduced to a single Value,
1102 /// it is returned, otherwise the Ops list is mutated as necessary.
1103 static Value *OptimizeAndOrXor(unsigned Opcode,
1105  // Scan the operand lists looking for X and ~X pairs, along with X,X pairs.
1106  // If we find any, we can simplify the expression. X&~X == 0, X|~X == -1.
1107  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1108  // First, check for X and ~X in the operand list.
1109  assert(i < Ops.size());
1110  Value *X;
1111  if (match(Ops[i].Op, m_Not(m_Value(X)))) { // Cannot occur for ^.
1112  unsigned FoundX = FindInOperandList(Ops, i, X);
1113  if (FoundX != i) {
1114  if (Opcode == Instruction::And) // ...&X&~X = 0
1115  return Constant::getNullValue(X->getType());
1116 
1117  if (Opcode == Instruction::Or) // ...|X|~X = -1
1118  return Constant::getAllOnesValue(X->getType());
1119  }
1120  }
1121 
1122  // Next, check for duplicate pairs of values, which we assume are next to
1123  // each other, due to our sorting criteria.
1124  assert(i < Ops.size());
1125  if (i+1 != Ops.size() && Ops[i+1].Op == Ops[i].Op) {
1126  if (Opcode == Instruction::And || Opcode == Instruction::Or) {
1127  // Drop duplicate values for And and Or.
1128  Ops.erase(Ops.begin()+i);
1129  --i; --e;
1130  ++NumAnnihil;
1131  continue;
1132  }
1133 
1134  // Drop pairs of values for Xor.
1135  assert(Opcode == Instruction::Xor);
1136  if (e == 2)
1137  return Constant::getNullValue(Ops[0].Op->getType());
1138 
1139  // Y ^ X^X -> Y
1140  Ops.erase(Ops.begin()+i, Ops.begin()+i+2);
1141  i -= 1; e -= 2;
1142  ++NumAnnihil;
1143  }
1144  }
1145  return nullptr;
1146 }
1147 
1148 /// Helper function of CombineXorOpnd(). It creates a bitwise-and
1149 /// instruction with the given two operands, and return the resulting
1150 /// instruction. There are two special cases: 1) if the constant operand is 0,
1151 /// it will return NULL. 2) if the constant is ~0, the symbolic operand will
1152 /// be returned.
1153 static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd,
1154  const APInt &ConstOpnd) {
1155  if (ConstOpnd.isNullValue())
1156  return nullptr;
1157 
1158  if (ConstOpnd.isAllOnesValue())
1159  return Opnd;
1160 
1161  Instruction *I = BinaryOperator::CreateAnd(
1162  Opnd, ConstantInt::get(Opnd->getType(), ConstOpnd), "and.ra",
1163  InsertBefore);
1164  I->setDebugLoc(InsertBefore->getDebugLoc());
1165  return I;
1166 }
1167 
1168 // Helper function of OptimizeXor(). It tries to simplify "Opnd1 ^ ConstOpnd"
1169 // into "R ^ C", where C would be 0, and R is a symbolic value.
1170 //
1171 // If it was successful, true is returned, and the "R" and "C" is returned
1172 // via "Res" and "ConstOpnd", respectively; otherwise, false is returned,
1173 // and both "Res" and "ConstOpnd" remain unchanged.
1174 bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
1175  APInt &ConstOpnd, Value *&Res) {
1176  // Xor-Rule 1: (x | c1) ^ c2 = (x | c1) ^ (c1 ^ c1) ^ c2
1177  // = ((x | c1) ^ c1) ^ (c1 ^ c2)
1178  // = (x & ~c1) ^ (c1 ^ c2)
1179  // It is useful only when c1 == c2.
1180  if (!Opnd1->isOrExpr() || Opnd1->getConstPart().isNullValue())
1181  return false;
1182 
1183  if (!Opnd1->getValue()->hasOneUse())
1184  return false;
1185 
1186  const APInt &C1 = Opnd1->getConstPart();
1187  if (C1 != ConstOpnd)
1188  return false;
1189 
1190  Value *X = Opnd1->getSymbolicPart();
1191  Res = createAndInstr(I, X, ~C1);
1192  // ConstOpnd was C2, now C1 ^ C2.
1193  ConstOpnd ^= C1;
1194 
1195  if (Instruction *T = dyn_cast<Instruction>(Opnd1->getValue()))
1196  RedoInsts.insert(T);
1197  return true;
1198 }
1199 
1200 // Helper function of OptimizeXor(). It tries to simplify
1201 // "Opnd1 ^ Opnd2 ^ ConstOpnd" into "R ^ C", where C would be 0, and R is a
1202 // symbolic value.
1203 //
1204 // If it was successful, true is returned, and the "R" and "C" is returned
1205 // via "Res" and "ConstOpnd", respectively (If the entire expression is
1206 // evaluated to a constant, the Res is set to NULL); otherwise, false is
1207 // returned, and both "Res" and "ConstOpnd" remain unchanged.
1208 bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
1209  XorOpnd *Opnd2, APInt &ConstOpnd,
1210  Value *&Res) {
1211  Value *X = Opnd1->getSymbolicPart();
1212  if (X != Opnd2->getSymbolicPart())
1213  return false;
1214 
1215  // This many instruction become dead.(At least "Opnd1 ^ Opnd2" will die.)
1216  int DeadInstNum = 1;
1217  if (Opnd1->getValue()->hasOneUse())
1218  DeadInstNum++;
1219  if (Opnd2->getValue()->hasOneUse())
1220  DeadInstNum++;
1221 
1222  // Xor-Rule 2:
1223  // (x | c1) ^ (x & c2)
1224  // = (x|c1) ^ (x&c2) ^ (c1 ^ c1) = ((x|c1) ^ c1) ^ (x & c2) ^ c1
1225  // = (x & ~c1) ^ (x & c2) ^ c1 // Xor-Rule 1
1226  // = (x & c3) ^ c1, where c3 = ~c1 ^ c2 // Xor-rule 3
1227  //
1228  if (Opnd1->isOrExpr() != Opnd2->isOrExpr()) {
1229  if (Opnd2->isOrExpr())
1230  std::swap(Opnd1, Opnd2);
1231 
1232  const APInt &C1 = Opnd1->getConstPart();
1233  const APInt &C2 = Opnd2->getConstPart();
1234  APInt C3((~C1) ^ C2);
1235 
1236  // Do not increase code size!
1237  if (!C3.isNullValue() && !C3.isAllOnesValue()) {
1238  int NewInstNum = ConstOpnd.getBoolValue() ? 1 : 2;
1239  if (NewInstNum > DeadInstNum)
1240  return false;
1241  }
1242 
1243  Res = createAndInstr(I, X, C3);
1244  ConstOpnd ^= C1;
1245  } else if (Opnd1->isOrExpr()) {
1246  // Xor-Rule 3: (x | c1) ^ (x | c2) = (x & c3) ^ c3 where c3 = c1 ^ c2
1247  //
1248  const APInt &C1 = Opnd1->getConstPart();
1249  const APInt &C2 = Opnd2->getConstPart();
1250  APInt C3 = C1 ^ C2;
1251 
1252  // Do not increase code size
1253  if (!C3.isNullValue() && !C3.isAllOnesValue()) {
1254  int NewInstNum = ConstOpnd.getBoolValue() ? 1 : 2;
1255  if (NewInstNum > DeadInstNum)
1256  return false;
1257  }
1258 
1259  Res = createAndInstr(I, X, C3);
1260  ConstOpnd ^= C3;
1261  } else {
1262  // Xor-Rule 4: (x & c1) ^ (x & c2) = (x & (c1^c2))
1263  //
1264  const APInt &C1 = Opnd1->getConstPart();
1265  const APInt &C2 = Opnd2->getConstPart();
1266  APInt C3 = C1 ^ C2;
1267  Res = createAndInstr(I, X, C3);
1268  }
1269 
1270  // Put the original operands in the Redo list; hope they will be deleted
1271  // as dead code.
1272  if (Instruction *T = dyn_cast<Instruction>(Opnd1->getValue()))
1273  RedoInsts.insert(T);
1274  if (Instruction *T = dyn_cast<Instruction>(Opnd2->getValue()))
1275  RedoInsts.insert(T);
1276 
1277  return true;
1278 }
1279 
1280 /// Optimize a series of operands to an 'xor' instruction. If it can be reduced
1281 /// to a single Value, it is returned, otherwise the Ops list is mutated as
1282 /// necessary.
1283 Value *ReassociatePass::OptimizeXor(Instruction *I,
1285  if (Value *V = OptimizeAndOrXor(Instruction::Xor, Ops))
1286  return V;
1287 
1288  if (Ops.size() == 1)
1289  return nullptr;
1290 
1292  SmallVector<XorOpnd*, 8> OpndPtrs;
1293  Type *Ty = Ops[0].Op->getType();
1294  APInt ConstOpnd(Ty->getScalarSizeInBits(), 0);
1295 
1296  // Step 1: Convert ValueEntry to XorOpnd
1297  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1298  Value *V = Ops[i].Op;
1299  const APInt *C;
1300  // TODO: Support non-splat vectors.
1301  if (match(V, m_APInt(C))) {
1302  ConstOpnd ^= *C;
1303  } else {
1304  XorOpnd O(V);
1305  O.setSymbolicRank(getRank(O.getSymbolicPart()));
1306  Opnds.push_back(O);
1307  }
1308  }
1309 
1310  // NOTE: From this point on, do *NOT* add/delete element to/from "Opnds".
1311  // It would otherwise invalidate the "Opnds"'s iterator, and hence invalidate
1312  // the "OpndPtrs" as well. For the similar reason, do not fuse this loop
1313  // with the previous loop --- the iterator of the "Opnds" may be invalidated
1314  // when new elements are added to the vector.
1315  for (unsigned i = 0, e = Opnds.size(); i != e; ++i)
1316  OpndPtrs.push_back(&Opnds[i]);
1317 
1318  // Step 2: Sort the Xor-Operands in a way such that the operands containing
1319  // the same symbolic value cluster together. For instance, the input operand
1320  // sequence ("x | 123", "y & 456", "x & 789") will be sorted into:
1321  // ("x | 123", "x & 789", "y & 456").
1322  //
1323  // The purpose is twofold:
1324  // 1) Cluster together the operands sharing the same symbolic-value.
1325  // 2) Operand having smaller symbolic-value-rank is permuted earlier, which
1326  // could potentially shorten crital path, and expose more loop-invariants.
1327  // Note that values' rank are basically defined in RPO order (FIXME).
1328  // So, if Rank(X) < Rank(Y) < Rank(Z), it means X is defined earlier
1329  // than Y which is defined earlier than Z. Permute "x | 1", "Y & 2",
1330  // "z" in the order of X-Y-Z is better than any other orders.
1331  std::stable_sort(OpndPtrs.begin(), OpndPtrs.end(),
1332  [](XorOpnd *LHS, XorOpnd *RHS) {
1333  return LHS->getSymbolicRank() < RHS->getSymbolicRank();
1334  });
1335 
1336  // Step 3: Combine adjacent operands
1337  XorOpnd *PrevOpnd = nullptr;
1338  bool Changed = false;
1339  for (unsigned i = 0, e = Opnds.size(); i < e; i++) {
1340  XorOpnd *CurrOpnd = OpndPtrs[i];
1341  // The combined value
1342  Value *CV;
1343 
1344  // Step 3.1: Try simplifying "CurrOpnd ^ ConstOpnd"
1345  if (!ConstOpnd.isNullValue() &&
1346  CombineXorOpnd(I, CurrOpnd, ConstOpnd, CV)) {
1347  Changed = true;
1348  if (CV)
1349  *CurrOpnd = XorOpnd(CV);
1350  else {
1351  CurrOpnd->Invalidate();
1352  continue;
1353  }
1354  }
1355 
1356  if (!PrevOpnd || CurrOpnd->getSymbolicPart() != PrevOpnd->getSymbolicPart()) {
1357  PrevOpnd = CurrOpnd;
1358  continue;
1359  }
1360 
1361  // step 3.2: When previous and current operands share the same symbolic
1362  // value, try to simplify "PrevOpnd ^ CurrOpnd ^ ConstOpnd"
1363  if (CombineXorOpnd(I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
1364  // Remove previous operand
1365  PrevOpnd->Invalidate();
1366  if (CV) {
1367  *CurrOpnd = XorOpnd(CV);
1368  PrevOpnd = CurrOpnd;
1369  } else {
1370  CurrOpnd->Invalidate();
1371  PrevOpnd = nullptr;
1372  }
1373  Changed = true;
1374  }
1375  }
1376 
1377  // Step 4: Reassemble the Ops
1378  if (Changed) {
1379  Ops.clear();
1380  for (unsigned int i = 0, e = Opnds.size(); i < e; i++) {
1381  XorOpnd &O = Opnds[i];
1382  if (O.isInvalid())
1383  continue;
1384  ValueEntry VE(getRank(O.getValue()), O.getValue());
1385  Ops.push_back(VE);
1386  }
1387  if (!ConstOpnd.isNullValue()) {
1388  Value *C = ConstantInt::get(Ty, ConstOpnd);
1389  ValueEntry VE(getRank(C), C);
1390  Ops.push_back(VE);
1391  }
1392  unsigned Sz = Ops.size();
1393  if (Sz == 1)
1394  return Ops.back().Op;
1395  if (Sz == 0) {
1396  assert(ConstOpnd.isNullValue());
1397  return ConstantInt::get(Ty, ConstOpnd);
1398  }
1399  }
1400 
1401  return nullptr;
1402 }
1403 
1404 /// Optimize a series of operands to an 'add' instruction. This
1405 /// optimizes based on identities. If it can be reduced to a single Value, it
1406 /// is returned, otherwise the Ops list is mutated as necessary.
1407 Value *ReassociatePass::OptimizeAdd(Instruction *I,
1409  // Scan the operand lists looking for X and -X pairs. If we find any, we
1410  // can simplify expressions like X+-X == 0 and X+~X ==-1. While we're at it,
1411  // scan for any
1412  // duplicates. We want to canonicalize Y+Y+Y+Z -> 3*Y+Z.
1413 
1414  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1415  Value *TheOp = Ops[i].Op;
1416  // Check to see if we've seen this operand before. If so, we factor all
1417  // instances of the operand together. Due to our sorting criteria, we know
1418  // that these need to be next to each other in the vector.
1419  if (i+1 != Ops.size() && Ops[i+1].Op == TheOp) {
1420  // Rescan the list, remove all instances of this operand from the expr.
1421  unsigned NumFound = 0;
1422  do {
1423  Ops.erase(Ops.begin()+i);
1424  ++NumFound;
1425  } while (i != Ops.size() && Ops[i].Op == TheOp);
1426 
1427  LLVM_DEBUG(dbgs() << "\nFACTORING [" << NumFound << "]: " << *TheOp
1428  << '\n');
1429  ++NumFactor;
1430 
1431  // Insert a new multiply.
1432  Type *Ty = TheOp->getType();
1433  Constant *C = Ty->isIntOrIntVectorTy() ?
1434  ConstantInt::get(Ty, NumFound) : ConstantFP::get(Ty, NumFound);
1435  Instruction *Mul = CreateMul(TheOp, C, "factor", I, I);
1436 
1437  // Now that we have inserted a multiply, optimize it. This allows us to
1438  // handle cases that require multiple factoring steps, such as this:
1439  // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6
1440  RedoInsts.insert(Mul);
1441 
1442  // If every add operand was a duplicate, return the multiply.
1443  if (Ops.empty())
1444  return Mul;
1445 
1446  // Otherwise, we had some input that didn't have the dupe, such as
1447  // "A + A + B" -> "A*2 + B". Add the new multiply to the list of
1448  // things being added by this operation.
1449  Ops.insert(Ops.begin(), ValueEntry(getRank(Mul), Mul));
1450 
1451  --i;
1452  e = Ops.size();
1453  continue;
1454  }
1455 
1456  // Check for X and -X or X and ~X in the operand list.
1457  Value *X;
1458  if (!match(TheOp, m_Neg(m_Value(X))) && !match(TheOp, m_Not(m_Value(X))) &&
1459  !match(TheOp, m_FNeg(m_Value(X))))
1460  continue;
1461 
1462  unsigned FoundX = FindInOperandList(Ops, i, X);
1463  if (FoundX == i)
1464  continue;
1465 
1466  // Remove X and -X from the operand list.
1467  if (Ops.size() == 2 &&
1468  (match(TheOp, m_Neg(m_Value())) || match(TheOp, m_FNeg(m_Value()))))
1469  return Constant::getNullValue(X->getType());
1470 
1471  // Remove X and ~X from the operand list.
1472  if (Ops.size() == 2 && match(TheOp, m_Not(m_Value())))
1473  return Constant::getAllOnesValue(X->getType());
1474 
1475  Ops.erase(Ops.begin()+i);
1476  if (i < FoundX)
1477  --FoundX;
1478  else
1479  --i; // Need to back up an extra one.
1480  Ops.erase(Ops.begin()+FoundX);
1481  ++NumAnnihil;
1482  --i; // Revisit element.
1483  e -= 2; // Removed two elements.
1484 
1485  // if X and ~X we append -1 to the operand list.
1486  if (match(TheOp, m_Not(m_Value()))) {
1488  Ops.insert(Ops.end(), ValueEntry(getRank(V), V));
1489  e += 1;
1490  }
1491  }
1492 
1493  // Scan the operand list, checking to see if there are any common factors
1494  // between operands. Consider something like A*A+A*B*C+D. We would like to
1495  // reassociate this to A*(A+B*C)+D, which reduces the number of multiplies.
1496  // To efficiently find this, we count the number of times a factor occurs
1497  // for any ADD operands that are MULs.
1498  DenseMap<Value*, unsigned> FactorOccurrences;
1499 
1500  // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4)
1501  // where they are actually the same multiply.
1502  unsigned MaxOcc = 0;
1503  Value *MaxOccVal = nullptr;
1504  for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1505  BinaryOperator *BOp =
1506  isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul);
1507  if (!BOp)
1508  continue;
1509 
1510  // Compute all of the factors of this added value.
1511  SmallVector<Value*, 8> Factors;
1512  FindSingleUseMultiplyFactors(BOp, Factors);
1513  assert(Factors.size() > 1 && "Bad linearize!");
1514 
1515  // Add one to FactorOccurrences for each unique factor in this op.
1516  SmallPtrSet<Value*, 8> Duplicates;
1517  for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
1518  Value *Factor = Factors[i];
1519  if (!Duplicates.insert(Factor).second)
1520  continue;
1521 
1522  unsigned Occ = ++FactorOccurrences[Factor];
1523  if (Occ > MaxOcc) {
1524  MaxOcc = Occ;
1525  MaxOccVal = Factor;
1526  }
1527 
1528  // If Factor is a negative constant, add the negated value as a factor
1529  // because we can percolate the negate out. Watch for minint, which
1530  // cannot be positivified.
1531  if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor)) {
1532  if (CI->isNegative() && !CI->isMinValue(true)) {
1533  Factor = ConstantInt::get(CI->getContext(), -CI->getValue());
1534  if (!Duplicates.insert(Factor).second)
1535  continue;
1536  unsigned Occ = ++FactorOccurrences[Factor];
1537  if (Occ > MaxOcc) {
1538  MaxOcc = Occ;
1539  MaxOccVal = Factor;
1540  }
1541  }
1542  } else if (ConstantFP *CF = dyn_cast<ConstantFP>(Factor)) {
1543  if (CF->isNegative()) {
1544  APFloat F(CF->getValueAPF());
1545  F.changeSign();
1546  Factor = ConstantFP::get(CF->getContext(), F);
1547  if (!Duplicates.insert(Factor).second)
1548  continue;
1549  unsigned Occ = ++FactorOccurrences[Factor];
1550  if (Occ > MaxOcc) {
1551  MaxOcc = Occ;
1552  MaxOccVal = Factor;
1553  }
1554  }
1555  }
1556  }
1557  }
1558 
1559  // If any factor occurred more than one time, we can pull it out.
1560  if (MaxOcc > 1) {
1561  LLVM_DEBUG(dbgs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal
1562  << '\n');
1563  ++NumFactor;
1564 
1565  // Create a new instruction that uses the MaxOccVal twice. If we don't do
1566  // this, we could otherwise run into situations where removing a factor
1567  // from an expression will drop a use of maxocc, and this can cause
1568  // RemoveFactorFromExpression on successive values to behave differently.
1569  Instruction *DummyInst =
1570  I->getType()->isIntOrIntVectorTy()
1571  ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal)
1572  : BinaryOperator::CreateFAdd(MaxOccVal, MaxOccVal);
1573 
1575  for (unsigned i = 0; i != Ops.size(); ++i) {
1576  // Only try to remove factors from expressions we're allowed to.
1577  BinaryOperator *BOp =
1578  isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul);
1579  if (!BOp)
1580  continue;
1581 
1582  if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) {
1583  // The factorized operand may occur several times. Convert them all in
1584  // one fell swoop.
1585  for (unsigned j = Ops.size(); j != i;) {
1586  --j;
1587  if (Ops[j].Op == Ops[i].Op) {
1588  NewMulOps.push_back(V);
1589  Ops.erase(Ops.begin()+j);
1590  }
1591  }
1592  --i;
1593  }
1594  }
1595 
1596  // No need for extra uses anymore.
1597  DummyInst->deleteValue();
1598 
1599  unsigned NumAddedValues = NewMulOps.size();
1600  Value *V = EmitAddTreeOfValues(I, NewMulOps);
1601 
1602  // Now that we have inserted the add tree, optimize it. This allows us to
1603  // handle cases that require multiple factoring steps, such as this:
1604  // A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C))
1605  assert(NumAddedValues > 1 && "Each occurrence should contribute a value");
1606  (void)NumAddedValues;
1607  if (Instruction *VI = dyn_cast<Instruction>(V))
1608  RedoInsts.insert(VI);
1609 
1610  // Create the multiply.
1611  Instruction *V2 = CreateMul(V, MaxOccVal, "reass.mul", I, I);
1612 
1613  // Rerun associate on the multiply in case the inner expression turned into
1614  // a multiply. We want to make sure that we keep things in canonical form.
1615  RedoInsts.insert(V2);
1616 
1617  // If every add operand included the factor (e.g. "A*B + A*C"), then the
1618  // entire result expression is just the multiply "A*(B+C)".
1619  if (Ops.empty())
1620  return V2;
1621 
1622  // Otherwise, we had some input that didn't have the factor, such as
1623  // "A*B + A*C + D" -> "A*(B+C) + D". Add the new multiply to the list of
1624  // things being added by this operation.
1625  Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2));
1626  }
1627 
1628  return nullptr;
1629 }
1630 
1631 /// Build up a vector of value/power pairs factoring a product.
1632 ///
1633 /// Given a series of multiplication operands, build a vector of factors and
1634 /// the powers each is raised to when forming the final product. Sort them in
1635 /// the order of descending power.
1636 ///
1637 /// (x*x) -> [(x, 2)]
1638 /// ((x*x)*x) -> [(x, 3)]
1639 /// ((((x*y)*x)*y)*x) -> [(x, 3), (y, 2)]
1640 ///
1641 /// \returns Whether any factors have a power greater than one.
1643  SmallVectorImpl<Factor> &Factors) {
1644  // FIXME: Have Ops be (ValueEntry, Multiplicity) pairs, simplifying this.
1645  // Compute the sum of powers of simplifiable factors.
1646  unsigned FactorPowerSum = 0;
1647  for (unsigned Idx = 1, Size = Ops.size(); Idx < Size; ++Idx) {
1648  Value *Op = Ops[Idx-1].Op;
1649 
1650  // Count the number of occurrences of this value.
1651  unsigned Count = 1;
1652  for (; Idx < Size && Ops[Idx].Op == Op; ++Idx)
1653  ++Count;
1654  // Track for simplification all factors which occur 2 or more times.
1655  if (Count > 1)
1656  FactorPowerSum += Count;
1657  }
1658 
1659  // We can only simplify factors if the sum of the powers of our simplifiable
1660  // factors is 4 or higher. When that is the case, we will *always* have
1661  // a simplification. This is an important invariant to prevent cyclicly
1662  // trying to simplify already minimal formations.
1663  if (FactorPowerSum < 4)
1664  return false;
1665 
1666  // Now gather the simplifiable factors, removing them from Ops.
1667  FactorPowerSum = 0;
1668  for (unsigned Idx = 1; Idx < Ops.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 < Ops.size() && Ops[Idx].Op == Op; ++Idx)
1674  ++Count;
1675  if (Count == 1)
1676  continue;
1677  // Move an even number of occurrences to Factors.
1678  Count &= ~1U;
1679  Idx -= Count;
1680  FactorPowerSum += Count;
1681  Factors.push_back(Factor(Op, Count));
1682  Ops.erase(Ops.begin()+Idx, Ops.begin()+Idx+Count);
1683  }
1684 
1685  // None of the adjustments above should have reduced the sum of factor powers
1686  // below our mininum of '4'.
1687  assert(FactorPowerSum >= 4);
1688 
1689  std::stable_sort(Factors.begin(), Factors.end(),
1690  [](const Factor &LHS, const Factor &RHS) {
1691  return LHS.Power > RHS.Power;
1692  });
1693  return true;
1694 }
1695 
1696 /// Build a tree of multiplies, computing the product of Ops.
1698  SmallVectorImpl<Value*> &Ops) {
1699  if (Ops.size() == 1)
1700  return Ops.back();
1701 
1702  Value *LHS = Ops.pop_back_val();
1703  do {
1704  if (LHS->getType()->isIntOrIntVectorTy())
1705  LHS = Builder.CreateMul(LHS, Ops.pop_back_val());
1706  else
1707  LHS = Builder.CreateFMul(LHS, Ops.pop_back_val());
1708  } while (!Ops.empty());
1709 
1710  return LHS;
1711 }
1712 
1713 /// Build a minimal multiplication DAG for (a^x)*(b^y)*(c^z)*...
1714 ///
1715 /// Given a vector of values raised to various powers, where no two values are
1716 /// equal and the powers are sorted in decreasing order, compute the minimal
1717 /// DAG of multiplies to compute the final product, and return that product
1718 /// value.
1719 Value *
1720 ReassociatePass::buildMinimalMultiplyDAG(IRBuilder<> &Builder,
1721  SmallVectorImpl<Factor> &Factors) {
1722  assert(Factors[0].Power);
1723  SmallVector<Value *, 4> OuterProduct;
1724  for (unsigned LastIdx = 0, Idx = 1, Size = Factors.size();
1725  Idx < Size && Factors[Idx].Power > 0; ++Idx) {
1726  if (Factors[Idx].Power != Factors[LastIdx].Power) {
1727  LastIdx = Idx;
1728  continue;
1729  }
1730 
1731  // We want to multiply across all the factors with the same power so that
1732  // we can raise them to that power as a single entity. Build a mini tree
1733  // for that.
1734  SmallVector<Value *, 4> InnerProduct;
1735  InnerProduct.push_back(Factors[LastIdx].Base);
1736  do {
1737  InnerProduct.push_back(Factors[Idx].Base);
1738  ++Idx;
1739  } while (Idx < Size && Factors[Idx].Power == Factors[LastIdx].Power);
1740 
1741  // Reset the base value of the first factor to the new expression tree.
1742  // We'll remove all the factors with the same power in a second pass.
1743  Value *M = Factors[LastIdx].Base = buildMultiplyTree(Builder, InnerProduct);
1744  if (Instruction *MI = dyn_cast<Instruction>(M))
1745  RedoInsts.insert(MI);
1746 
1747  LastIdx = Idx;
1748  }
1749  // Unique factors with equal powers -- we've folded them into the first one's
1750  // base.
1751  Factors.erase(std::unique(Factors.begin(), Factors.end(),
1752  [](const Factor &LHS, const Factor &RHS) {
1753  return LHS.Power == RHS.Power;
1754  }),
1755  Factors.end());
1756 
1757  // Iteratively collect the base of each factor with an add power into the
1758  // outer product, and halve each power in preparation for squaring the
1759  // expression.
1760  for (unsigned Idx = 0, Size = Factors.size(); Idx != Size; ++Idx) {
1761  if (Factors[Idx].Power & 1)
1762  OuterProduct.push_back(Factors[Idx].Base);
1763  Factors[Idx].Power >>= 1;
1764  }
1765  if (Factors[0].Power) {
1766  Value *SquareRoot = buildMinimalMultiplyDAG(Builder, Factors);
1767  OuterProduct.push_back(SquareRoot);
1768  OuterProduct.push_back(SquareRoot);
1769  }
1770  if (OuterProduct.size() == 1)
1771  return OuterProduct.front();
1772 
1773  Value *V = buildMultiplyTree(Builder, OuterProduct);
1774  return V;
1775 }
1776 
1777 Value *ReassociatePass::OptimizeMul(BinaryOperator *I,
1779  // We can only optimize the multiplies when there is a chain of more than
1780  // three, such that a balanced tree might require fewer total multiplies.
1781  if (Ops.size() < 4)
1782  return nullptr;
1783 
1784  // Try to turn linear trees of multiplies without other uses of the
1785  // intermediate stages into minimal multiply DAGs with perfect sub-expression
1786  // re-use.
1787  SmallVector<Factor, 4> Factors;
1788  if (!collectMultiplyFactors(Ops, Factors))
1789  return nullptr; // All distinct factors, so nothing left for us to do.
1790 
1791  IRBuilder<> Builder(I);
1792  // The reassociate transformation for FP operations is performed only
1793  // if unsafe algebra is permitted by FastMathFlags. Propagate those flags
1794  // to the newly generated operations.
1795  if (auto FPI = dyn_cast<FPMathOperator>(I))
1796  Builder.setFastMathFlags(FPI->getFastMathFlags());
1797 
1798  Value *V = buildMinimalMultiplyDAG(Builder, Factors);
1799  if (Ops.empty())
1800  return V;
1801 
1802  ValueEntry NewEntry = ValueEntry(getRank(V), V);
1803  Ops.insert(std::lower_bound(Ops.begin(), Ops.end(), NewEntry), NewEntry);
1804  return nullptr;
1805 }
1806 
1807 Value *ReassociatePass::OptimizeExpression(BinaryOperator *I,
1809  // Now that we have the linearized expression tree, try to optimize it.
1810  // Start by folding any constants that we found.
1811  Constant *Cst = nullptr;
1812  unsigned Opcode = I->getOpcode();
1813  while (!Ops.empty() && isa<Constant>(Ops.back().Op)) {
1814  Constant *C = cast<Constant>(Ops.pop_back_val().Op);
1815  Cst = Cst ? ConstantExpr::get(Opcode, C, Cst) : C;
1816  }
1817  // If there was nothing but constants then we are done.
1818  if (Ops.empty())
1819  return Cst;
1820 
1821  // Put the combined constant back at the end of the operand list, except if
1822  // there is no point. For example, an add of 0 gets dropped here, while a
1823  // multiplication by zero turns the whole expression into zero.
1824  if (Cst && Cst != ConstantExpr::getBinOpIdentity(Opcode, I->getType())) {
1825  if (Cst == ConstantExpr::getBinOpAbsorber(Opcode, I->getType()))
1826  return Cst;
1827  Ops.push_back(ValueEntry(0, Cst));
1828  }
1829 
1830  if (Ops.size() == 1) return Ops[0].Op;
1831 
1832  // Handle destructive annihilation due to identities between elements in the
1833  // argument list here.
1834  unsigned NumOps = Ops.size();
1835  switch (Opcode) {
1836  default: break;
1837  case Instruction::And:
1838  case Instruction::Or:
1839  if (Value *Result = OptimizeAndOrXor(Opcode, Ops))
1840  return Result;
1841  break;
1842 
1843  case Instruction::Xor:
1844  if (Value *Result = OptimizeXor(I, Ops))
1845  return Result;
1846  break;
1847 
1848  case Instruction::Add:
1849  case Instruction::FAdd:
1850  if (Value *Result = OptimizeAdd(I, Ops))
1851  return Result;
1852  break;
1853 
1854  case Instruction::Mul:
1855  case Instruction::FMul:
1856  if (Value *Result = OptimizeMul(I, Ops))
1857  return Result;
1858  break;
1859  }
1860 
1861  if (Ops.size() != NumOps)
1862  return OptimizeExpression(I, Ops);
1863  return nullptr;
1864 }
1865 
1866 // Remove dead instructions and if any operands are trivially dead add them to
1867 // Insts so they will be removed as well.
1868 void ReassociatePass::RecursivelyEraseDeadInsts(Instruction *I,
1869  OrderedSet &Insts) {
1870  assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
1871  SmallVector<Value *, 4> Ops(I->op_begin(), I->op_end());
1872  ValueRankMap.erase(I);
1873  Insts.remove(I);
1874  RedoInsts.remove(I);
1875  I->eraseFromParent();
1876  for (auto Op : Ops)
1877  if (Instruction *OpInst = dyn_cast<Instruction>(Op))
1878  if (OpInst->use_empty())
1879  Insts.insert(OpInst);
1880 }
1881 
1882 /// Zap the given instruction, adding interesting operands to the work list.
1883 void ReassociatePass::EraseInst(Instruction *I) {
1884  assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!");
1885  LLVM_DEBUG(dbgs() << "Erasing dead inst: "; I->dump());
1886 
1887  SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
1888  // Erase the dead instruction.
1889  ValueRankMap.erase(I);
1890  RedoInsts.remove(I);
1891  I->eraseFromParent();
1892  // Optimize its operands.
1893  SmallPtrSet<Instruction *, 8> Visited; // Detect self-referential nodes.
1894  for (unsigned i = 0, e = Ops.size(); i != e; ++i)
1895  if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
1896  // If this is a node in an expression tree, climb to the expression root
1897  // and add that since that's where optimization actually happens.
1898  unsigned Opcode = Op->getOpcode();
1899  while (Op->hasOneUse() && Op->user_back()->getOpcode() == Opcode &&
1900  Visited.insert(Op).second)
1901  Op = Op->user_back();
1902 
1903  // The instruction we're going to push may be coming from a
1904  // dead block, and Reassociate skips the processing of unreachable
1905  // blocks because it's a waste of time and also because it can
1906  // lead to infinite loop due to LLVM's non-standard definition
1907  // of dominance.
1908  if (ValueRankMap.find(Op) != ValueRankMap.end())
1909  RedoInsts.insert(Op);
1910  }
1911 
1912  MadeChange = true;
1913 }
1914 
1915 // Canonicalize expressions of the following form:
1916 // x + (-Constant * y) -> x - (Constant * y)
1917 // x - (-Constant * y) -> x + (Constant * y)
1918 Instruction *ReassociatePass::canonicalizeNegConstExpr(Instruction *I) {
1919  if (!I->hasOneUse() || I->getType()->isVectorTy())
1920  return nullptr;
1921 
1922  // Must be a fmul or fdiv instruction.
1923  unsigned Opcode = I->getOpcode();
1924  if (Opcode != Instruction::FMul && Opcode != Instruction::FDiv)
1925  return nullptr;
1926 
1927  auto *C0 = dyn_cast<ConstantFP>(I->getOperand(0));
1928  auto *C1 = dyn_cast<ConstantFP>(I->getOperand(1));
1929 
1930  // Both operands are constant, let it get constant folded away.
1931  if (C0 && C1)
1932  return nullptr;
1933 
1934  ConstantFP *CF = C0 ? C0 : C1;
1935 
1936  // Must have one constant operand.
1937  if (!CF)
1938  return nullptr;
1939 
1940  // Must be a negative ConstantFP.
1941  if (!CF->isNegative())
1942  return nullptr;
1943 
1944  // User must be a binary operator with one or more uses.
1945  Instruction *User = I->user_back();
1946  if (!isa<BinaryOperator>(User) || User->use_empty())
1947  return nullptr;
1948 
1949  unsigned UserOpcode = User->getOpcode();
1950  if (UserOpcode != Instruction::FAdd && UserOpcode != Instruction::FSub)
1951  return nullptr;
1952 
1953  // Subtraction is not commutative. Explicitly, the following transform is
1954  // not valid: (-Constant * y) - x -> x + (Constant * y)
1955  if (!User->isCommutative() && User->getOperand(1) != I)
1956  return nullptr;
1957 
1958  // Don't canonicalize x + (-Constant * y) -> x - (Constant * y), if the
1959  // resulting subtract will be broken up later. This can get us into an
1960  // infinite loop during reassociation.
1961  if (UserOpcode == Instruction::FAdd && ShouldBreakUpSubtract(User))
1962  return nullptr;
1963 
1964  // Change the sign of the constant.
1965  APFloat Val = CF->getValueAPF();
1966  Val.changeSign();
1967  I->setOperand(C0 ? 0 : 1, ConstantFP::get(CF->getContext(), Val));
1968 
1969  // Canonicalize I to RHS to simplify the next bit of logic. E.g.,
1970  // ((-Const*y) + x) -> (x + (-Const*y)).
1971  if (User->getOperand(0) == I && User->isCommutative())
1972  cast<BinaryOperator>(User)->swapOperands();
1973 
1974  Value *Op0 = User->getOperand(0);
1975  Value *Op1 = User->getOperand(1);
1976  BinaryOperator *NI;
1977  switch (UserOpcode) {
1978  default:
1979  llvm_unreachable("Unexpected Opcode!");
1980  case Instruction::FAdd:
1981  NI = BinaryOperator::CreateFSub(Op0, Op1);
1982  NI->setFastMathFlags(cast<FPMathOperator>(User)->getFastMathFlags());
1983  break;
1984  case Instruction::FSub:
1985  NI = BinaryOperator::CreateFAdd(Op0, Op1);
1986  NI->setFastMathFlags(cast<FPMathOperator>(User)->getFastMathFlags());
1987  break;
1988  }
1989 
1990  NI->insertBefore(User);
1991  NI->setName(User->getName());
1992  User->replaceAllUsesWith(NI);
1993  NI->setDebugLoc(I->getDebugLoc());
1994  RedoInsts.insert(I);
1995  MadeChange = true;
1996  return NI;
1997 }
1998 
1999 /// Inspect and optimize the given instruction. Note that erasing
2000 /// instructions is not allowed.
2001 void ReassociatePass::OptimizeInst(Instruction *I) {
2002  // Only consider operations that we understand.
2003  if (!isa<BinaryOperator>(I))
2004  return;
2005 
2006  if (I->getOpcode() == Instruction::Shl && isa<ConstantInt>(I->getOperand(1)))
2007  // If an operand of this shift is a reassociable multiply, or if the shift
2008  // is used by a reassociable multiply or add, turn into a multiply.
2009  if (isReassociableOp(I->getOperand(0), Instruction::Mul) ||
2010  (I->hasOneUse() &&
2011  (isReassociableOp(I->user_back(), Instruction::Mul) ||
2013  Instruction *NI = ConvertShiftToMul(I);
2014  RedoInsts.insert(I);
2015  MadeChange = true;
2016  I = NI;
2017  }
2018 
2019  // Canonicalize negative constants out of expressions.
2020  if (Instruction *Res = canonicalizeNegConstExpr(I))
2021  I = Res;
2022 
2023  // Commute binary operators, to canonicalize the order of their operands.
2024  // This can potentially expose more CSE opportunities, and makes writing other
2025  // transformations simpler.
2026  if (I->isCommutative())
2027  canonicalizeOperands(I);
2028 
2029  // Don't optimize floating-point instructions unless they are 'fast'.
2030  if (I->getType()->isFPOrFPVectorTy() && !I->isFast())
2031  return;
2032 
2033  // Do not reassociate boolean (i1) expressions. We want to preserve the
2034  // original order of evaluation for short-circuited comparisons that
2035  // SimplifyCFG has folded to AND/OR expressions. If the expression
2036  // is not further optimized, it is likely to be transformed back to a
2037  // short-circuited form for code gen, and the source order may have been
2038  // optimized for the most likely conditions.
2039  if (I->getType()->isIntegerTy(1))
2040  return;
2041 
2042  // If this is a subtract instruction which is not already in negate form,
2043  // see if we can convert it to X+-Y.
2044  if (I->getOpcode() == Instruction::Sub) {
2045  if (ShouldBreakUpSubtract(I)) {
2046  Instruction *NI = BreakUpSubtract(I, RedoInsts);
2047  RedoInsts.insert(I);
2048  MadeChange = true;
2049  I = NI;
2050  } else if (match(I, m_Neg(m_Value()))) {
2051  // Otherwise, this is a negation. See if the operand is a multiply tree
2052  // and if this is not an inner node of a multiply tree.
2053  if (isReassociableOp(I->getOperand(1), Instruction::Mul) &&
2054  (!I->hasOneUse() ||
2055  !isReassociableOp(I->user_back(), Instruction::Mul))) {
2057  // If the negate was simplified, revisit the users to see if we can
2058  // reassociate further.
2059  for (User *U : NI->users()) {
2060  if (BinaryOperator *Tmp = dyn_cast<BinaryOperator>(U))
2061  RedoInsts.insert(Tmp);
2062  }
2063  RedoInsts.insert(I);
2064  MadeChange = true;
2065  I = NI;
2066  }
2067  }
2068  } else if (I->getOpcode() == Instruction::FSub) {
2069  if (ShouldBreakUpSubtract(I)) {
2070  Instruction *NI = BreakUpSubtract(I, RedoInsts);
2071  RedoInsts.insert(I);
2072  MadeChange = true;
2073  I = NI;
2074  } else if (match(I, m_FNeg(m_Value()))) {
2075  // Otherwise, this is a negation. See if the operand is a multiply tree
2076  // and if this is not an inner node of a multiply tree.
2077  if (isReassociableOp(I->getOperand(1), Instruction::FMul) &&
2078  (!I->hasOneUse() ||
2079  !isReassociableOp(I->user_back(), Instruction::FMul))) {
2080  // If the negate was simplified, revisit the users to see if we can
2081  // reassociate further.
2083  for (User *U : NI->users()) {
2084  if (BinaryOperator *Tmp = dyn_cast<BinaryOperator>(U))
2085  RedoInsts.insert(Tmp);
2086  }
2087  RedoInsts.insert(I);
2088  MadeChange = true;
2089  I = NI;
2090  }
2091  }
2092  }
2093 
2094  // If this instruction is an associative binary operator, process it.
2095  if (!I->isAssociative()) return;
2096  BinaryOperator *BO = cast<BinaryOperator>(I);
2097 
2098  // If this is an interior node of a reassociable tree, ignore it until we
2099  // get to the root of the tree, to avoid N^2 analysis.
2100  unsigned Opcode = BO->getOpcode();
2101  if (BO->hasOneUse() && BO->user_back()->getOpcode() == Opcode) {
2102  // During the initial run we will get to the root of the tree.
2103  // But if we get here while we are redoing instructions, there is no
2104  // guarantee that the root will be visited. So Redo later
2105  if (BO->user_back() != BO &&
2106  BO->getParent() == BO->user_back()->getParent())
2107  RedoInsts.insert(BO->user_back());
2108  return;
2109  }
2110 
2111  // If this is an add tree that is used by a sub instruction, ignore it
2112  // until we process the subtract.
2113  if (BO->hasOneUse() && BO->getOpcode() == Instruction::Add &&
2114  cast<Instruction>(BO->user_back())->getOpcode() == Instruction::Sub)
2115  return;
2116  if (BO->hasOneUse() && BO->getOpcode() == Instruction::FAdd &&
2117  cast<Instruction>(BO->user_back())->getOpcode() == Instruction::FSub)
2118  return;
2119 
2120  ReassociateExpression(BO);
2121 }
2122 
2123 void ReassociatePass::ReassociateExpression(BinaryOperator *I) {
2124  // First, walk the expression tree, linearizing the tree, collecting the
2125  // operand information.
2127  MadeChange |= LinearizeExprTree(I, Tree);
2129  Ops.reserve(Tree.size());
2130  for (unsigned i = 0, e = Tree.size(); i != e; ++i) {
2131  RepeatedValue E = Tree[i];
2132  Ops.append(E.second.getZExtValue(),
2133  ValueEntry(getRank(E.first), E.first));
2134  }
2135 
2136  LLVM_DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n');
2137 
2138  // Now that we have linearized the tree to a list and have gathered all of
2139  // the operands and their ranks, sort the operands by their rank. Use a
2140  // stable_sort so that values with equal ranks will have their relative
2141  // positions maintained (and so the compiler is deterministic). Note that
2142  // this sorts so that the highest ranking values end up at the beginning of
2143  // the vector.
2144  std::stable_sort(Ops.begin(), Ops.end());
2145 
2146  // Now that we have the expression tree in a convenient
2147  // sorted form, optimize it globally if possible.
2148  if (Value *V = OptimizeExpression(I, Ops)) {
2149  if (V == I)
2150  // Self-referential expression in unreachable code.
2151  return;
2152  // This expression tree simplified to something that isn't a tree,
2153  // eliminate it.
2154  LLVM_DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n');
2155  I->replaceAllUsesWith(V);
2156  if (Instruction *VI = dyn_cast<Instruction>(V))
2157  if (I->getDebugLoc())
2158  VI->setDebugLoc(I->getDebugLoc());
2159  RedoInsts.insert(I);
2160  ++NumAnnihil;
2161  return;
2162  }
2163 
2164  // We want to sink immediates as deeply as possible except in the case where
2165  // this is a multiply tree used only by an add, and the immediate is a -1.
2166  // In this case we reassociate to put the negation on the outside so that we
2167  // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y
2168  if (I->hasOneUse()) {
2169  if (I->getOpcode() == Instruction::Mul &&
2170  cast<Instruction>(I->user_back())->getOpcode() == Instruction::Add &&
2171  isa<ConstantInt>(Ops.back().Op) &&
2172  cast<ConstantInt>(Ops.back().Op)->isMinusOne()) {
2173  ValueEntry Tmp = Ops.pop_back_val();
2174  Ops.insert(Ops.begin(), Tmp);
2175  } else if (I->getOpcode() == Instruction::FMul &&
2176  cast<Instruction>(I->user_back())->getOpcode() ==
2177  Instruction::FAdd &&
2178  isa<ConstantFP>(Ops.back().Op) &&
2179  cast<ConstantFP>(Ops.back().Op)->isExactlyValue(-1.0)) {
2180  ValueEntry Tmp = Ops.pop_back_val();
2181  Ops.insert(Ops.begin(), Tmp);
2182  }
2183  }
2184 
2185  LLVM_DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n');
2186 
2187  if (Ops.size() == 1) {
2188  if (Ops[0].Op == I)
2189  // Self-referential expression in unreachable code.
2190  return;
2191 
2192  // This expression tree simplified to something that isn't a tree,
2193  // eliminate it.
2194  I->replaceAllUsesWith(Ops[0].Op);
2195  if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op))
2196  OI->setDebugLoc(I->getDebugLoc());
2197  RedoInsts.insert(I);
2198  return;
2199  }
2200 
2201  if (Ops.size() > 2 && Ops.size() <= GlobalReassociateLimit) {
2202  // Find the pair with the highest count in the pairmap and move it to the
2203  // back of the list so that it can later be CSE'd.
2204  // example:
2205  // a*b*c*d*e
2206  // if c*e is the most "popular" pair, we can express this as
2207  // (((c*e)*d)*b)*a
2208  unsigned Max = 1;
2209  unsigned BestRank = 0;
2210  std::pair<unsigned, unsigned> BestPair;
2211  unsigned Idx = I->getOpcode() - Instruction::BinaryOpsBegin;
2212  for (unsigned i = 0; i < Ops.size() - 1; ++i)
2213  for (unsigned j = i + 1; j < Ops.size(); ++j) {
2214  unsigned Score = 0;
2215  Value *Op0 = Ops[i].Op;
2216  Value *Op1 = Ops[j].Op;
2217  if (std::less<Value *>()(Op1, Op0))
2218  std::swap(Op0, Op1);
2219  auto it = PairMap[Idx].find({Op0, Op1});
2220  if (it != PairMap[Idx].end())
2221  Score += it->second;
2222 
2223  unsigned MaxRank = std::max(Ops[i].Rank, Ops[j].Rank);
2224  if (Score > Max || (Score == Max && MaxRank < BestRank)) {
2225  BestPair = {i, j};
2226  Max = Score;
2227  BestRank = MaxRank;
2228  }
2229  }
2230  if (Max > 1) {
2231  auto Op0 = Ops[BestPair.first];
2232  auto Op1 = Ops[BestPair.second];
2233  Ops.erase(&Ops[BestPair.second]);
2234  Ops.erase(&Ops[BestPair.first]);
2235  Ops.push_back(Op0);
2236  Ops.push_back(Op1);
2237  }
2238  }
2239  // Now that we ordered and optimized the expressions, splat them back into
2240  // the expression tree, removing any unneeded nodes.
2241  RewriteExprTree(I, Ops);
2242 }
2243 
2244 void
2245 ReassociatePass::BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT) {
2246  // Make a "pairmap" of how often each operand pair occurs.
2247  for (BasicBlock *BI : RPOT) {
2248  for (Instruction &I : *BI) {
2249  if (!I.isAssociative())
2250  continue;
2251 
2252  // Ignore nodes that aren't at the root of trees.
2253  if (I.hasOneUse() && I.user_back()->getOpcode() == I.getOpcode())
2254  continue;
2255 
2256  // Collect all operands in a single reassociable expression.
2257  // Since Reassociate has already been run once, we can assume things
2258  // are already canonical according to Reassociation's regime.
2259  SmallVector<Value *, 8> Worklist = { I.getOperand(0), I.getOperand(1) };
2261  while (!Worklist.empty() && Ops.size() <= GlobalReassociateLimit) {
2262  Value *Op = Worklist.pop_back_val();
2264  if (!OpI || OpI->getOpcode() != I.getOpcode() || !OpI->hasOneUse()) {
2265  Ops.push_back(Op);
2266  continue;
2267  }
2268  // Be paranoid about self-referencing expressions in unreachable code.
2269  if (OpI->getOperand(0) != OpI)
2270  Worklist.push_back(OpI->getOperand(0));
2271  if (OpI->getOperand(1) != OpI)
2272  Worklist.push_back(OpI->getOperand(1));
2273  }
2274  // Skip extremely long expressions.
2275  if (Ops.size() > GlobalReassociateLimit)
2276  continue;
2277 
2278  // Add all pairwise combinations of operands to the pair map.
2279  unsigned BinaryIdx = I.getOpcode() - Instruction::BinaryOpsBegin;
2281  for (unsigned i = 0; i < Ops.size() - 1; ++i) {
2282  for (unsigned j = i + 1; j < Ops.size(); ++j) {
2283  // Canonicalize operand orderings.
2284  Value *Op0 = Ops[i];
2285  Value *Op1 = Ops[j];
2286  if (std::less<Value *>()(Op1, Op0))
2287  std::swap(Op0, Op1);
2288  if (!Visited.insert({Op0, Op1}).second)
2289  continue;
2290  auto res = PairMap[BinaryIdx].insert({{Op0, Op1}, 1});
2291  if (!res.second)
2292  ++res.first->second;
2293  }
2294  }
2295  }
2296  }
2297 }
2298 
2300  // Get the functions basic blocks in Reverse Post Order. This order is used by
2301  // BuildRankMap to pre calculate ranks correctly. It also excludes dead basic
2302  // blocks (it has been seen that the analysis in this pass could hang when
2303  // analysing dead basic blocks).
2305 
2306  // Calculate the rank map for F.
2307  BuildRankMap(F, RPOT);
2308 
2309  // Build the pair map before running reassociate.
2310  // Technically this would be more accurate if we did it after one round
2311  // of reassociation, but in practice it doesn't seem to help much on
2312  // real-world code, so don't waste the compile time running reassociate
2313  // twice.
2314  // If a user wants, they could expicitly run reassociate twice in their
2315  // pass pipeline for further potential gains.
2316  // It might also be possible to update the pair map during runtime, but the
2317  // overhead of that may be large if there's many reassociable chains.
2318  BuildPairMap(RPOT);
2319 
2320  MadeChange = false;
2321 
2322  // Traverse the same blocks that were analysed by BuildRankMap.
2323  for (BasicBlock *BI : RPOT) {
2324  assert(RankMap.count(&*BI) && "BB should be ranked.");
2325  // Optimize every instruction in the basic block.
2326  for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;)
2327  if (isInstructionTriviallyDead(&*II)) {
2328  EraseInst(&*II++);
2329  } else {
2330  OptimizeInst(&*II);
2331  assert(II->getParent() == &*BI && "Moved to a different block!");
2332  ++II;
2333  }
2334 
2335  // Make a copy of all the instructions to be redone so we can remove dead
2336  // instructions.
2337  OrderedSet ToRedo(RedoInsts);
2338  // Iterate over all instructions to be reevaluated and remove trivially dead
2339  // instructions. If any operand of the trivially dead instruction becomes
2340  // dead mark it for deletion as well. Continue this process until all
2341  // trivially dead instructions have been removed.
2342  while (!ToRedo.empty()) {
2343  Instruction *I = ToRedo.pop_back_val();
2344  if (isInstructionTriviallyDead(I)) {
2345  RecursivelyEraseDeadInsts(I, ToRedo);
2346  MadeChange = true;
2347  }
2348  }
2349 
2350  // Now that we have removed dead instructions, we can reoptimize the
2351  // remaining instructions.
2352  while (!RedoInsts.empty()) {
2353  Instruction *I = RedoInsts.front();
2354  RedoInsts.erase(RedoInsts.begin());
2356  EraseInst(I);
2357  else
2358  OptimizeInst(I);
2359  }
2360  }
2361 
2362  // We are done with the rank map and pair map.
2363  RankMap.clear();
2364  ValueRankMap.clear();
2365  for (auto &Entry : PairMap)
2366  Entry.clear();
2367 
2368  if (MadeChange) {
2369  PreservedAnalyses PA;
2370  PA.preserveSet<CFGAnalyses>();
2371  PA.preserve<GlobalsAA>();
2372  return PA;
2373  }
2374 
2375  return PreservedAnalyses::all();
2376 }
2377 
2378 namespace {
2379 
2380  class ReassociateLegacyPass : public FunctionPass {
2381  ReassociatePass Impl;
2382 
2383  public:
2384  static char ID; // Pass identification, replacement for typeid
2385 
2386  ReassociateLegacyPass() : FunctionPass(ID) {
2388  }
2389 
2390  bool runOnFunction(Function &F) override {
2391  if (skipFunction(F))
2392  return false;
2393 
2394  FunctionAnalysisManager DummyFAM;
2395  auto PA = Impl.run(F, DummyFAM);
2396  return !PA.areAllPreserved();
2397  }
2398 
2399  void getAnalysisUsage(AnalysisUsage &AU) const override {
2400  AU.setPreservesCFG();
2402  }
2403  };
2404 
2405 } // end anonymous namespace
2406 
2407 char ReassociateLegacyPass::ID = 0;
2408 
2409 INITIALIZE_PASS(ReassociateLegacyPass, "reassociate",
2410  "Reassociate expressions", false, false)
2411 
2412 // Public interface to the Reassociate pass
2414  return new ReassociateLegacyPass();
2415 }
Legacy wrapper pass to provide the GlobalsAAResult object.
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:258
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:315
INITIALIZE_PASS(ReassociateLegacyPass, "reassociate", "Reassociate expressions", false, false) FunctionPass *llvm
This is the interface for a simple mod/ref and alias analysis over globals.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
bool isIdempotent() const
Return true if the instruction is idempotent:
Definition: Instruction.h:495
void push_back(const T &Elt)
Definition: SmallVector.h:217
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:704
void deleteValue()
Delete a pointer to a generic Value.
Definition: Value.cpp:97
bool replaceDbgUsesWithUndef(Instruction *I)
Replace all the uses of an SSA value in .dbg intrinsics with undef.
Definition: Local.cpp:478
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:375
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:264
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:4297
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
amdgpu Simplify well known AMD library false Value Value const Twine & Name
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
bool isNilpotent() const
Return true if the instruction is nilpotent:
Definition: Instruction.h:509
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:284
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
auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1281
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:428
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:290
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:639
static bool runOnFunction(Function &F, bool PostInlining)
#define P(N)
static Constant * getFNeg(Constant *C)
Definition: Constants.cpp:2225
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:1246
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:307
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
Definition: PassManager.h:321
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp: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
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:128
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:2325
Value * getSymbolicPart() const
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
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:318
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:1414
iterator erase(const_iterator CI)
Definition: SmallVector.h:444
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:1047
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
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:846
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:380
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
void setSymbolicRank(unsigned R)
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:285
static Constant * get(Type *Ty, double V)
This returns a ConstantFP, or a vector containing a splat of a ConstantFP, for the specified value in...
Definition: Constants.cpp:684
bool isCommutative() const
Return true if the instruction is commutative:
Definition: Instruction.h:477
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:477
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:393
amdgpu Simplify well known AMD library false Value Value * Arg
static void FindSingleUseMultiplyFactors(Value *V, SmallVectorImpl< Value *> &Factors)
If V is a single-use multiply, recursively add its operands as factors, otherwise add V to the list o...
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2218
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:132
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match &#39;fneg X&#39; as &#39;fsub -0.0, X&#39;.
Definition: PatternMatch.h:688
iterator insert(iterator where, pointer New)
Definition: ilist.h:227
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:310
bool mayBeMemoryDependent(const Instruction &I)
Returns true if the result or effects of the given instructions I depend on or influence global memor...
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:651
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:213
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:322
uint32_t Size
Definition: Profile.cpp:46
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2308
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 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:348
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:2371
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:688
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:1805
PreservedAnalyses run(Function &F, FunctionAnalysisManager &)