1 //===- Reassociate.h - Reassociate binary expressions -----------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This pass reassociates commutative expressions in an order that is designed 10 // to promote better constant propagation, GCSE, LICM, PRE, etc. 11 // 12 // For example: 4 + (x + 5) -> x + (4 + 5) 13 // 14 // In the implementation of this algorithm, constants are assigned rank = 0, 15 // function arguments are rank = 1, and other values are assigned ranks 16 // corresponding to the reverse post order traversal of current function 17 // (starting at 2), which effectively gives values in deep loops higher rank 18 // than values not in loops. 19 // 20 //===----------------------------------------------------------------------===// 21 22 #ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H 23 #define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H 24 25 #include "llvm/ADT/DenseMap.h" 26 #include "llvm/ADT/PostOrderIterator.h" 27 #include "llvm/ADT/SetVector.h" 28 #include "llvm/IR/BasicBlock.h" 29 #include "llvm/IR/PassManager.h" 30 #include "llvm/IR/ValueHandle.h" 31 #include <deque> 32 33 namespace llvm { 34 35 class APInt; 36 class BasicBlock; 37 class BinaryOperator; 38 class Function; 39 class Instruction; 40 class IRBuilderBase; 41 class Value; 42 struct OverflowTracking; 43 44 /// A private "module" namespace for types and utilities used by Reassociate. 45 /// These are implementation details and should not be used by clients. 46 namespace reassociate { 47 48 struct ValueEntry { 49 unsigned Rank; 50 Value *Op; 51 ValueEntryValueEntry52 ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 53 }; 54 55 inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 56 return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 57 } 58 59 /// Utility class representing a base and exponent pair which form one 60 /// factor of some product. 61 struct Factor { 62 Value *Base; 63 unsigned Power; 64 FactorFactor65 Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {} 66 }; 67 68 class XorOpnd; 69 70 } // end namespace reassociate 71 72 /// Reassociate commutative expressions. 73 class ReassociatePass : public PassInfoMixin<ReassociatePass> { 74 public: 75 using OrderedSet = 76 SetVector<AssertingVH<Instruction>, std::deque<AssertingVH<Instruction>>>; 77 78 protected: 79 DenseMap<BasicBlock *, unsigned> RankMap; 80 DenseMap<AssertingVH<Value>, unsigned> ValueRankMap; 81 OrderedSet RedoInsts; 82 83 // Arbitrary, but prevents quadratic behavior. 84 static const unsigned GlobalReassociateLimit = 10; 85 static const unsigned NumBinaryOps = 86 Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin; 87 88 struct PairMapValue { 89 WeakVH Value1; 90 WeakVH Value2; 91 unsigned Score; isValidPairMapValue92 bool isValid() const { return Value1 && Value2; } 93 }; 94 DenseMap<std::pair<Value *, Value *>, PairMapValue> PairMap[NumBinaryOps]; 95 96 bool MadeChange; 97 98 public: 99 PreservedAnalyses run(Function &F, FunctionAnalysisManager &); 100 101 private: 102 void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT); 103 unsigned getRank(Value *V); 104 void canonicalizeOperands(Instruction *I); 105 void ReassociateExpression(BinaryOperator *I); 106 void RewriteExprTree(BinaryOperator *I, 107 SmallVectorImpl<reassociate::ValueEntry> &Ops, 108 OverflowTracking Flags); 109 Value *OptimizeExpression(BinaryOperator *I, 110 SmallVectorImpl<reassociate::ValueEntry> &Ops); 111 Value *OptimizeAdd(Instruction *I, 112 SmallVectorImpl<reassociate::ValueEntry> &Ops); 113 Value *OptimizeXor(Instruction *I, 114 SmallVectorImpl<reassociate::ValueEntry> &Ops); 115 bool CombineXorOpnd(BasicBlock::iterator It, reassociate::XorOpnd *Opnd1, 116 APInt &ConstOpnd, Value *&Res); 117 bool CombineXorOpnd(BasicBlock::iterator It, reassociate::XorOpnd *Opnd1, 118 reassociate::XorOpnd *Opnd2, APInt &ConstOpnd, 119 Value *&Res); 120 Value *buildMinimalMultiplyDAG(IRBuilderBase &Builder, 121 SmallVectorImpl<reassociate::Factor> &Factors); 122 Value *OptimizeMul(BinaryOperator *I, 123 SmallVectorImpl<reassociate::ValueEntry> &Ops); 124 Value *RemoveFactorFromExpression(Value *V, Value *Factor, DebugLoc DL); 125 void EraseInst(Instruction *I); 126 void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts); 127 void OptimizeInst(Instruction *I); 128 Instruction *canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op, 129 Value *OtherOp); 130 Instruction *canonicalizeNegFPConstants(Instruction *I); 131 void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT); 132 }; 133 134 } // end namespace llvm 135 136 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H 137