X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FReassociate.cpp;h=adfd5f9af9eafa938ab37a41cf8a7cc83461f8ef;hb=ec5f6e86e3d967c68dc921e2ba4ec802baa1f378;hp=b11567cc9dfd3c5867a730952021ffa8e92f298c;hpb=3b41039163185475945c4e3e970783014cc0975b;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/Reassociate.cpp b/lib/Transforms/Scalar/Reassociate.cpp index b11567cc9df..adfd5f9af9e 100644 --- a/lib/Transforms/Scalar/Reassociate.cpp +++ b/lib/Transforms/Scalar/Reassociate.cpp @@ -26,6 +26,8 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DerivedTypes.h" @@ -59,7 +61,7 @@ namespace { } #ifndef NDEBUG -/// PrintOps - Print out the expression identified in the Ops list. +/// Print out the expression identified in the Ops list. /// static void PrintOps(Instruction *I, const SmallVectorImpl &Ops) { Module *M = I->getParent()->getParent()->getParent(); @@ -172,10 +174,12 @@ namespace { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); + AU.addPreserved(); } private: void BuildRankMap(Function &F); unsigned getRank(Value *V); + void canonicalizeOperands(Instruction *I); void ReassociateExpression(BinaryOperator *I); void RewriteExprTree(BinaryOperator *I, SmallVectorImpl &Ops); Value *OptimizeExpression(BinaryOperator *I, @@ -194,6 +198,7 @@ namespace { Value *RemoveFactorFromExpression(Value *V, Value *Factor); void EraseInst(Instruction *I); void OptimizeInst(Instruction *I); + Instruction *canonicalizeNegConstExpr(Instruction *I); }; } @@ -231,11 +236,13 @@ INITIALIZE_PASS(Reassociate, "reassociate", // Public interface to the Reassociate pass FunctionPass *llvm::createReassociatePass() { return new Reassociate(); } -/// isReassociableOp - Return true if V is an instruction of the specified -/// opcode and if it only has one use. +/// Return true if V is an instruction of the specified opcode and if it +/// only has one use. static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode) { if (V->hasOneUse() && isa(V) && - cast(V)->getOpcode() == Opcode) + cast(V)->getOpcode() == Opcode && + (!isa(V) || + cast(V)->hasUnsafeAlgebra())) return cast(V); return nullptr; } @@ -244,38 +251,21 @@ static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode1, unsigned Opcode2) { if (V->hasOneUse() && isa(V) && (cast(V)->getOpcode() == Opcode1 || - cast(V)->getOpcode() == Opcode2)) + cast(V)->getOpcode() == Opcode2) && + (!isa(V) || + cast(V)->hasUnsafeAlgebra())) return cast(V); return nullptr; } -static bool isUnmovableInstruction(Instruction *I) { - switch (I->getOpcode()) { - case Instruction::PHI: - case Instruction::LandingPad: - case Instruction::Alloca: - case Instruction::Load: - case Instruction::Invoke: - case Instruction::UDiv: - case Instruction::SDiv: - case Instruction::FDiv: - case Instruction::URem: - case Instruction::SRem: - case Instruction::FRem: - return true; - case Instruction::Call: - return !isa(I); - default: - return false; - } -} - 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 RPOT(&F); for (ReversePostOrderTraversal::rpo_iterator I = RPOT.begin(), @@ -287,7 +277,7 @@ void Reassociate::BuildRankMap(Function &F) { // we cannot move. This ensures that the ranks for these instructions are // all different in the block. for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) - if (isUnmovableInstruction(I)) + if (mayBeMemoryDependent(*I)) ValueRankMap[&*I] = ++BBRank; } } @@ -313,21 +303,35 @@ unsigned Reassociate::getRank(Value *V) { // 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. - Type *Ty = V->getType(); - if ((!Ty->isIntegerTy() && !Ty->isFloatingPointTy()) || - (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I) && - !BinaryOperator::isFNeg(I))) + if (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(I) && + !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(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(RHS)) + return; + + if (isa(LHS) || RHSRank < LHSRank) + cast(I)->swapOperands(); +} + static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp) { - if (S1->getType()->isIntegerTy()) + if (S1->getType()->isIntOrIntVectorTy()) return BinaryOperator::CreateAdd(S1, S2, Name, InsertBefore); else { BinaryOperator *Res = @@ -339,7 +343,7 @@ static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name, static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp) { - if (S1->getType()->isIntegerTy()) + if (S1->getType()->isIntOrIntVectorTy()) return BinaryOperator::CreateMul(S1, S2, Name, InsertBefore); else { BinaryOperator *Res = @@ -351,7 +355,7 @@ static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name, static BinaryOperator *CreateNeg(Value *S1, const Twine &Name, Instruction *InsertBefore, Value *FlagsOp) { - if (S1->getType()->isIntegerTy()) + if (S1->getType()->isIntOrIntVectorTy()) return BinaryOperator::CreateNeg(S1, Name, InsertBefore); else { BinaryOperator *Res = BinaryOperator::CreateFNeg(S1, Name, InsertBefore); @@ -360,12 +364,11 @@ static BinaryOperator *CreateNeg(Value *S1, const Twine &Name, } } -/// LowerNegateToMultiply - Replace 0-X with X*-1. -/// +/// Replace 0-X with X*-1. static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) { Type *Ty = Neg->getType(); - Constant *NegOne = Ty->isIntegerTy() ? ConstantInt::getAllOnesValue(Ty) - : ConstantFP::get(Ty, -1.0); + Constant *NegOne = Ty->isIntOrIntVectorTy() ? + ConstantInt::getAllOnesValue(Ty) : ConstantFP::get(Ty, -1.0); BinaryOperator *Res = CreateMul(Neg->getOperand(1), NegOne, "", Neg, Neg); Neg->setOperand(1, Constant::getNullValue(Ty)); // Drop use of op. @@ -375,8 +378,8 @@ static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) { return Res; } -/// CarmichaelShift - Returns k such that lambda(2^Bitwidth) = 2^k, where lambda -/// is the Carmichael function. This means that x^(2^k) === 1 mod 2^Bitwidth for +/// Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael +/// function. This means that x^(2^k) === 1 mod 2^Bitwidth for /// every odd x, i.e. x^(2^k) = 1 for every odd x in Bitwidth-bit arithmetic. /// Note that 0 <= k < Bitwidth, and if Bitwidth > 3 then x^(2^k) = 0 for every /// even x in Bitwidth-bit arithmetic. @@ -386,7 +389,7 @@ static unsigned CarmichaelShift(unsigned Bitwidth) { return Bitwidth - 2; } -/// IncorporateWeight - Add the extra weight 'RHS' to the existing weight 'LHS', +/// Add the extra weight 'RHS' to the existing weight 'LHS', /// reducing the combined weight using any special properties of the operation. /// The existing weight LHS represents the computation X op X op ... op X where /// X occurs LHS times. The combined weight represents X op X op ... op X with @@ -468,7 +471,7 @@ static void IncorporateWeight(APInt &LHS, const APInt &RHS, unsigned Opcode) { typedef std::pair RepeatedValue; -/// LinearizeExprTree - Given an associative binary expression, return the leaf +/// Given an associative binary expression, return the leaf /// 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 @@ -562,7 +565,7 @@ static bool LinearizeExprTree(BinaryOperator *I, // ways to get to it. SmallVector, 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 @@ -599,7 +602,7 @@ static bool LinearizeExprTree(BinaryOperator *I, // 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; @@ -609,7 +612,7 @@ static bool LinearizeExprTree(BinaryOperator *I, 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. @@ -631,7 +634,7 @@ static bool LinearizeExprTree(BinaryOperator *I, // 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 @@ -660,7 +663,9 @@ static bool LinearizeExprTree(BinaryOperator *I, // 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(Op) || - cast(Op)->getOpcode() != Opcode) && + cast(Op)->getOpcode() != Opcode + || (isa(Op) && + !cast(Op)->hasUnsafeAlgebra())) && "Should have been handled above!"); assert(Op->hasOneUse() && "Has uses outside the expression tree!"); @@ -673,7 +678,7 @@ static bool LinearizeExprTree(BinaryOperator *I, BO = LowerNegateToMultiply(BO); DEBUG(dbgs() << *BO << '\n'); Worklist.push_back(std::make_pair(BO, Weight)); - MadeChange = true; + Changed = true; continue; } @@ -710,14 +715,14 @@ static bool LinearizeExprTree(BinaryOperator *I, 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))); + Ops.emplace_back(Identity, APInt(Bitwidth, 1)); } - return MadeChange; + return Changed; } -// RewriteExprTree - Now that the operands for this expression tree are -// linearized and optimized, emit them in-order. +/// Now that the operands for this expression tree are +/// linearized and optimized, emit them in-order. void Reassociate::RewriteExprTree(BinaryOperator *I, SmallVectorImpl &Ops) { assert(Ops.size() > 1 && "Single values should be used directly!"); @@ -846,7 +851,7 @@ void Reassociate::RewriteExprTree(BinaryOperator *I, Constant *Undef = UndefValue::get(I->getType()); NewOp = BinaryOperator::Create(Instruction::BinaryOps(Opcode), Undef, Undef, "", I); - if (NewOp->getType()->isFloatingPointTy()) + if (NewOp->getType()->isFPOrFPVectorTy()) NewOp->setFastMathFlags(I->getFastMathFlags()); } else { NewOp = NodesToRewrite.pop_back_val(); @@ -886,15 +891,18 @@ void Reassociate::RewriteExprTree(BinaryOperator *I, RedoInsts.insert(NodesToRewrite[i]); } -/// NegateValue - Insert instructions before the instruction pointed to by BI, +/// Insert instructions before the instruction pointed to by BI, /// that computes the negative version of the value specified. The negative /// 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(V)) - return ConstantExpr::getFNeg(C); - if (Constant *C = dyn_cast(V)) + if (Constant *C = dyn_cast(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 @@ -910,6 +918,10 @@ static Value *NegateValue(Value *V, Instruction *BI) { // Push the negates through the add. I->setOperand(0, NegateValue(I->getOperand(0), BI)); I->setOperand(1, NegateValue(I->getOperand(1), BI)); + if (I->getOpcode() == Instruction::Add) { + I->setHasNoUnsignedWrap(false); + I->setHasNoSignedWrap(false); + } // We must move the add instruction here, because the neg instructions do // not dominate the old add instruction in general. By moving it, we are @@ -941,6 +953,8 @@ static Value *NegateValue(Value *V, Instruction *BI) { if (Instruction *InstInput = dyn_cast(V)) { if (InvokeInst *II = dyn_cast(InstInput)) { InsertPt = II->getNormalDest()->begin(); + } else if (auto *CPI = dyn_cast(InstInput)) { + InsertPt = CPI->getNormalDest()->begin(); } else { InsertPt = InstInput; ++InsertPt; @@ -950,6 +964,12 @@ static Value *NegateValue(Value *V, Instruction *BI) { InsertPt = TheNeg->getParent()->getParent()->getEntryBlock().begin(); } TheNeg->moveBefore(InsertPt); + if (TheNeg->getOpcode() == Instruction::Sub) { + TheNeg->setHasNoUnsignedWrap(false); + TheNeg->setHasNoSignedWrap(false); + } else { + TheNeg->andIRFlags(BI); + } return TheNeg; } @@ -958,13 +978,16 @@ static Value *NegateValue(Value *V, Instruction *BI) { return CreateNeg(V, V->getName() + ".neg", BI, BI); } -/// ShouldBreakUpSubtract - Return true if we should break up this subtract of -/// X-Y into (X + -Y). +/// 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) || BinaryOperator::isFNeg(Sub)) return false; + // Don't breakup X - undef. + if (isa(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); @@ -984,9 +1007,8 @@ static bool ShouldBreakUpSubtract(Instruction *Sub) { 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. +/// 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 BinaryOperator *BreakUpSubtract(Instruction *Sub) { // Convert a subtract into an add and a neg instruction. This allows sub // instructions to be commuted with other add instructions. @@ -1008,9 +1030,8 @@ static BinaryOperator *BreakUpSubtract(Instruction *Sub) { return New; } -/// ConvertShiftToMul - If this is a shift of a reassociable multiply or is used -/// by one, change this into a multiply by a constant to assist with further -/// reassociation. +/// If this is a shift of a reassociable multiply or is used by one, change +/// this into a multiply by a constant to assist with further reassociation. static BinaryOperator *ConvertShiftToMul(Instruction *Shl) { Constant *MulCst = ConstantInt::get(Shl->getType(), 1); MulCst = ConstantExpr::getShl(MulCst, cast(Shl->getOperand(1))); @@ -1019,30 +1040,50 @@ static BinaryOperator *ConvertShiftToMul(Instruction *Shl) { 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(Shl)->hasNoSignedWrap(); + bool NUW = cast(Shl)->hasNoUnsignedWrap(); + if (NSW && NUW) + Mul->setHasNoSignedWrap(true); + Mul->setHasNoUnsignedWrap(NUW); return Mul; } -/// FindInOperandList - Scan backwards and forwards among values with the same -/// rank as element i to see if X exists. If X does not exist, return i. This -/// is useful when scanning for 'x' when we see '-x' because they both get the -/// same rank. +/// Scan backwards and forwards among values with the same rank as element i +/// to see if X exists. If X does not exist, return i. This is useful when +/// scanning for 'x' when we see '-x' because they both get the same rank. static unsigned FindInOperandList(SmallVectorImpl &Ops, unsigned i, 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(Ops[j].Op)) + if (Instruction *I2 = dyn_cast(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(Ops[j].Op)) + if (Instruction *I2 = dyn_cast(X)) + if (I1->isIdenticalTo(I2)) + return j; + } return i; } -/// EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together +/// Emit a tree of add instructions, summing Ops together /// and returning the result. Insert the tree before I. static Value *EmitAddTreeOfValues(Instruction *I, SmallVectorImpl &Ops){ @@ -1054,8 +1095,8 @@ static Value *EmitAddTreeOfValues(Instruction *I, return CreateAdd(V2, V1, "tmp", I, I); } -/// RemoveFactorFromExpression - If V is an expression tree that is a -/// multiplication sequence, and if this sequence contains a multiply by Factor, +/// If V is an expression tree that is a multiplication sequence, +/// and if this sequence contains a multiply by Factor, /// remove Factor from the tree and return the new tree. Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul); @@ -1127,8 +1168,8 @@ Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { return V; } -/// FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively -/// add its operands as factors, otherwise add V to the list of factors. +/// 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, @@ -1145,10 +1186,9 @@ static void FindSingleUseMultiplyFactors(Value *V, FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops); } -/// OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor' -/// instruction. This optimizes based on identities. If it can be reduced to -/// a single Value, it is returned, otherwise the Ops list is mutated as -/// necessary. +/// Optimize a series of operands to an 'and', 'or', or 'xor' instruction. +/// This optimizes based on identities. If it can be reduced to a single Value, +/// it is returned, otherwise the Ops list is mutated as necessary. static Value *OptimizeAndOrXor(unsigned Opcode, SmallVectorImpl &Ops) { // Scan the operand lists looking for X and ~X pairs, along with X,X pairs. @@ -1438,7 +1478,7 @@ Value *Reassociate::OptimizeXor(Instruction *I, return nullptr; } -/// OptimizeAdd - Optimize a series of operands to an 'add' instruction. This +/// Optimize a series of operands to an 'add' instruction. This /// optimizes based on identities. If it can be reduced to a single Value, it /// is returned, otherwise the Ops list is mutated as necessary. Value *Reassociate::OptimizeAdd(Instruction *I, @@ -1461,13 +1501,13 @@ Value *Reassociate::OptimizeAdd(Instruction *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. Type *Ty = TheOp->getType(); - Constant *C = Ty->isIntegerTy() ? ConstantInt::get(Ty, NumFound) - : ConstantFP::get(Ty, NumFound); + Constant *C = Ty->isIntOrIntVectorTy() ? + ConstantInt::get(Ty, NumFound) : ConstantFP::get(Ty, NumFound); Instruction *Mul = CreateMul(TheOp, C, "factor", I, I); // Now that we have inserted a multiply, optimize it. This allows us to @@ -1557,7 +1597,7 @@ Value *Reassociate::OptimizeAdd(Instruction *I, SmallPtrSet 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]; @@ -1599,7 +1639,7 @@ Value *Reassociate::OptimizeAdd(Instruction *I, // 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 @@ -1607,7 +1647,7 @@ Value *Reassociate::OptimizeAdd(Instruction *I, // from an expression will drop a use of maxocc, and this can cause // RemoveFactorFromExpression on successive values to behave differently. Instruction *DummyInst = - I->getType()->isIntegerTy() + I->getType()->isIntOrIntVectorTy() ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal) : BinaryOperator::CreateFAdd(MaxOccVal, MaxOccVal); @@ -1738,7 +1778,7 @@ static Value *buildMultiplyTree(IRBuilder<> &Builder, Value *LHS = Ops.pop_back_val(); do { - if (LHS->getType()->isIntegerTy()) + if (LHS->getType()->isIntOrIntVectorTy()) LHS = Builder.CreateMul(LHS, Ops.pop_back_val()); else LHS = Builder.CreateFMul(LHS, Ops.pop_back_val()); @@ -1891,8 +1931,7 @@ Value *Reassociate::OptimizeExpression(BinaryOperator *I, return nullptr; } -/// EraseInst - Zap the given instruction, adding interesting operands to the -/// work list. +/// Zap the given instruction, adding interesting operands to the work list. void Reassociate::EraseInst(Instruction *I) { assert(isInstructionTriviallyDead(I) && "Trivially dead instructions only!"); SmallVector Ops(I->op_begin(), I->op_end()); @@ -1908,13 +1947,91 @@ void Reassociate::EraseInst(Instruction *I) { // 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); } } -/// OptimizeInst - Inspect and optimize the given instruction. Note that erasing +// 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 fmul or fdiv instruction. + unsigned Opcode = I->getOpcode(); + if (Opcode != Instruction::FMul && Opcode != Instruction::FDiv) + return nullptr; + + auto *C0 = dyn_cast(I->getOperand(0)); + auto *C1 = dyn_cast(I->getOperand(1)); + + // Both operands are constant, let it get constant folded away. + if (C0 && C1) + return nullptr; + + ConstantFP *CF = C0 ? C0 : C1; + + // Must have one constant operand. + if (!CF) + return nullptr; + + // Must be a negative ConstantFP. + if (!CF->isNegative()) + return nullptr; + + // User must be a binary operator with one or more uses. + Instruction *User = I->user_back(); + if (!isa(User) || !User->hasNUsesOrMore(1)) + return nullptr; + + unsigned UserOpcode = User->getOpcode(); + if (UserOpcode != Instruction::FAdd && 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 = CF->getValueAPF(); + Val.changeSign(); + I->setOperand(C0 ? 0 : 1, 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(User)->swapOperands(); + + Value *Op0 = User->getOperand(0); + Value *Op1 = User->getOperand(1); + BinaryOperator *NI; + switch (UserOpcode) { + default: + llvm_unreachable("Unexpected Opcode!"); + case Instruction::FAdd: + NI = BinaryOperator::CreateFSub(Op0, Op1); + NI->setFastMathFlags(cast(User)->getFastMathFlags()); + break; + case Instruction::FSub: + NI = BinaryOperator::CreateFAdd(Op0, Op1); + NI->setFastMathFlags(cast(User)->getFastMathFlags()); + break; + } + + NI->insertBefore(User); + NI->setName(User->getName()); + User->replaceAllUsesWith(NI); + NI->setDebugLoc(I->getDebugLoc()); + RedoInsts.insert(I); + MadeChange = true; + return NI; +} + +/// Inspect and optimize the given instruction. Note that erasing /// instructions is not allowed. void Reassociate::OptimizeInst(Instruction *I) { // Only consider operations that we understand. @@ -1934,34 +2051,24 @@ void Reassociate::OptimizeInst(Instruction *I) { 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. - if (I->getOpcode() == Instruction::FMul || - I->getOpcode() == 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; - // FIXME: We should commute vector instructions as well. However, this - // requires further analysis to determine the effect on later passes. + // 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); - // Don't try to optimize vector instructions or anything that doesn't have - // unsafe algebra. - if (I->getType()->isVectorTy() || !I->hasUnsafeAlgebra()) - return; - } + // TODO: We should optimize vector Xor instructions, but they are + // currently unsupported. + if (I->getType()->isVectorTy() && I->getOpcode() == Instruction::Xor) + 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 @@ -2035,9 +2142,6 @@ void Reassociate::OptimizeInst(Instruction *I) { } void Reassociate::ReassociateExpression(BinaryOperator *I) { - assert(!I->getType()->isVectorTy() && - "Reassociation of vector instructions is not supported."); - // First, walk the expression tree, linearizing the tree, collecting the // operand information. SmallVector Tree; @@ -2060,7 +2164,7 @@ void Reassociate::ReassociateExpression(BinaryOperator *I) { // the vector. std::stable_sort(Ops.begin(), Ops.end()); - // OptimizeExpression - Now that we have the expression tree in a convenient + // 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)