Add getDemandedBits for uses.

[qunyanm]

Summary

Add getDemandedBits method for uses so we can query demanded bits for each use. This can help getting better use information. For example, for the code below
define i32 @test_use(i32 %a) {

%1 = and i32 %a, -256
%2 = or i32 %1, 1
%3 = trunc i32 %2 to i8 (didn't optimize this to 1 for illustration purpose)
... some use of %3
ret %2

}
if we look at the demanded bit of %2 (which is all 32 bits because of the return), we would conclude that %a is used regardless of how its return is used. However, if we look at each use separately, we will see that the demanded bit of %2 in trunc only uses the lower 8 bits of %a which is redefined, therefore %a's usage depends on how the function return is used.

[qunyanm]

• Formatting.

[lebedev.ri]

The patch's description states what the patch does, but not *why* it does that.

[RKSimon]

In D97074#2579069, @lebedev.ri wrote:

The patch's description states what the patch does, but not *why* it does that.

+1

llvm/lib/Analysis/DemandedBits.cpp

465

Could this be used in the APInt::getAllOnesValue() above instead of the getTypeSizeInBits call?

[qunyanm]

• Use getScalarSizeInBits() to get bitwidth of the type.

[qunyanm]

• Formatting.
• Use getScalarSizeInBits() to get bitwidth of the type.

[qunyanm]

In D97074#2579069, @lebedev.ri wrote:

The patch's description states what the patch does, but not *why* it does that.

I reworded the commit message. Just realized that I'm not sure if that's the patch's description you were referring to. Please let me know if it's wrong and how to update it. Sorry, I should've asked first.

llvm/lib/Analysis/DemandedBits.cpp

465

Yes. Thanks!

[lebedev.ri]

I think we'll need to see the patch that depends on this.

[qunyanm]

Revert last commit where getTypeSizeInBit() is replaced by getScalarSizeInBits() because
getScalareSizeInBits() returns 0 for cases such as non-primitive types where the use should
be all bit used.

[RKSimon]

llvm/lib/Analysis/DemandedBits.cpp

465

Hmm - what about

unsigned BitWidth = DL.getTypeSizeInBits(T->getScalarType());

[qunyanm]

In D97074#2628169, @lebedev.ri wrote:

I think we'll need to see the patch that depends on this.

I don't have a patch to submit that depends on this (I just use it in a tool built on top of llvm). The change is basically a wrapper to expose determineLiveOperandBits(), which is private, and set up the dummy arguments. It would allow inspection of demandedBits for each use in case we want finer grain information than the demandedBits of def which is an aggregate of all its uses..

llvm/lib/Analysis/DemandedBits.cpp

465

Actually it won't work since getScalarSizeInBits() returns 0 for non-primitive types that demandedBits don't track therefore should be marked as all bit used.

[qunyanm]

• Replace getScalarSizeInBits() with DL.getTypeSizeInBits since they return the same value for int.

[qunyanm]

llvm/lib/Analysis/DemandedBits.cpp

465

Yes, I believe they return the same value for int/intvector.

[RKSimon]

I've no strong objections to this going in purely for debug purposes, but would prefer it if there were use cases in the actual code.

[RKSimon]

This either needs use cases in code, or needs cleaning up to just operate in debug mode.

[qunyanm]

We have an out-of-tree code analysis tool that we want to surface use-level consumed-bits information, and thus want this method to be added to the public API surface of libLLVM (and therefore need it to be included in release builds). Part of the analysis includes propagating the demanded bits of returned values. So for the code example from the commit message:

define i32 @test_use(i32 %a) {
      %1 = and i32 %a, -256
      %2 = or i32 %1, 1
      %3 = trunc i32 %2 to i8 (didn't optimize this to 1 for illustration purpose)
      ... some use of %3
      ret %2
  }

In order to propagate the demanded bits of the returned value, we need to be able to get the demanded bits of %2 at "trunc". This change is just trying to make "determineLiveOperandBits" public as was done for "determineLiveOperandBitsAdd/determineLiveOperandBitsSub", and I added the use in the dump to make sure that the lit test suite exercises the code and verifies the result. Could you please clarify the concern/request? I.e., if the dump code executed in the lit test is not "actual code", but our motivating use case is an out-of-tree llvm-based code analysis tool, what code do you recommend I add a use in?

[qunyanm]

ping

[craig.topper]

llvm/lib/Analysis/DemandedBits.cpp

461

Please fix this clang-format warning

462

Drop curly braces

[qunyanm]

• Formatting.

[qunyanm]

ping

[RKSimon]

OK, let's go with this - LGTM (after you fix that clang-tidy warning)

llvm/lib/Analysis/DemandedBits.cpp

516

auto PrintDB

[qunyanm]

• Formatting

llvm/include/llvm/Analysis/DemandedBits.h

public:
   /// A bit is demanded if it is demanded for any of the vector elements. The
   /// size of the return value corresponds to the type size in bits of the
   /// scalar type.
   ///
   /// Instructions that do not have integer or vector of integer type are
   /// accepted, but will always produce a mask with all bits set.
   APInt getDemandedBits(Instruction *I);
 
+  /// Return the bits demanded from use U.
+  APInt getDemandedBits(Use *U);
+
   /// Return true if, during analysis, I could not be reached.
   bool isInstructionDead(Instruction *I);
 
   /// Return whether this use is dead by means of not having any demanded bits.
   bool isUseDead(Use *U);
 
   void print(raw_ostream &OS);
 

llvm/lib/Analysis/DemandedBits.cpp

APInt DemandedBits::getDemandedBits(Instruction *I) {
   if (Found != AliveBits.end())
     return Found->second;
 
   const DataLayout &DL = I->getModule()->getDataLayout();
   return APInt::getAllOnesValue(
       DL.getTypeSizeInBits(I->getType()->getScalarType()));
 }
 
+APInt DemandedBits::getDemandedBits(Use *U) {
+  Type *T = (*U)->getType();
+  Instruction *UserI = cast<Instruction>(U->getUser());
+
+  // We only track integer uses, everything else produces a mask with all bits set
+  if (!T->isIntOrIntVectorTy()) {
+    const DataLayout &DL = UserI->getModule()->getDataLayout();
+    return APInt::getAllOnesValue(DL.getTypeSizeInBits(T->getScalarType()));
+  }
+
+  unsigned BitWidth = T->getScalarSizeInBits();
+
+  if (isUseDead(U))
+    return APInt(BitWidth, 0);
+
+  performAnalysis();
+
+  APInt AOut = getDemandedBits(UserI);
+  APInt AB = APInt::getAllOnesValue(BitWidth);
+  KnownBits Known, Known2;
+  bool KnownBitsComputed = false;
+
+  determineLiveOperandBits(UserI, *U, U->getOperandNo(), AOut, AB, Known,
+                           Known2, KnownBitsComputed);
+
+  return AB;
+}
+
 bool DemandedBits::isInstructionDead(Instruction *I) {
   performAnalysis();
 
   return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
     !isAlwaysLive(I);
 }
 
 bool DemandedBits::isUseDead(Use *U) {
if (UserI->getType()->isIntOrIntVectorTy()) {
     if (Found != AliveBits.end() && Found->second.isNullValue())
       return true;
   }
 
   return false;
 }
 
 void DemandedBits::print(raw_ostream &OS) {
+  auto printDB = [&](const Instruction *I, const APInt &A, Value *V = nullptr) {
+    OS << "DemandedBits: 0x" << Twine::utohexstr(A.getLimitedValue())
+       << " for ";
+    if (V) {
+      V->printAsOperand(OS, false);
+      OS << " in ";
+    }
+    OS << *I << '\n';
+  };
+
   performAnalysis();
   for (auto &KV : AliveBits) {
-    OS << "DemandedBits: 0x" << Twine::utohexstr(KV.second.getLimitedValue())
-       << " for " << *KV.first << '\n';
+    Instruction *I = KV.first;
+    printDB(I, KV.second);
+
+    for (Use &OI : I->operands()) {
+      printDB(I, getDemandedBits(&OI), OI);
+    }
   }
 }
 
 static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo,
                                               const APInt &AOut,
                                               const KnownBits &LHS,
                                               const KnownBits &RHS,
                                               bool CarryZero, bool CarryOne) {

llvm/test/Analysis/DemandedBits/basic.ll

 ; RUN: opt -S -demanded-bits -analyze -enable-new-pm=0 < %s | FileCheck %s
 ; RUN: opt -S -disable-output -passes="print<demanded-bits>" < %s 2>&1 | FileCheck %s
  
 ; CHECK-DAG: DemandedBits: 0xff for   %1 = add nsw i32 %a, 5
 ; CHECK-DAG: DemandedBits: 0xff for   %3 = trunc i32 %2 to i8
 ; CHECK-DAG: DemandedBits: 0xff for   %2 = mul nsw i32 %1, %b
+; CHECK-DAG: DemandedBits: 0x1 for   %4 = trunc i32 %2 to i1
+; CHECK-DAG: DemandedBits: 0xff for   %5 = zext i1 %4 to i8
+; CHECK-DAG: DemandedBits: 0xff for   %6 = add nsw i8 %3, %5
+; CHECK-DAG: DemandedBits: 0xff for %a in   %1 = add nsw i32 %a, 5
+; CHECK-DAG: DemandedBits: 0xff for 5 in   %1 = add nsw i32 %a, 5
+; CHECK-DAG: DemandedBits: 0xff for %1 in   %2 = mul nsw i32 %1, %b
+; CHECK-DAG: DemandedBits: 0xff for %b in   %2 = mul nsw i32 %1, %b
+; CHECK-DAG: DemandedBits: 0xff for %2 in   %3 = trunc i32 %2 to i8
+; CHECK-DAG: DemandedBits: 0x1 for %2 in   %4 = trunc i32 %2 to i1
+; CHECK-DAG: DemandedBits: 0x1 for %4 in   %5 = zext i1 %4 to i8
+; CHECK-DAG: DemandedBits: 0xff for %3 in   %6 = add nsw i8 %3, %5
+; CHECK-DAG: DemandedBits: 0xff for %5 in   %6 = add nsw i8 %3, %5
 define i8 @test_mul(i32 %a, i32 %b) {
   %1 = add nsw i32 %a, 5
   %2 = mul nsw i32 %1, %b
   %3 = trunc i32 %2 to i8
-  ret i8 %3
+  %4 = trunc i32 %2 to i1
+  %5 = zext i1 %4 to i8
+  %6 = add nsw i8 %3, %5
+  ret i8 %6
 }