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