Re: [PATCH] Fix PR57521

[Richard Biener <rguenther at suse dot de>]

On Mon, 24 Jun 2013, Richard Biener wrote:

> 
> The following fixes a long-standing bug in tree if-conversion.
> The transform phase relies on being able to extract edge predicates
> by simply using the predicate under which its source block is
> executed.  That obviously isn't the correct one if the source
> block ends in a condition itself.  Thus the following patch
> verifies that each predecessor edge of blocks we will if-convert
> is non-critical.
> 
> Bootstrapped on x86_64-unknown-linux-gnu, testing in progress.

... to pick up where I left.

That didn't work out, we need to handle the case of one edge being
non-critical only to not regress.  I've dug in history where all the
strange existing tests come from - and they are all for bugs
exhibiting this very same problem, just they paper over it in various
interesting ways.

So the following removes all of them, re-doing the above fix in
a less conservative way.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2013-08-27  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/57521
	* tree-if-conv.c (if_convertible_bb_p): Verify that at least
	one edge is non-critical.
	(find_phi_replacement_condition): Make sure to use a non-critical
	edge.  Cleanup and remove old bug workarounds.
	(bb_postdominates_preds): Remove.
	(if_convertible_loop_p_1): Do not compute post-dominators.
	(combine_blocks): Do not free post-dominators.
	(main_tree_if_conversion): Likewise.
	(pass_data_if_conversion): Add TODO_verify_ssa.

	* gcc.dg/torture/pr57521.c: New testcase.

Index: gcc/tree-if-conv.c
===================================================================
*** gcc/tree-if-conv.c	(revision 202017)
--- gcc/tree-if-conv.c	(working copy)
*************** if_convertible_stmt_p (gimple stmt, vec<
*** 797,816 ****
    return true;
  }
  
- /* Return true when BB post-dominates all its predecessors.  */
- 
- static bool
- bb_postdominates_preds (basic_block bb)
- {
-   unsigned i;
- 
-   for (i = 0; i < EDGE_COUNT (bb->preds); i++)
-     if (!dominated_by_p (CDI_POST_DOMINATORS, EDGE_PRED (bb, i)->src, bb))
-       return false;
- 
-   return true;
- }
- 
  /* Return true when BB is if-convertible.  This routine does not check
     basic block's statements and phis.
  
--- 797,802 ----
*************** if_convertible_bb_p (struct loop *loop,
*** 868,877 ****
  	return false;
        }
  
!   if (EDGE_COUNT (bb->preds) == 2
!       && bb != loop->header
!       && !bb_postdominates_preds (bb))
!     return false;
  
    return true;
  }
--- 854,876 ----
  	return false;
        }
  
!   /* At least one incoming edge has to be non-critical as otherwise edge
!      predicates are not equal to basic-block predicates of the edge
!      source.  */
!   if (EDGE_COUNT (bb->preds) > 1
!       && bb != loop->header)
!     {
!       bool found = false;
!       FOR_EACH_EDGE (e, ei, bb->preds)
! 	if (EDGE_COUNT (e->src->succs) == 1)
! 	  found = true;
!       if (!found)
! 	{
! 	  if (dump_file && (dump_flags & TDF_DETAILS))
! 	    fprintf (dump_file, "only critical predecessors\n");
! 	  return false;
! 	}
!     }
  
    return true;
  }
*************** if_convertible_loop_p_1 (struct loop *lo
*** 1084,1090 ****
      return false;
  
    calculate_dominance_info (CDI_DOMINATORS);
-   calculate_dominance_info (CDI_POST_DOMINATORS);
  
    /* Allow statements that can be handled during if-conversion.  */
    ifc_bbs = get_loop_body_in_if_conv_order (loop);
--- 1083,1088 ----
*************** if_convertible_loop_p (struct loop *loop
*** 1220,1227 ****
     if-conversion.  */
  
  static basic_block
! find_phi_replacement_condition (struct loop *loop,
! 				basic_block bb, tree *cond,
  				gimple_stmt_iterator *gsi)
  {
    edge first_edge, second_edge;
--- 1218,1224 ----
     if-conversion.  */
  
  static basic_block
! find_phi_replacement_condition (basic_block bb, tree *cond,
  				gimple_stmt_iterator *gsi)
  {
    edge first_edge, second_edge;
*************** find_phi_replacement_condition (struct l
*** 1231,1264 ****
    first_edge = EDGE_PRED (bb, 0);
    second_edge = EDGE_PRED (bb, 1);
  
!   /* Use condition based on following criteria:
!      1)
!        S1: x = !c ? a : b;
! 
!        S2: x = c ? b : a;
! 
!        S2 is preferred over S1. Make 'b' first_bb and use its condition.
! 
!      2) Do not make loop header first_bb.
! 
!      3)
!        S1: x = !(c == d)? a : b;
! 
!        S21: t1 = c == d;
!        S22: x = t1 ? b : a;
! 
!        S3: x = (c == d) ? b : a;
! 
!        S3 is preferred over S1 and S2*, Make 'b' first_bb and use
!        its condition.
! 
!      4) If  pred B is dominated by pred A then use pred B's condition.
!         See PR23115.  */
! 
!   /* Select condition that is not TRUTH_NOT_EXPR.  */
    tmp_cond = bb_predicate (first_edge->src);
    gcc_assert (tmp_cond);
- 
    if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
      {
        edge tmp_edge;
--- 1228,1237 ----
    first_edge = EDGE_PRED (bb, 0);
    second_edge = EDGE_PRED (bb, 1);
  
!   /* Prefer an edge with a not negated predicate.
!      ???  That's a very weak cost model.  */
    tmp_cond = bb_predicate (first_edge->src);
    gcc_assert (tmp_cond);
    if (TREE_CODE (tmp_cond) == TRUTH_NOT_EXPR)
      {
        edge tmp_edge;
*************** find_phi_replacement_condition (struct l
*** 1268,1278 ****
        second_edge = tmp_edge;
      }
  
!   /* Check if FIRST_BB is loop header or not and make sure that
!      FIRST_BB does not dominate SECOND_BB.  */
!   if (first_edge->src == loop->header
!       || dominated_by_p (CDI_DOMINATORS,
! 			 second_edge->src, first_edge->src))
      {
        *cond = bb_predicate (second_edge->src);
  
--- 1241,1249 ----
        second_edge = tmp_edge;
      }
  
!   /* Check if the edge we take the condition from is not critical.
!      We know that at least one non-critical edge exists.  */
!   if (EDGE_COUNT (first_edge->src->succs) > 1)
      {
        *cond = bb_predicate (second_edge->src);
  
*************** predicate_scalar_phi (gimple phi, tree c
*** 1347,1355 ****
  	  arg_1 = gimple_phi_arg_def (phi, 1);
  	}
  
-       gcc_checking_assert (bb == bb->loop_father->header
- 			   || bb_postdominates_preds (bb));
- 
        /* Build new RHS using selected condition and arguments.  */
        rhs = fold_build_cond_expr (TREE_TYPE (res), unshare_expr (cond),
  				  arg_0, arg_1);
--- 1318,1323 ----
*************** predicate_all_scalar_phis (struct loop *
*** 1395,1401 ****
        /* BB has two predecessors.  Using predecessor's aux field, set
  	 appropriate condition for the PHI node replacement.  */
        gsi = gsi_after_labels (bb);
!       true_bb = find_phi_replacement_condition (loop, bb, &cond, &gsi);
  
        while (!gsi_end_p (phi_gsi))
  	{
--- 1363,1369 ----
        /* BB has two predecessors.  Using predecessor's aux field, set
  	 appropriate condition for the PHI node replacement.  */
        gsi = gsi_after_labels (bb);
!       true_bb = find_phi_replacement_condition (bb, &cond, &gsi);
  
        while (!gsi_end_p (phi_gsi))
  	{
*************** combine_blocks (struct loop *loop)
*** 1765,1773 ****
  
    free (ifc_bbs);
    ifc_bbs = NULL;
- 
-   /* Post-dominators are corrupt now.  */
-   free_dominance_info (CDI_POST_DOMINATORS);
  }
  
  /* If-convert LOOP when it is legal.  For the moment this pass has no
--- 1733,1738 ----
*************** main_tree_if_conversion (void)
*** 1830,1837 ****
    if (changed && flag_tree_loop_if_convert_stores)
      todo |= TODO_update_ssa_only_virtuals;
  
-   free_dominance_info (CDI_POST_DOMINATORS);
- 
  #ifdef ENABLE_CHECKING
    {
      basic_block bb;
--- 1795,1800 ----
*************** const pass_data pass_data_if_conversion
*** 1867,1873 ****
    0, /* properties_provided */
    0, /* properties_destroyed */
    0, /* todo_flags_start */
!   ( TODO_verify_stmts | TODO_verify_flow ), /* todo_flags_finish */
  };
  
  class pass_if_conversion : public gimple_opt_pass
--- 1830,1837 ----
    0, /* properties_provided */
    0, /* properties_destroyed */
    0, /* todo_flags_start */
!   ( TODO_verify_stmts | TODO_verify_flow
!     | TODO_verify_ssa ), /* todo_flags_finish */
  };
  
  class pass_if_conversion : public gimple_opt_pass
Index: gcc/testsuite/gcc.dg/torture/pr57521.c
===================================================================
*** gcc/testsuite/gcc.dg/torture/pr57521.c	(revision 0)
--- gcc/testsuite/gcc.dg/torture/pr57521.c	(working copy)
***************
*** 0 ****
--- 1,51 ----
+ /* { dg-do run } */
+ /* { dg-options "-ftree-loop-if-convert" } */
+ 
+ void abort (void);
+ 
+ int a, b, c, d, o = 1, p;
+ short e;
+ 
+ int
+ fn1 (int * p1)
+ {
+   int f, g, h, j = 0, k = 0, l = 0;
+   unsigned int i;
+   int *m[1] = { &l };
+   for (; b >= 0; b--)
+     {
+       if (*p1)
+ 	if (j >= 0)
+ 	  {
+ 	    int n = 1;
+ 	    e = 1;
+ 	    h = a ? a : 1 % n;
+ 	    g = h > 0 ? 0 : h + 1;
+ 	    k = c + g;
+ 	  }
+ 	else
+ 	  continue;
+       else
+ 	{
+ 
+ 	  f = d > 0 ? 0 : d + 1;
+ 	  i = f;
+ 	  j = 1 + i;
+ 	}
+       l++;
+     }
+   return k;
+ }
+ 
+ int
+ main ()
+ {
+   for (;; p++)
+     {
+       fn1 (&o);
+       break;
+     }
+   if (e != 1)
+     abort ();
+   return 0;
+ }