244 lines · cpp
1//===--- RDFDeadCode.cpp --------------------------------------------------===//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// RDF-based generic dead code elimination.10 11#include "RDFDeadCode.h"12 13#include "llvm/ADT/SetVector.h"14#include "llvm/CodeGen/MachineBasicBlock.h"15#include "llvm/CodeGen/MachineFunction.h"16#include "llvm/CodeGen/MachineRegisterInfo.h"17#include "llvm/CodeGen/RDFGraph.h"18#include "llvm/CodeGen/RDFLiveness.h"19#include "llvm/Support/Debug.h"20 21#include <queue>22 23using namespace llvm;24using namespace rdf;25 26// This drastically improves execution time in "collect" over using27// SetVector as a work queue, and popping the first element from it.28template<typename T> struct DeadCodeElimination::SetQueue {29 SetQueue() : Set(), Queue() {}30 31 bool empty() const {32 return Queue.empty();33 }34 T pop_front() {35 T V = Queue.front();36 Queue.pop();37 Set.erase(V);38 return V;39 }40 void push_back(T V) {41 if (Set.count(V))42 return;43 Queue.push(V);44 Set.insert(V);45 }46 47private:48 DenseSet<T> Set;49 std::queue<T> Queue;50};51 52 53// Check if the given instruction has observable side-effects, i.e. if54// it should be considered "live". It is safe for this function to be55// overly conservative (i.e. return "true" for all instructions), but it56// is not safe to return "false" for an instruction that should not be57// considered removable.58bool DeadCodeElimination::isLiveInstr(NodeAddr<StmtNode *> S) const {59 const MachineInstr *MI = S.Addr->getCode();60 if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn())61 return true;62 if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects() ||63 MI->isPosition())64 return true;65 if (MI->isPHI())66 return false;67 for (auto &Op : MI->operands()) {68 if (Op.isReg() && MRI.isReserved(Op.getReg()))69 return true;70 if (Op.isRegMask()) {71 const uint32_t *BM = Op.getRegMask();72 for (unsigned R = 0, RN = DFG.getTRI().getNumRegs(); R != RN; ++R) {73 if (BM[R/32] & (1u << (R%32)))74 continue;75 if (MRI.isReserved(R))76 return true;77 }78 }79 }80 return false;81}82 83void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,84 SetQueue<NodeId> &WorkQ) {85 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))86 return;87 if (!isLiveInstr(IA))88 return;89 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) {90 if (!LiveNodes.count(RA.Id))91 WorkQ.push_back(RA.Id);92 }93}94 95void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,96 SetQueue<NodeId> &WorkQ) {97 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);98 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {99 if (!LiveNodes.count(UA.Id))100 WorkQ.push_back(UA.Id);101 }102 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))103 LiveNodes.insert(TA.Id);104}105 106void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,107 SetQueue<NodeId> &WorkQ) {108 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) {109 if (!LiveNodes.count(DA.Id))110 WorkQ.push_back(DA.Id);111 }112}113 114// Traverse the DFG and collect the set dead RefNodes and the set of115// dead instructions. Return "true" if any of these sets is non-empty,116// "false" otherwise.117bool DeadCodeElimination::collect() {118 // This function works by first finding all live nodes. The dead nodes119 // are then the complement of the set of live nodes.120 //121 // Assume that all nodes are dead. Identify instructions which must be122 // considered live, i.e. instructions with observable side-effects, such123 // as calls and stores. All arguments of such instructions are considered124 // live. For each live def, all operands used in the corresponding125 // instruction are considered live. For each live use, all its reaching126 // defs are considered live.127 LiveNodes.clear();128 SetQueue<NodeId> WorkQ;129 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG))130 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG))131 scanInstr(IA, WorkQ);132 133 while (!WorkQ.empty()) {134 NodeId N = WorkQ.pop_front();135 LiveNodes.insert(N);136 auto RA = DFG.addr<RefNode*>(N);137 if (DFG.IsDef(RA))138 processDef(RA, WorkQ);139 else140 processUse(RA, WorkQ);141 }142 143 if (trace()) {144 dbgs() << "Live nodes:\n";145 for (NodeId N : LiveNodes) {146 auto RA = DFG.addr<RefNode*>(N);147 dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";148 }149 }150 151 auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool {152 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG))153 if (LiveNodes.count(DA.Id))154 return false;155 return true;156 };157 158 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {159 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {160 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))161 if (!LiveNodes.count(RA.Id))162 DeadNodes.insert(RA.Id);163 if (DFG.IsCode<NodeAttrs::Stmt>(IA))164 if (isLiveInstr(IA) || DFG.hasUntrackedRef(IA))165 continue;166 if (IsDead(IA)) {167 DeadInstrs.insert(IA.Id);168 if (trace())169 dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";170 }171 }172 }173 174 return !DeadNodes.empty();175}176 177// Erase the nodes given in the Nodes set from DFG. In addition to removing178// them from the DFG, if a node corresponds to a statement, the corresponding179// machine instruction is erased from the function.180bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {181 if (Nodes.empty())182 return false;183 184 // Prepare the actual set of ref nodes to remove: ref nodes from Nodes185 // are included directly, for each InstrNode in Nodes, include the set186 // of all RefNodes from it.187 NodeList DRNs, DINs;188 for (auto I : Nodes) {189 auto BA = DFG.addr<NodeBase*>(I);190 uint16_t Type = BA.Addr->getType();191 if (Type == NodeAttrs::Ref) {192 DRNs.push_back(DFG.addr<RefNode*>(I));193 continue;194 }195 196 // If it's a code node, add all ref nodes from it.197 uint16_t Kind = BA.Addr->getKind();198 if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) {199 append_range(DRNs, NodeAddr<CodeNode*>(BA).Addr->members(DFG));200 DINs.push_back(DFG.addr<InstrNode*>(I));201 } else {202 llvm_unreachable("Unexpected code node");203 return false;204 }205 }206 207 // Sort the list so that use nodes are removed first. This makes the208 // "unlink" functions a bit faster.209 auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool {210 uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind();211 if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def)212 return true;213 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)214 return false;215 return A.Id < B.Id;216 };217 llvm::sort(DRNs, UsesFirst);218 219 if (trace())220 dbgs() << "Removing dead ref nodes:\n";221 for (NodeAddr<RefNode*> RA : DRNs) {222 if (trace())223 dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n';224 if (DFG.IsUse(RA))225 DFG.unlinkUse(RA, true);226 else if (DFG.IsDef(RA))227 DFG.unlinkDef(RA, true);228 }229 230 // Now, remove all dead instruction nodes.231 for (NodeAddr<InstrNode*> IA : DINs) {232 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);233 BA.Addr->removeMember(IA, DFG);234 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))235 continue;236 237 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();238 if (trace())239 dbgs() << "erasing: " << *MI;240 MI->eraseFromParent();241 }242 return true;243}244