LCOV - code coverage report
Current view: top level - lib/Analysis - DemandedBits.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 190 194 97.9 %
Date: 2017-09-14 15:23:50 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       26580 : INITIALIZE_PASS_BEGIN(DemandedBitsWrapperPass, "demanded-bits",
      59             :                       "Demanded bits analysis", false, false)
      60       26580 : INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
      61       26580 : INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
      62      328722 : INITIALIZE_PASS_END(DemandedBitsWrapperPass, "demanded-bits",
      63             :                     "Demanded bits analysis", false, false)
      64             : 
      65       10125 : DemandedBitsWrapperPass::DemandedBitsWrapperPass() : FunctionPass(ID) {
      66        3375 :   initializeDemandedBitsWrapperPassPass(*PassRegistry::getPassRegistry());
      67        3375 : }
      68             : 
      69        3375 : void DemandedBitsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
      70        3375 :   AU.setPreservesCFG();
      71        3375 :   AU.addRequired<AssumptionCacheTracker>();
      72        3375 :   AU.addRequired<DominatorTreeWrapperPass>();
      73        3375 :   AU.setPreservesAll();
      74        3375 : }
      75             : 
      76           3 : void DemandedBitsWrapperPass::print(raw_ostream &OS, const Module *M) const {
      77           6 :   DB->print(OS);
      78           3 : }
      79             : 
      80     2219506 : static bool isAlwaysLive(Instruction *I) {
      81     4133767 :   return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
      82     5760133 :       I->isEHPad() || I->mayHaveSideEffects();
      83             : }
      84             : 
      85      524701 : void DemandedBits::determineLiveOperandBits(
      86             :     const Instruction *UserI, const Instruction *I, unsigned OperandNo,
      87             :     const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2) {
      88      524701 :   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        4310 :       [&](unsigned BitWidth, const Value *V1, const Value *V2) {
      98        4310 :         const DataLayout &DL = I->getModule()->getDataLayout();
      99        8620 :         Known = KnownBits(BitWidth);
     100       17110 :         computeKnownBits(V1, Known, DL, 0, &AC, UserI, &DT);
     101             : 
     102        4310 :         if (V2) {
     103        8490 :           Known2 = KnownBits(BitWidth);
     104       12735 :           computeKnownBits(V2, Known2, DL, 0, &AC, UserI, &DT);
     105             :         }
     106      529011 :       };
     107             : 
     108     1049402 :   switch (UserI->getOpcode()) {
     109             :   default: break;
     110        4460 :   case Instruction::Call:
     111             :   case Instruction::Invoke:
     112        4702 :     if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
     113         242 :       switch (II->getIntrinsicID()) {
     114             :       default: break;
     115          45 :       case Intrinsic::bswap:
     116             :         // The alive bits of the input are the swapped alive bits of
     117             :         // the output.
     118         135 :         AB = AOut.byteSwap();
     119          45 :         break;
     120           7 :       case Intrinsic::bitreverse:
     121             :         // The alive bits of the input are the reversed alive bits of
     122             :         // the output.
     123          21 :         AB = AOut.reverseBits();
     124           7 :         break;
     125          47 :       case Intrinsic::ctlz:
     126          47 :         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          47 :           ComputeKnownBits(BitWidth, I, nullptr);
     131         141 :           AB = APInt::getHighBitsSet(BitWidth,
     132         141 :                  std::min(BitWidth, Known.countMaxLeadingZeros()+1));
     133             :         }
     134             :         break;
     135          18 :       case Intrinsic::cttz:
     136          18 :         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          18 :           ComputeKnownBits(BitWidth, I, nullptr);
     141          54 :           AB = APInt::getLowBitsSet(BitWidth,
     142          54 :                  std::min(BitWidth, Known.countMaxTrailingZeros()+1));
     143             :         }
     144             :         break;
     145             :       }
     146             :     break;
     147      371424 :   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     1114272 :     AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
     154      371424 :     break;
     155        1565 :   case Instruction::Shl:
     156        1565 :     if (OperandNo == 0)
     157        3060 :       if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
     158        2040 :         uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
     159        3060 :         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        2040 :         const ShlOperator *S = cast<ShlOperator>(UserI);
     164        2040 :         if (S->hasNoSignedWrap())
     165         435 :           AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
     166         875 :         else if (S->hasNoUnsignedWrap())
     167         114 :           AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
     168             :       }
     169             :     break;
     170        1163 :   case Instruction::LShr:
     171        1163 :     if (OperandNo == 0)
     172        3346 :       if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
     173        2196 :         uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
     174        3294 :         AB = AOut.shl(ShiftAmt);
     175             : 
     176             :         // If the shift is exact, then the low bits are not dead
     177             :         // (they must be zero).
     178        3294 :         if (cast<LShrOperator>(UserI)->isExact())
     179         393 :           AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
     180             :       }
     181             :     break;
     182        1203 :   case Instruction::AShr:
     183        1203 :     if (OperandNo == 0)
     184        3606 :       if (auto *ShiftAmtC = dyn_cast<ConstantInt>(UserI->getOperand(1))) {
     185        2404 :         uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
     186        3606 :         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        4808 :         if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
     191        1202 :             .getBoolValue())
     192        1194 :           AB.setSignBit();
     193             : 
     194             :         // If the shift is exact, then the low bits are not dead
     195             :         // (they must be zero).
     196        3606 :         if (cast<AShrOperator>(UserI)->isExact())
     197        3408 :           AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
     198             :       }
     199             :     break;
     200        3243 :   case Instruction::And:
     201        3243 :     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        3243 :     if (OperandNo == 0) {
     208        4880 :       ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
     209       14640 :       AB &= ~Known2.Zero;
     210             :     } else {
     211        2409 :       if (!isa<Instruction>(UserI->getOperand(0)))
     212           0 :         ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
     213        8030 :       AB &= ~(Known.Zero & ~Known2.Zero);
     214             :     }
     215             :     break;
     216        2680 :   case Instruction::Or:
     217        2680 :     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        2680 :     if (OperandNo == 0) {
     224        3610 :       ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
     225       10830 :       AB &= ~Known2.One;
     226             :     } else {
     227        2625 :       if (!isa<Instruction>(UserI->getOperand(0)))
     228           0 :         ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
     229        8750 :       AB &= ~(Known.One & ~Known2.One);
     230             :     }
     231             :     break;
     232       39827 :   case Instruction::Xor:
     233             :   case Instruction::PHI:
     234       39827 :     AB = AOut;
     235       39827 :     break;
     236        1003 :   case Instruction::Trunc:
     237        3009 :     AB = AOut.zext(BitWidth);
     238        1003 :     break;
     239        4190 :   case Instruction::ZExt:
     240       12570 :     AB = AOut.trunc(BitWidth);
     241        4190 :     break;
     242         359 :   case Instruction::SExt:
     243        1077 :     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        1436 :     if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
     248         359 :                                       AOut.getBitWidth() - BitWidth))
     249         359 :         .getBoolValue())
     250         354 :       AB.setSignBit();
     251             :     break;
     252       28930 :   case Instruction::Select:
     253       28930 :     if (OperandNo != 0)
     254         537 :       AB = AOut;
     255             :     break;
     256             :   }
     257      524701 : }
     258             : 
     259       54680 : bool DemandedBitsWrapperPass::runOnFunction(Function &F) {
     260       54680 :   auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     261      109360 :   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     262       54680 :   DB.emplace(F, AC, DT);
     263       54680 :   return false;
     264             : }
     265             : 
     266       54680 : void DemandedBitsWrapperPass::releaseMemory() {
     267      109360 :   DB.reset();
     268       54680 : }
     269             : 
     270     2208275 : void DemandedBits::performAnalysis() {
     271     2208275 :   if (Analyzed)
     272             :     // Analysis already completed for this function.
     273     2174275 :     return;
     274       34000 :   Analyzed = true;
     275             :   
     276       34000 :   Visited.clear();
     277       34000 :   AliveBits.clear();
     278             : 
     279       68000 :   SmallVector<Instruction*, 128> Worklist;
     280             : 
     281             :   // Collect the set of "root" instructions that are known live.
     282     4132884 :   for (Instruction &I : instructions(F)) {
     283     2015442 :     if (!isAlwaysLive(&I))
     284     1098799 :       continue;
     285             : 
     286             :     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      934595 :     if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
     292       17952 :       if (AliveBits.try_emplace(&I, IT->getBitWidth(), 0).second)
     293        8973 :         Worklist.push_back(&I);
     294             : 
     295        8976 :       continue;
     296             :     }
     297             : 
     298             :     // Non-integer-typed instructions...
     299     4036490 :     for (Use &OI : I.operands()) {
     300     2221156 :       if (Instruction *J = dyn_cast<Instruction>(OI)) {
     301     1050780 :         if (IntegerType *IT = dyn_cast<IntegerType>(J->getType()))
     302     1669456 :           AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth());
     303      633416 :         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     2533250 :   while (!Worklist.empty()) {
     314     1249625 :     Instruction *UserI = Worklist.pop_back_val();
     315             : 
     316             :     DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
     317     2499250 :     APInt AOut;
     318     2499250 :     if (UserI->getType()->isIntegerTy()) {
     319     1758336 :       AOut = AliveBits[UserI];
     320             :       DEBUG(dbgs() << " Alive Out: " << AOut);
     321             :     }
     322             :     DEBUG(dbgs() << "\n");
     323             : 
     324     2499250 :     if (!UserI->getType()->isIntegerTy())
     325      370457 :       Visited.insert(UserI);
     326             : 
     327     3748875 :     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     4603079 :     for (Use &OI : UserI->operands()) {
     332     2103829 :       if (Instruction *I = dyn_cast<Instruction>(OI)) {
     333     1363062 :         if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
     334      524704 :           unsigned BitWidth = IT->getBitWidth();
     335     1049408 :           APInt AB = APInt::getAllOnesValue(BitWidth);
     336     1532062 :           if (UserI->getType()->isIntegerTy() && !AOut &&
     337         361 :               !isAlwaysLive(UserI)) {
     338           9 :             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      524701 :             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     1049408 :           APInt ABPrev(BitWidth, 0);
     351      524704 :           auto ABI = AliveBits.find(I);
     352     1574112 :           if (ABI != AliveBits.end())
     353       75292 :             ABPrev = ABI->second;
     354             : 
     355     2098816 :           APInt ABNew = AB | ABPrev;
     356      668500 :           if (ABNew != ABPrev || ABI == AliveBits.end()) {
     357     1358493 :             AliveBits[I] = std::move(ABNew);
     358      452831 :             Worklist.push_back(I);
     359             :           }
     360      313654 :         } else if (!Visited.count(I)) {
     361      154405 :           Worklist.push_back(I);
     362             :         }
     363             :       }
     364             :     }
     365             :   }
     366             : }
     367             : 
     368      867572 : APInt DemandedBits::getDemandedBits(Instruction *I) {
     369      867572 :   performAnalysis();
     370             :   
     371      867572 :   const DataLayout &DL = I->getModule()->getDataLayout();
     372      867572 :   auto Found = AliveBits.find(I);
     373     2602716 :   if (Found != AliveBits.end())
     374      867448 :     return Found->second;
     375         124 :   return APInt::getAllOnesValue(DL.getTypeSizeInBits(I->getType()));
     376             : }
     377             : 
     378     1340696 : bool DemandedBits::isInstructionDead(Instruction *I) {
     379     1340696 :   performAnalysis();
     380             : 
     381     3684618 :   return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
     382     1544400 :     !isAlwaysLive(I);
     383             : }
     384             : 
     385           6 : void DemandedBits::print(raw_ostream &OS) {
     386           6 :   performAnalysis();
     387          36 :   for (auto &KV : AliveBits) {
     388          72 :     OS << "DemandedBits: 0x" << utohexstr(KV.second.getLimitedValue()) << " for "
     389          36 :        << *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         201 : DemandedBits DemandedBitsAnalysis::run(Function &F,
     400             :                                              FunctionAnalysisManager &AM) {
     401         201 :   auto &AC = AM.getResult<AssumptionAnalysis>(F);
     402         201 :   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
     403         201 :   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