Preserve the original program while using graphite.

Earlier, graphite used to translate portions of the original program after
scop-detection in order to represent the SCoP into polyhedral model.  This was
required because each basic block was represented as independent basic block in
the polyhedral model. So all the cross-basic-block dependencies were translated
out-of-ssa.

With this patch those dependencies are also exposed to the ISL, so there is no
need to modify the original structure of the program.

After this patch we should be able to enable graphite at some default
optimization level.

Highlights:
Remove cross bb scalar to array translation
For reductions, add support for more than just INT_CST
Early bailout on codegen.
Verify loop-closed ssa structure during copy of renames
The uses of exprs should come from bb which dominates the bb
Collect the init value of close phi in loop-guard
Do not follow vuses for close-phi, postpone loop-close phi until the
    corresponding loop-phi is processed
Bail out if no bb found to place cond/loop -phis
Move insertion of liveouts at the end of codegen
Insert loop-phis in the loop-header.

This patch passes regtest and bootstrap with BOOT_CFLAGS='-O2 -fgraphite-identity -floop-nest-optimize'

2015-11-11  Aditya Kumar  <aditya.k7@samsung.com>
      Sebastian Pop  <s.pop@samsung.com>

	* graphite-isl-ast-to-gimple.c (class translate_isl_ast_to_gimple):
	  New member codegen_error
	(translate_isl_ast_for_loop): Remove call to single_succ_edge and early return.
	(translate_isl_ast_node_user): Early return in case of error.
	(translate_isl_ast_to_gimple::translate_isl_ast): Same.
	(translate_isl_ast_to_gimple::translate_pending_phi_nodes): New.
	(add_parameters_to_ivs_params): Remove macro.
	(graphite_regenerate_ast_isl): Add if_region pointer to region.
	* graphite-poly.c (new_poly_dr): Remove macro.
	(print_pdr): Same.
	(new_gimple_poly_bb): Same.
	(free_gimple_poly_bb): Same.
	(print_scop_params): Same.
	* graphite-poly.h (struct poly_dr): Same.
	(struct poly_bb): Add new_bb.
	(gbb_from_bb): Remove dead code.
	(pbb_from_bb): Same.
	* graphite-scop-detection.c (parameter_index_in_region_1): Same.
	(parameter_index_in_region): Same.
	(find_scop_parameters): Same.
	(build_cross_bb_scalars_def): New.
	(build_cross_bb_scalars_use): New.
	(graphite_find_cross_bb_scalar_vars): New
	(try_generate_gimple_bb): Reads and Writes.
	(build_alias_set): Move.
	(gather_bbs::before_dom_children): Gather bbs visited.
	(build_scops): call build_alias_set.
	* graphite-sese-to-poly.c (phi_arg_in_outermost_loop): Delete.
	(remove_simple_copy_phi): Delete.
	(remove_invariant_phi): Delete.
	(simple_copy_phi_p): Delete.
	(reduction_phi_p): Delete.
	(isl_id_for_dr): Remove unused param.
	(parameter_index_in_region_1): Remove macro usage.
	(set_scop_parameter_dim): Same.
	(add_param_constraints): Same.
	(add_conditions_to_constraints): Same
	(build_scop_iteration_domain): Same.
	(pdr_add_alias_set): Comment.
	(add_scalar_version_numbers): New.
	(build_poly_dr): ISL id.
	(build_scop_drs): Move.
	(build_poly_sr_1): Same.
	(insert_stmts): Remove.
	(build_poly_sr): New.
	(new_pbb_from_pbb): Delete.
	(insert_out_of_ssa_copy_on_edge): Delete.
	(create_zero_dim_array): Delete.
	(scalar_close_phi_node_p): Delete.
	(propagate_expr_outside_region): Delete.
	(rewrite_close_phi_out_of_ssa): Delete.
	(rewrite_phi_out_of_ssa): Delete.
	(rewrite_degenerate_phi): Delete.
	(rewrite_reductions_out_of_ssa): Delete.
	(rewrite_cross_bb_scalar_dependence): Delete.
	(handle_scalar_deps_crossing_scop_limits):
	(rewrite_cross_bb_scalar_deps): Delete.
	(build_poly_scop): Remove calls to out-of-ssa functions.
	* graphite.c (graphite_transform_loops): Early return in case of codegen error.
	* sese.c (debug_rename_map_1): Delete.
	(debug_rename_map): Delete.
	(sese_record_loop): Remove macro.
	(build_sese_loop_nests): Same.
	(new_sese_info): Same.
	(free_sese_info): Same.
	(sese_insert_phis_for_liveouts):
	(is_loop_closed_ssa_use): New.
	(number_of_phi_nodes): New.
	(bb_contains_loop_close_phi_nodes): New.
	(bb_contains_loop_phi_nodes): New.
	(phi_uses_name): New.
	(is_valid_rename):
	(get_rename): Add old_bb and loop_phi for more precise matching of
	exprs.
	(set_rename): Pass region.
	(later_of_the_two): New.
	(gsi_insert_earliest): New.
	(collect_all_ssa_names): New.
	(substitute_ssa_name): New.
	(rename_all_uses): New.
	(get_rename_from_scev): New.
	(rename_uses): Pass old_bb for more precise matching of exprs.
	(get_def_bb_for_const): New.
	(get_new_name): New.
	(get_loc): New.
	(get_edges): New.
	(copy_loop_phi_args): New.
	(copy_loop_phi_nodes): New.
	(get_loop_init_value): New.
	(find_init_value): New.
	(find_init_value_close_phi): New.
	(copy_loop_close_phi_args): New.
	(copy_loop_close_phi_nodes): New.
	(add_phi_arg_for_new_expr): New.
	(copy_cond_phi_args): New.
	(copy_cond_phi_nodes): New.
	(copy_phi_nodes): New.
	(should_copy_to_new_region): New.
	(set_rename_for_each_def): New.
	(graphite_copy_stmts_from_block): Early return in case of error.
	(copy_bb_and_scalar_dependences): Same.
	* sese.h (vec_find): New.
	(SESE_PARAMS): Delete.
	(SESE_LOOPS): Delete.
	(SESE_LOOP_NEST): Delete.
	(sese_contains_loop): Remove macro usage.
	(sese_nb_params): Same.
	(struct gimple_poly_bb): Added read_scalar_refs, write_scalar_refs.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@230200 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 152 insertions, 9 deletions

diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index 9fb82645501..a7179d97d89 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -1507,7 +1507,7 @@ parameter_index_in_region_1 (tree name, sese_info_p region)
 
   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;
 
@@ -1536,8 +1536,8 @@ parameter_index_in_region (tree name, sese_info_p region)
   if (i != -1)
     return i;
 
-  i = SESE_PARAMS (region).length ();
-  SESE_PARAMS (region).safe_push (name);
+  i = region->params.length ();
+  region->params.safe_push (name);
   return i;
 }
 
@@ -1635,7 +1635,7 @@ find_scop_parameters (scop_p scop)
   struct loop *loop;
 
   /* Find the parameters used in the loop bounds.  */
-  FOR_EACH_VEC_ELT (SESE_LOOP_NEST (region), i, loop)
+  FOR_EACH_VEC_ELT (region->loop_nest, i, loop)
     {
       tree nb_iters = number_of_latch_executions (loop);
 
@@ -1655,6 +1655,94 @@ find_scop_parameters (scop_p scop)
   scop_set_nb_params (scop, nbp);
 }
 
+/* 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)
+{
+  gcc_assert (def);
+  if (!is_gimple_reg (def))
+    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 (def, scop->scop_info->region))
+    return;
+
+  gimple *use_stmt;
+  imm_use_iterator imm_iter;
+  FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def)
+    if (def_bb != gimple_bb (use_stmt) && !is_gimple_debug (use_stmt))
+      {
+	writes->safe_push (def);
+	DEBUG_PRINT (dp << "Adding scalar write:\n";
+		     print_generic_expr (dump_file, def, 0);
+		     dp << "From stmt:\n";
+		     print_gimple_stmt (dump_file,
+					SSA_NAME_DEF_STMT (def), 0, 0));
+	/* This is required by the FOR_EACH_IMM_USE_STMT when we want to break
+	   before all the uses have been visited.  */
+	BREAK_FROM_IMM_USE_STMT (imm_iter);
+      }
+}
+
+/* Record DEF if it is used in other bbs different than DEF_BB in the SCOP.  */
+
+static void
+build_cross_bb_scalars_use (scop_p scop, tree use, gimple *use_stmt,
+			    vec<scalar_use> *reads)
+{
+  gcc_assert (use);
+  if (!is_gimple_reg (use))
+    return;
+
+  /* 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))
+    {
+      DEBUG_PRINT (dp << "Adding scalar read:\n";
+		   print_generic_expr (dump_file, use, 0);
+		   dp << "From stmt:\n";
+		   print_gimple_stmt (dump_file, use_stmt, 0, 0));
+      reads->safe_push (std::make_pair (use_stmt, use));
+    }
+}
+
+/* Record all scalar variables that are defined and used in different BBs of the
+   SCOP.  */
+
+static void
+graphite_find_cross_bb_scalar_vars (scop_p scop, gimple *stmt,
+				    vec<scalar_use> *reads, vec<tree> *writes)
+{
+  tree def;
+
+  if (gimple_code (stmt) == GIMPLE_ASSIGN)
+    def = gimple_assign_lhs (stmt);
+  else if (gimple_code (stmt) == GIMPLE_CALL)
+    def = gimple_call_lhs (stmt);
+  else if (gimple_code (stmt) == GIMPLE_PHI)
+    def = gimple_phi_result (stmt);
+  else
+    return;
+
+
+  build_cross_bb_scalars_def (scop, def, gimple_bb (stmt), writes);
+
+  ssa_op_iter iter;
+  use_operand_p use_p;
+  FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, iter, SSA_OP_USE)
+    {
+      tree use = USE_FROM_PTR (use_p);
+      build_cross_bb_scalars_use (scop, use, stmt, reads);
+    }
+}
+
 /* Generates a polyhedral black box only if the bb contains interesting
    information.  */
 
@@ -1662,7 +1750,12 @@ static gimple_poly_bb_p
 try_generate_gimple_bb (scop_p scop, basic_block bb)
 {
   vec<data_reference_p> drs;
-  drs.create (5);
+  drs.create (3);
+  vec<tree> writes;
+  writes.create (3);
+  vec<scalar_use> reads;
+  reads.create (3);
+
   sese_l region = scop->scop_info->region;
   loop_p nest = outermost_loop_in_sese (region, bb);
 
@@ -1670,17 +1763,58 @@ try_generate_gimple_bb (scop_p scop, basic_block bb)
   if (!loop_in_sese_p (loop, region))
     loop = nest;
 
-  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);
+      graphite_find_cross_bb_scalar_vars (scop, stmt, &reads, &writes);
     }
 
-  return new_gimple_poly_bb (bb, drs);
+  for (gphi_iterator psi = gsi_start_phis (bb); !gsi_end_p (psi);
+       gsi_next (&psi))
+    if (!virtual_operand_p (gimple_phi_result (psi.phi ())))
+      graphite_find_cross_bb_scalar_vars (scop, psi.phi (), &reads, &writes);
+
+  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 void
+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;
+
+  FOR_EACH_VEC_ELT (scop->drs, i, dr1)
+    for (j = i+1; scop->drs.iterate (j, &dr2); j++)
+      if (dr_may_alias_p (dr1->dr, dr2->dr, true))
+	{
+	  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;
+
+  graphds_dfs (g, all_vertices, num_vertices, NULL, true, NULL);
+  free (all_vertices);
+
+  for (i = 0; i < g->n_vertices; i++)
+    scop->drs[i].alias_set = g->vertices[i].component + 1;
+
+  free_graph (g);
 }
 
 /* Gather BBs and conditions for a SCOP.  */
@@ -1728,11 +1862,19 @@ gather_bbs::before_dom_children (basic_block bb)
   scop->scop_info->bbs.safe_push (bb);
 
   gimple_poly_bb_p gbb = try_generate_gimple_bb (scop, bb);
+  if (!gbb)
+    return;
+
   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)
+    scop->drs.safe_push (dr_info (dr, pbb));
 }
 
 /* Call-back for dom_walk executed after visiting the dominated
@@ -1776,6 +1918,8 @@ build_scops (vec<scop_p> *scops)
       /* Record all basic blocks and their conditions in REGION.  */
       gather_bbs (CDI_DOMINATORS, scop).walk (cfun->cfg->x_entry_block_ptr);
 
+      build_alias_set (scop);
+
       /* Do not optimize a scop containing only PBBs that do not belong
 	 to any loops.  */
       if (sb.nb_pbbs_in_loops (scop) == 0)
@@ -1807,7 +1951,6 @@ build_scops (vec<scop_p> *scops)
 		          << scop_nb_params (scop)
 		          << " larger than --param graphite-max-nb-scop-params="
 		          << max_dim << ".\n");
-
 	  free_scop (scop);
 	  continue;
 	}