lib/Target/Hexagon/RDFDeadCode.cpp

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