LLVM  13.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"
17 #include "llvm/CodeGen/RDFGraph.h"
19 #include "llvm/Support/Debug.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  append_range(DRNs, NodeAddr<CodeNode*>(BA).Addr->members(DFG));
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 }
DeadCodeElimination::SetQueue::SetQueue
SetQueue()
Definition: RDFDeadCode.cpp:29
IsDead
bool IsDead
Definition: SILowerControlFlow.cpp:158
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:102
llvm
Definition: AllocatorList.h:23
llvm::rdf::DataFlowGraph::getRelatedRefs
NodeList getRelatedRefs(NodeAddr< InstrNode * > IA, NodeAddr< RefNode * > RA) const
Definition: RDFGraph.cpp:1125
llvm::rdf::CodeNode::members_if
NodeList members_if(Predicate P, const DataFlowGraph &G) const
Definition: RDFGraph.h:909
llvm::rdf::InstrNode
Definition: RDFGraph.h:610
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::X86II::TA
@ TA
Definition: X86BaseInfo.h:803
MachineBasicBlock.h
llvm::rdf::DataFlowGraph::unlinkUse
void unlinkUse(NodeAddr< UseNode * > UA, bool RemoveFromOwner)
Definition: RDFGraph.h:768
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::rdf::PrintNode
Definition: RDFGraph.h:932
RDFDeadCode.h
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
RDFLiveness.h
llvm::rdf::DataFlowGraph::getFunc
NodeAddr< FuncNode * > getFunc() const
Definition: RDFGraph.h:660
llvm::rdf::NodeAddr
Definition: RDFGraph.h:334
llvm::MachineRegisterInfo::isReserved
bool isReserved(MCRegister PhysReg) const
isReserved - Returns true when PhysReg is a reserved register.
Definition: MachineRegisterInfo.h:915
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::rdf::NodeAttrs::Use
@ Use
Definition: RDFGraph.h:276
llvm::rdf::DataFlowGraph::IsDef
static bool IsDef(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:793
llvm::rdf::NodeAddr::Addr
T Addr
Definition: RDFGraph.h:351
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::DenseSet< T >
llvm::rdf::DataFlowGraph::IsCode
static bool IsCode(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:788
llvm::rdf::DataFlowGraph::addr
NodeAddr< T > addr(NodeId N) const
Definition: RDFGraph.h:656
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::rdf::DataFlowGraph::getTRI
const TargetRegisterInfo & getTRI() const
Definition: RDFGraph.h:663
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:80
llvm::rdf::CodeNode::members
NodeList members(const DataFlowGraph &G) const
Definition: RDFGraph.cpp:527
llvm::rdf::NodeAttrs::Stmt
@ Stmt
Definition: RDFGraph.h:278
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::rdf::DeadCodeElimination::collect
bool collect()
Definition: RDFDeadCode.cpp:116
llvm::M68kBeads::DA
@ DA
Definition: M68kBaseInfo.h:59
RA
SI optimize exec mask operations pre RA
Definition: SIOptimizeExecMaskingPreRA.cpp:71
RDFGraph.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
uint32_t
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1672
llvm::rdf::DataFlowGraph::IsUse
static bool IsUse(const NodeAddr< NodeBase * > BA)
Definition: RDFGraph.h:798
llvm::rdf::DeadCodeElimination::trace
bool trace() const
Definition: RDFDeadCode.h:41
DeadCodeElimination::SetQueue::pop_front
T pop_front()
Definition: RDFDeadCode.cpp:34
DeadCodeElimination::SetQueue
Definition: RDFDeadCode.cpp:28
llvm::rdf::CodeNode::removeMember
void removeMember(NodeAddr< NodeBase * > NA, const DataFlowGraph &G)
Definition: RDFGraph.cpp:495
DeadCodeElimination::SetQueue::push_back
void push_back(T V)
Definition: RDFDeadCode.cpp:40
uint16_t
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:314
llvm::rdf::NodeAttrs::Ref
@ Ref
Definition: RDFGraph.h:271
llvm::rdf::NodeBase
Definition: RDFGraph.h:449
DeadCodeElimination::SetQueue::empty
bool empty() const
Definition: RDFDeadCode.cpp:31
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1423
llvm::rdf::DeadCodeElimination::erase
bool erase(const SetVector< NodeId > &Nodes)
Definition: RDFDeadCode.cpp:179
llvm::rdf::NodeAddr::Id
NodeId Id
Definition: RDFGraph.h:352
llvm::rdf::DataFlowGraph::unlinkDef
void unlinkDef(NodeAddr< DefNode * > DA, bool RemoveFromOwner)
Definition: RDFGraph.h:774
N
#define N
llvm::rdf::NodeAttrs::Def
@ Def
Definition: RDFGraph.h:275
llvm::rdf::RefNode
Definition: RDFGraph.h:515
llvm::rdf::NodeAttrs::Phi
@ Phi
Definition: RDFGraph.h:277
RN
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Definition: README_P9.txt:262
llvm::rdf::Liveness::getAllReachingDefs
NodeList getAllReachingDefs(RegisterRef RefRR, NodeAddr< RefNode * > RefA, bool TopShadows, bool FullChain, const RegisterAggr &DefRRs)
Definition: RDFLiveness.cpp:109
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
MachineFunction.h
Debug.h
SetVector.h
llvm::rdf::InstrNode::getOwner
NodeAddr< NodeBase * > getOwner(const DataFlowGraph &G)
Definition: RDFGraph.cpp:533