Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Support/KnownBits.h
Line
Count
Source (jump to first uncovered line)
1
//===- llvm/Support/KnownBits.h - Stores known zeros/ones -------*- 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 contains a class for representing known zeros and ones used by
10
// computeKnownBits.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_SUPPORT_KNOWNBITS_H
15
#define LLVM_SUPPORT_KNOWNBITS_H
16
17
#include "llvm/ADT/APInt.h"
18
19
namespace llvm {
20
21
// Struct for tracking the known zeros and ones of a value.
22
struct KnownBits {
23
  APInt Zero;
24
  APInt One;
25
26
private:
27
  // Internal constructor for creating a KnownBits from two APInts.
28
  KnownBits(APInt Zero, APInt One)
29
96.8M
      : Zero(std::move(Zero)), One(std::move(One)) {}
30
31
public:
32
  // Default construct Zero and One.
33
242M
  KnownBits() {}
34
35
  /// Create a known bits object of BitWidth bits initialized to unknown.
36
638M
  KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
37
38
  /// Get the bit width of this value.
39
2.16G
  unsigned getBitWidth() const {
40
2.16G
    assert(Zero.getBitWidth() == One.getBitWidth() &&
41
2.16G
           "Zero and One should have the same width!");
42
2.16G
    return Zero.getBitWidth();
43
2.16G
  }
44
45
  /// Returns true if there is conflicting information.
46
25.0M
  bool hasConflict() const { return Zero.intersects(One); }
47
48
  /// Returns true if we know the value of all bits.
49
93.2M
  bool isConstant() const {
50
93.2M
    assert(!hasConflict() && "KnownBits conflict!");
51
93.2M
    return Zero.countPopulation() + One.countPopulation() == getBitWidth();
52
93.2M
  }
53
54
  /// Returns the value when all bits have a known value. This just returns One
55
  /// with a protective assertion.
56
358k
  const APInt &getConstant() const {
57
358k
    assert(isConstant() && "Can only get value when all bits are known");
58
358k
    return One;
59
358k
  }
60
61
  /// Returns true if we don't know any bits.
62
26.0M
  bool isUnknown() const { return Zero.isNullValue() && 
One.isNullValue()15.9M
; }
63
64
  /// Resets the known state of all bits.
65
661M
  void resetAll() {
66
661M
    Zero.clearAllBits();
67
661M
    One.clearAllBits();
68
661M
  }
69
70
  /// Returns true if value is all zero.
71
10.1M
  bool isZero() const {
72
10.1M
    assert(!hasConflict() && "KnownBits conflict!");
73
10.1M
    return Zero.isAllOnesValue();
74
10.1M
  }
75
76
  /// Returns true if value is all one bits.
77
458
  bool isAllOnes() const {
78
458
    assert(!hasConflict() && "KnownBits conflict!");
79
458
    return One.isAllOnesValue();
80
458
  }
81
82
  /// Make all bits known to be zero and discard any previous information.
83
9.48M
  void setAllZero() {
84
9.48M
    Zero.setAllBits();
85
9.48M
    One.clearAllBits();
86
9.48M
  }
87
88
  /// Make all bits known to be one and discard any previous information.
89
6
  void setAllOnes() {
90
6
    Zero.clearAllBits();
91
6
    One.setAllBits();
92
6
  }
93
94
  /// Returns true if this value is known to be negative.
95
124M
  bool isNegative() const { return One.isSignBitSet(); }
96
97
  /// Returns true if this value is known to be non-negative.
98
172M
  bool isNonNegative() const { return Zero.isSignBitSet(); }
99
100
  /// Make this value negative.
101
3.46k
  void makeNegative() {
102
3.46k
    One.setSignBit();
103
3.46k
  }
104
105
  /// Make this value non-negative.
106
18.9M
  void makeNonNegative() {
107
18.9M
    Zero.setSignBit();
108
18.9M
  }
109
110
  /// Truncate the underlying known Zero and One bits. This is equivalent
111
  /// to truncating the value we're tracking.
112
14.1M
  KnownBits trunc(unsigned BitWidth) const {
113
14.1M
    return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
114
14.1M
  }
115
116
  /// Extends the underlying known Zero and One bits.
117
  /// By setting ExtendedBitsAreKnownZero=true this will be equivalent to
118
  /// zero extending the value we're tracking.
119
  /// With ExtendedBitsAreKnownZero=false the extended bits are set to unknown.
120
25.1M
  KnownBits zext(unsigned BitWidth, bool ExtendedBitsAreKnownZero) const {
121
25.1M
    unsigned OldBitWidth = getBitWidth();
122
25.1M
    APInt NewZero = Zero.zext(BitWidth);
123
25.1M
    if (ExtendedBitsAreKnownZero)
124
15.6M
      NewZero.setBitsFrom(OldBitWidth);
125
25.1M
    return KnownBits(NewZero, One.zext(BitWidth));
126
25.1M
  }
127
128
  /// Sign extends the underlying known Zero and One bits. This is equivalent
129
  /// to sign extending the value we're tracking.
130
12.5M
  KnownBits sext(unsigned BitWidth) const {
131
12.5M
    return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
132
12.5M
  }
133
134
  /// Extends or truncates the underlying known Zero and One bits. When
135
  /// extending the extended bits can either be set as known zero (if
136
  /// ExtendedBitsAreKnownZero=true) or as unknown (if
137
  /// ExtendedBitsAreKnownZero=false).
138
  KnownBits zextOrTrunc(unsigned BitWidth,
139
68.9M
                        bool ExtendedBitsAreKnownZero) const {
140
68.9M
    if (BitWidth > getBitWidth())
141
23.8M
      return zext(BitWidth, ExtendedBitsAreKnownZero);
142
45.0M
    return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
143
45.0M
  }
144
145
  /// Returns the minimum number of trailing zero bits.
146
191M
  unsigned countMinTrailingZeros() const {
147
191M
    return Zero.countTrailingOnes();
148
191M
  }
149
150
  /// Returns the minimum number of trailing one bits.
151
3.97k
  unsigned countMinTrailingOnes() const {
152
3.97k
    return One.countTrailingOnes();
153
3.97k
  }
154
155
  /// Returns the minimum number of leading zero bits.
156
31.5M
  unsigned countMinLeadingZeros() const {
157
31.5M
    return Zero.countLeadingOnes();
158
31.5M
  }
159
160
  /// Returns the minimum number of leading one bits.
161
2.93M
  unsigned countMinLeadingOnes() const {
162
2.93M
    return One.countLeadingOnes();
163
2.93M
  }
164
165
  /// Returns the number of times the sign bit is replicated into the other
166
  /// bits.
167
15.2M
  unsigned countMinSignBits() const {
168
15.2M
    if (isNonNegative())
169
3.28M
      return countMinLeadingZeros();
170
11.9M
    if (isNegative())
171
176k
      return countMinLeadingOnes();
172
11.8M
    return 0;
173
11.8M
  }
174
175
  /// Returns the maximum number of trailing zero bits possible.
176
20.5k
  unsigned countMaxTrailingZeros() const {
177
20.5k
    return One.countTrailingZeros();
178
20.5k
  }
179
180
  /// Returns the maximum number of trailing one bits possible.
181
0
  unsigned countMaxTrailingOnes() const {
182
0
    return Zero.countTrailingZeros();
183
0
  }
184
185
  /// Returns the maximum number of leading zero bits possible.
186
2.30M
  unsigned countMaxLeadingZeros() const {
187
2.30M
    return One.countLeadingZeros();
188
2.30M
  }
189
190
  /// Returns the maximum number of leading one bits possible.
191
0
  unsigned countMaxLeadingOnes() const {
192
0
    return Zero.countLeadingZeros();
193
0
  }
194
195
  /// Returns the number of bits known to be one.
196
29.4k
  unsigned countMinPopulation() const {
197
29.4k
    return One.countPopulation();
198
29.4k
  }
199
200
  /// Returns the maximum number of bits that could be one.
201
134k
  unsigned countMaxPopulation() const {
202
134k
    return getBitWidth() - Zero.countPopulation();
203
134k
  }
204
205
  /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
206
  static KnownBits computeForAddCarry(
207
      const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
208
209
  /// Compute known bits resulting from adding LHS and RHS.
210
  static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
211
                                    KnownBits RHS);
212
};
213
214
} // end namespace llvm
215
216
#endif