• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 {
24   APInt Zero;
25   APInt One;
26 
27 private:
28   // Internal constructor for creating a KnownBits from two APInts.
KnownBitsKnownBits29   KnownBits(APInt Zero, APInt One)
30       : Zero(std::move(Zero)), One(std::move(One)) {}
31 
32 public:
33   // Default construct Zero and One.
KnownBitsKnownBits34   KnownBits() {}
35 
36   /// Create a known bits object of BitWidth bits initialized to unknown.
KnownBitsKnownBits37   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
38 
39   /// Get the bit width of this value.
getBitWidthKnownBits40   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.
hasConflictKnownBits47   bool hasConflict() const { return Zero.intersects(One); }
48 
49   /// Returns true if we know the value of all bits.
isConstantKnownBits50   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.
getConstantKnownBits57   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.
isUnknownKnownBits63   bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); }
64 
65   /// Resets the known state of all bits.
resetAllKnownBits66   void resetAll() {
67     Zero.clearAllBits();
68     One.clearAllBits();
69   }
70 
71   /// Returns true if value is all zero.
isZeroKnownBits72   bool isZero() const {
73     assert(!hasConflict() && "KnownBits conflict!");
74     return Zero.isAllOnesValue();
75   }
76 
77   /// Returns true if value is all one bits.
isAllOnesKnownBits78   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.
setAllZeroKnownBits84   void setAllZero() {
85     Zero.setAllBits();
86     One.clearAllBits();
87   }
88 
89   /// Make all bits known to be one and discard any previous information.
setAllOnesKnownBits90   void setAllOnes() {
91     Zero.clearAllBits();
92     One.setAllBits();
93   }
94 
95   /// Returns true if this value is known to be negative.
isNegativeKnownBits96   bool isNegative() const { return One.isSignBitSet(); }
97 
98   /// Returns true if this value is known to be non-negative.
isNonNegativeKnownBits99   bool isNonNegative() const { return Zero.isSignBitSet(); }
100 
101   /// Make this value negative.
makeNegativeKnownBits102   void makeNegative() {
103     One.setSignBit();
104   }
105 
106   /// Make this value non-negative.
makeNonNegativeKnownBits107   void makeNonNegative() {
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.
truncKnownBits113   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.
zextKnownBits119   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.
sextKnownBits125   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.
zextOrTruncKnownBits131   KnownBits zextOrTrunc(unsigned BitWidth) {
132     return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
133   }
134 
135   /// Returns the minimum number of trailing zero bits.
countMinTrailingZerosKnownBits136   unsigned countMinTrailingZeros() const {
137     return Zero.countTrailingOnes();
138   }
139 
140   /// Returns the minimum number of trailing one bits.
countMinTrailingOnesKnownBits141   unsigned countMinTrailingOnes() const {
142     return One.countTrailingOnes();
143   }
144 
145   /// Returns the minimum number of leading zero bits.
countMinLeadingZerosKnownBits146   unsigned countMinLeadingZeros() const {
147     return Zero.countLeadingOnes();
148   }
149 
150   /// Returns the minimum number of leading one bits.
countMinLeadingOnesKnownBits151   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.
countMinSignBitsKnownBits157   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.
countMaxTrailingZerosKnownBits166   unsigned countMaxTrailingZeros() const {
167     return One.countTrailingZeros();
168   }
169 
170   /// Returns the maximum number of trailing one bits possible.
countMaxTrailingOnesKnownBits171   unsigned countMaxTrailingOnes() const {
172     return Zero.countTrailingZeros();
173   }
174 
175   /// Returns the maximum number of leading zero bits possible.
countMaxLeadingZerosKnownBits176   unsigned countMaxLeadingZeros() const {
177     return One.countLeadingZeros();
178   }
179 
180   /// Returns the maximum number of leading one bits possible.
countMaxLeadingOnesKnownBits181   unsigned countMaxLeadingOnes() const {
182     return Zero.countLeadingZeros();
183   }
184 
185   /// Returns the number of bits known to be one.
countMinPopulationKnownBits186   unsigned countMinPopulation() const {
187     return One.countPopulation();
188   }
189 
190   /// Returns the maximum number of bits that could be one.
countMaxPopulationKnownBits191   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
203