Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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. #include <optional>
  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() = default;
  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.isZero() && One.isZero(); }
  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.isAllOnes();
  75.   }
  76.  
  77.   /// Returns true if value is all one bits.
  78.   bool isAllOnes() const {
  79.     assert(!hasConflict() && "KnownBits conflict!");
  80.     return One.isAllOnes();
  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.   /// Returns true if this value is known to be non-zero.
  102.   bool isNonZero() const { return !One.isZero(); }
  103.  
  104.   /// Returns true if this value is known to be positive.
  105.   bool isStrictlyPositive() const {
  106.     return Zero.isSignBitSet() && !One.isZero();
  107.   }
  108.  
  109.   /// Make this value negative.
  110.   void makeNegative() {
  111.     One.setSignBit();
  112.   }
  113.  
  114.   /// Make this value non-negative.
  115.   void makeNonNegative() {
  116.     Zero.setSignBit();
  117.   }
  118.  
  119.   /// Return the minimal unsigned value possible given these KnownBits.
  120.   APInt getMinValue() const {
  121.     // Assume that all bits that aren't known-ones are zeros.
  122.     return One;
  123.   }
  124.  
  125.   /// Return the minimal signed value possible given these KnownBits.
  126.   APInt getSignedMinValue() const {
  127.     // Assume that all bits that aren't known-ones are zeros.
  128.     APInt Min = One;
  129.     // Sign bit is unknown.
  130.     if (Zero.isSignBitClear())
  131.       Min.setSignBit();
  132.     return Min;
  133.   }
  134.  
  135.   /// Return the maximal unsigned value possible given these KnownBits.
  136.   APInt getMaxValue() const {
  137.     // Assume that all bits that aren't known-zeros are ones.
  138.     return ~Zero;
  139.   }
  140.  
  141.   /// Return the maximal signed value possible given these KnownBits.
  142.   APInt getSignedMaxValue() const {
  143.     // Assume that all bits that aren't known-zeros are ones.
  144.     APInt Max = ~Zero;
  145.     // Sign bit is unknown.
  146.     if (One.isSignBitClear())
  147.       Max.clearSignBit();
  148.     return Max;
  149.   }
  150.  
  151.   /// Return known bits for a truncation of the value we're tracking.
  152.   KnownBits trunc(unsigned BitWidth) const {
  153.     return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
  154.   }
  155.  
  156.   /// Return known bits for an "any" extension of the value we're tracking,
  157.   /// where we don't know anything about the extended bits.
  158.   KnownBits anyext(unsigned BitWidth) const {
  159.     return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
  160.   }
  161.  
  162.   /// Return known bits for a zero extension of the value we're tracking.
  163.   KnownBits zext(unsigned BitWidth) const {
  164.     unsigned OldBitWidth = getBitWidth();
  165.     APInt NewZero = Zero.zext(BitWidth);
  166.     NewZero.setBitsFrom(OldBitWidth);
  167.     return KnownBits(NewZero, One.zext(BitWidth));
  168.   }
  169.  
  170.   /// Return known bits for a sign extension of the value we're tracking.
  171.   KnownBits sext(unsigned BitWidth) const {
  172.     return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
  173.   }
  174.  
  175.   /// Return known bits for an "any" extension or truncation of the value we're
  176.   /// tracking.
  177.   KnownBits anyextOrTrunc(unsigned BitWidth) const {
  178.     if (BitWidth > getBitWidth())
  179.       return anyext(BitWidth);
  180.     if (BitWidth < getBitWidth())
  181.       return trunc(BitWidth);
  182.     return *this;
  183.   }
  184.  
  185.   /// Return known bits for a zero extension or truncation of the value we're
  186.   /// tracking.
  187.   KnownBits zextOrTrunc(unsigned BitWidth) const {
  188.     if (BitWidth > getBitWidth())
  189.       return zext(BitWidth);
  190.     if (BitWidth < getBitWidth())
  191.       return trunc(BitWidth);
  192.     return *this;
  193.   }
  194.  
  195.   /// Return known bits for a sign extension or truncation of the value we're
  196.   /// tracking.
  197.   KnownBits sextOrTrunc(unsigned BitWidth) const {
  198.     if (BitWidth > getBitWidth())
  199.       return sext(BitWidth);
  200.     if (BitWidth < getBitWidth())
  201.       return trunc(BitWidth);
  202.     return *this;
  203.   }
  204.  
  205.   /// Return known bits for a in-register sign extension of the value we're
  206.   /// tracking.
  207.   KnownBits sextInReg(unsigned SrcBitWidth) const;
  208.  
  209.   /// Insert the bits from a smaller known bits starting at bitPosition.
  210.   void insertBits(const KnownBits &SubBits, unsigned BitPosition) {
  211.     Zero.insertBits(SubBits.Zero, BitPosition);
  212.     One.insertBits(SubBits.One, BitPosition);
  213.   }
  214.  
  215.   /// Return a subset of the known bits from [bitPosition,bitPosition+numBits).
  216.   KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
  217.     return KnownBits(Zero.extractBits(NumBits, BitPosition),
  218.                      One.extractBits(NumBits, BitPosition));
  219.   }
  220.  
  221.   /// Concatenate the bits from \p Lo onto the bottom of *this.  This is
  222.   /// equivalent to:
  223.   ///   (this->zext(NewWidth) << Lo.getBitWidth()) | Lo.zext(NewWidth)
  224.   KnownBits concat(const KnownBits &Lo) const {
  225.     return KnownBits(Zero.concat(Lo.Zero), One.concat(Lo.One));
  226.   }
  227.  
  228.   /// Return KnownBits based on this, but updated given that the underlying
  229.   /// value is known to be greater than or equal to Val.
  230.   KnownBits makeGE(const APInt &Val) const;
  231.  
  232.   /// Returns the minimum number of trailing zero bits.
  233.   unsigned countMinTrailingZeros() const {
  234.     return Zero.countTrailingOnes();
  235.   }
  236.  
  237.   /// Returns the minimum number of trailing one bits.
  238.   unsigned countMinTrailingOnes() const {
  239.     return One.countTrailingOnes();
  240.   }
  241.  
  242.   /// Returns the minimum number of leading zero bits.
  243.   unsigned countMinLeadingZeros() const {
  244.     return Zero.countLeadingOnes();
  245.   }
  246.  
  247.   /// Returns the minimum number of leading one bits.
  248.   unsigned countMinLeadingOnes() const {
  249.     return One.countLeadingOnes();
  250.   }
  251.  
  252.   /// Returns the number of times the sign bit is replicated into the other
  253.   /// bits.
  254.   unsigned countMinSignBits() const {
  255.     if (isNonNegative())
  256.       return countMinLeadingZeros();
  257.     if (isNegative())
  258.       return countMinLeadingOnes();
  259.     // Every value has at least 1 sign bit.
  260.     return 1;
  261.   }
  262.  
  263.   /// Returns the maximum number of bits needed to represent all possible
  264.   /// signed values with these known bits. This is the inverse of the minimum
  265.   /// number of known sign bits. Examples for bitwidth 5:
  266.   /// 110?? --> 4
  267.   /// 0000? --> 2
  268.   unsigned countMaxSignificantBits() const {
  269.     return getBitWidth() - countMinSignBits() + 1;
  270.   }
  271.  
  272.   /// Returns the maximum number of trailing zero bits possible.
  273.   unsigned countMaxTrailingZeros() const {
  274.     return One.countTrailingZeros();
  275.   }
  276.  
  277.   /// Returns the maximum number of trailing one bits possible.
  278.   unsigned countMaxTrailingOnes() const {
  279.     return Zero.countTrailingZeros();
  280.   }
  281.  
  282.   /// Returns the maximum number of leading zero bits possible.
  283.   unsigned countMaxLeadingZeros() const {
  284.     return One.countLeadingZeros();
  285.   }
  286.  
  287.   /// Returns the maximum number of leading one bits possible.
  288.   unsigned countMaxLeadingOnes() const {
  289.     return Zero.countLeadingZeros();
  290.   }
  291.  
  292.   /// Returns the number of bits known to be one.
  293.   unsigned countMinPopulation() const {
  294.     return One.countPopulation();
  295.   }
  296.  
  297.   /// Returns the maximum number of bits that could be one.
  298.   unsigned countMaxPopulation() const {
  299.     return getBitWidth() - Zero.countPopulation();
  300.   }
  301.  
  302.   /// Returns the maximum number of bits needed to represent all possible
  303.   /// unsigned values with these known bits. This is the inverse of the
  304.   /// minimum number of leading zeros.
  305.   unsigned countMaxActiveBits() const {
  306.     return getBitWidth() - countMinLeadingZeros();
  307.   }
  308.  
  309.   /// Create known bits from a known constant.
  310.   static KnownBits makeConstant(const APInt &C) {
  311.     return KnownBits(~C, C);
  312.   }
  313.  
  314.   /// Compute known bits common to LHS and RHS.
  315.   static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) {
  316.     return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One);
  317.   }
  318.  
  319.   /// Return true if LHS and RHS have no common bits set.
  320.   static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
  321.     return (LHS.Zero | RHS.Zero).isAllOnes();
  322.   }
  323.  
  324.   /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
  325.   static KnownBits computeForAddCarry(
  326.       const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
  327.  
  328.   /// Compute known bits resulting from adding LHS and RHS.
  329.   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
  330.                                     KnownBits RHS);
  331.  
  332.   /// Compute known bits resulting from multiplying LHS and RHS.
  333.   static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS,
  334.                        bool NoUndefSelfMultiply = false);
  335.  
  336.   /// Compute known bits from sign-extended multiply-hi.
  337.   static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
  338.  
  339.   /// Compute known bits from zero-extended multiply-hi.
  340.   static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
  341.  
  342.   /// Compute known bits for udiv(LHS, RHS).
  343.   static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
  344.  
  345.   /// Compute known bits for urem(LHS, RHS).
  346.   static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
  347.  
  348.   /// Compute known bits for srem(LHS, RHS).
  349.   static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);
  350.  
  351.   /// Compute known bits for umax(LHS, RHS).
  352.   static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
  353.  
  354.   /// Compute known bits for umin(LHS, RHS).
  355.   static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
  356.  
  357.   /// Compute known bits for smax(LHS, RHS).
  358.   static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
  359.  
  360.   /// Compute known bits for smin(LHS, RHS).
  361.   static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
  362.  
  363.   /// Compute known bits for shl(LHS, RHS).
  364.   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
  365.   static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS);
  366.  
  367.   /// Compute known bits for lshr(LHS, RHS).
  368.   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
  369.   static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS);
  370.  
  371.   /// Compute known bits for ashr(LHS, RHS).
  372.   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
  373.   static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS);
  374.  
  375.   /// Determine if these known bits always give the same ICMP_EQ result.
  376.   static std::optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS);
  377.  
  378.   /// Determine if these known bits always give the same ICMP_NE result.
  379.   static std::optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS);
  380.  
  381.   /// Determine if these known bits always give the same ICMP_UGT result.
  382.   static std::optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS);
  383.  
  384.   /// Determine if these known bits always give the same ICMP_UGE result.
  385.   static std::optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS);
  386.  
  387.   /// Determine if these known bits always give the same ICMP_ULT result.
  388.   static std::optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS);
  389.  
  390.   /// Determine if these known bits always give the same ICMP_ULE result.
  391.   static std::optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS);
  392.  
  393.   /// Determine if these known bits always give the same ICMP_SGT result.
  394.   static std::optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS);
  395.  
  396.   /// Determine if these known bits always give the same ICMP_SGE result.
  397.   static std::optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS);
  398.  
  399.   /// Determine if these known bits always give the same ICMP_SLT result.
  400.   static std::optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS);
  401.  
  402.   /// Determine if these known bits always give the same ICMP_SLE result.
  403.   static std::optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS);
  404.  
  405.   /// Update known bits based on ANDing with RHS.
  406.   KnownBits &operator&=(const KnownBits &RHS);
  407.  
  408.   /// Update known bits based on ORing with RHS.
  409.   KnownBits &operator|=(const KnownBits &RHS);
  410.  
  411.   /// Update known bits based on XORing with RHS.
  412.   KnownBits &operator^=(const KnownBits &RHS);
  413.  
  414.   /// Compute known bits for the absolute value.
  415.   KnownBits abs(bool IntMinIsPoison = false) const;
  416.  
  417.   KnownBits byteSwap() const {
  418.     return KnownBits(Zero.byteSwap(), One.byteSwap());
  419.   }
  420.  
  421.   KnownBits reverseBits() const {
  422.     return KnownBits(Zero.reverseBits(), One.reverseBits());
  423.   }
  424.  
  425.   bool operator==(const KnownBits &Other) const {
  426.     return Zero == Other.Zero && One == Other.One;
  427.   }
  428.  
  429.   bool operator!=(const KnownBits &Other) const { return !(*this == Other); }
  430.  
  431.   void print(raw_ostream &OS) const;
  432.   void dump() const;
  433. };
  434.  
  435. inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
  436.   LHS &= RHS;
  437.   return LHS;
  438. }
  439.  
  440. inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
  441.   RHS &= LHS;
  442.   return std::move(RHS);
  443. }
  444.  
  445. inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
  446.   LHS |= RHS;
  447.   return LHS;
  448. }
  449.  
  450. inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
  451.   RHS |= LHS;
  452.   return std::move(RHS);
  453. }
  454.  
  455. inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
  456.   LHS ^= RHS;
  457.   return LHS;
  458. }
  459.  
  460. inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
  461.   RHS ^= LHS;
  462.   return std::move(RHS);
  463. }
  464.  
  465. } // end namespace llvm
  466.  
  467. #endif
  468.