gnupic: Re: [gnupic] Linker Optimizations
Subject:
Re: [gnupic] Linker Optimizations
From:
Scott Dattalo ####@####.####
Date:
5 Mar 2007 17:46:23 +0000
Message-Id: <45EC5728.2070100@dattalo.com>
David Barnett wrote:
> I'm not quite sure what constitutes pCode, though.
pCode is a term I came up with. C-compilers (and SDCC included) have an
intermediate code generation stage where the code there is called
'iCode'. Prior to the PIC backend, the other SDCC ports went straight
from iCode to assembly mnemonics. Once the assembly mnemonics have been
generated, then the only optimization available was a rather limited
peep hole optimizer.
When I added the first PIC port to SDCC, I saw that much further
PIC-specific optimizations were possible. One approach I could have
taken was to write a subsequent intermediate code optimizer. There was
some precedence for this already with port- specific memory and register
allocation generation stages. However, I saw further potential with an
architecture specific optimizer.
In a nutshell, the pCode is a one-to-one mapping of an object to a PIC
instruction. On the PIC backend, SDCC converts the iCode directly into
pCode. If no further optimizations are applied, then the pCode can be
converted in text and would be similar to the other ports. However, with
the pCode representation it is possible (or at least easier) to apply
optimizations. For example, I rewrote the peephole optimizer for the PIC
backend to work with wild cards. This made it possible to write
categories of rules as opposed to whole bunch of specific, special case
rules. But in general - each pass through one of the optimization stages
will convert pCode into potentially better optimized pCode. And since
the pCode has a one-to-one mapping onto PIC instructions, the pCode
optimizer is working much like a PIC firmware engineer.
A few other features of the pCode are tail optimizations, live range
analysis, and call tree analysis. These features don't make much sense
living in the compiler. It's best to apply these optimizations in the
linker. Take the call tree analysis. If the linker performs a call tree
analysis and determine that certain functions are never called - then no
code needs to be generated for them. Or if it determines that a certain
function is only called once, then that function can be inlined. What's
really cool is that after inlining you can run the code through the
pCode optimizer again. This subsequent pass may end up removing things
like parameter passing.
You may wish to compare SDCC's approach with gcc. gcc has an
intermediate code generation that's represented in a language they call
RTL - Register Transfer Language. RTL is a Lisp like language. gcc is a
multi-pass compiler. Each pass applies some specific optimization to the
RTL. There are ways of writing RTL for specific passes. But the general
idea is to apply some kind of optimization strategy to the RTL and run
through the RTL objects. The RTL objects either do nothing or convert
existing RTL objects into new ones. SDCC's iCode is somewhat like RTL.
However, gcc keeps the representation in RTL as long as possible. There
is not necessarily a one-to-one mapping between an RTL object and a
single assembly instruction.
If we were to move pCode into gplink, then this is probably the high
level approach that should be taken.
- define a set of assembler directives that can control the linker.
For example, we'd need to tell the linker things like 'the follow block
is really data table and not instructions' or 'the following code has
been hand crafted to run at a very specific rate and should not be
optimized' or etc...
- Introduce an pCode as a do-nothing intermediate stage.
It'll take time to modify gplink's infrastructure to accommodate
something like pCode. I suspect there are several built in assumptions
that need to dealt with. The 'do nothing' pCode provides a type of
invariance stage where you can resolve these assumptions before
introducing any of the pCode features.
- Introduce peep hole optimization
Once the code inside the linker is in a pCode format, then the simplest
thing to try is the peephole optimizer.
It's going to take several man-months to accomplish these high level tasks.
Scott
