Home | History | Annotate | Download | only in Support 
      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
    203