RFR: 8283775: VM support for graph querying in debugger with BFS traversal and node filtering

Mon May 2 07:07:21 UTC 2022

I implemented VM support for BFS traversal of IR nodes, where one can filter for input/output edges, and the node-type (control / data / memory). If one specifies the `target` node, we find a shortest path between `root` and `target`. With the `filter` string one can easily select which node types to traverse.

`void print_bfs(Node* root, const uint max_distance, Node* target, const char* filter)`

While a sufficient summary and description is in the comments above the function definition, I want to explain some useful use-cases here.

Please let me know if you would find this helpful, or if you have any feedback to improve it.
Thanks, Emanuel

**1. Better dump()**
The function is similar to `dump()`, we can also follow input / output edges up to a certain distance. There are a few improvements/added features:

1. Display the distance to the specified node. This way I can quickly assess how many nodes I have at a certain distance, and I can traverse edges from one distance to the next. The parent column shows the node one step closer to the BFS root.
2. Node filtering with types taken from `type->category()` help one limit traversal to control, data or memory flow. The categories are the same as in IGV.
3. Probably controversial: coloring of node types in terminal. By default it is off. May not work on all terminals. But I find it very useful to quickly separate memory, data and control - just as in IGV - but in my terminal!
4. After matching, we create Mach nodes from the IR nodes. For most Mach nodes, there is an associated old node. Often an assert is triggered for Mach nodes, but the graph already breaks in the IR graph. It is thus very helpful to have the old node idx displayed.
5. I also display the head node idx of the block a Mach node is scheduled for. This can be helpful if one gets bad dominance asserts, and needs to see why the blocks were scheduled in a bad way.

Example:

(rr) p print_bfs(find_node(7011), 2, 0, "cdmox+")
No target: perform BFS.
dis   par dir dump
-------------------------------------------
  0  7011 +d  7011  Bool  === _  7010  [[ 7012 ]] [gt] 
  1  7011 +d  7010  CmpI  === _  216  213  [[ 7011 ]] 
  2  7010 +d  216  AddI  === _  385  386  [[ 9066  7020  7010  385 ]] 
  2  7010 +d  213  Phi  ===  6987  378  6982  [[ 278  .... ]]

Example with Mach nodes:

(rr) p print_bfs(load, 2, 0, "cdmox+#OB")
No target: perform BFS.
dis  head  idom dep   old   par dir dump
-------------------------------------------
  0   314   315  18  o260   144 +d  144  loadF  ===  314  136  143  [[ 138  270 ]]
  1   314   315  18     _   144 +c  314  Region  ===  314  97  [[ 314  95  144 ]] 
  1   316   317  16  o305   144 +m  136  MachProj  ===  105  [[ 135  137  143  144  139  145  190  221  240  258 ]]
  1   316   317  16  o285   144 +d  143  loadN  === _  136  69  [[ 137  144  103  100  202 ]]
  2   315   316  17  o311   314 +c  97  IfTrue  ===  98  [[ 314 ]]
  2   316   317  16  o306   136 +x  105  membar_acquire  ===  316  0  147  0  0  [[ 136  104 ]]
  2    49     1   2   o10   143 +d  69  MachProj  ===  49  [[ 67  132  134  143  145  146  151  169  50  4  247 ]]

**2. Find loop body**
When I find myself in a loop, I try to localize the loop head and end, and map out at least one path between them.
`print_bfs(loop_end, 20, loop_head, "cox+")`
This provides us with a shortest path, given this path has a distance of at most 20.

Example:

(rr) p print_bfs(find_node(357), 30, find_node(587), "cox+")
Find shortest path: 357 -> 587.

Backtrace target.
disdir dump
-------------------------------------
 21 +c  587  CountedLoop  ===  587  361  121  [[ 587  589  603  604 ]]
 20 +x  589  MemBarAcquire  ===  587  1  603  1  1  [[ 588  590 ]] 
 19 +c  590  Proj  ===  589  [[ 591 ]] 
 18 +c  591  If  ===  590  574  [[ 592  605 ]]
 17 +c  592  IfTrue  ===  591  [[ 576  593 ]]
 16 +c  593  RangeCheck  ===  592  566  [[ 594  607 ]]
...
  2 +c  296  RangeCheck  ===  295  272  [[ 299  316 ]]
  1 +c  299  IfTrue  ===  296  [[ 258  265  357 ]]
  0   c  357  CountedLoopEnd  ===  299  356  [[ 358  121 ]] [lt]

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

Commit messages:
 - some white spaces fixed
 - fixing up root in shortest path backtracking
 - 8283775: VM support for graph querying in debugger with BFS traversal and node filtering

Changes: https://git.openjdk.java.net/jdk/pull/8468/files
 Webrev: https://webrevs.openjdk.java.net/?repo=jdk&pr=8468&range=00
  Issue: https://bugs.openjdk.java.net/browse/JDK-8283775
  Stats: 295 lines in 1 file changed: 295 ins; 0 del; 0 mod
  Patch: https://git.openjdk.java.net/jdk/pull/8468.diff
  Fetch: git fetch https://git.openjdk.java.net/jdk pull/8468/head:pull/8468

PR: https://git.openjdk.java.net/jdk/pull/8468