[ValueTracking] Begin adding some useful methods to the proposed KnownBits struct

[craig.topper]

Summary

This patch adds some plausible methods to the KnownBits struct from D32376.

I'm not married to the names for hasConflict, isValid, isComplete, and getValue.

hasConflict and isValid are opposites of each other, but I've added both because isValid is going to be primarily used in asserts that verify no conflicts. hasConflict will be used in a couple places in places where we explicitly check for conflicts today like in the assume handling code.

I've intentionally avoided calling isComplete something like allBitsKnown because the struct itself is usually a variable called Known so it would read repetitively.

[RKSimon]

include/llvm/Support/KnownBits.h

10

This should be in D32376

[RKSimon]

I realise there are plenty of possible helpers but zextOrTrunc and clearAllBits would definitely be useful.

include/llvm/Support/KnownBits.h

51

<bikeshed>Not too sure about isComplete - bit too similar to isValid?</bikeshed>

If isComplete and getValue are likely to always be used together is it worth merging them into a single method:

bool isCompleteValue(APInt &) ?

[craig.topper]

I definitely meant to add clearAllBits.

include/llvm/Support/KnownBits.h

51

I made it two separate methods because it's often going to be used like

if (Known.isComplete())
  return ConstantInt::get(Tyep, Known.getValue());

53

I'm slightly concerned that doing the population count in the single word APInt case on pre-Westmere CPUs(no harware popcnt) is worse than doing the OR and checking for all 1s. But in the multiword case the OR needs a temporary APInt so this may be better.

Considering adding something like isUnionFull to APInt to do the OR in place on each word without the allocation like intersects and isSubsetOf.

[craig.topper]

Maybe a better name for isComplete/getValue would be isConstant and getConstant?

[RKSimon]

In D32508#740518, @craig.topper wrote:

Maybe a better name for isComplete/getValue would be isConstant and getConstant?

Makes sense to me.

include/llvm/Support/KnownBits.h

53

Happy to go with this for now. APInt::isUnionFull makes sense - it complements the existing intersection/subset tests - but that can be a future change.

[spatel]

In D32508#740518, @craig.topper wrote:

Maybe a better name for isComplete/getValue would be isConstant and getConstant?

isConstant/getConstant are better IMO. Not sure if it would cause 'known' overload in the user code, but could remove more ambiguity with: allBitsKnown/getKnownConstant ?

[craig.topper]

My implementation of sext/zext/trunc is busted in this patch. They need to create a new object and should return the new object.

[RKSimon]

Is this patch still relevant?

include/llvm/Support/KnownBits.h

 //===- llvm/Support/KnownBits.h - Stores known zeros/ones -------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
-// This file contains a class for reprsenting known zeros and ones used by
+// This file contains a class for representing known zeros and ones used by
 // computeKnownBits.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_KNOWNBITS_H
 #define LLVM_SUPPORT_KNOWNBITS_H
 
 #include "llvm/ADT/APInt.h"
 
 namespace llvm {
 
-// For now this is a simple wrapper around two APInts.
+// Struct for managing the known zeros and ones of a value.
 struct KnownBits {
   APInt Zero;
   APInt One;
 
   // Default construct Zero and One.
   KnownBits() {}
 
   /// Create a known bits object of BitWidth bits initialized to unknown.
   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
 
   /// Get the bit width of this value.
   unsigned getBitWidth() const {
     assert(Zero.getBitWidth() == One.getBitWidth() &&
            "Zero and One should have the same width!");
     return Zero.getBitWidth();
   }
+
+  /// Returns true if there is conflicting information.
+  bool hasConflict() const { return Zero.intersects(One); }
+
+  /// Returns true if there is no conflicting information.
+  bool isValid() const {
+    assert(Zero.getBitWidth() == One.getBitWidth() &&
+           "Zero and One should have the same width!");
+    return !hasConflict();
+  }
+
+  /// Returns true if we know the value of all bits.
+  bool isComplete() const {
+    assert(isValid() && "KnownBits conflict!");
+    return Zero.countPopulation() + One.countPopulation() == getBitWidth();
+  }
+
+  /// Returns the value when all bits have a known value. This just returns One
+  /// with a protective assertion.
+  const APInt &getValue() const {
+    assert(isComplete() && "Can only get value when all bits are known");
+    return One;
+  }
+
+  /// Returns true if this value is known to be negative.
+  bool isNegative() const { return One.isSignBitSet(); }
+
+  /// Returns true if this value is known to be non-negative.
+  bool isNonNegative() const { return Zero.isSignBitSet(); }
+
+  /// Truncate the underlying known Zero and One bits. This is equivalent
+  /// to truncating the value we're tracking.
+  void trunc(unsigned BitWidth) {
+    Zero = Zero.trunc(BitWidth);
+    One  = One.trunc(BitWidth);
+  }
+
+  /// Zero extends the underlying known Zero and One bits. This is equivalent
+  /// to zero extending the value we're tracking.
+  void zext(unsigned BitWidth) {
+    Zero = Zero.zext(BitWidth);
+    One  = One.zext(BitWidth);
+  }
+
+  /// Sign extends the underlying known Zero and One bits. This is equivalent
+  /// to sign extending the value we're tracking. 
+  void sext(unsigned BitWidth) {
+    Zero = Zero.sext(BitWidth);
+    One  = One.sext(BitWidth);
+  }
 };
 
 } // end namespace llvm
 
 #endif