Public Types | |
| typedef same_succ_def | value_type |
| typedef same_succ_def | compare_type |
Static Public Member Functions | |
| static hashval_t | hash (const value_type *) |
| static int | equal (const value_type *, const compare_type *) |
| static void | remove (value_type *) |
Data Fields | |
| bitmap | bbs |
| bitmap | succs |
| bitmap | inverse |
| vec< int > | succ_flags |
| bool | in_worklist |
| hashval_t | hashval |
Detailed Description
Tail merging for gimple. Copyright (C) 2011-2013 Free Software Foundation, Inc. Contributed by Tom de Vries (tom@codesourcery.com)
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
- The pass first determines all groups of blocks with the same successor blocks.
- Within each group, it tries to determine clusters of equal basic blocks.
- The clusters are applied.
- The same successor groups are updated.
- 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.
Member Typedef Documentation
hash_table support.
Member Function Documentation
|
static |
Compares SAME_SUCCs E1 and E2.
References gimple_call_same_target_p(), gsi_advance_fw_nondebug_nonlocal(), gsi_next_nondebug(), gsi_stmt(), and is_gimple_call().
|
inlinestatic |
hash routine for hash_table support, returns hashval of E.
|
static |
Delete same_succ E.
Field Documentation
| bitmap same_succ_def::bbs |
The bbs that have the same successor bbs.
| hashval_t same_succ_def::hashval |
The hash value of the struct.
| bool same_succ_def::in_worklist |
Indicates whether the struct is currently in the worklist.
| bitmap same_succ_def::inverse |
Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for bb.
| vec<int> same_succ_def::succ_flags |
The edge flags for each of the successor bbs.
| bitmap same_succ_def::succs |
The successor bbs.
Referenced by print_worklist().
The documentation for this struct was generated from the following file:
