Line data Source code
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 79397 : 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 55701087 : KnownBits() {}
35 :
36 : /// Create a known bits object of BitWidth bits initialized to unknown.
37 277470038 : 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 131655464 : 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 9542755 : bool isConstant() const {
51 : assert(!hasConflict() && "KnownBits conflict!");
52 19085510 : 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 7644329 : bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); }
64 :
65 : /// Resets the known state of all bits.
66 : void resetAll() {
67 83499981 : Zero.clearAllBits();
68 83539237 : 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 228177 : Zero.setAllBits();
86 228177 : One.clearAllBits();
87 : }
88 :
89 : /// Make all bits known to be one and discard any previous information.
90 : void setAllOnes() {
91 6 : Zero.clearAllBits();
92 6 : One.setAllBits();
93 : }
94 :
95 : /// Returns true if this value is known to be negative.
96 16630775 : bool isNegative() const { return One.isSignBitSet(); }
97 :
98 : /// Returns true if this value is known to be non-negative.
99 16619853 : bool isNonNegative() const { return Zero.isSignBitSet(); }
100 :
101 : /// Make this value negative.
102 : void makeNegative() {
103 44 : One.setSignBit();
104 : }
105 :
106 : /// Make this value non-negative.
107 : void makeNonNegative() {
108 196259 : Zero.setSignBit();
109 : }
110 :
111 : /// Truncate the underlying known Zero and One bits. This is equivalent
112 : /// to truncating the value we're tracking.
113 1519963 : KnownBits trunc(unsigned BitWidth) {
114 1519963 : 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.
119 663139 : KnownBits zext(unsigned BitWidth) {
120 663139 : 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.
125 248976 : KnownBits sext(unsigned BitWidth) {
126 248976 : 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.
131 3554404 : KnownBits zextOrTrunc(unsigned BitWidth) {
132 3554404 : return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
133 : }
134 :
135 : /// Returns the minimum number of trailing zero bits.
136 : unsigned countMinTrailingZeros() const {
137 186398 : return Zero.countTrailingOnes();
138 : }
139 :
140 : /// Returns the minimum number of trailing one bits.
141 : unsigned countMinTrailingOnes() const {
142 : return One.countTrailingOnes();
143 : }
144 :
145 : /// Returns the minimum number of leading zero bits.
146 : unsigned countMinLeadingZeros() const {
147 9783331 : return Zero.countLeadingOnes();
148 : }
149 :
150 : /// Returns the minimum number of leading one bits.
151 : unsigned countMinLeadingOnes() const {
152 38706 : return One.countLeadingOnes();
153 : }
154 :
155 : /// Returns the number of times the sign bit is replicated into the other
156 : /// bits.
157 5840652 : unsigned countMinSignBits() const {
158 5840652 : if (isNonNegative())
159 217615 : return countMinLeadingZeros();
160 5623037 : if (isNegative())
161 5342 : return countMinLeadingOnes();
162 : return 0;
163 : }
164 :
165 : /// Returns the maximum number of trailing zero bits possible.
166 : unsigned countMaxTrailingZeros() const {
167 1898 : return One.countTrailingZeros();
168 : }
169 :
170 : /// Returns the maximum number of trailing one bits possible.
171 : unsigned countMaxTrailingOnes() const {
172 : return Zero.countTrailingZeros();
173 : }
174 :
175 : /// Returns the maximum number of leading zero bits possible.
176 : unsigned countMaxLeadingZeros() const {
177 57339 : return One.countLeadingZeros();
178 : }
179 :
180 : /// Returns the maximum number of leading one bits possible.
181 : unsigned countMaxLeadingOnes() const {
182 : return Zero.countLeadingZeros();
183 : }
184 :
185 : /// Returns the number of bits known to be one.
186 : unsigned countMinPopulation() const {
187 : return One.countPopulation();
188 : }
189 :
190 : /// Returns the maximum number of bits that could be one.
191 : unsigned countMaxPopulation() const {
192 9852 : 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
|
