• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/User.h"
36 
37 namespace llvm {
38   template<typename T>
39   class ArrayRef;
40   class AssumptionCache;
41   class DominatorTree;
42   class Instruction;
43   class DataLayout;
44   class FastMathFlags;
45   class TargetLibraryInfo;
46   class Type;
47   class Value;
48 
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 &DL,
53                          const TargetLibraryInfo *TLI = nullptr,
54                          const DominatorTree *DT = nullptr,
55                          AssumptionCache *AC = nullptr,
56                          const Instruction *CxtI = nullptr);
57 
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 &DL,
62                          const TargetLibraryInfo *TLI = nullptr,
63                          const DominatorTree *DT = nullptr,
64                          AssumptionCache *AC = nullptr,
65                          const Instruction *CxtI = nullptr);
66 
67   /// Given operands for an FAdd, see if we can fold the result.  If not, this
68   /// returns null.
69   Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
70                           const DataLayout &DL,
71                           const TargetLibraryInfo *TLI = nullptr,
72                           const DominatorTree *DT = nullptr,
73                           AssumptionCache *AC = nullptr,
74                           const Instruction *CxtI = nullptr);
75 
76   /// Given operands for an FSub, see if we can fold the result.  If not, this
77   /// returns null.
78   Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF,
79                           const DataLayout &DL,
80                           const TargetLibraryInfo *TLI = nullptr,
81                           const DominatorTree *DT = nullptr,
82                           AssumptionCache *AC = nullptr,
83                           const Instruction *CxtI = nullptr);
84 
85   /// Given operands for an FMul, see if we can fold the result.  If not, this
86   /// returns null.
87   Value *SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF,
88                           const DataLayout &DL,
89                           const TargetLibraryInfo *TLI = nullptr,
90                           const DominatorTree *DT = nullptr,
91                           AssumptionCache *AC = nullptr,
92                           const Instruction *CxtI = nullptr);
93 
94   /// SimplifyMulInst - Given operands for a Mul, see if we can
95   /// fold the result.  If not, this returns null.
96   Value *SimplifyMulInst(Value *LHS, Value *RHS, const DataLayout &DL,
97                          const TargetLibraryInfo *TLI = nullptr,
98                          const DominatorTree *DT = nullptr,
99                          AssumptionCache *AC = nullptr,
100                          const Instruction *CxtI = nullptr);
101 
102   /// SimplifySDivInst - Given operands for an SDiv, see if we can
103   /// fold the result.  If not, this returns null.
104   Value *SimplifySDivInst(Value *LHS, Value *RHS, const DataLayout &DL,
105                           const TargetLibraryInfo *TLI = nullptr,
106                           const DominatorTree *DT = nullptr,
107                           AssumptionCache *AC = nullptr,
108                           const Instruction *CxtI = nullptr);
109 
110   /// SimplifyUDivInst - Given operands for a UDiv, see if we can
111   /// fold the result.  If not, this returns null.
112   Value *SimplifyUDivInst(Value *LHS, Value *RHS, const DataLayout &DL,
113                           const TargetLibraryInfo *TLI = nullptr,
114                           const DominatorTree *DT = nullptr,
115                           AssumptionCache *AC = nullptr,
116                           const Instruction *CxtI = nullptr);
117 
118   /// SimplifyFDivInst - Given operands for an FDiv, see if we can
119   /// fold the result.  If not, this returns null.
120   Value *SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF,
121                           const DataLayout &DL,
122                           const TargetLibraryInfo *TLI = nullptr,
123                           const DominatorTree *DT = nullptr,
124                           AssumptionCache *AC = nullptr,
125                           const Instruction *CxtI = nullptr);
126 
127   /// SimplifySRemInst - Given operands for an SRem, see if we can
128   /// fold the result.  If not, this returns null.
129   Value *SimplifySRemInst(Value *LHS, Value *RHS, const DataLayout &DL,
130                           const TargetLibraryInfo *TLI = nullptr,
131                           const DominatorTree *DT = nullptr,
132                           AssumptionCache *AC = nullptr,
133                           const Instruction *CxtI = nullptr);
134 
135   /// SimplifyURemInst - Given operands for a URem, see if we can
136   /// fold the result.  If not, this returns null.
137   Value *SimplifyURemInst(Value *LHS, Value *RHS, const DataLayout &DL,
138                           const TargetLibraryInfo *TLI = nullptr,
139                           const DominatorTree *DT = nullptr,
140                           AssumptionCache *AC = nullptr,
141                           const Instruction *CxtI = nullptr);
142 
143   /// SimplifyFRemInst - Given operands for an FRem, see if we can
144   /// fold the result.  If not, this returns null.
145   Value *SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF,
146                           const DataLayout &DL,
147                           const TargetLibraryInfo *TLI = nullptr,
148                           const DominatorTree *DT = nullptr,
149                           AssumptionCache *AC = nullptr,
150                           const Instruction *CxtI = nullptr);
151 
152   /// SimplifyShlInst - Given operands for a Shl, see if we can
153   /// fold the result.  If not, this returns null.
154   Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
155                          const DataLayout &DL,
156                          const TargetLibraryInfo *TLI = nullptr,
157                          const DominatorTree *DT = nullptr,
158                          AssumptionCache *AC = nullptr,
159                          const Instruction *CxtI = nullptr);
160 
161   /// SimplifyLShrInst - Given operands for a LShr, see if we can
162   /// fold the result.  If not, this returns null.
163   Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
164                           const DataLayout &DL,
165                           const TargetLibraryInfo *TLI = nullptr,
166                           const DominatorTree *DT = nullptr,
167                           AssumptionCache *AC = nullptr,
168                           const Instruction *CxtI = nullptr);
169 
170   /// SimplifyAShrInst - Given operands for a AShr, see if we can
171   /// fold the result.  If not, this returns null.
172   Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
173                           const DataLayout &DL,
174                           const TargetLibraryInfo *TLI = nullptr,
175                           const DominatorTree *DT = nullptr,
176                           AssumptionCache *AC = nullptr,
177                           const Instruction *CxtI = nullptr);
178 
179   /// SimplifyAndInst - Given operands for an And, see if we can
180   /// fold the result.  If not, this returns null.
181   Value *SimplifyAndInst(Value *LHS, Value *RHS, const DataLayout &DL,
182                          const TargetLibraryInfo *TLI = nullptr,
183                          const DominatorTree *DT = nullptr,
184                          AssumptionCache *AC = nullptr,
185                          const Instruction *CxtI = nullptr);
186 
187   /// SimplifyOrInst - Given operands for an Or, see if we can
188   /// fold the result.  If not, this returns null.
189   Value *SimplifyOrInst(Value *LHS, Value *RHS, const DataLayout &DL,
190                         const TargetLibraryInfo *TLI = nullptr,
191                         const DominatorTree *DT = nullptr,
192                         AssumptionCache *AC = nullptr,
193                         const Instruction *CxtI = nullptr);
194 
195   /// SimplifyXorInst - Given operands for a Xor, see if we can
196   /// fold the result.  If not, this returns null.
197   Value *SimplifyXorInst(Value *LHS, Value *RHS, const DataLayout &DL,
198                          const TargetLibraryInfo *TLI = nullptr,
199                          const DominatorTree *DT = nullptr,
200                          AssumptionCache *AC = nullptr,
201                          const Instruction *CxtI = nullptr);
202 
203   /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
204   /// fold the result.  If not, this returns null.
205   Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
206                           const DataLayout &DL,
207                           const TargetLibraryInfo *TLI = nullptr,
208                           const DominatorTree *DT = nullptr,
209                           AssumptionCache *AC = nullptr,
210                           Instruction *CxtI = nullptr);
211 
212   /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
213   /// fold the result.  If not, this returns null.
214   Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
215                           FastMathFlags FMF, const DataLayout &DL,
216                           const TargetLibraryInfo *TLI = nullptr,
217                           const DominatorTree *DT = nullptr,
218                           AssumptionCache *AC = nullptr,
219                           const Instruction *CxtI = nullptr);
220 
221   /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
222   /// the result.  If not, this returns null.
223   Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
224                             const DataLayout &DL,
225                             const TargetLibraryInfo *TLI = nullptr,
226                             const DominatorTree *DT = nullptr,
227                             AssumptionCache *AC = nullptr,
228                             const Instruction *CxtI = nullptr);
229 
230   /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
231   /// fold the result.  If not, this returns null.
232   Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout &DL,
233                          const TargetLibraryInfo *TLI = nullptr,
234                          const DominatorTree *DT = nullptr,
235                          AssumptionCache *AC = nullptr,
236                          const Instruction *CxtI = nullptr);
237 
238   /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
239   /// can fold the result.  If not, this returns null.
240   Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
241                                  ArrayRef<unsigned> Idxs, const DataLayout &DL,
242                                  const TargetLibraryInfo *TLI = nullptr,
243                                  const DominatorTree *DT = nullptr,
244                                  AssumptionCache *AC = nullptr,
245                                  const Instruction *CxtI = nullptr);
246 
247   /// \brief Given operands for an ExtractValueInst, see if we can fold the
248   /// result.  If not, this returns null.
249   Value *SimplifyExtractValueInst(Value *Agg, ArrayRef<unsigned> Idxs,
250                                   const DataLayout &DL,
251                                   const TargetLibraryInfo *TLI = nullptr,
252                                   const DominatorTree *DT = nullptr,
253                                   AssumptionCache *AC = nullptr,
254                                   const Instruction *CxtI = nullptr);
255 
256   /// \brief Given operands for an ExtractElementInst, see if we can fold the
257   /// result.  If not, this returns null.
258   Value *SimplifyExtractElementInst(Value *Vec, Value *Idx,
259                                     const DataLayout &DL,
260                                     const TargetLibraryInfo *TLI = nullptr,
261                                     const DominatorTree *DT = nullptr,
262                                     AssumptionCache *AC = nullptr,
263                                     const Instruction *CxtI = nullptr);
264 
265   /// SimplifyTruncInst - Given operands for an TruncInst, see if we can fold
266   /// the result.  If not, this returns null.
267   Value *SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout &DL,
268                            const TargetLibraryInfo *TLI = nullptr,
269                            const DominatorTree *DT = nullptr,
270                            AssumptionCache *AC = nullptr,
271                            const Instruction *CxtI = nullptr);
272 
273   //=== Helper functions for higher up the class hierarchy.
274 
275 
276   /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
277   /// fold the result.  If not, this returns null.
278   Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
279                          const DataLayout &DL,
280                          const TargetLibraryInfo *TLI = nullptr,
281                          const DominatorTree *DT = nullptr,
282                          AssumptionCache *AC = nullptr,
283                          const Instruction *CxtI = nullptr);
284 
285   /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
286   /// fold the result.  If not, this returns null.
287   Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
288                        const DataLayout &DL,
289                        const TargetLibraryInfo *TLI = nullptr,
290                        const DominatorTree *DT = nullptr,
291                        AssumptionCache *AC = nullptr,
292                        const Instruction *CxtI = nullptr);
293   /// SimplifyFPBinOp - Given operands for a BinaryOperator, see if we can
294   /// fold the result.  If not, this returns null.
295   /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
296   /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
297   Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
298                          const FastMathFlags &FMF, const DataLayout &DL,
299                          const TargetLibraryInfo *TLI = nullptr,
300                          const DominatorTree *DT = nullptr,
301                          AssumptionCache *AC = nullptr,
302                          const Instruction *CxtI = nullptr);
303 
304   /// \brief Given a function and iterators over arguments, see if we can fold
305   /// the result.
306   ///
307   /// If this call could not be simplified returns null.
308   Value *SimplifyCall(Value *V, User::op_iterator ArgBegin,
309                       User::op_iterator ArgEnd, const DataLayout &DL,
310                       const TargetLibraryInfo *TLI = nullptr,
311                       const DominatorTree *DT = nullptr,
312                       AssumptionCache *AC = nullptr,
313                       const Instruction *CxtI = nullptr);
314 
315   /// \brief Given a function and set of arguments, see if we can fold the
316   /// result.
317   ///
318   /// If this call could not be simplified returns null.
319   Value *SimplifyCall(Value *V, ArrayRef<Value *> Args, const DataLayout &DL,
320                       const TargetLibraryInfo *TLI = nullptr,
321                       const DominatorTree *DT = nullptr,
322                       AssumptionCache *AC = nullptr,
323                       const Instruction *CxtI = nullptr);
324 
325   /// SimplifyInstruction - See if we can compute a simplified version of this
326   /// instruction.  If not, this returns null.
327   Value *SimplifyInstruction(Instruction *I, const DataLayout &DL,
328                              const TargetLibraryInfo *TLI = nullptr,
329                              const DominatorTree *DT = nullptr,
330                              AssumptionCache *AC = nullptr);
331 
332   /// \brief Replace all uses of 'I' with 'SimpleV' and simplify the uses
333   /// recursively.
334   ///
335   /// This first performs a normal RAUW of I with SimpleV. It then recursively
336   /// attempts to simplify those users updated by the operation. The 'I'
337   /// instruction must not be equal to the simplified value 'SimpleV'.
338   ///
339   /// The function returns true if any simplifications were performed.
340   bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
341                                      const TargetLibraryInfo *TLI = nullptr,
342                                      const DominatorTree *DT = nullptr,
343                                      AssumptionCache *AC = nullptr);
344 
345   /// \brief Recursively attempt to simplify an instruction.
346   ///
347   /// This routine uses SimplifyInstruction to simplify 'I', and if successful
348   /// replaces uses of 'I' with the simplified value. It then recurses on each
349   /// of the users impacted. It returns true if any simplifications were
350   /// performed.
351   bool recursivelySimplifyInstruction(Instruction *I,
352                                       const TargetLibraryInfo *TLI = nullptr,
353                                       const DominatorTree *DT = nullptr,
354                                       AssumptionCache *AC = nullptr);
355 } // end namespace llvm
356 
357 #endif
358 
359