Collaboration diagram for loop_cand:

Public Member Functions
	loop_cand (class loop , class loop )

	~loop_cand ()

reduction_p	find_reduction_by_stmt (gimple *)

void	classify_simple_reduction (reduction_p)

bool	analyze_iloop_reduction_var (tree)

bool	analyze_oloop_reduction_var (loop_cand *, tree)

bool	analyze_induction_var (tree, tree)

bool	analyze_carried_vars (loop_cand *)

bool	analyze_lcssa_phis (void)

bool	can_interchange_p (loop_cand *)

void	undo_simple_reduction (reduction_p, bitmap)

Data Fields
class loop *	m_loop

class loop *	m_outer

vec< induction_p >	m_inductions

vec< reduction_p >	m_reductions

vec< gphi * >	m_lcssa_nodes

edge	m_exit

basic_block *	m_bbs

int	m_num_stmts

int	m_const_init_reduc

Detailed Description

Loop candidate for interchange.

Constructor & Destructor Documentation

◆ loop_cand()

loop_cand::loop_cand	(	class loop *	loop,
		class loop *	outer )

Constructor.

References m_inductions, m_lcssa_nodes, and m_reductions.

◆ ~loop_cand()

loop_cand::~loop_cand ( )

Destructor.

References free(), i, m_bbs, m_inductions, m_lcssa_nodes, and m_reductions.

Member Function Documentation

◆ analyze_carried_vars()

bool loop_cand::analyze_carried_vars ( loop_cand * iloop )

Return true if all loop carried variables defined in loop header can
be successfully analyzed.

References analyze_iloop_reduction_var(), analyze_induction_var(), analyze_oloop_reduction_var(), analyze_scalar_evolution(), chrec_contains_symbols_defined_in_loop(), chrec_contains_undetermined(), dump_file, dump_flags, ggc_alloc(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, instantiate_scev(), loop_preheader_edge(), m_loop, m_outer, loop::num, gphi_iterator::phi(), PHI_RESULT, TDF_DETAILS, and virtual_operand_p().

◆ analyze_iloop_reduction_var()

bool loop_cand::analyze_iloop_reduction_var ( tree var )

Analyze reduction variable VAR for inner loop of the loop nest to be
interchanged.  Return true if analysis succeeds.

References associative_tree_code(), check_reduction_path(), classify_simple_reduction(), dump_file, dump_flags, dump_reduction(), FLOAT_TYPE_P, flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_FAST, ggc_alloc(), gimple_assign_rhs1_ptr(), gimple_assign_rhs_code(), gimple_bb(), is_gimple_debug(), loop_latch_edge(), loop_preheader_edge(), m_exit, m_loop, m_reductions, NULL, PHI_ARG_DEF_FROM_EDGE, single_imm_use(), single_use(), SSA_NAME_DEF_STMT, TDF_DETAILS, TREE_CODE, TREE_TYPE, and USE_STMT.

Referenced by analyze_carried_vars().

◆ analyze_induction_var()

bool loop_cand::analyze_induction_var	(	tree	var,
		tree	chrec )

Return true if VAR is induction variable of current loop whose scev is
specified by CHREC.

References build_zero_cst(), CHREC_LEFT, CHREC_RIGHT, CHREC_VARIABLE, dump_file, dump_flags, dump_induction(), ggc_alloc(), HONOR_SIGNED_ZEROS(), HONOR_SNANS(), loop_preheader_edge(), m_inductions, m_loop, NULL, loop::num, PHI_ARG_DEF_FROM_EDGE, SSA_NAME_DEF_STMT, iv::step, TDF_DETAILS, TREE_CODE, tree_contains_chrecs(), tree_does_not_contain_chrecs(), and TREE_TYPE.

Referenced by analyze_carried_vars().

◆ analyze_lcssa_phis()

bool loop_cand::analyze_lcssa_phis ( void )

Return TRUE if loop closed PHI nodes can be analyzed successfully.

References find_reduction_by_stmt(), gsi_end_p(), gsi_next(), gsi_start_phis(), m_exit, gphi_iterator::phi(), PHI_RESULT, and virtual_operand_p().

◆ analyze_oloop_reduction_var()

bool loop_cand::analyze_oloop_reduction_var	(	loop_cand *	iloop,
		tree	var )

Analyze reduction variable VAR for outer loop of the loop nest to be
interchanged.  ILOOP is not NULL and points to inner loop.  For the
moment, we only support double reduction for outer loop, like:

  for (int i = 0; i < n; i++)
    {
      int sum = 0;

      for (int j = 0; j < n; j++)    // outer loop
        for (int k = 0; k < n; k++)  // inner loop
          sum += a[i][k]*b[k][j];

      s[i] = sum;
    }

Note the innermost two loops are the loop nest to be interchanged.
Return true if analysis succeeds.

References DOUBLE_RTYPE, dump_file, dump_flags, dump_reduction(), flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_FAST, ggc_alloc(), gimple_bb(), i, is_gimple_debug(), loop_latch_edge(), loop_preheader_edge(), m_exit, m_loop, m_reductions, NULL, operand_equal_p(), PHI_ARG_DEF_FROM_EDGE, single_imm_use(), SSA_NAME_DEF_STMT, TDF_DETAILS, TREE_CODE, UNKNOWN_RTYPE, and USE_STMT.

Referenced by analyze_carried_vars().

◆ can_interchange_p()

bool loop_cand::can_interchange_p ( loop_cand * iloop )

Return true if current loop_cand be interchanged.  ILOOP is not NULL if
current loop_cand is outer loop in loop nest.

References ggc_alloc(), gimple_assign_lhs(), gimple_assign_single_p(), gimple_has_side_effects(), gimple_inexpensive_call_p(), gimple_vuse(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), loop::header, i, loop::inner, is_gimple_debug(), basic_block_def::loop_father, m_bbs, m_lcssa_nodes, m_loop, m_num_stmts, m_reductions, MAX_NUM_STMT, NULL, NULL_TREE, loop::num_nodes, gphi_iterator::phi(), PHI_RESULT, single_use_in_loop(), TREE_CODE, UNKNOWN_RTYPE, and virtual_operand_p().

◆ classify_simple_reduction()

void loop_cand::classify_simple_reduction ( reduction_p re )

Programmers and optimizers (like loop store motion) may optimize code:

  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      a[i] += b[j][i] * c[j][i];

into reduction:

  for (int i = 0; i < N; i++)
    {
      // producer.  Note sum can be intitialized to a constant.
      int sum = a[i];
      for (int j = 0; j < N; j++)
        {
          sum += b[j][i] * c[j][i];
        }
      // consumer.
      a[i] = sum;
    }

The result code can't be interchanged without undoing the optimization.
This function classifies this kind reduction and records information so
that we can undo the store motion during interchange.

References CONSTANT_CLASS_P, gcc_assert, gimple_assign_load_p(), gimple_assign_rhs1(), gimple_bb(), gimple_get_lhs(), gimple_store_p(), basic_block_def::loop_father, m_const_init_reduc, m_outer, operand_equal_p(), PHI_RESULT, SIMPLE_RTYPE, single_use_in_loop(), SSA_NAME_DEF_STMT, TREE_CODE, and unshare_expr().

Referenced by analyze_iloop_reduction_var().

◆ find_reduction_by_stmt()

reduction_p loop_cand::find_reduction_by_stmt ( gimple * stmt )

Return the reduction if STMT is one of its lcssa PHI, producer or consumer
stmt.

References ggc_alloc(), i, m_reductions, and NULL.

Referenced by analyze_lcssa_phis().

◆ undo_simple_reduction()

void loop_cand::undo_simple_reduction	(	reduction_p	re,
		bitmap	dce_seeds )

User can write, optimizers can generate simple reduction RE for inner
loop.  In order to make interchange valid, we have to undo reduction by
moving producer and consumer stmts into the inner loop.  For example,
below code:

  init = MEM_REF[idx];          //producer
  loop:
    var = phi<init, next>
    next = var op ...
  reduc_sum = phi<next>
  MEM_REF[idx] = reduc_sum              //consumer

is transformed into:

  loop:
    new_var = MEM_REF[idx];             //producer after moving
    next = new_var op ...
    MEM_REF[idx] = next;                //consumer after moving

Note if the reduction variable is initialized to constant, like:

  var = phi<0.0, next>

we compute new_var as below:

  loop:
    tmp = MEM_REF[idx];
    new_var = !first_iteration ? tmp : 0.0;

so that the initial const is used in the first iteration of loop.  Also
record ssa variables for dead code elimination in DCE_SEEDS.

References bitmap_set_bit, boolean_type_node, copy_ssa_name(), find_deps_in_bb_for_stmt(), FOR_EACH_IMM_USE_ON_STMT, FOR_EACH_IMM_USE_STMT, ggc_alloc(), gimple_assign_set_rhs1(), gimple_bb(), gimple_build_assign(), gimple_seq_add_stmt_without_update(), gimple_set_vdef(), gimple_set_vuse(), gimple_vdef(), gsi_after_labels(), gsi_for_stmt(), gsi_insert_seq_before(), gsi_move_after(), gsi_remove(), GSI_SAME_STMT, loop::header, m_inductions, m_loop, make_ssa_name(), NULL, NULL_TREE, PHI_RESULT, release_ssa_name(), SET_USE, SSA_NAME_DEF_STMT, SSA_NAME_VERSION, unlink_stmt_vdef(), and update_stmt().