Do not check whether memory references accessed in every iteration trap.

This patch relaxes the checks from gimple_could_trap_p in order to
allow the flag_loop_if_convert_stores to if-convert more loops
in which it is possible to prove that:

- the accesses to an array in a loop do not trap (more than the
  original non-if-converted loop).  This is true when the memory
  accesses are executed at every iteration of the if-converted loop.

- the writes to memory occur on arrays that are not const qualified.
  This is true when there exists at least one unconditional write to
  the array in the analyzed program.  In this patch this analysis is
  limited to the loop to be if-converted.

	* gimple.c (gimple_could_trap_p_1): Not static anymore.
	Pass an extra bool parameter include_mem.
	(gimple_could_trap_p): Adjust call to gimple_could_trap_p_1.
	(gimple_assign_rhs_could_trap_p): Same.
	* gimple.h (gimple_could_trap_p_1): Declared.
	* tree-data-ref.h (same_data_refs_base_objects): New.
	(same_data_refs): New.
	* tree-if-conv.c (memrefs_read_or_written_unconditionally): New.
	(write_memrefs_written_at_least_once): New.
	(ifcvt_memrefs_wont_trap): New.
	(operations_could_trap): New.
	(ifcvt_could_trap_p): New.
	(if_convertible_gimple_assign_stmt_p): Call ifcvt_could_trap_p.
	Gets a vector of data refs.
	(if_convertible_stmt_p): Same.
	(if_convertible_loop_p_1): New.
	(if_convertible_loop_p): Call if_convertible_loop_p_1.

	* gcc.dg/tree-ssa/ifc-5.c: New.

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

1 files changed, 204 insertions, 67 deletions

diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c
index ac60cef1e60..55e2a11a2b1 100644
--- a/gcc/tree-if-conv.c
+++ b/gcc/tree-if-conv.c
@@ -446,6 +446,132 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
   return true;
 }
 
+/* Returns true when the memory references of STMT are read or written
+   unconditionally.  In other words, this function returns true when
+   for every data reference A in STMT there exist other accesses to
+   the same data reference with predicates that add up (OR-up) to the
+   true predicate: this ensures that the data reference A is touched
+   (read or written) on every iteration of the if-converted loop.  */
+
+static bool
+memrefs_read_or_written_unconditionally (gimple stmt,
+					 VEC (data_reference_p, heap) *drs)
+{
+  int i, j;
+  data_reference_p a, b;
+  tree ca = bb_predicate (gimple_bb (stmt));
+
+  for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
+    if (DR_STMT (a) == stmt)
+      {
+	bool found = false;
+
+	for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++)
+	  if (DR_STMT (b) != stmt
+	      && same_data_refs (a, b))
+	    {
+	      tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
+
+	      if (is_true_predicate (cb)
+		  || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
+								 ca, cb)))
+		{
+		  found = true;
+		  break;
+		}
+	    }
+
+	if (!found)
+	  return false;
+      }
+
+  return true;
+}
+
+/* Returns true when the memory references of STMT are unconditionally
+   written.  In other words, this function returns true when for every
+   data reference A written in STMT, there exist other writes to the
+   same data reference with predicates that add up (OR-up) to the true
+   predicate: this ensures that the data reference A is written on
+   every iteration of the if-converted loop.  */
+
+static bool
+write_memrefs_written_at_least_once (gimple stmt,
+				     VEC (data_reference_p, heap) *drs)
+{
+  int i, j;
+  data_reference_p a, b;
+  tree ca = bb_predicate (gimple_bb (stmt));
+
+  for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
+    if (DR_STMT (a) == stmt
+	&& !DR_IS_READ (a))
+      {
+	bool found = false;
+
+	for (j = 0; VEC_iterate (data_reference_p, drs, j, b); j++)
+	  if (DR_STMT (b) != stmt
+	      && !DR_IS_READ (b)
+	      && same_data_refs_base_objects (a, b))
+	    {
+	      tree cb = bb_predicate (gimple_bb (DR_STMT (b)));
+
+	      if (is_true_predicate (cb)
+		  || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb),
+								 ca, cb)))
+		{
+		  found = true;
+		  break;
+		}
+	    }
+
+	if (!found)
+	  return false;
+      }
+
+  return true;
+}
+
+/* Return true when the memory references of STMT won't trap in the
+   if-converted code.  There are two things that we have to check for:
+
+   - writes to memory occur to writable memory: if-conversion of
+   memory writes transforms the conditional memory writes into
+   unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
+   into "A[i] = cond ? foo : A[i]", and as the write to memory may not
+   be executed at all in the original code, it may be a readonly
+   memory.  To check that A is not const-qualified, we check that
+   there exists at least an unconditional write to A in the current
+   function.
+
+   - reads or writes to memory are valid memory accesses for every
+   iteration.  To check that the memory accesses are correctly formed
+   and that we are allowed to read and write in these locations, we
+   check that the memory accesses to be if-converted occur at every
+   iteration unconditionally.  */
+
+static bool
+ifcvt_memrefs_wont_trap (gimple stmt, VEC (data_reference_p, heap) *refs)
+{
+  return write_memrefs_written_at_least_once (stmt, refs)
+    && memrefs_read_or_written_unconditionally (stmt, refs);
+}
+
+/* Wrapper around gimple_could_trap_p refined for the needs of the
+   if-conversion.  Try to prove that the memory accesses of STMT could
+   not trap in the innermost loop containing STMT.  */
+
+static bool
+ifcvt_could_trap_p (gimple stmt, VEC (data_reference_p, heap) *refs)
+{
+  if (gimple_vuse (stmt)
+      && !gimple_could_trap_p_1 (stmt, false, false)
+      && ifcvt_memrefs_wont_trap (stmt, refs))
+    return false;
+
+  return gimple_could_trap_p (stmt);
+}
+
 /* Return true when STMT is if-convertible.
 
    GIMPLE_ASSIGN statement is not if-convertible if,
@@ -454,7 +580,8 @@ if_convertible_phi_p (struct loop *loop, basic_block bb, gimple phi)
    - LHS is not var decl.  */
 
 static bool
-if_convertible_gimple_assign_stmt_p (gimple stmt)
+if_convertible_gimple_assign_stmt_p (gimple stmt,
+				     VEC (data_reference_p, heap) *refs)
 {
   tree lhs = gimple_assign_lhs (stmt);
   basic_block bb;
@@ -482,7 +609,7 @@ if_convertible_gimple_assign_stmt_p (gimple stmt)
 
   if (flag_tree_loop_if_convert_stores)
     {
-      if (gimple_could_trap_p (stmt))
+      if (ifcvt_could_trap_p (stmt, refs))
 	{
 	  if (dump_file && (dump_flags & TDF_DETAILS))
 	    fprintf (dump_file, "tree could trap...\n");
@@ -522,7 +649,7 @@ if_convertible_gimple_assign_stmt_p (gimple stmt)
    - it is a GIMPLE_LABEL or a GIMPLE_COND.  */
 
 static bool
-if_convertible_stmt_p (gimple stmt)
+if_convertible_stmt_p (gimple stmt, VEC (data_reference_p, heap) *refs)
 {
   switch (gimple_code (stmt))
     {
@@ -532,7 +659,7 @@ if_convertible_stmt_p (gimple stmt)
       return true;
 
     case GIMPLE_ASSIGN:
-      return if_convertible_gimple_assign_stmt_p (stmt);
+      return if_convertible_gimple_assign_stmt_p (stmt, refs);
 
     default:
       /* Don't know what to do with 'em so don't do anything.  */
@@ -800,69 +927,24 @@ predicate_bbs (loop_p loop)
   return true;
 }
 
-/* Return true when LOOP is if-convertible.
-   LOOP is if-convertible if:
-   - it is innermost,
-   - it has two or more basic blocks,
-   - it has only one exit,
-   - loop header is not the exit edge,
-   - if its basic blocks and phi nodes are if convertible.  */
+/* Return true when LOOP is if-convertible.  This is a helper function
+   for if_convertible_loop_p.  REFS and DDRS are initialized and freed
+   in if_convertible_loop_p.  */
 
 static bool
-if_convertible_loop_p (struct loop *loop)
+if_convertible_loop_p_1 (struct loop *loop,
+			 VEC (data_reference_p, heap) **refs,
+			 VEC (ddr_p, heap) **ddrs)
 {
+  bool res;
   unsigned int i;
-  edge e;
-  edge_iterator ei;
   basic_block exit_bb = NULL;
 
-  /* Handle only innermost loop.  */
-  if (!loop || loop->inner)
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "not innermost loop\n");
-      return false;
-    }
-
-  /* If only one block, no need for if-conversion.  */
-  if (loop->num_nodes <= 2)
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "less than 2 basic blocks\n");
-      return false;
-    }
-
-  /* More than one loop exit is too much to handle.  */
-  if (!single_exit (loop))
-    {
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	fprintf (dump_file, "multiple exits\n");
-      return false;
-    }
-
-  /* ??? Check target's vector conditional operation support for vectorizer.  */
-
-  /* If one of the loop header's edge is exit edge then do not apply
-     if-conversion.  */
-  FOR_EACH_EDGE (e, ei, loop->header->succs)
-    {
-      if (loop_exit_edge_p (loop, e))
-	return false;
-    }
-
   /* Don't if-convert the loop when the data dependences cannot be
      computed: the loop won't be vectorized in that case.  */
-  {
-    VEC (data_reference_p, heap) *refs = VEC_alloc (data_reference_p, heap, 5);
-    VEC (ddr_p, heap) *ddrs = VEC_alloc (ddr_p, heap, 25);
-    bool res = compute_data_dependences_for_loop (loop, true, &refs, &ddrs);
-
-    free_data_refs (refs);
-    free_dependence_relations (ddrs);
-
-    if (!res)
-      return false;
-  }
+  res = compute_data_dependences_for_loop (loop, true, refs, ddrs);
+  if (!res)
+    return false;
 
   calculate_dominance_info (CDI_DOMINATORS);
 
@@ -886,7 +968,8 @@ if_convertible_loop_p (struct loop *loop)
 	exit_bb = bb;
     }
 
-  if (!predicate_bbs (loop))
+  res = predicate_bbs (loop);
+  if (!res)
     return false;
 
   for (i = 0; i < loop->num_nodes; i++)
@@ -898,13 +981,11 @@ if_convertible_loop_p (struct loop *loop)
 	if (!if_convertible_phi_p (loop, bb, gsi_stmt (itr)))
 	  return false;
 
-      /* For non predicated BBs, don't check their statements.  */
-      if (!is_predicated (bb))
-	continue;
-
-      for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
-	if (!if_convertible_stmt_p (gsi_stmt (itr)))
-	  return false;
+      /* Check the if-convertibility of statements in predicated BBs.  */
+      if (is_predicated (bb))
+	for (itr = gsi_start_bb (bb); !gsi_end_p (itr); gsi_next (&itr))
+	  if (!if_convertible_stmt_p (gsi_stmt (itr), *refs))
+	    return false;
     }
 
   if (dump_file)
@@ -913,6 +994,62 @@ if_convertible_loop_p (struct loop *loop)
   return true;
 }
 
+/* Return true when LOOP is if-convertible.
+   LOOP is if-convertible if:
+   - it is innermost,
+   - it has two or more basic blocks,
+   - it has only one exit,
+   - loop header is not the exit edge,
+   - if its basic blocks and phi nodes are if convertible.  */
+
+static bool
+if_convertible_loop_p (struct loop *loop)
+{
+  edge e;
+  edge_iterator ei;
+  bool res = false;
+  VEC (data_reference_p, heap) *refs;
+  VEC (ddr_p, heap) *ddrs;
+
+  /* Handle only innermost loop.  */
+  if (!loop || loop->inner)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "not innermost loop\n");
+      return false;
+    }
+
+  /* If only one block, no need for if-conversion.  */
+  if (loop->num_nodes <= 2)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "less than 2 basic blocks\n");
+      return false;
+    }
+
+  /* More than one loop exit is too much to handle.  */
+  if (!single_exit (loop))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "multiple exits\n");
+      return false;
+    }
+
+  /* If one of the loop header's edge is an exit edge then do not
+     apply if-conversion.  */
+  FOR_EACH_EDGE (e, ei, loop->header->succs)
+    if (loop_exit_edge_p (loop, e))
+      return false;
+
+  refs = VEC_alloc (data_reference_p, heap, 5);
+  ddrs = VEC_alloc (ddr_p, heap, 25);
+  res = if_convertible_loop_p_1 (loop, &refs, &ddrs);
+
+  free_data_refs (refs);
+  free_dependence_relations (ddrs);
+  return res;
+}
+
 /* Basic block BB has two predecessors.  Using predecessor's bb
    predicate, set an appropriate condition COND for the PHI node
    replacement.  Return the true block whose phi arguments are