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 forJDK-8344213 where we added yet another BFS walk.
Thanks to [~epeter] for the brainstorming for coming up with the design draft.
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
Thanks to [~epeter] for the brainstorming for coming up with the design draft.
- relates to
-
JDK-8344213 Cleanup OpaqueLoop*Node verification code for Assertion Predicates
- Resolved