Coverage Report

Created: 2019-03-22 08:08

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/ValueLattice.h
Line
Count
Source (jump to first uncovered line)
1
//===- ValueLattice.h - Value constraint analysis ---------------*- 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
#ifndef LLVM_ANALYSIS_VALUELATTICE_H
10
#define LLVM_ANALYSIS_VALUELATTICE_H
11
12
#include "llvm/IR/ConstantRange.h"
13
#include "llvm/IR/Constants.h"
14
//
15
//===----------------------------------------------------------------------===//
16
//                               ValueLatticeElement
17
//===----------------------------------------------------------------------===//
18
19
/// This class represents lattice values for constants.
20
///
21
/// FIXME: This is basically just for bringup, this can be made a lot more rich
22
/// in the future.
23
///
24
25
namespace llvm {
26
class ValueLatticeElement {
27
  enum ValueLatticeElementTy {
28
    /// This Value has no known value yet.  As a result, this implies the
29
    /// producing instruction is dead.  Caution: We use this as the starting
30
    /// state in our local meet rules.  In this usage, it's taken to mean
31
    /// "nothing known yet".
32
    undefined,
33
34
    /// This Value has a specific constant value.  (For constant integers,
35
    /// constantrange is used instead.  Integer typed constantexprs can appear
36
    /// as constant.)
37
    constant,
38
39
    /// This Value is known to not have the specified value.  (For constant
40
    /// integers, constantrange is used instead.  As above, integer typed
41
    /// constantexprs can appear here.)
42
    notconstant,
43
44
    /// The Value falls within this range. (Used only for integer typed values.)
45
    constantrange,
46
47
    /// We can not precisely model the dynamic values this value might take.
48
    overdefined
49
  };
50
51
  ValueLatticeElementTy Tag;
52
53
  /// The union either stores a pointer to a constant or a constant range,
54
  /// associated to the lattice element. We have to ensure that Range is
55
  /// initialized or destroyed when changing state to or from constantrange.
56
  union {
57
    Constant *ConstVal;
58
    ConstantRange Range;
59
  };
60
61
public:
62
  // Const and Range are initialized on-demand.
63
260M
  ValueLatticeElement() : Tag(undefined) {}
64
65
  /// Custom destructor to ensure Range is properly destroyed, when the object
66
  /// is deallocated.
67
336M
  ~ValueLatticeElement() {
68
336M
    switch (Tag) {
69
336M
    case overdefined:
70
303M
    case undefined:
71
303M
    case constant:
72
303M
    case notconstant:
73
303M
      break;
74
303M
    case constantrange:
75
32.1M
      Range.~ConstantRange();
76
32.1M
      break;
77
336M
    };
78
336M
  }
79
80
  /// Custom copy constructor, to ensure Range gets initialized when
81
  /// copying a constant range lattice element.
82
75.4M
  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
83
75.4M
    *this = Other;
84
75.4M
  }
85
86
  /// Custom assignment operator, to ensure Range gets initialized when
87
  /// assigning a constant range lattice element.
88
223M
  ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
89
223M
    // If we change the state of this from constant range to non constant range,
90
223M
    // destroy Range.
91
223M
    if (isConstantRange() && 
!Other.isConstantRange()84.3k
)
92
1
      Range.~ConstantRange();
93
223M
94
223M
    // If we change the state of this from a valid ConstVal to another a state
95
223M
    // without a valid ConstVal, zero the pointer.
96
223M
    if ((isConstant() || 
isNotConstant()223M
) &&
!Other.isConstant()13.6k
&&
97
223M
        
!Other.isNotConstant()8.40k
)
98
0
      ConstVal = nullptr;
99
223M
100
223M
    switch (Other.Tag) {
101
223M
    case constantrange:
102
25.2M
      if (!isConstantRange())
103
25.1M
        new (&Range) ConstantRange(Other.Range);
104
84.3k
      else
105
84.3k
        Range = Other.Range;
106
25.2M
      break;
107
223M
    case constant:
108
46.8M
    case notconstant:
109
46.8M
      ConstVal = Other.ConstVal;
110
46.8M
      break;
111
151M
    case overdefined:
112
151M
    case undefined:
113
151M
      break;
114
223M
    }
115
223M
    Tag = Other.Tag;
116
223M
    return *this;
117
223M
  }
118
119
4.24M
  static ValueLatticeElement get(Constant *C) {
120
4.24M
    ValueLatticeElement Res;
121
4.24M
    if (!isa<UndefValue>(C))
122
4.24M
      Res.markConstant(C);
123
4.24M
    return Res;
124
4.24M
  }
125
4.52M
  static ValueLatticeElement getNot(Constant *C) {
126
4.52M
    ValueLatticeElement Res;
127
4.52M
    if (!isa<UndefValue>(C))
128
4.52M
      Res.markNotConstant(C);
129
4.52M
    return Res;
130
4.52M
  }
131
3.17M
  static ValueLatticeElement getRange(ConstantRange CR) {
132
3.17M
    ValueLatticeElement Res;
133
3.17M
    Res.markConstantRange(std::move(CR));
134
3.17M
    return Res;
135
3.17M
  }
136
90.8M
  static ValueLatticeElement getOverdefined() {
137
90.8M
    ValueLatticeElement Res;
138
90.8M
    Res.markOverdefined();
139
90.8M
    return Res;
140
90.8M
  }
141
142
81.8M
  bool isUndefined() const { return Tag == undefined; }
143
385M
  bool isConstant() const { return Tag == constant; }
144
334M
  bool isNotConstant() const { return Tag == notconstant; }
145
420M
  bool isConstantRange() const { return Tag == constantrange; }
146
236M
  bool isOverdefined() const { return Tag == overdefined; }
147
148
57.2k
  Constant *getConstant() const {
149
57.2k
    assert(isConstant() && "Cannot get the constant of a non-constant!");
150
57.2k
    return ConstVal;
151
57.2k
  }
152
153
4.33M
  Constant *getNotConstant() const {
154
4.33M
    assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
155
4.33M
    return ConstVal;
156
4.33M
  }
157
158
11.2M
  const ConstantRange &getConstantRange() const {
159
11.2M
    assert(isConstantRange() &&
160
11.2M
           "Cannot get the constant-range of a non-constant-range!");
161
11.2M
    return Range;
162
11.2M
  }
163
164
3.08M
  Optional<APInt> asConstantInteger() const {
165
3.08M
    if (isConstant() && 
isa<ConstantInt>(getConstant())407
) {
166
0
      return cast<ConstantInt>(getConstant())->getValue();
167
3.08M
    } else if (isConstantRange() && 
getConstantRange().isSingleElement()123k
) {
168
1.06k
      return *getConstantRange().getSingleElement();
169
1.06k
    }
170
3.08M
    return None;
171
3.08M
  }
172
173
private:
174
97.7M
  void markOverdefined() {
175
97.7M
    if (isOverdefined())
176
0
      return;
177
97.7M
    if (isConstant() || 
isNotConstant()97.7M
)
178
286k
      ConstVal = nullptr;
179
97.7M
    if (isConstantRange())
180
299k
      Range.~ConstantRange();
181
97.7M
    Tag = overdefined;
182
97.7M
  }
183
184
4.24M
  void markConstant(Constant *V) {
185
4.24M
    assert(V && "Marking constant with NULL");
186
4.24M
    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
187
3.58M
      markConstantRange(ConstantRange(CI->getValue()));
188
3.58M
      return;
189
3.58M
    }
190
653k
    if (isa<UndefValue>(V))
191
0
      return;
192
653k
193
653k
    assert((!isConstant() || getConstant() == V) &&
194
653k
           "Marking constant with different value");
195
653k
    assert(isUndefined());
196
653k
    Tag = constant;
197
653k
    ConstVal = V;
198
653k
  }
199
200
4.52M
  void markNotConstant(Constant *V) {
201
4.52M
    assert(V && "Marking constant with NULL");
202
4.52M
    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
203
493k
      markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
204
493k
      return;
205
493k
    }
206
4.03M
    if (isa<UndefValue>(V))
207
0
      return;
208
4.03M
209
4.03M
    assert((!isConstant() || getConstant() != V) &&
210
4.03M
           "Marking constant !constant with same value");
211
4.03M
    assert((!isNotConstant() || getNotConstant() == V) &&
212
4.03M
           "Marking !constant with different value");
213
4.03M
    assert(isUndefined() || isConstant());
214
4.03M
    Tag = notconstant;
215
4.03M
    ConstVal = V;
216
4.03M
  }
217
218
7.50M
  void markConstantRange(ConstantRange NewR) {
219
7.50M
    if (isConstantRange()) {
220
251k
      if (NewR.isEmptySet())
221
0
        markOverdefined();
222
251k
      else {
223
251k
        Range = std::move(NewR);
224
251k
      }
225
251k
      return;
226
251k
    }
227
7.25M
228
7.25M
    assert(isUndefined());
229
7.25M
    if (NewR.isEmptySet())
230
70
      markOverdefined();
231
7.25M
    else {
232
7.25M
      Tag = constantrange;
233
7.25M
      new (&Range) ConstantRange(std::move(NewR));
234
7.25M
    }
235
7.25M
  }
236
237
public:
238
  /// Updates this object to approximate both this object and RHS. Returns
239
  /// true if this object has been changed.
240
16.6M
  bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
241
16.6M
    if (RHS.isUndefined() || 
isOverdefined()16.4M
)
242
607k
      return false;
243
16.0M
    if (RHS.isOverdefined()) {
244
6.76M
      markOverdefined();
245
6.76M
      return true;
246
6.76M
    }
247
9.27M
248
9.27M
    if (isUndefined()) {
249
6.07M
      *this = RHS;
250
6.07M
      return !RHS.isUndefined();
251
6.07M
    }
252
3.19M
253
3.19M
    if (isConstant()) {
254
27.0k
      if (RHS.isConstant() && 
getConstant() == RHS.getConstant()15.3k
)
255
11.8k
        return false;
256
15.2k
      markOverdefined();
257
15.2k
      return true;
258
15.2k
    }
259
3.16M
260
3.16M
    if (isNotConstant()) {
261
2.14M
      if (RHS.isNotConstant() && 
getNotConstant() == RHS.getNotConstant()2.13M
)
262
2.13M
        return false;
263
11.5k
      markOverdefined();
264
11.5k
      return true;
265
11.5k
    }
266
1.02M
267
1.02M
    assert(isConstantRange() && "New ValueLattice type?");
268
1.02M
    if (!RHS.isConstantRange()) {
269
8
      // We can get here if we've encountered a constantexpr of integer type
270
8
      // and merge it with a constantrange.
271
8
      markOverdefined();
272
8
      return true;
273
8
    }
274
1.02M
    ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
275
1.02M
    if (NewR.isFullSet())
276
149k
      markOverdefined();
277
874k
    else if (NewR == getConstantRange())
278
622k
      return false;
279
251k
    else
280
251k
      markConstantRange(std::move(NewR));
281
1.02M
    
return true400k
;
282
1.02M
  }
283
284
  ConstantInt *getConstantInt() const {
285
    assert(isConstant() && isa<ConstantInt>(getConstant()) &&
286
           "No integer constant");
287
    return cast<ConstantInt>(getConstant());
288
  }
289
290
  /// Compares this symbolic value with Other using Pred and returns either
291
  /// true, false or undef constants, or nullptr if the comparison cannot be
292
  /// evaluated.
293
  Constant *getCompare(CmpInst::Predicate Pred, Type *Ty,
294
2.69M
                       const ValueLatticeElement &Other) const {
295
2.69M
    if (isUndefined() || 
Other.isUndefined()2.63M
)
296
94.0k
      return UndefValue::get(Ty);
297
2.60M
298
2.60M
    if (isConstant() && 
Other.isConstant()6.49k
)
299
6.01k
      return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
300
2.59M
301
2.59M
    // Integer constants are represented as ConstantRanges with single
302
2.59M
    // elements.
303
2.59M
    if (!isConstantRange() || 
!Other.isConstantRange()268k
)
304
2.49M
      return nullptr;
305
102k
306
102k
    const auto &CR = getConstantRange();
307
102k
    const auto &OtherCR = Other.getConstantRange();
308
102k
    if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
309
53.4k
      return ConstantInt::getTrue(Ty);
310
49.3k
    if (ConstantRange::makeSatisfyingICmpRegion(
311
49.3k
            CmpInst::getInversePredicate(Pred), OtherCR)
312
49.3k
            .contains(CR))
313
49.1k
      return ConstantInt::getFalse(Ty);
314
249
315
249
    return nullptr;
316
249
  }
317
};
318
319
raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
320
321
} // end namespace llvm
322
#endif