LLVM  9.0.0svn
NaryReassociate.h
Go to the documentation of this file.
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:
105 
106  // Glue for old PM.
107  bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_,
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);
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);
184 };
185 
186 } // end namespace llvm
187 
188 #endif // LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:110
Type
MessagePack types as defined in the standard, with the exception of Integer being divided into a sign...
Definition: MsgPackReader.h:48
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
The main scalar evolution driver.
A cache of @llvm.assume calls within a function.
F(f)
Hexagon Common GEP
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:873
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Provides information about what library functions are available for the current target.
bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_, ScalarEvolution *SE_, TargetLibraryInfo *TLI_, TargetTransformInfo *TTI_)
This class represents an analyzed expression in the program.
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM Value Representation.
Definition: Value.h:72
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.