|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:||Mon, 13 Jun 1994 14:01:53 GMT|
>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!
title="Jump Minimization in Linear Time",
author="M. V. S. Ramanath and Marvin Solomon",
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.
Return to the
Search the comp.compilers archives again.