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