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