Coverage Report

Created: 2019-04-21 11:35

/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
35.3M
  ValueLatticeElement() : Tag(undefined) {}
64
65
  /// Custom destructor to ensure Range is properly destroyed, when the object
66
  /// is deallocated.
67
45.4M
  ~ValueLatticeElement() {
68
45.4M
    switch (Tag) {
69
45.4M
    case overdefined:
70
40.9M
    case undefined:
71
40.9M
    case constant:
72
40.9M
    case notconstant:
73
40.9M
      break;
74
40.9M
    case constantrange:
75
4.51M
      Range.~ConstantRange();
76
4.51M
      break;
77
45.4M
    };
78
45.4M
  }
79
80
  /// Custom copy constructor, to ensure Range gets initialized when
81
  /// copying a constant range lattice element.
82
10.0M
  ValueLatticeElement(const ValueLatticeElement &Other) : Tag(undefined) {
83
10.0M
    *this = Other;
84
10.0M
  }
85
86
  /// Custom assignment operator, to ensure Range gets initialized when
87
  /// assigning a constant range lattice element.
88
30.0M
  ValueLatticeElement &operator=(const ValueLatticeElement &Other) {
89
30.0M
    // If we change the state of this from constant range to non constant range,
90
30.0M
    // destroy Range.
91
30.0M
    if (isConstantRange() && 
!Other.isConstantRange()11.7k
)
92
1
      Range.~ConstantRange();
93
30.0M
94
30.0M
    // If we change the state of this from a valid ConstVal to another a state
95
30.0M
    // without a valid ConstVal, zero the pointer.
96
30.0M
    if ((isConstant() || 
isNotConstant()30.0M
) &&
!Other.isConstant()2.49k
&&
97
30.0M
        
!Other.isNotConstant()1.35k
)
98
0
      ConstVal = nullptr;
99
30.0M
100
30.0M
    switch (Other.Tag) {
101
30.0M
    case constantrange:
102
3.54M
      if (!isConstantRange())
103
3.53M
        new (&Range) ConstantRange(Other.Range);
104
11.7k
      else
105
11.7k
        Range = Other.Range;
106
3.54M
      break;
107
30.0M
    case constant:
108
6.41M
    case notconstant:
109
6.41M
      ConstVal = Other.ConstVal;
110
6.41M
      break;
111
20.0M
    case overdefined:
112
20.0M
    case undefined:
113
20.0M
      break;
114
30.0M
    }
115
30.0M
    Tag = Other.Tag;
116
30.0M
    return *this;
117
30.0M
  }
118
119
614k
  static ValueLatticeElement get(Constant *C) {
120
614k
    ValueLatticeElement Res;
121
614k
    if (!isa<UndefValue>(C))
122
614k
      Res.markConstant(C);
123
614k
    return Res;
124
614k
  }
125
627k
  static ValueLatticeElement getNot(Constant *C) {
126
627k
    ValueLatticeElement Res;
127
627k
    if (!isa<UndefValue>(C))
128
627k
      Res.markNotConstant(C);
129
627k
    return Res;
130
627k
  }
131
420k
  static ValueLatticeElement getRange(ConstantRange CR) {
132
420k
    ValueLatticeElement Res;
133
420k
    Res.markConstantRange(std::move(CR));
134
420k
    return Res;
135
420k
  }
136
12.1M
  static ValueLatticeElement getOverdefined() {
137
12.1M
    ValueLatticeElement Res;
138
12.1M
    Res.markOverdefined();
139
12.1M
    return Res;
140
12.1M
  }
141
142
11.0M
  bool isUndefined() const { return Tag == undefined; }
143
51.7M
  bool isConstant() const { return Tag == constant; }
144
44.7M
  bool isNotConstant() const { return Tag == notconstant; }
145
56.7M
  bool isConstantRange() const { return Tag == constantrange; }
146
31.8M
  bool isOverdefined() const { return Tag == overdefined; }
147
148
11.8k
  Constant *getConstant() const {
149
11.8k
    assert(isConstant() && "Cannot get the constant of a non-constant!");
150
11.8k
    return ConstVal;
151
11.8k
  }
152
153
454k
  Constant *getNotConstant() const {
154
454k
    assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
155
454k
    return ConstVal;
156
454k
  }
157
158
1.59M
  const ConstantRange &getConstantRange() const {
159
1.59M
    assert(isConstantRange() &&
160
1.59M
           "Cannot get the constant-range of a non-constant-range!");
161
1.59M
    return Range;
162
1.59M
  }
163
164
349k
  Optional<APInt> asConstantInteger() const {
165
349k
    if (isConstant() && 
isa<ConstantInt>(getConstant())11
) {
166
0
      return cast<ConstantInt>(getConstant())->getValue();
167
349k
    } else if (isConstantRange() && 
getConstantRange().isSingleElement()12.1k
) {
168
181
      return *getConstantRange().getSingleElement();
169
181
    }
170
349k
    return None;
171
349k
  }
172
173
private:
174
13.1M
  void markOverdefined() {
175
13.1M
    if (isOverdefined())
176
0
      return;
177
13.1M
    if (isConstant() || 
isNotConstant()13.1M
)
178
37.7k
      ConstVal = nullptr;
179
13.1M
    if (isConstantRange())
180
40.1k
      Range.~ConstantRange();
181
13.1M
    Tag = overdefined;
182
13.1M
  }
183
184
614k
  void markConstant(Constant *V) {
185
614k
    assert(V && "Marking constant with NULL");
186
614k
    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
187
521k
      markConstantRange(ConstantRange(CI->getValue()));
188
521k
      return;
189
521k
    }
190
92.8k
    if (isa<UndefValue>(V))
191
0
      return;
192
92.8k
193
92.8k
    assert((!isConstant() || getConstant() == V) &&
194
92.8k
           "Marking constant with different value");
195
92.8k
    assert(isUndefined());
196
92.8k
    Tag = constant;
197
92.8k
    ConstVal = V;
198
92.8k
  }
199
200
627k
  void markNotConstant(Constant *V) {
201
627k
    assert(V && "Marking constant with NULL");
202
627k
    if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
203
77.5k
      markConstantRange(ConstantRange(CI->getValue() + 1, CI->getValue()));
204
77.5k
      return;
205
77.5k
    }
206
549k
    if (isa<UndefValue>(V))
207
0
      return;
208
549k
209
549k
    assert((!isConstant() || getConstant() != V) &&
210
549k
           "Marking constant !constant with same value");
211
549k
    assert((!isNotConstant() || getNotConstant() == V) &&
212
549k
           "Marking !constant with different value");
213
549k
    assert(isUndefined() || isConstant());
214
549k
    Tag = notconstant;
215
549k
    ConstVal = V;
216
549k
  }
217
218
1.05M
  void markConstantRange(ConstantRange NewR) {
219
1.05M
    if (isConstantRange()) {
220
39.0k
      if (NewR.isEmptySet())
221
0
        markOverdefined();
222
39.0k
      else {
223
39.0k
        Range = std::move(NewR);
224
39.0k
      }
225
39.0k
      return;
226
39.0k
    }
227
1.01M
228
1.01M
    assert(isUndefined());
229
1.01M
    if (NewR.isEmptySet())
230
27
      markOverdefined();
231
1.01M
    else {
232
1.01M
      Tag = constantrange;
233
1.01M
      new (&Range) ConstantRange(std::move(NewR));
234
1.01M
    }
235
1.01M
  }
236
237
public:
238
  /// Updates this object to approximate both this object and RHS. Returns
239
  /// true if this object has been changed.
240
2.26M
  bool mergeIn(const ValueLatticeElement &RHS, const DataLayout &DL) {
241
2.26M
    if (RHS.isUndefined() || 
isOverdefined()2.26M
)
242
113k
      return false;
243
2.15M
    if (RHS.isOverdefined()) {
244
916k
      markOverdefined();
245
916k
      return true;
246
916k
    }
247
1.24M
248
1.24M
    if (isUndefined()) {
249
873k
      *this = RHS;
250
873k
      return !RHS.isUndefined();
251
873k
    }
252
366k
253
366k
    if (isConstant()) {
254
5.04k
      if (RHS.isConstant() && 
getConstant() == RHS.getConstant()3.56k
)
255
2.85k
        return false;
256
2.18k
      markOverdefined();
257
2.18k
      return true;
258
2.18k
    }
259
361k
260
361k
    if (isNotConstant()) {
261
224k
      if (RHS.isNotConstant() && 
getNotConstant() == RHS.getNotConstant()223k
)
262
223k
        return false;
263
1.08k
      markOverdefined();
264
1.08k
      return true;
265
1.08k
    }
266
136k
267
136k
    assert(isConstantRange() && "New ValueLattice type?");
268
136k
    if (!RHS.isConstantRange()) {
269
2
      // We can get here if we've encountered a constantexpr of integer type
270
2
      // and merge it with a constantrange.
271
2
      markOverdefined();
272
2
      return true;
273
2
    }
274
136k
    ConstantRange NewR = getConstantRange().unionWith(RHS.getConstantRange());
275
136k
    if (NewR.isFullSet())
276
19.5k
      markOverdefined();
277
117k
    else if (NewR == getConstantRange())
278
78.1k
      return false;
279
39.0k
    else
280
39.0k
      markConstantRange(std::move(NewR));
281
136k
    
return true58.5k
;
282
136k
  }
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
360k
                       const ValueLatticeElement &Other) const {
295
360k
    if (isUndefined() || 
Other.isUndefined()352k
)
296
12.2k
      return UndefValue::get(Ty);
297
348k
298
348k
    if (isConstant() && 
Other.isConstant()952
)
299
890
      return ConstantExpr::getCompare(Pred, getConstant(), Other.getConstant());
300
347k
301
347k
    // Integer constants are represented as ConstantRanges with single
302
347k
    // elements.
303
347k
    if (!isConstantRange() || 
!Other.isConstantRange()45.9k
)
304
326k
      return nullptr;
305
21.7k
306
21.7k
    const auto &CR = getConstantRange();
307
21.7k
    const auto &OtherCR = Other.getConstantRange();
308
21.7k
    if (ConstantRange::makeSatisfyingICmpRegion(Pred, OtherCR).contains(CR))
309
14.9k
      return ConstantInt::getTrue(Ty);
310
6.79k
    if (ConstantRange::makeSatisfyingICmpRegion(
311
6.79k
            CmpInst::getInversePredicate(Pred), OtherCR)
312
6.79k
            .contains(CR))
313
6.73k
      return ConstantInt::getFalse(Ty);
314
55
315
55
    return nullptr;
316
55
  }
317
};
318
319
raw_ostream &operator<<(raw_ostream &OS, const ValueLatticeElement &Val);
320
321
} // end namespace llvm
322
#endif