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