#include "config.h"#include "system.h"#include "coretypes.h"#include "dumpfile.h"#include "tm.h"#include "ggc.h"#include "tree.h"#include "basic-block.h"#include "gimple-pretty-print.h"#include "gimple.h"#include "gimple-ssa.h"#include "tree-cfg.h"#include "tree-phinodes.h"#include "ssa-iterators.h"#include "tree-ssanames.h"#include "tree-ssa-loop-manip.h"#include "tree-into-ssa.h"#include "tree-ssa.h"#include "tree-pass.h"#include "cfgloop.h"#include "diagnostic-core.h"#include "tree-scalar-evolution.h"#include "tree-vectorizer.h"#include "langhooks.h"
Data Structures | |
| struct | adjust_info |
Functions | |
| static void | rename_use_op () |
| static void | rename_variables_in_bb () |
| static void | adjust_debug_stmts_now () |
| static void | adjust_vec_debug_stmts () |
| static void | adjust_debug_stmts () |
| static void | adjust_phi_and_debug_stmts () |
| static void | slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop, bool is_new_loop, basic_block *new_exit_bb) |
| static void | slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop, bool is_new_loop, basic_block *new_exit_bb) |
| void | slpeel_make_loop_iterate_ntimes () |
| struct loop * | slpeel_tree_duplicate_loop_to_edge_cfg () |
| static edge | slpeel_add_loop_guard (basic_block guard_bb, tree cond, gimple_seq cond_expr_stmt_list, basic_block exit_bb, basic_block dom_bb, int probability) |
| bool | slpeel_can_duplicate_loop_p () |
| static void | set_prologue_iterations (basic_block bb_before_first_loop, tree *first_niters, struct loop *loop, unsigned int th, int probability) |
| static struct loop * | slpeel_tree_peel_loop_to_edge (struct loop *loop, edge e, tree *first_niters, tree niters, bool update_first_loop_count, unsigned int th, bool check_profitability, tree cond_expr, gimple_seq cond_expr_stmt_list, int bound1, int bound2) |
| LOC | find_loop_location () |
| static tree | vect_build_loop_niters () |
| static void | vect_generate_tmps_on_preheader (loop_vec_info loop_vinfo, tree *ni_name_ptr, tree *ratio_mult_vf_name_ptr, tree *ratio_name_ptr, gimple_seq cond_expr_stmt_list) |
| bool | vect_can_advance_ivs_p () |
| static void | vect_update_ivs_after_vectorizer (loop_vec_info loop_vinfo, tree niters, edge update_e) |
| void | vect_do_peeling_for_loop_bound (loop_vec_info loop_vinfo, tree *ratio, unsigned int th, bool check_profitability) |
| static tree | vect_gen_niters_for_prolog_loop () |
| static void | vect_update_init_of_dr () |
| static void | vect_update_inits_of_drs () |
| void | vect_do_peeling_for_alignment (loop_vec_info loop_vinfo, unsigned int th, bool check_profitability) |
| static void | vect_create_cond_for_align_checks (loop_vec_info loop_vinfo, tree *cond_expr, gimple_seq *cond_expr_stmt_list) |
| static tree | vect_vfa_segment_size () |
| static void | vect_create_cond_for_alias_checks () |
| void | vect_loop_versioning (loop_vec_info loop_vinfo, unsigned int th, bool check_profitability) |
Variables | |
| static vec< adjust_info, va_heap > | adjust_vec |
Function Documentation
|
static |
Adjust any debug stmts that referenced FROM values to use the loop-closed TO, if the references are dominated by BB and not by the definition of FROM. If adjust_vec is non-NULL, adjustments will be postponed until adjust_vec_debug_stmts is called.
|
static |
Adjust any debug stmts that referenced AI->from values to use the loop-closed AI->to, if the references are dominated by AI->bb and not by the definition of AI->from.
Adjust any debug stmts that held onto non-loop-closed references.
|
static |
Change E's phi arg in UPDATE_PHI to NEW_DEF, and record information to adjust any debug stmts that referenced the old phi arg, presumably non-loop-closed references left over from other transformations.
References edge_def::dest, EDGE_SUCC, and loop::header.
Referenced by vect_can_advance_ivs_p(), and vect_create_cond_for_alias_checks().
|
static |
Adjust debug stmts as scheduled before.
| LOC find_loop_location | ( | ) |
Function vect_get_loop_location.
Extract the location of the loop in the source code. If the loop is not well formed for vectorization, an estimated location is calculated. Return the loop location if succeed and NULL if not.
If we got here the loop is probably not "well formed", try to estimate the loop location
References build_int_cst(), build_one_cst(), create_tmp_var, exact_log2(), fold_build2, is_gimple_val(), loop_preheader_edge(), LOOP_VINFO_LOOP, LOOP_VINFO_NITERS, LOOP_VINFO_PEELING_FOR_GAPS, LOOP_VINFO_VECT_FACTOR, NULL, TREE_TYPE, and vect_build_loop_niters().
|
static |
Vectorizer Specific Loop Manipulations 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/. Renames the use *OP_P.
Something defined outside of the loop.
An ordinary ssa name defined in the loop.
|
static |
Renames the variables in basic block BB.
|
static |
If the run time cost model check determines that vectorization is not profitable and hence scalar loop should be generated then set FIRST_NITERS to prologue peeled iterations. This will allow all the iterations to be executed in the prologue peeled scalar loop.
|
static |
Given the condition statement COND, put it as the last statement of GUARD_BB; EXIT_BB is the basic block to skip the loop; Assumes that this is the single exit of the guarded loop. Returns the skip edge, inserts new stmts on the COND_EXPR_STMT_LIST.
Add new edge to connect guard block to the merge/loop-exit block.
| bool slpeel_can_duplicate_loop_p | ( | ) |
This function verifies that the following restrictions apply to LOOP: (1) it is innermost (2) it consists of exactly 2 basic blocks - header, and an empty latch. (3) it is single entry, single exit (4) its exit condition is the last stmt in the header (5) E is the entry/exit edge of LOOP.
All loops have an outer scope; the only case loop->outer is NULL is for the function itself.
Verify that new loop exit condition can be trivially modified.
| void slpeel_make_loop_iterate_ntimes | ( | ) |
Make the LOOP iterate NITERS times. This is done by adding a new IV that starts at zero, increases by one and its limit is NITERS.
Assumption: the exit-condition of LOOP is the last stmt in the loop.
Remove old loop exit test:
|
read |
Given LOOP this function generates a new copy of it and puts it on E which is either the entry or exit of LOOP.
Check whether duplication is possible.
Generate new loop structure.
Also copy the pre-header, this avoids jumping through hoops to duplicate the loop entry PHI arguments. Create an empty pre-header unconditionally for this.
And remove the non-necessary forwarder again. Keep the other
one so we have a proper pre-header for the loop at the exit edge. And remove the non-necessary forwarder again. Keep the other
one so we have a proper pre-header for the loop at the exit edge.
Referenced by ssa_name_has_uses_outside_loop_p().
|
staticread |
Function slpeel_tree_peel_loop_to_edge.
Peel the first (last) iterations of LOOP into a new prolog (epilog) loop that is placed on the entry (exit) edge E of LOOP. After this transformation we have two loops one after the other - first-loop iterates FIRST_NITERS times, and second-loop iterates the remainder NITERS - FIRST_NITERS times. If the cost model indicates that it is profitable to emit a scalar loop instead of the vector one, then the prolog (epilog) loop will iterate for the entire unchanged scalar iterations of the loop.
Input:
- LOOP: the loop to be peeled.
- E: the exit or entry edge of LOOP. If it is the entry edge, we peel the first iterations of LOOP. In this case first-loop is LOOP, and second-loop is the newly created loop. If it is the exit edge, we peel the last iterations of LOOP. In this case, first-loop is the newly created loop, and second-loop is LOOP.
- NITERS: the number of iterations that LOOP iterates.
- FIRST_NITERS: the number of iterations that the first-loop should iterate.
- UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible for updating the loop bound of the first-loop to FIRST_NITERS. If it is false, the caller of this function may want to take care of this (this can be useful if we don't want new stmts added to first-loop).
- TH: cost model profitability threshold of iterations for vectorization.
- CHECK_PROFITABILITY: specify whether cost model check has not occurred during versioning and hence needs to occur during prologue generation or whether cost model check has not occurred during prologue generation and hence needs to occur during epilogue generation.
- BOUND1 is the upper bound on number of iterations of the first loop (if known)
- BOUND2 is the upper bound on number of iterations of the second loop (if known)
Output: The function returns a pointer to the new loop-copy, or NULL if it failed to perform the transformation.
The function generates two if-then-else guards: one before the first loop, and the other before the second loop: The first guard is: if (FIRST_NITERS == 0) then skip the first loop, and go directly to the second loop. The second guard is: if (FIRST_NITERS == NITERS) then skip the second loop.
If the optional COND_EXPR and COND_EXPR_STMT_LIST arguments are given then the generated condition is combined with COND_EXPR and the statements in COND_EXPR_STMT_LIST are emitted together with it.
FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p). FORNOW the resulting code will not be in loop-closed-ssa form.
There are many aspects to how likely the first loop is going to be executed. Without histogram we can't really do good job. Simply set it to 2/3, so the first loop is not reordered to the end of function and the hot path through stays short.
We might have a queued need to update virtual SSA form. As we delete the update SSA machinery below after doing a regular incremental SSA update during loop copying make sure we don't lose that fact. ??? Needing to update virtual SSA form by renaming is unfortunate but not all of the vectorizer code inserting new loads / stores properly assigns virtual operands to those statements.
If the loop has a virtual PHI, but exit bb doesn't, create a virtual PHI in the exit bb and rename all the uses after the loop. This simplifies the *guard[12] routines, which assume loop closed SSA form for all PHIs (but normally loop closed SSA form doesn't require virtual PHIs to be in the same form). Doing this early simplifies the checking what uses should be renamed.
1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
Resulting CFG would be:
first_loop:
do {
} while ...
second_loop:
do {
} while ...
orig_exit_bb:
NEW_LOOP was placed after LOOP.
NEW_LOOP was placed before LOOP.
2. Add the guard code in one of the following ways:
2.a Add the guard that controls whether the first loop is executed.
This occurs when this function is invoked for prologue or epilogue
generation and when the cost model check can be done at compile time.
Resulting CFG would be:
bb_before_first_loop:
if (FIRST_NITERS == 0) GOTO bb_before_second_loop
GOTO first-loop
first_loop:
do {
} while ...
bb_before_second_loop:
second_loop:
do {
} while ...
orig_exit_bb:
2.b Add the cost model check that allows the prologue
to iterate for the entire unchanged scalar
iterations of the loop in the event that the cost
model indicates that the scalar loop is more
profitable than the vector one. This occurs when
this function is invoked for prologue generation
and the cost model check needs to be done at run
time.
Resulting CFG after prologue peeling would be:
if (scalar_loop_iterations <= th)
FIRST_NITERS = scalar_loop_iterations
bb_before_first_loop:
if (FIRST_NITERS == 0) GOTO bb_before_second_loop
GOTO first-loop
first_loop:
do {
} while ...
bb_before_second_loop:
second_loop:
do {
} while ...
orig_exit_bb:
2.c Add the cost model check that allows the epilogue
to iterate for the entire unchanged scalar
iterations of the loop in the event that the cost
model indicates that the scalar loop is more
profitable than the vector one. This occurs when
this function is invoked for epilogue generation
and the cost model check needs to be done at run
time. This check is combined with any pre-existing
check in COND_EXPR to avoid versioning.
Resulting CFG after prologue peeling would be:
bb_before_first_loop:
if ((scalar_loop_iterations <= th)
||
FIRST_NITERS == 0) GOTO bb_before_second_loop
GOTO first-loop
first_loop:
do {
} while ...
bb_before_second_loop:
second_loop:
do {
} while ...
orig_exit_bb:
Loop copying insterted a forwarder block for us here.
Theoretically preheader edge of first loop and exit edge should have same frequencies. Loop exit probablities are however easy to get wrong. It is safer to copy value from original loop entry.
Epilogue peeling.
Prologue peeling.
3. Add the guard that controls whether the second loop is executed.
Resulting CFG would be:
bb_before_first_loop:
if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
GOTO first-loop
first_loop:
do {
} while ...
bb_between_loops:
if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
GOTO bb_before_second_loop
bb_before_second_loop:
second_loop:
do {
} while ...
bb_after_second_loop:
orig_exit_bb:
4. Make first-loop iterate FIRST_NITERS times, if requested.
Referenced by vect_update_ivs_after_vectorizer().
|
static |
Update PHI nodes for a guard of the LOOP.
Input:
- LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that controls whether LOOP is to be executed. GUARD_EDGE is the edge that originates from the guard-bb, skips LOOP and reaches the (unique) exit bb of LOOP. This loop-exit-bb is an empty bb with one successor. We denote this bb NEW_MERGE_BB because before the guard code was added it had a single predecessor (the LOOP header), and now it became a merge point of two paths - the path that ends with the LOOP exit-edge, and the path that ends with GUARD_EDGE.
- NEW_EXIT_BB: New basic block that is added by this function between LOOP and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
===> The CFG before the guard-code was added: LOOP_header_bb: loop_body if (exit_loop) goto update_bb else goto LOOP_header_bb update_bb:
==> The CFG after the guard-code was added: guard_bb: if (LOOP_guard_condition) goto new_merge_bb else goto LOOP_header_bb LOOP_header_bb: loop_body if (exit_loop_condition) goto new_merge_bb else goto LOOP_header_bb new_merge_bb: goto update_bb update_bb:
==> The CFG after this function: guard_bb: if (LOOP_guard_condition) goto new_merge_bb else goto LOOP_header_bb LOOP_header_bb: loop_body if (exit_loop_condition) goto new_exit_bb else goto LOOP_header_bb new_exit_bb: new_merge_bb: goto update_bb update_bb:
This function:
- creates and updates the relevant phi nodes to account for the new incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves: 1.1. Create phi nodes at NEW_MERGE_BB. 1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted UPDATE_BB). UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
- preserves loop-closed-ssa-form by creating the required phi nodes at the exit of LOOP (i.e, in NEW_EXIT_BB).
There are two flavors to this function:
slpeel_update_phi_nodes_for_guard1: Here the guard controls whether we enter or skip LOOP, where LOOP is a prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are for variables that have phis in the loop header.
slpeel_update_phi_nodes_for_guard2: Here the guard controls whether we enter or skip LOOP, where LOOP is an epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are for variables that have phis in the loop exit.
I.E., the overall structure is:
loop1_preheader_bb:
guard1 (goto loop1/merge1_bb)
loop1
loop1_exit_bb:
guard2 (goto merge1_bb/merge2_bb)
merge1_bb
loop2
loop2_exit_bb
merge2_bb
next_bb
slpeel_update_phi_nodes_for_guard1 takes care of creating phis in loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars that have phis in loop1->header).
slpeel_update_phi_nodes_for_guard2 takes care of creating phis in loop2_exit_bb and merge2_bb. These are exit phis (phis for the vars that have phis in next_bb). It also adds some of these phis to loop1_exit_bb.
slpeel_update_phi_nodes_for_guard1 is always called before slpeel_update_phi_nodes_for_guard2. They are both needed in order to create correct data-flow and loop-closed-ssa-form.
Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables that change between iterations of a loop (and therefore have a phi-node at the loop entry), whereas slpeel_update_phi_nodes_for_guard2 creates phis for variables that are used out of the loop (and therefore have loop-closed exit phis). Some variables may be both updated between iterations and used after the loop. This is why in loop1_exit_bb we may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1) and exit phis (created by slpeel_update_phi_nodes_for_guard2).
- IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of an original loop. i.e., we have:
orig_loop guard_bb (goto LOOP/new_merge) new_loop <– LOOP new_exit new_merge next_bb
If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we have:
new_loop guard_bb (goto LOOP/new_merge) orig_loop <– LOOP new_exit new_merge next_bb
The SSA names defined in the original loop have a current reaching definition that that records the corresponding new ssa-name used in the new duplicated loop copy.
Function slpeel_update_phi_nodes_for_guard1
Input:
- GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
- DEFS - a bitmap of ssa names to mark new names for which we recorded information.
In the context of the overall structure, we have:
loop1_preheader_bb:
guard1 (goto loop1/merge1_bb)
LOOP-> loop1 loop1_exit_bb: guard2 (goto merge1_bb/merge2_bb) merge1_bb loop2 loop2_exit_bb merge2_bb next_bb
For each name updated between loop iterations (i.e - for each name that has an entry (loop-header) phi in LOOP) we create a new phi in:
- merge1_bb (to account for the edge from guard1)
- loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
Create new bb between loop and new_merge_bb.
1. Handle new-merge-point phis
1.1. Generate new phi node in NEW_MERGE_BB:
1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
of LOOP. Set the two phi args in NEW_PHI for these edges: 1.3. Update phi in successor block.
2. Handle loop-closed-ssa-form phis
2.1. Generate new phi node in NEW_EXIT_BB:
2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.
2.3. Update phi in successor of NEW_EXIT_BB:
2.4. Record the newly created name with set_current_def.
We want to find a name such that
name = get_current_def (orig_loop_name)
and to set its current definition as follows:
set_current_def (name, new_phi_name)
If LOOP is a new loop then loop_arg is already the name we're
looking for. If LOOP is the original loop, then loop_arg is
the orig_loop_name and the relevant name is recorded in its
current reaching definition. current_def is not available only if the variable does not
change inside the loop, in which case we also don't care
about recording a current_def for it because we won't be
trying to create loop-exit-phis for it.
|
static |
Function slpeel_update_phi_nodes_for_guard2
Input:
- GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
In the context of the overall structure, we have:
loop1_preheader_bb:
guard1 (goto loop1/merge1_bb)
loop1
loop1_exit_bb:
guard2 (goto merge1_bb/merge2_bb)
merge1_bb
LOOP-> loop2 loop2_exit_bb merge2_bb next_bb
For each name used out side the loop (i.e - for each name that has an exit phi in next_bb) we create a new phi in:
- merge2_bb (to account for the edge from guard_bb)
- loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
- guard2 bb (an exit phi to keep the preceding loop in loop-closed form), if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
Create new bb between loop and new_merge_bb.
This loop-closed-phi actually doesn't represent a use
out of the loop - the phi arg is a constant. 1. Handle new-merge-point phis
1.1. Generate new phi node in NEW_MERGE_BB:
1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
of LOOP. Set the two PHI args in NEW_PHI for these edges: Some variables have both loop-entry-phis and loop-exit-phis.
Such variables were given yet newer names by phis placed in
guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
new_name2 = get_current_def (get_current_def (orig_name)). 1.3. Update phi in successor block.
2. Handle loop-closed-ssa-form phis
2.1. Generate new phi node in NEW_EXIT_BB:
2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop.
2.3. Update phi in successor of NEW_EXIT_BB:
3. Handle loop-closed-ssa-form phis for first loop
3.1. Find the relevant names that need an exit-phi in
GUARD_BB, i.e. names for which
slpeel_update_phi_nodes_for_guard1 had not already created a
phi node. This is the case for names that are used outside
the loop (and therefore need an exit phi) but are not updated
across loop iterations (and therefore don't have a
loop-header-phi).
slpeel_update_phi_nodes_for_guard1 is responsible for
creating loop-exit phis in GUARD_BB for names that have a
loop-header-phi. When such a phi is created we also record
the new name in its current definition. If this new name
exists, then guard_arg was set to this new name (see 1.2
above). Therefore, if guard_arg is not this new name, this
is an indication that an exit-phi in GUARD_BB was not yet
created, so we take care of it here. 3.2. Generate new phi node in GUARD_BB:
3.3. GUARD_BB has one incoming edge:
3.4. Update phi in successor of GUARD_BB:
|
static |
This function builds ni_name = number of iterations loop executes on the loop preheader. If SEQ is given the stmt is instead emitted there.
Referenced by find_loop_location().
| bool vect_can_advance_ivs_p | ( | ) |
Function vect_can_advance_ivs_p
In case the number of iterations that LOOP iterates is unknown at compile time, an epilog loop will be generated, and the loop induction variables (IVs) will be "advanced" to the value they are supposed to take just before the epilog loop. Here we check that the access function of the loop IVs and the expression that represents the loop bound are simple enough. These restrictions will be relaxed in the future.
Analyze phi functions of the loop header.
Skip virtual phi's. The data dependences that are associated with
virtual defs/uses (i.e., memory accesses) are analyzed elsewhere. Skip reduction phis.
Analyze the evolution function.
FORNOW: We do not transform initial conditions of IVs
which evolution functions are a polynomial of degree >= 2.
References adjust_phi_and_debug_stmts(), create_tmp_var, edge_def::dest, dump_enabled_p(), dump_gimple_stmt(), dump_printf(), dump_printf_loc(), fold_build2, fold_build_pointer_plus, fold_convert, force_gimple_operand_gsi(), gcc_assert, gimple_phi_result(), gsi_end_p(), gsi_last_bb(), gsi_next(), GSI_SAME_STMT, gsi_start_phis(), gsi_stmt(), loop::header, init_expr(), loop_preheader_edge(), LOOP_VINFO_LOOP, MSG_MISSED_OPTIMIZATION, MSG_NOTE, PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, POINTER_TYPE_P, single_exit(), single_pred_p(), STMT_VINFO_DEF_TYPE, STMT_VINFO_LOOP_PHI_EVOLUTION_PART, TDF_SLIM, tree_is_chrec(), TREE_TYPE, type(), unshare_expr(), vect_location, vect_reduction_def, vinfo_for_stmt(), and virtual_operand_p().
|
static |
Function vect_create_cond_for_alias_checks.
Create a conditional expression that represents the run-time checks for overlapping of address ranges represented by a list of data references relations passed as input.
Input: COND_EXPR - input conditional expression. New conditions will be chained with logical AND operation. LOOP_VINFO - field LOOP_VINFO_MAY_ALIAS_STMTS contains the list of ddrs to be checked.
Output: COND_EXPR - conditional expression.
The returned value is the conditional expression to be used in the if statement that controls which version of the loop gets executed at runtime.
Create expression ((store_ptr_0 + store_segment_length_0) <= load_ptr_0) || (load_ptr_0 + load_segment_length_0) <= store_ptr_0)) && ... && ((store_ptr_n + store_segment_length_n) <= load_ptr_n) || (load_ptr_n + load_segment_length_n) <= store_ptr_n))
References add_phi_arg(), adjust_phi_and_debug_stmts(), boolean_type_node, build_int_cst(), copy_ssa_name(), create_phi_node(), edge_def::dest, DR_IS_READ, DR_STEP, dump_enabled_p(), dump_printf_loc(), EDGE_COUNT, EDGE_SUCC, flow_bb_inside_loop_p(), fold_build2, FOR_EACH_SSA_TREE_OPERAND, force_gimple_operand_1(), free_original_copy_tables(), gcc_assert, gimple_nop_p(), gimple_phi_arg_location_from_edge(), gimple_seq_add_seq(), gimple_set_vuse(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), initialize_original_copy_tables(), integer_zerop(), is_gimple_assign(), is_gimple_condexpr(), LOCATION_LOCUS, LOOP_REQUIRES_VERSIONING_FOR_ALIAS, LOOP_REQUIRES_VERSIONING_FOR_ALIGNMENT, loop_version(), LOOP_VINFO_BBS, LOOP_VINFO_LOOP, LOOP_VINFO_NITERS, MSG_OPTIMIZED_LOCATIONS, NULL, NULL_TREE, loop::num_nodes, PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, basic_block_def::preds, REG_BR_PROB_BASE, single_exit(), split_edge(), SSA_NAME_DEF_STMT, SSA_OP_USE, STMT_VINFO_DATA_REF, TREE_TYPE, UNKNOWN_LOC, vect_create_cond_for_align_checks(), vect_location, and vinfo_for_stmt().
|
static |
Function vect_create_cond_for_align_checks.
Create a conditional expression that represents the alignment checks for all of data references (array element references) whose alignment must be checked at runtime.
Input: COND_EXPR - input conditional expression. New conditions will be chained with logical AND operation. LOOP_VINFO - two fields of the loop information are used. LOOP_VINFO_PTR_MASK is the mask used to check the alignment. LOOP_VINFO_MAY_MISALIGN_STMTS contains the refs to be checked.
Output: COND_EXPR_STMT_LIST - statements needed to construct the conditional expression. The returned value is the conditional expression to be used in the if statement that controls which version of the loop gets executed at runtime.
The algorithm makes two assumptions: 1) The number of bytes "n" in a vector is a power of 2. 2) An address "a" is aligned if an is zero and that this test can be done as a&(n-1) == 0. For example, for 16 byte vectors the test is a&0xf == 0.
Check that mask is one less than a power of 2, i.e., mask is all zeros followed by all ones.
Create expression (mask & (dr_1 || ... || dr_n)) where dr_i is the address of the first vector of the i'th data reference.
create: addr_tmp = (int)(address_of_first_vector)
The addresses are OR together.
create: or_tmp = or_tmp | addr_tmp
create: and_tmp = or_tmp & mask
Make and_tmp the left operand of the conditional test against zero. if and_tmp has a nonzero bit then some address is unaligned.
Referenced by vect_create_cond_for_alias_checks().
| void vect_do_peeling_for_alignment | ( | loop_vec_info | loop_vinfo, |
| unsigned int | th, | ||
| bool | check_profitability | ||
| ) |
Function vect_do_peeling_for_alignment
Peel the first 'niters' iterations of the loop represented by LOOP_VINFO. 'niters' is set to the misalignment of one of the data references in the loop, thereby forcing it to refer to an aligned location at the beginning of the execution of this loop. The data reference for which we are peeling is recorded in LOOP_VINFO_UNALIGNED_DR.
Peel the prolog loop and iterate it niters_of_prolog_loop.
For vectorization factor N, we need to copy at most N-1 values for alignment and this means N-2 loopback edge executions.
Update number of times loop executes.
Insert stmt on loop preheader edge.
Update the init conditions of the access functions of all data refs.
After peeling we have to reset scalar evolution analyzer.
| void vect_do_peeling_for_loop_bound | ( | loop_vec_info | loop_vinfo, |
| tree * | ratio, | ||
| unsigned int | th, | ||
| bool | check_profitability | ||
| ) |
Function vect_do_peeling_for_loop_bound
Peel the last iterations of the loop represented by LOOP_VINFO. The peeled iterations form a new epilog loop. Given that the loop now iterates NITERS times, the new epilog loop iterates NITERS % VECTORIZATION_FACTOR times.
The original loop will later be made to iterate NITERS / VECTORIZATION_FACTOR times (this value is placed into RATIO).
COND_EXPR and COND_EXPR_STMT_LIST are combined with a new generated test.
Generate the following variables on the preheader of original loop: ni_name = number of iteration the original loop executes ratio = ni_name / vf ratio_mult_vf_name = ratio * vf
A guard that controls whether the new_loop is to be executed or skipped is placed in LOOP->exit. LOOP->exit therefore has two successors - one is the preheader of NEW_LOOP, where the IVs from LOOP are used. The other is a bb after NEW_LOOP, where these IVs are not used. Find the edge that is on the path where the LOOP IVs are used and need to be updated.
Update IVs of original loop as if they were advanced by ratio_mult_vf_name steps.
For vectorization factor N, we need to copy last N-1 values in epilogue and this means N-2 loopback edge executions. PEELING_FOR_GAPS works by subtracting last iteration and thus the epilogue will execute at least LOOP_VINFO_VECT_FACTOR times.
After peeling we have to reset scalar evolution analyzer.
References BITS_PER_UNIT, build_int_cst(), create_tmp_var, DR_STEP, DR_STMT, dump_enabled_p(), dump_generic_expr(), dump_printf(), dump_printf_loc(), exact_log2(), fold_build2, fold_convert, force_gimple_operand(), gcc_assert, gsi_insert_seq_on_edge_immediate(), HOST_WIDE_INT, int_cst_value(), LOOP_PEELING_FOR_ALIGNMENT, loop_preheader_edge(), LOOP_VINFO_LOOP, LOOP_VINFO_UNALIGNED_DR, MSG_NOTE, NULL, NULL_TREE, offset, size_int, size_zero_node, STMT_VINFO_VECTYPE, TDF_SLIM, TREE_CODE, tree_int_cst_compare(), TREE_TYPE, TYPE_ALIGN, TYPE_SIZE_UNIT, TYPE_VECTOR_SUBPARTS, unsigned_type_for(), vect_create_addr_base_for_vector_ref(), vect_location, and vinfo_for_stmt().
|
static |
Function vect_gen_niters_for_prolog_loop
Set the number of iterations for the loop represented by LOOP_VINFO to the minimum between LOOP_NITERS (the original iteration count of the loop) and the misalignment of DR - the data reference recorded in LOOP_VINFO_UNALIGNED_DR (LOOP_VINFO). As a result, after the execution of this loop, the data reference DR will refer to an aligned location.
The following computation is generated:
If the misalignment of DR is known at compile time: addr_mis = int mis = DR_MISALIGNMENT (dr); Else, compute address misalignment in bytes: addr_mis = addr & (vectype_align - 1)
prolog_niters = min (LOOP_NITERS, ((VF - addr_mis/elem_size)&(VF-1))/step)
(elem_size = element type size; an element is the scalar element whose type is the inner type of the vectype)
When the step of the data-ref in the loop is not 1 (as in interleaved data and SLP), the number of iterations of the prolog must be divided by the step (which is equal to the size of interleaved group).
The above formulas assume that VF == number of elements in the vector. This may not hold when there are multiple-types in the loop. In this case, for some data-references in the loop the VF does not represent the number of elements that fit in the vector. Therefore, instead of VF we use TYPE_VECTOR_SUBPARTS.
Create: byte_misalign = addr & (vectype_align - 1)
Create: elem_misalign = byte_misalign / element_size
Create: (niters_type) (nelements - elem_misalign)&(nelements - 1)
Create: prolog_loop_niters = min (iters, loop_niters)
If the loop bound is known at compile time we already verified that it is
greater than vf; since the misalignment ('iters') is at most vf, there's
no need to generate the MIN_EXPR in this case. Insert stmt on loop preheader edge.
References DR_OFFSET, DR_STEP, fold_build2, fold_convert, offset, and sizetype.
|
static |
This function generates the following statements:
ni_name = number of iterations loop executes ratio = ni_name / vf ratio_mult_vf_name = ratio * vf
and places them at the loop preheader edge or in COND_EXPR_STMT_LIST if that is non-NULL.
Generate temporary variable that contains number of iterations loop executes.
If epilogue loop is required because of data accesses with gaps, we subtract one iteration from the total number of iterations here for correct calculation of RATIO.
Create: ratio = ni >> log2(vf)
Create: ratio_mult_vf = ratio << log2 (vf).
Referenced by vect_update_ivs_after_vectorizer().
| void vect_loop_versioning | ( | loop_vec_info | loop_vinfo, |
| unsigned int | th, | ||
| bool | check_profitability | ||
| ) |
Function vect_loop_versioning.
If the loop has data references that may or may not be aligned or/and has data reference relations whose independence was not proven then two versions of the loop need to be generated, one which is vectorized and one which isn't. A test is then generated to control which of the loops is executed. The test checks for the alignment of all of the data references that may or may not be aligned. An additional sequence of runtime tests is generated for each pairs of DDRs whose independence was not proven. The vectorized version of loop is executed only if both alias and alignment tests are passed.
The test generated to check which version of loop is executed is modified to also check for profitability as indicated by the cost model initially.
The versioning precondition(s) are placed in *COND_EXPR and *COND_EXPR_STMT_LIST.
Loop versioning violates an assumption we try to maintain during vectorization - that the loop exit block has a single predecessor. After versioning, the exit block of both loop versions is the same basic block (i.e. it has two predecessors). Just in order to simplify following transformations in the vectorizer, we fix this situation here by adding a new (empty) block on the exit-edge of the loop, with the proper loop-exit phis to maintain loop-closed-form.
Extract load statements on memrefs with zero-stride accesses.
In the loop body, we iterate each statement to check if it is a load.
Then we check the DR_STEP of the data reference. If DR_STEP is zero,
then we will hoist the load statement to the loop preheader. We hoist a statement if all SSA uses in it are defined
outside of the loop. End loop-exit-fixes after versioning.
|
static |
Function vect_update_init_of_dr
NITERS iterations were peeled from LOOP. DR represents a data reference in LOOP. This function updates the information recorded in DR to account for the fact that the first NITERS iterations had already been executed. Specifically, it updates the OFFSET field of DR.
|
static |
Function vect_update_inits_of_drs
NITERS iterations were peeled from the loop represented by LOOP_VINFO. This function updates the information recorded for the data references in the loop to account for the fact that the first NITERS iterations had already been executed. Specifically, it updates the initial_condition of the access_function of all the data_references in the loop.
References LOOP_VINFO_LOOP, and LOOP_VINFO_MAY_MISALIGN_STMTS.
|
static |
Function vect_update_ivs_after_vectorizer.
"Advance" the induction variables of LOOP to the value they should take after the execution of LOOP. This is currently necessary because the vectorizer does not handle induction variables that are used after the loop. Such a situation occurs when the last iterations of LOOP are peeled, because:
- We introduced new uses after LOOP for IVs that were not originally used after LOOP: the IVs of LOOP are now used by an epilog loop.
- LOOP is going to be vectorized; this means that it will iterate N/VF times, whereas the loop IVs should be bumped N times.
Input:
- LOOP - a loop that is going to be vectorized. The last few iterations of LOOP were peeled.
- NITERS - the number of iterations that LOOP executes (before it is vectorized). i.e, the number of times the ivs should be bumped.
UPDATE_E - a successor edge of LOOP->exit that is on the (only) path coming out from LOOP on which there are uses of the LOOP ivs (this is the path from LOOP->exit to epilog_loop->preheader).
The new definitions of the ivs are placed in LOOP->exit. The phi args associated with the edge UPDATE_E in the bb UPDATE_E->dest are updated accordingly.
Assumption 1: Like the rest of the vectorizer, this function assumes a single loop exit that has a single predecessor.
Assumption 2: The phi nodes in the LOOP header and in update_bb are organized in the same order.
Assumption 3: The access function of the ivs is simple enough (see vect_can_advance_ivs_p). This assumption will be relaxed in the future.
Assumption 4: Exactly one of the successors of LOOP exit-bb is on a path coming out of LOOP on which the ivs of LOOP are used (this is the path that leads to the epilog loop; other paths skip the epilog loop). This path starts with the edge UPDATE_E, and its destination (denoted update_bb) needs to have its phis updated.
gcc_assert (vect_can_advance_ivs_p (loop_vinfo));
Make sure there exists a single-predecessor exit bb:
Skip virtual phi's.
Skip reduction phis.
FORNOW: We do not support IVs whose evolution function is a polynomial
of degree >= 2 or exponential. Fix phi expressions in the successor bb.
References dump_enabled_p(), dump_printf(), dump_printf_loc(), EDGE_PRED, free_original_copy_tables(), double_int::from_shwi(), gcc_assert, initialize_original_copy_tables(), loop_preheader_edge(), LOOP_VINFO_LOOP, LOOP_VINFO_PEELING_FOR_GAPS, LOOP_VINFO_VECT_FACTOR, MAX, MSG_NOTE, NULL, NULL_TREE, loop::num, record_niter_bound(), scev_reset(), single_exit(), slpeel_tree_peel_loop_to_edge(), edge_def::src, vect_generate_tmps_on_preheader(), and vect_location.
|
static |
Function vect_vfa_segment_size.
Create an expression that computes the size of segment that will be accessed for a data reference. The functions takes into account that realignment loads may access one more vector.
Input: DR: The data reference. LENGTH_FACTOR: segment length to consider.
Return an expression whose value is the size of segment which will be accessed by DR.
Variable Documentation
|
static |
A stack of values to be adjusted in debug stmts. We have to process them LIFO, so that the closest substitution applies. If we processed them FIFO, without the stack, we might substitute uses with a PHI DEF that would soon become non-dominant, and when we got to the suitable one, it wouldn't have anything to substitute any more.
