|
121
|
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.
|
|
|
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.
|
|
|
108 void makeNonNegative() {
|
|
|
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
|
