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