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