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