contrib/llvm/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 // 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/CodeGen/MachineRegisterInfo.h"
  18 #include "llvm/Support/CommandLine.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Target/TargetRegisterInfo.h"
  21 using namespace llvm;
  22 using namespace rdf;
  23
  24 #ifndef NDEBUG
  25 static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
  26 static unsigned CpCount = 0;
  27 #endif
  28
  29 bool CopyPropagation::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
  30   unsigned Opc = MI->getOpcode();
  31   switch (Opc) {
  32     case TargetOpcode::COPY: {
  33       const MachineOperand &Dst = MI->getOperand(0);
  34       const MachineOperand &Src = MI->getOperand(1);
  35       RegisterRef DstR = { Dst.getReg(), Dst.getSubReg() };
  36       RegisterRef SrcR = { Src.getReg(), Src.getSubReg() };
  37       if (TargetRegisterInfo::isVirtualRegister(DstR.Reg)) {
  38         if (!TargetRegisterInfo::isVirtualRegister(SrcR.Reg))
  39           return false;
  40         MachineRegisterInfo &MRI = DFG.getMF().getRegInfo();
  41         if (MRI.getRegClass(DstR.Reg) != MRI.getRegClass(SrcR.Reg))
  42           return false;
  43       } else if (TargetRegisterInfo::isPhysicalRegister(DstR.Reg)) {
  44         if (!TargetRegisterInfo::isPhysicalRegister(SrcR.Reg))
  45           return false;
  46         const TargetRegisterInfo &TRI = DFG.getTRI();
  47         if (TRI.getMinimalPhysRegClass(DstR.Reg) !=
  48             TRI.getMinimalPhysRegClass(SrcR.Reg))
  49           return false;
  50       } else {
  51         // Copy between some unknown objects.
  52         return false;
  53       }
  54       EM.insert(std::make_pair(DstR, SrcR));
  55       return true;
  56     }
  57     case TargetOpcode::REG_SEQUENCE: {
  58       const MachineOperand &Dst = MI->getOperand(0);
  59       RegisterRef DefR = { Dst.getReg(), Dst.getSubReg() };
  60       SmallVector<TargetInstrInfo::RegSubRegPairAndIdx,2> Inputs;
  61       const TargetInstrInfo &TII = DFG.getTII();
  62       if (!TII.getRegSequenceInputs(*MI, 0, Inputs))
  63         return false;
  64       for (auto I : Inputs) {
  65         unsigned S = DFG.getTRI().composeSubRegIndices(DefR.Sub, I.SubIdx);
  66         RegisterRef DR = { DefR.Reg, S };
  67         RegisterRef SR = { I.Reg, I.SubReg };
  68         EM.insert(std::make_pair(DR, SR));
  69       }
  70       return true;
  71     }
  72   }
  73   return false;
  74 }
  75
  76
  77 void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) {
  78   CopyMap.insert(std::make_pair(SA.Id, EM));
  79   Copies.push_back(SA.Id);
  80
  81   for (auto I : EM) {
  82     auto FS = DefM.find(I.second);
  83     if (FS == DefM.end() || FS->second.empty())
  84       continue; // Undefined source
  85     RDefMap[I.second][SA.Id] = FS->second.top()->Id;
  86     // Insert DstR into the map.
  87     RDefMap[I.first];
  88   }
  89 }
  90
  91
  92 void CopyPropagation::updateMap(NodeAddr<InstrNode*> IA) {
  93   RegisterSet RRs;
  94   for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
  95     RRs.insert(RA.Addr->getRegRef());
  96   bool Common = false;
  97   for (auto &R : RDefMap) {
  98     if (!RRs.count(R.first))
  99       continue;
 100     Common = true;
 101     break;
 102   }
 103   if (!Common)
 104     return;
 105
 106   for (auto &R : RDefMap) {
 107     if (!RRs.count(R.first))
 108       continue;
 109     auto F = DefM.find(R.first);
 110     if (F == DefM.end() || F->second.empty())
 111       continue;
 112     R.second[IA.Id] = F->second.top()->Id;
 113   }
 114 }
 115
 116
 117 bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
 118   bool Changed = false;
 119   auto BA = DFG.getFunc().Addr->findBlock(B, DFG);
 120   DFG.markBlock(BA.Id, DefM);
 121
 122   for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
 123     if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
 124       NodeAddr<StmtNode*> SA = IA;
 125       EqualityMap EM;
 126       if (interpretAsCopy(SA.Addr->getCode(), EM))
 127         recordCopy(SA, EM);
 128     }
 129
 130     updateMap(IA);
 131     DFG.pushDefs(IA, DefM);
 132   }
 133
 134   MachineDomTreeNode *N = MDT.getNode(B);
 135   for (auto I : *N)
 136     Changed |= scanBlock(I->getBlock());
 137
 138   DFG.releaseBlock(BA.Id, DefM);
 139   return Changed;
 140 }
 141
 142
 143 bool CopyPropagation::run() {
 144   scanBlock(&DFG.getMF().front());
 145
 146   if (trace()) {
 147     dbgs() << "Copies:\n";
 148     for (auto I : Copies) {
 149       dbgs() << "Instr: " << *DFG.addr<StmtNode*>(I).Addr->getCode();
 150       dbgs() << "   eq: {";
 151       for (auto J : CopyMap[I])
 152         dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '='
 153                << Print<RegisterRef>(J.second, DFG);
 154       dbgs() << " }\n";
 155     }
 156     dbgs() << "\nRDef map:\n";
 157     for (auto R : RDefMap) {
 158       dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";
 159       for (auto &M : R.second)
 160         dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':'
 161                << Print<NodeId>(M.second, DFG);
 162       dbgs() << " }\n";
 163     }
 164   }
 165
 166   bool Changed = false;
 167 #ifndef NDEBUG
 168   bool HasLimit = CpLimit.getNumOccurrences() > 0;
 169 #endif
 170
 171   for (auto C : Copies) {
 172 #ifndef NDEBUG
 173     if (HasLimit && CpCount >= CpLimit)
 174       break;
 175 #endif
 176     auto SA = DFG.addr<InstrNode*>(C);
 177     auto FS = CopyMap.find(SA.Id);
 178     if (FS == CopyMap.end())
 179       continue;
 180
 181     EqualityMap &EM = FS->second;
 182     for (NodeAddr<DefNode*> DA : SA.Addr->members_if(DFG.IsDef, DFG)) {
 183       RegisterRef DR = DA.Addr->getRegRef();
 184       auto FR = EM.find(DR);
 185       if (FR == EM.end())
 186         continue;
 187       RegisterRef SR = FR->second;
 188       if (DR == SR)
 189         continue;
 190
 191       auto &RDefSR = RDefMap[SR];
 192       NodeId RDefSR_SA = RDefSR[SA.Id];
 193
 194       for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
 195         auto UA = DFG.addr<UseNode*>(N);
 196         NextN = UA.Addr->getSibling();
 197         uint16_t F = UA.Addr->getFlags();
 198         if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed))
 199           continue;
 200         if (UA.Addr->getRegRef() != DR)
 201           continue;
 202
 203         NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
 204         assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
 205         if (RDefSR[IA.Id] != RDefSR_SA)
 206           continue;
 207
 208         MachineOperand &Op = UA.Addr->getOp();
 209         if (Op.isTied())
 210           continue;
 211         if (trace()) {
 212           dbgs() << "Can replace " << Print<RegisterRef>(DR, DFG)
 213                  << " with " << Print<RegisterRef>(SR, DFG) << " in "
 214                  << *NodeAddr<StmtNode*>(IA).Addr->getCode();
 215         }
 216
 217         Op.setReg(SR.Reg);
 218         Op.setSubReg(SR.Sub);
 219         DFG.unlinkUse(UA, false);
 220         if (RDefSR_SA != 0) {
 221           UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode*>(RDefSR_SA));
 222         } else {
 223           UA.Addr->setReachingDef(0);
 224           UA.Addr->setSibling(0);
 225         }
 226
 227         Changed = true;
 228   #ifndef NDEBUG
 229         if (HasLimit && CpCount >= CpLimit)
 230           break;
 231         CpCount++;
 232   #endif
 233
 234         auto FC = CopyMap.find(IA.Id);
 235         if (FC != CopyMap.end()) {
 236           // Update the EM map in the copy's entry.
 237           auto &M = FC->second;
 238           for (auto &J : M) {
 239             if (J.second != DR)
 240               continue;
 241             J.second = SR;
 242             break;
 243           }
 244         }
 245       } // for (N in reached-uses)
 246     } // for (DA in defs)
 247   } // for (C in Copies)
 248
 249   return Changed;
 250 }
 251