https://github.com/llvmbot created https://github.com/llvm/llvm-project/pull/171472
Backport c94641833023ea1ed62b9a1c2b34c583719375cb Requested by: @iajbar >From dc5b96d25a4dfb7f4140d27c167f40a4185a2e13 Mon Sep 17 00:00:00 2001 From: Abinaya Saravanan <[email protected]> Date: Mon, 17 Nov 2025 15:28:30 +0530 Subject: [PATCH] [MachinePipeliner] Detect a cycle in PHI dependencies early on (#167095) - This patch detects cycles by phis and bails out if one is found. - It prevents to violate DAG restrictions. Abort pipelining in the below case %1 = phi i32 [ %a, %entry ], [ %3, %loop ] %2 = phi i32 [ %a, %entry ], [ %1, %loop ] %3 = phi i32 [ %b, %entry ], [ %2, %loop ] --------- Co-authored-by: Ryotaro Kasuga <[email protected]> (cherry picked from commit c94641833023ea1ed62b9a1c2b34c583719375cb) --- llvm/lib/CodeGen/MachinePipeliner.cpp | 60 ++++++++++++++++++++++ llvm/test/CodeGen/Hexagon/swp-phi-cycle.ll | 23 +++++++++ 2 files changed, 83 insertions(+) create mode 100644 llvm/test/CodeGen/Hexagon/swp-phi-cycle.ll diff --git a/llvm/lib/CodeGen/MachinePipeliner.cpp b/llvm/lib/CodeGen/MachinePipeliner.cpp index 0e7cb0c980d40..26ca5dee3735f 100644 --- a/llvm/lib/CodeGen/MachinePipeliner.cpp +++ b/llvm/lib/CodeGen/MachinePipeliner.cpp @@ -488,6 +488,61 @@ void MachinePipeliner::setPragmaPipelineOptions(MachineLoop &L) { } } +/// Depth-first search to detect cycles among PHI dependencies. +/// Returns true if a cycle is detected within the PHI-only subgraph. +static bool hasPHICycleDFS( + unsigned Reg, const DenseMap<unsigned, SmallVector<unsigned, 2>> &PhiDeps, + SmallSet<unsigned, 8> &Visited, SmallSet<unsigned, 8> &RecStack) { + + // If Reg is not a PHI-def it cannot contribute to a PHI cycle. + auto It = PhiDeps.find(Reg); + if (It == PhiDeps.end()) + return false; + + if (RecStack.count(Reg)) + return true; // backedge. + if (Visited.count(Reg)) + return false; + + Visited.insert(Reg); + RecStack.insert(Reg); + + for (unsigned Dep : It->second) { + if (hasPHICycleDFS(Dep, PhiDeps, Visited, RecStack)) + return true; + } + + RecStack.erase(Reg); + return false; +} + +static bool hasPHICycle(const MachineBasicBlock *LoopHeader, + const MachineRegisterInfo &MRI) { + DenseMap<unsigned, SmallVector<unsigned, 2>> PhiDeps; + + // Collect PHI nodes and their dependencies. + for (const MachineInstr &MI : LoopHeader->phis()) { + unsigned DefReg = MI.getOperand(0).getReg(); + auto Ins = PhiDeps.try_emplace(DefReg).first; + + // PHI operands are (Reg, MBB) pairs starting at index 1. + for (unsigned I = 1; I < MI.getNumOperands(); I += 2) + Ins->second.push_back(MI.getOperand(I).getReg()); + } + + // DFS to detect cycles among PHI nodes. + SmallSet<unsigned, 8> Visited, RecStack; + + // Start DFS from each PHI-def. + for (const auto &KV : PhiDeps) { + unsigned Reg = KV.first; + if (hasPHICycleDFS(Reg, PhiDeps, Visited, RecStack)) + return true; + } + + return false; +} + /// Return true if the loop can be software pipelined. The algorithm is /// restricted to loops with a single basic block. Make sure that the /// branch in the loop can be analyzed. @@ -502,6 +557,11 @@ bool MachinePipeliner::canPipelineLoop(MachineLoop &L) { return false; } + if (hasPHICycle(L.getHeader(), MF->getRegInfo())) { + LLVM_DEBUG(dbgs() << "Cannot pipeline loop due to PHI cycle\n"); + return false; + } + if (disabledByPragma) { ORE->emit([&]() { return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop", diff --git a/llvm/test/CodeGen/Hexagon/swp-phi-cycle.ll b/llvm/test/CodeGen/Hexagon/swp-phi-cycle.ll new file mode 100644 index 0000000000000..1b4fc464fa092 --- /dev/null +++ b/llvm/test/CodeGen/Hexagon/swp-phi-cycle.ll @@ -0,0 +1,23 @@ +; RUN: llc -mtriple=hexagon-unknown-linux-gnu -enable-pipeliner -debug-only=pipeliner < %s 2>&1 | FileCheck %s +; REQUIRES: asserts + +; CHECK: Cannot pipeline loop due to PHI cycle + +define void @phi_cycle_loop(i32 %a, i32 %b) { +entry: + br label %loop + +loop: + %1 = phi i32 [ %a, %entry ], [ %3, %loop ] + %2 = phi i32 [ %a, %entry ], [ %1, %loop ] + %3 = phi i32 [ %b, %entry ], [ %2, %loop ] + + ; Prevent PHI elimination by using all values + %add1 = add i32 %1, %2 + %add2 = add i32 %add1, %3 + %cmp = icmp slt i32 %add2, 100 + br i1 %cmp, label %loop, label %exit + +exit: + ret void +} _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
