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