[Tinycc-devel] Jump optimization and for loops

[Peter \"Firefly\" Lund]

On Tue, 11 Mar 2003, TK wrote:

> that it seems that TCC67 often generates 3 branches for each iteration
> in a "for" loop.  And sometimes a branch to a branch, which is

That's because tcc translates as it goes.  The output is stored linearly
into the code segment of the output binary (or memory).

for (e1; e2; e3)
  stmt;

would translate to:

    e1       ; initial expression

Lcheck:
    e2       ; loop condition, may jump to Lbreak
    jmp Lok

Lcontinue:
    e3       ; stuff to do at end of each iteration
    jmp  Lcheck

Lok:
    stmt
    jmp Lcontinue

Lbreak:


A better translation would be:


    e1
    jmp Lcheck

Lok:
    stmt
    e3
Lcheck:
    e2       ; may jump to Lbreak
    jmp   Lok

Lbreak:

If the expressions only lead to position independent code it would be
trivial to move the snippets around (if you live with slightly suboptimial
"direction" of branches).  Otherwise you will need to relocate them a bit.

> particularly bad for this processor.  Again a second pass through the
> generated code should be able to eliminate some of those.

You could use a true peephole optimizer for some of it.
Or you could keep data structures around that describe the basic blocks to
make it easier to optimize jumps.

The "traditional" solution is to use an intermediate language and perform
much of the moving around and jump optimization on that.  If you do that
in a language like C it will usually be nasty, ugly, and fraught with
special cases.  If you do it in ML (like c8 eventually will, when and if I
get around to writing it), it will be trivial (I have done so for a couple
of toy compilers).

Currently, tcc doesn't use any intermediate language -- but the interface
between tcc.c proper and i386-gen.c is close to something that could
become such a language (the functions that get called + the contents of
the vstack).

Whether we would ultimately want such an intermediate language or not is
not something I think we should decide yet.  I certainly don't think we
should try to put one in yet!  I'd rather fix bugs first and simplify the
compiler.

> that.  The main problem seems to be that when some code is deleted, many
> symbol references have to be adjusted to do the final relocations, but
> on the other hand the relocation might be required to be made first, to
> determine what is actually being referenced??   Insight here would be
> appreciated...

The only big problem here is that some architectures have instructions in
several variants depending on, say the size of an immediate or the reach
of a branch.

Yes, IA-32 is one such architecture ;)

You can get around a lot of it by simply being optimistic as you go
forward and go back and enlarge instructions when you are proven wrong.

(yes, there are much better algorithms, but they are complicated and I
would have to look them.  Anyway, it is a solved problem and 90% solutions
are easy)

-Peter