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 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 } 34 T pop_front() { 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 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 return false; 69 } 70 71 void DeadCodeElimination::scanInstr(NodeAddr<InstrNode*> IA, 72 SetQueue<NodeId> &WorkQ) { 73 if (!DFG.IsCode<NodeAttrs::Stmt>(IA)) 74 return; 75 if (!isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode())) 76 return; 77 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) { 78 if (!LiveNodes.count(RA.Id)) 79 WorkQ.push_back(RA.Id); 80 } 81 } 82 83 void DeadCodeElimination::processDef(NodeAddr<DefNode*> DA, 84 SetQueue<NodeId> &WorkQ) { 85 NodeAddr<InstrNode*> IA = DA.Addr->getOwner(DFG); 86 for (NodeAddr<UseNode*> UA : IA.Addr->members_if(DFG.IsUse, DFG)) { 87 if (!LiveNodes.count(UA.Id)) 88 WorkQ.push_back(UA.Id); 89 } 90 for (NodeAddr<DefNode*> TA : DFG.getRelatedRefs(IA, DA)) 91 LiveNodes.insert(TA.Id); 92 } 93 94 void DeadCodeElimination::processUse(NodeAddr<UseNode*> UA, 95 SetQueue<NodeId> &WorkQ) { 96 for (NodeAddr<DefNode*> DA : LV.getAllReachingDefs(UA)) { 97 if (!LiveNodes.count(DA.Id)) 98 WorkQ.push_back(DA.Id); 99 } 100 } 101 102 // Traverse the DFG and collect the set dead RefNodes and the set of 103 // dead instructions. Return "true" if any of these sets is non-empty, 104 // "false" otherwise. 105 bool DeadCodeElimination::collect() { 106 // This function works by first finding all live nodes. The dead nodes 107 // are then the complement of the set of live nodes. 108 // 109 // Assume that all nodes are dead. Identify instructions which must be 110 // considered live, i.e. instructions with observable side-effects, such 111 // as calls and stores. All arguments of such instructions are considered 112 // live. For each live def, all operands used in the corresponding 113 // instruction are considered live. For each live use, all its reaching 114 // defs are considered live. 115 LiveNodes.clear(); 116 SetQueue<NodeId> WorkQ; 117 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) 118 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) 119 scanInstr(IA, WorkQ); 120 121 while (!WorkQ.empty()) { 122 NodeId N = WorkQ.pop_front(); 123 LiveNodes.insert(N); 124 auto RA = DFG.addr<RefNode*>(N); 125 if (DFG.IsDef(RA)) 126 processDef(RA, WorkQ); 127 else 128 processUse(RA, WorkQ); 129 } 130 131 if (trace()) { 132 dbgs() << "Live nodes:\n"; 133 for (NodeId N : LiveNodes) { 134 auto RA = DFG.addr<RefNode*>(N); 135 dbgs() << PrintNode<RefNode*>(RA, DFG) << "\n"; 136 } 137 } 138 139 auto IsDead = [this] (NodeAddr<InstrNode*> IA) -> bool { 140 for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) 141 if (LiveNodes.count(DA.Id)) 142 return false; 143 return true; 144 }; 145 146 for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) { 147 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { 148 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) 149 if (!LiveNodes.count(RA.Id)) 150 DeadNodes.insert(RA.Id); 151 if (DFG.IsCode<NodeAttrs::Stmt>(IA)) 152 if (isLiveInstr(NodeAddr<StmtNode*>(IA).Addr->getCode())) 153 continue; 154 if (IsDead(IA)) { 155 DeadInstrs.insert(IA.Id); 156 if (trace()) 157 dbgs() << "Dead instr: " << PrintNode<InstrNode*>(IA, DFG) << "\n"; 158 } 159 } 160 } 161 162 return !DeadNodes.empty(); 163 } 164 165 // Erase the nodes given in the Nodes set from DFG. In addition to removing 166 // them from the DFG, if a node corresponds to a statement, the corresponding 167 // machine instruction is erased from the function. 168 bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) { 169 if (Nodes.empty()) 170 return false; 171 172 // Prepare the actual set of ref nodes to remove: ref nodes from Nodes 173 // are included directly, for each InstrNode in Nodes, include the set 174 // of all RefNodes from it. 175 NodeList DRNs, DINs; 176 for (auto I : Nodes) { 177 auto BA = DFG.addr<NodeBase*>(I); 178 uint16_t Type = BA.Addr->getType(); 179 if (Type == NodeAttrs::Ref) { 180 DRNs.push_back(DFG.addr<RefNode*>(I)); 181 continue; 182 } 183 184 // If it's a code node, add all ref nodes from it. 185 uint16_t Kind = BA.Addr->getKind(); 186 if (Kind == NodeAttrs::Stmt || Kind == NodeAttrs::Phi) { 187 for (auto N : NodeAddr<CodeNode*>(BA).Addr->members(DFG)) 188 DRNs.push_back(N); 189 DINs.push_back(DFG.addr<InstrNode*>(I)); 190 } else { 191 llvm_unreachable("Unexpected code node"); 192 return false; 193 } 194 } 195 196 // Sort the list so that use nodes are removed first. This makes the 197 // "unlink" functions a bit faster. 198 auto UsesFirst = [] (NodeAddr<RefNode*> A, NodeAddr<RefNode*> B) -> bool { 199 uint16_t KindA = A.Addr->getKind(), KindB = B.Addr->getKind(); 200 if (KindA == NodeAttrs::Use && KindB == NodeAttrs::Def) 201 return true; 202 if (KindA == NodeAttrs::Def && KindB == NodeAttrs::Use) 203 return false; 204 return A.Id < B.Id; 205 }; 206 std::sort(DRNs.begin(), DRNs.end(), UsesFirst); 207 208 if (trace()) 209 dbgs() << "Removing dead ref nodes:\n"; 210 for (NodeAddr<RefNode*> RA : DRNs) { 211 if (trace()) 212 dbgs() << " " << PrintNode<RefNode*>(RA, DFG) << '\n'; 213 if (DFG.IsUse(RA)) 214 DFG.unlinkUse(RA, true); 215 else if (DFG.IsDef(RA)) 216 DFG.unlinkDef(RA, true); 217 } 218 219 // Now, remove all dead instruction nodes. 220 for (NodeAddr<InstrNode*> IA : DINs) { 221 NodeAddr<BlockNode*> BA = IA.Addr->getOwner(DFG); 222 BA.Addr->removeMember(IA, DFG); 223 if (!DFG.IsCode<NodeAttrs::Stmt>(IA)) 224 continue; 225 226 MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode(); 227 if (trace()) 228 dbgs() << "erasing: " << *MI; 229 MI->eraseFromParent(); 230 } 231 return true; 232 } 233
