Which part of optimization is most important in a compiler?

Hi,all

I haven't taken the compiler course at college. Because my job is
to optimize code on DSP, I hope to understand compiler deep and begin
to read a compiler textbook. There are a lot of materials in a book,
but the overview of advanced compiling is not given in the book.

Maybe every part is important for a optimized compiler. I hope to know
which part of a compiler is most important in a compiler. Instruction
scheduling, or register allocation?

Best Regards
Jogging

Both instruction scheduling and Register allocation are important parts.
These two parts present in an optimizing compiler. In fact these two are
coupled.

Please find following book is useful:

"Advanced Compiler Design and Implementation" by
Steven S.Muchnick, Pub: Morgan Kaufmann

>    I haven't taken the compiler course at college. Because my job is
> to optimize code on DSP, I hope to understand compiler deep and begin
> to read a compiler textbook. There are a lot of materials in a book,
> but the overview of advanced compiling is not given in the book.
>
> Maybe every part is important for a optimized compiler. I hope to know
> which part of a compiler is most important in a compiler. Instruction
> scheduling, or register allocation?

joggingsong@gmail.com writes:

>    I haven't taken the compiler course at college. Because my job is
> to optimize code on DSP, I hope to understand compiler deep and begin
> to read a compiler textbook. There are a lot of materials in a book,
> but the overview of advanced compiling is not given in the book.
>
> Maybe every part is important for a optimized compiler. I hope to know
> which part of a compiler is most important in a compiler. Instruction
> scheduling, or register allocation?

This depends a lot on both the target processor and the types of
programs you want to run.

If the target processor does out-of-order run-time scheduling of
instructions, compile-time scheduling is less important than if the
processor runs instructions in the order they appear but with
pipelining or multiple simultanious instructions (that don't have
overlapping resource needs).  Scheduling is even more important if you
need to explicitly group instructions that start at the same time, as
some DSPs (and Intel's Itanium) do.

Register allocation is important if you have a limited number of
registers and register access is much more efficient than memory
access (which is usually the case).  It becomes even more important
(and complex) if different instructions use different registers or if
there are instructions that can operate on multiple adjacent registers
or on parts of registers (which may allow allocating several small
values in on register).

DSPs are notoriously difficult for compilers to generate optimal code
for, since they commonly have specialised registers,
multiple/part-register operations and need for explicit grouping of
instructions (or at least compile-time scheduling).

Torben

joggingsong@gmail.com wrote:
>    I haven't taken the compiler course at college. Because my job is
> to optimize code on DSP, I hope to understand compiler deep and begin
> to read a compiler textbook. There are a lot of materials in a book,
> but the overview of advanced compiling is not given in the book.
>
> Maybe every part is important for a optimized compiler. I hope to know
> which part of a compiler is most important in a compiler. Instruction
> scheduling, or register allocation?

"Most important" is an impossible question to answer -- it depends on
which one is being done badly.  If the instruction scheduling is done
badly, the compiled program will spend all its time with stalled
pipelines and run slowly, and the best register allocation in the world
won't fix it.  If the register allocation is done badly, the compiled
program will spend all its time in memory fetches and stores and run
slowly, and the best instruction scheduling in the world won't fix it.

It also depends heavily on the processor architecture and the program.
On a Cell SPE, instruction ordering can make an order-of-magnitude
difference in execution time, but with 128 registers, allocating the
registers in an optimum way is often not especially critical.  On a
processor that does instruction-reordering in hardware but has a
half-dozen registers, however, the register allocation is critical and
the instruction ordering much less so.  I don't know where your DSP
would fit in this spectrum.

With that said, a program with poor instruction scheduling will still
run, whereas the registers have to be allocated _somehow_ in order to
get a running program, so you might as well learn about register
allocation first.

Also, if you have any experience with writing assembly-code programs for
your DSP, that should give you some insight into what's most important
to get things to run fast on your processor.  (If you don't have
experience with that, it's probably useful to get some -- it's hard to
write a program to produce something that you don't know how to produce
yourself!)

- Brooks


--
The "bmoses-nospam" address is valid; no unmunging needed.

>Scheduling is even more important if you
> need to explicitly group instructions that start at the same time, as
> some DSPs (and Intel's Itanium) do.

>Please find following book is useful:
>"Advanced Compiler Design and Implementation" by
>Steven S.Muchnick, Pub: Morgan Kaufmann

I've done a quick search for instruction scheduling especially for
Itanium / instruction-level parallelism. Are there some main texts
(academic papers, etc.) of main techniques on this topic?  I'm
interested in implementing scheduling for my toy-compiler, to try on
Itanium. It doesn't have to be the best technique around, in fact, the
simpler the better (more advanced will be attempted later!).

The book "Engineering a Compiler" by Cooper and Torczon (Morgan
Kaufmann) has an introductory chapter which reviews instruction
scheduling but I'm not sure whether it outlines a specific algorithm
for it.


K. Phillips

kphillips wrote:
> I've done a quick search for instruction scheduling especially for
> Itanium / instruction-level parallelism. Are there some main texts
> (academic papers, etc.) of main techniques on this topic?  I'm
> interested in implementing scheduling for my toy-compiler, to try on
> Itanium. It doesn't have to be the best technique around, in fact, the
> simpler the better (more advanced will be attempted later!).

Google for "list scheduling", that should give you plenty of pointers.
--
Pertti

Pertti Kellomdki schrieb:

> Google for "list scheduling", that should give you plenty of pointers.

That's how the stuff is called that I reinvented myself :-)

Thanks a lot for giving this hint. There are indeed lots of papers that
I can read over the next ws.

Nils

> >    I haven't taken the compiler course at college. Because my job is 

I have written many assembly codes for DSPs. Most time I try to use
SIMD instructions.  Instruction scheduling is used to hide latency of
multi-cycle instructions, but almost every instruction is single cycle
instruction.  Now only computation-intensive routines need to be
rewritten in assembly codes.  So in my opinion, trying to use SIMD and
special instructions, which is hard to express in c language, is the
right way to improve performance.

Register allocation tries to reduce spill code, but in most curreent
DSPs stack is in cache or L1 SRAM, of which access latency is 1 cycle.

Best Regards
Jogging