GCC Middle and Back End API 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"
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 induction * | induction_p |
typedef struct reduction * | reduction_p |
Enumerations | |
enum | reduction_type { UNKNOWN_RTYPE = 0 , SIMPLE_RTYPE , DOUBLE_RTYPE } |
#define DR_ACCESS_STRIDE | ( | dr | ) |
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().
#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().
#define MAX_DATAREFS (param_loop_max_datarefs_for_datadeps) |
Maximum number of data references in loop nest.
#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().
#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().
#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 struct induction * induction_p |
Structure recording loop induction variable.
typedef struct reduction * reduction_p |
Structure recording loop reduction variable.
enum reduction_type |
|
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().
|
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().
|
static |
Dump access strides for all DATAREFS.
References DR_ACCESS_STRIDE, DR_REF, dump_file, i, print_generic_expr(), and TDF_SLIM.
|
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().
|
static |
Dump reduction RE.
References DOUBLE_RTYPE, dump_file, print_gimple_stmt(), and SIMPLE_RTYPE.
Referenced by loop_cand::analyze_iloop_reduction_var(), and loop_cand::analyze_oloop_reduction_var().
|
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().
|
static |
Free DATAREFS and its auxiliary memory.
References data_reference::aux, DR_ACCESS_STRIDE, free_data_refs(), i, and NULL.
gimple_opt_pass * make_pass_linterchange | ( | gcc::context * | ctxt | ) |
|
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().
|
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().
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().
Return true if E is unsupported in loop interchange, i.e, E is a complex edge or part of irreducible loop.
References EDGE_COMPLEX.