1 //===-- InstructionSimplify.h - Fold instrs into simpler forms --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
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.
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).
30 //===----------------------------------------------------------------------===//
32 #ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
33 #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
35 #include "llvm/IR/User.h"
40 class AssumptionTracker;
45 class TargetLibraryInfo;
49 /// SimplifyAddInst - Given operands for an Add, see if we can
50 /// fold the result. If not, this returns null.
51 Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
52 const DataLayout *TD = nullptr,
53 const TargetLibraryInfo *TLI = nullptr,
54 const DominatorTree *DT = nullptr,
55 AssumptionTracker *AT = nullptr,
56 const Instruction *CxtI = nullptr);
58 /// SimplifySubInst - Given operands for a Sub, see if we can
59 /// fold the result. If not, this returns null.
60 Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
61 const DataLayout *TD = nullptr,
62 const TargetLibraryInfo *TLI = nullptr,
63 const DominatorTree *DT = nullptr,
64 AssumptionTracker *AT = nullptr,
65 const Instruction *CxtI = nullptr);
67 /// Given operands for an FAdd, see if we can fold the result. If not, this
69 Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
70 const DataLayout *TD = nullptr,
71 const TargetLibraryInfo *TLI = nullptr,
72 const DominatorTree *DT = nullptr,
73 AssumptionTracker *AT = nullptr,
74 const Instruction *CxtI = nullptr);
76 /// Given operands for an FSub, see if we can fold the result. If not, this
78 Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
79 const DataLayout *TD = nullptr,
80 const TargetLibraryInfo *TLI = nullptr,
81 const DominatorTree *DT = nullptr,
82 AssumptionTracker *AT = nullptr,
83 const Instruction *CxtI = nullptr);
85 /// Given operands for an FMul, see if we can fold the result. If not, this
87 Value *SimplifyFMulInst(Value *LHS, Value *RHS,
89 const DataLayout *TD = nullptr,
90 const TargetLibraryInfo *TLI = nullptr,
91 const DominatorTree *DT = nullptr,
92 AssumptionTracker *AT = nullptr,
93 const Instruction *CxtI = nullptr);
95 /// SimplifyMulInst - Given operands for a Mul, see if we can
96 /// fold the result. If not, this returns null.
97 Value *SimplifyMulInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr,
98 const TargetLibraryInfo *TLI = nullptr,
99 const DominatorTree *DT = nullptr,
100 AssumptionTracker *AT = nullptr,
101 const Instruction *CxtI = nullptr);
103 /// SimplifySDivInst - Given operands for an SDiv, see if we can
104 /// fold the result. If not, this returns null.
105 Value *SimplifySDivInst(Value *LHS, Value *RHS,
106 const DataLayout *TD = nullptr,
107 const TargetLibraryInfo *TLI = nullptr,
108 const DominatorTree *DT = nullptr,
109 AssumptionTracker *AT = nullptr,
110 const Instruction *CxtI = nullptr);
112 /// SimplifyUDivInst - Given operands for a UDiv, see if we can
113 /// fold the result. If not, this returns null.
114 Value *SimplifyUDivInst(Value *LHS, Value *RHS,
115 const DataLayout *TD = nullptr,
116 const TargetLibraryInfo *TLI = nullptr,
117 const DominatorTree *DT = nullptr,
118 AssumptionTracker *AT = nullptr,
119 const Instruction *CxtI = nullptr);
121 /// SimplifyFDivInst - Given operands for an FDiv, see if we can
122 /// fold the result. If not, this returns null.
123 Value *SimplifyFDivInst(Value *LHS, Value *RHS,
124 const DataLayout *TD = nullptr,
125 const TargetLibraryInfo *TLI = nullptr,
126 const DominatorTree *DT = nullptr,
127 AssumptionTracker *AT = nullptr,
128 const Instruction *CxtI = nullptr);
130 /// SimplifySRemInst - Given operands for an SRem, see if we can
131 /// fold the result. If not, this returns null.
132 Value *SimplifySRemInst(Value *LHS, Value *RHS,
133 const DataLayout *TD = nullptr,
134 const TargetLibraryInfo *TLI = nullptr,
135 const DominatorTree *DT = nullptr,
136 AssumptionTracker *AT = nullptr,
137 const Instruction *CxtI = nullptr);
139 /// SimplifyURemInst - Given operands for a URem, see if we can
140 /// fold the result. If not, this returns null.
141 Value *SimplifyURemInst(Value *LHS, Value *RHS,
142 const DataLayout *TD = nullptr,
143 const TargetLibraryInfo *TLI = nullptr,
144 const DominatorTree *DT = nullptr,
145 AssumptionTracker *AT = nullptr,
146 const Instruction *CxtI = nullptr);
148 /// SimplifyFRemInst - Given operands for an FRem, see if we can
149 /// fold the result. If not, this returns null.
150 Value *SimplifyFRemInst(Value *LHS, Value *RHS,
151 const DataLayout *TD = nullptr,
152 const TargetLibraryInfo *TLI = nullptr,
153 const DominatorTree *DT = nullptr,
154 AssumptionTracker *AT = nullptr,
155 const Instruction *CxtI = nullptr);
157 /// SimplifyShlInst - Given operands for a Shl, see if we can
158 /// fold the result. If not, this returns null.
159 Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
160 const DataLayout *TD = nullptr,
161 const TargetLibraryInfo *TLI = nullptr,
162 const DominatorTree *DT = nullptr,
163 AssumptionTracker *AT = nullptr,
164 const Instruction *CxtI = nullptr);
166 /// SimplifyLShrInst - Given operands for a LShr, see if we can
167 /// fold the result. If not, this returns null.
168 Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
169 const DataLayout *TD = nullptr,
170 const TargetLibraryInfo *TLI = nullptr,
171 const DominatorTree *DT = nullptr,
172 AssumptionTracker *AT = nullptr,
173 const Instruction *CxtI = nullptr);
175 /// SimplifyAShrInst - Given operands for a AShr, see if we can
176 /// fold the result. If not, this returns null.
177 Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
178 const DataLayout *TD = nullptr,
179 const TargetLibraryInfo *TLI = nullptr,
180 const DominatorTree *DT = nullptr,
181 AssumptionTracker *AT = nullptr,
182 const Instruction *CxtI = nullptr);
184 /// SimplifyAndInst - Given operands for an And, see if we can
185 /// fold the result. If not, this returns null.
186 Value *SimplifyAndInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr,
187 const TargetLibraryInfo *TLI = nullptr,
188 const DominatorTree *DT = nullptr,
189 AssumptionTracker *AT = nullptr,
190 const Instruction *CxtI = nullptr);
192 /// SimplifyOrInst - Given operands for an Or, see if we can
193 /// fold the result. If not, this returns null.
194 Value *SimplifyOrInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr,
195 const TargetLibraryInfo *TLI = nullptr,
196 const DominatorTree *DT = nullptr,
197 AssumptionTracker *AT = nullptr,
198 const Instruction *CxtI = nullptr);
200 /// SimplifyXorInst - Given operands for a Xor, see if we can
201 /// fold the result. If not, this returns null.
202 Value *SimplifyXorInst(Value *LHS, Value *RHS, const DataLayout *TD = nullptr,
203 const TargetLibraryInfo *TLI = nullptr,
204 const DominatorTree *DT = nullptr,
205 AssumptionTracker *AT = nullptr,
206 const Instruction *CxtI = nullptr);
208 /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
209 /// fold the result. If not, this returns null.
210 Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
211 const DataLayout *TD = nullptr,
212 const TargetLibraryInfo *TLI = nullptr,
213 const DominatorTree *DT = nullptr,
214 AssumptionTracker *AT = nullptr,
215 Instruction *CxtI = nullptr);
217 /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
218 /// fold the result. If not, this returns null.
219 Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
220 const DataLayout *TD = nullptr,
221 const TargetLibraryInfo *TLI = nullptr,
222 const DominatorTree *DT = nullptr,
223 AssumptionTracker *AT = nullptr,
224 const Instruction *CxtI = nullptr);
226 /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
227 /// the result. If not, this returns null.
228 Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
229 const DataLayout *TD = nullptr,
230 const TargetLibraryInfo *TLI = nullptr,
231 const DominatorTree *DT = nullptr,
232 AssumptionTracker *AT = nullptr,
233 const Instruction *CxtI = nullptr);
235 /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
236 /// fold the result. If not, this returns null.
237 Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *TD = nullptr,
238 const TargetLibraryInfo *TLI = nullptr,
239 const DominatorTree *DT = nullptr,
240 AssumptionTracker *AT = nullptr,
241 const Instruction *CxtI = nullptr);
243 /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
244 /// can fold the result. If not, this returns null.
245 Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
246 ArrayRef<unsigned> Idxs,
247 const DataLayout *TD = nullptr,
248 const TargetLibraryInfo *TLI = nullptr,
249 const DominatorTree *DT = nullptr,
250 AssumptionTracker *AT = nullptr,
251 const Instruction *CxtI = nullptr);
253 /// SimplifyTruncInst - Given operands for an TruncInst, see if we can fold
254 /// the result. If not, this returns null.
255 Value *SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *TD = nullptr,
256 const TargetLibraryInfo *TLI = nullptr,
257 const DominatorTree *DT = nullptr,
258 AssumptionTracker *AT = nullptr,
259 const Instruction *CxtI = nullptr);
261 //=== Helper functions for higher up the class hierarchy.
264 /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
265 /// fold the result. If not, this returns null.
266 Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
267 const DataLayout *TD = nullptr,
268 const TargetLibraryInfo *TLI = nullptr,
269 const DominatorTree *DT = nullptr,
270 AssumptionTracker *AT = nullptr,
271 const Instruction *CxtI = nullptr);
273 /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
274 /// fold the result. If not, this returns null.
275 Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
276 const DataLayout *TD = nullptr,
277 const TargetLibraryInfo *TLI = nullptr,
278 const DominatorTree *DT = nullptr,
279 AssumptionTracker *AT = nullptr,
280 const Instruction *CxtI = nullptr);
282 /// \brief Given a function and iterators over arguments, see if we can fold
285 /// If this call could not be simplified returns null.
286 Value *SimplifyCall(Value *V, User::op_iterator ArgBegin,
287 User::op_iterator ArgEnd, const DataLayout *TD = nullptr,
288 const TargetLibraryInfo *TLI = nullptr,
289 const DominatorTree *DT = nullptr,
290 AssumptionTracker *AT = nullptr,
291 const Instruction *CxtI = nullptr);
293 /// \brief Given a function and set of arguments, see if we can fold the
296 /// If this call could not be simplified returns null.
297 Value *SimplifyCall(Value *V, ArrayRef<Value *> Args,
298 const DataLayout *TD = nullptr,
299 const TargetLibraryInfo *TLI = nullptr,
300 const DominatorTree *DT = nullptr,
301 AssumptionTracker *AT = nullptr,
302 const Instruction *CxtI = nullptr);
304 /// SimplifyInstruction - See if we can compute a simplified version of this
305 /// instruction. If not, this returns null.
306 Value *SimplifyInstruction(Instruction *I, const DataLayout *TD = nullptr,
307 const TargetLibraryInfo *TLI = nullptr,
308 const DominatorTree *DT = nullptr,
309 AssumptionTracker *AT = nullptr);
312 /// \brief Replace all uses of 'I' with 'SimpleV' and simplify the uses
315 /// This first performs a normal RAUW of I with SimpleV. It then recursively
316 /// attempts to simplify those users updated by the operation. The 'I'
317 /// instruction must not be equal to the simplified value 'SimpleV'.
319 /// The function returns true if any simplifications were performed.
320 bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
321 const DataLayout *TD = nullptr,
322 const TargetLibraryInfo *TLI = nullptr,
323 const DominatorTree *DT = nullptr,
324 AssumptionTracker *AT = nullptr);
326 /// \brief Recursively attempt to simplify an instruction.
328 /// This routine uses SimplifyInstruction to simplify 'I', and if successful
329 /// replaces uses of 'I' with the simplified value. It then recurses on each
330 /// of the users impacted. It returns true if any simplifications were
332 bool recursivelySimplifyInstruction(Instruction *I,
333 const DataLayout *TD = nullptr,
334 const TargetLibraryInfo *TLI = nullptr,
335 const DominatorTree *DT = nullptr,
336 AssumptionTracker *AT = nullptr);
337 } // end namespace llvm