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

   1 //===- llvm/Support/KnownBits.h - Stores known zeros/ones -------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file contains a class for representing known zeros and ones used by
  10 // computeKnownBits.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_SUPPORT_KNOWNBITS_H
  15 #define LLVM_SUPPORT_KNOWNBITS_H
  16
  17 #include "llvm/ADT/APInt.h"
  18
  19 namespace llvm {
  20
  21 // Struct for tracking the known zeros and ones of a value.
  22 struct KnownBits {
  23   APInt Zero;
  24   APInt One;
  25
  26 private:
  27   // Internal constructor for creating a KnownBits from two APInts.
  28   KnownBits(APInt Zero, APInt One)
  29       : Zero(std::move(Zero)), One(std::move(One)) {}
  30
  31 public:
  32   // Default construct Zero and One.
  33   KnownBits() {}
  34
  35   /// Create a known bits object of BitWidth bits initialized to unknown.
  36   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
  37
  38   /// Get the bit width of this value.
  39   unsigned getBitWidth() const {
  40     assert(Zero.getBitWidth() == One.getBitWidth() &&
  41            "Zero and One should have the same width!");
  42     return Zero.getBitWidth();
  43   }
  44
  45   /// Returns true if there is conflicting information.
  46   bool hasConflict() const { return Zero.intersects(One); }
  47
  48   /// Returns true if we know the value of all bits.
  49   bool isConstant() const {
  50     assert(!hasConflict() && "KnownBits conflict!");
  51     return Zero.countPopulation() + One.countPopulation() == getBitWidth();
  52   }
  53
  54   /// Returns the value when all bits have a known value. This just returns One
  55   /// with a protective assertion.
  56   const APInt &getConstant() const {
  57     assert(isConstant() && "Can only get value when all bits are known");
  58     return One;
  59   }
  60
  61   /// Returns true if we don't know any bits.
  62   bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); }
  63
  64   /// Resets the known state of all bits.
  65   void resetAll() {
  66     Zero.clearAllBits();
  67     One.clearAllBits();
  68   }
  69
  70   /// Returns true if value is all zero.
  71   bool isZero() const {
  72     assert(!hasConflict() && "KnownBits conflict!");
  73     return Zero.isAllOnesValue();
  74   }
  75
  76   /// Returns true if value is all one bits.
  77   bool isAllOnes() const {
  78     assert(!hasConflict() && "KnownBits conflict!");
  79     return One.isAllOnesValue();
  80   }
  81
  82   /// Make all bits known to be zero and discard any previous information.
  83   void setAllZero() {
  84     Zero.setAllBits();
  85     One.clearAllBits();
  86   }
  87
  88   /// Make all bits known to be one and discard any previous information.
  89   void setAllOnes() {
  90     Zero.clearAllBits();
  91     One.setAllBits();
  92   }
  93
  94   /// Returns true if this value is known to be negative.
  95   bool isNegative() const { return One.isSignBitSet(); }
  96
  97   /// Returns true if this value is known to be non-negative.
  98   bool isNonNegative() const { return Zero.isSignBitSet(); }
  99
 100   /// Returns true if this value is known to be positive.
 101   bool isStrictlyPositive() const { return Zero.isSignBitSet() && !One.isNullValue(); }
 102
 103   /// Make this value negative.
 104   void makeNegative() {
 105     One.setSignBit();
 106   }
 107
 108   /// Make this value non-negative.
 109   void makeNonNegative() {
 110     Zero.setSignBit();
 111   }
 112
 113   /// Return the minimal value possible given these KnownBits.
 114   APInt getMinValue() const {
 115     // Assume that all bits that aren't known-ones are zeros.
 116     return One;
 117   }
 118
 119   /// Return the maximal value possible given these KnownBits.
 120   APInt getMaxValue() const {
 121     // Assume that all bits that aren't known-zeros are ones.
 122     return ~Zero;
 123   }
 124
 125   /// Return known bits for a truncation of the value we're tracking.
 126   KnownBits trunc(unsigned BitWidth) const {
 127     return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
 128   }
 129
 130   /// Return known bits for an "any" extension of the value we're tracking,
 131   /// where we don't know anything about the extended bits.
 132   KnownBits anyext(unsigned BitWidth) const {
 133     return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
 134   }
 135
 136   /// Return known bits for a zero extension of the value we're tracking.
 137   KnownBits zext(unsigned BitWidth) const {
 138     unsigned OldBitWidth = getBitWidth();
 139     APInt NewZero = Zero.zext(BitWidth);
 140     NewZero.setBitsFrom(OldBitWidth);
 141     return KnownBits(NewZero, One.zext(BitWidth));
 142   }
 143
 144   /// Return known bits for a sign extension of the value we're tracking.
 145   KnownBits sext(unsigned BitWidth) const {
 146     return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
 147   }
 148
 149   /// Return known bits for an "any" extension or truncation of the value we're
 150   /// tracking.
 151   KnownBits anyextOrTrunc(unsigned BitWidth) const {
 152     if (BitWidth > getBitWidth())
 153       return anyext(BitWidth);
 154     if (BitWidth < getBitWidth())
 155       return trunc(BitWidth);
 156     return *this;
 157   }
 158
 159   /// Return known bits for a zero extension or truncation of the value we're
 160   /// tracking.
 161   KnownBits zextOrTrunc(unsigned BitWidth) const {
 162     if (BitWidth > getBitWidth())
 163       return zext(BitWidth);
 164     if (BitWidth < getBitWidth())
 165       return trunc(BitWidth);
 166     return *this;
 167   }
 168
 169   /// Return a KnownBits with the extracted bits
 170   /// [bitPosition,bitPosition+numBits).
 171   KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
 172     return KnownBits(Zero.extractBits(NumBits, BitPosition),
 173                      One.extractBits(NumBits, BitPosition));
 174   }
 175
 176   /// Returns the minimum number of trailing zero bits.
 177   unsigned countMinTrailingZeros() const {
 178     return Zero.countTrailingOnes();
 179   }
 180
 181   /// Returns the minimum number of trailing one bits.
 182   unsigned countMinTrailingOnes() const {
 183     return One.countTrailingOnes();
 184   }
 185
 186   /// Returns the minimum number of leading zero bits.
 187   unsigned countMinLeadingZeros() const {
 188     return Zero.countLeadingOnes();
 189   }
 190
 191   /// Returns the minimum number of leading one bits.
 192   unsigned countMinLeadingOnes() const {
 193     return One.countLeadingOnes();
 194   }
 195
 196   /// Returns the number of times the sign bit is replicated into the other
 197   /// bits.
 198   unsigned countMinSignBits() const {
 199     if (isNonNegative())
 200       return countMinLeadingZeros();
 201     if (isNegative())
 202       return countMinLeadingOnes();
 203     return 0;
 204   }
 205
 206   /// Returns the maximum number of trailing zero bits possible.
 207   unsigned countMaxTrailingZeros() const {
 208     return One.countTrailingZeros();
 209   }
 210
 211   /// Returns the maximum number of trailing one bits possible.
 212   unsigned countMaxTrailingOnes() const {
 213     return Zero.countTrailingZeros();
 214   }
 215
 216   /// Returns the maximum number of leading zero bits possible.
 217   unsigned countMaxLeadingZeros() const {
 218     return One.countLeadingZeros();
 219   }
 220
 221   /// Returns the maximum number of leading one bits possible.
 222   unsigned countMaxLeadingOnes() const {
 223     return Zero.countLeadingZeros();
 224   }
 225
 226   /// Returns the number of bits known to be one.
 227   unsigned countMinPopulation() const {
 228     return One.countPopulation();
 229   }
 230
 231   /// Returns the maximum number of bits that could be one.
 232   unsigned countMaxPopulation() const {
 233     return getBitWidth() - Zero.countPopulation();
 234   }
 235
 236   /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
 237   static KnownBits computeForAddCarry(
 238       const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
 239
 240   /// Compute known bits resulting from adding LHS and RHS.
 241   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
 242                                     KnownBits RHS);
 243
 244   /// Update known bits based on ANDing with RHS.
 245   KnownBits &operator&=(const KnownBits &RHS);
 246
 247   /// Update known bits based on ORing with RHS.
 248   KnownBits &operator|=(const KnownBits &RHS);
 249
 250   /// Update known bits based on XORing with RHS.
 251   KnownBits &operator^=(const KnownBits &RHS);
 252 };
 253
 254 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
 255   LHS &= RHS;
 256   return LHS;
 257 }
 258
 259 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
 260   RHS &= LHS;
 261   return std::move(RHS);
 262 }
 263
 264 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
 265   LHS |= RHS;
 266   return LHS;
 267 }
 268
 269 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
 270   RHS |= LHS;
 271   return std::move(RHS);
 272 }
 273
 274 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
 275   LHS ^= RHS;
 276   return LHS;
 277 }
 278
 279 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
 280   RHS ^= LHS;
 281   return std::move(RHS);
 282 }
 283
 284 } // end namespace llvm
 285
 286 #endif