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