Re: How Smart Can We Afford to be?

In article 92-02-046, jjones@uiuc.edu writes:
> 6. Can sophisticated optimizing compilers be built correctly in a timely
> fashion?


I agree with previous posters, Bob Metzger in particular, in saying that
sophisticated optimizing compilers are not significantly different than
other large software projects. If you define "correctly" as having few
enough bugs that users can get their work done, and "timely" as getting to
market soon enough to make a profit, then I think the answer is Yes. If
you define "correctly" as being completely free of bugs, then the answer
is No for any non-trivial software product, compiler or otherwise.


> 7. What are the tradeoffs in writing a compiler that takes advantage of
> lots of registers, versus a compiler that does a good job of instruction
> scheduling and taking advantage of a pipeline?


Having built a compiler for a pipelined RISC machine, with said compiler
having a sophisticated register allocator AND a good instruction
scheduler, we have found that there are two primary difficulties:


    1. It is very difficult to tell whether using an additional register, in
          order to better use the pipeline, will benefit more than the cost of
          saving/restoring that register on procedure entry/exit. This is
          especially true in basic blocks that are conditionally executed. The
          problem becomes more intractable if you can't predict with 100%
          reliability the exact execution sequence of instructions (for
          instance, if loads from memory can be stalled by cache misses that you
          can't predict).


    2. The register allocator can seldom know which instructions will be
          close together after scheduling. Thus it may allocate the same
          register for different purposes in instructions that were initially
          widely separated, but after scheduling end up close together. This
          can stall a pipeline.


These problems can be alleviated with heuristics, but which ones you use
depends on the type of code you expect to compile.
--
Bill Leonard
Harris Computer Systems Division
2101 W. Cypress Creek Road
Fort Lauderdale, FL 33309
bill@ssd.csd.harris.com
--

Return to the comp.compilers page.
Search the comp.compilers archives again.