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
31using namespace llvm;
32using namespace rdf;
33
34#ifndef NDEBUG
35static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
36static unsigned CpCount = 0;
37#endif
38
39bool 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(i: 0);
44 const MachineOperand &Src = MI->getOperand(i: 1);
45 RegisterRef DstR = DFG.makeRegRef(Reg: Dst.getReg(), Sub: Dst.getSubReg());
46 RegisterRef SrcR = DFG.makeRegRef(Reg: Src.getReg(), Sub: Src.getSubReg());
47 assert(Register::isPhysicalRegister(DstR.Reg));
48 assert(Register::isPhysicalRegister(SrcR.Reg));
49 const TargetRegisterInfo &TRI = DFG.getTRI();
50 if (TRI.getMinimalPhysRegClass(Reg: DstR.Reg) !=
51 TRI.getMinimalPhysRegClass(Reg: SrcR.Reg))
52 return false;
53 if (!DFG.isTracked(RR: SrcR) || !DFG.isTracked(RR: DstR))
54 return false;
55 EM.insert(x: std::make_pair(x&: DstR, y&: SrcR));
56 return true;
57 }
58 case TargetOpcode::REG_SEQUENCE:
59 llvm_unreachable("Unexpected REG_SEQUENCE");
60 }
61 return false;
62}
63
64void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) {
65 CopyMap.insert(x: std::make_pair(x&: SA.Id, y&: EM));
66 Copies.push_back(x: SA.Id);
67
68 for (auto I : EM) {
69 auto FS = DefM.find(x: 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
79void CopyPropagation::updateMap(NodeAddr<InstrNode*> IA) {
80 RegisterSet RRs(DFG.getPRI());
81 for (NodeAddr<RefNode*> RA : IA.Addr->members(G: DFG))
82 RRs.insert(x: RA.Addr->getRegRef(G: DFG));
83 bool Common = false;
84 for (auto &R : RDefMap) {
85 if (!RRs.count(x: 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(x: R.first))
95 continue;
96 auto F = DefM.find(x: 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
103bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
104 bool Changed = false;
105 NodeAddr<BlockNode*> BA = DFG.findBlock(BB: B);
106 DFG.markBlock(B: BA.Id, DefM);
107
108 for (NodeAddr<InstrNode*> IA : BA.Addr->members(G: DFG)) {
109 if (DFG.IsCode<NodeAttrs::Stmt>(BA: IA)) {
110 NodeAddr<StmtNode*> SA = IA;
111 EqualityMap EM(std::less<RegisterRef>(DFG.getPRI()));
112 if (interpretAsCopy(MI: SA.Addr->getCode(), EM))
113 recordCopy(SA, EM);
114 }
115
116 updateMap(IA);
117 DFG.pushAllDefs(IA, DM&: DefM);
118 }
119
120 MachineDomTreeNode *N = MDT.getNode(BB: B);
121 for (auto *I : *N)
122 Changed |= scanBlock(B: I->getBlock());
123
124 DFG.releaseBlock(B: BA.Id, DefM);
125 return Changed;
126}
127
128bool CopyPropagation::run() {
129 scanBlock(B: &DFG.getMF().front());
130
131 if (trace()) {
132 dbgs() << "Copies:\n";
133 for (NodeId I : Copies) {
134 dbgs() << "Instr: " << *DFG.addr<StmtNode*>(N: I).Addr->getCode();
135 dbgs() << " eq: {";
136 if (auto It = CopyMap.find(x: I); It != CopyMap.end()) {
137 for (auto J : It->second)
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(Reg: 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(SubIdx: 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*>(N: C);
178 auto FS = CopyMap.find(x: SA.Id);
179 if (FS == CopyMap.end())
180 continue;
181
182 EqualityMap &EM = FS->second;
183 for (NodeAddr<DefNode*> DA : SA.Addr->members_if(P: DFG.IsDef, G: DFG)) {
184 RegisterRef DR = DA.Addr->getRegRef(G: DFG);
185 auto FR = EM.find(x: DR);
186 if (FR == EM.end())
187 continue;
188 RegisterRef SR = FR->second;
189 if (PRI.equal_to(A: DR, B: 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(A: UA.Addr->getRegRef(G: DFG), B: DR))
202 continue;
203
204 NodeAddr<InstrNode*> IA = UA.Addr->getOwner(G: 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, RemoveFromOwner: false);
222 if (RDefSR_SA != 0) {
223 UA.Addr->linkToDef(Self: UA.Id, DA: DFG.addr<DefNode*>(N: 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(x: 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(A: J.second, B: 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}
253