From c6ddd04d73c31d970176df3e52edfd7a58e91d86 Mon Sep 17 00:00:00 2001 From: Krzysztof Parzyszek Date: Mon, 29 May 2023 16:58:28 -0700 Subject: [PATCH] [RDF] Create individual phi for each indivisible register This isn't quite using register units, but it's getting close. The phi generation is driven by register units, but each phi still contains a reference to a register, potentially with a mask that amounts to a unit. In cases of explicit register aliasing this may still create phis with references that are aliased, whereas separate phis would ideally contain disjoint references (this is all within a single basic block). Previously phis used maximal registers, now they use minimal. This is a step towards both, using register units directly, and a simpler liveness calculation algorithm. The idea is that a phi cannot reach a reference to anything smaller than the phi itself represents. Before there could be a phi for R1_R0, now there will be two for this case (assuming R0 and R1 have one unit each). --- llvm/lib/CodeGen/RDFGraph.cpp | 77 +++---------------------------- llvm/lib/CodeGen/RDFLiveness.cpp | 9 +++- llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp | 6 ++- llvm/test/CodeGen/Hexagon/newify-crash.ll | 2 +- 4 files changed, 19 insertions(+), 75 deletions(-) diff --git a/llvm/lib/CodeGen/RDFGraph.cpp b/llvm/lib/CodeGen/RDFGraph.cpp index 14f9c11..8011134 100644 --- a/llvm/lib/CodeGen/RDFGraph.cpp +++ b/llvm/lib/CodeGen/RDFGraph.cpp @@ -1433,87 +1433,24 @@ void DataFlowGraph::buildPhis(BlockRefsMap &PhiM, RegisterSet &AllRefs, if (HasDF == PhiM.end() || HasDF->second.empty()) return; - // First, remove all R in Refs in such that there exists T in Refs - // such that T covers R. In other words, only leave those refs that - // are not covered by another ref (i.e. maximal with respect to covering). - - auto MaxCoverIn = [this](RegisterRef RR, RegisterSet &RRs) -> RegisterRef { - for (RegisterRef I : RRs) - if (I != RR && RegisterAggr::isCoverOf(I, RR, PRI)) - RR = I; - return RR; - }; - - RegisterSet MaxDF, DefsDF; - for (auto I = HasDF->second.rr_begin(), E = HasDF->second.rr_end(); I != E; - ++I) { - DefsDF.insert(*I); - } - for (RegisterRef I : DefsDF) - MaxDF.insert(MaxCoverIn(I, DefsDF)); - - std::vector MaxRefs; - for (RegisterRef I : MaxDF) - MaxRefs.push_back(MaxCoverIn(I, AllRefs)); - - // Now, for each R in MaxRefs, get the alias closure of R. If the closure - // only has R in it, create a phi a def for R. Otherwise, create a phi, - // and add a def for each S in the closure. - - // Sort the refs so that the phis will be created in a deterministic order. - llvm::sort(MaxRefs); - // Remove duplicates. - auto NewEnd = std::unique(MaxRefs.begin(), MaxRefs.end()); - MaxRefs.erase(NewEnd, MaxRefs.end()); - - auto Aliased = [this, &MaxRefs](RegisterRef RR, - std::vector &Closure) -> bool { - for (unsigned I : Closure) - if (PRI.alias(RR, MaxRefs[I])) - return true; - return false; - }; - // Prepare a list of NodeIds of the block's predecessors. NodeList Preds; const MachineBasicBlock *MBB = BA.Addr->getCode(); for (MachineBasicBlock *PB : MBB->predecessors()) Preds.push_back(findBlock(PB)); - while (!MaxRefs.empty()) { - // Put the first element in the closure, and then add all subsequent - // elements from MaxRefs to it, if they alias at least one element - // already in the closure. - // ClosureIdx: vector of indices in MaxRefs of members of the closure. - std::vector ClosureIdx = {0}; - for (unsigned i = 1; i != MaxRefs.size(); ++i) - if (Aliased(MaxRefs[i], ClosureIdx)) - ClosureIdx.push_back(i); - - // Build a phi for the closure. - unsigned CS = ClosureIdx.size(); + const RegisterAggr &Defs = PhiM[BA.Id]; + uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; + + for (auto I = Defs.rr_begin(), E = Defs.rr_end(); I != E; ++I) { + RegisterRef RR = *I; NodeAddr PA = newPhi(BA); + PA.Addr->addMember(newDef(PA, RR, PhiFlags), *this); - // Add defs. - for (unsigned X = 0; X != CS; ++X) { - RegisterRef RR = MaxRefs[ClosureIdx[X]]; - uint16_t PhiFlags = NodeAttrs::PhiRef | NodeAttrs::Preserving; - NodeAddr DA = newDef(PA, RR, PhiFlags); - PA.Addr->addMember(DA, *this); - } // Add phi uses. for (NodeAddr PBA : Preds) { - for (unsigned X = 0; X != CS; ++X) { - RegisterRef RR = MaxRefs[ClosureIdx[X]]; - NodeAddr PUA = newPhiUse(PA, RR, PBA); - PA.Addr->addMember(PUA, *this); - } + PA.Addr->addMember(newPhiUse(PA, RR, PBA), *this); } - - // Erase from MaxRefs all elements in the closure. - auto Begin = MaxRefs.begin(); - for (unsigned Idx : llvm::reverse(ClosureIdx)) - MaxRefs.erase(Begin + Idx); } } diff --git a/llvm/lib/CodeGen/RDFLiveness.cpp b/llvm/lib/CodeGen/RDFLiveness.cpp index 484ab6e..c3ef9ed 100644 --- a/llvm/lib/CodeGen/RDFLiveness.cpp +++ b/llvm/lib/CodeGen/RDFLiveness.cpp @@ -560,7 +560,11 @@ void Liveness::computePhiInfo() { auto UA = DFG.addr(I.first); // Undef flag is checked above. assert((UA.Addr->getFlags() & NodeAttrs::Undef) == 0); - RegisterRef R(UI->first, I.second); + RegisterRef UseR(UI->first, I.second); // Ref from Uses + // R = intersection of the ref from the phi and the ref from Uses + RegisterRef R = PhiDRs.at(PhiA.Id).intersectWith(UseR); + if (!R) + continue; // Calculate the exposed part of the reached use. RegisterAggr Covered(PRI); for (NodeAddr DA : getAllReachingDefs(R, UA)) { @@ -781,9 +785,10 @@ void Liveness::computeLiveIns() { for (NodeAddr BA : Blocks) { MachineBasicBlock *MB = BA.Addr->getCode(); RefMap &LON = PhiLON[MB]; - for (auto P : BA.Addr->members_if(DFG.IsCode, DFG)) + for (auto P : BA.Addr->members_if(DFG.IsCode, DFG)) { for (const RefMap::value_type &S : RealUseMap[P.Id]) LON[S.first].insert(S.second.begin(), S.second.end()); + } } if (Trace) { diff --git a/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp b/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp index 99aaf1c1..418cb3c 100644 --- a/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp +++ b/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp @@ -320,8 +320,10 @@ bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) { Changed |= DCE.run(); if (Changed) { - if (RDFDump) - dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n'; + if (RDFDump) { + dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n' + << PrintNode(G.getFunc(), G) << '\n'; + } Liveness LV(*MRI, G); LV.trace(RDFDump); LV.computeLiveIns(); diff --git a/llvm/test/CodeGen/Hexagon/newify-crash.ll b/llvm/test/CodeGen/Hexagon/newify-crash.ll index bb29954..2454a38 100644 --- a/llvm/test/CodeGen/Hexagon/newify-crash.ll +++ b/llvm/test/CodeGen/Hexagon/newify-crash.ll @@ -1,7 +1,7 @@ ; RUN: llc -march=hexagon < %s | FileCheck %s ; ; Check that this testcase doesn't crash. -; CHECK: vadd +; CHECK: jump f0 target triple = "hexagon" -- 2.7.4