1//===- ConstantFPRange.cpp - ConstantFPRange implementation ---------------===//
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#include "llvm/IR/ConstantFPRange.h"
10#include "llvm/ADT/APFloat.h"
11#include "llvm/Support/Debug.h"
12#include "llvm/Support/raw_ostream.h"
13#include <cassert>
14
15using namespace llvm;
16
17void ConstantFPRange::makeEmpty() {
18 auto &Sem = Lower.getSemantics();
19 Lower = APFloat::getInf(Sem, /*Negative=*/false);
20 Upper = APFloat::getInf(Sem, /*Negative=*/true);
21 MayBeQNaN = false;
22 MayBeSNaN = false;
23}
24
25void ConstantFPRange::makeFull() {
26 auto &Sem = Lower.getSemantics();
27 Lower = APFloat::getInf(Sem, /*Negative=*/true);
28 Upper = APFloat::getInf(Sem, /*Negative=*/false);
29 MayBeQNaN = true;
30 MayBeSNaN = true;
31}
32
33bool ConstantFPRange::isNaNOnly() const {
34 return Lower.isPosInfinity() && Upper.isNegInfinity();
35}
36
37ConstantFPRange::ConstantFPRange(const fltSemantics &Sem, bool IsFullSet)
38 : Lower(Sem, APFloat::uninitialized), Upper(Sem, APFloat::uninitialized) {
39 Lower = APFloat::getInf(Sem, /*Negative=*/IsFullSet);
40 Upper = APFloat::getInf(Sem, /*Negative=*/!IsFullSet);
41 MayBeQNaN = IsFullSet;
42 MayBeSNaN = IsFullSet;
43}
44
45ConstantFPRange::ConstantFPRange(const APFloat &Value)
46 : Lower(Value.getSemantics(), APFloat::uninitialized),
47 Upper(Value.getSemantics(), APFloat::uninitialized) {
48 if (Value.isNaN()) {
49 makeEmpty();
50 bool IsSNaN = Value.isSignaling();
51 MayBeQNaN = !IsSNaN;
52 MayBeSNaN = IsSNaN;
53 } else {
54 Lower = Upper = Value;
55 MayBeQNaN = MayBeSNaN = false;
56 }
57}
58
59// We treat that -0 is less than 0 here.
60static APFloat::cmpResult strictCompare(const APFloat &LHS,
61 const APFloat &RHS) {
62 assert(!LHS.isNaN() && !RHS.isNaN() && "Unordered compare");
63 if (LHS.isZero() && RHS.isZero()) {
64 if (LHS.isNegative() == RHS.isNegative())
65 return APFloat::cmpEqual;
66 return LHS.isNegative() ? APFloat::cmpLessThan : APFloat::cmpGreaterThan;
67 }
68 return LHS.compare(RHS);
69}
70
71static bool isNonCanonicalEmptySet(const APFloat &Lower, const APFloat &Upper) {
72 return strictCompare(LHS: Lower, RHS: Upper) == APFloat::cmpGreaterThan &&
73 !(Lower.isInfinity() && Upper.isInfinity());
74}
75
76static void canonicalizeRange(APFloat &Lower, APFloat &Upper) {
77 if (isNonCanonicalEmptySet(Lower, Upper)) {
78 Lower = APFloat::getInf(Sem: Lower.getSemantics(), /*Negative=*/false);
79 Upper = APFloat::getInf(Sem: Upper.getSemantics(), /*Negative=*/true);
80 }
81}
82
83ConstantFPRange::ConstantFPRange(APFloat LowerVal, APFloat UpperVal,
84 bool MayBeQNaNVal, bool MayBeSNaNVal)
85 : Lower(std::move(LowerVal)), Upper(std::move(UpperVal)),
86 MayBeQNaN(MayBeQNaNVal), MayBeSNaN(MayBeSNaNVal) {
87 assert(&Lower.getSemantics() == &Upper.getSemantics() &&
88 "Should only use the same semantics");
89 assert(!isNonCanonicalEmptySet(Lower, Upper) && "Non-canonical form");
90}
91
92ConstantFPRange ConstantFPRange::getFinite(const fltSemantics &Sem) {
93 return ConstantFPRange(APFloat::getLargest(Sem, /*Negative=*/true),
94 APFloat::getLargest(Sem, /*Negative=*/false),
95 /*MayBeQNaN=*/false, /*MayBeSNaN=*/false);
96}
97
98ConstantFPRange ConstantFPRange::getNaNOnly(const fltSemantics &Sem,
99 bool MayBeQNaN, bool MayBeSNaN) {
100 return ConstantFPRange(APFloat::getInf(Sem, /*Negative=*/false),
101 APFloat::getInf(Sem, /*Negative=*/true), MayBeQNaN,
102 MayBeSNaN);
103}
104
105ConstantFPRange ConstantFPRange::getNonNaN(const fltSemantics &Sem) {
106 return ConstantFPRange(APFloat::getInf(Sem, /*Negative=*/true),
107 APFloat::getInf(Sem, /*Negative=*/false),
108 /*MayBeQNaN=*/false, /*MayBeSNaN=*/false);
109}
110
111/// Return true for ULT/UGT/OLT/OGT
112static bool fcmpPredExcludesEqual(FCmpInst::Predicate Pred) {
113 return !(Pred & FCmpInst::FCMP_OEQ);
114}
115
116/// Return [-inf, V) or [-inf, V]
117static ConstantFPRange makeLessThan(APFloat V, FCmpInst::Predicate Pred) {
118 const fltSemantics &Sem = V.getSemantics();
119 if (fcmpPredExcludesEqual(Pred)) {
120 if (V.isNegInfinity())
121 return ConstantFPRange::getEmpty(Sem);
122 V.next(/*nextDown=*/true);
123 }
124 return ConstantFPRange::getNonNaN(LowerVal: APFloat::getInf(Sem, /*Negative=*/true),
125 UpperVal: std::move(V));
126}
127
128/// Return (V, +inf] or [V, +inf]
129static ConstantFPRange makeGreaterThan(APFloat V, FCmpInst::Predicate Pred) {
130 const fltSemantics &Sem = V.getSemantics();
131 if (fcmpPredExcludesEqual(Pred)) {
132 if (V.isPosInfinity())
133 return ConstantFPRange::getEmpty(Sem);
134 V.next(/*nextDown=*/false);
135 }
136 return ConstantFPRange::getNonNaN(LowerVal: std::move(V),
137 UpperVal: APFloat::getInf(Sem, /*Negative=*/false));
138}
139
140/// Make sure that +0/-0 are both included in the range.
141static ConstantFPRange extendZeroIfEqual(const ConstantFPRange &CR,
142 FCmpInst::Predicate Pred) {
143 if (fcmpPredExcludesEqual(Pred))
144 return CR;
145
146 APFloat Lower = CR.getLower();
147 APFloat Upper = CR.getUpper();
148 if (Lower.isPosZero())
149 Lower = APFloat::getZero(Sem: Lower.getSemantics(), /*Negative=*/true);
150 if (Upper.isNegZero())
151 Upper = APFloat::getZero(Sem: Upper.getSemantics(), /*Negative=*/false);
152 return ConstantFPRange(std::move(Lower), std::move(Upper), CR.containsQNaN(),
153 CR.containsSNaN());
154}
155
156static ConstantFPRange setNaNField(const ConstantFPRange &CR,
157 FCmpInst::Predicate Pred) {
158 bool ContainsNaN = FCmpInst::isUnordered(predicate: Pred);
159 return ConstantFPRange(CR.getLower(), CR.getUpper(),
160 /*MayBeQNaN=*/ContainsNaN, /*MayBeSNaN=*/ContainsNaN);
161}
162
163ConstantFPRange
164ConstantFPRange::makeAllowedFCmpRegion(FCmpInst::Predicate Pred,
165 const ConstantFPRange &Other) {
166 if (Other.isEmptySet())
167 return Other;
168 if (Other.containsNaN() && FCmpInst::isUnordered(predicate: Pred))
169 return getFull(Sem: Other.getSemantics());
170 if (Other.isNaNOnly() && FCmpInst::isOrdered(predicate: Pred))
171 return getEmpty(Sem: Other.getSemantics());
172
173 switch (Pred) {
174 case FCmpInst::FCMP_TRUE:
175 return getFull(Sem: Other.getSemantics());
176 case FCmpInst::FCMP_FALSE:
177 return getEmpty(Sem: Other.getSemantics());
178 case FCmpInst::FCMP_ORD:
179 return getNonNaN(Sem: Other.getSemantics());
180 case FCmpInst::FCMP_UNO:
181 return getNaNOnly(Sem: Other.getSemantics(), /*MayBeQNaN=*/true,
182 /*MayBeSNaN=*/true);
183 case FCmpInst::FCMP_OEQ:
184 case FCmpInst::FCMP_UEQ:
185 return setNaNField(CR: extendZeroIfEqual(CR: Other, Pred), Pred);
186 case FCmpInst::FCMP_ONE:
187 case FCmpInst::FCMP_UNE:
188 if (const APFloat *SingleElement =
189 Other.getSingleElement(/*ExcludesNaN=*/true)) {
190 const fltSemantics &Sem = SingleElement->getSemantics();
191 if (SingleElement->isPosInfinity())
192 return setNaNField(
193 CR: getNonNaN(LowerVal: APFloat::getInf(Sem, /*Negative=*/true),
194 UpperVal: APFloat::getLargest(Sem, /*Negative=*/false)),
195 Pred);
196 if (SingleElement->isNegInfinity())
197 return setNaNField(
198 CR: getNonNaN(LowerVal: APFloat::getLargest(Sem, /*Negative=*/true),
199 UpperVal: APFloat::getInf(Sem, /*Negative=*/false)),
200 Pred);
201 }
202 return Pred == FCmpInst::FCMP_ONE ? getNonNaN(Sem: Other.getSemantics())
203 : getFull(Sem: Other.getSemantics());
204 case FCmpInst::FCMP_OLT:
205 case FCmpInst::FCMP_OLE:
206 case FCmpInst::FCMP_ULT:
207 case FCmpInst::FCMP_ULE:
208 return setNaNField(
209 CR: extendZeroIfEqual(CR: makeLessThan(V: Other.getUpper(), Pred), Pred), Pred);
210 case FCmpInst::FCMP_OGT:
211 case FCmpInst::FCMP_OGE:
212 case FCmpInst::FCMP_UGT:
213 case FCmpInst::FCMP_UGE:
214 return setNaNField(
215 CR: extendZeroIfEqual(CR: makeGreaterThan(V: Other.getLower(), Pred), Pred), Pred);
216 default:
217 llvm_unreachable("Unexpected predicate");
218 }
219}
220
221ConstantFPRange
222ConstantFPRange::makeSatisfyingFCmpRegion(FCmpInst::Predicate Pred,
223 const ConstantFPRange &Other) {
224 if (Other.isEmptySet())
225 return getFull(Sem: Other.getSemantics());
226 if (Other.containsNaN() && FCmpInst::isOrdered(predicate: Pred))
227 return getEmpty(Sem: Other.getSemantics());
228 if (Other.isNaNOnly() && FCmpInst::isUnordered(predicate: Pred))
229 return getFull(Sem: Other.getSemantics());
230
231 switch (Pred) {
232 case FCmpInst::FCMP_TRUE:
233 return getFull(Sem: Other.getSemantics());
234 case FCmpInst::FCMP_FALSE:
235 return getEmpty(Sem: Other.getSemantics());
236 case FCmpInst::FCMP_ORD:
237 return getNonNaN(Sem: Other.getSemantics());
238 case FCmpInst::FCMP_UNO:
239 return getNaNOnly(Sem: Other.getSemantics(), /*MayBeQNaN=*/true,
240 /*MayBeSNaN=*/true);
241 case FCmpInst::FCMP_OEQ:
242 case FCmpInst::FCMP_UEQ:
243 return setNaNField(CR: Other.isSingleElement(/*ExcludesNaN=*/true) ||
244 ((Other.classify() & ~fcNan) == fcZero)
245 ? extendZeroIfEqual(CR: Other, Pred)
246 : getEmpty(Sem: Other.getSemantics()),
247 Pred);
248 case FCmpInst::FCMP_ONE:
249 case FCmpInst::FCMP_UNE:
250 return getEmpty(Sem: Other.getSemantics());
251 case FCmpInst::FCMP_OLT:
252 case FCmpInst::FCMP_OLE:
253 case FCmpInst::FCMP_ULT:
254 case FCmpInst::FCMP_ULE:
255 return setNaNField(
256 CR: extendZeroIfEqual(CR: makeLessThan(V: Other.getLower(), Pred), Pred), Pred);
257 case FCmpInst::FCMP_OGT:
258 case FCmpInst::FCMP_OGE:
259 case FCmpInst::FCMP_UGT:
260 case FCmpInst::FCMP_UGE:
261 return setNaNField(
262 CR: extendZeroIfEqual(CR: makeGreaterThan(V: Other.getUpper(), Pred), Pred), Pred);
263 default:
264 llvm_unreachable("Unexpected predicate");
265 }
266}
267
268std::optional<ConstantFPRange>
269ConstantFPRange::makeExactFCmpRegion(FCmpInst::Predicate Pred,
270 const APFloat &Other) {
271 if ((Pred == FCmpInst::FCMP_UNE || Pred == FCmpInst::FCMP_ONE) &&
272 !Other.isNaN())
273 return std::nullopt;
274 return makeSatisfyingFCmpRegion(Pred, Other: ConstantFPRange(Other));
275}
276
277bool ConstantFPRange::fcmp(FCmpInst::Predicate Pred,
278 const ConstantFPRange &Other) const {
279 return makeSatisfyingFCmpRegion(Pred, Other).contains(CR: *this);
280}
281
282bool ConstantFPRange::isFullSet() const {
283 return Lower.isNegInfinity() && Upper.isPosInfinity() && MayBeQNaN &&
284 MayBeSNaN;
285}
286
287bool ConstantFPRange::isEmptySet() const {
288 return Lower.isPosInfinity() && Upper.isNegInfinity() && !MayBeQNaN &&
289 !MayBeSNaN;
290}
291
292bool ConstantFPRange::contains(const APFloat &Val) const {
293 assert(&getSemantics() == &Val.getSemantics() &&
294 "Should only use the same semantics");
295
296 if (Val.isNaN())
297 return Val.isSignaling() ? MayBeSNaN : MayBeQNaN;
298 return strictCompare(LHS: Lower, RHS: Val) != APFloat::cmpGreaterThan &&
299 strictCompare(LHS: Val, RHS: Upper) != APFloat::cmpGreaterThan;
300}
301
302bool ConstantFPRange::contains(const ConstantFPRange &CR) const {
303 assert(&getSemantics() == &CR.getSemantics() &&
304 "Should only use the same semantics");
305
306 if (CR.MayBeQNaN && !MayBeQNaN)
307 return false;
308
309 if (CR.MayBeSNaN && !MayBeSNaN)
310 return false;
311
312 return strictCompare(LHS: Lower, RHS: CR.Lower) != APFloat::cmpGreaterThan &&
313 strictCompare(LHS: CR.Upper, RHS: Upper) != APFloat::cmpGreaterThan;
314}
315
316const APFloat *ConstantFPRange::getSingleElement(bool ExcludesNaN) const {
317 if (!ExcludesNaN && (MayBeSNaN || MayBeQNaN))
318 return nullptr;
319 return Lower.bitwiseIsEqual(RHS: Upper) ? &Lower : nullptr;
320}
321
322std::optional<bool> ConstantFPRange::getSignBit() const {
323 if (!MayBeSNaN && !MayBeQNaN && Lower.isNegative() == Upper.isNegative())
324 return Lower.isNegative();
325 return std::nullopt;
326}
327
328bool ConstantFPRange::operator==(const ConstantFPRange &CR) const {
329 if (MayBeSNaN != CR.MayBeSNaN || MayBeQNaN != CR.MayBeQNaN)
330 return false;
331 return Lower.bitwiseIsEqual(RHS: CR.Lower) && Upper.bitwiseIsEqual(RHS: CR.Upper);
332}
333
334FPClassTest ConstantFPRange::classify() const {
335 uint32_t Mask = fcNone;
336 if (MayBeSNaN)
337 Mask |= fcSNan;
338 if (MayBeQNaN)
339 Mask |= fcQNan;
340 if (!isNaNOnly()) {
341 FPClassTest LowerMask = Lower.classify();
342 FPClassTest UpperMask = Upper.classify();
343 assert(LowerMask <= UpperMask && "Range is nan-only.");
344 // Set all bits from log2(LowerMask) to log2(UpperMask).
345 Mask |= (UpperMask << 1) - LowerMask;
346 }
347 return static_cast<FPClassTest>(Mask);
348}
349
350void ConstantFPRange::print(raw_ostream &OS) const {
351 if (isFullSet())
352 OS << "full-set";
353 else if (isEmptySet())
354 OS << "empty-set";
355 else {
356 bool NaNOnly = isNaNOnly();
357 if (!NaNOnly)
358 OS << '[' << Lower << ", " << Upper << ']';
359
360 if (MayBeSNaN || MayBeQNaN) {
361 if (!NaNOnly)
362 OS << " with ";
363 if (MayBeSNaN && MayBeQNaN)
364 OS << "NaN";
365 else if (MayBeSNaN)
366 OS << "SNaN";
367 else if (MayBeQNaN)
368 OS << "QNaN";
369 }
370 }
371}
372
373#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
374LLVM_DUMP_METHOD void ConstantFPRange::dump() const { print(dbgs()); }
375#endif
376
377ConstantFPRange
378ConstantFPRange::intersectWith(const ConstantFPRange &CR) const {
379 assert(&getSemantics() == &CR.getSemantics() &&
380 "Should only use the same semantics");
381 APFloat NewLower = maxnum(A: Lower, B: CR.Lower);
382 APFloat NewUpper = minnum(A: Upper, B: CR.Upper);
383 canonicalizeRange(Lower&: NewLower, Upper&: NewUpper);
384 return ConstantFPRange(std::move(NewLower), std::move(NewUpper),
385 MayBeQNaN & CR.MayBeQNaN, MayBeSNaN & CR.MayBeSNaN);
386}
387
388ConstantFPRange ConstantFPRange::unionWith(const ConstantFPRange &CR) const {
389 assert(&getSemantics() == &CR.getSemantics() &&
390 "Should only use the same semantics");
391 return ConstantFPRange(minnum(A: Lower, B: CR.Lower), maxnum(A: Upper, B: CR.Upper),
392 MayBeQNaN | CR.MayBeQNaN, MayBeSNaN | CR.MayBeSNaN);
393}
394