Coverage Report

Created: 2018-09-23 16:00

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/InstructionSimplify.h
Line
Count
Source (jump to first uncovered line)
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
330M
  InstrInfoQuery(bool UMD) : UseInstrInfo(UMD) {}
62
188M
  InstrInfoQuery() : UseInstrInfo(true) {}
63
  bool UseInstrInfo = true;
64
65
207M
  MDNode *getMetadata(const Instruction *I, unsigned KindID) const {
66
207M
    if (UseInstrInfo)
67
207M
      return I->getMetadata(KindID);
68
933
    return nullptr;
69
933
  }
70
71
6.06M
  template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const {
72
6.06M
    if (UseInstrInfo)
73
6.06M
      return Op->hasNoUnsignedWrap();
74
60
    return false;
75
60
  }
bool llvm::InstrInfoQuery::hasNoUnsignedWrap<llvm::OverflowingBinaryOperator>(llvm::OverflowingBinaryOperator const*) const
Line
Count
Source
71
2.46M
  template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const {
72
2.46M
    if (UseInstrInfo)
73
2.46M
      return Op->hasNoUnsignedWrap();
74
60
    return false;
75
60
  }
bool llvm::InstrInfoQuery::hasNoUnsignedWrap<llvm::BinaryOperator>(llvm::BinaryOperator const*) const
Line
Count
Source
71
3.60M
  template <class InstT> bool hasNoUnsignedWrap(const InstT *Op) const {
72
3.60M
    if (UseInstrInfo)
73
3.60M
      return Op->hasNoUnsignedWrap();
74
0
    return false;
75
0
  }
76
77
116M
  template <class InstT> bool hasNoSignedWrap(const InstT *Op) const {
78
116M
    if (UseInstrInfo)
79
116M
      return Op->hasNoSignedWrap();
80
325
    return false;
81
325
  }
bool llvm::InstrInfoQuery::hasNoSignedWrap<llvm::OverflowingBinaryOperator>(llvm::OverflowingBinaryOperator const*) const
Line
Count
Source
77
111M
  template <class InstT> bool hasNoSignedWrap(const InstT *Op) const {
78
111M
    if (UseInstrInfo)
79
111M
      return Op->hasNoSignedWrap();
80
325
    return false;
81
325
  }
bool llvm::InstrInfoQuery::hasNoSignedWrap<llvm::BinaryOperator>(llvm::BinaryOperator const*) const
Line
Count
Source
77
3.62M
  template <class InstT> bool hasNoSignedWrap(const InstT *Op) const {
78
3.62M
    if (UseInstrInfo)
79
3.62M
      return Op->hasNoSignedWrap();
80
0
    return false;
81
0
  }
bool llvm::InstrInfoQuery::hasNoSignedWrap<llvm::Instruction>(llvm::Instruction const*) const
Line
Count
Source
77
669k
  template <class InstT> bool hasNoSignedWrap(const InstT *Op) const {
78
669k
    if (UseInstrInfo)
79
669k
      return Op->hasNoSignedWrap();
80
0
    return false;
81
0
  }
82
83
491k
  bool isExact(const BinaryOperator *Op) const {
84
491k
    if (UseInstrInfo && isa<PossiblyExactOperator>(Op))
85
491k
      return cast<PossiblyExactOperator>(Op)->isExact();
86
0
    return false;
87
0
  }
88
};
89
90
struct SimplifyQuery {
91
  const DataLayout &DL;
92
  const TargetLibraryInfo *TLI = nullptr;
93
  const DominatorTree *DT = nullptr;
94
  AssumptionCache *AC = nullptr;
95
  const Instruction *CxtI = nullptr;
96
97
  // Wrapper to query additional information for instructions like metadata or
98
  // keywords like nsw, which provides conservative results if those cannot
99
  // be safely used.
100
  const InstrInfoQuery IIQ;
101
102
  SimplifyQuery(const DataLayout &DL, const Instruction *CXTI = nullptr)
103
188M
      : DL(DL), CxtI(CXTI) {}
104
105
  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
46.6M
      : DL(DL), TLI(TLI), DT(DT), AC(AC), CxtI(CXTI), IIQ(UseInstrInfo) {}
110
209M
  SimplifyQuery getWithInstruction(Instruction *I) const {
111
209M
    SimplifyQuery Copy(*this);
112
209M
    Copy.CxtI = I;
113
209M
    return Copy;
114
209M
  }
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
/// Given operands for an FAdd, fold the result or return null.
130
Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF,
131
                        const SimplifyQuery &Q);
132
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