LLVM 19.0.0git
RDFDeadCode.cpp
Go to the documentation of this file.
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"
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 }
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(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 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(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 else
140 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 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*>(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 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(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}
unsigned const MachineRegisterInfo * MRI
static bool processUse(CallInst *CI, bool IsV5OrAbove)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
uint64_t Addr
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
bool IsDead
SI optimize exec mask operations pre RA
This file implements a set that has insertion order iteration characteristics.
This class represents an Operation in the Expression.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Representation of each machine instruction.
Definition: MachineInstr.h:69
A vector that has set insertion semantics.
Definition: SetVector.h:57
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
bool erase(const ValueT &V)
Definition: DenseSet.h:101
size_type count(const_arg_type_t< ValueT > V) const
Return 1 if the specified key is in the set, 0 otherwise.
Definition: DenseSet.h:97
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2053
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1656
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
#define N