RFR: 8282547: IGV: add control-flow graph view [v2]
Roberto Castañeda Lozano
rcastanedalo at openjdk.java.net
Wed Mar 23 09:26:31 UTC 2022
On Wed, 23 Mar 2022 08:20:57 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).
>
> Roberto Castañeda Lozano has updated the pull request incrementally with one additional commit since the last revision:
>
> Refactor code as suggested by Christian
Thanks Christian for reviewing and providing so many suggestions! I have implemented all of them except a few for which I have provided separate answers.
> 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.
This is actually deliberate, I thought it would be useful to preserve the control-flow context, so that the user can at all times know e.g. whether a block she is looking at is within a loop. Having said that, I agree that sometimes, particularly for large graphs, it would be useful to hide the empty blocks. This behavior would also be more consistent with the clustered sea-of-nodes view. Would it make sense to add a toolbar button to hide/show empty blocks in the control-flow graph view? If you think so, I will create a RFE to do that separately.
-------------
PR: https://git.openjdk.java.net/jdk/pull/7817
More information about the hotspot-compiler-dev
mailing list