0
$\begingroup$

I have a reducible control flow graph with only natural loops, produced from a simple DSL. Every node keeps a list of successors and a list of predecessors. I need to make a sequence of nodes out of this CFG with following properties:

  1. All predecessors of a block are located before this block, with the exception of backward edges of loops. This implies that all dominators of a block are located before this block.
  2. All blocks that are part of the same loop are contiguous, i.e., there is no non-loop block between two loop blocks.

What would be the most efficient algorithm to produce such a sequence?

For illustration consider following CFG (left) with desired output (right).

CFG

CFG has been produced from a DSL which is roughly equivalent to pseudocode:

    for(; a && b; c++) {
        if (d) {
          dostuff1();
        } else {
          dostuff2();
        }
        dostuff3();
    }
    dostuff4();

Here is also CFG itself in python:

from collections import defaultdict

class Node:
    def __init__(self, id, name):
        self.id = id
        self.name = name
        self.succ = []

class Graph:
    def __init__(self):
        self.graph = defaultdict(Node)

    def addNode(self, node):
        self.graph[node.id] = node

    def addEdge(self, uid, vid):
        self.graph[uid].succ.append(self.graph[vid])

g = Graph()

g.addNode(Node(0, "Entry"))
g.addNode(Node(1, "For-Loop-Entry"))
g.addNode(Node(2, "Logical-And-Left"))
g.addNode(Node(3, "Logical-And-Right"))
g.addNode(Node(4, "For-Loop-Test"))
g.addNode(Node(5, "If"))
g.addNode(Node(6, "If-Consequent"))
g.addNode(Node(7, "If-Alternative"))
g.addNode(Node(8, "For-Loop-Body"))
g.addNode(Node(9, "For-Loop-Update"))
g.addNode(Node(10, "Body"))
g.addNode(Node(11, "Exit"))

g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(2, 4)
g.addEdge(3, 4)
g.addEdge(4, 5)
g.addEdge(4, 6)
g.addEdge(6, 7)
g.addEdge(6, 8)
g.addEdge(7, 9)
g.addEdge(8, 9)
g.addEdge(9, 10)
g.addEdge(10, 1)
g.addEdge(5, 11)
$\endgroup$
4
  • 1
    $\begingroup$ What is a "natural" loop? Which properties does your graph have that make you certain that such an order even exists? Have you looked at the standard algorithms for topological sorting? I'm sure one or the other can be adapted to consume cycles greedily, which would then give you your result. $\endgroup$
    – Raphael
    Jun 20, 2017 at 13:15
  • $\begingroup$ Term natural comes from "Compilers..." by Aho&Ulman, and described as a loop having a single entry node ("header") and a single back edge entering loop header. One node can be a header for a number of (nested) loops though. Yes, I'm sure such order is possible. One possible solution would be recursive interval splitting, but it's damn expensive, especially in terms of RAM. The most close O(E+V) algorithm I found was Tarjan's SCCs finder, but it fails with nested loops. $\endgroup$ Jun 20, 2017 at 13:38
  • $\begingroup$ When/why does a plain depth-first-search that ignores back edges fail? $\endgroup$
    – Raphael
    Jun 20, 2017 at 14:47
  • $\begingroup$ I have added a proper illustration. Simple DFS would produce an incorrect order for this CFG. $\endgroup$ Jun 21, 2017 at 7:04

1 Answer 1

0
$\begingroup$

I believe you may be looking for the dominator tree of the CFG. Some useful resources:

It could also possibly be the "reverse postorder" mentioned in the first link.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.