Patchwork [3/9,SMS] Eliminate redundant edges

login
register
mail settings
Submitter zhroma@ispras.ru
Date July 21, 2011, 4:30 p.m.
Message ID <1311265834-2144-4-git-send-email-zhroma@ispras.ru>
Download mbox | patch
Permalink /patch/106096/
State New
Headers show

Comments

zhroma@ispras.ru - July 21, 2011, 4:30 p.m.
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(-)
Revital1 Eres - July 24, 2011, 7:31 a.m.
Hi Roman,

> 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

It would be much appreciated if you could provide an example for the
problematic scenario which leads to the miscompilation.

Thanks,
Revital

Patch

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