llvm/lib/Target/Hexagon/RDFCopy.cpp

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