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
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  /// 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
205