gcc/d/dmd/intrange.h

   1
   2 /* Compiler implementation of the D programming language
   3  * Copyright (C) 1999-2018 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.
  31     SignExtendedNumber() {}
  32
  33     /// Create a sign-extended number from an unsigned 64-bit number.
  34     SignExtendedNumber(uinteger_t value_)
  35         : value(value_), negative(false) {}
  36     /// Create a sign-extended number from the lower 64-bit and the sign bit.
  37     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();
  50     static SignExtendedNumber min() { return SignExtendedNumber(0, true); }
  51
  52     /// Check if the sign-extended number is minimum or zero.
  53     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.
 101     IntRange() {}
 102
 103     /// Create a range consisting of a single number.
 104     IntRange(const SignExtendedNumber& a)
 105         : imin(a), imax(a) {}
 106     /// Create a range with the lower and upper bounds.
 107     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 };