LLVM  6.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  assert(!isNonNegative() && "Can't make a non-negative value negative");
104  One.setSignBit();
105  }
106 
107  /// Make this value negative.
109  assert(!isNegative() && "Can't make a negative value non-negative");
110  Zero.setSignBit();
111  }
112 
113  /// Truncate the underlying known Zero and One bits. This is equivalent
114  /// to truncating the value we're tracking.
115  KnownBits trunc(unsigned BitWidth) {
116  return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
117  }
118 
119  /// Zero extends the underlying known Zero and One bits. This is equivalent
120  /// to zero extending the value we're tracking.
121  KnownBits zext(unsigned BitWidth) {
122  return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
123  }
124 
125  /// Sign extends the underlying known Zero and One bits. This is equivalent
126  /// to sign extending the value we're tracking.
127  KnownBits sext(unsigned BitWidth) {
128  return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
129  }
130 
131  /// Zero extends or truncates the underlying known Zero and One bits. This is
132  /// equivalent to zero extending or truncating the value we're tracking.
133  KnownBits zextOrTrunc(unsigned BitWidth) {
134  return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
135  }
136 
137  /// Returns the minimum number of trailing zero bits.
138  unsigned countMinTrailingZeros() const {
139  return Zero.countTrailingOnes();
140  }
141 
142  /// Returns the minimum number of trailing one bits.
143  unsigned countMinTrailingOnes() const {
144  return One.countTrailingOnes();
145  }
146 
147  /// Returns the minimum number of leading zero bits.
148  unsigned countMinLeadingZeros() const {
149  return Zero.countLeadingOnes();
150  }
151 
152  /// Returns the minimum number of leading one bits.
153  unsigned countMinLeadingOnes() const {
154  return One.countLeadingOnes();
155  }
156 
157  /// Returns the number of times the sign bit is replicated into the other
158  /// bits.
159  unsigned countMinSignBits() const {
160  if (isNonNegative())
161  return countMinLeadingZeros();
162  if (isNegative())
163  return countMinLeadingOnes();
164  return 0;
165  }
166 
167  /// Returns the maximum number of trailing zero bits possible.
168  unsigned countMaxTrailingZeros() const {
169  return One.countTrailingZeros();
170  }
171 
172  /// Returns the maximum number of trailing one bits possible.
173  unsigned countMaxTrailingOnes() const {
174  return Zero.countTrailingZeros();
175  }
176 
177  /// Returns the maximum number of leading zero bits possible.
178  unsigned countMaxLeadingZeros() const {
179  return One.countLeadingZeros();
180  }
181 
182  /// Returns the maximum number of leading one bits possible.
183  unsigned countMaxLeadingOnes() const {
184  return Zero.countLeadingZeros();
185  }
186 
187  /// Returns the number of bits known to be one.
188  unsigned countMinPopulation() const {
189  return One.countPopulation();
190  }
191 
192  /// Returns the maximum number of bits that could be one.
193  unsigned countMaxPopulation() const {
194  return getBitWidth() - Zero.countPopulation();
195  }
196 
197  /// Compute known bits resulting from adding LHS and RHS.
198  static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
199  KnownBits RHS);
200 };
201 
202 } // end namespace llvm
203 
204 #endif
void clearAllBits()
Set every bit to 0.
Definition: APInt.h:1431
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1392
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:841
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:188
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:865
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:818
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1369
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
Definition: APInt.cpp:883
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:168
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:1488
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:138
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1611
Definition: BitVector.h:920
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:121
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:159
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
Definition: KnownBits.h:193
KnownBits zextOrTrunc(unsigned BitWidth)
Zero extends or truncates the underlying known Zero and One bits.
Definition: KnownBits.h:133
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:389
unsigned countPopulation() const
Count the number of bits set.
Definition: APInt.h:1637
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:173
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:115
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 negative.
Definition: KnownBits.h:108
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:178
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1625
Class for arbitrary precision integers.
Definition: APInt.h:69
unsigned countMinLeadingOnes() const
Returns the minimum number of leading one bits.
Definition: KnownBits.h:153
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:1300
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:127
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
Definition: APInt.h:369
unsigned countMaxLeadingOnes() const
Returns the maximum number of leading one bits possible.
Definition: KnownBits.h:183
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:148
unsigned countMinTrailingOnes() const
Returns the minimum number of trailing one bits.
Definition: KnownBits.h:143
unsigned countLeadingOnes() const
Count the number of leading one bits.
Definition: APInt.h:1591
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:1575
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:399
void makeNegative()
Make this value negative.
Definition: KnownBits.h:102