Generalized structured programs and loop trees
Any directed graph, even a flow graph representing "spaghetti code", is shown here to have at least one loop tree, which is a structure of loops within loops in which no loops overlap. The nodes of the graph may be rearranged in such a way that, with respect to their new order, every edge proceeds in the forward direction except for the loopbacks. Here a loopback goes from somewhere in a loop L to the head of L. We refer to such a rearrangement as a generalized structured program, in which forward goto statements remain unrestricted. Like a min-heap or a max-heap, a loop tree has an array representation, without pointers; it may be constructed in time no worse than O(n(2)) for any program written in this fashion. A scalable version of this construction uses a label graph, whose only nodes are the labels of the given program. A graph has a unique loop tree if and only if it is reducible. (c) 2007 Elsevier B.V. All rights reserved.
generalized structured program loop trees gsp reducible graphs overlapping loops strongly connected components