1 //===-- ConstantRange.cpp - ConstantRange implementation ------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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):
17 // [F, F) = {} = Empty set
20 // [T, T) = {F, T} = Full set
22 //===----------------------------------------------------------------------===//
24 #include "llvm/Support/ConstantRange.h"
25 #include "llvm/Type.h"
26 #include "llvm/Instruction.h"
27 #include "llvm/ConstantHandling.h"
30 /// Initialize a full (the default) or empty set for the specified type.
32 ConstantRange::ConstantRange(const Type *Ty, bool Full) {
33 assert(Ty->isIntegral() &&
34 "Cannot make constant range of non-integral type!");
36 Lower = Upper = ConstantIntegral::getMaxValue(Ty);
38 Lower = Upper = ConstantIntegral::getMinValue(Ty);
41 /// Initialize a range of values explicitly... this will assert out if
42 /// Lower==Upper and Lower != Min or Max for its type (or if the two constants
43 /// have different types)
45 ConstantRange::ConstantRange(ConstantIntegral *L,
46 ConstantIntegral *U) : Lower(L), Upper(U) {
47 assert(Lower->getType() == Upper->getType() &&
48 "Incompatible types for ConstantRange!");
50 // Make sure that if L & U are equal that they are either Min or Max...
51 assert((L != U || (L == ConstantIntegral::getMaxValue(L->getType()) ||
52 L == ConstantIntegral::getMinValue(L->getType()))) &&
53 "Lower == Upper, but they aren't min or max for type!");
56 static ConstantIntegral *Next(ConstantIntegral *CI) {
57 if (CI->getType() == Type::BoolTy)
58 return CI == ConstantBool::True ? ConstantBool::False : ConstantBool::True;
60 // Otherwise use operator+ in the ConstantHandling Library.
61 Constant *Result = *ConstantInt::get(CI->getType(), 1) + *CI;
62 assert(Result && "ConstantHandling not implemented for integral plus!?");
63 return cast<ConstantIntegral>(Result);
66 /// Initialize a set of values that all satisfy the condition with C.
68 ConstantRange::ConstantRange(unsigned SetCCOpcode, ConstantIntegral *C) {
69 switch (SetCCOpcode) {
70 default: assert(0 && "Invalid SetCC opcode to ConstantRange ctor!");
71 case Instruction::SetEQ: Lower = C; Upper = Next(C); return;
72 case Instruction::SetNE: Upper = C; Lower = Next(C); return;
73 case Instruction::SetLT:
74 Lower = ConstantIntegral::getMinValue(C->getType());
77 case Instruction::SetGT:
79 Upper = ConstantIntegral::getMinValue(C->getType()); // Min = Next(Max)
81 case Instruction::SetLE:
82 Lower = ConstantIntegral::getMinValue(C->getType());
85 case Instruction::SetGE:
87 Upper = ConstantIntegral::getMinValue(C->getType()); // Min = Next(Max)
92 /// getType - Return the LLVM data type of this range.
94 const Type *ConstantRange::getType() const { return Lower->getType(); }
96 /// isFullSet - Return true if this set contains all of the elements possible
97 /// for this data-type
98 bool ConstantRange::isFullSet() const {
99 return Lower == Upper && Lower == ConstantIntegral::getMaxValue(getType());
102 /// isEmptySet - Return true if this set contains no members.
104 bool ConstantRange::isEmptySet() const {
105 return Lower == Upper && Lower == ConstantIntegral::getMinValue(getType());
108 /// isWrappedSet - Return true if this set wraps around the top of the range,
109 /// for example: [100, 8)
111 bool ConstantRange::isWrappedSet() const {
112 return (*(Constant*)Lower > *(Constant*)Upper)->getValue();
116 /// getSingleElement - If this set contains a single element, return it,
117 /// otherwise return null.
118 ConstantIntegral *ConstantRange::getSingleElement() const {
119 if (Upper == Next(Lower)) // Is it a single element range?
124 /// getSetSize - Return the number of elements in this set.
126 uint64_t ConstantRange::getSetSize() const {
127 if (isEmptySet()) return 0;
128 if (getType() == Type::BoolTy) {
129 if (Lower != Upper) // One of T or F in the set...
131 return 2; // Must be full set...
134 // Simply subtract the bounds...
135 Constant *Result = *(Constant*)Upper - *(Constant*)Lower;
136 assert(Result && "Subtraction of constant integers not implemented?");
137 return cast<ConstantInt>(Result)->getRawValue();
143 // intersect1Wrapped - This helper function is used to intersect two ranges when
144 // it is known that LHS is wrapped and RHS isn't.
146 static ConstantRange intersect1Wrapped(const ConstantRange &LHS,
147 const ConstantRange &RHS) {
148 assert(LHS.isWrappedSet() && !RHS.isWrappedSet());
150 // Check to see if we overlap on the Left side of RHS...
152 if ((*(Constant*)RHS.getLower() < *(Constant*)LHS.getUpper())->getValue()) {
153 // We do overlap on the left side of RHS, see if we overlap on the right of
155 if ((*(Constant*)RHS.getUpper() > *(Constant*)LHS.getLower())->getValue()) {
156 // Ok, the result overlaps on both the left and right sides. See if the
157 // resultant interval will be smaller if we wrap or not...
159 if (LHS.getSetSize() < RHS.getSetSize())
165 // No overlap on the right, just on the left.
166 return ConstantRange(RHS.getLower(), LHS.getUpper());
170 // We don't overlap on the left side of RHS, see if we overlap on the right
172 if ((*(Constant*)RHS.getUpper() > *(Constant*)LHS.getLower())->getValue()) {
174 return ConstantRange(LHS.getLower(), RHS.getUpper());
177 return ConstantRange(LHS.getType(), false);
182 static ConstantIntegral *Min(ConstantIntegral *A, ConstantIntegral *B) {
183 if ((*(Constant*)A < *(Constant*)B)->getValue())
187 static ConstantIntegral *Max(ConstantIntegral *A, ConstantIntegral *B) {
188 if ((*(Constant*)A > *(Constant*)B)->getValue())
194 /// intersect - Return the range that results from the intersection of this
195 /// range with another range.
197 ConstantRange ConstantRange::intersectWith(const ConstantRange &CR) const {
198 assert(getType() == CR.getType() && "ConstantRange types don't agree!");
199 // Handle common special cases
200 if (isEmptySet() || CR.isFullSet()) return *this;
201 if (isFullSet() || CR.isEmptySet()) return CR;
203 if (!isWrappedSet()) {
204 if (!CR.isWrappedSet()) {
205 ConstantIntegral *L = Max(Lower, CR.Lower);
206 ConstantIntegral *U = Min(Upper, CR.Upper);
208 if ((*L < *U)->getValue()) // If range isn't empty...
209 return ConstantRange(L, U);
211 return ConstantRange(getType(), false); // Otherwise, return empty set
213 return intersect1Wrapped(CR, *this);
214 } else { // We know "this" is wrapped...
215 if (!CR.isWrappedSet())
216 return intersect1Wrapped(*this, CR);
218 // Both ranges are wrapped...
219 ConstantIntegral *L = Max(Lower, CR.Lower);
220 ConstantIntegral *U = Min(Upper, CR.Upper);
221 return ConstantRange(L, U);
227 /// union - Return the range that results from the union of this range with
228 /// another range. The resultant range is guaranteed to include the elements of
229 /// both sets, but may contain more. For example, [3, 9) union [12,15) is [3,
230 /// 15), which includes 9, 10, and 11, which were not included in either set
233 ConstantRange ConstantRange::unionWith(const ConstantRange &CR) const {
234 assert(getType() == CR.getType() && "ConstantRange types don't agree!");
236 assert(0 && "Range union not implemented yet!");
241 /// print - Print out the bounds to a stream...
243 void ConstantRange::print(std::ostream &OS) const {
244 OS << "[" << Lower << "," << Upper << " )";
247 /// dump - Allow printing from a debugger easily...
249 void ConstantRange::dump() const {