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     One.setSignBit();
 104   }
 105
 106   /// Make this value non-negative.
 107   void makeNonNegative() {
 108     Zero.setSignBit();
 109   }
 110
 111   /// Truncate the underlying known Zero and One bits. This is equivalent
 112   /// to truncating the value we're tracking.
 113   KnownBits trunc(unsigned BitWidth) {
 114     return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
 115   }
 116
 117   /// Zero extends the underlying known Zero and One bits. This is equivalent
 118   /// to zero extending the value we're tracking.
 119   KnownBits zext(unsigned BitWidth) {
 120     return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
 121   }
 122
 123   /// Sign extends the underlying known Zero and One bits. This is equivalent
 124   /// to sign extending the value we're tracking.
 125   KnownBits sext(unsigned BitWidth) {
 126     return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
 127   }
 128
 129   /// Zero extends or truncates the underlying known Zero and One bits. This is
 130   /// equivalent to zero extending or truncating the value we're tracking.
 131   KnownBits zextOrTrunc(unsigned BitWidth) {
 132     return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
 133   }
 134
 135   /// Returns the minimum number of trailing zero bits.
 136   unsigned countMinTrailingZeros() const {
 137     return Zero.countTrailingOnes();
 138   }
 139
 140   /// Returns the minimum number of trailing one bits.
 141   unsigned countMinTrailingOnes() const {
 142     return One.countTrailingOnes();
 143   }
 144
 145   /// Returns the minimum number of leading zero bits.
 146   unsigned countMinLeadingZeros() const {
 147     return Zero.countLeadingOnes();
 148   }
 149
 150   /// Returns the minimum number of leading one bits.
 151   unsigned countMinLeadingOnes() const {
 152     return One.countLeadingOnes();
 153   }
 154
 155   /// Returns the number of times the sign bit is replicated into the other
 156   /// bits.
 157   unsigned countMinSignBits() const {
 158     if (isNonNegative())
 159       return countMinLeadingZeros();
 160     if (isNegative())
 161       return countMinLeadingOnes();
 162     return 0;
 163   }
 164
 165   /// Returns the maximum number of trailing zero bits possible.
 166   unsigned countMaxTrailingZeros() const {
 167     return One.countTrailingZeros();
 168   }
 169
 170   /// Returns the maximum number of trailing one bits possible.
 171   unsigned countMaxTrailingOnes() const {
 172     return Zero.countTrailingZeros();
 173   }
 174
 175   /// Returns the maximum number of leading zero bits possible.
 176   unsigned countMaxLeadingZeros() const {
 177     return One.countLeadingZeros();
 178   }
 179
 180   /// Returns the maximum number of leading one bits possible.
 181   unsigned countMaxLeadingOnes() const {
 182     return Zero.countLeadingZeros();
 183   }
 184
 185   /// Returns the number of bits known to be one.
 186   unsigned countMinPopulation() const {
 187     return One.countPopulation();
 188   }
 189
 190   /// Returns the maximum number of bits that could be one.
 191   unsigned countMaxPopulation() const {
 192     return getBitWidth() - Zero.countPopulation();
 193   }
 194
 195   /// Compute known bits resulting from adding LHS and RHS.
 196   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
 197                                     KnownBits RHS);
 198 };
 199
 200 } // end namespace llvm
 201
 202 #endif