Generalized structured programs and loop trees

✍ Scribed by Ward Douglas Maurer

• Publisher: Elsevier Science
• Year: 2007
• Tongue: English
• Weight: 440 KB
• Volume: 67
• Category: Article
• ISSN: 0167-6423
• DOI: 10.1016/j.scico.2007.02.002

✦ Synopsis

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.