LLVM  6.0.0svn
RDFDeadCode.cpp
Go to the documentation of this file.
1 //===--- RDFDeadCode.cpp --------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // RDF-based generic dead code elimination.
11 
12 #include "RDFDeadCode.h"
13 #include "RDFGraph.h"
14 #include "RDFLiveness.h"
15 
16 #include "llvm/ADT/SetVector.h"
20 
21 #include <queue>
22 
23 using namespace llvm;
24 using 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.
28 template<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 
47 private:
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.
58 bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const {
59  if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn())
60  return true;
61  if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects() ||
62  MI->isPosition())
63  return true;
64  if (MI->isPHI())
65  return false;
66  for (auto &Op : MI->operands()) {
67  if (Op.isReg() && MRI.isReserved(Op.getReg()))
68  return true;
69  if (Op.isRegMask()) {
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)))
73  continue;
74  if (MRI.isReserved(R))
75  return true;
76  }
77  }
78  }
79  return false;
80 }
81 
82 void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA,
83  SetQueue<NodeId> &WorkQ) {
84  if (!DFG.IsCode<NodeAttrs::Stmt>(IA))
85  return;
86  if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode()))
87  return;
88  for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) {
89  if (!LiveNodes.count(RA.Id))
90  WorkQ.push_back(RA.Id);
91  }
92 }
93 
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);
100  }
101  for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA))
102  LiveNodes.insert(TA.Id);
103 }
104 
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);
110  }
111 }
112 
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.
117  // This function works by first finding all live nodes. The dead nodes
118  // are then the complement of the set of live nodes.
119  //
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.
126  LiveNodes.clear();
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);
131 
132  while (!WorkQ.empty()) {
133  NodeId N = WorkQ.pop_front();
134  LiveNodes.insert(N);
135  auto RA = DFG.addr<RefNode*>(N);
136  if (DFG.IsDef(RA))
137  processDef(RA, WorkQ);
138  else
139  processUse(RA, WorkQ);
140  }
141 
142  if (trace()) {
143  dbgs() << "Live nodes:\n";
144  for (NodeId N : LiveNodes) {
145  auto RA = DFG.addr<RefNode*>(N);
146  dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n";
147  }
148  }
149 
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))
153  return false;
154  return true;
155  };
156 
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()))
164  continue;
165  if (IsDead(IA)) {
166  DeadInstrs.insert(IA.Id);
167  if (trace())
168  dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n";
169  }
170  }
171  }
172 
173  return !DeadNodes.empty();
174 }
175 
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.
180  if (Nodes.empty())
181  return false;
182 
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.
186  NodeList DRNs, DINs;
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));
192  continue;
193  }
194 
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))
199  DRNs.push_back(N);
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  std::sort(DRNs.begin(), DRNs.end(), 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 }
void push_back(const T &Elt)
Definition: SmallVector.h:212
bool isCall(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:458
bool IsDead
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:332
bool isPHI() const
Definition: MachineInstr.h:826
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:552
bool isBranch(QueryType Type=AnyInBundle) const
Returns true if this is a conditional, unconditional, or indirect branch.
Definition: MachineInstr.h:482
bool isReturn(QueryType Type=AnyInBundle) const
Definition: MachineInstr.h:454
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:639
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:46
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
uint16_t getKind() const
Definition: RDFGraph.h:456
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:914
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:546
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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:514
Representation of each machine instruction.
Definition: MachineInstr.h:59
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:453
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:120
#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:73
bool erase(const SetVector< NodeId > &Nodes)
const unsigned Kind
A vector that has set insertion semantics.
Definition: SetVector.h:41
bool isPosition() const
Definition: MachineInstr.h:814
bool hasUnmodeledSideEffects() const
Return true if this instruction has side effects that are not modeled by mayLoad / mayStore...
IRTranslator LLVM IR MI
void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End, const Comparator &Comp=Comparator())
Definition: Parallel.h:199