#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
+#include "llvm/IRBuilder.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Pass.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
-#include "llvm/Support/IRBuilder.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ValueHandle.h"
#include "llvm/Support/raw_ostream.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/PostOrderIterator.h"
-#include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/Statistic.h"
#include <algorithm>
using namespace llvm;
private:
void BuildRankMap(Function &F);
unsigned getRank(Value *V);
- Value *ReassociateExpression(BinaryOperator *I);
+ void ReassociateExpression(BinaryOperator *I);
void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
Value *OptimizeExpression(BinaryOperator *I,
SmallVectorImpl<ValueEntry> &Ops);
/// nodes in Ops along with their weights (how many times the leaf occurs). The
/// original expression is the same as
/// (Ops[0].first op Ops[0].first op ... Ops[0].first) <- Ops[0].second times
-/// op
+/// op
/// (Ops[1].first op Ops[1].first op ... Ops[1].first) <- Ops[1].second times
/// op
/// ...
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
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)) {
// 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!");
Leaves.erase(It);
continue;
}
+#endif
// If we still have uses that are not accounted for by the expression
// then it is not safe to modify the value.
// 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) {
+ // If combining multiple constants resulted in the absorber then the entire
+ // expression must evaluate to the absorber.
+ if (Cst == Absorber)
+ Ops.clear();
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)));
}
/// the new expression into.
SmallVector<BinaryOperator*, 8> NodesToRewrite;
unsigned Opcode = I->getOpcode();
- NodesToRewrite.push_back(I);
+ BinaryOperator *Op = I;
// ExpressionChanged - Non-null if the rewritten expression differs from the
// original in some non-trivial way, requiring the clearing of optional flags.
// Flags are cleared from the operator in ExpressionChanged up to I inclusive.
BinaryOperator *ExpressionChanged = 0;
- BinaryOperator *Previous;
- BinaryOperator *Op = 0;
- for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
- assert(!NodesToRewrite.empty() &&
- "Optimized expressions has more nodes than original!");
- Previous = Op; Op = NodesToRewrite.pop_back_val();
- if (ExpressionChanged)
- // Compactify the tree instructions together with each other to guarantee
- // that the expression tree is dominated by all of Ops.
- Op->moveBefore(Previous);
-
+ for (unsigned i = 0; ; ++i) {
// The last operation (which comes earliest in the IR) is special as both
// operands will come from Ops, rather than just one with the other being
// a subexpression.
// from the original expression then just rewrite the rest of the expression
// into it.
if (BinaryOperator *BO = isReassociableOp(Op->getOperand(0), Opcode)) {
- NodesToRewrite.push_back(BO);
+ Op = BO;
continue;
}
// Otherwise, grab a spare node from the original expression and use that as
- // the left-hand side.
- assert(!NodesToRewrite.empty() &&
- "Optimized expressions has more nodes than original!");
+ // the left-hand side. If there are no nodes left then the optimizers made
+ // an expression with more nodes than the original! This usually means that
+ // they did something stupid but it might mean that the problem was just too
+ // hard (finding the mimimal number of multiplications needed to realize a
+ // multiplication expression is NP-complete). Whatever the reason, smart or
+ // 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);
+ } else {
+ NewOp = NodesToRewrite.pop_back_val();
+ }
+
DEBUG(dbgs() << "RA: " << *Op << '\n');
- Op->setOperand(0, NodesToRewrite.back());
+ Op->setOperand(0, NewOp);
DEBUG(dbgs() << "TO: " << *Op << '\n');
ExpressionChanged = Op;
MadeChange = true;
++NumChanged;
+ Op = NewOp;
}
// If the expression changed non-trivially then clear out all subclass data
- // starting from the operator specified in ExpressionChanged.
- if (ExpressionChanged) {
+ // starting from the operator specified in ExpressionChanged, and compactify
+ // the operators to just before the expression root to guarantee that the
+ // expression tree is dominated by all of Ops.
+ if (ExpressionChanged)
do {
ExpressionChanged->clearSubclassOptionalData();
if (ExpressionChanged == I)
break;
+ ExpressionChanged->moveBefore(I);
ExpressionChanged = cast<BinaryOperator>(*ExpressionChanged->use_begin());
} while (1);
- }
// Throw away any left over nodes from the original expression.
for (unsigned i = 0, e = NodesToRewrite.size(); i != e; ++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();
SmallVector<Value*, 8> Ops(I->op_begin(), I->op_end());
// Erase the dead instruction.
ValueRankMap.erase(I);
+ RedoInsts.remove(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])) {
// 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();
- while (Op->hasOneUse() && Op->use_back()->getOpcode() == Opcode)
+ while (Op->hasOneUse() && Op->use_back()->getOpcode() == Opcode &&
+ Visited.insert(Op))
Op = Op->use_back();
RedoInsts.insert(Op);
}
// If this is an interior node of a reassociable tree, ignore it until we
// get to the root of the tree, to avoid N^2 analysis.
- if (BO->hasOneUse() && BO->use_back()->getOpcode() == BO->getOpcode())
+ unsigned Opcode = BO->getOpcode();
+ if (BO->hasOneUse() && BO->use_back()->getOpcode() == Opcode)
return;
// If this is an add tree that is used by a sub instruction, ignore it
ReassociateExpression(BO);
}
-Value *Reassociate::ReassociateExpression(BinaryOperator *I) {
+void Reassociate::ReassociateExpression(BinaryOperator *I) {
// First, walk the expression tree, linearizing the tree, collecting the
// operand information.
// OptimizeExpression - Now that we have the expression tree in a convenient
// sorted form, optimize it globally if possible.
if (Value *V = OptimizeExpression(I, Ops)) {
+ if (V == I)
+ // Self-referential expression in unreachable code.
+ return;
// This expression tree simplified to something that isn't a tree,
// eliminate it.
DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n');
VI->setDebugLoc(I->getDebugLoc());
RedoInsts.insert(I);
++NumAnnihil;
- return V;
+ return;
}
// We want to sink immediates as deeply as possible except in the case where
DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n');
if (Ops.size() == 1) {
+ if (Ops[0].Op == I)
+ // Self-referential expression in unreachable code.
+ return;
+
// This expression tree simplified to something that isn't a tree,
// eliminate it.
I->replaceAllUsesWith(Ops[0].Op);
if (Instruction *OI = dyn_cast<Instruction>(Ops[0].Op))
OI->setDebugLoc(I->getDebugLoc());
RedoInsts.insert(I);
- return Ops[0].Op;
+ return;
}
// Now that we ordered and optimized the expressions, splat them back into
// the expression tree, removing any unneeded nodes.
RewriteExprTree(I, Ops);
- return I;
}
bool Reassociate::runOnFunction(Function &F) {
projects / oota-llvm.git / blobdiff