Index: include/llvm/Analysis/DemandedBits.h =================================================================== --- /dev/null +++ include/llvm/Analysis/DemandedBits.h @@ -0,0 +1,74 @@ +//===-- 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 Visited; + DenseMap AliveBits; +}; + +/// Create a demanded bits analysis pass. +FunctionPass *createDemandedBitsPass(); + +} // End llvm namespace + +#endif Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -304,6 +304,7 @@ void initializeFloat2IntPass(PassRegistry&); void initializeLoopDistributePass(PassRegistry&); void initializeSjLjEHPreparePass(PassRegistry&); +void initializeDemandedBitsPass(PassRegistry&); } #endif Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -37,6 +37,7 @@ initializeCFLAliasAnalysisPass(Registry); initializeDependenceAnalysisPass(Registry); initializeDelinearizationPass(Registry); + initializeDemandedBitsPass(Registry); initializeDivergenceAnalysisPass(Registry); initializeDominanceFrontierPass(Registry); initializeDomViewerPass(Registry); Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -19,6 +19,7 @@ CodeMetrics.cpp ConstantFolding.cpp Delinearization.cpp + DemandedBits.cpp DependenceAnalysis.cpp DivergenceAnalysis.cpp DomPrinter.cpp Index: lib/Analysis/DemandedBits.cpp =================================================================== --- /dev/null +++ lib/Analysis/DemandedBits.cpp @@ -0,0 +1,367 @@ +//===---- 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(); + AU.addRequired(); + AU.setPreservesAll(); +} + +static bool isAlwaysLive(Instruction *I) { + return isa(I) || isa(I) || + isa(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(V1), KnownZero, KnownOne, DL, 0, + AC, UserI, DT); + + if (V2) { + KnownZero2 = APInt(BitWidth, 0); + KnownOne2 = APInt(BitWidth, 0); + computeKnownBits(const_cast(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(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(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(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(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(UserI)->isExact()) + AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt); + } + break; + case Instruction::AShr: + if (OperandNo == 0) + if (ConstantInt *CI = + dyn_cast(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(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(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(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().getAssumptionCache(F); + DT = &getAnalysis().getDomTree(); + + Visited.clear(); + AliveBits.clear(); + + SmallVector 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(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(OI)) { + if (IntegerType *IT = dyn_cast(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(OI)) { + if (IntegerType *IT = dyn_cast(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(); +} Index: lib/Transforms/Scalar/BDCE.cpp =================================================================== --- lib/Transforms/Scalar/BDCE.cpp +++ lib/Transforms/Scalar/BDCE.cpp @@ -15,26 +15,17 @@ //===----------------------------------------------------------------------===// #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" @@ -53,26 +44,15 @@ void getAnalysisUsage(AnalysisUsage& AU) const override { AU.setPreservesCFG(); - AU.addRequired(); - AU.addRequired(); + AU.addRequired(); } - - 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) @@ -81,285 +61,13 @@ isa(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(V1), KnownZero, KnownOne, DL, 0, - AC, UserI, DT); - - if (V2) { - KnownZero2 = APInt(BitWidth, 0); - KnownOne2 = APInt(BitWidth, 0); - computeKnownBits(const_cast(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(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(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(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(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(UserI)->isExact()) - AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt); - } - break; - case Instruction::AShr: - if (OperandNo == 0) - if (ConstantInt *CI = - dyn_cast(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(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(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(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(); - AC = &getAnalysis().getAssumptionCache(F); - DT = &getAnalysis().getDomTree(); - - DenseMap AliveBits; SmallVector Worklist; - // The set of visited instructions (non-integer-typed only). - SmallPtrSet 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(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(OI)) { - if (IntegerType *IT = dyn_cast(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(OI)) { - if (IntegerType *IT = dyn_cast(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 @@ -370,9 +78,8 @@ // 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"); @@ -384,7 +91,7 @@ I.replaceAllUsesWith(Zero); Changed = true; } - } else if (Visited.count(&I)) { + } else if (!DB.isInstructionDead(&I)) { continue; }