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#include "llvm/ADT/Optional.h"
19
20namespace llvm {
21
22// Struct for tracking the known zeros and ones of a value.
23struct KnownBits {
24 APInt Zero;
25 APInt One;
26
27private:
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
32public:
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 /// Returns true if this value is known to be non-zero.
102 bool isNonZero() const { return !One.isNullValue(); }
103
104 /// Returns true if this value is known to be positive.
105 bool isStrictlyPositive() const { return Zero.isSignBitSet() && !One.isNullValue(); }
106
107 /// Make this value negative.
108 void makeNegative() {
109 One.setSignBit();
110 }
111
112 /// Make this value non-negative.
113 void makeNonNegative() {
114 Zero.setSignBit();
115 }
116
117 /// Return the minimal unsigned value possible given these KnownBits.
118 APInt getMinValue() const {
119 // Assume that all bits that aren't known-ones are zeros.
120 return One;
121 }
122
123 /// Return the minimal signed value possible given these KnownBits.
124 APInt getSignedMinValue() const {
125 // Assume that all bits that aren't known-ones are zeros.
126 APInt Min = One;
127 // Sign bit is unknown.
128 if (Zero.isSignBitClear())
129 Min.setSignBit();
130 return Min;
131 }
132
133 /// Return the maximal unsigned value possible given these KnownBits.
134 APInt getMaxValue() const {
135 // Assume that all bits that aren't known-zeros are ones.
136 return ~Zero;
137 }
138
139 /// Return the maximal signed value possible given these KnownBits.
140 APInt getSignedMaxValue() const {
141 // Assume that all bits that aren't known-zeros are ones.
142 APInt Max = ~Zero;
143 // Sign bit is unknown.
144 if (One.isSignBitClear())
145 Max.clearSignBit();
146 return Max;
147 }
148
149 /// Return known bits for a truncation of the value we're tracking.
150 KnownBits trunc(unsigned BitWidth) const {
151 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
152 }
153
154 /// Return known bits for an "any" extension of the value we're tracking,
155 /// where we don't know anything about the extended bits.
156 KnownBits anyext(unsigned BitWidth) const {
157 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
158 }
159
160 /// Return known bits for a zero extension of the value we're tracking.
161 KnownBits zext(unsigned BitWidth) const {
162 unsigned OldBitWidth = getBitWidth();
163 APInt NewZero = Zero.zext(BitWidth);
164 NewZero.setBitsFrom(OldBitWidth);
165 return KnownBits(NewZero, One.zext(BitWidth));
166 }
167
168 /// Return known bits for a sign extension of the value we're tracking.
169 KnownBits sext(unsigned BitWidth) const {
170 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
171 }
172
173 /// Return known bits for an "any" extension or truncation of the value we're
174 /// tracking.
175 KnownBits anyextOrTrunc(unsigned BitWidth) const {
176 if (BitWidth > getBitWidth())
177 return anyext(BitWidth);
178 if (BitWidth < getBitWidth())
179 return trunc(BitWidth);
180 return *this;
181 }
182
183 /// Return known bits for a zero extension or truncation of the value we're
184 /// tracking.
185 KnownBits zextOrTrunc(unsigned BitWidth) const {
186 if (BitWidth > getBitWidth())
187 return zext(BitWidth);
188 if (BitWidth < getBitWidth())
189 return trunc(BitWidth);
190 return *this;
191 }
192
193 /// Return known bits for a sign extension or truncation of the value we're
194 /// tracking.
195 KnownBits sextOrTrunc(unsigned BitWidth) const {
196 if (BitWidth > getBitWidth())
197 return sext(BitWidth);
198 if (BitWidth < getBitWidth())
199 return trunc(BitWidth);
200 return *this;
201 }
202
203 /// Return known bits for a in-register sign extension of the value we're
204 /// tracking.
205 KnownBits sextInReg(unsigned SrcBitWidth) const;
206
207 /// Return a KnownBits with the extracted bits
208 /// [bitPosition,bitPosition+numBits).
209 KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
210 return KnownBits(Zero.extractBits(NumBits, BitPosition),
211 One.extractBits(NumBits, BitPosition));
212 }
213
214 /// Return KnownBits based on this, but updated given that the underlying
215 /// value is known to be greater than or equal to Val.
216 KnownBits makeGE(const APInt &Val) const;
217
218 /// Returns the minimum number of trailing zero bits.
219 unsigned countMinTrailingZeros() const {
220 return Zero.countTrailingOnes();
221 }
222
223 /// Returns the minimum number of trailing one bits.
224 unsigned countMinTrailingOnes() const {
225 return One.countTrailingOnes();
226 }
227
228 /// Returns the minimum number of leading zero bits.
229 unsigned countMinLeadingZeros() const {
230 return Zero.countLeadingOnes();
231 }
232
233 /// Returns the minimum number of leading one bits.
234 unsigned countMinLeadingOnes() const {
235 return One.countLeadingOnes();
236 }
237
238 /// Returns the number of times the sign bit is replicated into the other
239 /// bits.
240 unsigned countMinSignBits() const {
241 if (isNonNegative())
242 return countMinLeadingZeros();
243 if (isNegative())
244 return countMinLeadingOnes();
245 return 0;
246 }
247
248 /// Returns the maximum number of trailing zero bits possible.
249 unsigned countMaxTrailingZeros() const {
250 return One.countTrailingZeros();
251 }
252
253 /// Returns the maximum number of trailing one bits possible.
254 unsigned countMaxTrailingOnes() const {
255 return Zero.countTrailingZeros();
256 }
257
258 /// Returns the maximum number of leading zero bits possible.
259 unsigned countMaxLeadingZeros() const {
260 return One.countLeadingZeros();
261 }
262
263 /// Returns the maximum number of leading one bits possible.
264 unsigned countMaxLeadingOnes() const {
265 return Zero.countLeadingZeros();
266 }
267
268 /// Returns the number of bits known to be one.
269 unsigned countMinPopulation() const {
270 return One.countPopulation();
271 }
272
273 /// Returns the maximum number of bits that could be one.
274 unsigned countMaxPopulation() const {
275 return getBitWidth() - Zero.countPopulation();
276 }
277
278 /// Create known bits from a known constant.
279 static KnownBits makeConstant(const APInt &C) {
280 return KnownBits(~C, C);
281 }
282
283 /// Compute known bits common to LHS and RHS.
284 static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) {
285 return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One);
286 }
287
288 /// Return true if LHS and RHS have no common bits set.
289 static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
290 return (LHS.Zero | RHS.Zero).isAllOnesValue();
291 }
292
293 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
294 static KnownBits computeForAddCarry(
295 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
296
297 /// Compute known bits resulting from adding LHS and RHS.
298 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
299 KnownBits RHS);
300
301 /// Compute known bits resulting from multiplying LHS and RHS.
302 static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS);
303
304 /// Compute known bits from sign-extended multiply-hi.
305 static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
306
307 /// Compute known bits from zero-extended multiply-hi.
308 static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
309
310 /// Compute known bits for udiv(LHS, RHS).
311 static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
312
313 /// Compute known bits for urem(LHS, RHS).
314 static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
315
316 /// Compute known bits for srem(LHS, RHS).
317 static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);
318
319 /// Compute known bits for umax(LHS, RHS).
320 static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
321
322 /// Compute known bits for umin(LHS, RHS).
323 static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
324
325 /// Compute known bits for smax(LHS, RHS).
326 static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
327
328 /// Compute known bits for smin(LHS, RHS).
329 static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
330
331 /// Compute known bits for shl(LHS, RHS).
332 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
333 static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS);
334
335 /// Compute known bits for lshr(LHS, RHS).
336 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
337 static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS);
338
339 /// Compute known bits for ashr(LHS, RHS).
340 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
341 static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS);
342
343 /// Determine if these known bits always give the same ICMP_EQ result.
344 static Optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS);
345
346 /// Determine if these known bits always give the same ICMP_NE result.
347 static Optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS);
348
349 /// Determine if these known bits always give the same ICMP_UGT result.
350 static Optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS);
351
352 /// Determine if these known bits always give the same ICMP_UGE result.
353 static Optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS);
354
355 /// Determine if these known bits always give the same ICMP_ULT result.
356 static Optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS);
357
358 /// Determine if these known bits always give the same ICMP_ULE result.
359 static Optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS);
360
361 /// Determine if these known bits always give the same ICMP_SGT result.
362 static Optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS);
363
364 /// Determine if these known bits always give the same ICMP_SGE result.
365 static Optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS);
366
367 /// Determine if these known bits always give the same ICMP_SLT result.
368 static Optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS);
369
370 /// Determine if these known bits always give the same ICMP_SLE result.
371 static Optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS);
372
373 /// Insert the bits from a smaller known bits starting at bitPosition.
374 void insertBits(const KnownBits &SubBits, unsigned BitPosition) {
375 Zero.insertBits(SubBits.Zero, BitPosition);
376 One.insertBits(SubBits.One, BitPosition);
377 }
378
379 /// Return a subset of the known bits from [bitPosition,bitPosition+numBits).
380 KnownBits extractBits(unsigned NumBits, unsigned BitPosition) {
381 return KnownBits(Zero.extractBits(NumBits, BitPosition),
382 One.extractBits(NumBits, BitPosition));
383 }
384
385 /// Update known bits based on ANDing with RHS.
386 KnownBits &operator&=(const KnownBits &RHS);
387
388 /// Update known bits based on ORing with RHS.
389 KnownBits &operator|=(const KnownBits &RHS);
390
391 /// Update known bits based on XORing with RHS.
392 KnownBits &operator^=(const KnownBits &RHS);
393
394 /// Compute known bits for the absolute value.
395 KnownBits abs(bool IntMinIsPoison = false) const;
396
397 KnownBits byteSwap() {
398 return KnownBits(Zero.byteSwap(), One.byteSwap());
399 }
400
401 KnownBits reverseBits() {
402 return KnownBits(Zero.reverseBits(), One.reverseBits());
403 }
404
405 void print(raw_ostream &OS) const;
406 void dump() const;
407};
408
409inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
410 LHS &= RHS;
411 return LHS;
412}
413
414inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
415 RHS &= LHS;
416 return std::move(RHS);
417}
418
419inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
420 LHS |= RHS;
421 return LHS;
422}
423
424inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
425 RHS |= LHS;
426 return std::move(RHS);
427}
428
429inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
430 LHS ^= RHS;
431 return LHS;
432}
433
434inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
435 RHS ^= LHS;
436 return std::move(RHS);
437}
438
439} // end namespace llvm
440
441#endif
442