Re: Block Scheduling: determ vs nondeterm

preston@noel.cs.rice.edu (Preston Briggs)
Thu, 16 Jun 1994 14:04:06 GMT

          From comp.compilers

Related articles
Block Scheduling: determ vs nondeterm PAULLONG@delphi.com (1994-06-05)
Re: Block Scheduling: determ vs nondeterm preston@noel.cs.rice.edu (1994-06-13)
Re: Block Scheduling: determ vs nondeterm paullong@delphi.com (1994-06-15)
Re: Block Scheduling: determ vs nondeterm preston@noel.cs.rice.edu (1994-06-16)
Re: Block Scheduling: determ vs nondeterm chase@Think.COM (1994-06-16)
Re: Block Scheduling: determ vs nondeterm grunwald@foobar.cs.colorado.edu (1994-06-20)
| List of all articles for this month |

Newsgroups: comp.compilers
From: preston@noel.cs.rice.edu (Preston Briggs)
Keywords: optimize
Organization: Rice University, Houston
References: 94-06-060 94-06-089
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


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


Post a followup to this message

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