[PATCH] Make SSA propagator iteration order consistent

[Richard Biener <rguenther at suse dot de>]

The intent (as I read it) of the iteration order in ssa_propagate is
to process stmts in the following order:

 1) complete simulation of BBs from making one of their entries executable
 2) simulation of stmts fed by stmts that changed to VARYING
 3) simulation of the rest of stmts fed by stmts that changed their 
lattice value

but the current implementation fails to enforce this order because it
drains the full worklists before considering entries added to the
others by simulating a statement.  This leads to quite some extra
simulation with too optimistic values from not yet executable edges
(just run into this while debugging PR66733).

The current state is that of the original propagator implementation
in this area.

The patch cuts the number of visited stmts for the testcase in PR66773
from 23 to 20 (it visits PHI nodes 3 times less).

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

Richard.

2015-07-06  Richard Biener  <rguenther@suse.de>

	* tree-ssa-propagate.c (add_ssa_edge): Dump what edge list we
	add which use to.
	(add_control_edge): Remove excessive vertical space in dumping.
	(process_ssa_edge_worklist): Simulate at most one statement and
	return whether we did.  Do not simulate PHIs if they are in a
	BB not yet simulated.
	(ssa_propagate): Adjust to always drain the BB worklist whenever
	a BB is available there, likewise the VARYING edges list before
	the interesting edge list.

Index: gcc/tree-ssa-propagate.c
===================================================================
*** gcc/tree-ssa-propagate.c	(revision 225449)
--- gcc/tree-ssa-propagate.c	(working copy)
*************** add_ssa_edge (tree var, bool is_varying)
*** 281,289 ****
  	{
  	  gimple_set_plf (use_stmt, STMT_IN_SSA_EDGE_WORKLIST, true);
  	  if (is_varying)
! 	    varying_ssa_edges.safe_push (use_stmt);
  	  else
! 	    interesting_ssa_edges.safe_push (use_stmt);
  	}
      }
  }
--- 281,303 ----
  	{
  	  gimple_set_plf (use_stmt, STMT_IN_SSA_EDGE_WORKLIST, true);
  	  if (is_varying)
! 	    {
! 	      if (dump_file && (dump_flags & TDF_DETAILS))
! 		{
! 		  fprintf (dump_file, "varying_ssa_edges: adding SSA use in ");
! 		  print_gimple_stmt (dump_file, use_stmt, 0, TDF_SLIM);
! 		}
! 	      varying_ssa_edges.safe_push (use_stmt);
! 	    }
  	  else
! 	    {
! 	      if (dump_file && (dump_flags & TDF_DETAILS))
! 		{
! 		  fprintf (dump_file, "interesting_ssa_edges: adding SSA use in ");
! 		  print_gimple_stmt (dump_file, use_stmt, 0, TDF_SLIM);
! 		}
! 	      interesting_ssa_edges.safe_push (use_stmt);
! 	    }
  	}
      }
  }
*************** add_control_edge (edge e)
*** 311,317 ****
    cfg_blocks_add (bb);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
!     fprintf (dump_file, "\nAdding Destination of edge (%d -> %d) to worklist\n",
  	e->src->index, e->dest->index);
  }
  
--- 325,331 ----
    cfg_blocks_add (bb);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
!     fprintf (dump_file, "Adding destination of edge (%d -> %d) to worklist\n",
  	e->src->index, e->dest->index);
  }
  
*************** simulate_stmt (gimple stmt)
*** 414,427 ****
  
  /* Process an SSA edge worklist.  WORKLIST is the SSA edge worklist to
     drain.  This pops statements off the given WORKLIST and processes
!    them until there are no more statements on WORKLIST.
!    We take a pointer to WORKLIST because it may be reallocated when an
!    SSA edge is added to it in simulate_stmt.  */
  
! static void
! process_ssa_edge_worklist (vec<gimple> *worklist)
  {
!   /* Drain the entire worklist.  */
    while (worklist->length () > 0)
      {
        basic_block bb;
--- 428,442 ----
  
  /* Process an SSA edge worklist.  WORKLIST is the SSA edge worklist to
     drain.  This pops statements off the given WORKLIST and processes
!    them until one statement was simulated or there are no more statements
!    on WORKLIST.  We take a pointer to WORKLIST because it may be reallocated
!    when an SSA edge is added to it in simulate_stmt.  Return true if a stmt
!    was simulated.  */
  
! static bool 
! process_ssa_edge_worklist (vec<gimple> *worklist, const char *edge_list_name)
  {
!   /* Process the next entry from the worklist.  */
    while (worklist->length () > 0)
      {
        basic_block bb;
*************** process_ssa_edge_worklist (vec<gimple> *
*** 437,457 ****
        /* STMT is no longer in a worklist.  */
        gimple_set_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST, false);
  
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
! 	  fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
  	  print_gimple_stmt (dump_file, stmt, 0, dump_flags);
  	}
  
!       bb = gimple_bb (stmt);
  
!       /* PHI nodes are always visited, regardless of whether or not
! 	 the destination block is executable.  Otherwise, visit the
! 	 statement only if its block is marked executable.  */
!       if (gimple_code (stmt) == GIMPLE_PHI
! 	  || bitmap_bit_p (executable_blocks, bb->index))
! 	simulate_stmt (stmt);
      }
  }
  
  
--- 452,486 ----
        /* STMT is no longer in a worklist.  */
        gimple_set_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST, false);
  
+       bb = gimple_bb (stmt);
+ 
+       /* Visit the statement only if its block is marked executable.
+          If it is not executable then it will be visited when we simulate
+ 	 all statements in the block as soon as an incoming edge gets
+ 	 marked executable.  */
+       if (!bitmap_bit_p (executable_blocks, bb->index))
+ 	{
+ 	  if (dump_file && (dump_flags & TDF_DETAILS))
+ 	    {
+ 	      fprintf (dump_file, "\nDropping statement from SSA worklist: ");
+ 	      print_gimple_stmt (dump_file, stmt, 0, dump_flags);
+ 	    }
+ 	  continue;
+ 	}
+ 
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
! 	  fprintf (dump_file, "\nSimulating statement (from %s): ",
! 		   edge_list_name);
  	  print_gimple_stmt (dump_file, stmt, 0, dump_flags);
  	}
  
!       simulate_stmt (stmt);
  
!       return true;
      }
+ 
+   return false;
  }
  
  
*************** ssa_propagate (ssa_prop_visit_stmt_fn vi
*** 917,930 ****
  	  /* Pull the next block to simulate off the worklist.  */
  	  basic_block dest_block = cfg_blocks_get ();
  	  simulate_block (dest_block);
  	}
  
        /* In order to move things to varying as quickly as
  	 possible,process the VARYING_SSA_EDGES worklist first.  */
!       process_ssa_edge_worklist (&varying_ssa_edges);
  
        /* Now process the INTERESTING_SSA_EDGES worklist.  */
!       process_ssa_edge_worklist (&interesting_ssa_edges);
      }
  
    ssa_prop_fini ();
--- 946,962 ----
  	  /* Pull the next block to simulate off the worklist.  */
  	  basic_block dest_block = cfg_blocks_get ();
  	  simulate_block (dest_block);
+ 	  continue;
  	}
  
        /* In order to move things to varying as quickly as
  	 possible,process the VARYING_SSA_EDGES worklist first.  */
!       if (process_ssa_edge_worklist (&varying_ssa_edges, "varying_ssa_edges"))
! 	continue;
  
        /* Now process the INTERESTING_SSA_EDGES worklist.  */
!       process_ssa_edge_worklist (&interesting_ssa_edges,
! 				 "interesting_ssa_edges");
      }
  
    ssa_prop_fini ();