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/RDFGraph.h" 18 #include "llvm/CodeGen/RDFLiveness.h" 19 #include "llvm/CodeGen/RDFRegisters.h" 20 #include "llvm/CodeGen/TargetOpcodes.h" 21 #include "llvm/CodeGen/TargetRegisterInfo.h" 22 #include "llvm/MC/MCRegisterInfo.h" 23 #include "llvm/Support/CommandLine.h" 24 #include "llvm/Support/Debug.h" 25 #include "llvm/Support/ErrorHandling.h" 26 #include "llvm/Support/raw_ostream.h" 27 #include <cassert> 28 #include <cstdint> 29 #include <utility> 30 31 using namespace llvm; 32 using namespace rdf; 33 34 #ifndef NDEBUG 35 static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden); 36 static unsigned CpCount = 0; 37 #endif 38 39 bool CopyPropagation::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) { 40 unsigned Opc = MI->getOpcode(); 41 switch (Opc) { 42 case TargetOpcode::COPY: { 43 const MachineOperand &Dst = MI->getOperand(0); 44 const MachineOperand &Src = MI->getOperand(1); 45 RegisterRef DstR = DFG.makeRegRef(Dst.getReg(), Dst.getSubReg()); 46 RegisterRef SrcR = DFG.makeRegRef(Src.getReg(), Src.getSubReg()); 47 assert(Register::isPhysicalRegister(DstR.Reg)); 48 assert(Register::isPhysicalRegister(SrcR.Reg)); 49 const TargetRegisterInfo &TRI = DFG.getTRI(); 50 if (TRI.getMinimalPhysRegClass(DstR.Reg) != 51 TRI.getMinimalPhysRegClass(SrcR.Reg)) 52 return false; 53 if (!DFG.isTracked(SrcR) || !DFG.isTracked(DstR)) 54 return false; 55 EM.insert(std::make_pair(DstR, SrcR)); 56 return true; 57 } 58 case TargetOpcode::REG_SEQUENCE: 59 llvm_unreachable("Unexpected REG_SEQUENCE"); 60 } 61 return false; 62 } 63 64 void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) { 65 CopyMap.insert(std::make_pair(SA.Id, EM)); 66 Copies.push_back(SA.Id); 67 68 for (auto I : EM) { 69 auto FS = DefM.find(I.second.Reg); 70 if (FS == DefM.end() || FS->second.empty()) 71 continue; // Undefined source 72 RDefMap[I.second][SA.Id] = FS->second.top()->Id; 73 // Insert DstR into the map. 74 RDefMap[I.first]; 75 } 76 } 77 78 79 void CopyPropagation::updateMap(NodeAddr<InstrNode*> IA) { 80 RegisterSet RRs(DFG.getPRI()); 81 for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG)) 82 RRs.insert(RA.Addr->getRegRef(DFG)); 83 bool Common = false; 84 for (auto &R : RDefMap) { 85 if (!RRs.count(R.first)) 86 continue; 87 Common = true; 88 break; 89 } 90 if (!Common) 91 return; 92 93 for (auto &R : RDefMap) { 94 if (!RRs.count(R.first)) 95 continue; 96 auto F = DefM.find(R.first.Reg); 97 if (F == DefM.end() || F->second.empty()) 98 continue; 99 R.second[IA.Id] = F->second.top()->Id; 100 } 101 } 102 103 bool CopyPropagation::scanBlock(MachineBasicBlock *B) { 104 bool Changed = false; 105 NodeAddr<BlockNode*> BA = DFG.findBlock(B); 106 DFG.markBlock(BA.Id, DefM); 107 108 for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) { 109 if (DFG.IsCode<NodeAttrs::Stmt>(IA)) { 110 NodeAddr<StmtNode*> SA = IA; 111 EqualityMap EM(std::less<RegisterRef>(DFG.getPRI())); 112 if (interpretAsCopy(SA.Addr->getCode(), EM)) 113 recordCopy(SA, EM); 114 } 115 116 updateMap(IA); 117 DFG.pushAllDefs(IA, DefM); 118 } 119 120 MachineDomTreeNode *N = MDT.getNode(B); 121 for (auto *I : *N) 122 Changed |= scanBlock(I->getBlock()); 123 124 DFG.releaseBlock(BA.Id, DefM); 125 return Changed; 126 } 127 128 bool CopyPropagation::run() { 129 scanBlock(&DFG.getMF().front()); 130 131 if (trace()) { 132 dbgs() << "Copies:\n"; 133 for (NodeId I : Copies) { 134 dbgs() << "Instr: " << *DFG.addr<StmtNode*>(I).Addr->getCode(); 135 dbgs() << " eq: {"; 136 if (CopyMap.count(I)) { 137 for (auto J : CopyMap.at(I)) 138 dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '=' 139 << Print<RegisterRef>(J.second, DFG); 140 } 141 dbgs() << " }\n"; 142 } 143 dbgs() << "\nRDef map:\n"; 144 for (auto R : RDefMap) { 145 dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {"; 146 for (auto &M : R.second) 147 dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':' 148 << Print<NodeId>(M.second, DFG); 149 dbgs() << " }\n"; 150 } 151 } 152 153 bool Changed = false; 154 #ifndef NDEBUG 155 bool HasLimit = CpLimit.getNumOccurrences() > 0; 156 #endif 157 158 auto MinPhysReg = [this] (RegisterRef RR) -> unsigned { 159 const TargetRegisterInfo &TRI = DFG.getTRI(); 160 const TargetRegisterClass &RC = *TRI.getMinimalPhysRegClass(RR.Reg); 161 if ((RC.LaneMask & RR.Mask) == RC.LaneMask) 162 return RR.Reg; 163 for (MCSubRegIndexIterator S(RR.Reg, &TRI); S.isValid(); ++S) 164 if (RR.Mask == TRI.getSubRegIndexLaneMask(S.getSubRegIndex())) 165 return S.getSubReg(); 166 llvm_unreachable("Should have found a register"); 167 return 0; 168 }; 169 170 const PhysicalRegisterInfo &PRI = DFG.getPRI(); 171 172 for (NodeId 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(DFG); 185 auto FR = EM.find(DR); 186 if (FR == EM.end()) 187 continue; 188 RegisterRef SR = FR->second; 189 if (PRI.equal_to(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 (!PRI.equal_to(UA.Addr->getRegRef(DFG), 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 unsigned NewReg = MinPhysReg(SR); 219 Op.setReg(NewReg); 220 Op.setSubReg(0); 221 DFG.unlinkUse(UA, false); 222 if (RDefSR_SA != 0) { 223 UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode*>(RDefSR_SA)); 224 } else { 225 UA.Addr->setReachingDef(0); 226 UA.Addr->setSibling(0); 227 } 228 229 Changed = true; 230 #ifndef NDEBUG 231 if (HasLimit && CpCount >= CpLimit) 232 break; 233 CpCount++; 234 #endif 235 236 auto FC = CopyMap.find(IA.Id); 237 if (FC != CopyMap.end()) { 238 // Update the EM map in the copy's entry. 239 auto &M = FC->second; 240 for (auto &J : M) { 241 if (!PRI.equal_to(J.second, DR)) 242 continue; 243 J.second = SR; 244 break; 245 } 246 } 247 } // for (N in reached-uses) 248 } // for (DA in defs) 249 } // for (C in Copies) 250 251 return Changed; 252 } 253