RFR: 8282547: IGV: add control-flow graph view
Christian Hagedorn
chagedorn at openjdk.java.net
Thu Mar 17 12:55:43 UTC 2022
On Tue, 15 Mar 2022 11:36:21 GMT, Roberto Castañeda Lozano <rcastanedalo at openjdk.org> wrote:
> This change adds a new view to the Ideal Graph Visualizer showing a classic control-flow graph (CFG) where nodes are serialized within basic blocks and arcs across basic blocks represent control flow:
>
> 
>
> The CFG provides a higher-level, more compact view of the graph than the existing views, where it can be hard to see the overall structure for all but the smallest graphs:
>
> 
>
> 
>
> If a schedule is available in the input graph (because it corresponds to the _Global code motion_ phase or later), the CFG, including the serialization of nodes within basic blocks, is derived from it. Otherwise, the CFG is approximated by the C2-specific `ServerCompilerScheduler` class. Dependencies among nodes are shown textually, by extending the label of each node with a list of its inputs:
>
> <p align="center">
> <img width="35%" src="https://user-images.githubusercontent.com/8792647/158367428-5aa222e9-6a5c-4e78-871f-853e5b918599.png">
> </p>
>
> The exact information shown about each input can be configured in Tools -> Options -> Tiny Node Text.
>
> The new CFG view is available at the same level as the existing "sea of nodes" (default) and "clustered sea-of-nodes" views. The view can be selected from the main toolbar:
>
> 
>
> The default view shown when opening a new graph can be configured in Tools -> Options -> Default View.
>
> The same functionality available for the existing views also applies to the new CFG:
>
> - node extraction:
>
> 
>
> - pop-up information on edges:
>
> 
>
> - filtering:
>
> 
>
> - quick node and basic block search:
>
> 
>
> - and exporting.
>
> The list of custom filters is extended with three new block-hiding filters:
>
> - `Hide root block`: remove root block and hide all back-edges from exiting blocks that clutter the CFG.
>
> - `Hide uncommon trap blocks`: remove blocks with uncommon traps to simplify following the "hot paths" in the CFG.
>
> - `Hide exception blocks`: remove blocks that create and throw exceptions to also simplify following the "hot paths" in the CFG.
>
> When using the CFG view, it is important to keep in mind that, in graphs corresponding to phases earlier than _Global code motion_, the presented CFG is just one of many possible projections of the sea-of-nodes representation, and that this projection is computed by an approximation of what C2 would do if it scheduled the graph at that stage. The approximation has some known limitations ([JDK-8280568](https://bugs.openjdk.java.net/browse/JDK-8280568), [JDK-8282053](https://bugs.openjdk.java.net/browse/JDK-8282053)). Future work should address these and warn the user when the approximated CFG is known to be inaccurate.
>
> ### Testing
>
> #### Functionality
>
> - Tested the above functionality manually on a small selection of graphs.
>
> - Tested automatically that scheduling (approximating C2's GCM and LCM algorithms) and viewing thousands of graphs in the three views does not trigger any assertion failure (by instrumenting IGV to schedule and view graphs as they are loaded and running `java -Xcomp -XX:-TieredCompilation -XX:PrintIdealGraphLevel=4`).
>
> #### Performance
>
> - Measured the scheduling and view creation time for each of the three views on a selection of 22 large graphs (between 2515 and 7329 nodes). On average:
>
> - The change introduces a slight overhead when creating the existing views (2% and 5% for the clustered and non-clustered sea-of-nodes views). This overhead is due to the introduction of abstractions and data structures required by the CFG view.
>
> - The new CFG view is considerably faster to create than the existing ones (4.2x and 2.5x faster than the clustered and non-clustered sea-of-nodes views), as it can be expected, since only basic blocks have to be laid out. Furthermore, the CFG view scales better as the size of the graph increases.
>
> - The change slows down scheduling by 27%. This overhead corresponds to the additional work of approximating C2's LCM, and it is essential for the CFG view. Fortunately, scheduling takes only a fraction of the time needed to create a view (typically no more than a third), and it only needs to run once for each graph, whereas views have to be re-created on node extraction, filtering, etc.
>
> The performance results are [attached](https://github.com/openjdk/jdk/files/8252786/performance-evaluation.ods) (note that each measurement in the sheet corresponds to the median of ten runs).
Great work Roberto! This looks very nice. I've tried it out and it worked well. The only thing I've noticed in the compact CFG view: When extracting a node, it shows all the empty blocks of the entire graph. I would have expected that empty blocks that are neither in- nor outputs of the extracted node are hidden. But I think that could also be potentially handled in a separate RFE and should not block this change.
My review comments are mostly just about code styling and the like since I'm not very familiar with the IGV code which made it hard to review - I trust your expertise in that area :-)
Thanks,
Christian
src/utils/IdealGraphVisualizer/Data/src/main/java/com/sun/hotspot/igv/data/InputGraph.java line 66:
> 64: public InputBlockEdge addBlockEdge(InputBlock left, InputBlock right, String label) {
> 65: InputBlockEdge edge = new InputBlockEdge(left, right);
> 66: edge.setLabel(label);
As you only use `setLabel()` here, you could also directly pass it into the `InputBlockEdge()` constructor.
src/utils/IdealGraphVisualizer/Data/src/main/java/com/sun/hotspot/igv/data/InputGraph.java line 177:
> 175: if (!scheduledNodes.contains(n)) {
> 176: if (noBlock == null) {
> 177: noBlock = this.addArtificialBlock();
`this` can be removed.
src/utils/IdealGraphVisualizer/Filter/src/main/java/com/sun/hotspot/igv/filter/RemoveBlockFilter.java line 37:
> 35:
> 36: private List<RemoveBlockRule> rules;
> 37: private String name;
Both can be made `final`.
src/utils/IdealGraphVisualizer/Filter/src/main/java/com/sun/hotspot/igv/filter/RemoveBlockFilter.java line 64:
> 62: public static class RemoveBlockRule {
> 63:
> 64: private BlockSelector selector;
Can also be made `final`.
src/utils/IdealGraphVisualizer/Graal/src/main/java/com/sun/hotspot/igv/graal/filters/GraalEdgeColorFilter.java line 63:
> 61: String type = null;
> 62:
> 63: if (type != null) {
This block is dead since `type` is `null`. Is this intended?
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/AnySelector.java line 32:
> 30: public class AnySelector implements BlockSelector {
> 31:
> 32: private Selector selector;
Can be made `final`.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/BlockConnection.java line 39:
> 37:
> 38: private Block sourceBlock;
> 39: private Block destinationBlock;
Can be made `final`.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/BlockConnection.java line 71:
> 69: public String getLabel() {
> 70: return label;
> 71: }
Appears to be unused and can be removed.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/BlockConnection.java line 77:
> 75: StringBuilder builder = new StringBuilder();
> 76: builder.append("B" + sourceBlock.getInputBlock().getName() + " → " +
> 77: "B" + destinationBlock.getInputBlock().getName());
Could be replaced by `append()` calls:
Suggestion:
builder.append("B").append(sourceBlock.getInputBlock().getName())
.append(" → B").append(destinationBlock.getInputBlock().getName());
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Connection.java line 38:
> 36: }
> 37:
> 38: public ConnectionStyle getStyle();
`public` is implied for interface methods and does not need to be stated explicitly.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Diagram.java line 55:
> 53: // Whether widgets derived from this diagram should be adapted for the
> 54: // control-flow graph view.
> 55: private boolean cfg = false;
This assignment can be removed as you initialize it in the constructor.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Diagram.java line 56:
> 54: // control-flow graph view.
> 55: private boolean cfg = false;
> 56: private Set<BlockConnection> blockConnections;
Can be made `final`.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Diagram.java line 119:
> 117: }
> 118:
> 119: public Diagram getNext() {
Appears to be unused?
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Diagram.java line 127:
> 125: }
> 126:
> 127: public Diagram getPrev() {
Appears to be unused?
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Diagram.java line 175:
> 173: d.nodeText = nodeText;
> 174: d.shortNodeText = shortNodeText;
> 175: d.tinyNodeText = tinyNodeText;
Could be passed as arguments to the constructor.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Diagram.java line 226:
> 224: BlockConnection c = new BlockConnection(p, s, e.getLabel());
> 225: c.setStyle(Connection.ConnectionStyle.BOLD);
> 226: c.setColor(Color.BLUE);
These settings are only set here and could thus also be moved directly into the `BlockConnection()` constructor.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Diagram.java line 296:
> 294:
> 295: public Set<FigureConnection> getConnections() {
> 296:
New line can be removed
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Diagram.java line 299:
> 297: Set<FigureConnection> connections = new HashSet<>();
> 298: for (Figure f : figures) {
> 299:
New line can be removed
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/Figure.java line 74:
> 72: Graphics g = image.getGraphics();
> 73: g.setFont(diagram.getFont().deriveFont(Font.BOLD));
> 74: FontMetrics metrics = g.getFontMetrics();
Do you really need to create a fake image just to get the font metrics?
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/FigureConnection.java line 2:
> 1: /*
> 2: * Copyright (c) 2008, 2022, Oracle and/or its affiliates. All rights reserved.
Should only be 2022 for a new file.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/FigureConnection.java line 35:
> 33: /**
> 34: *
> 35: * @author Thomas Wuerthinger
You should take credit of this class instead ;-)
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/FigureConnection.java line 42:
> 40: public boolean isVIP() {
> 41: return style == ConnectionStyle.BOLD;
> 42: }
Should be moved down to the other methods.
src/utils/IdealGraphVisualizer/Graph/src/main/java/com/sun/hotspot/igv/graph/FigureConnection.java line 44:
> 42: }
> 43: private InputSlot inputSlot;
> 44: private OutputSlot outputSlot;
Can be made `final`.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalCFGLayoutManager.java line 43:
> 41: private FontMetrics fontMetrics;
> 42: private LayoutManager subManager;
> 43: private LayoutManager manager;
You might want to add a comment what each of these managers do or why you need a sub manager as well.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalCFGLayoutManager.java line 85:
> 83: cn.setBorder(BLOCK_BORDER);
> 84: cn.setHeaderVerticalSpace(fontMetrics.getHeight());
> 85: cn.setNodeOffset(c.getNodeOffset());
Could be combined to a second constructor in `ClusterNode` instead of using separate `set()` methods.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalCFGLayoutManager.java line 86:
> 84: cn.setHeaderVerticalSpace(fontMetrics.getHeight());
> 85: cn.setNodeOffset(c.getNodeOffset());
> 86: String blockLabel = "B" + c.toString();
`toString()` is implicit and can be removed.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalCFGLayoutManager.java line 139:
> 137: Link l = inputLink.get(new AbstractMap.SimpleEntry<Cluster, Cluster>(ce.getFromCluster(), ce.getToCluster()));
> 138: l.setControlPoints(ce.getControlPoints());
> 139: }
Refactor suggestion:
All the code blocks with a comment could be extracted to separate methods with method names matching the comments accordingly.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalCFGLayoutManager.java line 143:
> 141:
> 142: public void doRouting(LayoutGraph graph) {
> 143: }
All the `doRouting()` methods do nothing. These could be removed together with the interface declaration.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalLayoutManager.java line 228:
> 226: new BuildDatastructure().start();
> 227:
> 228: if (!layoutSelfEdges) {
This block could be extracted to a separate method.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/HierarchicalLayoutManager.java line 260:
> 258:
> 259: // Hide self-edges from the core layout algorithm.
> 260: for (LayoutNode node : nodes) {
This block could also be extracted to a separate method.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/LinearLayoutManager.java line 36:
> 34:
> 35: // Ranking determining the vertical node ordering.
> 36: private Map<? extends Vertex, Integer> vertexRank;
Can be made `final`.
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/LinearLayoutManager.java line 56:
> 54: vertices.sort((Vertex a, Vertex b) ->
> 55: Integer.compare(vertexRank.getOrDefault(a, Integer.MAX_VALUE),
> 56: vertexRank.getOrDefault(b, Integer.MAX_VALUE)));
Could be simplified to:
Suggestion:
vertices.sort(Comparator.comparingInt((Vertex a) -> vertexRank.getOrDefault(a, Integer.MAX_VALUE)));
src/utils/IdealGraphVisualizer/HierarchicalLayout/src/main/java/com/sun/hotspot/igv/hierarchicallayout/LinearLayoutManager.java line 63:
> 61: v.setPosition(new Point(0, curY));
> 62: curY += v.getSize().getHeight();
> 63: }
Could be extracted to a separate `assignVerticalCoordinates()` method.
src/utils/IdealGraphVisualizer/Layout/src/main/java/com/sun/hotspot/igv/layout/LayoutGraph.java line 55:
> 53: for (Link l : links) {
> 54: if (l.getFrom() == null || l.getTo() == null)
> 55: continue;
Missing braces
src/utils/IdealGraphVisualizer/Layout/src/main/java/com/sun/hotspot/igv/layout/Link.java line 37:
> 35: public Port getFrom();
> 36:
> 37: public Cluster getFromCluster();
`public` can be removed for interface methods.
src/utils/IdealGraphVisualizer/ServerCompiler/src/main/java/com/sun/hotspot/igv/servercompiler/ServerCompilerScheduler.java line 127:
> 125: // Ensure that the block ordering is deterministic.
> 126: Collections.sort(nControlSuccs, (Node a, Node b) ->
> 127: Integer.compare(a.inputNode.getId(), b.inputNode.getId()));
Could be simplified to:
Suggestion:
nControlSuccs.sort(Comparator.comparingInt((Node a) -> a.inputNode.getId()));
src/utils/IdealGraphVisualizer/ServerCompiler/src/main/java/com/sun/hotspot/igv/servercompiler/ServerCompilerScheduler.java line 570:
> 568: }
> 569:
> 570: private static boolean isRegion(Node n) {
Is unused and can be removed.
src/utils/IdealGraphVisualizer/ServerCompiler/src/main/java/com/sun/hotspot/igv/servercompiler/ServerCompilerScheduler.java line 575:
> 573:
> 574: private static boolean isOtherBlockStart(Node n) {
> 575: return n.inputNode.getProperties().get("name").equals("CountedLoopEnd");
This pattern is used several times. How about replacing these by a new method something like that:
private static boolean isOtherBlockStart(Node n) {
return isNodeWithName(n, "CountedLoopEnd");
}
private static boolean isNodeWithName(Node node, String nodeName) {
return node.inputNode.getProperties().get("name").equals(nodeName);
}
src/utils/IdealGraphVisualizer/ServerCompiler/src/main/resources/com/sun/hotspot/igv/servercompiler/filters/hideExceptionBlocks.filter line 4:
> 2:
> 3: var f = new RemoveBlockFilter("Hide exception blocks");
> 4: f.addRule(
Could the rule object directly be passed to the constructor instead of going over `addRule()`? On top of that, all filters follow the pattern "create f + `f.apply(graph)`". This could be moved into a single method to simplify filters. But this would exceed the scope of this change and could be done in a separate RFE.
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/BlockQuickSearch.java line 91:
> 89: if (!response.addResult(new Runnable() {
> 90: @Override
> 91: public void run() {
Could be replaced by lambda:
if (!response.addResult(() -> {
final EditorTopComponent comp = EditorTopComponent.getActive();
....
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/BlockQuickSearch.java line 122:
> 120: response.addResult(new Runnable() {
> 121: @Override
> 122: public void run() {
Can be replaced by lambda.
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/DiagramScene.java line 649:
> 647: m.setSubManager(new HierarchicalLayoutManager(HierarchicalLayoutManager.Combine.SAME_OUTPUTS));
> 648: m.doLayout(new LayoutGraph(edges, figures));
> 649: } else if (getModel().getShowCFG()) {
Code code be put into separate `doCFGLayout()` method or something like that. Also, you can directly use `model` instead of `getModel()`.
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/NodeQuickSearch.java line 33:
> 31: import com.sun.hotspot.igv.settings.Settings;
> 32: import com.sun.hotspot.igv.util.LookupHistory;
> 33: import com.sun.hotspot.igv.util.StringUtils;
Copyright of this file should be updated (I somehow cannot comment on non-shown lines)
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/actions/EnableBlockLayoutAction.java line 2:
> 1: /*
> 2: * Copyright (c) 2008, 2021, Oracle and/or its affiliates. All rights reserved.
Should be 2022.
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/actions/EnableSeaLayoutAction.java line 34:
> 32: public class EnableSeaLayoutAction extends AbstractAction {
> 33:
> 34: private boolean state;
Seems to be unused and can be removed.
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/actions/EnableSeaLayoutAction.java line 46:
> 44: }
> 45:
> 46: public void setSelected(boolean b) {
I might be missing something but this method seems to be unused as well.
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/widgets/BlockWidget.java line 46:
> 44: public static final int BORDER = 20;
> 45: public static final Color BACKGROUND_COLOR = new Color(235, 235, 255);
> 46: private static final Font titleFont = new Font("Arial", Font.BOLD, 14);
Should be in upper case: `TITLE_FONT`
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/widgets/InputSlotWidget.java line 44:
> 42: inputSlot = slot;
> 43: //init();
> 44: //getFigureWidget().getLeftWidget().addChild(this);
Can also be removed?
src/utils/IdealGraphVisualizer/View/src/main/java/com/sun/hotspot/igv/view/widgets/SlotWidget.java line 72:
> 70: this.setPreferredLocation(p);
> 71:
> 72: //this.setPreferredBounds(this.calculateClientArea());
Can be removed?
-------------
Changes requested by chagedorn (Reviewer).
PR: https://git.openjdk.java.net/jdk/pull/7817
More information about the hotspot-compiler-dev
mailing list