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   DominatorTree *DT;
  68 };
  69 }
  70
  71 char BDCE::ID = 0;
  72 INITIALIZE_PASS_BEGIN(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
  73                       false, false)
  74 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
  75 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
  76 INITIALIZE_PASS_END(BDCE, "bdce", "Bit-Tracking Dead Code Elimination",
  77                     false, false)
  78
  79 static bool isAlwaysLive(Instruction *I) {
  80   return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
  81          isa<LandingPadInst>(I) || I->mayHaveSideEffects();
  82 }
  83
  84 void BDCE::determineLiveOperandBits(const Instruction *UserI,
  85                                     const Instruction *I, unsigned OperandNo,
  86                                     const APInt &AOut, APInt &AB,
  87                                     APInt &KnownZero, APInt &KnownOne,
  88                                     APInt &KnownZero2, APInt &KnownOne2) {
  89   unsigned BitWidth = AB.getBitWidth();
  90
  91   // We're called once per operand, but for some instructions, we need to
  92   // compute known bits of both operands in order to determine the live bits of
  93   // either (when both operands are instructions themselves). We don't,
  94   // however, want to do this twice, so we cache the result in APInts that live
  95   // in the caller. For the two-relevant-operands case, both operand values are
  96   // provided here.
  97   auto ComputeKnownBits =
  98       [&](unsigned BitWidth, const Value *V1, const Value *V2) {
  99         const DataLayout &DL = I->getModule()->getDataLayout();
 100         KnownZero = APInt(BitWidth, 0);
 101         KnownOne = APInt(BitWidth, 0);
 102         computeKnownBits(const_cast<Value *>(V1), KnownZero, KnownOne, DL, 0,
 103                          AC, 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,
 109                            0, AC, 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   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 267
 268   DenseMap<Instruction *, APInt> AliveBits;
 269   SmallVector<Instruction*, 128> Worklist;
 270
 271   // The set of visited instructions (non-integer-typed only).
 272   SmallPtrSet<Instruction*, 128> Visited;
 273
 274   // Collect the set of "root" instructions that are known live.
 275   for (Instruction &I : inst_range(F)) {
 276     if (!isAlwaysLive(&I))
 277       continue;
 278
 279     DEBUG(dbgs() << "BDCE: Root: " << I << "\n");
 280     // For integer-valued instructions, set up an initial empty set of alive
 281     // bits and add the instruction to the work list. For other instructions
 282     // add their operands to the work list (for integer values operands, mark
 283     // all bits as live).
 284     if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
 285       if (!AliveBits.count(&I)) {
 286         AliveBits[&I] = APInt(IT->getBitWidth(), 0);
 287         Worklist.push_back(&I);
 288       }
 289
 290       continue;
 291     }
 292
 293     // Non-integer-typed instructions...
 294     for (Use &OI : I.operands()) {
 295       if (Instruction *J = dyn_cast<Instruction>(OI)) {
 296         if (IntegerType *IT = dyn_cast<IntegerType>(J->getType()))
 297           AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth());
 298         Worklist.push_back(J);
 299       }
 300     }
 301     // To save memory, we don't add I to the Visited set here. Instead, we
 302     // check isAlwaysLive on every instruction when searching for dead
 303     // instructions later (we need to check isAlwaysLive for the
 304     // integer-typed instructions anyway).
 305   }
 306
 307   // Propagate liveness backwards to operands.
 308   while (!Worklist.empty()) {
 309     Instruction *UserI = Worklist.pop_back_val();
 310
 311     DEBUG(dbgs() << "BDCE: Visiting: " << *UserI);
 312     APInt AOut;
 313     if (UserI->getType()->isIntegerTy()) {
 314       AOut = AliveBits[UserI];
 315       DEBUG(dbgs() << " Alive Out: " << AOut);
 316     }
 317     DEBUG(dbgs() << "\n");
 318
 319     if (!UserI->getType()->isIntegerTy())
 320       Visited.insert(UserI);
 321
 322     APInt KnownZero, KnownOne, KnownZero2, KnownOne2;
 323     // Compute the set of alive bits for each operand. These are anded into the
 324     // existing set, if any, and if that changes the set of alive bits, the
 325     // operand is added to the work-list.
 326     for (Use &OI : UserI->operands()) {
 327       if (Instruction *I = dyn_cast<Instruction>(OI)) {
 328         if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
 329           unsigned BitWidth = IT->getBitWidth();
 330           APInt AB = APInt::getAllOnesValue(BitWidth);
 331           if (UserI->getType()->isIntegerTy() && !AOut &&
 332               !isAlwaysLive(UserI)) {
 333             AB = APInt(BitWidth, 0);
 334           } else {
 335             // If all bits of the output are dead, then all bits of the input
 336             // Bits of each operand that are used to compute alive bits of the
 337             // output are alive, all others are dead.
 338             determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB,
 339                                      KnownZero, KnownOne,
 340                                      KnownZero2, KnownOne2);
 341           }
 342
 343           // If we've added to the set of alive bits (or the operand has not
 344           // been previously visited), then re-queue the operand to be visited
 345           // again.
 346           APInt ABPrev(BitWidth, 0);
 347           auto ABI = AliveBits.find(I);
 348           if (ABI != AliveBits.end())
 349             ABPrev = ABI->second;
 350
 351           APInt ABNew = AB | ABPrev;
 352           if (ABNew != ABPrev || ABI == AliveBits.end()) {
 353             AliveBits[I] = std::move(ABNew);
 354             Worklist.push_back(I);
 355           }
 356         } else if (!Visited.count(I)) {
 357           Worklist.push_back(I);
 358         }
 359       }
 360     }
 361   }
 362
 363   bool Changed = false;
 364   // The inverse of the live set is the dead set.  These are those instructions
 365   // which have no side effects and do not influence the control flow or return
 366   // value of the function, and may therefore be deleted safely.
 367   // NOTE: We reuse the Worklist vector here for memory efficiency.
 368   for (Instruction &I : inst_range(F)) {
 369     // For live instructions that have all dead bits, first make them dead by
 370     // replacing all uses with something else. Then, if they don't need to
 371     // remain live (because they have side effects, etc.) we can remove them.
 372     if (I.getType()->isIntegerTy()) {
 373       auto ABI = AliveBits.find(&I);
 374       if (ABI != AliveBits.end()) {
 375         if (ABI->second.getBoolValue())
 376           continue;
 377
 378         DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n");
 379         // FIXME: In theory we could substitute undef here instead of zero.
 380         // This should be reconsidered once we settle on the semantics of
 381         // undef, poison, etc.
 382         Value *Zero = ConstantInt::get(I.getType(), 0);
 383         ++NumSimplified;
 384         I.replaceAllUsesWith(Zero);
 385         Changed = true;
 386       }
 387     } else if (Visited.count(&I)) {
 388       continue;
 389     }
 390
 391     if (isAlwaysLive(&I))
 392       continue;
 393
 394     Worklist.push_back(&I);
 395     I.dropAllReferences();
 396     Changed = true;
 397   }
 398
 399   for (Instruction *&I : Worklist) {
 400     ++NumRemoved;
 401     I->eraseFromParent();
 402   }
 403
 404   return Changed;
 405 }
 406
 407 FunctionPass *llvm::createBitTrackingDCEPass() {
 408   return new BDCE();
 409 }
 410