Coverage Report

Created: 2019-07-24 05:18

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