ifcvt cond_exec support rewrite

[Bernd Schmidt]

Our current cond_exec support in ifcvt is essentially limited to single
basic blocks. There is a mechanism to detect a sequence of && or ||
blocks, but it has a number of limitations:

- it requires backend support: IFCVT_MODIFY_MULTIPLE_TESTS, only
  present on FRV. See below on a question what to do about FRV.
- it does not support arbitrary if-statements, but only those with
  multiple test blocks all ending in one of a fixed choice of one
  then or one else block.
- the conditions it calculates are sometimes nonsensical

The last point may need explanation. Consider an "or_or" block,

if (cond1) goto then;
if (cond2) goto then;
if (cond3) goto else; [*]
then: stuff;
else: more stuff;

then we'd construct a predicate for the then block by twice going through
         f = gen_rtx_AND (GET_MODE (t), false_expr, f);
which comes out after the first time as (!cond1 && !cond2), correct for
the test block marked [*], but then the final result (!cond1 && !cond2
&& !cond3) isn't useful for anything.  Maybe frv.c adjusts for it -
difficult to tell from the code.

The following patch rewrites essentially all the cond_exec support in
ifcvt; reviewing is probably easier if it's thought of as new code. A
large overview comment is added to basic-block.h.

The motivation for it was a benchmark in a popular embedded testsuite
that probably mustn't be named, where we have the following inside a loop:

    7   9
   / \ / \
  6 - 8   \
 /     \   \
5       10  \
 \        \  |
  11 ------ 12

Modulo scheduling only works on fully if-converted loops, so we need to
flatten that to a single basic block. 5, 6 and 8 are the test blocks.
This implies the following code generation:

C5 = test5
[!C5] C6 = test6
[C5] C6 = 1;		[*]
[!C6] block 7
[!C5] C8 = test8
[C5] C8 = 1		[*]
[!C8] block 9
[C5] C8 = 0		[*]
[C8] block 10
[C5] block 11
block 12

The trick is to modify inner conditions based on outer ones; these extra
instructions are marked [*]. If we only had the blocks 5-8, we could
alternatively try to ensure that C5 and C6 use the same register, and
avoid the extra modification by just reusing the condition.

So, features of this patch:
- detect complicated if-block structures where then, else and join
  blocks may themselves be if blocks
- Rename condition registers so that they aren't clobbered in the
  predicated blocks, and so that conditions may be reused if
  possible
- rewrite condition registers in cases where reuse isn't possible
- support matching heads/tails in then and else blocks as before, but
  also within nested conditions (using the predicate from one level
  higher)

Unfortunately this no longer works on FRV, which needs special code to
move condition registers to predication registers. The problem I have is
that I've been unabled to find an instruction set manual for the chip
(there is a manual for something called FR, but that appears different),
and the code in frv.c is somewhat nontrivial. Experiments show that the
existing multi-if-block support isn't terribly effective on FRV;
before-after comparisons show that by turning it off, there are three
spots in gcc that are meaningfully changed, and below 20 in the C
benchmarks of SPEC2k.

FRV also doesn't build in mainline, and it looks as if it likely hasn't
in a while, so I haven't tried testing this patch on it. If no public
manual can be found, is it still my responsibility to keep this support
working, or can we put the burden on the FRV maintainers?

This patch was bootstrapped on ia64-linux; a slightly earlier version
was regression tested and had a random guality failure that goes away
with this one (gcc & g++ tested again). It's also been tested on c6x-elf
along the way (currently testing again for the latest version and
looking OK so far), and it's in our 4.5 c6x tree.

Comments, or approvals?


Bernd
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ifcvt0929a.diff
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20110929/31d72779/attachment.ksh>