Re: Compiler optimisation

From: Danny Thorpe (dthorpe_at_bozofilter.borland.com)
Date: 01/21/05 

Date: 21 Jan 2005 12:02:01 -0800

Dejan Stankovic wrote:

>
> Keep in mind that Delphi is one-pass compiler (apparently).

Incorrect. The Delphi compiler is a one-pass, top-down parser with
incremental code generation.

> This
> limits number of possible optimizations to ones that do not operate
> on intermediate code.

True, but not applicable to Delphi. The Delphi compiler does use
intermediate representations and multi-stage AST tree trimming
optimizations.

>
> For your reference, following is, as complete as I could make it,
> list of all optimizations that are used in todays compilers.
>

I've added notations for which of these the Delphi compiler implements.

> -Aggregation of global references
No, if this is referring to global constant folding (strings, primarily)

> -Algebraic simplifications, including reassociations
Yes, but to a limited degree. We don't replace division with multiply
by reciprocal, for example, because of concerns about loss of precision
at the edges.

> -Basic-block and branch scheduling
No.

> -Branch optimizations
Yes.

> and conditional moves
No.

> -Branch prediction
Static.

> -Code hoisting
No.

> -Constant folding
Yes.

> -Control-flow optimizations
Unclear.

> -Data prefetching
No.

> -Data-cache optimizations
No.

> -Dead-code elimination
Yes.

> -Global value numbering
No.

> -In-line expansion
Yes.

> -Induction-variable removal
Yes.

> -Induction-variable strength reduction
Yes.

> -Instruction prefetching
No.

> -Interprocedureal constant propagation
Unclear. A constant is constant everywhere, no?

> -Interprocedureal register allocation
No.

> -Intraprocedureal instruction cache optimization
No.

> -Leaf-routine optimization
No.

> -Linear-function test replacement
Unclear.

> -Local and global common-subexpression elimination
Yes.

> -Local and global copy propagation
No.

> -Loop-invariant code motion
Yes.

> -Machine idioms
No.

> -Partial-redundancy elimination
Yes. (for pointer derefs)

> -Procedure integration
Unclear.

> -Procedure specialization and clonning
No.

> -Scalar replacement of aggregates
> -Scalar replacement of array references

If this refers to constant expression evaluation, yes.

> -Shrink wrapping
??

> -Software pipelining, with loop unrolling, variable expansion,
> register -renaming and hierarchical reduction

Codegen templates are hand-tuned to favor instruction scheduling for
the U and V pipelines of the Pentium family of processors.

> -Sparse conditional constant propagation
No.

> -Tail call optimization, including tail recursion elimination
No.

> -Tail merging
No.

> -Unnecessary bounds checking elimination
Yes.

>
> Keep in mind that even very good compilers implement only a small
> number of those and that not all of those are speed optimizations.
>

Correct. The tail recursion optimizations in your list, for example,
are astronomically rare in the wild. Such optimizations typically only
kick in if you write you recursive routines "just so" which means only
the illuminati will benefit by it.

The mantra for Delphi optimizations is to make everyday code work
better. We don't the luxury of chasing after miraculous optimizations
that almost never work. I leave that to the grad students. ;>

 
> Now going back to Delphi. It has always been a solid compiler with
> two important features: it generates good code to begin with and it
> is one-pass (lightning fast). If you ever wandered why C++ takes ages
> to compile as compared to Delphi, this is the answer. A lot of that
> Delphi has to thank to the language itself.
>

True, except for the one-pass assertion. The codegen phase is
multi-pass intermediate node tree traversals and pruning. We just do
it many times faster than the more traditional compiler models that
were originally concieved for batch processing of punched cards.

>
> This brings me to another point. Delphi has never been designed to be
> high-end compiler. For the purpose that people use it, it is more
> than fast enough.
>

Correct. It could be said that Delphi is fast enough to lead some
folks to believe it should be the best at every computational scenario.

Delphi's objective is to be the most productive software development
tool for a very broad audience of developers. The compiler is one
small part of that.

> >
> > It is too bad Danny Thorpe is no longer posting here, as he would
> > be able to authoritatively set you straight on the issue of
> > optimizations in Delphi code.
> >
>

I wish you people would quit invoking my name. Popping in here with a
big puff of smoke and a few lightning bolts is fun and all, but it
takes days to get the smell of sulfur out of my hair.

-Danny 

-- 
Delphi Compiler Core:  http://blogs.borland.com/dcc

Relevant Pages

  • Re: fpc beats gcc? delphi?
    ... I know that for what I do, Delphi and C++ Builder are really bad compared to other commercial C++ compilers... ... Maybe for the x64 compiler... ... just over 1 vote per issue per year. ... about adding optimizations to the compiler. ...
    (borland.public.delphi.non-technical)
  • Alternative Future of Delphi?
    ... relevant compiler or interpreter... ... No more intricate code generation required for a particular platform ... on the Delphi compiler side. ...
    (borland.public.delphi.non-technical)
  • Re: Which Delphi Version To Buy
    ... Given the fact that Delphi compiler is quick and small, do you see feasible having a runtime compiler/parser enabling what you describe above? ... For example the basic data types processing in Delphi is sensibly superior to .NET's one exactly because is closer to the iron. ... Well, for parallel programming I, for one, certainly feel the need of a VM simply because the actual CPU architecture is far from the way in which humans deal with the reality which is parallel. ... The vast majority of the games you have to deal with /different/ characters doing /different/ actions in parallel, responding each one to the stimuli which comes from the environment. ...
    (borland.public.delphi.non-technical)
  • D7 revival? stirring the old pot + Delphi 64 suggestion
    ... The new compiler, but with the old IDE, the old help. ... You can check other areas of the site and poster stats, it's not that Delphi posters don't use .Net, it's just that they don't use Delphi for .Net work. ... As for the 64bit debugging, a CPU view debugger would be all that is really needed to get things started (this is for fastcode after all), no need for rich source-level debugging, inspectors, etc. early on. ... Validation could be two-ways: one in the fastcode challenge, another made via CodeGear private unit tests. ...
    (borland.public.delphi.non-technical)
  • Re: Version after Version
    ... merely because Delphi has no 64-bit compiler? ... >> targeted instructions and increasing the size of the cache to 32,000 ... >> That has nothing to do with the number of address lines on the CPU ...
    (alt.comp.lang.borland-delphi)