GCC Middle and Back End API Reference
loop_cand Class Reference
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 loopm_loop
class loopm_outer
vec< induction_pm_inductions
vec< reduction_pm_reductions
vec< gphi * > m_lcssa_nodes
edge m_exit
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 )

References m_inductions, m_lcssa_nodes, and m_reductions.

◆ ~loop_cand()

loop_cand::~loop_cand ( )

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

Member Function Documentation

◆ analyze_carried_vars()

◆ analyze_iloop_reduction_var()

◆ analyze_induction_var()

◆ 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().

Referenced by tree_loop_interchange::interchange().

◆ 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 as_a(), DOUBLE_RTYPE, dump_file, dump_flags, dump_reduction(), dyn_cast(), flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_FAST, gimple_bb(), i, reduction::init, is_gimple_debug(), reduction::lcssa_phi, loop_latch_edge(), loop_preheader_edge(), m_exit, m_loop, m_reductions, NULL, operand_equal_p(), reduction::phi, PHI_ARG_DEF_FROM_EDGE, reduction::producer, single_imm_use(), SSA_NAME_DEF_STMT, TDF_DETAILS, TREE_CODE, reduction::type, UNKNOWN_RTYPE, and USE_STMT.

Referenced by analyze_carried_vars().

◆ can_interchange_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

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

Referenced by analyze_lcssa_phis(), and can_interchange_p().

◆ 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
    var = phi<init, next>
    next = var op ...
  reduc_sum = phi<next>
  MEM_REF[idx] = reduc_sum              //consumer

is transformed into:

    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:

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

Referenced by tree_loop_interchange::interchange_loops().

Field Documentation

◆ m_bbs

◆ m_const_init_reduc

int loop_cand::m_const_init_reduc

◆ m_exit

◆ m_inductions

◆ m_lcssa_nodes

vec<gphi *> loop_cand::m_lcssa_nodes

◆ m_loop

◆ m_num_stmts

int loop_cand::m_num_stmts

◆ m_outer

class loop* loop_cand::m_outer

◆ m_reductions

The documentation for this class was generated from the following file: