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