LLVM 20.0.0git
RDFCopy.cpp
Go to the documentation of this file.
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"
25#include "llvm/Support/Debug.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());
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
65void 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
80void 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
104bool 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)) {
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
129bool 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}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
uint64_t Addr
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
static cl::opt< unsigned > CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden)
static unsigned CpCount
Definition: RDFCopy.cpp:37
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI Lower i1 Copies
SI optimize exec mask operations pre RA
This class represents an Operation in the Expression.
Base class for the actual dominator tree node.
Iterator that enumerates the sub-registers of a Reg and the associated sub-register indices.
bool isValid() const
Returns true if this iterator is not yet at the end.
Representation of each machine instruction.
Definition: MachineInstr.h:69
MachineOperand class - Representation of each machine instruction operand.
static constexpr bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
std::set< RegisterRef > RegisterSet
Definition: RDFGraph.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
#define N
std::map< RegisterRef, RegisterRef > EqualityMap
Definition: RDFCopy.h:38
bool equal_to(RegisterRef A, RegisterRef B) const
NodeId getSibling() const
Definition: RDFGraph.h:569