Re: Block Scheduling: determ vs nondeterm

>>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


block A
if (p) goto C


block B
goto D


block C


block D
...


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
traversals


(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.


Preston Briggs
--

Return to the comp.compilers page.
Search the comp.compilers archives again.