[BDCE] Remove dead uses of arguments

[nikic]

Summary

Another followup to D55563.

In addition to finding dead uses of instructions, also find dead uses of function arguments, and replace them with zero as well.

I'm changing the way the known bits are computed here to remove the coupling between the transfer function and the algorithm. It previously relied on the first op being visited first and computing known bits -- unless the first op is not an instruction, in which case they're computed on the second op. I could have adjusted this to check for "instruction or argument", but I think it's better to avoid the repeated calculation with an explicit flag.

[hfinkel]

LGTM

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

public:
   /// 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 Value *Val, unsigned OperandNo,
     const APInt &AOut, APInt &AB,
-    KnownBits &Known, KnownBits &Known2);
+    KnownBits &Known, KnownBits &Known2, bool &KnownBitsComputed);
 
   Function &F;
   AssumptionCache ∾
   DominatorTree &DT;
 
   bool Analyzed = false;
 
   // The set of visited instructions (non-integer-typed only).

llvm/trunk/lib/Analysis/DemandedBits.cpp

 }
 
 static bool isAlwaysLive(Instruction *I) {
   return I->isTerminator() || isa<DbgInfoIntrinsic>(I) || I->isEHPad() ||
          I->mayHaveSideEffects();
 }
 
 void DemandedBits::determineLiveOperandBits(
-    const Instruction *UserI, const Instruction *I, unsigned OperandNo,
-    const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2) {
+    const Instruction *UserI, const Value *Val, unsigned OperandNo,
+    const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2,
+    bool &KnownBitsComputed) {
   unsigned BitWidth = AB.getBitWidth();
 
   // We're called once per operand, but for some instructions, we need to
   // compute known bits of both operands in order to determine the live bits of
   // either (when both operands are instructions themselves). We don't,
   // however, want to do this twice, so we cache the result in APInts that live
   // in the caller. For the two-relevant-operands case, both operand values are
   // provided here.
   auto ComputeKnownBits =
       [&](unsigned BitWidth, const Value *V1, const Value *V2) {
-        const DataLayout &DL = I->getModule()->getDataLayout();
+        if (KnownBitsComputed)
+          return;
+        KnownBitsComputed = true;
+
+        const DataLayout &DL = UserI->getModule()->getDataLayout();
         Known = KnownBits(BitWidth);
         computeKnownBits(V1, Known, DL, 0, &AC, UserI, &DT);
 
         if (V2) {
           Known2 = KnownBits(BitWidth);
           computeKnownBits(V2, Known2, DL, 0, &AC, UserI, &DT);
         }
       };
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
         // the output.
         AB = AOut.reverseBits();
         break;
       case Intrinsic::ctlz:
         if (OperandNo == 0) {
           // We need some output bits, so we need all bits of the
           // input to the left of, and including, the leftmost bit
           // known to be one.
-          ComputeKnownBits(BitWidth, I, nullptr);
+          ComputeKnownBits(BitWidth, Val, nullptr);
           AB = APInt::getHighBitsSet(BitWidth,
                  std::min(BitWidth, Known.countMaxLeadingZeros()+1));
         }
         break;
       case Intrinsic::cttz:
         if (OperandNo == 0) {
           // We need some output bits, so we need all bits of the
           // input to the right of, and including, the rightmost bit
           // known to be one.
-          ComputeKnownBits(BitWidth, I, nullptr);
+          ComputeKnownBits(BitWidth, Val, nullptr);
           AB = APInt::getLowBitsSet(BitWidth,
                  std::min(BitWidth, Known.countMaxTrailingZeros()+1));
         }
         break;
       case Intrinsic::fshl:
       case Intrinsic::fshr: {
         const APInt *SA;
         if (OperandNo == 2) {
case Instruction::AShr:
     break;
   case Instruction::And:
     AB = AOut;
 
     // For bits that are known zero, the corresponding bits in the
     // other operand are dead (unless they're both zero, in which
     // case they can't both be dead, so just mark the LHS bits as
     // dead).
-    if (OperandNo == 0) {
-      ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
+    ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
+    if (OperandNo == 0)
       AB &= ~Known2.Zero;
-    } else {
-      if (!isa<Instruction>(UserI->getOperand(0)))
-        ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
+    else
       AB &= ~(Known.Zero & ~Known2.Zero);
-    }
     break;
   case Instruction::Or:
     AB = AOut;
 
     // For bits that are known one, the corresponding bits in the
     // other operand are dead (unless they're both one, in which
     // case they can't both be dead, so just mark the LHS bits as
     // dead).
-    if (OperandNo == 0) {
-      ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
+    ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
+    if (OperandNo == 0)
       AB &= ~Known2.One;
-    } else {
-      if (!isa<Instruction>(UserI->getOperand(0)))
-        ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
+    else
       AB &= ~(Known.One & ~Known2.One);
-    }
     break;
   case Instruction::Xor:
   case Instruction::PHI:
     AB = AOut;
     break;
   case Instruction::Trunc:
     AB = AOut.zext(BitWidth);
     break;
if (UserI->getType()->isIntOrIntVectorTy()) {
                         << Twine::utohexstr(AOut.getLimitedValue()));
     }
     LLVM_DEBUG(dbgs() << "\n");
 
     if (!UserI->getType()->isIntOrIntVectorTy())
       Visited.insert(UserI);
 
     KnownBits Known, Known2;
+    bool KnownBitsComputed = false;
     // 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 {
-            // 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);
+      // We also want to detect dead uses of arguments, but will only store
+      // demanded bits for instructions.
+      Instruction *I = dyn_cast<Instruction>(OI);
+      if (!I && !isa<Argument>(OI))
+        continue;
+
+      Type *T = OI->getType();
+          determineLiveOperandBits(UserI, OI, OI.getOperandNo(), AOut, AB,
+                                   Known, Known2, KnownBitsComputed);
 
-            // Keep track of uses which have no demanded bits.
-            if (AB.isNullValue())
-              DeadUses.insert(&OI);
-            else
-              DeadUses.erase(&OI);
-          }
 
+        if (I) {
           // 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())
             ABPrev = ABI->second;
 
           APInt ABNew = AB | ABPrev;
           if (ABNew != ABPrev || ABI == AliveBits.end()) {
             AliveBits[I] = std::move(ABNew);
             Worklist.push_back(I);
           }
-        } else if (!Visited.count(I)) {
-          Worklist.push_back(I);
         }
+      } else if (I && !Visited.count(I)) {
+        Worklist.push_back(I);
       }
     }
   }
 }
 
 APInt DemandedBits::getDemandedBits(Instruction *I) {
   performAnalysis();
 

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

if (DB.isInstructionDead(&I) ||
       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))
+      if (!isa<Instruction>(U) && !isa<Argument>(U))
         continue;
 
       if (!DB.isUseDead(&U))
         continue;
 
       LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");
 
       clearAssumptionsOfUsers(&I, DB);

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

;
   %d = xor <2 x i32> %c, %b
   %e = and <2 x i32> %d, <i32 31, i32 31>
   ret <2 x i32> %e
 }
 
 ; First fshr operand is dead, but it comes from an argument, not instruction.
 define i32 @pr39771_fshr_multi_use_arg(i32 %a) {
 ; CHECK-LABEL: @pr39771_fshr_multi_use_arg(
-; CHECK-NEXT:    [[B:%.*]] = tail call i32 @llvm.fshr.i32(i32 [[A:%.*]], i32 [[A]], i32 1)
+; CHECK-NEXT:    [[B:%.*]] = tail call i32 @llvm.fshr.i32(i32 0, i32 [[A:%.*]], 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]]
 ;
   %b = tail call i32 @llvm.fshr.i32(i32 %a, i32 %a, i32 1)
   %c = lshr i32 %b, 23
   %d = xor i32 %c, %b
   %e = and i32 %d, 31
   ret i32 %e
 }
 
-; Second or operand is dead, but BDCE does not realize this.
 define i32 @pr39771_expanded_fshr_multi_use(i32 %a) {
 ; CHECK-LABEL: @pr39771_expanded_fshr_multi_use(
 ; CHECK-NEXT:    [[TMP:%.*]] = lshr i32 [[A:%.*]], 1
-; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 [[A]], 31
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 0, 31
 ; CHECK-NEXT:    [[B:%.*]] = or i32 [[TMP]], [[TMP2]]
 ; 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]]
 ;
   %tmp = lshr i32 %a, 1
   %tmp2 = shl i32 %a, 31