[PATCH 3/9] [SMS] Eliminate redundant edges

[zhroma@ispras.ru]

While building a data dependency graph for loop a ddg edge for some pair
of instructions with inter-loop dependency should be created only if
there is no edge for intra-loop dependency between these instructions.
Creating both of edges leads sometimes to the fact that function
generate_reg_moves creates a redundant register renaming, and some
instruction receives wrong register value from previous iteration.
Overall, this gives a miscompilation.

The add_inter_loop_mem_dep(from,to) function is called only when no
inter-loop "from->to" edge exists, but this function sometimes creates
backward "to->from" edges.  This patch prevents these backward edges to
be redundant, it allows to create such edge only when there is no
inter-loop one.

2011-07-20  Roman Zhuykov  <zhroma@ispras.ru>
	* ddg.c (add_intra_loop_mem_dep): Add new parameter (from_index).
	Use it to check whether backward edge is redundant.
	(build_intra_loop_deps): Update call to add_intra_loop_mem_dep.
---
 gcc/ddg.c |   15 +++++++++------
 1 files changed, 9 insertions(+), 6 deletions(-)

diff --git a/gcc/ddg.c b/gcc/ddg.c
index 2bb2cc1..5d0a401 100644
--- a/gcc/ddg.c
+++ b/gcc/ddg.c
@@ -418,7 +418,7 @@ add_intra_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
 /* Given two nodes, analyze their RTL insns and add inter-loop mem deps
    to ddg G.  */
 static void
-add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
+add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to, int from_index)
 {
   if (!insns_may_alias_p (from->insn, to->insn))
     /* Do not create edge if memory references have disjoint alias sets.  */
@@ -442,10 +442,13 @@ add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
       else if (from->cuid != to->cuid)
 	{
 	  create_ddg_dep_no_link (g, from, to, ANTI_DEP, MEM_DEP, 1);
-	  if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn))
-	    create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1);
-	  else
-	    create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
+	  if (! TEST_BIT (to->successors, from_index))
+	    {
+	      if (DEBUG_INSN_P (from->insn) || DEBUG_INSN_P (to->insn))
+		create_ddg_dep_no_link (g, to, from, ANTI_DEP, MEM_DEP, 1);
+	      else
+		create_ddg_dep_no_link (g, to, from, TRUE_DEP, MEM_DEP, 1);
+	    }
 	}
     }
 
@@ -511,7 +514,7 @@ build_intra_loop_deps (ddg_ptr g)
 		  /* Don't bother calculating inter-loop dep if an intra-loop dep
 		     already exists.  */
 	      	  if (! TEST_BIT (dest_node->successors, j))
-		    add_inter_loop_mem_dep (g, dest_node, j_node);
+		    add_inter_loop_mem_dep (g, dest_node, j_node, i);
 		  /* If -fmodulo-sched-allow-regmoves
 		     is set certain anti-dep edges are not created.
 		     It might be that these anti-dep edges are on the
-- 
Roman Zhuykov
zhroma@ispras.ru