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-exception
6//
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 using
27// 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. 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.
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(PhysReg: 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(PhysReg: 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>(BA: IA))
86 return;
87 if (!isLiveInstr(S: IA))
88 return;
89 for (NodeAddr<RefNode*> RA : IA.Addr->members(G: DFG)) {
90 if (!LiveNodes.count(key: RA.Id))
91 WorkQ.push_back(V: RA.Id);
92 }
93}
94
95void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,
96 SetQueue<NodeId> &WorkQ) {
97 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(G: DFG);
98 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(P: DFG.IsUse, G: DFG)) {
99 if (!LiveNodes.count(key: UA.Id))
100 WorkQ.push_back(V: UA.Id);
101 }
102 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, RA: DA))
103 LiveNodes.insert(X: TA.Id);
104}
105
106void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,
107 SetQueue<NodeId> &WorkQ) {
108 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(RefA: UA)) {
109 if (!LiveNodes.count(key: DA.Id))
110 WorkQ.push_back(V: DA.Id);
111 }
112}
113
114// Traverse the DFG and collect the set dead RefNodes and the set of
115// 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 nodes
119 // are then the complement of the set of live nodes.
120 //
121 // Assume that all nodes are dead. Identify instructions which must be
122 // considered live, i.e. instructions with observable side-effects, such
123 // as calls and stores. All arguments of such instructions are considered
124 // live. For each live def, all operands used in the corresponding
125 // instruction are considered live. For each live use, all its reaching
126 // defs are considered live.
127 LiveNodes.clear();
128 SetQueue<NodeId> WorkQ;
129 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(G: DFG))
130 for (NodeAddr<InstrNode*> IA : BA.Addr->members(G: DFG))
131 scanInstr(IA, WorkQ);
132
133 while (!WorkQ.empty()) {
134 NodeId N = WorkQ.pop_front();
135 LiveNodes.insert(X: N);
136 auto RA = DFG.addr<RefNode*>(N);
137 if (DFG.IsDef(BA: RA))
138 processDef(DA: RA, WorkQ);
139 else
140 processUse(UA: 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(P: DFG.IsDef, G: DFG))
153 if (LiveNodes.count(key: DA.Id))
154 return false;
155 return true;
156 };
157
158 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(G: DFG)) {
159 for (NodeAddr<InstrNode*> IA : BA.Addr->members(G: DFG)) {
160 for (NodeAddr<RefNode*> RA : IA.Addr->members(G: DFG))
161 if (!LiveNodes.count(key: RA.Id))
162 DeadNodes.insert(X: RA.Id);
163 if (DFG.IsCode<NodeAttrs::Stmt>(BA: IA))
164 if (isLiveInstr(S: IA) || DFG.hasUntrackedRef(S: IA))
165 continue;
166 if (IsDead(IA)) {
167 DeadInstrs.insert(X: 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 removing
178// them from the DFG, if a node corresponds to a statement, the corresponding
179// 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 Nodes
185 // are included directly, for each InstrNode in Nodes, include the set
186 // of all RefNodes from it.
187 NodeList DRNs, DINs;
188 for (auto I : Nodes) {
189 auto BA = DFG.addr<NodeBase*>(N: I);
190 uint16_t Type = BA.Addr->getType();
191 if (Type == NodeAttrs::Ref) {
192 DRNs.push_back(Elt: DFG.addr<RefNode*>(N: 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(C&: DRNs, R: NodeAddr<CodeNode*>(BA).Addr->members(G: DFG));
200 DINs.push_back(Elt: DFG.addr<InstrNode*>(N: 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 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)
212 return true;
213 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)
214 return false;
215 return A.Id < B.Id;
216 };
217 llvm::sort(C&: DRNs, Comp: 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(BA: RA))
225 DFG.unlinkUse(UA: RA, RemoveFromOwner: true);
226 else if (DFG.IsDef(BA: RA))
227 DFG.unlinkDef(DA: RA, RemoveFromOwner: true);
228 }
229
230 // Now, remove all dead instruction nodes.
231 for (NodeAddr<InstrNode*> IA : DINs) {
232 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(G: DFG);
233 BA.Addr->removeMember(NA: IA, G: DFG);
234 if (!DFG.IsCode<NodeAttrs::Stmt>(BA: 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