lib/Transforms/Scalar/BDCE.cpp

   1 //===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the Bit-Tracking Dead Code Elimination pass. Some
  11 // instructions (shifts, some ands, ors, etc.) kill some of their input bits.
  12 // We track these dead bits and remove instructions that compute only these
  13 // dead bits.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/DepthFirstIterator.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/Analysis/AssumptionCache.h"
  24 #include "llvm/Analysis/ValueTracking.h"
  25 #include "llvm/IR/BasicBlock.h"
  26 #include "llvm/IR/CFG.h"
  27 #include "llvm/IR/DataLayout.h"
  28 #include "llvm/IR/Dominators.h"
  29 #include "llvm/IR/InstIterator.h"
  30 #include "llvm/IR/Instructions.h"
  31 #include "llvm/IR/IntrinsicInst.h"
  32 #include "llvm/IR/Module.h"
  33 #include "llvm/IR/Operator.h"
  34 #include "llvm/Pass.h"
  35 #include "llvm/Support/Debug.h"
  36 #include "llvm/Support/raw_ostream.h"
  37
  38 using namespace llvm;
  39
  40 #define DEBUG_TYPE "bdce"
  41
  42 STATISTIC(NumRemoved, "Number of instructions removed (unused)");
  43 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
  44
  45 namespace {
  46 struct BDCE : public FunctionPass {
  47   static char ID; // Pass identification, replacement for typeid
  48   BDCE() : FunctionPass(ID) {
  49     initializeBDCEPass(*PassRegistry::getPassRegistry());
  50   }
  51
  52   bool runOnFunction(Function& F) override;
  53
  54   void getAnalysisUsage(AnalysisUsage& AU) const override {
  55     AU.setPreservesCFG();
  56     AU.addRequired<AssumptionCacheTracker>();
  57     AU.addRequired<DominatorTreeWrapperPass>();
  58   }
  59
  60   void determineLiveOperandBits(const Instruction *UserI,
  61                                 const Instruction *I, unsigned OperandNo,
  62                                 const APInt &AOut, APInt &AB,
  63                                 APInt &KnownZero, APInt &KnownOne,
  64                                 APInt &KnownZero2, APInt &KnownOne2);
  65
  66   AssumptionCache *AC;
  67   const DataLayout *DL;
  68   DominatorTree *DT;
  69 };
  70 }
  71
  72 char BDCE::ID = 0;
  73 INITIALIZE_PASS_BEGIN(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
  74                       false, false)
  75 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
  76 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  77 INITIALIZE_PASS_END(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
  78                     false, false)
  79
  80 static bool isAlwaysLive(Instruction *I) {
  81   return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
  82          isa<LandingPadInst>(I) || I->mayHaveSideEffects();
  83 }
  84
  85 void BDCE::determineLiveOperandBits(const Instruction *UserI,
  86                                     const Instruction *I, unsigned OperandNo,
  87                                     const APInt &AOut, APInt &AB,
  88                                     APInt &KnownZero, APInt &KnownOne,
  89                                     APInt &KnownZero2, APInt &KnownOne2) {
  90   unsigned BitWidth = AB.getBitWidth();
  91
  92   // We're called once per operand, but for some instructions, we need to
  93   // compute known bits of both operands in order to determine the live bits of
  94   // either (when both operands are instructions themselves). We don't,
  95   // however, want to do this twice, so we cache the result in APInts that live
  96   // in the caller. For the two-relevant-operands case, both operand values are
  97   // provided here.
  98   auto ComputeKnownBits = [&](unsigned BitWidth, const Value *V1,
  99                               const Value *V2) {
 100     KnownZero = APInt(BitWidth, 0);
 101     KnownOne =  APInt(BitWidth, 0);
 102     computeKnownBits(const_cast<Value*>(V1), KnownZero, KnownOne, DL, 0, AC,
 103                      UserI, DT);
 104
 105     if (V2) {
 106       KnownZero2 = APInt(BitWidth, 0);
 107       KnownOne2 =  APInt(BitWidth, 0);
 108       computeKnownBits(const_cast<Value*>(V2), KnownZero2, KnownOne2, DL, 0, AC,
 109                        UserI, DT);
 110     }
 111   };
 112
 113   switch (UserI->getOpcode()) {
 114   default: break;
 115   case Instruction::Call:
 116   case Instruction::Invoke:
 117     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
 118       switch (II->getIntrinsicID()) {
 119       default: break;
 120       case Intrinsic::bswap:
 121         // The alive bits of the input are the swapped alive bits of
 122         // the output.
 123         AB = AOut.byteSwap();
 124         break;
 125       case Intrinsic::ctlz:
 126         if (OperandNo == 0) {
 127           // We need some output bits, so we need all bits of the
 128           // input to the left of, and including, the leftmost bit
 129           // known to be one.
 130           ComputeKnownBits(BitWidth, I, nullptr);
 131           AB = APInt::getHighBitsSet(BitWidth,
 132                  std::min(BitWidth, KnownOne.countLeadingZeros()+1));
 133         }
 134         break;
 135       case Intrinsic::cttz:
 136         if (OperandNo == 0) {
 137           // We need some output bits, so we need all bits of the
 138           // input to the right of, and including, the rightmost bit
 139           // known to be one.
 140           ComputeKnownBits(BitWidth, I, nullptr);
 141           AB = APInt::getLowBitsSet(BitWidth,
 142                  std::min(BitWidth, KnownOne.countTrailingZeros()+1));
 143         }
 144         break;
 145       }
 146     break;
 147   case Instruction::Add:
 148   case Instruction::Sub:
 149     // Find the highest live output bit. We don't need any more input
 150     // bits than that (adds, and thus subtracts, ripple only to the
 151     // left).
 152     AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
 153     break;
 154   case Instruction::Shl:
 155     if (OperandNo == 0)
 156       if (ConstantInt *CI =
 157             dyn_cast<ConstantInt>(UserI->getOperand(1))) {
 158         uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
 159         AB = AOut.lshr(ShiftAmt);
 160
 161         // If the shift is nuw/nsw, then the high bits are not dead
 162         // (because we've promised that they *must* be zero).
 163         const ShlOperator *S = cast<ShlOperator>(UserI);
 164         if (S->hasNoSignedWrap())
 165           AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
 166         else if (S->hasNoUnsignedWrap())
 167           AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
 168       }
 169     break;
 170   case Instruction::LShr:
 171     if (OperandNo == 0)
 172       if (ConstantInt *CI =
 173             dyn_cast<ConstantInt>(UserI->getOperand(1))) {
 174         uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
 175         AB = AOut.shl(ShiftAmt);
 176
 177         // If the shift is exact, then the low bits are not dead
 178         // (they must be zero).
 179         if (cast<LShrOperator>(UserI)->isExact())
 180           AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
 181       }
 182     break;
 183   case Instruction::AShr:
 184     if (OperandNo == 0)
 185       if (ConstantInt *CI =
 186             dyn_cast<ConstantInt>(UserI->getOperand(1))) {
 187         uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
 188         AB = AOut.shl(ShiftAmt);
 189         // Because the high input bit is replicated into the
 190         // high-order bits of the result, if we need any of those
 191         // bits, then we must keep the highest input bit.
 192         if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
 193             .getBoolValue())
 194           AB.setBit(BitWidth-1);
 195
 196         // If the shift is exact, then the low bits are not dead
 197         // (they must be zero).
 198         if (cast<AShrOperator>(UserI)->isExact())
 199           AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
 200       }
 201     break;
 202   case Instruction::And:
 203     AB = AOut;
 204
 205     // For bits that are known zero, the corresponding bits in the
 206     // other operand are dead (unless they're both zero, in which
 207     // case they can't both be dead, so just mark the LHS bits as
 208     // dead).
 209     if (OperandNo == 0) {
 210       ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
 211       AB &= ~KnownZero2;
 212     } else {
 213       if (!isa<Instruction>(UserI->getOperand(0)))
 214         ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
 215       AB &= ~(KnownZero & ~KnownZero2);
 216     }
 217     break;
 218   case Instruction::Or:
 219     AB = AOut;
 220
 221     // For bits that are known one, the corresponding bits in the
 222     // other operand are dead (unless they're both one, in which
 223     // case they can't both be dead, so just mark the LHS bits as
 224     // dead).
 225     if (OperandNo == 0) {
 226       ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
 227       AB &= ~KnownOne2;
 228     } else {
 229       if (!isa<Instruction>(UserI->getOperand(0)))
 230         ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
 231       AB &= ~(KnownOne & ~KnownOne2);
 232     }
 233     break;
 234   case Instruction::Xor:
 235   case Instruction::PHI:
 236     AB = AOut;
 237     break;
 238   case Instruction::Trunc:
 239     AB = AOut.zext(BitWidth);
 240     break;
 241   case Instruction::ZExt:
 242     AB = AOut.trunc(BitWidth);
 243     break;
 244   case Instruction::SExt:
 245     AB = AOut.trunc(BitWidth);
 246     // Because the high input bit is replicated into the
 247     // high-order bits of the result, if we need any of those
 248     // bits, then we must keep the highest input bit.
 249     if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
 250                                       AOut.getBitWidth() - BitWidth))
 251         .getBoolValue())
 252       AB.setBit(BitWidth-1);
 253     break;
 254   case Instruction::Select:
 255     if (OperandNo != 0)
 256       AB = AOut;
 257     break;
 258   }
 259 }
 260
 261 bool BDCE::runOnFunction(Function& F) {
 262   if (skipOptnoneFunction(F))
 263     return false;
 264
 265   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 266   DL = F.getParent()->getDataLayout();
 267   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 268
 269   DenseMap<Instruction *, APInt> AliveBits;
 270   SmallVector<Instruction*, 128> Worklist;
 271
 272   // The set of visited instructions (non-integer-typed only).
 273   SmallPtrSet<Instruction*, 128> Visited;
 274
 275   // Collect the set of "root" instructions that are known live.
 276   for (Instruction &I : inst_range(F)) {
 277     if (!isAlwaysLive(&I))
 278       continue;
 279
 280     DEBUG(dbgs() << "BDCE: Root: " << I);
 281     // For integer-valued instructions, set up an initial empty set of alive
 282     // bits and add the instruction to the work list. For other instructions
 283     // add their operands to the work list (for integer values operands, mark
 284     // all bits as live).
 285     if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
 286       if (!AliveBits.count(&I)) {
 287         AliveBits[&I] = APInt(IT->getBitWidth(), 0);
 288         Worklist.push_back(&I);
 289       }
 290
 291       continue;
 292     }
 293
 294     // Non-integer-typed instructions...
 295     for (Use &OI : I.operands()) {
 296       if (Instruction *J = dyn_cast<Instruction>(OI)) {
 297         if (IntegerType *IT = dyn_cast<IntegerType>(J->getType()))
 298           AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth());
 299         Worklist.push_back(J);
 300       }
 301     }
 302     // To save memory, we don't add I to the Visited set here. Instead, we
 303     // check isAlwaysLive on every instruction when searching for dead
 304     // instructions later (we need to check isAlwaysLive for the
 305     // integer-typed instructions anyway).
 306   }
 307
 308   // Propagate liveness backwards to operands.
 309   while (!Worklist.empty()) {
 310     Instruction *UserI = Worklist.pop_back_val();
 311
 312     DEBUG(dbgs() << "BDCE: Visiting: " << *UserI);
 313     APInt AOut;
 314     if (UserI->getType()->isIntegerTy()) {
 315       AOut = AliveBits[UserI];
 316       DEBUG(dbgs() << " Alive Out: " << AOut);
 317     }
 318     DEBUG(dbgs() << "\n");
 319
 320     if (!UserI->getType()->isIntegerTy())
 321       Visited.insert(UserI);
 322
 323     APInt KnownZero, KnownOne, KnownZero2, KnownOne2;
 324     // Compute the set of alive bits for each operand. These are anded into the
 325     // existing set, if any, and if that changes the set of alive bits, the
 326     // operand is added to the work-list.
 327     for (Use &OI : UserI->operands()) {
 328       if (Instruction *I = dyn_cast<Instruction>(OI)) {
 329         if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
 330           unsigned BitWidth = IT->getBitWidth();
 331           APInt AB = APInt::getAllOnesValue(BitWidth);
 332           if (UserI->getType()->isIntegerTy() && !AOut &&
 333               !isAlwaysLive(UserI)) {
 334             AB = APInt(BitWidth, 0);
 335           } else {
 336             // If all bits of the output are dead, then all bits of the input
 337             // Bits of each operand that are used to compute alive bits of the
 338             // output are alive, all others are dead.
 339             determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB,
 340                                      KnownZero, KnownOne,
 341                                      KnownZero2, KnownOne2);
 342           }
 343
 344           // If we've added to the set of alive bits (or the operand has not
 345           // been previously visited), then re-queue the operand to be visited
 346           // again.
 347           APInt ABPrev(BitWidth, 0);
 348           auto ABI = AliveBits.find(I);
 349           if (ABI != AliveBits.end())
 350             ABPrev = ABI->second;
 351
 352           APInt ABNew = AB | ABPrev;
 353           if (ABNew != ABPrev || ABI == AliveBits.end()) {
 354             AliveBits[I] = std::move(ABNew);
 355             Worklist.push_back(I);
 356           }
 357         } else if (!Visited.count(I)) {
 358           Worklist.push_back(I);
 359         }
 360       }
 361     }
 362   }
 363
 364   bool Changed = false;
 365   // The inverse of the live set is the dead set.  These are those instructions
 366   // which have no side effects and do not influence the control flow or return
 367   // value of the function, and may therefore be deleted safely.
 368   // NOTE: We reuse the Worklist vector here for memory efficiency.
 369   for (Instruction &I : inst_range(F)) {
 370     // For live instructions that have all dead bits, first make them dead by
 371     // replacing all uses with something else. Then, if they don't need to
 372     // remain live (because they have side effects, etc.) we can remove them.
 373     if (I.getType()->isIntegerTy()) {
 374       auto ABI = AliveBits.find(&I);
 375       if (ABI != AliveBits.end()) {
 376         if (ABI->second.getBoolValue())
 377           continue;
 378
 379         DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");
 380         // FIXME: In theory we could substitute undef here instead of zero.
 381         // This should be reconsidered once we settle on the semantics of
 382         // undef, poison, etc.
 383         Value *Zero = ConstantInt::get(I.getType(), 0);
 384         ++NumSimplified;
 385         I.replaceAllUsesWith(Zero);
 386         Changed = true;
 387       }
 388     } else if (Visited.count(&I)) {
 389       continue;
 390     }
 391
 392     if (isAlwaysLive(&I))
 393       continue;
 394
 395     Worklist.push_back(&I);
 396     I.dropAllReferences();
 397     Changed = true;
 398   }
 399
 400   for (Instruction *&I : Worklist) {
 401     ++NumRemoved;
 402     I->eraseFromParent();
 403   }
 404
 405   return Changed;
 406 }
 407
 408 FunctionPass *llvm::createBitTrackingDCEPass() {
 409   return new BDCE();
 410 }
 411