A bit-tracking DCE Pass

[hfinkel]

Summary

This patch introduces a bit-tracking dead code elimination pass, it is based on ADCE (the "aggressive DCE" pass), with the added capability to track dead bits of integer valued instructions and remove those instructions when all of the bits are dead.

Currently, it does not actually do this all-bits-dead removal, but rather replaces the instruction's uses with a constant zero, and lets instcombine (and the later run of ADCE) do the rest. Because we essentially get a run of ADCE "for free" while tracking the dead bits, we also do what ADCE does and removes actually-dead instructions as well.

The motivation for this is a case like:

int __attribute__((const)) foo(int i);
int bar(int x) {
  x |= (4 & foo(5));
  x |= (8 & foo(3));
  x |= (16 & foo(2));
  x |= (32 & foo(1));
  x |= (64 & foo(0));
  x |= (128& foo(4));
  return x >> 4;
}

As it turns out, if you order the bit-field insertions so that all of the dead ones come last, then instcombine will remove them. However, if you pick some other order (such as the one above), the fact that some of the calls to foo() are useless is not locally obvious, and we don't remove them. I could not think of any current pass that "should" remove them, and so I created this one.

It is also possible to do other things with this pass, like "shrink" constant operands to or/and/xor when not all of the bits are required (this might not always be profitable, and we'd probably need to use TTI to make sure we were actually making the constant cheaper).

I did a quick compile-time overhead check using sqlite from the test suite (Release+Asserts). BDCE took ~0.4% of the compilation time (making it about twice as expensive as ADCE).

I've not looked at why yet, but we eliminate instructions due to having all-dead bits in:
External/SPEC/CFP2006/447.dealII/447.dealII
External/SPEC/CINT2006/400.perlbench/400.perlbench
External/SPEC/CINT2006/403.gcc/403.gcc
MultiSource/Applications/ClamAV/clamscan
MultiSource/Benchmarks/7zip/7zip-benchmark

P.S. I hacked this together in one day; criticism is expected. ;) [and more regression tests are certainly needed].

[sanjoy]

Quick first pass comments inline. I'm okay with this landing in tree with the comments addressed in some way or another, but I think I'll wait for someone else to give an explicit LGTM.

lib/Transforms/Scalar/BDCE.cpp

97

But if you're not the one removing the side-effecting instructions, they should not be removed anyway, right, even if their result is unused? In fact, I think it will be desirable to rewrite the result of foo() to be 0 if possible, even if foo() is a side-effecting call that cannot be removed.

143

[Minor] This is just my opinion, and does not stem form the LLVM style guide; but it'd be easier to tell where the for loop ended if you put braces around the body.

150

I don't think this is correct for side-effecting instructions.

214

Shouldn't this be AOut & ...?

267

Again, I think this should be AOut & ...

304

Am I right in understanding that this will delete %z in the
following case?

;; all i8
%z = add %x, %y
%z0 = and 0x0f, %z
%z1 = and 0xf0, %z0
side_effect(%z0)

Since you'll never visit %z as AliveBits[%z] will be 0?

In any case, a one-liner on how this is better than trivial DCE will be helpful.

[majnemer]

lib/Transforms/Scalar/BDCE.cpp

145

Pointer on the right hand side.

[hfinkel]

lib/Transforms/Scalar/BDCE.cpp

97

I had been using the setting of all bits to be live as the way to communicate that they'd not be removed.

You're right, however, that even if the call can't be removed, having an unnecessary dependency on the output is also not optimal. I'll change this.

143

I'll refactor this, I think.

150

Good point. Currently, all such instructions have all of their alive bits set, but if I change that, I'll need to change this too.

214

Heh, yes.

267

Yes.

304

Since you'll never visit %z as AliveBits[%z] will be 0?

No, because we set all of its alive bits in the first loop (as with all of the side-effecting instructions).

[hfinkel]

lib/Transforms/Scalar/BDCE.cpp

145

I don't understand. The RHS has OI, which is an Instruction::op_iterator, which is a Use*.

[hfinkel]

Updated to reflect Sanjoy's suggestions. We can now remove the dependence on a dead function return value even if we can't remove the function itself. I've added a test case for that.

Also, I chatted earlier with James, who suggested looking at how this relates to the implementation of InstCombiner::SimplifyDemandedUseBits. I did not see any obvious way of refactoring the logic there so that it could be reused here, but looking at the implementation did point out that I needed a few more lines of code to correctly handle nsw/nuw/exact flags on the shift operators. That's now been added too.

[hfinkel]

Added a few more regression tests.

[chandlerc]

FYI, my review is in progress.

[majnemer]

lib/Transforms/Scalar/BDCE.cpp

145

I was referring to your Instruction* I, I think it should be Instruction *I.

[hfinkel]

lib/Transforms/Scalar/BDCE.cpp

145

Agreed. (I think this was one of the copy-and-paste lines from ADCE; I'll need to remember to clean this up in both places).

[reames]

A few comments inline. As with Sanjoy, happy to see this evolve in tree.

lib/Transforms/Scalar/BDCE.cpp

95

You could you inst_range and a range for loop here

105

I don't get this line. Isn't the worklist of instructions, not of iterators?

111

Shouldn't you be adding I to Visited here?

143

This needs broken up into helper functions. It's hard to follow as is.

159

Having this switch pulled out into it's own function would help readability a lot.

326

Having this up near the top of the loop with an early might be more readable.

348

range-for?

368

Given we're not invalidating iterators here, can't these two loops be merged?

Also, why not do this step first and then delete the dead instruction in the previous loop?

Also, if the bits are dead, why not use undef?

[hfinkel]

FYI: A number of the review comments here apply to code copied from the ADCE pass (formatting, use of range-based fors, etc.). I've committed those changed to the ADCE pass (r229315 - r229319). I'll also incorporate those changes into the next version of this patch.

[jmolloy]

Hi Hal,

I'm looking at using very similar information in a pass I'm writing (live bits information). Would it be easy enough to move the AliveBits stuff into a utility class so it can be called from elsewhere?

Cheers,

James

[hfinkel]

In D7531#123922, @jmolloy wrote:

Hi Hal,

I'm looking at using very similar information in a pass I'm writing (live bits information). Would it be easy enough to move the AliveBits stuff into a utility class so it can be called from elsewhere?

Yes, I think we could separate the analysis part from the part that removes the completely-dead parts. If you can tell me, what are you working on?

Cheers,

James

[hfinkel]

lib/Transforms/Scalar/BDCE.cpp

95

Good point, will do.

105

This is left over from ADCE, which I've now fixed there. The iterators are convertable to Instruction*s. It is, however, unnecessary (doubly so after converting to a range-based for loop).

111

No need, we need to check isAlwaysLive on the instructions again anyway to determine whether or not to delete them. I've added a comment.

159

Fair enough; I'll pull this out.

326

Okay.

348

Yes.

368

We could do that (although, maybe we should also remove the all-dead-bits instructions).

Regarding undef, I considered that, but I'm somewhat afraid of that given our discussions recently regarding poison and undef.

[hfinkel]

Updated in response to review comments (using range-based fors, adjusting other formatting, refactoring, fusing ending loops, etc.).

[Still all one pass, analysis has not been split out into a separate pass yet].

[hfinkel]

In D7531#123925, @hfinkel wrote:

In D7531#123922, @jmolloy wrote:

Hi Hal,

I'm looking at using very similar information in a pass I'm writing (live bits information). Would it be easy enough to move the AliveBits stuff into a utility class so it can be called from elsewhere?

Yes, I think we could separate the analysis part from the part that removes the completely-dead parts. If you can tell me, what are you working on?

Upon further reflection, I'm not sure what the right refactoring for this would be. It could be an analysis pass, but it could also be a utility class exported from here. An actual analysis pass may not be particularly useful here because I don't think it would be likely to be preserved by any non-trivial transformation. I don't think there is any real way to "locally repair" the analysis after making a change (you could update it to get conservative answer, but because you never remove live bits under iteration, you'd not get the same answer as you might running the analysis from the beginning).

As a result, we might want to get this functionality in-tree, and then refactor it there.

Cheers,

James

[chandlerc]

Lots of nit-picky comments. Generally, this looks really nice. Have you profiled it? Have you tried to synthesize extreme test cases with very large integers to make sure this doesn't become *too* expensive?

I'm generally fine just landing this and sorting out these issues after the fact. Please commit, and sorry for the delay reviewing it.

lib/Transforms/Scalar/BDCE.cpp

45

clang-format doesn't indent things in an anonymous namespace, and I prefer that.

46

clang-format won't indent this, and that's my preference as well.

74

Accept 'Instruction &'?

94

Why accept const inputs just to cast it way?

96

'*I'?

97–99

This behavior doesn't really make sense. Maybe add a comment to the lambda to clarify what V1 and V2 are and why they would work this way?

258–259

Just dig it out of the module, simpler than using the analysis layer.

278–279

continue after this?

341

std::move?

Probably a few other places you might want to move here so that large APInt values don't trigger too many copies of a heap allocated set of bits.

361–363

Invert the conditions, use continue, and un-indent this?

365–367

Why not replace with undef?

380–382

Why not just erase the instructions? You can use the two-level iterators and pre-increment the iterator to avoid invalidation...

test/Transforms/BDCE/dce-pure.ll

6

The indentation (and weird comments) make my OCD-tendencies twitch.

[hfinkel]

In D7531#124045, @chandlerc wrote:

Lots of nit-picky comments. Generally, this looks really nice. Have you profiled it? Have you tried to synthesize extreme test cases with very large integers to make sure this doesn't become *too* expensive?

I've not profiled it in detail; I've checked compile-time overhead on a few key test cases (like sqlite), and saw nothing significant.

I'm generally fine just landing this and sorting out these issues after the fact. Please commit, and sorry for the delay reviewing it.

lib/Transforms/Scalar/BDCE.cpp

45

Will do (corresponding change made to ADCE in r229412).

94

To keep the casts localized to one place.

97–99

Will do. The general idea is that, we don't want to repeat the known-bits calculation for both operands at each operand.

258–259

Will do.

278–279

Sure.

341

Good point.

365–367

That's probably the right thing to do. However, given some of the discussion on poison/undef semantics, I'm not sure I want to do that. I've tried to stay away from cases here where the instructions themselves are trivial (like icmp sgt x, INT_MAX), but we *could* handle them here, and I'd like to test that change separately.

380–382

For the same reason that ADCE doesn't. The instructions themselves might not be trivially dead (there might be cyclic dependencies on other instructions that we'll visit here later, and the entire cycle will be removed). That's why this is done in two stages.

[hfinkel]

r229462; thanks everyone!

include/llvm-c/Transforms/Scalar.h

  * @ingroup LLVMCTransforms
  *
  * @{
  */
 
 /** See llvm::createAggressiveDCEPass function. */
 void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM);
 
+/** See llvm::createBitTrackingDCEPass function. */
+void LLVMAddBitTrackingDCEPass(LLVMPassManagerRef PM);
+
 /** See llvm::createAlignmentFromAssumptionsPass function. */
 void LLVMAddAlignmentFromAssumptionsPass(LLVMPassManagerRef PM);
 
 /** See llvm::createCFGSimplificationPass function. */
 void LLVMAddCFGSimplificationPass(LLVMPassManagerRef PM);
 
 /** See llvm::createDeadStoreEliminationPass function. */
 void LLVMAddDeadStoreEliminationPass(LLVMPassManagerRef PM);

include/llvm/InitializePasses.h

 void initializeCodeGen(PassRegistry&);
 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void initializeTarget(PassRegistry&);
 
 void initializeAAEvalPass(PassRegistry&);
 void initializeAddDiscriminatorsPass(PassRegistry&);
 void initializeADCEPass(PassRegistry&);
+void initializeBDCEPass(PassRegistry&);
 void initializeAliasAnalysisAnalysisGroup(PassRegistry&);
 void initializeAliasAnalysisCounterPass(PassRegistry&);
 void initializeAliasDebuggerPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlwaysInlinerPass(PassRegistry&);
 void initializeArgPromotionPass(PassRegistry&);
 void initializeAtomicExpandPass(PassRegistry&);
 void initializeSampleProfileLoaderPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       // delete it all as dead code, even with whole program optimization,
       // yet is effectively a NO-OP. As the compiler isn't smart enough
       // to know that getenv() never returns -1, this will do the job.
       if (std::getenv("bar") != (char*) -1)
         return;
 
       (void) llvm::createAAEvalPass();
       (void) llvm::createAggressiveDCEPass();
+      (void) llvm::createBitTrackingDCEPass();
       (void) llvm::createAliasAnalysisCounterPass();
       (void) llvm::createAliasDebugger();
       (void) llvm::createArgumentPromotionPass();
       (void) llvm::createAlignmentFromAssumptionsPass();
       (void) llvm::createBasicAliasAnalysisPass();
       (void) llvm::createLibCallAliasAnalysisPass(nullptr);
       (void) llvm::createScalarEvolutionAliasAnalysisPass();
       (void) llvm::createTypeBasedAliasAnalysisPass();

include/llvm/Transforms/Scalar.h

 // AggressiveDCE - This pass uses the SSA based Aggressive DCE algorithm.  This
 // algorithm assumes instructions are dead until proven otherwise, which makes
 // it more successful are removing non-obviously dead instructions.
 //
 FunctionPass *createAggressiveDCEPass();
 
 //===----------------------------------------------------------------------===//
 //
+// BitTrackingDCE - This pass uses a bit-tracking DCE algorithm in order to
+// remove computations of dead bits.
+//
+FunctionPass *createBitTrackingDCEPass();
+
+//===----------------------------------------------------------------------===//
+//
 // SROA - Replace aggregates or pieces of aggregates with scalar SSA values.
 //
 FunctionPass *createSROAPass(bool RequiresDomTree = true);
 
 //===----------------------------------------------------------------------===//
 //
 // ScalarReplAggregates - Break up alloca's of aggregates into multiple allocas
 // if possible.

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
   if (OptLevel > 1) {
     if (EnableMLSM)
       MPM.add(createMergedLoadStoreMotionPass()); // Merge ld/st in diamonds
     MPM.add(createGVNPass(DisableGVNLoadPRE));  // Remove redundancies
   }
   MPM.add(createMemCpyOptPass());             // Remove memcpy / form memset
   MPM.add(createSCCPPass());                  // Constant prop with SCCP
 
+  // Delete dead bit computations (instcombine runs after to fold away the dead
+  // computations, and then ADCE will run later to exploit any new DCE
+  // opportunities that creates).
+  MPM.add(createBitTrackingDCEPass());        // Delete dead bit computations
+
   // Run instcombine after redundancy elimination to exploit opportunities
   // opened up by them.
   MPM.add(createInstructionCombiningPass());
   addExtensionsToPM(EP_Peephole, MPM);
   MPM.add(createJumpThreadingPass());         // Thread jumps
   MPM.add(createCorrelatedValuePropagationPass());
   MPM.add(createDeadStoreEliminationPass());  // Delete dead stores
 

lib/Transforms/Scalar/BDCE.cpp

+//===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the Bit-Tracking Dead Code Elimination pass. Some
+// instructions (shifts, some ands, ors, etc.) kill some of their input bits.
+// We track these dead bits and remove instructions that compute only these
+// dead bits.
+//
+//===----------------------------------------------------------------------===//
+
+#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/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/Operator.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "bdce"
+
+STATISTIC(NumRemoved, "Number of instructions removed (unused)");
+STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
+
+namespace {
+  struct BDCE : public FunctionPass {
+    static char ID; // Pass identification, replacement for typeid
+    BDCE() : FunctionPass(ID) {
+      initializeBDCEPass(*PassRegistry::getPassRegistry());
+    }
+
+    bool runOnFunction(Function& F) override;
+
+    void getAnalysisUsage(AnalysisUsage& AU) const override {
+      AU.setPreservesCFG();
+      AU.addRequired<AssumptionCacheTracker>();
+      AU.addRequired<DominatorTreeWrapperPass>();
+    }
+
+    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;
+    const DataLayout *DL;
+    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_END(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
+                    false, false)
+
+static bool isAlwaysLive(Instruction *I) {
+  return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
+         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();
+  auto ComputeKnownBits = [&](unsigned BitWidth, const Value *V1,
+                              const Value *V2) {
+    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;
+
+  AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
+  DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
+  DL = DLP ? &DLP->getDataLayout() : nullptr;
+  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;
+
+    // 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())) {
+      AliveBits[&I] = APInt(IT->getBitWidth(), 0);
+      Worklist.push_back(&I);
+    } else {
+      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] = 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
+  // value of the function, and may therefore be deleted safely.
+  // NOTE: We reuse the Worklist vector here for memory efficiency.
+  for (Instruction &I : inst_range(F)) {
+    // 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.
+    if (I.getType()->isIntegerTy()) {
+      auto ABI = AliveBits.find(&I);
+      if (ABI != AliveBits.end()) {
+        if (!ABI->second) {
+          DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");
+          Value *Zero = ConstantInt::get(I.getType(), 0);
+          ++NumSimplified;
+          I.replaceAllUsesWith(Zero);
+          Changed = true;
+        } else {
+          continue;
+        }
+      }
+    } else if (Visited.count(&I)) {
+      continue;
+    }
+
+    if (isAlwaysLive(&I))
+      continue;
+
+    DEBUG(dbgs() << "BDCE: Removing: " << I << " (unused)\n");
+    Worklist.push_back(&I);
+    I.dropAllReferences();
+    Changed = true;
+  }
+
+  for (Instruction *&I : Worklist) {
+    ++NumRemoved;
+    I->eraseFromParent();
+  }
+
+  return Changed;
+}
+
+FunctionPass *llvm::createBitTrackingDCEPass() {
+  return new BDCE();
+}
+

lib/Transforms/Scalar/CMakeLists.txt

 add_llvm_library(LLVMScalarOpts
   ADCE.cpp
   AlignmentFromAssumptions.cpp
+  BDCE.cpp
   ConstantHoisting.cpp
   ConstantProp.cpp
   CorrelatedValuePropagation.cpp
   DCE.cpp
   DeadStoreElimination.cpp
   EarlyCSE.cpp
   FlattenCFGPass.cpp
   GVN.cpp

lib/Transforms/Scalar/Scalar.cpp

 #include "llvm/IR/LegacyPassManager.h"
 
 using namespace llvm;
 
 /// initializeScalarOptsPasses - Initialize all passes linked into the
 /// ScalarOpts library.
 void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeADCEPass(Registry);
+  initializeBDCEPass(Registry);
   initializeAlignmentFromAssumptionsPass(Registry);
   initializeSampleProfileLoaderPass(Registry);
   initializeConstantHoistingPass(Registry);
   initializeConstantPropagationPass(Registry);
   initializeCorrelatedValuePropagationPass(Registry);
   initializeDCEPass(Registry);
   initializeDeadInstEliminationPass(Registry);
   initializeScalarizerPass(Registry);

 void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) {
   initializeScalarOpts(*unwrap(R));
 }
 
 void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createAggressiveDCEPass());
 }
 
+void LLVMAddBitTrackingDCEPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createBitTrackingDCEPass());
+}
+
 void LLVMAddAlignmentFromAssumptionsPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createAlignmentFromAssumptionsPass());
 }
 
 void LLVMAddCFGSimplificationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createCFGSimplificationPass());
 }
 

test/Transforms/BDCE/basic.ll

+; RUN: opt -S -bdce -instsimplify < %s | FileCheck %s
+; RUN: opt -S -instsimplify < %s | FileCheck %s -check-prefix=CHECK-IO
+target datalayout = "E-m:e-i64:64-n32:64"
+target triple = "powerpc64-unknown-linux-gnu"
+
+; Function Attrs: nounwind readnone
+define signext i32 @bar(i32 signext %x) #0 {
+entry:
+  %call = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call, 4
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @foo(i32 signext 3) #0
+  %and2 = and i32 %call1, 8
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @foo(i32 signext 2) #0
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @foo(i32 signext 1) #0
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @foo(i32 signext 0) #0
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @foo(i32 signext 4) #0
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %shr = ashr i32 %or15, 4
+  ret i32 %shr
+
+; CHECK-LABEL: @bar
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 2)
+; CHECK: tail call signext i32 @foo(i32 signext 1)
+; CHECK: tail call signext i32 @foo(i32 signext 0)
+; CHECK: tail call signext i32 @foo(i32 signext 4)
+; CHECK: ret i32
+
+; Check that instsimplify is not doing this all on its own.
+; CHECK-IO-LABEL: @bar
+; CHECK-IO: tail call signext i32 @foo(i32 signext 5)
+; CHECK-IO: tail call signext i32 @foo(i32 signext 3)
+; CHECK-IO: tail call signext i32 @foo(i32 signext 2)
+; CHECK-IO: tail call signext i32 @foo(i32 signext 1)
+; CHECK-IO: tail call signext i32 @foo(i32 signext 0)
+; CHECK-IO: tail call signext i32 @foo(i32 signext 4)
+; CHECK-IO: ret i32
+}
+
+; Function Attrs: nounwind readnone
+declare signext i32 @foo(i32 signext) #0
+
+; Function Attrs: nounwind readnone
+define signext i32 @far(i32 signext %x) #1 {
+entry:
+  %call = tail call signext i32 @goo(i32 signext 5) #1
+  %and = and i32 %call, 4
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @goo(i32 signext 3) #1
+  %and2 = and i32 %call1, 8
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @goo(i32 signext 2) #1
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @goo(i32 signext 1) #1
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @goo(i32 signext 0) #1
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @goo(i32 signext 4) #1
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %shr = ashr i32 %or15, 4
+  ret i32 %shr
+
+; CHECK-LABEL: @far
+; Calls to foo(5) and foo(3) are still there, but their results are not used.
+; CHECK: tail call signext i32 @goo(i32 signext 5)
+; CHECK-NEXT: tail call signext i32 @goo(i32 signext 3)
+; CHECK-NEXT: tail call signext i32 @goo(i32 signext 2)
+; CHECK: tail call signext i32 @goo(i32 signext 1)
+; CHECK: tail call signext i32 @goo(i32 signext 0)
+; CHECK: tail call signext i32 @goo(i32 signext 4)
+; CHECK: ret i32
+
+; Check that instsimplify is not doing this all on its own.
+; CHECK-IO-LABEL: @far
+; CHECK-IO: tail call signext i32 @goo(i32 signext 5)
+; CHECK-IO: tail call signext i32 @goo(i32 signext 3)
+; CHECK-IO: tail call signext i32 @goo(i32 signext 2)
+; CHECK-IO: tail call signext i32 @goo(i32 signext 1)
+; CHECK-IO: tail call signext i32 @goo(i32 signext 0)
+; CHECK-IO: tail call signext i32 @goo(i32 signext 4)
+; CHECK-IO: ret i32
+}
+
+declare signext i32 @goo(i32 signext) #1
+
+; Function Attrs: nounwind readnone
+define signext i32 @tar1(i32 signext %x) #0 {
+entry:
+  %call = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call, 33554432
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @foo(i32 signext 3) #0
+  %and2 = and i32 %call1, 67108864
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @foo(i32 signext 2) #0
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @foo(i32 signext 1) #0
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @foo(i32 signext 0) #0
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @foo(i32 signext 4) #0
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %bs = tail call i32 @llvm.bswap.i32(i32 %or15) #0
+  %shr = ashr i32 %bs, 4
+  ret i32 %shr
+
+; CHECK-LABEL: @tar1
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 2)
+; CHECK: tail call signext i32 @foo(i32 signext 1)
+; CHECK: tail call signext i32 @foo(i32 signext 0)
+; CHECK: tail call signext i32 @foo(i32 signext 4)
+; CHECK: ret i32
+}
+
+; Function Attrs: nounwind readnone
+declare i32 @llvm.bswap.i32(i32) #0
+
+; Function Attrs: nounwind readnone
+define signext i32 @tar2(i32 signext %x) #0 {
+entry:
+  %call = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call, 33554432
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @foo(i32 signext 3) #0
+  %and2 = and i32 %call1, 67108864
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @foo(i32 signext 2) #0
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @foo(i32 signext 1) #0
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @foo(i32 signext 0) #0
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @foo(i32 signext 4) #0
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %shl = shl i32 %or15, 10
+  ret i32 %shl
+
+; CHECK-LABEL: @tar2
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 2)
+; CHECK: tail call signext i32 @foo(i32 signext 1)
+; CHECK: tail call signext i32 @foo(i32 signext 0)
+; CHECK: tail call signext i32 @foo(i32 signext 4)
+; CHECK: ret i32
+}
+
+; Function Attrs: nounwind readnone
+define signext i32 @tar3(i32 signext %x) #0 {
+entry:
+  %call = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call, 33554432
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @foo(i32 signext 3) #0
+  %and2 = and i32 %call1, 67108864
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @foo(i32 signext 2) #0
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @foo(i32 signext 1) #0
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @foo(i32 signext 0) #0
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @foo(i32 signext 4) #0
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %add = add i32 %or15, 5
+  %shl = shl i32 %add, 10
+  ret i32 %shl
+
+; CHECK-LABEL: @tar3
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 2)
+; CHECK: tail call signext i32 @foo(i32 signext 1)
+; CHECK: tail call signext i32 @foo(i32 signext 0)
+; CHECK: tail call signext i32 @foo(i32 signext 4)
+; CHECK: ret i32
+}
+
+; Function Attrs: nounwind readnone
+define signext i32 @tar4(i32 signext %x) #0 {
+entry:
+  %call = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call, 33554432
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @foo(i32 signext 3) #0
+  %and2 = and i32 %call1, 67108864
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @foo(i32 signext 2) #0
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @foo(i32 signext 1) #0
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @foo(i32 signext 0) #0
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @foo(i32 signext 4) #0
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %sub = sub i32 %or15, 5
+  %shl = shl i32 %sub, 10
+  ret i32 %shl
+
+; CHECK-LABEL: @tar4
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 2)
+; CHECK: tail call signext i32 @foo(i32 signext 1)
+; CHECK: tail call signext i32 @foo(i32 signext 0)
+; CHECK: tail call signext i32 @foo(i32 signext 4)
+; CHECK: ret i32
+}
+
+; Function Attrs: nounwind readnone
+define signext i32 @tar5(i32 signext %x) #0 {
+entry:
+  %call = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call, 33554432
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @foo(i32 signext 3) #0
+  %and2 = and i32 %call1, 67108864
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @foo(i32 signext 2) #0
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @foo(i32 signext 1) #0
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @foo(i32 signext 0) #0
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @foo(i32 signext 4) #0
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %xor = xor i32 %or15, 5
+  %shl = shl i32 %xor, 10
+  ret i32 %shl
+
+; CHECK-LABEL: @tar5
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 2)
+; CHECK: tail call signext i32 @foo(i32 signext 1)
+; CHECK: tail call signext i32 @foo(i32 signext 0)
+; CHECK: tail call signext i32 @foo(i32 signext 4)
+; CHECK: ret i32
+}
+
+; Function Attrs: nounwind readnone
+define signext i32 @tar7(i32 signext %x, i1 %b) #0 {
+entry:
+  %call = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call, 33554432
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @foo(i32 signext 3) #0
+  %and2 = and i32 %call1, 67108864
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @foo(i32 signext 2) #0
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @foo(i32 signext 1) #0
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @foo(i32 signext 0) #0
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @foo(i32 signext 4) #0
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %v = select i1 %b, i32 %or15, i32 5
+  %shl = shl i32 %v, 10
+  ret i32 %shl
+
+; CHECK-LABEL: @tar7
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 2)
+; CHECK: tail call signext i32 @foo(i32 signext 1)
+; CHECK: tail call signext i32 @foo(i32 signext 0)
+; CHECK: tail call signext i32 @foo(i32 signext 4)
+; CHECK: ret i32
+}
+
+; Function Attrs: nounwind readnone
+define signext i16 @tar8(i32 signext %x) #0 {
+entry:
+  %call = tail call signext i32 @foo(i32 signext 5) #0
+  %and = and i32 %call, 33554432
+  %or = or i32 %and, %x
+  %call1 = tail call signext i32 @foo(i32 signext 3) #0
+  %and2 = and i32 %call1, 67108864
+  %or3 = or i32 %or, %and2
+  %call4 = tail call signext i32 @foo(i32 signext 2) #0
+  %and5 = and i32 %call4, 16
+  %or6 = or i32 %or3, %and5
+  %call7 = tail call signext i32 @foo(i32 signext 1) #0
+  %and8 = and i32 %call7, 32
+  %or9 = or i32 %or6, %and8
+  %call10 = tail call signext i32 @foo(i32 signext 0) #0
+  %and11 = and i32 %call10, 64
+  %or12 = or i32 %or9, %and11
+  %call13 = tail call signext i32 @foo(i32 signext 4) #0
+  %and14 = and i32 %call13, 128
+  %or15 = or i32 %or12, %and14
+  %tr = trunc i32 %or15 to i16
+  ret i16 %tr
+
+; CHECK-LABEL: @tar8
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 5)
+; CHECK-NOT: tail call signext i32 @foo(i32 signext 3)
+; CHECK: tail call signext i32 @foo(i32 signext 2)
+; CHECK: tail call signext i32 @foo(i32 signext 1)
+; CHECK: tail call signext i32 @foo(i32 signext 0)
+; CHECK: tail call signext i32 @foo(i32 signext 4)
+; CHECK: ret i16
+}
+
+attributes #0 = { nounwind readnone }
+attributes #1 = { nounwind }
+

test/Transforms/BDCE/dce-pure.ll

+; RUN: opt -bdce -S < %s | FileCheck %s
+
+declare i32 @strlen(i8*) readonly nounwind
+
+define void @test1() {
+        call i32 @strlen( i8* null )                ; <i32>:1 [#uses=0]
+        ret void
+
+; CHECK-LABEL: @test1
+; CHECK-NOT: call
+; CHECK: ret void
+}
+
+define i32 @test2() {
+        ; invoke of pure function should not be deleted!
+        invoke i32 @strlen( i8* null ) readnone
+                        to label %Cont unwind label %Other              ; <i32>:1 [#uses=0]
+
+Cont:           ; preds = %0
+        ret i32 0
+
+Other:          ; preds = %0
+         %exn = landingpad {i8*, i32} personality i32 (...)* @__gxx_personality_v0
+                  cleanup
+        ret i32 1
+
+; CHECK-LABEL: @test2
+; CHECK: invoke
+; CHECK: ret i32 1
+}
+
+declare i32 @__gxx_personality_v0(...)
+