X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FReassociate.cpp;h=b677523d70328d19d528635e541be02551cc0ef6;hb=f3bad3fece05e87f02d6d33af0534840d9df8801;hp=010f17aae0b6db428ffcd8a67a9b5800f9b7f5eb;hpb=423f19f2dadee9325766008b63c1faf3c644043b;p=oota-llvm.git diff --git a/lib/Transforms/Scalar/Reassociate.cpp b/lib/Transforms/Scalar/Reassociate.cpp index 010f17aae0b..b677523d703 100644 --- a/lib/Transforms/Scalar/Reassociate.cpp +++ b/lib/Transforms/Scalar/Reassociate.cpp @@ -20,29 +20,29 @@ // //===----------------------------------------------------------------------===// -#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" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Pass.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/STLExtras.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" -#include "llvm/ADT/DenseMap.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Utils/Local.h" #include using namespace llvm; -STATISTIC(NumLinear , "Number of insts linearized"); +#define DEBUG_TYPE "reassociate" + STATISTIC(NumChanged, "Number of insts reassociated"); STATISTIC(NumAnnihil, "Number of expr tree annihilated"); STATISTIC(NumFactor , "Number of multiplies factored"); @@ -59,7 +59,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(); @@ -67,7 +67,7 @@ static void PrintOps(Instruction *I, const SmallVectorImpl &Ops) { << *Ops[0].Op->getType() << '\t'; for (unsigned i = 0, e = Ops.size(); i != e; ++i) { dbgs() << "[ "; - WriteAsOperand(dbgs(), Ops[i].Op, false, M); + Ops[i].Op->printAsOperand(dbgs(), false, M); dbgs() << ", #" << Ops[i].Rank << "] "; } } @@ -110,14 +110,57 @@ namespace { } }; }; + + /// Utility class representing a non-constant Xor-operand. We classify + /// non-constant Xor-Operands into two categories: + /// C1) The operand is in the form "X & C", where C is a constant and C != ~0 + /// C2) + /// C2.1) The operand is in the form of "X | C", where C is a non-zero + /// constant. + /// C2.2) Any operand E which doesn't fall into C1 and C2.1, we view this + /// operand as "E | 0" + class XorOpnd { + public: + XorOpnd(Value *V); + + bool isInvalid() const { return SymbolicPart == nullptr; } + bool isOrExpr() const { return isOr; } + Value *getValue() const { return OrigVal; } + Value *getSymbolicPart() const { return SymbolicPart; } + unsigned getSymbolicRank() const { return SymbolicRank; } + const APInt &getConstPart() const { return ConstPart; } + + void Invalidate() { SymbolicPart = OrigVal = nullptr; } + void setSymbolicRank(unsigned R) { SymbolicRank = R; } + + // Sort the XorOpnd-Pointer in ascending order of symbolic-value-rank. + // The purpose is twofold: + // 1) Cluster together the operands sharing the same symbolic-value. + // 2) Operand having smaller symbolic-value-rank is permuted earlier, which + // could potentially shorten crital path, and expose more loop-invariants. + // Note that values' rank are basically defined in RPO order (FIXME). + // So, if Rank(X) < Rank(Y) < Rank(Z), it means X is defined earlier + // than Y which is defined earlier than Z. Permute "x | 1", "Y & 2", + // "z" in the order of X-Y-Z is better than any other orders. + struct PtrSortFunctor { + bool operator()(XorOpnd * const &LHS, XorOpnd * const &RHS) { + return LHS->getSymbolicRank() < RHS->getSymbolicRank(); + } + }; + private: + Value *OrigVal; + Value *SymbolicPart; + APInt ConstPart; + unsigned SymbolicRank; + bool isOr; + }; } namespace { class Reassociate : public FunctionPass { DenseMap RankMap; DenseMap, unsigned> ValueRankMap; - SmallVector RedoInsts; - SmallVector DeadInsts; + SetVector > RedoInsts; bool MadeChange; public: static char ID; // Pass identification, replacement for typeid @@ -125,34 +168,64 @@ namespace { initializeReassociatePass(*PassRegistry::getPassRegistry()); } - bool runOnFunction(Function &F); + bool runOnFunction(Function &F) override; - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); } private: void BuildRankMap(Function &F); unsigned getRank(Value *V); - Value *ReassociateExpression(BinaryOperator *I); - void RewriteExprTree(BinaryOperator *I, SmallVectorImpl &Ops, - unsigned Idx = 0); + void canonicalizeOperands(Instruction *I); + void ReassociateExpression(BinaryOperator *I); + void RewriteExprTree(BinaryOperator *I, SmallVectorImpl &Ops); Value *OptimizeExpression(BinaryOperator *I, SmallVectorImpl &Ops); Value *OptimizeAdd(Instruction *I, SmallVectorImpl &Ops); + Value *OptimizeXor(Instruction *I, SmallVectorImpl &Ops); + bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, APInt &ConstOpnd, + Value *&Res); + bool CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2, + APInt &ConstOpnd, Value *&Res); bool collectMultiplyFactors(SmallVectorImpl &Ops, SmallVectorImpl &Factors); Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder, SmallVectorImpl &Factors); Value *OptimizeMul(BinaryOperator *I, SmallVectorImpl &Ops); - void LinearizeExprTree(BinaryOperator *I, SmallVectorImpl &Ops); - void LinearizeExpr(BinaryOperator *I); Value *RemoveFactorFromExpression(Value *V, Value *Factor); - void ReassociateInst(BasicBlock::iterator &BBI); - - void RemoveDeadBinaryOp(Value *V); + void EraseInst(Instruction *I); + void OptimizeInst(Instruction *I); + Instruction *canonicalizeNegConstExpr(Instruction *I); }; } +XorOpnd::XorOpnd(Value *V) { + assert(!isa(V) && "No ConstantInt"); + OrigVal = V; + Instruction *I = dyn_cast(V); + SymbolicRank = 0; + + if (I && (I->getOpcode() == Instruction::Or || + I->getOpcode() == Instruction::And)) { + Value *V0 = I->getOperand(0); + Value *V1 = I->getOperand(1); + if (isa(V0)) + std::swap(V0, V1); + + if (ConstantInt *C = dyn_cast(V1)) { + ConstPart = C->getValue(); + SymbolicPart = V0; + isOr = (I->getOpcode() == Instruction::Or); + return; + } + } + + // view the operand as "V | 0" + SymbolicPart = V; + ConstPart = APInt::getNullValue(V->getType()->getIntegerBitWidth()); + isOr = true; +} + char Reassociate::ID = 0; INITIALIZE_PASS(Reassociate, "reassociate", "Reassociate expressions", false, false) @@ -160,43 +233,57 @@ INITIALIZE_PASS(Reassociate, "reassociate", // Public interface to the Reassociate pass FunctionPass *llvm::createReassociatePass() { return new Reassociate(); } -void Reassociate::RemoveDeadBinaryOp(Value *V) { - Instruction *Op = dyn_cast(V); - if (!Op || !isa(Op)) - return; - - Value *LHS = Op->getOperand(0), *RHS = Op->getOperand(1); +/// 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 && + (!isa(V) || + cast(V)->hasUnsafeAlgebra())) + return cast(V); + return nullptr; +} - ValueRankMap.erase(Op); - DeadInsts.push_back(Op); - RemoveDeadBinaryOp(LHS); - RemoveDeadBinaryOp(RHS); +static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode1, + unsigned Opcode2) { + if (V->hasOneUse() && isa(V) && + (cast(V)->getOpcode() == Opcode1 || + cast(V)->getOpcode() == Opcode2) && + (!isa(V) || + cast(V)->hasUnsafeAlgebra())) + return cast(V); + return nullptr; } static bool isUnmovableInstruction(Instruction *I) { - if (I->getOpcode() == Instruction::PHI || - I->getOpcode() == Instruction::LandingPad || - I->getOpcode() == Instruction::Alloca || - I->getOpcode() == Instruction::Load || - I->getOpcode() == Instruction::Invoke || - (I->getOpcode() == Instruction::Call && - !isa(I)) || - I->getOpcode() == Instruction::UDiv || - I->getOpcode() == Instruction::SDiv || - I->getOpcode() == Instruction::FDiv || - I->getOpcode() == Instruction::URem || - I->getOpcode() == Instruction::SRem || - I->getOpcode() == Instruction::FRem) + 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; - return false; + 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(), @@ -215,7 +302,7 @@ void Reassociate::BuildRankMap(Function &F) { unsigned Reassociate::getRank(Value *V) { Instruction *I = dyn_cast(V); - if (I == 0) { + if (!I) { if (isa(V)) return ValueRankMap[V]; // Function argument. return 0; // Otherwise it's a global or constant, rank 0. } @@ -234,217 +321,606 @@ 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. - if (!I->getType()->isIntegerTy() || - (!BinaryOperator::isNot(I) && !BinaryOperator::isNeg(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; } -/// isReassociableOp - 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() || V->use_empty()) && isa(V) && - cast(V)->getOpcode() == Opcode) - return cast(V); - return 0; +// 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(); } -/// LowerNegateToMultiply - Replace 0-X with X*-1. -/// -static Instruction *LowerNegateToMultiply(Instruction *Neg, - DenseMap, unsigned> &ValueRankMap) { - Constant *Cst = Constant::getAllOnesValue(Neg->getType()); +static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name, + Instruction *InsertBefore, Value *FlagsOp) { + if (S1->getType()->isIntOrIntVectorTy()) + return BinaryOperator::CreateAdd(S1, S2, Name, InsertBefore); + else { + BinaryOperator *Res = + BinaryOperator::CreateFAdd(S1, S2, Name, InsertBefore); + Res->setFastMathFlags(cast(FlagsOp)->getFastMathFlags()); + return Res; + } +} + +static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name, + Instruction *InsertBefore, Value *FlagsOp) { + if (S1->getType()->isIntOrIntVectorTy()) + return BinaryOperator::CreateMul(S1, S2, Name, InsertBefore); + else { + BinaryOperator *Res = + BinaryOperator::CreateFMul(S1, S2, Name, InsertBefore); + Res->setFastMathFlags(cast(FlagsOp)->getFastMathFlags()); + return Res; + } +} - Instruction *Res = BinaryOperator::CreateMul(Neg->getOperand(1), Cst, "",Neg); - ValueRankMap.erase(Neg); +static BinaryOperator *CreateNeg(Value *S1, const Twine &Name, + Instruction *InsertBefore, Value *FlagsOp) { + if (S1->getType()->isIntOrIntVectorTy()) + return BinaryOperator::CreateNeg(S1, Name, InsertBefore); + else { + BinaryOperator *Res = BinaryOperator::CreateFNeg(S1, Name, InsertBefore); + Res->setFastMathFlags(cast(FlagsOp)->getFastMathFlags()); + return Res; + } +} + +/// Replace 0-X with X*-1. +static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) { + Type *Ty = Neg->getType(); + 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. Res->takeName(Neg); Neg->replaceAllUsesWith(Res); Res->setDebugLoc(Neg->getDebugLoc()); - Neg->eraseFromParent(); return Res; } -// Given an expression of the form '(A+B)+(D+C)', turn it into '(((A+B)+C)+D)'. -// Note that if D is also part of the expression tree that we recurse to -// linearize it as well. Besides that case, this does not recurse into A,B, or -// C. -void Reassociate::LinearizeExpr(BinaryOperator *I) { - BinaryOperator *LHS = isReassociableOp(I->getOperand(0), I->getOpcode()); - BinaryOperator *RHS = isReassociableOp(I->getOperand(1), I->getOpcode()); - assert(LHS && RHS && "Not an expression that needs linearization?"); - - DEBUG({ - dbgs() << "Linear:\n"; - dbgs() << '\t' << *LHS << "\t\n" << *RHS << "\t\n" << *I << '\n'; - }); - - // Move the RHS instruction to live immediately before I, avoiding breaking - // dominator properties. - RHS->moveBefore(I); - - // Move operands around to do the linearization. - I->setOperand(1, RHS->getOperand(0)); - 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(dbgs() << "Linearized: " << *I << '\n'); +/// 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. +static unsigned CarmichaelShift(unsigned Bitwidth) { + if (Bitwidth < 3) + return Bitwidth - 1; + return Bitwidth - 2; +} + +/// 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 +/// X occurring LHS + RHS times. If op is "Xor" for example then the combined +/// operation is equivalent to X if LHS + RHS is odd, or 0 if LHS + RHS is even; +/// the routine returns 1 in LHS in the first case, and 0 in LHS in the second. +static void IncorporateWeight(APInt &LHS, const APInt &RHS, unsigned Opcode) { + // If we were working with infinite precision arithmetic then the combined + // weight would be LHS + RHS. But we are using finite precision arithmetic, + // and the APInt sum LHS + RHS may not be correct if it wraps (it is correct + // for nilpotent operations and addition, but not for idempotent operations + // and multiplication), so it is important to correctly reduce the combined + // weight back into range if wrapping would be wrong. + + // If RHS is zero then the weight didn't change. + if (RHS.isMinValue()) + return; + // If LHS is zero then the combined weight is RHS. + if (LHS.isMinValue()) { + LHS = RHS; + return; + } + // From this point on we know that neither LHS nor RHS is zero. + + if (Instruction::isIdempotent(Opcode)) { + // Idempotent means X op X === X, so any non-zero weight is equivalent to a + // weight of 1. Keeping weights at zero or one also means that wrapping is + // not a problem. + assert(LHS == 1 && RHS == 1 && "Weights not reduced!"); + return; // Return a weight of 1. + } + if (Instruction::isNilpotent(Opcode)) { + // Nilpotent means X op X === 0, so reduce weights modulo 2. + assert(LHS == 1 && RHS == 1 && "Weights not reduced!"); + LHS = 0; // 1 + 1 === 0 modulo 2. + return; + } + if (Opcode == Instruction::Add || Opcode == Instruction::FAdd) { + // TODO: Reduce the weight by exploiting nsw/nuw? + LHS += RHS; + return; + } - // If D is part of this expression tree, tail recurse. - if (isReassociableOp(I->getOperand(1), I->getOpcode())) - LinearizeExpr(I); + assert((Opcode == Instruction::Mul || Opcode == Instruction::FMul) && + "Unknown associative operation!"); + unsigned Bitwidth = LHS.getBitWidth(); + // If CM is the Carmichael number then a weight W satisfying W >= CM+Bitwidth + // can be replaced with W-CM. That's because x^W=x^(W-CM) for every Bitwidth + // bit number x, since either x is odd in which case x^CM = 1, or x is even in + // which case both x^W and x^(W - CM) are zero. By subtracting off multiples + // of CM like this weights can always be reduced to the range [0, CM+Bitwidth) + // which by a happy accident means that they can always be represented using + // Bitwidth bits. + // TODO: Reduce the weight by exploiting nsw/nuw? (Could do much better than + // the Carmichael number). + if (Bitwidth > 3) { + /// CM - The value of Carmichael's lambda function. + APInt CM = APInt::getOneBitSet(Bitwidth, CarmichaelShift(Bitwidth)); + // Any weight W >= Threshold can be replaced with W - CM. + APInt Threshold = CM + Bitwidth; + assert(LHS.ult(Threshold) && RHS.ult(Threshold) && "Weights not reduced!"); + // For Bitwidth 4 or more the following sum does not overflow. + LHS += RHS; + while (LHS.uge(Threshold)) + LHS -= CM; + } else { + // To avoid problems with overflow do everything the same as above but using + // a larger type. + unsigned CM = 1U << CarmichaelShift(Bitwidth); + unsigned Threshold = CM + Bitwidth; + assert(LHS.getZExtValue() < Threshold && RHS.getZExtValue() < Threshold && + "Weights not reduced!"); + unsigned Total = LHS.getZExtValue() + RHS.getZExtValue(); + while (Total >= Threshold) + Total -= CM; + LHS = Total; + } } -/// 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 expression (((a+b)+c)+d), and collects information about the -/// rank of the non-tree operands. +typedef std::pair RepeatedValue; + +/// 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 +/// op +/// (Ops[1].first op Ops[1].first op ... Ops[1].first) <- Ops[1].second times +/// op +/// ... +/// op +/// (Ops[N].first op Ops[N].first op ... Ops[N].first) <- Ops[N].second times +/// +/// Note that the values Ops[0].first, ..., Ops[N].first are all distinct. +/// +/// This routine may modify the function, in which case it returns 'true'. The +/// changes it makes may well be destructive, changing the value computed by 'I' +/// to something completely different. Thus if the routine returns 'true' then +/// you MUST either replace I with a new expression computed from the Ops array, +/// or use RewriteExprTree to put the values back in. /// -/// NOTE: These intentionally destroys the expression tree operands (turning -/// them into undef values) to reduce #uses of the values. This means that the -/// caller MUST use something like RewriteExprTree to put the values back in. +/// A leaf node is either not a binary operation of the same kind as the root +/// node 'I' (i.e. is not a binary operator at all, or is, but with a different +/// opcode), or is the same kind of binary operator but has a use which either +/// does not belong to the expression, or does belong to the expression but is +/// a leaf node. Every leaf node has at least one use that is a non-leaf node +/// of the expression, while for non-leaf nodes (except for the root 'I') every +/// use is a non-leaf node of the expression. /// -void Reassociate::LinearizeExprTree(BinaryOperator *I, - SmallVectorImpl &Ops) { - Value *LHS = I->getOperand(0), *RHS = I->getOperand(1); +/// For example: +/// expression graph node names +/// +/// + | I +/// / \ | +/// + + | A, B +/// / \ / \ | +/// * + * | C, D, E +/// / \ / \ / \ | +/// + * | F, G +/// +/// The leaf nodes are C, E, F and G. The Ops array will contain (maybe not in +/// that order) (C, 1), (E, 1), (F, 2), (G, 2). +/// +/// The expression is maximal: if some instruction is a binary operator of the +/// same kind as 'I', and all of its uses are non-leaf nodes of the expression, +/// then the instruction also belongs to the expression, is not a leaf node of +/// it, and its operands also belong to the expression (but may be leaf nodes). +/// +/// NOTE: This routine will set operands of non-leaf non-root nodes to undef in +/// order to ensure that every non-root node in the expression has *exactly one* +/// use by a non-leaf node of the expression. This destruction means that the +/// caller MUST either replace 'I' with a new expression or use something like +/// RewriteExprTree to put the values back in if the routine indicates that it +/// made a change by returning 'true'. +/// +/// In the above example either the right operand of A or the left operand of B +/// will be replaced by undef. If it is B's operand then this gives: +/// +/// + | I +/// / \ | +/// + + | A, B - operand of B replaced with undef +/// / \ \ | +/// * + * | C, D, E +/// / \ / \ / \ | +/// + * | F, G +/// +/// Note that such undef operands can only be reached by passing through 'I'. +/// For example, if you visit operands recursively starting from a leaf node +/// then you will never see such an undef operand unless you get back to 'I', +/// which requires passing through a phi node. +/// +/// Note that this routine may also mutate binary operators of the wrong type +/// that have all uses inside the expression (i.e. only used by non-leaf nodes +/// of the expression) if it can turn them into binary operators of the right +/// type and thus make the expression bigger. + +static bool LinearizeExprTree(BinaryOperator *I, + SmallVectorImpl &Ops) { + DEBUG(dbgs() << "LINEARIZE: " << *I << '\n'); + unsigned Bitwidth = I->getType()->getScalarType()->getPrimitiveSizeInBits(); unsigned Opcode = I->getOpcode(); + assert(I->isAssociative() && I->isCommutative() && + "Expected an associative and commutative operation!"); + + // 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 + // the number of times that operand occurs in the linearized expression). + // For example, if I = X + A, where X = A + B, then I, X and B have weight 1 + // while A has weight two. + + // Worklist of non-leaf nodes (their operands are in the expression too) along + // with their weights, representing a certain number of paths to the operator. + // If an operator occurs in the worklist multiple times then we found multiple + // ways to get to it. + SmallVector, 8> Worklist; // (Op, Weight) + Worklist.push_back(std::make_pair(I, APInt(Bitwidth, 1))); + 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 + // some uses that are not inside the expression. For example, in I = X + X, + // X = A + B, the value X has two uses (by I) that are in the expression. If + // X has any other uses, for example in a return instruction, then we consider + // X to be a leaf, and won't analyze it further. When we first visit a value, + // if it has more than one use then at first we conservatively consider it to + // be a leaf. Later, as the expression is explored, we may discover some more + // uses of the value from inside the expression. If all uses turn out to be + // from within the expression (and the value is a binary operator of the right + // kind) then the value is no longer considered to be a leaf, and its operands + // are explored. + + // Leaves - Keeps track of the set of putative leaves as well as the number of + // paths to each leaf seen so far. + typedef DenseMap LeafMap; + LeafMap Leaves; // Leaf -> Total weight so far. + SmallVector LeafOrder; // Ensure deterministic leaf output order. - // First step, linearize the expression if it is in ((A+B)+(C+D)) form. - BinaryOperator *LHSBO = isReassociableOp(LHS, Opcode); - BinaryOperator *RHSBO = isReassociableOp(RHS, Opcode); - - // If this is a multiply expression tree and it contains internal negations, - // transform them into multiplies by -1 so they can be reassociated. - if (I->getOpcode() == Instruction::Mul) { - if (!LHSBO && LHS->hasOneUse() && BinaryOperator::isNeg(LHS)) { - LHS = LowerNegateToMultiply(cast(LHS), ValueRankMap); - LHSBO = isReassociableOp(LHS, Opcode); - } - if (!RHSBO && RHS->hasOneUse() && BinaryOperator::isNeg(RHS)) { - RHS = LowerNegateToMultiply(cast(RHS), ValueRankMap); - RHSBO = isReassociableOp(RHS, Opcode); - } - } +#ifndef NDEBUG + SmallPtrSet Visited; // For sanity checking the iteration scheme. +#endif + while (!Worklist.empty()) { + std::pair P = Worklist.pop_back_val(); + I = P.first; // We examine the operands of this binary operator. + + for (unsigned OpIdx = 0; OpIdx < 2; ++OpIdx) { // Visit operands. + Value *Op = I->getOperand(OpIdx); + APInt Weight = P.second; // Number of paths to this operand. + DEBUG(dbgs() << "OPERAND: " << *Op << " (" << Weight << ")\n"); + assert(!Op->use_empty() && "No uses, so how did we get to it?!"); + + // 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).second && "Not first visit!"); + DEBUG(dbgs() << "DIRECT ADD: " << *Op << " (" << Weight << ")\n"); + Worklist.push_back(std::make_pair(BO, Weight)); + continue; + } - if (!LHSBO) { - if (!RHSBO) { - // Neither the LHS or RHS as part of the tree, thus this is a leaf. As - // such, just remember these operands and their rank. - Ops.push_back(ValueEntry(getRank(LHS), LHS)); - Ops.push_back(ValueEntry(getRank(RHS), RHS)); + // Appears to be a leaf. Is the operand already in the set of leaves? + 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).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. + DEBUG(dbgs() << "ADD USES LEAF: " << *Op << " (" << Weight << ")\n"); + LeafOrder.push_back(Op); + Leaves[Op] = Weight; + continue; + } + // No uses outside the expression, try morphing it. + } else if (It != Leaves.end()) { + // Already in the leaf map. + assert(Visited.count(Op) && "In leaf map but not visited!"); + + // 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!"); + I->setOperand(OpIdx, UndefValue::get(I->getType())); + 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 + // to the expression, then no longer consider it to be a leaf and add + // its operands to the expression. + if (BinaryOperator *BO = isReassociableOp(Op, Opcode)) { + DEBUG(dbgs() << "UNLEAF: " << *Op << " (" << It->second << ")\n"); + Worklist.push_back(std::make_pair(BO, It->second)); + Leaves.erase(It); + continue; + } +#endif - // Clear the leaves out. - I->setOperand(0, UndefValue::get(I->getType())); - I->setOperand(1, UndefValue::get(I->getType())); - return; - } + // If we still have uses that are not accounted for by the expression + // then it is not safe to modify the value. + if (!Op->hasOneUse()) + continue; - // Turn X+(Y+Z) -> (Y+Z)+X - std::swap(LHSBO, RHSBO); - std::swap(LHS, RHS); - bool Success = !I->swapOperands(); - assert(Success && "swapOperands failed"); - (void)Success; - MadeChange = true; - } else if (RHSBO) { - // 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(I->getOperand(0)); - RHS = I->getOperand(1); - RHSBO = 0; - } + // No uses outside the expression, try morphing it. + Weight = It->second; + Leaves.erase(It); // Since the value may be morphed below. + } - // Okay, now we know that the LHS is a nested expression and that the RHS is - // not. Perform reassociation. - assert(!isReassociableOp(RHS, Opcode) && "LinearizeExpr failed!"); + // At this point we have a value which, first of all, is not a binary + // expression of the right kind, and secondly, is only used inside the + // 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 + || (isa(Op) && + !cast(Op)->hasUnsafeAlgebra())) && + "Should have been handled above!"); + assert(Op->hasOneUse() && "Has uses outside the expression tree!"); + + // If this is a multiply expression, turn any internal negations into + // multiplies by -1 so they can be reassociated. + if (BinaryOperator *BO = dyn_cast(Op)) + if ((Opcode == Instruction::Mul && BinaryOperator::isNeg(BO)) || + (Opcode == Instruction::FMul && BinaryOperator::isFNeg(BO))) { + DEBUG(dbgs() << "MORPH LEAF: " << *Op << " (" << Weight << ") TO "); + BO = LowerNegateToMultiply(BO); + DEBUG(dbgs() << *BO << '\n'); + Worklist.push_back(std::make_pair(BO, Weight)); + Changed = true; + continue; + } - // Move LHS right before I to make sure that the tree expression dominates all - // values. - LHSBO->moveBefore(I); + // Failed to morph into an expression of the right type. This really is + // a leaf. + DEBUG(dbgs() << "ADD LEAF: " << *Op << " (" << Weight << ")\n"); + assert(!isReassociableOp(Op, Opcode) && "Value was morphed?"); + LeafOrder.push_back(Op); + Leaves[Op] = Weight; + } + } - // Linearize the expression tree on the LHS. - LinearizeExprTree(LHSBO, Ops); + // The leaves, repeated according to their weights, represent the linearized + // form of the expression. + for (unsigned i = 0, e = LeafOrder.size(); i != e; ++i) { + Value *V = LeafOrder[i]; + LeafMap::iterator It = Leaves.find(V); + if (It == Leaves.end()) + // Node initially thought to be a leaf wasn't. + continue; + assert(!isReassociableOp(V, Opcode) && "Shouldn't be a leaf!"); + APInt Weight = It->second; + if (Weight.isMinValue()) + // Leaf already output or weight reduction eliminated it. + continue; + // Ensure the leaf is only output once. + It->second = 0; + Ops.push_back(std::make_pair(V, Weight)); + } - // Remember the RHS operand and its rank. - Ops.push_back(ValueEntry(getRank(RHS), RHS)); + // 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))); + } - // Clear the RHS leaf out. - I->setOperand(1, UndefValue::get(I->getType())); + return Changed; } -// RewriteExprTree - Now that the operands for this expression tree are -// linearized and optimized, emit them in-order. This function is written to be -// tail recursive. +/// Now that the operands for this expression tree are +/// linearized and optimized, emit them in-order. void Reassociate::RewriteExprTree(BinaryOperator *I, - SmallVectorImpl &Ops, - unsigned i) { - if (i+2 == Ops.size()) { - if (I->getOperand(0) != Ops[i].Op || - I->getOperand(1) != Ops[i+1].Op) { - Value *OldLHS = I->getOperand(0); - DEBUG(dbgs() << "RA: " << *I << '\n'); - I->setOperand(0, Ops[i].Op); - I->setOperand(1, Ops[i+1].Op); - - // 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'); + SmallVectorImpl &Ops) { + assert(Ops.size() > 1 && "Single values should be used directly!"); + + // Since our optimizations should never increase the number of operations, the + // new expression can usually be written reusing the existing binary operators + // from the original expression tree, without creating any new instructions, + // though the rewritten expression may have a completely different topology. + // We take care to not change anything if the new expression will be the same + // as the original. If more than trivial changes (like commuting operands) + // were made then we are obliged to clear out any optional subclass data like + // nsw flags. + + /// NodesToRewrite - Nodes from the original expression available for writing + /// the new expression into. + SmallVector NodesToRewrite; + unsigned Opcode = I->getOpcode(); + BinaryOperator *Op = I; + + /// NotRewritable - The operands being written will be the leaves of the new + /// expression and must not be used as inner nodes (via NodesToRewrite) by + /// mistake. Inner nodes are always reassociable, and usually leaves are not + /// (if they were they would have been incorporated into the expression and so + /// would not be leaves), so most of the time there is no danger of this. But + /// in rare cases a leaf may become reassociable if an optimization kills uses + /// of it, or it may momentarily become reassociable during rewriting (below) + /// due it being removed as an operand of one of its uses. Ensure that misuse + /// of leaf nodes as inner nodes cannot occur by remembering all of the future + /// leaves and refusing to reuse any of them as inner nodes. + SmallPtrSet NotRewritable; + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + NotRewritable.insert(Ops[i].Op); + + // 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 = nullptr; + 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. + if (i+2 == Ops.size()) { + Value *NewLHS = Ops[i].Op; + Value *NewRHS = Ops[i+1].Op; + Value *OldLHS = Op->getOperand(0); + Value *OldRHS = Op->getOperand(1); + + if (NewLHS == OldLHS && NewRHS == OldRHS) + // Nothing changed, leave it alone. + break; + + if (NewLHS == OldRHS && NewRHS == OldLHS) { + // The order of the operands was reversed. Swap them. + DEBUG(dbgs() << "RA: " << *Op << '\n'); + Op->swapOperands(); + DEBUG(dbgs() << "TO: " << *Op << '\n'); + MadeChange = true; + ++NumChanged; + break; + } + + // The new operation differs non-trivially from the original. Overwrite + // the old operands with the new ones. + DEBUG(dbgs() << "RA: " << *Op << '\n'); + if (NewLHS != OldLHS) { + BinaryOperator *BO = isReassociableOp(OldLHS, Opcode); + if (BO && !NotRewritable.count(BO)) + NodesToRewrite.push_back(BO); + Op->setOperand(0, NewLHS); + } + if (NewRHS != OldRHS) { + BinaryOperator *BO = isReassociableOp(OldRHS, Opcode); + if (BO && !NotRewritable.count(BO)) + NodesToRewrite.push_back(BO); + Op->setOperand(1, NewRHS); + } + DEBUG(dbgs() << "TO: " << *Op << '\n'); + + ExpressionChanged = Op; MadeChange = true; ++NumChanged; - // If we reassociated a tree to fewer operands (e.g. (1+a+2) -> (a+3) - // delete the extra, now dead, nodes. - RemoveDeadBinaryOp(OldLHS); + break; + } + + // Not the last operation. The left-hand side will be a sub-expression + // while the right-hand side will be the current element of Ops. + Value *NewRHS = Ops[i].Op; + if (NewRHS != Op->getOperand(1)) { + DEBUG(dbgs() << "RA: " << *Op << '\n'); + if (NewRHS == Op->getOperand(0)) { + // The new right-hand side was already present as the left operand. If + // we are lucky then swapping the operands will sort out both of them. + Op->swapOperands(); + } else { + // Overwrite with the new right-hand side. + BinaryOperator *BO = isReassociableOp(Op->getOperand(1), Opcode); + if (BO && !NotRewritable.count(BO)) + NodesToRewrite.push_back(BO); + Op->setOperand(1, NewRHS); + ExpressionChanged = Op; + } + DEBUG(dbgs() << "TO: " << *Op << '\n'); + MadeChange = true; + ++NumChanged; } - return; - } - assert(i+2 < Ops.size() && "Ops index out of range!"); - if (I->getOperand(1) != Ops[i].Op) { - DEBUG(dbgs() << "RA: " << *I << '\n'); - I->setOperand(1, Ops[i].Op); + // Now deal with the left-hand side. If this is already an operation node + // from the original expression then just rewrite the rest of the expression + // into it. + BinaryOperator *BO = isReassociableOp(Op->getOperand(0), Opcode); + if (BO && !NotRewritable.count(BO)) { + Op = BO; + continue; + } - // Conservatively clear all the optional flags, which may not hold - // after the reassociation. - I->clearSubclassOptionalData(); + // Otherwise, grab a spare node from the original expression and use that as + // 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); + if (NewOp->getType()->isFPOrFPVectorTy()) + NewOp->setFastMathFlags(I->getFastMathFlags()); + } else { + NewOp = NodesToRewrite.pop_back_val(); + } - DEBUG(dbgs() << "TO: " << *I << '\n'); + DEBUG(dbgs() << "RA: " << *Op << '\n'); + Op->setOperand(0, NewOp); + DEBUG(dbgs() << "TO: " << *Op << '\n'); + ExpressionChanged = Op; MadeChange = true; ++NumChanged; + Op = NewOp; } - BinaryOperator *LHS = cast(I->getOperand(0)); - assert(LHS->getOpcode() == I->getOpcode() && - "Improper expression tree!"); - - // Compactify the tree instructions together with each other to guarantee - // that the expression tree is dominated by all of Ops. - LHS->moveBefore(I); - RewriteExprTree(LHS, Ops, i+1); + // If the expression changed non-trivially then clear out all subclass data + // 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 { + // Preserve FastMathFlags. + if (isa(I)) { + FastMathFlags Flags = I->getFastMathFlags(); + ExpressionChanged->clearSubclassOptionalData(); + ExpressionChanged->setFastMathFlags(Flags); + } else + ExpressionChanged->clearSubclassOptionalData(); + + if (ExpressionChanged == I) + break; + ExpressionChanged->moveBefore(I); + ExpressionChanged = cast(*ExpressionChanged->user_begin()); + } while (1); + + // Throw away any left over nodes from the original expression. + for (unsigned i = 0, e = NodesToRewrite.size(); i != e; ++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 (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 @@ -455,27 +931,27 @@ static Value *NegateValue(Value *V, Instruction *BI) { // the constants. We assume that instcombine will clean up the mess later if // we introduce tons of unnecessary negation instructions. // - if (Instruction *I = dyn_cast(V)) - if (I->getOpcode() == Instruction::Add && I->hasOneUse()) { - // Push the negates through the add. - I->setOperand(0, NegateValue(I->getOperand(0), BI)); - I->setOperand(1, NegateValue(I->getOperand(1), BI)); - - // 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 - // assured that the neg instructions we just inserted dominate the - // instruction we are about to insert after them. - // - I->moveBefore(BI); - I->setName(I->getName()+".neg"); - return I; - } + if (BinaryOperator *I = + isReassociableOp(V, Instruction::Add, Instruction::FAdd)) { + // Push the negates through the add. + I->setOperand(0, NegateValue(I->getOperand(0), BI)); + I->setOperand(1, NegateValue(I->getOperand(1), BI)); + + // 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 + // assured that the neg instructions we just inserted dominate the + // instruction we are about to insert after them. + // + I->moveBefore(BI); + I->setName(I->getName()+".neg"); + return I; + } // 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){ - User *U = *UI; - if (!BinaryOperator::isNeg(U)) continue; + for (User *U : V->users()) { + if (!BinaryOperator::isNeg(U) && !BinaryOperator::isFNeg(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 @@ -505,37 +981,41 @@ static Value *NegateValue(Value *V, Instruction *BI) { // Insert a 'neg' instruction that subtracts the value from zero to get the // negation. - return BinaryOperator::CreateNeg(V, V->getName() + ".neg", 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)) + 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. - if (isReassociableOp(Sub->getOperand(0), Instruction::Add) || - isReassociableOp(Sub->getOperand(0), Instruction::Sub)) + Value *V0 = Sub->getOperand(0); + if (isReassociableOp(V0, Instruction::Add, Instruction::FAdd) || + isReassociableOp(V0, Instruction::Sub, Instruction::FSub)) return true; - if (isReassociableOp(Sub->getOperand(1), Instruction::Add) || - isReassociableOp(Sub->getOperand(1), Instruction::Sub)) + Value *V1 = Sub->getOperand(1); + if (isReassociableOp(V1, Instruction::Add, Instruction::FAdd) || + isReassociableOp(V1, Instruction::Sub, Instruction::FSub)) return true; + Value *VB = Sub->user_back(); if (Sub->hasOneUse() && - (isReassociableOp(Sub->use_back(), Instruction::Add) || - isReassociableOp(Sub->use_back(), Instruction::Sub))) + (isReassociableOp(VB, Instruction::Add, Instruction::FAdd) || + isReassociableOp(VB, Instruction::Sub, Instruction::FSub))) 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, - DenseMap, unsigned> &ValueRankMap) { +/// 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. // @@ -543,65 +1023,73 @@ static Instruction *BreakUpSubtract(Instruction *Sub, // and set it as the RHS of the add instruction we just made. // Value *NegVal = NegateValue(Sub->getOperand(1), Sub); - Instruction *New = - BinaryOperator::CreateAdd(Sub->getOperand(0), NegVal, "", Sub); + BinaryOperator *New = CreateAdd(Sub->getOperand(0), NegVal, "", Sub, Sub); + Sub->setOperand(0, Constant::getNullValue(Sub->getType())); // Drop use of op. + Sub->setOperand(1, Constant::getNullValue(Sub->getType())); // Drop use of op. New->takeName(Sub); // Everyone now refers to the add instruction. - ValueRankMap.erase(Sub); Sub->replaceAllUsesWith(New); New->setDebugLoc(Sub->getDebugLoc()); - Sub->eraseFromParent(); DEBUG(dbgs() << "Negated: " << *New << '\n'); 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. -static Instruction *ConvertShiftToMul(Instruction *Shl, - DenseMap, unsigned> &ValueRankMap) { - // If an operand of this shift is a reassociable multiply, or if the shift - // is used by a reassociable multiply or add, turn into a multiply. - if (isReassociableOp(Shl->getOperand(0), Instruction::Mul) || - (Shl->hasOneUse() && - (isReassociableOp(Shl->use_back(), Instruction::Mul) || - isReassociableOp(Shl->use_back(), Instruction::Add)))) { - Constant *MulCst = ConstantInt::get(Shl->getType(), 1); - MulCst = ConstantExpr::getShl(MulCst, cast(Shl->getOperand(1))); - - Instruction *Mul = - BinaryOperator::CreateMul(Shl->getOperand(0), MulCst, "", Shl); - ValueRankMap.erase(Shl); - Mul->takeName(Shl); - Shl->replaceAllUsesWith(Mul); - Mul->setDebugLoc(Shl->getDebugLoc()); - Shl->eraseFromParent(); - return Mul; - } - return 0; +/// 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))); + + BinaryOperator *Mul = + 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){ @@ -610,18 +1098,26 @@ static Value *EmitAddTreeOfValues(Instruction *I, Value *V1 = Ops.back(); Ops.pop_back(); Value *V2 = EmitAddTreeOfValues(I, Ops); - return BinaryOperator::CreateAdd(V2, V1, "tmp", 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); - if (!BO) return 0; + BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul); + if (!BO) + return nullptr; + SmallVector Tree; + MadeChange |= LinearizeExprTree(BO, Tree); SmallVector Factors; - LinearizeExprTree(BO, Factors); + Factors.reserve(Tree.size()); + for (unsigned i = 0, e = Tree.size(); i != e; ++i) { + RepeatedValue E = Tree[i]; + Factors.append(E.second.getZExtValue(), + ValueEntry(getRank(E.first), E.first)); + } bool FoundFactor = false; bool NeedsNegate = false; @@ -633,19 +1129,31 @@ Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { } // If this is a negative version of this factor, remove it. - if (ConstantInt *FC1 = dyn_cast(Factor)) + if (ConstantInt *FC1 = dyn_cast(Factor)) { if (ConstantInt *FC2 = dyn_cast(Factors[i].Op)) if (FC1->getValue() == -FC2->getValue()) { FoundFactor = NeedsNegate = true; Factors.erase(Factors.begin()+i); break; } + } else if (ConstantFP *FC1 = dyn_cast(Factor)) { + if (ConstantFP *FC2 = dyn_cast(Factors[i].Op)) { + APFloat F1(FC1->getValueAPF()); + APFloat F2(FC2->getValueAPF()); + F2.changeSign(); + if (F1.compare(F2) == APFloat::cmpEqual) { + FoundFactor = NeedsNegate = true; + Factors.erase(Factors.begin() + i); + break; + } + } + } } if (!FoundFactor) { // Make sure to restore the operands to the expression tree. RewriteExprTree(BO, Factors); - return 0; + return nullptr; } BasicBlock::iterator InsertPt = BO; ++InsertPt; @@ -653,8 +1161,7 @@ Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { // If this was just a single multiply, remove the multiply and return the only // remaining operand. if (Factors.size() == 1) { - ValueRankMap.erase(BO); - DeadInsts.push_back(BO); + RedoInsts.insert(BO); V = Factors[0].Op; } else { RewriteExprTree(BO, Factors); @@ -662,48 +1169,32 @@ Value *Reassociate::RemoveFactorFromExpression(Value *V, Value *Factor) { } if (NeedsNegate) - V = BinaryOperator::CreateNeg(V, "neg", InsertPt); + V = CreateNeg(V, "neg", InsertPt, BO); 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, SmallVectorImpl &Factors, - const SmallVectorImpl &Ops, - bool IsRoot) { - BinaryOperator *BO; - if (!(V->hasOneUse() || V->use_empty()) || // More than one use. - !(BO = dyn_cast(V)) || - BO->getOpcode() != Instruction::Mul) { + const SmallVectorImpl &Ops) { + BinaryOperator *BO = isReassociableOp(V, Instruction::Mul, Instruction::FMul); + if (!BO) { 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, Ops, false); - FindSingleUseMultiplyFactors(BO->getOperand(0), Factors, Ops, false); + FindSingleUseMultiplyFactors(BO->getOperand(1), Factors, Ops); + 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. @@ -746,20 +1237,263 @@ static Value *OptimizeAndOrXor(unsigned Opcode, ++NumAnnihil; } } - return 0; + return nullptr; +} + +/// Helper funciton of CombineXorOpnd(). It creates a bitwise-and +/// instruction with the given two operands, and return the resulting +/// instruction. There are two special cases: 1) if the constant operand is 0, +/// it will return NULL. 2) if the constant is ~0, the symbolic operand will +/// be returned. +static Value *createAndInstr(Instruction *InsertBefore, Value *Opnd, + const APInt &ConstOpnd) { + if (ConstOpnd != 0) { + if (!ConstOpnd.isAllOnesValue()) { + LLVMContext &Ctx = Opnd->getType()->getContext(); + Instruction *I; + I = BinaryOperator::CreateAnd(Opnd, ConstantInt::get(Ctx, ConstOpnd), + "and.ra", InsertBefore); + I->setDebugLoc(InsertBefore->getDebugLoc()); + return I; + } + return Opnd; + } + return nullptr; +} + +// Helper function of OptimizeXor(). It tries to simplify "Opnd1 ^ ConstOpnd" +// into "R ^ C", where C would be 0, and R is a symbolic value. +// +// If it was successful, true is returned, and the "R" and "C" is returned +// via "Res" and "ConstOpnd", respectively; otherwise, false is returned, +// and both "Res" and "ConstOpnd" remain unchanged. +// +bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, + APInt &ConstOpnd, Value *&Res) { + // Xor-Rule 1: (x | c1) ^ c2 = (x | c1) ^ (c1 ^ c1) ^ c2 + // = ((x | c1) ^ c1) ^ (c1 ^ c2) + // = (x & ~c1) ^ (c1 ^ c2) + // It is useful only when c1 == c2. + if (Opnd1->isOrExpr() && Opnd1->getConstPart() != 0) { + if (!Opnd1->getValue()->hasOneUse()) + return false; + + const APInt &C1 = Opnd1->getConstPart(); + if (C1 != ConstOpnd) + return false; + + Value *X = Opnd1->getSymbolicPart(); + Res = createAndInstr(I, X, ~C1); + // ConstOpnd was C2, now C1 ^ C2. + ConstOpnd ^= C1; + + if (Instruction *T = dyn_cast(Opnd1->getValue())) + RedoInsts.insert(T); + return true; + } + return false; +} + + +// Helper function of OptimizeXor(). It tries to simplify +// "Opnd1 ^ Opnd2 ^ ConstOpnd" into "R ^ C", where C would be 0, and R is a +// symbolic value. +// +// If it was successful, true is returned, and the "R" and "C" is returned +// via "Res" and "ConstOpnd", respectively (If the entire expression is +// evaluated to a constant, the Res is set to NULL); otherwise, false is +// returned, and both "Res" and "ConstOpnd" remain unchanged. +bool Reassociate::CombineXorOpnd(Instruction *I, XorOpnd *Opnd1, XorOpnd *Opnd2, + APInt &ConstOpnd, Value *&Res) { + Value *X = Opnd1->getSymbolicPart(); + if (X != Opnd2->getSymbolicPart()) + return false; + + // This many instruction become dead.(At least "Opnd1 ^ Opnd2" will die.) + int DeadInstNum = 1; + if (Opnd1->getValue()->hasOneUse()) + DeadInstNum++; + if (Opnd2->getValue()->hasOneUse()) + DeadInstNum++; + + // Xor-Rule 2: + // (x | c1) ^ (x & c2) + // = (x|c1) ^ (x&c2) ^ (c1 ^ c1) = ((x|c1) ^ c1) ^ (x & c2) ^ c1 + // = (x & ~c1) ^ (x & c2) ^ c1 // Xor-Rule 1 + // = (x & c3) ^ c1, where c3 = ~c1 ^ c2 // Xor-rule 3 + // + if (Opnd1->isOrExpr() != Opnd2->isOrExpr()) { + if (Opnd2->isOrExpr()) + std::swap(Opnd1, Opnd2); + + const APInt &C1 = Opnd1->getConstPart(); + const APInt &C2 = Opnd2->getConstPart(); + APInt C3((~C1) ^ C2); + + // Do not increase code size! + if (C3 != 0 && !C3.isAllOnesValue()) { + int NewInstNum = ConstOpnd != 0 ? 1 : 2; + if (NewInstNum > DeadInstNum) + return false; + } + + Res = createAndInstr(I, X, C3); + ConstOpnd ^= C1; + + } else if (Opnd1->isOrExpr()) { + // Xor-Rule 3: (x | c1) ^ (x | c2) = (x & c3) ^ c3 where c3 = c1 ^ c2 + // + const APInt &C1 = Opnd1->getConstPart(); + const APInt &C2 = Opnd2->getConstPart(); + APInt C3 = C1 ^ C2; + + // Do not increase code size + if (C3 != 0 && !C3.isAllOnesValue()) { + int NewInstNum = ConstOpnd != 0 ? 1 : 2; + if (NewInstNum > DeadInstNum) + return false; + } + + Res = createAndInstr(I, X, C3); + ConstOpnd ^= C3; + } else { + // Xor-Rule 4: (x & c1) ^ (x & c2) = (x & (c1^c2)) + // + const APInt &C1 = Opnd1->getConstPart(); + const APInt &C2 = Opnd2->getConstPart(); + APInt C3 = C1 ^ C2; + Res = createAndInstr(I, X, C3); + } + + // Put the original operands in the Redo list; hope they will be deleted + // as dead code. + if (Instruction *T = dyn_cast(Opnd1->getValue())) + RedoInsts.insert(T); + if (Instruction *T = dyn_cast(Opnd2->getValue())) + RedoInsts.insert(T); + + return true; +} + +/// Optimize a series of operands to an 'xor' instruction. If it can be reduced +/// to a single Value, it is returned, otherwise the Ops list is mutated as +/// necessary. +Value *Reassociate::OptimizeXor(Instruction *I, + SmallVectorImpl &Ops) { + if (Value *V = OptimizeAndOrXor(Instruction::Xor, Ops)) + return V; + + if (Ops.size() == 1) + return nullptr; + + SmallVector Opnds; + SmallVector OpndPtrs; + Type *Ty = Ops[0].Op->getType(); + APInt ConstOpnd(Ty->getIntegerBitWidth(), 0); + + // Step 1: Convert ValueEntry to XorOpnd + for (unsigned i = 0, e = Ops.size(); i != e; ++i) { + Value *V = Ops[i].Op; + if (!isa(V)) { + XorOpnd O(V); + O.setSymbolicRank(getRank(O.getSymbolicPart())); + Opnds.push_back(O); + } else + ConstOpnd ^= cast(V)->getValue(); + } + + // NOTE: From this point on, do *NOT* add/delete element to/from "Opnds". + // It would otherwise invalidate the "Opnds"'s iterator, and hence invalidate + // the "OpndPtrs" as well. For the similar reason, do not fuse this loop + // with the previous loop --- the iterator of the "Opnds" may be invalidated + // when new elements are added to the vector. + for (unsigned i = 0, e = Opnds.size(); i != e; ++i) + OpndPtrs.push_back(&Opnds[i]); + + // Step 2: Sort the Xor-Operands in a way such that the operands containing + // the same symbolic value cluster together. For instance, the input operand + // sequence ("x | 123", "y & 456", "x & 789") will be sorted into: + // ("x | 123", "x & 789", "y & 456"). + std::stable_sort(OpndPtrs.begin(), OpndPtrs.end(), XorOpnd::PtrSortFunctor()); + + // Step 3: Combine adjacent operands + XorOpnd *PrevOpnd = nullptr; + bool Changed = false; + for (unsigned i = 0, e = Opnds.size(); i < e; i++) { + XorOpnd *CurrOpnd = OpndPtrs[i]; + // The combined value + Value *CV; + + // Step 3.1: Try simplifying "CurrOpnd ^ ConstOpnd" + if (ConstOpnd != 0 && CombineXorOpnd(I, CurrOpnd, ConstOpnd, CV)) { + Changed = true; + if (CV) + *CurrOpnd = XorOpnd(CV); + else { + CurrOpnd->Invalidate(); + continue; + } + } + + if (!PrevOpnd || CurrOpnd->getSymbolicPart() != PrevOpnd->getSymbolicPart()) { + PrevOpnd = CurrOpnd; + continue; + } + + // step 3.2: When previous and current operands share the same symbolic + // value, try to simplify "PrevOpnd ^ CurrOpnd ^ ConstOpnd" + // + if (CombineXorOpnd(I, CurrOpnd, PrevOpnd, ConstOpnd, CV)) { + // Remove previous operand + PrevOpnd->Invalidate(); + if (CV) { + *CurrOpnd = XorOpnd(CV); + PrevOpnd = CurrOpnd; + } else { + CurrOpnd->Invalidate(); + PrevOpnd = nullptr; + } + Changed = true; + } + } + + // Step 4: Reassemble the Ops + if (Changed) { + Ops.clear(); + for (unsigned int i = 0, e = Opnds.size(); i < e; i++) { + XorOpnd &O = Opnds[i]; + if (O.isInvalid()) + continue; + ValueEntry VE(getRank(O.getValue()), O.getValue()); + Ops.push_back(VE); + } + if (ConstOpnd != 0) { + Value *C = ConstantInt::get(Ty->getContext(), ConstOpnd); + ValueEntry VE(getRank(C), C); + Ops.push_back(VE); + } + int Sz = Ops.size(); + if (Sz == 1) + return Ops.back().Op; + else if (Sz == 0) { + assert(ConstOpnd == 0); + return ConstantInt::get(Ty->getContext(), ConstOpnd); + } + } + + 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, SmallVectorImpl &Ops) { // Scan the operand lists looking for X and -X pairs. If we find any, we - // can simplify the expression. X+-X == 0. While we're at it, scan for any + // can simplify expressions like X+-X == 0 and X+~X ==-1. While we're at it, + // scan for any // duplicates. We want to canonicalize Y+Y+Y+Z -> 3*Y+Z. - // - // TODO: We could handle "X + ~X" -> "-1" if we wanted, since "-X = ~X+1". - // + for (unsigned i = 0, e = Ops.size(); i != e; ++i) { Value *TheOp = Ops[i].Op; // Check to see if we've seen this operand before. If so, we factor all @@ -773,17 +1507,19 @@ 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. - Value *Mul = ConstantInt::get(cast(I->getType()), NumFound); - Mul = BinaryOperator::CreateMul(TheOp, Mul, "factor", I); + Type *Ty = TheOp->getType(); + 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 // handle cases that require multiple factoring steps, such as this: // (X*2) + (X*2) + (X*2) -> (X*2)*3 -> X*6 - RedoInsts.push_back(Mul); + RedoInsts.insert(Mul); // If every add operand was a duplicate, return the multiply. if (Ops.empty()) @@ -799,19 +1535,30 @@ Value *Reassociate::OptimizeAdd(Instruction *I, continue; } - // Check for X and -X in the operand list. - if (!BinaryOperator::isNeg(TheOp)) + // Check for X and -X or X and ~X in the operand list. + if (!BinaryOperator::isNeg(TheOp) && !BinaryOperator::isFNeg(TheOp) && + !BinaryOperator::isNot(TheOp)) continue; - Value *X = BinaryOperator::getNegArgument(TheOp); + Value *X = nullptr; + if (BinaryOperator::isNeg(TheOp) || BinaryOperator::isFNeg(TheOp)) + X = BinaryOperator::getNegArgument(TheOp); + else if (BinaryOperator::isNot(TheOp)) + X = BinaryOperator::getNotArgument(TheOp); + unsigned FoundX = FindInOperandList(Ops, i, X); if (FoundX == i) continue; // Remove X and -X from the operand list. - if (Ops.size() == 2) + if (Ops.size() == 2 && + (BinaryOperator::isNeg(TheOp) || BinaryOperator::isFNeg(TheOp))) return Constant::getNullValue(X->getType()); + // Remove X and ~X from the operand list. + if (Ops.size() == 2 && BinaryOperator::isNot(TheOp)) + return Constant::getAllOnesValue(X->getType()); + Ops.erase(Ops.begin()+i); if (i < FoundX) --FoundX; @@ -821,6 +1568,13 @@ Value *Reassociate::OptimizeAdd(Instruction *I, ++NumAnnihil; --i; // Revisit element. e -= 2; // Removed two elements. + + // if X and ~X we append -1 to the operand list. + if (BinaryOperator::isNot(TheOp)) { + Value *V = Constant::getAllOnesValue(X->getType()); + Ops.insert(Ops.end(), ValueEntry(getRank(V), V)); + e += 1; + } } // Scan the operand list, checking to see if there are any common factors @@ -833,56 +1587,82 @@ Value *Reassociate::OptimizeAdd(Instruction *I, // Keep track of each multiply we see, to avoid triggering on (X*4)+(X*4) // where they are actually the same multiply. unsigned MaxOcc = 0; - Value *MaxOccVal = 0; + Value *MaxOccVal = nullptr; for (unsigned i = 0, e = Ops.size(); i != e; ++i) { - BinaryOperator *BOp = dyn_cast(Ops[i].Op); - if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty()) + BinaryOperator *BOp = + isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul); + if (!BOp) continue; // Compute all of the factors of this added value. SmallVector Factors; - FindSingleUseMultiplyFactors(BOp, Factors, Ops, true); + FindSingleUseMultiplyFactors(BOp, Factors, Ops); assert(Factors.size() > 1 && "Bad linearize!"); // Add one to FactorOccurrences for each unique factor in this op. SmallPtrSet Duplicates; for (unsigned i = 0, e = Factors.size(); i != e; ++i) { Value *Factor = Factors[i]; - if (!Duplicates.insert(Factor)) continue; + if (!Duplicates.insert(Factor).second) + continue; unsigned Occ = ++FactorOccurrences[Factor]; - if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } + if (Occ > MaxOcc) { + MaxOcc = Occ; + MaxOccVal = Factor; + } // If Factor is a negative constant, add the negated value as a factor // because we can percolate the negate out. Watch for minint, which // cannot be positivified. - if (ConstantInt *CI = dyn_cast(Factor)) + if (ConstantInt *CI = dyn_cast(Factor)) { 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"); - unsigned Occ = ++FactorOccurrences[Factor]; - if (Occ > MaxOcc) { MaxOcc = Occ; MaxOccVal = Factor; } + if (Occ > MaxOcc) { + MaxOcc = Occ; + MaxOccVal = Factor; + } + } + } else if (ConstantFP *CF = dyn_cast(Factor)) { + if (CF->isNegative()) { + APFloat F(CF->getValueAPF()); + F.changeSign(); + Factor = ConstantFP::get(CF->getContext(), F); + assert(!Duplicates.count(Factor) && + "Shouldn't have two constant factors, missed a canonicalize"); + unsigned Occ = ++FactorOccurrences[Factor]; + if (Occ > MaxOcc) { + MaxOcc = Occ; + MaxOccVal = 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 // 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 = + I->getType()->isIntOrIntVectorTy() + ? BinaryOperator::CreateAdd(MaxOccVal, MaxOccVal) + : BinaryOperator::CreateFAdd(MaxOccVal, MaxOccVal); + SmallVector NewMulOps; for (unsigned i = 0; i != Ops.size(); ++i) { // Only try to remove factors from expressions we're allowed to. - BinaryOperator *BOp = dyn_cast(Ops[i].Op); - if (BOp == 0 || BOp->getOpcode() != Instruction::Mul || !BOp->use_empty()) + BinaryOperator *BOp = + isReassociableOp(Ops[i].Op, Instruction::Mul, Instruction::FMul); + if (!BOp) continue; if (Value *V = RemoveFactorFromExpression(Ops[i].Op, MaxOccVal)) { @@ -910,14 +1690,15 @@ Value *Reassociate::OptimizeAdd(Instruction *I, // 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(V)); + if (Instruction *VI = dyn_cast(V)) + RedoInsts.insert(VI); // Create the multiply. - Value *V2 = BinaryOperator::CreateMul(V, MaxOccVal, "tmp", I); + Instruction *V2 = CreateMul(V, MaxOccVal, "tmp", I, I); // Rerun associate on the multiply in case the inner expression turned into // a multiply. We want to make sure that we keep things in canonical form. - V2 = ReassociateExpression(cast(V2)); + RedoInsts.insert(V2); // If every add operand included the factor (e.g. "A*B + A*C"), then the // entire result expression is just the multiply "A*(B+C)". @@ -930,20 +1711,7 @@ Value *Reassociate::OptimizeAdd(Instruction *I, Ops.insert(Ops.begin(), ValueEntry(getRank(V2), V2)); } - return 0; -} - -namespace { - /// \brief Predicate tests whether a ValueEntry's op is in a map. - struct IsValueInMap { - const DenseMap ⤅ - - IsValueInMap(const DenseMap &Map) : Map(Map) {} - - bool operator()(const ValueEntry &Entry) { - return Map.find(Entry.Op) != Map.end(); - } - }; + return nullptr; } /// \brief Build up a vector of value/power pairs factoring a product. @@ -959,34 +1727,21 @@ namespace { /// \returns Whether any factors have a power greater than one. bool Reassociate::collectMultiplyFactors(SmallVectorImpl &Ops, SmallVectorImpl &Factors) { + // FIXME: Have Ops be (ValueEntry, Multiplicity) pairs, simplifying this. + // Compute the sum of powers of simplifiable factors. unsigned FactorPowerSum = 0; - DenseMap FactorCounts; - for (unsigned LastIdx = 0, Idx = 0, Size = Ops.size(); Idx < Size; ++Idx) { - // Note that 'use_empty' uses means the only use is in the linearized tree - // represented by Ops -- we remove the values from the actual operations to - // reduce their use count. - if (!Ops[Idx].Op->use_empty()) { - if (LastIdx == Idx) - ++LastIdx; - continue; - } - if (LastIdx == Idx || Ops[LastIdx].Op != Ops[Idx].Op) { - LastIdx = Idx; - continue; - } + for (unsigned Idx = 1, Size = Ops.size(); Idx < Size; ++Idx) { + Value *Op = Ops[Idx-1].Op; + + // Count the number of occurrences of this value. + unsigned Count = 1; + for (; Idx < Size && Ops[Idx].Op == Op; ++Idx) + ++Count; // Track for simplification all factors which occur 2 or more times. - DenseMap::iterator CountIt; - bool Inserted; - llvm::tie(CountIt, Inserted) - = FactorCounts.insert(std::make_pair(Ops[Idx].Op, 2)); - if (Inserted) { - FactorPowerSum += 2; - Factors.push_back(Factor(Ops[Idx].Op, 2)); - } else { - ++CountIt->second; - ++FactorPowerSum; - } + if (Count > 1) + FactorPowerSum += Count; } + // We can only simplify factors if the sum of the powers of our simplifiable // factors is 4 or higher. When that is the case, we will *always* have // a simplification. This is an important invariant to prevent cyclicly @@ -994,36 +1749,30 @@ bool Reassociate::collectMultiplyFactors(SmallVectorImpl &Ops, if (FactorPowerSum < 4) return false; - // Remove all the operands which are in the map. - Ops.erase(std::remove_if(Ops.begin(), Ops.end(), IsValueInMap(FactorCounts)), - Ops.end()); + // Now gather the simplifiable factors, removing them from Ops. + FactorPowerSum = 0; + for (unsigned Idx = 1; Idx < Ops.size(); ++Idx) { + Value *Op = Ops[Idx-1].Op; - // Record the adjusted power for the simplification factors. We add back into - // the Ops list any values with an odd power, and make the power even. This - // allows the outer-most multiplication tree to remain in tact during - // simplification. - unsigned OldOpsSize = Ops.size(); - for (unsigned Idx = 0, Size = Factors.size(); Idx != Size; ++Idx) { - Factors[Idx].Power = FactorCounts[Factors[Idx].Base]; - if (Factors[Idx].Power & 1) { - Ops.push_back(ValueEntry(getRank(Factors[Idx].Base), Factors[Idx].Base)); - --Factors[Idx].Power; - --FactorPowerSum; - } + // Count the number of occurrences of this value. + unsigned Count = 1; + for (; Idx < Ops.size() && Ops[Idx].Op == Op; ++Idx) + ++Count; + if (Count == 1) + continue; + // Move an even number of occurrences to Factors. + Count &= ~1U; + Idx -= Count; + FactorPowerSum += Count; + Factors.push_back(Factor(Op, Count)); + Ops.erase(Ops.begin()+Idx, Ops.begin()+Idx+Count); } + // None of the adjustments above should have reduced the sum of factor powers // below our mininum of '4'. assert(FactorPowerSum >= 4); - // Patch up the sort of the ops vector by sorting the factors we added back - // onto the back, and merging the two sequences. - if (OldOpsSize != Ops.size()) { - SmallVectorImpl::iterator MiddleIt = Ops.begin() + OldOpsSize; - std::sort(MiddleIt, Ops.end()); - std::inplace_merge(Ops.begin(), MiddleIt, Ops.end()); - } - - std::sort(Factors.begin(), Factors.end(), Factor::PowerDescendingSorter()); + std::stable_sort(Factors.begin(), Factors.end(), Factor::PowerDescendingSorter()); return true; } @@ -1035,7 +1784,10 @@ static Value *buildMultiplyTree(IRBuilder<> &Builder, Value *LHS = Ops.pop_back_val(); do { - LHS = Builder.CreateMul(LHS, Ops.pop_back_val()); + if (LHS->getType()->isIntOrIntVectorTy()) + LHS = Builder.CreateMul(LHS, Ops.pop_back_val()); + else + LHS = Builder.CreateFMul(LHS, Ops.pop_back_val()); } while (!Ops.empty()); return LHS; @@ -1070,9 +1822,9 @@ Value *Reassociate::buildMinimalMultiplyDAG(IRBuilder<> &Builder, // Reset the base value of the first factor to the new expression tree. // We'll remove all the factors with the same power in a second pass. - Factors[LastIdx].Base - = ReassociateExpression( - cast(buildMultiplyTree(Builder, InnerProduct))); + Value *M = Factors[LastIdx].Base = buildMultiplyTree(Builder, InnerProduct); + if (Instruction *MI = dyn_cast(M)) + RedoInsts.insert(MI); LastIdx = Idx; } @@ -1098,8 +1850,8 @@ Value *Reassociate::buildMinimalMultiplyDAG(IRBuilder<> &Builder, if (OuterProduct.size() == 1) return OuterProduct.front(); - return ReassociateExpression( - cast(buildMultiplyTree(Builder, OuterProduct))); + Value *V = buildMultiplyTree(Builder, OuterProduct); + return V; } Value *Reassociate::OptimizeMul(BinaryOperator *I, @@ -1107,14 +1859,14 @@ Value *Reassociate::OptimizeMul(BinaryOperator *I, // We can only optimize the multiplies when there is a chain of more than // three, such that a balanced tree might require fewer total multiplies. if (Ops.size() < 4) - return 0; + return nullptr; // Try to turn linear trees of multiplies without other uses of the // intermediate stages into minimal multiply DAGs with perfect sub-expression // re-use. SmallVector Factors; if (!collectMultiplyFactors(Ops, Factors)) - return 0; // All distinct factors, so nothing left for us to do. + return nullptr; // All distinct factors, so nothing left for us to do. IRBuilder<> Builder(I); Value *V = buildMinimalMultiplyDAG(Builder, Factors); @@ -1123,54 +1875,32 @@ Value *Reassociate::OptimizeMul(BinaryOperator *I, ValueEntry NewEntry = ValueEntry(getRank(V), V); Ops.insert(std::lower_bound(Ops.begin(), Ops.end(), NewEntry), NewEntry); - return 0; + return nullptr; } Value *Reassociate::OptimizeExpression(BinaryOperator *I, SmallVectorImpl &Ops) { // Now that we have the linearized expression tree, try to optimize it. // Start by folding any constants that we found. - bool IterateOptimization = false; - if (Ops.size() == 1) return Ops[0].Op; - + Constant *Cst = nullptr; unsigned Opcode = I->getOpcode(); + while (!Ops.empty() && isa(Ops.back().Op)) { + Constant *C = cast(Ops.pop_back_val().Op); + Cst = Cst ? ConstantExpr::get(Opcode, C, Cst) : C; + } + // If there was nothing but constants then we are done. + if (Ops.empty()) + return Cst; + + // Put the combined constant back at the end of the operand list, except if + // there is no point. For example, an add of 0 gets dropped here, while a + // multiplication by zero turns the whole expression into zero. + if (Cst && Cst != ConstantExpr::getBinOpIdentity(Opcode, I->getType())) { + if (Cst == ConstantExpr::getBinOpAbsorber(Opcode, I->getType())) + return Cst; + Ops.push_back(ValueEntry(0, Cst)); + } - if (Constant *V1 = dyn_cast(Ops[Ops.size()-2].Op)) - if (Constant *V2 = dyn_cast(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(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(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 @@ -1180,65 +1910,184 @@ Value *Reassociate::OptimizeExpression(BinaryOperator *I, default: break; case Instruction::And: case Instruction::Or: - case Instruction::Xor: if (Value *Result = OptimizeAndOrXor(Opcode, Ops)) return Result; break; + case Instruction::Xor: + if (Value *Result = OptimizeXor(I, Ops)) + return Result; + break; + case Instruction::Add: + case Instruction::FAdd: if (Value *Result = OptimizeAdd(I, Ops)) return Result; break; case Instruction::Mul: + case Instruction::FMul: if (Value *Result = OptimizeMul(I, Ops)) return Result; break; } - if (IterateOptimization || Ops.size() != NumOps) + if (Ops.size() != NumOps) return OptimizeExpression(I, Ops); - return 0; + return nullptr; } -/// 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(BI->getOperand(1))) - if (Instruction *NI = ConvertShiftToMul(BI, ValueRankMap)) { - MadeChange = true; - BI = NI; +/// 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()); + // Erase the dead instruction. + ValueRankMap.erase(I); + RedoInsts.remove(I); + I->eraseFromParent(); + // Optimize its operands. + SmallPtrSet Visited; // Detect self-referential nodes. + for (unsigned i = 0, e = Ops.size(); i != e; ++i) + if (Instruction *Op = dyn_cast(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->user_back()->getOpcode() == Opcode && + Visited.insert(Op).second) + Op = Op->user_back(); + RedoInsts.insert(Op); } +} - // Floating point binary operators are not associative, but we can still - // commute (some) of them, to canonicalize the order of their operands. - // This can potentially expose more CSE opportunities, and makes writing - // other transformations simpler. - if (isa(BI) && - (BI->getType()->isFloatingPointTy() || BI->getType()->isVectorTy())) { - // FAdd and FMul can be commuted. - if (BI->getOpcode() != Instruction::FMul && - BI->getOpcode() != Instruction::FAdd) - return; +// 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(I->getOperand(0)); + Constant *C1 = dyn_cast(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(C)) { + if (!CI->isNegative() || CI->isMinValue(true)) + return nullptr; + } else if (auto *CF = dyn_cast(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(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. + if (ConstantInt *CI = dyn_cast(C)) + I->setOperand(ConstIdx, ConstantInt::get(CI->getContext(), -CI->getValue())); + else { + ConstantFP *CF = cast(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(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(User)->getFastMathFlags()); + break; + case Instruction::FSub: + NI = BinaryOperator::CreateFAdd(Op0, Op1); + NI->setFastMathFlags(cast(User)->getFastMathFlags()); + break; + } - Value *LHS = BI->getOperand(0); - Value *RHS = BI->getOperand(1); - unsigned LHSRank = getRank(LHS); - unsigned RHSRank = getRank(RHS); + 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. + if (!isa(I)) + return; - // Sort the operands by rank. - if (RHSRank < LHSRank) { - BI->setOperand(0, RHS); - BI->setOperand(1, LHS); + if (I->getOpcode() == Instruction::Shl && isa(I->getOperand(1))) + // If an operand of this shift is a reassociable multiply, or if the shift + // is used by a reassociable multiply or add, turn into a multiply. + if (isReassociableOp(I->getOperand(0), Instruction::Mul) || + (I->hasOneUse() && + (isReassociableOp(I->user_back(), Instruction::Mul) || + isReassociableOp(I->user_back(), Instruction::Add)))) { + Instruction *NI = ConvertShiftToMul(I); + RedoInsts.insert(I); + MadeChange = true; + I = NI; } + // Canonicalize negative constants out of expressions. + if (Instruction *Res = canonicalizeNegConstExpr(I)) + I = Res; + + // 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); + + // TODO: We should optimize vector Xor instructions, but they are + // currently unsupported. + if (I->getType()->isVectorTy() && I->getOpcode() == Instruction::Xor) return; - } - // Do not reassociate operations that we do not understand. - if (!isa(BI)) + // 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 @@ -1247,55 +2096,83 @@ void Reassociate::ReassociateInst(BasicBlock::iterator &BBI) { // 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)) + if (I->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); - // Reset the BBI iterator in case BreakUpSubtract changed the - // instruction it points to. - BBI = BI; - ++BBI; + if (I->getOpcode() == Instruction::Sub) { + if (ShouldBreakUpSubtract(I)) { + Instruction *NI = BreakUpSubtract(I); + RedoInsts.insert(I); + MadeChange = true; + I = NI; + } else if (BinaryOperator::isNeg(I)) { + // 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(I->getOperand(1), Instruction::Mul) && + (!I->hasOneUse() || + !isReassociableOp(I->user_back(), Instruction::Mul))) { + Instruction *NI = LowerNegateToMultiply(I); + RedoInsts.insert(I); + MadeChange = true; + I = NI; + } + } + } else if (I->getOpcode() == Instruction::FSub) { + if (ShouldBreakUpSubtract(I)) { + Instruction *NI = BreakUpSubtract(I); + RedoInsts.insert(I); MadeChange = true; - } else if (BinaryOperator::isNeg(BI)) { + I = NI; + } else if (BinaryOperator::isFNeg(I)) { // 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); + if (isReassociableOp(I->getOperand(1), Instruction::FMul) && + (!I->hasOneUse() || + !isReassociableOp(I->user_back(), Instruction::FMul))) { + Instruction *NI = LowerNegateToMultiply(I); + RedoInsts.insert(I); MadeChange = true; + I = NI; } } } - // If this instruction is a commutative binary operator, process it. - if (!BI->isAssociative()) return; - BinaryOperator *I = cast(BI); + // If this instruction is an associative binary operator, process it. + if (!I->isAssociative()) return; + BinaryOperator *BO = cast(I); // 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())) + unsigned Opcode = BO->getOpcode(); + if (BO->hasOneUse() && BO->user_back()->getOpcode() == Opcode) 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(I->use_back())->getOpcode() == Instruction::Sub) + if (BO->hasOneUse() && BO->getOpcode() == Instruction::Add && + cast(BO->user_back())->getOpcode() == Instruction::Sub) + return; + if (BO->hasOneUse() && BO->getOpcode() == Instruction::FAdd && + cast(BO->user_back())->getOpcode() == Instruction::FSub) return; - ReassociateExpression(I); + ReassociateExpression(BO); } -Value *Reassociate::ReassociateExpression(BinaryOperator *I) { - +void Reassociate::ReassociateExpression(BinaryOperator *I) { // First, walk the expression tree, linearizing the tree, collecting the // operand information. + SmallVector Tree; + MadeChange |= LinearizeExprTree(I, Tree); SmallVector Ops; - LinearizeExprTree(I, Ops); + Ops.reserve(Tree.size()); + for (unsigned i = 0, e = Tree.size(); i != e; ++i) { + RepeatedValue E = Tree[i]; + Ops.append(E.second.getZExtValue(), + ValueEntry(getRank(E.first), E.first)); + } DEBUG(dbgs() << "RAIn:\t"; PrintOps(I, Ops); dbgs() << '\n'); @@ -1307,74 +2184,97 @@ Value *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) + // 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'); I->replaceAllUsesWith(V); if (Instruction *VI = dyn_cast(V)) VI->setDebugLoc(I->getDebugLoc()); - RemoveDeadBinaryOp(I); + RedoInsts.insert(I); ++NumAnnihil; - return V; + return; } // We want to sink immediates as deeply as possible except in the case where // this is a multiply tree used only by an add, and the immediate is a -1. // In this case we reassociate to put the negation on the outside so that we // can fold the negation into the add: (-X)*Y + Z -> Z-X*Y - if (I->getOpcode() == Instruction::Mul && I->hasOneUse() && - cast(I->use_back())->getOpcode() == Instruction::Add && - isa(Ops.back().Op) && - cast(Ops.back().Op)->isAllOnesValue()) { - ValueEntry Tmp = Ops.pop_back_val(); - Ops.insert(Ops.begin(), Tmp); + if (I->hasOneUse()) { + if (I->getOpcode() == Instruction::Mul && + cast(I->user_back())->getOpcode() == Instruction::Add && + isa(Ops.back().Op) && + cast(Ops.back().Op)->isAllOnesValue()) { + ValueEntry Tmp = Ops.pop_back_val(); + Ops.insert(Ops.begin(), Tmp); + } else if (I->getOpcode() == Instruction::FMul && + cast(I->user_back())->getOpcode() == + Instruction::FAdd && + isa(Ops.back().Op) && + cast(Ops.back().Op)->isExactlyValue(-1.0)) { + ValueEntry Tmp = Ops.pop_back_val(); + Ops.insert(Ops.begin(), Tmp); + } } 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(Ops[0].Op)) OI->setDebugLoc(I->getDebugLoc()); - RemoveDeadBinaryOp(I); - return Ops[0].Op; + RedoInsts.insert(I); + 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) { - // Recalculate the rank map for F + if (skipOptnoneFunction(F)) + return false; + + // Calculate the rank map for F BuildRankMap(F); MadeChange = false; - for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++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(V); - ReassociateInst(BBI); - } + for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { + // Optimize every instruction in the basic block. + for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; ) + if (isInstructionTriviallyDead(II)) { + EraseInst(II++); + } else { + OptimizeInst(II); + assert(II->getParent() == BI && "Moved to a different block!"); + ++II; + } - // 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); + // If this produced extra instructions to optimize, handle them now. + while (!RedoInsts.empty()) { + Instruction *I = RedoInsts.pop_back_val(); + if (isInstructionTriviallyDead(I)) + EraseInst(I); + else + OptimizeInst(I); + } + } // We are done with the rank map. RankMap.clear(); ValueRankMap.clear(); + return MadeChange; }