Block reording.

I'm new to compiler optimization, so can anyone tell me where to look
about this?

I have some code structured roughly like this:

for(int i=0; i < N; i++)
{
if( cond1a)
if(cond 2a)
goto stuff;
else if(cond2b)
continue;
else
continue
else if(bond 1b)
if(cond3a)
continue;
else if(cond3b)
goto stuff;
else
continue;
else
continue;
stuff:
//do something here
}


Condition condXa and condXb work in the same data point, the if-else
tree above is only an example, it's actually a general tree, and the
continue and gotos are distributed round the leaves (though an else
condition can't have a goto, just a continue).

The code isn't C, it's only ever present as a tree. The problem comes
when generating the machine code for this (x86 machine code, as it
happens). The code looks like repeated blocks of:

mov XX, %eax //Fetch some data
cmp %ebx, %eax //Conition Xa
jg ##### //goto ###
cmp %ecx, %eax //Condition Xb
jg ##### //got ###
// <--- else block follows directly

The code is simple to generate if I only use long distance jumps for
je, since then every block is the same size and every jump is more or
less equal in cost. However, a jump to an arbitrary point is 6 bytes
of machine code, where as a jump to a nearby point can be sone in
only 2 bytes. Naturally, I'd rather use as many short jumps as
possible, but this requires some strategy to reorder the blocks and
switching from a 6 byte jump to a 2 byte has the potential to affect
the distances of a large number of the other jumps. And the shrinking
of the code size may allow other short jumps to be used, etc...

The final point it that the optimization needs to be reasonable
efficient since the compiled code currently takes about 10ms to
execute. There's usually around 1000 blocks, but it can be up to
10,000.

Can anyone gove me some pointers about this?

Thanks
-Ed
.

Relevant Pages

  • Re: new to the condition system
    ... We can conditional jumps anywhere in the code. ... but nevertheless don't grow the stack. ... GO in Common Lisp isn't exactly the same as a goto in some other ... On the other hand, it is the caller that makes the distinction, not ...
    (comp.lang.lisp)
  • Re: PEP 3107 and stronger typing (note: probably a newbie question)
    ... design a language completely free from conditional jumps? ... GOTO is unconditional. ... You are seeing the machine language behind it, and of course there are lots ...
    (comp.lang.python)
  • Re: GOTO vis-a-vis professional vs amateur programmers
    ... Including GOTO. ... that language is Java (or any other language that doesn't include ... Did you try the code I listed which jumps out of a FOR..NEXT loop? ...
    (comp.lang.basic.misc)
  • Re: continue
    ... I do not really see that goto is worse programming practice than attaching ... code for us the discuss this, so I will assume that you really need to exit ... jumps, and even makes guarantees about cleanup involved in stack unwinding. ...
    (comp.lang.cpp)