LLVM  9.0.0svn
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 #include "RDFGraph.h"
13 #include "RDFLiveness.h"
14 
15 #include "llvm/ADT/SetVector.h"
19 
20 #include <queue>
21 
22 using namespace llvm;
23 using namespace rdf;
24 
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() {}
29 
30  bool empty() const {
31  return Queue.empty();
32  }
34  T V = Queue.front();
35  Queue.pop();
36  Set.erase(V);
37  return V;
38  }
39  void push_back(T V) {
40  if (Set.count(V))
41  return;
42  Queue.push(V);
43  Set.insert(V);
44  }
45 
46 private:
47  DenseSet<T> Set;
48  std::queue<T> Queue;
49 };
50 
51 
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())
59  return true;
60  if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects() ||
61  MI->isPosition())
62  return true;
63  if (MI->isPHI())
64  return false;
65  for (auto &Op : MI->operands()) {
66  if (Op.isReg() && MRI.isReserved(Op.getReg()))
67  return true;
68  if (Op.isRegMask()) {
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)))
72  continue;
73  if (MRI.isReserved(R))
74  return true;
75  }
76  }
77  }
78  return false;
79 }
80 
81 void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
82  SetQueue<NodeId> &WorkQ) {
83  if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
84  return;
85  if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
86  return;
87  for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) {
88  if (!LiveNodes.count(RA.Id))
89  WorkQ.push_back(RA.Id);
90  }
91 }
92 
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);
99  }
100  for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
101  LiveNodes.insert(TA.Id);
102 }
103 
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);
109  }
110 }
111 
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.
116  // This function works by first finding all live nodes. The dead nodes
117  // are then the complement of the set of live nodes.
118  //
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.
125  LiveNodes.clear();
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);
130 
131  while (!WorkQ.empty()) {
132  NodeId N = WorkQ.pop_front();
133  LiveNodes.insert(N);
134  auto RA = DFG.addr<RefNode*>(N);
135  if (DFG.IsDef(RA))
136  processDef(RA, WorkQ);
137  else
138  processUse(RA, WorkQ);
139  }
140 
141  if (trace()) {
142  dbgs() << "Live nodes:\n";
143  for (NodeId N : LiveNodes) {
144  auto RA = DFG.addr<RefNode*>(N);
145  dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";
146  }
147  }
148 
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))
152  return false;
153  return true;
154  };
155 
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()))
163  continue;
164  if (IsDead(IA)) {
165  DeadInstrs.insert(IA.Id);
166  if (trace())
167  dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
168  }
169  }
170  }
171 
172  return !DeadNodes.empty();
173 }
174 
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.
179  if (Nodes.empty())
180  return false;
181 
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.
185  NodeList DRNs, DINs;
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));
191  continue;
192  }
193 
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))
198  DRNs.push_back(N);
199  DINs.push_back(DFG.addr<InstrNode*>(I));
200  } else {
201  llvm_unreachable("Unexpected code node");
202  return false;
203  }
204  }
205 
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)
211  return true;
212  if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use)
213  return false;
214  return A.Id < B.Id;
215  };
216  llvm::sort(DRNs, UsesFirst);
217 
218  if (trace())
219  dbgs() << "Removing dead ref nodes:\n";
220  for (NodeAddr<RefNode*> RA : DRNs) {
221  if (trace())
222  dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n';
223  if (DFG.IsUse(RA))
224  DFG.unlinkUse(RA, true);
225  else if (DFG.IsDef(RA))
226  DFG.unlinkDef(RA, true);
227  }
228 
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))
234  continue;
235 
236  MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
237  if (trace())
238  dbgs() << "erasing: " << *MI;
239  MI->eraseFromParent();
240  }
241  return true;
242 }
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:635
bool IsDead
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void push_back(const T &Elt)
Definition: SmallVector.h:211
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:461
bool isPHI() const
SI optimize exec mask operations pre RA
void eraseFromParent()
Unlink &#39;this&#39; from the containing basic block and delete it.
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:533
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:659
bool isReturn(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:625
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:822
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
unsigned const MachineRegisterInfo * MRI
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
uint16_t getKind() const
Definition: RDFGraph.h:455
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:913
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:527
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1122
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
bool hasOrderedMemoryRef() const
Return true if this instruction may have an ordered or volatile memory reference, or if the informati...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void removeMember(NodeAddr< NodeBase *> NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:495
Representation of each machine instruction.
Definition: MachineInstr.h:64
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:434
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
bool erase(const SetVector< NodeId > &Nodes)
A vector that has set insertion semantics.
Definition: SetVector.h:40
bool isPosition() const
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI