/* Detection of Static Control Parts (SCoP) for Graphite.
- Copyright (C) 2009 Free Software Foundation, Inc.
+ Copyright (C) 2009, 2010 Free Software Foundation, Inc.
Contributed by Sebastian Pop <sebastian.pop@amd.com> and
Tobias Grosser <grosser@fim.uni-passau.de>.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "tree.h"
-#include "rtl.h"
-#include "basic-block.h"
-#include "diagnostic.h"
#include "tree-flow.h"
-#include "toplev.h"
-#include "tree-dump.h"
-#include "timevar.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
-#include "domwalk.h"
-#include "value-prof.h"
-#include "pointer-set.h"
-#include "gimple.h"
#include "sese.h"
#ifdef HAVE_cloog
-#include "cloog/cloog.h"
#include "ppl_c.h"
#include "graphite-ppl.h"
-#include "graphite.h"
#include "graphite-poly.h"
#include "graphite-scop-detection.h"
+/* Forward declarations. */
+static void make_close_phi_nodes_unique (basic_block);
+
/* The type of the analyzed basic block. */
typedef enum gbb_type {
sd_region *s;
int i;
- for (i = 0; VEC_iterate (sd_region, *source, i, s); i++)
+ FOR_EACH_VEC_ELT (sd_region, *source, i, s)
VEC_safe_push (sd_region, heap, *target, s);
VEC_free (sd_region, heap, *source);
1 i + 20 j + (-2) m + 25
- Something like "i * n" or "n * m" is not allowed.
-
- OUTERMOST_LOOP defines the outermost loop that can variate. */
+ Something like "i * n" or "n * m" is not allowed. */
static bool
-graphite_can_represent_scev (tree scev, int outermost_loop)
+graphite_can_represent_scev (tree scev)
{
if (chrec_contains_undetermined (scev))
return false;
{
case PLUS_EXPR:
case MINUS_EXPR:
- return graphite_can_represent_scev (TREE_OPERAND (scev, 0), outermost_loop)
- && graphite_can_represent_scev (TREE_OPERAND (scev, 1), outermost_loop);
+ return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
+ && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
case MULT_EXPR:
return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
&& !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
&& !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
&& chrec_contains_symbols (TREE_OPERAND (scev, 1)))
- && graphite_can_represent_scev (TREE_OPERAND (scev, 0), outermost_loop)
- && graphite_can_represent_scev (TREE_OPERAND (scev, 1), outermost_loop);
+ && graphite_can_represent_init (scev)
+ && graphite_can_represent_scev (TREE_OPERAND (scev, 0))
+ && graphite_can_represent_scev (TREE_OPERAND (scev, 1));
case POLYNOMIAL_CHREC:
/* Check for constant strides. With a non constant stride of
if (!scev_is_linear_expression (scev))
return false;
- return evolution_function_is_invariant_p (scev, outermost_loop)
- || evolution_function_is_affine_multivariate_p (scev, outermost_loop);
+ return true;
}
This means an expression can be represented, if it is linear with
respect to the loops and the strides are non parametric.
- LOOP is the place where the expr will be evaluated and OUTERMOST_LOOP
- defindes the outermost loop that can variate. SCOP_ENTRY defines the
+ LOOP is the place where the expr will be evaluated. SCOP_ENTRY defines the
entry of the region we analyse. */
static bool
graphite_can_represent_expr (basic_block scop_entry, loop_p loop,
- loop_p outermost_loop, tree expr)
+ tree expr)
{
tree scev = analyze_scalar_evolution (loop, expr);
scev = instantiate_scev (scop_entry, loop, scev);
- return graphite_can_represent_scev (scev, outermost_loop->num);
+ return graphite_can_represent_scev (scev);
}
/* Return true if the data references of STMT can be represented by
Graphite. */
static bool
-stmt_has_simple_data_refs_p (loop_p outermost_loop, gimple stmt)
+stmt_has_simple_data_refs_p (loop_p outermost_loop ATTRIBUTE_UNUSED,
+ gimple stmt)
{
data_reference_p dr;
unsigned i;
int j;
bool res = true;
- int loop = outermost_loop->num;
- VEC (data_reference_p, heap) *drs = VEC_alloc (data_reference_p, heap, 5);
+ VEC (data_reference_p, heap) *drs = NULL;
+ loop_p outer;
- graphite_find_data_references_in_stmt (outermost_loop, stmt, &drs);
+ for (outer = loop_containing_stmt (stmt); outer; outer = loop_outer (outer))
+ {
+ graphite_find_data_references_in_stmt (outer,
+ loop_containing_stmt (stmt),
+ stmt, &drs);
- for (j = 0; VEC_iterate (data_reference_p, drs, j, dr); j++)
- for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
- if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i), loop))
- {
- res = false;
- goto done;
- }
+ FOR_EACH_VEC_ELT (data_reference_p, drs, j, dr)
+ for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
+ if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i)))
+ {
+ res = false;
+ goto done;
+ }
+
+ free_data_refs (drs);
+ drs = NULL;
+ }
done:
free_data_refs (drs);
return res;
}
-/* Return false if the TREE_CODE of the operand OP or any of its operands
- is a COMPONENT_REF. */
-
-static bool
-exclude_component_ref (tree op)
-{
- int i;
- int len;
-
- if (!op)
- return true;
-
- if (TREE_CODE (op) == COMPONENT_REF)
- return false;
-
- len = TREE_OPERAND_LENGTH (op);
- for (i = 0; i < len; ++i)
- if (!exclude_component_ref (TREE_OPERAND (op, i)))
- return false;
-
- return true;
-}
-
-/* Return true if the operand OP used in STMT is simple in regards to
- OUTERMOST_LOOP. */
-
-static inline bool
-is_simple_operand (tree op)
-{
- /* It is not a simple operand when it is a declaration or a
- structure. */
- return !DECL_P (op) && !AGGREGATE_TYPE_P (TREE_TYPE (op))
- && exclude_component_ref (op);
-}
-
/* Return true only when STMT is simple enough for being handled by
Graphite. This depends on SCOP_ENTRY, as the parameters are
initialized relatively to this basic block, the linear functions
return false;
FOR_EACH_SSA_TREE_OPERAND (op, stmt, op_iter, SSA_OP_ALL_USES)
- if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop,
- op)
+ if (!graphite_can_represent_expr (scop_entry, loop, op)
/* We can not handle REAL_TYPE. Failed for pr39260. */
|| TREE_CODE (TREE_TYPE (op)) == REAL_TYPE)
return false;
}
case GIMPLE_ASSIGN:
- {
- enum tree_code code = gimple_assign_rhs_code (stmt);
-
- switch (get_gimple_rhs_class (code))
- {
- case GIMPLE_UNARY_RHS:
- case GIMPLE_SINGLE_RHS:
- return (is_simple_operand (gimple_assign_lhs (stmt))
- && is_simple_operand (gimple_assign_rhs1 (stmt)));
-
- case GIMPLE_BINARY_RHS:
- return (is_simple_operand (gimple_assign_lhs (stmt))
- && is_simple_operand (gimple_assign_rhs1 (stmt))
- && is_simple_operand (gimple_assign_rhs2 (stmt)));
-
- case GIMPLE_INVALID_RHS:
- default:
- gcc_unreachable ();
- }
- }
-
case GIMPLE_CALL:
- {
- size_t i;
- size_t n = gimple_call_num_args (stmt);
- tree lhs = gimple_call_lhs (stmt);
-
- if (lhs && !is_simple_operand (lhs))
- return false;
-
- for (i = 0; i < n; i++)
- if (!is_simple_operand (gimple_call_arg (stmt, i)))
- return false;
-
- return true;
- }
+ return true;
default:
/* These nodes cut a new scope. */
return NULL;
}
-/* Return true when it is not possible to represent LOOP in the
- polyhedral representation. This is evaluated taking SCOP_ENTRY and
+/* Return true if LOOP can be represented in the polyhedral
+ representation. This is evaluated taking SCOP_ENTRY and
OUTERMOST_LOOP in mind. */
static bool
-graphite_can_represent_loop (basic_block scop_entry, loop_p outermost_loop,
- loop_p loop)
+graphite_can_represent_loop (basic_block scop_entry, loop_p loop)
{
- tree niter = number_of_latch_executions (loop);
+ tree niter;
+ struct tree_niter_desc niter_desc;
- /* Number of iterations unknown. */
- if (chrec_contains_undetermined (niter))
- return false;
+ /* FIXME: For the moment, graphite cannot be used on loops that
+ iterate using induction variables that wrap. */
- /* Number of iterations not affine. */
- if (!graphite_can_represent_expr (scop_entry, loop, outermost_loop, niter))
- return false;
-
- return true;
+ return 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)
+ && graphite_can_represent_expr (scop_entry, loop, niter);
}
/* Store information needed by scopdet_* functions. */
sinfo = build_scops_1 (bb, outermost_loop, ®ions, loop);
- if (!graphite_can_represent_loop (entry_block, outermost_loop, loop))
+ if (!graphite_can_represent_loop (entry_block, loop))
result.difficult = true;
result.difficult |= sinfo.difficult;
- The exit destinations are dominated by another bb inside
the loop.
- The loop dominates bbs, that are not exit destinations. */
- for (i = 0; VEC_iterate (edge, exits, i, e); i++)
+ FOR_EACH_VEC_ELT (edge, exits, i, e)
if (e->src->loop_father == loop
&& dominated_by_p (CDI_DOMINATORS, e->dest, e->src))
{
/* First check the successors of BB, and check if it is
possible to join the different branches. */
- for (i = 0; VEC_iterate (edge, bb->succs, i, e); i++)
+ FOR_EACH_VEC_ELT (edge, bb->succs, i, e)
{
/* Ignore loop exits. They will be handled after the loop
body. */
- if (is_loop_exit (loop, e->dest))
+ if (loop_exits_to_bb_p (loop, e->dest))
{
result.exits = true;
continue;
/* Scan remaining bbs dominated by BB. */
dominated = get_dominated_by (CDI_DOMINATORS, bb);
- for (i = 0; VEC_iterate (basic_block, dominated, i, dom_bb); i++)
+ FOR_EACH_VEC_ELT (basic_block, dominated, i, dom_bb)
{
/* Ignore loop exits: they will be handled after the loop body. */
if (loop_depth (find_common_loop (loop, dom_bb->loop_father))
single edge pointing from outside into the loop. */
gcc_unreachable ();
-#ifdef ENABLE_CHECKING
- gcc_assert (find_single_entry_edge (region));
-#endif
+ gcc_checking_assert (find_single_entry_edge (region));
}
/* Check if the sd_region, mentioned in EDGE, has no exit bb. */
edge forwarder = NULL;
basic_block exit;
- if (find_single_exit_edge (region))
- return;
-
/* We create a forwarder bb (5) for all edges leaving this region
(3->5, 4->5). All other edges leading to the same bb, are moved
to a new bb (6). If these edges where part of another region (2->5)
if (e->aux)
((sd_region *) e->aux)->exit = forwarder->dest;
-#ifdef ENABLE_CHECKING
- gcc_assert (find_single_exit_edge (region));
-#endif
+ gcc_checking_assert (find_single_exit_edge (region));
}
/* Unmark the exit edges of all REGIONS.
edge e;
edge_iterator ei;
- for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+ FOR_EACH_VEC_ELT (sd_region, regions, i, s)
FOR_EACH_EDGE (e, ei, s->exit->preds)
e->aux = NULL;
}
edge e;
edge_iterator ei;
- for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+ FOR_EACH_VEC_ELT (sd_region, regions, i, s)
FOR_EACH_EDGE (e, ei, s->exit->preds)
if (bb_in_sd_region (e->src, s))
e->aux = s;
int i;
sd_region *s;
- for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+ FOR_EACH_VEC_ELT (sd_region, regions, i, s)
create_single_entry_edge (s);
mark_exit_edges (regions);
- for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
- create_single_exit_edge (s);
+ FOR_EACH_VEC_ELT (sd_region, regions, i, s)
+ /* Don't handle multiple edges exiting the function. */
+ if (!find_single_exit_edge (s)
+ && s->exit != EXIT_BLOCK_PTR)
+ create_single_exit_edge (s);
unmark_exit_edges (regions);
int i;
sd_region *s;
- for (i = 0; VEC_iterate (sd_region, regions, i, s); i++)
+ FOR_EACH_VEC_ELT (sd_region, regions, i, s)
{
edge entry = find_single_entry_edge (s);
edge exit = find_single_exit_edge (s);
- scop_p scop = new_scop (new_sese (entry, exit));
+ scop_p scop;
+
+ if (!exit)
+ continue;
+
+ scop = new_scop (new_sese (entry, exit));
VEC_safe_push (scop_p, heap, *scops, scop);
/* Are there overlapping SCoPs? */
int j;
sd_region *s2;
- for (j = 0; VEC_iterate (sd_region, regions, j, s2); j++)
+ FOR_EACH_VEC_ELT (sd_region, regions, j, s2)
if (s != s2)
gcc_assert (!bb_in_sd_region (s->entry, s2));
}
int i;
scop_p scop;
- for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
+ FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
print_graphite_scop_statistics (file, scop);
}
int i;
scop_p scop;
- for (i = 0; VEC_iterate (scop_p, *scops, i, scop); i++)
+ FOR_EACH_VEC_ELT (scop_p, *scops, i, scop)
{
int j;
loop_p loop;
sese region = SCOP_REGION (scop);
build_sese_loop_nests (region);
- for (j = 0; VEC_iterate (loop_p, SESE_LOOP_NEST (region), j, loop); j++)
+ FOR_EACH_VEC_ELT (loop_p, SESE_LOOP_NEST (region), j, loop)
if (!loop_in_sese_p (loop_outer (loop), region)
&& single_exit (loop))
{
VEC_free (sd_region, heap, regions);
}
+/* Returns true when P1 and P2 are close phis with the same
+ argument. */
+
+static inline bool
+same_close_phi_node (gimple p1, gimple p2)
+{
+ return operand_equal_p (gimple_phi_arg_def (p1, 0),
+ gimple_phi_arg_def (p2, 0), 0);
+}
+
+/* Remove the close phi node at GSI and replace its rhs with the rhs
+ of PHI. */
+
+static void
+remove_duplicate_close_phi (gimple phi, gimple_stmt_iterator *gsi)
+{
+ gimple use_stmt;
+ use_operand_p use_p;
+ imm_use_iterator imm_iter;
+ tree res = gimple_phi_result (phi);
+ tree def = gimple_phi_result (gsi_stmt (*gsi));
+
+ gcc_assert (same_close_phi_node (phi, gsi_stmt (*gsi)));
+
+ FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
+ {
+ FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
+ SET_USE (use_p, res);
+
+ update_stmt (use_stmt);
+
+ /* It is possible that we just created a duplicate close-phi
+ for an already-processed containing loop. Check for this
+ case and clean it up. */
+ if (gimple_code (use_stmt) == GIMPLE_PHI
+ && gimple_phi_num_args (use_stmt) == 1)
+ make_close_phi_nodes_unique (gimple_bb (use_stmt));
+ }
+
+ remove_phi_node (gsi, true);
+}
+
+/* Removes all the close phi duplicates from BB. */
+
+static void
+make_close_phi_nodes_unique (basic_block bb)
+{
+ gimple_stmt_iterator psi;
+
+ for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
+ {
+ gimple_stmt_iterator gsi = psi;
+ gimple phi = gsi_stmt (psi);
+
+ /* At this point, PHI should be a close phi in normal form. */
+ gcc_assert (gimple_phi_num_args (phi) == 1);
+
+ /* Iterate over the next phis and remove duplicates. */
+ gsi_next (&gsi);
+ while (!gsi_end_p (gsi))
+ if (same_close_phi_node (phi, gsi_stmt (gsi)))
+ remove_duplicate_close_phi (phi, &gsi);
+ else
+ gsi_next (&gsi);
+ }
+}
+
/* Transforms LOOP to the canonical loop closed SSA form. */
static void
bb = e->dest;
if (VEC_length (edge, bb->preds) == 1)
- split_block_after_labels (bb);
+ {
+ e = split_block_after_labels (bb);
+ make_close_phi_nodes_unique (e->src);
+ }
else
{
gimple_stmt_iterator psi;
update_stmt (phi);
}
}
+
+ make_close_phi_nodes_unique (close);
}
+
+ /* The code above does not properly handle changes in the post dominance
+ information (yet). */
+ free_dominance_info (CDI_POST_DOMINATORS);
}
/* Converts the current loop closed SSA form to a canonical form
- the basic block containing the close phi nodes does not contain
other statements.
+
+ - there exist only one phi node per definition in the loop.
*/
static void
loop_p loop;
#ifdef ENABLE_CHECKING
- verify_loop_closed_ssa ();
+ verify_loop_closed_ssa (true);
#endif
FOR_EACH_LOOP (li, loop, 0)
update_ssa (TODO_update_ssa);
#ifdef ENABLE_CHECKING
- verify_loop_closed_ssa ();
+ verify_loop_closed_ssa (true);
#endif
}
canonicalize_loop_closed_ssa_form ();
build_scops_1 (single_succ (ENTRY_BLOCK_PTR), ENTRY_BLOCK_PTR->loop_father,
- ®ions, loop);
+ ®ions, loop);
create_sese_edges (regions);
build_graphite_scops (regions, scops);
fprintf (file, "CELLSPACING=\"0\">\n");
/* Select color for SCoP. */
- for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++)
+ FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
{
sese region = SCOP_REGION (scop);
if (bb_in_sese_p (bb, region)
/* Display all SCoPs using dotty. */
-void
+DEBUG_FUNCTION void
dot_all_scops (VEC (scop_p, heap) *scops)
{
/* When debugging, enable the following code. This cannot be used
dot_all_scops_1 (stream, scops);
fclose (stream);
- x = system ("dotty /tmp/allscops.dot");
+ x = system ("dotty /tmp/allscops.dot &");
#else
dot_all_scops_1 (stderr, scops);
#endif
/* Display all SCoPs using dotty. */
-void
+DEBUG_FUNCTION void
dot_scop (scop_p scop)
{
VEC (scop_p, heap) *scops = NULL;
dot_all_scops_1 (stream, scops);
fclose (stream);
- x = system ("dotty /tmp/allscops.dot");
+ x = system ("dotty /tmp/allscops.dot &");
}
#else
dot_all_scops_1 (stderr, scops);
OSDN Git Service
