211 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the Bit-Tracking Dead Code Elimination pass. Some10// instructions (shifts, some ands, ors, etc.) kill some of their input bits.11// We track these dead bits and remove instructions that compute only these12// dead bits. We also simplify sext that generates unused extension bits,13// converting it to a zext.14//15//===----------------------------------------------------------------------===//16 17#include "llvm/Transforms/Scalar/BDCE.h"18#include "llvm/ADT/SmallPtrSet.h"19#include "llvm/ADT/SmallVector.h"20#include "llvm/ADT/Statistic.h"21#include "llvm/Analysis/DemandedBits.h"22#include "llvm/Analysis/GlobalsModRef.h"23#include "llvm/IR/IRBuilder.h"24#include "llvm/IR/InstIterator.h"25#include "llvm/IR/Instructions.h"26#include "llvm/IR/PatternMatch.h"27#include "llvm/Support/Debug.h"28#include "llvm/Support/raw_ostream.h"29#include "llvm/Transforms/Utils/Local.h"30 31using namespace llvm;32using namespace PatternMatch;33 34#define DEBUG_TYPE "bdce"35 36STATISTIC(NumRemoved, "Number of instructions removed (unused)");37STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)");38STATISTIC(NumSExt2ZExt,39 "Number of sign extension instructions converted to zero extension");40 41/// If an instruction is trivialized (dead), then the chain of users of that42/// instruction may need to be cleared of assumptions that can no longer be43/// guaranteed correct.44static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) {45 assert(I->getType()->isIntOrIntVectorTy() &&46 "Trivializing a non-integer value?");47 48 // If all bits of a user are demanded, then we know that nothing below that49 // in the def-use chain needs to be changed.50 if (DB.getDemandedBits(I).isAllOnes())51 return;52 53 // Initialize the worklist with eligible direct users.54 SmallPtrSet<Instruction *, 16> Visited;55 SmallVector<Instruction *, 16> WorkList;56 for (User *JU : I->users()) {57 auto *J = cast<Instruction>(JU);58 if (J->getType()->isIntOrIntVectorTy()) {59 Visited.insert(J);60 WorkList.push_back(J);61 }62 63 // Note that we need to check for non-int types above before asking for64 // demanded bits. Normally, the only way to reach an instruction with an65 // non-int type is via an instruction that has side effects (or otherwise66 // will demand its input bits). However, if we have a readnone function67 // that returns an unsized type (e.g., void), we must avoid asking for the68 // demanded bits of the function call's return value. A void-returning69 // readnone function is always dead (and so we can stop walking the use/def70 // chain here), but the check is necessary to avoid asserting.71 }72 73 // DFS through subsequent users while tracking visits to avoid cycles.74 while (!WorkList.empty()) {75 Instruction *J = WorkList.pop_back_val();76 77 // NSW, NUW, and exact are based on operands that might have changed.78 J->dropPoisonGeneratingAnnotations();79 80 // We do not have to worry about llvm.assume, because it demands its81 // operand, so trivializing can't change it.82 83 // If all bits of a user are demanded, then we know that nothing below84 // that in the def-use chain needs to be changed.85 if (DB.getDemandedBits(J).isAllOnes())86 continue;87 88 for (User *KU : J->users()) {89 auto *K = cast<Instruction>(KU);90 if (Visited.insert(K).second && K->getType()->isIntOrIntVectorTy())91 WorkList.push_back(K);92 }93 }94}95 96static bool bitTrackingDCE(Function &F, DemandedBits &DB) {97 SmallVector<Instruction*, 128> Worklist;98 bool Changed = false;99 for (Instruction &I : instructions(F)) {100 // If the instruction has side effects and no non-dbg uses,101 // skip it. This way we avoid computing known bits on an instruction102 // that will not help us.103 if (I.mayHaveSideEffects() && I.use_empty())104 continue;105 106 // Remove instructions that are dead, either because they were not reached107 // during analysis or have no demanded bits.108 if (DB.isInstructionDead(&I) ||109 (I.getType()->isIntOrIntVectorTy() && DB.getDemandedBits(&I).isZero() &&110 wouldInstructionBeTriviallyDead(&I))) {111 Worklist.push_back(&I);112 Changed = true;113 continue;114 }115 116 // Convert SExt into ZExt if none of the extension bits is required117 if (SExtInst *SE = dyn_cast<SExtInst>(&I)) {118 APInt Demanded = DB.getDemandedBits(SE);119 const uint32_t SrcBitSize = SE->getSrcTy()->getScalarSizeInBits();120 auto *const DstTy = SE->getDestTy();121 const uint32_t DestBitSize = DstTy->getScalarSizeInBits();122 if (Demanded.countl_zero() >= (DestBitSize - SrcBitSize)) {123 clearAssumptionsOfUsers(SE, DB);124 IRBuilder<> Builder(SE);125 I.replaceAllUsesWith(126 Builder.CreateZExt(SE->getOperand(0), DstTy, SE->getName()));127 Worklist.push_back(SE);128 Changed = true;129 NumSExt2ZExt++;130 continue;131 }132 }133 134 // Simplify and, or, xor when their mask does not affect the demanded bits.135 if (auto *BO = dyn_cast<BinaryOperator>(&I)) {136 APInt Demanded = DB.getDemandedBits(BO);137 if (!Demanded.isAllOnes()) {138 const APInt *Mask;139 if (match(BO->getOperand(1), m_APInt(Mask))) {140 bool CanBeSimplified = false;141 switch (BO->getOpcode()) {142 case Instruction::Or:143 case Instruction::Xor:144 CanBeSimplified = !Demanded.intersects(*Mask);145 break;146 case Instruction::And:147 CanBeSimplified = Demanded.isSubsetOf(*Mask);148 break;149 default:150 // TODO: Handle more cases here.151 break;152 }153 154 if (CanBeSimplified) {155 clearAssumptionsOfUsers(BO, DB);156 BO->replaceAllUsesWith(BO->getOperand(0));157 Worklist.push_back(BO);158 ++NumSimplified;159 Changed = true;160 continue;161 }162 }163 }164 }165 166 for (Use &U : I.operands()) {167 // DemandedBits only detects dead integer uses.168 if (!U->getType()->isIntOrIntVectorTy())169 continue;170 171 if (!isa<Instruction>(U) && !isa<Argument>(U))172 continue;173 174 if (!DB.isUseDead(&U))175 continue;176 177 LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n");178 179 clearAssumptionsOfUsers(&I, DB);180 181 // Substitute all uses with zero. In theory we could use `freeze poison`182 // instead, but that seems unlikely to be profitable.183 U.set(ConstantInt::get(U->getType(), 0));184 ++NumSimplified;185 Changed = true;186 }187 }188 189 for (Instruction *&I : llvm::reverse(Worklist)) {190 salvageDebugInfo(*I);191 I->dropAllReferences();192 }193 194 for (Instruction *&I : Worklist) {195 ++NumRemoved;196 I->eraseFromParent();197 }198 199 return Changed;200}201 202PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) {203 auto &DB = AM.getResult<DemandedBitsAnalysis>(F);204 if (!bitTrackingDCE(F, DB))205 return PreservedAnalyses::all();206 207 PreservedAnalyses PA;208 PA.preserveSet<CFGAnalyses>();209 return PA;210}211