Alternative layout engine for CFGs

[OfekShilon]

Describe the bug

In the example below the block sw.epilog is needlessly aligned to the right. This is a rather common phenomena, and fixing it would make the graphs nicer.

Steps to reproduce

https://godbolt.org/z/ocTW1xxa4

Expected behavior

Centered CFG graphs, with as much of the flow as possible concentrated in a single view.

Reproduction link

https://godbolt.org/z/ocTW1xxa4

Screenshots

Operating System

No response

Browser version

No response

[OfekShilon]

Such layout is the result of pruning DAG edges into a tree, than recursively adjusting each block subtree to the right.
Looking in the GraphGridLayout doc this closely matches the 'Placing parent between direct children' approach (image rhs):

We can relatively easily switch to the more compact left approach ('parent in the middle of bounds') but frankly I'm not entirely happy with either.

==========================================
Here's one alternative: use the LLVM built-in CFG generation facility - LLVM can generate .dot text files and use graphviz for layout and rendering. For the same IR code above it generates -

Which I personally prefer. The layout is compact yet easy to follow, blocks that add in br/select have added info at the bottom (including outgoing arrows from the right label) and more. The edges can be customized to be more similar to the existing CFG by splines=ortho:

or splines=polyline (my personal preference):

One apparent downside is that backedges target the bottom of the dest-block and not its top. This is somewhat-solvable with the edge attribute [headport=n] but the result still isn't very nice:

To generate the .dot from IR you use opt:

$ opt -dot-cfg -disable-output -enable-new-pm=0 <your IR file.ll>

and see the results either offline -

$ dot -Tpng -otest.png <generagted file.dot>

or paste the .dot contents into http://magjac.com/graphviz-visual-editor/ or https://viz-js.com/ or similar.

=====================================================
To achieve the same in CE we would need to:

1. Run $ opt -dot-cfg in the server on the IR output file (admittedly, some more backend load)
2. Send the generated .dot string to the front end and use either viz.js, 3d-graphviz or similar engine to render. (I'm leaning towards viz.js but have no strong opinion).

My guess is the added backend burden isn't substantial, but this is a medium+ size project - so I really hope to collect some opinions before going there.

@jeremy-rifkin WDYT?

[OfekShilon]

For IR CFGs the opt can take us from IR to .dot. For assembly CFGs we'd still need the existing generateFunctionCfg and add a step of converting its result to a .dot string, eg with https://olado.github.io/doT/index.html.

[jeremy-rifkin]

@OfekShilon I think the solution here would be to do layout compacting, possibly in addition to placing the parent between children, as outlined in the cutter docs

This has been on the backlog and one of the big remaining things I've wanted to implement.

We could definitely have an option for a graphviz layout. Personally I haven't been a big fan of graphviz layouts for this type of thing because I don't think it handles edges well. For example, edges coming out of different sides of a block in the for.body above or the back-edge on the loop running into the bottom of a block rather than a top as you briefly mentioned.

[OfekShilon]

Thanks, I get it - dropping the graphviz thing.
Do you think you'd get to implement these missing parts in the near time? I'm a heavy CFG user and could benefit a lot from it. If you don't have time I'll look into it myself sometime.

[jeremy-rifkin]

I'm hoping to, the big hurdle is solving linear programming problems in the browser. Unfortunately there's no nodejs package for this (at least last time I checked). Realistically we can probably just approximate it though, as opposed to implementing a real linear programming solver :)

[OfekShilon]

Layout compacting is really needed:

[OfekShilon]

I do see a few simplex implementations in node.js : https://www.npmjs.com/package/linear-program-solver, https://www.npmjs.com/package/javascript-lp-solver, and a fork of the 2nd - https://www.npmjs.com/package/@ellbur/javascript-lp-solver. Hopefully compacting the CFG is feasible today.