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 43 /// A private "module" namespace for types and utilities used by Reassociate. 44 /// These are implementation details and should not be used by clients. 45 namespace reassociate { 46 47 struct ValueEntry { 48 unsigned Rank; 49 Value *Op; 50 ValueEntryValueEntry51 ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {} 52 }; 53 54 inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) { 55 return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start. 56 } 57 58 /// Utility class representing a base and exponent pair which form one 59 /// factor of some product. 60 struct Factor { 61 Value *Base; 62 unsigned Power; 63 FactorFactor64 Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {} 65 }; 66 67 struct OverflowTracking { 68 bool HasNUW; 69 bool HasNSW; 70 bool AllKnownNonNegative; 71 bool AllKnownNonZero; 72 // Note: AllKnownNonNegative can be true in a case where one of the operands 73 // is negative, but one the operators is not NSW. AllKnownNonNegative should 74 // not be used independently of HasNSW OverflowTrackingOverflowTracking75 OverflowTracking() 76 : HasNUW(true), HasNSW(true), AllKnownNonNegative(true), 77 AllKnownNonZero(true) {} 78 }; 79 80 class XorOpnd; 81 82 } // end namespace reassociate 83 84 /// Reassociate commutative expressions. 85 class ReassociatePass : public PassInfoMixin<ReassociatePass> { 86 public: 87 using OrderedSet = 88 SetVector<AssertingVH<Instruction>, std::deque<AssertingVH<Instruction>>>; 89 90 protected: 91 DenseMap<BasicBlock *, unsigned> RankMap; 92 DenseMap<AssertingVH<Value>, unsigned> ValueRankMap; 93 OrderedSet RedoInsts; 94 95 // Arbitrary, but prevents quadratic behavior. 96 static const unsigned GlobalReassociateLimit = 10; 97 static const unsigned NumBinaryOps = 98 Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin; 99 100 struct PairMapValue { 101 WeakVH Value1; 102 WeakVH Value2; 103 unsigned Score; isValidPairMapValue104 bool isValid() const { return Value1 && Value2; } 105 }; 106 DenseMap<std::pair<Value *, Value *>, PairMapValue> PairMap[NumBinaryOps]; 107 108 bool MadeChange; 109 110 public: 111 PreservedAnalyses run(Function &F, FunctionAnalysisManager &); 112 113 private: 114 void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT); 115 unsigned getRank(Value *V); 116 void canonicalizeOperands(Instruction *I); 117 void ReassociateExpression(BinaryOperator *I); 118 void RewriteExprTree(BinaryOperator *I, 119 SmallVectorImpl<reassociate::ValueEntry> &Ops, 120 reassociate::OverflowTracking Flags); 121 Value *OptimizeExpression(BinaryOperator *I, 122 SmallVectorImpl<reassociate::ValueEntry> &Ops); 123 Value *OptimizeAdd(Instruction *I, 124 SmallVectorImpl<reassociate::ValueEntry> &Ops); 125 Value *OptimizeXor(Instruction *I, 126 SmallVectorImpl<reassociate::ValueEntry> &Ops); 127 bool CombineXorOpnd(BasicBlock::iterator It, reassociate::XorOpnd *Opnd1, 128 APInt &ConstOpnd, Value *&Res); 129 bool CombineXorOpnd(BasicBlock::iterator It, reassociate::XorOpnd *Opnd1, 130 reassociate::XorOpnd *Opnd2, APInt &ConstOpnd, 131 Value *&Res); 132 Value *buildMinimalMultiplyDAG(IRBuilderBase &Builder, 133 SmallVectorImpl<reassociate::Factor> &Factors); 134 Value *OptimizeMul(BinaryOperator *I, 135 SmallVectorImpl<reassociate::ValueEntry> &Ops); 136 Value *RemoveFactorFromExpression(Value *V, Value *Factor); 137 void EraseInst(Instruction *I); 138 void RecursivelyEraseDeadInsts(Instruction *I, OrderedSet &Insts); 139 void OptimizeInst(Instruction *I); 140 Instruction *canonicalizeNegFPConstantsForOp(Instruction *I, Instruction *Op, 141 Value *OtherOp); 142 Instruction *canonicalizeNegFPConstants(Instruction *I); 143 void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT); 144 }; 145 146 } // end namespace llvm 147 148 #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H 149