GCC Middle and Back End API Reference
same_succ_def Struct Reference
Collaboration diagram for same_succ_def:

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@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.


   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)
       = (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>;
       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>;
       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),
     # 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.


   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.


   1. The pass first determines all groups of blocks with the same successor
   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.


   - 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.

   This 'pass' is not a stand-alone gimple pass, but runs as part of
   pass_pre, in order to share the value numbering.


   - 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

int same_succ_def::equal ( const value_type e1,
const compare_type e2 
hashval_t same_succ_def::hash ( const value_type e)
   hash routine for hash_table support, returns hashval of E.  
void same_succ_def::remove ( value_type )
   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
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: