JDK-8344957 : C2: Add dedicated classes to do BFS traversals on C2 nodes
  • Type: Enhancement
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 24
  • Priority: P4
  • Status: Open
  • Resolution: Unresolved
  • Submitted: 2024-11-25
  • Updated: 2024-11-25
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
Other
tbdUnresolved
Related Reports
Relates :  
Description
This RFE aims at providing a simple way to do customizable BFS traversals on C2 nodes. This should be achieved by a generic NodeBFSTraversal class that takes two strategy interfaces:

1. NodeTraversalStrategy: This interface defines for each visited node during the BFS traversal whether a neighbor should be further visited. The key for the implementing classes is to filter as fundamental as possible. For example, should we visit inputs or outputs or both? Should we visit CFG or data nodes or both?
These strategy classes should be pre-defined.
2. NodeVisitStrategy: This interface defines for each input of a visited node during the BFS traversal whether it should be further visited. The key difference to the NodeTraversalStrategy is that a user of the BFS can define their own specific strategy.

The NodeBFSTraversal class should provide the following methods:
- run() // Runs the BFS with the provided strategies
- visited_nodes() // Return the visited nodes during the BFS
- add_start_node() // Allow to add multiple start nodes

We can find many instances in the current C2 code where we do some kind of BFS. For example:
- dump_bfs()/PrintBFS
- Assertion Predicates cloning

Mostly the code looks similar but there is always some tweak involved. Therefore, we want to provide a unified way to do BFS walks. The only thing a user needs to provide is a user-defined NodeTraversalStrategy. The mentioned examples could be used as a use case for the new unified BFS implementation.

This work is motivated by the PR for JDK-8344213 where we added yet another BFS walk.

Thanks to [~epeter] for the brainstorming for coming up with the design draft.