[DemandedBits][BDCE] Support vectors of integers

[nikic]

Summary

This came up during D54876. DemandedBits and BDCE currently only support scalar integers. This patch extends them to also handle vector integer operations. In this case the demanded bits are tracked for all lanes at once (as is done for known bits and demanded bits analyses in other places).

The implementation is mostly a matter of going from isIntegerTy to isIntOrIntVectorTy and switching some ConstantInt dyn_casts to use match instead.

I think the main notable change here from an API perspective is that the getDemandedBits() method now a) requires the instruction to have an int/vec-of-int type and b) returns a "scalar size in bits" value. Previously it allowed any sized instruction and returned a "type size in bits" value. In particular, for vectors this method would have previously returned a num elements * scalar size large value (of 1s). I checked existing uses of getDemandedBits() and from what I can determine none will be invoked on anything other than integer instructions. Only BDCE passed non-integer instructions to it sometimes, but that's also adjusted as part of this patch.

[hfinkel]

test/Analysis/DemandedBits/vectors.ll

7

I'm missing something here. Shouldn't there be two groups of demanded bits here, one group per vector lane, so that the overall demanded bits looks something like: 0x000000ff000000ff?

[nikic]

test/Analysis/DemandedBits/vectors.ll

7

The demanded bits are tracked for all vector lanes together. A bit is demanded if it is demanded in any of the vector lanes.

Other passes that do similar things (computeKnownBits in ValueTracking and SimplifyDemandedBits in InstCombine) take the same approach. I assume that because it's usually not worth the additional computational cost (and in this case also memory usage) to track bits for individual lanes. It also simplifies things for consumers of the analysis, as it allows treating scalar and vectors in the same way.

[RKSimon]

test/Analysis/DemandedBits/vectors.ll

7

I raised https://bugs.llvm.org/show_bug.cgi?id=36319 about at least adding the same DemandedElts argument support to ValueTracking that we have with the SelectionDAG computeKnownBits/ComputeNumSignBits equivalents.

I have toyed with the idea of adding a DemandedElts argument to SimplifyDemandedBits as well but haven't pursued it yet (so not completely "per bit" but at least limited to shared demandedbits from the vector elements we care about).

[nikic]

test/Analysis/DemandedBits/vectors.ll

7

That's interesting, I wasn't aware that SelectionDAG also tracks demanded elements. This is probably more valuable for cases where you look at a single use-site (what computeKnownBits does) than an analysis such as this one (which considers the whole function, so e.g. all extractelements will end up as demanded elements, with no distinction for which one demands what).

[hfinkel]

This LGTM. However, please, in llvm/Analysis/DemandedBits.h, document what this means for vectors (that it treats all elements the same and returns a mask of the scalar size). You might expand on the comment:

/// Return the bits demanded from instruction I.
APInt getDemandedBits(Instruction *I);

[nikic]

Reverted this shortly afterwards via rL348558 due to assertion failures, so reopening this revision.

[nikic]

Remove the requirement that the instruction passed to getDemandedBits() must have integer or vector of integer type. While the analysis only deals with these instructions, it is more convenient for consuming code to not have type restrictions.

Add a LoopVectorize test case which triggered an assertion with the previous implementation, as it called getDemandedBits() on a pointer-typed instruction.

[hfinkel]

LGTM

lib/Analysis/DemandedBits.cpp

 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cstdint>
 
 using namespace llvm;
+using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "demanded-bits"
 
 char DemandedBitsWrapperPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(DemandedBitsWrapperPass, "demanded-bits",
                       "Demanded bits analysis", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
           // 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, Known.countMaxTrailingZeros()+1));
         }
         break;
       case Intrinsic::fshl:
-      case Intrinsic::fshr:
+      case Intrinsic::fshr: {
+        const APInt *SA;
         if (OperandNo == 2) {
           // Shift amount is modulo the bitwidth. For powers of two we have
           // SA % BW == SA & (BW - 1).
           if (isPowerOf2_32(BitWidth))
             AB = BitWidth - 1;
-        } else if (auto *SA = dyn_cast<ConstantInt>(II->getOperand(2))) {
-          // TODO: Support vectors.
+        } else if (match(II->getOperand(2), m_APInt(SA))) {
           // Normalize to funnel shift left. APInt shifts of BitWidth are well-
           // defined, so no need to special-case zero shifts here.
-          uint64_t ShiftAmt = SA->getValue().urem(BitWidth);
+          uint64_t ShiftAmt = SA->urem(BitWidth);
           if (II->getIntrinsicID() == Intrinsic::fshr)
             ShiftAmt = BitWidth - ShiftAmt;
 
           if (OperandNo == 0)
             AB = AOut.lshr(ShiftAmt);
           else if (OperandNo == 1)
             AB = AOut.shl(BitWidth - ShiftAmt);
         }
         break;
       }
+      }
     break;
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Mul:
     // 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 (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
+    if (OperandNo == 0) {
+      const APInt *ShiftAmtC;
+      if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
         uint64_t ShiftAmt = ShiftAmtC->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 (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
+    if (OperandNo == 0) {
+      const APInt *ShiftAmtC;
+      if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
         uint64_t ShiftAmt = ShiftAmtC->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 (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
+    if (OperandNo == 0) {
+      const APInt *ShiftAmtC;
+      if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
         uint64_t ShiftAmt = ShiftAmtC->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.setSignBit();
 
         // 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 ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
                                       AOut.getBitWidth() - BitWidth))
         .getBoolValue())
       AB.setSignBit();
     break;
   case Instruction::Select:
     if (OperandNo != 0)
       AB = AOut;
     break;
+  case Instruction::ExtractElement:
+    if (OperandNo == 0)
+      AB = AOut;
+    break;
+  case Instruction::InsertElement:
+  case Instruction::ShuffleVector:
+    if (OperandNo == 0 || OperandNo == 1)
+      AB = AOut;
+    break;
   }
 }
 
 bool DemandedBitsWrapperPass::runOnFunction(Function &F) {
   auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   DB.emplace(F, AC, DT);
   return false;
for (Instruction &I : instructions(F)) {
     if (!isAlwaysLive(&I))
       continue;
 
     LLVM_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.try_emplace(&I, IT->getBitWidth(), 0).second)
+    Type *T = I.getType();
+    if (T->isIntOrIntVectorTy()) {
+      if (AliveBits.try_emplace(&I, T->getScalarSizeInBits(), 0).second)
         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());
+        Type *T = J->getType();
+        if (T->isIntOrIntVectorTy())
+          AliveBits[J] = APInt::getAllOnesValue(T->getScalarSizeInBits());
         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();
 
     LLVM_DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
     APInt AOut;
-    if (UserI->getType()->isIntegerTy()) {
+    if (UserI->getType()->isIntOrIntVectorTy()) {
       AOut = AliveBits[UserI];
       LLVM_DEBUG(dbgs() << " Alive Out: " << AOut);
     }
     LLVM_DEBUG(dbgs() << "\n");
 
-    if (!UserI->getType()->isIntegerTy())
+    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)) {
-        if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
-          unsigned BitWidth = IT->getBitWidth();
+        Type *T = I->getType();
+        if (T->isIntOrIntVectorTy()) {
+          unsigned BitWidth = T->getScalarSizeInBits();
           APInt AB = APInt::getAllOnesValue(BitWidth);
-          if (UserI->getType()->isIntegerTy() && !AOut &&
+          if (UserI->getType()->isIntOrIntVectorTy() && !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,
                                      Known, Known2);
for (Use &OI : UserI->operands()) {
           Worklist.push_back(I);
         }
       }
     }
   }
 }
 
 APInt DemandedBits::getDemandedBits(Instruction *I) {
-  performAnalysis();
+  assert(I->getType()->isIntOrIntVectorTy() &&
+         "Not an integer or vector of integer instruction");
 
-  const DataLayout &DL = I->getModule()->getDataLayout();
+  performAnalysis();
   auto Found = AliveBits.find(I);
   if (Found != AliveBits.end())
     return Found->second;
-  return APInt::getAllOnesValue(DL.getTypeSizeInBits(I->getType()));
+  return APInt::getAllOnesValue(I->getType()->getScalarSizeInBits());
 }
 
 bool DemandedBits::isInstructionDead(Instruction *I) {
   performAnalysis();
 
   return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
     !isAlwaysLive(I);
 }

lib/Transforms/Scalar/BDCE.cpp

 
 STATISTIC(NumRemoved, "Number of instructions removed (unused)");
 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
 
 /// If an instruction is trivialized (dead), then the chain of users of that
 /// instruction may need to be cleared of assumptions that can no longer be
 /// guaranteed correct.
 static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) {
-  assert(I->getType()->isIntegerTy() && "Trivializing a non-integer value?");
+  assert(I->getType()->isIntOrIntVectorTy() &&
+         "Trivializing a non-integer value?");
 
   // Initialize the worklist with eligible direct users.
   SmallVector<Instruction *, 16> WorkList;
   for (User *JU : I->users()) {
     // If all bits of a user are demanded, then we know that nothing below that
     // in the def-use chain needs to be changed.
     auto *J = dyn_cast<Instruction>(JU);
-    if (J && J->getType()->isSized() &&
+    if (J && J->getType()->isIntOrIntVectorTy() &&
         !DB.getDemandedBits(J).isAllOnesValue())
       WorkList.push_back(J);
 
-    // Note that we need to check for unsized types above before asking for
+    // Note that we need to check for non-int types above before asking for
     // demanded bits. Normally, the only way to reach an instruction with an
-    // unsized type is via an instruction that has side effects (or otherwise
+    // non-int type is via an instruction that has side effects (or otherwise
     // will demand its input bits). However, if we have a readnone function
     // that returns an unsized type (e.g., void), we must avoid asking for the
     // demanded bits of the function call's return value. A void-returning
     // readnone function is always dead (and so we can stop walking the use/def
     // chain here), but the check is necessary to avoid asserting.
   }
 
   // DFS through subsequent users while tracking visits to avoid cycles.
while (!WorkList.empty()) {
     // 2. range metadata only applies to memory accesses which demand all bits.
 
     Visited.insert(J);
 
     for (User *KU : J->users()) {
       // If all bits of a user are demanded, then we know that nothing below
       // that in the def-use chain needs to be changed.
       auto *K = dyn_cast<Instruction>(KU);
-      if (K && !Visited.count(K) && K->getType()->isSized() &&
+      if (K && !Visited.count(K) && K->getType()->isIntOrIntVectorTy() &&
           !DB.getDemandedBits(K).isAllOnesValue())
         WorkList.push_back(K);
     }
   }
 }
 
 static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
   SmallVector<Instruction*, 128> Worklist;
   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()->isIntegerTy() &&
+    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");
 
       clearAssumptionsOfUsers(&I, DB);
 

test/Analysis/DemandedBits/vectors.ll

+; RUN: opt -S -demanded-bits -analyze < %s | FileCheck %s
+; RUN: opt -S -disable-output -passes="print<demanded-bits>" < %s 2>&1 | FileCheck %s
+ 
+; CHECK-DAG: DemandedBits: 0xff00 for   %x = or <2 x i32> %a, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xff00 for   %y = or <2 x i32> %b, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xff00 for   %z = or <2 x i32> %x, %y
+; CHECK-DAG: DemandedBits: 0xff for   %u = lshr <2 x i32> %z, <i32 8, i32 8>
+; CHECK-DAG: DemandedBits: 0xff for   %r = trunc <2 x i32> %u to <2 x i8>
+define <2 x i8> @test_basic(<2 x i32> %a, <2 x i32> %b) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %y = or <2 x i32> %b, zeroinitializer
+  %z = or <2 x i32> %x, %y
+  %u = lshr <2 x i32> %z, <i32 8, i32 8>
+  %r = trunc <2 x i32> %u to <2 x i8>
+  ret <2 x i8> %r
+}
+
+; Vector-specific instructions
+
+; CHECK-DAG: DemandedBits: 0xff for   %x = or <2 x i32> %a, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xf0 for   %z = extractelement <2 x i32> %x, i32 1
+; CHECK-DAG: DemandedBits: 0xf for   %y = extractelement <2 x i32> %x, i32 0
+; CHECK-DAG: DemandedBits: 0xffffffff for   %u = and i32 %y, 15
+; CHECK-DAG: DemandedBits: 0xffffffff for   %v = and i32 %z, 240
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = or i32 %u, %v
+define i32 @test_extractelement(<2 x i32> %a) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %y = extractelement <2 x i32> %x, i32 0
+  %z = extractelement <2 x i32> %x, i32 1
+  %u = and i32 %y, 15
+  %v = and i32 %z, 240
+  %r = or i32 %u, %v
+  ret i32 %r
+}
+
+; CHECK-DAG: DemandedBits: 0xff for   %x = or i32 %a, 0
+; CHECK-DAG: DemandedBits: 0xff for   %y = or i32 %b, 0
+; CHECK-DAG: DemandedBits: 0xff for   %z = insertelement <2 x i32> undef, i32 %x, i32 0
+; CHECK-DAG: DemandedBits: 0xff for   %u = insertelement <2 x i32> %z, i32 %y, i32 1
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and <2 x i32> %u, <i32 255, i32 127>
+define <2 x i32> @test_insertelement(i32 %a, i32 %b) {
+  %x = or i32 %a, 0
+  %y = or i32 %b, 0
+  %z = insertelement <2 x i32> undef, i32 %x, i32 0
+  %u = insertelement <2 x i32> %z, i32 %y, i32 1
+  %r = and <2 x i32> %u, <i32 255, i32 127>
+  ret <2 x i32> %r
+}
+
+; CHECK-DAG: DemandedBits: 0xff for   %x = or <2 x i32> %a, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xff for   %y = or <2 x i32> %b, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xff for   %z = shufflevector <2 x i32> %x, <2 x i32> %y, <3 x i32> <i32 0, i32 3, i32 1>
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and <3 x i32> %z, <i32 255, i32 127, i32 0>
+define <3 x i32> @test_shufflevector(<2 x i32> %a, <2 x i32> %b) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %y = or <2 x i32> %b, zeroinitializer
+  %z = shufflevector <2 x i32> %x, <2 x i32> %y, <3 x i32> <i32 0, i32 3, i32 1>
+  %r = and <3 x i32> %z, <i32 255, i32 127, i32 0>
+  ret <3 x i32> %r
+}
+
+; Shifts with splat shift amounts
+
+; CHECK-DAG: DemandedBits: 0xf for   %x = or <2 x i32> %a, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xf0 for   %y = shl <2 x i32> %x, <i32 4, i32 4>
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and <2 x i32> %y, <i32 240, i32 240>
+define <2 x i32> @test_shl(<2 x i32> %a) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %y = shl <2 x i32> %x, <i32 4, i32 4>
+  %r = and <2 x i32> %y, <i32 240, i32 240>
+  ret <2 x i32> %r
+}
+
+; CHECK-DAG: DemandedBits: 0xf00 for   %x = or <2 x i32> %a, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xf0 for   %y = ashr <2 x i32> %x, <i32 4, i32 4>
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and <2 x i32> %y, <i32 240, i32 240>
+define <2 x i32> @test_ashr(<2 x i32> %a) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %y = ashr <2 x i32> %x, <i32 4, i32 4>
+  %r = and <2 x i32> %y, <i32 240, i32 240>
+  ret <2 x i32> %r
+}
+
+; CHECK-DAG: DemandedBits: 0xf00 for   %x = or <2 x i32> %a, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xf0 for   %y = lshr <2 x i32> %x, <i32 4, i32 4>
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and <2 x i32> %y, <i32 240, i32 240>
+define <2 x i32> @test_lshr(<2 x i32> %a) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %y = lshr <2 x i32> %x, <i32 4, i32 4>
+  %r = and <2 x i32> %y, <i32 240, i32 240>
+  ret <2 x i32> %r
+}
+
+declare <2 x i32> @llvm.fshl.i32(<2 x i32>, <2 x i32>, <2 x i32>)
+declare <2 x i32> @llvm.fshr.i32(<2 x i32>, <2 x i32>, <2 x i32>)
+
+; CHECK-DAG: DemandedBits: 0xf for   %x = or <2 x i32> %a, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xf0000000 for   %y = or <2 x i32> %b, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xff for   %z = call <2 x i32> @llvm.fshl.v2i32(<2 x i32> %x, <2 x i32> %y, <2 x i32> <i32 4, i32 4>)
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and <2 x i32> %z, <i32 255, i32 255>
+define <2 x i32> @test_fshl(<2 x i32> %a, <2 x i32> %b) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %y = or <2 x i32> %b, zeroinitializer
+  %z = call <2 x i32> @llvm.fshl.i32(<2 x i32> %x, <2 x i32> %y, <2 x i32> <i32 4, i32 4>)
+  %r = and <2 x i32> %z, <i32 255, i32 255>
+  ret <2 x i32> %r
+}
+
+; CHECK-DAG: DemandedBits: 0xf for   %x = or <2 x i32> %a, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xf0000000 for   %y = or <2 x i32> %b, zeroinitializer
+; CHECK-DAG: DemandedBits: 0xff for   %z = call <2 x i32> @llvm.fshr.v2i32(<2 x i32> %x, <2 x i32> %y, <2 x i32> <i32 28, i32 28>)
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and <2 x i32> %z, <i32 255, i32 255>
+define <2 x i32> @test_fshr(<2 x i32> %a, <2 x i32> %b) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %y = or <2 x i32> %b, zeroinitializer
+  %z = call <2 x i32> @llvm.fshr.i32(<2 x i32> %x, <2 x i32> %y, <2 x i32> <i32 28, i32 28>)
+  %r = and <2 x i32> %z, <i32 255, i32 255>
+  ret <2 x i32> %r
+}
+
+; FP / Int conversion. These have different input / output types.
+
+; CHECK-DAG: DemandedBits: 0xffffffff for   %x = or <2 x i32> %a, zeroinitializer
+define <2 x float> @test_uitofp(<2 x i32> %a) {
+  %x = or <2 x i32> %a, zeroinitializer
+  %r = uitofp <2 x i32> %x to <2 x float>
+  ret <2 x float> %r
+}
+
+; CHECK-DAG: DemandedBits: 0xffffffff for   %y = fptoui <2 x float> %x to <2 x i32>
+define <2 x i32> @test_fptoui(<2 x float> %a) {
+  %x = fadd <2 x float> %a, <float 1.0, float 1.0>
+  %y = fptoui <2 x float> %x to <2 x i32>
+  %r = and <2 x i32> %y, <i32 255, i32 255>
+  ret <2 x i32> %y
+}

test/Transforms/BDCE/vectors.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -bdce -instsimplify < %s | FileCheck %s
+; RUN: opt -S -instsimplify < %s | FileCheck %s -check-prefix=CHECK-IO
+; CHECK-IO lines to ensure that transformations are not performed by only instsimplify.
+
+; BDCE also works on integer vectors.
+
+define <2 x i32> @test_basic(<2 x i32> %a, <2 x i32> %b) {
+; CHECK-LABEL: @test_basic(
+; CHECK-NEXT:    [[B2:%.*]] = add <2 x i32> [[B:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[B3:%.*]] = and <2 x i32> [[B2]], <i32 8, i32 8>
+; CHECK-NEXT:    [[D:%.*]] = ashr <2 x i32> [[B3]], <i32 3, i32 3>
+; CHECK-NEXT:    ret <2 x i32> [[D]]
+;
+; CHECK-IO-LABEL: @test_basic(
+; CHECK-IO-NEXT:    [[A2:%.*]] = add <2 x i32> [[A:%.*]], <i32 1, i32 1>
+; CHECK-IO-NEXT:    [[A3:%.*]] = and <2 x i32> [[A2]], <i32 4, i32 4>
+; CHECK-IO-NEXT:    [[B2:%.*]] = add <2 x i32> [[B:%.*]], <i32 1, i32 1>
+; CHECK-IO-NEXT:    [[B3:%.*]] = and <2 x i32> [[B2]], <i32 8, i32 8>
+; CHECK-IO-NEXT:    [[C:%.*]] = or <2 x i32> [[A3]], [[B3]]
+; CHECK-IO-NEXT:    [[D:%.*]] = ashr <2 x i32> [[C]], <i32 3, i32 3>
+; CHECK-IO-NEXT:    ret <2 x i32> [[D]]
+;
+  %a2 = add <2 x i32> %a, <i32 1, i32 1>
+  %a3 = and <2 x i32> %a2, <i32 4, i32 4>
+  %b2 = add <2 x i32> %b, <i32 1, i32 1>
+  %b3 = and <2 x i32> %b2, <i32 8, i32 8>
+  %c = or <2 x i32> %a3, %b3
+  %d = ashr <2 x i32> %c, <i32 3, i32 3>
+  ret <2 x i32> %d
+}
+
+; Going vector -> scalar
+define i32 @test_extractelement(<2 x i32> %a, <2 x i32> %b) {
+; CHECK-LABEL: @test_extractelement(
+; CHECK-NEXT:    [[B2:%.*]] = add <2 x i32> [[B:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[B3:%.*]] = and <2 x i32> [[B2]], <i32 8, i32 8>
+; CHECK-NEXT:    [[D:%.*]] = extractelement <2 x i32> [[B3]], i32 0
+; CHECK-NEXT:    [[E:%.*]] = ashr i32 [[D]], 3
+; CHECK-NEXT:    ret i32 [[E]]
+;
+; CHECK-IO-LABEL: @test_extractelement(
+; CHECK-IO-NEXT:    [[A2:%.*]] = add <2 x i32> [[A:%.*]], <i32 1, i32 1>
+; CHECK-IO-NEXT:    [[A3:%.*]] = and <2 x i32> [[A2]], <i32 4, i32 4>
+; CHECK-IO-NEXT:    [[B2:%.*]] = add <2 x i32> [[B:%.*]], <i32 1, i32 1>
+; CHECK-IO-NEXT:    [[B3:%.*]] = and <2 x i32> [[B2]], <i32 8, i32 8>
+; CHECK-IO-NEXT:    [[C:%.*]] = or <2 x i32> [[A3]], [[B3]]
+; CHECK-IO-NEXT:    [[D:%.*]] = extractelement <2 x i32> [[C]], i32 0
+; CHECK-IO-NEXT:    [[E:%.*]] = ashr i32 [[D]], 3
+; CHECK-IO-NEXT:    ret i32 [[E]]
+;
+  %a2 = add <2 x i32> %a, <i32 1, i32 1>
+  %a3 = and <2 x i32> %a2, <i32 4, i32 4>
+  %b2 = add <2 x i32> %b, <i32 1, i32 1>
+  %b3 = and <2 x i32> %b2, <i32 8, i32 8>
+  %c = or <2 x i32> %a3, %b3
+  %d = extractelement <2 x i32> %c, i32 0
+  %e = ashr i32 %d, 3
+  ret i32 %e
+}
+
+; Going scalar -> vector
+define <2 x i32> @test_insertelement(i32 %a, i32 %b) {
+; CHECK-LABEL: @test_insertelement(
+; CHECK-NEXT:    [[Y:%.*]] = insertelement <2 x i32> undef, i32 [[B:%.*]], i32 0
+; CHECK-NEXT:    [[Y2:%.*]] = insertelement <2 x i32> [[Y]], i32 [[A:%.*]], i32 1
+; CHECK-NEXT:    [[Y3:%.*]] = and <2 x i32> [[Y2]], <i32 8, i32 8>
+; CHECK-NEXT:    [[U:%.*]] = ashr <2 x i32> [[Y3]], <i32 3, i32 3>
+; CHECK-NEXT:    ret <2 x i32> [[U]]
+;
+; CHECK-IO-LABEL: @test_insertelement(
+; CHECK-IO-NEXT:    [[X:%.*]] = insertelement <2 x i32> undef, i32 [[A:%.*]], i32 0
+; CHECK-IO-NEXT:    [[X2:%.*]] = insertelement <2 x i32> [[X]], i32 [[B:%.*]], i32 1
+; CHECK-IO-NEXT:    [[X3:%.*]] = and <2 x i32> [[X2]], <i32 4, i32 4>
+; CHECK-IO-NEXT:    [[Y:%.*]] = insertelement <2 x i32> undef, i32 [[B]], i32 0
+; CHECK-IO-NEXT:    [[Y2:%.*]] = insertelement <2 x i32> [[Y]], i32 [[A]], i32 1
+; CHECK-IO-NEXT:    [[Y3:%.*]] = and <2 x i32> [[Y2]], <i32 8, i32 8>
+; CHECK-IO-NEXT:    [[Z:%.*]] = or <2 x i32> [[X3]], [[Y3]]
+; CHECK-IO-NEXT:    [[U:%.*]] = ashr <2 x i32> [[Z]], <i32 3, i32 3>
+; CHECK-IO-NEXT:    ret <2 x i32> [[U]]
+;
+  %x = insertelement <2 x i32> undef, i32 %a, i32 0
+  %x2 = insertelement <2 x i32> %x, i32 %b, i32 1
+  %x3 = and <2 x i32> %x2, <i32 4, i32 4>
+  %y = insertelement <2 x i32> undef, i32 %b, i32 0
+  %y2 = insertelement <2 x i32> %y, i32 %a, i32 1
+  %y3 = and <2 x i32> %y2, <i32 8, i32 8>
+  %z = or <2 x i32> %x3, %y3
+  %u = ashr <2 x i32> %z, <i32 3, i32 3>
+  ret <2 x i32> %u
+}
+
+; Some non-int vectors and conversions
+define <2 x i32> @test_conversion(<2 x i32> %a) {
+; CHECK-LABEL: @test_conversion(
+; CHECK-NEXT:    [[A2:%.*]] = add <2 x i32> [[A:%.*]], <i32 1, i32 1>
+; CHECK-NEXT:    [[A3:%.*]] = and <2 x i32> [[A2]], <i32 2, i32 2>
+; CHECK-NEXT:    [[X:%.*]] = uitofp <2 x i32> [[A3]] to <2 x double>
+; CHECK-NEXT:    [[Y:%.*]] = fadd <2 x double> [[X]], <double 1.000000e+00, double 1.000000e+00>
+; CHECK-NEXT:    [[Z:%.*]] = fptoui <2 x double> [[Y]] to <2 x i32>
+; CHECK-NEXT:    [[U:%.*]] = ashr <2 x i32> [[Z]], <i32 3, i32 3>
+; CHECK-NEXT:    ret <2 x i32> [[U]]
+;
+; CHECK-IO-LABEL: @test_conversion(
+; CHECK-IO-NEXT:    [[A2:%.*]] = add <2 x i32> [[A:%.*]], <i32 1, i32 1>
+; CHECK-IO-NEXT:    [[A3:%.*]] = and <2 x i32> [[A2]], <i32 2, i32 2>
+; CHECK-IO-NEXT:    [[X:%.*]] = uitofp <2 x i32> [[A3]] to <2 x double>
+; CHECK-IO-NEXT:    [[Y:%.*]] = fadd <2 x double> [[X]], <double 1.000000e+00, double 1.000000e+00>
+; CHECK-IO-NEXT:    [[Z:%.*]] = fptoui <2 x double> [[Y]] to <2 x i32>
+; CHECK-IO-NEXT:    [[U:%.*]] = ashr <2 x i32> [[Z]], <i32 3, i32 3>
+; CHECK-IO-NEXT:    ret <2 x i32> [[U]]
+;
+  %a2 = add <2 x i32> %a, <i32 1, i32 1>
+  %a3 = and <2 x i32> %a2, <i32 2, i32 2>
+  %x = uitofp <2 x i32> %a3 to <2 x double>
+  %y = fadd <2 x double> %x, <double 1.0, double 1.0>
+  %z = fptoui <2 x double> %y to <2 x i32>
+  %u = ashr <2 x i32> %z, <i32 3, i32 3>
+  ret <2 x i32> %u
+}
+
+; Assumption invalidation (adapted from invalidate-assumptions.ll)
+define <2 x i1> @test_assumption_invalidation(<2 x i1> %b, <2 x i8> %x) {
+; CHECK-LABEL: @test_assumption_invalidation(
+; CHECK-NEXT:    [[LITTLE_NUMBER:%.*]] = zext <2 x i1> [[B:%.*]] to <2 x i8>
+; CHECK-NEXT:    [[SUB:%.*]] = sub <2 x i8> zeroinitializer, [[LITTLE_NUMBER]]
+; CHECK-NEXT:    [[TRUNC:%.*]] = trunc <2 x i8> [[SUB]] to <2 x i1>
+; CHECK-NEXT:    ret <2 x i1> [[TRUNC]]
+;
+; CHECK-IO-LABEL: @test_assumption_invalidation(
+; CHECK-IO-NEXT:    [[SETBIT:%.*]] = or <2 x i8> [[X:%.*]], <i8 64, i8 64>
+; CHECK-IO-NEXT:    [[LITTLE_NUMBER:%.*]] = zext <2 x i1> [[B:%.*]] to <2 x i8>
+; CHECK-IO-NEXT:    [[BIG_NUMBER:%.*]] = shl <2 x i8> [[SETBIT]], <i8 1, i8 1>
+; CHECK-IO-NEXT:    [[SUB:%.*]] = sub nuw <2 x i8> [[BIG_NUMBER]], [[LITTLE_NUMBER]]
+; CHECK-IO-NEXT:    [[TRUNC:%.*]] = trunc <2 x i8> [[SUB]] to <2 x i1>
+; CHECK-IO-NEXT:    ret <2 x i1> [[TRUNC]]
+;
+  %setbit = or <2 x i8> %x, <i8 64, i8 64>
+  %little_number = zext <2 x i1> %b to <2 x i8>
+  %big_number = shl <2 x i8> %setbit, <i8 1, i8 1>
+  %sub = sub nuw <2 x i8> %big_number, %little_number
+  %trunc = trunc <2 x i8> %sub to <2 x i1>
+  ret <2 x i1> %trunc
+}