/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/Support/KnownBits.h
Line | Count | Source (jump to first uncovered line) |
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 | 146M | : Zero(std::move(Zero)), One(std::move(One)) {} |
31 | | |
32 | | public: |
33 | | // Default construct Zero and One. |
34 | 333M | KnownBits() {} |
35 | | |
36 | | /// Create a known bits object of BitWidth bits initialized to unknown. |
37 | 959M | KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {} |
38 | | |
39 | | /// Get the bit width of this value. |
40 | 2.92G | unsigned getBitWidth() const { |
41 | 2.92G | assert(Zero.getBitWidth() == One.getBitWidth() && |
42 | 2.92G | "Zero and One should have the same width!"); |
43 | 2.92G | return Zero.getBitWidth(); |
44 | 2.92G | } |
45 | | |
46 | | /// Returns true if there is conflicting information. |
47 | 0 | bool hasConflict() const { return Zero.intersects(One); } |
48 | | |
49 | | /// Returns true if we know the value of all bits. |
50 | 133M | bool isConstant() const { |
51 | 133M | assert(!hasConflict() && "KnownBits conflict!"); |
52 | 133M | return Zero.countPopulation() + One.countPopulation() == getBitWidth(); |
53 | 133M | } |
54 | | |
55 | | /// Returns the value when all bits have a known value. This just returns One |
56 | | /// with a protective assertion. |
57 | 636k | const APInt &getConstant() const { |
58 | 636k | assert(isConstant() && "Can only get value when all bits are known"); |
59 | 636k | return One; |
60 | 636k | } |
61 | | |
62 | | /// Returns true if we don't know any bits. |
63 | 1.66M | bool isUnknown() const { return Zero.isNullValue() && 1.66M One.isNullValue()1.59M ; } |
64 | | |
65 | | /// Resets the known state of all bits. |
66 | 929M | void resetAll() { |
67 | 929M | Zero.clearAllBits(); |
68 | 929M | One.clearAllBits(); |
69 | 929M | } |
70 | | |
71 | | /// Returns true if value is all zero. |
72 | 14.6M | bool isZero() const { |
73 | 14.6M | assert(!hasConflict() && "KnownBits conflict!"); |
74 | 14.6M | return Zero.isAllOnesValue(); |
75 | 14.6M | } |
76 | | |
77 | | /// Returns true if value is all one bits. |
78 | 414 | bool isAllOnes() const { |
79 | 414 | assert(!hasConflict() && "KnownBits conflict!"); |
80 | 414 | return One.isAllOnesValue(); |
81 | 414 | } |
82 | | |
83 | | /// Make all bits known to be zero and discard any previous information. |
84 | 4.57M | void setAllZero() { |
85 | 4.57M | Zero.setAllBits(); |
86 | 4.57M | One.clearAllBits(); |
87 | 4.57M | } |
88 | | |
89 | | /// Make all bits known to be one and discard any previous information. |
90 | 6 | void setAllOnes() { |
91 | 6 | Zero.clearAllBits(); |
92 | 6 | One.setAllBits(); |
93 | 6 | } |
94 | | |
95 | | /// Returns true if this value is known to be negative. |
96 | 117M | bool isNegative() const { return One.isSignBitSet(); } |
97 | | |
98 | | /// Returns true if this value is known to be non-negative. |
99 | 135M | bool isNonNegative() const { return Zero.isSignBitSet(); } |
100 | | |
101 | | /// Make this value negative. |
102 | 113 | void makeNegative() { |
103 | 113 | assert(!isNonNegative() && "Can't make a non-negative value negative"); |
104 | 113 | One.setSignBit(); |
105 | 113 | } |
106 | | |
107 | | /// Make this value negative. |
108 | 565k | void makeNonNegative() { |
109 | 565k | assert(!isNegative() && "Can't make a negative value non-negative"); |
110 | 565k | Zero.setSignBit(); |
111 | 565k | } |
112 | | |
113 | | /// Truncate the underlying known Zero and One bits. This is equivalent |
114 | | /// to truncating the value we're tracking. |
115 | 28.2M | KnownBits trunc(unsigned BitWidth) { |
116 | 28.2M | return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth)); |
117 | 28.2M | } |
118 | | |
119 | | /// Zero extends the underlying known Zero and One bits. This is equivalent |
120 | | /// to zero extending the value we're tracking. |
121 | 3.23M | KnownBits zext(unsigned BitWidth) { |
122 | 3.23M | return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth)); |
123 | 3.23M | } |
124 | | |
125 | | /// Sign extends the underlying known Zero and One bits. This is equivalent |
126 | | /// to sign extending the value we're tracking. |
127 | 25.3M | KnownBits sext(unsigned BitWidth) { |
128 | 25.3M | return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth)); |
129 | 25.3M | } |
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 | 90.0M | KnownBits zextOrTrunc(unsigned BitWidth) { |
134 | 90.0M | return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth)); |
135 | 90.0M | } |
136 | | |
137 | | /// Returns the minimum number of trailing zero bits. |
138 | 296M | unsigned countMinTrailingZeros() const { |
139 | 296M | return Zero.countTrailingOnes(); |
140 | 296M | } |
141 | | |
142 | | /// Returns the minimum number of trailing one bits. |
143 | 30.8k | unsigned countMinTrailingOnes() const { |
144 | 30.8k | return One.countTrailingOnes(); |
145 | 30.8k | } |
146 | | |
147 | | /// Returns the minimum number of leading zero bits. |
148 | 79.5M | unsigned countMinLeadingZeros() const { |
149 | 79.5M | return Zero.countLeadingOnes(); |
150 | 79.5M | } |
151 | | |
152 | | /// Returns the minimum number of leading one bits. |
153 | 4.28M | unsigned countMinLeadingOnes() const { |
154 | 4.28M | return One.countLeadingOnes(); |
155 | 4.28M | } |
156 | | |
157 | | /// Returns the number of times the sign bit is replicated into the other |
158 | | /// bits. |
159 | 13.9M | unsigned countMinSignBits() const { |
160 | 13.9M | if (isNonNegative()) |
161 | 4.17M | return countMinLeadingZeros(); |
162 | 9.74M | if (9.74M isNegative()9.74M ) |
163 | 236k | return countMinLeadingOnes(); |
164 | 9.50M | return 0; |
165 | 13.9M | } |
166 | | |
167 | | /// Returns the maximum number of trailing zero bits possible. |
168 | 13.6k | unsigned countMaxTrailingZeros() const { |
169 | 13.6k | return One.countTrailingZeros(); |
170 | 13.6k | } |
171 | | |
172 | | /// Returns the maximum number of trailing one bits possible. |
173 | 33 | unsigned countMaxTrailingOnes() const { |
174 | 33 | return Zero.countTrailingZeros(); |
175 | 33 | } |
176 | | |
177 | | /// Returns the maximum number of leading zero bits possible. |
178 | 3.78M | unsigned countMaxLeadingZeros() const { |
179 | 3.78M | return One.countLeadingZeros(); |
180 | 3.78M | } |
181 | | |
182 | | /// Returns the maximum number of leading one bits possible. |
183 | 0 | unsigned countMaxLeadingOnes() const { |
184 | 0 | return Zero.countLeadingZeros(); |
185 | 0 | } |
186 | | |
187 | | /// Returns the number of bits known to be one. |
188 | 179 | unsigned countMinPopulation() const { |
189 | 179 | return One.countPopulation(); |
190 | 179 | } |
191 | | |
192 | | /// Returns the maximum number of bits that could be one. |
193 | 10.1k | unsigned countMaxPopulation() const { |
194 | 10.1k | return getBitWidth() - Zero.countPopulation(); |
195 | 10.1k | } |
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 |