[graphite] fix code generation fails

["Sebastian Pop" <sebpop at gmail dot com>]

Hi,

I just committed the attached patch from Jan that fixes the out of
graphite fails from the C testsuite.  The only fail that remains is
block-1.f90 that will require some more changes to make it work
correctly.

Sebastian Pop
--
AMD - GNU Tools

Index: tree-phinodes.c
===================================================================
--- tree-phinodes.c	(revision 139502)
+++ tree-phinodes.c	(working copy)
@@ -202,10 +202,9 @@ ideal_phi_node_len (int len)
   return new_len;
 }
 
-
 /* Return a PHI node with LEN argument slots for variable VAR.  */
 
-static gimple
+gimple
 make_phi_node (tree var, int len)
 {
   gimple phi;
@@ -348,15 +347,12 @@ reserve_phi_args_for_new_edge (basic_blo
     }
 }
 
+/* Adds PHI to BB.  */
 
-/* Create a new PHI node for variable VAR at basic block BB.  */
-
-gimple
-create_phi_node (tree var, basic_block bb)
+void 
+add_phi_node_to_bb (gimple phi, basic_block bb)
 {
   gimple_stmt_iterator gsi;
-  gimple phi = make_phi_node (var, EDGE_COUNT (bb->preds));
-
   /* Add the new PHI node to the list of PHI nodes for block BB.  */
   if (phi_nodes (bb) == NULL)
     set_phi_nodes (bb, gimple_seq_alloc ());
@@ -367,6 +363,16 @@ create_phi_node (tree var, basic_block b
   /* Associate BB to the PHI node.  */
   gimple_set_bb (phi, bb);
 
+}
+
+/* Create a new PHI node for variable VAR at basic block BB.  */
+
+gimple
+create_phi_node (tree var, basic_block bb)
+{
+  gimple phi = make_phi_node (var, EDGE_COUNT (bb->preds));
+
+  add_phi_node_to_bb (phi, bb);
   return phi;
 }
 
Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c	(revision 139502)
+++ tree-ssa-loop-ivopts.c	(working copy)
@@ -5002,18 +5002,38 @@ create_new_ivs (struct ivopts_data *data
     }
 }
 
+/* Returns the phi-node in BB with result RESULT.  */
+
+static gimple
+get_phi_with_result (basic_block bb, tree result)
+{
+  gimple_stmt_iterator i = gsi_start_phis (bb);
+
+  for (; !gsi_end_p (i); gsi_next (&i))
+    if (gimple_phi_result (gsi_stmt (i)) == result)
+      return gsi_stmt (i);
+
+  gcc_unreachable ();
+  return NULL;
+}
+
+
 /* Removes statement STMT (real or a phi node).  If INCLUDING_DEFINED_NAME
    is true, remove also the ssa name defined by the statement.  */
 
 static void
 remove_statement (gimple stmt, bool including_defined_name)
 {
-  gimple_stmt_iterator bsi = gsi_for_stmt (stmt);
-
   if (gimple_code (stmt) == GIMPLE_PHI)
-    remove_phi_node (&bsi, including_defined_name);
+    {
+      gimple bb_phi = get_phi_with_result (gimple_bb (stmt), 
+					 gimple_phi_result (stmt));
+      gimple_stmt_iterator bsi = gsi_for_stmt (bb_phi);
+      remove_phi_node (&bsi, including_defined_name);
+    }
   else
     {
+      gimple_stmt_iterator bsi = gsi_for_stmt (stmt);
       gsi_remove (&bsi, true);
       release_defs (stmt); 
     }
Index: graphite.c
===================================================================
--- graphite.c	(revision 139608)
+++ graphite.c	(working copy)
@@ -78,7 +78,7 @@ void debug_loop_vec (graphite_bb_p gb)
   int i;
   loop_p loop;
 
-  fprintf(stderr, "Loop Vec:");
+  fprintf (stderr, "Loop Vec:");
 
   for (i=0; VEC_iterate (loop_p, GBB_LOOPS (gb), i, loop); i++)
     fprintf (stderr, "%d: %d, ", i, loop ? loop->num : -1);
@@ -89,6 +89,9 @@ void debug_loop_vec (graphite_bb_p gb)
 typedef VEC(name_tree, heap) **loop_iv_stack;
 void loop_iv_stack_debug (loop_iv_stack);
 
+static void expand_scalar_variables_stmt (gimple, graphite_bb_p, scop_p,
+					  loop_p, loop_iv_stack);
+
 /* Push (IV, NAME) on STACK.  */
 
 static void 
@@ -3025,6 +3028,165 @@ graphite_rename_ivs_stmt (gimple stmt, g
     }
 }
 
+/* Returns true if SSA_NAME is a parameter of SCOP.  */
+
+static bool
+is_parameter (scop_p scop, tree ssa_name)
+{
+  int i;
+  VEC (name_tree, heap) *params = SCOP_PARAMS (scop);
+  name_tree param;
+
+  for (i = 0; VEC_iterate (name_tree, params, i, param); i++)
+    if (param->t == ssa_name)
+      return true;
+
+  return false;
+}
+
+/* Returns true if SSA_NAME is an old_iv in SCOP.  */
+
+static bool
+is_old_iv (scop_p scop, loop_p old_loop_father, tree ssa_name)
+{
+  return get_old_iv_from_ssa_name (scop, old_loop_father, ssa_name) != NULL;
+
+}
+
+/* Constructs a tree which only contains old_ivs and parameters. Any
+   other variables that are defined outside GBB will be eliminated by
+   using their definitions in the constructed tree.  */
+
+static tree
+expand_scalar_variables_expr (tree type, tree op0, enum tree_code code, 
+			      tree op1, graphite_bb_p gbb, scop_p scop, 
+			      loop_p old_loop_father, loop_iv_stack ivstack)
+{
+  if (TREE_CODE_CLASS (code) == tcc_constant
+      && code == INTEGER_CST)
+      return op0;
+
+  if (TREE_CODE_CLASS (code) == tcc_unary)
+    {
+      tree op0_type = TREE_TYPE (op0);
+      enum tree_code op0_code = TREE_CODE (op0);
+      tree op0_expr = 
+	expand_scalar_variables_expr (op0_type, op0, op0_code,
+				      NULL, gbb, scop, old_loop_father,
+				      ivstack);
+
+      return fold_build1 (code, type, op0_expr);
+    }
+
+  if (TREE_CODE_CLASS (code) == tcc_binary)
+    {
+      tree op0_type = TREE_TYPE (op0);
+      enum tree_code op0_code = TREE_CODE (op0);
+      tree op0_expr = 
+	expand_scalar_variables_expr (op0_type, op0, op0_code,
+				      NULL, gbb, scop, old_loop_father,
+				      ivstack);
+      tree op1_type = TREE_TYPE (op1);
+      enum tree_code op1_code = TREE_CODE (op1);
+      tree op1_expr = 
+	expand_scalar_variables_expr (op1_type, op1, op1_code,
+				      NULL, gbb, scop, old_loop_father,
+				      ivstack);
+
+      return fold_build2 (code, type, op0_expr, op1_expr);
+    }
+
+  if (code == SSA_NAME)
+    {
+      tree var0, var1;
+      gimple def_stmt;
+      enum tree_code subcode;
+      
+      if(is_parameter (scop, op0) ||
+	 is_old_iv (scop, old_loop_father, op0))
+	return op0;
+      
+      def_stmt = SSA_NAME_DEF_STMT (op0);
+      
+      if (gimple_bb (def_stmt) == GBB_BB (gbb))
+	{
+	  /* If the defining statement is in the basic block already
+	     we do not need to create a new expression for it, we
+	     only need to ensure its operands are expanded.  */
+	  expand_scalar_variables_stmt (def_stmt, gbb, scop,
+					old_loop_father, ivstack);
+	  return op0;
+	  
+	}
+      else
+	{
+	  if (gimple_code (def_stmt) != GIMPLE_ASSIGN)
+	    return op0;
+	  
+	  var0 = gimple_assign_rhs1 (def_stmt);
+	  subcode = gimple_assign_rhs_code (def_stmt);
+	  var1 = gimple_assign_rhs2 (def_stmt);
+	  
+	  return expand_scalar_variables_expr (type, var0, subcode, var1, 
+					       gbb, scop, old_loop_father, 
+					       ivstack);
+	}
+    }
+
+  gcc_unreachable ();
+  return NULL;
+}
+
+/* Replicates any uses of non-parameters and non-old-ivs variablesthat
+   are defind outside GBB with code that is inserted in GBB.  */
+ 
+static void
+expand_scalar_variables_stmt (gimple stmt, graphite_bb_p gbb, scop_p scop,
+			      loop_p old_loop_father, loop_iv_stack ivstack)
+{
+  ssa_op_iter iter;
+  use_operand_p use_p;
+  basic_block bb = GBB_BB (gbb);
+
+  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+    {
+      tree use = USE_FROM_PTR (use_p);
+      tree type = TREE_TYPE (use);
+      enum tree_code code  = TREE_CODE (use);
+      tree use_expr = expand_scalar_variables_expr (type, use, code, NULL,
+						    gbb, scop, old_loop_father, 
+						    ivstack);
+      if (use_expr != use)
+	{
+	  gimple_stmt_iterator gsi = gsi_after_labels (bb);
+	  tree new_use =
+	    force_gimple_operand_gsi (&gsi, use_expr, true, NULL,
+				      true, GSI_NEW_STMT);
+	  SET_USE (use_p, new_use);
+	}
+    }
+}
+
+/* Copies the definitions outside of GBB of variables that are not
+   induction variables nor parameters. GBB must only contain
+   "external" references to these types of variables.  */
+
+static void 
+expand_scalar_variables (graphite_bb_p gbb, scop_p scop, 
+			 loop_p old_loop_father, loop_iv_stack ivstack)
+{
+  basic_block bb = GBB_BB (gbb);
+  gimple_stmt_iterator gsi;
+  
+  for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
+    {
+      gimple stmt = gsi_stmt (gsi);
+      expand_scalar_variables_stmt (stmt, gbb, scop, old_loop_father, 
+				    ivstack); 
+      gsi_next (&gsi);
+    }
+}
+
 /* Rename all the SSA_NAMEs from block GBB that appear in IVSTACK in
    terms of new induction variables.  */
 
@@ -3049,7 +3211,6 @@ graphite_rename_ivs (graphite_bb_p gbb, 
 	  graphite_rename_ivs_stmt (stmt, gbb, scop, old_loop_father, ivstack); 
 	  gsi_next (&gsi);
 	}
-
     }
 }
 
@@ -3060,23 +3221,19 @@ move_phi_nodes (scop_p scop, loop_p old_
 		basic_block to)
 {
   gimple_stmt_iterator gsi;
-  gimple_stmt_iterator gsi_1;
-  gimple_stmt_iterator gsi_2;  
 
-  for (gsi = gsi_start_phis (from); !gsi_end_p (gsi); gsi_next (&gsi))
+  for (gsi = gsi_start_phis (from); !gsi_end_p (gsi);)
     {
       gimple phi = gsi_stmt (gsi);
       tree op = gimple_phi_result (phi);
 
       if (get_old_iv_from_ssa_name (scop, old_loop_father, op) == NULL)
 	{
-	  gsi_1 = gsi_for_stmt (phi);
-	  gsi_2 = gsi_after_labels (to);
-	  gsi_move_before (&gsi_1, &gsi_2);
+	  gimple new_phi = make_phi_node (op, 0);
+	  add_phi_node_to_bb (new_phi, to);
 	}
+      remove_phi_node (&gsi, false);
     }
-
-  set_phi_nodes (from, NULL); 
 }
 
 /* Remove COND_EXPRs from BB.  */
@@ -3135,6 +3292,7 @@ translate_clast (scop_p scop, struct loo
 	return next_e;
 
       remove_cond_exprs (bb);
+      expand_scalar_variables (gbb, scop, old_loop_father, ivstack);
       remove_all_edges (bb, next_e);
       move_phi_nodes (scop, old_loop_father, bb, next_e->src);	
       redirect_edge_succ_nodup (next_e, bb);
@@ -3433,6 +3591,11 @@ find_vdef_for_var_in_bb (basic_block bb,
       if (SSA_NAME_VAR (*def_var) == var)
 	return *def_var;
 
+  for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
+    FOR_EACH_SSA_DEF_OPERAND (def_var, gsi_stmt (gsi), op_iter, SSA_OP_DEF)
+      if (SSA_NAME_VAR (*def_var) == var)
+	return *def_var;
+
   for (gsi = gsi_start_phis (bb); !gsi_end_p(gsi); gsi_next (&gsi))
     {
       phi = gsi_stmt (gsi);
@@ -3563,19 +3726,6 @@ remove_dead_loops (void)
     }
 }
 
-/* Remove the edges linked to the BBS to be removed.  */
-
-static void
-remove_edges_around_useless_blocks (scop_p scop, VEC (basic_block,heap) *bbs)
-{
-  int i;
-  basic_block bb;
- for (i = 0; VEC_iterate (basic_block, bbs, i, bb); i++)
-    if (!bb_in_scop_p (bb, scop)
-	&& bb != SCOP_EXIT (scop))
-      remove_all_edges (bb, NULL);
-}
-
 /* Returns true when it is possible to generate code for this STMT.  */
 
 static bool 
@@ -3629,6 +3779,62 @@ can_generate_code (struct clast_stmt *st
   return result;
 }
 
+/* Skip any definition that is a phi node with a single phi def.  */
+
+static tree 
+skip_phi_defs (tree ssa_name)
+{
+  tree result = ssa_name;
+  gimple def_stmt = SSA_NAME_DEF_STMT (ssa_name);
+
+  if (gimple_code (def_stmt) == GIMPLE_PHI 
+      && gimple_phi_num_args (def_stmt) == 1)
+    result = skip_phi_defs (gimple_phi_arg(def_stmt,0)->def);
+
+  return result;
+}
+
+/* Returns a VEC containing the phi-arg defs coming from SCOP_EXIT in
+   the destination block of SCOP_EXIT.  */
+
+static VEC (tree, heap) *
+collect_scop_exit_phi_args (edge scop_exit)
+{
+  VEC (tree, heap) *phi_args = VEC_alloc (tree, heap, 1);
+  gimple_stmt_iterator gsi;
+
+  for (gsi = gsi_start_phis (scop_exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple phi = gsi_stmt (gsi);
+      tree phi_arg = skip_phi_defs(PHI_ARG_DEF_FROM_EDGE (phi, scop_exit));
+
+      VEC_safe_push (tree, heap, phi_args, phi_arg);
+    }
+
+  return phi_args;
+}
+
+/* Patches (adds) PHI_ARGS to the phi nodes in SCOP_EXIT destination.  */
+
+static void
+patch_scop_exit_phi_args (edge scop_exit,
+			  VEC (tree, heap) *phi_args)
+{
+  int i = 0;
+  gimple_stmt_iterator gsi;
+
+  for (gsi = gsi_start_phis (scop_exit->dest); !gsi_end_p (gsi);
+       gsi_next (&gsi), i++)
+    {
+      tree def = VEC_index (tree, phi_args, i);
+      gimple phi = gsi_stmt (gsi);
+
+      gcc_assert (PHI_ARG_DEF_FROM_EDGE (phi, scop_exit) == NULL);
+
+      add_phi_arg (phi, def, scop_exit);
+    }
+}
+
 /* GIMPLE Loop Generator: generates loops from STMT in GIMPLE form for
    the given SCOP.  */
 
@@ -3637,9 +3843,10 @@ gloog (scop_p scop, struct clast_stmt *s
 {
   edge new_scop_exit_edge = NULL;
   basic_block scop_exit = SCOP_EXIT (scop);
+  VEC (tree, heap)* phi_args = 
+    collect_scop_exit_phi_args (SESE_EXIT (SCOP_REGION (scop)));
   VEC (name_tree, heap) *ivstack = VEC_alloc (name_tree, heap, 10);
   edge construction_edge = SESE_ENTRY (SCOP_REGION (scop));
-  VEC (basic_block,heap) *bbs = VEC_alloc (basic_block, heap, 10);
   basic_block old_scop_exit_idom = get_immediate_dominator (CDI_DOMINATORS,
 							    scop_exit);
 
@@ -3649,7 +3856,6 @@ gloog (scop_p scop, struct clast_stmt *s
       return;
     }
 
-  gather_blocks_in_sese_region (SCOP_ENTRY (scop), SCOP_EXIT (scop), &bbs);
   new_scop_exit_edge = translate_clast (scop, 
 					construction_edge->src->loop_father,
 					stmt, construction_edge, &ivstack);
@@ -3666,15 +3872,11 @@ gloog (scop_p scop, struct clast_stmt *s
 
   if (new_scop_exit_edge->dest == EXIT_BLOCK_PTR)
     new_scop_exit_edge->flags = 0;
-
-  remove_edges_around_useless_blocks (scop, bbs);
  
-  VEC_free (basic_block, heap, bbs);
-
-  patch_phis_for_virtual_defs ();
-
   find_unreachable_blocks ();
-  delete_unreachable_blocks();
+  delete_unreachable_blocks ();
+  patch_phis_for_virtual_defs ();
+  patch_scop_exit_phi_args (new_scop_exit_edge, phi_args);
   mark_old_loops (scop);
   remove_dead_loops ();
 
@@ -3683,8 +3885,8 @@ gloog (scop_p scop, struct clast_stmt *s
   verify_dominators (CDI_DOMINATORS);
 #endif
 
-  rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
   update_ssa (TODO_update_ssa);
+  rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); 
 
 #ifdef ENABLE_CHECKING
   verify_ssa (false);
Index: tree-flow.h
===================================================================
--- tree-flow.h	(revision 139502)
+++ tree-flow.h	(working copy)
@@ -786,6 +786,8 @@ extern gimple get_single_def_stmt_with_p
 
 /* In tree-phinodes.c  */
 extern void reserve_phi_args_for_new_edge (basic_block);
+extern void add_phi_node_to_bb (gimple phi, basic_block bb);
+extern gimple make_phi_node (tree var, int len);
 extern gimple create_phi_node (tree, basic_block);
 extern void add_phi_arg (gimple, tree, edge);
 extern void remove_phi_args (edge);
Index: ChangeLog.graphite
===================================================================
--- ChangeLog.graphite	(revision 139608)
+++ ChangeLog.graphite	(working copy)
@@ -1,3 +1,27 @@
+2008-08-29  Jan Sjodin  <jan.sjodin@amd.com>
+
+	* tree-phinodes.c (make_phi_node): Extern.
+	(add_phi_node_to_bb): New.
+	(create_phi_node): Call add_phi_node_to_bb.
+	* tree-ssa-loop-ivopts.c (get_phi_with_result): New.
+	(remove_statement): Handle case where stored phi was updated
+	and is no longer the same.
+	* graphite.c (is_parameter): New.
+	(is_old_iv): New.
+	(expand_scalar_variables_expr): New.
+	(expand_scalar_variables_stmt): New.
+	(expand_scalar_variables): New.
+	(move_phi_nodes): Create new phi instead of moving old one.
+	(translate_clast): Call expand_scalar_variables.
+	(find_vdef_for_var_in_bb): Also scan regular definitions. 
+	(skip_phi_defs): New.
+	(collect_scop_exit_phi_args): New.
+	(patch_scop_exit_phi_args): New.
+	(gloog): Patch phis after scop.
+
+	* tree-flow.h: (add_phi_node_to_bb): Declared.
+	(make_phi_node): Declared.
+
 2008-08-26  Sebastian Pop  <sebastian.pop@amd.com>
 
 	* graphite.c (end_scop): Split the entry of the scop when it