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 "RDFLiveness.h"
15 #include "llvm/CodeGen/MachineBasicBlock.h"
16 #include "llvm/CodeGen/MachineDominators.h"
17 #include "llvm/CodeGen/MachineInstr.h"
18 #include "llvm/CodeGen/MachineRegisterInfo.h"
19 #include "llvm/Support/CommandLine.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21 #include "llvm/Target/TargetRegisterInfo.h"
22 using namespace llvm;
23 using namespace rdf;
24 
25 #ifndef NDEBUG
26 static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
27 static unsigned CpCount = 0;
28 #endif
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 = DFG.makeRegRef(Dst.getReg(), Dst.getSubReg());
37       RegisterRef SrcR = DFG.makeRegRef(Src.getReg(), Src.getSubReg());
38       assert(TargetRegisterInfo::isPhysicalRegister(DstR.Reg));
39       assert(TargetRegisterInfo::isPhysicalRegister(SrcR.Reg));
40       const TargetRegisterInfo &TRI = DFG.getTRI();
41       if (TRI.getMinimalPhysRegClass(DstR.Reg) !=
42           TRI.getMinimalPhysRegClass(SrcR.Reg))
43         return false;
44       EM.insert(std::make_pair(DstR, SrcR));
45       return true;
46     }
47     case TargetOpcode::REG_SEQUENCE:
48       llvm_unreachable("Unexpected REG_SEQUENCE");
49   }
50   return false;
51 }
52 
53 
54 void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) {
55   CopyMap.insert(std::make_pair(SA.Id, EM));
56   Copies.push_back(SA.Id);
57 }
58 
59 
60 bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
61   bool Changed = false;
62   NodeAddr<BlockNode*> BA = DFG.findBlock(B);
63 
64   for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
65     if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
66       NodeAddr<StmtNode*> SA = IA;
67       EqualityMap EM;
68       if (interpretAsCopy(SA.Addr->getCode(), EM))
69         recordCopy(SA, EM);
70     }
71   }
72 
73   MachineDomTreeNode *N = MDT.getNode(B);
74   for (auto I : *N)
75     Changed |= scanBlock(I->getBlock());
76 
77   return Changed;
78 }
79 
80 
81 NodeId CopyPropagation::getLocalReachingDef(RegisterRef RefRR,
82       NodeAddr<InstrNode*> IA) {
83   NodeAddr<RefNode*> RA = L.getNearestAliasedRef(RefRR, IA);
84   if (RA.Id != 0) {
85     if (RA.Addr->getKind() == NodeAttrs::Def)
86       return RA.Id;
87     assert(RA.Addr->getKind() == NodeAttrs::Use);
88     if (NodeId RD = RA.Addr->getReachingDef())
89       return RD;
90   }
91   return 0;
92 }
93 
94 
95 bool CopyPropagation::run() {
96   scanBlock(&DFG.getMF().front());
97 
98   if (trace()) {
99     dbgs() << "Copies:\n";
100     for (auto I : Copies) {
101       dbgs() << "Instr: " << *DFG.addr<StmtNode*>(I).Addr->getCode();
102       dbgs() << "   eq: {";
103       for (auto J : CopyMap[I])
104         dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '='
105                << Print<RegisterRef>(J.second, DFG);
106       dbgs() << " }\n";
107     }
108   }
109 
110   bool Changed = false;
111 #ifndef NDEBUG
112   bool HasLimit = CpLimit.getNumOccurrences() > 0;
113 #endif
114 
115   auto MinPhysReg = [this] (RegisterRef RR) -> unsigned {
116     const TargetRegisterInfo &TRI = DFG.getTRI();
117     const TargetRegisterClass &RC = *TRI.getMinimalPhysRegClass(RR.Reg);
118     if ((RC.LaneMask & RR.Mask) == RC.LaneMask)
119       return RR.Reg;
120     for (MCSubRegIndexIterator S(RR.Reg, &TRI); S.isValid(); ++S)
121       if (RR.Mask == TRI.getSubRegIndexLaneMask(S.getSubRegIndex()))
122         return S.getSubReg();
123     llvm_unreachable("Should have found a register");
124     return 0;
125   };
126 
127   for (auto C : Copies) {
128 #ifndef NDEBUG
129     if (HasLimit && CpCount >= CpLimit)
130       break;
131 #endif
132     auto SA = DFG.addr<InstrNode*>(C);
133     auto FS = CopyMap.find(SA.Id);
134     if (FS == CopyMap.end())
135       continue;
136 
137     EqualityMap &EM = FS->second;
138     for (NodeAddr<DefNode*> DA : SA.Addr->members_if(DFG.IsDef, DFG)) {
139       RegisterRef DR = DA.Addr->getRegRef(DFG);
140       auto FR = EM.find(DR);
141       if (FR == EM.end())
142         continue;
143       RegisterRef SR = FR->second;
144       if (DR == SR)
145         continue;
146 
147       NodeId AtCopy = getLocalReachingDef(SR, SA);
148 
149       for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
150         auto UA = DFG.addr<UseNode*>(N);
151         NextN = UA.Addr->getSibling();
152         uint16_t F = UA.Addr->getFlags();
153         if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed))
154           continue;
155         if (UA.Addr->getRegRef(DFG) != DR)
156           continue;
157 
158         NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
159         assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
160         NodeId AtUse = getLocalReachingDef(SR, IA);
161         if (AtCopy != AtUse)
162           continue;
163 
164         MachineOperand &Op = UA.Addr->getOp();
165         if (Op.isTied())
166           continue;
167         if (trace()) {
168           dbgs() << "Can replace " << Print<RegisterRef>(DR, DFG)
169                  << " with " << Print<RegisterRef>(SR, DFG) << " in "
170                  << *NodeAddr<StmtNode*>(IA).Addr->getCode();
171         }
172 
173         unsigned NewReg = MinPhysReg(SR);
174         Op.setReg(NewReg);
175         Op.setSubReg(0);
176         DFG.unlinkUse(UA, false);
177         if (AtCopy != 0) {
178           UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode*>(AtCopy));
179         } else {
180           UA.Addr->setReachingDef(0);
181           UA.Addr->setSibling(0);
182         }
183 
184         Changed = true;
185   #ifndef NDEBUG
186         if (HasLimit && CpCount >= CpLimit)
187           break;
188         CpCount++;
189   #endif
190 
191         auto FC = CopyMap.find(IA.Id);
192         if (FC != CopyMap.end()) {
193           // Update the EM map in the copy's entry.
194           auto &M = FC->second;
195           for (auto &J : M) {
196             if (J.second != DR)
197               continue;
198             J.second = SR;
199             break;
200           }
201         }
202       } // for (N in reached-uses)
203     } // for (DA in defs)
204   } // for (C in Copies)
205 
206   return Changed;
207 }
208 
209