contrib/llvm/include/llvm/Support/KnownBits.h

   1 //===- llvm/Support/KnownBits.h - Stores known zeros/ones -------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains a class for representing known zeros and ones used by
  11 // computeKnownBits.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_SUPPORT_KNOWNBITS_H
  16 #define LLVM_SUPPORT_KNOWNBITS_H
  17
  18 #include "llvm/ADT/APInt.h"
  19
  20 namespace llvm {
  21
  22 // Struct for tracking the known zeros and ones of a value.
  23 struct KnownBits {
  24   APInt Zero;
  25   APInt One;
  26
  27 private:
  28   // Internal constructor for creating a KnownBits from two APInts.
  29   KnownBits(APInt Zero, APInt One)
  30       : Zero(std::move(Zero)), One(std::move(One)) {}
  31
  32 public:
  33   // Default construct Zero and One.
  34   KnownBits() {}
  35
  36   /// Create a known bits object of BitWidth bits initialized to unknown.
  37   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
  38
  39   /// Get the bit width of this value.
  40   unsigned getBitWidth() const {
  41     assert(Zero.getBitWidth() == One.getBitWidth() &&
  42            "Zero and One should have the same width!");
  43     return Zero.getBitWidth();
  44   }
  45
  46   /// Returns true if there is conflicting information.
  47   bool hasConflict() const { return Zero.intersects(One); }
  48
  49   /// Returns true if we know the value of all bits.
  50   bool isConstant() const {
  51     assert(!hasConflict() && "KnownBits conflict!");
  52     return Zero.countPopulation() + One.countPopulation() == getBitWidth();
  53   }
  54
  55   /// Returns the value when all bits have a known value. This just returns One
  56   /// with a protective assertion.
  57   const APInt &getConstant() const {
  58     assert(isConstant() && "Can only get value when all bits are known");
  59     return One;
  60   }
  61
  62   /// Returns true if we don't know any bits.
  63   bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); }
  64
  65   /// Resets the known state of all bits.
  66   void resetAll() {
  67     Zero.clearAllBits();
  68     One.clearAllBits();
  69   }
  70
  71   /// Returns true if value is all zero.
  72   bool isZero() const {
  73     assert(!hasConflict() && "KnownBits conflict!");
  74     return Zero.isAllOnesValue();
  75   }
  76
  77   /// Returns true if value is all one bits.
  78   bool isAllOnes() const {
  79     assert(!hasConflict() && "KnownBits conflict!");
  80     return One.isAllOnesValue();
  81   }
  82
  83   /// Make all bits known to be zero and discard any previous information.
  84   void setAllZero() {
  85     Zero.setAllBits();
  86     One.clearAllBits();
  87   }
  88
  89   /// Make all bits known to be one and discard any previous information.
  90   void setAllOnes() {
  91     Zero.clearAllBits();
  92     One.setAllBits();
  93   }
  94
  95   /// Returns true if this value is known to be negative.
  96   bool isNegative() const { return One.isSignBitSet(); }
  97
  98   /// Returns true if this value is known to be non-negative.
  99   bool isNonNegative() const { return Zero.isSignBitSet(); }
 100
 101   /// Make this value negative.
 102   void makeNegative() {
 103     assert(!isNonNegative() && "Can't make a non-negative value negative");
 104     One.setSignBit();
 105   }
 106
 107   /// Make this value negative.
 108   void makeNonNegative() {
 109     assert(!isNegative() && "Can't make a negative value non-negative");
 110     Zero.setSignBit();
 111   }
 112
 113   /// Truncate the underlying known Zero and One bits. This is equivalent
 114   /// to truncating the value we're tracking.
 115   KnownBits trunc(unsigned BitWidth) {
 116     return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
 117   }
 118
 119   /// Zero extends the underlying known Zero and One bits. This is equivalent
 120   /// to zero extending the value we're tracking.
 121   KnownBits zext(unsigned BitWidth) {
 122     return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
 123   }
 124
 125   /// Sign extends the underlying known Zero and One bits. This is equivalent
 126   /// to sign extending the value we're tracking.
 127   KnownBits sext(unsigned BitWidth) {
 128     return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
 129   }
 130
 131   /// Zero extends or truncates the underlying known Zero and One bits. This is
 132   /// equivalent to zero extending or truncating the value we're tracking.
 133   KnownBits zextOrTrunc(unsigned BitWidth) {
 134     return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
 135   }
 136
 137   /// Returns the minimum number of trailing zero bits.
 138   unsigned countMinTrailingZeros() const {
 139     return Zero.countTrailingOnes();
 140   }
 141
 142   /// Returns the minimum number of trailing one bits.
 143   unsigned countMinTrailingOnes() const {
 144     return One.countTrailingOnes();
 145   }
 146
 147   /// Returns the minimum number of leading zero bits.
 148   unsigned countMinLeadingZeros() const {
 149     return Zero.countLeadingOnes();
 150   }
 151
 152   /// Returns the minimum number of leading one bits.
 153   unsigned countMinLeadingOnes() const {
 154     return One.countLeadingOnes();
 155   }
 156
 157   /// Returns the number of times the sign bit is replicated into the other
 158   /// bits.
 159   unsigned countMinSignBits() const {
 160     if (isNonNegative())
 161       return countMinLeadingZeros();
 162     if (isNegative())
 163       return countMinLeadingOnes();
 164     return 0;
 165   }
 166
 167   /// Returns the maximum number of trailing zero bits possible.
 168   unsigned countMaxTrailingZeros() const {
 169     return One.countTrailingZeros();
 170   }
 171
 172   /// Returns the maximum number of trailing one bits possible.
 173   unsigned countMaxTrailingOnes() const {
 174     return Zero.countTrailingZeros();
 175   }
 176
 177   /// Returns the maximum number of leading zero bits possible.
 178   unsigned countMaxLeadingZeros() const {
 179     return One.countLeadingZeros();
 180   }
 181
 182   /// Returns the maximum number of leading one bits possible.
 183   unsigned countMaxLeadingOnes() const {
 184     return Zero.countLeadingZeros();
 185   }
 186
 187   /// Returns the number of bits known to be one.
 188   unsigned countMinPopulation() const {
 189     return One.countPopulation();
 190   }
 191
 192   /// Returns the maximum number of bits that could be one.
 193   unsigned countMaxPopulation() const {
 194     return getBitWidth() - Zero.countPopulation();
 195   }
 196
 197   /// Compute known bits resulting from adding LHS and RHS.
 198   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
 199                                     KnownBits RHS);
 200 };
 201
 202 } // end namespace llvm
 203
 204 #endif