From 891b09a57737f3576dc2e9d2d26e0262d71c8e3e Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Thu, 8 Jun 2023 08:18:07 -0700 Subject: [PATCH] [Hexagon] Make RDF copy propagation a bit more aggressive Update the testcase to actually test for RDF's output. --- llvm/lib/Target/Hexagon/RDFCopy.cpp | 70 ++++++++++++++++++++++++++--------- llvm/lib/Target/Hexagon/RDFCopy.h | 10 ++--- llvm/test/CodeGen/Hexagon/rdf-copy.ll | 8 +++- 3 files changed, 63 insertions(+), 25 deletions(-) diff --git a/llvm/lib/Target/Hexagon/RDFCopy.cpp b/llvm/lib/Target/Hexagon/RDFCopy.cpp index cb31ec0..e24f66d 100644 --- a/llvm/lib/Target/Hexagon/RDFCopy.cpp +++ b/llvm/lib/Target/Hexagon/RDFCopy.cpp @@ -63,11 +63,46 @@ bool CopyPropagation::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) { void CopyPropagation::recordCopy(NodeAddr SA, EqualityMap &EM) { CopyMap.insert(std::make_pair(SA.Id, EM)); Copies.push_back(SA.Id); + + for (auto I : EM) { + auto FS = DefM.find(I.second.Reg); + if (FS == DefM.end() || FS->second.empty()) + continue; // Undefined source + RDefMap[I.second][SA.Id] = FS->second.top()->Id; + // Insert DstR into the map. + RDefMap[I.first]; + } +} + + +void CopyPropagation::updateMap(NodeAddr IA) { + RegisterSet RRs; + for (NodeAddr RA : IA.Addr->members(DFG)) + RRs.insert(RA.Addr->getRegRef(DFG)); + bool Common = false; + for (auto &R : RDefMap) { + if (!RRs.count(R.first)) + continue; + Common = true; + break; + } + if (!Common) + return; + + for (auto &R : RDefMap) { + if (!RRs.count(R.first)) + continue; + auto F = DefM.find(R.first.Reg); + if (F == DefM.end() || F->second.empty()) + continue; + R.second[IA.Id] = F->second.top()->Id; + } } bool CopyPropagation::scanBlock(MachineBasicBlock *B) { bool Changed = false; NodeAddr BA = DFG.findBlock(B); + DFG.markBlock(BA.Id, DefM); for (NodeAddr IA : BA.Addr->members(DFG)) { if (DFG.IsCode(IA)) { @@ -76,28 +111,19 @@ bool CopyPropagation::scanBlock(MachineBasicBlock *B) { if (interpretAsCopy(SA.Addr->getCode(), EM)) recordCopy(SA, EM); } + + updateMap(IA); + DFG.pushAllDefs(IA, DefM); } MachineDomTreeNode *N = MDT.getNode(B); for (auto *I : *N) Changed |= scanBlock(I->getBlock()); + DFG.releaseBlock(BA.Id, DefM); return Changed; } -NodeId CopyPropagation::getLocalReachingDef(RegisterRef RefRR, - NodeAddr IA) { - NodeAddr RA = L.getNearestAliasedRef(RefRR, IA); - if (RA.Id != 0) { - if (RA.Addr->getKind() == NodeAttrs::Def) - return RA.Id; - assert(RA.Addr->getKind() == NodeAttrs::Use); - if (NodeId RD = RA.Addr->getReachingDef()) - return RD; - } - return 0; -} - bool CopyPropagation::run() { scanBlock(&DFG.getMF().front()); @@ -111,6 +137,14 @@ bool CopyPropagation::run() { << Print(J.second, DFG); dbgs() << " }\n"; } + dbgs() << "\nRDef map:\n"; + for (auto R : RDefMap) { + dbgs() << Print(R.first, DFG) << " -> {"; + for (auto &M : R.second) + dbgs() << ' ' << Print(M.first, DFG) << ':' + << Print(M.second, DFG); + dbgs() << " }\n"; + } } bool Changed = false; @@ -150,7 +184,8 @@ bool CopyPropagation::run() { if (DR == SR) continue; - NodeId AtCopy = getLocalReachingDef(SR, SA); + auto &RDefSR = RDefMap[SR]; + NodeId RDefSR_SA = RDefSR[SA.Id]; for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) { auto UA = DFG.addr(N); @@ -163,8 +198,7 @@ bool CopyPropagation::run() { NodeAddr IA = UA.Addr->getOwner(DFG); assert(DFG.IsCode(IA)); - NodeId AtUse = getLocalReachingDef(SR, IA); - if (AtCopy != AtUse) + if (RDefSR[IA.Id] != RDefSR_SA) continue; MachineOperand &Op = UA.Addr->getOp(); @@ -180,8 +214,8 @@ bool CopyPropagation::run() { Op.setReg(NewReg); Op.setSubReg(0); DFG.unlinkUse(UA, false); - if (AtCopy != 0) { - UA.Addr->linkToDef(UA.Id, DFG.addr(AtCopy)); + if (RDefSR_SA != 0) { + UA.Addr->linkToDef(UA.Id, DFG.addr(RDefSR_SA)); } else { UA.Addr->setReachingDef(0); UA.Addr->setSibling(0); diff --git a/llvm/lib/Target/Hexagon/RDFCopy.h b/llvm/lib/Target/Hexagon/RDFCopy.h index 99b18a7..8bca374 100644 --- a/llvm/lib/Target/Hexagon/RDFCopy.h +++ b/llvm/lib/Target/Hexagon/RDFCopy.h @@ -25,8 +25,7 @@ class MachineInstr; namespace rdf { struct CopyPropagation { - CopyPropagation(DataFlowGraph &dfg) : MDT(dfg.getDT()), DFG(dfg), - L(dfg.getMF().getRegInfo(), dfg) {} + CopyPropagation(DataFlowGraph &dfg) : MDT(dfg.getDT()), DFG(dfg) {} virtual ~CopyPropagation() = default; @@ -36,22 +35,23 @@ namespace rdf { DataFlowGraph &getDFG() { return DFG; } using EqualityMap = std::map; - virtual bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM); private: const MachineDominatorTree &MDT; DataFlowGraph &DFG; - Liveness L; + DataFlowGraph::DefStackMap DefM; bool Trace = false; + // map: register -> (map: stmt -> reaching def) + std::map> RDefMap; // map: statement -> (map: dst reg -> src reg) std::map CopyMap; std::vector Copies; void recordCopy(NodeAddr SA, EqualityMap &EM); + void updateMap(NodeAddr IA); bool scanBlock(MachineBasicBlock *B); - NodeId getLocalReachingDef(RegisterRef RefRR, NodeAddr IA); }; } // end namespace rdf diff --git a/llvm/test/CodeGen/Hexagon/rdf-copy.ll b/llvm/test/CodeGen/Hexagon/rdf-copy.ll index 5d0f223..fa1efea 100644 --- a/llvm/test/CodeGen/Hexagon/rdf-copy.ll +++ b/llvm/test/CodeGen/Hexagon/rdf-copy.ll @@ -1,4 +1,6 @@ -; RUN: llc -march=hexagon < %s | FileCheck %s +; RUN: llc -march=hexagon -disable-copyprop < %s | FileCheck %s +; Disable MachineCopyPropagation to expose this opportunity to RDF copy. + ; ; Check that ; { @@ -26,7 +28,7 @@ target triple = "hexagon" %struct.t = type { [12 x i8], ptr, double } %struct.r = type opaque -define ptr @foo(ptr %chain) nounwind readonly { +define ptr @foo(ptr %chain) nounwind readonly #0 { entry: %tobool = icmp eq ptr %chain, null br i1 %tobool, label %if.end, label %while.cond.preheader @@ -48,6 +50,8 @@ if.end: ; preds = %if.end.loopexit, %e ret ptr %chain.addr.1 } +attributes #0 = { nounwind "target-features"="-packets" } + !0 = !{!"any pointer", !1} !1 = !{!"omnipotent char", !2} !2 = !{!"Simple C/C++ TBAA"} -- 2.7.4