Unconstraining multiple edges between 2 nodes [rendering CFG with multiple relations]

Many thanks to authors/developers of Graphviz, and people who offer help here on the forum!

My usecase is rendering a Control Flow Graph (CFG) for program analysis, which is definitely not an unheard of usage for Graphviz. Nodes of CFG are Basic Blocks, i.e. linear sequences of instructions. In other words, nodes do have their own internal structure. And for this usecase, it is important where edges from a node originate, and where incoming edges point. Specifically, I would like outgoing edges to originate from the bottom of the node (i.e. after the last instruction of a Basic Block), and incoming edges to go to the top of node (to the first instruction). Due to this, I have to specify “compass values” for edges. I specifically found that instead of raw “s” (node bottom) and “n” (node top), “se” and “ne” usually work best.

But so far, we talk about control flow edges between nodes. There are other relationships among the nodes of CFG, and I would like to represent a few at the same time. For example, I would like to show Dominator Tree structure of the CFG.

With such a configuration, it’s not uncommon for nodes “l1” and “l2” to have a l2 -> l1 control edge, and at the same time, have l2 -> l1 “immediate dominator” edge. Here’s where problem comes - somehow, Graphviz thinks that if two nodes have multiple (here, 2 edges) between them, then these edges must be somehow related. It seems to go out of its way to route these 2 edges in such a way that there was a point where they are “close enough” to each other. Given that one of the edge is constrained to the sides of the node, and another not, this leads to completely twisted, unnatural edge rendering, as presented below:

[dot verbose=true]

digraph strlen {
node [shape=plain]
"pre_entry" [label=<<table cellspacing='0' border='0' cellborder='1'><tr><td>pre_entry</td><td><font point-size='9'>post#40</font></td></tr><tr><td colspan='2'><font point-size='9'>livein: </font></td></tr><tr><td balign='left' colspan='2'><b>0:</b> nop <br/><b>1:</b> nop <br/><b>2:</b> (000) s_2 = param 0 <font color='grey' point-size='9'><i>uses=1[@202]</i></font></td></tr><tr><td colspan='2'><font point-size='9'>liveout: s_2</font></td></tr></table>>]
"pre_entry" -> "start"
"start" [label=<<table cellspacing='0' border='0' cellborder='1'><tr><td>start</td><td><font point-size='9'>post#30</font></td></tr><tr><td colspan='2'><font point-size='9'>livein: s_2</font></td></tr><tr><td balign='left' colspan='2'><b>3:</b> (000) len_3 = 0 <font color='grey' point-size='9'><i>uses=1[@201]</i></font></td></tr><tr><td colspan='2'><font point-size='9'>liveout: len_3, s_2</font></td></tr></table>>]
"start" -> "l1"
"start" -> "pre_entry" [style=dotted, constraint=false]
"l1" [label=<<table cellspacing='0' border='0' cellborder='1'><tr><td>l1</td><td><font point-size='9'>post#20</font></td></tr><tr><td colspan='2'><font point-size='9'>livein: len_201, s_202</font></td></tr><tr><td balign='left' colspan='2'><b>200:</b> nop <br/><b>201:</b> (000) len_201 = phi len_3(000), len_6(000) <font color='grey' point-size='9'><i>uses=2[@8, @6]</i></font><br/><b>202:</b> (000) s_202 = phi s_2(000), s_7(000) <font color='grey' point-size='9'><i>uses=2[@4, @7]</i></font><br/><b>4:</b> (000) c_4 = $load s_202(000), ?u8 <font color='grey' point-size='9'><i>uses=1[@5]</i></font><br/><b>5:</b> if c_4*(000), ==, 0</td></tr><tr><td colspan='2'><font point-size='9'>liveout: len_201, s_202</font></td></tr></table>>]
"l1" -> "end" [label="t"]
"l1" -> "l2" [label="f"]
"l1" -> "start" [style=dotted, constraint=false]
"l2" [label=<<table cellspacing='0' border='0' cellborder='1'><tr><td>l2</td><td port='fooport'><font point-size='9'>post#10</font></td></tr><tr><td colspan='2'><font point-size='9'>livein: len_201, s_202</font></td></tr><tr><td balign='left' colspan='2'><b>6:</b> (000) len_6 = + len_201*(000), 1 <font color='grey' point-size='9'><i>uses=1[@201]</i></font><br/><b>7:</b> (000) s_7 = + s_202*(000), 1 <font color='grey' point-size='9'><i>uses=1[@202]</i></font></td></tr><tr><td colspan='2'><font point-size='9'>liveout: len_6, s_7</font></td></tr></table>>]
"l2":se -> "l1":ne
"l2" -> "l1" [style=dotted, constraint=false]
"end" [label=<<table cellspacing='0' border='0' cellborder='1'><tr><td>end</td><td><font point-size='9'>post#0</font></td></tr><tr><td colspan='2'><font point-size='9'>livein: len_201</font></td></tr><tr><td balign='left' colspan='2'><b>8:</b> return len_201*(000)</td></tr><tr><td colspan='2'><font point-size='9'>liveout: </font></td></tr></table>>]
"end" -> "l1" [style=dotted, constraint=false]


For reference, 2 problematic edges are defined as:

"l2":se -> "l1":ne
"l2":fooport -> "l1" [style=dotted, constraint=false]

The question is thus how to tell Graphviz that multiple edges between 2 nodes are completely unrelated and should not be constrained to each other in any way. Thanks.

1 Like

Note that with Graphviz 2.version I have locally (2.40.1, Ubuntu 18.04), it’s rendered even worse than here online:

Screenshot at 2020-06-28 15-21-06

1 Like

I took the liberty to change your post by adding [dot verbose=true] to show your DOT code. This will make it easier for people to help.

If you want to do interactive experiments, you might want to try the Graphviz Visual Editor.

The constraint=true attributes seem to also trigger the route_edges_in_a_wacky_manner attribute! Remove all the constraint=true attributes and you should get this:

The constraint=true attributes seem to also trigger the route_edges_in_a_wacky_manner attribute!

@steveroush, funny thing is that I actually use constraint=false. With “constraint” attribute described in the docs as:

If false, the edge is not used in ranking the nodes.

My idea was that “immediate dominator” relation is auxiliary and should not dictate graph shape (I believe I added it after I saw undesired effect on the graph shape indeed). I also thought I tried to switch that edge to constraint=true, but apparently, I didn’t. Thanks for the answer!

Thinking about it more, I wonder if for the spec like:

"l2":se -> "l1":ne
"l2":fooport -> "l1" [style=dotted, constraint=false]

“constraint=false” gets propagated to both edges (as having the same source/dest), which causes both of them that “too curly” look.

I’m sorry about this, I don’t believe there’s a workaround.

I believe there are logic problems in how our code handles multiple edges, particularly when there are edge ports involved.

constraint=false won’t help; IIRC this only affects level assignment and (maybe) crossing avoidance.