Re: Block Scheduling: determ vs nondeterm

Preston Briggs <preston@noel.cs.rice.edu> writes:


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


Oh, I hadn't thought of that. 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.


I'll look up the article. Thanks.


>sledgehammer would be fun...


You're absolutely right. After I posted the article, I realized that the
resources that a GA would require would not balance the possible small
reduction in code space. But it would definitely be fun.


On a whim, I implemented a random block scheduler (how's that for non-
deterministic?). I started with basically the same order as the source-
language program then swapped two blocks at random. I continued to do so
over first 1000 then 10000 iterations. If an arrangement "scored" better
than the original, it would become the best arrangement, etc. Pretty poor
performance! The score (number of jumps that the back end would remove)
dropped quickly then hovers around 2. It would likely take way too many
iterations to find an arrangement as good as the original. Random order
is bad! I scrapped that method and implemented the following: starting
with basic blocks that are generally in the same order as the source
program, look for a block whos successors do not follow it in the list of
basic blocks. Next, see whether one of those successors is isolated by
not having a predecessor that immediately precedes it in the list and is
the start of a sequence of basic blocks that ends with a block whos
successors do not follow it in the list. If such a situation is found,
move that string of otherwise isolated basic blocks after the first block
that I mentioned. Continue with the next block in the list. This works
pretty good. The only two situations I've seen it reschedule a sequence
of blocks is where goto's in the source language isolated a section of
code and in blocks that represent a case statement. In the latter case,
it moved the selection blocks that the front end placed at the end of the
case statement to the front of the statement.


Paul Long
--

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