- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
|
static |
Function bb_in_loop_p Used as predicate for dfs order traversal of the loop bbs.
References flow_bb_inside_loop_p().
Referenced by new_loop_vec_info().
| void destroy_loop_vec_info | ( | ) |
Function destroy_loop_vec_info. Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the stmts in the loop.
References loop::aux, destroy_cost_data(), free(), free_data_refs(), free_dependence_relations(), free_stmt_vec_info(), gimple_assign_rhs1(), gimple_assign_rhs1_ptr(), gimple_assign_rhs2_ptr(), gimple_assign_rhs_code(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), is_gimple_assign(), loop::num_nodes, si, swap_tree_operands(), and vect_free_slp_instance().
Referenced by gather_scalar_reductions(), vect_analyze_loop(), vect_analyze_loop_form(), and vectorize_loops().
|
static |
Function get_initial_def_for_induction Input: STMT - a stmt that performs an induction operation in the loop. IV_PHI - the initial value of the induction variable Output: Return a vector variable, initialized with the first VF values of the induction variable. E.g., for an iv with IV_PHI='X' and evolution S, for a vector of 4 units, we want to return: [X, X + S, X + 2*S, X + 3*S].
References add_phi_arg(), analyze_scalar_evolution(), build_constructor(), build_int_cst(), build_vector_from_ctor(), build_vector_from_val(), create_phi_node(), dump_enabled_p(), dump_gimple_stmt(), dump_printf(), dump_printf_loc(), flow_bb_inside_loop_p(), force_gimple_operand(), get_vectype_for_scalar_type(), gimple_assign_lhs(), gimple_assign_set_lhs(), gimple_bb(), gimple_build_assign_with_ops(), gsi_after_labels(), gsi_insert_before(), gsi_insert_on_edge_immediate(), gsi_insert_seq_on_edge_immediate(), GSI_SAME_STMT, loop::header, init_expr(), loop::inner, is_gimple_min_invariant(), loop_latch_edge(), loop_preheader_edge(), make_ssa_name(), nested_in_vect_loop_p(), new_stmt_vec_info(), loop::num, set_vinfo_for_stmt(), si, unshare_expr(), useless_type_conversion_p(), vec_alloc(), vect_get_new_vect_var(), vect_get_vec_def_for_operand(), vect_init_vector(), vect_is_simple_iv_evolution(), vect_location, vect_scalar_var, vect_simple_var, and vinfo_for_stmt().
Referenced by vectorizable_induction().
Function get_initial_def_for_reduction
Input:
STMT - a stmt that performs a reduction operation in the loop.
INIT_VAL - the initial value of the reduction variable
Output:
ADJUSTMENT_DEF - a tree that holds a value to be added to the final result
of the reduction (used for adjusting the epilog - see below).
Return a vector variable, initialized according to the operation that STMT
performs. This vector will be used as the initial value of the
vector of partial results.
Option1 (adjust in epilog): Initialize the vector as follows:
add/bit or/xor: [0,0,...,0,0]
mult/bit and: [1,1,...,1,1]
min/max/cond_expr: [init_val,init_val,..,init_val,init_val]
and when necessary (e.g. add/mult case) let the caller know
that it needs to adjust the result by init_val.
Option2: Initialize the vector as follows:
add/bit or/xor: [init_val,0,0,...,0]
mult/bit and: [init_val,1,1,...,1]
min/max/cond_expr: [init_val,init_val,...,init_val]
and no adjustments are needed.
For example, for the following code:
s = init_val;
for (i=0;i<n;i++)
s = s + a[i];
STMT is 's = s + a[i]', and the reduction variable is 's'.
For a vector of 4 units, we want to return either [0,0,0,init_val],
or [0,0,0,0] and let the caller know that it needs to adjust
the result at the end by 'init_val'.
FORNOW, we are using the 'adjust in epilog' scheme, because this way the
initialization vector is simpler (same element in all entries), if
ADJUSTMENT_DEF is not NULL, and Option2 otherwise.
A cost model should help decide between these two schemes.
References build_constructor(), build_int_cst(), build_real(), build_vector_from_val(), dconst0, dconst1, flow_bb_inside_loop_p(), get_vectype_for_scalar_type(), gimple_assign_rhs_code(), nested_in_vect_loop_p(), vec_alloc(), vect_create_destination_var(), vect_double_reduction_def, vect_get_vec_def_for_operand(), and vinfo_for_stmt().
Referenced by vect_create_epilog_for_reduction(), and vect_get_vec_def_for_operand().
|
static |
Function new_loop_vec_info. Create and initialize a new loop_vec_info struct for LOOP, as well as stmt_vec_info structs for all the stmts in LOOP.
References bb_in_loop_p(), dfs_enumerate_from(), free(), get_loop_body(), gimple_set_uid(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), loop::header, init_cost(), loop::inner, basic_block_def::loop_father, new_stmt_vec_info(), loop::num_nodes, set_vinfo_for_stmt(), si, and vinfo_for_stmt().
Referenced by vect_analyze_loop_form().
|
static |
Function reduction_code_for_scalar_code
Input:
CODE - tree_code of a reduction operations.
Output:
REDUC_CODE - the corresponding tree-code to be used to reduce the
vector of partial results into a single scalar result (which
will also reside in a vector) or ERROR_MARK if the operation is
a supported reduction operation, but does not have such tree-code.
Return FALSE if CODE currently cannot be vectorized as reduction.
Referenced by vectorizable_reduction().
|
static |
Error reporting helper for vect_is_simple_reduction below. GIMPLE statement STMT is printed with a message MSG.
References dump_gimple_stmt(), dump_printf_loc(), and vect_location.
Referenced by vect_is_simple_reduction_1().
| loop_vec_info vect_analyze_loop | ( | ) |
Function vect_analyze_loop. Apply a set of analyses on LOOP, and create a loop_vec_info struct for it. The different analyses will record information in the loop_vec_info struct.
References current_vector_size, destroy_loop_vec_info(), dump_enabled_p(), dump_printf_loc(), floor_log2(), loop_outer(), loop_vec_info_for_loop(), targetm, vect_analyze_loop_2(), vect_analyze_loop_form(), and vect_location.
Referenced by vectorize_loops().
|
static |
Function vect_analyze_loop_1. Apply a set of analyses on LOOP, and create a loop_vec_info struct for it. The different analyses will record information in the loop_vec_info struct. This is a subset of the analyses applied in vect_analyze_loop, to be applied on an inner-loop nested in the loop that is now considered for (outer-loop) vectorization.
References dump_enabled_p(), dump_printf_loc(), vect_analyze_loop_form(), and vect_location.
Referenced by vect_analyze_loop_form().
|
static |
Function vect_analyze_loop_2. Apply a set of analyses on LOOP, and create a loop_vec_info struct for it. The different analyses will record information in the loop_vec_info struct.
References dump_enabled_p(), dump_printf_loc(), vect_analyze_data_ref_accesses(), vect_analyze_data_ref_dependences(), vect_analyze_data_refs(), vect_analyze_data_refs_alignment(), vect_analyze_loop_operations(), vect_analyze_scalar_cycles(), vect_analyze_slp(), vect_detect_hybrid_slp(), vect_determine_vectorization_factor(), vect_enhance_data_refs_alignment(), vect_location, vect_make_slp_decision(), vect_mark_stmts_to_be_vectorized(), vect_pattern_recog(), and vect_prune_runtime_alias_test_list().
Referenced by vect_analyze_loop().
| loop_vec_info vect_analyze_loop_form | ( | ) |
Function vect_analyze_loop_form.
Verify that certain CFG restrictions hold, including:
- the loop has a pre-header
- the loop has a single entry and exit
- the loop exit condition is simple enough, and the number of iterations
can be analyzed (a countable loop).
References loop::aux, chrec_contains_undetermined(), destroy_loop_vec_info(), dump_enabled_p(), dump_generic_expr(), dump_printf(), dump_printf_loc(), empty_block_p(), expr_invariant_in_loop_p(), edge_def::flags, gimple_seq_empty_p(), loop::header, loop::inner, loop::latch, loop_exit_ctrl_vec_info_type, new_loop_vec_info(), loop::num_nodes, phi_nodes(), basic_block_def::preds, single_exit(), single_pred_p(), split_loop_exit_edge(), edge_def::src, vect_analyze_loop_1(), vect_get_loop_niters(), vect_location, and vinfo_for_stmt().
Referenced by gather_scalar_reductions(), vect_analyze_loop(), and vect_analyze_loop_1().
|
static |
Function vect_analyze_loop_operations. Scan the loop stmts and make sure they are all vectorizable.
References dump_enabled_p(), dump_gimple_stmt(), dump_printf_loc(), estimated_stmt_executions_int(), flow_bb_inside_loop_p(), gimple_clobber_p(), gimple_phi_num_args(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), HOST_WIDE_INT, HOST_WIDE_INT_PRINT_DEC, is_loop_header_bb_p(), least_common_multiple(), max_stmt_executions_int(), loop::num_nodes, si, single_exit(), slpeel_can_duplicate_loop_p(), vect_analyze_stmt(), vect_can_advance_ivs_p(), vect_double_reduction_def, vect_estimate_min_profitable_iters(), vect_induction_def, vect_location, vect_update_slp_costs_according_to_vf(), vect_used_in_outer, vect_used_in_outer_by_reduction, vect_used_in_scope, vectorizable_induction(), and vinfo_for_stmt().
Referenced by vect_analyze_loop_2().
|
static |
Function vect_analyze_scalar_cycles.
Examine the cross iteration def-use cycles of scalar variables, by
analyzing the loop-header PHIs of scalar variables. Classify each
cycle as one of the following: invariant, induction, reduction, unknown.
We do that for the loop represented by LOOP_VINFO, and also to its
inner-loop, if exists.
Examples for scalar cycles:
Example1: reduction:
loop1:
for (i=0; i<N; i++)
sum += a[i];
Example2: induction:
loop2:
for (i=0; i<N; i++)
a[i] = i;
References loop::inner, and vect_analyze_scalar_cycles_1().
Referenced by vect_analyze_loop_2().
|
static |
Function vect_analyze_scalar_cycles_1. Examine the cross iteration def-use cycles of scalar variables in LOOP. LOOP_VINFO represents the loop that is now being considered for vectorization (can be LOOP, or an outer-loop enclosing LOOP).
References analyze_scalar_evolution(), dump_enabled_p(), dump_generic_expr(), dump_gimple_stmt(), dump_printf_loc(), evolution_part_in_loop_num(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, loop::num, vect_double_reduction_def, vect_force_simple_reduction(), vect_induction_def, vect_is_simple_iv_evolution(), vect_location, vect_nested_cycle, vect_reduction_def, vect_unknown_def_type, vinfo_for_stmt(), virtual_operand_p(), and worklist.
Referenced by vect_analyze_scalar_cycles().
|
static |
Function vect_create_epilog_for_reduction
Create code at the loop-epilog to finalize the result of a reduction
computation.
VECT_DEFS is list of vector of partial results, i.e., the lhs's of vector
reduction statements.
STMT is the scalar reduction stmt that is being vectorized.
NCOPIES is > 1 in case the vectorization factor (VF) is bigger than the
number of elements that we can fit in a vectype (nunits). In this case
we have to generate more than one vector stmt - i.e - we need to "unroll"
the vector stmt by a factor VF/nunits. For more details see documentation
in vectorizable_operation.
REDUC_CODE is the tree-code for the epilog reduction.
REDUCTION_PHIS is a list of the phi-nodes that carry the reduction
computation.
REDUC_INDEX is the index of the operand in the right hand side of the
statement that is defined by REDUCTION_PHI.
DOUBLE_REDUC is TRUE if double reduction phi nodes should be handled.
SLP_NODE is an SLP node containing a group of reduction statements. The
first one in this group is STMT.
This function:
1. Creates the reduction def-use cycles: sets the arguments for
REDUCTION_PHIS:
The loop-entry argument is the vectorized initial-value of the reduction.
The loop-latch argument is taken from VECT_DEFS - the vector of partial
sums.
2. "Reduces" each vector of partial results VECT_DEFS into a single result,
by applying the operation specified by REDUC_CODE if available, or by
other means (whole-vector shifts or a scalar loop).
The function also creates a new phi node at the loop exit to preserve
loop-closed form, as illustrated below.
The flow at the entry to this function:
loop:
vec_def = phi <null, null> # REDUCTION_PHI
VECT_DEF = vector_stmt # vectorized form of STMT
s_loop = scalar_stmt # (scalar) STMT
loop_exit:
s_out0 = phi <s_loop> # (scalar) EXIT_PHI
use <s_out0>
use <s_out0>
The above is transformed by this function into:
loop:
vec_def = phi <vec_init, VECT_DEF> # REDUCTION_PHI
VECT_DEF = vector_stmt # vectorized form of STMT
s_loop = scalar_stmt # (scalar) STMT
loop_exit:
s_out0 = phi <s_loop> # (scalar) EXIT_PHI
v_out1 = phi <VECT_DEF> # NEW_EXIT_PHI
v_out2 = reduce <v_out1>
s_out3 = extract_field <v_out2, 0>
s_out4 = adjust_result <s_out3>
use <s_out4>
use <s_out4>
References add_phi_arg(), copy_ssa_name(), create_phi_node(), edge_def::dest, edge_def::dest_idx, dump_enabled_p(), dump_gimple_stmt(), dump_printf(), dump_printf_loc(), flow_bb_inside_loop_p(), get_gimple_rhs_class(), get_initial_def_for_reduction(), get_vectype_for_scalar_type(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_assign_set_lhs(), gimple_bb(), GIMPLE_BINARY_RHS, gimple_build_assign_with_ops(), gimple_op(), gimple_phi_num_args(), GIMPLE_SINGLE_RHS, GIMPLE_TERNARY_RHS, GIMPLE_UNARY_RHS, gsi_after_labels(), gsi_insert_before(), GSI_SAME_STMT, loop::inner, basic_block_def::loop_father, loop_latch_edge(), loop_preheader_edge(), loop_vec_info_for_loop(), make_ssa_name(), nested_in_vect_loop_p(), new_stmt_vec_info(), optab_default, optab_for_tree_code(), optab_handler(), phis, reduction_phi(), set_vinfo_for_stmt(), single_exit(), ternary_op, tree_low_cst(), vect_create_destination_var(), vect_double_reduction_def, vect_get_vec_def_for_operand(), vect_get_vec_def_for_stmt_copy(), vect_get_vec_defs(), vect_init_vector(), vect_location, vect_unknown_def_type, vinfo_for_stmt(), and vNULL.
Referenced by vectorizable_reduction().
|
static |
Function vect_determine_vectorization_factor
Determine the vectorization factor (VF). VF is the number of data elements
that are operated upon in parallel in a single iteration of the vectorized
loop. For example, when vectorizing a loop that operates on 4byte elements,
on a target with vector size (VS) 16byte, the VF is set to 4, since 4
elements can fit in a single vector register.
We currently support vectorization of loops in which all types operated upon
are of the same size. Therefore this function currently sets VF according to
the size of the types operated upon, and fails if there are multiple sizes
in the loop.
VF is also the factor by which the loop iterations are strip-mined, e.g.:
original loop:
for (i=0; i<N; i++){
a[i] = b[i] + c[i];
}
vectorized loop:
for (i=0; i<N; i+=VF){
a[i:VF] = b[i:VF] + c[i:VF];
}
References dump_enabled_p(), dump_generic_expr(), dump_gimple_stmt(), dump_printf(), dump_printf_loc(), get_vectype_for_scalar_type(), gimple_clobber_p(), gimple_expr_type(), gimple_get_lhs(), gsi_end_p(), gsi_next(), gsi_none(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), HOST_WIDE_INT, is_pattern_stmt_p(), loop::num_nodes, si, vect_get_smallest_scalar_type(), vect_location, and vinfo_for_stmt().
Referenced by vect_analyze_loop_2().
|
static |
@verbatim Loop Vectorization
Copyright (C) 2003-2013 Free Software Foundation, Inc. Contributed by Dorit Naishlos dorit@il.ibm.com and Ira Rosen irar@il.ibm.com
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/.
Loop Vectorization Pass.
This pass tries to vectorize loops.
For example, the vectorizer transforms the following simple loop:
short a[N]; short b[N]; short c[N]; int i;
for (i=0; i<N; i++){
a[i] = b[i] + c[i];
}
as if it was manually vectorized by rewriting the source code into:
typedef int __attribute__((mode(V8HI))) v8hi;
short a[N]; short b[N]; short c[N]; int i;
v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
v8hi va, vb, vc;
for (i=0; i<N/8; i++){
vb = pb[i];
vc = pc[i];
va = vb + vc;
pa[i] = va;
}
The main entry to this pass is vectorize_loops(), in which
the vectorizer applies a set of analyses on a given set of loops,
followed by the actual vectorization transformation for the loops that
had successfully passed the analysis phase.
Throughout this pass we make a distinction between two types of
data: scalars (which are represented by SSA_NAMES), and memory references
("data-refs"). These two types of data require different handling both
during analysis and transformation. The types of data-refs that the
vectorizer currently supports are ARRAY_REFS which base is an array DECL
(not a pointer), and INDIRECT_REFS through pointers; both array and pointer
accesses are required to have a simple (consecutive) access pattern.
Analysis phase:
===============
The driver for the analysis phase is vect_analyze_loop().
It applies a set of analyses, some of which rely on the scalar evolution
analyzer (scev) developed by Sebastian Pop.
During the analysis phase the vectorizer records some information
per stmt in a "stmt_vec_info" struct which is attached to each stmt in the
loop, as well as general information about the loop as a whole, which is
recorded in a "loop_vec_info" struct attached to each loop.
Transformation phase:
=====================
The loop transformation phase scans all the stmts in the loop, and
creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
the loop that needs to be vectorized. It inserts the vector code sequence
just before the scalar stmt S, and records a pointer to the vector code
in STMT_VINFO_VEC_STMT (stmt_info) (stmt_info is the stmt_vec_info struct
attached to S). This pointer will be used for the vectorization of following
stmts which use the def of stmt S. Stmt S is removed if it writes to memory;
otherwise, we rely on dead code elimination for removing it.
For example, say stmt S1 was vectorized into stmt VS1:
VS1: vb = px[i];
S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
S2: a = b;
To vectorize stmt S2, the vectorizer first finds the stmt that defines
the operand 'b' (S1), and gets the relevant vector def 'vb' from the
vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
resulting sequence would be:
VS1: vb = px[i];
S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
VS2: va = vb;
S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
Operands that are not SSA_NAMEs, are data-refs that appear in
load/store operations (like 'x[i]' in S1), and are handled differently.
Target modeling:
=================
Currently the only target specific information that is used is the
size of the vector (in bytes) - "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD".
Targets that can support different sizes of vectors, for now will need
to specify one value for "TARGET_VECTORIZE_UNITS_PER_SIMD_WORD". More
flexibility will be added in the future.
Since we only vectorize operations which vector form can be
expressed using existing tree codes, to verify that an operation is
supported, the vectorizer checks the relevant optab at the relevant
machine_mode (e.g, optab_handler (add_optab, V8HImode)). If
the value found is CODE_FOR_nothing, then there's no target support, and
we can't vectorize the stmt.
For additional information on this project see:
http://gcc.gnu.org/projects/tree-ssa/vectorization.htmlFunction vect_estimate_min_profitable_iters Return the number of iterations required for the vector version of the loop to be profitable relative to the cost of the scalar version of the loop.
References add_stmt_cost(), cond_branch_not_taken, cond_branch_taken, _stmt_info_for_cost::count, dump_enabled_p(), dump_printf(), dump_printf_loc(), finish_cost(), _stmt_info_for_cost::kind, len, _stmt_info_for_cost::misalign, scalar_stmt, si, _stmt_info_for_cost::stmt, vect_epilogue, vect_get_known_peeling_cost(), vect_get_single_scalar_iteration_cost(), vect_get_stmt_cost(), vect_location, vect_prologue, vector_stmt, and vinfo_for_stmt().
Referenced by vect_analyze_loop_operations().
| gimple vect_force_simple_reduction | ( | loop_vec_info | loop_info, |
| gimple | phi, | ||
| bool | check_reduction, | ||
| bool * | double_reduc | ||
| ) |
Wrapper around vect_is_simple_reduction_1, which will modify code in-place if it enables detection of more reductions. Arguments as there.
References vect_is_simple_reduction_1().
Referenced by gather_scalar_reductions(), and vect_analyze_scalar_cycles_1().
| int vect_get_known_peeling_cost | ( | loop_vec_info | loop_vinfo, |
| int | peel_iters_prologue, | ||
| int * | peel_iters_epilogue, | ||
| int | scalar_single_iter_cost, | ||
| stmt_vector_for_cost * | prologue_cost_vec, | ||
| stmt_vector_for_cost * | epilogue_cost_vec | ||
| ) |
Calculate cost of peeling the loop PEEL_ITERS_PROLOGUE times.
References cond_branch_taken, dump_enabled_p(), dump_printf_loc(), record_stmt_cost(), scalar_stmt, vect_epilogue, vect_location, and vect_prologue.
Referenced by vect_estimate_min_profitable_iters(), and vect_peeling_hash_get_lowest_cost().
|
static |
Function vect_get_loop_niters. Determine how many iterations the loop is executed. If an expression that represents the number of iterations can be constructed, place it in NUMBER_OF_ITERATIONS. Return the loop exit condition.
References chrec_dont_know, dump_enabled_p(), dump_generic_expr(), dump_printf_loc(), get_loop_exit_condition(), number_of_exit_cond_executions(), and vect_location.
Referenced by vect_analyze_loop_form().
| int vect_get_single_scalar_iteration_cost | ( | ) |
Calculate the cost of one scalar iteration of the loop.
References DR_IS_READ, gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), loop::inner, is_gimple_assign(), is_gimple_call(), basic_block_def::loop_father, loop::num_nodes, scalar_load, scalar_stmt, scalar_store, si, stmt_cost(), vect_get_stmt_cost(), and vinfo_for_stmt().
Referenced by vect_estimate_min_profitable_iters(), and vect_peeling_hash_get_lowest_cost().
|
static |
Function vect_is_simple_iv_evolution. FORNOW: A simple evolution of an induction variables in the loop is considered a polynomial evolution.
References cfun, dump_enabled_p(), dump_generic_expr(), dump_printf(), dump_printf_loc(), evolution_part_in_loop_num(), flow_bb_inside_loop_p(), get_loop(), init_expr(), initial_condition_in_loop_num(), tree_is_chrec(), unshare_expr(), and vect_location.
Referenced by get_initial_def_for_induction(), and vect_analyze_scalar_cycles_1().
|
static |
Wrapper around vect_is_simple_reduction_1, that won't modify code in-place. Arguments as there.
References vect_is_simple_reduction_1().
Referenced by vectorizable_reduction().
|
static |
Function vect_is_simple_reduction_1
(1) Detect a cross-iteration def-use cycle that represents a simple
reduction computation. We look for the following pattern:
loop_header:
a1 = phi < a0, a2 >
a3 = ...
a2 = operation (a3, a1)
such that:
1. operation is commutative and associative and it is safe to
change the order of the computation (if CHECK_REDUCTION is true)
2. no uses for a2 in the loop (a2 is used out of the loop)
3. no uses of a1 in the loop besides the reduction operation
4. no uses of a1 outside the loop.
Conditions 1,4 are tested here.
Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
(2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
nested cycles, if CHECK_REDUCTION is false.
(3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
reductions:
a1 = phi < a0, a2 >
inner loop (def of a3)
a2 = phi < a3 >
If MODIFY is true it tries also to rework the code in-place to enable
detection of more reduction patterns. For the time being we rewrite
"res -= RHS" into "rhs += -RHS" when it seems worthwhile.
References associative_tree_code(), commutative_tree_code(), dump_enabled_p(), dump_generic_expr(), dump_gimple_stmt(), dump_printf(), dump_printf_loc(), flow_bb_inside_loop_p(), flow_loop_nested_p(), get_gimple_rhs_class(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs1_ptr(), gimple_assign_rhs2(), gimple_assign_rhs2_ptr(), gimple_assign_rhs3(), gimple_assign_rhs_code(), gimple_assign_set_rhs2(), gimple_assign_set_rhs_code(), gimple_bb(), GIMPLE_BINARY_RHS, gimple_build_assign_with_ops(), gimple_nop_p(), gimple_phi_num_args(), gsi_for_stmt(), gsi_insert_before(), GSI_NEW_STMT, loop::inner, is_gimple_assign(), is_gimple_call(), is_gimple_debug(), is_loop_header_bb_p(), is_pattern_stmt_p(), loop_latch_edge(), make_ssa_name(), new_stmt_vec_info(), report_vect_op(), set_vinfo_for_stmt(), swap_tree_operands(), type(), types_compatible_p(), update_stmt(), vect_induction_def, vect_internal_def, vect_is_slp_reduction(), vect_location, and vinfo_for_stmt().
Referenced by vect_force_simple_reduction(), and vect_is_simple_reduction().
|
static |
Detect SLP reduction of the form: #a1 = phi <a5, a0> a2 = operation (a1) a3 = operation (a2) a4 = operation (a3) a5 = operation (a4) #a = phi <a5> PHI is the reduction phi node (#a1 = phi <a5, a0> above) FIRST_STMT is the first reduction stmt in the chain (a2 = operation (a1)). Return TRUE if a reduction chain was detected.
References dump_enabled_p(), dump_gimple_stmt(), dump_printf_loc(), first, flow_bb_inside_loop_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs1_ptr(), gimple_assign_rhs2(), gimple_assign_rhs2_ptr(), gimple_assign_rhs_code(), gimple_bb(), is_gimple_assign(), is_gimple_call(), is_gimple_debug(), is_loop_header_bb_p(), swap_tree_operands(), update_stmt(), vect_induction_def, vect_internal_def, vect_location, and vinfo_for_stmt().
Referenced by vect_is_simple_reduction_1().
|
static |
Kill any debug uses outside LOOP of SSA names defined in STMT.
References dump_enabled_p(), dump_printf_loc(), flow_bb_inside_loop_p(), gimple_bb(), gimple_debug_bind_p(), gimple_debug_bind_reset_value(), is_gimple_debug(), update_stmt(), and vect_location.
Referenced by vect_transform_loop().
| int vect_min_worthwhile_factor | ( | ) |
Function vect_min_worthwhile_factor. For a loop where we could vectorize the operation indicated by CODE, return the minimum vectorization factor that makes it worthwhile to use generic vectors.
Referenced by vectorizable_operation(), vectorizable_reduction(), and vectorizable_shift().
|
static |
Function vect_model_induction_cost. Models cost for induction operations.
References add_stmt_cost(), dump_enabled_p(), dump_printf_loc(), scalar_to_vec, vect_body, vect_location, vect_prologue, and vector_stmt.
Referenced by vectorizable_induction().
|
static |
TODO: Close dependency between vect_model_*_cost and vectorizable_* functions. Design better to avoid maintenance issues.
Function vect_model_reduction_cost. Models cost for a reduction operation, including the vector ops generated within the strip-mine loop, the initial definition before the loop, and the epilogue code that must be generated.
References add_stmt_cost(), dump_enabled_p(), dump_generic_expr(), dump_printf(), dump_printf_loc(), exact_log2(), get_gimple_rhs_class(), get_vectype_for_scalar_type(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs3(), gimple_assign_rhs_code(), GIMPLE_BINARY_RHS, GIMPLE_SINGLE_RHS, GIMPLE_TERNARY_RHS, GIMPLE_UNARY_RHS, _stmt_vec_info::loop_vinfo, nested_in_vect_loop_p(), optab_default, optab_for_tree_code(), optab_handler(), scalar_to_vec, _stmt_vec_info::stmt, ternary_op, tree_low_cst(), vec_to_scalar, vect_body, vect_epilogue, vect_location, vect_prologue, vector_stmt, and _stmt_vec_info::vectype.
Referenced by vectorizable_reduction().
| void vect_transform_loop | ( | ) |
Function vect_transform_loop. The analysis phase has determined that the loop is vectorizable. Vectorize the loop - created vectorized stmts to replace the scalar stmts in the loop, and update the loop exit condition.
References loop::any_estimate, build_int_cst(), dump_enabled_p(), dump_gimple_stmt(), dump_printf_loc(), expected_loop_iterations_unbounded(), free_stmt_vec_info(), double_int::from_uhwi(), gimple_clobber_p(), gsi_end_p(), gsi_next(), gsi_none(), gsi_remove(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), loop::header, HOST_WIDE_INT, loop::inner, is_pattern_stmt_p(), loop_preheader_edge(), loop::nb_iterations_estimate, loop::nb_iterations_upper_bound, loop::num_nodes, basic_block_def::preds, release_defs(), scale_loop_profile(), si, slpeel_make_loop_iterate_ntimes(), split_edge(), double_int::udiv(), unlink_stmt_vdef(), vect_do_peeling_for_alignment(), vect_do_peeling_for_loop_bound(), vect_induction_def, vect_location, vect_loop_kill_debug_uses(), vect_loop_versioning(), vect_remove_stores(), vect_schedule_slp(), vect_transform_stmt(), and vinfo_for_stmt().
Referenced by vectorize_loops().
| bool vectorizable_induction | ( | gimple | phi, |
| gimple_stmt_iterator * | gsi, | ||
| gimple * | vec_stmt | ||
| ) |
Function vectorizable_induction Check if PHI performs an induction computation that can be vectorized. If VEC_STMT is also passed, vectorize the induction PHI: create a vectorized phi to replace it, put it in VEC_STMT, and add it to the same basic block. Return FALSE if not a vectorizable STMT, TRUE otherwise.
Transform. *
References dump_enabled_p(), dump_printf_loc(), flow_bb_inside_loop_p(), get_initial_def_for_induction(), induc_vec_info_type, loop::inner, loop_latch_edge(), nested_in_vect_loop_p(), vect_induction_def, vect_location, vect_model_induction_cost(), and vinfo_for_stmt().
Referenced by vect_analyze_loop_operations(), and vect_transform_stmt().
| bool vectorizable_live_operation | ( | gimple | stmt, |
| gimple_stmt_iterator * | gsi, | ||
| gimple * | vec_stmt | ||
| ) |
Function vectorizable_live_operation. STMT computes a value that is used outside the loop. Check if it can be supported.
References binary_op, build_int_cst(), edge_def::dest, edge_def::dest_idx, dump_enabled_p(), dump_printf_loc(), get_gimple_rhs_class(), gimple_assign_lhs(), gimple_assign_rhs_code(), GIMPLE_BINARY_RHS, gimple_call_arg(), gimple_call_internal_fn(), gimple_call_internal_p(), gimple_call_lhs(), gimple_op(), GIMPLE_SINGLE_RHS, GIMPLE_UNARY_RHS, is_gimple_assign(), nested_in_vect_loop_p(), loop::simduid, single_exit(), unary_op, vect_constant_def, vect_external_def, vect_is_simple_use(), vect_location, vect_reduction_def, _loop_vec_info::vectorization_factor, and vinfo_for_stmt().
Referenced by vect_analyze_stmt(), and vect_transform_stmt().
| bool vectorizable_reduction | ( | gimple | stmt, |
| gimple_stmt_iterator * | gsi, | ||
| gimple * | vec_stmt, | ||
| slp_tree | slp_node | ||
| ) |
Function vectorizable_reduction.
Check if STMT performs a reduction operation that can be vectorized.
If VEC_STMT is also passed, vectorize the STMT: create a vectorized
stmt to replace it, put it in VEC_STMT, and insert it at GSI.
Return FALSE if not a vectorizable STMT, TRUE otherwise.
This function also handles reduction idioms (patterns) that have been
recognized in advance during vect_pattern_recog. In this case, STMT may be
of this form:
X = pattern_expr (arg0, arg1, ..., X)
and it's STMT_VINFO_RELATED_STMT points to the last stmt in the original
sequence that had been detected and replaced by the pattern-stmt (STMT).
In some cases of reduction patterns, the type of the reduction variable X is
different than the type of the other arguments of STMT.
In such cases, the vectype that is used when transforming STMT into a vector
stmt is different than the vectype that is used to determine the
vectorization factor, because it consists of a different number of elements
than the actual number of elements that are being operated upon in parallel.
For example, consider an accumulation of shorts into an int accumulator.
On some targets it's possible to vectorize this pattern operating on 8
shorts at a time (hence, the vectype for purposes of determining the
vectorization factor should be V8HI); on the other hand, the vectype that
is used to create the vector form is actually V4SI (the type of the result).
Upon entry to this function, STMT_VINFO_VECTYPE records the vectype that
indicates what is the actual level of parallelism (V8HI in the example), so
that the right vectorization factor would be derived. This vectype
corresponds to the type of arguments to the reduction stmt, and should *NOT*
be used to create the vectorized stmt. The right vectype for the vectorized
stmt is obtained from the type of the result X:
get_vectype_for_scalar_type (TREE_TYPE (X))
This means that, contrary to "regular" reductions (or "regular" stmts in
general), the following equation:
STMT_VINFO_VECTYPE == get_vectype_for_scalar_type (TREE_TYPE (X))
does *NOT* necessarily hold for reduction patterns. Transform. *
References binary_op, create_phi_node(), dump_enabled_p(), dump_printf(), dump_printf_loc(), flow_bb_inside_loop_p(), get_gimple_rhs_class(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs3(), gimple_assign_rhs_code(), gimple_assign_set_lhs(), gimple_bb(), GIMPLE_BINARY_RHS, GIMPLE_SINGLE_RHS, GIMPLE_TERNARY_RHS, GIMPLE_UNARY_RHS, loop::header, loop::inner, is_gimple_assign(), basic_block_def::loop_father, loop_preheader_edge(), make_ssa_name(), nested_in_vect_loop_p(), new_stmt_vec_info(), optab_default, optab_for_tree_code(), optab_handler(), phis, reduc_vec_info_type, reduction_code_for_scalar_code(), set_vinfo_for_stmt(), ternary_op, types_compatible_p(), vect_constant_def, vect_create_destination_var(), vect_create_epilog_for_reduction(), vect_double_reduction_def, vect_external_def, vect_finish_stmt_generation(), vect_get_vec_def_for_operand(), vect_get_vec_def_for_stmt_copy(), vect_get_vec_defs(), vect_induction_def, vect_internal_def, vect_is_simple_reduction(), vect_is_simple_use(), vect_is_simple_use_1(), vect_location, vect_min_worthwhile_factor(), vect_model_reduction_cost(), vect_nested_cycle, vect_reduction_def, vect_unused_in_scope, vect_used_in_outer, vectorizable_condition(), vinfo_for_stmt(), and vNULL.
Referenced by vect_analyze_stmt(), and vect_transform_stmt().
1.8.1.1