/* Detection of Static Control Parts (SCoP) for Graphite.
- Copyright (C) 2009-2015 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 INCLUDE_ISL
+
#include "config.h"
#ifdef HAVE_isl
-/* Workaround for GMP 5.1.3 bug, see PR56019. */
-#include <stddef.h>
-
-#include <isl/constraint.h>
-#include <isl/set.h>
-#include <isl/map.h>
-#include <isl/union_map.h>
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "cfghooks.h"
#include "domwalk.h"
-#include "params.h"
#include "tree.h"
#include "gimple.h"
#include "ssa.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
-#include "graphite-poly.h"
#include "tree-ssa-propagate.h"
-#include "graphite-scop-detection.h"
#include "gimple-pretty-print.h"
+#include "cfganal.h"
+#include "graphite.h"
class debug_printer
{
#define DEBUG_PRINT(args) do \
{ \
if (dump_file && (dump_flags & TDF_DETAILS)) { args; } \
- } while (0);
-
-
-/* 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)
- return false;
-
- return true;
-}
-
-/* Returns true when P1 and P2 are close phis with the same
- argument. */
-
-static inline bool
-same_close_phi_node (gphi *p1, gphi *p2)
-{
- return operand_equal_p (gimple_phi_arg_def (p1, 0),
- gimple_phi_arg_def (p2, 0), 0);
-}
+ } while (0)
-static void make_close_phi_nodes_unique (basic_block bb);
+/* Pretty print to FILE all the SCoPs in DOT format and mark them with
+ different colors. If there are not enough colors, paint the
+ remaining SCoPs in gray.
-/* Remove the close phi node at GSI and replace its rhs with the rhs
- of PHI. */
+ Special nodes:
+ - "*" after the node number denotes the entry of a SCoP,
+ - "#" after the node number denotes the exit of a SCoP,
+ - "()" around the node number denotes the entry or the
+ exit nodes of the SCOP. These are not part of SCoP. */
-static void
-remove_duplicate_close_phi (gphi *phi, gphi_iterator *gsi)
+DEBUG_FUNCTION void
+dot_all_sese (FILE *file, vec<sese_l>& scops)
{
- 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->phi ());
-
- gcc_assert (same_close_phi_node (phi, gsi->phi ()));
-
- 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. */
+ /* Disable debugging while printing graph. */
+ dump_flags_t tmp_dump_flags = dump_flags;
+ dump_flags = TDF_NONE;
-static void
-make_close_phi_nodes_unique (basic_block bb)
-{
- gphi_iterator psi;
+ fprintf (file, "digraph all {\n");
- for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
+ basic_block bb;
+ FOR_ALL_BB_FN (bb, cfun)
{
- gphi_iterator gsi = psi;
- gphi *phi = psi.phi ();
-
- /* 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.phi ()))
- remove_duplicate_close_phi (phi, &gsi);
- else
- gsi_next (&gsi);
- }
-}
+ int part_of_scop = false;
-/* Transforms LOOP to the canonical loop closed SSA form. */
+ /* Use HTML for every bb label. So we are able to print bbs
+ which are part of two different SCoPs, with two different
+ background colors. */
+ fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
+ bb->index);
+ fprintf (file, "CELLSPACING=\"0\">\n");
-static void
-canonicalize_loop_closed_ssa (loop_p loop)
-{
- edge e = single_exit (loop);
- basic_block bb;
+ /* Select color for SCoP. */
+ sese_l *region;
+ int i;
+ FOR_EACH_VEC_ELT (scops, i, region)
+ {
+ bool sese_in_region = bb_in_sese_p (bb, *region);
+ if (sese_in_region || (region->exit->dest == bb)
+ || (region->entry->dest == bb))
+ {
+ const char *color;
+ switch (i % 17)
+ {
+ case 0: /* red */
+ color = "#e41a1c";
+ break;
+ case 1: /* blue */
+ color = "#377eb8";
+ break;
+ case 2: /* green */
+ color = "#4daf4a";
+ break;
+ case 3: /* purple */
+ color = "#984ea3";
+ break;
+ case 4: /* orange */
+ color = "#ff7f00";
+ break;
+ case 5: /* yellow */
+ color = "#ffff33";
+ break;
+ case 6: /* brown */
+ color = "#a65628";
+ break;
+ case 7: /* rose */
+ color = "#f781bf";
+ break;
+ case 8:
+ color = "#8dd3c7";
+ break;
+ case 9:
+ color = "#ffffb3";
+ break;
+ case 10:
+ color = "#bebada";
+ break;
+ case 11:
+ color = "#fb8072";
+ break;
+ case 12:
+ color = "#80b1d3";
+ break;
+ case 13:
+ color = "#fdb462";
+ break;
+ case 14:
+ color = "#b3de69";
+ break;
+ case 15:
+ color = "#fccde5";
+ break;
+ case 16:
+ color = "#bc80bd";
+ break;
+ default: /* gray */
+ color = "#999999";
+ }
- if (!e || e->flags & EDGE_ABNORMAL)
- return;
+ fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
+ color);
- bb = e->dest;
+ if (!sese_in_region)
+ fprintf (file, " (");
- if (single_pred_p (bb))
- {
- e = split_block_after_labels (bb);
- DEBUG_PRINT (dp << "\nSplitting bb_" << bb->index);
- make_close_phi_nodes_unique (e->src);
- }
- else
- {
- gphi_iterator psi;
- basic_block close = split_edge (e);
+ if (bb == region->entry->dest && bb == region->exit->dest)
+ fprintf (file, " %d*# ", bb->index);
+ else if (bb == region->entry->dest)
+ fprintf (file, " %d* ", bb->index);
+ else if (bb == region->exit->dest)
+ fprintf (file, " %d# ", bb->index);
+ else
+ fprintf (file, " %d ", bb->index);
- e = single_succ_edge (close);
- DEBUG_PRINT (dp << "\nSplitting edge (" << e->src->index << ","
- << e->dest->index << ")\n");
+ fprintf (file, "{lp_%d}", bb->loop_father->num);
- for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
- {
- gphi *phi = psi.phi ();
- unsigned i;
+ if (!sese_in_region)
+ fprintf (file, ")");
- for (i = 0; i < gimple_phi_num_args (phi); i++)
- if (gimple_phi_arg_edge (phi, i) == e)
- {
- tree res, arg = gimple_phi_arg_def (phi, i);
- use_operand_p use_p;
- gphi *close_phi;
-
- if (TREE_CODE (arg) != SSA_NAME)
- continue;
-
- close_phi = create_phi_node (NULL_TREE, close);
- res = create_new_def_for (arg, close_phi,
- gimple_phi_result_ptr (close_phi));
- add_phi_arg (close_phi, arg,
- gimple_phi_arg_edge (close_phi, 0),
- UNKNOWN_LOCATION);
- use_p = gimple_phi_arg_imm_use_ptr (phi, i);
- replace_exp (use_p, res);
- update_stmt (phi);
- }
+ fprintf (file, "</TD></TR>\n");
+ part_of_scop = true;
+ }
}
- make_close_phi_nodes_unique (close);
+ if (!part_of_scop)
+ {
+ fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
+ fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
+ bb->loop_father->num);
+ }
+ fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
}
- /* The code above does not properly handle changes in the post dominance
- information (yet). */
- recompute_all_dominators ();
-}
-
-/* Converts the current loop closed SSA form to a canonical form
- expected by the Graphite code generation.
-
- The loop closed SSA form has the following invariant: a variable
- defined in a loop that is used outside the loop appears only in the
- phi nodes in the destination of the loop exit. These phi nodes are
- called close phi nodes.
-
- The canonical loop closed SSA form contains the extra invariants:
+ FOR_ALL_BB_FN (bb, cfun)
+ {
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
+ }
- - when the loop contains only one exit, the close phi nodes contain
- only one argument. That implies that the basic block that contains
- the close phi nodes has only one predecessor, that is a basic block
- in the loop.
+ fputs ("}\n\n", file);
- - the basic block containing the close phi nodes does not contain
- other statements.
+ /* Enable debugging again. */
+ dump_flags = tmp_dump_flags;
+}
- - there exist only one phi node per definition in the loop.
-*/
+/* Display SCoP on stderr. */
-static void
-canonicalize_loop_closed_ssa_form (void)
+DEBUG_FUNCTION void
+dot_sese (sese_l& scop)
{
- checking_verify_loop_closed_ssa (true);
+ vec<sese_l> scops;
+ scops.create (1);
- loop_p loop;
- FOR_EACH_LOOP (loop, 0)
- canonicalize_loop_closed_ssa (loop);
+ if (scop)
+ scops.safe_push (scop);
- rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
- update_ssa (TODO_update_ssa);
+ dot_all_sese (stderr, scops);
- checking_verify_loop_closed_ssa (true);
+ scops.release ();
}
-/* 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)
+DEBUG_FUNCTION void
+dot_cfg ()
{
- 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;
+ vec<sese_l> scops;
+ scops.create (1);
+ dot_all_sese (stderr, scops);
+ scops.release ();
}
/* Returns a COND_EXPR statement when BB has a single predecessor, the
public:
scop_detection () : scops (vNULL) {}
+ ~scop_detection ()
+ {
+ scops.release ();
+ }
+
/* A marker for invalid sese_l. */
static sese_l invalid_sese;
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);
-
- /* Print S to FILE. */
-
- static void print_sese (FILE *file, sese_l s);
-
/* Merge scops at same loop depth and returns the new sese.
Returns a new SESE when merge was successful, INVALID_SESE otherwise. */
/* Build scop outer->inner if possible. */
- sese_l build_scop_depth (sese_l s, loop_p loop);
-
- /* If loop and loop->next are valid scops, try to merge them. */
-
- sese_l build_scop_breadth (sese_l s1, loop_p loop);
-
- /* Return true when LOOP is a valid scop, that is a Static Control Part, a
- region of code that can be represented in the polyhedral model. SCOP
- defines the region we analyse. */
-
- bool loop_is_valid_scop (loop_p loop, sese_l scop) const;
+ void build_scop_depth (loop_p loop);
/* Return true when BEGIN is the preheader edge of a loop with a single exit
END. */
void remove_intersecting_scops (sese_l s1);
- /* Return true when the body of LOOP has statements that can be represented
- as a valid scop. */
-
- bool loop_body_is_valid_scop (loop_p loop, sese_l scop) const;
-
- /* Return true when BB contains a harmful operation for a scop: that
- can be a function call with side effects, the induction variables
- are not linear with respect to SCOP, etc. The current open
- scop should end before this statement. */
+ /* Return true when a statement in SCOP cannot be represented by Graphite. */
- bool harmful_stmt_in_bb (sese_l scop, basic_block bb) const;
-
- /* 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. */
-
- bool harmful_stmt_in_region (sese_l scop) const;
+ bool harmful_loop_in_region (sese_l scop) const;
/* Return true only when STMT is simple enough for being handled by Graphite.
This depends on SCOP, as the parameters are initialized relatively to
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.
FIXME: For the moment, graphite cannot be used on loops that iterate using
induction variables that wrap. */
- static bool can_represent_loop_1 (loop_p loop, sese_l scop);
-
- /* Return true when all the loops within LOOP can be represented by
- Graphite. */
-
static bool can_represent_loop (loop_p loop, sese_l scop);
/* Returns the number of pbbs that are in loops contained in SCOP. */
static int nb_pbbs_in_loops (scop_p scop);
- static bool graphite_can_represent_stmt (sese_l, gimple *, basic_block);
-
private:
vec<sese_l> scops;
};
if (!loop)
return invalid_sese;
- if (!loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS))
- return invalid_sese;
+ edge scop_begin = loop_preheader_edge (loop);
edge scop_end = single_exit (loop);
- if (!scop_end)
+ if (!scop_end || (scop_end->flags & (EDGE_COMPLEX|EDGE_FAKE)))
return invalid_sese;
- edge scop_begin = loop_preheader_edge (loop);
- sese_l s (scop_begin, scop_end);
- return s;
-}
-
-/* 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 e1->src dominates e2->src then e1->src will also dominate dom. */
- if (dom->preds->length () == 2)
- {
- edge e1 = (*dom->preds)[0];
- edge e2 = (*dom->preds)[1];
- if (dominated_by_p (CDI_DOMINATORS, e2->src, e1->src))
- return e1;
- if (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 dom)
-{
- if (!dom->succs)
- return NULL;
- if (dom->succs->length () == 2)
- {
- edge e1 = (*dom->succs)[0];
- edge e2 = (*dom->succs)[1];
- if (dominated_by_p (CDI_POST_DOMINATORS, e2->dest, e1->dest))
- return e1;
- if (dominated_by_p (CDI_POST_DOMINATORS, e1->dest, e2->dest))
- return e2;
- }
-
- while (dom->succs->length () != 1)
- {
- if (dom->succs->length () < 1)
- return NULL;
- dom = get_immediate_dominator (CDI_POST_DOMINATORS, dom);
- if (!dom->succs)
- return NULL;
- }
- return (*dom->succs)[0];
-}
-
-/* Print S to FILE. */
-void
-scop_detection::print_sese (FILE *file, sese_l s)
-{
- fprintf (file, "(entry_edge (bb_%d, bb_%d), exit_edge (bb_%d, bb_%d))\n",
- s.entry->src->index, s.entry->dest->index,
- s.exit->src->index, s.exit->dest->index);
+ return sese_l (scop_begin, scop_end);
}
/* Merge scops at same loop depth and returns the new sese.
if (!second)
return first;
- DEBUG_PRINT (dp << "[try-merging-sese] s1: "; print_sese (dump_file, first);
- dp << "[try-merging-sese] s2: ";
+ DEBUG_PRINT (dp << "[scop-detection] try merging sese s1: ";
+ print_sese (dump_file, first);
+ 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)
- 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)
- return invalid_sese;
-
- sese_l combined (entry, exit);
-
- /* 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 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;
- }
-
- /* FIXME: We should remove this piece of code once
- canonicalize_loop_closed_ssa has been removed, because that function
- adds a BB with single exit. */
- if (!trivially_empty_bb_p (get_exit_bb (combined)))
+ 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
{
- /* Find the first empty succ (with single exit) of combined.exit. */
- basic_block imm_succ = combined.exit->dest;
- if (single_succ_p (imm_succ) && trivially_empty_bb_p (imm_succ))
- combined.exit = single_succ_edge (imm_succ);
- else
+ 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)
{
- DEBUG_PRINT (dp << "\n[scop-detection-fail] Discarding SCoP because "
- << "no single exit (empty succ) for sese exit";
- print_sese (dump_file, 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));
- /* Analyze all the BBs in new sese. */
- if (harmful_stmt_in_region (combined))
- return invalid_sese;
+ sese_l combined (entry, exit);
DEBUG_PRINT (dp << "[merged-sese] s1: "; print_sese (dump_file, combined));
/* Build scop outer->inner if possible. */
-sese_l
-scop_detection::build_scop_depth (sese_l s, loop_p loop)
+void
+scop_detection::build_scop_depth (loop_p loop)
{
- if (!loop)
- return s;
-
- DEBUG_PRINT (dp << "\n[Depth loop_" << loop->num << "]");
- s = build_scop_depth (s, loop->inner);
-
- sese_l s2 = merge_sese (s, get_sese (loop));
- if (!s2)
- {
- /* s might be a valid scop, so return it and start analyzing from the
- adjacent loop. */
- build_scop_depth (invalid_sese, loop->next);
- return s;
- }
-
- if (!loop_is_valid_scop (loop, s2))
- return build_scop_depth (invalid_sese, loop->next);
-
- return build_scop_breadth (s2, loop);
-}
-
-/* If loop and loop->next are valid scops, try to merge them. */
-
-sese_l
-scop_detection::build_scop_breadth (sese_l s1, loop_p loop)
-{
- if (!loop)
- return s1;
- DEBUG_PRINT (dp << "\n[Breadth loop_" << loop->num << "]");
- gcc_assert (s1);
-
- loop_p l = loop;
- sese_l s2 = build_scop_depth (invalid_sese, l->next);
- if (!s2)
+ sese_l s = invalid_sese;
+ loop = loop->inner;
+ while (loop)
{
- if (s1)
- add_scop (s1);
- return s1;
+ sese_l next = get_sese (loop);
+ if (! next
+ || harmful_loop_in_region (next))
+ {
+ if (s)
+ add_scop (s);
+ build_scop_depth (loop);
+ s = invalid_sese;
+ }
+ else if (! s)
+ s = next;
+ else
+ {
+ sese_l combined = merge_sese (s, next);
+ if (! combined
+ || harmful_loop_in_region (combined))
+ {
+ add_scop (s);
+ s = next;
+ }
+ else
+ s = combined;
+ }
+ loop = loop->next;
}
-
- sese_l combined = merge_sese (s1, s2);
-
- if (combined)
- s1 = combined;
- else
- add_scop (s2);
-
- if (s1)
- add_scop (s1);
- return s1;
+ if (s)
+ add_scop (s);
}
/* Returns true when Graphite can represent LOOP in SCOP.
induction variables that wrap. */
bool
-scop_detection::can_represent_loop_1 (loop_p loop, sese_l scop)
+scop_detection::can_represent_loop (loop_p loop, sese_l scop)
{
tree niter;
struct tree_niter_desc niter_desc;
- return single_exit (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))
&& graphite_can_represent_expr (scop, loop, niter);
}
-/* Return true when all the loops within LOOP can be represented by
- Graphite. */
-
-bool
-scop_detection::can_represent_loop (loop_p loop, sese_l scop)
-{
- if (!can_represent_loop_1 (loop, scop))
- return false;
- if (loop->inner && !can_represent_loop (loop->inner, scop))
- return false;
- if (loop->next && !can_represent_loop (loop->next, scop))
- return false;
-
- return true;
-}
-
-/* Return true when LOOP is a valid scop, that is a Static Control Part, a
- region of code that can be represented in the polyhedral model. SCOP
- defines the region we analyse. */
-
-bool
-scop_detection::loop_is_valid_scop (loop_p loop, sese_l scop) const
-{
- if (!scop)
- return false;
-
- if (!can_represent_loop (loop, scop))
- {
- DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
- << loop->num << "\n");
- return false;
- }
-
- if (loop_body_is_valid_scop (loop, scop))
- {
- DEBUG_PRINT (dp << "[valid-scop] loop_" << loop->num
- << "is a valid scop.\n");
- return true;
- }
- return false;
-}
-
/* Return true when BEGIN is the preheader edge of a loop with a single exit
END. */
return false;
/* Otherwise, check whether we have adjacent loops. */
- return begin->dest->loop_father == end->src->loop_father;
+ return (single_pred_p (end->src)
+ && begin->dest->loop_father == single_pred (end->src)->loop_father);
}
/* Add to SCOPS a scop starting at SCOP_BEGIN and ending at SCOP_END. */
{
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 << "\n[scop-detection-fail] Discarding one loop SCoP";
+ DEBUG_PRINT (dp << "[scop-detection-fail] Discarding one loop SCoP: ";
print_sese (dump_file, s));
return;
}
if (get_exit_bb (s) == EXIT_BLOCK_PTR_FOR_FN (cfun))
{
- DEBUG_PRINT (dp << "\n[scop-detection-fail] "
- << "Discarding SCoP exiting to return";
+ DEBUG_PRINT (dp << "[scop-detection-fail] "
+ << "Discarding SCoP exiting to return: ";
print_sese (dump_file, s));
return;
}
/* Remove all the scops which are subsumed by s. */
remove_subscops (s);
- /* Replace this with split-intersecting scops. */
+ /* Remove intersecting scops. FIXME: It will be a good idea to keep
+ the non-intersecting part of the scop already in the list. */
remove_intersecting_scops (s);
scops.safe_push (s);
- DEBUG_PRINT (dp << "\nAdding SCoP "; print_sese (dump_file, 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_stmt_in_region (sese_l scop) const
+scop_detection::harmful_loop_in_region (sese_l scop) const
{
basic_block exit_bb = get_exit_bb (scop);
basic_block entry_bb = get_entry_bb (scop);
- DEBUG_PRINT (dp << "\n[checking-harmful-bbs] ";
+ DEBUG_PRINT (dp << "[checking-harmful-bbs] ";
print_sese (dump_file, scop));
gcc_assert (dominated_by_p (CDI_DOMINATORS, exit_bb, entry_bb));
- int depth = bb_dom_dfs_in (CDI_DOMINATORS, exit_bb)
- - bb_dom_dfs_in (CDI_DOMINATORS, entry_bb);
+ auto_vec<basic_block> worklist;
+ auto_bitmap loops;
- gcc_assert (depth > 0);
+ worklist.safe_push (entry_bb);
+ while (! worklist.is_empty ())
+ {
+ basic_block bb = worklist.pop ();
+ DEBUG_PRINT (dp << "Visiting bb_" << bb->index << "\n");
- vec<basic_block> dom
- = get_dominated_to_depth (CDI_DOMINATORS, entry_bb, depth);
- int i;
- basic_block bb;
- FOR_EACH_VEC_ELT (dom, i, bb)
+ /* The basic block should not be part of an irreducible loop. */
+ if (bb->flags & BB_IRREDUCIBLE_LOOP)
+ return true;
+
+ /* Check for unstructured control flow: CFG not generated by structured
+ if-then-else. */
+ if (bb->succs->length () > 1)
+ {
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (!dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest)
+ && !dominated_by_p (CDI_DOMINATORS, e->dest, bb))
+ return true;
+ }
+
+ /* Collect all loops in the current region. */
+ loop_p loop = bb->loop_father;
+ if (loop_in_sese_p (loop, scop))
+ bitmap_set_bit (loops, loop->num);
+
+ /* Check for harmful statements in basic blocks part of the region. */
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
+ !gsi_end_p (gsi); gsi_next (&gsi))
+ if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
+ return true;
+
+ 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);
+ }
+
+ /* Go through all loops and check that they are still valid in the combined
+ scop. */
+ unsigned j;
+ bitmap_iterator bi;
+ EXECUTE_IF_SET_IN_BITMAP (loops, 0, j, bi)
{
- DEBUG_PRINT (dp << "\nVisiting bb_" << bb->index);
+ loop_p loop = (*current_loops->larray)[j];
+ gcc_assert (loop->num == (int) j);
- /* We don't want to analyze any bb outside sese. */
- if (!dominated_by_p (CDI_POST_DOMINATORS, bb, exit_bb))
- continue;
+ /* Check if the loop nests are to be optimized for speed. */
+ if (! loop->inner
+ && ! optimize_loop_for_speed_p (loop))
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] loop_"
+ << loop->num << " is not on a hot path.\n");
+ return true;
+ }
- if (harmful_stmt_in_bb (scop, bb))
- return true;
+ if (! can_represent_loop (loop, scop))
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] cannot represent loop_"
+ << loop->num << "\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
+ loops and reject those when we build a SESE region for a loop
+ during SESE discovery. */
+ if (! loop->inner
+ && ! loop_nest_has_data_refs (loop))
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
+ << "does not have any data reference.\n");
+ return true;
+ }
}
- return false;
+ return false;
}
/* Returns true if S1 subsumes/surrounds S2. */
{
if (subsumes (s1, *s2))
{
- DEBUG_PRINT (dp << "\nRemoving sub-SCoP";
+ DEBUG_PRINT (dp << "Removing sub-SCoP";
print_sese (dump_file, *s2));
scops.unordered_remove (j);
}
{
if (intersects (s1, *s2))
{
- DEBUG_PRINT (dp << "\nRemoving intersecting SCoP";
- print_sese (dump_file, *s2); dp << "Intersects with:";
+ DEBUG_PRINT (dp << "Removing intersecting SCoP";
+ print_sese (dump_file, *s2);
+ dp << "Intersects with:";
print_sese (dump_file, s1));
scops.unordered_remove (j);
}
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);
- vec<data_reference_p> drs = vNULL;
+ if (!loop_in_sese_p (loop, scop))
+ loop = NULL;
- graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
+ auto_vec<data_reference_p> drs;
+ if (! graphite_find_data_references_in_stmt (nest, loop, stmt, &drs))
+ return false;
int j;
data_reference_p dr;
FOR_EACH_VEC_ELT (drs, j, dr)
{
- int nb_subscripts = DR_NUM_DIMENSIONS (dr);
-
- if (nb_subscripts < 1)
- {
- free_data_refs (drs);
+ for (unsigned i = 0; i < DR_NUM_DIMENSIONS (dr); ++i)
+ if (! graphite_can_represent_scev (scop, DR_ACCESS_FN (dr, i)))
return false;
- }
-
- tree ref = DR_REF (dr);
-
- for (int i = nb_subscripts - 1; i >= 0; i--)
- {
- if (!graphite_can_represent_scev (DR_ACCESS_FN (dr, i))
- || (TREE_CODE (ref) != ARRAY_REF && TREE_CODE (ref) != MEM_REF
- && TREE_CODE (ref) != COMPONENT_REF))
- {
- free_data_refs (drs);
- return false;
- }
-
- ref = TREE_OPERAND (ref, 0);
- }
}
- free_data_refs (drs);
- return true;
+ return true;
}
/* GIMPLE_ASM and GIMPLE_CALL may embed arbitrary side effects.
return false;
}
-/* Returns true if STMT can be represented in polyhedral model. LABEL,
- simple COND stmts, pure calls, and assignments can be repesented. */
+/* Return true only when STMT is simple enough for being handled by Graphite.
+ This depends on SCOP, as the parameters are initialized relatively to
+ this basic block, the linear functions are initialized based on the outermost
+ loop containing STMT inside the SCOP. BB is the place where we try to
+ evaluate the STMT. */
bool
-scop_detection::graphite_can_represent_stmt (sese_l scop, gimple *stmt,
- basic_block bb)
+scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
+ basic_block bb) const
{
- loop_p loop = bb->loop_father;
+ gcc_assert (scop);
+
+ if (is_gimple_debug (stmt))
+ return true;
+
+ if (stmt_has_side_effects (stmt))
+ return false;
+
+ if (!stmt_has_simple_data_refs_p (scop, stmt))
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] "
+ << "Graphite cannot handle data-refs in stmt:\n";
+ print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
+ return false;
+ }
+
switch (gimple_code (stmt))
{
case GIMPLE_LABEL:
return false;
}
+ loop_p loop = bb->loop_father;
for (unsigned i = 0; i < 2; ++i)
{
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 true only when STMT is simple enough for being handled by Graphite.
- This depends on SCOP, as the parameters are initialized relatively to
- this basic block, the linear functions are initialized based on the outermost
- loop containing STMT inside the SCOP. BB is the place where we try to
- evaluate the STMT. */
-
-bool
-scop_detection::stmt_simple_for_scop_p (sese_l scop, gimple *stmt,
- basic_block bb) const
-{
- gcc_assert (scop);
-
- if (is_gimple_debug (stmt))
- return true;
-
- if (stmt_has_side_effects (stmt))
- return false;
-
- if (!stmt_has_simple_data_refs_p (scop, stmt))
- {
- DEBUG_PRINT (dp << "[scop-detection-fail] "
- << "Graphite cannot handle data-refs in stmt:\n";
- print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS|TDF_MEMSYMS););
- return false;
- }
-
- return graphite_can_represent_stmt (scop, stmt, bb);
-}
-
-/* Return true when BB contains a harmful operation for a scop: that
- can be a function call with side effects, the induction variables
- are not linear with respect to SCOP, etc. The current open
- scop should end before this statement. */
-
-bool
-scop_detection::harmful_stmt_in_bb (sese_l scop, basic_block bb) const
-{
- gimple_stmt_iterator gsi;
-
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- if (!stmt_simple_for_scop_p (scop, gsi_stmt (gsi), bb))
- return true;
-
- return false;
-}
-
-/* Pretty print to FILE all the SCoPs in DOT format and mark them with
- different colors. If there are not enough colors, paint the
- remaining SCoPs in gray.
-
- Special nodes:
- - "*" after the node number denotes the entry of a SCoP,
- - "#" after the node number denotes the exit of a SCoP,
- - "()" around the node number denotes the entry or the
- exit nodes of the SCOP. These are not part of SCoP. */
-
-static void
-dot_all_scops_1 (FILE *file, vec<scop_p> scops)
-{
- basic_block bb;
- edge e;
- edge_iterator ei;
- scop_p scop;
- const char *color;
- int i;
-
- /* Disable debugging while printing graph. */
- int tmp_dump_flags = dump_flags;
- dump_flags = 0;
-
- fprintf (file, "digraph all {\n");
-
- FOR_ALL_BB_FN (bb, cfun)
- {
- int part_of_scop = false;
-
- /* Use HTML for every bb label. So we are able to print bbs
- which are part of two different SCoPs, with two different
- background colors. */
- fprintf (file, "%d [label=<\n <TABLE BORDER=\"0\" CELLBORDER=\"1\" ",
- bb->index);
- fprintf (file, "CELLSPACING=\"0\">\n");
-
- /* Select color for SCoP. */
- FOR_EACH_VEC_ELT (scops, i, scop)
- {
- sese_l region = scop->scop_info->region;
- if (bb_in_sese_p (bb, region) || (region.exit->dest == bb)
- || (region.entry->dest == bb))
- {
- switch (i % 17)
- {
- case 0: /* red */
- color = "#e41a1c";
- break;
- case 1: /* blue */
- color = "#377eb8";
- break;
- case 2: /* green */
- color = "#4daf4a";
- break;
- case 3: /* purple */
- color = "#984ea3";
- break;
- case 4: /* orange */
- color = "#ff7f00";
- break;
- case 5: /* yellow */
- color = "#ffff33";
- break;
- case 6: /* brown */
- color = "#a65628";
- break;
- case 7: /* rose */
- color = "#f781bf";
- break;
- case 8:
- color = "#8dd3c7";
- break;
- case 9:
- color = "#ffffb3";
- break;
- case 10:
- color = "#bebada";
- break;
- case 11:
- color = "#fb8072";
- break;
- case 12:
- color = "#80b1d3";
- break;
- case 13:
- color = "#fdb462";
- break;
- case 14:
- color = "#b3de69";
- break;
- case 15:
- color = "#fccde5";
- break;
- case 16:
- color = "#bc80bd";
- break;
- default: /* gray */
- color = "#999999";
- }
-
- fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"%s\">",
- color);
-
- if (!bb_in_sese_p (bb, region))
- fprintf (file, " (");
-
- if (bb == region.entry->dest && bb == region.exit->dest)
- fprintf (file, " %d*# ", bb->index);
- else if (bb == region.entry->dest)
- fprintf (file, " %d* ", bb->index);
- else if (bb == region.exit->dest)
- fprintf (file, " %d# ", bb->index);
- else
- fprintf (file, " %d ", bb->index);
-
- fprintf (file, "{lp_%d}", bb->loop_father->num);
-
- if (!bb_in_sese_p (bb, region))
- fprintf (file, ")");
-
- fprintf (file, "</TD></TR>\n");
- part_of_scop = true;
- }
- }
-
- if (!part_of_scop)
- {
- fprintf (file, " <TR><TD WIDTH=\"50\" BGCOLOR=\"#ffffff\">");
- fprintf (file, " %d {lp_%d} </TD></TR>\n", bb->index,
- bb->loop_father->num);
- }
- fprintf (file, " </TABLE>>, shape=box, style=\"setlinewidth(0)\"]\n");
- }
-
- FOR_ALL_BB_FN (bb, cfun)
- {
- FOR_EACH_EDGE (e, ei, bb->succs)
- fprintf (file, "%d -> %d;\n", bb->index, e->dest->index);
- }
-
- fputs ("}\n\n", file);
-
- /* Enable debugging again. */
- dump_flags = tmp_dump_flags;
-}
-
-/* Display all SCoPs using dotty. */
-
-DEBUG_FUNCTION void
-dot_all_scops (vec<scop_p> scops)
-{
- /* When debugging, enable the following code. This cannot be used
- in production compilers because it calls "system". */
-#if 0
- int x;
- FILE *stream = fopen ("/tmp/allscops.dot", "w");
- gcc_assert (stream);
-
- dot_all_scops_1 (stream, scops);
- fclose (stream);
-
- x = system ("dotty /tmp/allscops.dot &");
-#else
- dot_all_scops_1 (stderr, scops);
-#endif
-}
-
-/* Display all SCoPs using dotty. */
-
-DEBUG_FUNCTION void
-dot_scop (scop_p scop)
-{
- auto_vec<scop_p, 1> scops;
-
- if (scop)
- scops.safe_push (scop);
-
- /* When debugging, enable the following code. This cannot be used
- in production compilers because it calls "system". */
-#if 0
- {
- int x;
- FILE *stream = fopen ("/tmp/allscops.dot", "w");
- gcc_assert (stream);
-
- dot_all_scops_1 (stream, scops);
- fclose (stream);
- x = system ("dotty /tmp/allscops.dot &");
- }
-#else
- dot_all_scops_1 (stderr, scops);
-#endif
-}
-
-/* Return true when the body of LOOP has statements that can be represented as a
- valid scop. */
-
-bool
-scop_detection::loop_body_is_valid_scop (loop_p loop, sese_l scop) const
-{
- if (!loop_ivs_can_be_represented (loop))
- {
- DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
- << "IV cannot be represented.\n");
- return false;
- }
-
- if (!loop_nest_has_data_refs (loop))
- {
- DEBUG_PRINT (dp << "[scop-detection-fail] loop_" << loop->num
- << "does not have any data reference.\n");
- return false;
- }
-
- basic_block *bbs = get_loop_body (loop);
- for (unsigned i = 0; i < loop->num_nodes; i++)
- {
- basic_block bb = bbs[i];
-
- if (harmful_stmt_in_bb (scop, bb))
- return false;
- }
- free (bbs);
-
- if (loop->inner)
- {
- loop = loop->inner;
- while (loop)
- {
- if (!loop_body_is_valid_scop (loop, scop))
- return false;
- loop = loop->next;
- }
- }
-
- return true;
-}
-
/* Returns the number of pbbs that are in loops contained in SCOP. */
int
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 (SESE_PARAMS (region), i, p)
+ 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 = SESE_PARAMS (region).length ();
- SESE_PARAMS (region).safe_push (name);
- return i;
+ region->params.safe_push (name);
}
/* 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 (SESE_LOOP_NEST (region), 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 (!is_gimple_reg (def))
+ return;
+
+ bool scev_analyzable = scev_analyzable_p (def, scop->scop_info->region);
+
+ gimple *use_stmt;
+ imm_use_iterator imm_iter;
+ FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
+ /* Do not gather scalar variables that can be analyzed by SCEV as they can
+ be generated out of the induction variables. */
+ if ((! scev_analyzable
+ /* 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)))
+ {
+ add_write (writes, def);
+ break;
+ }
+}
+
+/* Record USE if it is defined in other bbs different than USE_STMT
+ in the SCOP. */
+
+static void
+build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
+ vec<scalar_use> *reads)
+{
+ if (!is_gimple_reg (use))
+ return;
+
+ /* Do not gather scalar variables that can be analyzed by SCEV as they can be
+ generated out of the induction variables. */
+ if (scev_analyzable_p (use, scop->scop_info->region))
+ return;
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (use);
+ 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
information. */
static gimple_poly_bb_p
try_generate_gimple_bb (scop_p scop, basic_block bb)
{
- vec<data_reference_p> drs;
- drs.create (5);
- sese_l region = scop->scop_info->region;
- loop_p nest = outermost_loop_in_sese (region, bb);
+ vec<data_reference_p> drs = vNULL;
+ vec<tree> writes = vNULL;
+ vec<scalar_use> reads = vNULL;
+ sese_l region = scop->scop_info->region;
+ edge nest = region.entry;
loop_p loop = bb->loop_father;
if (!loop_in_sese_p (loop, region))
- loop = nest;
+ loop = NULL;
- gimple_stmt_iterator gsi;
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
gimple *stmt = gsi_stmt (gsi);
if (is_gimple_debug (stmt))
continue;
graphite_find_data_references_in_stmt (nest, loop, stmt, &drs);
+
+ 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))
+ {
+ 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;
}
- return new_gimple_poly_bb (bb, drs);
+ /* 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;
+
+ return new_gimple_poly_bb (bb, drs, reads, writes);
+}
+
+/* Compute alias-sets for all data references in DRS. */
+
+static bool
+build_alias_set (scop_p scop)
+{
+ int num_vertices = scop->drs.length ();
+ struct graph *g = new_graph (num_vertices);
+ dr_info *dr1, *dr2;
+ 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, nest))
+ {
+ /* Dependences in the same alias set need to be handled
+ by just looking at DR_ACCESS_FNs. */
+ if (DR_NUM_DIMENSIONS (dr1->dr) == 0
+ || DR_NUM_DIMENSIONS (dr1->dr) != DR_NUM_DIMENSIONS (dr2->dr)
+ || ! operand_equal_p (DR_BASE_OBJECT (dr1->dr),
+ DR_BASE_OBJECT (dr2->dr),
+ OEP_ADDRESS_OF)
+ || ! types_compatible_p (TREE_TYPE (DR_BASE_OBJECT (dr1->dr)),
+ TREE_TYPE (DR_BASE_OBJECT (dr2->dr))))
+ {
+ free_graph (g);
+ return false;
+ }
+ add_edge (g, i, j);
+ add_edge (g, j, i);
+ }
+
+ all_vertices = XNEWVEC (int, num_vertices);
+ for (i = 0; i < num_vertices; i++)
+ all_vertices[i] = i;
+
+ 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++)
+ scop->drs[i].alias_set = g->vertices[i].component + 1;
+
+ free_graph (g);
+ return true;
}
/* Gather BBs and conditions for a SCOP. */
class gather_bbs : public dom_walker
{
public:
- gather_bbs (cdi_direction, scop_p);
+ gather_bbs (cdi_direction, scop_p, int *);
- virtual void before_dom_children (basic_block);
+ virtual edge before_dom_children (basic_block);
virtual void after_dom_children (basic_block);
private:
scop_p scop;
};
}
-gather_bbs::gather_bbs (cdi_direction direction, scop_p scop)
- : dom_walker (direction), scop (scop)
+gather_bbs::gather_bbs (cdi_direction direction, scop_p scop, int *bb_to_rpo)
+ : dom_walker (direction, ALL_BLOCKS, bb_to_rpo), scop (scop)
{
}
/* Call-back for dom_walk executed before visiting the dominated
blocks. */
-void
+edge
gather_bbs::before_dom_children (basic_block bb)
{
- if (!bb_in_sese_p (bb, scop->scop_info->region))
- return;
+ sese_info_p region = scop->scop_info;
+ if (!bb_in_sese_p (bb, region->region))
+ return dom_walker::STOP;
- 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);
gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
+ if (!gbb)
+ return NULL;
+
GBB_CONDITIONS (gbb) = conditions.copy ();
GBB_CONDITION_CASES (gbb) = cases.copy ();
poly_bb_p pbb = new_poly_bb (scop, gbb);
scop->pbbs.safe_push (pbb);
+
+ int i;
+ data_reference_p dr;
+ FOR_EACH_VEC_ELT (gbb->data_refs, i, dr)
+ {
+ DEBUG_PRINT (dp << "Adding memory ";
+ if (dr->is_read)
+ dp << "read: ";
+ else
+ dp << "write: ";
+ print_generic_expr (dump_file, dr->ref);
+ dp << "\nFrom stmt: ";
+ print_gimple_stmt (dump_file, dr->stmt, 0));
+
+ scop->drs.safe_push (dr_info (dr, pbb));
+ }
+
+ return NULL;
}
/* Call-back for dom_walk executed after visiting the dominated
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 int *bb_to_rpo;
+
+/* Helper for qsort, sorting after order above. */
+
+static int
+cmp_pbbs (const void *pa, const void *pb)
+{
+ poly_bb_p bb1 = *((const poly_bb_p *)pa);
+ poly_bb_p bb2 = *((const poly_bb_p *)pb);
+ if (bb_to_rpo[bb1->black_box->bb->index]
+ < bb_to_rpo[bb2->black_box->bb->index])
+ return -1;
+ else if (bb_to_rpo[bb1->black_box->bb->index]
+ > bb_to_rpo[bb2->black_box->bb->index])
+ return 1;
+ else
+ return 0;
+}
+
/* Find Static Control Parts (SCoP) in the current function and pushes
them to SCOPS. */
if (dump_file)
dp.set_dump_file (dump_file);
- canonicalize_loop_closed_ssa_form ();
-
scop_detection sb;
- sb.build_scop_depth (scop_detection::invalid_sese, current_loops->tree_root);
+ sb.build_scop_depth (current_loops->tree_root);
/* Now create scops from the lightweight SESEs. */
vec<sese_l> scops_l = sb.get_scops ();
+
+ /* 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);
+ 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);
+
int i;
sese_l *s;
FOR_EACH_VEC_ELT (scops_l, i, s)
scop_p scop = new_scop (s->entry, s->exit);
/* Record all basic blocks and their conditions in REGION. */
- gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr);
+ gather_bbs (CDI_DOMINATORS, scop, bb_to_rpo).walk (s->entry->dest);
+
+ /* Sort pbbs after execution order for initial schedule generation. */
+ scop->pbbs.qsort (cmp_pbbs);
+
+ if (! build_alias_set (scop))
+ {
+ DEBUG_PRINT (dp << "[scop-detection-fail] cannot handle dependences\n");
+ free_scop (scop);
+ continue;
+ }
/* Do not optimize a scop containing only PBBs that do not belong
to any loops. */
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 ()
continue;
}
- build_sese_loop_nests (scop->scop_info);
-
find_scop_parameters (scop);
- graphite_dim_t max_dim = PARAM_VALUE (PARAM_GRAPHITE_MAX_NB_SCOP_PARAMS);
-
- if (scop_nb_params (scop) > max_dim)
+ graphite_dim_t max_dim = param_graphite_max_nb_scop_params;
+ if (max_dim > 0
+ && scop_nb_params (scop) > max_dim)
{
DEBUG_PRINT (dp << "[scop-detection-fail] too many parameters: "
- << scop_nb_params (scop)
- << " larger than --param graphite-max-nb-scop-params="
- << max_dim << ".\n");
-
+ << scop_nb_params (scop)
+ << " larger than --param graphite-max-nb-scop-params="
+ << max_dim << ".\n");
free_scop (scop);
continue;
}
scops->safe_push (scop);
}
+ free (bb_to_rpo);
+ bb_to_rpo = NULL;
DEBUG_PRINT (dp << "number of SCoPs: " << (scops ? scops->length () : 0););
}
projects / thirdparty / gcc.git / blobdiff