Re: Prediction of local code modifications

Tim Frink wrote:
(snip)

> My optimizations deal with moving basic blocks (determined by some
> cost functions) from the slow main memory to a small but fast memory
> thus allowing a fast access to these particular blocks. However, I
> have large problems with the "optimized" code. The moved blocks
> benefit from the faster memory but due to the moving the addresses of
> the subsequent instructions obviously change.
(snip)

> Thus, my problem is that I can achieve a local optimization for the
> moved blocks but the resulting global influence is not predictable
> and might even undo the benefits and even result in a degraded
> runtime of the program.

> How do compiler developers cope with this problem? Are there any
> approaches which allow to predict the influence of a local code
> optimization on the global code performance for complex processors?

If I understand your question right, the answer is 'dynamic programming'.

Dynamic programming, which is neither dynamic nor programming, allows
one to do global optimization given weights (cost functions) of the
various choices.

http://en.wikipedia.org/wiki/Dynamic_programming

http://www.ics.uci.edu/~dan/class/161/notes/6/Dynamic.html

First popularized by biologists comparing protein sequences, it was
then used by the unix 'diff' program for finding a minimal set of
differences between two files.  (Again, with the appropriate
weighting.)  In general, dynamic programming allows one to do in
polynomial time what would otherwise seem to take exponential time.

The use of dynamic programming for code generation in compilers is
described in the book about LCC,

http://drhanson.s3.amazonaws.com/storage/do***ents/linux.html

and likely in other compiler books.

-- glen