/* Loop Vectorization
|
/* Loop Vectorization
|
Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
|
Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
|
Contributed by Dorit Naishlos <dorit@il.ibm.com>
|
Contributed by Dorit Naishlos <dorit@il.ibm.com>
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it under
|
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
|
the terms of the GNU General Public License as published by the Free
|
Software Foundation; either version 3, or (at your option) any later
|
Software Foundation; either version 3, or (at your option) any later
|
version.
|
version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
/* Loop Vectorization Pass.
|
/* Loop Vectorization Pass.
|
|
|
This pass tries to vectorize loops. This first implementation focuses on
|
This pass tries to vectorize loops. This first implementation focuses on
|
simple inner-most loops, with no conditional control flow, and a set of
|
simple inner-most loops, with no conditional control flow, and a set of
|
simple operations which vector form can be expressed using existing
|
simple operations which vector form can be expressed using existing
|
tree codes (PLUS, MULT etc).
|
tree codes (PLUS, MULT etc).
|
|
|
For example, the vectorizer transforms the following simple loop:
|
For example, the vectorizer transforms the following simple loop:
|
|
|
short a[N]; short b[N]; short c[N]; int i;
|
short a[N]; short b[N]; short c[N]; int i;
|
|
|
for (i=0; i<N; i++){
|
for (i=0; i<N; i++){
|
a[i] = b[i] + c[i];
|
a[i] = b[i] + c[i];
|
}
|
}
|
|
|
as if it was manually vectorized by rewriting the source code into:
|
as if it was manually vectorized by rewriting the source code into:
|
|
|
typedef int __attribute__((mode(V8HI))) v8hi;
|
typedef int __attribute__((mode(V8HI))) v8hi;
|
short a[N]; short b[N]; short c[N]; int i;
|
short a[N]; short b[N]; short c[N]; int i;
|
v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
|
v8hi *pa = (v8hi*)a, *pb = (v8hi*)b, *pc = (v8hi*)c;
|
v8hi va, vb, vc;
|
v8hi va, vb, vc;
|
|
|
for (i=0; i<N/8; i++){
|
for (i=0; i<N/8; i++){
|
vb = pb[i];
|
vb = pb[i];
|
vc = pc[i];
|
vc = pc[i];
|
va = vb + vc;
|
va = vb + vc;
|
pa[i] = va;
|
pa[i] = va;
|
}
|
}
|
|
|
The main entry to this pass is vectorize_loops(), in which
|
The main entry to this pass is vectorize_loops(), in which
|
the vectorizer applies a set of analyses on a given set of loops,
|
the vectorizer applies a set of analyses on a given set of loops,
|
followed by the actual vectorization transformation for the loops that
|
followed by the actual vectorization transformation for the loops that
|
had successfully passed the analysis phase.
|
had successfully passed the analysis phase.
|
|
|
Throughout this pass we make a distinction between two types of
|
Throughout this pass we make a distinction between two types of
|
data: scalars (which are represented by SSA_NAMES), and memory references
|
data: scalars (which are represented by SSA_NAMES), and memory references
|
("data-refs"). These two types of data require different handling both
|
("data-refs"). These two types of data require different handling both
|
during analysis and transformation. The types of data-refs that the
|
during analysis and transformation. The types of data-refs that the
|
vectorizer currently supports are ARRAY_REFS which base is an array DECL
|
vectorizer currently supports are ARRAY_REFS which base is an array DECL
|
(not a pointer), and INDIRECT_REFS through pointers; both array and pointer
|
(not a pointer), and INDIRECT_REFS through pointers; both array and pointer
|
accesses are required to have a simple (consecutive) access pattern.
|
accesses are required to have a simple (consecutive) access pattern.
|
|
|
Analysis phase:
|
Analysis phase:
|
===============
|
===============
|
The driver for the analysis phase is vect_analyze_loop_nest().
|
The driver for the analysis phase is vect_analyze_loop_nest().
|
It applies a set of analyses, some of which rely on the scalar evolution
|
It applies a set of analyses, some of which rely on the scalar evolution
|
analyzer (scev) developed by Sebastian Pop.
|
analyzer (scev) developed by Sebastian Pop.
|
|
|
During the analysis phase the vectorizer records some information
|
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
|
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
|
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.
|
recorded in a "loop_vec_info" struct attached to each loop.
|
|
|
Transformation phase:
|
Transformation phase:
|
=====================
|
=====================
|
The loop transformation phase scans all the stmts in the loop, and
|
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
|
creates a vector stmt (or a sequence of stmts) for each scalar stmt S in
|
the loop that needs to be vectorized. It insert the vector code sequence
|
the loop that needs to be vectorized. It insert the vector code sequence
|
just before the scalar stmt S, and records a pointer to the vector code
|
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
|
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
|
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;
|
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.
|
otherwise, we rely on dead code elimination for removing it.
|
|
|
For example, say stmt S1 was vectorized into stmt VS1:
|
For example, say stmt S1 was vectorized into stmt VS1:
|
|
|
VS1: vb = px[i];
|
VS1: vb = px[i];
|
S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
|
S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
|
S2: a = b;
|
S2: a = b;
|
|
|
To vectorize stmt S2, the vectorizer first finds the stmt that defines
|
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
|
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
|
vector stmt VS1 pointed to by STMT_VINFO_VEC_STMT (stmt_info (S1)). The
|
resulting sequence would be:
|
resulting sequence would be:
|
|
|
VS1: vb = px[i];
|
VS1: vb = px[i];
|
S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
|
S1: b = x[i]; STMT_VINFO_VEC_STMT (stmt_info (S1)) = VS1
|
VS2: va = vb;
|
VS2: va = vb;
|
S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
|
S2: a = b; STMT_VINFO_VEC_STMT (stmt_info (S2)) = VS2
|
|
|
Operands that are not SSA_NAMEs, are data-refs that appear in
|
Operands that are not SSA_NAMEs, are data-refs that appear in
|
load/store operations (like 'x[i]' in S1), and are handled differently.
|
load/store operations (like 'x[i]' in S1), and are handled differently.
|
|
|
Target modeling:
|
Target modeling:
|
=================
|
=================
|
Currently the only target specific information that is used is the
|
Currently the only target specific information that is used is the
|
size of the vector (in bytes) - "UNITS_PER_SIMD_WORD". Targets that can
|
size of the vector (in bytes) - "UNITS_PER_SIMD_WORD". Targets that can
|
support different sizes of vectors, for now will need to specify one value
|
support different sizes of vectors, for now will need to specify one value
|
for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
|
for "UNITS_PER_SIMD_WORD". More flexibility will be added in the future.
|
|
|
Since we only vectorize operations which vector form can be
|
Since we only vectorize operations which vector form can be
|
expressed using existing tree codes, to verify that an operation is
|
expressed using existing tree codes, to verify that an operation is
|
supported, the vectorizer checks the relevant optab at the relevant
|
supported, the vectorizer checks the relevant optab at the relevant
|
machine_mode (e.g, add_optab->handlers[(int) V8HImode].insn_code). If
|
machine_mode (e.g, add_optab->handlers[(int) V8HImode].insn_code). If
|
the value found is CODE_FOR_nothing, then there's no target support, and
|
the value found is CODE_FOR_nothing, then there's no target support, and
|
we can't vectorize the stmt.
|
we can't vectorize the stmt.
|
|
|
For additional information on this project see:
|
For additional information on this project see:
|
http://gcc.gnu.org/projects/tree-ssa/vectorization.html
|
http://gcc.gnu.org/projects/tree-ssa/vectorization.html
|
*/
|
*/
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "ggc.h"
|
#include "ggc.h"
|
#include "tree.h"
|
#include "tree.h"
|
#include "target.h"
|
#include "target.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "diagnostic.h"
|
#include "diagnostic.h"
|
#include "tree-flow.h"
|
#include "tree-flow.h"
|
#include "tree-dump.h"
|
#include "tree-dump.h"
|
#include "timevar.h"
|
#include "timevar.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "cfglayout.h"
|
#include "cfglayout.h"
|
#include "expr.h"
|
#include "expr.h"
|
#include "optabs.h"
|
#include "optabs.h"
|
#include "params.h"
|
#include "params.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "tree-chrec.h"
|
#include "tree-chrec.h"
|
#include "tree-data-ref.h"
|
#include "tree-data-ref.h"
|
#include "tree-scalar-evolution.h"
|
#include "tree-scalar-evolution.h"
|
#include "input.h"
|
#include "input.h"
|
#include "tree-vectorizer.h"
|
#include "tree-vectorizer.h"
|
#include "tree-pass.h"
|
#include "tree-pass.h"
|
|
|
/*************************************************************************
|
/*************************************************************************
|
Simple Loop Peeling Utilities
|
Simple Loop Peeling Utilities
|
*************************************************************************/
|
*************************************************************************/
|
static struct loop *slpeel_tree_duplicate_loop_to_edge_cfg
|
static struct loop *slpeel_tree_duplicate_loop_to_edge_cfg
|
(struct loop *, struct loops *, edge);
|
(struct loop *, struct loops *, edge);
|
static void slpeel_update_phis_for_duplicate_loop
|
static void slpeel_update_phis_for_duplicate_loop
|
(struct loop *, struct loop *, bool after);
|
(struct loop *, struct loop *, bool after);
|
static void slpeel_update_phi_nodes_for_guard1
|
static void slpeel_update_phi_nodes_for_guard1
|
(edge, struct loop *, bool, basic_block *, bitmap *);
|
(edge, struct loop *, bool, basic_block *, bitmap *);
|
static void slpeel_update_phi_nodes_for_guard2
|
static void slpeel_update_phi_nodes_for_guard2
|
(edge, struct loop *, bool, basic_block *);
|
(edge, struct loop *, bool, basic_block *);
|
static edge slpeel_add_loop_guard (basic_block, tree, basic_block, basic_block);
|
static edge slpeel_add_loop_guard (basic_block, tree, basic_block, basic_block);
|
|
|
static void rename_use_op (use_operand_p);
|
static void rename_use_op (use_operand_p);
|
static void rename_variables_in_bb (basic_block);
|
static void rename_variables_in_bb (basic_block);
|
static void rename_variables_in_loop (struct loop *);
|
static void rename_variables_in_loop (struct loop *);
|
|
|
/*************************************************************************
|
/*************************************************************************
|
General Vectorization Utilities
|
General Vectorization Utilities
|
*************************************************************************/
|
*************************************************************************/
|
static void vect_set_dump_settings (void);
|
static void vect_set_dump_settings (void);
|
|
|
/* vect_dump will be set to stderr or dump_file if exist. */
|
/* vect_dump will be set to stderr or dump_file if exist. */
|
FILE *vect_dump;
|
FILE *vect_dump;
|
|
|
/* vect_verbosity_level set to an invalid value
|
/* vect_verbosity_level set to an invalid value
|
to mark that it's uninitialized. */
|
to mark that it's uninitialized. */
|
enum verbosity_levels vect_verbosity_level = MAX_VERBOSITY_LEVEL;
|
enum verbosity_levels vect_verbosity_level = MAX_VERBOSITY_LEVEL;
|
|
|
/* Number of loops, at the beginning of vectorization. */
|
/* Number of loops, at the beginning of vectorization. */
|
unsigned int vect_loops_num;
|
unsigned int vect_loops_num;
|
|
|
/* Loop location. */
|
/* Loop location. */
|
static LOC vect_loop_location;
|
static LOC vect_loop_location;
|
|
|
/* Bitmap of virtual variables to be renamed. */
|
/* Bitmap of virtual variables to be renamed. */
|
bitmap vect_vnames_to_rename;
|
bitmap vect_vnames_to_rename;
|
|
|
/*************************************************************************
|
/*************************************************************************
|
Simple Loop Peeling Utilities
|
Simple Loop Peeling Utilities
|
|
|
Utilities to support loop peeling for vectorization purposes.
|
Utilities to support loop peeling for vectorization purposes.
|
*************************************************************************/
|
*************************************************************************/
|
|
|
|
|
/* Renames the use *OP_P. */
|
/* Renames the use *OP_P. */
|
|
|
static void
|
static void
|
rename_use_op (use_operand_p op_p)
|
rename_use_op (use_operand_p op_p)
|
{
|
{
|
tree new_name;
|
tree new_name;
|
|
|
if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
|
if (TREE_CODE (USE_FROM_PTR (op_p)) != SSA_NAME)
|
return;
|
return;
|
|
|
new_name = get_current_def (USE_FROM_PTR (op_p));
|
new_name = get_current_def (USE_FROM_PTR (op_p));
|
|
|
/* Something defined outside of the loop. */
|
/* Something defined outside of the loop. */
|
if (!new_name)
|
if (!new_name)
|
return;
|
return;
|
|
|
/* An ordinary ssa name defined in the loop. */
|
/* An ordinary ssa name defined in the loop. */
|
|
|
SET_USE (op_p, new_name);
|
SET_USE (op_p, new_name);
|
}
|
}
|
|
|
|
|
/* Renames the variables in basic block BB. */
|
/* Renames the variables in basic block BB. */
|
|
|
static void
|
static void
|
rename_variables_in_bb (basic_block bb)
|
rename_variables_in_bb (basic_block bb)
|
{
|
{
|
tree phi;
|
tree phi;
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
tree stmt;
|
tree stmt;
|
use_operand_p use_p;
|
use_operand_p use_p;
|
ssa_op_iter iter;
|
ssa_op_iter iter;
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
struct loop *loop = bb->loop_father;
|
struct loop *loop = bb->loop_father;
|
|
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
|
{
|
{
|
stmt = bsi_stmt (bsi);
|
stmt = bsi_stmt (bsi);
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
|
FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
|
(SSA_OP_ALL_USES | SSA_OP_ALL_KILLS))
|
(SSA_OP_ALL_USES | SSA_OP_ALL_KILLS))
|
rename_use_op (use_p);
|
rename_use_op (use_p);
|
}
|
}
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
{
|
{
|
if (!flow_bb_inside_loop_p (loop, e->dest))
|
if (!flow_bb_inside_loop_p (loop, e->dest))
|
continue;
|
continue;
|
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
|
rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e));
|
rename_use_op (PHI_ARG_DEF_PTR_FROM_EDGE (phi, e));
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Renames variables in new generated LOOP. */
|
/* Renames variables in new generated LOOP. */
|
|
|
static void
|
static void
|
rename_variables_in_loop (struct loop *loop)
|
rename_variables_in_loop (struct loop *loop)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
basic_block *bbs;
|
basic_block *bbs;
|
|
|
bbs = get_loop_body (loop);
|
bbs = get_loop_body (loop);
|
|
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
rename_variables_in_bb (bbs[i]);
|
rename_variables_in_bb (bbs[i]);
|
|
|
free (bbs);
|
free (bbs);
|
}
|
}
|
|
|
|
|
/* Update the PHI nodes of NEW_LOOP.
|
/* Update the PHI nodes of NEW_LOOP.
|
|
|
NEW_LOOP is a duplicate of ORIG_LOOP.
|
NEW_LOOP is a duplicate of ORIG_LOOP.
|
AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
|
AFTER indicates whether NEW_LOOP executes before or after ORIG_LOOP:
|
AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
|
AFTER is true if NEW_LOOP executes after ORIG_LOOP, and false if it
|
executes before it. */
|
executes before it. */
|
|
|
static void
|
static void
|
slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
|
slpeel_update_phis_for_duplicate_loop (struct loop *orig_loop,
|
struct loop *new_loop, bool after)
|
struct loop *new_loop, bool after)
|
{
|
{
|
tree new_ssa_name;
|
tree new_ssa_name;
|
tree phi_new, phi_orig;
|
tree phi_new, phi_orig;
|
tree def;
|
tree def;
|
edge orig_loop_latch = loop_latch_edge (orig_loop);
|
edge orig_loop_latch = loop_latch_edge (orig_loop);
|
edge orig_entry_e = loop_preheader_edge (orig_loop);
|
edge orig_entry_e = loop_preheader_edge (orig_loop);
|
edge new_loop_exit_e = new_loop->single_exit;
|
edge new_loop_exit_e = new_loop->single_exit;
|
edge new_loop_entry_e = loop_preheader_edge (new_loop);
|
edge new_loop_entry_e = loop_preheader_edge (new_loop);
|
edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
|
edge entry_arg_e = (after ? orig_loop_latch : orig_entry_e);
|
|
|
/*
|
/*
|
step 1. For each loop-header-phi:
|
step 1. For each loop-header-phi:
|
Add the first phi argument for the phi in NEW_LOOP
|
Add the first phi argument for the phi in NEW_LOOP
|
(the one associated with the entry of NEW_LOOP)
|
(the one associated with the entry of NEW_LOOP)
|
|
|
step 2. For each loop-header-phi:
|
step 2. For each loop-header-phi:
|
Add the second phi argument for the phi in NEW_LOOP
|
Add the second phi argument for the phi in NEW_LOOP
|
(the one associated with the latch of NEW_LOOP)
|
(the one associated with the latch of NEW_LOOP)
|
|
|
step 3. Update the phis in the successor block of NEW_LOOP.
|
step 3. Update the phis in the successor block of NEW_LOOP.
|
|
|
case 1: NEW_LOOP was placed before ORIG_LOOP:
|
case 1: NEW_LOOP was placed before ORIG_LOOP:
|
The successor block of NEW_LOOP is the header of ORIG_LOOP.
|
The successor block of NEW_LOOP is the header of ORIG_LOOP.
|
Updating the phis in the successor block can therefore be done
|
Updating the phis in the successor block can therefore be done
|
along with the scanning of the loop header phis, because the
|
along with the scanning of the loop header phis, because the
|
header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
|
header blocks of ORIG_LOOP and NEW_LOOP have exactly the same
|
phi nodes, organized in the same order.
|
phi nodes, organized in the same order.
|
|
|
case 2: NEW_LOOP was placed after ORIG_LOOP:
|
case 2: NEW_LOOP was placed after ORIG_LOOP:
|
The successor block of NEW_LOOP is the original exit block of
|
The successor block of NEW_LOOP is the original exit block of
|
ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
|
ORIG_LOOP - the phis to be updated are the loop-closed-ssa phis.
|
We postpone updating these phis to a later stage (when
|
We postpone updating these phis to a later stage (when
|
loop guards are added).
|
loop guards are added).
|
*/
|
*/
|
|
|
|
|
/* Scan the phis in the headers of the old and new loops
|
/* Scan the phis in the headers of the old and new loops
|
(they are organized in exactly the same order). */
|
(they are organized in exactly the same order). */
|
|
|
for (phi_new = phi_nodes (new_loop->header),
|
for (phi_new = phi_nodes (new_loop->header),
|
phi_orig = phi_nodes (orig_loop->header);
|
phi_orig = phi_nodes (orig_loop->header);
|
phi_new && phi_orig;
|
phi_new && phi_orig;
|
phi_new = PHI_CHAIN (phi_new), phi_orig = PHI_CHAIN (phi_orig))
|
phi_new = PHI_CHAIN (phi_new), phi_orig = PHI_CHAIN (phi_orig))
|
{
|
{
|
/* step 1. */
|
/* step 1. */
|
def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
|
def = PHI_ARG_DEF_FROM_EDGE (phi_orig, entry_arg_e);
|
add_phi_arg (phi_new, def, new_loop_entry_e);
|
add_phi_arg (phi_new, def, new_loop_entry_e);
|
|
|
/* step 2. */
|
/* step 2. */
|
def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
|
def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
|
if (TREE_CODE (def) != SSA_NAME)
|
if (TREE_CODE (def) != SSA_NAME)
|
continue;
|
continue;
|
|
|
new_ssa_name = get_current_def (def);
|
new_ssa_name = get_current_def (def);
|
if (!new_ssa_name)
|
if (!new_ssa_name)
|
{
|
{
|
/* This only happens if there are no definitions
|
/* This only happens if there are no definitions
|
inside the loop. use the phi_result in this case. */
|
inside the loop. use the phi_result in this case. */
|
new_ssa_name = PHI_RESULT (phi_new);
|
new_ssa_name = PHI_RESULT (phi_new);
|
}
|
}
|
|
|
/* An ordinary ssa name defined in the loop. */
|
/* An ordinary ssa name defined in the loop. */
|
add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
|
add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
|
|
|
/* step 3 (case 1). */
|
/* step 3 (case 1). */
|
if (!after)
|
if (!after)
|
{
|
{
|
gcc_assert (new_loop_exit_e == orig_entry_e);
|
gcc_assert (new_loop_exit_e == orig_entry_e);
|
SET_PHI_ARG_DEF (phi_orig,
|
SET_PHI_ARG_DEF (phi_orig,
|
new_loop_exit_e->dest_idx,
|
new_loop_exit_e->dest_idx,
|
new_ssa_name);
|
new_ssa_name);
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Update PHI nodes for a guard of the LOOP.
|
/* Update PHI nodes for a guard of the LOOP.
|
|
|
Input:
|
Input:
|
- LOOP, GUARD_EDGE: LOOP is a loop for which we added guard code that
|
- 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
|
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
|
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.
|
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
|
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
|
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
|
point of two paths - the path that ends with the LOOP exit-edge, and
|
the path that ends with GUARD_EDGE.
|
the path that ends with GUARD_EDGE.
|
- NEW_EXIT_BB: New basic block that is added by this function between LOOP
|
- 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.
|
and NEW_MERGE_BB. It is used to place loop-closed-ssa-form exit-phis.
|
|
|
===> The CFG before the guard-code was added:
|
===> The CFG before the guard-code was added:
|
LOOP_header_bb:
|
LOOP_header_bb:
|
loop_body
|
loop_body
|
if (exit_loop) goto update_bb
|
if (exit_loop) goto update_bb
|
else goto LOOP_header_bb
|
else goto LOOP_header_bb
|
update_bb:
|
update_bb:
|
|
|
==> The CFG after the guard-code was added:
|
==> The CFG after the guard-code was added:
|
guard_bb:
|
guard_bb:
|
if (LOOP_guard_condition) goto new_merge_bb
|
if (LOOP_guard_condition) goto new_merge_bb
|
else goto LOOP_header_bb
|
else goto LOOP_header_bb
|
LOOP_header_bb:
|
LOOP_header_bb:
|
loop_body
|
loop_body
|
if (exit_loop_condition) goto new_merge_bb
|
if (exit_loop_condition) goto new_merge_bb
|
else goto LOOP_header_bb
|
else goto LOOP_header_bb
|
new_merge_bb:
|
new_merge_bb:
|
goto update_bb
|
goto update_bb
|
update_bb:
|
update_bb:
|
|
|
==> The CFG after this function:
|
==> The CFG after this function:
|
guard_bb:
|
guard_bb:
|
if (LOOP_guard_condition) goto new_merge_bb
|
if (LOOP_guard_condition) goto new_merge_bb
|
else goto LOOP_header_bb
|
else goto LOOP_header_bb
|
LOOP_header_bb:
|
LOOP_header_bb:
|
loop_body
|
loop_body
|
if (exit_loop_condition) goto new_exit_bb
|
if (exit_loop_condition) goto new_exit_bb
|
else goto LOOP_header_bb
|
else goto LOOP_header_bb
|
new_exit_bb:
|
new_exit_bb:
|
new_merge_bb:
|
new_merge_bb:
|
goto update_bb
|
goto update_bb
|
update_bb:
|
update_bb:
|
|
|
This function:
|
This function:
|
1. creates and updates the relevant phi nodes to account for the new
|
1. creates and updates the relevant phi nodes to account for the new
|
incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
|
incoming edge (GUARD_EDGE) into NEW_MERGE_BB. This involves:
|
1.1. Create phi nodes at NEW_MERGE_BB.
|
1.1. Create phi nodes at NEW_MERGE_BB.
|
1.2. Update the phi nodes at the successor of NEW_MERGE_BB (denoted
|
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
|
UPDATE_BB). UPDATE_BB was the exit-bb of LOOP before NEW_MERGE_BB
|
2. preserves loop-closed-ssa-form by creating the required phi nodes
|
2. preserves loop-closed-ssa-form by creating the required phi nodes
|
at the exit of LOOP (i.e, in NEW_EXIT_BB).
|
at the exit of LOOP (i.e, in NEW_EXIT_BB).
|
|
|
There are two flavors to this function:
|
There are two flavors to this function:
|
|
|
slpeel_update_phi_nodes_for_guard1:
|
slpeel_update_phi_nodes_for_guard1:
|
Here the guard controls whether we enter or skip LOOP, where LOOP is a
|
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
|
prolog_loop (loop1 below), and the new phis created in NEW_MERGE_BB are
|
for variables that have phis in the loop header.
|
for variables that have phis in the loop header.
|
|
|
slpeel_update_phi_nodes_for_guard2:
|
slpeel_update_phi_nodes_for_guard2:
|
Here the guard controls whether we enter or skip LOOP, where LOOP is an
|
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
|
epilog_loop (loop2 below), and the new phis created in NEW_MERGE_BB are
|
for variables that have phis in the loop exit.
|
for variables that have phis in the loop exit.
|
|
|
I.E., the overall structure is:
|
I.E., the overall structure is:
|
|
|
loop1_preheader_bb:
|
loop1_preheader_bb:
|
guard1 (goto loop1/merg1_bb)
|
guard1 (goto loop1/merg1_bb)
|
loop1
|
loop1
|
loop1_exit_bb:
|
loop1_exit_bb:
|
guard2 (goto merge1_bb/merge2_bb)
|
guard2 (goto merge1_bb/merge2_bb)
|
merge1_bb
|
merge1_bb
|
loop2
|
loop2
|
loop2_exit_bb
|
loop2_exit_bb
|
merge2_bb
|
merge2_bb
|
next_bb
|
next_bb
|
|
|
slpeel_update_phi_nodes_for_guard1 takes care of creating phis in
|
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
|
loop1_exit_bb and merge1_bb. These are entry phis (phis for the vars
|
that have phis in loop1->header).
|
that have phis in loop1->header).
|
|
|
slpeel_update_phi_nodes_for_guard2 takes care of creating phis in
|
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
|
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
|
that have phis in next_bb). It also adds some of these phis to
|
loop1_exit_bb.
|
loop1_exit_bb.
|
|
|
slpeel_update_phi_nodes_for_guard1 is always called before
|
slpeel_update_phi_nodes_for_guard1 is always called before
|
slpeel_update_phi_nodes_for_guard2. They are both needed in order
|
slpeel_update_phi_nodes_for_guard2. They are both needed in order
|
to create correct data-flow and loop-closed-ssa-form.
|
to create correct data-flow and loop-closed-ssa-form.
|
|
|
Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
|
Generally slpeel_update_phi_nodes_for_guard1 creates phis for variables
|
that change between iterations of a loop (and therefore have a phi-node
|
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
|
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
|
phis for variables that are used out of the loop (and therefore have
|
loop-closed exit phis). Some variables may be both updated between
|
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
|
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)
|
may need both entry_phis (created by slpeel_update_phi_nodes_for_guard1)
|
and exit phis (created by slpeel_update_phi_nodes_for_guard2).
|
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
|
- IS_NEW_LOOP: if IS_NEW_LOOP is true, then LOOP is a newly created copy of
|
an original loop. i.e., we have:
|
an original loop. i.e., we have:
|
|
|
orig_loop
|
orig_loop
|
guard_bb (goto LOOP/new_merge)
|
guard_bb (goto LOOP/new_merge)
|
new_loop <-- LOOP
|
new_loop <-- LOOP
|
new_exit
|
new_exit
|
new_merge
|
new_merge
|
next_bb
|
next_bb
|
|
|
If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
|
If IS_NEW_LOOP is false, then LOOP is an original loop, in which case we
|
have:
|
have:
|
|
|
new_loop
|
new_loop
|
guard_bb (goto LOOP/new_merge)
|
guard_bb (goto LOOP/new_merge)
|
orig_loop <-- LOOP
|
orig_loop <-- LOOP
|
new_exit
|
new_exit
|
new_merge
|
new_merge
|
next_bb
|
next_bb
|
|
|
The SSA names defined in the original loop have a current
|
The SSA names defined in the original loop have a current
|
reaching definition that that records the corresponding new
|
reaching definition that that records the corresponding new
|
ssa-name used in the new duplicated loop copy.
|
ssa-name used in the new duplicated loop copy.
|
*/
|
*/
|
|
|
/* Function slpeel_update_phi_nodes_for_guard1
|
/* Function slpeel_update_phi_nodes_for_guard1
|
|
|
Input:
|
Input:
|
- GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
|
- 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
|
- DEFS - a bitmap of ssa names to mark new names for which we recorded
|
information.
|
information.
|
|
|
In the context of the overall structure, we have:
|
In the context of the overall structure, we have:
|
|
|
loop1_preheader_bb:
|
loop1_preheader_bb:
|
guard1 (goto loop1/merg1_bb)
|
guard1 (goto loop1/merg1_bb)
|
LOOP-> loop1
|
LOOP-> loop1
|
loop1_exit_bb:
|
loop1_exit_bb:
|
guard2 (goto merge1_bb/merge2_bb)
|
guard2 (goto merge1_bb/merge2_bb)
|
merge1_bb
|
merge1_bb
|
loop2
|
loop2
|
loop2_exit_bb
|
loop2_exit_bb
|
merge2_bb
|
merge2_bb
|
next_bb
|
next_bb
|
|
|
For each name updated between loop iterations (i.e - for each name that has
|
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:
|
an entry (loop-header) phi in LOOP) we create a new phi in:
|
1. merge1_bb (to account for the edge from guard1)
|
1. merge1_bb (to account for the edge from guard1)
|
2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
|
2. loop1_exit_bb (an exit-phi to keep LOOP in loop-closed form)
|
*/
|
*/
|
|
|
static void
|
static void
|
slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
|
slpeel_update_phi_nodes_for_guard1 (edge guard_edge, struct loop *loop,
|
bool is_new_loop, basic_block *new_exit_bb,
|
bool is_new_loop, basic_block *new_exit_bb,
|
bitmap *defs)
|
bitmap *defs)
|
{
|
{
|
tree orig_phi, new_phi;
|
tree orig_phi, new_phi;
|
tree update_phi, update_phi2;
|
tree update_phi, update_phi2;
|
tree guard_arg, loop_arg;
|
tree guard_arg, loop_arg;
|
basic_block new_merge_bb = guard_edge->dest;
|
basic_block new_merge_bb = guard_edge->dest;
|
edge e = EDGE_SUCC (new_merge_bb, 0);
|
edge e = EDGE_SUCC (new_merge_bb, 0);
|
basic_block update_bb = e->dest;
|
basic_block update_bb = e->dest;
|
basic_block orig_bb = loop->header;
|
basic_block orig_bb = loop->header;
|
edge new_exit_e;
|
edge new_exit_e;
|
tree current_new_name;
|
tree current_new_name;
|
tree name;
|
tree name;
|
|
|
/* Create new bb between loop and new_merge_bb. */
|
/* Create new bb between loop and new_merge_bb. */
|
*new_exit_bb = split_edge (loop->single_exit);
|
*new_exit_bb = split_edge (loop->single_exit);
|
add_bb_to_loop (*new_exit_bb, loop->outer);
|
add_bb_to_loop (*new_exit_bb, loop->outer);
|
|
|
new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
|
new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
|
|
|
for (orig_phi = phi_nodes (orig_bb), update_phi = phi_nodes (update_bb);
|
for (orig_phi = phi_nodes (orig_bb), update_phi = phi_nodes (update_bb);
|
orig_phi && update_phi;
|
orig_phi && update_phi;
|
orig_phi = PHI_CHAIN (orig_phi), update_phi = PHI_CHAIN (update_phi))
|
orig_phi = PHI_CHAIN (orig_phi), update_phi = PHI_CHAIN (update_phi))
|
{
|
{
|
/* Virtual phi; Mark it for renaming. We actually want to call
|
/* Virtual phi; Mark it for renaming. We actually want to call
|
mar_sym_for_renaming, but since all ssa renaming datastructures
|
mar_sym_for_renaming, but since all ssa renaming datastructures
|
are going to be freed before we get to call ssa_upate, we just
|
are going to be freed before we get to call ssa_upate, we just
|
record this name for now in a bitmap, and will mark it for
|
record this name for now in a bitmap, and will mark it for
|
renaming later. */
|
renaming later. */
|
name = PHI_RESULT (orig_phi);
|
name = PHI_RESULT (orig_phi);
|
if (!is_gimple_reg (SSA_NAME_VAR (name)))
|
if (!is_gimple_reg (SSA_NAME_VAR (name)))
|
bitmap_set_bit (vect_vnames_to_rename, SSA_NAME_VERSION (name));
|
bitmap_set_bit (vect_vnames_to_rename, SSA_NAME_VERSION (name));
|
|
|
/** 1. Handle new-merge-point phis **/
|
/** 1. Handle new-merge-point phis **/
|
|
|
/* 1.1. Generate new phi node in NEW_MERGE_BB: */
|
/* 1.1. Generate new phi node in NEW_MERGE_BB: */
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
new_merge_bb);
|
new_merge_bb);
|
|
|
/* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
|
/* 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: */
|
of LOOP. Set the two phi args in NEW_PHI for these edges: */
|
loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
|
loop_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, EDGE_SUCC (loop->latch, 0));
|
guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
|
guard_arg = PHI_ARG_DEF_FROM_EDGE (orig_phi, loop_preheader_edge (loop));
|
|
|
add_phi_arg (new_phi, loop_arg, new_exit_e);
|
add_phi_arg (new_phi, loop_arg, new_exit_e);
|
add_phi_arg (new_phi, guard_arg, guard_edge);
|
add_phi_arg (new_phi, guard_arg, guard_edge);
|
|
|
/* 1.3. Update phi in successor block. */
|
/* 1.3. Update phi in successor block. */
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == loop_arg
|
|| PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
|
|| PHI_ARG_DEF_FROM_EDGE (update_phi, e) == guard_arg);
|
SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
|
SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
|
update_phi2 = new_phi;
|
update_phi2 = new_phi;
|
|
|
|
|
/** 2. Handle loop-closed-ssa-form phis **/
|
/** 2. Handle loop-closed-ssa-form phis **/
|
|
|
/* 2.1. Generate new phi node in NEW_EXIT_BB: */
|
/* 2.1. Generate new phi node in NEW_EXIT_BB: */
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
*new_exit_bb);
|
*new_exit_bb);
|
|
|
/* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
|
/* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
|
add_phi_arg (new_phi, loop_arg, loop->single_exit);
|
add_phi_arg (new_phi, loop_arg, loop->single_exit);
|
|
|
/* 2.3. Update phi in successor of NEW_EXIT_BB: */
|
/* 2.3. Update phi in successor of NEW_EXIT_BB: */
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
|
SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
|
SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
|
|
|
/* 2.4. Record the newly created name with set_current_def.
|
/* 2.4. Record the newly created name with set_current_def.
|
We want to find a name such that
|
We want to find a name such that
|
name = get_current_def (orig_loop_name)
|
name = get_current_def (orig_loop_name)
|
and to set its current definition as follows:
|
and to set its current definition as follows:
|
set_current_def (name, new_phi_name)
|
set_current_def (name, new_phi_name)
|
|
|
If LOOP is a new loop then loop_arg is already the name we're
|
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
|
looking for. If LOOP is the original loop, then loop_arg is
|
the orig_loop_name and the relevant name is recorded in its
|
the orig_loop_name and the relevant name is recorded in its
|
current reaching definition. */
|
current reaching definition. */
|
if (is_new_loop)
|
if (is_new_loop)
|
current_new_name = loop_arg;
|
current_new_name = loop_arg;
|
else
|
else
|
{
|
{
|
current_new_name = get_current_def (loop_arg);
|
current_new_name = get_current_def (loop_arg);
|
/* current_def is not available only if the variable does not
|
/* current_def is not available only if the variable does not
|
change inside the loop, in which case we also don't care
|
change inside the loop, in which case we also don't care
|
about recording a current_def for it because we won't be
|
about recording a current_def for it because we won't be
|
trying to create loop-exit-phis for it. */
|
trying to create loop-exit-phis for it. */
|
if (!current_new_name)
|
if (!current_new_name)
|
continue;
|
continue;
|
}
|
}
|
gcc_assert (get_current_def (current_new_name) == NULL_TREE);
|
gcc_assert (get_current_def (current_new_name) == NULL_TREE);
|
|
|
set_current_def (current_new_name, PHI_RESULT (new_phi));
|
set_current_def (current_new_name, PHI_RESULT (new_phi));
|
bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
|
bitmap_set_bit (*defs, SSA_NAME_VERSION (current_new_name));
|
}
|
}
|
|
|
set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
|
set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
|
}
|
}
|
|
|
|
|
/* Function slpeel_update_phi_nodes_for_guard2
|
/* Function slpeel_update_phi_nodes_for_guard2
|
|
|
Input:
|
Input:
|
- GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
|
- GUARD_EDGE, LOOP, IS_NEW_LOOP, NEW_EXIT_BB - as explained above.
|
|
|
In the context of the overall structure, we have:
|
In the context of the overall structure, we have:
|
|
|
loop1_preheader_bb:
|
loop1_preheader_bb:
|
guard1 (goto loop1/merg1_bb)
|
guard1 (goto loop1/merg1_bb)
|
loop1
|
loop1
|
loop1_exit_bb:
|
loop1_exit_bb:
|
guard2 (goto merge1_bb/merge2_bb)
|
guard2 (goto merge1_bb/merge2_bb)
|
merge1_bb
|
merge1_bb
|
LOOP-> loop2
|
LOOP-> loop2
|
loop2_exit_bb
|
loop2_exit_bb
|
merge2_bb
|
merge2_bb
|
next_bb
|
next_bb
|
|
|
For each name used out side the loop (i.e - for each name that has an exit
|
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:
|
phi in next_bb) we create a new phi in:
|
1. merge2_bb (to account for the edge from guard_bb)
|
1. merge2_bb (to account for the edge from guard_bb)
|
2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
|
2. loop2_exit_bb (an exit-phi to keep LOOP in loop-closed form)
|
3. guard2 bb (an exit phi to keep the preceding loop in loop-closed form),
|
3. 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).
|
if needed (if it wasn't handled by slpeel_update_phis_nodes_for_phi1).
|
*/
|
*/
|
|
|
static void
|
static void
|
slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
|
slpeel_update_phi_nodes_for_guard2 (edge guard_edge, struct loop *loop,
|
bool is_new_loop, basic_block *new_exit_bb)
|
bool is_new_loop, basic_block *new_exit_bb)
|
{
|
{
|
tree orig_phi, new_phi;
|
tree orig_phi, new_phi;
|
tree update_phi, update_phi2;
|
tree update_phi, update_phi2;
|
tree guard_arg, loop_arg;
|
tree guard_arg, loop_arg;
|
basic_block new_merge_bb = guard_edge->dest;
|
basic_block new_merge_bb = guard_edge->dest;
|
edge e = EDGE_SUCC (new_merge_bb, 0);
|
edge e = EDGE_SUCC (new_merge_bb, 0);
|
basic_block update_bb = e->dest;
|
basic_block update_bb = e->dest;
|
edge new_exit_e;
|
edge new_exit_e;
|
tree orig_def, orig_def_new_name;
|
tree orig_def, orig_def_new_name;
|
tree new_name, new_name2;
|
tree new_name, new_name2;
|
tree arg;
|
tree arg;
|
|
|
/* Create new bb between loop and new_merge_bb. */
|
/* Create new bb between loop and new_merge_bb. */
|
*new_exit_bb = split_edge (loop->single_exit);
|
*new_exit_bb = split_edge (loop->single_exit);
|
add_bb_to_loop (*new_exit_bb, loop->outer);
|
add_bb_to_loop (*new_exit_bb, loop->outer);
|
|
|
new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
|
new_exit_e = EDGE_SUCC (*new_exit_bb, 0);
|
|
|
for (update_phi = phi_nodes (update_bb); update_phi;
|
for (update_phi = phi_nodes (update_bb); update_phi;
|
update_phi = PHI_CHAIN (update_phi))
|
update_phi = PHI_CHAIN (update_phi))
|
{
|
{
|
orig_phi = update_phi;
|
orig_phi = update_phi;
|
orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
|
orig_def = PHI_ARG_DEF_FROM_EDGE (orig_phi, e);
|
/* This loop-closed-phi actually doesn't represent a use
|
/* This loop-closed-phi actually doesn't represent a use
|
out of the loop - the phi arg is a constant. */
|
out of the loop - the phi arg is a constant. */
|
if (TREE_CODE (orig_def) != SSA_NAME)
|
if (TREE_CODE (orig_def) != SSA_NAME)
|
continue;
|
continue;
|
orig_def_new_name = get_current_def (orig_def);
|
orig_def_new_name = get_current_def (orig_def);
|
arg = NULL_TREE;
|
arg = NULL_TREE;
|
|
|
/** 1. Handle new-merge-point phis **/
|
/** 1. Handle new-merge-point phis **/
|
|
|
/* 1.1. Generate new phi node in NEW_MERGE_BB: */
|
/* 1.1. Generate new phi node in NEW_MERGE_BB: */
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
new_merge_bb);
|
new_merge_bb);
|
|
|
/* 1.2. NEW_MERGE_BB has two incoming edges: GUARD_EDGE and the exit-edge
|
/* 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: */
|
of LOOP. Set the two PHI args in NEW_PHI for these edges: */
|
new_name = orig_def;
|
new_name = orig_def;
|
new_name2 = NULL_TREE;
|
new_name2 = NULL_TREE;
|
if (orig_def_new_name)
|
if (orig_def_new_name)
|
{
|
{
|
new_name = orig_def_new_name;
|
new_name = orig_def_new_name;
|
/* Some variables have both loop-entry-phis and loop-exit-phis.
|
/* Some variables have both loop-entry-phis and loop-exit-phis.
|
Such variables were given yet newer names by phis placed in
|
Such variables were given yet newer names by phis placed in
|
guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
|
guard_bb by slpeel_update_phi_nodes_for_guard1. I.e:
|
new_name2 = get_current_def (get_current_def (orig_name)). */
|
new_name2 = get_current_def (get_current_def (orig_name)). */
|
new_name2 = get_current_def (new_name);
|
new_name2 = get_current_def (new_name);
|
}
|
}
|
|
|
if (is_new_loop)
|
if (is_new_loop)
|
{
|
{
|
guard_arg = orig_def;
|
guard_arg = orig_def;
|
loop_arg = new_name;
|
loop_arg = new_name;
|
}
|
}
|
else
|
else
|
{
|
{
|
guard_arg = new_name;
|
guard_arg = new_name;
|
loop_arg = orig_def;
|
loop_arg = orig_def;
|
}
|
}
|
if (new_name2)
|
if (new_name2)
|
guard_arg = new_name2;
|
guard_arg = new_name2;
|
|
|
add_phi_arg (new_phi, loop_arg, new_exit_e);
|
add_phi_arg (new_phi, loop_arg, new_exit_e);
|
add_phi_arg (new_phi, guard_arg, guard_edge);
|
add_phi_arg (new_phi, guard_arg, guard_edge);
|
|
|
/* 1.3. Update phi in successor block. */
|
/* 1.3. Update phi in successor block. */
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi, e) == orig_def);
|
SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
|
SET_PHI_ARG_DEF (update_phi, e->dest_idx, PHI_RESULT (new_phi));
|
update_phi2 = new_phi;
|
update_phi2 = new_phi;
|
|
|
|
|
/** 2. Handle loop-closed-ssa-form phis **/
|
/** 2. Handle loop-closed-ssa-form phis **/
|
|
|
/* 2.1. Generate new phi node in NEW_EXIT_BB: */
|
/* 2.1. Generate new phi node in NEW_EXIT_BB: */
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
*new_exit_bb);
|
*new_exit_bb);
|
|
|
/* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
|
/* 2.2. NEW_EXIT_BB has one incoming edge: the exit-edge of the loop. */
|
add_phi_arg (new_phi, loop_arg, loop->single_exit);
|
add_phi_arg (new_phi, loop_arg, loop->single_exit);
|
|
|
/* 2.3. Update phi in successor of NEW_EXIT_BB: */
|
/* 2.3. Update phi in successor of NEW_EXIT_BB: */
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, new_exit_e) == loop_arg);
|
SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
|
SET_PHI_ARG_DEF (update_phi2, new_exit_e->dest_idx, PHI_RESULT (new_phi));
|
|
|
|
|
/** 3. Handle loop-closed-ssa-form phis for first loop **/
|
/** 3. Handle loop-closed-ssa-form phis for first loop **/
|
|
|
/* 3.1. Find the relevant names that need an exit-phi in
|
/* 3.1. Find the relevant names that need an exit-phi in
|
GUARD_BB, i.e. names for which
|
GUARD_BB, i.e. names for which
|
slpeel_update_phi_nodes_for_guard1 had not already created a
|
slpeel_update_phi_nodes_for_guard1 had not already created a
|
phi node. This is the case for names that are used outside
|
phi node. This is the case for names that are used outside
|
the loop (and therefore need an exit phi) but are not updated
|
the loop (and therefore need an exit phi) but are not updated
|
across loop iterations (and therefore don't have a
|
across loop iterations (and therefore don't have a
|
loop-header-phi).
|
loop-header-phi).
|
|
|
slpeel_update_phi_nodes_for_guard1 is responsible for
|
slpeel_update_phi_nodes_for_guard1 is responsible for
|
creating loop-exit phis in GUARD_BB for names that have a
|
creating loop-exit phis in GUARD_BB for names that have a
|
loop-header-phi. When such a phi is created we also record
|
loop-header-phi. When such a phi is created we also record
|
the new name in its current definition. If this new name
|
the new name in its current definition. If this new name
|
exists, then guard_arg was set to this new name (see 1.2
|
exists, then guard_arg was set to this new name (see 1.2
|
above). Therefore, if guard_arg is not this new name, this
|
above). Therefore, if guard_arg is not this new name, this
|
is an indication that an exit-phi in GUARD_BB was not yet
|
is an indication that an exit-phi in GUARD_BB was not yet
|
created, so we take care of it here. */
|
created, so we take care of it here. */
|
if (guard_arg == new_name2)
|
if (guard_arg == new_name2)
|
continue;
|
continue;
|
arg = guard_arg;
|
arg = guard_arg;
|
|
|
/* 3.2. Generate new phi node in GUARD_BB: */
|
/* 3.2. Generate new phi node in GUARD_BB: */
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
new_phi = create_phi_node (SSA_NAME_VAR (PHI_RESULT (orig_phi)),
|
guard_edge->src);
|
guard_edge->src);
|
|
|
/* 3.3. GUARD_BB has one incoming edge: */
|
/* 3.3. GUARD_BB has one incoming edge: */
|
gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
|
gcc_assert (EDGE_COUNT (guard_edge->src->preds) == 1);
|
add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0));
|
add_phi_arg (new_phi, arg, EDGE_PRED (guard_edge->src, 0));
|
|
|
/* 3.4. Update phi in successor of GUARD_BB: */
|
/* 3.4. Update phi in successor of GUARD_BB: */
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
|
gcc_assert (PHI_ARG_DEF_FROM_EDGE (update_phi2, guard_edge)
|
== guard_arg);
|
== guard_arg);
|
SET_PHI_ARG_DEF (update_phi2, guard_edge->dest_idx, PHI_RESULT (new_phi));
|
SET_PHI_ARG_DEF (update_phi2, guard_edge->dest_idx, PHI_RESULT (new_phi));
|
}
|
}
|
|
|
set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
|
set_phi_nodes (new_merge_bb, phi_reverse (phi_nodes (new_merge_bb)));
|
}
|
}
|
|
|
|
|
/* Make the LOOP iterate NITERS times. This is done by adding a new IV
|
/* 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.
|
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. */
|
Assumption: the exit-condition of LOOP is the last stmt in the loop. */
|
|
|
void
|
void
|
slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
|
slpeel_make_loop_iterate_ntimes (struct loop *loop, tree niters)
|
{
|
{
|
tree indx_before_incr, indx_after_incr, cond_stmt, cond;
|
tree indx_before_incr, indx_after_incr, cond_stmt, cond;
|
tree orig_cond;
|
tree orig_cond;
|
edge exit_edge = loop->single_exit;
|
edge exit_edge = loop->single_exit;
|
block_stmt_iterator loop_cond_bsi;
|
block_stmt_iterator loop_cond_bsi;
|
block_stmt_iterator incr_bsi;
|
block_stmt_iterator incr_bsi;
|
bool insert_after;
|
bool insert_after;
|
tree begin_label = tree_block_label (loop->latch);
|
tree begin_label = tree_block_label (loop->latch);
|
tree exit_label = tree_block_label (loop->single_exit->dest);
|
tree exit_label = tree_block_label (loop->single_exit->dest);
|
tree init = build_int_cst (TREE_TYPE (niters), 0);
|
tree init = build_int_cst (TREE_TYPE (niters), 0);
|
tree step = build_int_cst (TREE_TYPE (niters), 1);
|
tree step = build_int_cst (TREE_TYPE (niters), 1);
|
tree then_label;
|
tree then_label;
|
tree else_label;
|
tree else_label;
|
LOC loop_loc;
|
LOC loop_loc;
|
|
|
orig_cond = get_loop_exit_condition (loop);
|
orig_cond = get_loop_exit_condition (loop);
|
gcc_assert (orig_cond);
|
gcc_assert (orig_cond);
|
loop_cond_bsi = bsi_for_stmt (orig_cond);
|
loop_cond_bsi = bsi_for_stmt (orig_cond);
|
|
|
standard_iv_increment_position (loop, &incr_bsi, &insert_after);
|
standard_iv_increment_position (loop, &incr_bsi, &insert_after);
|
create_iv (init, step, NULL_TREE, loop,
|
create_iv (init, step, NULL_TREE, loop,
|
&incr_bsi, insert_after, &indx_before_incr, &indx_after_incr);
|
&incr_bsi, insert_after, &indx_before_incr, &indx_after_incr);
|
|
|
if (exit_edge->flags & EDGE_TRUE_VALUE) /* 'then' edge exits the loop. */
|
if (exit_edge->flags & EDGE_TRUE_VALUE) /* 'then' edge exits the loop. */
|
{
|
{
|
cond = build2 (GE_EXPR, boolean_type_node, indx_after_incr, niters);
|
cond = build2 (GE_EXPR, boolean_type_node, indx_after_incr, niters);
|
then_label = build1 (GOTO_EXPR, void_type_node, exit_label);
|
then_label = build1 (GOTO_EXPR, void_type_node, exit_label);
|
else_label = build1 (GOTO_EXPR, void_type_node, begin_label);
|
else_label = build1 (GOTO_EXPR, void_type_node, begin_label);
|
}
|
}
|
else /* 'then' edge loops back. */
|
else /* 'then' edge loops back. */
|
{
|
{
|
cond = build2 (LT_EXPR, boolean_type_node, indx_after_incr, niters);
|
cond = build2 (LT_EXPR, boolean_type_node, indx_after_incr, niters);
|
then_label = build1 (GOTO_EXPR, void_type_node, begin_label);
|
then_label = build1 (GOTO_EXPR, void_type_node, begin_label);
|
else_label = build1 (GOTO_EXPR, void_type_node, exit_label);
|
else_label = build1 (GOTO_EXPR, void_type_node, exit_label);
|
}
|
}
|
|
|
cond_stmt = build3 (COND_EXPR, TREE_TYPE (orig_cond), cond,
|
cond_stmt = build3 (COND_EXPR, TREE_TYPE (orig_cond), cond,
|
then_label, else_label);
|
then_label, else_label);
|
bsi_insert_before (&loop_cond_bsi, cond_stmt, BSI_SAME_STMT);
|
bsi_insert_before (&loop_cond_bsi, cond_stmt, BSI_SAME_STMT);
|
|
|
/* Remove old loop exit test: */
|
/* Remove old loop exit test: */
|
bsi_remove (&loop_cond_bsi, true);
|
bsi_remove (&loop_cond_bsi, true);
|
|
|
loop_loc = find_loop_location (loop);
|
loop_loc = find_loop_location (loop);
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
if (loop_loc != UNKNOWN_LOC)
|
if (loop_loc != UNKNOWN_LOC)
|
fprintf (dump_file, "\nloop at %s:%d: ",
|
fprintf (dump_file, "\nloop at %s:%d: ",
|
LOC_FILE (loop_loc), LOC_LINE (loop_loc));
|
LOC_FILE (loop_loc), LOC_LINE (loop_loc));
|
print_generic_expr (dump_file, cond_stmt, TDF_SLIM);
|
print_generic_expr (dump_file, cond_stmt, TDF_SLIM);
|
}
|
}
|
|
|
loop->nb_iterations = niters;
|
loop->nb_iterations = niters;
|
}
|
}
|
|
|
|
|
/* Given LOOP this function generates a new copy of it and puts it
|
/* Given LOOP this function generates a new copy of it and puts it
|
on E which is either the entry or exit of LOOP. */
|
on E which is either the entry or exit of LOOP. */
|
|
|
static struct loop *
|
static struct loop *
|
slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, struct loops *loops,
|
slpeel_tree_duplicate_loop_to_edge_cfg (struct loop *loop, struct loops *loops,
|
edge e)
|
edge e)
|
{
|
{
|
struct loop *new_loop;
|
struct loop *new_loop;
|
basic_block *new_bbs, *bbs;
|
basic_block *new_bbs, *bbs;
|
bool at_exit;
|
bool at_exit;
|
bool was_imm_dom;
|
bool was_imm_dom;
|
basic_block exit_dest;
|
basic_block exit_dest;
|
tree phi, phi_arg;
|
tree phi, phi_arg;
|
|
|
at_exit = (e == loop->single_exit);
|
at_exit = (e == loop->single_exit);
|
if (!at_exit && e != loop_preheader_edge (loop))
|
if (!at_exit && e != loop_preheader_edge (loop))
|
return NULL;
|
return NULL;
|
|
|
bbs = get_loop_body (loop);
|
bbs = get_loop_body (loop);
|
|
|
/* Check whether duplication is possible. */
|
/* Check whether duplication is possible. */
|
if (!can_copy_bbs_p (bbs, loop->num_nodes))
|
if (!can_copy_bbs_p (bbs, loop->num_nodes))
|
{
|
{
|
free (bbs);
|
free (bbs);
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
/* Generate new loop structure. */
|
/* Generate new loop structure. */
|
new_loop = duplicate_loop (loops, loop, loop->outer);
|
new_loop = duplicate_loop (loops, loop, loop->outer);
|
if (!new_loop)
|
if (!new_loop)
|
{
|
{
|
free (bbs);
|
free (bbs);
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
exit_dest = loop->single_exit->dest;
|
exit_dest = loop->single_exit->dest;
|
was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
|
was_imm_dom = (get_immediate_dominator (CDI_DOMINATORS,
|
exit_dest) == loop->header ?
|
exit_dest) == loop->header ?
|
true : false);
|
true : false);
|
|
|
new_bbs = XNEWVEC (basic_block, loop->num_nodes);
|
new_bbs = XNEWVEC (basic_block, loop->num_nodes);
|
|
|
copy_bbs (bbs, loop->num_nodes, new_bbs,
|
copy_bbs (bbs, loop->num_nodes, new_bbs,
|
&loop->single_exit, 1, &new_loop->single_exit, NULL,
|
&loop->single_exit, 1, &new_loop->single_exit, NULL,
|
e->src);
|
e->src);
|
|
|
/* Duplicating phi args at exit bbs as coming
|
/* Duplicating phi args at exit bbs as coming
|
also from exit of duplicated loop. */
|
also from exit of duplicated loop. */
|
for (phi = phi_nodes (exit_dest); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (exit_dest); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, loop->single_exit);
|
phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, loop->single_exit);
|
if (phi_arg)
|
if (phi_arg)
|
{
|
{
|
edge new_loop_exit_edge;
|
edge new_loop_exit_edge;
|
|
|
if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
|
if (EDGE_SUCC (new_loop->header, 0)->dest == new_loop->latch)
|
new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
|
new_loop_exit_edge = EDGE_SUCC (new_loop->header, 1);
|
else
|
else
|
new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
|
new_loop_exit_edge = EDGE_SUCC (new_loop->header, 0);
|
|
|
add_phi_arg (phi, phi_arg, new_loop_exit_edge);
|
add_phi_arg (phi, phi_arg, new_loop_exit_edge);
|
}
|
}
|
}
|
}
|
|
|
if (at_exit) /* Add the loop copy at exit. */
|
if (at_exit) /* Add the loop copy at exit. */
|
{
|
{
|
redirect_edge_and_branch_force (e, new_loop->header);
|
redirect_edge_and_branch_force (e, new_loop->header);
|
set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
|
set_immediate_dominator (CDI_DOMINATORS, new_loop->header, e->src);
|
if (was_imm_dom)
|
if (was_imm_dom)
|
set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
|
set_immediate_dominator (CDI_DOMINATORS, exit_dest, new_loop->header);
|
}
|
}
|
else /* Add the copy at entry. */
|
else /* Add the copy at entry. */
|
{
|
{
|
edge new_exit_e;
|
edge new_exit_e;
|
edge entry_e = loop_preheader_edge (loop);
|
edge entry_e = loop_preheader_edge (loop);
|
basic_block preheader = entry_e->src;
|
basic_block preheader = entry_e->src;
|
|
|
if (!flow_bb_inside_loop_p (new_loop,
|
if (!flow_bb_inside_loop_p (new_loop,
|
EDGE_SUCC (new_loop->header, 0)->dest))
|
EDGE_SUCC (new_loop->header, 0)->dest))
|
new_exit_e = EDGE_SUCC (new_loop->header, 0);
|
new_exit_e = EDGE_SUCC (new_loop->header, 0);
|
else
|
else
|
new_exit_e = EDGE_SUCC (new_loop->header, 1);
|
new_exit_e = EDGE_SUCC (new_loop->header, 1);
|
|
|
redirect_edge_and_branch_force (new_exit_e, loop->header);
|
redirect_edge_and_branch_force (new_exit_e, loop->header);
|
set_immediate_dominator (CDI_DOMINATORS, loop->header,
|
set_immediate_dominator (CDI_DOMINATORS, loop->header,
|
new_exit_e->src);
|
new_exit_e->src);
|
|
|
/* We have to add phi args to the loop->header here as coming
|
/* We have to add phi args to the loop->header here as coming
|
from new_exit_e edge. */
|
from new_exit_e edge. */
|
for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
|
phi_arg = PHI_ARG_DEF_FROM_EDGE (phi, entry_e);
|
if (phi_arg)
|
if (phi_arg)
|
add_phi_arg (phi, phi_arg, new_exit_e);
|
add_phi_arg (phi, phi_arg, new_exit_e);
|
}
|
}
|
|
|
redirect_edge_and_branch_force (entry_e, new_loop->header);
|
redirect_edge_and_branch_force (entry_e, new_loop->header);
|
set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
|
set_immediate_dominator (CDI_DOMINATORS, new_loop->header, preheader);
|
}
|
}
|
|
|
free (new_bbs);
|
free (new_bbs);
|
free (bbs);
|
free (bbs);
|
|
|
return new_loop;
|
return new_loop;
|
}
|
}
|
|
|
|
|
/* Given the condition statement COND, put it as the last statement
|
/* Given the condition statement COND, put it as the last statement
|
of GUARD_BB; EXIT_BB is the basic block to skip the loop;
|
of GUARD_BB; EXIT_BB is the basic block to skip the loop;
|
Assumes that this is the single exit of the guarded loop.
|
Assumes that this is the single exit of the guarded loop.
|
Returns the skip edge. */
|
Returns the skip edge. */
|
|
|
static edge
|
static edge
|
slpeel_add_loop_guard (basic_block guard_bb, tree cond, basic_block exit_bb,
|
slpeel_add_loop_guard (basic_block guard_bb, tree cond, basic_block exit_bb,
|
basic_block dom_bb)
|
basic_block dom_bb)
|
{
|
{
|
block_stmt_iterator bsi;
|
block_stmt_iterator bsi;
|
edge new_e, enter_e;
|
edge new_e, enter_e;
|
tree cond_stmt, then_label, else_label;
|
tree cond_stmt, then_label, else_label;
|
|
|
enter_e = EDGE_SUCC (guard_bb, 0);
|
enter_e = EDGE_SUCC (guard_bb, 0);
|
enter_e->flags &= ~EDGE_FALLTHRU;
|
enter_e->flags &= ~EDGE_FALLTHRU;
|
enter_e->flags |= EDGE_FALSE_VALUE;
|
enter_e->flags |= EDGE_FALSE_VALUE;
|
bsi = bsi_last (guard_bb);
|
bsi = bsi_last (guard_bb);
|
|
|
then_label = build1 (GOTO_EXPR, void_type_node,
|
then_label = build1 (GOTO_EXPR, void_type_node,
|
tree_block_label (exit_bb));
|
tree_block_label (exit_bb));
|
else_label = build1 (GOTO_EXPR, void_type_node,
|
else_label = build1 (GOTO_EXPR, void_type_node,
|
tree_block_label (enter_e->dest));
|
tree_block_label (enter_e->dest));
|
cond_stmt = build3 (COND_EXPR, void_type_node, cond,
|
cond_stmt = build3 (COND_EXPR, void_type_node, cond,
|
then_label, else_label);
|
then_label, else_label);
|
bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
|
bsi_insert_after (&bsi, cond_stmt, BSI_NEW_STMT);
|
/* Add new edge to connect guard block to the merge/loop-exit block. */
|
/* Add new edge to connect guard block to the merge/loop-exit block. */
|
new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
|
new_e = make_edge (guard_bb, exit_bb, EDGE_TRUE_VALUE);
|
set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
|
set_immediate_dominator (CDI_DOMINATORS, exit_bb, dom_bb);
|
return new_e;
|
return new_e;
|
}
|
}
|
|
|
|
|
/* This function verifies that the following restrictions apply to LOOP:
|
/* This function verifies that the following restrictions apply to LOOP:
|
(1) it is innermost
|
(1) it is innermost
|
(2) it consists of exactly 2 basic blocks - header, and an empty latch.
|
(2) it consists of exactly 2 basic blocks - header, and an empty latch.
|
(3) it is single entry, single exit
|
(3) it is single entry, single exit
|
(4) its exit condition is the last stmt in the header
|
(4) its exit condition is the last stmt in the header
|
(5) E is the entry/exit edge of LOOP.
|
(5) E is the entry/exit edge of LOOP.
|
*/
|
*/
|
|
|
bool
|
bool
|
slpeel_can_duplicate_loop_p (struct loop *loop, edge e)
|
slpeel_can_duplicate_loop_p (struct loop *loop, edge e)
|
{
|
{
|
edge exit_e = loop->single_exit;
|
edge exit_e = loop->single_exit;
|
edge entry_e = loop_preheader_edge (loop);
|
edge entry_e = loop_preheader_edge (loop);
|
tree orig_cond = get_loop_exit_condition (loop);
|
tree orig_cond = get_loop_exit_condition (loop);
|
block_stmt_iterator loop_exit_bsi = bsi_last (exit_e->src);
|
block_stmt_iterator loop_exit_bsi = bsi_last (exit_e->src);
|
|
|
if (need_ssa_update_p ())
|
if (need_ssa_update_p ())
|
return false;
|
return false;
|
|
|
if (loop->inner
|
if (loop->inner
|
/* All loops have an outer scope; the only case loop->outer is NULL is for
|
/* All loops have an outer scope; the only case loop->outer is NULL is for
|
the function itself. */
|
the function itself. */
|
|| !loop->outer
|
|| !loop->outer
|
|| loop->num_nodes != 2
|
|| loop->num_nodes != 2
|
|| !empty_block_p (loop->latch)
|
|| !empty_block_p (loop->latch)
|
|| !loop->single_exit
|
|| !loop->single_exit
|
/* Verify that new loop exit condition can be trivially modified. */
|
/* Verify that new loop exit condition can be trivially modified. */
|
|| (!orig_cond || orig_cond != bsi_stmt (loop_exit_bsi))
|
|| (!orig_cond || orig_cond != bsi_stmt (loop_exit_bsi))
|
|| (e != exit_e && e != entry_e))
|
|| (e != exit_e && e != entry_e))
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
#ifdef ENABLE_CHECKING
|
#ifdef ENABLE_CHECKING
|
void
|
void
|
slpeel_verify_cfg_after_peeling (struct loop *first_loop,
|
slpeel_verify_cfg_after_peeling (struct loop *first_loop,
|
struct loop *second_loop)
|
struct loop *second_loop)
|
{
|
{
|
basic_block loop1_exit_bb = first_loop->single_exit->dest;
|
basic_block loop1_exit_bb = first_loop->single_exit->dest;
|
basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
|
basic_block loop2_entry_bb = loop_preheader_edge (second_loop)->src;
|
basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
|
basic_block loop1_entry_bb = loop_preheader_edge (first_loop)->src;
|
|
|
/* A guard that controls whether the second_loop is to be executed or skipped
|
/* A guard that controls whether the second_loop is to be executed or skipped
|
is placed in first_loop->exit. first_loopt->exit therefore has two
|
is placed in first_loop->exit. first_loopt->exit therefore has two
|
successors - one is the preheader of second_loop, and the other is a bb
|
successors - one is the preheader of second_loop, and the other is a bb
|
after second_loop.
|
after second_loop.
|
*/
|
*/
|
gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
|
gcc_assert (EDGE_COUNT (loop1_exit_bb->succs) == 2);
|
|
|
/* 1. Verify that one of the successors of first_loopt->exit is the preheader
|
/* 1. Verify that one of the successors of first_loopt->exit is the preheader
|
of second_loop. */
|
of second_loop. */
|
|
|
/* The preheader of new_loop is expected to have two predecessors:
|
/* The preheader of new_loop is expected to have two predecessors:
|
first_loop->exit and the block that precedes first_loop. */
|
first_loop->exit and the block that precedes first_loop. */
|
|
|
gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
|
gcc_assert (EDGE_COUNT (loop2_entry_bb->preds) == 2
|
&& ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
|
&& ((EDGE_PRED (loop2_entry_bb, 0)->src == loop1_exit_bb
|
&& EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
|
&& EDGE_PRED (loop2_entry_bb, 1)->src == loop1_entry_bb)
|
|| (EDGE_PRED (loop2_entry_bb, 1)->src == loop1_exit_bb
|
|| (EDGE_PRED (loop2_entry_bb, 1)->src == loop1_exit_bb
|
&& EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
|
&& EDGE_PRED (loop2_entry_bb, 0)->src == loop1_entry_bb)));
|
|
|
/* Verify that the other successor of first_loopt->exit is after the
|
/* Verify that the other successor of first_loopt->exit is after the
|
second_loop. */
|
second_loop. */
|
/* TODO */
|
/* TODO */
|
}
|
}
|
#endif
|
#endif
|
|
|
/* Function slpeel_tree_peel_loop_to_edge.
|
/* Function slpeel_tree_peel_loop_to_edge.
|
|
|
Peel the first (last) iterations of LOOP into a new prolog (epilog) loop
|
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
|
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
|
we have two loops one after the other - first-loop iterates FIRST_NITERS
|
times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
|
times, and second-loop iterates the remainder NITERS - FIRST_NITERS times.
|
|
|
Input:
|
Input:
|
- LOOP: the loop to be peeled.
|
- LOOP: the loop to be peeled.
|
- E: the exit or entry edge of LOOP.
|
- E: the exit or entry edge of LOOP.
|
If it is the entry edge, we peel the first iterations of LOOP. In this
|
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.
|
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
|
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.
|
case, first-loop is the newly created loop, and second-loop is LOOP.
|
- NITERS: the number of iterations that LOOP iterates.
|
- NITERS: the number of iterations that LOOP iterates.
|
- FIRST_NITERS: the number of iterations that the first-loop should iterate.
|
- FIRST_NITERS: the number of iterations that the first-loop should iterate.
|
- UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible
|
- UPDATE_FIRST_LOOP_COUNT: specified whether this function is responsible
|
for updating the loop bound of the first-loop to FIRST_NITERS. If it
|
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
|
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).
|
(this can be useful if we don't want new stmts added to first-loop).
|
|
|
Output:
|
Output:
|
The function returns a pointer to the new loop-copy, or NULL if it failed
|
The function returns a pointer to the new loop-copy, or NULL if it failed
|
to perform the transformation.
|
to perform the transformation.
|
|
|
The function generates two if-then-else guards: one before the first loop,
|
The function generates two if-then-else guards: one before the first loop,
|
and the other before the second loop:
|
and the other before the second loop:
|
The first guard is:
|
The first guard is:
|
if (FIRST_NITERS == 0) then skip the first loop,
|
if (FIRST_NITERS == 0) then skip the first loop,
|
and go directly to the second loop.
|
and go directly to the second loop.
|
The second guard is:
|
The second guard is:
|
if (FIRST_NITERS == NITERS) then skip the second loop.
|
if (FIRST_NITERS == NITERS) then skip the second loop.
|
|
|
FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
|
FORNOW only simple loops are supported (see slpeel_can_duplicate_loop_p).
|
FORNOW the resulting code will not be in loop-closed-ssa form.
|
FORNOW the resulting code will not be in loop-closed-ssa form.
|
*/
|
*/
|
|
|
struct loop*
|
struct loop*
|
slpeel_tree_peel_loop_to_edge (struct loop *loop, struct loops *loops,
|
slpeel_tree_peel_loop_to_edge (struct loop *loop, struct loops *loops,
|
edge e, tree first_niters,
|
edge e, tree first_niters,
|
tree niters, bool update_first_loop_count)
|
tree niters, bool update_first_loop_count)
|
{
|
{
|
struct loop *new_loop = NULL, *first_loop, *second_loop;
|
struct loop *new_loop = NULL, *first_loop, *second_loop;
|
edge skip_e;
|
edge skip_e;
|
tree pre_condition;
|
tree pre_condition;
|
bitmap definitions;
|
bitmap definitions;
|
basic_block bb_before_second_loop, bb_after_second_loop;
|
basic_block bb_before_second_loop, bb_after_second_loop;
|
basic_block bb_before_first_loop;
|
basic_block bb_before_first_loop;
|
basic_block bb_between_loops;
|
basic_block bb_between_loops;
|
basic_block new_exit_bb;
|
basic_block new_exit_bb;
|
edge exit_e = loop->single_exit;
|
edge exit_e = loop->single_exit;
|
LOC loop_loc;
|
LOC loop_loc;
|
|
|
if (!slpeel_can_duplicate_loop_p (loop, e))
|
if (!slpeel_can_duplicate_loop_p (loop, e))
|
return NULL;
|
return NULL;
|
|
|
/* We have to initialize cfg_hooks. Then, when calling
|
/* We have to initialize cfg_hooks. Then, when calling
|
cfg_hooks->split_edge, the function tree_split_edge
|
cfg_hooks->split_edge, the function tree_split_edge
|
is actually called and, when calling cfg_hooks->duplicate_block,
|
is actually called and, when calling cfg_hooks->duplicate_block,
|
the function tree_duplicate_bb is called. */
|
the function tree_duplicate_bb is called. */
|
tree_register_cfg_hooks ();
|
tree_register_cfg_hooks ();
|
|
|
|
|
/* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
|
/* 1. Generate a copy of LOOP and put it on E (E is the entry/exit of LOOP).
|
Resulting CFG would be:
|
Resulting CFG would be:
|
|
|
first_loop:
|
first_loop:
|
do {
|
do {
|
} while ...
|
} while ...
|
|
|
second_loop:
|
second_loop:
|
do {
|
do {
|
} while ...
|
} while ...
|
|
|
orig_exit_bb:
|
orig_exit_bb:
|
*/
|
*/
|
|
|
if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, loops, e)))
|
if (!(new_loop = slpeel_tree_duplicate_loop_to_edge_cfg (loop, loops, e)))
|
{
|
{
|
loop_loc = find_loop_location (loop);
|
loop_loc = find_loop_location (loop);
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
{
|
{
|
if (loop_loc != UNKNOWN_LOC)
|
if (loop_loc != UNKNOWN_LOC)
|
fprintf (dump_file, "\n%s:%d: note: ",
|
fprintf (dump_file, "\n%s:%d: note: ",
|
LOC_FILE (loop_loc), LOC_LINE (loop_loc));
|
LOC_FILE (loop_loc), LOC_LINE (loop_loc));
|
fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
|
fprintf (dump_file, "tree_duplicate_loop_to_edge_cfg failed.\n");
|
}
|
}
|
return NULL;
|
return NULL;
|
}
|
}
|
|
|
if (e == exit_e)
|
if (e == exit_e)
|
{
|
{
|
/* NEW_LOOP was placed after LOOP. */
|
/* NEW_LOOP was placed after LOOP. */
|
first_loop = loop;
|
first_loop = loop;
|
second_loop = new_loop;
|
second_loop = new_loop;
|
}
|
}
|
else
|
else
|
{
|
{
|
/* NEW_LOOP was placed before LOOP. */
|
/* NEW_LOOP was placed before LOOP. */
|
first_loop = new_loop;
|
first_loop = new_loop;
|
second_loop = loop;
|
second_loop = loop;
|
}
|
}
|
|
|
definitions = ssa_names_to_replace ();
|
definitions = ssa_names_to_replace ();
|
slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
|
slpeel_update_phis_for_duplicate_loop (loop, new_loop, e == exit_e);
|
rename_variables_in_loop (new_loop);
|
rename_variables_in_loop (new_loop);
|
|
|
|
|
/* 2. Add the guard that controls whether the first loop is executed.
|
/* 2. Add the guard that controls whether the first loop is executed.
|
Resulting CFG would be:
|
Resulting CFG would be:
|
|
|
bb_before_first_loop:
|
bb_before_first_loop:
|
if (FIRST_NITERS == 0) GOTO bb_before_second_loop
|
if (FIRST_NITERS == 0) GOTO bb_before_second_loop
|
GOTO first-loop
|
GOTO first-loop
|
|
|
first_loop:
|
first_loop:
|
do {
|
do {
|
} while ...
|
} while ...
|
|
|
bb_before_second_loop:
|
bb_before_second_loop:
|
|
|
second_loop:
|
second_loop:
|
do {
|
do {
|
} while ...
|
} while ...
|
|
|
orig_exit_bb:
|
orig_exit_bb:
|
*/
|
*/
|
|
|
bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
|
bb_before_first_loop = split_edge (loop_preheader_edge (first_loop));
|
add_bb_to_loop (bb_before_first_loop, first_loop->outer);
|
add_bb_to_loop (bb_before_first_loop, first_loop->outer);
|
bb_before_second_loop = split_edge (first_loop->single_exit);
|
bb_before_second_loop = split_edge (first_loop->single_exit);
|
add_bb_to_loop (bb_before_second_loop, first_loop->outer);
|
add_bb_to_loop (bb_before_second_loop, first_loop->outer);
|
|
|
pre_condition =
|
pre_condition =
|
fold_build2 (LE_EXPR, boolean_type_node, first_niters,
|
fold_build2 (LE_EXPR, boolean_type_node, first_niters,
|
build_int_cst (TREE_TYPE (first_niters), 0));
|
build_int_cst (TREE_TYPE (first_niters), 0));
|
skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
|
skip_e = slpeel_add_loop_guard (bb_before_first_loop, pre_condition,
|
bb_before_second_loop, bb_before_first_loop);
|
bb_before_second_loop, bb_before_first_loop);
|
slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
|
slpeel_update_phi_nodes_for_guard1 (skip_e, first_loop,
|
first_loop == new_loop,
|
first_loop == new_loop,
|
&new_exit_bb, &definitions);
|
&new_exit_bb, &definitions);
|
|
|
|
|
/* 3. Add the guard that controls whether the second loop is executed.
|
/* 3. Add the guard that controls whether the second loop is executed.
|
Resulting CFG would be:
|
Resulting CFG would be:
|
|
|
bb_before_first_loop:
|
bb_before_first_loop:
|
if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
|
if (FIRST_NITERS == 0) GOTO bb_before_second_loop (skip first loop)
|
GOTO first-loop
|
GOTO first-loop
|
|
|
first_loop:
|
first_loop:
|
do {
|
do {
|
} while ...
|
} while ...
|
|
|
bb_between_loops:
|
bb_between_loops:
|
if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
|
if (FIRST_NITERS == NITERS) GOTO bb_after_second_loop (skip second loop)
|
GOTO bb_before_second_loop
|
GOTO bb_before_second_loop
|
|
|
bb_before_second_loop:
|
bb_before_second_loop:
|
|
|
second_loop:
|
second_loop:
|
do {
|
do {
|
} while ...
|
} while ...
|
|
|
bb_after_second_loop:
|
bb_after_second_loop:
|
|
|
orig_exit_bb:
|
orig_exit_bb:
|
*/
|
*/
|
|
|
bb_between_loops = new_exit_bb;
|
bb_between_loops = new_exit_bb;
|
bb_after_second_loop = split_edge (second_loop->single_exit);
|
bb_after_second_loop = split_edge (second_loop->single_exit);
|
add_bb_to_loop (bb_after_second_loop, second_loop->outer);
|
add_bb_to_loop (bb_after_second_loop, second_loop->outer);
|
|
|
pre_condition =
|
pre_condition =
|
fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
|
fold_build2 (EQ_EXPR, boolean_type_node, first_niters, niters);
|
skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition,
|
skip_e = slpeel_add_loop_guard (bb_between_loops, pre_condition,
|
bb_after_second_loop, bb_before_first_loop);
|
bb_after_second_loop, bb_before_first_loop);
|
slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
|
slpeel_update_phi_nodes_for_guard2 (skip_e, second_loop,
|
second_loop == new_loop, &new_exit_bb);
|
second_loop == new_loop, &new_exit_bb);
|
|
|
/* 4. Make first-loop iterate FIRST_NITERS times, if requested.
|
/* 4. Make first-loop iterate FIRST_NITERS times, if requested.
|
*/
|
*/
|
if (update_first_loop_count)
|
if (update_first_loop_count)
|
slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
|
slpeel_make_loop_iterate_ntimes (first_loop, first_niters);
|
|
|
BITMAP_FREE (definitions);
|
BITMAP_FREE (definitions);
|
delete_update_ssa ();
|
delete_update_ssa ();
|
|
|
return new_loop;
|
return new_loop;
|
}
|
}
|
|
|
/* Function vect_get_loop_location.
|
/* Function vect_get_loop_location.
|
|
|
Extract the location of the loop in the source code.
|
Extract the location of the loop in the source code.
|
If the loop is not well formed for vectorization, an estimated
|
If the loop is not well formed for vectorization, an estimated
|
location is calculated.
|
location is calculated.
|
Return the loop location if succeed and NULL if not. */
|
Return the loop location if succeed and NULL if not. */
|
|
|
LOC
|
LOC
|
find_loop_location (struct loop *loop)
|
find_loop_location (struct loop *loop)
|
{
|
{
|
tree node = NULL_TREE;
|
tree node = NULL_TREE;
|
basic_block bb;
|
basic_block bb;
|
block_stmt_iterator si;
|
block_stmt_iterator si;
|
|
|
if (!loop)
|
if (!loop)
|
return UNKNOWN_LOC;
|
return UNKNOWN_LOC;
|
|
|
node = get_loop_exit_condition (loop);
|
node = get_loop_exit_condition (loop);
|
|
|
if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node)
|
if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node)
|
&& EXPR_FILENAME (node) && EXPR_LINENO (node))
|
&& EXPR_FILENAME (node) && EXPR_LINENO (node))
|
return EXPR_LOC (node);
|
return EXPR_LOC (node);
|
|
|
/* If we got here the loop is probably not "well formed",
|
/* If we got here the loop is probably not "well formed",
|
try to estimate the loop location */
|
try to estimate the loop location */
|
|
|
if (!loop->header)
|
if (!loop->header)
|
return UNKNOWN_LOC;
|
return UNKNOWN_LOC;
|
|
|
bb = loop->header;
|
bb = loop->header;
|
|
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
{
|
{
|
node = bsi_stmt (si);
|
node = bsi_stmt (si);
|
if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node))
|
if (node && EXPR_P (node) && EXPR_HAS_LOCATION (node))
|
return EXPR_LOC (node);
|
return EXPR_LOC (node);
|
}
|
}
|
|
|
return UNKNOWN_LOC;
|
return UNKNOWN_LOC;
|
}
|
}
|
|
|
|
|
/*************************************************************************
|
/*************************************************************************
|
Vectorization Debug Information.
|
Vectorization Debug Information.
|
*************************************************************************/
|
*************************************************************************/
|
|
|
/* Function vect_set_verbosity_level.
|
/* Function vect_set_verbosity_level.
|
|
|
Called from toplev.c upon detection of the
|
Called from toplev.c upon detection of the
|
-ftree-vectorizer-verbose=N option. */
|
-ftree-vectorizer-verbose=N option. */
|
|
|
void
|
void
|
vect_set_verbosity_level (const char *val)
|
vect_set_verbosity_level (const char *val)
|
{
|
{
|
unsigned int vl;
|
unsigned int vl;
|
|
|
vl = atoi (val);
|
vl = atoi (val);
|
if (vl < MAX_VERBOSITY_LEVEL)
|
if (vl < MAX_VERBOSITY_LEVEL)
|
vect_verbosity_level = vl;
|
vect_verbosity_level = vl;
|
else
|
else
|
vect_verbosity_level = MAX_VERBOSITY_LEVEL - 1;
|
vect_verbosity_level = MAX_VERBOSITY_LEVEL - 1;
|
}
|
}
|
|
|
|
|
/* Function vect_set_dump_settings.
|
/* Function vect_set_dump_settings.
|
|
|
Fix the verbosity level of the vectorizer if the
|
Fix the verbosity level of the vectorizer if the
|
requested level was not set explicitly using the flag
|
requested level was not set explicitly using the flag
|
-ftree-vectorizer-verbose=N.
|
-ftree-vectorizer-verbose=N.
|
Decide where to print the debugging information (dump_file/stderr).
|
Decide where to print the debugging information (dump_file/stderr).
|
If the user defined the verbosity level, but there is no dump file,
|
If the user defined the verbosity level, but there is no dump file,
|
print to stderr, otherwise print to the dump file. */
|
print to stderr, otherwise print to the dump file. */
|
|
|
static void
|
static void
|
vect_set_dump_settings (void)
|
vect_set_dump_settings (void)
|
{
|
{
|
vect_dump = dump_file;
|
vect_dump = dump_file;
|
|
|
/* Check if the verbosity level was defined by the user: */
|
/* Check if the verbosity level was defined by the user: */
|
if (vect_verbosity_level != MAX_VERBOSITY_LEVEL)
|
if (vect_verbosity_level != MAX_VERBOSITY_LEVEL)
|
{
|
{
|
/* If there is no dump file, print to stderr. */
|
/* If there is no dump file, print to stderr. */
|
if (!dump_file)
|
if (!dump_file)
|
vect_dump = stderr;
|
vect_dump = stderr;
|
return;
|
return;
|
}
|
}
|
|
|
/* User didn't specify verbosity level: */
|
/* User didn't specify verbosity level: */
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
if (dump_file && (dump_flags & TDF_DETAILS))
|
vect_verbosity_level = REPORT_DETAILS;
|
vect_verbosity_level = REPORT_DETAILS;
|
else if (dump_file && (dump_flags & TDF_STATS))
|
else if (dump_file && (dump_flags & TDF_STATS))
|
vect_verbosity_level = REPORT_UNVECTORIZED_LOOPS;
|
vect_verbosity_level = REPORT_UNVECTORIZED_LOOPS;
|
else
|
else
|
vect_verbosity_level = REPORT_NONE;
|
vect_verbosity_level = REPORT_NONE;
|
|
|
gcc_assert (dump_file || vect_verbosity_level == REPORT_NONE);
|
gcc_assert (dump_file || vect_verbosity_level == REPORT_NONE);
|
}
|
}
|
|
|
|
|
/* Function debug_loop_details.
|
/* Function debug_loop_details.
|
|
|
For vectorization debug dumps. */
|
For vectorization debug dumps. */
|
|
|
bool
|
bool
|
vect_print_dump_info (enum verbosity_levels vl)
|
vect_print_dump_info (enum verbosity_levels vl)
|
{
|
{
|
if (vl > vect_verbosity_level)
|
if (vl > vect_verbosity_level)
|
return false;
|
return false;
|
|
|
if (!current_function_decl || !vect_dump)
|
if (!current_function_decl || !vect_dump)
|
return false;
|
return false;
|
|
|
if (vect_loop_location == UNKNOWN_LOC)
|
if (vect_loop_location == UNKNOWN_LOC)
|
fprintf (vect_dump, "\n%s:%d: note: ",
|
fprintf (vect_dump, "\n%s:%d: note: ",
|
DECL_SOURCE_FILE (current_function_decl),
|
DECL_SOURCE_FILE (current_function_decl),
|
DECL_SOURCE_LINE (current_function_decl));
|
DECL_SOURCE_LINE (current_function_decl));
|
else
|
else
|
fprintf (vect_dump, "\n%s:%d: note: ",
|
fprintf (vect_dump, "\n%s:%d: note: ",
|
LOC_FILE (vect_loop_location), LOC_LINE (vect_loop_location));
|
LOC_FILE (vect_loop_location), LOC_LINE (vect_loop_location));
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
|
|
/*************************************************************************
|
/*************************************************************************
|
Vectorization Utilities.
|
Vectorization Utilities.
|
*************************************************************************/
|
*************************************************************************/
|
|
|
/* Function new_stmt_vec_info.
|
/* Function new_stmt_vec_info.
|
|
|
Create and initialize a new stmt_vec_info struct for STMT. */
|
Create and initialize a new stmt_vec_info struct for STMT. */
|
|
|
stmt_vec_info
|
stmt_vec_info
|
new_stmt_vec_info (tree stmt, loop_vec_info loop_vinfo)
|
new_stmt_vec_info (tree stmt, loop_vec_info loop_vinfo)
|
{
|
{
|
stmt_vec_info res;
|
stmt_vec_info res;
|
res = (stmt_vec_info) xcalloc (1, sizeof (struct _stmt_vec_info));
|
res = (stmt_vec_info) xcalloc (1, sizeof (struct _stmt_vec_info));
|
|
|
STMT_VINFO_TYPE (res) = undef_vec_info_type;
|
STMT_VINFO_TYPE (res) = undef_vec_info_type;
|
STMT_VINFO_STMT (res) = stmt;
|
STMT_VINFO_STMT (res) = stmt;
|
STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
|
STMT_VINFO_LOOP_VINFO (res) = loop_vinfo;
|
STMT_VINFO_RELEVANT_P (res) = 0;
|
STMT_VINFO_RELEVANT_P (res) = 0;
|
STMT_VINFO_LIVE_P (res) = 0;
|
STMT_VINFO_LIVE_P (res) = 0;
|
STMT_VINFO_VECTYPE (res) = NULL;
|
STMT_VINFO_VECTYPE (res) = NULL;
|
STMT_VINFO_VEC_STMT (res) = NULL;
|
STMT_VINFO_VEC_STMT (res) = NULL;
|
STMT_VINFO_IN_PATTERN_P (res) = false;
|
STMT_VINFO_IN_PATTERN_P (res) = false;
|
STMT_VINFO_RELATED_STMT (res) = NULL;
|
STMT_VINFO_RELATED_STMT (res) = NULL;
|
STMT_VINFO_DATA_REF (res) = NULL;
|
STMT_VINFO_DATA_REF (res) = NULL;
|
if (TREE_CODE (stmt) == PHI_NODE)
|
if (TREE_CODE (stmt) == PHI_NODE)
|
STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
|
STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
|
else
|
else
|
STMT_VINFO_DEF_TYPE (res) = vect_loop_def;
|
STMT_VINFO_DEF_TYPE (res) = vect_loop_def;
|
STMT_VINFO_SAME_ALIGN_REFS (res) = VEC_alloc (dr_p, heap, 5);
|
STMT_VINFO_SAME_ALIGN_REFS (res) = VEC_alloc (dr_p, heap, 5);
|
|
|
return res;
|
return res;
|
}
|
}
|
|
|
|
|
/* Function new_loop_vec_info.
|
/* Function new_loop_vec_info.
|
|
|
Create and initialize a new loop_vec_info struct for LOOP, as well as
|
Create and initialize a new loop_vec_info struct for LOOP, as well as
|
stmt_vec_info structs for all the stmts in LOOP. */
|
stmt_vec_info structs for all the stmts in LOOP. */
|
|
|
loop_vec_info
|
loop_vec_info
|
new_loop_vec_info (struct loop *loop)
|
new_loop_vec_info (struct loop *loop)
|
{
|
{
|
loop_vec_info res;
|
loop_vec_info res;
|
basic_block *bbs;
|
basic_block *bbs;
|
block_stmt_iterator si;
|
block_stmt_iterator si;
|
unsigned int i;
|
unsigned int i;
|
|
|
res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
|
res = (loop_vec_info) xcalloc (1, sizeof (struct _loop_vec_info));
|
|
|
bbs = get_loop_body (loop);
|
bbs = get_loop_body (loop);
|
|
|
/* Create stmt_info for all stmts in the loop. */
|
/* Create stmt_info for all stmts in the loop. */
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
{
|
{
|
basic_block bb = bbs[i];
|
basic_block bb = bbs[i];
|
tree phi;
|
tree phi;
|
|
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
stmt_ann_t ann = get_stmt_ann (phi);
|
stmt_ann_t ann = get_stmt_ann (phi);
|
set_stmt_info (ann, new_stmt_vec_info (phi, res));
|
set_stmt_info (ann, new_stmt_vec_info (phi, res));
|
}
|
}
|
|
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
{
|
{
|
tree stmt = bsi_stmt (si);
|
tree stmt = bsi_stmt (si);
|
stmt_ann_t ann;
|
stmt_ann_t ann;
|
|
|
ann = stmt_ann (stmt);
|
ann = stmt_ann (stmt);
|
set_stmt_info (ann, new_stmt_vec_info (stmt, res));
|
set_stmt_info (ann, new_stmt_vec_info (stmt, res));
|
}
|
}
|
}
|
}
|
|
|
LOOP_VINFO_LOOP (res) = loop;
|
LOOP_VINFO_LOOP (res) = loop;
|
LOOP_VINFO_BBS (res) = bbs;
|
LOOP_VINFO_BBS (res) = bbs;
|
LOOP_VINFO_EXIT_COND (res) = NULL;
|
LOOP_VINFO_EXIT_COND (res) = NULL;
|
LOOP_VINFO_NITERS (res) = NULL;
|
LOOP_VINFO_NITERS (res) = NULL;
|
LOOP_VINFO_VECTORIZABLE_P (res) = 0;
|
LOOP_VINFO_VECTORIZABLE_P (res) = 0;
|
LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
|
LOOP_PEELING_FOR_ALIGNMENT (res) = 0;
|
LOOP_VINFO_VECT_FACTOR (res) = 0;
|
LOOP_VINFO_VECT_FACTOR (res) = 0;
|
LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
|
LOOP_VINFO_DATAREFS (res) = VEC_alloc (data_reference_p, heap, 10);
|
LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
|
LOOP_VINFO_DDRS (res) = VEC_alloc (ddr_p, heap, 10 * 10);
|
LOOP_VINFO_UNALIGNED_DR (res) = NULL;
|
LOOP_VINFO_UNALIGNED_DR (res) = NULL;
|
LOOP_VINFO_MAY_MISALIGN_STMTS (res)
|
LOOP_VINFO_MAY_MISALIGN_STMTS (res)
|
= VEC_alloc (tree, heap, PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS));
|
= VEC_alloc (tree, heap, PARAM_VALUE (PARAM_VECT_MAX_VERSION_CHECKS));
|
|
|
return res;
|
return res;
|
}
|
}
|
|
|
|
|
/* Function 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
|
Free LOOP_VINFO struct, as well as all the stmt_vec_info structs of all the
|
stmts in the loop. */
|
stmts in the loop. */
|
|
|
void
|
void
|
destroy_loop_vec_info (loop_vec_info loop_vinfo)
|
destroy_loop_vec_info (loop_vec_info loop_vinfo)
|
{
|
{
|
struct loop *loop;
|
struct loop *loop;
|
basic_block *bbs;
|
basic_block *bbs;
|
int nbbs;
|
int nbbs;
|
block_stmt_iterator si;
|
block_stmt_iterator si;
|
int j;
|
int j;
|
|
|
if (!loop_vinfo)
|
if (!loop_vinfo)
|
return;
|
return;
|
|
|
loop = LOOP_VINFO_LOOP (loop_vinfo);
|
loop = LOOP_VINFO_LOOP (loop_vinfo);
|
|
|
bbs = LOOP_VINFO_BBS (loop_vinfo);
|
bbs = LOOP_VINFO_BBS (loop_vinfo);
|
nbbs = loop->num_nodes;
|
nbbs = loop->num_nodes;
|
|
|
for (j = 0; j < nbbs; j++)
|
for (j = 0; j < nbbs; j++)
|
{
|
{
|
basic_block bb = bbs[j];
|
basic_block bb = bbs[j];
|
tree phi;
|
tree phi;
|
stmt_vec_info stmt_info;
|
stmt_vec_info stmt_info;
|
|
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
|
{
|
{
|
stmt_ann_t ann = stmt_ann (phi);
|
stmt_ann_t ann = stmt_ann (phi);
|
|
|
stmt_info = vinfo_for_stmt (phi);
|
stmt_info = vinfo_for_stmt (phi);
|
free (stmt_info);
|
free (stmt_info);
|
set_stmt_info (ann, NULL);
|
set_stmt_info (ann, NULL);
|
}
|
}
|
|
|
for (si = bsi_start (bb); !bsi_end_p (si); )
|
for (si = bsi_start (bb); !bsi_end_p (si); )
|
{
|
{
|
tree stmt = bsi_stmt (si);
|
tree stmt = bsi_stmt (si);
|
stmt_ann_t ann = stmt_ann (stmt);
|
stmt_ann_t ann = stmt_ann (stmt);
|
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
|
|
|
if (stmt_info)
|
if (stmt_info)
|
{
|
{
|
/* Check if this is a "pattern stmt" (introduced by the
|
/* Check if this is a "pattern stmt" (introduced by the
|
vectorizer during the pattern recognition pass). */
|
vectorizer during the pattern recognition pass). */
|
bool remove_stmt_p = false;
|
bool remove_stmt_p = false;
|
tree orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
|
tree orig_stmt = STMT_VINFO_RELATED_STMT (stmt_info);
|
if (orig_stmt)
|
if (orig_stmt)
|
{
|
{
|
stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
|
stmt_vec_info orig_stmt_info = vinfo_for_stmt (orig_stmt);
|
if (orig_stmt_info
|
if (orig_stmt_info
|
&& STMT_VINFO_IN_PATTERN_P (orig_stmt_info))
|
&& STMT_VINFO_IN_PATTERN_P (orig_stmt_info))
|
remove_stmt_p = true;
|
remove_stmt_p = true;
|
}
|
}
|
|
|
/* Free stmt_vec_info. */
|
/* Free stmt_vec_info. */
|
VEC_free (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmt_info));
|
VEC_free (dr_p, heap, STMT_VINFO_SAME_ALIGN_REFS (stmt_info));
|
free (stmt_info);
|
free (stmt_info);
|
set_stmt_info (ann, NULL);
|
set_stmt_info (ann, NULL);
|
|
|
/* Remove dead "pattern stmts". */
|
/* Remove dead "pattern stmts". */
|
if (remove_stmt_p)
|
if (remove_stmt_p)
|
bsi_remove (&si, true);
|
bsi_remove (&si, true);
|
}
|
}
|
bsi_next (&si);
|
bsi_next (&si);
|
}
|
}
|
}
|
}
|
|
|
free (LOOP_VINFO_BBS (loop_vinfo));
|
free (LOOP_VINFO_BBS (loop_vinfo));
|
free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
|
free_data_refs (LOOP_VINFO_DATAREFS (loop_vinfo));
|
free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
|
free_dependence_relations (LOOP_VINFO_DDRS (loop_vinfo));
|
VEC_free (tree, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
|
VEC_free (tree, heap, LOOP_VINFO_MAY_MISALIGN_STMTS (loop_vinfo));
|
|
|
free (loop_vinfo);
|
free (loop_vinfo);
|
}
|
}
|
|
|
|
|
/* Function vect_force_dr_alignment_p.
|
/* Function vect_force_dr_alignment_p.
|
|
|
Returns whether the alignment of a DECL can be forced to be aligned
|
Returns whether the alignment of a DECL can be forced to be aligned
|
on ALIGNMENT bit boundary. */
|
on ALIGNMENT bit boundary. */
|
|
|
bool
|
bool
|
vect_can_force_dr_alignment_p (tree decl, unsigned int alignment)
|
vect_can_force_dr_alignment_p (tree decl, unsigned int alignment)
|
{
|
{
|
if (TREE_CODE (decl) != VAR_DECL)
|
if (TREE_CODE (decl) != VAR_DECL)
|
return false;
|
return false;
|
|
|
if (DECL_EXTERNAL (decl))
|
if (DECL_EXTERNAL (decl))
|
return false;
|
return false;
|
|
|
if (TREE_ASM_WRITTEN (decl))
|
if (TREE_ASM_WRITTEN (decl))
|
return false;
|
return false;
|
|
|
if (TREE_STATIC (decl))
|
if (TREE_STATIC (decl))
|
return (alignment <= MAX_OFILE_ALIGNMENT);
|
return (alignment <= MAX_OFILE_ALIGNMENT);
|
else
|
else
|
/* This is not 100% correct. The absolute correct stack alignment
|
/* This is not 100% correct. The absolute correct stack alignment
|
is STACK_BOUNDARY. We're supposed to hope, but not assume, that
|
is STACK_BOUNDARY. We're supposed to hope, but not assume, that
|
PREFERRED_STACK_BOUNDARY is honored by all translation units.
|
PREFERRED_STACK_BOUNDARY is honored by all translation units.
|
However, until someone implements forced stack alignment, SSE
|
However, until someone implements forced stack alignment, SSE
|
isn't really usable without this. */
|
isn't really usable without this. */
|
return (alignment <= PREFERRED_STACK_BOUNDARY);
|
return (alignment <= PREFERRED_STACK_BOUNDARY);
|
}
|
}
|
|
|
|
|
/* Function get_vectype_for_scalar_type.
|
/* Function get_vectype_for_scalar_type.
|
|
|
Returns the vector type corresponding to SCALAR_TYPE as supported
|
Returns the vector type corresponding to SCALAR_TYPE as supported
|
by the target. */
|
by the target. */
|
|
|
tree
|
tree
|
get_vectype_for_scalar_type (tree scalar_type)
|
get_vectype_for_scalar_type (tree scalar_type)
|
{
|
{
|
enum machine_mode inner_mode = TYPE_MODE (scalar_type);
|
enum machine_mode inner_mode = TYPE_MODE (scalar_type);
|
int nbytes = GET_MODE_SIZE (inner_mode);
|
int nbytes = GET_MODE_SIZE (inner_mode);
|
int nunits;
|
int nunits;
|
tree vectype;
|
tree vectype;
|
|
|
if (nbytes == 0 || nbytes >= UNITS_PER_SIMD_WORD)
|
if (nbytes == 0 || nbytes >= UNITS_PER_SIMD_WORD)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
/* FORNOW: Only a single vector size per target (UNITS_PER_SIMD_WORD)
|
/* FORNOW: Only a single vector size per target (UNITS_PER_SIMD_WORD)
|
is expected. */
|
is expected. */
|
nunits = UNITS_PER_SIMD_WORD / nbytes;
|
nunits = UNITS_PER_SIMD_WORD / nbytes;
|
|
|
vectype = build_vector_type (scalar_type, nunits);
|
vectype = build_vector_type (scalar_type, nunits);
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "get vectype with %d units of type ", nunits);
|
fprintf (vect_dump, "get vectype with %d units of type ", nunits);
|
print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
|
print_generic_expr (vect_dump, scalar_type, TDF_SLIM);
|
}
|
}
|
|
|
if (!vectype)
|
if (!vectype)
|
return NULL_TREE;
|
return NULL_TREE;
|
|
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "vectype: ");
|
fprintf (vect_dump, "vectype: ");
|
print_generic_expr (vect_dump, vectype, TDF_SLIM);
|
print_generic_expr (vect_dump, vectype, TDF_SLIM);
|
}
|
}
|
|
|
if (!VECTOR_MODE_P (TYPE_MODE (vectype))
|
if (!VECTOR_MODE_P (TYPE_MODE (vectype))
|
&& !INTEGRAL_MODE_P (TYPE_MODE (vectype)))
|
&& !INTEGRAL_MODE_P (TYPE_MODE (vectype)))
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "mode not supported by target.");
|
fprintf (vect_dump, "mode not supported by target.");
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
return vectype;
|
return vectype;
|
}
|
}
|
|
|
|
|
/* Function vect_supportable_dr_alignment
|
/* Function vect_supportable_dr_alignment
|
|
|
Return whether the data reference DR is supported with respect to its
|
Return whether the data reference DR is supported with respect to its
|
alignment. */
|
alignment. */
|
|
|
enum dr_alignment_support
|
enum dr_alignment_support
|
vect_supportable_dr_alignment (struct data_reference *dr)
|
vect_supportable_dr_alignment (struct data_reference *dr)
|
{
|
{
|
tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
|
tree vectype = STMT_VINFO_VECTYPE (vinfo_for_stmt (DR_STMT (dr)));
|
enum machine_mode mode = (int) TYPE_MODE (vectype);
|
enum machine_mode mode = (int) TYPE_MODE (vectype);
|
|
|
if (aligned_access_p (dr))
|
if (aligned_access_p (dr))
|
return dr_aligned;
|
return dr_aligned;
|
|
|
/* Possibly unaligned access. */
|
/* Possibly unaligned access. */
|
|
|
if (DR_IS_READ (dr))
|
if (DR_IS_READ (dr))
|
{
|
{
|
if (vec_realign_load_optab->handlers[mode].insn_code != CODE_FOR_nothing
|
if (vec_realign_load_optab->handlers[mode].insn_code != CODE_FOR_nothing
|
&& (!targetm.vectorize.builtin_mask_for_load
|
&& (!targetm.vectorize.builtin_mask_for_load
|
|| targetm.vectorize.builtin_mask_for_load ()))
|
|| targetm.vectorize.builtin_mask_for_load ()))
|
return dr_unaligned_software_pipeline;
|
return dr_unaligned_software_pipeline;
|
|
|
if (movmisalign_optab->handlers[mode].insn_code != CODE_FOR_nothing)
|
if (movmisalign_optab->handlers[mode].insn_code != CODE_FOR_nothing)
|
/* Can't software pipeline the loads, but can at least do them. */
|
/* Can't software pipeline the loads, but can at least do them. */
|
return dr_unaligned_supported;
|
return dr_unaligned_supported;
|
}
|
}
|
|
|
/* Unsupported. */
|
/* Unsupported. */
|
return dr_unaligned_unsupported;
|
return dr_unaligned_unsupported;
|
}
|
}
|
|
|
|
|
/* Function vect_is_simple_use.
|
/* Function vect_is_simple_use.
|
|
|
Input:
|
Input:
|
LOOP - the loop that is being vectorized.
|
LOOP - the loop that is being vectorized.
|
OPERAND - operand of a stmt in LOOP.
|
OPERAND - operand of a stmt in LOOP.
|
DEF - the defining stmt in case OPERAND is an SSA_NAME.
|
DEF - the defining stmt in case OPERAND is an SSA_NAME.
|
|
|
Returns whether a stmt with OPERAND can be vectorized.
|
Returns whether a stmt with OPERAND can be vectorized.
|
Supportable operands are constants, loop invariants, and operands that are
|
Supportable operands are constants, loop invariants, and operands that are
|
defined by the current iteration of the loop. Unsupportable operands are
|
defined by the current iteration of the loop. Unsupportable operands are
|
those that are defined by a previous iteration of the loop (as is the case
|
those that are defined by a previous iteration of the loop (as is the case
|
in reduction/induction computations). */
|
in reduction/induction computations). */
|
|
|
bool
|
bool
|
vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt,
|
vect_is_simple_use (tree operand, loop_vec_info loop_vinfo, tree *def_stmt,
|
tree *def, enum vect_def_type *dt)
|
tree *def, enum vect_def_type *dt)
|
{
|
{
|
basic_block bb;
|
basic_block bb;
|
stmt_vec_info stmt_vinfo;
|
stmt_vec_info stmt_vinfo;
|
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
|
|
|
*def_stmt = NULL_TREE;
|
*def_stmt = NULL_TREE;
|
*def = NULL_TREE;
|
*def = NULL_TREE;
|
|
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "vect_is_simple_use: operand ");
|
fprintf (vect_dump, "vect_is_simple_use: operand ");
|
print_generic_expr (vect_dump, operand, TDF_SLIM);
|
print_generic_expr (vect_dump, operand, TDF_SLIM);
|
}
|
}
|
|
|
if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
|
if (TREE_CODE (operand) == INTEGER_CST || TREE_CODE (operand) == REAL_CST)
|
{
|
{
|
*dt = vect_constant_def;
|
*dt = vect_constant_def;
|
return true;
|
return true;
|
}
|
}
|
|
|
if (TREE_CODE (operand) != SSA_NAME)
|
if (TREE_CODE (operand) != SSA_NAME)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "not ssa-name.");
|
fprintf (vect_dump, "not ssa-name.");
|
return false;
|
return false;
|
}
|
}
|
|
|
*def_stmt = SSA_NAME_DEF_STMT (operand);
|
*def_stmt = SSA_NAME_DEF_STMT (operand);
|
if (*def_stmt == NULL_TREE )
|
if (*def_stmt == NULL_TREE )
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "no def_stmt.");
|
fprintf (vect_dump, "no def_stmt.");
|
return false;
|
return false;
|
}
|
}
|
|
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "def_stmt: ");
|
fprintf (vect_dump, "def_stmt: ");
|
print_generic_expr (vect_dump, *def_stmt, TDF_SLIM);
|
print_generic_expr (vect_dump, *def_stmt, TDF_SLIM);
|
}
|
}
|
|
|
/* empty stmt is expected only in case of a function argument.
|
/* empty stmt is expected only in case of a function argument.
|
(Otherwise - we expect a phi_node or a modify_expr). */
|
(Otherwise - we expect a phi_node or a modify_expr). */
|
if (IS_EMPTY_STMT (*def_stmt))
|
if (IS_EMPTY_STMT (*def_stmt))
|
{
|
{
|
tree arg = TREE_OPERAND (*def_stmt, 0);
|
tree arg = TREE_OPERAND (*def_stmt, 0);
|
if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST)
|
if (TREE_CODE (arg) == INTEGER_CST || TREE_CODE (arg) == REAL_CST)
|
{
|
{
|
*def = operand;
|
*def = operand;
|
*dt = vect_invariant_def;
|
*dt = vect_invariant_def;
|
return true;
|
return true;
|
}
|
}
|
|
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "Unexpected empty stmt.");
|
fprintf (vect_dump, "Unexpected empty stmt.");
|
return false;
|
return false;
|
}
|
}
|
|
|
bb = bb_for_stmt (*def_stmt);
|
bb = bb_for_stmt (*def_stmt);
|
if (!flow_bb_inside_loop_p (loop, bb))
|
if (!flow_bb_inside_loop_p (loop, bb))
|
*dt = vect_invariant_def;
|
*dt = vect_invariant_def;
|
else
|
else
|
{
|
{
|
stmt_vinfo = vinfo_for_stmt (*def_stmt);
|
stmt_vinfo = vinfo_for_stmt (*def_stmt);
|
*dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
|
*dt = STMT_VINFO_DEF_TYPE (stmt_vinfo);
|
}
|
}
|
|
|
if (*dt == vect_unknown_def_type)
|
if (*dt == vect_unknown_def_type)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "Unsupported pattern.");
|
fprintf (vect_dump, "Unsupported pattern.");
|
return false;
|
return false;
|
}
|
}
|
|
|
/* stmts inside the loop that have been identified as performing
|
/* stmts inside the loop that have been identified as performing
|
a reduction operation cannot have uses in the loop. */
|
a reduction operation cannot have uses in the loop. */
|
if (*dt == vect_reduction_def && TREE_CODE (*def_stmt) != PHI_NODE)
|
if (*dt == vect_reduction_def && TREE_CODE (*def_stmt) != PHI_NODE)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "reduction used in loop.");
|
fprintf (vect_dump, "reduction used in loop.");
|
return false;
|
return false;
|
}
|
}
|
|
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "type of def: %d.",*dt);
|
fprintf (vect_dump, "type of def: %d.",*dt);
|
|
|
switch (TREE_CODE (*def_stmt))
|
switch (TREE_CODE (*def_stmt))
|
{
|
{
|
case PHI_NODE:
|
case PHI_NODE:
|
*def = PHI_RESULT (*def_stmt);
|
*def = PHI_RESULT (*def_stmt);
|
gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def
|
gcc_assert (*dt == vect_induction_def || *dt == vect_reduction_def
|
|| *dt == vect_invariant_def);
|
|| *dt == vect_invariant_def);
|
break;
|
break;
|
|
|
case MODIFY_EXPR:
|
case MODIFY_EXPR:
|
*def = TREE_OPERAND (*def_stmt, 0);
|
*def = TREE_OPERAND (*def_stmt, 0);
|
gcc_assert (*dt == vect_loop_def || *dt == vect_invariant_def);
|
gcc_assert (*dt == vect_loop_def || *dt == vect_invariant_def);
|
break;
|
break;
|
|
|
default:
|
default:
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "unsupported defining stmt: ");
|
fprintf (vect_dump, "unsupported defining stmt: ");
|
return false;
|
return false;
|
}
|
}
|
|
|
if (*dt == vect_induction_def)
|
if (*dt == vect_induction_def)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "induction not supported.");
|
fprintf (vect_dump, "induction not supported.");
|
return false;
|
return false;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
|
|
/* Function reduction_code_for_scalar_code
|
/* Function reduction_code_for_scalar_code
|
|
|
Input:
|
Input:
|
CODE - tree_code of a reduction operations.
|
CODE - tree_code of a reduction operations.
|
|
|
Output:
|
Output:
|
REDUC_CODE - the corresponding tree-code to be used to reduce the
|
REDUC_CODE - the corresponding tree-code to be used to reduce the
|
vector of partial results into a single scalar result (which
|
vector of partial results into a single scalar result (which
|
will also reside in a vector).
|
will also reside in a vector).
|
|
|
Return TRUE if a corresponding REDUC_CODE was found, FALSE otherwise. */
|
Return TRUE if a corresponding REDUC_CODE was found, FALSE otherwise. */
|
|
|
bool
|
bool
|
reduction_code_for_scalar_code (enum tree_code code,
|
reduction_code_for_scalar_code (enum tree_code code,
|
enum tree_code *reduc_code)
|
enum tree_code *reduc_code)
|
{
|
{
|
switch (code)
|
switch (code)
|
{
|
{
|
case MAX_EXPR:
|
case MAX_EXPR:
|
*reduc_code = REDUC_MAX_EXPR;
|
*reduc_code = REDUC_MAX_EXPR;
|
return true;
|
return true;
|
|
|
case MIN_EXPR:
|
case MIN_EXPR:
|
*reduc_code = REDUC_MIN_EXPR;
|
*reduc_code = REDUC_MIN_EXPR;
|
return true;
|
return true;
|
|
|
case PLUS_EXPR:
|
case PLUS_EXPR:
|
*reduc_code = REDUC_PLUS_EXPR;
|
*reduc_code = REDUC_PLUS_EXPR;
|
return true;
|
return true;
|
|
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Function vect_is_simple_reduction
|
/* Function vect_is_simple_reduction
|
|
|
Detect a cross-iteration def-use cucle that represents a simple
|
Detect a cross-iteration def-use cucle that represents a simple
|
reduction computation. We look for the following pattern:
|
reduction computation. We look for the following pattern:
|
|
|
loop_header:
|
loop_header:
|
a1 = phi < a0, a2 >
|
a1 = phi < a0, a2 >
|
a3 = ...
|
a3 = ...
|
a2 = operation (a3, a1)
|
a2 = operation (a3, a1)
|
|
|
such that:
|
such that:
|
1. operation is commutative and associative and it is safe to
|
1. operation is commutative and associative and it is safe to
|
change the order of the computation.
|
change the order of the computation.
|
2. no uses for a2 in the loop (a2 is used out of the loop)
|
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.
|
3. no uses of a1 in the loop besides the reduction operation.
|
|
|
Condition 1 is tested here.
|
Condition 1 is tested here.
|
Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized. */
|
Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized. */
|
|
|
tree
|
tree
|
vect_is_simple_reduction (struct loop *loop, tree phi)
|
vect_is_simple_reduction (struct loop *loop, tree phi)
|
{
|
{
|
edge latch_e = loop_latch_edge (loop);
|
edge latch_e = loop_latch_edge (loop);
|
tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
|
tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
|
tree def_stmt, def1, def2;
|
tree def_stmt, def1, def2;
|
enum tree_code code;
|
enum tree_code code;
|
int op_type;
|
int op_type;
|
tree operation, op1, op2;
|
tree operation, op1, op2;
|
tree type;
|
tree type;
|
|
|
if (TREE_CODE (loop_arg) != SSA_NAME)
|
if (TREE_CODE (loop_arg) != SSA_NAME)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: not ssa_name: ");
|
fprintf (vect_dump, "reduction: not ssa_name: ");
|
print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
|
print_generic_expr (vect_dump, loop_arg, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
def_stmt = SSA_NAME_DEF_STMT (loop_arg);
|
def_stmt = SSA_NAME_DEF_STMT (loop_arg);
|
if (!def_stmt)
|
if (!def_stmt)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "reduction: no def_stmt.");
|
fprintf (vect_dump, "reduction: no def_stmt.");
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
if (TREE_CODE (def_stmt) != MODIFY_EXPR)
|
if (TREE_CODE (def_stmt) != MODIFY_EXPR)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
|
print_generic_expr (vect_dump, def_stmt, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
operation = TREE_OPERAND (def_stmt, 1);
|
operation = TREE_OPERAND (def_stmt, 1);
|
code = TREE_CODE (operation);
|
code = TREE_CODE (operation);
|
if (!commutative_tree_code (code) || !associative_tree_code (code))
|
if (!commutative_tree_code (code) || !associative_tree_code (code))
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: not commutative/associative: ");
|
fprintf (vect_dump, "reduction: not commutative/associative: ");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
op_type = TREE_CODE_LENGTH (code);
|
op_type = TREE_CODE_LENGTH (code);
|
if (op_type != binary_op)
|
if (op_type != binary_op)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: not binary operation: ");
|
fprintf (vect_dump, "reduction: not binary operation: ");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
op1 = TREE_OPERAND (operation, 0);
|
op1 = TREE_OPERAND (operation, 0);
|
op2 = TREE_OPERAND (operation, 1);
|
op2 = TREE_OPERAND (operation, 1);
|
if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
|
if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: uses not ssa_names: ");
|
fprintf (vect_dump, "reduction: uses not ssa_names: ");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
/* Check that it's ok to change the order of the computation. */
|
/* Check that it's ok to change the order of the computation. */
|
type = TREE_TYPE (operation);
|
type = TREE_TYPE (operation);
|
if (TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op1))
|
if (TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op1))
|
|| TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op2)))
|
|| TYPE_MAIN_VARIANT (type) != TYPE_MAIN_VARIANT (TREE_TYPE (op2)))
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: multiple types: operation type: ");
|
fprintf (vect_dump, "reduction: multiple types: operation type: ");
|
print_generic_expr (vect_dump, type, TDF_SLIM);
|
print_generic_expr (vect_dump, type, TDF_SLIM);
|
fprintf (vect_dump, ", operands types: ");
|
fprintf (vect_dump, ", operands types: ");
|
print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
|
print_generic_expr (vect_dump, TREE_TYPE (op1), TDF_SLIM);
|
fprintf (vect_dump, ",");
|
fprintf (vect_dump, ",");
|
print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
|
print_generic_expr (vect_dump, TREE_TYPE (op2), TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
/* CHECKME: check for !flag_finite_math_only too? */
|
/* CHECKME: check for !flag_finite_math_only too? */
|
if (SCALAR_FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
|
if (SCALAR_FLOAT_TYPE_P (type) && !flag_unsafe_math_optimizations)
|
{
|
{
|
/* Changing the order of operations changes the semantics. */
|
/* Changing the order of operations changes the semantics. */
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: unsafe fp math optimization: ");
|
fprintf (vect_dump, "reduction: unsafe fp math optimization: ");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type))
|
else if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_TRAPS (type))
|
{
|
{
|
/* Changing the order of operations changes the semantics. */
|
/* Changing the order of operations changes the semantics. */
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: unsafe int math optimization: ");
|
fprintf (vect_dump, "reduction: unsafe int math optimization: ");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
/* reduction is safe. we're dealing with one of the following:
|
/* reduction is safe. we're dealing with one of the following:
|
1) integer arithmetic and no trapv
|
1) integer arithmetic and no trapv
|
2) floating point arithmetic, and special flags permit this optimization.
|
2) floating point arithmetic, and special flags permit this optimization.
|
*/
|
*/
|
def1 = SSA_NAME_DEF_STMT (op1);
|
def1 = SSA_NAME_DEF_STMT (op1);
|
def2 = SSA_NAME_DEF_STMT (op2);
|
def2 = SSA_NAME_DEF_STMT (op2);
|
if (!def1 || !def2)
|
if (!def1 || !def2)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: no defs for operands: ");
|
fprintf (vect_dump, "reduction: no defs for operands: ");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
|
|
if (TREE_CODE (def1) == MODIFY_EXPR
|
if (TREE_CODE (def1) == MODIFY_EXPR
|
&& flow_bb_inside_loop_p (loop, bb_for_stmt (def1))
|
&& flow_bb_inside_loop_p (loop, bb_for_stmt (def1))
|
&& def2 == phi)
|
&& def2 == phi)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "detected reduction:");
|
fprintf (vect_dump, "detected reduction:");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
return def_stmt;
|
return def_stmt;
|
}
|
}
|
else if (TREE_CODE (def2) == MODIFY_EXPR
|
else if (TREE_CODE (def2) == MODIFY_EXPR
|
&& flow_bb_inside_loop_p (loop, bb_for_stmt (def2))
|
&& flow_bb_inside_loop_p (loop, bb_for_stmt (def2))
|
&& def1 == phi)
|
&& def1 == phi)
|
{
|
{
|
/* Swap operands (just for simplicity - so that the rest of the code
|
/* Swap operands (just for simplicity - so that the rest of the code
|
can assume that the reduction variable is always the last (second)
|
can assume that the reduction variable is always the last (second)
|
argument). */
|
argument). */
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "detected reduction: need to swap operands:");
|
fprintf (vect_dump, "detected reduction: need to swap operands:");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
swap_tree_operands (def_stmt, &TREE_OPERAND (operation, 0),
|
swap_tree_operands (def_stmt, &TREE_OPERAND (operation, 0),
|
&TREE_OPERAND (operation, 1));
|
&TREE_OPERAND (operation, 1));
|
return def_stmt;
|
return def_stmt;
|
}
|
}
|
else
|
else
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "reduction: unknown pattern.");
|
fprintf (vect_dump, "reduction: unknown pattern.");
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
print_generic_expr (vect_dump, operation, TDF_SLIM);
|
}
|
}
|
return NULL_TREE;
|
return NULL_TREE;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Function vect_is_simple_iv_evolution.
|
/* Function vect_is_simple_iv_evolution.
|
|
|
FORNOW: A simple evolution of an induction variables in the loop is
|
FORNOW: A simple evolution of an induction variables in the loop is
|
considered a polynomial evolution with constant step. */
|
considered a polynomial evolution with constant step. */
|
|
|
bool
|
bool
|
vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
|
vect_is_simple_iv_evolution (unsigned loop_nb, tree access_fn, tree * init,
|
tree * step)
|
tree * step)
|
{
|
{
|
tree init_expr;
|
tree init_expr;
|
tree step_expr;
|
tree step_expr;
|
|
|
tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
|
tree evolution_part = evolution_part_in_loop_num (access_fn, loop_nb);
|
|
|
/* When there is no evolution in this loop, the evolution function
|
/* When there is no evolution in this loop, the evolution function
|
is not "simple". */
|
is not "simple". */
|
if (evolution_part == NULL_TREE)
|
if (evolution_part == NULL_TREE)
|
return false;
|
return false;
|
|
|
/* When the evolution is a polynomial of degree >= 2
|
/* When the evolution is a polynomial of degree >= 2
|
the evolution function is not "simple". */
|
the evolution function is not "simple". */
|
if (tree_is_chrec (evolution_part))
|
if (tree_is_chrec (evolution_part))
|
return false;
|
return false;
|
|
|
step_expr = evolution_part;
|
step_expr = evolution_part;
|
init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
|
init_expr = unshare_expr (initial_condition_in_loop_num (access_fn,
|
loop_nb));
|
loop_nb));
|
|
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
{
|
{
|
fprintf (vect_dump, "step: ");
|
fprintf (vect_dump, "step: ");
|
print_generic_expr (vect_dump, step_expr, TDF_SLIM);
|
print_generic_expr (vect_dump, step_expr, TDF_SLIM);
|
fprintf (vect_dump, ", init: ");
|
fprintf (vect_dump, ", init: ");
|
print_generic_expr (vect_dump, init_expr, TDF_SLIM);
|
print_generic_expr (vect_dump, init_expr, TDF_SLIM);
|
}
|
}
|
|
|
*init = init_expr;
|
*init = init_expr;
|
*step = step_expr;
|
*step = step_expr;
|
|
|
if (TREE_CODE (step_expr) != INTEGER_CST)
|
if (TREE_CODE (step_expr) != INTEGER_CST)
|
{
|
{
|
if (vect_print_dump_info (REPORT_DETAILS))
|
if (vect_print_dump_info (REPORT_DETAILS))
|
fprintf (vect_dump, "step unknown.");
|
fprintf (vect_dump, "step unknown.");
|
return false;
|
return false;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
|
|
/* Function vectorize_loops.
|
/* Function vectorize_loops.
|
|
|
Entry Point to loop vectorization phase. */
|
Entry Point to loop vectorization phase. */
|
|
|
void
|
void
|
vectorize_loops (struct loops *loops)
|
vectorize_loops (struct loops *loops)
|
{
|
{
|
unsigned int i;
|
unsigned int i;
|
unsigned int num_vectorized_loops = 0;
|
unsigned int num_vectorized_loops = 0;
|
|
|
/* Fix the verbosity level if not defined explicitly by the user. */
|
/* Fix the verbosity level if not defined explicitly by the user. */
|
vect_set_dump_settings ();
|
vect_set_dump_settings ();
|
|
|
/* Allocate the bitmap that records which virtual variables that
|
/* Allocate the bitmap that records which virtual variables that
|
need to be renamed. */
|
need to be renamed. */
|
vect_vnames_to_rename = BITMAP_ALLOC (NULL);
|
vect_vnames_to_rename = BITMAP_ALLOC (NULL);
|
|
|
/* ----------- Analyze loops. ----------- */
|
/* ----------- Analyze loops. ----------- */
|
|
|
/* If some loop was duplicated, it gets bigger number
|
/* If some loop was duplicated, it gets bigger number
|
than all previously defined loops. This fact allows us to run
|
than all previously defined loops. This fact allows us to run
|
only over initial loops skipping newly generated ones. */
|
only over initial loops skipping newly generated ones. */
|
vect_loops_num = loops->num;
|
vect_loops_num = loops->num;
|
for (i = 1; i < vect_loops_num; i++)
|
for (i = 1; i < vect_loops_num; i++)
|
{
|
{
|
loop_vec_info loop_vinfo;
|
loop_vec_info loop_vinfo;
|
struct loop *loop = loops->parray[i];
|
struct loop *loop = loops->parray[i];
|
|
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
|
|
vect_loop_location = find_loop_location (loop);
|
vect_loop_location = find_loop_location (loop);
|
loop_vinfo = vect_analyze_loop (loop);
|
loop_vinfo = vect_analyze_loop (loop);
|
loop->aux = loop_vinfo;
|
loop->aux = loop_vinfo;
|
|
|
if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
|
if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
|
continue;
|
continue;
|
|
|
vect_transform_loop (loop_vinfo, loops);
|
vect_transform_loop (loop_vinfo, loops);
|
num_vectorized_loops++;
|
num_vectorized_loops++;
|
}
|
}
|
vect_loop_location = UNKNOWN_LOC;
|
vect_loop_location = UNKNOWN_LOC;
|
|
|
if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS))
|
if (vect_print_dump_info (REPORT_VECTORIZED_LOOPS))
|
fprintf (vect_dump, "vectorized %u loops in function.\n",
|
fprintf (vect_dump, "vectorized %u loops in function.\n",
|
num_vectorized_loops);
|
num_vectorized_loops);
|
|
|
/* ----------- Finalize. ----------- */
|
/* ----------- Finalize. ----------- */
|
|
|
BITMAP_FREE (vect_vnames_to_rename);
|
BITMAP_FREE (vect_vnames_to_rename);
|
|
|
for (i = 1; i < vect_loops_num; i++)
|
for (i = 1; i < vect_loops_num; i++)
|
{
|
{
|
struct loop *loop = loops->parray[i];
|
struct loop *loop = loops->parray[i];
|
loop_vec_info loop_vinfo;
|
loop_vec_info loop_vinfo;
|
|
|
if (!loop)
|
if (!loop)
|
continue;
|
continue;
|
loop_vinfo = loop->aux;
|
loop_vinfo = loop->aux;
|
destroy_loop_vec_info (loop_vinfo);
|
destroy_loop_vec_info (loop_vinfo);
|
loop->aux = NULL;
|
loop->aux = NULL;
|
}
|
}
|
}
|
}
|
|
|
