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	slpeel_verify_cfg_after_peeling (struct loop first_loop, struct loop second_loop)
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_stack >	adjust_vec

Function Documentation

static void adjust_debug_stmts ( )

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.

References adjust_debug_stmts_now(), adjust_info::bb, adjust_info::from, adjust_info::to, and virtual_operand_p().

Referenced by adjust_phi_and_debug_stmts().

static void adjust_debug_stmts_now ( )

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.

References adjust_info::bb, CDI_DOMINATORS, dom_info_available_p(), dominated_by_p(), adjust_info::from, gimple_bb(), gimple_debug_bind_p(), gimple_debug_bind_reset_value(), is_gimple_debug(), adjust_info::to, and update_stmt().

Referenced by adjust_debug_stmts(), and adjust_vec_debug_stmts().

static void adjust_phi_and_debug_stmts ( )

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 adjust_debug_stmts(), and edge_def::dest_idx.

Referenced by slpeel_update_phi_nodes_for_guard1(), slpeel_update_phi_nodes_for_guard2(), vect_loop_versioning(), and vect_update_ivs_after_vectorizer().

static void adjust_vec_debug_stmts ( )

static

Adjust debug stmts as scheduled before.

References adjust_debug_stmts_now().

Referenced by slpeel_tree_peel_loop_to_edge().

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.

References get_loop_exit_condition(), gimple_location(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_stmt(), loop::header, and si.

Referenced by parallelize_loops(), slpeel_make_loop_iterate_ntimes(), slpeel_tree_peel_loop_to_edge(), and vectorize_loops().

static void rename_use_op ( )

static

@verbatim Vectorizer Specific Loop Manipulations

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.

References get_current_def().

Referenced by rename_variables_in_bb().

static void rename_variables_in_bb ( )

static

Renames the variables in basic block BB.

References flow_bb_inside_loop_p(), gsi_end_p(), gsi_next(), gsi_start_bb(), gsi_start_phis(), gsi_stmt(), basic_block_def::loop_father, basic_block_def::preds, rename_use_op(), and edge_def::src.

Referenced by slpeel_tree_duplicate_loop_to_edge_cfg().

static void set_prologue_iterations	(	basic_block	bb_before_first_loop,
		tree *	first_niters,
		struct loop *	loop,
		unsigned int	th,
		int	probability
	)

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.

References add_phi_arg(), apply_probability(), build_int_cst(), CDI_DOMINATORS, edge_def::count, basic_block_def::count, create_phi_node(), create_tmp_var(), edge_def::flags, force_gimple_operand(), force_gimple_operand_gsi_1(), basic_block_def::frequency, gimple_build_cond_from_tree(), GSI_CONTINUE_LINKING, gsi_insert_after(), gsi_insert_seq_after(), gsi_last_bb(), GSI_NEW_STMT, inverse_probability(), is_gimple_condexpr(), loop_vec_info_for_loop(), make_single_succ_edge(), edge_def::probability, set_immediate_dominator(), single_pred_edge(), split_edge(), and unshare_expr().

Referenced by slpeel_tree_peel_loop_to_edge().

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
	)

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.

References apply_probability(), CDI_DOMINATORS, edge_def::count, basic_block_def::count, edge_def::flags, force_gimple_operand_1(), gimple_build_cond_from_tree(), gimple_seq_add_seq(), gsi_insert_after(), gsi_insert_seq_after(), gsi_last_bb(), GSI_NEW_STMT, inverse_probability(), is_gimple_condexpr(), make_edge(), edge_def::probability, and set_immediate_dominator().

Referenced by slpeel_tree_peel_loop_to_edge().

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.

References empty_block_p(), get_loop_exit_condition(), gsi_last_bb(), gsi_stmt(), loop::inner, loop::latch, loop_outer(), loop_preheader_edge(), loop::num_nodes, single_exit(), and edge_def::src.

Referenced by slpeel_tree_peel_loop_to_edge(), vect_analyze_loop_operations(), and vect_enhance_data_refs_alignment().

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.

References build_int_cst(), create_iv(), dump_enabled_p(), dump_gimple_stmt(), dump_printf(), find_loop_location(), edge_def::flags, force_gimple_operand_gsi(), free_stmt_vec_info(), get_loop_exit_condition(), gimple_build_cond(), gsi_for_stmt(), gsi_insert_before(), gsi_remove(), GSI_SAME_STMT, loop::nb_iterations, single_exit(), and standard_iv_increment_position().

Referenced by slpeel_tree_peel_loop_to_edge(), and vect_transform_loop().

struct loop* slpeel_tree_duplicate_loop_to_edge_cfg ( )

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.

References add_phi_args_after_copy(), can_copy_bbs_p(), CDI_DOMINATORS, copy_bbs(), delete_basic_block(), edge_def::dest, duplicate_loop(), duplicate_subloops(), flush_pending_stmts(), free(), get_immediate_dominator(), get_loop_body_with_size(), loop::header, loop_outer(), loop_preheader_edge(), loop::num_nodes, redirect_edge_and_branch_force(), redirect_edge_pred(), rename_variables_in_bb(), set_immediate_dominator(), single_exit(), single_pred(), single_pred_edge(), single_succ_edge(), split_edge(), edge_def::src, and verify_dominators().

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
	)

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.

References add_phi_arg(), adjust_vec_debug_stmts(), apply_probability(), build_int_cst(), combine_probabilities(), copy_ssa_name(), edge_def::count, basic_block_def::count, create_phi_node(), delete_update_ssa(), edge_def::dest, dump_printf_loc(), find_loop_location(), basic_block_def::frequency, gimple_phi_result(), gimple_phi_set_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, inverse_probability(), loop::latch, loop_preheader_edge(), loop_vec_info_for_loop(), scale_loop_profile(), set_prologue_iterations(), single_exit(), single_succ_edge(), slpeel_add_loop_guard(), slpeel_can_duplicate_loop_p(), slpeel_make_loop_iterate_ntimes(), slpeel_tree_duplicate_loop_to_edge_cfg(), slpeel_update_phi_nodes_for_guard1(), slpeel_update_phi_nodes_for_guard2(), split_edge(), unshare_expr(), update_ssa(), and virtual_operand_p().

Referenced by vect_do_peeling_for_alignment(), and vect_do_peeling_for_loop_bound().

static void slpeel_update_phi_nodes_for_guard1	(	edge	guard_edge,
		struct loop *	loop,
		bool	is_new_loop,
		basic_block *	new_exit_bb
	)

static

@verbatim 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:
   1. merge1_bb (to account for the edge from guard1)
   2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)

Handle new-merge-point phis *

Handle loop-closed-ssa-form phis *

References add_phi_arg(), adjust_phi_and_debug_stmts(), copy_ssa_name(), create_phi_node(), edge_def::dest, get_current_def(), gimple_phi_arg_location_from_edge(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, loop::latch, loop_preheader_edge(), set_current_def(), single_exit(), split_edge(), and virtual_operand_p().

Referenced by slpeel_tree_peel_loop_to_edge().

static void slpeel_update_phi_nodes_for_guard2	(	edge	guard_edge,
		struct loop *	loop,
		bool	is_new_loop,
		basic_block *	new_exit_bb
	)

static

@verbatim 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).

Handle new-merge-point phis *

Handle loop-closed-ssa-form phis *

Handle loop-closed-ssa-form phis for first loop *

References add_phi_arg(), adjust_phi_and_debug_stmts(), copy_ssa_name(), create_phi_node(), edge_def::dest, get_current_def(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), basic_block_def::preds, single_exit(), split_edge(), and edge_def::src.

Referenced by slpeel_tree_peel_loop_to_edge().

static void slpeel_verify_cfg_after_peeling	(	struct loop *	first_loop,
		struct loop *	second_loop
	)

static

References edge_def::dest, loop_preheader_edge(), basic_block_def::preds, single_exit(), edge_def::src, and basic_block_def::succs.

Referenced by vect_do_peeling_for_alignment(), and vect_do_peeling_for_loop_bound().

static tree vect_build_loop_niters ( )

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.

References create_tmp_var(), force_gimple_operand(), gimple_seq_add_seq(), gsi_insert_seq_on_edge_immediate(), loop_preheader_edge(), and unshare_expr().

Referenced by vect_do_peeling_for_alignment(), and vect_generate_tmps_on_preheader().

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.

References dump_enabled_p(), dump_gimple_stmt(), dump_printf(), dump_printf_loc(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, tree_is_chrec(), vect_location, vect_reduction_def, vinfo_for_stmt(), and virtual_operand_p().

Referenced by vect_analyze_loop_operations(), and vect_enhance_data_refs_alignment().

static void vect_create_cond_for_alias_checks ( )

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.

References DDR_A, DDR_B, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_REF, DR_STEP, DR_STMT, dump_enabled_p(), dump_generic_expr(), dump_printf(), dump_printf_loc(), operand_equal_p(), tree_int_cst_compare(), vect_location, vect_vfa_segment_size(), and vinfo_for_stmt().

Referenced by vect_loop_versioning().

static void vect_create_cond_for_align_checks	(	loop_vec_info	loop_vinfo,
		tree *	cond_expr,
		gimple_seq *	cond_expr_stmt_list
	)

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 a%n 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.

References build_int_cst(), DR_STEP, gimple_build_assign_with_ops(), gimple_seq_add_seq(), gimple_seq_add_stmt(), make_temp_ssa_name(), offset, signed_type_for(), tree_int_cst_compare(), vect_create_addr_base_for_vector_ref(), and vinfo_for_stmt().

Referenced by vect_loop_versioning().

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.

References create_tmp_var(), dump_enabled_p(), dump_printf(), dump_printf_loc(), force_gimple_operand(), free_original_copy_tables(), double_int::from_shwi(), gsi_insert_seq_on_edge_immediate(), initialize_original_copy_tables(), loop_preheader_edge(), record_niter_bound(), scev_reset(), slpeel_tree_peel_loop_to_edge(), slpeel_verify_cfg_after_peeling(), types_compatible_p(), vect_build_loop_niters(), vect_gen_niters_for_prolog_loop(), vect_location, and vect_update_inits_of_drs().

Referenced by vect_transform_loop().

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.

References dump_enabled_p(), dump_printf(), dump_printf_loc(), free_original_copy_tables(), double_int::from_shwi(), initialize_original_copy_tables(), loop_preheader_edge(), loop::num, record_niter_bound(), scev_reset(), single_exit(), slpeel_tree_peel_loop_to_edge(), slpeel_verify_cfg_after_peeling(), edge_def::src, vect_generate_tmps_on_preheader(), vect_location, and vect_update_ivs_after_vectorizer().

Referenced by vect_transform_loop().

static tree vect_gen_niters_for_prolog_loop ( )

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.

References build_int_cst(), create_tmp_var(), DR_STEP, DR_STMT, dump_enabled_p(), dump_generic_expr(), dump_printf_loc(), exact_log2(), force_gimple_operand(), gsi_insert_seq_on_edge_immediate(), HOST_WIDE_INT, int_cst_value(), loop_preheader_edge(), offset, tree_int_cst_compare(), unsigned_type_for(), vect_create_addr_base_for_vector_ref(), vect_location, and vinfo_for_stmt().

Referenced by vect_do_peeling_for_alignment().

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
	)

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.

References build_int_cst(), build_one_cst(), create_tmp_var(), exact_log2(), force_gimple_operand(), gimple_seq_add_seq(), gsi_insert_seq_on_edge_immediate(), is_gimple_val(), loop_preheader_edge(), and vect_build_loop_niters().

Referenced by vect_do_peeling_for_loop_bound().

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.

References add_phi_arg(), adjust_phi_and_debug_stmts(), build_int_cst(), copy_ssa_name(), create_phi_node(), edge_def::dest, force_gimple_operand_1(), free_original_copy_tables(), gimple_phi_arg_location_from_edge(), gimple_seq_add_seq(), gsi_end_p(), gsi_insert_seq_before(), gsi_last_bb(), gsi_next(), GSI_SAME_STMT, gsi_start_phis(), gsi_stmt(), initialize_original_copy_tables(), is_gimple_condexpr(), loop_version(), basic_block_def::preds, prob, single_exit(), split_edge(), update_ssa(), vect_create_cond_for_alias_checks(), and vect_create_cond_for_align_checks().

Referenced by vect_transform_loop().

static void vect_update_init_of_dr ( )

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.

References DR_OFFSET, DR_STEP, and offset.

Referenced by vect_update_inits_of_drs().

static void vect_update_inits_of_drs ( )

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 dump_enabled_p(), dump_printf_loc(), vect_location, and vect_update_init_of_dr().

Referenced by vect_do_peeling_for_alignment().

static void vect_update_ivs_after_vectorizer	(	loop_vec_info	loop_vinfo,
		tree	niters,
		edge	update_e
	)

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:
     1. 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.
     2. 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.

References adjust_phi_and_debug_stmts(), create_tmp_var(), edge_def::dest, dump_enabled_p(), dump_gimple_stmt(), dump_printf_loc(), force_gimple_operand_gsi(), 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(), single_exit(), single_pred_p(), tree_is_chrec(), type(), unshare_expr(), vect_location, vect_reduction_def, vinfo_for_stmt(), and virtual_operand_p().

Referenced by vect_do_peeling_for_loop_bound().

static tree vect_vfa_segment_size ( )

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.

References dr_explicit_realign_optimized, DR_REF, DR_STEP, DR_STMT, integer_zerop(), vect_supportable_dr_alignment(), and vinfo_for_stmt().

Referenced by vect_create_cond_for_alias_checks().

Variable Documentation

vec<adjust_info, va_stack> adjust_vec

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.

Data Structures

Functions

Variables

Function Documentation

Variable Documentation