Separate out BDCE's analysis into a separate DemandedBits analysis.

[jmolloy]

Summary

This allows other areas of the compiler (LoopVectorize, soon!) to use BDCE's bit-tracking.

NFCI.

[jmolloy]

Ping! Hal, do you have any comments on this?

[hfinkel]

include/llvm/Analysis/DemandedBits.h

55

I think that I prefer the present tense for analysis results, let's name this:

isInstructionDead

lib/Analysis/DemandedBits.cpp

352

Given that you return a conservative answer regardless, I don't see any reason to have this assert. I recommend removing it (and the associated comment in the header).

355

Use getSizeInBits instead of getScalarSizeInBits so that we get the right conservative answer for vectors.

lib/Transforms/Scalar/BDCE.cpp

82

Is looks like, as you have it setup, getDemandedBits will return all ones for an instruction not in the map (for any instruction for which DB.demandedBitsKnown(&I) would return false). As a result, we don't need the DB.demandedBitsKnown(&I) check and can just use the DB.getDemandedBits check (avoiding repeating the map lookup).

[jmolloy]

Hi Hal,

I've updated the diff with most of your comments updated, however:

Is looks like, as you have it setup, getDemandedBits will return all ones for an instruction not in the map (for any instruction for which DB.demandedBitsKnown(&I) would return false). As a result, we don't need the DB.demandedBitsKnown(&I) check and can just use the DB.getDemandedBits check (avoiding repeating the map lookup).

Unfortunately this isn't the case. BDCE expects to handle the case where an instruction was analyzed, but has bits demanded differently to an instruction that wasn't even analyzed. In the second case it expects to dive off down the else path, in the first case it doesn't. Changing that behavior at all leads to lots of use-before-free asserts.

James

[hfinkel]

In D11596#222847, @jmolloy wrote:

Hi Hal,

I've updated the diff with most of your comments updated, however:

Is looks like, as you have it setup, getDemandedBits will return all ones for an instruction not in the map (for any instruction for which DB.demandedBitsKnown(&I) would return false). As a result, we don't need the DB.demandedBitsKnown(&I) check and can just use the DB.getDemandedBits check (avoiding repeating the map lookup).

Unfortunately this isn't the case. BDCE expects to handle the case where an instruction was analyzed, but has bits demanded differently to an instruction that wasn't even analyzed. In the second case it expects to dive off down the else path, in the first case it doesn't. Changing that behavior at all leads to lots of use-before-free asserts.

I'm not sure what exactly you did, but the underlying logic should be this:

if (instruction is dead) {
  mark for deletion
} else if (all bits are dead and has an integer type) {
  replace all uses with zero
  mark for deletion 
}

if (marked for deletion && not an always-live instruction) {
  drop references and add to the to-delete worklist
}

I believe to implement my suggestion, you'll need to slightly rearrange the logic there. Thanks again!

James

[jmolloy]

Hi Hal,

I worked out where I was getting confused. In DemandedBits, the "Visited" set only contains non-integer instructions. In "isInstructionDead" I was only visiting membership of the Visited set - I needed to check membership of AliveBits too because that's where all the integer types live.

With that change, I've been able to do away with a no-longer needed API function and the code looks a lot neater.

Cheers,

James

[hfinkel]

One comment below, otherwise LGTM.

lib/Transforms/Scalar/BDCE.cpp

94

You don't need this check here because you also have the isAlwaysLive check in DB.isInstructionDead (and I think that's a good thing).

[jmolloy]

Hi Hal,

Thanks, I removed the isAlwaysLive() check (and function) and simplified the logic in r245038.

Cheers,

James

include/llvm/Analysis/DemandedBits.h

+//===-- llvm/Analysis/DemandedBits.h - Determine demanded bits --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass implements a demanded bits analysis. A demanded bit is one that
+// contributes to a result; bits that are not demanded can be either zero or
+// one without affecting control or data flow. For example in this sequence:
+//
+//   %1 = add i32 %x, %y
+//   %2 = trunc i32 %1 to i16
+//
+// Only the lowest 16 bits of %1 are demanded; the rest are removed by the
+// trunc.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DEMANDED_BITS_H
+#define LLVM_ANALYSIS_DEMANDED_BITS_H
+
+#include "llvm/Pass.h"
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+
+namespace llvm {
+
+class FunctionPass;
+class Function;
+class Instruction;
+class DominatorTree;
+class AssumptionCache;
+
+struct DemandedBits : public FunctionPass {
+  static char ID; // Pass identification, replacement for typeid
+  DemandedBits();
+
+  bool runOnFunction(Function& F) override;
+  void getAnalysisUsage(AnalysisUsage& AU) const override;
+
+  /// Return the bits demanded from instruction I.
+  APInt getDemandedBits(Instruction *I);
+
+  /// Return true if I was analyzed and its demanded bits were determined.
+  bool demandedBitsKnown(Instruction *I);
+
+  /// Return true if, during analysis, I could not be reached.
+  bool isInstructionDead(Instruction *I);
+
+private:
+  void determineLiveOperandBits(const Instruction *UserI,
+                                const Instruction *I, unsigned OperandNo,
+                                const APInt &AOut, APInt &AB,
+                                APInt &KnownZero, APInt &KnownOne,
+                                APInt &KnownZero2, APInt &KnownOne2);
+
+  AssumptionCache *AC;
+  DominatorTree *DT;
+
+  // The set of visited instructions (non-integer-typed only).
+  SmallPtrSet<Instruction*, 128> Visited;
+  DenseMap<Instruction *, APInt> AliveBits;
+};
+
+/// Create a demanded bits analysis pass.
+FunctionPass *createDemandedBitsPass();
+
+} // End llvm namespace
+
+#endif

include/llvm/InitializePasses.h

 void initializeFloat2IntPass(PassRegistry&);
 void initializeLoopDistributePass(PassRegistry&);
 void initializeSjLjEHPreparePass(PassRegistry&);
+void initializeDemandedBitsPass(PassRegistry&);
 }
 
 #endif

lib/Analysis/Analysis.cpp

   initializeCFLAliasAnalysisPass(Registry);
   initializeDependenceAnalysisPass(Registry);
   initializeDelinearizationPass(Registry);
+  initializeDemandedBitsPass(Registry);
   initializeDivergenceAnalysisPass(Registry);
   initializeDominanceFrontierPass(Registry);
   initializeDomViewerPass(Registry);

lib/Analysis/CMakeLists.txt

   CodeMetrics.cpp
   ConstantFolding.cpp
   Delinearization.cpp
+  DemandedBits.cpp
   DependenceAnalysis.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp

lib/Analysis/DemandedBits.cpp

+//===---- DemandedBits.cpp - Determine demanded bits -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass implements a demanded bits analysis. A demanded bit is one that
+// contributes to a result; bits that are not demanded can be either zero or
+// one without affecting control or data flow. For example in this sequence:
+//
+//   %1 = add i32 %x, %y
+//   %2 = trunc i32 %1 to i16
+//
+// Only the lowest 16 bits of %1 are demanded; the rest are removed by the
+// trunc.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/DemandedBits.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "demanded-bits"
+
+char DemandedBits::ID = 0;
+INITIALIZE_PASS_BEGIN(DemandedBits, "demanded-bits", "Demanded bits analysis",
+                      false, false)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_END(DemandedBits, "demanded-bits", "Demanded bits analysis",
+      false, false)
+
+DemandedBits::DemandedBits() : FunctionPass(ID) {
+  initializeDemandedBitsPass(*PassRegistry::getPassRegistry());
+}
+
+
+void DemandedBits::getAnalysisUsage(AnalysisUsage& AU) const {
+  AU.setPreservesCFG();
+  AU.addRequired<AssumptionCacheTracker>();
+  AU.addRequired<DominatorTreeWrapperPass>();
+  AU.setPreservesAll();
+}
+
+static bool isAlwaysLive(Instruction *I) {
+  return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
+         isa<LandingPadInst>(I) || I->mayHaveSideEffects();
+}
+
+void
+DemandedBits::determineLiveOperandBits(const Instruction *UserI,
+               const Instruction *I, unsigned OperandNo,
+               const APInt &AOut, APInt &AB,
+               APInt &KnownZero, APInt &KnownOne,
+               APInt &KnownZero2, APInt &KnownOne2) {
+  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();
+        KnownZero = APInt(BitWidth, 0);
+        KnownOne = APInt(BitWidth, 0);
+        computeKnownBits(const_cast<Value *>(V1), KnownZero, KnownOne, DL, 0,
+                         AC, UserI, DT);
+
+        if (V2) {
+          KnownZero2 = APInt(BitWidth, 0);
+          KnownOne2 = APInt(BitWidth, 0);
+          computeKnownBits(const_cast<Value *>(V2), KnownZero2, KnownOne2, DL,
+                           0, AC, UserI, DT);
+        }
+      };
+
+  switch (UserI->getOpcode()) {
+  default: break;
+  case Instruction::Call:
+  case Instruction::Invoke:
+    if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
+      switch (II->getIntrinsicID()) {
+      default: break;
+      case Intrinsic::bswap:
+        // The alive bits of the input are the swapped alive bits of
+        // the output.
+        AB = AOut.byteSwap();
+        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);
+          AB = APInt::getHighBitsSet(BitWidth,
+                 std::min(BitWidth, KnownOne.countLeadingZeros()+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);
+          AB = APInt::getLowBitsSet(BitWidth,
+                 std::min(BitWidth, KnownOne.countTrailingZeros()+1));
+        }
+        break;
+      }
+    break;
+  case Instruction::Add:
+  case Instruction::Sub:
+    // Find the highest live output bit. We don't need any more input
+    // bits than that (adds, and thus subtracts, ripple only to the
+    // left).
+    AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
+    break;
+  case Instruction::Shl:
+    if (OperandNo == 0)
+      if (ConstantInt *CI =
+            dyn_cast<ConstantInt>(UserI->getOperand(1))) {
+        uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
+        AB = AOut.lshr(ShiftAmt);
+
+        // If the shift is nuw/nsw, then the high bits are not dead
+        // (because we've promised that they *must* be zero).
+        const ShlOperator *S = cast<ShlOperator>(UserI);
+        if (S->hasNoSignedWrap())
+          AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
+        else if (S->hasNoUnsignedWrap())
+          AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
+      }
+    break;
+  case Instruction::LShr:
+    if (OperandNo == 0)
+      if (ConstantInt *CI =
+            dyn_cast<ConstantInt>(UserI->getOperand(1))) {
+        uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
+        AB = AOut.shl(ShiftAmt);
+
+        // If the shift is exact, then the low bits are not dead
+        // (they must be zero).
+        if (cast<LShrOperator>(UserI)->isExact())
+          AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
+      }
+    break;
+  case Instruction::AShr:
+    if (OperandNo == 0)
+      if (ConstantInt *CI =
+            dyn_cast<ConstantInt>(UserI->getOperand(1))) {
+        uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
+        AB = AOut.shl(ShiftAmt);
+        // Because the high input bit is replicated into the
+        // high-order bits of the result, if we need any of those
+        // bits, then we must keep the highest input bit.
+        if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
+            .getBoolValue())
+          AB.setBit(BitWidth-1);
+
+        // If the shift is exact, then the low bits are not dead
+        // (they must be zero).
+        if (cast<AShrOperator>(UserI)->isExact())
+          AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
+      }
+    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));
+      AB &= ~KnownZero2;
+    } else {
+      if (!isa<Instruction>(UserI->getOperand(0)))
+        ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
+      AB &= ~(KnownZero & ~KnownZero2);
+    }
+    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));
+      AB &= ~KnownOne2;
+    } else {
+      if (!isa<Instruction>(UserI->getOperand(0)))
+        ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
+      AB &= ~(KnownOne & ~KnownOne2);
+    }
+    break;
+  case Instruction::Xor:
+  case Instruction::PHI:
+    AB = AOut;
+    break;
+  case Instruction::Trunc:
+    AB = AOut.zext(BitWidth);
+    break;
+  case Instruction::ZExt:
+    AB = AOut.trunc(BitWidth);
+    break;
+  case Instruction::SExt:
+    AB = AOut.trunc(BitWidth);
+    // Because the high input bit is replicated into the
+    // high-order bits of the result, if we need any of those
+    // bits, then we must keep the highest input bit.
+    if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
+                                      AOut.getBitWidth() - BitWidth))
+        .getBoolValue())
+      AB.setBit(BitWidth-1);
+    break;
+  case Instruction::Select:
+    if (OperandNo != 0)
+      AB = AOut;
+    break;
+  }
+}
+
+bool DemandedBits::runOnFunction(Function& F) {
+  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  Visited.clear();
+  AliveBits.clear();
+
+  SmallVector<Instruction*, 128> Worklist;
+
+  // Collect the set of "root" instructions that are known live.
+  for (Instruction &I : inst_range(F)) {
+    if (!isAlwaysLive(&I))
+      continue;
+
+    DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
+    // For integer-valued instructions, set up an initial empty set of alive
+    // bits and add the instruction to the work list. For other instructions
+    // add their operands to the work list (for integer values operands, mark
+    // all bits as live).
+    if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
+      if (!AliveBits.count(&I)) {
+        AliveBits[&I] = APInt(IT->getBitWidth(), 0);
+        Worklist.push_back(&I);
+      }
+
+      continue;
+    }
+
+    // Non-integer-typed instructions...
+    for (Use &OI : I.operands()) {
+      if (Instruction *J = dyn_cast<Instruction>(OI)) {
+        if (IntegerType *IT = dyn_cast<IntegerType>(J->getType()))
+          AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth());
+        Worklist.push_back(J);
+      }
+    }
+    // To save memory, we don't add I to the Visited set here. Instead, we
+    // check isAlwaysLive on every instruction when searching for dead
+    // instructions later (we need to check isAlwaysLive for the
+    // integer-typed instructions anyway).
+  }
+
+  // Propagate liveness backwards to operands.
+  while (!Worklist.empty()) {
+    Instruction *UserI = Worklist.pop_back_val();
+
+    DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
+    APInt AOut;
+    if (UserI->getType()->isIntegerTy()) {
+      AOut = AliveBits[UserI];
+      DEBUG(dbgs() << " Alive Out: " << AOut);
+    }
+    DEBUG(dbgs() << "\n");
+
+    if (!UserI->getType()->isIntegerTy())
+      Visited.insert(UserI);
+
+    APInt KnownZero, KnownOne, KnownZero2, KnownOne2;
+    // 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)) {
+        if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
+          unsigned BitWidth = IT->getBitWidth();
+          APInt AB = APInt::getAllOnesValue(BitWidth);
+          if (UserI->getType()->isIntegerTy() && !AOut &&
+              !isAlwaysLive(UserI)) {
+            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,
+                                     KnownZero, KnownOne,
+                                     KnownZero2, KnownOne2);
+          }
+
+          // 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);
+        }
+      }
+    }
+  }
+
+  return false;
+}
+
+APInt DemandedBits::getDemandedBits(Instruction *I) {
+  const DataLayout &DL = I->getParent()->getModule()->getDataLayout();
+  if (AliveBits.count(I))
+    return AliveBits[I];
+  return APInt::getAllOnesValue(DL.getTypeSizeInBits(I->getType()));
+}
+
+bool DemandedBits::demandedBitsKnown(Instruction *I) {
+  return AliveBits.find(I) != AliveBits.end();
+}
+
+bool DemandedBits::isInstructionDead(Instruction *I) {
+  return !Visited.count(I) && !isAlwaysLive(I);
+}
+
+FunctionPass *llvm::createDemandedBitsPass() {
+  return new DemandedBits();
+}

lib/Transforms/Scalar/BDCE.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar.h"
-#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/DepthFirstIterator.h"
-#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/ValueTracking.h"
-#include "llvm/IR/BasicBlock.h"
+#include "llvm/Analysis/DemandedBits.h"
 #include "llvm/IR/CFG.h"
-#include "llvm/IR/DataLayout.h"
-#include "llvm/IR/Dominators.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
-
 using namespace llvm;
 
 #define DEBUG_TYPE "bdce"

 
   void getAnalysisUsage(AnalysisUsage& AU) const override {
     AU.setPreservesCFG();
-    AU.addRequired<AssumptionCacheTracker>();
-    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<DemandedBits>();
   }
-
-  void determineLiveOperandBits(const Instruction *UserI,
-                                const Instruction *I, unsigned OperandNo,
-                                const APInt &AOut, APInt &AB,
-                                APInt &KnownZero, APInt &KnownOne,
-                                APInt &KnownZero2, APInt &KnownOne2);
-
-  AssumptionCache *AC;
-  DominatorTree *DT;
 };
 }
 
 char BDCE::ID = 0;
 INITIALIZE_PASS_BEGIN(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
                       false, false)
-INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
-INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DemandedBits)
 INITIALIZE_PASS_END(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
                     false, false)
 

          isa<LandingPadInst>(I) || I->mayHaveSideEffects();
 }
 
-void BDCE::determineLiveOperandBits(const Instruction *UserI,
-                                    const Instruction *I, unsigned OperandNo,
-                                    const APInt &AOut, APInt &AB,
-                                    APInt &KnownZero, APInt &KnownOne,
-                                    APInt &KnownZero2, APInt &KnownOne2) {
-  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();
-        KnownZero = APInt(BitWidth, 0);
-        KnownOne = APInt(BitWidth, 0);
-        computeKnownBits(const_cast<Value *>(V1), KnownZero, KnownOne, DL, 0,
-                         AC, UserI, DT);
-
-        if (V2) {
-          KnownZero2 = APInt(BitWidth, 0);
-          KnownOne2 = APInt(BitWidth, 0);
-          computeKnownBits(const_cast<Value *>(V2), KnownZero2, KnownOne2, DL,
-                           0, AC, UserI, DT);
-        }
-      };
-
-  switch (UserI->getOpcode()) {
-  default: break;
-  case Instruction::Call:
-  case Instruction::Invoke:
-    if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
-      switch (II->getIntrinsicID()) {
-      default: break;
-      case Intrinsic::bswap:
-        // The alive bits of the input are the swapped alive bits of
-        // the output.
-        AB = AOut.byteSwap();
-        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);
-          AB = APInt::getHighBitsSet(BitWidth,
-                 std::min(BitWidth, KnownOne.countLeadingZeros()+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);
-          AB = APInt::getLowBitsSet(BitWidth,
-                 std::min(BitWidth, KnownOne.countTrailingZeros()+1));
-        }
-        break;
-      }
-    break;
-  case Instruction::Add:
-  case Instruction::Sub:
-    // Find the highest live output bit. We don't need any more input
-    // bits than that (adds, and thus subtracts, ripple only to the
-    // left).
-    AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
-    break;
-  case Instruction::Shl:
-    if (OperandNo == 0)
-      if (ConstantInt *CI =
-            dyn_cast<ConstantInt>(UserI->getOperand(1))) {
-        uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
-        AB = AOut.lshr(ShiftAmt);
-
-        // If the shift is nuw/nsw, then the high bits are not dead
-        // (because we've promised that they *must* be zero).
-        const ShlOperator *S = cast<ShlOperator>(UserI);
-        if (S->hasNoSignedWrap())
-          AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
-        else if (S->hasNoUnsignedWrap())
-          AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
-      }
-    break;
-  case Instruction::LShr:
-    if (OperandNo == 0)
-      if (ConstantInt *CI =
-            dyn_cast<ConstantInt>(UserI->getOperand(1))) {
-        uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
-        AB = AOut.shl(ShiftAmt);
-
-        // If the shift is exact, then the low bits are not dead
-        // (they must be zero).
-        if (cast<LShrOperator>(UserI)->isExact())
-          AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
-      }
-    break;
-  case Instruction::AShr:
-    if (OperandNo == 0)
-      if (ConstantInt *CI =
-            dyn_cast<ConstantInt>(UserI->getOperand(1))) {
-        uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
-        AB = AOut.shl(ShiftAmt);
-        // Because the high input bit is replicated into the
-        // high-order bits of the result, if we need any of those
-        // bits, then we must keep the highest input bit.
-        if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
-            .getBoolValue())
-          AB.setBit(BitWidth-1);
-
-        // If the shift is exact, then the low bits are not dead
-        // (they must be zero).
-        if (cast<AShrOperator>(UserI)->isExact())
-          AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
-      }
-    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));
-      AB &= ~KnownZero2;
-    } else {
-      if (!isa<Instruction>(UserI->getOperand(0)))
-        ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
-      AB &= ~(KnownZero & ~KnownZero2);
-    }
-    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));
-      AB &= ~KnownOne2;
-    } else {
-      if (!isa<Instruction>(UserI->getOperand(0)))
-        ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
-      AB &= ~(KnownOne & ~KnownOne2);
-    }
-    break;
-  case Instruction::Xor:
-  case Instruction::PHI:
-    AB = AOut;
-    break;
-  case Instruction::Trunc:
-    AB = AOut.zext(BitWidth);
-    break;
-  case Instruction::ZExt:
-    AB = AOut.trunc(BitWidth);
-    break;
-  case Instruction::SExt:
-    AB = AOut.trunc(BitWidth);
-    // Because the high input bit is replicated into the
-    // high-order bits of the result, if we need any of those
-    // bits, then we must keep the highest input bit.
-    if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
-                                      AOut.getBitWidth() - BitWidth))
-        .getBoolValue())
-      AB.setBit(BitWidth-1);
-    break;
-  case Instruction::Select:
-    if (OperandNo != 0)
-      AB = AOut;
-    break;
-  }
-}
-
 bool BDCE::runOnFunction(Function& F) {
   if (skipOptnoneFunction(F))
     return false;
+  DemandedBits &DB = getAnalysis<DemandedBits>();
 
-  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
-  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-
-  DenseMap<Instruction *, APInt> AliveBits;
   SmallVector<Instruction*, 128> Worklist;
 
-  // The set of visited instructions (non-integer-typed only).
-  SmallPtrSet<Instruction*, 128> Visited;
-
-  // Collect the set of "root" instructions that are known live.
-  for (Instruction &I : inst_range(F)) {
-    if (!isAlwaysLive(&I))
-      continue;
-
-    DEBUG(dbgs() << "BDCE: Root: " << I << "\n");
-    // For integer-valued instructions, set up an initial empty set of alive
-    // bits and add the instruction to the work list. For other instructions
-    // add their operands to the work list (for integer values operands, mark
-    // all bits as live).
-    if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
-      if (!AliveBits.count(&I)) {
-        AliveBits[&I] = APInt(IT->getBitWidth(), 0);
-        Worklist.push_back(&I);
-      }
-
-      continue;
-    }
-
-    // Non-integer-typed instructions...
-    for (Use &OI : I.operands()) {
-      if (Instruction *J = dyn_cast<Instruction>(OI)) {
-        if (IntegerType *IT = dyn_cast<IntegerType>(J->getType()))
-          AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth());
-        Worklist.push_back(J);
-      }
-    }
-    // To save memory, we don't add I to the Visited set here. Instead, we
-    // check isAlwaysLive on every instruction when searching for dead
-    // instructions later (we need to check isAlwaysLive for the
-    // integer-typed instructions anyway).
-  }
-
-  // Propagate liveness backwards to operands.
-  while (!Worklist.empty()) {
-    Instruction *UserI = Worklist.pop_back_val();
-
-    DEBUG(dbgs() << "BDCE: Visiting: " << *UserI);
-    APInt AOut;
-    if (UserI->getType()->isIntegerTy()) {
-      AOut = AliveBits[UserI];
-      DEBUG(dbgs() << " Alive Out: " << AOut);
-    }
-    DEBUG(dbgs() << "\n");
-
-    if (!UserI->getType()->isIntegerTy())
-      Visited.insert(UserI);
-
-    APInt KnownZero, KnownOne, KnownZero2, KnownOne2;
-    // 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)) {
-        if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
-          unsigned BitWidth = IT->getBitWidth();
-          APInt AB = APInt::getAllOnesValue(BitWidth);
-          if (UserI->getType()->isIntegerTy() && !AOut &&
-              !isAlwaysLive(UserI)) {
-            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,
-                                     KnownZero, KnownOne,
-                                     KnownZero2, KnownOne2);
-          }
-
-          // 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);
-        }
-      }
-    }
-  }
-
   bool Changed = false;
   // The inverse of the live set is the dead set.  These are those instructions
   // which have no side effects and do not influence the control flow or return

     // 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.
     if (I.getType()->isIntegerTy()) {
-      auto ABI = AliveBits.find(&I);
-      if (ABI != AliveBits.end()) {
-        if (ABI->second.getBoolValue())
+      if (DB.demandedBitsKnown(&I)) {
+        if (DB.getDemandedBits(&I).getBoolValue())
           continue;
 
         DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");

         I.replaceAllUsesWith(Zero);
         Changed = true;
       }
-    } else if (Visited.count(&I)) {
+    } else if (!DB.isInstructionDead(&I)) {
       continue;
     }