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 "RDFGraph.h" 13#include "RDFLiveness.h" 14#include "RDFDeadCode.h" 15 16#include "llvm/ADT/SetVector.h" 17#include "llvm/CodeGen/MachineBasicBlock.h" 18#include "llvm/CodeGen/MachineFunction.h" 19#include "llvm/CodeGen/MachineRegisterInfo.h" 20 21using namespace llvm; 22using namespace rdf; 23 24// Check if the given instruction has observable side-effects, i.e. if 25// it should be considered "live". It is safe for this function to be 26// overly conservative (i.e. return "true" for all instructions), but it 27// is not safe to return "false" for an instruction that should not be 28// considered removable. 29bool DeadCodeElimination::isLiveInstr(const MachineInstr *MI) const { 30 if (MI->mayStore() || MI->isBranch() || MI->isCall() || MI->isReturn()) 31 return true; 32 if (MI->hasOrderedMemoryRef() || MI->hasUnmodeledSideEffects()) 33 return true; 34 if (MI->isPHI()) 35 return false; 36 for (auto &Op : MI->operands()) 37 if (Op.isReg() && MRI.isReserved(Op.getReg())) 38 return true; 39 return false; 40} 41 42void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA, 43 SetVector<NodeId> &WorkQ) { 44 if (!DFG.IsCode<NodeAttrs::Stmt>(IA)) 45 return; 46 if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode())) 47 return; 48 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) { 49 if (!LiveNodes.count(RA.Id)) 50 WorkQ.insert(RA.Id); 51 } 52} 53 54void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA, 55 SetVector<NodeId> &WorkQ) { 56 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG); 57 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { 58 if (!LiveNodes.count(UA.Id)) 59 WorkQ.insert(UA.Id); 60 } 61 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA)) 62 LiveNodes.insert(TA.Id); 63} 64 65void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA, 66 SetVector<NodeId> &WorkQ) { 67 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) { 68 if (!LiveNodes.count(DA.Id)) 69 WorkQ.insert(DA.Id); 70 } 71} 72 73// Traverse the DFG and collect the set dead RefNodes and the set of 74// dead instructions. Return "true" if any of these sets is non-empty, 75// "false" otherwise. 76bool DeadCodeElimination::collect() { 77 // This function works by first finding all live nodes. The dead nodes 78 // are then the complement of the set of live nodes. 79 // 80 // Assume that all nodes are dead. Identify instructions which must be 81 // considered live, i.e. instructions with observable side-effects, such 82 // as calls and stores. All arguments of such instructions are considered 83 // live. For each live def, all operands used in the corresponding 84 // instruction are considered live. For each live use, all its reaching 85 // defs are considered live. 86 LiveNodes.clear(); 87 SetVector<NodeId> WorkQ; 88 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) 89 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) 90 scanInstr(IA, WorkQ); 91 92 while (!WorkQ.empty()) { 93 NodeId N = *WorkQ.begin(); 94 WorkQ.remove(N); 95 LiveNodes.insert(N); 96 auto RA = DFG.addr<RefNode*>(N); 97 if (DFG.IsDef(RA)) 98 processDef(RA, WorkQ); 99 else 100 processUse(RA, WorkQ); 101 } 102 103 if (trace()) { 104 dbgs() << "Live nodes:\n"; 105 for (NodeId N : LiveNodes) { 106 auto RA = DFG.addr<RefNode*>(N); 107 dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n"; 108 } 109 } 110 111 auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool { 112 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) 113 if (LiveNodes.count(DA.Id)) 114 return false; 115 return true; 116 }; 117 118 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { 119 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { 120 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) 121 if (!LiveNodes.count(RA.Id)) 122 DeadNodes.insert(RA.Id); 123 if (DFG.IsCode<NodeAttrs::Stmt>(IA)) 124 if (isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode())) 125 continue; 126 if (IsDead(IA)) { 127 DeadInstrs.insert(IA.Id); 128 if (trace()) 129 dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n"; 130 } 131 } 132 } 133 134 return !DeadNodes.empty(); 135} 136 137// Erase the nodes given in the Nodes set from DFG. In addition to removing 138// them from the DFG, if a node corresponds to a statement, the corresponding 139// machine instruction is erased from the function. 140bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) { 141 if (Nodes.empty()) 142 return false; 143 144 // Prepare the actual set of ref nodes to remove: ref nodes from Nodes 145 // are included directly, for each InstrNode in Nodes, include the set 146 // of all RefNodes from it. 147 NodeList DRNs, DINs; 148 for (auto I : Nodes) { 149 auto BA = DFG.addr<NodeBase*>(I); 150 uint16_t Type = BA.Addr->getType(); 151 if (Type == NodeAttrs::Ref) { 152 DRNs.push_back(DFG.addr<RefNode*>(I)); 153 continue; 154 } 155 156 // If it's a code node, add all ref nodes from it. 157 uint16_t Kind = BA.Addr->getKind(); 158 if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) { 159 for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG)) 160 DRNs.push_back(N); 161 DINs.push_back(DFG.addr<InstrNode*>(I)); 162 } else { 163 llvm_unreachable("Unexpected code node"); 164 return false; 165 } 166 } 167 168 // Sort the list so that use nodes are removed first. This makes the 169 // "unlink" functions a bit faster. 170 auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool { 171 uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind(); 172 if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def) 173 return true; 174 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use) 175 return false; 176 return A.Id < B.Id; 177 }; 178 std::sort(DRNs.begin(), DRNs.end(), UsesFirst); 179 180 if (trace()) 181 dbgs() << "Removing dead ref nodes:\n"; 182 for (NodeAddr<RefNode*> RA : DRNs) { 183 if (trace()) 184 dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n'; 185 if (DFG.IsUse(RA)) 186 DFG.unlinkUse(RA); 187 else if (DFG.IsDef(RA)) 188 DFG.unlinkDef(RA); 189 } 190 191 // Now, remove all dead instruction nodes. 192 for (NodeAddr<InstrNode*> IA : DINs) { 193 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); 194 BA.Addr->removeMember(IA, DFG); 195 if (!DFG.IsCode<NodeAttrs::Stmt>(IA)) 196 continue; 197 198 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode(); 199 if (trace()) 200 dbgs() << "erasing: " << *MI; 201 MI->eraseFromParent(); 202 } 203 return true; 204} 205