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 "RDFLiveness.h"
15 #include "llvm/ADT/SetVector.h"
16 #include "llvm/CodeGen/MachineBasicBlock.h"
17 #include "llvm/CodeGen/MachineFunction.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
25 // This drastically improves execution time in "collect" over using
26 // SetVector as a work queue, and popping the first element from it.
27 template<typename T> struct DeadCodeElimination::SetQueue {
28 SetQueue() : Set(), Queue() {}
52 // Check if the given instruction has observable side-effects, i.e. if
53 // it should be considered "live". It is safe for this function to be
54 // overly conservative (i.e. return "true" for all instructions), but it
55 // is not safe to return "false" for an instruction that should not be
56 // considered removable.
57 bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const {
58 if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn())
60 if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects() ||
65 for (auto &Op : MI->operands()) {
66 if (Op.isReg() && MRI.isReserved(Op.getReg()))
69 const uint32_t *BM = Op.getRegMask();
70 for (unsigned R = 0, RN = DFG.getTRI().getNumRegs(); R != RN; ++R) {
71 if (BM[R/32] & (1u << (R%32)))
73 if (MRI.isReserved(R))
81 void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
82 SetQueue<NodeId> &WorkQ) {
83 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
85 if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
87 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) {
88 if (!LiveNodes.count(RA.Id))
89 WorkQ.push_back(RA.Id);
93 void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA,
94 SetQueue<NodeId> &WorkQ) {
95 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG);
96 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) {
97 if (!LiveNodes.count(UA.Id))
98 WorkQ.push_back(UA.Id);
100 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
101 LiveNodes.insert(TA.Id);
104 void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA,
105 SetQueue<NodeId> &WorkQ) {
106 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) {
107 if (!LiveNodes.count(DA.Id))
108 WorkQ.push_back(DA.Id);
112 // Traverse the DFG and collect the set dead RefNodes and the set of
113 // dead instructions. Return "true" if any of these sets is non-empty,
114 // "false" otherwise.
115 bool DeadCodeElimination::collect() {
116 // This function works by first finding all live nodes. The dead nodes
117 // are then the complement of the set of live nodes.
119 // Assume that all nodes are dead. Identify instructions which must be
120 // considered live, i.e. instructions with observable side-effects, such
121 // as calls and stores. All arguments of such instructions are considered
122 // live. For each live def, all operands used in the corresponding
123 // instruction are considered live. For each live use, all its reaching
124 // defs are considered live.
126 SetQueue<NodeId> WorkQ;
127 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG))
128 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG))
129 scanInstr(IA, WorkQ);
131 while (!WorkQ.empty()) {
132 NodeId N = WorkQ.pop_front();
134 auto RA = DFG.addr<RefNode*>(N);
136 processDef(RA, WorkQ);
138 processUse(RA, WorkQ);
142 dbgs() << "Live nodes:\n";
143 for (NodeId N : LiveNodes) {
144 auto RA = DFG.addr<RefNode*>(N);
145 dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";
149 auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool {
150 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG))
151 if (LiveNodes.count(DA.Id))
156 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
157 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
158 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
159 if (!LiveNodes.count(RA.Id))
160 DeadNodes.insert(RA.Id);
161 if (DFG.IsCode<NodeAttrs::Stmt>(IA))
162 if (isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
165 DeadInstrs.insert(IA.Id);
167 dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
172 return !DeadNodes.empty();
175 // Erase the nodes given in the Nodes set from DFG. In addition to removing
176 // them from the DFG, if a node corresponds to a statement, the corresponding
177 // machine instruction is erased from the function.
178 bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) {
182 // Prepare the actual set of ref nodes to remove: ref nodes from Nodes
183 // are included directly, for each InstrNode in Nodes, include the set
184 // of all RefNodes from it.
186 for (auto I : Nodes) {
187 auto BA = DFG.addr<NodeBase*>(I);
188 uint16_t Type = BA.Addr->getType();
189 if (Type == NodeAttrs::Ref) {
190 DRNs.push_back(DFG.addr<RefNode*>(I));
194 // If it's a code node, add all ref nodes from it.
195 uint16_t Kind = BA.Addr->getKind();
196 if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) {
197 for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG))
199 DINs.push_back(DFG.addr<InstrNode*>(I));
201 llvm_unreachable("Unexpected code node");
206 // Sort the list so that use nodes are removed first. This makes the
207 // "unlink" functions a bit faster.
208 auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool {
209 uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind();
210 if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def)
212 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)
216 llvm::sort(DRNs, UsesFirst);
219 dbgs() << "Removing dead ref nodes:\n";
220 for (NodeAddr<RefNode*> RA : DRNs) {
222 dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n';
224 DFG.unlinkUse(RA, true);
225 else if (DFG.IsDef(RA))
226 DFG.unlinkDef(RA, true);
229 // Now, remove all dead instruction nodes.
230 for (NodeAddr<InstrNode*> IA : DINs) {
231 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG);
232 BA.Addr->removeMember(IA, DFG);
233 if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
236 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
238 dbgs() << "erasing: " << *MI;
239 MI->eraseFromParent();