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