[SMS, DDG] Additional edges to instructions with clobber

[Roman Zhuykov <zhroma at ispras dot ru>]

Apologies for the messed up previous e-mails.

This letter contains the first separate patch for ddg.c
It creates additional nessesary anti-dep edges in data dependency graph.

2011/10/12 Ayal Zaks <ayal.zaks@gmail.com>:
>>> The following situation happens when SMS is enabled without register renaming
>>> (-fno-modulo-sched-allow-regmoves).  When data dependency graph is built, there
>>> is a step when we generate anti-dependencies from last register use to first
>>> write of this register at the next iteration.
>
> is a step when we generate anti-dependencies from all last registers
> uses (i.e., of last register def) to first write of this register at
> the next iteration.
>

Right.

>>> At this moment we should also
>>> create such dependencies to all instructions which clobber the register to
>>> prevent this clobbers being before last use is new schedule.
>>>
>
> well, we simply need to connect these last uses to either the first
> write *or* the first clobber of this register at the next iteration,
> according to whichever is first, no?

No, is works now just how you describe. Clobber is considered as a write,
and last uses are connected with first write or first clobber.
But this is not sufficient: similarly to how there's no dependencies
between last uses,
there shall be no dependency between "first" clobbers (i.e. clobbers
of a register
can be permuted freely). So at least we have to make an additional dependency
edge to each clobber before first write.

>>> Here is an model of example:
>>>
>>> loop {
>>> set1 regR
>>> use1 regR
>>> clobber regR
>>> set2 regR
>>> use2 regR
>>> }
>>>
>>> If we create only use2->set1 anti-dependency (and no use2->cloober) the
>>> following wrong schedule is possible:
>>>
>>> prologue {
>>> set1 regR
>>> use1 regR
>>> clobber regR
>>> }
>>> kernel {
>>> set2 regR
>>> clobber regR (instruction from next iteration in terms of old loop kernel)
>>> use2 regR
>>> set1 regR (also from next iteration)
>>> use1 regR (also from next iteration)
>>> }
>>> epilogue {
>>> set2 regR
>>> use2 regR
>>> }
>>>
>
> strange; according to prolog (and epilog), clobber should appear after
> use1 in the kernel, no? Aren't there (intra-iteration) dependencies
> preventing the clobber to skip over use1 and/or set1?
>

Yeah, this is bad example - I wrongly suggested that there is no
anti-dep between use1 and clobber.

New example:
loop {
 clobber1
 clobber2
 set
 use
}
When there is no "use->clobber2" anti-dep - the following wrong schedule
is possible. Clobber2 is on stage0, other instructions are on stage1.
prologue {
 clobber2
}
kernel {
 clobber1
 set
 clobber2
 use
}
epilogue {
 clobber1
 set
 use
}

>>> This problem was succesfully fixed by creating a vector of all clobbering
>>> instructions together with first write and adding all needed dependencies.
>>>
>
> seems like an overkill to me; we didn't draw an edge between every
> last use and every write, because writes are kept in order by having
> output dependences between them. So should be the case with clobbers.

Clobbers themselves aren't kept in order - there are no output dependences
between them. They may be scheduled in any order.

> Presumably, the ddg already has all intra-iteration edges preventing
> motion of clobbering instructions within an iteration, and we are only
> missing inter-iteration deps or deps surfaced by eliminating
> anti-deps, right?

I think the new version of a fix suits this reasoning.
Now it creates dependencies only to clobber instructions before first write.
And certainly to first write instruction itself.

--
Roman Zhuykov
zhroma@ispras.ru

2011-12-07  Roman Zhuykov  <zhroma@ispras.ru>
	* ddg.c: New VEC.
	(add_cross_iteration_register_deps): Store information about
	clobbers before first write to a register.  Use collected
	information to create anti-dependencies from last uses.
---

diff --git a/gcc/ddg.c b/gcc/ddg.c
index 2b1cfe8..e3e065c 100644
--- a/gcc/ddg.c
+++ b/gcc/ddg.c
@@ -49,6 +49,10 @@ along with GCC; see the file COPYING3.  If not see
 /* A flag indicating that a ddg edge belongs to an SCC or not.  */
 enum edge_flag {NOT_IN_SCC = 0, IN_SCC};
 
+/* A vector of dependencies needed while processing clobbers.  */
+DEF_VEC_P(df_ref);
+DEF_VEC_ALLOC_P(df_ref,heap);
+
 /* Forward declarations.  */
 static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr);
 static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
@@ -273,24 +277,52 @@ create_ddg_dep_no_link (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to,
 static void
 add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
 {
-  int regno = DF_REF_REGNO (last_def);
+  unsigned int regno = DF_REF_REGNO (last_def);
   struct df_link *r_use;
   int has_use_in_bb_p = false;
-  rtx def_insn = DF_REF_INSN (last_def);
+  rtx insn, def_insn = DF_REF_INSN (last_def);
   ddg_node_ptr last_def_node = get_node_of_insn (g, def_insn);
   ddg_node_ptr use_node;
 #ifdef ENABLE_CHECKING
   struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
 #endif
-  df_ref first_def = df_bb_regno_first_def_find (g->bb, regno);
+  static VEC(df_ref,heap) *clobbers;
+  df_ref first_write_def = NULL;
+  df_ref *def_rec;
+  unsigned int uid;
+  
+  clobbers = VEC_alloc (df_ref, heap, 0);
+
+  FOR_BB_INSNS (g->bb, insn)
+    {
+      if (!INSN_P (insn))
+        continue;
+      uid = INSN_UID (insn);
+      for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
+        {
+          df_ref def = *def_rec;
+          if (DF_REF_REGNO (def) == regno)
+            {
+	      VEC_safe_push (df_ref, heap, clobbers, def);
+	      if (!(DF_REF_FLAGS (def)
+		    & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+		{
+		  first_write_def = def;
+		  break;
+		}
+	    }
+        }
+      if (first_write_def != NULL)
+	break;
+    }
 
   gcc_assert (last_def_node);
-  gcc_assert (first_def);
+  gcc_assert (first_write_def);
 
 #ifdef ENABLE_CHECKING
-  if (DF_REF_ID (last_def) != DF_REF_ID (first_def))
+  if (DF_REF_ID (last_def) != DF_REF_ID (first_write_def))
     gcc_assert (!bitmap_bit_p (&bb_info->gen,
-			       DF_REF_ID (first_def)));
+			       DF_REF_ID (first_write_def)));
 #endif
 
   /* Create inter-loop true dependences and anti dependences.  */
@@ -316,29 +348,35 @@ add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
 	}
       else if (!DEBUG_INSN_P (use_insn))
 	{
+	  unsigned int i;
+	  df_ref curr_def;
 	  /* Add anti deps from last_def's uses in the current iteration
-	     to the first def in the next iteration.  We do not add ANTI
-	     dep when there is an intra-loop TRUE dep in the opposite
-	     direction, but use regmoves to fix such disregarded ANTI
-	     deps when broken.	If the first_def reaches the USE then
-	     there is such a dep.  */
-	  ddg_node_ptr first_def_node = get_node_of_insn (g,
-							  DF_REF_INSN (first_def));
-
-	  gcc_assert (first_def_node);
-
-         /* Always create the edge if the use node is a branch in
-            order to prevent the creation of reg-moves.  
-            If the address that is being auto-inc or auto-dec in LAST_DEF
-            is used in USE_INSN then do not remove the edge to make sure
-            reg-moves will not be created for that address.  */
-          if (DF_REF_ID (last_def) != DF_REF_ID (first_def)
-              || !flag_modulo_sched_allow_regmoves
-	      || JUMP_P (use_node->insn)
-              || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn))
-            create_ddg_dep_no_link (g, use_node, first_def_node, ANTI_DEP,
-                                    REG_DEP, 1);
-
+	     to the first def and all clobbers before it in the next iteration.
+	     We do not add ANTI dep when there is an intra-loop TRUE dep
+	     in the opposite direction, but use regmoves to fix such
+	     disregarded ANTI deps when broken.	If the curr_def reaches
+	     the USE then there is such a dep.  */
+	  FOR_EACH_VEC_ELT (df_ref, clobbers, i, curr_def)
+	    {
+	      if (DF_REF_ID (last_def) != DF_REF_ID (curr_def)
+		  /* Some hard regs (for ex. CC-flags) can't be renamed.  
+                  || HARD_REGISTER_P (DF_REF_REG (last_def)) */
+		  || !flag_modulo_sched_allow_regmoves
+		  /* If the address that is being auto-inc or auto-dec in LAST_DEF
+		     is used in USE_INSN then do not remove the edge to make sure
+		     reg-moves will not be created for that address.  */
+		  || autoinc_var_is_used_p (DF_REF_INSN (last_def), use_insn)
+		  /* Always create the edge if the use node is a branch in
+		     order to prevent the creation of reg-moves.  */
+		  || JUMP_P (use_node->insn))
+		{
+	          ddg_node_ptr curr_def_node = get_node_of_insn (g,
+						DF_REF_INSN (curr_def));
+		  gcc_assert (curr_def_node);
+		  create_ddg_dep_no_link (g, use_node, curr_def_node,
+					  ANTI_DEP, REG_DEP, 1);
+	        }
+	    }
 	}
     }
   /* Create an inter-loop output dependence between LAST_DEF (which is the
@@ -352,14 +390,16 @@ add_cross_iteration_register_deps (ddg_ptr g, df_ref last_def)
     {
       ddg_node_ptr dest_node;
 
-      if (DF_REF_ID (last_def) == DF_REF_ID (first_def))
+      if (DF_REF_ID (last_def) == DF_REF_ID (first_write_def))
 	return;
 
-      dest_node = get_node_of_insn (g, DF_REF_INSN (first_def));
+      dest_node = get_node_of_insn (g, DF_REF_INSN (first_write_def));
       gcc_assert (dest_node);
       create_ddg_dep_no_link (g, last_def_node, dest_node,
 			      OUTPUT_DEP, REG_DEP, 1);
     }
+
+  VEC_free (df_ref, heap, clobbers);
 }
 /* Build inter-loop dependencies, by looking at DF analysis backwards.  */
 static void