1 //===--- RDFCopy.cpp ------------------------------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // RDF-based copy propagation.
11 
12 #include "RDFCopy.h"
13 #include "RDFGraph.h"
14 #include "llvm/CodeGen/MachineBasicBlock.h"
15 #include "llvm/CodeGen/MachineDominators.h"
16 #include "llvm/CodeGen/MachineInstr.h"
17 #include "llvm/CodeGen/MachineRegisterInfo.h"
18 #include "llvm/Support/CommandLine.h"
19 #include "llvm/Target/TargetInstrInfo.h"
20 #include "llvm/Target/TargetRegisterInfo.h"
21 
22 #ifndef NDEBUG
23 static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
24 static unsigned CpCount = 0;
25 #endif
26 
27 using namespace llvm;
28 using namespace rdf;
29 
30 bool CopyPropagation::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
31   unsigned Opc = MI->getOpcode();
32   switch (Opc) {
33     case TargetOpcode::COPY: {
34       const MachineOperand &Dst = MI->getOperand(0);
35       const MachineOperand &Src = MI->getOperand(1);
36       RegisterRef DstR = { Dst.getReg(), Dst.getSubReg() };
37       RegisterRef SrcR = { Src.getReg(), Src.getSubReg() };
38       if (TargetRegisterInfo::isVirtualRegister(DstR.Reg)) {
39         if (!TargetRegisterInfo::isVirtualRegister(SrcR.Reg))
40           return false;
41         MachineRegisterInfo &MRI = DFG.getMF().getRegInfo();
42         if (MRI.getRegClass(DstR.Reg) != MRI.getRegClass(SrcR.Reg))
43           return false;
44       } else if (TargetRegisterInfo::isPhysicalRegister(DstR.Reg)) {
45         if (!TargetRegisterInfo::isPhysicalRegister(SrcR.Reg))
46           return false;
47         const TargetRegisterInfo &TRI = DFG.getTRI();
48         if (TRI.getMinimalPhysRegClass(DstR.Reg) !=
49             TRI.getMinimalPhysRegClass(SrcR.Reg))
50           return false;
51       } else {
52         // Copy between some unknown objects.
53         return false;
54       }
55       EM.insert(std::make_pair(DstR, SrcR));
56       return true;
57     }
58     case TargetOpcode::REG_SEQUENCE: {
59       const MachineOperand &Dst = MI->getOperand(0);
60       RegisterRef DefR = { Dst.getReg(), Dst.getSubReg() };
61       SmallVector<TargetInstrInfo::RegSubRegPairAndIdx,2> Inputs;
62       const TargetInstrInfo &TII = DFG.getTII();
63       if (!TII.getRegSequenceInputs(*MI, 0, Inputs))
64         return false;
65       for (auto I : Inputs) {
66         unsigned S = DFG.getTRI().composeSubRegIndices(DefR.Sub, I.SubIdx);
67         RegisterRef DR = { DefR.Reg, S };
68         RegisterRef SR = { I.Reg, I.SubReg };
69         EM.insert(std::make_pair(DR, SR));
70       }
71       return true;
72     }
73   }
74   return false;
75 }
76 
77 
78 void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) {
79   CopyMap.insert(std::make_pair(SA.Id, EM));
80   Copies.push_back(SA.Id);
81 
82   for (auto I : EM) {
83     auto FS = DefM.find(I.second);
84     if (FS == DefM.end() || FS->second.empty())
85       continue; // Undefined source
86     RDefMap[I.second][SA.Id] = FS->second.top()->Id;
87     // Insert DstR into the map.
88     RDefMap[I.first];
89   }
90 }
91 
92 
93 void CopyPropagation::updateMap(NodeAddr<InstrNode*> IA) {
94   RegisterSet RRs;
95   for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
96     RRs.insert(RA.Addr->getRegRef());
97   bool Common = false;
98   for (auto &R : RDefMap) {
99     if (!RRs.count(R.first))
100       continue;
101     Common = true;
102     break;
103   }
104   if (!Common)
105     return;
106 
107   for (auto &R : RDefMap) {
108     if (!RRs.count(R.first))
109       continue;
110     auto F = DefM.find(R.first);
111     if (F == DefM.end() || F->second.empty())
112       continue;
113     R.second[IA.Id] = F->second.top()->Id;
114   }
115 }
116 
117 
118 bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
119   bool Changed = false;
120   auto BA = DFG.getFunc().Addr->findBlock(B, DFG);
121   DFG.markBlock(BA.Id, DefM);
122 
123   for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
124     if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
125       NodeAddr<StmtNode*> SA = IA;
126       EqualityMap EM;
127       if (interpretAsCopy(SA.Addr->getCode(), EM))
128         recordCopy(SA, EM);
129     }
130 
131     updateMap(IA);
132     DFG.pushDefs(IA, DefM);
133   }
134 
135   MachineDomTreeNode *N = MDT.getNode(B);
136   for (auto I : *N)
137     Changed |= scanBlock(I->getBlock());
138 
139   DFG.releaseBlock(BA.Id, DefM);
140   return Changed;
141 }
142 
143 
144 bool CopyPropagation::run() {
145   scanBlock(&DFG.getMF().front());
146 
147   if (trace()) {
148     dbgs() << "Copies:\n";
149     for (auto I : Copies) {
150       dbgs() << "Instr: " << *DFG.addr<StmtNode*>(I).Addr->getCode();
151       dbgs() << "   eq: {";
152       for (auto J : CopyMap[I])
153         dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '='
154                << Print<RegisterRef>(J.second, DFG);
155       dbgs() << " }\n";
156     }
157     dbgs() << "\nRDef map:\n";
158     for (auto R : RDefMap) {
159       dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";
160       for (auto &M : R.second)
161         dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':'
162                << Print<NodeId>(M.second, DFG);
163       dbgs() << " }\n";
164     }
165   }
166 
167   bool Changed = false;
168 #ifndef NDEBUG
169   bool HasLimit = CpLimit.getNumOccurrences() > 0;
170 #endif
171 
172   for (auto C : Copies) {
173 #ifndef NDEBUG
174     if (HasLimit && CpCount >= CpLimit)
175       break;
176 #endif
177     auto SA = DFG.addr<InstrNode*>(C);
178     auto FS = CopyMap.find(SA.Id);
179     if (FS == CopyMap.end())
180       continue;
181 
182     EqualityMap &EM = FS->second;
183     for (NodeAddr<DefNode*> DA : SA.Addr->members_if(DFG.IsDef, DFG)) {
184       RegisterRef DR = DA.Addr->getRegRef();
185       auto FR = EM.find(DR);
186       if (FR == EM.end())
187         continue;
188       RegisterRef SR = FR->second;
189       if (DR == SR)
190         continue;
191 
192       auto &RDefSR = RDefMap[SR];
193       NodeId RDefSR_SA = RDefSR[SA.Id];
194 
195       for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
196         auto UA = DFG.addr<UseNode*>(N);
197         NextN = UA.Addr->getSibling();
198         uint16_t F = UA.Addr->getFlags();
199         if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed))
200           continue;
201         if (UA.Addr->getRegRef() != DR)
202           continue;
203 
204         NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
205         assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
206         if (RDefSR[IA.Id] != RDefSR_SA)
207           continue;
208 
209         MachineOperand &Op = UA.Addr->getOp();
210         if (Op.isTied())
211           continue;
212         if (trace()) {
213           dbgs() << "Can replace " << Print<RegisterRef>(DR, DFG)
214                  << " with " << Print<RegisterRef>(SR, DFG) << " in "
215                  << *NodeAddr<StmtNode*>(IA).Addr->getCode();
216         }
217 
218         Op.setReg(SR.Reg);
219         Op.setSubReg(SR.Sub);
220         DFG.unlinkUse(UA, false);
221         UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode*>(RDefSR_SA));
222 
223         Changed = true;
224   #ifndef NDEBUG
225         if (HasLimit && CpCount >= CpLimit)
226           break;
227         CpCount++;
228   #endif
229 
230         auto FC = CopyMap.find(IA.Id);
231         if (FC != CopyMap.end()) {
232           // Update the EM map in the copy's entry.
233           auto &M = FC->second;
234           for (auto &J : M) {
235             if (J.second != DR)
236               continue;
237             J.second = SR;
238             break;
239           }
240         }
241       } // for (N in reached-uses)
242     } // for (DA in defs)
243   } // for (C in Copies)
244 
245   return Changed;
246 }
247 
248