xref: /netbsd-src/external/gpl3/gcc.old/dist/gcc/d/dmd/intrange.h (revision 627f7eb200a4419d89b531d55fccd2ee3ffdcde0)
1 
2 /* Compiler implementation of the D programming language
3  * Copyright (C) 1999-2019 by The D Language Foundation, All Rights Reserved
4  * written by KennyTM
5  * http://www.digitalmars.com
6  * Distributed under the Boost Software License, Version 1.0.
7  * http://www.boost.org/LICENSE_1_0.txt
8  * https://github.com/dlang/dmd/blob/master/src/intrange.h
9  */
10 
11 #pragma once
12 
13 #include "globals.h"   // for uinteger_t
14 class Type;
15 class Expression;
16 
17 /**
18 This class represents a "sign-extended number", i.e. a 65-bit number, which can
19 represent all built-in integer types in D. This class is mainly used for
20 performing value-range propagation only, therefore all arithmetic are done with
21 saturation, not wrapping as usual.
22 */
23 struct SignExtendedNumber
24 {
25     /// The lower 64-bit of the number.
26     uinteger_t value;
27     /// The sign (i.e. the most significant bit) of the number.
28     bool negative;
29 
30     /// Create an uninitialized sign-extended number.
SignExtendedNumberSignExtendedNumber31     SignExtendedNumber() {}
32 
33     /// Create a sign-extended number from an unsigned 64-bit number.
SignExtendedNumberSignExtendedNumber34     SignExtendedNumber(uinteger_t value_)
35         : value(value_), negative(false) {}
36     /// Create a sign-extended number from the lower 64-bit and the sign bit.
SignExtendedNumberSignExtendedNumber37     SignExtendedNumber(uinteger_t value_, bool negative_)
38         : value(value_), negative(negative_) {}
39 
40     /// Create a sign-extended number from a signed 64-bit number.
41     static SignExtendedNumber fromInteger(uinteger_t value_);
42 
43     /// Get the minimum or maximum value of a sign-extended number.
44     static SignExtendedNumber extreme(bool minimum);
45 
46     // These names probably shouldn't be used anyway, as they are common macros
47 #undef max
48 #undef min
49     static SignExtendedNumber max();
minSignExtendedNumber50     static SignExtendedNumber min() { return SignExtendedNumber(0, true); }
51 
52     /// Check if the sign-extended number is minimum or zero.
isMinimumSignExtendedNumber53     bool isMinimum() const { return negative && value == 0; }
54 
55     /// Compare two sign-extended number.
56     bool operator==(const SignExtendedNumber&) const;
57     bool operator!=(const SignExtendedNumber& a) const { return !(*this == a); }
58     bool operator<(const SignExtendedNumber&) const;
59     bool operator>(const SignExtendedNumber& a) const { return a < *this; }
60     bool operator<=(const SignExtendedNumber& a) const { return !(a < *this); }
61     bool operator>=(const SignExtendedNumber& a) const { return !(*this < a); }
62 
63     /// Increase the sign-extended number by 1 (saturated).
64     SignExtendedNumber& operator++();
65     /// Compute the saturated complement of a sign-extended number.
66     SignExtendedNumber operator~() const;
67     /// Compute the saturated negation of a sign-extended number.
68     SignExtendedNumber operator-() const;
69 
70     /// Compute the saturated binary and of two sign-extended number.
71     SignExtendedNumber operator&(const SignExtendedNumber&) const;
72     /// Compute the saturated binary or of two sign-extended number.
73     SignExtendedNumber operator|(const SignExtendedNumber&) const;
74     /// Compute the saturated binary xor of two sign-extended number.
75     SignExtendedNumber operator^(const SignExtendedNumber&) const;
76     /// Compute the saturated sum of two sign-extended number.
77     SignExtendedNumber operator+(const SignExtendedNumber&) const;
78     /// Compute the saturated difference of two sign-extended number.
79     SignExtendedNumber operator-(const SignExtendedNumber&) const;
80     /// Compute the saturated product of two sign-extended number.
81     SignExtendedNumber operator*(const SignExtendedNumber&) const;
82     /// Compute the saturated quotient of two sign-extended number.
83     SignExtendedNumber operator/(const SignExtendedNumber&) const;
84     /// Compute the saturated modulus of two sign-extended number.
85     SignExtendedNumber operator%(const SignExtendedNumber&) const;
86 
87     /// Compute the saturated shifts of two sign-extended number.
88     SignExtendedNumber operator<<(const SignExtendedNumber&) const;
89     SignExtendedNumber operator>>(const SignExtendedNumber&) const;
90 };
91 
92 /**
93 This class represents a range of integers, denoted by its lower and upper bounds
94 (inclusive).
95 */
96 struct IntRange
97 {
98     SignExtendedNumber imin, imax;
99 
100     /// Create an uninitialized range.
IntRangeIntRange101     IntRange() {}
102 
103     /// Create a range consisting of a single number.
IntRangeIntRange104     IntRange(const SignExtendedNumber& a)
105         : imin(a), imax(a) {}
106     /// Create a range with the lower and upper bounds.
IntRangeIntRange107     IntRange(const SignExtendedNumber& lower, const SignExtendedNumber& upper)
108         : imin(lower), imax(upper) {}
109 
110     /// Create the tightest range containing all valid integers in the specified
111     /// type.
112     static IntRange fromType(Type *type);
113     /// Create the tightest range containing all valid integers in the type with
114     /// a forced signedness.
115     static IntRange fromType(Type *type, bool isUnsigned);
116 
117 
118     /// Create the tightest range containing all specified numbers.
119     static IntRange fromNumbers2(const SignExtendedNumber numbers[2]);
120     static IntRange fromNumbers4(const SignExtendedNumber numbers[4]);
121 
122     /// Create the widest range possible.
123     static IntRange widest();
124 
125     /// Cast the integer range to a signed type with the given size mask.
126     IntRange& castSigned(uinteger_t mask);
127     /// Cast the integer range to an unsigned type with the given size mask.
128     IntRange& castUnsigned(uinteger_t mask);
129     /// Cast the integer range to the dchar type.
130     IntRange& castDchar();
131 
132     /// Cast the integer range to a specific type.
133     IntRange& cast(Type *type);
134     /// Cast the integer range to a specific type, forcing it to be unsigned.
135     IntRange& castUnsigned(Type *type);
136 
137     /// Check if this range contains another range.
138     bool contains(const IntRange& a) const;
139 
140     /// Check if this range contains 0.
141     bool containsZero() const;
142 
143     /// Compute the range of the negated absolute values of the original range.
144     IntRange absNeg() const;
145 
146     /// Compute the union of two ranges.
147     IntRange unionWith(const IntRange& other) const;
148     void unionOrAssign(const IntRange& other, bool& union_);
149 
150     /// Dump the content of the integer range to the console.
151     const IntRange& dump(const char* funcName, Expression *e) const;
152 
153     /// Split the range into two nonnegative- and negative-only subintervals.
154     void splitBySign(IntRange& negRange, bool& hasNegRange,
155                      IntRange& nonNegRange, bool& hasNonNegRange) const;
156 
157     /// Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
158     /// https://github.com/tgehr/d-compiler/blob/master/vrange.d
159     static SignExtendedNumber maxOr(const IntRange&, const IntRange&);
160     static SignExtendedNumber minOr(const IntRange&, const IntRange&);
161     static SignExtendedNumber maxAnd(const IntRange&, const IntRange&);
162     static SignExtendedNumber minAnd(const IntRange&, const IntRange&);
163     static void swap(IntRange&, IntRange&);
164 
165     IntRange operator~() const;
166     IntRange operator-() const;
167     IntRange operator&(const IntRange&) const;
168     IntRange operator|(const IntRange&) const;
169     IntRange operator^(const IntRange&) const;
170     IntRange operator+(const IntRange&) const;
171     IntRange operator-(const IntRange&) const;
172     IntRange operator*(const IntRange&) const;
173     IntRange operator/(const IntRange&) const;
174     IntRange operator%(const IntRange&) const;
175     IntRange operator<<(const IntRange&) const;
176     IntRange operator>>(const IntRange&) const;
177 };
178