Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8344957

C2: Add dedicated classes to do BFS traversals on C2 nodes

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Unresolved
    • Icon: P4 P4
    • tbd
    • 24
    • hotspot

      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.

            chagedorn Christian Hagedorn
            chagedorn Christian Hagedorn
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated: