LCOV - code coverage report
Current view: top level - lib/Analysis - DemandedBits.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 174 178 97.8 %
Date: 2018-07-13 00:08:38 Functions: 16 17 94.1 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- DemandedBits.cpp - Determine demanded bits -------------------------===//
       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 pass implements a demanded bits analysis. A demanded bit is one that
      11             : // contributes to a result; bits that are not demanded can be either zero or
      12             : // one without affecting control or data flow. For example in this sequence:
      13             : //
      14             : //   %1 = add i32 %x, %y
      15             : //   %2 = trunc i32 %1 to i16
      16             : //
      17             : // Only the lowest 16 bits of %1 are demanded; the rest are removed by the
      18             : // trunc.
      19             : //
      20             : //===----------------------------------------------------------------------===//
      21             : 
      22             : #include "llvm/Analysis/DemandedBits.h"
      23             : #include "llvm/ADT/APInt.h"
      24             : #include "llvm/ADT/SmallPtrSet.h"
      25             : #include "llvm/ADT/SmallVector.h"
      26             : #include "llvm/ADT/StringExtras.h"
      27             : #include "llvm/Analysis/AssumptionCache.h"
      28             : #include "llvm/Analysis/ValueTracking.h"
      29             : #include "llvm/IR/BasicBlock.h"
      30             : #include "llvm/IR/Constants.h"
      31             : #include "llvm/IR/DataLayout.h"
      32             : #include "llvm/IR/DerivedTypes.h"
      33             : #include "llvm/IR/Dominators.h"
      34             : #include "llvm/IR/InstIterator.h"
      35             : #include "llvm/IR/InstrTypes.h"
      36             : #include "llvm/IR/Instruction.h"
      37             : #include "llvm/IR/IntrinsicInst.h"
      38             : #include "llvm/IR/Intrinsics.h"
      39             : #include "llvm/IR/Module.h"
      40             : #include "llvm/IR/Operator.h"
      41             : #include "llvm/IR/PassManager.h"
      42             : #include "llvm/IR/Type.h"
      43             : #include "llvm/IR/Use.h"
      44             : #include "llvm/Pass.h"
      45             : #include "llvm/Support/Casting.h"
      46             : #include "llvm/Support/Debug.h"
      47             : #include "llvm/Support/KnownBits.h"
      48             : #include "llvm/Support/raw_ostream.h"
      49             : #include <algorithm>
      50             : #include <cstdint>
      51             : 
      52             : using namespace llvm;
      53             : 
      54             : #define DEBUG_TYPE "demanded-bits"
      55             : 
      56             : char DemandedBitsWrapperPass::ID = 0;
      57             : 
      58       31825 : INITIALIZE_PASS_BEGIN(DemandedBitsWrapperPass, "demanded-bits",
      59             :                       "Demanded bits analysis", false, false)
      60       31825 : INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
      61       31825 : INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
      62      283408 : INITIALIZE_PASS_END(DemandedBitsWrapperPass, "demanded-bits",
      63             :                     "Demanded bits analysis", false, false)
      64             : 
      65        8904 : DemandedBitsWrapperPass::DemandedBitsWrapperPass() : FunctionPass(ID) {
      66        4452 :   initializeDemandedBitsWrapperPassPass(*PassRegistry::getPassRegistry());
      67        4452 : }
      68             : 
      69        4452 : void DemandedBitsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
      70        4452 :   AU.setPreservesCFG();
      71             :   AU.addRequired<AssumptionCacheTracker>();
      72             :   AU.addRequired<DominatorTreeWrapperPass>();
      73             :   AU.setPreservesAll();
      74        4452 : }
      75             : 
      76           3 : void DemandedBitsWrapperPass::print(raw_ostream &OS, const Module *M) const {
      77           3 :   DB->print(OS);
      78           3 : }
      79             : 
      80     2388524 : static bool isAlwaysLive(Instruction *I) {
      81             :   return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
      82     4260247 :       I->isEHPad() || I->mayHaveSideEffects();
      83             : }
      84             : 
      85      575024 : void DemandedBits::determineLiveOperandBits(
      86             :     const Instruction *UserI, const Instruction *I, unsigned OperandNo,
      87             :     const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2) {
      88      575024 :   unsigned BitWidth = AB.getBitWidth();
      89             : 
      90             :   // We're called once per operand, but for some instructions, we need to
      91             :   // compute known bits of both operands in order to determine the live bits of
      92             :   // either (when both operands are instructions themselves). We don't,
      93             :   // however, want to do this twice, so we cache the result in APInts that live
      94             :   // in the caller. For the two-relevant-operands case, both operand values are
      95             :   // provided here.
      96             :   auto ComputeKnownBits =
      97        5033 :       [&](unsigned BitWidth, const Value *V1, const Value *V2) {
      98        5033 :         const DataLayout &DL = I->getModule()->getDataLayout();
      99       10066 :         Known = KnownBits(BitWidth);
     100       19880 :         computeKnownBits(V1, Known, DL, 0, &AC, UserI, &DT);
     101             : 
     102        5033 :         if (V2) {
     103        9814 :           Known2 = KnownBits(BitWidth);
     104       14721 :           computeKnownBits(V2, Known2, DL, 0, &AC, UserI, &DT);
     105             :         }
     106      580057 :       };
     107             : 
     108     1150048 :   switch (UserI->getOpcode()) {
     109             :   default: break;
     110        4934 :   case Instruction::Call:
     111             :   case Instruction::Invoke:
     112             :     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
     113         297 :       switch (II->getIntrinsicID()) {
     114             :       default: break;
     115          46 :       case Intrinsic::bswap:
     116             :         // The alive bits of the input are the swapped alive bits of
     117             :         // the output.
     118          92 :         AB = AOut.byteSwap();
     119          46 :         break;
     120           8 :       case Intrinsic::bitreverse:
     121             :         // The alive bits of the input are the reversed alive bits of
     122             :         // the output.
     123          16 :         AB = AOut.reverseBits();
     124           8 :         break;
     125          70 :       case Intrinsic::ctlz:
     126          70 :         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          70 :           ComputeKnownBits(BitWidth, I, nullptr);
     131         140 :           AB = APInt::getHighBitsSet(BitWidth,
     132         140 :                  std::min(BitWidth, Known.countMaxLeadingZeros()+1));
     133             :         }
     134             :         break;
     135          56 :       case Intrinsic::cttz:
     136          56 :         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          56 :           ComputeKnownBits(BitWidth, I, nullptr);
     141         112 :           AB = APInt::getLowBitsSet(BitWidth,
     142         112 :                  std::min(BitWidth, Known.countMaxTrailingZeros()+1));
     143             :         }
     144             :         break;
     145             :       }
     146             :     break;
     147             :   case Instruction::Add:
     148             :   case Instruction::Sub:
     149             :   case Instruction::Mul:
     150             :     // Find the highest live output bit. We don't need any more input
     151             :     // bits than that (adds, and thus subtracts, ripple only to the
     152             :     // left).
     153      815364 :     AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
     154      407682 :     break;
     155        2039 :   case Instruction::Shl:
     156        2039 :     if (OperandNo == 0)
     157        1252 :       if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
     158        1142 :         uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
     159        2284 :         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        1142 :         const ShlOperator *S = cast<ShlOperator>(UserI);
     164        1142 :         if (S->hasNoSignedWrap())
     165         342 :           AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
     166         971 :         else if (S->hasNoUnsignedWrap())
     167          60 :           AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
     168             :       }
     169             :     break;
     170        1532 :   case Instruction::LShr:
     171        1532 :     if (OperandNo == 0)
     172        1332 :       if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
     173        1194 :         uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
     174        2388 :         AB = AOut.shl(ShiftAmt);
     175             : 
     176             :         // If the shift is exact, then the low bits are not dead
     177             :         // (they must be zero).
     178        2388 :         if (cast<LShrOperator>(UserI)->isExact())
     179         302 :           AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
     180             :       }
     181             :     break;
     182        1303 :   case Instruction::AShr:
     183        1303 :     if (OperandNo == 0)
     184        1302 :       if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
     185        1302 :         uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
     186        2604 :         AB = AOut.shl(ShiftAmt);
     187             :         // Because the high input bit is replicated into the
     188             :         // high-order bits of the result, if we need any of those
     189             :         // bits, then we must keep the highest input bit.
     190        3906 :         if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
     191             :             .getBoolValue())
     192        1300 :           AB.setSignBit();
     193             : 
     194             :         // If the shift is exact, then the low bits are not dead
     195             :         // (they must be zero).
     196        2604 :         if (cast<AShrOperator>(UserI)->isExact())
     197        2512 :           AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
     198             :       }
     199             :     break;
     200        3950 :   case Instruction::And:
     201        3950 :     AB = AOut;
     202             : 
     203             :     // For bits that are known zero, the corresponding bits in the
     204             :     // other operand are dead (unless they're both zero, in which
     205             :     // case they can't both be dead, so just mark the LHS bits as
     206             :     // dead).
     207        3950 :     if (OperandNo == 0) {
     208        5900 :       ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
     209        8850 :       AB &= ~Known2.Zero;
     210             :     } else {
     211        2000 :       if (!isa<Instruction>(UserI->getOperand(0)))
     212           0 :         ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
     213        6000 :       AB &= ~(Known.Zero & ~Known2.Zero);
     214             :     }
     215             :     break;
     216        3000 :   case Instruction::Or:
     217        3000 :     AB = AOut;
     218             : 
     219             :     // For bits that are known one, the corresponding bits in the
     220             :     // other operand are dead (unless they're both one, in which
     221             :     // case they can't both be dead, so just mark the LHS bits as
     222             :     // dead).
     223        3000 :     if (OperandNo == 0) {
     224        3914 :       ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
     225        5871 :       AB &= ~Known2.One;
     226             :     } else {
     227        2086 :       if (!isa<Instruction>(UserI->getOperand(0)))
     228           0 :         ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
     229        6258 :       AB &= ~(Known.One & ~Known2.One);
     230             :     }
     231             :     break;
     232       42625 :   case Instruction::Xor:
     233             :   case Instruction::PHI:
     234       42625 :     AB = AOut;
     235       42625 :     break;
     236        1107 :   case Instruction::Trunc:
     237        2214 :     AB = AOut.zext(BitWidth);
     238        1107 :     break;
     239        4626 :   case Instruction::ZExt:
     240        9252 :     AB = AOut.trunc(BitWidth);
     241        4626 :     break;
     242         817 :   case Instruction::SExt:
     243        1634 :     AB = AOut.trunc(BitWidth);
     244             :     // Because the high input bit is replicated into the
     245             :     // high-order bits of the result, if we need any of those
     246             :     // bits, then we must keep the highest input bit.
     247        2451 :     if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
     248         817 :                                       AOut.getBitWidth() - BitWidth))
     249             :         .getBoolValue())
     250         811 :       AB.setSignBit();
     251             :     break;
     252       31093 :   case Instruction::Select:
     253       31093 :     if (OperandNo != 0)
     254         678 :       AB = AOut;
     255             :     break;
     256             :   }
     257      575024 : }
     258             : 
     259       56957 : bool DemandedBitsWrapperPass::runOnFunction(Function &F) {
     260       56957 :   auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     261       56957 :   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     262       56957 :   DB.emplace(F, AC, DT);
     263       56957 :   return false;
     264             : }
     265             : 
     266       56957 : void DemandedBitsWrapperPass::releaseMemory() {
     267             :   DB.reset();
     268       56957 : }
     269             : 
     270     2418212 : void DemandedBits::performAnalysis() {
     271     2418212 :   if (Analyzed)
     272             :     // Analysis already completed for this function.
     273     2381877 :     return;
     274       36335 :   Analyzed = true;
     275             :   
     276       36335 :   Visited.clear();
     277       36335 :   AliveBits.clear();
     278             : 
     279             :   SmallVector<Instruction*, 128> Worklist;
     280             : 
     281             :   // Collect the set of "root" instructions that are known live.
     282     2194840 :   for (Instruction &I : instructions(F)) {
     283     2158505 :     if (!isAlwaysLive(&I))
     284     1199925 :       continue;
     285             : 
     286             :     LLVM_DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
     287             :     // For integer-valued instructions, set up an initial empty set of alive
     288             :     // bits and add the instruction to the work list. For other instructions
     289             :     // add their operands to the work list (for integer values operands, mark
     290             :     // all bits as live).
     291      968100 :     if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
     292       19040 :       if (AliveBits.try_emplace(&I, IT->getBitWidth(), 0).second)
     293        9517 :         Worklist.push_back(&I);
     294             : 
     295        9520 :       continue;
     296             :     }
     297             : 
     298             :     // Non-integer-typed instructions...
     299     6338944 :     for (Use &OI : I.operands()) {
     300     2220412 :       if (Instruction *J = dyn_cast<Instruction>(OI)) {
     301      686554 :         if (IntegerType *IT = dyn_cast<IntegerType>(J->getType()))
     302      915056 :           AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth());
     303      686554 :         Worklist.push_back(J);
     304             :       }
     305             :     }
     306             :     // To save memory, we don't add I to the Visited set here. Instead, we
     307             :     // check isAlwaysLive on every instruction when searching for dead
     308             :     // instructions later (we need to check isAlwaysLive for the
     309             :     // integer-typed instructions anyway).
     310             :   }
     311             : 
     312             :   // Propagate liveness backwards to operands.
     313     2756583 :   while (!Worklist.empty()) {
     314     1360124 :     Instruction *UserI = Worklist.pop_back_val();
     315             : 
     316             :     LLVM_DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
     317             :     APInt AOut;
     318     2720248 :     if (UserI->getType()->isIntegerTy()) {
     319      965005 :       AOut = AliveBits[UserI];
     320             :       LLVM_DEBUG(dbgs() << " Alive Out: " << AOut);
     321             :     }
     322             :     LLVM_DEBUG(dbgs() << "\n");
     323             : 
     324     2720248 :     if (!UserI->getType()->isIntegerTy())
     325      395119 :       Visited.insert(UserI);
     326             : 
     327     1360124 :     KnownBits Known, Known2;
     328             :     // Compute the set of alive bits for each operand. These are anded into the
     329             :     // existing set, if any, and if that changes the set of alive bits, the
     330             :     // operand is added to the work-list.
     331     7295446 :     for (Use &OI : UserI->operands()) {
     332     2287599 :       if (Instruction *I = dyn_cast<Instruction>(OI)) {
     333      912418 :         if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
     334             :           unsigned BitWidth = IT->getBitWidth();
     335      575027 :           APInt AB = APInt::getAllOnesValue(BitWidth);
     336     1679196 :           if (UserI->getType()->isIntegerTy() && !AOut &&
     337         372 :               !isAlwaysLive(UserI)) {
     338           3 :             AB = APInt(BitWidth, 0);
     339             :           } else {
     340             :             // If all bits of the output are dead, then all bits of the input
     341             :             // Bits of each operand that are used to compute alive bits of the
     342             :             // output are alive, all others are dead.
     343      575024 :             determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB,
     344             :                                      Known, Known2);
     345             :           }
     346             : 
     347             :           // If we've added to the set of alive bits (or the operand has not
     348             :           // been previously visited), then re-queue the operand to be visited
     349             :           // again.
     350             :           APInt ABPrev(BitWidth, 0);
     351      575027 :           auto ABI = AliveBits.find(I);
     352      575027 :           if (ABI != AliveBits.end())
     353       80894 :             ABPrev = ABI->second;
     354             : 
     355      575027 :           APInt ABNew = AB | ABPrev;
     356      652137 :           if (ABNew != ABPrev || ABI == AliveBits.end()) {
     357             :             AliveBits[I] = std::move(ABNew);
     358      497960 :             Worklist.push_back(I);
     359             :           }
     360      337391 :         } else if (!Visited.count(I)) {
     361      166093 :           Worklist.push_back(I);
     362             :         }
     363             :       }
     364             :     }
     365             :   }
     366             : }
     367             : 
     368      951606 : APInt DemandedBits::getDemandedBits(Instruction *I) {
     369      951606 :   performAnalysis();
     370             :   
     371      951606 :   const DataLayout &DL = I->getModule()->getDataLayout();
     372      951606 :   auto Found = AliveBits.find(I);
     373      951606 :   if (Found != AliveBits.end())
     374      951457 :     return Found->second;
     375         149 :   return APInt::getAllOnesValue(DL.getTypeSizeInBits(I->getType()));
     376             : }
     377             : 
     378     1466600 : bool DemandedBits::isInstructionDead(Instruction *I) {
     379     1466600 :   performAnalysis();
     380             : 
     381     2875207 :   return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
     382     1696247 :     !isAlwaysLive(I);
     383             : }
     384             : 
     385           6 : void DemandedBits::print(raw_ostream &OS) {
     386           6 :   performAnalysis();
     387          30 :   for (auto &KV : AliveBits) {
     388          54 :     OS << "DemandedBits: 0x" << Twine::utohexstr(KV.second.getLimitedValue())
     389          18 :        << " for " << *KV.first << '\n';
     390             :   }
     391           6 : }
     392             : 
     393           0 : FunctionPass *llvm::createDemandedBitsWrapperPass() {
     394           0 :   return new DemandedBitsWrapperPass();
     395             : }
     396             : 
     397             : AnalysisKey DemandedBitsAnalysis::Key;
     398             : 
     399         246 : DemandedBits DemandedBitsAnalysis::run(Function &F,
     400             :                                              FunctionAnalysisManager &AM) {
     401             :   auto &AC = AM.getResult<AssumptionAnalysis>(F);
     402             :   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
     403         246 :   return DemandedBits(F, AC, DT);
     404             : }
     405             : 
     406           3 : PreservedAnalyses DemandedBitsPrinterPass::run(Function &F,
     407             :                                                FunctionAnalysisManager &AM) {
     408           3 :   AM.getResult<DemandedBitsAnalysis>(F).print(OS);
     409           3 :   return PreservedAnalyses::all();
     410             : }

Generated by: LCOV version 1.13