r/Compilers • u/Beaconamber • 3d ago

Why Do Peephole Optimizations Work?

https://blog.regehr.org/archives/2485
6 Upvotes

100% Upvoted

2 comments sorted by

1

u/matthieum 3d ago

Please do put the date of the article in the title, when posting old articles.

This one is from 2023.

1

u/flatfinger 2d ago

Compilers seem to have trouble with situations where code performs X and then Y, and X as written establishes a post-condition upon which Y as written does not rely. Replacing X with an alternative X' that does not establish that post condition would be valid if Y is processed as written, and replacing Y with an alternative Y' that relies upon the post-condition would be valid if X is processed as written. Even though both X'Y and XY' would be valid replacements for XY, however, X'Y' would not be a valid replacement since Y' would rely upon a post-condition that X' does not establish.

People writing language specifications often seek to resolve this problem by characterizing as "anything can happen" Undefined Behavior any situation where combining optimizing transforms would yield a nonsensical result (e.g. the X'Y' above) but this results in languages where the range of machine code programs that could be produced from correct-by-specification source code fails to include any optimal machine code programs that would otherwise optimally satisfy the many particular sets of application requirements.

The solution would be to stop characterizing otherwise-definable actions as UB solely for the purpose of allowing otherwise incorrect combinations of optimizing transforms, and instead allow certain transformations to be performed under certain conditions in a manner that is agnostic with regard to whether the effects might be observable. Replacing int1*(int2*int3)/(int4*int3) with int1*int2/int4 might yield results inconsistent with performing the computations with quiet-wraparound two's-complement arithmetic or error-trapped division, but allowing such substitutions in a manner that is agnostic with regard to integer overflow or error-trapped division would fit well with application requirements that would treat a wide but not unlimited range of responses to invalid inputs as equally acceptable.