@verbatim
Tail merging for gimple. Copyright (C) 2011-2013 Free Software Foundation, Inc. Contributed by Tom de Vries (tom@c.nosp@m.odes.nosp@m.ource.nosp@m.ry.c.nosp@m.om)
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.
Pass overview.
MOTIVATIONAL EXAMPLE
gimple representation of gcc/testsuite/gcc.dg/pr43864.c at
hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
{
struct FILED.1638 * fpD.2605;
charD.1 fileNameD.2604[1000];
intD.0 D.3915;
const charD.1 * restrict outputFileName.0D.3914;
# BLOCK 2 freq:10000
# PRED: ENTRY [100.0%] (fallthru,exec)
# PT = nonlocal { D.3926 } (restr)
outputFileName.0D.3914_3
= (const charD.1 * restrict) outputFileNameD.2600_2(D);
# .MEMD.3923_13 = VDEF <.MEMD.3923_12(D)>
# USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
# CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
sprintfD.759 (&fileNameD.2604, outputFileName.0D.3914_3);
# .MEMD.3923_14 = VDEF <.MEMD.3923_13>
# USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
# CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
D.3915_4 = accessD.2606 (&fileNameD.2604, 1);
if (D.3915_4 == 0)
goto <bb 3>;
else
goto <bb 4>;
# SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec)
# BLOCK 3 freq:1000
# PRED: 2 [10.0%] (true,exec)
# .MEMD.3923_15 = VDEF <.MEMD.3923_14>
# USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
# CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
freeD.898 (ctxD.2601_5(D));
goto <bb 7>;
# SUCC: 7 [100.0%] (fallthru,exec)
# BLOCK 4 freq:9000
# PRED: 2 [90.0%] (false,exec)
# .MEMD.3923_16 = VDEF <.MEMD.3923_14>
# PT = nonlocal escaped
# USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
# CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
fpD.2605_8 = fopenD.1805 (&fileNameD.2604[0], 0B);
if (fpD.2605_8 == 0B)
goto <bb 5>;
else
goto <bb 6>;
# SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec)
# BLOCK 5 freq:173
# PRED: 4 [1.9%] (true,exec)
# .MEMD.3923_17 = VDEF <.MEMD.3923_16>
# USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
# CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
freeD.898 (ctxD.2601_5(D));
goto <bb 7>;
# SUCC: 7 [100.0%] (fallthru,exec)
# BLOCK 6 freq:8827
# PRED: 4 [98.1%] (false,exec)
# .MEMD.3923_18 = VDEF <.MEMD.3923_16>
# USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
# CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
fooD.2599 (outputFileNameD.2600_2(D), fpD.2605_8);
# SUCC: 7 [100.0%] (fallthru,exec)
# BLOCK 7 freq:10000
# PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
6 [100.0%] (fallthru,exec)
# PT = nonlocal null
# ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)>
# .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5),
.MEMD.3923_18(6)>
# VUSE <.MEMD.3923_11>
return ctxD.2601_1;
# SUCC: EXIT [100.0%]
}
bb 3 and bb 5 can be merged. The blocks have different predecessors, but the
same successors, and the same operations.
CONTEXT
A technique called tail merging (or cross jumping) can fix the example
above. For a block, we look for common code at the end (the tail) of the
predecessor blocks, and insert jumps from one block to the other.
The example is a special case for tail merging, in that 2 whole blocks
can be merged, rather than just the end parts of it.
We currently only focus on whole block merging, so in that sense
calling this pass tail merge is a bit of a misnomer.
We distinguish 2 kinds of situations in which blocks can be merged:
- same operations, same predecessors. The successor edges coming from one
block are redirected to come from the other block.
- same operations, same successors. The predecessor edges entering one block
are redirected to enter the other block. Note that this operation might
involve introducing phi operations.
For efficient implementation, we would like to value numbers the blocks, and
have a comparison operator that tells us whether the blocks are equal.
Besides being runtime efficient, block value numbering should also abstract
from irrelevant differences in order of operations, much like normal value
numbering abstracts from irrelevant order of operations.
For the first situation (same_operations, same predecessors), normal value
numbering fits well. We can calculate a block value number based on the
value numbers of the defs and vdefs.
For the second situation (same operations, same successors), this approach
doesn't work so well. We can illustrate this using the example. The calls
to free use different vdefs: MEMD.3923_16 and MEMD.3923_14, and these will
remain different in value numbering, since they represent different memory
states. So the resulting vdefs of the frees will be different in value
numbering, so the block value numbers will be different.
The reason why we call the blocks equal is not because they define the same
values, but because uses in the blocks use (possibly different) defs in the
same way. To be able to detect this efficiently, we need to do some kind of
reverse value numbering, meaning number the uses rather than the defs, and
calculate a block value number based on the value number of the uses.
Ideally, a block comparison operator will also indicate which phis are needed
to merge the blocks.
For the moment, we don't do block value numbering, but we do insn-by-insn
matching, using scc value numbers to match operations with results, and
structural comparison otherwise, while ignoring vop mismatches.
IMPLEMENTATION
1. The pass first determines all groups of blocks with the same successor
blocks.
2. Within each group, it tries to determine clusters of equal basic blocks.
3. The clusters are applied.
4. The same successor groups are updated.
5. This process is repeated from 2 onwards, until no more changes.
LIMITATIONS/TODO
- block only
- handles only 'same operations, same successors'.
It handles same predecessors as a special subcase though.
- does not implement the reverse value numbering and block value numbering.
- improve memory allocation: use garbage collected memory, obstacks,
allocpools where appropriate.
- no insertion of gimple_reg phis, We only introduce vop-phis.
- handle blocks with gimple_reg phi_nodes.
PASS PLACEMENT
This 'pass' is not a stand-alone gimple pass, but runs as part of
pass_pre, in order to share the value numbering.
SWITCHES
- ftree-tail-merge. On at -O2. We may have to enable it only at -Os. Describes a group of bbs with the same successors. The successor bbs are
cached in succs, and the successor edge flags are cached in succ_flags.
If a bb has the EDGE_TRUE/VALSE_VALUE flags swapped compared to succ_flags,
it's marked in inverse.
Additionally, the hash value for the struct is cached in hashval, and
in_worklist indicates whether it's currently part of worklist.
