Functions
static basic_block	find_bb_for_arg ()
static bool	all_immediate_uses_same_place ()
static basic_block	nearest_common_dominator_of_uses ()
static basic_block	select_best_block (basic_block early_bb, basic_block late_bb, gimple stmt)
static bool	statement_sink_location (gimple stmt, basic_block frombb, gimple_stmt_iterator *togsi)
static void	sink_code_in_bb ()
static void	execute_sink_code ()
static unsigned int	do_sink ()
static bool	gate_sink ()
gimple_opt_pass *	make_pass_sink_code ()

Variables
struct {
int sunk
}	sink_stats

Function Documentation

static bool all_immediate_uses_same_place ( )

static

When the first immediate use is in a statement, then return true if all
   immediate uses in IMM are in the same statement.
   We could also do the case where  the first immediate use is in a phi node,
   and all the other uses are in phis in the same basic block, but this
   requires some expensive checking later (you have to make sure no def/vdef
   in the statement occurs for multiple edges in the various phi nodes it's
   used in, so that you only have one place you can sink it to.

References is_gimple_debug().

Referenced by statement_sink_location().

static unsigned int do_sink ( )

static

Gate and execute functions for PRE.

References execute_sink_code().

static void execute_sink_code ( )

static

Perform code sinking.
   This moves code down the flowgraph when we know it would be
   profitable to do so, or it wouldn't increase the number of
   executions of the statement.

   IE given

   a_1 = b + c;
   if (<something>)
   {
   }
   else
   {
     foo (&b, &c);
     a_5 = b + c;
   }
   a_6 = PHI (a_5, a_1);
   USE a_6.

   we'll transform this into:

   if (<something>)
   {
      a_1 = b + c;
   }
   else
   {
      foo (&b, &c);
      a_5 = b + c;
   }
   a_6 = PHI (a_5, a_1);
   USE a_6.

   Note that this reduces the number of computations of a = b + c to 1
   when we take the else edge, instead of 2.

References calculate_dominance_info(), CDI_DOMINATORS, CDI_POST_DOMINATORS, cfun, connect_infinite_loops_to_exit(), free_dominance_info(), loop_optimizer_finalize(), loop_optimizer_init(), memset(), remove_fake_exit_edges(), sink_code_in_bb(), sink_stats, and statistics_counter_event().

Referenced by do_sink().

static basic_block find_bb_for_arg ( )

static

Given a PHI, and one of its arguments (DEF), find the edge for
   that argument and return it.  If the argument occurs twice in the PHI node,
   we return NULL.

References gimple_phi_arg_edge(), gimple_phi_num_args(), and edge_def::src.

Referenced by statement_sink_location().

static bool gate_sink ( )

static

gimple_opt_pass* make_pass_sink_code ( )

static basic_block nearest_common_dominator_of_uses ( )

static

Find the nearest common dominator of all of the immediate uses in IMM.

References bitmap_clear(), bitmap_first_set_bit(), bitmap_set_bit(), CDI_DOMINATORS, gimple_bb(), gimple_phi_arg_edge(), basic_block_def::index, is_gimple_debug(), nearest_common_dominator(), and edge_def::src.

Referenced by statement_sink_location().

static basic_block select_best_block	(	basic_block	early_bb,
		basic_block	late_bb,
		gimple	stmt
	)

static

Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
   tree, return the best basic block between them (inclusive) to place
   statements.

   We want the most control dependent block in the shallowest loop nest.

   If the resulting block is in a shallower loop nest, then use it.  Else
   only use the resulting block if it has significantly lower execution
   frequency than EARLY_BB to avoid gratutious statement movement.  We
   consider statements with VOPS more desirable to move.

   This pass would obviously benefit from PDO as it utilizes block
   frequencies.  It would also benefit from recomputing frequencies
   if profile data is not available since frequencies often get out
   of sync with reality.

References bb_loop_depth(), CDI_DOMINATORS, basic_block_def::frequency, get_immediate_dominator(), gimple_vdef(), and gimple_vuse().

Referenced by statement_sink_location().

static void sink_code_in_bb ( )

static

Perform code sinking on BB

References CDI_DOMINATORS, CDI_POST_DOMINATORS, dump_file, first_dom_son(), edge_def::flags, gimple_vdef(), gimple_vuse(), gsi_bb(), gsi_end_p(), gsi_last_bb(), gsi_move_before(), gsi_move_to_bb_end(), gsi_prev(), gsi_stmt(), basic_block_def::index, last, next_dom_son(), print_gimple_stmt(), sink_stats, statement_sink_location(), and basic_block_def::succs.

Referenced by execute_sink_code().

static bool statement_sink_location	(	gimple	stmt,
		basic_block	frombb,
		gimple_stmt_iterator *	togsi
	)

static

Given a statement (STMT) and the basic block it is currently in (FROMBB),
   determine the location to sink the statement to, if any.
   Returns true if there is such location; in that case, TOGSI points to the
   statement before that STMT should be moved.

References all_immediate_uses_same_place(), CDI_DOMINATORS, cfun, dominated_by_p(), empty_block_p(), find_bb_for_arg(), gimple_assign_lhs(), gimple_bb(), gimple_get_lhs(), gimple_has_lhs(), gimple_has_side_effects(), gimple_has_volatile_ops(), gimple_vdef(), gimple_vuse(), gsi_after_labels(), gsi_for_stmt(), function::has_local_explicit_reg_vars, has_zero_uses(), is_gimple_assign(), is_gimple_debug(), loop::latch, basic_block_def::loop_father, nearest_common_dominator_of_uses(), operand_equal_p(), ref_maybe_used_by_stmt_p(), select_best_block(), single_ssa_def_operand(), stmt_ends_bb_p(), and stmt_kills_ref_p().

Referenced by sink_code_in_bb().

Variable Documentation

struct { ... } sink_stats

@verbatim Code sinking for trees

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

TODO:
   1. Sinking store only using scalar promotion (IE without moving the RHS):

   *q = p;
   p = p + 1;
   if (something)
     *q = <not p>;
   else
     y = *q;


   should become
   sinktemp = p;
   p = p + 1;
   if (something)
     *q = <not p>;
   else
   {
     *q = sinktemp;
     y = *q
   }
   Store copy propagation will take care of the store elimination above.


   2. Sinking using Partial Dead Code Elimination.

Referenced by execute_sink_code(), and sink_code_in_bb().

int sunk

Functions

Variables

Function Documentation

Variable Documentation