|Block Scheduling: determ vs nondeterm PAULLONG@delphi.com (1994-06-05)|
|Re: Block Scheduling: determ vs nondeterm firstname.lastname@example.org (1994-06-13)|
|Re: Block Scheduling: determ vs nondeterm email@example.com (1994-06-15)|
|Re: Block Scheduling: determ vs nondeterm firstname.lastname@example.org (1994-06-16)|
|Re: Block Scheduling: determ vs nondeterm chase@Think.COM (1994-06-16)|
|Re: Block Scheduling: determ vs nondeterm email@example.com (1994-06-20)|
|From:||firstname.lastname@example.org (Preston Briggs)|
|Organization:||Rice University, Houston|
|Date:||Thu, 16 Jun 1994 14:04:06 GMT|
>>Just sort the blocks by their postorder index (in reverse).
>Shouldn't one traverse the tree in preorder?
>Seems like it'd require a bit more memory, e.g., stack space, to do it
>postorder, and there is no benefit.
Preorder and postorder walks require the same amount of time and space;
i.e., O(n+e) time and O(n) space, where n is the number of blocks in the
control-flow graph and e is the number of edges. In practice, they're
both very fast and very small; especially when compared to the rest of the
analysis required for optimization. After all, they only look at the
blocks and edges, not the actual instructions.
In my experience, preorder generates "unnatural" block orderings.
Consider the following fragment
if (p) goto C
There are two possible preorder traversals
(A B D ... C) and (A C D ... B).
Both seem unnatural to me in that one of the clauses (B or C) will end
up after D. On the other hand, the two possible reverse postorder
(A B C D ...) and (A C B D ...)
are both intuitive and compact. For more fun, consider loops with
embedded control flow. The same situations arise, and the results
look even more absurd.
Return to the
Search the comp.compilers archives again.