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" 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 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. 116 bool DeadCodeElimination::collect() { 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. 179 bool DeadCodeElimination::erase(const SetVector<NodeId> &Nodes) { 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 llvm::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 } 244
