Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rochester!pt.cs.cmu.edu!sei.cmu.edu!firth
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: net.arch
Subject: Delayed Branches
Message-ID: <304@sei.cmu.edu>
Date: Wed, 3-Sep-86 11:51:41 EDT
Article-I.D.: sei.304
Posted: Wed Sep  3 11:51:41 1986
Date-Received: Wed, 3-Sep-86 21:01:59 EDT
Organization: Carnegie-Mellon University, SEI
Lines: 45

To respond to some issues that have been raised.

First, I don't believe the Assembler should
reorganise code.  The purpose of assembler code
is to allow the user total control over what
the machine will do, and the assembler has no business
taking away any of that control.

Moreover, why would you WANT the assembler to
reorganise?  Presumably you are writing in
assembler to do things the compiler can't, such
as access interrupts, devices &c, in which case you
probably need tight control.  If you are writing
in assembler because you don't trust the optimising
compiler, well, would you trust an optimising
assembler?

Filling the hole after a delayed branch, and similar
transformations, are done at a late stage in the
compilation process, because it is only at that
late stage that the program representation has
branch instructions in it.  While being compiled,
a program usually goes through several intermediate
transformations, gradually becoming more and more
like machine code.  What starts as a Pascal WHILE
loop becomes a tree node with the key token "while",
then maybe a flowgraph node with two entries and
one exit, then maybe a code node with "branch false"
token.  Only at the last stage is it possible to
do instruction reordering.

Unfortunately, this way of building compilers misses
a lot of optimisations.  To reuse a previous example,
filling the hole by loop rotation may be impossible,
because at the stage where the compiler knows about
branches, it has forgotten about WHILE statements,
and must laboriously reanalyse the flow by scanning the
linear machine code.  The lesson here is that one can
get good code with successive optimisations based on
partial information and heuristics, but to get truly
"optimal" code one must never throw information away.
Hence, the program representation must contain the
fact that there is a branch, and SIMULTANEOUSLY the
fact that this branch is the branch back at the
end of a pure WHILE loop.