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