RFR: 8309463: IGV: Dynamic graph layout algorithm

[Tobias Holenstein]

On Wed, 7 Jun 2023 08:33:12 GMT, emmyyin <duke at openjdk.org> wrote:

> ### Purpose
> 
> IGV currently uses a static layout algorithm to visualize graphs. However, this is problematic due to the use cases of IGV. Most often, the graphs that are visualized are dynamic, meaning the graphs change over time. A dynamic graph can be thought of as a sequence of graphs where a given graph in the sequence is the state of the dynamic graph at that point in time. Static layout algorithms do not account for the rest of the sequence when visualizing a given graph. On one hand, it makes each layout more readable. But on the other hand, the layout for two consecutive graphs in the sequence can be vastly different even though the difference between the graphs is small. This makes it difficult to identify the changes that has occurred to the graph and can damage the internal understanding of the graph that the viewer has obtained. A dynamic layout algorithm takes the changes into account when visualizing a graph. To enhance IGV, such an algorithm has been implemented in this PR.
> 
> The layout drawn by the static layout algorithm is called "sea of nodes", while the layout drawn by the dynamic algorithm is called "stable sea of nodes".
> 
> The difference between the algorithms is illustrated in the following video:
> 
> 
> https://github.com/openjdk/jdk/assets/52547536/35023362-a191-425e-b066-c7474db631f1
> 
> 
> This work is the result of my Master's thesis which can be found [here](https://kth.diva-portal.org/smash/get/diva2:1770643/FULLTEXT01.pdf).
> 
> 
> ### Implementation
> 
> The algorithm is based on update actions that are applied incrementally to a graph layout in order to obtain the layout of the next graph in the sequence. By doing so, the nodes that appears in both graphs remain in their relative positions. A new layout manager called `HierarchicalStableLayoutManager` has been added which holds the core algorithm. The corresponding layout manager with the static layout algorithm is called `HierarchicalLayoutManager`.
> 
> If no layouts have been drawn yet, the `HierarchicalLayoutManager` is used. This is because the dynamic algorithm needs an initial layout to apply the update actions on.
> 
> The whole graph is represented by `LayoutNode` and `LayoutEdge` objects, that holds the positions of the nodes and edges along with other relevant information such as ID, name and size. These are updated, added and removed in accordance with the update actions.
> 
> Since `HierarchicalStableLayoutManager` tries to preserve the node positions, the layouts might get unreadable after a fe...

A few tips and comments:
- Remove TODOs, unused code (commented out) and personal comments
- Adjust copyright year of all touched files to 2023
- Add comments to important and/or complex parts of your code
- Can we somehow separate the evaluation from the layout algorithm?
   - Either in separate files or at least disable evaluation by default with a flag
- Do we want to keep the shortcuts?
   - Perhaps keep `LayoutAction1` for relayout with static layout algorithm
   - rename `LayoutAction1`  and give it a better shortcut
- ideally leave `HierarchicalLayoutManager.java` untouched or at least make sure other parts of IGV work as before
- rename `new_layout.png` , `NewLayoutManager.java` and `EnableNewLayoutAction.java`
- make sure to document in the PR description what changed other than the new layout algorithm   
   - e.g. what changed in the settings (`ANIMATION_LIMIT`) 
   - what changed in `ServerCompilerScheduler.java`

src/utils/IdealGraphVisualizer/ControlFlow/src/main/java/com/sun/hotspot/igv/controlflow/HierarchicalGraphLayout.java line 164:

> 162: 
> 163:         LayoutGraph layoutGraph = new LayoutGraph(links, vertices);
> 164:         m.doLayout(layoutGraph);

should be uncommented

src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalLayoutManager.java line 1463:

> 1461:                 boolean hasReversedDown =
> 1462:                     reversedDown.size() > 0 &&
> 1463:                     !(reversedDown.size() == 1 && hasSelfEdge);

Please avoid style changes to code that you did not touch otherwise (sometimes the IDE does this automatically)

src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/DiagramScene.java line 1221:

> 1219:         HashSet<Connection> visibleConnections = getVisibleConnections();
> 1220: 
> 1221:         String key = getModel().getGraph().getGroup().getName() + "::" + getModel().getGraph().getName();

What is the purpose of this? Is it needed?

src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/DiagramViewModel.java line 369:

> 367:             Scheduler s = Lookup.getDefault().lookup(Scheduler.class);
> 368:             graph.clearBlocks();
> 369:             s.schedule(graph);

was this commented out on purpose? If yes, we can remove the code

-------------

PR Comment: https://git.openjdk.org/jdk/pull/14349#issuecomment-1580239463
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1221161139
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1221210767
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1221216343
PR Review Comment: https://git.openjdk.org/jdk/pull/14349#discussion_r1221218395