Line data Source code
1 : //===- NaryReassociate.h - Reassociate n-ary expressions --------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This pass reassociates n-ary add expressions and eliminates the redundancy
11 : // exposed by the reassociation.
12 : //
13 : // A motivating example:
14 : //
15 : // void foo(int a, int b) {
16 : // bar(a + b);
17 : // bar((a + 2) + b);
18 : // }
19 : //
20 : // An ideal compiler should reassociate (a + 2) + b to (a + b) + 2 and simplify
21 : // the above code to
22 : //
23 : // int t = a + b;
24 : // bar(t);
25 : // bar(t + 2);
26 : //
27 : // However, the Reassociate pass is unable to do that because it processes each
28 : // instruction individually and believes (a + 2) + b is the best form according
29 : // to its rank system.
30 : //
31 : // To address this limitation, NaryReassociate reassociates an expression in a
32 : // form that reuses existing instructions. As a result, NaryReassociate can
33 : // reassociate (a + 2) + b in the example to (a + b) + 2 because it detects that
34 : // (a + b) is computed before.
35 : //
36 : // NaryReassociate works as follows. For every instruction in the form of (a +
37 : // b) + c, it checks whether a + c or b + c is already computed by a dominating
38 : // instruction. If so, it then reassociates (a + b) + c into (a + c) + b or (b +
39 : // c) + a and removes the redundancy accordingly. To efficiently look up whether
40 : // an expression is computed before, we store each instruction seen and its SCEV
41 : // into an SCEV-to-instruction map.
42 : //
43 : // Although the algorithm pattern-matches only ternary additions, it
44 : // automatically handles many >3-ary expressions by walking through the function
45 : // in the depth-first order. For example, given
46 : //
47 : // (a + c) + d
48 : // ((a + b) + c) + d
49 : //
50 : // NaryReassociate first rewrites (a + b) + c to (a + c) + b, and then rewrites
51 : // ((a + c) + b) + d into ((a + c) + d) + b.
52 : //
53 : // Finally, the above dominator-based algorithm may need to be run multiple
54 : // iterations before emitting optimal code. One source of this need is that we
55 : // only split an operand when it is used only once. The above algorithm can
56 : // eliminate an instruction and decrease the usage count of its operands. As a
57 : // result, an instruction that previously had multiple uses may become a
58 : // single-use instruction and thus eligible for split consideration. For
59 : // example,
60 : //
61 : // ac = a + c
62 : // ab = a + b
63 : // abc = ab + c
64 : // ab2 = ab + b
65 : // ab2c = ab2 + c
66 : //
67 : // In the first iteration, we cannot reassociate abc to ac+b because ab is used
68 : // twice. However, we can reassociate ab2c to abc+b in the first iteration. As a
69 : // result, ab2 becomes dead and ab will be used only once in the second
70 : // iteration.
71 : //
72 : // Limitations and TODO items:
73 : //
74 : // 1) We only considers n-ary adds and muls for now. This should be extended
75 : // and generalized.
76 : //
77 : //===----------------------------------------------------------------------===//
78 :
79 : #ifndef LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
80 : #define LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
81 :
82 : #include "llvm/ADT/DenseMap.h"
83 : #include "llvm/ADT/SmallVector.h"
84 : #include "llvm/IR/PassManager.h"
85 : #include "llvm/IR/ValueHandle.h"
86 :
87 : namespace llvm {
88 :
89 : class AssumptionCache;
90 : class BinaryOperator;
91 : class DataLayout;
92 : class DominatorTree;
93 : class Function;
94 : class GetElementPtrInst;
95 : class Instruction;
96 : class ScalarEvolution;
97 : class SCEV;
98 : class TargetLibraryInfo;
99 : class TargetTransformInfo;
100 : class Type;
101 : class Value;
102 :
103 2430 : class NaryReassociatePass : public PassInfoMixin<NaryReassociatePass> {
104 : public:
105 : PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
106 :
107 : // Glue for old PM.
108 : bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_,
109 : ScalarEvolution *SE_, TargetLibraryInfo *TLI_,
110 : TargetTransformInfo *TTI_);
111 :
112 : private:
113 : // Runs only one iteration of the dominator-based algorithm. See the header
114 : // comments for why we need multiple iterations.
115 : bool doOneIteration(Function &F);
116 :
117 : // Reassociates I for better CSE.
118 : Instruction *tryReassociate(Instruction *I);
119 :
120 : // Reassociate GEP for better CSE.
121 : Instruction *tryReassociateGEP(GetElementPtrInst *GEP);
122 :
123 : // Try splitting GEP at the I-th index and see whether either part can be
124 : // CSE'ed. This is a helper function for tryReassociateGEP.
125 : //
126 : // \p IndexedType The element type indexed by GEP's I-th index. This is
127 : // equivalent to
128 : // GEP->getIndexedType(GEP->getPointerOperand(), 0-th index,
129 : // ..., i-th index).
130 : GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
131 : unsigned I, Type *IndexedType);
132 :
133 : // Given GEP's I-th index = LHS + RHS, see whether &Base[..][LHS][..] or
134 : // &Base[..][RHS][..] can be CSE'ed and rewrite GEP accordingly.
135 : GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
136 : unsigned I, Value *LHS,
137 : Value *RHS, Type *IndexedType);
138 :
139 : // Reassociate binary operators for better CSE.
140 : Instruction *tryReassociateBinaryOp(BinaryOperator *I);
141 :
142 : // A helper function for tryReassociateBinaryOp. LHS and RHS are explicitly
143 : // passed.
144 : Instruction *tryReassociateBinaryOp(Value *LHS, Value *RHS,
145 : BinaryOperator *I);
146 : // Rewrites I to (LHS op RHS) if LHS is computed already.
147 : Instruction *tryReassociatedBinaryOp(const SCEV *LHS, Value *RHS,
148 : BinaryOperator *I);
149 :
150 : // Tries to match Op1 and Op2 by using V.
151 : bool matchTernaryOp(BinaryOperator *I, Value *V, Value *&Op1, Value *&Op2);
152 :
153 : // Gets SCEV for (LHS op RHS).
154 : const SCEV *getBinarySCEV(BinaryOperator *I, const SCEV *LHS,
155 : const SCEV *RHS);
156 :
157 : // Returns the closest dominator of \c Dominatee that computes
158 : // \c CandidateExpr. Returns null if not found.
159 : Instruction *findClosestMatchingDominator(const SCEV *CandidateExpr,
160 : Instruction *Dominatee);
161 :
162 : // GetElementPtrInst implicitly sign-extends an index if the index is shorter
163 : // than the pointer size. This function returns whether Index is shorter than
164 : // GEP's pointer size, i.e., whether Index needs to be sign-extended in order
165 : // to be an index of GEP.
166 : bool requiresSignExtension(Value *Index, GetElementPtrInst *GEP);
167 :
168 : AssumptionCache *AC;
169 : const DataLayout *DL;
170 : DominatorTree *DT;
171 : ScalarEvolution *SE;
172 : TargetLibraryInfo *TLI;
173 : TargetTransformInfo *TTI;
174 :
175 : // A lookup table quickly telling which instructions compute the given SCEV.
176 : // Note that there can be multiple instructions at different locations
177 : // computing to the same SCEV, so we map a SCEV to an instruction list. For
178 : // example,
179 : //
180 : // if (p1)
181 : // foo(a + b);
182 : // if (p2)
183 : // bar(a + b);
184 : DenseMap<const SCEV *, SmallVector<WeakTrackingVH, 2>> SeenExprs;
185 : };
186 :
187 : } // end namespace llvm
188 :
189 : #endif // LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
|
