#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include <algorithm>
+#include <map>
using namespace llvm;
STATISTIC(NumLinear , "Number of insts linearized");
<< "," << Ops[i].Rank;
}
-namespace {
+namespace {
class VISIBILITY_HIDDEN Reassociate : public FunctionPass {
std::map<BasicBlock*, unsigned> RankMap;
std::map<Value*, unsigned> ValueRankMap;
void RemoveDeadBinaryOp(Value *V);
};
-
- char Reassociate::ID = 0;
- RegisterPass<Reassociate> X("reassociate", "Reassociate expressions");
}
+char Reassociate::ID = 0;
+static RegisterPass<Reassociate> X("reassociate", "Reassociate expressions");
+
// Public interface to the Reassociate pass
FunctionPass *llvm::createReassociatePass() { return new Reassociate(); }
static Instruction *LowerNegateToMultiply(Instruction *Neg) {
Constant *Cst = ConstantInt::getAllOnesValue(Neg->getType());
- Instruction *Res = BinaryOperator::createMul(Neg->getOperand(1), Cst, "",Neg);
+ Instruction *Res = BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg);
Res->takeName(Neg);
Neg->replaceAllUsesWith(Res);
Neg->eraseFromParent();
// Insert a 'neg' instruction that subtracts the value from zero to get the
// negation.
//
- return BinaryOperator::createNeg(V, V->getName() + ".neg", BI);
+ return BinaryOperator::CreateNeg(V, V->getName() + ".neg", BI);
+}
+
+/// ShouldBreakUpSubtract - Return true if we should break up this subtract of
+/// X-Y into (X + -Y).
+static bool ShouldBreakUpSubtract(Instruction *Sub) {
+ // If this is a negation, we can't split it up!
+ if (BinaryOperator::isNeg(Sub))
+ return false;
+
+ // Don't bother to break this up unless either the LHS is an associable add or
+ // subtract or if this is only used by one.
+ if (isReassociableOp(Sub->getOperand(0), Instruction::Add) ||
+ isReassociableOp(Sub->getOperand(0), Instruction::Sub))
+ return true;
+ if (isReassociableOp(Sub->getOperand(1), Instruction::Add) ||
+ isReassociableOp(Sub->getOperand(1), Instruction::Sub))
+ return true;
+ if (Sub->hasOneUse() &&
+ (isReassociableOp(Sub->use_back(), Instruction::Add) ||
+ isReassociableOp(Sub->use_back(), Instruction::Sub)))
+ return true;
+
+ return false;
}
/// BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is
/// only used by an add, transform this into (X+(0-Y)) to promote better
/// reassociation.
static Instruction *BreakUpSubtract(Instruction *Sub) {
- // Don't bother to break this up unless either the LHS is an associable add or
- // if this is only used by one.
- if (!isReassociableOp(Sub->getOperand(0), Instruction::Add) &&
- !isReassociableOp(Sub->getOperand(1), Instruction::Add) &&
- !(Sub->hasOneUse() &&isReassociableOp(Sub->use_back(), Instruction::Add)))
- return 0;
-
// Convert a subtract into an add and a neg instruction... so that sub
// instructions can be commuted with other add instructions...
//
//
Value *NegVal = NegateValue(Sub->getOperand(1), Sub);
Instruction *New =
- BinaryOperator::createAdd(Sub->getOperand(0), NegVal, "", Sub);
+ BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub);
New->takeName(Sub);
// Everyone now refers to the add instruction.
Constant *MulCst = ConstantInt::get(Shl->getType(), 1);
MulCst = ConstantExpr::getShl(MulCst, cast<Constant>(Shl->getOperand(1)));
- Instruction *Mul = BinaryOperator::createMul(Shl->getOperand(0), MulCst,
+ Instruction *Mul = BinaryOperator::CreateMul(Shl->getOperand(0), MulCst,
"", Shl);
Mul->takeName(Shl);
Shl->replaceAllUsesWith(Mul);
Value *V1 = Ops.back();
Ops.pop_back();
Value *V2 = EmitAddTreeOfValues(I, Ops);
- return BinaryOperator::createAdd(V2, V1, "tmp", I);
+ return BinaryOperator::CreateAdd(V2, V1, "tmp", I);
}
/// RemoveFactorFromExpression - If V is an expression tree that is a
// this, we could otherwise run into situations where removing a factor
// from an expression will drop a use of maxocc, and this can cause
// RemoveFactorFromExpression on successive values to behave differently.
- Instruction *DummyInst = BinaryOperator::createAdd(MaxOccVal, MaxOccVal);
+ Instruction *DummyInst = BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal);
std::vector<Value*> NewMulOps;
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) {
unsigned NumAddedValues = NewMulOps.size();
Value *V = EmitAddTreeOfValues(I, NewMulOps);
- Value *V2 = BinaryOperator::createMul(V, MaxOccVal, "tmp", I);
+ Value *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I);
// Now that we have inserted V and its sole use, optimize it. This allows
// us to handle cases that require multiple factoring steps, such as this:
++NumFactor;
- if (Ops.size() == 0)
+ if (Ops.empty())
return V2;
// Add the new value to the list of things being added.
// 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 (!BinaryOperator::isNeg(BI)) {
- if (Instruction *NI = BreakUpSubtract(BI)) {
- MadeChange = true;
- BI = NI;
- }
- } else {
+ if (ShouldBreakUpSubtract(BI)) {
+ BI = BreakUpSubtract(BI);
+ 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) &&