[AMDGPU] Refine GCNHazardRecognizer hasHazard() #138841

perlfu · 2025-05-07T10:22:37Z

Remove recursion to avoid stack overflow on large CFGs.
Avoid worklist for hazard search within single MachineBasicBlock.
Ensure predecessors are visited for all state combinations.

llvmbot · 2025-05-07T10:23:12Z

@llvm/pr-subscribers-backend-amdgpu

Author: Carl Ritson (perlfu)

Changes

Remove recursion to avoid stack overflow on large CFGs.
Avoid worklist for hazard search within single MachineBasicBlock.
Ensure predecessors are visited for all state combinations.

Full diff: https://github.com/llvm/llvm-project/pull/138841.diff

1 Files Affected:

(modified) llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp (+48-31)

diff --git a/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp b/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp
index aaefe27b1324f..644fbb77a495a 100644
--- a/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp
+++ b/llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp
@@ -436,42 +436,55 @@ using IsExpiredFn = function_ref<bool(const MachineInstr &, int WaitStates)>;
 using GetNumWaitStatesFn = function_ref<unsigned int(const MachineInstr &)>;
 
 // Search for a hazard in a block and its predecessors.
+// StateT must implement getHashValue().
 template <typename StateT>
 static bool
-hasHazard(StateT State,
+hasHazard(StateT InitialState,
           function_ref<HazardFnResult(StateT &, const MachineInstr &)> IsHazard,
           function_ref<void(StateT &, const MachineInstr &)> UpdateState,
-          const MachineBasicBlock *MBB,
-          MachineBasicBlock::const_reverse_instr_iterator I,
-          DenseSet<const MachineBasicBlock *> &Visited) {
-  for (auto E = MBB->instr_rend(); I != E; ++I) {
-    // No need to look at parent BUNDLE instructions.
-    if (I->isBundle())
-      continue;
+          const MachineBasicBlock *InitialMBB,
+          MachineBasicBlock::const_reverse_instr_iterator InitialI) {
+  SmallVector<std::pair<const MachineBasicBlock *, StateT>> Worklist;
+  DenseSet<std::pair<const MachineBasicBlock *, unsigned>> Visited;
+  const MachineBasicBlock *MBB = InitialMBB;
+  StateT State = InitialState;
+  auto I = InitialI;
+
+  for (;;) {
+    bool Expired = false;
+    for (auto E = MBB->instr_rend(); I != E; ++I) {
+      // No need to look at parent BUNDLE instructions.
+      if (I->isBundle())
+        continue;
 
-    switch (IsHazard(State, *I)) {
-    case HazardFound:
-      return true;
-    case HazardExpired:
-      return false;
-    default:
-      // Continue search
-      break;
-    }
+      auto Result = IsHazard(State, *I);
+      if (Result == HazardFound)
+        return true;
+      if (Result == HazardExpired) {
+        Expired = true;
+        break;
+      }
 
-    if (I->isInlineAsm() || I->isMetaInstruction())
-      continue;
+      if (I->isInlineAsm() || I->isMetaInstruction())
+        continue;
 
-    UpdateState(State, *I);
-  }
+      UpdateState(State, *I);
+    }
 
-  for (MachineBasicBlock *Pred : MBB->predecessors()) {
-    if (!Visited.insert(Pred).second)
-      continue;
+    if (!Expired) {
+      unsigned StateHash = State.getHashValue();
+      for (MachineBasicBlock *Pred : MBB->predecessors()) {
+        if (!Visited.insert(std::pair(Pred, StateHash)).second)
+          continue;
+        Worklist.emplace_back(Pred, State);
+      }
+    }
 
-    if (hasHazard(State, IsHazard, UpdateState, Pred, Pred->instr_rbegin(),
-                  Visited))
-      return true;
+    if (Worklist.empty())
+      break;
+
+    std::tie(MBB, State) = Worklist.pop_back_val();
+    I = MBB->instr_rbegin();
   }
 
   return false;
@@ -1624,6 +1637,10 @@ bool GCNHazardRecognizer::fixVALUPartialForwardingHazard(MachineInstr *MI) {
     SmallDenseMap<Register, int, 4> DefPos;
     int ExecPos = std::numeric_limits<int>::max();
     int VALUs = 0;
+
+    unsigned getHashValue() const {
+      return hash_combine(ExecPos, VALUs, hash_combine_range(DefPos));
+    }
   };
 
   StateType State;
@@ -1718,9 +1735,8 @@ bool GCNHazardRecognizer::fixVALUPartialForwardingHazard(MachineInstr *MI) {
       State.VALUs += 1;
   };
 
-  DenseSet<const MachineBasicBlock *> Visited;
   if (!hasHazard<StateType>(State, IsHazardFn, UpdateStateFn, MI->getParent(),
-                            std::next(MI->getReverseIterator()), Visited))
+                            std::next(MI->getReverseIterator())))
     return false;
 
   BuildMI(*MI->getParent(), MI, MI->getDebugLoc(),
@@ -1761,6 +1777,8 @@ bool GCNHazardRecognizer::fixVALUTransUseHazard(MachineInstr *MI) {
   struct StateType {
     int VALUs = 0;
     int TRANS = 0;
+
+    unsigned getHashValue() const { return hash_combine(VALUs, TRANS); }
   };
 
   StateType State;
@@ -1796,9 +1814,8 @@ bool GCNHazardRecognizer::fixVALUTransUseHazard(MachineInstr *MI) {
       State.TRANS += 1;
   };
 
-  DenseSet<const MachineBasicBlock *> Visited;
   if (!hasHazard<StateType>(State, IsHazardFn, UpdateStateFn, MI->getParent(),
-                            std::next(MI->getReverseIterator()), Visited))
+                            std::next(MI->getReverseIterator())))
     return false;
 
   // Hazard is observed - insert a wait on va_dst counter to ensure hazard is

jayfoad · 2025-05-07T12:17:36Z

llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp

+    if (!Expired) {
+      unsigned StateHash = State.getHashValue();
+      for (MachineBasicBlock *Pred : MBB->predecessors()) {
+        if (!Visited.insert(std::pair(Pred, StateHash)).second)


This isn't safe in the presence of hash collisions.

As an alternative, could StateT have a "merge" or "min" function which takes two states and chooses the most constrained one, or the most contraining combination of them? Then if we reach the same predecessor twice by different paths we can merge the states and continue with the merged state.

Then perhaps the worklist could be a MapVector<const MachineBasicBlock *, StateT> with no need for a separate Visited set.

I wrote this on the basis that is safer than current solution that never revisits a predecessor.

I had considered a solution similar to the one you propose.
But had performance concerns.

I'll work it through and test performance, but I do think we should consider a partial solution such as the one thing patch.

I thought about this more and I concluded a merge or min state is not viable.
The min state would have to be "unsafer" of the two, which could create convergence problems.
Merging states would lead to visiting blocks with synthetic states that don't actually exist.
For some hazards it might not be possible to derive a merged state or determine the least safe state.

I have reworked the implementation to address hash collisions.
This now keeps a deduplicated vector or states, which is the only place states are retained.
Worklist and visited set retain indexes into this vector which are constant and unique for execution of the search.
Hashing is used to map states to vector indexes with a slow path provided for collisions.
(I have seen no collisions in my in depth testing.)

I thought about this more and I concluded a merge or min state is not viable.
The min state would have to be "unsafer" of the two, which could create convergence problems.
Merging states would lead to visiting blocks with synthetic states that don't actually exist.
For some hazards it might not be possible to derive a merged state or determine the least safe state.

I disagree with your conclusions, but I guess your way is OK for now, since you've implemented it. Just to be clear: the tradeoff you're making here is that you will potentially revisit the same MBB multiple times with different states, corresponding to different paths back through the CFG that can reach that block (even in the absence of loops).

perlfu · 2025-05-22T01:09:20Z

Ping

perlfu · 2025-06-02T08:10:44Z

Ping

perlfu · 2025-06-30T05:15:10Z

Ping

perlfu · 2025-07-16T08:03:43Z

Can anyone take another look at this?
I'd like to land this and #138663

Remove recursion to avoid stack overflow on large CFGs. Avoid worklist for hazard search within single MachineBasicBlock. Ensure predecessors are visited for all state combinations.

- Handle hashing collisions

rovka

This looks fine to me with a couple readability nits, but please wait a few days in case Jay wants to have another look.

rovka · 2025-09-04T08:44:21Z

llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp

+          MachineBasicBlock::const_reverse_instr_iterator InitialI) {
+  SmallVector<std::pair<const MachineBasicBlock *, unsigned>> Worklist;
+  SmallDenseSet<std::pair<const MachineBasicBlock *, unsigned>> Visited;
+  SmallVector<std::pair<unsigned, unsigned>, 1> Collisions;


Nit: Maybe typedef a HashTy and IdxTy, to make all these definitions easier to grok.

rovka · 2025-09-04T08:45:51Z

llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp

+      StateIdx = StateHash2Idx[StateHash];
+      if (LLVM_UNLIKELY(!StateT::isEqual(State, States[StateIdx]))) {
+        // Hash collision
+        auto Collision = llvm::find_if(Collisions, [&](auto &C) {


If you're doing the previous nit, also spell out the type of C here (The other auto can stay).

jayfoad

I think the behaviour you've imlemented is OK but I'd really like to see the implementation cleaned up as mentioned inline.

jayfoad · 2025-09-04T10:45:40Z

llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp

          function_ref<HazardFnResult(StateT &, const MachineInstr &)> IsHazard,
          function_ref<void(StateT &, const MachineInstr &)> UpdateState,


Not something to address in the current patch, but I think this IsHazard/UpdateState interface is confusing because IsHazard also updates the state. So technically I think there is no need for the separate UpdateState function, it could just become part of what IsHazard does before returning NoHazardFound.

jayfoad · 2025-09-04T10:49:18Z

llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp

+  SmallDenseMap<unsigned, unsigned> StateHash2Idx;
+  SmallVector<StateT> States;
+
+  // States contains a vector of unique state structures.


This feels overcomplicated and it's also similar to what MapVector does internally. I think you could probably reimplement this with a MapVector<StateT, void>, using MapVector::getArrayRef to convert between states and StateIdxs. This would have the (I claim) benefit that StateT would have to support standard DenseMap traits instead of the less standard getHashValue and isEqual methods.

Stepping back a bit, why do you want this level of indirection in the first place? Is it "just" a performance thing, to avoid copying around states which could be large, and avoid storing multiple copies of identical states? The MapVector solution would still store two copies of each state, since MapVector has a SmallVector of keys+values as well as a DenseMap of the keys.

Another possibility might be to have a DenseMap of pointers to states hashed by the state itself not the pointer value, a bit like this does for MachineInstrs: **

llvm-project/llvm/include/llvm/CodeGen/MachineInstr.h

Line 2086 in 8f37668

/// Special DenseMapInfo traits to compare MachineInstr* by *value* of the

jayfoad · 2025-09-04T10:51:04Z

llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp

+        if (!Visited.insert(std::pair(Pred, StateIdx)).second)
+          continue;
+        Worklist.emplace_back(Pred, StateIdx);


Instead of having separate Visited and Worklist, you could implement this with a single SetVector Worklist which you iterate through with a loop that keeps going while new items are inserted, like for (unsigned I = 0; I < Worklist.size(); ++I).

jayfoad · 2025-09-04T10:55:11Z

llvm/lib/Target/AMDGPU/GCNHazardRecognizer.cpp

+    if (!Expired) {
+      unsigned StateHash = State.getHashValue();
+      for (MachineBasicBlock *Pred : MBB->predecessors()) {
+        if (!Visited.insert(std::pair(Pred, StateHash)).second)


I thought about this more and I concluded a merge or min state is not viable.
The min state would have to be "unsafer" of the two, which could create convergence problems.
Merging states would lead to visiting blocks with synthetic states that don't actually exist.
For some hazards it might not be possible to derive a merged state or determine the least safe state.

I disagree with your conclusions, but I guess your way is OK for now, since you've implemented it. Just to be clear: the tradeoff you're making here is that you will potentially revisit the same MBB multiple times with different states, corresponding to different paths back through the CFG that can reach that block (even in the absence of loops).

perlfu requested review from jayfoad and rampitec May 7, 2025 10:22

llvmbot added the backend:AMDGPU label May 7, 2025

jayfoad reviewed May 7, 2025

View reviewed changes

perlfu mentioned this pull request May 22, 2025

[AMDGPU] Rework GFX11 VALU Mask Write Hazard #138663

Open

perlfu requested review from piotrAMD and arsenm June 16, 2025 01:16

perlfu force-pushed the amdgpu-has-hazard-rework branch from c8c36ab to 4d6dded Compare July 15, 2025 10:39

perlfu added 3 commits September 4, 2025 14:18

[AMDGPU] Refine GCNHazardRecognizer hasHazard()

0230c8e

Remove recursion to avoid stack overflow on large CFGs. Avoid worklist for hazard search within single MachineBasicBlock. Ensure predecessors are visited for all state combinations.

- Rework to use unified store of states

2a18fbe

- Handle hashing collisions

- Fix use of llvm::find_if

9532454

perlfu force-pushed the amdgpu-has-hazard-rework branch from 4d6dded to 9532454 Compare September 4, 2025 05:53

rovka approved these changes Sep 4, 2025

View reviewed changes

jayfoad reviewed Sep 4, 2025

View reviewed changes

		function_ref<HazardFnResult(StateT &, const MachineInstr &)> IsHazard,
		function_ref<void(StateT &, const MachineInstr &)> UpdateState,

[AMDGPU] Refine GCNHazardRecognizer hasHazard() #138841

Are you sure you want to change the base?

[AMDGPU] Refine GCNHazardRecognizer hasHazard() #138841

Conversation

perlfu commented May 7, 2025

Uh oh!

llvmbot commented May 7, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

perlfu commented May 22, 2025

Uh oh!

perlfu commented Jun 2, 2025

Uh oh!

perlfu commented Jun 30, 2025

Uh oh!

perlfu commented Jul 16, 2025

Uh oh!

rovka left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jayfoad left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!