//===- Reassociate.cpp - Reassociate binary expressions -------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This pass reassociates commutative expressions in an order that is designed // to promote better constant propagation, GCSE, LICM, PRE, etc. // // For example: 4 + (x + 5) -> x + (4 + 5) // // In the implementation of this algorithm, constants are assigned rank = 0, // function arguments are rank = 1, and other values are assigned ranks // corresponding to the reverse post order traversal of current function // (starting at 2), which effectively gives values in deep loops higher rank // than values not in loops. // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/Reassociate.h" #include "llvm/ADT/APFloat.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PassManager.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/IR/ValueHandle.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/Local.h" #include <algorithm> #include <cassert> #include <utility> usingnamespacellvm; usingnamespacereassociate; usingnamespacePatternMatch; #define DEBUG_TYPE … STATISTIC(NumChanged, "Number of insts reassociated"); STATISTIC(NumAnnihil, "Number of expr tree annihilated"); STATISTIC(NumFactor , "Number of multiplies factored"); static cl::opt<bool> UseCSELocalOpt(DEBUG_TYPE "-use-cse-local", cl::desc("Only reorder expressions within a basic block " "when exposing CSE opportunities"), cl::init(true), cl::Hidden); #ifndef NDEBUG /// Print out the expression identified in the Ops list. static void PrintOps(Instruction *I, const SmallVectorImpl<ValueEntry> &Ops) { Module *M = I->getModule(); dbgs() << Instruction::getOpcodeName(I->getOpcode()) << " " << *Ops[0].Op->getType() << '\t'; for (unsigned i = 0, e = Ops.size(); i != e; ++i) { dbgs() << "[ "; Ops[i].Op->printAsOperand(dbgs(), false, M); dbgs() << ", #" << Ops[i].Rank << "] "; } } #endif /// 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 llvm::reassociate::XorOpnd { … }; XorOpnd::XorOpnd(Value *V) { … } /// Return true if I is an instruction with the FastMathFlags that are needed /// for general reassociation set. This is not the same as testing /// Instruction::isAssociative() because it includes operations like fsub. /// (This routine is only intended to be called for floating-point operations.) static bool hasFPAssociativeFlags(Instruction *I) { … } /// 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) { … } static BinaryOperator *isReassociableOp(Value *V, unsigned Opcode1, unsigned Opcode2) { … } void ReassociatePass::BuildRankMap(Function &F, ReversePostOrderTraversal<Function*> &RPOT) { … } unsigned ReassociatePass::getRank(Value *V) { … } // Canonicalize constants to RHS. Otherwise, sort the operands by rank. void ReassociatePass::canonicalizeOperands(Instruction *I) { … } static BinaryOperator *CreateAdd(Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore, Value *FlagsOp) { … } static BinaryOperator *CreateMul(Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore, Value *FlagsOp) { … } static Instruction *CreateNeg(Value *S1, const Twine &Name, BasicBlock::iterator InsertBefore, Value *FlagsOp) { … } /// Replace 0-X with X*-1. static BinaryOperator *LowerNegateToMultiply(Instruction *Neg) { … } 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. /// /// 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. /// /// 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(Instruction *I, SmallVectorImpl<RepeatedValue> &Ops, ReassociatePass::OrderedSet &ToRedo, reassociate::OverflowTracking &Flags) { … } /// Now that the operands for this expression tree are /// linearized and optimized, emit them in-order. void ReassociatePass::RewriteExprTree(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops, OverflowTracking Flags) { … } /// 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. /// Also add intermediate instructions to the redo list that are modified while /// pushing the negates through adds. These will be revisited to see if /// additional opportunities have been exposed. static Value *NegateValue(Value *V, Instruction *BI, ReassociatePass::OrderedSet &ToRedo) { … } // See if this `or` looks like an load widening reduction, i.e. that it // consists of an `or`/`shl`/`zext`/`load` nodes only. Note that we don't // ensure that the pattern is *really* a load widening reduction, // we do not ensure that it can really be replaced with a widened load, // only that it mostly looks like one. static bool isLoadCombineCandidate(Instruction *Or) { … } /// Return true if it may be profitable to convert this (X|Y) into (X+Y). static bool shouldConvertOrWithNoCommonBitsToAdd(Instruction *Or) { … } /// If we have (X|Y), and iff X and Y have no common bits set, /// transform this into (X+Y) to allow arithmetics reassociation. static BinaryOperator *convertOrWithNoCommonBitsToAdd(Instruction *Or) { … } /// Return true if we should break up this subtract of X-Y into (X + -Y). static bool ShouldBreakUpSubtract(Instruction *Sub) { … } /// 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, ReassociatePass::OrderedSet &ToRedo) { … } /// 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) { … } /// 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(const SmallVectorImpl<ValueEntry> &Ops, unsigned i, Value *X) { … } /// Emit a tree of add instructions, summing Ops together /// and returning the result. Insert the tree before I. static Value *EmitAddTreeOfValues(BasicBlock::iterator It, SmallVectorImpl<WeakTrackingVH> &Ops) { … } /// 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 *ReassociatePass::RemoveFactorFromExpression(Value *V, Value *Factor) { … } /// If V is a single-use multiply, recursively add its operands as factors, /// otherwise add V to the list of factors. /// /// Ops is the top-level list of add operands we're trying to factor. static void FindSingleUseMultiplyFactors(Value *V, SmallVectorImpl<Value*> &Factors) { … } /// 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<ValueEntry> &Ops) { … } /// Helper function 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(BasicBlock::iterator InsertBefore, Value *Opnd, const APInt &ConstOpnd) { … } // 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 ReassociatePass::CombineXorOpnd(BasicBlock::iterator It, XorOpnd *Opnd1, APInt &ConstOpnd, Value *&Res) { … } // 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 ReassociatePass::CombineXorOpnd(BasicBlock::iterator It, XorOpnd *Opnd1, XorOpnd *Opnd2, APInt &ConstOpnd, Value *&Res) { … } /// 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 *ReassociatePass::OptimizeXor(Instruction *I, SmallVectorImpl<ValueEntry> &Ops) { … } /// 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 *ReassociatePass::OptimizeAdd(Instruction *I, SmallVectorImpl<ValueEntry> &Ops) { … } /// Build up a vector of value/power pairs factoring a product. /// /// Given a series of multiplication operands, build a vector of factors and /// the powers each is raised to when forming the final product. Sort them in /// the order of descending power. /// /// (x*x) -> [(x, 2)] /// ((x*x)*x) -> [(x, 3)] /// ((((x*y)*x)*y)*x) -> [(x, 3), (y, 2)] /// /// \returns Whether any factors have a power greater than one. static bool collectMultiplyFactors(SmallVectorImpl<ValueEntry> &Ops, SmallVectorImpl<Factor> &Factors) { … } /// Build a tree of multiplies, computing the product of Ops. static Value *buildMultiplyTree(IRBuilderBase &Builder, SmallVectorImpl<Value*> &Ops) { … } /// Build a minimal multiplication DAG for (a^x)*(b^y)*(c^z)*... /// /// Given a vector of values raised to various powers, where no two values are /// equal and the powers are sorted in decreasing order, compute the minimal /// DAG of multiplies to compute the final product, and return that product /// value. Value * ReassociatePass::buildMinimalMultiplyDAG(IRBuilderBase &Builder, SmallVectorImpl<Factor> &Factors) { … } Value *ReassociatePass::OptimizeMul(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops) { … } Value *ReassociatePass::OptimizeExpression(BinaryOperator *I, SmallVectorImpl<ValueEntry> &Ops) { … } // Remove dead instructions and if any operands are trivially dead add them to // Insts so they will be removed as well. void ReassociatePass::RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts) { … } /// Zap the given instruction, adding interesting operands to the work list. void ReassociatePass::EraseInst(Instruction *I) { … } /// Recursively analyze an expression to build a list of instructions that have /// negative floating-point constant operands. The caller can then transform /// the list to create positive constants for better reassociation and CSE. static void getNegatibleInsts(Value *V, SmallVectorImpl<Instruction *> &Candidates) { … } /// Given an fadd/fsub with an operand that is a one-use instruction /// (the fadd/fsub), try to change negative floating-point constants into /// positive constants to increase potential for reassociation and CSE. Instruction *ReassociatePass::canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op, Value *OtherOp) { … } /// Canonicalize expressions that contain a negative floating-point constant /// of the following form: /// OtherOp + (subtree) -> OtherOp {+/-} (canonical subtree) /// (subtree) + OtherOp -> OtherOp {+/-} (canonical subtree) /// OtherOp - (subtree) -> OtherOp {+/-} (canonical subtree) /// /// The fadd/fsub opcode may be switched to allow folding a negation into the /// input instruction. Instruction *ReassociatePass::canonicalizeNegFPConstants(Instruction *I) { … } /// Inspect and optimize the given instruction. Note that erasing /// instructions is not allowed. void ReassociatePass::OptimizeInst(Instruction *I) { … } void ReassociatePass::ReassociateExpression(BinaryOperator *I) { … } void ReassociatePass::BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT) { … } PreservedAnalyses ReassociatePass::run(Function &F, FunctionAnalysisManager &) { … } namespace { class ReassociateLegacyPass : public FunctionPass { … }; } // end anonymous namespace char ReassociateLegacyPass::ID = …; INITIALIZE_PASS(…) // Public interface to the Reassociate pass FunctionPass *llvm::createReassociatePass() { … }
Codebase Browser
llvm