LLVM  10.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) const {
113  return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
114  }
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  KnownBits zext(unsigned BitWidth, bool ExtendedBitsAreKnownZero) const {
121  unsigned OldBitWidth = getBitWidth();
122  APInt NewZero = Zero.zext(BitWidth);
123  if (ExtendedBitsAreKnownZero)
124  NewZero.setBitsFrom(OldBitWidth);
125  return KnownBits(NewZero, One.zext(BitWidth));
126  }
127 
128  /// Sign extends the underlying known Zero and One bits. This is equivalent
129  /// to sign extending the value we're tracking.
130  KnownBits sext(unsigned BitWidth) const {
131  return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
132  }
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  bool ExtendedBitsAreKnownZero) const {
140  if (BitWidth > getBitWidth())
141  return zext(BitWidth, ExtendedBitsAreKnownZero);
142  return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
143  }
144 
145  /// Returns the minimum number of trailing zero bits.
146  unsigned countMinTrailingZeros() const {
147  return Zero.countTrailingOnes();
148  }
149 
150  /// Returns the minimum number of trailing one bits.
151  unsigned countMinTrailingOnes() const {
152  return One.countTrailingOnes();
153  }
154 
155  /// Returns the minimum number of leading zero bits.
156  unsigned countMinLeadingZeros() const {
157  return Zero.countLeadingOnes();
158  }
159 
160  /// Returns the minimum number of leading one bits.
161  unsigned countMinLeadingOnes() const {
162  return One.countLeadingOnes();
163  }
164 
165  /// Returns the number of times the sign bit is replicated into the other
166  /// bits.
167  unsigned countMinSignBits() const {
168  if (isNonNegative())
169  return countMinLeadingZeros();
170  if (isNegative())
171  return countMinLeadingOnes();
172  return 0;
173  }
174 
175  /// Returns the maximum number of trailing zero bits possible.
176  unsigned countMaxTrailingZeros() const {
177  return One.countTrailingZeros();
178  }
179 
180  /// Returns the maximum number of trailing one bits possible.
181  unsigned countMaxTrailingOnes() const {
182  return Zero.countTrailingZeros();
183  }
184 
185  /// Returns the maximum number of leading zero bits possible.
186  unsigned countMaxLeadingZeros() const {
187  return One.countLeadingZeros();
188  }
189 
190  /// Returns the maximum number of leading one bits possible.
191  unsigned countMaxLeadingOnes() const {
192  return Zero.countLeadingZeros();
193  }
194 
195  /// Returns the number of bits known to be one.
196  unsigned countMinPopulation() const {
197  return One.countPopulation();
198  }
199 
200  /// Returns the maximum number of bits that could be one.
201  unsigned countMaxPopulation() const {
202  return getBitWidth() - Zero.countPopulation();
203  }
204 
205  /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
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
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:836
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:196
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:860
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:813
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:878
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
Definition: APInt.h:1436
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:176
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:1515
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:146
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
Definition: APInt.h:1638
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:54
This file implements a class to represent arbitrary precision integral constant values and operations...
KnownBits zextOrTrunc(unsigned BitWidth, bool ExtendedBitsAreKnownZero) const
Extends or truncates the underlying known Zero and One bits.
Definition: KnownBits.h:138
unsigned countMinSignBits() const
Returns the number of times the sign bit is replicated into the other bits.
Definition: KnownBits.h:167
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
Definition: KnownBits.h:201
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry)
Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
Definition: KnownBits.cpp:47
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:1664
KnownBits zext(unsigned BitWidth, bool ExtendedBitsAreKnownZero) const
Extends the underlying known Zero and One bits.
Definition: KnownBits.h:120
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:181
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
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:186
KnownBits sext(unsigned BitWidth) const
Sign extends the underlying known Zero and One bits.
Definition: KnownBits.h:130
KnownBits trunc(unsigned BitWidth) const
Truncate the underlying known Zero and One bits.
Definition: KnownBits.h:112
unsigned countTrailingOnes() const
Count the number of trailing one bits.
Definition: APInt.h:1652
Class for arbitrary precision integers.
Definition: APInt.h:69
unsigned countMinLeadingOnes() const
Returns the minimum number of leading one bits.
Definition: KnownBits.h:161
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
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:191
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:156
unsigned countMinTrailingOnes() const
Returns the minimum number of trailing one bits.
Definition: KnownBits.h:151
unsigned countLeadingOnes() const
Count the number of leading one bits.
Definition: APInt.h:1618
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:1602
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
void makeNegative()
Make this value negative.
Definition: KnownBits.h:101