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