/* Detection of Static Control Parts (SCoP) for Graphite.
- Copyright (C) 2009-2017 Free Software Foundation, Inc.
+ Copyright (C) 2009-2021 Free Software Foundation, Inc.
Contributed by Sebastian Pop <sebastian.pop@amd.com> and
Tobias Grosser <grosser@fim.uni-passau.de>.
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
-#define USES_ISL
+#define INCLUDE_ISL
#include "config.h"
#include "backend.h"
#include "cfghooks.h"
#include "domwalk.h"
-#include "params.h"
#include "tree.h"
#include "gimple.h"
#include "ssa.h"
#define DEBUG_PRINT(args) do \
{ \
if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
- } while (0);
+ } while (0)
/* Pretty print to FILE all the SCoPs in DOT format and mark them with
different colors. If there are not enough colors, paint the
scops.release ();
}
-/* Return true if BB is empty, contains only DEBUG_INSNs. */
-
-static bool
-trivially_empty_bb_p (basic_block bb)
-{
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- if (gimple_code (gsi_stmt (gsi)) != GIMPLE_DEBUG
- && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
- return false;
-
- return true;
-}
-
-/* Can all ivs be represented by a signed integer?
- As isl might generate negative values in its expressions, signed loop ivs
- are required in the backend. */
-
-static bool
-loop_ivs_can_be_represented (loop_p loop)
-{
- unsigned type_long_long = TYPE_PRECISION (long_long_integer_type_node);
- for (gphi_iterator psi = gsi_start_phis (loop->header); !gsi_end_p (psi);
- gsi_next (&psi))
- {
- gphi *phi = psi.phi ();
- tree res = PHI_RESULT (phi);
- tree type = TREE_TYPE (res);
-
- if (TYPE_UNSIGNED (type) && TYPE_PRECISION (type) >= type_long_long)
- return false;
- }
-
- return true;
-}
-
/* Returns a COND_EXPR statement when BB has a single predecessor, the
edge between BB and its predecessor is not a loop exit edge, and
the last statement of the single predecessor is a COND_EXPR. */
sese_l get_sese (loop_p loop);
- /* Return the closest dominator with a single entry edge. In case of a
- back-loop the back-edge is not counted. */
-
- static edge get_nearest_dom_with_single_entry (basic_block dom);
-
- /* Return the closest post-dominator with a single exit edge. In case of a
- back-loop the back-edge is not counted. */
-
- static edge get_nearest_pdom_with_single_exit (basic_block dom);
-
/* Merge scops at same loop depth and returns the new sese.
Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
void remove_intersecting_scops (sese_l s1);
- /* Return true when a statement in SCOP cannot be represented by Graphite.
- The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
- Limit the number of bbs between adjacent loops to
- PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
+ /* Return true when a statement in SCOP cannot be represented by Graphite. */
bool harmful_loop_in_region (sese_l scop) const;
Something like "i * n" or "n * m" is not allowed. */
- static bool graphite_can_represent_scev (tree scev);
+ static bool graphite_can_represent_scev (sese_l scop, tree scev);
/* Return true when EXPR can be represented in the polyhedral model.
edge scop_begin = loop_preheader_edge (loop);
edge scop_end = single_exit (loop);
- if (!scop_end || (scop_end->flags & EDGE_COMPLEX))
+ if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
return invalid_sese;
- /* Include the BB with the loop-closed SSA PHI nodes.
- canonicalize_loop_closed_ssa makes sure that is in proper shape. */
- if (! single_pred_p (scop_end->dest)
- || ! single_succ_p (scop_end->dest)
- || ! trivially_empty_bb_p (scop_end->dest))
- gcc_unreachable ();
- scop_end = single_succ_edge (scop_end->dest);
return sese_l (scop_begin, scop_end);
}
-/* Return the closest dominator with a single entry edge. */
-
-edge
-scop_detection::get_nearest_dom_with_single_entry (basic_block dom)
-{
- if (!dom->preds)
- return NULL;
-
- /* If any of the dominators has two predecessors but one of them is a back
- edge, then that basic block also qualifies as a dominator with single
- entry. */
- if (dom->preds->length () == 2)
- {
- /* If e1->src dominates e2->src then e1->src will also dominate dom. */
- edge e1 = (*dom->preds)[0];
- edge e2 = (*dom->preds)[1];
- loop_p l = dom->loop_father;
- loop_p l1 = e1->src->loop_father;
- loop_p l2 = e2->src->loop_father;
- if (l != l1 && l == l2
- && dominated_by_p (CDI_DOMINATORS, e2->src, e1->src))
- return e1;
- if (l != l2 && l == l1
- && dominated_by_p (CDI_DOMINATORS, e1->src, e2->src))
- return e2;
- }
-
- while (dom->preds->length () != 1)
- {
- if (dom->preds->length () < 1)
- return NULL;
- dom = get_immediate_dominator (CDI_DOMINATORS, dom);
- if (!dom->preds)
- return NULL;
- }
- return (*dom->preds)[0];
-}
-
-/* Return the closest post-dominator with a single exit edge. In case of a
- back-loop the back-edge is not counted. */
-
-edge
-scop_detection::get_nearest_pdom_with_single_exit (basic_block pdom)
-{
- if (!pdom->succs)
- return NULL;
-
- /* If any of the post-dominators has two successors but one of them is a back
- edge, then that basic block also qualifies as a post-dominator with single
- exit. */
- if (pdom->succs->length () == 2)
- {
- /* If e1->dest post-dominates e2->dest then e1->dest will also
- post-dominate pdom. */
- edge e1 = (*pdom->succs)[0];
- edge e2 = (*pdom->succs)[1];
- loop_p l = pdom->loop_father;
- loop_p l1 = e1->dest->loop_father;
- loop_p l2 = e2->dest->loop_father;
- if (l != l1 && l == l2
- && dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest))
- return e1;
- if (l != l2 && l == l1
- && dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest))
- return e2;
- }
-
- while (pdom->succs->length () != 1)
- {
- if (pdom->succs->length () < 1)
- return NULL;
- pdom = get_immediate_dominator (CDI_POST_DOMINATORS, pdom);
- if (!pdom->succs)
- return NULL;
- }
-
- return (*pdom->succs)[0];
-}
-
/* Merge scops at same loop depth and returns the new sese.
Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
dp << "[scop-detection] try merging sese s2: ";
print_sese (dump_file, second));
- /* Assumption: Both the sese's should be at the same loop depth or one scop
- should subsume the other like in case of nested loops. */
-
- /* Find the common dominators for entry,
- and common post-dominators for the exit. */
- basic_block dom = nearest_common_dominator (CDI_DOMINATORS,
- get_entry_bb (first),
- get_entry_bb (second));
-
- edge entry = get_nearest_dom_with_single_entry (dom);
-
- if (!entry || (entry->flags & EDGE_IRREDUCIBLE_LOOP))
- return invalid_sese;
-
- basic_block pdom = nearest_common_dominator (CDI_POST_DOMINATORS,
- get_exit_bb (first),
- get_exit_bb (second));
- pdom = nearest_common_dominator (CDI_POST_DOMINATORS, dom, pdom);
-
- edge exit = get_nearest_pdom_with_single_exit (pdom);
-
- if (!exit || (exit->flags & EDGE_IRREDUCIBLE_LOOP))
- return invalid_sese;
-
- sese_l combined (entry, exit);
-
- DEBUG_PRINT (dp << "[scop-detection] checking combined sese: ";
- print_sese (dump_file, combined));
-
- /* FIXME: We could iterate to find the dom which dominates pdom, and pdom
- which post-dominates dom, until it stabilizes. Also, ENTRY->SRC and
- EXIT->DEST should be in the same loop nest. */
- if (!dominated_by_p (CDI_DOMINATORS, pdom, dom)
- || loop_depth (entry->src->loop_father)
- != loop_depth (exit->dest->loop_father))
- return invalid_sese;
-
- /* For now we just bail out when there is a loop exit in the region
- that is not also the exit of the region. We could enlarge the
- region to cover the loop that region exits to. See PR79977. */
- if (loop_outer (entry->src->loop_father))
+ auto_bitmap worklist, in_sese_region;
+ bitmap_set_bit (worklist, get_entry_bb (first)->index);
+ bitmap_set_bit (worklist, get_exit_bb (first)->index);
+ bitmap_set_bit (worklist, get_entry_bb (second)->index);
+ bitmap_set_bit (worklist, get_exit_bb (second)->index);
+ edge entry = NULL, exit = NULL;
+
+ /* We can optimize the case of adding a loop entry dest or exit
+ src to the worklist (for single-exit loops) by skipping
+ directly to the exit dest / entry src. in_sese_region
+ doesn't have to cover all blocks in the region but merely
+ its border it acts more like a visited bitmap. */
+ do
{
- vec<edge> exits = get_loop_exit_edges (entry->src->loop_father);
- for (unsigned i = 0; i < exits.length (); ++i)
+ int index = bitmap_first_set_bit (worklist);
+ bitmap_clear_bit (worklist, index);
+ basic_block bb = BASIC_BLOCK_FOR_FN (cfun, index);
+ edge_iterator ei;
+ edge e;
+
+ /* With fake exit edges we can end up with no possible exit. */
+ if (index == EXIT_BLOCK)
{
- if (exits[i] != exit
- && bb_in_region (exits[i]->src, entry->dest, exit->src))
- {
- DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
- exits.release ();
- return invalid_sese;
- }
+ DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
+ return invalid_sese;
}
- exits.release ();
- }
- /* For now we just want to bail out when exit does not post-dominate entry.
- TODO: We might just add a basic_block at the exit to make exit
- post-dominate entry (the entire region). */
- if (!dominated_by_p (CDI_POST_DOMINATORS, get_entry_bb (combined),
- get_exit_bb (combined))
- || !dominated_by_p (CDI_DOMINATORS, get_exit_bb (combined),
- get_entry_bb (combined)))
- {
- DEBUG_PRINT (dp << "[scop-detection-fail] cannot merge seses.\n");
- return invalid_sese;
+ bitmap_set_bit (in_sese_region, bb->index);
+
+ basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ if (e->src == dom
+ && (! entry
+ || dominated_by_p (CDI_DOMINATORS, entry->dest, bb)))
+ {
+ if (entry
+ && ! bitmap_bit_p (in_sese_region, entry->src->index))
+ bitmap_set_bit (worklist, entry->src->index);
+ entry = e;
+ }
+ else if (! bitmap_bit_p (in_sese_region, e->src->index))
+ bitmap_set_bit (worklist, e->src->index);
+
+ basic_block pdom = get_immediate_dominator (CDI_POST_DOMINATORS, bb);
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (e->dest == pdom
+ && (! exit
+ || dominated_by_p (CDI_POST_DOMINATORS, exit->src, bb)))
+ {
+ if (exit
+ && ! bitmap_bit_p (in_sese_region, exit->dest->index))
+ bitmap_set_bit (worklist, exit->dest->index);
+ exit = e;
+ }
+ else if (! bitmap_bit_p (in_sese_region, e->dest->index))
+ bitmap_set_bit (worklist, e->dest->index);
}
+ while (! bitmap_empty_p (worklist));
+
+ sese_l combined (entry, exit);
DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
tree niter;
struct tree_niter_desc niter_desc;
- return single_exit (loop)
- && !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
+ /* We can only handle do {} while () style loops correctly. */
+ edge exit = single_exit (loop);
+ if (!exit
+ || !single_pred_p (loop->latch)
+ || exit->src != single_pred (loop->latch)
+ || !empty_block_p (loop->latch))
+ return false;
+
+ return !(loop_preheader_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)
&& number_of_iterations_exit (loop, single_exit (loop), &niter_desc, false)
&& niter_desc.control.no_overflow
&& (niter = number_of_latch_executions (loop))
&& !chrec_contains_undetermined (niter)
- && !chrec_contains_undetermined (scalar_evolution_in_region (scop,
- loop, niter))
&& graphite_can_represent_expr (scop, loop, niter);
}
{
gcc_assert (s);
+ /* If the exit edge is fake discard the SCoP for now as we're removing the
+ fake edges again after analysis. */
+ if (s.exit->flags & EDGE_FAKE)
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] Discarding infinite loop SCoP: ";
+ print_sese (dump_file, s));
+ return;
+ }
+
+ /* Include the BB with the loop-closed SSA PHI nodes, we need this
+ block in the region for code-generating out-of-SSA copies.
+ canonicalize_loop_closed_ssa makes sure that is in proper shape. */
+ if (s.exit->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
+ && loop_exit_edge_p (s.exit->src->loop_father, s.exit))
+ {
+ gcc_assert (single_pred_p (s.exit->dest)
+ && single_succ_p (s.exit->dest)
+ && sese_trivially_empty_bb_p (s.exit->dest));
+ s.exit = single_succ_edge (s.exit->dest);
+ }
+
/* Do not add scops with only one loop. */
if (region_has_one_loop (s))
{
DEBUG_PRINT (dp << "[scop-detection] Adding SCoP: "; print_sese (dump_file, s));
}
-/* Return true when a statement in SCOP cannot be represented by Graphite.
- The assumptions are that L1 dominates L2, and SCOP->entry dominates L1.
- Limit the number of bbs between adjacent loops to
- PARAM_SCOP_MAX_NUM_BBS_BETWEEN_LOOPS. */
+/* Return true when a statement in SCOP cannot be represented by Graphite. */
bool
scop_detection::harmful_loop_in_region (sese_l scop) const
if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
return true;
- if (bb != exit_bb)
- for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
- dom;
- dom = next_dom_son (CDI_DOMINATORS, dom))
+ for (basic_block dom = first_dom_son (CDI_DOMINATORS, bb);
+ dom;
+ dom = next_dom_son (CDI_DOMINATORS, dom))
+ if (dom != scop.exit->dest)
worklist.safe_push (dom);
}
return true;
}
- if (! loop_ivs_can_be_represented (loop))
- {
- DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
- << "IV cannot be represented.\n");
- return true;
- }
-
/* Check if all loop nests have at least one data reference.
??? This check is expensive and loops premature at this point.
If important to retain we can pre-compute this for all innermost
Something like "i * n" or "n * m" is not allowed. */
bool
-scop_detection::graphite_can_represent_scev (tree scev)
+scop_detection::graphite_can_represent_scev (sese_l scop, tree scev)
{
if (chrec_contains_undetermined (scev))
return false;
- /* We disable the handling of pointer types, because it’s currently not
- supported by Graphite with the isl AST generator. SSA_NAME nodes are
- the only nodes, which are disabled in case they are pointers to object
- types, but this can be changed. */
-
- if (POINTER_TYPE_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
- return false;
-
switch (TREE_CODE (scev))
{
case NEGATE_EXPR:
case BIT_NOT_EXPR:
CASE_CONVERT:
case NON_LVALUE_EXPR:
- return graphite_can_represent_scev (TREE_OPERAND (scev, 0));
+ return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0));
case PLUS_EXPR:
case POINTER_PLUS_EXPR:
case MINUS_EXPR:
- return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
- && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
+ return graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
+ && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
case MULT_EXPR:
return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
&& !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
&& chrec_contains_symbols (TREE_OPERAND (scev, 1)))
&& graphite_can_represent_init (scev)
- && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
- && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
+ && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 0))
+ && graphite_can_represent_scev (scop, TREE_OPERAND (scev, 1));
case POLYNOMIAL_CHREC:
/* Check for constant strides. With a non constant stride of
'n' we would have a value of 'iv * n'. Also check that the
initial value can represented: for example 'n * m' cannot be
represented. */
+ gcc_assert (loop_in_sese_p (get_loop (cfun,
+ CHREC_VARIABLE (scev)), scop));
if (!evolution_function_right_is_integer_cst (scev)
|| !graphite_can_represent_init (scev))
return false;
- return graphite_can_represent_scev (CHREC_LEFT (scev));
+ return graphite_can_represent_scev (scop, CHREC_LEFT (scev));
+
+ case ADDR_EXPR:
+ /* We cannot encode addresses for ISL. */
+ return false;
default:
break;
scop_detection::graphite_can_represent_expr (sese_l scop, loop_p loop,
tree expr)
{
- tree scev = scalar_evolution_in_region (scop, loop, expr);
- return graphite_can_represent_scev (scev);
+ tree scev = cached_scalar_evolution_in_region (scop, loop, expr);
+ return graphite_can_represent_scev (scop, scev);
}
/* Return true if the data references of STMT can be represented by Graphite.
bool
scop_detection::stmt_has_simple_data_refs_p (sese_l scop, gimple *stmt)
{
- loop_p nest = outermost_loop_in_sese (scop, gimple_bb (stmt));
+ edge nest = scop.entry;
loop_p loop = loop_containing_stmt (stmt);
if (!loop_in_sese_p (loop, scop))
- loop = nest;
+ loop = NULL;
auto_vec<data_reference_p> drs;
if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
FOR_EACH_VEC_ELT (drs, j, dr)
{
for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
- if (! graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
+ if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
return false;
}
tree op = gimple_op (stmt, i);
if (!graphite_can_represent_expr (scop, loop, op)
/* We can only constrain on integer type. */
- || (TREE_CODE (TREE_TYPE (op)) != INTEGER_TYPE))
+ || ! INTEGRAL_TYPE_P (TREE_TYPE (op)))
{
DEBUG_PRINT (dp << "[scop-detection-fail] "
<< "Graphite cannot represent stmt:\n";
case GIMPLE_ASSIGN:
case GIMPLE_CALL:
- return true;
+ {
+ tree op, lhs = gimple_get_lhs (stmt);
+ ssa_op_iter i;
+ /* If we are not going to instantiate the stmt do not require
+ its operands to be instantiatable at this point. */
+ if (lhs
+ && TREE_CODE (lhs) == SSA_NAME
+ && scev_analyzable_p (lhs, scop))
+ return true;
+ /* Verify that if we can analyze operands at their def site we
+ also can represent them when analyzed at their uses. */
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
+ if (scev_analyzable_p (op, scop)
+ && chrec_contains_undetermined
+ (cached_scalar_evolution_in_region (scop,
+ bb->loop_father, op)))
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] "
+ << "Graphite cannot code-gen stmt:\n";
+ print_gimple_stmt (dump_file, stmt, 0,
+ TDF_VOPS | TDF_MEMSYMS));
+ return false;
+ }
+ return true;
+ }
default:
/* These nodes cut a new scope. */
return res;
}
-/* When parameter NAME is in REGION, returns its index in SESE_PARAMS.
- Otherwise returns -1. */
+/* Assigns the parameter NAME an index in REGION. */
-static inline int
-parameter_index_in_region_1 (tree name, sese_info_p region)
+static void
+assign_parameter_index_in_region (tree name, sese_info_p region)
{
+ gcc_assert (TREE_CODE (name) == SSA_NAME
+ && ! defined_in_sese_p (name, region->region));
int i;
tree p;
-
- gcc_assert (TREE_CODE (name) == SSA_NAME);
-
FOR_EACH_VEC_ELT (region->params, i, p)
if (p == name)
- return i;
-
- return -1;
-}
-
-/* When the parameter NAME is in REGION, returns its index in
- SESE_PARAMS. Otherwise this function inserts NAME in SESE_PARAMS
- and returns the index of NAME. */
-
-static int
-parameter_index_in_region (tree name, sese_info_p region)
-{
- int i;
-
- gcc_assert (TREE_CODE (name) == SSA_NAME);
-
- /* Cannot constrain on anything else than INTEGER_TYPE parameters. */
- if (TREE_CODE (TREE_TYPE (name)) != INTEGER_TYPE)
- return -1;
-
- if (!invariant_in_sese_p_rec (name, region->region, NULL))
- return -1;
-
- i = parameter_index_in_region_1 (name, region);
- if (i != -1)
- return i;
+ return;
- i = region->params.length ();
region->params.safe_push (name);
- return i;
}
/* In the context of sese S, scan the expression E and translate it to
break;
case SSA_NAME:
- parameter_index_in_region (e, s);
+ assign_parameter_index_in_region (e, s);
break;
case INTEGER_CST:
/* Find parameters in conditional statements. */
gimple *stmt;
- loop_p loop = GBB_BB (gbb)->loop_father;
FOR_EACH_VEC_ELT (GBB_CONDITIONS (gbb), i, stmt)
{
- tree lhs = scalar_evolution_in_region (region->region, loop,
- gimple_cond_lhs (stmt));
- tree rhs = scalar_evolution_in_region (region->region, loop,
- gimple_cond_rhs (stmt));
+ loop_p loop = gimple_bb (stmt)->loop_father;
+ tree lhs = cached_scalar_evolution_in_region (region->region, loop,
+ gimple_cond_lhs (stmt));
+ tree rhs = cached_scalar_evolution_in_region (region->region, loop,
+ gimple_cond_rhs (stmt));
+ gcc_assert (!chrec_contains_undetermined (lhs)
+ && !chrec_contains_undetermined (rhs));
scan_tree_for_params (region, lhs);
scan_tree_for_params (region, rhs);
}
}
-/* Record the parameters used in the SCOP. A variable is a parameter
+/* Record the parameters used in the SCOP BBs. A variable is a parameter
in a scop if it does not vary during the execution of that scop. */
static void
{
unsigned i;
sese_info_p region = scop->scop_info;
- struct loop *loop;
-
- /* Find the parameters used in the loop bounds. */
- FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
- {
- tree nb_iters = number_of_latch_executions (loop);
- if (!chrec_contains_symbols (nb_iters))
- continue;
-
- nb_iters = scalar_evolution_in_region (region->region, loop, nb_iters);
- scan_tree_for_params (region, nb_iters);
- }
+ /* Parameters used in loop bounds are processed during gather_bbs. */
/* Find the parameters used in data accesses. */
poly_bb_p pbb;
scop_set_nb_params (scop, nbp);
}
+static void
+add_write (vec<tree> *writes, tree def)
+{
+ writes->safe_push (def);
+ DEBUG_PRINT (dp << "Adding scalar write: ";
+ print_generic_expr (dump_file, def);
+ dp << "\nFrom stmt: ";
+ print_gimple_stmt (dump_file,
+ SSA_NAME_DEF_STMT (def), 0));
+}
+
+static void
+add_read (vec<scalar_use> *reads, tree use, gimple *use_stmt)
+{
+ DEBUG_PRINT (dp << "Adding scalar read: ";
+ print_generic_expr (dump_file, use);
+ dp << "\nFrom stmt: ";
+ print_gimple_stmt (dump_file, use_stmt, 0));
+ reads->safe_push (std::make_pair (use_stmt, use));
+}
+
+
/* Record DEF if it is used in other bbs different than DEF_BB in the SCOP. */
static void
build_cross_bb_scalars_def (scop_p scop, tree def, basic_block def_bb,
vec<tree> *writes)
{
- if (!def || !is_gimple_reg (def))
+ if (!is_gimple_reg (def))
return;
bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
/* But gather SESE liveouts as we otherwise fail to rewrite their
exit PHIs. */
|| ! bb_in_sese_p (gimple_bb (use_stmt), scop->scop_info->region))
- && ((def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))
- /* PHIs have their effect at "BBs" on the edges. See PR79622. */
- || gimple_code (SSA_NAME_DEF_STMT (def)) == GIMPLE_PHI))
+ && (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt)))
{
- writes->safe_push (def);
- DEBUG_PRINT (dp << "Adding scalar write: ";
- print_generic_expr (dump_file, def);
- dp << "\nFrom stmt: ";
- print_gimple_stmt (dump_file,
- SSA_NAME_DEF_STMT (def), 0));
- /* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
- before all the uses have been visited. */
- BREAK_FROM_IMM_USE_STMT (imm_iter);
+ add_write (writes, def);
+ break;
}
}
build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
vec<scalar_use> *reads)
{
- gcc_assert (use);
if (!is_gimple_reg (use))
return;
return;
gimple *def_stmt = SSA_NAME_DEF_STMT (use);
- if (gimple_bb (def_stmt) != gimple_bb (use_stmt)
- /* PHIs have their effect at "BBs" on the edges. See PR79622. */
- || gimple_code (def_stmt) == GIMPLE_PHI)
- {
- DEBUG_PRINT (dp << "Adding scalar read: ";
- print_generic_expr (dump_file, use);
- dp << "\nFrom stmt: ";
- print_gimple_stmt (dump_file, use_stmt, 0));
- reads->safe_push (std::make_pair (use_stmt, use));
- }
-}
-
-/* Record all scalar variables that are defined and used in different BBs of the
- SCOP. */
-
-static void
-graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt,
- vec<scalar_use> *reads, vec<tree> *writes)
-{
- tree def;
-
- if (gimple_code (stmt) == GIMPLE_ASSIGN)
- def = gimple_assign_lhs (stmt);
- else if (gimple_code (stmt) == GIMPLE_CALL)
- def = gimple_call_lhs (stmt);
- else if (gimple_code (stmt) == GIMPLE_PHI)
- def = gimple_phi_result (stmt);
- else
- return;
-
-
- build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes);
-
- ssa_op_iter iter;
- use_operand_p use_p;
- FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
- {
- tree use = USE_FROM_PTR (use_p);
- build_cross_bb_scalars_use (scop, use, stmt, reads);
- }
+ if (gimple_bb (def_stmt) != gimple_bb (use_stmt))
+ add_read (reads, use, use_stmt);
}
/* Generates a polyhedral black box only if the bb contains interesting
vec<scalar_use> reads = vNULL;
sese_l region = scop->scop_info->region;
- loop_p nest = outermost_loop_in_sese (region, bb);
-
+ edge nest = region.entry;
loop_p loop = bb->loop_father;
if (!loop_in_sese_p (loop, region))
- loop = nest;
+ loop = NULL;
for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
gsi_next (&gsi))
continue;
graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
- graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes);
+
+ tree def = gimple_get_lhs (stmt);
+ if (def)
+ build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), &writes);
+
+ ssa_op_iter iter;
+ tree use;
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
+ build_cross_bb_scalars_use (scop, use, stmt, &reads);
}
+ /* Handle defs and uses in PHIs. Those need special treatment given
+ that we have to present ISL with sth that looks like we've rewritten
+ the IL out-of-SSA. */
for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
gsi_next (&psi))
- if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
- graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes);
+ {
+ gphi *phi = psi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res)
+ || scev_analyzable_p (res, scop->scop_info->region))
+ continue;
+ /* To simulate out-of-SSA the block containing the PHI node has
+ reads of the PHI destination. And to preserve SSA dependences
+ we also write to it (the out-of-SSA decl and the SSA result
+ are coalesced for dependence purposes which is good enough). */
+ add_read (&reads, res, phi);
+ add_write (&writes, res);
+ }
+ basic_block bb_for_succs = bb;
+ if (bb_for_succs == bb_for_succs->loop_father->latch
+ && bb_in_sese_p (bb_for_succs, scop->scop_info->region)
+ && sese_trivially_empty_bb_p (bb_for_succs))
+ bb_for_succs = NULL;
+ while (bb_for_succs)
+ {
+ basic_block latch = NULL;
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb_for_succs->succs)
+ {
+ for (gphi_iterator psi = gsi_start_phis (e->dest); !gsi_end_p (psi);
+ gsi_next (&psi))
+ {
+ gphi *phi = psi.phi ();
+ tree res = gimple_phi_result (phi);
+ if (virtual_operand_p (res))
+ continue;
+ /* To simulate out-of-SSA the predecessor of edges into PHI nodes
+ has a copy from the PHI argument to the PHI destination. */
+ if (! scev_analyzable_p (res, scop->scop_info->region))
+ add_write (&writes, res);
+ tree use = PHI_ARG_DEF_FROM_EDGE (phi, e);
+ if (TREE_CODE (use) == SSA_NAME
+ && ! SSA_NAME_IS_DEFAULT_DEF (use)
+ && gimple_bb (SSA_NAME_DEF_STMT (use)) != bb_for_succs
+ && ! scev_analyzable_p (use, scop->scop_info->region))
+ add_read (&reads, use, phi);
+ }
+ if (e->dest == bb_for_succs->loop_father->latch
+ && bb_in_sese_p (e->dest, scop->scop_info->region)
+ && sese_trivially_empty_bb_p (e->dest))
+ latch = e->dest;
+ }
+ /* Handle empty latch block PHIs here, otherwise we confuse ISL
+ with extra conditional code where it then peels off the last
+ iteration just because of that. It would be simplest if we
+ just didn't force simple latches (thus remove the forwarder). */
+ bb_for_succs = latch;
+ }
+
+ /* For the region exit block add reads for all live-out vars. */
+ if (bb == scop->scop_info->region.exit->src)
+ {
+ sese_build_liveouts (scop->scop_info);
+ unsigned i;
+ bitmap_iterator bi;
+ EXECUTE_IF_SET_IN_BITMAP (scop->scop_info->liveout, 0, i, bi)
+ {
+ tree use = ssa_name (i);
+ add_read (&reads, use, NULL);
+ }
+ }
if (drs.is_empty () && writes.is_empty () && reads.is_empty ())
return NULL;
int i, j;
int *all_vertices;
+ struct loop *nest
+ = find_common_loop (scop->scop_info->region.entry->dest->loop_father,
+ scop->scop_info->region.exit->src->loop_father);
+
FOR_EACH_VEC_ELT (scop->drs, i, dr1)
for (j = i+1; scop->drs.iterate (j, &dr2); j++)
- if (dr_may_alias_p (dr1->dr, dr2->dr, true))
+ if (dr_may_alias_p (dr1->dr, dr2->dr, nest))
{
/* Dependences in the same alias set need to be handled
by just looking at DR_ACCESS_FNs. */
for (i = 0; i < num_vertices; i++)
all_vertices[i] = i;
- graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
+ scop->max_alias_set
+ = graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL) + 1;
free (all_vertices);
for (i = 0; i < g->n_vertices; i++)
};
}
gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
- : dom_walker (direction, false, bb_to_rpo), scop (scop)
+ : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
{
}
-/* Record in execution order the loops fully contained in the region. */
-
-static void
-record_loop_in_sese (basic_block bb, sese_info_p region)
-{
- loop_p father = bb->loop_father;
- if (loop_in_sese_p (father, region->region))
- {
- bool found = false;
- loop_p loop0;
- int j;
- FOR_EACH_VEC_ELT (region->loop_nest, j, loop0)
- if (father == loop0)
- {
- found = true;
- break;
- }
- if (!found)
- region->loop_nest.safe_push (father);
- }
-}
-
/* Call-back for dom_walk executed before visiting the dominated
blocks. */
if (!bb_in_sese_p (bb, region->region))
return dom_walker::STOP;
- record_loop_in_sese (bb, region);
-
- gcond *stmt = single_pred_cond_non_loop_exit (bb);
+ /* For loops fully contained in the region record parameters in the
+ loop bounds. */
+ loop_p loop = bb->loop_father;
+ if (loop->header == bb
+ && loop_in_sese_p (loop, region->region))
+ {
+ tree nb_iters = number_of_latch_executions (loop);
+ if (chrec_contains_symbols (nb_iters))
+ {
+ nb_iters = cached_scalar_evolution_in_region (region->region,
+ loop, nb_iters);
+ scan_tree_for_params (region, nb_iters);
+ }
+ }
- if (stmt)
+ if (gcond *stmt = single_pred_cond_non_loop_exit (bb))
{
edge e = single_pred_edge (bb);
-
- conditions.safe_push (stmt);
-
- if (e->flags & EDGE_TRUE_VALUE)
- cases.safe_push (stmt);
- else
- cases.safe_push (NULL);
+ /* Make sure the condition is in the region and thus was verified
+ to be handled. */
+ if (e != region->region.entry)
+ {
+ conditions.safe_push (stmt);
+ if (e->flags & EDGE_TRUE_VALUE)
+ cases.safe_push (stmt);
+ else
+ cases.safe_push (NULL);
+ }
}
scop->scop_info->bbs.safe_push (bb);
if (single_pred_cond_non_loop_exit (bb))
{
- conditions.pop ();
- cases.pop ();
+ edge e = single_pred_edge (bb);
+ if (e != scop->scop_info->region.entry)
+ {
+ conditions.pop ();
+ cases.pop ();
+ }
}
}
/* Compute sth like an execution order, dominator order with first executing
edges that stay inside the current loop, delaying processing exit edges. */
-static vec<unsigned> order;
-
-static void
-get_order (scop_p scop, basic_block bb, vec<unsigned> *order, unsigned *dfs_num)
-{
- if (! bb_in_sese_p (bb, scop->scop_info->region))
- return;
-
- (*order)[bb->index] = (*dfs_num)++;
- for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
- son;
- son = next_dom_son (CDI_DOMINATORS, son))
- if (flow_bb_inside_loop_p (bb->loop_father, son))
- get_order (scop, son, order, dfs_num);
- for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
- son;
- son = next_dom_son (CDI_DOMINATORS, son))
- if (! flow_bb_inside_loop_p (bb->loop_father, son))
- get_order (scop, son, order, dfs_num);
-}
+static int *bb_to_rpo;
/* Helper for qsort, sorting after order above. */
{
poly_bb_p bb1 = *((const poly_bb_p *)pa);
poly_bb_p bb2 = *((const poly_bb_p *)pb);
- if (order[bb1->black_box->bb->index] < order[bb2->black_box->bb->index])
+ if (bb_to_rpo[bb1->black_box->bb->index]
+ < bb_to_rpo[bb2->black_box->bb->index])
return -1;
- else if (order[bb1->black_box->bb->index] > order[bb2->black_box->bb->index])
+ else if (bb_to_rpo[bb1->black_box->bb->index]
+ > bb_to_rpo[bb2->black_box->bb->index])
return 1;
else
return 0;
/* Domwalk needs a bb to RPO mapping. Compute it once here. */
int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
int postorder_num = pre_and_rev_post_order_compute (NULL, postorder, true);
- int *bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
+ bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
for (int i = 0; i < postorder_num; ++i)
bb_to_rpo[postorder[i]] = i;
free (postorder);
/* Record all basic blocks and their conditions in REGION. */
gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
- /* domwalk does not fulfil our code-generations constraints on the
- order of pbb which is to produce sth like execution order, delaying
- exection of loop exit edges. So compute such order and sort after
- that. */
- order.create (last_basic_block_for_fn (cfun));
- order.quick_grow (last_basic_block_for_fn (cfun));
- unsigned dfs_num = 0;
- get_order (scop, s->entry->dest, &order, &dfs_num);
+ /* Sort pbbs after execution order for initial schedule generation. */
scop->pbbs.qsort (cmp_pbbs);
- order.release ();
if (! build_alias_set (scop))
{
continue;
}
- unsigned max_arrays = PARAM_VALUE (PARAM_GRAPHITE_MAX_ARRAYS_PER_SCOP);
- if (scop->drs.length () >= max_arrays)
+ unsigned max_arrays = param_graphite_max_arrays_per_scop;
+ if (max_arrays > 0
+ && scop->drs.length () >= max_arrays)
{
DEBUG_PRINT (dp << "[scop-detection-fail] too many data references: "
<< scop->drs.length ()
}
find_scop_parameters (scop);
- graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
+ graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
if (max_dim > 0
&& scop_nb_params (scop) > max_dim)
{
}
free (bb_to_rpo);
+ bb_to_rpo = NULL;
DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
}
projects / thirdparty / gcc.git / blobdiff