/* Single entry single exit control flow regions.
- Copyright (C) 2008-2015 Free Software Foundation, Inc.
+ Copyright (C) 2008-2019 Free Software Foundation, Inc.
Contributed by Jan Sjodin <jan.sjodin@amd.com> and
Sebastian Pop <sebastian.pop@amd.com>.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "hash-map.h"
+#include "backend.h"
#include "tree.h"
-#include "tree-pretty-print.h"
-#include "predict.h"
-#include "vec.h"
-#include "hashtab.h"
-#include "hash-set.h"
-#include "machmode.h"
-#include "tm.h"
-#include "hard-reg-set.h"
-#include "input.h"
-#include "function.h"
-#include "dominance.h"
-#include "cfg.h"
-#include "basic-block.h"
-#include "tree-ssa-alias.h"
-#include "internal-fn.h"
-#include "gimple-fold.h"
-#include "tree-eh.h"
-#include "gimple-expr.h"
-#include "is-a.h"
#include "gimple.h"
+#include "cfghooks.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "tree-pretty-print.h"
+#include "fold-const.h"
#include "gimplify.h"
#include "gimple-iterator.h"
+#include "gimple-pretty-print.h"
#include "gimplify-me.h"
-#include "gimple-ssa.h"
#include "tree-cfg.h"
-#include "tree-phinodes.h"
-#include "ssa-iterators.h"
-#include "stringpool.h"
-#include "tree-ssanames.h"
#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "cfgloop.h"
-#include "tree-chrec.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
-#include "tree-pass.h"
-#include "value-prof.h"
-#include "sese.h"
#include "tree-ssa-propagate.h"
-
-/* Helper function for debug_rename_map. */
-
-bool
-debug_rename_map_1 (tree_node *const &old_name, tree_node *const &expr,
- void *)
-{
- fprintf (stderr, "(");
- print_generic_expr (stderr, old_name, 0);
- fprintf (stderr, ", ");
- print_generic_expr (stderr, expr, 0);
- fprintf (stderr, ")\n");
- return true;
-}
-\f
-
-/* Hashtable helpers. */
-
-struct rename_map_hasher : default_hashmap_traits
-{
- static inline hashval_t hash (tree);
-};
-
-/* Computes a hash function for database element ELT. */
-
-inline hashval_t
-rename_map_hasher::hash (tree old_name)
-{
- return SSA_NAME_VERSION (old_name);
-}
-
-typedef hash_map<tree, tree, rename_map_hasher> rename_map_type;
-\f
-
-/* Print to stderr all the elements of RENAME_MAP. */
-
-DEBUG_FUNCTION void
-debug_rename_map (rename_map_type *rename_map)
-{
- rename_map->traverse <void *, debug_rename_map_1> (NULL);
-}
-\f
-
-/* Record LOOP as occurring in REGION. */
-
-static void
-sese_record_loop (sese region, loop_p loop)
-{
- if (sese_contains_loop (region, loop))
- return;
-
- bitmap_set_bit (SESE_LOOPS (region), loop->num);
- SESE_LOOP_NEST (region).safe_push (loop);
-}
-
-/* Build the loop nests contained in REGION. Returns true when the
- operation was successful. */
-
-void
-build_sese_loop_nests (sese region)
-{
- unsigned i;
- basic_block bb;
- struct loop *loop0, *loop1;
-
- FOR_EACH_BB_FN (bb, cfun)
- if (bb_in_sese_p (bb, region))
- {
- struct loop *loop = bb->loop_father;
-
- /* Only add loops if they are completely contained in the SCoP. */
- if (loop->header == bb
- && bb_in_sese_p (loop->latch, region))
- sese_record_loop (region, loop);
- }
-
- /* Make sure that the loops in the SESE_LOOP_NEST are ordered. It
- can be the case that an inner loop is inserted before an outer
- loop. To avoid this, semi-sort once. */
- FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop0)
- {
- if (SESE_LOOP_NEST (region).length () == i + 1)
- break;
-
- loop1 = SESE_LOOP_NEST (region)[i + 1];
- if (loop0->num > loop1->num)
- {
- SESE_LOOP_NEST (region)[i] = loop1;
- SESE_LOOP_NEST (region)[i + 1] = loop0;
- }
- }
-}
+#include "cfganal.h"
+#include "sese.h"
/* For a USE in BB, if BB is outside REGION, mark the USE in the
LIVEOUTS set. */
static void
-sese_build_liveouts_use (sese region, bitmap liveouts, basic_block bb,
+sese_build_liveouts_use (sese_info_p region, bitmap liveouts, basic_block bb,
tree use)
{
- unsigned ver;
- basic_block def_bb;
-
+ gcc_assert (!bb_in_sese_p (bb, region->region));
if (TREE_CODE (use) != SSA_NAME)
return;
- ver = SSA_NAME_VERSION (use);
- def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
+ basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
- if (!def_bb
- || !bb_in_sese_p (def_bb, region)
- || bb_in_sese_p (bb, region))
+ if (!def_bb || !bb_in_sese_p (def_bb, region->region))
return;
+ unsigned ver = SSA_NAME_VERSION (use);
bitmap_set_bit (liveouts, ver);
}
used in BB that is outside of the REGION. */
static void
-sese_build_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
+sese_build_liveouts_bb (sese_info_p region, basic_block bb)
{
- edge e;
- edge_iterator ei;
ssa_op_iter iter;
use_operand_p use_p;
- FOR_EACH_EDGE (e, ei, bb->succs)
- for (gphi_iterator bsi = gsi_start_phis (e->dest); !gsi_end_p (bsi);
- gsi_next (&bsi))
- sese_build_liveouts_use (region, liveouts, bb,
- PHI_ARG_DEF_FROM_EDGE (bsi.phi (), e));
+ for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);
+ gsi_next (&bsi))
+ FOR_EACH_PHI_ARG (use_p, bsi.phi (), iter, SSA_OP_USE)
+ sese_build_liveouts_use (region, region->liveout,
+ bb, USE_FROM_PTR (use_p));
for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi);
gsi_next (&bsi))
{
- gimple stmt = gsi_stmt (bsi);
+ gimple *stmt = gsi_stmt (bsi);
+ bitmap liveouts = region->liveout;
if (is_gimple_debug (stmt))
- continue;
+ liveouts = region->debug_liveout;
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
sese_build_liveouts_use (region, liveouts, bb, USE_FROM_PTR (use_p));
}
}
-/* For a USE in BB, return true if BB is outside REGION and it's not
- in the LIVEOUTS set. */
-
-static bool
-sese_bad_liveouts_use (sese region, bitmap liveouts, basic_block bb,
- tree use)
-{
- unsigned ver;
- basic_block def_bb;
-
- if (TREE_CODE (use) != SSA_NAME)
- return false;
-
- ver = SSA_NAME_VERSION (use);
-
- /* If it's in liveouts, the variable will get a new PHI node, and
- the debug use will be properly adjusted. */
- if (bitmap_bit_p (liveouts, ver))
- return false;
-
- def_bb = gimple_bb (SSA_NAME_DEF_STMT (use));
-
- if (!def_bb
- || !bb_in_sese_p (def_bb, region)
- || bb_in_sese_p (bb, region))
- return false;
-
- return true;
-}
-
/* Reset debug stmts that reference SSA_NAMES defined in REGION that
are not marked as liveouts. */
static void
-sese_reset_debug_liveouts_bb (sese region, bitmap liveouts, basic_block bb)
+sese_reset_debug_liveouts (sese_info_p region)
{
- gimple_stmt_iterator bsi;
- ssa_op_iter iter;
- use_operand_p use_p;
-
- for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
+ bitmap_iterator bi;
+ unsigned i;
+ EXECUTE_IF_AND_COMPL_IN_BITMAP (region->debug_liveout, region->liveout,
+ 0, i, bi)
{
- gimple stmt = gsi_stmt (bsi);
-
- if (!is_gimple_debug (stmt))
- continue;
-
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
- if (sese_bad_liveouts_use (region, liveouts, bb,
- USE_FROM_PTR (use_p)))
- {
- gimple_debug_bind_reset_value (stmt);
- update_stmt (stmt);
- break;
- }
+ tree name = ssa_name (i);
+ auto_vec<gimple *, 4> stmts;
+ gimple *use_stmt;
+ imm_use_iterator use_iter;
+ FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name)
+ {
+ if (! is_gimple_debug (use_stmt)
+ || bb_in_sese_p (gimple_bb (use_stmt), region->region))
+ continue;
+ stmts.safe_push (use_stmt);
+ }
+ while (!stmts.is_empty ())
+ {
+ gimple *stmt = stmts.pop ();
+ gimple_debug_bind_reset_value (stmt);
+ update_stmt (stmt);
+ }
}
}
/* Build the LIVEOUTS of REGION: the set of variables defined inside
and used outside the REGION. */
-static void
-sese_build_liveouts (sese region, bitmap liveouts)
+void
+sese_build_liveouts (sese_info_p region)
{
basic_block bb;
+ gcc_assert (region->liveout == NULL
+ && region->debug_liveout == NULL);
+
+ region->liveout = BITMAP_ALLOC (NULL);
+ region->debug_liveout = BITMAP_ALLOC (NULL);
+
+ /* FIXME: We could start iterating form the successor of sese. */
FOR_EACH_BB_FN (bb, cfun)
- sese_build_liveouts_bb (region, liveouts, bb);
- if (MAY_HAVE_DEBUG_STMTS)
- FOR_EACH_BB_FN (bb, cfun)
- sese_reset_debug_liveouts_bb (region, liveouts, bb);
+ if (!bb_in_sese_p (bb, region->region))
+ sese_build_liveouts_bb (region, bb);
}
/* Builds a new SESE region from edges ENTRY and EXIT. */
-sese
-new_sese (edge entry, edge exit)
+sese_info_p
+new_sese_info (edge entry, edge exit)
{
- sese region = XNEW (struct sese_s);
+ sese_info_p region = XNEW (class sese_info_t);
- SESE_ENTRY (region) = entry;
- SESE_EXIT (region) = exit;
- SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
- SESE_LOOP_NEST (region).create (3);
- SESE_ADD_PARAMS (region) = true;
- SESE_PARAMS (region).create (3);
+ region->region.entry = entry;
+ region->region.exit = exit;
+ region->liveout = NULL;
+ region->debug_liveout = NULL;
+ region->params.create (3);
+ region->rename_map = new hash_map <tree, tree>;
+ region->bbs.create (3);
return region;
}
/* Deletes REGION. */
void
-free_sese (sese region)
+free_sese_info (sese_info_p region)
{
- if (SESE_LOOPS (region))
- SESE_LOOPS (region) = BITMAP_ALLOC (NULL);
+ region->params.release ();
+ BITMAP_FREE (region->liveout);
+ BITMAP_FREE (region->debug_liveout);
- SESE_PARAMS (region).release ();
- SESE_LOOP_NEST (region).release ();
+ delete region->rename_map;
+ region->rename_map = NULL;
+ region->bbs.release ();
XDELETE (region);
}
create_new_def_for (use, phi, gimple_phi_result_ptr (phi));
add_phi_arg (phi, use, false_e, UNKNOWN_LOCATION);
add_phi_arg (phi, use, true_e, UNKNOWN_LOCATION);
+ update_stmt (phi);
}
/* Insert in the block BB phi nodes for variables defined in REGION
*/
void
-sese_insert_phis_for_liveouts (sese region, basic_block bb,
+sese_insert_phis_for_liveouts (sese_info_p region, basic_block bb,
edge false_e, edge true_e)
{
+ if (MAY_HAVE_DEBUG_BIND_STMTS)
+ sese_reset_debug_liveouts (region);
+
unsigned i;
bitmap_iterator bi;
- bitmap liveouts = BITMAP_ALLOC (NULL);
+ EXECUTE_IF_SET_IN_BITMAP (region->liveout, 0, i, bi)
+ if (!virtual_operand_p (ssa_name (i)))
+ sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
+}
+
+/* Returns the outermost loop in SCOP that contains BB. */
- update_ssa (TODO_update_ssa);
+class loop *
+outermost_loop_in_sese_1 (sese_l ®ion, basic_block bb)
+{
+ class loop *nest;
- sese_build_liveouts (region, liveouts);
- EXECUTE_IF_SET_IN_BITMAP (liveouts, 0, i, bi)
- sese_add_exit_phis_edge (bb, ssa_name (i), false_e, true_e);
- BITMAP_FREE (liveouts);
+ nest = bb->loop_father;
+ while (loop_outer (nest)
+ && loop_in_sese_p (loop_outer (nest), region))
+ nest = loop_outer (nest);
- update_ssa (TODO_update_ssa);
+ return nest;
+}
+
+/* Same as outermost_loop_in_sese_1, returns the outermost loop
+ containing BB in REGION, but makes sure that the returned loop
+ belongs to the REGION, and so this returns the first loop in the
+ REGION when the loop containing BB does not belong to REGION. */
+
+loop_p
+outermost_loop_in_sese (sese_l ®ion, basic_block bb)
+{
+ loop_p nest = outermost_loop_in_sese_1 (region, bb);
+
+ if (loop_in_sese_p (nest, region))
+ return nest;
+
+ /* When the basic block BB does not belong to a loop in the region,
+ return the first loop in the region. */
+ nest = nest->inner;
+ while (nest)
+ if (loop_in_sese_p (nest, region))
+ break;
+ else
+ nest = nest->next;
+
+ gcc_assert (nest);
+ return nest;
}
/* Returns the first successor edge of BB with EDGE_TRUE_VALUE flag set. */
return NULL;
}
-/* Returns the expression associated to OLD_NAME in RENAME_MAP. */
+/* Moves REGION in a condition expression:
+ | if (1)
+ | ;
+ | else
+ | REGION;
+*/
-static tree
-get_rename (rename_map_type *rename_map, tree old_name)
+ifsese
+move_sese_in_condition (sese_info_p region)
{
- gcc_assert (TREE_CODE (old_name) == SSA_NAME);
- tree *expr = rename_map->get (old_name);
- if (expr)
- return *expr;
+ basic_block region_entry_dest = region->region.entry->dest;
+ basic_block pred_block = split_edge (region->region.entry);
+ basic_block merge_block = split_edge (region->region.exit);
+
+ edge true_edge = make_edge (pred_block, merge_block, EDGE_TRUE_VALUE);
+ edge false_edge = find_edge (pred_block, region_entry_dest);
+ false_edge->flags &= ~EDGE_FALLTHRU;
+ false_edge->flags |= EDGE_FALSE_VALUE;
+ gimple_stmt_iterator gsi = gsi_last_bb (pred_block);
+ gcond *cond = gimple_build_cond (NE_EXPR, integer_one_node, integer_zero_node,
+ NULL_TREE, NULL_TREE);
+ gsi_insert_after (&gsi, cond, GSI_CONTINUE_LINKING);
+ if (dom_info_available_p (CDI_DOMINATORS))
+ set_immediate_dominator (CDI_DOMINATORS, merge_block, pred_block);
+
+ ifsese if_region = XNEW (ifsese_s);
+ if_region->region = XCNEW (sese_info_t);
+ if_region->true_region = XCNEW (sese_info_t);
+ if_region->false_region = XCNEW (sese_info_t);
+ if_region->region->region.entry = single_pred_edge (pred_block);
+ if_region->region->region.exit = single_succ_edge (merge_block);
+ if_region->false_region->region.entry = false_edge;
+ if_region->false_region->region.exit = region->region.exit;
+ if_region->true_region->region.entry = true_edge;
+ if_region->true_region->region.exit
+ = single_succ_edge (split_edge (true_edge));
+
+ region->region = if_region->false_region->region;
- return NULL_TREE;
+ return if_region;
}
-/* Register in RENAME_MAP the rename tuple (OLD_NAME, EXPR). */
+/* Replaces the condition of the IF_REGION with CONDITION:
+ | if (CONDITION)
+ | true_region;
+ | else
+ | false_region;
+*/
-static void
-set_rename (rename_map_type *rename_map, tree old_name, tree expr)
+void
+set_ifsese_condition (ifsese if_region, tree condition)
{
- if (old_name == expr)
- return;
+ sese_info_p region = if_region->region;
+ edge entry = region->region.entry;
+ basic_block bb = entry->dest;
+ gimple *last = last_stmt (bb);
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ gcond *cond_stmt;
- rename_map->put (old_name, expr);
+ gcc_assert (gimple_code (last) == GIMPLE_COND);
+
+ gsi_remove (&gsi, true);
+ gsi = gsi_last_bb (bb);
+ condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
+ false, GSI_NEW_STMT);
+ cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
+ gsi = gsi_last_bb (bb);
+ gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
}
-/* Renames the scalar uses of the statement COPY, using the
- substitution map RENAME_MAP, inserting the gimplification code at
- GSI_TGT, for the translation REGION, with the original copied
- statement in LOOP, and using the induction variable renaming map
- IV_MAP. Returns true when something has been renamed. GLOOG_ERROR
- is set when the code generation cannot continue. */
-
-static bool
-rename_uses (gimple copy, rename_map_type *rename_map,
- gimple_stmt_iterator *gsi_tgt,
- sese region, loop_p loop, vec<tree> iv_map,
- bool *gloog_error)
+/* Return true when T is defined outside REGION or when no definitions are
+ variant in REGION. When HAS_VDEFS is a valid pointer, sets HAS_VDEFS to true
+ when T depends on memory that may change in REGION. */
+
+bool
+invariant_in_sese_p_rec (tree t, const sese_l ®ion, bool *has_vdefs)
{
- use_operand_p use_p;
- ssa_op_iter op_iter;
- bool changed = false;
+ if (!defined_in_sese_p (t, region))
+ return true;
- if (is_gimple_debug (copy))
- {
- if (gimple_debug_bind_p (copy))
- gimple_debug_bind_reset_value (copy);
- else if (gimple_debug_source_bind_p (copy))
- return false;
- else
- gcc_unreachable ();
+ gimple *stmt = SSA_NAME_DEF_STMT (t);
- return false;
- }
+ if (gimple_code (stmt) == GIMPLE_PHI
+ || gimple_code (stmt) == GIMPLE_CALL)
+ return false;
- FOR_EACH_SSA_USE_OPERAND (use_p, copy, op_iter, SSA_OP_USE)
+ /* VDEF is variant when it is in the region. */
+ if (gimple_vdef (stmt))
{
- tree old_name = USE_FROM_PTR (use_p);
- tree new_expr, scev;
- gimple_seq stmts;
-
- if (TREE_CODE (old_name) != SSA_NAME
- || SSA_NAME_IS_DEFAULT_DEF (old_name))
- continue;
-
- changed = true;
- new_expr = get_rename (rename_map, old_name);
- if (new_expr)
- {
- tree type_old_name = TREE_TYPE (old_name);
- tree type_new_expr = TREE_TYPE (new_expr);
-
- if (type_old_name != type_new_expr
- || TREE_CODE (new_expr) != SSA_NAME)
- {
- tree var = create_tmp_var (type_old_name, "var");
-
- if (!useless_type_conversion_p (type_old_name, type_new_expr))
- new_expr = fold_convert (type_old_name, new_expr);
-
- new_expr = force_gimple_operand (new_expr, &stmts, true, var);
- gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
- }
-
- replace_exp (use_p, new_expr);
- continue;
- }
-
- scev = scalar_evolution_in_region (region, loop, old_name);
-
- /* At this point we should know the exact scev for each
- scalar SSA_NAME used in the scop: all the other scalar
- SSA_NAMEs should have been translated out of SSA using
- arrays with one element. */
- if (chrec_contains_undetermined (scev))
- {
- *gloog_error = true;
- new_expr = build_zero_cst (TREE_TYPE (old_name));
- }
- else
- new_expr = chrec_apply_map (scev, iv_map);
-
- /* The apply should produce an expression tree containing
- the uses of the new induction variables. We should be
- able to use new_expr instead of the old_name in the newly
- generated loop nest. */
- if (chrec_contains_undetermined (new_expr)
- || tree_contains_chrecs (new_expr, NULL))
- {
- *gloog_error = true;
- new_expr = build_zero_cst (TREE_TYPE (old_name));
- }
- else
- /* Replace the old_name with the new_expr. */
- new_expr = force_gimple_operand (unshare_expr (new_expr), &stmts,
- true, NULL_TREE);
-
- gsi_insert_seq_before (gsi_tgt, stmts, GSI_SAME_STMT);
- replace_exp (use_p, new_expr);
-
- if (TREE_CODE (new_expr) == INTEGER_CST
- && is_gimple_assign (copy))
- {
- tree rhs = gimple_assign_rhs1 (copy);
-
- if (TREE_CODE (rhs) == ADDR_EXPR)
- recompute_tree_invariant_for_addr_expr (rhs);
- }
-
- set_rename (rename_map, old_name, new_expr);
+ if (has_vdefs)
+ *has_vdefs = true;
+ return false;
}
- return changed;
-}
-
-/* Duplicates the statements of basic block BB into basic block NEW_BB
- and compute the new induction variables according to the IV_MAP.
- GLOOG_ERROR is set when the code generation cannot continue. */
+ /* A VUSE may or may not be variant following the VDEFs. */
+ if (tree vuse = gimple_vuse (stmt))
+ return invariant_in_sese_p_rec (vuse, region, has_vdefs);
-static void
-graphite_copy_stmts_from_block (basic_block bb, basic_block new_bb,
- rename_map_type *rename_map,
- vec<tree> iv_map, sese region,
- bool *gloog_error)
-{
- gimple_stmt_iterator gsi, gsi_tgt;
- loop_p loop = bb->loop_father;
-
- gsi_tgt = gsi_start_bb (new_bb);
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ ssa_op_iter iter;
+ use_operand_p use_p;
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
- def_operand_p def_p;
- ssa_op_iter op_iter;
- gimple stmt = gsi_stmt (gsi);
- gimple copy;
- tree lhs;
-
- /* Do not copy labels or conditions. */
- if (gimple_code (stmt) == GIMPLE_LABEL
- || gimple_code (stmt) == GIMPLE_COND)
- continue;
+ tree use = USE_FROM_PTR (use_p);
- /* Do not copy induction variables. */
- if (is_gimple_assign (stmt)
- && (lhs = gimple_assign_lhs (stmt))
- && TREE_CODE (lhs) == SSA_NAME
- && is_gimple_reg (lhs)
- && scev_analyzable_p (lhs, region))
+ if (!defined_in_sese_p (use, region))
continue;
- /* Create a new copy of STMT and duplicate STMT's virtual
- operands. */
- copy = gimple_copy (stmt);
- gsi_insert_after (&gsi_tgt, copy, GSI_NEW_STMT);
-
- maybe_duplicate_eh_stmt (copy, stmt);
- gimple_duplicate_stmt_histograms (cfun, copy, cfun, stmt);
-
- /* Create new names for all the definitions created by COPY and
- add replacement mappings for each new name. */
- FOR_EACH_SSA_DEF_OPERAND (def_p, copy, op_iter, SSA_OP_ALL_DEFS)
- {
- tree old_name = DEF_FROM_PTR (def_p);
- tree new_name = create_new_def_for (old_name, copy, def_p);
- set_rename (rename_map, old_name, new_name);
- }
-
- if (rename_uses (copy, rename_map, &gsi_tgt, region, loop, iv_map,
- gloog_error))
- {
- gcc_assert (gsi_stmt (gsi_tgt) == copy);
- fold_stmt_inplace (&gsi_tgt);
- }
-
- update_stmt (copy);
+ if (!invariant_in_sese_p_rec (use, region, has_vdefs))
+ return false;
}
-}
-
-/* Copies BB and includes in the copied BB all the statements that can
- be reached following the use-def chains from the memory accesses,
- and returns the next edge following this new block. GLOOG_ERROR is
- set when the code generation cannot continue. */
-
-edge
-copy_bb_and_scalar_dependences (basic_block bb, sese region,
- edge next_e, vec<tree> iv_map,
- bool *gloog_error)
-{
- basic_block new_bb = split_edge (next_e);
- rename_map_type rename_map (10);
- next_e = single_succ_edge (new_bb);
- graphite_copy_stmts_from_block (bb, new_bb, &rename_map, iv_map, region,
- gloog_error);
- remove_phi_nodes (new_bb);
-
- return next_e;
+ return true;
}
-/* Returns the outermost loop in SCOP that contains BB. */
+/* Return true when DEF can be analyzed in REGION by the scalar
+ evolution analyzer. */
-struct loop *
-outermost_loop_in_sese (sese region, basic_block bb)
+bool
+scev_analyzable_p (tree def, sese_l ®ion)
{
- struct loop *nest;
+ loop_p loop;
+ tree scev;
+ tree type = TREE_TYPE (def);
+
+ /* When Graphite generates code for a scev, the code generator
+ expresses the scev in function of a single induction variable.
+ This is unsafe for floating point computations, as it may replace
+ a floating point sum reduction with a multiplication. The
+ following test returns false for non integer types to avoid such
+ problems. */
+ if (!INTEGRAL_TYPE_P (type)
+ && !POINTER_TYPE_P (type))
+ return false;
- nest = bb->loop_father;
- while (loop_outer (nest)
- && loop_in_sese_p (loop_outer (nest), region))
- nest = loop_outer (nest);
+ loop = loop_containing_stmt (SSA_NAME_DEF_STMT (def));
+ scev = scalar_evolution_in_region (region, loop, def);
- return nest;
+ return (!chrec_contains_undetermined (scev)
+ && (TREE_CODE (scev) != SSA_NAME
+ || !defined_in_sese_p (scev, region))
+ && scev_is_linear_expression (scev)
+ && (! loop
+ || ! loop_in_sese_p (loop, region)
+ || ! chrec_contains_symbols_defined_in_loop (scev, loop->num)));
}
-/* Sets the false region of an IF_REGION to REGION. */
+/* Returns the scalar evolution of T in REGION. Every variable that
+ is not defined in the REGION is considered a parameter. */
-void
-if_region_set_false_region (ifsese if_region, sese region)
+tree
+scalar_evolution_in_region (const sese_l ®ion, loop_p loop, tree t)
{
- basic_block condition = if_region_get_condition_block (if_region);
- edge false_edge = get_false_edge_from_guard_bb (condition);
- basic_block dummy = false_edge->dest;
- edge entry_region = SESE_ENTRY (region);
- edge exit_region = SESE_EXIT (region);
- basic_block before_region = entry_region->src;
- basic_block last_in_region = exit_region->src;
- hashval_t hash = htab_hash_pointer (exit_region);
- loop_exit **slot
- = current_loops->exits->find_slot_with_hash (exit_region, hash, NO_INSERT);
-
- entry_region->flags = false_edge->flags;
- false_edge->flags = exit_region->flags;
-
- redirect_edge_pred (entry_region, condition);
- redirect_edge_pred (exit_region, before_region);
- redirect_edge_pred (false_edge, last_in_region);
- redirect_edge_succ (false_edge, single_succ (dummy));
- delete_basic_block (dummy);
-
- exit_region->flags = EDGE_FALLTHRU;
- recompute_all_dominators ();
-
- SESE_EXIT (region) = false_edge;
-
- free (if_region->false_region);
- if_region->false_region = region;
-
- if (slot)
- {
- struct loop_exit *loop_exit = ggc_cleared_alloc<struct loop_exit> ();
+ /* SCOP parameters. */
+ if (TREE_CODE (t) == SSA_NAME
+ && !defined_in_sese_p (t, region))
+ return t;
- memcpy (loop_exit, *((struct loop_exit **) slot), sizeof (struct loop_exit));
- current_loops->exits->clear_slot (slot);
+ if (!loop_in_sese_p (loop, region))
+ loop = NULL;
- hashval_t hash = htab_hash_pointer (false_edge);
- slot = current_loops->exits->find_slot_with_hash (false_edge, hash,
- INSERT);
- loop_exit->e = false_edge;
- *slot = loop_exit;
- false_edge->src->loop_father->exits->next = loop_exit;
- }
+ return instantiate_scev (region.entry, loop,
+ analyze_scalar_evolution (loop, t));
}
-/* Creates an IFSESE with CONDITION on edge ENTRY. */
+/* Return true if BB is empty, contains only DEBUG_INSNs. */
-static ifsese
-create_if_region_on_edge (edge entry, tree condition)
-{
- edge e;
- edge_iterator ei;
- sese sese_region = XNEW (struct sese_s);
- sese true_region = XNEW (struct sese_s);
- sese false_region = XNEW (struct sese_s);
- ifsese if_region = XNEW (struct ifsese_s);
- edge exit = create_empty_if_region_on_edge (entry, condition);
-
- if_region->region = sese_region;
- if_region->region->entry = entry;
- if_region->region->exit = exit;
+bool
+sese_trivially_empty_bb_p (basic_block bb)
+{
+ gimple_stmt_iterator gsi;
- FOR_EACH_EDGE (e, ei, entry->dest->succs)
- {
- if (e->flags & EDGE_TRUE_VALUE)
- {
- true_region->entry = e;
- true_region->exit = single_succ_edge (e->dest);
- if_region->true_region = true_region;
- }
- else if (e->flags & EDGE_FALSE_VALUE)
- {
- false_region->entry = e;
- false_region->exit = single_succ_edge (e->dest);
- if_region->false_region = false_region;
- }
- }
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ if (!is_gimple_debug (gsi_stmt (gsi))
+ && gimple_code (gsi_stmt (gsi)) != GIMPLE_LABEL)
+ return false;
- return if_region;
+ return true;
}
-/* Moves REGION in a condition expression:
- | if (1)
- | ;
- | else
- | REGION;
-*/
+/* Pretty print edge E to FILE. */
-ifsese
-move_sese_in_condition (sese region)
+void
+print_edge (FILE *file, const_edge e)
{
- basic_block pred_block = split_edge (SESE_ENTRY (region));
- ifsese if_region;
-
- SESE_ENTRY (region) = single_succ_edge (pred_block);
- if_region = create_if_region_on_edge (single_pred_edge (pred_block), integer_one_node);
- if_region_set_false_region (if_region, region);
-
- return if_region;
+ fprintf (file, "edge (bb_%d, bb_%d)", e->src->index, e->dest->index);
}
-/* Replaces the condition of the IF_REGION with CONDITION:
- | if (CONDITION)
- | true_region;
- | else
- | false_region;
-*/
+/* Pretty print sese S to FILE. */
void
-set_ifsese_condition (ifsese if_region, tree condition)
+print_sese (FILE *file, const sese_l &s)
{
- sese region = if_region->region;
- edge entry = region->entry;
- basic_block bb = entry->dest;
- gimple last = last_stmt (bb);
- gimple_stmt_iterator gsi = gsi_last_bb (bb);
- gcond *cond_stmt;
-
- gcc_assert (gimple_code (last) == GIMPLE_COND);
-
- gsi_remove (&gsi, true);
- gsi = gsi_last_bb (bb);
- condition = force_gimple_operand_gsi (&gsi, condition, true, NULL,
- false, GSI_NEW_STMT);
- cond_stmt = gimple_build_cond_from_tree (condition, NULL_TREE, NULL_TREE);
- gsi = gsi_last_bb (bb);
- gsi_insert_after (&gsi, cond_stmt, GSI_NEW_STMT);
+ fprintf (file, "(entry_"); print_edge (file, s.entry);
+ fprintf (file, ", exit_"); print_edge (file, s.exit);
+ fprintf (file, ")\n");
}
-/* Returns the scalar evolution of T in REGION. Every variable that
- is not defined in the REGION is considered a parameter. */
+/* Pretty print edge E to STDERR. */
-tree
-scalar_evolution_in_region (sese region, loop_p loop, tree t)
+DEBUG_FUNCTION void
+debug_edge (const_edge e)
{
- gimple def;
- struct loop *def_loop;
- basic_block before = block_before_sese (region);
-
- /* SCOP parameters. */
- if (TREE_CODE (t) == SSA_NAME
- && !defined_in_sese_p (t, region))
- return t;
-
- if (TREE_CODE (t) != SSA_NAME
- || loop_in_sese_p (loop, region))
- return instantiate_scev (before, loop,
- analyze_scalar_evolution (loop, t));
+ print_edge (stderr, e);
+}
- def = SSA_NAME_DEF_STMT (t);
- def_loop = loop_containing_stmt (def);
+/* Pretty print sese S to STDERR. */
- if (loop_in_sese_p (def_loop, region))
- {
- t = analyze_scalar_evolution (def_loop, t);
- def_loop = superloop_at_depth (def_loop, loop_depth (loop) + 1);
- t = compute_overall_effect_of_inner_loop (def_loop, t);
- return t;
- }
- else
- return instantiate_scev (before, loop, t);
+DEBUG_FUNCTION void
+debug_sese (const sese_l &s)
+{
+ print_sese (stderr, s);
}
projects / thirdparty / gcc.git / blobdiff