LLVM  9.0.0svn
KnownBits.h
Go to the documentation of this file.
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 {
25 
26 private:
27  // Internal constructor for creating a KnownBits from two APInts.
28  KnownBits(APInt Zero, APInt One)
29  : Zero(std::move(Zero)), One(std::move(One)) {}
30 
31 public:
32  // Default construct Zero and One.
33  KnownBits() {}
34 
35  /// Create a known bits object of BitWidth bits initialized to unknown.
36  KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
37 
38  /// Get the bit width of this value.
39  unsigned getBitWidth() const {
40  assert(Zero.getBitWidth() == One.getBitWidth() &&
41  "Zero and One should have the same width!");
42  return Zero.getBitWidth();
43  }
44 
45  /// Returns true if there is conflicting information.
46  bool hasConflict() const { return Zero.intersects(One); }
47 
48  /// Returns true if we know the value of all bits.
49  bool isConstant() const {
50  assert(!hasConflict() && "KnownBits conflict!");
51  return Zero.countPopulation() + One.countPopulation() == getBitWidth();
52  }
53 
54  /// Returns the value when all bits have a known value. This just returns One
55  /// with a protective assertion.
56  const APInt &getConstant() const {
57  assert(isConstant() && "Can only get value when all bits are known");
58  return One;
59  }
60 
61  /// Returns true if we don't know any bits.
62  bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); }
63 
64  /// Resets the known state of all bits.
65  void resetAll() {
66  Zero.clearAllBits();
67  One.clearAllBits();
68  }
69 
70  /// Returns true if value is all zero.
71  bool isZero() const {
72  assert(!hasConflict() && "KnownBits conflict!");
73  return Zero.isAllOnesValue();
74  }
75 
76  /// Returns true if value is all one bits.
77  bool isAllOnes() const {
78  assert(!hasConflict() && "KnownBits conflict!");
79  return One.isAllOnesValue();
80  }
81 
82  /// Make all bits known to be zero and discard any previous information.
83  void setAllZero() {
84  Zero.setAllBits();
85  One.clearAllBits();
86  }
87 
88  /// Make all bits known to be one and discard any previous information.
89  void setAllOnes() {
90  Zero.clearAllBits();
91  One.setAllBits();
92  }
93 
94  /// Returns true if this value is known to be negative.
95  bool isNegative() const { return One.isSignBitSet(); }
96 
97  /// Returns true if this value is known to be non-negative.
98  bool isNonNegative() const { return Zero.isSignBitSet(); }
99 
100  /// Make this value negative.
101  void makeNegative() {
102  One.setSignBit();
103  }
104 
105  /// Make this value non-negative.
107  Zero.setSignBit();
108  }
109 
110  /// Truncate the underlying known Zero and One bits. This is equivalent
111  /// to truncating the value we're tracking.
112  KnownBits trunc(unsigned BitWidth) {
113  return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
114  }
115 
116  /// Zero extends the underlying known Zero and One bits. This is equivalent
117  /// to zero extending the value we're tracking.
118  KnownBits zext(unsigned BitWidth) {
119  return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
120  }
121 
122  /// Sign extends the underlying known Zero and One bits. This is equivalent
123  /// to sign extending the value we're tracking.
124  KnownBits sext(unsigned BitWidth) {
125  return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
126  }
127 
128  /// Zero extends or truncates the underlying known Zero and One bits. This is
129  /// equivalent to zero extending or truncating the value we're tracking.
130  KnownBits zextOrTrunc(unsigned BitWidth) {
131  return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
132  }
133 
134  /// Returns the minimum number of trailing zero bits.
135  unsigned countMinTrailingZeros() const {
136  return Zero.countTrailingOnes();
137  }
138 
139  /// Returns the minimum number of trailing one bits.
140  unsigned countMinTrailingOnes() const {
141  return One.countTrailingOnes();
142  }
143 
144  /// Returns the minimum number of leading zero bits.
145  unsigned countMinLeadingZeros() const {
146  return Zero.countLeadingOnes();
147  }
148 
149  /// Returns the minimum number of leading one bits.
150  unsigned countMinLeadingOnes() const {
151  return One.countLeadingOnes();
152  }
153 
154  /// Returns the number of times the sign bit is replicated into the other
155  /// bits.
156  unsigned countMinSignBits() const {
157  if (isNonNegative())
158  return countMinLeadingZeros();
159  if (isNegative())
160  return countMinLeadingOnes();
161  return 0;
162  }
163 
164  /// Returns the maximum number of trailing zero bits possible.
165  unsigned countMaxTrailingZeros() const {
166  return One.countTrailingZeros();
167  }
168 
169  /// Returns the maximum number of trailing one bits possible.
170  unsigned countMaxTrailingOnes() const {
171  return Zero.countTrailingZeros();
172  }
173 
174  /// Returns the maximum number of leading zero bits possible.
175  unsigned countMaxLeadingZeros() const {
176  return One.countLeadingZeros();
177  }
178 
179  /// Returns the maximum number of leading one bits possible.
180  unsigned countMaxLeadingOnes() const {
181  return Zero.countLeadingZeros();
182  }
183 
184  /// Returns the number of bits known to be one.
185  unsigned countMinPopulation() const {
186  return One.countPopulation();
187  }
188 
189  /// Returns the maximum number of bits that could be one.
190  unsigned countMaxPopulation() const {
191  return getBitWidth() - Zero.countPopulation();
192  }
193 
194  /// Compute known bits resulting from adding LHS and RHS.
195  static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
196  KnownBits RHS);
197 };
198 
199 } // end namespace llvm
200 
201 #endif
void clearAllBits()
Set every bit to 0.
Definition: APInt.h:1451
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1412
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:833
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned countMinPopulation() const
Returns the number of bits known to be one.
Definition: KnownBits.h:185
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:46
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:857
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:810
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1389
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:875
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:165
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:39
void setAllZero()
Make all bits known to be zero and discard any previous information.
Definition: KnownBits.h:83
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1508
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:135
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1631
Definition: BitVector.h:937
static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS)
Compute known bits resulting from adding LHS and RHS.
Definition: KnownBits.cpp:18
KnownBits zext(unsigned BitWidth)
Zero extends the underlying known Zero and One bits.
Definition: KnownBits.h:118
This file implements a class to represent arbitrary precision integral constant values and operations...
unsigned countMinSignBits() const
Returns the number of times the sign bit is replicated into the other bits.
Definition: KnownBits.h:156
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
Definition: KnownBits.h:190
KnownBits zextOrTrunc(unsigned BitWidth)
Zero extends or truncates the underlying known Zero and One bits.
Definition: KnownBits.h:130
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:95
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:395
unsigned countPopulation() const
Count the number of bits set.
Definition: APInt.h:1657
void resetAll()
Resets the known state of all bits.
Definition: KnownBits.h:65
unsigned countMaxTrailingOnes() const
Returns the maximum number of trailing one bits possible.
Definition: KnownBits.h:170
const APInt & getConstant() const
Returns the value when all bits have a known value.
Definition: KnownBits.h:56
bool isConstant() const
Returns true if we know the value of all bits.
Definition: KnownBits.h:49
KnownBits trunc(unsigned BitWidth)
Truncate the underlying known Zero and One bits.
Definition: KnownBits.h:112
bool isAllOnes() const
Returns true if value is all one bits.
Definition: KnownBits.h:77
bool isZero() const
Returns true if value is all zero.
Definition: KnownBits.h:71
void makeNonNegative()
Make this value non-negative.
Definition: KnownBits.h:106
KnownBits(unsigned BitWidth)
Create a known bits object of BitWidth bits initialized to unknown.
Definition: KnownBits.h:36
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:175
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1645
Class for arbitrary precision integers.
Definition: APInt.h:69
unsigned countMinLeadingOnes() const
Returns the minimum number of leading one bits.
Definition: KnownBits.h:150
bool isUnknown() const
Returns true if we don't know any bits.
Definition: KnownBits.h:62
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1320
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void setAllOnes()
Make all bits known to be one and discard any previous information.
Definition: KnownBits.h:89
KnownBits sext(unsigned BitWidth)
Sign extends the underlying known Zero and One bits.
Definition: KnownBits.h:124
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
Definition: APInt.h:375
unsigned countMaxLeadingOnes() const
Returns the maximum number of leading one bits possible.
Definition: KnownBits.h:180
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:145
unsigned countMinTrailingOnes() const
Returns the minimum number of trailing one bits.
Definition: KnownBits.h:140
unsigned countLeadingOnes() const
Count the number of leading one bits.
Definition: APInt.h:1611
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:98
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
Definition: APInt.h:1595
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
void makeNegative()
Make this value negative.
Definition: KnownBits.h:101