Re: Block Scheduling: determ vs nondeterm

PAULLONG@delphi.com writes:
>In order to remove as many jumps from one basic block to another, I
>understand that one needs to perform block scheduling, much like
>instruction scheduling. However, I've never written a block scheduler and
>don't know what the traditional approach is. My first inclination is to
>write a non-deterministic block scheduler using a genetic algorithm to
>obtain a soltuion that is "good enough."


Hmmm, building a sledgehammer would be fun...
Or you could review the literature!
See especially


    title="Jump Minimization in Linear Time",
    author="M. V. S. Ramanath and Marvin Solomon",
    pages="527--545",
    journal=toplas,
    year=1984,
    month=oct,
    volume=6,
    number=4


Or, just sort the blocks by their postorder index (in reverse).


Recall "preorder", "inorder", and "postorder" from your data
structures class when they explained how to walk over a binary
tree. Postorder means we number a node after visiting all
it's successors. So, the start node of the control-flow graph
will end up with the highest number.


I don't expect this is optimal, but it's certainly fast and tends to
get some things right.


Preston Briggs
--

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