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 | |