gimple-loop-interchange.cc File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "is-a.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "fold-const.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
#include "cfgloop.h"
#include "tree-ssa.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-dce.h"
#include "tree-data-ref.h"
#include "tree-vectorizer.h"

Include dependency graph for gimple-loop-interchange.cc:

Data Structures
struct	induction
struct	reduction
class	loop_cand
class	tree_loop_interchange

Macros
#define	MAX_NUM_STMT   (param_loop_interchange_max_num_stmts)
#define	MAX_DATAREFS   (param_loop_max_datarefs_for_datadeps)
#define	OUTER_STRIDE_RATIO   (param_loop_interchange_stride_ratio)
#define	INNER_STRIDE_RATIO   ((OUTER_STRIDE_RATIO) + 1)
#define	STMT_COST_RATIO   (3)
#define	DR_ACCESS_STRIDE(dr)   ((vec<tree> *) dr->aux)

Typedefs
typedef struct induction *	induction_p
typedef struct reduction *	reduction_p

Enumerations
enum	reduction_type { UNKNOWN_RTYPE = 0 , SIMPLE_RTYPE , DOUBLE_RTYPE }

Functions
static void	dump_reduction (reduction_p re)
static void	dump_induction (class loop *loop, induction_p iv)
static gimple *	single_use_in_loop (tree var, class loop *loop)
static bool	unsupported_edge (edge e)
static void	find_deps_in_bb_for_stmt (gimple_seq *stmts, basic_block bb, gimple *consumer)
static void	free_data_refs_with_aux (vec< data_reference_p > datarefs)
static void	compute_access_stride (class loop *&loop_nest, class loop *loop, data_reference_p dr)
static class loop *	compute_access_strides (class loop *loop_nest, class loop *loop, vec< data_reference_p > datarefs)
static void	prune_access_strides_not_in_loop (class loop *loop_nest, class loop *innermost, vec< data_reference_p > datarefs)
static void	dump_access_strides (vec< data_reference_p > datarefs)
static bool	should_interchange_loops (unsigned i_idx, unsigned o_idx, vec< data_reference_p > datarefs, unsigned i_stmt_cost, unsigned o_stmt_cost, bool innermost_loops_p, bool dump_info_p=true)
gimple_opt_pass *	make_pass_linterchange (gcc::context *ctxt)

Macro Definition Documentation

DR_ACCESS_STRIDE

#define DR_ACCESS_STRIDE

(

dr

)

((vec<tree> *) dr->aux)

Vector of strides that DR accesses in each level loop of a loop nest.   

Referenced by compute_access_strides(), dump_access_strides(), free_data_refs_with_aux(), prune_access_strides_not_in_loop(), should_interchange_loops(), and tree_loop_interchange::update_data_info().

INNER_STRIDE_RATIO

#define INNER_STRIDE_RATIO   ((OUTER_STRIDE_RATIO) + 1)

The same as above, but we require higher ratio for interchanging the
innermost two loops.   

Referenced by should_interchange_loops().

MAX_DATAREFS

#define MAX_DATAREFS   (param_loop_max_datarefs_for_datadeps)

Maximum number of data references in loop nest.   

MAX_NUM_STMT

#define MAX_NUM_STMT   (param_loop_interchange_max_num_stmts)

Loop interchange.
   Copyright (C) 2017-2024 Free Software Foundation, Inc.
   Contributed by ARM Ltd.

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

This pass performs loop interchange: for example, the loop nest

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

is transformed to

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

This pass implements loop interchange in the following steps:

  1) Find perfect loop nest for each innermost loop and compute data
     dependence relations for it.  For above example, loop nest is
     <loop_j, loop_k, loop_i>.
  2) From innermost to outermost loop, this pass tries to interchange
     each loop pair.  For above case, it firstly tries to interchange
     <loop_k, loop_i> and loop nest becomes <loop_j, loop_i, loop_k>.
     Then it tries to interchange <loop_j, loop_i> and loop nest becomes
     <loop_i, loop_j, loop_k>.  The overall effect is to move innermost
     loop to the outermost position.  For loop pair <loop_i, loop_j>
     to be interchanged, we:
  3) Check if data dependence relations are valid for loop interchange.
  4) Check if both loops can be interchanged in terms of transformation.
  5) Check if interchanging the two loops is profitable.
  6) Interchange the two loops by mapping induction variables.

This pass also handles reductions in loop nest.  So far we only support
simple reduction of inner loop and double reduction of the loop nest.   

Maximum number of stmts in each loop that should be interchanged.   

Referenced by loop_cand::can_interchange_p().

OUTER_STRIDE_RATIO

#define OUTER_STRIDE_RATIO   (param_loop_interchange_stride_ratio)

Comparison ratio of access stride between inner/outer loops to be
interchanged.  This is the minimum stride ratio for loop interchange
to be profitable.   

Referenced by should_interchange_loops().

STMT_COST_RATIO

#define STMT_COST_RATIO   (3)

Comparison ratio of stmt cost between inner/outer loops.  Loops won't
be interchanged if outer loop has too many stmts.   

Referenced by should_interchange_loops().

Typedef Documentation

induction_p

typedef struct induction * induction_p

Structure recording loop induction variable.   

reduction_p

typedef struct reduction * reduction_p

Structure recording loop reduction variable.   

Enumeration Type Documentation

reduction_type

enum reduction_type

Enum type for loop reduction variable.   

Enumerator
UNKNOWN_RTYPE
SIMPLE_RTYPE
DOUBLE_RTYPE

Function Documentation

compute_access_stride()

static void compute_access_stride ( class loop *& loop_nest, class loop * loop, data_reference_p dr )

static

Given data reference DR in LOOP_NEST, the function computes DR's access
stride at each level of loop from innermost LOOP to outer.  On success,
it saves access stride at each level loop in a vector which is pointed
by DR->aux.  For example:

  int arr[100][100][100];
  for (i = 0; i < 100; i++)       ;(DR->aux)strides[0] = 40000
    for (j = 100; j > 0; j--)     ;(DR->aux)strides[1] = 400
      for (k = 0; k < 100; k++)   ;(DR->aux)strides[2] = 4
        arr[i][j - 1][k] = 0;   

References analyze_scalar_evolution(), data_reference::aux, build3(), build_fold_addr_expr, build_int_cst(), chrec_contains_undetermined(), CHREC_LEFT, CHREC_RIGHT, DECL_BIT_FIELD, DECL_BIT_FIELD_REPRESENTATIVE, DR_REF, DR_STMT, flow_bb_inside_loop_p(), gcc_assert, get_chrec_loop(), ggc_alloc(), gimple_bb(), loop::inner, instantiate_scev(), basic_block_def::loop_father, loop_outer(), loop_preheader_edge(), NULL, NULL_TREE, size_int, sizetype, sl, TREE_CODE, tree_contains_chrecs(), TREE_OPERAND, and TREE_TYPE.

Referenced by compute_access_strides().

compute_access_strides()

static class loop * compute_access_strides ( class loop * loop_nest, class loop * loop, vec< data_reference_p > datarefs )

static

Given loop nest LOOP_NEST with innermost LOOP, the function computes
access strides with respect to each level loop for all data refs in
DATAREFS from inner loop to outer loop.  On success, it returns the
outermost loop that access strides can be computed successfully for
all data references.  If access strides cannot be computed at least
for two levels of loop for any data reference, it returns NULL.   

References compute_access_stride(), DR_ACCESS_STRIDE, flow_loop_nested_p(), gcc_assert, ggc_alloc(), i, loop_depth(), NULL, and superloop_at_depth().

dump_access_strides()

static void dump_access_strides ( vec< data_reference_p > datarefs )

static

Dump access strides for all DATAREFS.   

References DR_ACCESS_STRIDE, DR_REF, dump_file, ggc_alloc(), i, print_generic_expr(), and TDF_SLIM.

dump_induction()

static void dump_induction ( class loop * loop, induction_p iv )

static

Dump LOOP's induction IV.   

References dump_file, ggc_alloc(), loop::num, print_generic_expr(), iv::step, and TDF_SLIM.

Referenced by loop_cand::analyze_induction_var().

dump_reduction()

static void dump_reduction ( reduction_p re )

static

Dump reduction RE.   

References DOUBLE_RTYPE, dump_file, ggc_alloc(), print_gimple_stmt(), and SIMPLE_RTYPE.

Referenced by loop_cand::analyze_iloop_reduction_var(), and loop_cand::analyze_oloop_reduction_var().

find_deps_in_bb_for_stmt()

static void find_deps_in_bb_for_stmt ( gimple_seq * stmts, basic_block bb, gimple * consumer )

static

CONSUMER is a stmt in BB storing reduction result into memory object.
When the reduction is intialized from constant value, we need to add
a stmt loading from the memory object to target basic block in inner
loop during undoing the reduction.  Problem is that memory reference
may use ssa variables not dominating the target basic block.  This
function finds all stmts on which CONSUMER depends in basic block BB,
records and returns them via STMTS.   

References FOR_EACH_SSA_USE_OPERAND, GF_PLF_1, ggc_alloc(), gimple_bb(), gimple_plf(), gimple_seq_add_stmt_without_update(), gimple_set_plf(), gsi_end_p(), gsi_next(), gsi_next_nondebug(), gsi_remove(), gsi_start_bb(), gsi_start_nondebug_bb(), gsi_stmt(), SSA_NAME_DEF_STMT, SSA_OP_USE, USE_FROM_PTR, and worklist.

Referenced by loop_cand::undo_simple_reduction().

free_data_refs_with_aux()

static void free_data_refs_with_aux ( vec< data_reference_p > datarefs )

static

Free DATAREFS and its auxiliary memory.   

References data_reference::aux, DR_ACCESS_STRIDE, free_data_refs(), i, and NULL.

make_pass_linterchange()

gimple_opt_pass * make_pass_linterchange

(

gcc::context *

ctxt

)

References ggc_alloc().

prune_access_strides_not_in_loop()

static void prune_access_strides_not_in_loop ( class loop * loop_nest, class loop * innermost, vec< data_reference_p > datarefs )

static

Prune access strides for data references in DATAREFS by removing strides
of loops that isn't in current LOOP_NEST.   

References DR_ACCESS_STRIDE, gcc_assert, ggc_alloc(), i, and loop_depth().

should_interchange_loops()

static bool should_interchange_loops ( unsigned i_idx, unsigned o_idx, vec< data_reference_p > datarefs, unsigned i_stmt_cost, unsigned o_stmt_cost, bool innermost_loops_p, bool dump_info_p = true )

static

Return true if it's profitable to interchange two loops whose index
in whole loop nest vector are I_IDX/O_IDX respectively.  The function
computes and compares three types information from all DATAREFS:
  1) Access stride for loop I_IDX and O_IDX.
  2) Number of invariant memory references with respect to I_IDX before
     and after loop interchange.
  3) Flags indicating if all memory references access sequential memory
     in ILOOP, before and after loop interchange.
If INNMOST_LOOP_P is true, the two loops for interchanging are the two
innermost loops in loop nest.  This function also dumps information if
DUMP_INFO_P is true.   

References wi::add(), DR_ACCESS_STRIDE, DR_REF, dump_file, dump_flags, ggc_alloc(), wi::gtu_p(), i, INNER_STRIDE_RATIO, integer_zerop(), wi::mul(), multiple_of_p(), operand_equal_p(), OUTER_STRIDE_RATIO, print_decu(), STMT_COST_RATIO, TDF_DETAILS, wi::to_widest(), TREE_CODE, TREE_TYPE, and TYPE_SIZE_UNIT.

Referenced by tree_loop_interchange::interchange().

single_use_in_loop()

static gimple * single_use_in_loop ( tree var, class loop * loop )

static

Return single use stmt of VAR in LOOP, otherwise return NULL.   

References flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_FAST, ggc_alloc(), gimple_bb(), is_gimple_debug(), NULL, and USE_STMT.

Referenced by loop_cand::can_interchange_p(), and loop_cand::classify_simple_reduction().

unsupported_edge()

static bool unsupported_edge ( edge e )

inlinestatic

Return true if E is unsupported in loop interchange, i.e, E is a complex
edge or part of irreducible loop.   

References EDGE_COMPLEX, and ggc_alloc().