private:
void BuildRankMap(Function &F);
unsigned getRank(Value *V);
+ void canonicalizeOperands(Instruction *I);
void ReassociateExpression(BinaryOperator *I);
void RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
Value *OptimizeExpression(BinaryOperator *I,
Value *OptimizeMul(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops);
Value *RemoveFactorFromExpression(Value *V, Value *Factor);
void EraseInst(Instruction *I);
- void optimizeFAddNegExpr(ConstantFP *ConstOperand, Instruction *I,
- int OperandNr);
void OptimizeInst(Instruction *I);
+ Instruction *canonicalizeNegConstExpr(Instruction *I);
};
}
/// opcode and if it only has one use.
static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) {
if (V->hasOneUse() && isa<Instruction>(V) &&
- cast<Instruction>(V)->getOpcode() == Opcode)
+ cast<Instruction>(V)->getOpcode() == Opcode &&
+ (!isa<FPMathOperator>(V) ||
+ cast<Instruction>(V)->hasUnsafeAlgebra()))
return cast<BinaryOperator>(V);
return nullptr;
}
unsigned Opcode2) {
if (V->hasOneUse() && isa<Instruction>(V) &&
(cast<Instruction>(V)->getOpcode() == Opcode1 ||
- cast<Instruction>(V)->getOpcode() == Opcode2))
+ cast<Instruction>(V)->getOpcode() == Opcode2) &&
+ (!isa<FPMathOperator>(V) ||
+ cast<Instruction>(V)->hasUnsafeAlgebra()))
return cast<BinaryOperator>(V);
return nullptr;
}
void Reassociate::BuildRankMap(Function &F) {
unsigned i = 2;
- // Assign distinct ranks to function arguments
- for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
+ // Assign distinct ranks to function arguments.
+ for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
ValueRankMap[&*I] = ++i;
+ DEBUG(dbgs() << "Calculated Rank[" << I->getName() << "] = " << i << "\n");
+ }
ReversePostOrderTraversal<Function*> RPOT(&F);
for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
!BinaryOperator::isFNeg(I)))
++Rank;
- //DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = "
- // << Rank << "\n");
+ DEBUG(dbgs() << "Calculated Rank[" << V->getName() << "] = " << Rank << "\n");
return ValueRankMap[I] = Rank;
}
+// Canonicalize constants to RHS. Otherwise, sort the operands by rank.
+void Reassociate::canonicalizeOperands(Instruction *I) {
+ assert(isa<BinaryOperator>(I) && "Expected binary operator.");
+ assert(I->isCommutative() && "Expected commutative operator.");
+
+ Value *LHS = I->getOperand(0);
+ Value *RHS = I->getOperand(1);
+ unsigned LHSRank = getRank(LHS);
+ unsigned RHSRank = getRank(RHS);
+
+ if (isa<Constant>(RHS))
+ return;
+
+ if (isa<Constant>(LHS) || RHSRank < LHSRank)
+ cast<BinaryOperator>(I)->swapOperands();
+}
+
static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name,
Instruction *InsertBefore, Value *FlagsOp) {
if (S1->getType()->isIntegerTy())
// ways to get to it.
SmallVector<std::pair<BinaryOperator*, APInt>, 8> Worklist; // (Op, Weight)
Worklist.push_back(std::make_pair(I, APInt(Bitwidth, 1)));
- bool MadeChange = false;
+ bool Changed = false;
// Leaves of the expression are values that either aren't the right kind of
// operation (eg: a constant, or a multiply in an add tree), or are, but have
// 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)) {
- assert(Visited.insert(Op) && "Not first visit!");
+ assert(Visited.insert(Op).second && "Not first visit!");
DEBUG(dbgs() << "DIRECT ADD: " << *Op << " (" << Weight << ")\n");
Worklist.push_back(std::make_pair(BO, Weight));
continue;
LeafMap::iterator It = Leaves.find(Op);
if (It == Leaves.end()) {
// Not in the leaf map. Must be the first time we saw this operand.
- assert(Visited.insert(Op) && "Not first visit!");
+ assert(Visited.insert(Op).second && "Not first visit!");
if (!Op->hasOneUse()) {
// This value has uses not accounted for by the expression, so it is
// not safe to modify. Mark it as being a leaf.
// 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()));
- MadeChange = true;
+ 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
// expression. This means that it can safely be modified. See if we
// can usefully morph it into an expression of the right kind.
assert((!isa<Instruction>(Op) ||
- cast<Instruction>(Op)->getOpcode() != Opcode) &&
+ cast<Instruction>(Op)->getOpcode() != Opcode
+ || (isa<FPMathOperator>(Op) &&
+ !cast<Instruction>(Op)->hasUnsafeAlgebra())) &&
"Should have been handled above!");
assert(Op->hasOneUse() && "Has uses outside the expression tree!");
BO = LowerNegateToMultiply(BO);
DEBUG(dbgs() << *BO << '\n');
Worklist.push_back(std::make_pair(BO, Weight));
- MadeChange = true;
+ Changed = true;
continue;
}
Ops.push_back(std::make_pair(Identity, APInt(Bitwidth, 1)));
}
- return MadeChange;
+ return Changed;
}
// RewriteExprTree - Now that the operands for this expression tree are
/// version of the value is returned, and BI is left pointing at the instruction
/// that should be processed next by the reassociation pass.
static Value *NegateValue(Value *V, Instruction *BI) {
- if (ConstantFP *C = dyn_cast<ConstantFP>(V))
- return ConstantExpr::getFNeg(C);
- if (Constant *C = dyn_cast<Constant>(V))
+ if (Constant *C = dyn_cast<Constant>(V)) {
+ if (C->getType()->isFPOrFPVectorTy()) {
+ return ConstantExpr::getFNeg(C);
+ }
return ConstantExpr::getNeg(C);
+ }
+
// We are trying to expose opportunity for reassociation. One of the things
// that we want to do to achieve this is to push a negation as deep into an
if (BinaryOperator::isNeg(Sub) || BinaryOperator::isFNeg(Sub))
return false;
+ // Don't breakup X - undef.
+ if (isa<UndefValue>(Sub->getOperand(1)))
+ 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.
Value *V0 = Sub->getOperand(0);
BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl);
Shl->setOperand(0, UndefValue::get(Shl->getType())); // Drop use of op.
Mul->takeName(Shl);
+
+ // Everyone now refers to the mul instruction.
Shl->replaceAllUsesWith(Mul);
Mul->setDebugLoc(Shl->getDebugLoc());
+
+ // We can safely preserve the nuw flag in all cases. It's also safe to turn a
+ // nuw nsw shl into a nuw nsw mul. However, nsw in isolation requires special
+ // handling.
+ bool NSW = cast<BinaryOperator>(Shl)->hasNoSignedWrap();
+ bool NUW = cast<BinaryOperator>(Shl)->hasNoUnsignedWrap();
+ if (NSW && NUW)
+ Mul->setHasNoSignedWrap(true);
+ Mul->setHasNoUnsignedWrap(NUW);
return Mul;
}
Value *X) {
unsigned XRank = Ops[i].Rank;
unsigned e = Ops.size();
- for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j)
+ for (unsigned j = i+1; j != e && Ops[j].Rank == XRank; ++j) {
if (Ops[j].Op == X)
return j;
+ if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
+ if (Instruction *I2 = dyn_cast<Instruction>(X))
+ if (I1->isIdenticalTo(I2))
+ return j;
+ }
// Scan backwards.
- for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j)
+ for (unsigned j = i-1; j != ~0U && Ops[j].Rank == XRank; --j) {
if (Ops[j].Op == X)
return j;
+ if (Instruction *I1 = dyn_cast<Instruction>(Ops[j].Op))
+ if (Instruction *I2 = dyn_cast<Instruction>(X))
+ if (I1->isIdenticalTo(I2))
+ return j;
+ }
return i;
}
++NumFound;
} while (i != Ops.size() && Ops[i].Op == TheOp);
- DEBUG(errs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n');
+ DEBUG(dbgs() << "\nFACTORING [" << NumFound << "]: " << *TheOp << '\n');
++NumFactor;
// Insert a new multiply.
SmallPtrSet<Value*, 8> Duplicates;
for (unsigned i = 0, e = Factors.size(); i != e; ++i) {
Value *Factor = Factors[i];
- if (!Duplicates.insert(Factor))
+ if (!Duplicates.insert(Factor).second)
continue;
unsigned Occ = ++FactorOccurrences[Factor];
// If any factor occurred more than one time, we can pull it out.
if (MaxOcc > 1) {
- DEBUG(errs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n');
+ DEBUG(dbgs() << "\nFACTORING [" << MaxOcc << "]: " << *MaxOccVal << '\n');
++NumFactor;
// Create a new instruction that uses the MaxOccVal twice. If we don't do
// and add that since that's where optimization actually happens.
unsigned Opcode = Op->getOpcode();
while (Op->hasOneUse() && Op->user_back()->getOpcode() == Opcode &&
- Visited.insert(Op))
+ Visited.insert(Op).second)
Op = Op->user_back();
RedoInsts.insert(Op);
}
}
-void Reassociate::optimizeFAddNegExpr(ConstantFP *ConstOperand, Instruction *I,
- int OperandNr) {
+// Canonicalize expressions of the following form:
+// x + (-Constant * y) -> x - (Constant * y)
+// x - (-Constant * y) -> x + (Constant * y)
+Instruction *Reassociate::canonicalizeNegConstExpr(Instruction *I) {
+ if (!I->hasOneUse() || I->getType()->isVectorTy())
+ return nullptr;
+
+ // Must be a mul, fmul, or fdiv instruction.
+ unsigned Opcode = I->getOpcode();
+ if (Opcode != Instruction::Mul && Opcode != Instruction::FMul &&
+ Opcode != Instruction::FDiv)
+ return nullptr;
+
+ // Must have at least one constant operand.
+ Constant *C0 = dyn_cast<Constant>(I->getOperand(0));
+ Constant *C1 = dyn_cast<Constant>(I->getOperand(1));
+ if (!C0 && !C1)
+ return nullptr;
+
+ // Must be a negative ConstantInt or ConstantFP.
+ Constant *C = C0 ? C0 : C1;
+ unsigned ConstIdx = C0 ? 0 : 1;
+ if (auto *CI = dyn_cast<ConstantInt>(C)) {
+ if (!CI->isNegative() || CI->isMinValue(true))
+ return nullptr;
+ } else if (auto *CF = dyn_cast<ConstantFP>(C)) {
+ if (!CF->isNegative())
+ return nullptr;
+ } else
+ return nullptr;
+
+ // User must be a binary operator with one or more uses.
+ Instruction *User = I->user_back();
+ if (!isa<BinaryOperator>(User) || !User->getNumUses())
+ return nullptr;
+
+ unsigned UserOpcode = User->getOpcode();
+ if (UserOpcode != Instruction::Add && UserOpcode != Instruction::FAdd &&
+ UserOpcode != Instruction::Sub && UserOpcode != Instruction::FSub)
+ return nullptr;
+
+ // Subtraction is not commutative. Explicitly, the following transform is
+ // not valid: (-Constant * y) - x -> x + (Constant * y)
+ if (!User->isCommutative() && User->getOperand(1) != I)
+ return nullptr;
+
// Change the sign of the constant.
- APFloat Val = ConstOperand->getValueAPF();
- Val.changeSign();
- I->setOperand(0, ConstantFP::get(ConstOperand->getContext(), Val));
-
- assert(I->hasOneUse() && "Only a single use can be replaced.");
- Instruction *Parent = I->user_back();
-
- Value *OtherOperand = Parent->getOperand(1 - OperandNr);
-
- unsigned Opcode = Parent->getOpcode();
- assert(Opcode == Instruction::FAdd ||
- (Opcode == Instruction::FSub && Parent->getOperand(1) == I));
-
- BinaryOperator *NI = Opcode == Instruction::FAdd
- ? BinaryOperator::CreateFSub(OtherOperand, I)
- : BinaryOperator::CreateFAdd(OtherOperand, I);
- NI->setFastMathFlags(cast<FPMathOperator>(Parent)->getFastMathFlags());
- NI->insertBefore(Parent);
- NI->setName(Parent->getName() + ".repl");
- Parent->replaceAllUsesWith(NI);
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(C))
+ I->setOperand(ConstIdx, ConstantInt::get(CI->getContext(), -CI->getValue()));
+ else {
+ ConstantFP *CF = cast<ConstantFP>(C);
+ APFloat Val = CF->getValueAPF();
+ Val.changeSign();
+ I->setOperand(ConstIdx, ConstantFP::get(CF->getContext(), Val));
+ }
+
+ // Canonicalize I to RHS to simplify the next bit of logic. E.g.,
+ // ((-Const*y) + x) -> (x + (-Const*y)).
+ if (User->getOperand(0) == I && User->isCommutative())
+ cast<BinaryOperator>(User)->swapOperands();
+
+ Value *Op0 = User->getOperand(0);
+ Value *Op1 = User->getOperand(1);
+ BinaryOperator *NI;
+ switch(UserOpcode) {
+ default:
+ llvm_unreachable("Unexpected Opcode!");
+ case Instruction::Add:
+ NI = BinaryOperator::CreateSub(Op0, Op1);
+ break;
+ case Instruction::Sub:
+ NI = BinaryOperator::CreateAdd(Op0, Op1);
+ break;
+ case Instruction::FAdd:
+ NI = BinaryOperator::CreateFSub(Op0, Op1);
+ NI->setFastMathFlags(cast<FPMathOperator>(User)->getFastMathFlags());
+ break;
+ case Instruction::FSub:
+ NI = BinaryOperator::CreateFAdd(Op0, Op1);
+ NI->setFastMathFlags(cast<FPMathOperator>(User)->getFastMathFlags());
+ break;
+ }
+
+ NI->insertBefore(User);
+ NI->setName(User->getName());
+ User->replaceAllUsesWith(NI);
NI->setDebugLoc(I->getDebugLoc());
+ RedoInsts.insert(I);
MadeChange = true;
+ return NI;
}
/// OptimizeInst - Inspect and optimize the given instruction. Note that erasing
I = NI;
}
- // Commute floating point binary operators, to canonicalize the order of their
- // operands. This can potentially expose more CSE opportunities, and makes
- // writing other transformations simpler.
- if (I->getType()->isFloatingPointTy() || I->getType()->isVectorTy()) {
-
- // FAdd and FMul can be commuted.
- unsigned Opcode = I->getOpcode();
- if (Opcode == Instruction::FMul || Opcode == Instruction::FAdd) {
- Value *LHS = I->getOperand(0);
- Value *RHS = I->getOperand(1);
- unsigned LHSRank = getRank(LHS);
- unsigned RHSRank = getRank(RHS);
-
- // Sort the operands by rank.
- if (RHSRank < LHSRank) {
- I->setOperand(0, RHS);
- I->setOperand(1, LHS);
- }
- }
+ // Canonicalize negative constants out of expressions.
+ if (Instruction *Res = canonicalizeNegConstExpr(I))
+ I = Res;
- // Reassociate: x + -ConstantFP * y -> x - ConstantFP * y
- // The FMul can also be an FDiv, and FAdd can be a FSub.
- if (Opcode == Instruction::FMul || Opcode == Instruction::FDiv) {
- if (ConstantFP *LHSConst = dyn_cast<ConstantFP>(I->getOperand(0))) {
- if (LHSConst->isNegative() && I->hasOneUse()) {
- Instruction *Parent = I->user_back();
- if (Parent->getOpcode() == Instruction::FAdd) {
- if (Parent->getOperand(0) == I)
- optimizeFAddNegExpr(LHSConst, I, 0);
- else if (Parent->getOperand(1) == I)
- optimizeFAddNegExpr(LHSConst, I, 1);
- } else if (Parent->getOpcode() == Instruction::FSub)
- if (Parent->getOperand(1) == I)
- optimizeFAddNegExpr(LHSConst, I, 1);
- }
- }
- }
+ // Commute binary operators, to canonicalize the order of their operands.
+ // This can potentially expose more CSE opportunities, and makes writing other
+ // transformations simpler.
+ if (I->isCommutative())
+ canonicalizeOperands(I);
- // FIXME: We should commute vector instructions as well. However, this
- // requires further analysis to determine the effect on later passes.
+ // Don't optimize vector instructions.
+ if (I->getType()->isVectorTy())
+ return;
- // Don't try to optimize vector instructions or anything that doesn't have
- // unsafe algebra.
- if (I->getType()->isVectorTy() || !I->hasUnsafeAlgebra())
- return;
- }
+ // Don't optimize floating point instructions that don't have unsafe algebra.
+ if (I->getType()->isFloatingPointTy() && !I->hasUnsafeAlgebra())
+ return;
// Do not reassociate boolean (i1) expressions. We want to preserve the
// original order of evaluation for short-circuited comparisons that
projects / oota-llvm.git / blobdiff