lib/Transforms/Scalar/BDCE.cpp

   1 //===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the Bit-Tracking Dead Code Elimination pass. Some
  10 // instructions (shifts, some ands, ors, etc.) kill some of their input bits.
  11 // We track these dead bits and remove instructions that compute only these
  12 // dead bits.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/Scalar/BDCE.h"
  17 #include "llvm/ADT/SmallPtrSet.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/Analysis/DemandedBits.h"
  21 #include "llvm/Analysis/GlobalsModRef.h"
  22 #include "llvm/Transforms/Utils/Local.h"
  23 #include "llvm/IR/InstIterator.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/Pass.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include "llvm/Transforms/Scalar.h"
  29 using namespace llvm;
  30
  31 #define DEBUG_TYPE "bdce"
  32
  33 STATISTIC(NumRemoved, "Number of instructions removed (unused)");
  34 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");
  35
  36 /// If an instruction is trivialized (dead), then the chain of users of that
  37 /// instruction may need to be cleared of assumptions that can no longer be
  38 /// guaranteed correct.
  39 static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) {
  40   assert(I->getType()->isIntOrIntVectorTy() &&
  41          "Trivializing a non-integer value?");
  42
  43   // Initialize the worklist with eligible direct users.
  44   SmallVector<Instruction *, 16> WorkList;
  45   for (User *JU : I->users()) {
  46     // If all bits of a user are demanded, then we know that nothing below that
  47     // in the def-use chain needs to be changed.
  48     auto *J = dyn_cast<Instruction>(JU);
  49     if (J && J->getType()->isIntOrIntVectorTy() &&
  50         !DB.getDemandedBits(J).isAllOnesValue())
  51       WorkList.push_back(J);
  52
  53     // Note that we need to check for non-int types above before asking for
  54     // demanded bits. Normally, the only way to reach an instruction with an
  55     // non-int type is via an instruction that has side effects (or otherwise
  56     // will demand its input bits). However, if we have a readnone function
  57     // that returns an unsized type (e.g., void), we must avoid asking for the
  58     // demanded bits of the function call's return value. A void-returning
  59     // readnone function is always dead (and so we can stop walking the use/def
  60     // chain here), but the check is necessary to avoid asserting.
  61   }
  62
  63   // DFS through subsequent users while tracking visits to avoid cycles.
  64   SmallPtrSet<Instruction *, 16> Visited;
  65   while (!WorkList.empty()) {
  66     Instruction *J = WorkList.pop_back_val();
  67
  68     // NSW, NUW, and exact are based on operands that might have changed.
  69     J->dropPoisonGeneratingFlags();
  70
  71     // We do not have to worry about llvm.assume or range metadata:
  72     // 1. llvm.assume demands its operand, so trivializing can't change it.
  73     // 2. range metadata only applies to memory accesses which demand all bits.
  74
  75     Visited.insert(J);
  76
  77     for (User *KU : J->users()) {
  78       // If all bits of a user are demanded, then we know that nothing below
  79       // that in the def-use chain needs to be changed.
  80       auto *K = dyn_cast<Instruction>(KU);
  81       if (K && !Visited.count(K) && K->getType()->isIntOrIntVectorTy() &&
  82           !DB.getDemandedBits(K).isAllOnesValue())
  83         WorkList.push_back(K);
  84     }
  85   }
  86 }
  87
  88 static bool bitTrackingDCE(Function &F, DemandedBits &DB) {
  89   SmallVector<Instruction*, 128> Worklist;
  90   bool Changed = false;
  91   for (Instruction &I : instructions(F)) {
  92     // If the instruction has side effects and no non-dbg uses,
  93     // skip it. This way we avoid computing known bits on an instruction
  94     // that will not help us.
  95     if (I.mayHaveSideEffects() && I.use_empty())
  96       continue;
  97
  98     // Remove instructions that are dead, either because they were not reached
  99     // during analysis or have no demanded bits.
 100     if (DB.isInstructionDead(&I) ||
 101         (I.getType()->isIntOrIntVectorTy() &&
 102          DB.getDemandedBits(&I).isNullValue() &&
 103          wouldInstructionBeTriviallyDead(&I))) {
 104       salvageDebugInfo(I);
 105       Worklist.push_back(&I);
 106       I.dropAllReferences();
 107       Changed = true;
 108       continue;
 109     }
 110
 111     for (Use &U : I.operands()) {
 112       // DemandedBits only detects dead integer uses.
 113       if (!U->getType()->isIntOrIntVectorTy())
 114         continue;
 115
 116       if (!isa<Instruction>(U) && !isa<Argument>(U))
 117         continue;
 118
 119       if (!DB.isUseDead(&U))
 120         continue;
 121
 122       LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");
 123
 124       clearAssumptionsOfUsers(&I, DB);
 125
 126       // FIXME: In theory we could substitute undef here instead of zero.
 127       // This should be reconsidered once we settle on the semantics of
 128       // undef, poison, etc.
 129       U.set(ConstantInt::get(U->getType(), 0));
 130       ++NumSimplified;
 131       Changed = true;
 132     }
 133   }
 134
 135   for (Instruction *&I : Worklist) {
 136     ++NumRemoved;
 137     I->eraseFromParent();
 138   }
 139
 140   return Changed;
 141 }
 142
 143 PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) {
 144   auto &DB = AM.getResult<DemandedBitsAnalysis>(F);
 145   if (!bitTrackingDCE(F, DB))
 146     return PreservedAnalyses::all();
 147
 148   PreservedAnalyses PA;
 149   PA.preserveSet<CFGAnalyses>();
 150   PA.preserve<GlobalsAA>();
 151   return PA;
 152 }
 153
 154 namespace {
 155 struct BDCELegacyPass : public FunctionPass {
 156   static char ID; // Pass identification, replacement for typeid
 157   BDCELegacyPass() : FunctionPass(ID) {
 158     initializeBDCELegacyPassPass(*PassRegistry::getPassRegistry());
 159   }
 160
 161   bool runOnFunction(Function &F) override {
 162     if (skipFunction(F))
 163       return false;
 164     auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits();
 165     return bitTrackingDCE(F, DB);
 166   }
 167
 168   void getAnalysisUsage(AnalysisUsage &AU) const override {
 169     AU.setPreservesCFG();
 170     AU.addRequired<DemandedBitsWrapperPass>();
 171     AU.addPreserved<GlobalsAAWrapperPass>();
 172   }
 173 };
 174 }
 175
 176 char BDCELegacyPass::ID = 0;
 177 INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce",
 178                       "Bit-Tracking Dead Code Elimination", false, false)
 179 INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass)
 180 INITIALIZE_PASS_END(BDCELegacyPass, "bdce",
 181                     "Bit-Tracking Dead Code Elimination", false, false)
 182
 183 FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); }