Shrink-wrapping: Introduction

[Bernd Schmidt]

I'll be posting a series of patches that add an implementation of
shrink-wrapping to gcc. I've used the algorithm in Muchnick's book as a
guideline, but ended up with an implementation that is somewhat more
conservative.

One of my goals was to reuse the existing prologue/epilogue
infrastructure as much as possible so that it is relatively easy to add
shrink-wrapping capability to a new port, rather than having to rewrite
prologue/epilogue generation for each. This implies that we still only
generate one prologue per function, rather than saving individual
registers at exactly the location where it becomes necessary. Still,
this is good enough to detect and optimize many early-exit cases.

There's a new comment at the top of thread_prologue_and_epilogue_insns
which describes the algorithm in some detail.

For now, the targets that can make use of this are ARM, MIPS and i386.
This turned out to be a fortunate choice, as these cover a large range
of situations. ARM has conditional return instructions, and requires a
distinction between return (which may pop lots of registers) and
simple_return (which just branches). MIPS has delay slots, so making it
work required fixing up reorg.c for the JUMP_LABEL changes.

One of the nastiest problems I ran into is that various RTL-level CFG
functions interpret a branch target of NULL to be the exit block, and
create branches using "return". This needed surgery to distinguish
between return and simple_return exits. JUMP_LABEL is now set and
maintained for return jumps.

A possible future enhancement is to add a targetm.gen_epilogue hook,
rather than using instruction patterns, and use that to pass information
about the set of registers that need to be saved. Epilogues for
tail-calls can be generated in multiple places, and it isn't always
necessary to restore the entire set of registers.

The patch has been in our local tree as well as the Linaro gcc tree for
a while now. That hasn't entirely been without pain, but most of the
issues we had should be ironed out by now. For this submission, I've
rested the patch (in some cases slightly earlier versions) on arm-linux,
mips64-elf and i686-linux (the latter including bootstraps).


Bernd