LLVM  6.0.0svn
InstructionSimplify.h
Go to the documentation of this file.
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 class Function;
39 template <typename T, typename... TArgs> class AnalysisManager;
40 template <class T> class ArrayRef;
41 class AssumptionCache;
42 class DominatorTree;
43 class Instruction;
44 class ImmutableCallSite;
45 class DataLayout;
46 class FastMathFlags;
49 class Pass;
50 class TargetLibraryInfo;
51 class Type;
52 class Value;
53 
54 struct SimplifyQuery {
55  const DataLayout &DL;
56  const TargetLibraryInfo *TLI = nullptr;
57  const DominatorTree *DT = nullptr;
58  AssumptionCache *AC = nullptr;
59  const Instruction *CxtI = nullptr;
60 
61  SimplifyQuery(const DataLayout &DL, const Instruction *CXTI = nullptr)
62  : DL(DL), CxtI(CXTI) {}
63 
65  const DominatorTree *DT = nullptr,
66  AssumptionCache *AC = nullptr,
67  const Instruction *CXTI = nullptr)
68  : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI) {}
70  SimplifyQuery Copy(*this);
71  Copy.CxtI = I;
72  return Copy;
73  }
74 };
75 
76 // NOTE: the explicit multiple argument versions of these functions are
77 // deprecated.
78 // Please use the SimplifyQuery versions in new code.
79 
80 /// Given operands for an Add, fold the result or return null.
81 Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
82  const SimplifyQuery &Q);
83 
84 /// Given operands for a Sub, fold the result or return null.
85 Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
86  const SimplifyQuery &Q);
87 
88 /// Given operands for an FAdd, fold the result or return null.
90  const SimplifyQuery &Q);
91 
92 /// Given operands for an FSub, fold the result or return null.
94  const SimplifyQuery &Q);
95 
96 /// Given operands for an FMul, fold the result or return null.
98  const SimplifyQuery &Q);
99 
100 /// Given operands for a Mul, fold the result or return null.
101 Value *SimplifyMulInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
102 
103 /// Given operands for an SDiv, fold the result or return null.
104 Value *SimplifySDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
105 
106 /// Given operands for a UDiv, fold the result or return null.
107 Value *SimplifyUDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
108 
109 /// Given operands for an FDiv, fold the result or return null.
111  const SimplifyQuery &Q);
112 
113 /// Given operands for an SRem, fold the result or return null.
114 Value *SimplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
115 
116 /// Given operands for a URem, fold the result or return null.
117 Value *SimplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
118 
119 /// Given operands for an FRem, fold the result or return null.
121  const SimplifyQuery &Q);
122 
123 /// Given operands for a Shl, fold the result or return null.
124 Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
125  const SimplifyQuery &Q);
126 
127 /// Given operands for a LShr, fold the result or return null.
128 Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
129  const SimplifyQuery &Q);
130 
131 /// Given operands for a AShr, fold the result or return nulll.
132 Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
133  const SimplifyQuery &Q);
134 
135 /// Given operands for an And, fold the result or return null.
136 Value *SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
137 
138 /// Given operands for an Or, fold the result or return null.
139 Value *SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
140 
141 /// Given operands for an Xor, fold the result or return null.
142 Value *SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q);
143 
144 /// Given operands for an ICmpInst, fold the result or return null.
145 Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
146  const SimplifyQuery &Q);
147 
148 /// Given operands for an FCmpInst, fold the result or return null.
149 Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
150  FastMathFlags FMF, const SimplifyQuery &Q);
151 
152 /// Given operands for a SelectInst, fold the result or return null.
153 Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
154  const SimplifyQuery &Q);
155 
156 /// Given operands for a GetElementPtrInst, fold the result or return null.
158  const SimplifyQuery &Q);
159 
160 /// Given operands for an InsertValueInst, fold the result or return null.
162  const SimplifyQuery &Q);
163 
164 /// Given operands for an InsertElement, fold the result or return null.
166  const SimplifyQuery &Q);
167 
168 /// Given operands for an ExtractValueInst, fold the result or return null.
170  const SimplifyQuery &Q);
171 
172 /// Given operands for an ExtractElementInst, fold the result or return null.
174  const SimplifyQuery &Q);
175 
176 /// Given operands for a CastInst, fold the result or return null.
177 Value *SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty,
178  const SimplifyQuery &Q);
179 
180 /// Given operands for a ShuffleVectorInst, fold the result or return null.
182  Type *RetTy, const SimplifyQuery &Q);
183 
184 //=== Helper functions for higher up the class hierarchy.
185 
186 /// Given operands for a CmpInst, fold the result or return null.
187 Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
188  const SimplifyQuery &Q);
189 
190 /// Given operands for a BinaryOperator, fold the result or return null.
191 Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
192  const SimplifyQuery &Q);
193 
194 /// Given operands for an FP BinaryOperator, fold the result or return null.
195 /// In contrast to SimplifyBinOp, try to use FastMathFlag when folding the
196 /// result. In case we don't need FastMathFlags, simply fall to SimplifyBinOp.
197 Value *SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS,
198  FastMathFlags FMF, const SimplifyQuery &Q);
199 
200 /// Given a function and iterators over arguments, fold the result or return
201 /// null.
203  User::op_iterator ArgEnd, const SimplifyQuery &Q);
204 
205 /// Given a function and set of arguments, fold the result or return null.
207  const SimplifyQuery &Q);
208 
209 /// See if we can compute a simplified version of this instruction. If not,
210 /// return null.
212  OptimizationRemarkEmitter *ORE = nullptr);
213 
214 /// Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
215 ///
216 /// This first performs a normal RAUW of I with SimpleV. It then recursively
217 /// attempts to simplify those users updated by the operation. The 'I'
218 /// instruction must not be equal to the simplified value 'SimpleV'.
219 ///
220 /// The function returns true if any simplifications were performed.
222  const TargetLibraryInfo *TLI = nullptr,
223  const DominatorTree *DT = nullptr,
224  AssumptionCache *AC = nullptr);
225 
226 /// Recursively attempt to simplify an instruction.
227 ///
228 /// This routine uses SimplifyInstruction to simplify 'I', and if successful
229 /// replaces uses of 'I' with the simplified value. It then recurses on each
230 /// of the users impacted. It returns true if any simplifications were
231 /// performed.
233  const TargetLibraryInfo *TLI = nullptr,
234  const DominatorTree *DT = nullptr,
235  AssumptionCache *AC = nullptr);
236 
237 // These helper functions return a SimplifyQuery structure that contains as
238 // many of the optional analysis we use as are currently valid. This is the
239 // strongly preferred way of constructing SimplifyQuery in passes.
241 template <class T, class... TArgs>
243  Function &);
245  const DataLayout &);
246 } // end namespace llvm
247 
248 #endif
249 
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
Value * SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an ICmpInst, fold the result or return null.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
Value * SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FCmpInst, fold the result or return null.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
SimplifyQuery getWithInstruction(Instruction *I) const
const Instruction * CxtI
A cache of .assume calls within a function.
SimplifyQuery(const DataLayout &DL, const TargetLibraryInfo *TLI, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, const Instruction *CXTI=nullptr)
Value * SimplifySDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an SDiv, fold the result or return null.
Value * SimplifyUDivInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a UDiv, fold the result or return null.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Value * SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for a Shl, fold the result or return null.
const SimplifyQuery getBestSimplifyQuery(Pass &, Function &)
const TargetLibraryInfo * TLI
Value * SimplifyOrInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Or, fold the result or return null.
Value * SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q)
Given operands for a LShr, fold the result or return null.
Value * SimplifyFPBinOp(unsigned Opcode, Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FP BinaryOperator, fold the result or return null.
Value * SimplifyExtractValueInst(Value *Agg, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an ExtractValueInst, fold the result or return null.
SimplifyQuery(const DataLayout &DL, const Instruction *CXTI=nullptr)
Value * SimplifyCall(ImmutableCallSite CS, Value *V, User::op_iterator ArgBegin, User::op_iterator ArgEnd, const SimplifyQuery &Q)
Given a function and iterators over arguments, fold the result or return null.
Value * SimplifyGEPInst(Type *SrcTy, ArrayRef< Value *> Ops, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
Value * SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FAdd, fold the result or return null.
Value * SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a CmpInst, fold the result or return null.
#define T
Value * SimplifyMulInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a Mul, fold the result or return null.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
Value * SimplifyInsertElementInst(Value *Vec, Value *Elt, Value *Idx, const SimplifyQuery &Q)
Given operands for an InsertElement, fold the result or return null.
Value * SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, const SimplifyQuery &Q)
Given operands for a SelectInst, fold the result or return null.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
Value * SimplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a URem, fold the result or return null.
This is an important base class in LLVM.
Definition: Constant.h:42
Value * SimplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
Value * SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
Value * SimplifyFDivInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FDiv, fold the result or return null.
Value * SimplifyFRemInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FRem, fold the result or return null.
Value * SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask, Type *RetTy, const SimplifyQuery &Q)
Given operands for a ShuffleVectorInst, fold the result or return null.
bool recursivelySimplifyInstruction(Instruction *I, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr)
Recursively attempt to simplify an instruction.
Provides information about what library functions are available for the current target.
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:27
Value * SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FSub, fold the result or return null.
Value * SimplifyFMulInst(Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FMul, fold the result or return null.
Value * SimplifyAndInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an And, fold the result or return null.
Establish a view to a call site for examination.
Definition: CallSite.h:713
Value * SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, const SimplifyQuery &Q)
Given operands for a AShr, fold the result or return nulll.
#define I(x, y, z)
Definition: MD5.cpp:58
AssumptionCache * AC
Value * SimplifyXorInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an Xor, fold the result or return null.
Value * SimplifySRemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an SRem, fold the result or return null.
Value * SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a BinaryOperator, fold the result or return null.
LLVM Value Representation.
Definition: Value.h:73
Value * SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &Q)
Given operands for an ExtractElementInst, fold the result or return null.
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
const DataLayout & DL
Value * SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, const SimplifyQuery &Q)
Given operands for a Sub, fold the result or return null.
Value * SimplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const SimplifyQuery &Q)
Given operands for an InsertValueInst, fold the result or return null.
Convenience struct for specifying and reasoning about fast-math flags.
Definition: Operator.h:160
const DominatorTree * DT
A container for analyses that lazily runs them and caches their results.
bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr)
Replace all uses of &#39;I&#39; with &#39;SimpleV&#39; and simplify the uses recursively.
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
The optimization diagnostic interface.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.