[PATCH] Fix PR67975, teach SCCVN basic control equivalency for PHI value-numbering

[PATCH] Fix PR67975, teach SCCVN basic control equivalency for PHI value-numbering

[Richard Biener]

The following patch teaches SCCVN to value-number two PHI nodes the same
even when they are in a different basic-block.  To do that we have to
prove equivalency of the edge predicates into the PHI (and of course
equivalence of the PHI arguments).  The patch handles the simple case
of PHI nodes with two arguments, more arguments would require some sort
of pairwise reduction.  The patch doesn't yet consider swapped
predicates (non-canonical form can easily happen if the operands
are valueized).

It's enough to make the testcase in PR67975 be optimized in FRE1 where
we get

  <bb 2>:
  if (y_5(D) >= 1.0e+1)
    goto <bb 3>;
  else
    goto <bb 7>;

  <bb 3>:
  if (x_6(D) < 2.0e+1)
    goto <bb 4>;
  else
    goto <bb 5>;

  <bb 4>:
  iftmp.1_7 = x_6(D);
  goto <bb 6>;

  <bb 5>:
  iftmp.1_8 = y_5(D);

  <bb 6>:
  # iftmp.1_2 = PHI <iftmp.1_7(4), iftmp.1_8(5)>
  iftmp.0_9 = __builtin_tan (iftmp.1_2);
  goto <bb 8>;

  <bb 7>:
  iftmp.0_10 = x_6(D);

  <bb 8>:
  # iftmp.0_1 = PHI <iftmp.0_9(6), iftmp.0_10(7)>
  z1_11 = __builtin_cos (iftmp.0_1);
  if (y_5(D) >= 1.0e+1)
    goto <bb 9>;
  else
    goto <bb 13>;

  <bb 9>:
  if (x_6(D) < 2.0e+1)
    goto <bb 10>;
  else
    goto <bb 11>;

  <bb 10>:
  iftmp.3_12 = x_6(D);
  goto <bb 12>;

  <bb 11>:
  iftmp.3_13 = y_5(D);

  <bb 12>:
  # iftmp.3_4 = PHI <iftmp.3_12(10), iftmp.3_13(11)>
  iftmp.2_14 = __builtin_tan (iftmp.3_4);
  goto <bb 14>;

  <bb 13>:
  iftmp.2_15 = x_6(D);

  <bb 14>:
  # iftmp.2_3 = PHI <iftmp.2_14(12), iftmp.2_15(13)>
  z2_16 = __builtin_cos (iftmp.2_3);
  _17 = z1_11 == z2_16;
  _18 = (int) _17;
  return _18;

and FRE1 now figures that z1_11 == z2_16 and make us return 1 via

Setting value number of iftmp.1_2 to iftmp.1_2 (changed)
Setting value number of iftmp.0_9 to iftmp.0_9 (changed)
Setting value number of iftmp.0_1 to iftmp.0_1 (changed)
Setting value number of z1_11 to z1_11 (changed)
Setting value number of iftmp.3_4 to iftmp.1_2 (changed)
Setting value number of iftmp.2_14 to iftmp.0_9 (changed)
Setting value number of iftmp.2_3 to iftmp.0_1 (changed)
Setting value number of z2_16 to z1_11 (changed)
Setting value number of _17 to 1 (changed)
Setting value number of _18 to 1 (changed)
  
Previously figuring out any such equivalence would require jump threading 
and PRE to prove PHI equivalency via PHI translation.  For the testcase in
question jump-threading wasn't aggressive enough.

A not cleaned up patch passed bootstrap and regtest on 
x86_64-unknown-linux-gnu, I am currently re-bootstrapping and testing
the following (and plan to commit on Monday if that succeeded).

Thanks,
Richard.

2015-10-16  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/67975
	* tree-cfg.h (extract_true_false_controlled_edges): Declare.
	* tree-cfg.c (extract_true_false_controlled_edges): Split out
	core worker from ...
	* tree-ssa-loop-im.c (extract_true_false_args_from_phi): ... here.
	* tree-ssa-sccvn.c (vn_phi_compute_hash): Hash number of args
	instead of block number for PHIs with two or one args.
	(vn_phi_eq): Compare edge predicates of PHIs that are in different
	blocks.

	* gcc.dg/tree-ssa/ssa-fre-50.c: New testcase.

Index: gcc/tree-cfg.h
===================================================================
*** gcc/tree-cfg.h	(revision 228863)
--- gcc/tree-cfg.h	(working copy)
*************** extern unsigned int execute_fixup_cfg (v
*** 105,109 ****
--- 105,111 ----
  extern unsigned int split_critical_edges (void);
  extern basic_block insert_cond_bb (basic_block, gimple *, gimple *);
  extern bool gimple_find_sub_bbs (gimple_seq, gimple_stmt_iterator *);
+ extern bool extract_true_false_controlled_edges (basic_block, basic_block,
+ 						 edge *, edge *);
  
  #endif /* _TREE_CFG_H  */
Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c	(revision 228863)
--- gcc/tree-cfg.c	(working copy)
*************** extract_true_false_edges_from_block (bas
*** 8532,8537 ****
--- 8578,8652 ----
      }
  }
  
+ 
+ /* From a controlling predicate in the immediate dominator DOM of
+    PHIBLOCK determine the edges into PHIBLOCK that are chosen if the
+    predicate evaluates to true and false and store them to
+    *TRUE_CONTROLLED_EDGE and *FALSE_CONTROLLED_EDGE if
+    they are non-NULL.  Returns true if the edges can be determined,
+    else return false.  */
+ 
+ bool
+ extract_true_false_controlled_edges (basic_block dom, basic_block phiblock,
+ 				     edge *true_controlled_edge,
+ 				     edge *false_controlled_edge)
+ {
+   basic_block bb = phiblock;
+   edge true_edge, false_edge, tem;
+   edge e0 = NULL, e1 = NULL;
+ 
+   /* We have to verify that one edge into the PHI node is dominated
+      by the true edge of the predicate block and the other edge
+      dominated by the false edge.  This ensures that the PHI argument
+      we are going to take is completely determined by the path we
+      take from the predicate block.
+      We can only use BB dominance checks below if the destination of
+      the true/false edges are dominated by their edge, thus only
+      have a single predecessor.  */
+   extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
+   tem = EDGE_PRED (bb, 0);
+   if (tem == true_edge
+       || (single_pred_p (true_edge->dest)
+ 	  && (tem->src == true_edge->dest
+ 	      || dominated_by_p (CDI_DOMINATORS,
+ 				 tem->src, true_edge->dest))))
+     e0 = tem;
+   else if (tem == false_edge
+ 	   || (single_pred_p (false_edge->dest)
+ 	       && (tem->src == false_edge->dest
+ 		   || dominated_by_p (CDI_DOMINATORS,
+ 				      tem->src, false_edge->dest))))
+     e1 = tem;
+   else
+     return false;
+   tem = EDGE_PRED (bb, 1);
+   if (tem == true_edge
+       || (single_pred_p (true_edge->dest)
+ 	  && (tem->src == true_edge->dest
+ 	      || dominated_by_p (CDI_DOMINATORS,
+ 				 tem->src, true_edge->dest))))
+     e0 = tem;
+   else if (tem == false_edge
+ 	   || (single_pred_p (false_edge->dest)
+ 	       && (tem->src == false_edge->dest
+ 		   || dominated_by_p (CDI_DOMINATORS,
+ 				      tem->src, false_edge->dest))))
+     e1 = tem;
+   else
+     return false;
+   if (!e0 || !e1)
+     return false;
+ 
+   if (true_controlled_edge)
+     *true_controlled_edge = e0;
+   if (false_controlled_edge)
+     *false_controlled_edge = e1;
+ 
+   return true;
+ }
+ 
+ 
+ 
  /* Emit return warnings.  */
  
  namespace {
Index: gcc/tree-ssa-loop-im.c
===================================================================
*** gcc/tree-ssa-loop-im.c	(revision 228863)
--- gcc/tree-ssa-loop-im.c	(working copy)
*************** static bool
*** 619,674 ****
  extract_true_false_args_from_phi (basic_block dom, gphi *phi,
  				  tree *true_arg_p, tree *false_arg_p)
  {
!   basic_block bb = gimple_bb (phi);
!   edge true_edge, false_edge, tem;
!   tree arg0 = NULL_TREE, arg1 = NULL_TREE;
! 
!   /* We have to verify that one edge into the PHI node is dominated
!      by the true edge of the predicate block and the other edge
!      dominated by the false edge.  This ensures that the PHI argument
!      we are going to take is completely determined by the path we
!      take from the predicate block.
!      We can only use BB dominance checks below if the destination of
!      the true/false edges are dominated by their edge, thus only
!      have a single predecessor.  */
!   extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
!   tem = EDGE_PRED (bb, 0);
!   if (tem == true_edge
!       || (single_pred_p (true_edge->dest)
! 	  && (tem->src == true_edge->dest
! 	      || dominated_by_p (CDI_DOMINATORS,
! 				 tem->src, true_edge->dest))))
!     arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
!   else if (tem == false_edge
! 	   || (single_pred_p (false_edge->dest)
! 	       && (tem->src == false_edge->dest
! 		   || dominated_by_p (CDI_DOMINATORS,
! 				      tem->src, false_edge->dest))))
!     arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
!   else
!     return false;
!   tem = EDGE_PRED (bb, 1);
!   if (tem == true_edge
!       || (single_pred_p (true_edge->dest)
! 	  && (tem->src == true_edge->dest
! 	      || dominated_by_p (CDI_DOMINATORS,
! 				 tem->src, true_edge->dest))))
!     arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
!   else if (tem == false_edge
! 	   || (single_pred_p (false_edge->dest)
! 	       && (tem->src == false_edge->dest
! 		   || dominated_by_p (CDI_DOMINATORS,
! 				      tem->src, false_edge->dest))))
!     arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
!   else
!     return false;
!   if (!arg0 || !arg1)
      return false;
  
    if (true_arg_p)
!     *true_arg_p = arg0;
    if (false_arg_p)
!     *false_arg_p = arg1;
  
    return true;
  }
--- 652,666 ----
  extract_true_false_args_from_phi (basic_block dom, gphi *phi,
  				  tree *true_arg_p, tree *false_arg_p)
  {
!   edge te, fe;
!   if (! extract_true_false_controlled_edges (dom, gimple_bb (phi),
! 					     &te, &fe))
      return false;
  
    if (true_arg_p)
!     *true_arg_p = PHI_ARG_DEF (phi, te->dest_idx);
    if (false_arg_p)
!     *false_arg_p = PHI_ARG_DEF (phi, fe->dest_idx);
  
    return true;
  }

Index: gcc/tree-ssa-sccvn.c
===================================================================
*** gcc/tree-ssa-sccvn.c	(revision 228863)
--- gcc/tree-ssa-sccvn.c	(working copy)
*************** vn_nary_op_insert_stmt (gimple *stmt, tr
*** 2658,2664 ****
  static inline hashval_t
  vn_phi_compute_hash (vn_phi_t vp1)
  {
!   inchash::hash hstate (vp1->block->index);
    tree phi1op;
    tree type;
    edge e;
--- 2704,2711 ----
  static inline hashval_t
  vn_phi_compute_hash (vn_phi_t vp1)
  {
!   inchash::hash hstate (vp1->phiargs.length () > 2
! 			? vp1->block->index : vp1->phiargs.length ());
    tree phi1op;
    tree type;
    edge e;
*************** vn_phi_compute_hash (vn_phi_t vp1)
*** 2685,2690 ****
--- 2732,2738 ----
    return hstate.end ();
  }
  
+ 
  /* Compare two phi entries for equality, ignoring VN_TOP arguments.  */
  
  static int
*************** vn_phi_eq (const_vn_phi_t const vp1, con
*** 2693,2721 ****
    if (vp1->hashcode != vp2->hashcode)
      return false;
  
!   if (vp1->block == vp2->block)
      {
!       int i;
!       tree phi1op;
! 
!       /* If the PHI nodes do not have compatible types
! 	 they are not the same.  */
!       if (!types_compatible_p (vp1->type, vp2->type))
  	return false;
  
!       /* Any phi in the same block will have it's arguments in the
! 	 same edge order, because of how we store phi nodes.  */
!       FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
  	{
! 	  tree phi2op = vp2->phiargs[i];
! 	  if (phi1op == VN_TOP || phi2op == VN_TOP)
! 	    continue;
! 	  if (!expressions_equal_p (phi1op, phi2op))
! 	    return false;
  	}
-       return true;
      }
!   return false;
  }
  
  static vec<tree> shared_lookup_phiargs;
--- 2741,2837 ----
    if (vp1->hashcode != vp2->hashcode)
      return false;
  
!   if (vp1->block != vp2->block)
      {
!       if (vp1->phiargs.length () != vp2->phiargs.length ())
  	return false;
  
!       switch (vp1->phiargs.length ())
  	{
! 	case 1:
! 	  /* Single-arg PHIs are just copies.  */
! 	  break;
! 
! 	case 2:
! 	  {
! 	    /* Rule out backedges into the PHI.  */
! 	    if (vp1->block->loop_father->header == vp1->block
! 		|| vp2->block->loop_father->header == vp2->block)
! 	      return false;
! 
! 	    /* If the PHI nodes do not have compatible types
! 	       they are not the same.  */
! 	    if (!types_compatible_p (vp1->type, vp2->type))
! 	      return false;
! 
! 	    basic_block idom1
! 	      = get_immediate_dominator (CDI_DOMINATORS, vp1->block);
! 	    basic_block idom2
! 	      = get_immediate_dominator (CDI_DOMINATORS, vp2->block);
! 	    /* If the immediate dominator end in switch stmts multiple
! 	       values may end up in the same PHI arg via intermediate
! 	       CFG merges.  */
! 	    if (EDGE_COUNT (idom1->succs) != 2
! 		|| EDGE_COUNT (idom2->succs) != 2)
! 	      return false;
! 
! 	    /* Verify the controlling stmt is the same.  */
! 	    gimple *last1 = last_stmt (idom1);
! 	    gimple *last2 = last_stmt (idom2);
! 	    if (gimple_code (last1) != GIMPLE_COND
! 		|| gimple_code (last2) != GIMPLE_COND)
! 	      return false;
! 	    gcond *cond1 = as_a <gcond *> (last1);
! 	    gcond *cond2 = as_a <gcond *> (last2);
! 	    if (gimple_cond_code (cond1) != gimple_cond_code (cond2)
! 		|| ! expressions_equal_p (gimple_cond_lhs (cond1),
! 				       gimple_cond_lhs (cond2))
! 		|| ! expressions_equal_p (gimple_cond_rhs (cond1),
! 					  gimple_cond_rhs (cond2)))
! 	      return false;
! 
! 	    /* Get at true/false controlled edges into the PHI.  */
! 	    edge te1, te2, fe1, fe2;
! 	    if (! extract_true_false_controlled_edges (idom1, vp1->block,
! 						       &te1, &fe1)
! 		|| ! extract_true_false_controlled_edges (idom2, vp2->block,
! 							  &te2, &fe2))
! 	      return false;
! 
! 	    /* ???  Handle VN_TOP specially.  */
! 	    if (! expressions_equal_p (vp1->phiargs[te1->dest_idx],
! 				       vp2->phiargs[te2->dest_idx])
! 		|| ! expressions_equal_p (vp1->phiargs[fe1->dest_idx],
! 					  vp2->phiargs[fe2->dest_idx]))
! 	      return false;
! 
! 	    return true;
! 	  }
! 
! 	default:
! 	  return false;
  	}
      }
! 
!   /* If the PHI nodes do not have compatible types
!      they are not the same.  */
!   if (!types_compatible_p (vp1->type, vp2->type))
!     return false;
! 
!   /* Any phi in the same block will have it's arguments in the
!      same edge order, because of how we store phi nodes.  */
!   int i;
!   tree phi1op;
!   FOR_EACH_VEC_ELT (vp1->phiargs, i, phi1op)
!     {
!       tree phi2op = vp2->phiargs[i];
!       if (phi1op == VN_TOP || phi2op == VN_TOP)
! 	continue;
!       if (!expressions_equal_p (phi1op, phi2op))
! 	return false;
!     }
! 
!   return true;
  }
  
  static vec<tree> shared_lookup_phiargs;
Index: gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-50.c
===================================================================
*** gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-50.c	(revision 0)
--- gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-50.c	(working copy)
***************
*** 0 ****
--- 1,15 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -ffinite-math-only -fdump-tree-fre1" } */
+ 
+ extern double cos (double);
+ extern double tan (double);
+ 
+ int
+ f1 (double x, double y)
+ {
+   double z1 = cos(y<10 ? x : tan(x<20 ? x : y));
+   double z2 = cos(y<10 ? x : tan(x<20 ? x : y));
+   return z1 == z2;
+ }
+ 
+ /* { dg-final { scan-tree-dump "return 1;" "fre1" } } */