Index: llvm/trunk/include/llvm/Analysis/DemandedBits.h =================================================================== --- llvm/trunk/include/llvm/Analysis/DemandedBits.h +++ llvm/trunk/include/llvm/Analysis/DemandedBits.h @@ -57,6 +57,9 @@ /// Return true if, during analysis, I could not be reached. bool isInstructionDead(Instruction *I); + /// Return whether this use is dead by means of not having any demanded bits. + bool isUseDead(Use *U); + void print(raw_ostream &OS); private: @@ -75,6 +78,9 @@ // The set of visited instructions (non-integer-typed only). SmallPtrSet Visited; DenseMap AliveBits; + // Uses with no demanded bits. If the user also has no demanded bits, the use + // might not be stored explicitly in this map, to save memory during analysis. + SmallPtrSet DeadUses; }; class DemandedBitsWrapperPass : public FunctionPass { Index: llvm/trunk/lib/Analysis/DemandedBits.cpp =================================================================== --- llvm/trunk/lib/Analysis/DemandedBits.cpp +++ llvm/trunk/lib/Analysis/DemandedBits.cpp @@ -314,6 +314,7 @@ Visited.clear(); AliveBits.clear(); + DeadUses.clear(); SmallVector Worklist; @@ -358,7 +359,8 @@ APInt AOut; if (UserI->getType()->isIntOrIntVectorTy()) { AOut = AliveBits[UserI]; - LLVM_DEBUG(dbgs() << " Alive Out: " << AOut); + LLVM_DEBUG(dbgs() << " Alive Out: 0x" + << Twine::utohexstr(AOut.getLimitedValue())); } LLVM_DEBUG(dbgs() << "\n"); @@ -377,13 +379,20 @@ APInt AB = APInt::getAllOnesValue(BitWidth); if (UserI->getType()->isIntOrIntVectorTy() && !AOut && !isAlwaysLive(UserI)) { + // If all bits of the output are dead, then all bits of the input + // are also dead. AB = APInt(BitWidth, 0); } else { - // If all bits of the output are dead, then all bits of the input // Bits of each operand that are used to compute alive bits of the // output are alive, all others are dead. determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB, Known, Known2); + + // Keep track of uses which have no demanded bits. + if (AB.isNullValue()) + DeadUses.insert(&OI); + else + DeadUses.erase(&OI); } // If we've added to the set of alive bits (or the operand has not @@ -426,6 +435,31 @@ !isAlwaysLive(I); } +bool DemandedBits::isUseDead(Use *U) { + // We only track integer uses, everything else is assumed live. + if (!(*U)->getType()->isIntOrIntVectorTy()) + return false; + + // Uses by always-live instructions are never dead. + Instruction *UserI = cast(U->getUser()); + if (isAlwaysLive(UserI)) + return false; + + performAnalysis(); + if (DeadUses.count(U)) + return true; + + // If no output bits are demanded, no input bits are demanded and the use + // is dead. These uses might not be explicitly present in the DeadUses map. + if (UserI->getType()->isIntOrIntVectorTy()) { + auto Found = AliveBits.find(UserI); + if (Found != AliveBits.end() && Found->second.isNullValue()) + return true; + } + + return false; +} + void DemandedBits::print(raw_ostream &OS) { performAnalysis(); for (auto &KV : AliveBits) { Index: llvm/trunk/lib/Transforms/Scalar/BDCE.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/BDCE.cpp +++ llvm/trunk/lib/Transforms/Scalar/BDCE.cpp @@ -96,30 +96,38 @@ if (I.mayHaveSideEffects() && I.use_empty()) continue; - if (I.getType()->isIntOrIntVectorTy() && - !DB.getDemandedBits(&I).getBoolValue()) { - // For live instructions that have all dead bits, first make them dead by - // replacing all uses with something else. Then, if they don't need to - // remain live (because they have side effects, etc.) we can remove them. - LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n"); + // Remove instructions not reached during analysis. + if (DB.isInstructionDead(&I)) { + salvageDebugInfo(I); + Worklist.push_back(&I); + I.dropAllReferences(); + Changed = true; + continue; + } + + for (Use &U : I.operands()) { + // DemandedBits only detects dead integer uses. + if (!U->getType()->isIntOrIntVectorTy()) + continue; + + // TODO: We could also find dead non-instruction uses, e.g. arguments. + if (!isa(U)) + continue; + + if (!DB.isUseDead(&U)) + continue; + + LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n"); clearAssumptionsOfUsers(&I, DB); // FIXME: In theory we could substitute undef here instead of zero. // This should be reconsidered once we settle on the semantics of // undef, poison, etc. - Value *Zero = ConstantInt::get(I.getType(), 0); + U.set(ConstantInt::get(U->getType(), 0)); ++NumSimplified; - I.replaceNonMetadataUsesWith(Zero); Changed = true; } - if (!DB.isInstructionDead(&I)) - continue; - - salvageDebugInfo(I); - Worklist.push_back(&I); - I.dropAllReferences(); - Changed = true; } for (Instruction *&I : Worklist) { Index: llvm/trunk/test/Transforms/BDCE/dead-uses.ll =================================================================== --- llvm/trunk/test/Transforms/BDCE/dead-uses.ll +++ llvm/trunk/test/Transforms/BDCE/dead-uses.ll @@ -10,7 +10,7 @@ define i32 @pr39771_fshr_multi_use_instr(i32 %a) { ; CHECK-LABEL: @pr39771_fshr_multi_use_instr( ; CHECK-NEXT: [[X:%.*]] = or i32 [[A:%.*]], 0 -; CHECK-NEXT: [[B:%.*]] = tail call i32 @llvm.fshr.i32(i32 [[X]], i32 [[X]], i32 1) +; CHECK-NEXT: [[B:%.*]] = tail call i32 @llvm.fshr.i32(i32 0, i32 [[X]], i32 1) ; CHECK-NEXT: [[C:%.*]] = lshr i32 [[B]], 23 ; CHECK-NEXT: [[D:%.*]] = xor i32 [[C]], [[B]] ; CHECK-NEXT: [[E:%.*]] = and i32 [[D]], 31 @@ -28,7 +28,7 @@ define <2 x i32> @pr39771_fshr_multi_use_instr_vec(<2 x i32> %a) { ; CHECK-LABEL: @pr39771_fshr_multi_use_instr_vec( ; CHECK-NEXT: [[X:%.*]] = or <2 x i32> [[A:%.*]], zeroinitializer -; CHECK-NEXT: [[B:%.*]] = tail call <2 x i32> @llvm.fshr.v2i32(<2 x i32> [[X]], <2 x i32> [[X]], <2 x i32> ) +; CHECK-NEXT: [[B:%.*]] = tail call <2 x i32> @llvm.fshr.v2i32(<2 x i32> zeroinitializer, <2 x i32> [[X]], <2 x i32> ) ; CHECK-NEXT: [[C:%.*]] = lshr <2 x i32> [[B]], ; CHECK-NEXT: [[D:%.*]] = xor <2 x i32> [[C]], [[B]] ; CHECK-NEXT: [[E:%.*]] = and <2 x i32> [[D]], @@ -77,3 +77,28 @@ %e = and i32 %d, 31 ret i32 %e } + +; %b operand of %c will be dead initially, but later found live. +define void @dead_use_invalidation(i32 %a) { +; CHECK-LABEL: @dead_use_invalidation( +; CHECK-NEXT: [[B:%.*]] = or i32 [[A:%.*]], 0 +; CHECK-NEXT: [[C:%.*]] = shl i32 [[B]], 31 +; CHECK-NEXT: [[D:%.*]] = and i32 [[C]], 1 +; CHECK-NEXT: [[E:%.*]] = or i32 [[C]], 0 +; CHECK-NEXT: [[F:%.*]] = or i32 [[D]], 0 +; CHECK-NEXT: call void @dummy(i32 [[E]]) +; CHECK-NEXT: call void @dummy(i32 [[F]]) +; CHECK-NEXT: call void @dummy(i32 [[B]]) +; CHECK-NEXT: ret void +; + %b = or i32 %a, 0 + %c = shl i32 %b, 31 + %d = and i32 %c, 1 + %e = or i32 %c, 0 + %f = or i32 %d, 0 + call void @dummy(i32 %e) + call void @dummy(i32 %f) + call void @dummy(i32 %b) + ret void +} +declare void @dummy(i32)