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