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