GCC Middle and Back End API Reference
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)
 

Typedefs

typedef struct inductioninduction_p
 
typedef struct reductionreduction_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 gimplesingle_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 loopcompute_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_passmake_pass_linterchange (gcc::context *ctxt)
 

Macro Definition Documentation

◆ DR_ACCESS_STRIDE

#define DR_ACCESS_STRIDE ( dr)
Value:
((vec<tree> *) dr->aux)
Definition vec.h:450
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 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(), 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, 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, 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, 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

◆ 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, 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(), is_a(), 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)

◆ 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, 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, 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, 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.