summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Constants.h8
-rw-r--r--lib/Transforms/Scalar/Reassociate.cpp54
-rw-r--r--lib/VMCore/Constants.cpp25
3 files changed, 44 insertions, 43 deletions
diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h
index a3f5b95dbc..fdd53823aa 100644
--- a/include/llvm/Constants.h
+++ b/include/llvm/Constants.h
@@ -919,9 +919,15 @@ public:
/// getBinOpIdentity - Return the identity for the given binary operation,
/// i.e. a constant C such that X op C = X and C op X = X for every X. It
- /// is an error to call this for an operation that doesn't have an identity.
+ /// returns null if the operator doesn't have an identity.
static Constant *getBinOpIdentity(unsigned Opcode, Type *Ty);
+ /// getBinOpAbsorber - Return the absorbing element for the given binary
+ /// operation, i.e. a constant C such that X op C = C and C op X = C for
+ /// every X. For example, this returns zero for integer multiplication.
+ /// It returns null if the operator doesn't have an absorbing element.
+ static Constant *getBinOpAbsorber(unsigned Opcode, Type *Ty);
+
/// Transparently provide more efficient getOperand methods.
DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Constant);
diff --git a/lib/Transforms/Scalar/Reassociate.cpp b/lib/Transforms/Scalar/Reassociate.cpp
index 8cace5eebd..ed7340f7e6 100644
--- a/lib/Transforms/Scalar/Reassociate.cpp
+++ b/lib/Transforms/Scalar/Reassociate.cpp
@@ -455,6 +455,10 @@ static bool LinearizeExprTree(BinaryOperator *I,
assert(Instruction::isAssociative(Opcode) &&
Instruction::isCommutative(Opcode) &&
"Expected an associative and commutative operation!");
+ // If we see an absorbing element then the entire expression must be equal to
+ // it. For example, if this is a multiplication expression and zero occurs as
+ // an operand somewhere in it then the result of the expression must be zero.
+ Constant *Absorber = ConstantExpr::getBinOpAbsorber(Opcode, I->getType());
// Visit all operands of the expression, keeping track of their weight (the
// number of paths from the expression root to the operand, or if you like
@@ -502,6 +506,13 @@ static bool LinearizeExprTree(BinaryOperator *I,
DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n");
assert(!Op->use_empty() && "No uses, so how did we get to it?!");
+ // If the expression contains an absorbing element then there is no need
+ // to analyze it further: it must evaluate to the absorbing element.
+ if (Op == Absorber && !Weight.isMinValue()) {
+ Ops.push_back(std::make_pair(Absorber, APInt(Bitwidth, 1)));
+ return MadeChange;
+ }
+
// If this is a binary operation of the right kind with only one use then
// add its operands to the expression.
if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) {
@@ -617,14 +628,15 @@ static bool LinearizeExprTree(BinaryOperator *I,
// Add any constants back into Ops, all globbed together and reduced to having
// weight 1 for the convenience of users.
- if (Cst && Cst != ConstantExpr::getBinOpIdentity(Opcode, I->getType()))
+ Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, I->getType());
+ if (Cst && Cst != Identity)
Ops.push_back(std::make_pair(Cst, APInt(Bitwidth, 1)));
// For nilpotent operations or addition there may be no operands, for example
// because the expression was "X xor X" or consisted of 2^Bitwidth additions:
// in both cases the weight reduces to 0 causing the value to be skipped.
if (Ops.empty()) {
- Constant *Identity = ConstantExpr::getBinOpIdentity(Opcode, I->getType());
+ assert(Identity && "Associative operation without identity!");
Ops.push_back(std::make_pair(Identity, APInt(Bitwidth, 1)));
}
@@ -1426,44 +1438,6 @@ Value *Reassociate::OptimizeExpression(BinaryOperator *I,
unsigned Opcode = I->getOpcode();
- if (Constant *V1 = dyn_cast<Constant>(Ops[Ops.size()-2].Op))
- if (Constant *V2 = dyn_cast<Constant>(Ops.back().Op)) {
- Ops.pop_back();
- Ops.back().Op = ConstantExpr::get(Opcode, V1, V2);
- return OptimizeExpression(I, Ops);
- }
-
- // Check for destructive annihilation due to a constant being used.
- if (ConstantInt *CstVal = dyn_cast<ConstantInt>(Ops.back().Op))
- switch (Opcode) {
- default: break;
- case Instruction::And:
- if (CstVal->isZero()) // X & 0 -> 0
- return CstVal;
- if (CstVal->isAllOnesValue()) // X & -1 -> X
- Ops.pop_back();
- break;
- case Instruction::Mul:
- if (CstVal->isZero()) { // X * 0 -> 0
- ++NumAnnihil;
- return CstVal;
- }
-
- if (cast<ConstantInt>(CstVal)->isOne())
- Ops.pop_back(); // X * 1 -> X
- break;
- case Instruction::Or:
- if (CstVal->isAllOnesValue()) // X | -1 -> -1
- return CstVal;
- // FALLTHROUGH!
- case Instruction::Add:
- case Instruction::Xor:
- if (CstVal->isZero()) // X [|^+] 0 -> X
- Ops.pop_back();
- break;
- }
- if (Ops.size() == 1) return Ops[0].Op;
-
// Handle destructive annihilation due to identities between elements in the
// argument list here.
unsigned NumOps = Ops.size();
diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp
index 17bad97e6f..400b2741cd 100644
--- a/lib/VMCore/Constants.cpp
+++ b/lib/VMCore/Constants.cpp
@@ -2009,11 +2009,13 @@ Constant *ConstantExpr::getAShr(Constant *C1, Constant *C2, bool isExact) {
/// getBinOpIdentity - Return the identity for the given binary operation,
/// i.e. a constant C such that X op C = X and C op X = X for every X. It
-/// is an error to call this for an operation that doesn't have an identity.
+/// returns null if the operator doesn't have an identity.
Constant *ConstantExpr::getBinOpIdentity(unsigned Opcode, Type *Ty) {
switch (Opcode) {
default:
- llvm_unreachable("Not a binary operation with identity");
+ // Doesn't have an identity.
+ return 0;
+
case Instruction::Add:
case Instruction::Or:
case Instruction::Xor:
@@ -2027,6 +2029,25 @@ Constant *ConstantExpr::getBinOpIdentity(unsigned Opcode, Type *Ty) {
}
}
+/// getBinOpAbsorber - Return the absorbing element for the given binary
+/// operation, i.e. a constant C such that X op C = C and C op X = C for
+/// every X. For example, this returns zero for integer multiplication.
+/// It returns null if the operator doesn't have an absorbing element.
+Constant *ConstantExpr::getBinOpAbsorber(unsigned Opcode, Type *Ty) {
+ switch (Opcode) {
+ default:
+ // Doesn't have an absorber.
+ return 0;
+
+ case Instruction::Or:
+ return Constant::getAllOnesValue(Ty);
+
+ case Instruction::And:
+ case Instruction::Mul:
+ return Constant::getNullValue(Ty);
+ }
+}
+
// destroyConstant - Remove the constant from the constant table...
//
void ConstantExpr::destroyConstant() {
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-18 04:19:24 +0000