Re: Prediction of local code modifications
- From: glen herrmannsfeldt <gah@xxxxxxxxxxxxxxxx>
- Date: Fri, 28 Mar 2008 02:44:26 -0800
Tim Frink wrote:
(snip)
My optimizations deal with moving basic blocks (determined by some(snip)
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.
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/documents/linux.html
and likely in other compiler books.
-- glen
.
- Follow-Ups:
- Re: Prediction of local code modifications
- From: preston.briggs@xxxxxxxxx
- Re: Prediction of local code modifications
- References:
- Prediction of local code modifications
- From: Tim Frink
- Prediction of local code modifications
- Prev by Date: Re: Which part of optimization is most important in a compiler?
- Next by Date: Re: Prediction of local code modifications
- Previous by thread: Prediction of local code modifications
- Next by thread: Re: Prediction of local code modifications
- Index(es):
Relevant Pages
|
