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