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

Thu May 12 15:35:27 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 `this` and `target`. With the `options` string one can easily select which node types to traverse.
> 
> `void Node::print_bfs(const uint max_distance, Node* target, const char* options)`
> 
> 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 (this).
> 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 find_node(35)->print_bfs(2, 0, "cdmox+")
> No target: perform BFS.
> dis   par c dump
> ---------------------------------------------
>   0    35 d  35  CmpP  === _  34  25  [[ 36 ]] 
>   1    35 d  34  LoadP  === _  31  33  [[ 35 ]] 
>   1    35 d  25  ConP  ===  0  [[ 26  27  31  35  41 ]]  #NULL
>   2    34 m  31  StoreP  ===  20  27  29  25  [[ 23  34  41  42 ]]  
>   2    34 d  33  AddP  === _  1  12  32  [[ 34 ]] 
> 
> 
> Example with Mach nodes:
> 
> (rr) p ctrl->print_bfs(4, 0, "cdmox+OB")
> No target: perform BFS.
> dis [head  idom  d]   old   par c dump
> ---------------------------------------------
>   0   159   147   6     _   159 c  159  Region  ===  159  57  [[ 159  158  59 ]] 
>   1   147   148   5  o183   159 c  57  IfTrue  ===  8  [[ 159 ]] 
>   2   147   148   5  o182    57 c  8  jmpConU  ===  147  9  [[ 7  57 ]] 
>   3   147   148   5     _     8 c  147  Region  ===  147  14  [[ 147  8 ]] 
>   3   147   148   5  o180     8 d  9  compUL_rReg  === _  10  13  [[ 8 ]] 
>   4   148   149   4  o174   147 c  14  IfTrue  ===  15  [[ 147 ]] 
>   4   147   148   5  o203     9 d  10  decL_rReg  === _  11  [[ 12  9 ]] 
>   4   147   148   5  o179     9 d  13  convI2L_reg_reg  === _  28  [[ 9 ]]
> 
> 
> **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.
> `loop_end->print_bfs(20, loop_head, "cox+")`
> This provides us with a shortest path, given this path has a distance of at most 20.
> 
> Example:
> 
> (rr) p find_node(158)->print_bfs(20, find_node(160), "cox+")
> Find shortest path: 158 -> 160.
> 
> Backtrace target.
> dis c dump
> ---------------------------------------------
>   9 c  160  OuterStripMinedLoop  ===  160  339  159  [[ 160  358 ]] 
>   8 c  358  CountedLoop  ===  358  160  143  [[ 358  362  363 ]] 
>   7 c  363  If  ===  358  351  [[ 364  367 ]] 
>   6 c  364  IfTrue  ===  363  [[ 128 ]] 
>   5 c  128  If  ===  364  127  [[ 129  130 ]]
>   4 c  129  IfTrue  ===  128  [[ 155 ]] 
>   3 c  155  CountedLoopEnd  ===  129  154  [[ 157  143 ]] [lt] 
>   2 c  157  IfFalse  ===  155  [[ 162  163 ]] 
>   1 c  162  SafePoint  ===  157  1  7  1  1  163  100  1  1  13  27  133  [[ 158 ]]
>   0 c  158  OuterStripMinedLoopEnd  ===  162  156  [[ 159  227 ]]
> 
> Example with Mach nodes:
> 
> (rr) p ctrl->print_bfs(10, val, "cdmox-+OB")
> Find shortest path: 159 -> 27.
> 
> Backtrace target.
> dis [head  idom  d]   old e c dump
> ---------------------------------------------
>   2    24     1   2   o10 + d  27  MachProj  ===  24  [[ 19  28  4  59  95  99  118 ]] 
>   1    56   159   7  o239 - d  59  loadB  ===  159  29  27  60  [[ 55 ]] 
>   0   159   147   6     _   c  159  Region  ===  159  57  [[ 159  158  59 ]]

Emanuel Peter has updated the pull request incrementally with one additional commit since the last revision:

  refactoring into class, no lambdas

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

Changes:
  - all: https://git.openjdk.java.net/jdk/pull/8468/files
  - new: https://git.openjdk.java.net/jdk/pull/8468/files/4b7e3b1d..d6d2666d

Webrevs:
 - full: https://webrevs.openjdk.java.net/?repo=jdk&pr=8468&range=06
 - incr: https://webrevs.openjdk.java.net/?repo=jdk&pr=8468&range=05-06

  Stats: 393 lines in 1 file changed: 163 ins; 141 del; 89 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