blob: bd65aede9403b0534f1a7a4bcc0d096db0cc998d [file] [log] [blame]
Eugene Zelenkode6cce22017-06-19 22:05:08 +00001//===- ConstantRange.cpp - ConstantRange implementation -------------------===//
Misha Brukmanb1c93172005-04-21 23:48:37 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanb1c93172005-04-21 23:48:37 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner113f2ae2002-09-01 23:53:36 +00009//
10// Represent a range of possible values that may occur when the program is run
11// for an integral value. This keeps track of a lower and upper bound for the
12// constant, which MAY wrap around the end of the numeric range. To do this, it
13// keeps track of a [lower, upper) bound, which specifies an interval just like
14// STL iterators. When used with boolean values, the following are important
15// ranges (other integral ranges use min/max values for special range values):
16//
17// [F, F) = {} = Empty set
18// [T, F) = {T}
19// [F, T) = {F}
20// [T, T) = {F, T} = Full set
21//
22//===----------------------------------------------------------------------===//
23
Eugene Zelenkode6cce22017-06-19 22:05:08 +000024#include "llvm/ADT/APInt.h"
Nico Weber432a3882018-04-30 14:59:11 +000025#include "llvm/Config/llvm-config.h"
Chandler Carruth8cd041e2014-03-04 12:24:34 +000026#include "llvm/IR/ConstantRange.h"
Eugene Zelenkode6cce22017-06-19 22:05:08 +000027#include "llvm/IR/Constants.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000028#include "llvm/IR/InstrTypes.h"
29#include "llvm/IR/Instruction.h"
Eugene Zelenkode6cce22017-06-19 22:05:08 +000030#include "llvm/IR/Metadata.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000031#include "llvm/IR/Operator.h"
Eugene Zelenkode6cce22017-06-19 22:05:08 +000032#include "llvm/Support/Compiler.h"
David Greenede7b3532010-01-05 01:28:32 +000033#include "llvm/Support/Debug.h"
Eugene Zelenkode6cce22017-06-19 22:05:08 +000034#include "llvm/Support/ErrorHandling.h"
Chris Lattner0c19df42008-08-23 22:23:09 +000035#include "llvm/Support/raw_ostream.h"
Eugene Zelenkode6cce22017-06-19 22:05:08 +000036#include <algorithm>
37#include <cassert>
38#include <cstdint>
39
Chris Lattnerc9499b62003-12-14 21:35:53 +000040using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000041
Craig Topperee4f22d2017-04-29 05:08:52 +000042ConstantRange::ConstantRange(uint32_t BitWidth, bool Full)
43 : Lower(Full ? APInt::getMaxValue(BitWidth) : APInt::getMinValue(BitWidth)),
44 Upper(Lower) {}
Chris Lattner113f2ae2002-09-01 23:53:36 +000045
Craig Topper37df0182017-04-13 00:20:31 +000046ConstantRange::ConstantRange(APInt V)
Chandler Carruth002da5d2014-03-02 04:08:41 +000047 : Lower(std::move(V)), Upper(Lower + 1) {}
Chris Lattner113f2ae2002-09-01 23:53:36 +000048
Craig Topper37df0182017-04-13 00:20:31 +000049ConstantRange::ConstantRange(APInt L, APInt U)
Chandler Carruth002da5d2014-03-02 04:08:41 +000050 : Lower(std::move(L)), Upper(std::move(U)) {
Benjamin Kramercce97be2013-07-11 15:37:27 +000051 assert(Lower.getBitWidth() == Upper.getBitWidth() &&
Dan Gohmandc33ae22009-07-09 23:16:10 +000052 "ConstantRange with unequal bit widths");
Benjamin Kramercce97be2013-07-11 15:37:27 +000053 assert((Lower != Upper || (Lower.isMaxValue() || Lower.isMinValue())) &&
Reid Spencere1f3f192007-02-28 17:36:23 +000054 "Lower == Upper, but they aren't min or max value!");
55}
56
Sanjoy Das7182d362015-03-18 00:41:24 +000057ConstantRange ConstantRange::makeAllowedICmpRegion(CmpInst::Predicate Pred,
58 const ConstantRange &CR) {
Nick Lewycky5154ee02010-09-28 18:18:36 +000059 if (CR.isEmptySet())
60 return CR;
61
Nick Lewyckydcfdce92009-07-11 06:15:39 +000062 uint32_t W = CR.getBitWidth();
63 switch (Pred) {
Sanjoy Das7182d362015-03-18 00:41:24 +000064 default:
65 llvm_unreachable("Invalid ICmp predicate to makeAllowedICmpRegion()");
Sanjay Patelf8ee0e02016-06-19 17:20:27 +000066 case CmpInst::ICMP_EQ:
67 return CR;
68 case CmpInst::ICMP_NE:
69 if (CR.isSingleElement())
70 return ConstantRange(CR.getUpper(), CR.getLower());
71 return ConstantRange(W);
72 case CmpInst::ICMP_ULT: {
73 APInt UMax(CR.getUnsignedMax());
74 if (UMax.isMinValue())
75 return ConstantRange(W, /* empty */ false);
Craig Topperb7920252017-04-29 06:40:47 +000076 return ConstantRange(APInt::getMinValue(W), std::move(UMax));
Sanjay Patelf8ee0e02016-06-19 17:20:27 +000077 }
78 case CmpInst::ICMP_SLT: {
79 APInt SMax(CR.getSignedMax());
80 if (SMax.isMinSignedValue())
81 return ConstantRange(W, /* empty */ false);
Craig Topperb7920252017-04-29 06:40:47 +000082 return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax));
Sanjay Patelf8ee0e02016-06-19 17:20:27 +000083 }
84 case CmpInst::ICMP_ULE: {
85 APInt UMax(CR.getUnsignedMax());
86 if (UMax.isMaxValue())
Nick Lewyckydcfdce92009-07-11 06:15:39 +000087 return ConstantRange(W);
Craig Topperb7920252017-04-29 06:40:47 +000088 return ConstantRange(APInt::getMinValue(W), std::move(UMax) + 1);
Sanjay Patelf8ee0e02016-06-19 17:20:27 +000089 }
90 case CmpInst::ICMP_SLE: {
91 APInt SMax(CR.getSignedMax());
92 if (SMax.isMaxSignedValue())
93 return ConstantRange(W);
Craig Topperb7920252017-04-29 06:40:47 +000094 return ConstantRange(APInt::getSignedMinValue(W), std::move(SMax) + 1);
Sanjay Patelf8ee0e02016-06-19 17:20:27 +000095 }
96 case CmpInst::ICMP_UGT: {
97 APInt UMin(CR.getUnsignedMin());
98 if (UMin.isMaxValue())
99 return ConstantRange(W, /* empty */ false);
Craig Topperb7920252017-04-29 06:40:47 +0000100 return ConstantRange(std::move(UMin) + 1, APInt::getNullValue(W));
Sanjay Patelf8ee0e02016-06-19 17:20:27 +0000101 }
102 case CmpInst::ICMP_SGT: {
103 APInt SMin(CR.getSignedMin());
104 if (SMin.isMaxSignedValue())
105 return ConstantRange(W, /* empty */ false);
Craig Topperb7920252017-04-29 06:40:47 +0000106 return ConstantRange(std::move(SMin) + 1, APInt::getSignedMinValue(W));
Sanjay Patelf8ee0e02016-06-19 17:20:27 +0000107 }
108 case CmpInst::ICMP_UGE: {
109 APInt UMin(CR.getUnsignedMin());
110 if (UMin.isMinValue())
111 return ConstantRange(W);
Craig Topperb7920252017-04-29 06:40:47 +0000112 return ConstantRange(std::move(UMin), APInt::getNullValue(W));
Sanjay Patelf8ee0e02016-06-19 17:20:27 +0000113 }
114 case CmpInst::ICMP_SGE: {
115 APInt SMin(CR.getSignedMin());
116 if (SMin.isMinSignedValue())
117 return ConstantRange(W);
Craig Topperb7920252017-04-29 06:40:47 +0000118 return ConstantRange(std::move(SMin), APInt::getSignedMinValue(W));
Sanjay Patelf8ee0e02016-06-19 17:20:27 +0000119 }
Nick Lewyckydcfdce92009-07-11 06:15:39 +0000120 }
121}
122
Sanjoy Das7182d362015-03-18 00:41:24 +0000123ConstantRange ConstantRange::makeSatisfyingICmpRegion(CmpInst::Predicate Pred,
124 const ConstantRange &CR) {
125 // Follows from De-Morgan's laws:
126 //
127 // ~(~A union ~B) == A intersect B.
128 //
129 return makeAllowedICmpRegion(CmpInst::getInversePredicate(Pred), CR)
130 .inverse();
131}
132
Balaram Makam569eaec2016-05-04 21:32:14 +0000133ConstantRange ConstantRange::makeExactICmpRegion(CmpInst::Predicate Pred,
134 const APInt &C) {
135 // Computes the exact range that is equal to both the constant ranges returned
136 // by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true
137 // when RHS is a singleton such as an APInt and so the assert is valid.
138 // However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion
139 // returns [0,4) but makeSatisfyICmpRegion returns [0,2).
140 //
141 assert(makeAllowedICmpRegion(Pred, C) == makeSatisfyingICmpRegion(Pred, C));
142 return makeAllowedICmpRegion(Pred, C);
143}
144
Sanjoy Das590614c2016-05-19 03:53:06 +0000145bool ConstantRange::getEquivalentICmp(CmpInst::Predicate &Pred,
146 APInt &RHS) const {
147 bool Success = false;
148
149 if (isFullSet() || isEmptySet()) {
150 Pred = isEmptySet() ? CmpInst::ICMP_ULT : CmpInst::ICMP_UGE;
151 RHS = APInt(getBitWidth(), 0);
152 Success = true;
Sanjoy Dasc7d32912016-10-02 20:59:05 +0000153 } else if (auto *OnlyElt = getSingleElement()) {
154 Pred = CmpInst::ICMP_EQ;
155 RHS = *OnlyElt;
156 Success = true;
157 } else if (auto *OnlyMissingElt = getSingleMissingElement()) {
158 Pred = CmpInst::ICMP_NE;
159 RHS = *OnlyMissingElt;
160 Success = true;
Sanjoy Das590614c2016-05-19 03:53:06 +0000161 } else if (getLower().isMinSignedValue() || getLower().isMinValue()) {
162 Pred =
163 getLower().isMinSignedValue() ? CmpInst::ICMP_SLT : CmpInst::ICMP_ULT;
164 RHS = getUpper();
165 Success = true;
166 } else if (getUpper().isMinSignedValue() || getUpper().isMinValue()) {
167 Pred =
168 getUpper().isMinSignedValue() ? CmpInst::ICMP_SGE : CmpInst::ICMP_UGE;
169 RHS = getLower();
170 Success = true;
171 }
172
173 assert((!Success || ConstantRange::makeExactICmpRegion(Pred, RHS) == *this) &&
174 "Bad result!");
175
176 return Success;
177}
178
Sanjoy Das5079f622016-02-22 16:13:02 +0000179ConstantRange
180ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp,
Sanjoy Dasf3867e62016-03-03 18:31:16 +0000181 const ConstantRange &Other,
182 unsigned NoWrapKind) {
Eugene Zelenkode6cce22017-06-19 22:05:08 +0000183 using OBO = OverflowingBinaryOperator;
Sanjoy Das6ed05302015-10-22 03:12:57 +0000184
185 // Computes the intersection of CR0 and CR1. It is different from
186 // intersectWith in that the ConstantRange returned will only contain elements
187 // in both CR0 and CR1 (i.e. SubsetIntersect(X, Y) is a *subset*, proper or
188 // not, of both X and Y).
189 auto SubsetIntersect =
190 [](const ConstantRange &CR0, const ConstantRange &CR1) {
191 return CR0.inverse().unionWith(CR1.inverse()).inverse();
192 };
193
194 assert(BinOp >= Instruction::BinaryOpsBegin &&
195 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
196
197 assert((NoWrapKind == OBO::NoSignedWrap ||
198 NoWrapKind == OBO::NoUnsignedWrap ||
199 NoWrapKind == (OBO::NoUnsignedWrap | OBO::NoSignedWrap)) &&
200 "NoWrapKind invalid!");
201
Sanjoy Dasf3867e62016-03-03 18:31:16 +0000202 unsigned BitWidth = Other.getBitWidth();
Joel Galensonc32b0fc2017-12-05 18:14:23 +0000203 ConstantRange Result(BitWidth);
204
205 switch (BinOp) {
206 default:
Sanjoy Das6ed05302015-10-22 03:12:57 +0000207 // Conservative answer: empty set
208 return ConstantRange(BitWidth, false);
209
Joel Galensonc32b0fc2017-12-05 18:14:23 +0000210 case Instruction::Add:
211 if (auto *C = Other.getSingleElement())
212 if (C->isNullValue())
213 // Full set: nothing signed / unsigned wraps when added to 0.
214 return ConstantRange(BitWidth);
215 if (NoWrapKind & OBO::NoUnsignedWrap)
216 Result =
217 SubsetIntersect(Result, ConstantRange(APInt::getNullValue(BitWidth),
218 -Other.getUnsignedMax()));
219 if (NoWrapKind & OBO::NoSignedWrap) {
220 const APInt &SignedMin = Other.getSignedMin();
221 const APInt &SignedMax = Other.getSignedMax();
222 if (SignedMax.isStrictlyPositive())
223 Result = SubsetIntersect(
224 Result,
225 ConstantRange(APInt::getSignedMinValue(BitWidth),
226 APInt::getSignedMinValue(BitWidth) - SignedMax));
227 if (SignedMin.isNegative())
228 Result = SubsetIntersect(
229 Result,
230 ConstantRange(APInt::getSignedMinValue(BitWidth) - SignedMin,
231 APInt::getSignedMinValue(BitWidth)));
232 }
233 return Result;
Sanjoy Das6ed05302015-10-22 03:12:57 +0000234
Joel Galensonc32b0fc2017-12-05 18:14:23 +0000235 case Instruction::Sub:
236 if (auto *C = Other.getSingleElement())
237 if (C->isNullValue())
238 // Full set: nothing signed / unsigned wraps when subtracting 0.
239 return ConstantRange(BitWidth);
240 if (NoWrapKind & OBO::NoUnsignedWrap)
241 Result =
242 SubsetIntersect(Result, ConstantRange(Other.getUnsignedMax(),
243 APInt::getMinValue(BitWidth)));
244 if (NoWrapKind & OBO::NoSignedWrap) {
245 const APInt &SignedMin = Other.getSignedMin();
246 const APInt &SignedMax = Other.getSignedMax();
247 if (SignedMax.isStrictlyPositive())
248 Result = SubsetIntersect(
249 Result,
250 ConstantRange(APInt::getSignedMinValue(BitWidth) + SignedMax,
251 APInt::getSignedMinValue(BitWidth)));
252 if (SignedMin.isNegative())
253 Result = SubsetIntersect(
254 Result,
255 ConstantRange(APInt::getSignedMinValue(BitWidth),
256 APInt::getSignedMinValue(BitWidth) + SignedMin));
257 }
258 return Result;
Sanjoy Das6ed05302015-10-22 03:12:57 +0000259 }
Sanjoy Das6ed05302015-10-22 03:12:57 +0000260}
261
Chris Lattner113f2ae2002-09-01 23:53:36 +0000262bool ConstantRange::isFullSet() const {
Zhou Sheng31787362007-04-26 16:42:07 +0000263 return Lower == Upper && Lower.isMaxValue();
Chris Lattner113f2ae2002-09-01 23:53:36 +0000264}
Misha Brukmanb1c93172005-04-21 23:48:37 +0000265
Chris Lattner113f2ae2002-09-01 23:53:36 +0000266bool ConstantRange::isEmptySet() const {
Zhou Sheng31787362007-04-26 16:42:07 +0000267 return Lower == Upper && Lower.isMinValue();
Chris Lattner113f2ae2002-09-01 23:53:36 +0000268}
269
Reid Spencer6a440332007-03-01 07:54:15 +0000270bool ConstantRange::isWrappedSet() const {
Reid Spencere1f3f192007-02-28 17:36:23 +0000271 return Lower.ugt(Upper);
Chris Lattner113f2ae2002-09-01 23:53:36 +0000272}
273
Nick Lewyckya35462d2010-09-06 23:52:49 +0000274bool ConstantRange::isSignWrappedSet() const {
275 return contains(APInt::getSignedMaxValue(getBitWidth())) &&
276 contains(APInt::getSignedMinValue(getBitWidth()));
277}
278
Reid Spencere1f3f192007-02-28 17:36:23 +0000279APInt ConstantRange::getSetSize() const {
Craig Topper8c5c6fe2017-04-29 17:59:41 +0000280 if (isFullSet())
281 return APInt::getOneBitSet(getBitWidth()+1, getBitWidth());
Misha Brukmanb1c93172005-04-21 23:48:37 +0000282
Nuno Lopes216d5712012-07-17 15:43:59 +0000283 // This is also correct for wrapped sets.
Nuno Lopes99504c52012-07-16 18:08:12 +0000284 return (Upper - Lower).zext(getBitWidth()+1);
Chris Lattner113f2ae2002-09-01 23:53:36 +0000285}
286
Michael Zolotukhinc69955c2017-03-20 06:33:07 +0000287bool
Craig Topperd29549e2017-05-07 21:48:08 +0000288ConstantRange::isSizeStrictlySmallerThan(const ConstantRange &Other) const {
Michael Zolotukhinc69955c2017-03-20 06:33:07 +0000289 assert(getBitWidth() == Other.getBitWidth());
290 if (isFullSet())
291 return false;
292 if (Other.isFullSet())
293 return true;
294 return (Upper - Lower).ult(Other.Upper - Other.Lower);
295}
296
Craig Topper7e3e7af2017-05-07 22:22:11 +0000297bool
298ConstantRange::isSizeLargerThan(uint64_t MaxSize) const {
299 assert(MaxSize && "MaxSize can't be 0.");
300 // If this a full set, we need special handling to avoid needing an extra bit
301 // to represent the size.
302 if (isFullSet())
303 return APInt::getMaxValue(getBitWidth()).ugt(MaxSize - 1);
304
305 return (Upper - Lower).ugt(MaxSize);
306}
307
Nick Lewyckye4559372007-03-10 15:54:12 +0000308APInt ConstantRange::getUnsignedMax() const {
309 if (isFullSet() || isWrappedSet())
310 return APInt::getMaxValue(getBitWidth());
Nick Lewycky228f5b42012-01-03 20:33:00 +0000311 return getUpper() - 1;
Nick Lewyckye4559372007-03-10 15:54:12 +0000312}
313
Nick Lewyckye4559372007-03-10 15:54:12 +0000314APInt ConstantRange::getUnsignedMin() const {
Craig Topper61729fd2017-05-09 05:01:29 +0000315 if (isFullSet() || (isWrappedSet() && !getUpper().isNullValue()))
Nick Lewyckye4559372007-03-10 15:54:12 +0000316 return APInt::getMinValue(getBitWidth());
Nick Lewycky228f5b42012-01-03 20:33:00 +0000317 return getLower();
Nick Lewyckye4559372007-03-10 15:54:12 +0000318}
319
Nick Lewyckye4559372007-03-10 15:54:12 +0000320APInt ConstantRange::getSignedMax() const {
Craig Topper61e684a2017-06-16 23:26:23 +0000321 if (isFullSet() || Lower.sgt(Upper))
Craig Topper88c64f32017-04-18 23:02:39 +0000322 return APInt::getSignedMaxValue(getBitWidth());
Nick Lewycky228f5b42012-01-03 20:33:00 +0000323 return getUpper() - 1;
Nick Lewyckye4559372007-03-10 15:54:12 +0000324}
325
Nick Lewyckye4559372007-03-10 15:54:12 +0000326APInt ConstantRange::getSignedMin() const {
Craig Topper61e684a2017-06-16 23:26:23 +0000327 if (isFullSet() || (Lower.sgt(Upper) && !getUpper().isMinSignedValue()))
Craig Topper88c64f32017-04-18 23:02:39 +0000328 return APInt::getSignedMinValue(getBitWidth());
Nick Lewycky228f5b42012-01-03 20:33:00 +0000329 return getLower();
Nick Lewyckye4559372007-03-10 15:54:12 +0000330}
331
Reid Spencer6a440332007-03-01 07:54:15 +0000332bool ConstantRange::contains(const APInt &V) const {
333 if (Lower == Upper)
334 return isFullSet();
Chris Lattner113f2ae2002-09-01 23:53:36 +0000335
Reid Spencer6a440332007-03-01 07:54:15 +0000336 if (!isWrappedSet())
337 return Lower.ule(V) && V.ult(Upper);
Nick Lewycky228f5b42012-01-03 20:33:00 +0000338 return Lower.ule(V) || V.ult(Upper);
Chris Lattner55481f72004-03-30 00:20:08 +0000339}
340
Nick Lewyckydcfdce92009-07-11 06:15:39 +0000341bool ConstantRange::contains(const ConstantRange &Other) const {
Nick Lewyckyd385c222010-08-11 22:04:36 +0000342 if (isFullSet() || Other.isEmptySet()) return true;
343 if (isEmptySet() || Other.isFullSet()) return false;
Nick Lewyckydcfdce92009-07-11 06:15:39 +0000344
345 if (!isWrappedSet()) {
346 if (Other.isWrappedSet())
347 return false;
348
349 return Lower.ule(Other.getLower()) && Other.getUpper().ule(Upper);
350 }
351
352 if (!Other.isWrappedSet())
353 return Other.getUpper().ule(Upper) ||
354 Lower.ule(Other.getLower());
355
356 return Other.getUpper().ule(Upper) && Lower.ule(Other.getLower());
357}
358
Reid Spencer3a7e9d82007-02-28 19:57:34 +0000359ConstantRange ConstantRange::subtract(const APInt &Val) const {
Reid Spencer9b3d6ec2007-02-28 22:02:48 +0000360 assert(Val.getBitWidth() == getBitWidth() && "Wrong bit width");
Chris Lattner55481f72004-03-30 00:20:08 +0000361 // If the set is empty or full, don't modify the endpoints.
Reid Spencere1f3f192007-02-28 17:36:23 +0000362 if (Lower == Upper)
363 return *this;
Reid Spencere1f3f192007-02-28 17:36:23 +0000364 return ConstantRange(Lower - Val, Upper - Val);
Chris Lattner55481f72004-03-30 00:20:08 +0000365}
Chris Lattner113f2ae2002-09-01 23:53:36 +0000366
Nuno Lopes5020db22012-06-28 16:10:13 +0000367ConstantRange ConstantRange::difference(const ConstantRange &CR) const {
368 return intersectWith(CR.inverse());
369}
370
Reid Spencer6a440332007-03-01 07:54:15 +0000371ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
Reid Spencer9b3d6ec2007-02-28 22:02:48 +0000372 assert(getBitWidth() == CR.getBitWidth() &&
373 "ConstantRange types don't agree!");
Nick Lewycky61b4a262007-07-14 02:51:34 +0000374
375 // Handle common cases.
376 if ( isEmptySet() || CR.isFullSet()) return *this;
377 if (CR.isEmptySet() || isFullSet()) return CR;
378
379 if (!isWrappedSet() && CR.isWrappedSet())
Nick Lewycky0d139032009-07-18 06:34:42 +0000380 return CR.intersectWith(*this);
Nick Lewycky61b4a262007-07-14 02:51:34 +0000381
382 if (!isWrappedSet() && !CR.isWrappedSet()) {
383 if (Lower.ult(CR.Lower)) {
384 if (Upper.ule(CR.Lower))
385 return ConstantRange(getBitWidth(), false);
386
387 if (Upper.ult(CR.Upper))
388 return ConstantRange(CR.Lower, Upper);
389
390 return CR;
Nick Lewycky61b4a262007-07-14 02:51:34 +0000391 }
Nick Lewycky228f5b42012-01-03 20:33:00 +0000392 if (Upper.ult(CR.Upper))
393 return *this;
394
395 if (Lower.ult(CR.Upper))
396 return ConstantRange(Lower, CR.Upper);
397
398 return ConstantRange(getBitWidth(), false);
Nick Lewycky61b4a262007-07-14 02:51:34 +0000399 }
400
401 if (isWrappedSet() && !CR.isWrappedSet()) {
402 if (CR.Lower.ult(Upper)) {
403 if (CR.Upper.ult(Upper))
404 return CR;
405
Nuno Lopes63afc082012-05-18 00:14:36 +0000406 if (CR.Upper.ule(Lower))
Nick Lewycky61b4a262007-07-14 02:51:34 +0000407 return ConstantRange(CR.Lower, Upper);
408
Craig Topperd29549e2017-05-07 21:48:08 +0000409 if (isSizeStrictlySmallerThan(CR))
Nick Lewycky61b4a262007-07-14 02:51:34 +0000410 return *this;
Nick Lewycky228f5b42012-01-03 20:33:00 +0000411 return CR;
412 }
413 if (CR.Lower.ult(Lower)) {
Nick Lewycky61b4a262007-07-14 02:51:34 +0000414 if (CR.Upper.ule(Lower))
415 return ConstantRange(getBitWidth(), false);
416
417 return ConstantRange(Lower, CR.Upper);
418 }
419 return CR;
420 }
421
422 if (CR.Upper.ult(Upper)) {
423 if (CR.Lower.ult(Upper)) {
Craig Topperd29549e2017-05-07 21:48:08 +0000424 if (isSizeStrictlySmallerThan(CR))
Nick Lewycky61b4a262007-07-14 02:51:34 +0000425 return *this;
Nick Lewycky228f5b42012-01-03 20:33:00 +0000426 return CR;
Nick Lewycky61b4a262007-07-14 02:51:34 +0000427 }
428
429 if (CR.Lower.ult(Lower))
430 return ConstantRange(Lower, CR.Upper);
431
432 return CR;
Nick Lewycky228f5b42012-01-03 20:33:00 +0000433 }
Nuno Lopesebb0c942012-06-28 00:59:33 +0000434 if (CR.Upper.ule(Lower)) {
Nick Lewycky61b4a262007-07-14 02:51:34 +0000435 if (CR.Lower.ult(Lower))
436 return *this;
437
438 return ConstantRange(CR.Lower, Upper);
439 }
Craig Topperd29549e2017-05-07 21:48:08 +0000440 if (isSizeStrictlySmallerThan(CR))
Nick Lewycky61b4a262007-07-14 02:51:34 +0000441 return *this;
Nick Lewycky228f5b42012-01-03 20:33:00 +0000442 return CR;
Nick Lewycky61b4a262007-07-14 02:51:34 +0000443}
444
Reid Spencer6a440332007-03-01 07:54:15 +0000445ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
Reid Spencer9b3d6ec2007-02-28 22:02:48 +0000446 assert(getBitWidth() == CR.getBitWidth() &&
447 "ConstantRange types don't agree!");
Chris Lattner113f2ae2002-09-01 23:53:36 +0000448
Nick Lewyckycf87f9e2007-03-02 03:33:05 +0000449 if ( isFullSet() || CR.isEmptySet()) return *this;
450 if (CR.isFullSet() || isEmptySet()) return CR;
Chris Lattner113f2ae2002-09-01 23:53:36 +0000451
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000452 if (!isWrappedSet() && CR.isWrappedSet()) return CR.unionWith(*this);
453
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000454 if (!isWrappedSet() && !CR.isWrappedSet()) {
Nick Lewycky567daf32009-07-19 03:44:35 +0000455 if (CR.Upper.ult(Lower) || Upper.ult(CR.Lower)) {
456 // If the two ranges are disjoint, find the smaller gap and bridge it.
457 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
458 if (d1.ult(d2))
459 return ConstantRange(Lower, CR.Upper);
Nick Lewycky228f5b42012-01-03 20:33:00 +0000460 return ConstantRange(CR.Lower, Upper);
Nick Lewycky567daf32009-07-19 03:44:35 +0000461 }
462
Craig Topper8fb5a142017-04-29 07:24:13 +0000463 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
464 APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
Nick Lewycky567daf32009-07-19 03:44:35 +0000465
Craig Topper61729fd2017-05-09 05:01:29 +0000466 if (L.isNullValue() && U.isNullValue())
Nick Lewycky567daf32009-07-19 03:44:35 +0000467 return ConstantRange(getBitWidth());
468
Craig Topperb7920252017-04-29 06:40:47 +0000469 return ConstantRange(std::move(L), std::move(U));
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000470 }
471
Nick Lewycky567daf32009-07-19 03:44:35 +0000472 if (!CR.isWrappedSet()) {
473 // ------U L----- and ------U L----- : this
474 // L--U L--U : CR
475 if (CR.Upper.ule(Upper) || CR.Lower.uge(Lower))
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000476 return *this;
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000477
Nick Lewycky567daf32009-07-19 03:44:35 +0000478 // ------U L----- : this
479 // L---------U : CR
480 if (CR.Lower.ule(Upper) && Lower.ule(CR.Upper))
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000481 return ConstantRange(getBitWidth());
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000482
Nick Lewycky567daf32009-07-19 03:44:35 +0000483 // ----U L---- : this
484 // L---U : CR
485 // <d1> <d2>
486 if (Upper.ule(CR.Lower) && CR.Upper.ule(Lower)) {
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000487 APInt d1 = CR.Lower - Upper, d2 = Lower - CR.Upper;
Nick Lewycky567daf32009-07-19 03:44:35 +0000488 if (d1.ult(d2))
489 return ConstantRange(Lower, CR.Upper);
Nick Lewycky228f5b42012-01-03 20:33:00 +0000490 return ConstantRange(CR.Lower, Upper);
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000491 }
492
Nick Lewycky567daf32009-07-19 03:44:35 +0000493 // ----U L----- : this
494 // L----U : CR
495 if (Upper.ult(CR.Lower) && Lower.ult(CR.Upper))
496 return ConstantRange(CR.Lower, Upper);
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000497
Nick Lewycky567daf32009-07-19 03:44:35 +0000498 // ------U L---- : this
499 // L-----U : CR
Nick Lewycky228f5b42012-01-03 20:33:00 +0000500 assert(CR.Lower.ult(Upper) && CR.Upper.ult(Lower) &&
501 "ConstantRange::unionWith missed a case with one range wrapped");
502 return ConstantRange(Lower, CR.Upper);
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000503 }
504
Nick Lewycky567daf32009-07-19 03:44:35 +0000505 // ------U L---- and ------U L---- : this
506 // -U L----------- and ------------U L : CR
507 if (CR.Lower.ule(Upper) || Lower.ule(CR.Upper))
508 return ConstantRange(getBitWidth());
Nick Lewyckyf22938a2007-04-01 03:47:44 +0000509
Craig Topper8fb5a142017-04-29 07:24:13 +0000510 APInt L = CR.Lower.ult(Lower) ? CR.Lower : Lower;
511 APInt U = CR.Upper.ugt(Upper) ? CR.Upper : Upper;
Nick Lewyckycf87f9e2007-03-02 03:33:05 +0000512
Craig Topperb7920252017-04-29 06:40:47 +0000513 return ConstantRange(std::move(L), std::move(U));
Chris Lattner113f2ae2002-09-01 23:53:36 +0000514}
Chris Lattnere0bb9eb2002-09-02 00:18:22 +0000515
Philip Reames4d00af12016-12-01 20:08:47 +0000516ConstantRange ConstantRange::castOp(Instruction::CastOps CastOp,
517 uint32_t ResultBitWidth) const {
518 switch (CastOp) {
519 default:
520 llvm_unreachable("unsupported cast type");
521 case Instruction::Trunc:
522 return truncate(ResultBitWidth);
523 case Instruction::SExt:
524 return signExtend(ResultBitWidth);
525 case Instruction::ZExt:
526 return zeroExtend(ResultBitWidth);
527 case Instruction::BitCast:
528 return *this;
529 case Instruction::FPToUI:
530 case Instruction::FPToSI:
531 if (getBitWidth() == ResultBitWidth)
532 return *this;
533 else
534 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
535 case Instruction::UIToFP: {
536 // TODO: use input range if available
537 auto BW = getBitWidth();
538 APInt Min = APInt::getMinValue(BW).zextOrSelf(ResultBitWidth);
539 APInt Max = APInt::getMaxValue(BW).zextOrSelf(ResultBitWidth);
Craig Topperb7920252017-04-29 06:40:47 +0000540 return ConstantRange(std::move(Min), std::move(Max));
Philip Reames4d00af12016-12-01 20:08:47 +0000541 }
542 case Instruction::SIToFP: {
543 // TODO: use input range if available
544 auto BW = getBitWidth();
545 APInt SMin = APInt::getSignedMinValue(BW).sextOrSelf(ResultBitWidth);
546 APInt SMax = APInt::getSignedMaxValue(BW).sextOrSelf(ResultBitWidth);
Craig Topperb7920252017-04-29 06:40:47 +0000547 return ConstantRange(std::move(SMin), std::move(SMax));
Philip Reames4d00af12016-12-01 20:08:47 +0000548 }
549 case Instruction::FPTrunc:
550 case Instruction::FPExt:
551 case Instruction::IntToPtr:
552 case Instruction::PtrToInt:
553 case Instruction::AddrSpaceCast:
554 // Conservatively return full set.
555 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
556 };
557}
558
Reid Spencer9b3d6ec2007-02-28 22:02:48 +0000559ConstantRange ConstantRange::zeroExtend(uint32_t DstTySize) const {
Nick Lewyckya35462d2010-09-06 23:52:49 +0000560 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
561
Reid Spencer9b3d6ec2007-02-28 22:02:48 +0000562 unsigned SrcTySize = getBitWidth();
Reid Spencere1f3f192007-02-28 17:36:23 +0000563 assert(SrcTySize < DstTySize && "Not a value extension");
Nuno Lopeseb9d2752012-07-23 20:33:29 +0000564 if (isFullSet() || isWrappedSet()) {
Nick Lewyckya35462d2010-09-06 23:52:49 +0000565 // Change into [0, 1 << src bit width)
Nuno Lopeseb9d2752012-07-23 20:33:29 +0000566 APInt LowerExt(DstTySize, 0);
567 if (!Upper) // special case: [X, 0) -- not really wrapping around
568 LowerExt = Lower.zext(DstTySize);
Craig Topperb7920252017-04-29 06:40:47 +0000569 return ConstantRange(std::move(LowerExt),
570 APInt::getOneBitSet(DstTySize, SrcTySize));
Nuno Lopeseb9d2752012-07-23 20:33:29 +0000571 }
Chris Lattner55481f72004-03-30 00:20:08 +0000572
Jay Foad583abbc2010-12-07 08:25:19 +0000573 return ConstantRange(Lower.zext(DstTySize), Upper.zext(DstTySize));
Chris Lattner55481f72004-03-30 00:20:08 +0000574}
575
Nick Lewyckyb89804f2007-04-07 15:41:33 +0000576ConstantRange ConstantRange::signExtend(uint32_t DstTySize) const {
Nick Lewyckya35462d2010-09-06 23:52:49 +0000577 if (isEmptySet()) return ConstantRange(DstTySize, /*isFullSet=*/false);
578
Nick Lewyckyb89804f2007-04-07 15:41:33 +0000579 unsigned SrcTySize = getBitWidth();
580 assert(SrcTySize < DstTySize && "Not a value extension");
Nuno Lopes1112eca2013-10-30 15:36:50 +0000581
582 // special case: [X, INT_MIN) -- not really wrapping around
Nuno Lopes14d4b0c2013-10-31 19:53:53 +0000583 if (Upper.isMinSignedValue())
Nuno Lopes1112eca2013-10-30 15:36:50 +0000584 return ConstantRange(Lower.sext(DstTySize), Upper.zext(DstTySize));
585
Nick Lewyckya35462d2010-09-06 23:52:49 +0000586 if (isFullSet() || isSignWrappedSet()) {
Nick Lewyckyb89804f2007-04-07 15:41:33 +0000587 return ConstantRange(APInt::getHighBitsSet(DstTySize,DstTySize-SrcTySize+1),
Nick Lewycky5edc4592009-07-13 04:17:23 +0000588 APInt::getLowBitsSet(DstTySize, SrcTySize-1) + 1);
Nick Lewyckyb89804f2007-04-07 15:41:33 +0000589 }
590
Jay Foad583abbc2010-12-07 08:25:19 +0000591 return ConstantRange(Lower.sext(DstTySize), Upper.sext(DstTySize));
Nick Lewyckyb89804f2007-04-07 15:41:33 +0000592}
593
Reid Spencer9b3d6ec2007-02-28 22:02:48 +0000594ConstantRange ConstantRange::truncate(uint32_t DstTySize) const {
Benjamin Kramer6709e052011-11-24 17:24:33 +0000595 assert(getBitWidth() > DstTySize && "Not a value truncation");
Nuno Lopesc14776d2012-07-19 16:27:45 +0000596 if (isEmptySet())
597 return ConstantRange(DstTySize, /*isFullSet=*/false);
598 if (isFullSet())
Nick Lewyckyd385c222010-08-11 22:04:36 +0000599 return ConstantRange(DstTySize, /*isFullSet=*/true);
Chris Lattner55481f72004-03-30 00:20:08 +0000600
Nuno Lopesc14776d2012-07-19 16:27:45 +0000601 APInt LowerDiv(Lower), UpperDiv(Upper);
602 ConstantRange Union(DstTySize, /*isFullSet=*/false);
603
604 // Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue]
605 // We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and
606 // then we do the union with [MaxValue, Upper)
607 if (isWrappedSet()) {
Craig Topperf6e138d2017-06-05 20:48:05 +0000608 // If Upper is greater than or equal to MaxValue(DstTy), it covers the whole
609 // truncated range.
610 if (Upper.getActiveBits() > DstTySize ||
611 Upper.countTrailingOnes() == DstTySize)
Nuno Lopesc14776d2012-07-19 16:27:45 +0000612 return ConstantRange(DstTySize, /*isFullSet=*/true);
613
614 Union = ConstantRange(APInt::getMaxValue(DstTySize),Upper.trunc(DstTySize));
Craig Topper86616532017-04-30 00:44:05 +0000615 UpperDiv.setAllBits();
Nuno Lopesc14776d2012-07-19 16:27:45 +0000616
617 // Union covers the MaxValue case, so return if the remaining range is just
Craig Topperf6e138d2017-06-05 20:48:05 +0000618 // MaxValue(DstTy).
Nuno Lopesc14776d2012-07-19 16:27:45 +0000619 if (LowerDiv == UpperDiv)
620 return Union;
621 }
622
623 // Chop off the most significant bits that are past the destination bitwidth.
Craig Topperf6e138d2017-06-05 20:48:05 +0000624 if (LowerDiv.getActiveBits() > DstTySize) {
625 // Mask to just the signficant bits and subtract from LowerDiv/UpperDiv.
626 APInt Adjust = LowerDiv & APInt::getBitsSetFrom(getBitWidth(), DstTySize);
627 LowerDiv -= Adjust;
628 UpperDiv -= Adjust;
Nuno Lopesc14776d2012-07-19 16:27:45 +0000629 }
630
Craig Topperf6e138d2017-06-05 20:48:05 +0000631 unsigned UpperDivWidth = UpperDiv.getActiveBits();
632 if (UpperDivWidth <= DstTySize)
Nuno Lopesc14776d2012-07-19 16:27:45 +0000633 return ConstantRange(LowerDiv.trunc(DstTySize),
634 UpperDiv.trunc(DstTySize)).unionWith(Union);
635
Nick Lewyckybfad0152016-06-06 01:51:23 +0000636 // The truncated value wraps around. Check if we can do better than fullset.
Craig Topperf6e138d2017-06-05 20:48:05 +0000637 if (UpperDivWidth == DstTySize + 1) {
638 // Clear the MSB so that UpperDiv wraps around.
639 UpperDiv.clearBit(DstTySize);
640 if (UpperDiv.ult(LowerDiv))
641 return ConstantRange(LowerDiv.trunc(DstTySize),
642 UpperDiv.trunc(DstTySize)).unionWith(Union);
643 }
Nuno Lopesc14776d2012-07-19 16:27:45 +0000644
645 return ConstantRange(DstTySize, /*isFullSet=*/true);
Chris Lattner55481f72004-03-30 00:20:08 +0000646}
647
Nuno Lopes640eb702009-11-09 15:36:28 +0000648ConstantRange ConstantRange::zextOrTrunc(uint32_t DstTySize) const {
649 unsigned SrcTySize = getBitWidth();
650 if (SrcTySize > DstTySize)
651 return truncate(DstTySize);
Nick Lewycky228f5b42012-01-03 20:33:00 +0000652 if (SrcTySize < DstTySize)
Nuno Lopes640eb702009-11-09 15:36:28 +0000653 return zeroExtend(DstTySize);
Nick Lewycky228f5b42012-01-03 20:33:00 +0000654 return *this;
Nuno Lopes640eb702009-11-09 15:36:28 +0000655}
656
Nuno Lopes640eb702009-11-09 15:36:28 +0000657ConstantRange ConstantRange::sextOrTrunc(uint32_t DstTySize) const {
658 unsigned SrcTySize = getBitWidth();
659 if (SrcTySize > DstTySize)
660 return truncate(DstTySize);
Nick Lewycky228f5b42012-01-03 20:33:00 +0000661 if (SrcTySize < DstTySize)
Nuno Lopes640eb702009-11-09 15:36:28 +0000662 return signExtend(DstTySize);
Nick Lewycky228f5b42012-01-03 20:33:00 +0000663 return *this;
Nuno Lopes640eb702009-11-09 15:36:28 +0000664}
665
Philip Reames4d00af12016-12-01 20:08:47 +0000666ConstantRange ConstantRange::binaryOp(Instruction::BinaryOps BinOp,
667 const ConstantRange &Other) const {
668 assert(BinOp >= Instruction::BinaryOpsBegin &&
669 BinOp < Instruction::BinaryOpsEnd && "Binary operators only!");
670
671 switch (BinOp) {
672 case Instruction::Add:
673 return add(Other);
674 case Instruction::Sub:
675 return sub(Other);
676 case Instruction::Mul:
677 return multiply(Other);
678 case Instruction::UDiv:
679 return udiv(Other);
680 case Instruction::Shl:
681 return shl(Other);
682 case Instruction::LShr:
683 return lshr(Other);
Max Kazantsevd7921712017-12-18 13:01:32 +0000684 case Instruction::AShr:
685 return ashr(Other);
Philip Reames4d00af12016-12-01 20:08:47 +0000686 case Instruction::And:
687 return binaryAnd(Other);
688 case Instruction::Or:
689 return binaryOr(Other);
690 // Note: floating point operations applied to abstract ranges are just
691 // ideal integer operations with a lossy representation
692 case Instruction::FAdd:
693 return add(Other);
694 case Instruction::FSub:
695 return sub(Other);
696 case Instruction::FMul:
697 return multiply(Other);
698 default:
699 // Conservatively return full set.
700 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
701 }
702}
703
Dan Gohman5035fbf2009-07-09 22:07:27 +0000704ConstantRange
705ConstantRange::add(const ConstantRange &Other) const {
706 if (isEmptySet() || Other.isEmptySet())
707 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nick Lewycky73b704d2009-07-13 02:49:08 +0000708 if (isFullSet() || Other.isFullSet())
709 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Dan Gohman5035fbf2009-07-09 22:07:27 +0000710
Dan Gohman5035fbf2009-07-09 22:07:27 +0000711 APInt NewLower = getLower() + Other.getLower();
712 APInt NewUpper = getUpper() + Other.getUpper() - 1;
713 if (NewLower == NewUpper)
714 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
715
Craig Topperb7920252017-04-29 06:40:47 +0000716 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
Craig Topperd29549e2017-05-07 21:48:08 +0000717 if (X.isSizeStrictlySmallerThan(*this) ||
718 X.isSizeStrictlySmallerThan(Other))
Dan Gohman5035fbf2009-07-09 22:07:27 +0000719 // We've wrapped, therefore, full set.
720 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Dan Gohman5035fbf2009-07-09 22:07:27 +0000721 return X;
Chris Lattnere0bb9eb2002-09-02 00:18:22 +0000722}
723
Artur Pilipenkoed841032016-10-19 14:44:23 +0000724ConstantRange ConstantRange::addWithNoSignedWrap(const APInt &Other) const {
725 // Calculate the subset of this range such that "X + Other" is
726 // guaranteed not to wrap (overflow) for all X in this subset.
727 // makeGuaranteedNoWrapRegion will produce an exact NSW range since we are
728 // passing a single element range.
729 auto NSWRange = ConstantRange::makeGuaranteedNoWrapRegion(BinaryOperator::Add,
730 ConstantRange(Other),
731 OverflowingBinaryOperator::NoSignedWrap);
732 auto NSWConstrainedRange = intersectWith(NSWRange);
733
734 return NSWConstrainedRange.add(ConstantRange(Other));
735}
736
Dan Gohman5035fbf2009-07-09 22:07:27 +0000737ConstantRange
Nick Lewyckyd385c222010-08-11 22:04:36 +0000738ConstantRange::sub(const ConstantRange &Other) const {
739 if (isEmptySet() || Other.isEmptySet())
740 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
741 if (isFullSet() || Other.isFullSet())
742 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
743
Nick Lewycky5dc6b792011-06-22 21:13:46 +0000744 APInt NewLower = getLower() - Other.getUpper() + 1;
745 APInt NewUpper = getUpper() - Other.getLower();
Nick Lewyckyd385c222010-08-11 22:04:36 +0000746 if (NewLower == NewUpper)
747 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
748
Craig Topperb7920252017-04-29 06:40:47 +0000749 ConstantRange X = ConstantRange(std::move(NewLower), std::move(NewUpper));
Craig Topperd29549e2017-05-07 21:48:08 +0000750 if (X.isSizeStrictlySmallerThan(*this) ||
751 X.isSizeStrictlySmallerThan(Other))
Nick Lewyckyd385c222010-08-11 22:04:36 +0000752 // We've wrapped, therefore, full set.
753 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Nick Lewyckyd385c222010-08-11 22:04:36 +0000754 return X;
755}
756
757ConstantRange
Dan Gohman5035fbf2009-07-09 22:07:27 +0000758ConstantRange::multiply(const ConstantRange &Other) const {
Dan Gohman3f8ed9e2010-01-26 15:56:18 +0000759 // TODO: If either operand is a single element and the multiply is known to
760 // be non-wrapping, round the result min and max value to the appropriate
761 // multiple of that element. If wrapping is possible, at least adjust the
762 // range according to the greatest power-of-two factor of the single element.
Dan Gohman5325efc2010-01-26 04:13:15 +0000763
Nick Lewycky2951c992009-07-12 02:19:05 +0000764 if (isEmptySet() || Other.isEmptySet())
765 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nuno Lopes986cc182012-07-16 20:47:16 +0000766
James Molloydcc78ec2015-03-06 15:50:47 +0000767 // Multiplication is signedness-independent. However different ranges can be
768 // obtained depending on how the input ranges are treated. These different
769 // ranges are all conservatively correct, but one might be better than the
770 // other. We calculate two ranges; one treating the inputs as unsigned
771 // and the other signed, then return the smallest of these ranges.
772
773 // Unsigned range first.
Nick Lewycky53023892009-07-13 03:27:41 +0000774 APInt this_min = getUnsignedMin().zext(getBitWidth() * 2);
775 APInt this_max = getUnsignedMax().zext(getBitWidth() * 2);
776 APInt Other_min = Other.getUnsignedMin().zext(getBitWidth() * 2);
777 APInt Other_max = Other.getUnsignedMax().zext(getBitWidth() * 2);
Nick Lewycky2951c992009-07-12 02:19:05 +0000778
Nick Lewycky53023892009-07-13 03:27:41 +0000779 ConstantRange Result_zext = ConstantRange(this_min * Other_min,
780 this_max * Other_max + 1);
James Molloydcc78ec2015-03-06 15:50:47 +0000781 ConstantRange UR = Result_zext.truncate(getBitWidth());
782
Pete Cooper34a7a942016-05-27 17:06:50 +0000783 // If the unsigned range doesn't wrap, and isn't negative then it's a range
784 // from one positive number to another which is as good as we can generate.
785 // In this case, skip the extra work of generating signed ranges which aren't
786 // going to be better than this range.
Craig Topperc51d0532017-05-10 20:01:48 +0000787 if (!UR.isWrappedSet() &&
788 (UR.getUpper().isNonNegative() || UR.getUpper().isMinSignedValue()))
Pete Cooper34a7a942016-05-27 17:06:50 +0000789 return UR;
790
James Molloydcc78ec2015-03-06 15:50:47 +0000791 // Now the signed range. Because we could be dealing with negative numbers
792 // here, the lower bound is the smallest of the cartesian product of the
793 // lower and upper ranges; for example:
794 // [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6.
795 // Similarly for the upper bound, swapping min for max.
796
797 this_min = getSignedMin().sext(getBitWidth() * 2);
798 this_max = getSignedMax().sext(getBitWidth() * 2);
799 Other_min = Other.getSignedMin().sext(getBitWidth() * 2);
800 Other_max = Other.getSignedMax().sext(getBitWidth() * 2);
801
802 auto L = {this_min * Other_min, this_min * Other_max,
803 this_max * Other_min, this_max * Other_max};
804 auto Compare = [](const APInt &A, const APInt &B) { return A.slt(B); };
805 ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
806 ConstantRange SR = Result_sext.truncate(getBitWidth());
807
Craig Topperd29549e2017-05-07 21:48:08 +0000808 return UR.isSizeStrictlySmallerThan(SR) ? UR : SR;
Dan Gohman5035fbf2009-07-09 22:07:27 +0000809}
810
811ConstantRange
812ConstantRange::smax(const ConstantRange &Other) const {
Dan Gohmandc33ae22009-07-09 23:16:10 +0000813 // X smax Y is: range(smax(X_smin, Y_smin),
814 // smax(X_smax, Y_smax))
815 if (isEmptySet() || Other.isEmptySet())
816 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Dan Gohmandc33ae22009-07-09 23:16:10 +0000817 APInt NewL = APIntOps::smax(getSignedMin(), Other.getSignedMin());
818 APInt NewU = APIntOps::smax(getSignedMax(), Other.getSignedMax()) + 1;
819 if (NewU == NewL)
820 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Craig Topperb7920252017-04-29 06:40:47 +0000821 return ConstantRange(std::move(NewL), std::move(NewU));
Dan Gohman5035fbf2009-07-09 22:07:27 +0000822}
823
824ConstantRange
825ConstantRange::umax(const ConstantRange &Other) const {
826 // X umax Y is: range(umax(X_umin, Y_umin),
827 // umax(X_umax, Y_umax))
828 if (isEmptySet() || Other.isEmptySet())
829 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Dan Gohman5035fbf2009-07-09 22:07:27 +0000830 APInt NewL = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
831 APInt NewU = APIntOps::umax(getUnsignedMax(), Other.getUnsignedMax()) + 1;
832 if (NewU == NewL)
833 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Craig Topperb7920252017-04-29 06:40:47 +0000834 return ConstantRange(std::move(NewL), std::move(NewU));
Dan Gohman5035fbf2009-07-09 22:07:27 +0000835}
836
837ConstantRange
Philip Reamesba313122016-02-26 22:08:18 +0000838ConstantRange::smin(const ConstantRange &Other) const {
839 // X smin Y is: range(smin(X_smin, Y_smin),
840 // smin(X_smax, Y_smax))
841 if (isEmptySet() || Other.isEmptySet())
842 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
843 APInt NewL = APIntOps::smin(getSignedMin(), Other.getSignedMin());
844 APInt NewU = APIntOps::smin(getSignedMax(), Other.getSignedMax()) + 1;
845 if (NewU == NewL)
846 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Craig Topperb7920252017-04-29 06:40:47 +0000847 return ConstantRange(std::move(NewL), std::move(NewU));
Philip Reamesba313122016-02-26 22:08:18 +0000848}
849
850ConstantRange
851ConstantRange::umin(const ConstantRange &Other) const {
852 // X umin Y is: range(umin(X_umin, Y_umin),
853 // umin(X_umax, Y_umax))
854 if (isEmptySet() || Other.isEmptySet())
855 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
856 APInt NewL = APIntOps::umin(getUnsignedMin(), Other.getUnsignedMin());
857 APInt NewU = APIntOps::umin(getUnsignedMax(), Other.getUnsignedMax()) + 1;
858 if (NewU == NewL)
859 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Craig Topperb7920252017-04-29 06:40:47 +0000860 return ConstantRange(std::move(NewL), std::move(NewU));
Philip Reamesba313122016-02-26 22:08:18 +0000861}
862
863ConstantRange
Nick Lewyckyf1b8cb32009-07-12 05:18:18 +0000864ConstantRange::udiv(const ConstantRange &RHS) const {
Craig Topper61729fd2017-05-09 05:01:29 +0000865 if (isEmptySet() || RHS.isEmptySet() || RHS.getUnsignedMax().isNullValue())
Nick Lewyckyf1b8cb32009-07-12 05:18:18 +0000866 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
867 if (RHS.isFullSet())
868 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
869
870 APInt Lower = getUnsignedMin().udiv(RHS.getUnsignedMax());
871
872 APInt RHS_umin = RHS.getUnsignedMin();
Craig Topper61729fd2017-05-09 05:01:29 +0000873 if (RHS_umin.isNullValue()) {
Nick Lewyckyf1b8cb32009-07-12 05:18:18 +0000874 // We want the lowest value in RHS excluding zero. Usually that would be 1
875 // except for a range in the form of [X, 1) in which case it would be X.
876 if (RHS.getUpper() == 1)
877 RHS_umin = RHS.getLower();
878 else
Craig Topper86616532017-04-30 00:44:05 +0000879 RHS_umin = 1;
Nick Lewyckyf1b8cb32009-07-12 05:18:18 +0000880 }
881
882 APInt Upper = getUnsignedMax().udiv(RHS_umin) + 1;
883
884 // If the LHS is Full and the RHS is a wrapped interval containing 1 then
885 // this could occur.
886 if (Lower == Upper)
887 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
888
Craig Topperb7920252017-04-29 06:40:47 +0000889 return ConstantRange(std::move(Lower), std::move(Upper));
Dan Gohman5035fbf2009-07-09 22:07:27 +0000890}
891
Nuno Lopes60d5b1c2009-11-12 14:53:53 +0000892ConstantRange
Nick Lewyckyad48e012010-09-07 05:39:02 +0000893ConstantRange::binaryAnd(const ConstantRange &Other) const {
894 if (isEmptySet() || Other.isEmptySet())
895 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
896
897 // TODO: replace this with something less conservative
898
899 APInt umin = APIntOps::umin(Other.getUnsignedMax(), getUnsignedMax());
900 if (umin.isAllOnesValue())
901 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Craig Topperb7920252017-04-29 06:40:47 +0000902 return ConstantRange(APInt::getNullValue(getBitWidth()), std::move(umin) + 1);
Nick Lewyckyad48e012010-09-07 05:39:02 +0000903}
904
905ConstantRange
906ConstantRange::binaryOr(const ConstantRange &Other) const {
907 if (isEmptySet() || Other.isEmptySet())
908 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
909
910 // TODO: replace this with something less conservative
911
912 APInt umax = APIntOps::umax(getUnsignedMin(), Other.getUnsignedMin());
Craig Toppere8dea1b2017-04-28 21:48:09 +0000913 if (umax.isNullValue())
Nick Lewyckyad48e012010-09-07 05:39:02 +0000914 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Craig Topperb7920252017-04-29 06:40:47 +0000915 return ConstantRange(std::move(umax), APInt::getNullValue(getBitWidth()));
Nick Lewyckyad48e012010-09-07 05:39:02 +0000916}
917
918ConstantRange
Nick Lewyckyd385c222010-08-11 22:04:36 +0000919ConstantRange::shl(const ConstantRange &Other) const {
920 if (isEmptySet() || Other.isEmptySet())
921 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nuno Lopes60d5b1c2009-11-12 14:53:53 +0000922
Craig Topperef028032017-05-09 07:04:04 +0000923 APInt max = getUnsignedMax();
924 APInt Other_umax = Other.getUnsignedMax();
Nuno Lopes60d5b1c2009-11-12 14:53:53 +0000925
Craig Topperef028032017-05-09 07:04:04 +0000926 // there's overflow!
927 if (Other_umax.uge(max.countLeadingZeros()))
928 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Nuno Lopes60d5b1c2009-11-12 14:53:53 +0000929
930 // FIXME: implement the other tricky cases
Craig Topperef028032017-05-09 07:04:04 +0000931
932 APInt min = getUnsignedMin();
933 min <<= Other.getUnsignedMin();
934 max <<= Other_umax;
935
936 return ConstantRange(std::move(min), std::move(max) + 1);
Nuno Lopes60d5b1c2009-11-12 14:53:53 +0000937}
938
939ConstantRange
Nick Lewyckyd385c222010-08-11 22:04:36 +0000940ConstantRange::lshr(const ConstantRange &Other) const {
941 if (isEmptySet() || Other.isEmptySet())
942 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Craig Topper79b76662017-05-09 07:04:02 +0000943
944 APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
Nick Lewyckyd385c222010-08-11 22:04:36 +0000945 APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
Craig Topper79b76662017-05-09 07:04:02 +0000946 if (min == max)
Nick Lewyckyd385c222010-08-11 22:04:36 +0000947 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
948
Craig Topper79b76662017-05-09 07:04:02 +0000949 return ConstantRange(std::move(min), std::move(max));
Nuno Lopes60d5b1c2009-11-12 14:53:53 +0000950}
951
Max Kazantsevd7921712017-12-18 13:01:32 +0000952ConstantRange
953ConstantRange::ashr(const ConstantRange &Other) const {
954 if (isEmptySet() || Other.isEmptySet())
955 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
956
957 // May straddle zero, so handle both positive and negative cases.
958 // 'PosMax' is the upper bound of the result of the ashr
959 // operation, when Upper of the LHS of ashr is a non-negative.
960 // number. Since ashr of a non-negative number will result in a
961 // smaller number, the Upper value of LHS is shifted right with
962 // the minimum value of 'Other' instead of the maximum value.
963 APInt PosMax = getSignedMax().ashr(Other.getUnsignedMin()) + 1;
964
965 // 'PosMin' is the lower bound of the result of the ashr
966 // operation, when Lower of the LHS is a non-negative number.
967 // Since ashr of a non-negative number will result in a smaller
968 // number, the Lower value of LHS is shifted right with the
969 // maximum value of 'Other'.
970 APInt PosMin = getSignedMin().ashr(Other.getUnsignedMax());
971
972 // 'NegMax' is the upper bound of the result of the ashr
973 // operation, when Upper of the LHS of ashr is a negative number.
974 // Since 'ashr' of a negative number will result in a bigger
975 // number, the Upper value of LHS is shifted right with the
976 // maximum value of 'Other'.
977 APInt NegMax = getSignedMax().ashr(Other.getUnsignedMax()) + 1;
978
979 // 'NegMin' is the lower bound of the result of the ashr
980 // operation, when Lower of the LHS of ashr is a negative number.
981 // Since 'ashr' of a negative number will result in a bigger
982 // number, the Lower value of LHS is shifted right with the
983 // minimum value of 'Other'.
984 APInt NegMin = getSignedMin().ashr(Other.getUnsignedMin());
985
986 APInt max, min;
987 if (getSignedMin().isNonNegative()) {
988 // Upper and Lower of LHS are non-negative.
989 min = PosMin;
990 max = PosMax;
991 } else if (getSignedMax().isNegative()) {
992 // Upper and Lower of LHS are negative.
993 min = NegMin;
994 max = NegMax;
995 } else {
996 // Upper is non-negative and Lower is negative.
997 min = NegMin;
998 max = PosMax;
999 }
1000 if (min == max)
1001 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
1002
1003 return ConstantRange(std::move(min), std::move(max));
1004}
1005
Owen Anderson1a9078b2010-08-07 05:47:46 +00001006ConstantRange ConstantRange::inverse() const {
Nick Lewycky228f5b42012-01-03 20:33:00 +00001007 if (isFullSet())
Nick Lewyckyd385c222010-08-11 22:04:36 +00001008 return ConstantRange(getBitWidth(), /*isFullSet=*/false);
Nick Lewycky228f5b42012-01-03 20:33:00 +00001009 if (isEmptySet())
Nick Lewyckyd385c222010-08-11 22:04:36 +00001010 return ConstantRange(getBitWidth(), /*isFullSet=*/true);
Owen Anderson1a9078b2010-08-07 05:47:46 +00001011 return ConstantRange(Upper, Lower);
1012}
1013
Dan Gohmandc33ae22009-07-09 23:16:10 +00001014void ConstantRange::print(raw_ostream &OS) const {
Dan Gohman837ada72010-01-26 04:12:55 +00001015 if (isFullSet())
1016 OS << "full-set";
1017 else if (isEmptySet())
1018 OS << "empty-set";
1019 else
1020 OS << "[" << Lower << "," << Upper << ")";
Dan Gohman5035fbf2009-07-09 22:07:27 +00001021}
1022
Aaron Ballman615eb472017-10-15 14:32:27 +00001023#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Yaron Kereneb2a2542016-01-29 20:50:44 +00001024LLVM_DUMP_METHOD void ConstantRange::dump() const {
David Greenede7b3532010-01-05 01:28:32 +00001025 print(dbgs());
Dan Gohman5035fbf2009-07-09 22:07:27 +00001026}
Matthias Braun8c209aa2017-01-28 02:02:38 +00001027#endif
Peter Collingbourneecdd58f2016-10-21 19:59:26 +00001028
1029ConstantRange llvm::getConstantRangeFromMetadata(const MDNode &Ranges) {
1030 const unsigned NumRanges = Ranges.getNumOperands() / 2;
1031 assert(NumRanges >= 1 && "Must have at least one range!");
1032 assert(Ranges.getNumOperands() % 2 == 0 && "Must be a sequence of pairs");
1033
1034 auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
1035 auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
1036
1037 ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
1038
1039 for (unsigned i = 1; i < NumRanges; ++i) {
1040 auto *Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
1041 auto *High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
1042
1043 // Note: unionWith will potentially create a range that contains values not
1044 // contained in any of the original N ranges.
1045 CR = CR.unionWith(ConstantRange(Low->getValue(), High->getValue()));
1046 }
1047
1048 return CR;
1049}