Rockbox.org home
release
dev builds
extras
themes manual
wiki
device status forums
mailing lists
IRC bugs
patches
dev guide



Rockbox mail archive

Subject: Re: time to sleep?
From: Sven Karlsson (svenka_at_it.kth.se)
Date: 2002-08-25


Hi,

> Register allocation is a matter for backend, that is, dependent of a
target,

Not in GCC. See below.

> or there is a more general algo for register allocation ?

Yes there are plenty of register allocation algorithms and most are rather
high-level dealing with pseudo instructions. In fact, you often do several
passes of register allocation during the optimization phases.
On load-store architectures you quite often do register allocation before
and after instruction selection. Back when I did work on GCC you simply
specified which registers and register classes were available. I very doubt
much this has changed since then.

I should mention that the target descriptions in GCC aren't entire back-ends
and AFAIK all optimization stages and other things like register allocation
are common for all targets. What you do describe in the target is what kind
of registers and what registers there are in the architecture, what kind of
instructions there are or rather how expressions and statements are mapped
on instructions, and what kind of adressing modes you have available.

When compiling GCC this description is taken and a backend is generated from
it. So the quality of the backend comes from how well the architecture is
described in the description and how well that description suits the
compiler. It appears that the optimization passes in GCC has during the last
years been tuned for i386, not surprisingly, and it looks like the other
targets are lagging behind.

>for me SH1 target
> is less optimizing than IA32 (for example, I was forced to use if/else
> instead of switch/case in a inline function because even with a constant
> selector in switch, it still produces all the cases statements, IA32
target
> does the right job).

Now that's instruction selection. And that is part of the target
descriptions in GCC. See above.

> algos to O(n) for example, instead trying to gain just 5% by reducing and
> optimizing assembly instructions to real save power.

Naturally, and that was at the top of the list. The main objective is to
make sure the idle time is as long as possible.

However, and this is nothing I know about so this is pure speculation. I
would be surprised if the bulk of the code in rockbox runs in any kind of
loops. And that would basically mean that there is rather little room for
algorithmical improvments. Have anyone done any in depth profiling on the
firmware?

> So it really depends on the contents of your functions.

Naturally. However, the number of registers available is most probably
enough unless you have a very large number of live variables in a function.
Rember that SPARC do not have that many "local" registers due to the
register windows.

There is a rather good book on the subject, i.e., optimizing compilers,
called "Advanced Compiler Design & Implementation" by Steven Muchnick. It
gives a good overview of modern compilers but it does have a lot of annoying
errors in the description of the algorithms and I suggest that you read the
associated papers of you want to implement anything.

Best regards
 Sven



Page was last modified "Jan 10 2012" The Rockbox Crew
aaa