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