Line data Source code
1 : //===-- InstructionSimplify.h - Fold instrs into simpler forms --*- 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 file declares routines for folding instructions into simpler forms
11 : // that do not require creating new instructions. This does constant folding
12 : // ("add i32 1, 1" -> "2") but can also handle non-constant operands, either
13 : // returning a constant ("and i32 %x, 0" -> "0") or an already existing value
14 : // ("and i32 %x, %x" -> "%x"). If the simplification is also an instruction
15 : // then it dominates the original instruction.
16 : //
17 : // These routines implicitly resolve undef uses. The easiest way to be safe when
18 : // using these routines to obtain simplified values for existing instructions is
19 : // to always replace all uses of the instructions with the resulting simplified
20 : // values. This will prevent other code from seeing the same undef uses and
21 : // resolving them to different values.
22 : //
23 : // These routines are designed to tolerate moderately incomplete IR, such as
24 : // instructions that are not connected to basic blocks yet. However, they do
25 : // require that all the IR that they encounter be valid. In particular, they
26 : // require that all non-constant values be defined in the same function, and the
27 : // same call context of that function (and not split between caller and callee
28 : // contexts of a directly recursive call, for example).
29 : //
30 : //===----------------------------------------------------------------------===//
31 :
32 : #ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
33 : #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
34 :
35 : #include "llvm/IR/Instruction.h"
36 : #include "llvm/IR/Operator.h"
37 : #include "llvm/IR/User.h"
38 :
39 : namespace llvm {
40 : class Function;
41 : template <typename T, typename... TArgs> class AnalysisManager;
42 : template <class T> class ArrayRef;
43 : class AssumptionCache;
44 : class DominatorTree;
45 : class ImmutableCallSite;
46 : class DataLayout;
47 : class FastMathFlags;
48 : struct LoopStandardAnalysisResults;
49 : class OptimizationRemarkEmitter;
50 : class Pass;
51 : class TargetLibraryInfo;
52 : class Type;
53 : class Value;
54 : class MDNode;
55 : class BinaryOperator;
56 :
57 : /// InstrInfoQuery provides an interface to query additional information for
58 : /// instructions like metadata or keywords like nsw, which provides conservative
59 : /// results if the users specified it is safe to use.
60 : struct InstrInfoQuery {
61 70113018 : InstrInfoQuery(bool UMD) : UseInstrInfo(UMD) {}
62 56763874 : InstrInfoQuery() : UseInstrInfo(true) {}
63 : bool UseInstrInfo = true;
64 :
65 0 : MDNode *getMetadata(const Instruction *I, unsigned KindID) const {
66 36565451 : if (UseInstrInfo)
67 : return I->getMetadata(KindID);
68 : return nullptr;
69 : }
70 :
71 0 : template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const {
72 2683472 : if (UseInstrInfo)
73 2569447 : return Op->hasNoUnsignedWrap();
74 : return false;
75 : }
76 0 :
77 0 : template <class InstT> bool hasNoSignedWrap(const InstT *Op) const {
78 5369601 : if (UseInstrInfo)
79 1421 : return Op->hasNoSignedWrap();
80 : return false;
81 0 : }
82 0 :
83 0 : bool isExact(const BinaryOperator *Op) const {
84 0 : if (UseInstrInfo && isa<PossiblyExactOperator>(Op))
85 : return cast<PossiblyExactOperator>(Op)->isExact();
86 : return false;
87 0 : }
88 2616422 : };
89 2569571 :
90 : struct SimplifyQuery {
91 : const DataLayout &DL;
92 0 : const TargetLibraryInfo *TLI = nullptr;
93 0 : const DominatorTree *DT = nullptr;
94 0 : AssumptionCache *AC = nullptr;
95 : const Instruction *CxtI = nullptr;
96 :
97 0 : // Wrapper to query additional information for instructions like metadata or
98 0 : // keywords like nsw, which provides conservative results if those cannot
99 0 : // be safely used.
100 : const InstrInfoQuery IIQ;
101 :
102 : SimplifyQuery(const DataLayout &DL, const Instruction *CXTI = nullptr)
103 44310328 : : DL(DL), CxtI(CXTI) {}
104 55169 :
105 0 : SimplifyQuery(const DataLayout &DL, const TargetLibraryInfo *TLI,
106 : const DominatorTree *DT = nullptr,
107 : AssumptionCache *AC = nullptr,
108 : const Instruction *CXTI = nullptr, bool UseInstrInfo = true)
109 7509763 : : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI), IIQ(UseInstrInfo) {}
110 : SimplifyQuery getWithInstruction(Instruction *I) const {
111 11451715 : SimplifyQuery Copy(*this);
112 11433733 : Copy.CxtI = I;
113 12453546 : return Copy;
114 : }
115 : };
116 :
117 : // NOTE: the explicit multiple argument versions of these functions are
118 : // deprecated.
119 : // Please use the SimplifyQuery versions in new code.
120 :
121 : /// Given operands for an Add, fold the result or return null.
122 : Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
123 : const SimplifyQuery &Q);
124 :
125 : /// Given operands for a Sub, fold the result or return null.
126 : Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
127 : const SimplifyQuery &Q);
128 :
129 165 : /// Given operands for an FAdd, fold the result or return null.
130 : Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
131 52195723 : const SimplifyQuery &Q);
132 52195723 :
133 : /// Given operands for an FSub, fold the result or return null.
134 : Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
135 : const SimplifyQuery &Q);
136 :
137 : /// Given operands for an FMul, fold the result or return null.
138 : Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF,
139 : const SimplifyQuery &Q);
140 :
141 : /// Given operands for a Mul, fold the result or return null.
142 : Value *SimplifyMulInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
143 :
144 : /// Given operands for an SDiv, fold the result or return null.
145 : Value *SimplifySDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
146 :
147 : /// Given operands for a UDiv, fold the result or return null.
148 : Value *SimplifyUDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
149 :
150 : /// Given operands for an FDiv, fold the result or return null.
151 : Value *SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF,
152 : const SimplifyQuery &Q);
153 :
154 : /// Given operands for an SRem, fold the result or return null.
155 : Value *SimplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
156 :
157 : /// Given operands for a URem, fold the result or return null.
158 : Value *SimplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
159 :
160 : /// Given operands for an FRem, fold the result or return null.
161 : Value *SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF,
162 : const SimplifyQuery &Q);
163 :
164 : /// Given operands for a Shl, fold the result or return null.
165 : Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
166 : const SimplifyQuery &Q);
167 :
168 : /// Given operands for a LShr, fold the result or return null.
169 : Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
170 : const SimplifyQuery &Q);
171 :
172 : /// Given operands for a AShr, fold the result or return nulll.
173 : Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
174 : const SimplifyQuery &Q);
175 :
176 : /// Given operands for an And, fold the result or return null.
177 : Value *SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
178 :
179 : /// Given operands for an Or, fold the result or return null.
180 : Value *SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
181 :
182 : /// Given operands for an Xor, fold the result or return null.
183 : Value *SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
184 :
185 : /// Given operands for an ICmpInst, fold the result or return null.
186 : Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
187 : const SimplifyQuery &Q);
188 :
189 : /// Given operands for an FCmpInst, fold the result or return null.
190 : Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
191 : FastMathFlags FMF, const SimplifyQuery &Q);
192 :
193 : /// Given operands for a SelectInst, fold the result or return null.
194 : Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
195 : const SimplifyQuery &Q);
196 :
197 : /// Given operands for a GetElementPtrInst, fold the result or return null.
198 : Value *SimplifyGEPInst(Type *SrcTy, ArrayRef<Value *> Ops,
199 : const SimplifyQuery &Q);
200 :
201 : /// Given operands for an InsertValueInst, fold the result or return null.
202 : Value *SimplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef<unsigned> Idxs,
203 : const SimplifyQuery &Q);
204 :
205 : /// Given operands for an InsertElement, fold the result or return null.
206 : Value *SimplifyInsertElementInst(Value *Vec, Value *Elt, Value *Idx,
207 : const SimplifyQuery &Q);
208 :
209 : /// Given operands for an ExtractValueInst, fold the result or return null.
210 : Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
211 : const SimplifyQuery &Q);
212 :
213 : /// Given operands for an ExtractElementInst, fold the result or return null.
214 : Value *SimplifyExtractElementInst(Value *Vec, Value *Idx,
215 : const SimplifyQuery &Q);
216 :
217 : /// Given operands for a CastInst, fold the result or return null.
218 : Value *SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
219 : const SimplifyQuery &Q);
220 :
221 : /// Given operands for a ShuffleVectorInst, fold the result or return null.
222 : Value *SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask,
223 : Type *RetTy, const SimplifyQuery &Q);
224 :
225 : //=== Helper functions for higher up the class hierarchy.
226 :
227 : /// Given operands for a CmpInst, fold the result or return null.
228 : Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
229 : const SimplifyQuery &Q);
230 :
231 : /// Given operands for a BinaryOperator, fold the result or return null.
232 : Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
233 : const SimplifyQuery &Q);
234 :
235 : /// Given operands for an FP BinaryOperator, fold the result or return null.
236 : /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
237 : /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
238 : Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
239 : FastMathFlags FMF, const SimplifyQuery &Q);
240 :
241 : /// Given a callsite, fold the result or return null.
242 : Value *SimplifyCall(ImmutableCallSite CS, const SimplifyQuery &Q);
243 :
244 : /// Given a function and iterators over arguments, fold the result or return
245 : /// null.
246 : Value *SimplifyCall(ImmutableCallSite CS, Value *V, User::op_iterator ArgBegin,
247 : User::op_iterator ArgEnd, const SimplifyQuery &Q);
248 :
249 : /// Given a function and set of arguments, fold the result or return null.
250 : Value *SimplifyCall(ImmutableCallSite CS, Value *V, ArrayRef<Value *> Args,
251 : const SimplifyQuery &Q);
252 :
253 : /// See if we can compute a simplified version of this instruction. If not,
254 : /// return null.
255 : Value *SimplifyInstruction(Instruction *I, const SimplifyQuery &Q,
256 : OptimizationRemarkEmitter *ORE = nullptr);
257 :
258 : /// Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
259 : ///
260 : /// This first performs a normal RAUW of I with SimpleV. It then recursively
261 : /// attempts to simplify those users updated by the operation. The 'I'
262 : /// instruction must not be equal to the simplified value 'SimpleV'.
263 : ///
264 : /// The function returns true if any simplifications were performed.
265 : bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
266 : const TargetLibraryInfo *TLI = nullptr,
267 : const DominatorTree *DT = nullptr,
268 : AssumptionCache *AC = nullptr);
269 :
270 : /// Recursively attempt to simplify an instruction.
271 : ///
272 : /// This routine uses SimplifyInstruction to simplify 'I', and if successful
273 : /// replaces uses of 'I' with the simplified value. It then recurses on each
274 : /// of the users impacted. It returns true if any simplifications were
275 : /// performed.
276 : bool recursivelySimplifyInstruction(Instruction *I,
277 : const TargetLibraryInfo *TLI = nullptr,
278 : const DominatorTree *DT = nullptr,
279 : AssumptionCache *AC = nullptr);
280 :
281 : // These helper functions return a SimplifyQuery structure that contains as
282 : // many of the optional analysis we use as are currently valid. This is the
283 : // strongly preferred way of constructing SimplifyQuery in passes.
284 : const SimplifyQuery getBestSimplifyQuery(Pass &, Function &);
285 : template <class T, class... TArgs>
286 : const SimplifyQuery getBestSimplifyQuery(AnalysisManager<T, TArgs...> &,
287 : Function &);
288 : const SimplifyQuery getBestSimplifyQuery(LoopStandardAnalysisResults &,
289 : const DataLayout &);
290 : } // end namespace llvm
291 :
292 : #endif
293 :
|
