RDFCopy.cpp revision 363496 
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/MachineRegisterInfo.h"
18#include "llvm/CodeGen/RDFGraph.h"
19#include "llvm/CodeGen/RDFLiveness.h"
20#include "llvm/CodeGen/RDFRegisters.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
32using namespace llvm;
33using namespace rdf;
34
35#ifndef NDEBUG
36static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
37static unsigned CpCount = 0;
38#endif
39
40bool 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
63void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) {
64  CopyMap.insert(std::make_pair(SA.Id, EM));
65  Copies.push_back(SA.Id);
66}
67
68bool 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
88NodeId 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
101bool 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}
214