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