#define DEBUG_TYPE "reassociate"
#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
///
static void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) {
Module *M = I->getParent()->getParent()->getParent();
- errs() << Instruction::getOpcodeName(I->getOpcode()) << " "
+ dbgs() << Instruction::getOpcodeName(I->getOpcode()) << " "
<< *Ops[0].Op->getType() << '\t';
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
- errs() << "[ ";
- WriteAsOperand(errs(), Ops[i].Op, false, M);
- errs() << ", #" << Ops[i].Rank << "] ";
+ dbgs() << "[ ";
+ WriteAsOperand(dbgs(), Ops[i].Op, false, M);
+ dbgs() << ", #" << Ops[i].Rank << "] ";
}
}
#endif
class Reassociate : public FunctionPass {
DenseMap<BasicBlock*, unsigned> RankMap;
DenseMap<AssertingVH<>, unsigned> ValueRankMap;
+ SmallVector<WeakVH, 8> RedoInsts;
+ SmallVector<WeakVH, 8> DeadInsts;
bool MadeChange;
public:
static char ID; // Pass identification, replacement for typeid
- Reassociate() : FunctionPass(&ID) {}
+ Reassociate() : FunctionPass(ID) {
+ initializeReassociatePass(*PassRegistry::getPassRegistry());
+ }
bool runOnFunction(Function &F);
void LinearizeExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
void LinearizeExpr(BinaryOperator *I);
Value *RemoveFactorFromExpression(Value *V, Value *Factor);
- void ReassociateBB(BasicBlock *BB);
+ void ReassociateInst(BasicBlock::iterator &BBI);
void RemoveDeadBinaryOp(Value *V);
};
}
char Reassociate::ID = 0;
-static RegisterPass<Reassociate> X("reassociate", "Reassociate expressions");
+INITIALIZE_PASS(Reassociate, "reassociate",
+ "Reassociate expressions", false, false)
// Public interface to the Reassociate pass
FunctionPass *llvm::createReassociatePass() { return new Reassociate(); }
void Reassociate::RemoveDeadBinaryOp(Value *V) {
Instruction *Op = dyn_cast<Instruction>(V);
- if (!Op || !isa<BinaryOperator>(Op) || !Op->use_empty())
+ if (!Op || !isa<BinaryOperator>(Op))
return;
Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1);
ValueRankMap.erase(Op);
- Op->eraseFromParent();
+ DeadInsts.push_back(Op);
RemoveDeadBinaryOp(LHS);
RemoveDeadBinaryOp(RHS);
}
// If this is a not or neg instruction, do not count it for rank. This
// assures us that X and ~X will have the same rank.
- if (!I->getType()->isInteger() ||
+ if (!I->getType()->isIntegerTy() ||
(!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I)))
++Rank;
- //DEBUG(errs() << "Calculated Rank[" << V->getName() << "] = "
+ //DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = "
// << Rank << "\n");
return ValueRankMap[I] = Rank;
ValueRankMap.erase(Neg);
Res->takeName(Neg);
Neg->replaceAllUsesWith(Res);
+ Res->setDebugLoc(Neg->getDebugLoc());
Neg->eraseFromParent();
return Res;
}
isReassociableOp(RHS, I->getOpcode()) &&
"Not an expression that needs linearization?");
- DEBUG(errs() << "Linear" << *LHS << '\n' << *RHS << '\n' << *I << '\n');
+ DEBUG(dbgs() << "Linear" << *LHS << '\n' << *RHS << '\n' << *I << '\n');
// Move the RHS instruction to live immediately before I, avoiding breaking
// dominator properties.
RHS->setOperand(0, LHS);
I->setOperand(0, RHS);
+ // Conservatively clear all the optional flags, which may not hold
+ // after the reassociation.
+ I->clearSubclassOptionalData();
+ LHS->clearSubclassOptionalData();
+ RHS->clearSubclassOptionalData();
+
++NumLinear;
MadeChange = true;
- DEBUG(errs() << "Linearized: " << *I << '\n');
+ DEBUG(dbgs() << "Linearized: " << *I << '\n');
// If D is part of this expression tree, tail recurse.
if (isReassociableOp(I->getOperand(1), I->getOpcode()))
/// LinearizeExprTree - Given an associative binary expression tree, traverse
/// all of the uses putting it into canonical form. This forces a left-linear
-/// form of the the expression (((a+b)+c)+d), and collects information about the
+/// form of the expression (((a+b)+c)+d), and collects information about the
/// rank of the non-tree operands.
///
/// NOTE: These intentionally destroys the expression tree operands (turning
std::swap(LHS, RHS);
bool Success = !I->swapOperands();
assert(Success && "swapOperands failed");
- Success = false;
+ (void)Success;
MadeChange = true;
} else if (RHSBO) {
- // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the the RHS is not
+ // Turn (A+B)+(C+D) -> (((A+B)+C)+D). This guarantees the RHS is not
// part of the expression tree.
LinearizeExpr(I);
LHS = LHSBO = cast<BinaryOperator>(I->getOperand(0));
if (I->getOperand(0) != Ops[i].Op ||
I->getOperand(1) != Ops[i+1].Op) {
Value *OldLHS = I->getOperand(0);
- DEBUG(errs() << "RA: " << *I << '\n');
+ DEBUG(dbgs() << "RA: " << *I << '\n');
I->setOperand(0, Ops[i].Op);
I->setOperand(1, Ops[i+1].Op);
- DEBUG(errs() << "TO: " << *I << '\n');
+
+ // Clear all the optional flags, which may not hold after the
+ // reassociation if the expression involved more than just this operation.
+ if (Ops.size() != 2)
+ I->clearSubclassOptionalData();
+
+ DEBUG(dbgs() << "TO: " << *I << '\n');
MadeChange = true;
++NumChanged;
assert(i+2 < Ops.size() && "Ops index out of range!");
if (I->getOperand(1) != Ops[i].Op) {
- DEBUG(errs() << "RA: " << *I << '\n');
+ DEBUG(dbgs() << "RA: " << *I << '\n');
I->setOperand(1, Ops[i].Op);
- DEBUG(errs() << "TO: " << *I << '\n');
+
+ // Conservatively clear all the optional flags, which may not hold
+ // after the reassociation.
+ I->clearSubclassOptionalData();
+
+ DEBUG(dbgs() << "TO: " << *I << '\n');
MadeChange = true;
++NumChanged;
}
// Okay, we need to materialize a negated version of V with an instruction.
// Scan the use lists of V to see if we have one already.
for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;++UI){
- if (!BinaryOperator::isNeg(*UI)) continue;
+ User *U = *UI;
+ if (!BinaryOperator::isNeg(U)) continue;
// We found one! Now we have to make sure that the definition dominates
// this use. We do this by moving it to the entry block (if it is a
// non-instruction value) or right after the definition. These negates will
// be zapped by reassociate later, so we don't need much finesse here.
- BinaryOperator *TheNeg = cast<BinaryOperator>(*UI);
+ BinaryOperator *TheNeg = cast<BinaryOperator>(U);
// Verify that the negate is in this function, V might be a constant expr.
if (TheNeg->getParent()->getParent() != BI->getParent()->getParent())
// Everyone now refers to the add instruction.
ValueRankMap.erase(Sub);
Sub->replaceAllUsesWith(New);
+ New->setDebugLoc(Sub->getDebugLoc());
Sub->eraseFromParent();
- DEBUG(errs() << "Negated: " << *New << '\n');
+ DEBUG(dbgs() << "Negated: " << *New << '\n');
return New;
}
ValueRankMap.erase(Shl);
Mul->takeName(Shl);
Shl->replaceAllUsesWith(Mul);
+ Mul->setDebugLoc(Shl->getDebugLoc());
Shl->eraseFromParent();
return Mul;
}
// remaining operand.
if (Factors.size() == 1) {
ValueRankMap.erase(BO);
- BO->eraseFromParent();
+ DeadInsts.push_back(BO);
V = Factors[0].Op;
} else {
RewriteExprTree(BO, Factors);
/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively
/// add its operands as factors, otherwise add V to the list of factors.
+///
+/// Ops is the top-level list of add operands we're trying to factor.
static void FindSingleUseMultiplyFactors(Value *V,
- SmallVectorImpl<Value*> &Factors) {
+ SmallVectorImpl<Value*> &Factors,
+ const SmallVectorImpl<ValueEntry> &Ops,
+ bool IsRoot) {
BinaryOperator *BO;
- if ((!V->hasOneUse() && !V->use_empty()) ||
+ if (!(V->hasOneUse() || V->use_empty()) || // More than one use.
!(BO = dyn_cast<BinaryOperator>(V)) ||
BO->getOpcode() != Instruction::Mul) {
Factors.push_back(V);
return;
}
+ // If this value has a single use because it is another input to the add
+ // tree we're reassociating and we dropped its use, it actually has two
+ // uses and we can't factor it.
+ if (!IsRoot) {
+ for (unsigned i = 0, e = Ops.size(); i != e; ++i)
+ if (Ops[i].Op == V) {
+ Factors.push_back(V);
+ return;
+ }
+ }
+
+
// Otherwise, add the LHS and RHS to the list of factors.
- FindSingleUseMultiplyFactors(BO->getOperand(1), Factors);
- FindSingleUseMultiplyFactors(BO->getOperand(0), Factors);
+ FindSingleUseMultiplyFactors(BO->getOperand(1), Factors, Ops, false);
+ FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops, false);
}
/// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor'
// Now that we have inserted a multiply, optimize it. This allows us to
// handle cases that require multiple factoring steps, such as this:
// (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6
- Mul = ReassociateExpression(cast<BinaryOperator>(Mul));
+ RedoInsts.push_back(Mul);
// If every add operand was a duplicate, return the multiply.
if (Ops.empty())
// Compute all of the factors of this added value.
SmallVector<Value*, 8> Factors;
- FindSingleUseMultiplyFactors(BOp, Factors);
+ FindSingleUseMultiplyFactors(BOp, Factors, Ops, true);
assert(Factors.size() > 1 && "Bad linearize!");
// Add one to FactorOccurrences for each unique factor in this op.
// because we can percolate the negate out. Watch for minint, which
// cannot be positivified.
if (ConstantInt *CI = dyn_cast<ConstantInt>(Factor))
- if (CI->getValue().isNegative() && !CI->getValue().isMinSignedValue()) {
+ if (CI->isNegative() && !CI->isMinValue(true)) {
Factor = ConstantInt::get(CI->getContext(), -CI->getValue());
assert(!Duplicates.count(Factor) &&
"Shouldn't have two constant factors, missed a canonicalize");
// RemoveFactorFromExpression on successive values to behave differently.
Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal);
SmallVector<Value*, 4> NewMulOps;
- for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
+ for (unsigned i = 0; i != Ops.size(); ++i) {
+ // Only try to remove factors from expressions we're allowed to.
+ BinaryOperator *BOp = dyn_cast<BinaryOperator>(Ops[i].Op);
+ if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty())
+ continue;
+
if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) {
- NewMulOps.push_back(V);
- Ops.erase(Ops.begin()+i);
- --i; --e;
+ // The factorized operand may occur several times. Convert them all in
+ // one fell swoop.
+ for (unsigned j = Ops.size(); j != i;) {
+ --j;
+ if (Ops[j].Op == Ops[i].Op) {
+ NewMulOps.push_back(V);
+ Ops.erase(Ops.begin()+j);
+ }
+ }
+ --i;
}
}
// No need for extra uses anymore.
delete DummyInst;
-
+
unsigned NumAddedValues = NewMulOps.size();
Value *V = EmitAddTreeOfValues(I, 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:
// A*A*B + A*A*C --> A*(A*B+A*C) --> A*(A*(B+C))
assert(NumAddedValues > 1 && "Each occurrence should contribute a value");
+ (void)NumAddedValues;
V = ReassociateExpression(cast<BinaryOperator>(V));
// Create the multiply.
}
-/// ReassociateBB - Inspect all of the instructions in this basic block,
-/// reassociating them as we go.
-void Reassociate::ReassociateBB(BasicBlock *BB) {
- for (BasicBlock::iterator BBI = BB->begin(); BBI != BB->end(); ) {
- Instruction *BI = BBI++;
- if (BI->getOpcode() == Instruction::Shl &&
- isa<ConstantInt>(BI->getOperand(1)))
- if (Instruction *NI = ConvertShiftToMul(BI, ValueRankMap)) {
- MadeChange = true;
- BI = NI;
- }
+/// ReassociateInst - Inspect and reassociate the instruction at the
+/// given position, post-incrementing the position.
+void Reassociate::ReassociateInst(BasicBlock::iterator &BBI) {
+ Instruction *BI = BBI++;
+ if (BI->getOpcode() == Instruction::Shl &&
+ isa<ConstantInt>(BI->getOperand(1)))
+ if (Instruction *NI = ConvertShiftToMul(BI, ValueRankMap)) {
+ MadeChange = true;
+ BI = NI;
+ }
- // Reject cases where it is pointless to do this.
- if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPoint() ||
- isa<VectorType>(BI->getType()))
- continue; // Floating point ops are not associative.
+ // Reject cases where it is pointless to do this.
+ if (!isa<BinaryOperator>(BI) || BI->getType()->isFloatingPointTy() ||
+ BI->getType()->isVectorTy())
+ return; // Floating point ops are not associative.
+
+ // Do not reassociate boolean (i1) expressions. We want to preserve the
+ // original order of evaluation for short-circuited comparisons that
+ // SimplifyCFG has folded to AND/OR expressions. If the expression
+ // is not further optimized, it is likely to be transformed back to a
+ // short-circuited form for code gen, and the source order may have been
+ // optimized for the most likely conditions.
+ if (BI->getType()->isIntegerTy(1))
+ return;
- // If this is a subtract instruction which is not already in negate form,
- // see if we can convert it to X+-Y.
- if (BI->getOpcode() == Instruction::Sub) {
- if (ShouldBreakUpSubtract(BI)) {
- BI = BreakUpSubtract(BI, ValueRankMap);
+ // If this is a subtract instruction which is not already in negate form,
+ // see if we can convert it to X+-Y.
+ if (BI->getOpcode() == Instruction::Sub) {
+ if (ShouldBreakUpSubtract(BI)) {
+ BI = BreakUpSubtract(BI, ValueRankMap);
+ // Reset the BBI iterator in case BreakUpSubtract changed the
+ // instruction it points to.
+ BBI = BI;
+ ++BBI;
+ MadeChange = true;
+ } else if (BinaryOperator::isNeg(BI)) {
+ // Otherwise, this is a negation. See if the operand is a multiply tree
+ // and if this is not an inner node of a multiply tree.
+ if (isReassociableOp(BI->getOperand(1), Instruction::Mul) &&
+ (!BI->hasOneUse() ||
+ !isReassociableOp(BI->use_back(), Instruction::Mul))) {
+ BI = LowerNegateToMultiply(BI, ValueRankMap);
MadeChange = true;
- } else if (BinaryOperator::isNeg(BI)) {
- // Otherwise, this is a negation. See if the operand is a multiply tree
- // and if this is not an inner node of a multiply tree.
- if (isReassociableOp(BI->getOperand(1), Instruction::Mul) &&
- (!BI->hasOneUse() ||
- !isReassociableOp(BI->use_back(), Instruction::Mul))) {
- BI = LowerNegateToMultiply(BI, ValueRankMap);
- MadeChange = true;
- }
}
}
+ }
- // If this instruction is a commutative binary operator, process it.
- if (!BI->isAssociative()) continue;
- BinaryOperator *I = cast<BinaryOperator>(BI);
+ // If this instruction is a commutative binary operator, process it.
+ if (!BI->isAssociative()) return;
+ BinaryOperator *I = cast<BinaryOperator>(BI);
- // 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 (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode()))
- continue;
+ // 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 (I->hasOneUse() && isReassociableOp(I->use_back(), I->getOpcode()))
+ return;
- // If this is an add tree that is used by a sub instruction, ignore it
- // until we process the subtract.
- if (I->hasOneUse() && I->getOpcode() == Instruction::Add &&
- cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub)
- continue;
+ // If this is an add tree that is used by a sub instruction, ignore it
+ // until we process the subtract.
+ if (I->hasOneUse() && I->getOpcode() == Instruction::Add &&
+ cast<Instruction>(I->use_back())->getOpcode() == Instruction::Sub)
+ return;
- ReassociateExpression(I);
- }
+ ReassociateExpression(I);
}
Value *Reassociate::ReassociateExpression(BinaryOperator *I) {
SmallVector<ValueEntry, 8> Ops;
LinearizeExprTree(I, Ops);
- DEBUG(errs() << "RAIn:\t"; PrintOps(I, Ops); errs() << '\n');
+ DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n');
// Now that we have linearized the tree to a list and have gathered all of
// the operands and their ranks, sort the operands by their rank. Use a
if (Value *V = OptimizeExpression(I, Ops)) {
// This expression tree simplified to something that isn't a tree,
// eliminate it.
- DEBUG(errs() << "Reassoc to scalar: " << *V << '\n');
+ DEBUG(dbgs() << "Reassoc to scalar: " << *V << '\n');
I->replaceAllUsesWith(V);
+ if (Instruction *VI = dyn_cast<Instruction>(V))
+ VI->setDebugLoc(I->getDebugLoc());
RemoveDeadBinaryOp(I);
++NumAnnihil;
return V;
Ops.insert(Ops.begin(), Tmp);
}
- DEBUG(errs() << "RAOut:\t"; PrintOps(I, Ops); errs() << '\n');
+ DEBUG(dbgs() << "RAOut:\t"; PrintOps(I, Ops); dbgs() << '\n');
if (Ops.size() == 1) {
// 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());
RemoveDeadBinaryOp(I);
return Ops[0].Op;
}
MadeChange = false;
for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
- ReassociateBB(FI);
+ for (BasicBlock::iterator BBI = FI->begin(); BBI != FI->end(); )
+ ReassociateInst(BBI);
+
+ // Now that we're done, revisit any instructions which are likely to
+ // have secondary reassociation opportunities.
+ while (!RedoInsts.empty())
+ if (Value *V = RedoInsts.pop_back_val()) {
+ BasicBlock::iterator BBI = cast<Instruction>(V);
+ ReassociateInst(BBI);
+ }
+
+ // Now that we're done, delete any instructions which are no longer used.
+ while (!DeadInsts.empty())
+ if (Value *V = DeadInsts.pop_back_val())
+ RecursivelyDeleteTriviallyDeadInstructions(V);
// We are done with the rank map.
RankMap.clear();
projects / oota-llvm.git / blobdiff