lib/Target/Hexagon/RDFCopy.cpp

   1 //===--- RDFCopy.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 // Simplistic RDF-based copy propagation.
  11
  12 #include "RDFCopy.h"
  13 #include "RDFGraph.h"
  14 #include "llvm/CodeGen/MachineBasicBlock.h"
  15 #include "llvm/CodeGen/MachineDominators.h"
  16 #include "llvm/CodeGen/MachineInstr.h"
  17 #include "llvm/Support/CommandLine.h"
  18
  19 #include <atomic>
  20
  21 #ifndef NDEBUG
  22 static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
  23 static unsigned CpCount = 0;
  24 #endif
  25
  26 using namespace llvm;
  27 using namespace rdf;
  28
  29 void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, MachineInstr *MI) {
  30   assert(MI->getOpcode() == TargetOpcode::COPY);
  31   const MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1);
  32   RegisterRef DstR = { Op0.getReg(), Op0.getSubReg() };
  33   RegisterRef SrcR = { Op1.getReg(), Op1.getSubReg() };
  34   auto FS = DefM.find(SrcR);
  35   if (FS == DefM.end() || FS->second.empty())
  36     return;
  37   Copies.push_back(SA.Id);
  38   RDefMap[SrcR][SA.Id] = FS->second.top()->Id;
  39   // Insert DstR into the map.
  40   RDefMap[DstR];
  41 }
  42
  43
  44 void CopyPropagation::updateMap(NodeAddr<InstrNode*> IA) {
  45   RegisterSet RRs;
  46   for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
  47     RRs.insert(RA.Addr->getRegRef());
  48   bool Common = false;
  49   for (auto &R : RDefMap) {
  50     if (!RRs.count(R.first))
  51       continue;
  52     Common = true;
  53     break;
  54   }
  55   if (!Common)
  56     return;
  57
  58   for (auto &R : RDefMap) {
  59     if (!RRs.count(R.first))
  60       continue;
  61     auto F = DefM.find(R.first);
  62     if (F == DefM.end() || F->second.empty())
  63       continue;
  64     R.second[IA.Id] = F->second.top()->Id;
  65   }
  66 }
  67
  68
  69 bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
  70   bool Changed = false;
  71   auto BA = DFG.getFunc().Addr->findBlock(B, DFG);
  72   DFG.markBlock(BA.Id, DefM);
  73
  74   for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
  75     if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
  76       NodeAddr<StmtNode*> SA = IA;
  77       MachineInstr *MI = SA.Addr->getCode();
  78       if (MI->isCopy())
  79         recordCopy(SA, MI);
  80     }
  81
  82     updateMap(IA);
  83     DFG.pushDefs(IA, DefM);
  84   }
  85
  86   MachineDomTreeNode *N = MDT.getNode(B);
  87   for (auto I : *N)
  88     Changed |= scanBlock(I->getBlock());
  89
  90   DFG.releaseBlock(BA.Id, DefM);
  91   return Changed;
  92 }
  93
  94
  95 bool CopyPropagation::run() {
  96   scanBlock(&DFG.getMF().front());
  97
  98   if (trace()) {
  99     dbgs() << "Copies:\n";
 100     for (auto I : Copies)
 101       dbgs() << *DFG.addr<StmtNode*>(I).Addr->getCode();
 102     dbgs() << "\nRDef map:\n";
 103     for (auto R : RDefMap) {
 104       dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";
 105       for (auto &M : R.second)
 106         dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':'
 107                << Print<NodeId>(M.second, DFG);
 108       dbgs() << " }\n";
 109     }
 110   }
 111
 112   bool Changed = false;
 113   NodeSet Deleted;
 114 #ifndef NDEBUG
 115   bool HasLimit = CpLimit.getNumOccurrences() > 0;
 116 #endif
 117
 118   for (auto I : Copies) {
 119 #ifndef NDEBUG
 120     if (HasLimit && CpCount >= CpLimit)
 121       break;
 122 #endif
 123     if (Deleted.count(I))
 124       continue;
 125     auto SA = DFG.addr<InstrNode*>(I);
 126     NodeList Ds = SA.Addr->members_if(DFG.IsDef, DFG);
 127     if (Ds.size() != 1)
 128       continue;
 129     NodeAddr<DefNode*> DA = Ds[0];
 130     RegisterRef DR0 = DA.Addr->getRegRef();
 131     NodeList Us = SA.Addr->members_if(DFG.IsUse, DFG);
 132     if (Us.size() != 1)
 133       continue;
 134     NodeAddr<UseNode*> UA0 = Us[0];
 135     RegisterRef UR0 = UA0.Addr->getRegRef();
 136     NodeId RD0 = UA0.Addr->getReachingDef();
 137
 138     for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
 139       auto UA = DFG.addr<UseNode*>(N);
 140       NextN = UA.Addr->getSibling();
 141       uint16_t F = UA.Addr->getFlags();
 142       if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed))
 143         continue;
 144       if (UA.Addr->getRegRef() != DR0)
 145         continue;
 146       NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
 147       assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
 148       MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
 149       if (RDefMap[UR0][IA.Id] != RD0)
 150         continue;
 151       MachineOperand &Op = UA.Addr->getOp();
 152       if (Op.isTied())
 153         continue;
 154       if (trace()) {
 155         dbgs() << "can replace " << Print<RegisterRef>(DR0, DFG)
 156                << " with " << Print<RegisterRef>(UR0, DFG) << " in "
 157                << *NodeAddr<StmtNode*>(IA).Addr->getCode();
 158       }
 159
 160       Op.setReg(UR0.Reg);
 161       Op.setSubReg(UR0.Sub);
 162       Changed = true;
 163 #ifndef NDEBUG
 164       if (HasLimit && CpCount >= CpLimit)
 165         break;
 166       CpCount++;
 167 #endif
 168
 169       if (MI->isCopy()) {
 170         MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1);
 171         if (Op0.getReg() == Op1.getReg() && Op0.getSubReg() == Op1.getSubReg())
 172           MI->eraseFromParent();
 173         Deleted.insert(IA.Id);
 174       }
 175     }
 176   }
 177
 178   return Changed;
 179 }
 180