aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp')
-rw-r--r--contrib/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp293
1 files changed, 105 insertions, 188 deletions
diff --git a/contrib/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp b/contrib/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp
index 818c7b40d489..e742d2ed12af 100644
--- a/contrib/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp
+++ b/contrib/llvm-project/llvm/lib/Transforms/Scalar/Reassociate.cpp
@@ -246,7 +246,8 @@ void ReassociatePass::canonicalizeOperands(Instruction *I) {
}
static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name,
- Instruction *InsertBefore, Value *FlagsOp) {
+ BasicBlock::iterator InsertBefore,
+ Value *FlagsOp) {
if (S1->getType()->isIntOrIntVectorTy())
return BinaryOperator::CreateAdd(S1, S2, Name, InsertBefore);
else {
@@ -258,7 +259,8 @@ static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name,
}
static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name,
- Instruction *InsertBefore, Value *FlagsOp) {
+ BasicBlock::iterator InsertBefore,
+ Value *FlagsOp) {
if (S1->getType()->isIntOrIntVectorTy())
return BinaryOperator::CreateMul(S1, S2, Name, InsertBefore);
else {
@@ -270,7 +272,8 @@ static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name,
}
static Instruction *CreateNeg(Value *S1, const Twine &Name,
- Instruction *InsertBefore, Value *FlagsOp) {
+ BasicBlock::iterator InsertBefore,
+ Value *FlagsOp) {
if (S1->getType()->isIntOrIntVectorTy())
return BinaryOperator::CreateNeg(S1, Name, InsertBefore);
@@ -290,7 +293,8 @@ static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) {
Constant *NegOne = Ty->isIntOrIntVectorTy() ?
ConstantInt::getAllOnesValue(Ty) : ConstantFP::get(Ty, -1.0);
- BinaryOperator *Res = CreateMul(Neg->getOperand(OpNo), NegOne, "", Neg, Neg);
+ BinaryOperator *Res =
+ CreateMul(Neg->getOperand(OpNo), NegOne, "", Neg->getIterator(), Neg);
Neg->setOperand(OpNo, Constant::getNullValue(Ty)); // Drop use of op.
Res->takeName(Neg);
Neg->replaceAllUsesWith(Res);
@@ -298,98 +302,7 @@ static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) {
return Res;
}
-/// Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael
-/// function. This means that x^(2^k) === 1 mod 2^Bitwidth for
-/// every odd x, i.e. x^(2^k) = 1 for every odd x in Bitwidth-bit arithmetic.
-/// Note that 0 <= k < Bitwidth, and if Bitwidth > 3 then x^(2^k) = 0 for every
-/// even x in Bitwidth-bit arithmetic.
-static unsigned CarmichaelShift(unsigned Bitwidth) {
- if (Bitwidth < 3)
- return Bitwidth - 1;
- return Bitwidth - 2;
-}
-
-/// Add the extra weight 'RHS' to the existing weight 'LHS',
-/// reducing the combined weight using any special properties of the operation.
-/// The existing weight LHS represents the computation X op X op ... op X where
-/// X occurs LHS times. The combined weight represents X op X op ... op X with
-/// X occurring LHS + RHS times. If op is "Xor" for example then the combined
-/// operation is equivalent to X if LHS + RHS is odd, or 0 if LHS + RHS is even;
-/// the routine returns 1 in LHS in the first case, and 0 in LHS in the second.
-static void IncorporateWeight(APInt &LHS, const APInt &RHS, unsigned Opcode) {
- // If we were working with infinite precision arithmetic then the combined
- // weight would be LHS + RHS. But we are using finite precision arithmetic,
- // and the APInt sum LHS + RHS may not be correct if it wraps (it is correct
- // for nilpotent operations and addition, but not for idempotent operations
- // and multiplication), so it is important to correctly reduce the combined
- // weight back into range if wrapping would be wrong.
-
- // If RHS is zero then the weight didn't change.
- if (RHS.isMinValue())
- return;
- // If LHS is zero then the combined weight is RHS.
- if (LHS.isMinValue()) {
- LHS = RHS;
- return;
- }
- // From this point on we know that neither LHS nor RHS is zero.
-
- if (Instruction::isIdempotent(Opcode)) {
- // Idempotent means X op X === X, so any non-zero weight is equivalent to a
- // weight of 1. Keeping weights at zero or one also means that wrapping is
- // not a problem.
- assert(LHS == 1 && RHS == 1 && "Weights not reduced!");
- return; // Return a weight of 1.
- }
- if (Instruction::isNilpotent(Opcode)) {
- // Nilpotent means X op X === 0, so reduce weights modulo 2.
- assert(LHS == 1 && RHS == 1 && "Weights not reduced!");
- LHS = 0; // 1 + 1 === 0 modulo 2.
- return;
- }
- if (Opcode == Instruction::Add || Opcode == Instruction::FAdd) {
- // TODO: Reduce the weight by exploiting nsw/nuw?
- LHS += RHS;
- return;
- }
-
- assert((Opcode == Instruction::Mul || Opcode == Instruction::FMul) &&
- "Unknown associative operation!");
- unsigned Bitwidth = LHS.getBitWidth();
- // If CM is the Carmichael number then a weight W satisfying W >= CM+Bitwidth
- // can be replaced with W-CM. That's because x^W=x^(W-CM) for every Bitwidth
- // bit number x, since either x is odd in which case x^CM = 1, or x is even in
- // which case both x^W and x^(W - CM) are zero. By subtracting off multiples
- // of CM like this weights can always be reduced to the range [0, CM+Bitwidth)
- // which by a happy accident means that they can always be represented using
- // Bitwidth bits.
- // TODO: Reduce the weight by exploiting nsw/nuw? (Could do much better than
- // the Carmichael number).
- if (Bitwidth > 3) {
- /// CM - The value of Carmichael's lambda function.
- APInt CM = APInt::getOneBitSet(Bitwidth, CarmichaelShift(Bitwidth));
- // Any weight W >= Threshold can be replaced with W - CM.
- APInt Threshold = CM + Bitwidth;
- assert(LHS.ult(Threshold) && RHS.ult(Threshold) && "Weights not reduced!");
- // For Bitwidth 4 or more the following sum does not overflow.
- LHS += RHS;
- while (LHS.uge(Threshold))
- LHS -= CM;
- } else {
- // To avoid problems with overflow do everything the same as above but using
- // a larger type.
- unsigned CM = 1U << CarmichaelShift(Bitwidth);
- unsigned Threshold = CM + Bitwidth;
- assert(LHS.getZExtValue() < Threshold && RHS.getZExtValue() < Threshold &&
- "Weights not reduced!");
- unsigned Total = LHS.getZExtValue() + RHS.getZExtValue();
- while (Total >= Threshold)
- Total -= CM;
- LHS = Total;
- }
-}
-
-using RepeatedValue = std::pair<Value*, APInt>;
+using RepeatedValue = std::pair<Value *, uint64_t>;
/// Given an associative binary expression, return the leaf
/// nodes in Ops along with their weights (how many times the leaf occurs). The
@@ -467,11 +380,10 @@ using RepeatedValue = std::pair<Value*, APInt>;
static bool LinearizeExprTree(Instruction *I,
SmallVectorImpl<RepeatedValue> &Ops,
ReassociatePass::OrderedSet &ToRedo,
- bool &HasNUW) {
+ reassociate::OverflowTracking &Flags) {
assert((isa<UnaryOperator>(I) || isa<BinaryOperator>(I)) &&
"Expected a UnaryOperator or BinaryOperator!");
LLVM_DEBUG(dbgs() << "LINEARIZE: " << *I << '\n');
- unsigned Bitwidth = I->getType()->getScalarType()->getPrimitiveSizeInBits();
unsigned Opcode = I->getOpcode();
assert(I->isAssociative() && I->isCommutative() &&
"Expected an associative and commutative operation!");
@@ -486,8 +398,8 @@ static bool LinearizeExprTree(Instruction *I,
// with their weights, representing a certain number of paths to the operator.
// If an operator occurs in the worklist multiple times then we found multiple
// ways to get to it.
- SmallVector<std::pair<Instruction*, APInt>, 8> Worklist; // (Op, Weight)
- Worklist.push_back(std::make_pair(I, APInt(Bitwidth, 1)));
+ SmallVector<std::pair<Instruction *, uint64_t>, 8> Worklist; // (Op, Weight)
+ Worklist.push_back(std::make_pair(I, 1));
bool Changed = false;
// Leaves of the expression are values that either aren't the right kind of
@@ -505,23 +417,25 @@ static bool LinearizeExprTree(Instruction *I,
// Leaves - Keeps track of the set of putative leaves as well as the number of
// paths to each leaf seen so far.
- using LeafMap = DenseMap<Value *, APInt>;
+ using LeafMap = DenseMap<Value *, uint64_t>;
LeafMap Leaves; // Leaf -> Total weight so far.
SmallVector<Value *, 8> LeafOrder; // Ensure deterministic leaf output order.
+ const DataLayout DL = I->getDataLayout();
#ifndef NDEBUG
SmallPtrSet<Value *, 8> Visited; // For checking the iteration scheme.
#endif
while (!Worklist.empty()) {
- std::pair<Instruction*, APInt> P = Worklist.pop_back_val();
- I = P.first; // We examine the operands of this binary operator.
+ // We examine the operands of this binary operator.
+ auto [I, Weight] = Worklist.pop_back_val();
- if (isa<OverflowingBinaryOperator>(I))
- HasNUW &= I->hasNoUnsignedWrap();
+ if (isa<OverflowingBinaryOperator>(I)) {
+ Flags.HasNUW &= I->hasNoUnsignedWrap();
+ Flags.HasNSW &= I->hasNoSignedWrap();
+ }
for (unsigned OpIdx = 0; OpIdx < I->getNumOperands(); ++OpIdx) { // Visit operands.
Value *Op = I->getOperand(OpIdx);
- APInt Weight = P.second; // Number of paths to this operand.
LLVM_DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n");
assert(!Op->use_empty() && "No uses, so how did we get to it?!");
@@ -555,26 +469,8 @@ static bool LinearizeExprTree(Instruction *I,
"In leaf map but not visited!");
// Update the number of paths to the leaf.
- IncorporateWeight(It->second, Weight, Opcode);
-
-#if 0 // TODO: Re-enable once PR13021 is fixed.
- // The leaf already has one use from inside the expression. As we want
- // exactly one such use, drop this new use of the leaf.
- assert(!Op->hasOneUse() && "Only one use, but we got here twice!");
- I->setOperand(OpIdx, UndefValue::get(I->getType()));
- Changed = true;
-
- // If the leaf is a binary operation of the right kind and we now see
- // that its multiple original uses were in fact all by nodes belonging
- // to the expression, then no longer consider it to be a leaf and add
- // its operands to the expression.
- if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
- LLVM_DEBUG(dbgs() << "UNLEAF: " << *Op << " (" << It->second << ")\n");
- Worklist.push_back(std::make_pair(BO, It->second));
- Leaves.erase(It);
- continue;
- }
-#endif
+ It->second += Weight;
+ assert(It->second >= Weight && "Weight overflows");
// If we still have uses that are not accounted for by the expression
// then it is not safe to modify the value.
@@ -637,13 +533,22 @@ static bool LinearizeExprTree(Instruction *I,
// Node initially thought to be a leaf wasn't.
continue;
assert(!isReassociableOp(V, Opcode) && "Shouldn't be a leaf!");
- APInt Weight = It->second;
- if (Weight.isMinValue())
- // Leaf already output or weight reduction eliminated it.
- continue;
+ uint64_t Weight = It->second;
// Ensure the leaf is only output once.
It->second = 0;
Ops.push_back(std::make_pair(V, Weight));
+ if (Opcode == Instruction::Add && Flags.AllKnownNonNegative && Flags.HasNSW)
+ Flags.AllKnownNonNegative &= isKnownNonNegative(V, SimplifyQuery(DL));
+ else if (Opcode == Instruction::Mul) {
+ // To preserve NUW we need all inputs non-zero.
+ // To preserve NSW we need all inputs strictly positive.
+ if (Flags.AllKnownNonZero &&
+ (Flags.HasNUW || (Flags.HasNSW && Flags.AllKnownNonNegative))) {
+ Flags.AllKnownNonZero &= isKnownNonZero(V, SimplifyQuery(DL));
+ if (Flags.HasNSW && Flags.AllKnownNonNegative)
+ Flags.AllKnownNonNegative &= isKnownNonNegative(V, SimplifyQuery(DL));
+ }
+ }
}
// For nilpotent operations or addition there may be no operands, for example
@@ -652,7 +557,7 @@ static bool LinearizeExprTree(Instruction *I,
if (Ops.empty()) {
Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, I->getType());
assert(Identity && "Associative operation without identity!");
- Ops.emplace_back(Identity, APInt(Bitwidth, 1));
+ Ops.emplace_back(Identity, 1);
}
return Changed;
@@ -662,7 +567,7 @@ static bool LinearizeExprTree(Instruction *I,
/// linearized and optimized, emit them in-order.
void ReassociatePass::RewriteExprTree(BinaryOperator *I,
SmallVectorImpl<ValueEntry> &Ops,
- bool HasNUW) {
+ OverflowTracking Flags) {
assert(Ops.size() > 1 && "Single values should be used directly!");
// Since our optimizations should never increase the number of operations, the
@@ -691,8 +596,8 @@ void ReassociatePass::RewriteExprTree(BinaryOperator *I,
/// of leaf nodes as inner nodes cannot occur by remembering all of the future
/// leaves and refusing to reuse any of them as inner nodes.
SmallPtrSet<Value*, 8> NotRewritable;
- for (unsigned i = 0, e = Ops.size(); i != e; ++i)
- NotRewritable.insert(Ops[i].Op);
+ for (const ValueEntry &Op : Ops)
+ NotRewritable.insert(Op.Op);
// ExpressionChangedStart - Non-null if the rewritten expression differs from
// the original in some non-trivial way, requiring the clearing of optional
@@ -792,9 +697,9 @@ void ReassociatePass::RewriteExprTree(BinaryOperator *I,
// stupid, create a new node if there are none left.
BinaryOperator *NewOp;
if (NodesToRewrite.empty()) {
- Constant *Undef = UndefValue::get(I->getType());
- NewOp = BinaryOperator::Create(Instruction::BinaryOps(Opcode),
- Undef, Undef, "", I);
+ Constant *Poison = PoisonValue::get(I->getType());
+ NewOp = BinaryOperator::Create(Instruction::BinaryOps(Opcode), Poison,
+ Poison, "", I->getIterator());
if (isa<FPMathOperator>(NewOp))
NewOp->setFastMathFlags(I->getFastMathFlags());
} else {
@@ -827,11 +732,14 @@ void ReassociatePass::RewriteExprTree(BinaryOperator *I,
ExpressionChangedStart->setFastMathFlags(Flags);
} else {
ExpressionChangedStart->clearSubclassOptionalData();
- // Note that it doesn't hold for mul if one of the operands is zero.
- // TODO: We can preserve NUW flag if we prove that all mul operands
- // are non-zero.
- if (HasNUW && ExpressionChangedStart->getOpcode() == Instruction::Add)
- ExpressionChangedStart->setHasNoUnsignedWrap();
+ if (ExpressionChangedStart->getOpcode() == Instruction::Add ||
+ (ExpressionChangedStart->getOpcode() == Instruction::Mul &&
+ Flags.AllKnownNonZero)) {
+ if (Flags.HasNUW)
+ ExpressionChangedStart->setHasNoUnsignedWrap();
+ if (Flags.HasNSW && (Flags.AllKnownNonNegative || Flags.HasNUW))
+ ExpressionChangedStart->setHasNoSignedWrap();
+ }
}
}
@@ -854,8 +762,8 @@ void ReassociatePass::RewriteExprTree(BinaryOperator *I,
}
// Throw away any left over nodes from the original expression.
- for (unsigned i = 0, e = NodesToRewrite.size(); i != e; ++i)
- RedoInsts.insert(NodesToRewrite[i]);
+ for (BinaryOperator *BO : NodesToRewrite)
+ RedoInsts.insert(BO);
}
/// Insert instructions before the instruction pointed to by BI,
@@ -868,7 +776,7 @@ void ReassociatePass::RewriteExprTree(BinaryOperator *I,
static Value *NegateValue(Value *V, Instruction *BI,
ReassociatePass::OrderedSet &ToRedo) {
if (auto *C = dyn_cast<Constant>(V)) {
- const DataLayout &DL = BI->getModule()->getDataLayout();
+ const DataLayout &DL = BI->getDataLayout();
Constant *Res = C->getType()->isFPOrFPVectorTy()
? ConstantFoldUnaryOpOperand(Instruction::FNeg, C, DL)
: ConstantExpr::getNeg(C);
@@ -945,7 +853,13 @@ static Value *NegateValue(Value *V, Instruction *BI,
->getIterator();
}
+ // Check that if TheNeg is moved out of its parent block, we drop its
+ // debug location to avoid extra coverage.
+ // See test dropping_debugloc_the_neg.ll for a detailed example.
+ if (TheNeg->getParent() != InsertPt->getParent())
+ TheNeg->dropLocation();
TheNeg->moveBefore(*InsertPt->getParent(), InsertPt);
+
if (TheNeg->getOpcode() == Instruction::Sub) {
TheNeg->setHasNoUnsignedWrap(false);
TheNeg->setHasNoSignedWrap(false);
@@ -958,7 +872,8 @@ static Value *NegateValue(Value *V, Instruction *BI,
// Insert a 'neg' instruction that subtracts the value from zero to get the
// negation.
- Instruction *NewNeg = CreateNeg(V, V->getName() + ".neg", BI, BI);
+ Instruction *NewNeg =
+ CreateNeg(V, V->getName() + ".neg", BI->getIterator(), BI);
ToRedo.insert(NewNeg);
return NewNeg;
}
@@ -1044,8 +959,8 @@ static bool shouldConvertOrWithNoCommonBitsToAdd(Instruction *Or) {
/// transform this into (X+Y) to allow arithmetics reassociation.
static BinaryOperator *convertOrWithNoCommonBitsToAdd(Instruction *Or) {
// Convert an or into an add.
- BinaryOperator *New =
- CreateAdd(Or->getOperand(0), Or->getOperand(1), "", Or, Or);
+ BinaryOperator *New = CreateAdd(Or->getOperand(0), Or->getOperand(1), "",
+ Or->getIterator(), Or);
New->setHasNoSignedWrap();
New->setHasNoUnsignedWrap();
New->takeName(Or);
@@ -1097,7 +1012,8 @@ static BinaryOperator *BreakUpSubtract(Instruction *Sub,
// Calculate the negative value of Operand 1 of the sub instruction,
// and set it as the RHS of the add instruction we just made.
Value *NegVal = NegateValue(Sub->getOperand(1), Sub, ToRedo);
- BinaryOperator *New = CreateAdd(Sub->getOperand(0), NegVal, "", Sub, Sub);
+ BinaryOperator *New =
+ CreateAdd(Sub->getOperand(0), NegVal, "", Sub->getIterator(), Sub);
Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op.
Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op.
New->takeName(Sub);
@@ -1115,10 +1031,11 @@ static BinaryOperator *BreakUpSubtract(Instruction *Sub,
static BinaryOperator *ConvertShiftToMul(Instruction *Shl) {
Constant *MulCst = ConstantInt::get(Shl->getType(), 1);
auto *SA = cast<ConstantInt>(Shl->getOperand(1));
- MulCst = ConstantExpr::getShl(MulCst, SA);
+ MulCst = ConstantFoldBinaryInstruction(Instruction::Shl, MulCst, SA);
+ assert(MulCst && "Constant folding of immediate constants failed");
- BinaryOperator *Mul =
- BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl);
+ BinaryOperator *Mul = BinaryOperator::CreateMul(Shl->getOperand(0), MulCst,
+ "", Shl->getIterator());
Shl->setOperand(0, PoisonValue::get(Shl->getType())); // Drop use of op.
Mul->takeName(Shl);
@@ -1168,13 +1085,13 @@ static unsigned FindInOperandList(const SmallVectorImpl<ValueEntry> &Ops,
/// Emit a tree of add instructions, summing Ops together
/// and returning the result. Insert the tree before I.
-static Value *EmitAddTreeOfValues(Instruction *I,
+static Value *EmitAddTreeOfValues(BasicBlock::iterator It,
SmallVectorImpl<WeakTrackingVH> &Ops) {
if (Ops.size() == 1) return Ops.back();
Value *V1 = Ops.pop_back_val();
- Value *V2 = EmitAddTreeOfValues(I, Ops);
- return CreateAdd(V2, V1, "reass.add", I, I);
+ Value *V2 = EmitAddTreeOfValues(It, Ops);
+ return CreateAdd(V2, V1, "reass.add", It, &*It);
}
/// If V is an expression tree that is a multiplication sequence,
@@ -1186,14 +1103,13 @@ Value *ReassociatePass::RemoveFactorFromExpression(Value *V, Value *Factor) {
return nullptr;
SmallVector<RepeatedValue, 8> Tree;
- bool HasNUW = true;
- MadeChange |= LinearizeExprTree(BO, Tree, RedoInsts, HasNUW);
+ OverflowTracking Flags;
+ MadeChange |= LinearizeExprTree(BO, Tree, RedoInsts, Flags);
SmallVector<ValueEntry, 8> Factors;
Factors.reserve(Tree.size());
for (unsigned i = 0, e = Tree.size(); i != e; ++i) {
RepeatedValue E = Tree[i];
- Factors.append(E.second.getZExtValue(),
- ValueEntry(getRank(E.first), E.first));
+ Factors.append(E.second, ValueEntry(getRank(E.first), E.first));
}
bool FoundFactor = false;
@@ -1229,7 +1145,7 @@ Value *ReassociatePass::RemoveFactorFromExpression(Value *V, Value *Factor) {
if (!FoundFactor) {
// Make sure to restore the operands to the expression tree.
- RewriteExprTree(BO, Factors, HasNUW);
+ RewriteExprTree(BO, Factors, Flags);
return nullptr;
}
@@ -1241,12 +1157,12 @@ Value *ReassociatePass::RemoveFactorFromExpression(Value *V, Value *Factor) {
RedoInsts.insert(BO);
V = Factors[0].Op;
} else {
- RewriteExprTree(BO, Factors, HasNUW);
+ RewriteExprTree(BO, Factors, Flags);
V = BO;
}
if (NeedsNegate)
- V = CreateNeg(V, "neg", &*InsertPt, BO);
+ V = CreateNeg(V, "neg", InsertPt, BO);
return V;
}
@@ -1321,7 +1237,7 @@ static Value *OptimizeAndOrXor(unsigned Opcode,
/// instruction. There are two special cases: 1) if the constant operand is 0,
/// it will return NULL. 2) if the constant is ~0, the symbolic operand will
/// be returned.
-static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd,
+static Value *createAndInstr(BasicBlock::iterator InsertBefore, Value *Opnd,
const APInt &ConstOpnd) {
if (ConstOpnd.isZero())
return nullptr;
@@ -1342,7 +1258,7 @@ static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd,
// If it was successful, true is returned, and the "R" and "C" is returned
// via "Res" and "ConstOpnd", respectively; otherwise, false is returned,
// and both "Res" and "ConstOpnd" remain unchanged.
-bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
+bool ReassociatePass::CombineXorOpnd(BasicBlock::iterator It, XorOpnd *Opnd1,
APInt &ConstOpnd, Value *&Res) {
// Xor-Rule 1: (x | c1) ^ c2 = (x | c1) ^ (c1 ^ c1) ^ c2
// = ((x | c1) ^ c1) ^ (c1 ^ c2)
@@ -1359,7 +1275,7 @@ bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
return false;
Value *X = Opnd1->getSymbolicPart();
- Res = createAndInstr(I, X, ~C1);
+ Res = createAndInstr(It, X, ~C1);
// ConstOpnd was C2, now C1 ^ C2.
ConstOpnd ^= C1;
@@ -1376,7 +1292,7 @@ bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
// via "Res" and "ConstOpnd", respectively (If the entire expression is
// evaluated to a constant, the Res is set to NULL); otherwise, false is
// returned, and both "Res" and "ConstOpnd" remain unchanged.
-bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
+bool ReassociatePass::CombineXorOpnd(BasicBlock::iterator It, XorOpnd *Opnd1,
XorOpnd *Opnd2, APInt &ConstOpnd,
Value *&Res) {
Value *X = Opnd1->getSymbolicPart();
@@ -1411,7 +1327,7 @@ bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
return false;
}
- Res = createAndInstr(I, X, C3);
+ Res = createAndInstr(It, X, C3);
ConstOpnd ^= C1;
} else if (Opnd1->isOrExpr()) {
// Xor-Rule 3: (x | c1) ^ (x | c2) = (x & c3) ^ c3 where c3 = c1 ^ c2
@@ -1427,7 +1343,7 @@ bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
return false;
}
- Res = createAndInstr(I, X, C3);
+ Res = createAndInstr(It, X, C3);
ConstOpnd ^= C3;
} else {
// Xor-Rule 4: (x & c1) ^ (x & c2) = (x & (c1^c2))
@@ -1435,7 +1351,7 @@ bool ReassociatePass::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1,
const APInt &C1 = Opnd1->getConstPart();
const APInt &C2 = Opnd2->getConstPart();
APInt C3 = C1 ^ C2;
- Res = createAndInstr(I, X, C3);
+ Res = createAndInstr(It, X, C3);
}
// Put the original operands in the Redo list; hope they will be deleted
@@ -1483,8 +1399,8 @@ Value *ReassociatePass::OptimizeXor(Instruction *I,
// the "OpndPtrs" as well. For the similar reason, do not fuse this loop
// with the previous loop --- the iterator of the "Opnds" may be invalidated
// when new elements are added to the vector.
- for (unsigned i = 0, e = Opnds.size(); i != e; ++i)
- OpndPtrs.push_back(&Opnds[i]);
+ for (XorOpnd &Op : Opnds)
+ OpndPtrs.push_back(&Op);
// Step 2: Sort the Xor-Operands in a way such that the operands containing
// the same symbolic value cluster together. For instance, the input operand
@@ -1512,7 +1428,8 @@ Value *ReassociatePass::OptimizeXor(Instruction *I,
Value *CV;
// Step 3.1: Try simplifying "CurrOpnd ^ ConstOpnd"
- if (!ConstOpnd.isZero() && CombineXorOpnd(I, CurrOpnd, ConstOpnd, CV)) {
+ if (!ConstOpnd.isZero() &&
+ CombineXorOpnd(I->getIterator(), CurrOpnd, ConstOpnd, CV)) {
Changed = true;
if (CV)
*CurrOpnd = XorOpnd(CV);
@@ -1529,7 +1446,7 @@ Value *ReassociatePass::OptimizeXor(Instruction *I,
// step 3.2: When previous and current operands share the same symbolic
// value, try to simplify "PrevOpnd ^ CurrOpnd ^ ConstOpnd"
- if (CombineXorOpnd(I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
+ if (CombineXorOpnd(I->getIterator(), CurrOpnd, PrevOpnd, ConstOpnd, CV)) {
// Remove previous operand
PrevOpnd->Invalidate();
if (CV) {
@@ -1600,7 +1517,7 @@ Value *ReassociatePass::OptimizeAdd(Instruction *I,
Type *Ty = TheOp->getType();
Constant *C = Ty->isIntOrIntVectorTy() ?
ConstantInt::get(Ty, NumFound) : ConstantFP::get(Ty, NumFound);
- Instruction *Mul = CreateMul(TheOp, C, "factor", I, I);
+ Instruction *Mul = CreateMul(TheOp, C, "factor", I->getIterator(), I);
// Now that we have inserted a multiply, optimize it. This allows us to
// handle cases that require multiple factoring steps, such as this:
@@ -1764,7 +1681,7 @@ Value *ReassociatePass::OptimizeAdd(Instruction *I,
DummyInst->deleteValue();
unsigned NumAddedValues = NewMulOps.size();
- Value *V = EmitAddTreeOfValues(I, NewMulOps);
+ Value *V = EmitAddTreeOfValues(I->getIterator(), NewMulOps);
// Now that we have inserted the add tree, optimize it. This allows us to
// handle cases that require multiple factoring steps, such as this:
@@ -1775,7 +1692,7 @@ Value *ReassociatePass::OptimizeAdd(Instruction *I,
RedoInsts.insert(VI);
// Create the multiply.
- Instruction *V2 = CreateMul(V, MaxOccVal, "reass.mul", I, I);
+ Instruction *V2 = CreateMul(V, MaxOccVal, "reass.mul", I->getIterator(), I);
// Rerun associate on the multiply in case the inner expression turned into
// a multiply. We want to make sure that we keep things in canonical form.
@@ -1914,10 +1831,10 @@ ReassociatePass::buildMinimalMultiplyDAG(IRBuilderBase &Builder,
}
// Unique factors with equal powers -- we've folded them into the first one's
// base.
- Factors.erase(std::unique(Factors.begin(), Factors.end(),
- [](const Factor &LHS, const Factor &RHS) {
- return LHS.Power == RHS.Power;
- }),
+ Factors.erase(llvm::unique(Factors,
+ [](const Factor &LHS, const Factor &RHS) {
+ return LHS.Power == RHS.Power;
+ }),
Factors.end());
// Iteratively collect the base of each factor with an add power into the
@@ -1974,7 +1891,7 @@ Value *ReassociatePass::OptimizeExpression(BinaryOperator *I,
SmallVectorImpl<ValueEntry> &Ops) {
// Now that we have the linearized expression tree, try to optimize it.
// Start by folding any constants that we found.
- const DataLayout &DL = I->getModule()->getDataLayout();
+ const DataLayout &DL = I->getDataLayout();
Constant *Cst = nullptr;
unsigned Opcode = I->getOpcode();
while (!Ops.empty()) {
@@ -2071,8 +1988,8 @@ void ReassociatePass::EraseInst(Instruction *I) {
I->eraseFromParent();
// Optimize its operands.
SmallPtrSet<Instruction *, 8> Visited; // Detect self-referential nodes.
- for (unsigned i = 0, e = Ops.size(); i != e; ++i)
- if (Instruction *Op = dyn_cast<Instruction>(Ops[i])) {
+ for (Value *V : Ops)
+ if (Instruction *Op = dyn_cast<Instruction>(V)) {
// If this is a node in an expression tree, climb to the expression root
// and add that since that's where optimization actually happens.
unsigned Opcode = Op->getOpcode();
@@ -2270,7 +2187,7 @@ void ReassociatePass::OptimizeInst(Instruction *I) {
shouldConvertOrWithNoCommonBitsToAdd(I) && !isLoadCombineCandidate(I) &&
(cast<PossiblyDisjointInst>(I)->isDisjoint() ||
haveNoCommonBitsSet(I->getOperand(0), I->getOperand(1),
- SimplifyQuery(I->getModule()->getDataLayout(),
+ SimplifyQuery(I->getDataLayout(),
/*DT=*/nullptr, /*AC=*/nullptr, I)))) {
Instruction *NI = convertOrWithNoCommonBitsToAdd(I);
RedoInsts.insert(I);
@@ -2366,12 +2283,12 @@ void ReassociatePass::ReassociateExpression(BinaryOperator *I) {
// First, walk the expression tree, linearizing the tree, collecting the
// operand information.
SmallVector<RepeatedValue, 8> Tree;
- bool HasNUW = true;
- MadeChange |= LinearizeExprTree(I, Tree, RedoInsts, HasNUW);
+ OverflowTracking Flags;
+ MadeChange |= LinearizeExprTree(I, Tree, RedoInsts, Flags);
SmallVector<ValueEntry, 8> Ops;
Ops.reserve(Tree.size());
for (const RepeatedValue &E : Tree)
- Ops.append(E.second.getZExtValue(), ValueEntry(getRank(E.first), E.first));
+ Ops.append(E.second, ValueEntry(getRank(E.first), E.first));
LLVM_DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n');
@@ -2560,7 +2477,7 @@ void ReassociatePass::ReassociateExpression(BinaryOperator *I) {
dbgs() << '\n');
// Now that we ordered and optimized the expressions, splat them back into
// the expression tree, removing any unneeded nodes.
- RewriteExprTree(I, Ops, HasNUW);
+ RewriteExprTree(I, Ops, Flags);
}
void
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-30 20:32:03 +0000