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$
  • 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 '17 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$ – Alexey Naidyonov Jun 20 '17 at 13:38
  • $\begingroup$ When/why does a plain depth-first-search that ignores back edges fail? $\endgroup$ – Raphael Jun 20 '17 at 14:47
  • $\begingroup$ I have added a proper illustration. Simple DFS would produce an incorrect order for this CFG. $\endgroup$ – Alexey Naidyonov Jun 21 '17 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.