[BDCE][DemandedBits] Detect dead uses of undead instructions

[nikic]

Summary

This (mostly) fixes https://bugs.llvm.org/show_bug.cgi?id=39771.

BDCE currently detects instructions that don't have any demanded bits and replaces their uses with zero. However, if an instruction has multiple uses, then some of the uses may be dead (have no demanded bits) even though the instruction itself is still live. This patch extends DemandedBits/BDCE to detect such uses and replace them with zero. While this will not immediately render any instructions dead, it may lead to simplifications (in the motivating case, by converting a rotate into a simple shift), break dependencies, etc.

The implementation tries to strike a balance between analysis power and complexity/memory usage. Originally I wanted to track demanded bits on a per-use level, but ultimately we're only really interested in whether a use is entirely dead or not. I'm using an extra set to track which uses are dead. However, as initially all uses are dead, I'm not storing uses those user is also dead. This case is checked separately instead.

The test case has a couple of cases that are simplified yet. In particular, we're only looking at uses of instructions right now. I think it would make sense to also extend this to arguments. Furthermore DemandedBits doesn't yet know some of the tricks that InstCombine does for the demanded bits or bitwise or/and/xor in combination with known bits information.

[nikic]

Ping

[hfinkel]

lib/Analysis/DemandedBits.cpp

440 ↗

(On Diff #177726)

Please remove this assert. For consistency with the other interfaces, we should just have the function return false in this case.

455 ↗

(On Diff #177726)

We know that this will never return AliveBits.end()? A comment or assert should explain this.

lib/Transforms/Scalar/BDCE.cpp

113 ↗

(On Diff #177726)

TODO: (add colon)

130 ↗

(On Diff #177726)

With this new logic, where do we now remove instructions for which all uses have been trivialized?

[nikic]

Remove assert, check that instr is in AliveBits.

[nikic]

lib/Analysis/DemandedBits.cpp

455 ↗

(On Diff #177726)

I think that due to the way the API is used by BDCE (checking isInstructionDead first) this case can't be hit, but from the perspective of just this API it could happen. I've added a check.

lib/Transforms/Scalar/BDCE.cpp

130 ↗

(On Diff #177726)

BDCE currently (also before this change) does not remove instructions without demanded bits, it only replaces their uses with zero and lets somebody else handle the cleanup (some BDCE tests run instcombine afterwards). Only instructions not reached during analysis are removed entirely (the isInstructionDead check).

I think BDCE *should* be dropping them, but it's probably best to do this as a separate change, as it will require changes to otherwise unrelated BDCE tests.

[hfinkel]

lib/Transforms/Scalar/BDCE.cpp

130 ↗

(On Diff #177726)

I think BDCE *should* be dropping them, but it's probably best to do this as a separate change, as it will require changes to otherwise unrelated BDCE tests.

I agree (the old logic looks like it won't do this, and that seems to be a mistake). If you could do this as follow-up, that would be great.

LGTM.

[nikic]

I've reverted this, because it causes enc-3des.execution_time from test-suite to fail (e.g. http://lab.llvm.org:8011/builders/clang-cmake-x86_64-sde-avx512-linux/builds/16746).

[nikic]

Fix removal of dead uses. The previous version had a check whether the previous demanded bits are empty and only dropped the use from the DeadUses set in that case. The motivation for this was that the use could only be part of DeadUses if the demanded bits are empty, so we can save a redundant hash lookup. Of course, this is not actually true, because the previous demanded bits are for the instruction across all users, which is a superset of the demanded bits for a single use. (That being kind of the whole point of this change, I'm really not sure what I was thinking there...)

So now I'm just always doing the erase() call when a use has non-empty demanded bits. I've also added a testcase that was miscompiled with the previous version. I believe that this is also what caused the failure in enc-3des from the test-suite.

[hfinkel]

In D55563#1342816, @nikic wrote:

Fix removal of dead uses. The previous version had a check whether the previous demanded bits are empty and only dropped the use from the DeadUses set in that case. The motivation for this was that the use could only be part of DeadUses if the demanded bits are empty, so we can save a redundant hash lookup. Of course, this is not actually true, because the previous demanded bits are for the instruction across all users, which is a superset of the demanded bits for a single use. (That being kind of the whole point of this change, I'm really not sure what I was thinking there...)

So now I'm just always doing the erase() call when a use has non-empty demanded bits. I've also added a testcase that was miscompiled with the previous version. I believe that this is also what caused the failure in enc-3des from the test-suite.

LGTM

llvm/trunk/include/llvm/Analysis/DemandedBits.h

public:
   ///
   /// 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 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);
 
 private:
   void performAnalysis();
   void determineLiveOperandBits(const Instruction *UserI,
     const Instruction *I, unsigned OperandNo,
     const APInt &AOut, APInt &AB,
     KnownBits &Known, KnownBits &Known2);
 
   Function &F;
   AssumptionCache ∾
   DominatorTree &DT;
 
   bool Analyzed = false;
 
   // The set of visited instructions (non-integer-typed only).
   SmallPtrSet<Instruction*, 32> Visited;
   DenseMap<Instruction *, APInt> AliveBits;
+  // Uses with no demanded bits. If the user also has no demanded bits, the use
+  // might not be stored explicitly in this map, to save memory during analysis.
+  SmallPtrSet<Use *, 16> DeadUses;
 };
 
 class DemandedBitsWrapperPass : public FunctionPass {
 private:
   mutable Optional<DemandedBits> DB;
 
 public:
   static char ID; // Pass identification, replacement for typeid

llvm/trunk/lib/Analysis/DemandedBits.cpp

 void DemandedBits::performAnalysis() {
   if (Analyzed)
     // Analysis already completed for this function.
     return;
   Analyzed = true;
 
   Visited.clear();
   AliveBits.clear();
+  DeadUses.clear();
 
   SmallVector<Instruction*, 128> Worklist;
 
   // Collect the set of "root" instructions that are known live.
   for (Instruction &I : instructions(F)) {
     if (!isAlwaysLive(&I))
       continue;
 
void DemandedBits::performAnalysis() {
   // Propagate liveness backwards to operands.
   while (!Worklist.empty()) {
     Instruction *UserI = Worklist.pop_back_val();
 
     LLVM_DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
     APInt AOut;
     if (UserI->getType()->isIntOrIntVectorTy()) {
       AOut = AliveBits[UserI];
-      LLVM_DEBUG(dbgs() << " Alive Out: " << AOut);
+      LLVM_DEBUG(dbgs() << " Alive Out: 0x"
+                        << Twine::utohexstr(AOut.getLimitedValue()));
     }
     LLVM_DEBUG(dbgs() << "\n");
 
     if (!UserI->getType()->isIntOrIntVectorTy())
       Visited.insert(UserI);
 
     KnownBits Known, Known2;
     // Compute the set of alive bits for each operand. These are anded into the
     // existing set, if any, and if that changes the set of alive bits, the
     // operand is added to the work-list.
     for (Use &OI : UserI->operands()) {
       if (Instruction *I = dyn_cast<Instruction>(OI)) {
         Type *T = I->getType();
         if (T->isIntOrIntVectorTy()) {
           unsigned BitWidth = T->getScalarSizeInBits();
           APInt AB = APInt::getAllOnesValue(BitWidth);
           if (UserI->getType()->isIntOrIntVectorTy() && !AOut &&
               !isAlwaysLive(UserI)) {
+            // If all bits of the output are dead, then all bits of the input
+            // are also dead.
             AB = APInt(BitWidth, 0);
           } else {
-            // If all bits of the output are dead, then all bits of the input
             // Bits of each operand that are used to compute alive bits of the
             // output are alive, all others are dead.
             determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB,
                                      Known, Known2);
+
+            // Keep track of uses which have no demanded bits.
+            if (AB.isNullValue())
+              DeadUses.insert(&OI);
+            else
+              DeadUses.erase(&OI);
           }
 
           // If we've added to the set of alive bits (or the operand has not
           // been previously visited), then re-queue the operand to be visited
           // again.
           APInt ABPrev(BitWidth, 0);
           auto ABI = AliveBits.find(I);
           if (ABI != AliveBits.end())

 
 bool DemandedBits::isInstructionDead(Instruction *I) {
   performAnalysis();
 
   return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
     !isAlwaysLive(I);
 }
 
+bool DemandedBits::isUseDead(Use *U) {
+  // We only track integer uses, everything else is assumed live.
+  if (!(*U)->getType()->isIntOrIntVectorTy())
+    return false;
+
+  // Uses by always-live instructions are never dead.
+  Instruction *UserI = cast<Instruction>(U->getUser());
+  if (isAlwaysLive(UserI))
+    return false;
+
+  performAnalysis();
+  if (DeadUses.count(U))
+    return true;
+
+  // If no output bits are demanded, no input bits are demanded and the use
+  // is dead. These uses might not be explicitly present in the DeadUses map.
+  if (UserI->getType()->isIntOrIntVectorTy()) {
+    auto Found = AliveBits.find(UserI);
+    if (Found != AliveBits.end() && Found->second.isNullValue())
+      return true;
+  }
+
+  return false;
+}
+
 void DemandedBits::print(raw_ostream &OS) {
   performAnalysis();
   for (auto &KV : AliveBits) {
     OS << "DemandedBits: 0x" << Twine::utohexstr(KV.second.getLimitedValue())
        << " for " << *KV.first << '\n';
   }
 }
 

llvm/trunk/lib/Transforms/Scalar/BDCE.cpp

static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
   bool Changed = false;
   for (Instruction &I : instructions(F)) {
     // If the instruction has side effects and no non-dbg uses,
     // skip it. This way we avoid computing known bits on an instruction
     // that will not help us.
     if (I.mayHaveSideEffects() && I.use_empty())
       continue;
 
-    if (I.getType()->isIntOrIntVectorTy() &&
-        !DB.getDemandedBits(&I).getBoolValue()) {
-      // For live instructions that have all dead bits, first make them dead by
-      // replacing all uses with something else. Then, if they don't need to
-      // remain live (because they have side effects, etc.) we can remove them.
-      LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");
+    // Remove instructions not reached during analysis.
+    if (DB.isInstructionDead(&I)) {
+      salvageDebugInfo(I);
+      Worklist.push_back(&I);
+      I.dropAllReferences();
+      Changed = true;
+      continue;
+    }
+
+    for (Use &U : I.operands()) {
+      // DemandedBits only detects dead integer uses.
+      if (!U->getType()->isIntOrIntVectorTy())
+        continue;
+
+      // TODO: We could also find dead non-instruction uses, e.g. arguments.
+      if (!isa<Instruction>(U))
+        continue;
+
+      if (!DB.isUseDead(&U))
+        continue;
+
+      LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");
 
       clearAssumptionsOfUsers(&I, DB);
 
       // FIXME: In theory we could substitute undef here instead of zero.
       // This should be reconsidered once we settle on the semantics of
       // undef, poison, etc.
-      Value *Zero = ConstantInt::get(I.getType(), 0);
+      U.set(ConstantInt::get(U->getType(), 0));
       ++NumSimplified;
-      I.replaceNonMetadataUsesWith(Zero);
       Changed = true;
     }
-    if (!DB.isInstructionDead(&I))
-      continue;
-
-    salvageDebugInfo(I);
-    Worklist.push_back(&I);
-    I.dropAllReferences();
-    Changed = true;
   }
 
   for (Instruction *&I : Worklist) {
     ++NumRemoved;
     I->eraseFromParent();
   }
 
   return Changed;

llvm/trunk/test/Transforms/BDCE/dead-uses.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -bdce -S < %s | FileCheck %s
 
 ; Funnel shift based rotate test cases from PR39771
 
 declare i32 @llvm.fshr.i32(i32, i32, i32)
 declare <2 x i32> @llvm.fshr.v2i32(<2 x i32>, <2 x i32>, <2 x i32>)
 
 ; First fshr operand is dead.
 define i32 @pr39771_fshr_multi_use_instr(i32 %a) {
 ; CHECK-LABEL: @pr39771_fshr_multi_use_instr(
 ; CHECK-NEXT:    [[X:%.*]] = or i32 [[A:%.*]], 0
-; CHECK-NEXT:    [[B:%.*]] = tail call i32 @llvm.fshr.i32(i32 [[X]], i32 [[X]], i32 1)
+; CHECK-NEXT:    [[B:%.*]] = tail call i32 @llvm.fshr.i32(i32 0, i32 [[X]], i32 1)
 ; CHECK-NEXT:    [[C:%.*]] = lshr i32 [[B]], 23
 ; CHECK-NEXT:    [[D:%.*]] = xor i32 [[C]], [[B]]
 ; CHECK-NEXT:    [[E:%.*]] = and i32 [[D]], 31
 ; CHECK-NEXT:    ret i32 [[E]]
 ;
   %x = or i32 %a, 0
   %b = tail call i32 @llvm.fshr.i32(i32 %x, i32 %x, i32 1)
   %c = lshr i32 %b, 23
   %d = xor i32 %c, %b
   %e = and i32 %d, 31
   ret i32 %e
 }
 
 ; First fshr operand is dead (vector variant).
 define <2 x i32> @pr39771_fshr_multi_use_instr_vec(<2 x i32> %a) {
 ; CHECK-LABEL: @pr39771_fshr_multi_use_instr_vec(
 ; CHECK-NEXT:    [[X:%.*]] = or <2 x i32> [[A:%.*]], zeroinitializer
-; CHECK-NEXT:    [[B:%.*]] = tail call <2 x i32> @llvm.fshr.v2i32(<2 x i32> [[X]], <2 x i32> [[X]], <2 x i32> <i32 1, i32 1>)
+; CHECK-NEXT:    [[B:%.*]] = tail call <2 x i32> @llvm.fshr.v2i32(<2 x i32> zeroinitializer, <2 x i32> [[X]], <2 x i32> <i32 1, i32 1>)
 ; CHECK-NEXT:    [[C:%.*]] = lshr <2 x i32> [[B]], <i32 23, i32 23>
 ; CHECK-NEXT:    [[D:%.*]] = xor <2 x i32> [[C]], [[B]]
 ; CHECK-NEXT:    [[E:%.*]] = and <2 x i32> [[D]], <i32 31, i32 31>
 ; CHECK-NEXT:    ret <2 x i32> [[E]]
 ;
   %x = or <2 x i32> %a, zeroinitializer
   %b = tail call <2 x i32> @llvm.fshr.v2i32(<2 x i32> %x, <2 x i32> %x, <2 x i32> <i32 1, i32 1>)
   %c = lshr <2 x i32> %b, <i32 23, i32 23>
;
   %tmp = lshr i32 %a, 1
   %tmp2 = shl i32 %a, 32
   %b = or i32 %tmp, %tmp2
   %c = lshr i32 %b, 23
   %d = xor i32 %c, %b
   %e = and i32 %d, 31
   ret i32 %e
 }
+
+; %b operand of %c will be dead initially, but later found live.
+define void @dead_use_invalidation(i32 %a) {
+; CHECK-LABEL: @dead_use_invalidation(
+; CHECK-NEXT:    [[B:%.*]] = or i32 [[A:%.*]], 0
+; CHECK-NEXT:    [[C:%.*]] = shl i32 [[B]], 31
+; CHECK-NEXT:    [[D:%.*]] = and i32 [[C]], 1
+; CHECK-NEXT:    [[E:%.*]] = or i32 [[C]], 0
+; CHECK-NEXT:    [[F:%.*]] = or i32 [[D]], 0
+; CHECK-NEXT:    call void @dummy(i32 [[E]])
+; CHECK-NEXT:    call void @dummy(i32 [[F]])
+; CHECK-NEXT:    call void @dummy(i32 [[B]])
+; CHECK-NEXT:    ret void
+;
+  %b = or i32 %a, 0
+  %c = shl i32 %b, 31
+  %d = and i32 %c, 1
+  %e = or i32 %c, 0
+  %f = or i32 %d, 0
+  call void @dummy(i32 %e)
+  call void @dummy(i32 %f)
+  call void @dummy(i32 %b)
+  ret void
+}
+declare void @dummy(i32)