tree_loop_interchange Class Reference

Collaboration diagram for tree_loop_interchange:

Public Member Functions
	tree_loop_interchange (vec< class loop * > loop_nest)
	~tree_loop_interchange ()
bool	interchange (vec< data_reference_p >, vec< ddr_p >)

Private Member Functions
void	update_data_info (unsigned, unsigned, vec< data_reference_p >, vec< ddr_p >)
bool	valid_data_dependences (unsigned, unsigned, vec< ddr_p >)
void	interchange_loops (loop_cand &, loop_cand &)
void	map_inductions_to_loop (loop_cand &, loop_cand &)
void	move_code_to_inner_loop (class loop *, class loop *, basic_block *)

Private Attributes
vec< class loop * >	m_loop_nest
tree	m_niters_iv_var
bitmap	m_dce_seeds

Detailed Description

Class for loop interchange transformation.   

Constructor & Destructor Documentation

tree_loop_interchange()

tree_loop_interchange::tree_loop_interchange ( vec< class loop * > loop_nest )

inline

~tree_loop_interchange()

tree_loop_interchange::~tree_loop_interchange ( )

inline

References BITMAP_FREE, and m_dce_seeds.

Member Function Documentation

interchange()

bool tree_loop_interchange::interchange	(	vec< data_reference_p >	datarefs,
		vec< ddr_p >	ddrs )

Try to interchange inner loop of a loop nest to outer level.   

References dump_enabled_p(), dump_file, dump_flags, dump_printf_loc(), find_loop_location(), ggc_alloc(), i, interchange_loops(), m_dce_seeds, m_loop_nest, MSG_OPTIMIZED_LOCATIONS, NULL, should_interchange_loops(), simple_dce_from_worklist(), stmt_cost(), TDF_DETAILS, update_data_info(), and valid_data_dependences().

interchange_loops()

void tree_loop_interchange::interchange_loops ( loop_cand & iloop, loop_cand & oloop )

private

Interchange two loops specified by ILOOP and OLOOP.   

References analyze_scalar_evolution(), bitmap_set_bit, create_canonical_iv(), DOUBLE_RTYPE, force_gimple_operand_gsi(), free_numbers_of_iterations_estimates(), gcc_assert, ggc_alloc(), GSI_CONTINUE_LINKING, gsi_last_bb(), i, instantiate_scev(), loop_outer(), loop_preheader_edge(), m_dce_seeds, m_loop_nest, m_niters_iv_var, map_inductions_to_loop(), move_code_to_inner_loop(), NULL, NULL_TREE, number_of_latch_executions(), reset_debug_uses(), scev_reset_htab(), SSA_NAME_DEF_STMT, SSA_NAME_VERSION, and unshare_expr().

Referenced by interchange().

map_inductions_to_loop()

void tree_loop_interchange::map_inductions_to_loop ( loop_cand & src, loop_cand & tgt )

private

Map induction variables of SRC loop to TGT loop.  The function firstly
creates the same IV of SRC loop in TGT loop, then deletes the original
IV and re-initialize it using the newly created IV.  For example, loop
nest:

  for (i = 0; i < N; i++)
    for (j = 0; j < M; j++)
      {
        //use of i;
        //use of j;
      }

will be transformed into:

  for (jj = 0; jj < M; jj++)
    for (ii = 0; ii < N; ii++)
      {
        //use of ii;
        //use of jj;
      }

after loop interchange.   

References bitmap_set_bit, create_iv(), FOR_EACH_IMM_USE_ON_STMT, FOR_EACH_IMM_USE_STMT, FOR_EACH_PHI_OR_STMT_USE, gcc_assert, ggc_alloc(), gsi_for_stmt(), gsi_last_bb(), i, m_dce_seeds, loop_cand::m_inductions, m_niters_iv_var, remove_phi_node(), SET_USE, SSA_NAME_DEF_STMT, SSA_NAME_IS_DEFAULT_DEF, SSA_NAME_VAR, SSA_NAME_VERSION, SSA_OP_USE, iv::step, TREE_CODE, unshare_expr(), update_stmt(), and USE_FROM_PTR.

Referenced by interchange_loops().

move_code_to_inner_loop()

void tree_loop_interchange::move_code_to_inner_loop ( class loop * outer, class loop * inner, basic_block * outer_bbs )

private

Move stmts of outer loop to inner loop.   

References flow_bb_inside_loop_p(), ggc_alloc(), gimple_set_vdef(), gimple_set_vuse(), gimple_vdef(), gimple_vuse(), gsi_after_labels(), gsi_end_p(), gsi_last_bb(), gsi_move_before(), gsi_next(), gsi_stmt(), loop::header, i, loop::latch, NULL_TREE, loop::num_nodes, release_ssa_name(), reset_debug_uses(), single_exit(), unlink_stmt_vdef(), and update_stmt().

Referenced by interchange_loops().

update_data_info()

void tree_loop_interchange::update_data_info ( unsigned i_idx, unsigned o_idx, vec< data_reference_p > datarefs, vec< ddr_p > ddrs )

private

Update data refs' access stride and dependence information after loop
interchange.  I_IDX/O_IDX gives indices of interchanged loops in loop
nest.  DATAREFS are data references.  DDRS are data dependences.   

References chrec_known, DDR_ARE_DEPENDENT, DDR_DIST_VECT, DDR_NUM_DIST_VECTS, DR_ACCESS_STRIDE, gcc_assert, ggc_alloc(), and i.

Referenced by interchange().

valid_data_dependences()

bool tree_loop_interchange::valid_data_dependences ( unsigned i_idx, unsigned o_idx, vec< ddr_p > ddrs )

private

Check data dependence relations, return TRUE if it's valid to interchange
two loops specified by I_IDX/O_IDX.  Theoretically, interchanging the two
loops is valid only if dist vector, after interchanging, doesn't have '>'
as the leftmost non-'=' direction.  Practically, this function have been
conservative here by not checking some valid cases.   

References chrec_known, DDR_ARE_DEPENDENT, DDR_DIST_VECT, DDR_NUM_DIST_VECTS, DDR_REVERSED_P, dependence_level(), ggc_alloc(), i, and m_loop_nest.

Referenced by interchange().

Field Documentation

m_dce_seeds

bitmap tree_loop_interchange::m_dce_seeds

private

Referenced by interchange(), interchange_loops(), map_inductions_to_loop(), and ~tree_loop_interchange().

m_loop_nest

vec<class loop *> tree_loop_interchange::m_loop_nest

private

Referenced by interchange(), interchange_loops(), and valid_data_dependences().

m_niters_iv_var

tree tree_loop_interchange::m_niters_iv_var

private

Referenced by interchange_loops(), and map_inductions_to_loop().

---

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

• gimple-loop-interchange.cc