1 //===--- RDFDeadCode.cpp --------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
9 // RDF-based generic dead code elimination.
11 #include "RDFDeadCode.h"
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"
26 // This drastically improves execution time in "collect" over using
27 // SetVector as a work queue, and popping the first element from it.
28 template<typename T> struct DeadCodeElimination::SetQueue {
29 SetQueue() : Set(), Queue() {}
53 // Check if the given instruction has observable side-effects, i.e. if
54 // it should be considered "live". It is safe for this function to be
55 // overly conservative (i.e. return "true" for all instructions), but it
56 // is not safe to return "false" for an instruction that should not be
57 // considered removable.
58 bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const {
59 if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn())
61 if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects() ||
66 for (auto &Op : MI->operands()) {
67 if (Op.isReg() && MRI.isReserved(Op.getReg()))
70 const uint32_t *BM = Op.getRegMask();
71 for (unsigned R = 0, RN = DFG.getTRI().getNumRegs(); R != RN; ++R) {
72 if (BM[R/32] & (1u << (R%32)))
74 if (MRI.isReserved(R))
82 void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
83 SetQueue<NodeId> &WorkQ) {
84 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
86 if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
88 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) {
89 if (!LiveNodes.count(RA.Id))
90 WorkQ.push_back(RA.Id);
94 void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,
95 SetQueue<NodeId> &WorkQ) {
96 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
97 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
98 if (!LiveNodes.count(UA.Id))
99 WorkQ.push_back(UA.Id);
101 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
102 LiveNodes.insert(TA.Id);
105 void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,
106 SetQueue<NodeId> &WorkQ) {
107 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) {
108 if (!LiveNodes.count(DA.Id))
109 WorkQ.push_back(DA.Id);
113 // Traverse the DFG and collect the set dead RefNodes and the set of
114 // dead instructions. Return "true" if any of these sets is non-empty,
115 // "false" otherwise.
116 bool DeadCodeElimination::collect() {
117 // This function works by first finding all live nodes. The dead nodes
118 // are then the complement of the set of live nodes.
120 // Assume that all nodes are dead. Identify instructions which must be
121 // considered live, i.e. instructions with observable side-effects, such
122 // as calls and stores. All arguments of such instructions are considered
123 // live. For each live def, all operands used in the corresponding
124 // instruction are considered live. For each live use, all its reaching
125 // defs are considered live.
127 SetQueue<NodeId> WorkQ;
128 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG))
129 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG))
130 scanInstr(IA, WorkQ);
132 while (!WorkQ.empty()) {
133 NodeId N = WorkQ.pop_front();
135 auto RA = DFG.addr<RefNode*>(N);
137 processDef(RA, WorkQ);
139 processUse(RA, WorkQ);
143 dbgs() << "Live nodes:\n";
144 for (NodeId N : LiveNodes) {
145 auto RA = DFG.addr<RefNode*>(N);
146 dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";
150 auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool {
151 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG))
152 if (LiveNodes.count(DA.Id))
157 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
158 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
159 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
160 if (!LiveNodes.count(RA.Id))
161 DeadNodes.insert(RA.Id);
162 if (DFG.IsCode<NodeAttrs::Stmt>(IA))
163 if (isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
166 DeadInstrs.insert(IA.Id);
168 dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
173 return !DeadNodes.empty();
176 // Erase the nodes given in the Nodes set from DFG. In addition to removing
177 // them from the DFG, if a node corresponds to a statement, the corresponding
178 // machine instruction is erased from the function.
179 bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {
183 // Prepare the actual set of ref nodes to remove: ref nodes from Nodes
184 // are included directly, for each InstrNode in Nodes, include the set
185 // of all RefNodes from it.
187 for (auto I : Nodes) {
188 auto BA = DFG.addr<NodeBase*>(I);
189 uint16_t Type = BA.Addr->getType();
190 if (Type == NodeAttrs::Ref) {
191 DRNs.push_back(DFG.addr<RefNode*>(I));
195 // If it's a code node, add all ref nodes from it.
196 uint16_t Kind = BA.Addr->getKind();
197 if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) {
198 for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG))
200 DINs.push_back(DFG.addr<InstrNode*>(I));
202 llvm_unreachable("Unexpected code node");
207 // Sort the list so that use nodes are removed first. This makes the
208 // "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)
213 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)
217 llvm::sort(DRNs, UsesFirst);
220 dbgs() << "Removing dead ref nodes:\n";
221 for (NodeAddr<RefNode*> RA : DRNs) {
223 dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n';
225 DFG.unlinkUse(RA, true);
226 else if (DFG.IsDef(RA))
227 DFG.unlinkDef(RA, true);
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))
237 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
239 dbgs() << "erasing: " << *MI;
240 MI->eraseFromParent();