[ tree-ssa ] Avoid useless reevaluations in CCP

[law at redhat dot com]

Tree CCP has the nasty habit of performing pointless reevaluations of
statements.  This can happen due to a couple of implementation details.

First it's worth noting that the ssa_edges worklist is a list of 
definitions which need their immediate uses reevaluated.

  1. We can get duplicate entries on the ssa_edges worklist.  Roughly
     1% of the time we wanted to add a new def to the ssa_edges worklist
     the def was already on the worklist.

     This can be addressed simply by tracking which def sites are on
     the worklist and avoid adding a def that is already on the list.
  
  2. visit_stmt when called via simulate_block can evaluate a statement
     that will be later reevaluated because a def which feeds the statement
     handled in visit_stmt is currently on the ssa_edges worklist.


#1 is easy to fix by keeping track of what defs are on the worklist
and avoiding adding a def that is already on the list.

#2 is harder.  To avoid these we need to change the nature of the
worklist.  Specifically we need to change it to a worklist of statements
that need to be reevaluated.  That way when visit_stmt evaluates a 
statement it can "delete" the statement from the worklist.

[ It's not actually deleted since we don't have a convenient way to 
  get to the stmt's entry on the worklist.  So instead we "cancel" it
  by setting a bit indicating we don't need the value which instructs
  the main loop to not reevaluate that stmt. ]


Anyway, with this patch we now avoid the wasteful reevaluations, which
also helps avoid creating useless copies of nodes, etc etc.

This change cuts another 15% off the time charged to CCP for my batch of
tests (that translates into about 1 second off the total compile time)
Not huge, but CCP is slowly, but surely getting close to reasonable
performance.

	* tree-flow.h (struct stmt_ann_d): Add new field in_ccp_worklist.
	* tree-ssa-ccp.c (simulate_stmt): Renamed from simulate_def_use_edges.
	(add_var_to_ssa_edges_worklist): New function.  Only add statements
	to the ssa_edges worklist if they are not already on the worklist.
	(def_to_undefined, def_to_varying, set_lattice_value)
	(tree_ssa_ccp): Only reevaluate the statement if in_ccp_worklist
	is set for the element popped off the ssa_edges worklist.
	(simulate_statement): Simplify now that ssa_edges is a worklist
	of statements to reevaluate rather than a worklist of defs
	that need their immediate uses reevaluated.
	(visit_stmt): Clear in_ccp_worklist.
	
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.56
diff -c -3 -p -r1.1.4.56 tree-flow.h
*** tree-flow.h	13 Feb 2003 17:30:25 -0000	1.1.4.56
--- tree-flow.h	14 Feb 2003 22:13:40 -0000
*************** struct stmt_ann_d GTY(())
*** 146,151 ****
--- 146,156 ----
       need to be scanned again).  */
    unsigned modified : 1;
  
+   /* Nonzero if the statement is in the CCP worklist and has not been
+      "cancelled".  If we ever need to use this bit outside CCP, then
+      it should be renamed.  */
+   unsigned in_ccp_worklist: 1;
+ 
    /* Basic block that contains this statement.  */
    basic_block GTY ((skip (""))) bb;
  
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.50
diff -c -3 -p -r1.1.2.50 tree-ssa-ccp.c
*** tree-ssa-ccp.c	14 Feb 2003 17:49:25 -0000	1.1.2.50
--- tree-ssa-ccp.c	14 Feb 2003 22:13:52 -0000
*************** static value cp_lattice_meet		PARAMS ((v
*** 103,115 ****
  static void visit_stmt			PARAMS ((tree));
  static void visit_cond_stmt		PARAMS ((tree));
  static void visit_assignment		PARAMS ((tree));
  static void add_outgoing_control_edges	PARAMS ((basic_block));
  static void add_control_edge		PARAMS ((edge));
  static void def_to_undefined		PARAMS ((tree));
  static void def_to_varying		PARAMS ((tree));
  static void set_lattice_value		PARAMS ((tree, value));
  static void simulate_block		PARAMS ((basic_block));
! static void simulate_def_use_edges	PARAMS ((tree));
  static void substitute_and_fold		PARAMS ((void));
  static value evaluate_stmt		PARAMS ((tree));
  static void dump_lattice_value		PARAMS ((FILE *, const char *, value));
--- 103,116 ----
  static void visit_stmt			PARAMS ((tree));
  static void visit_cond_stmt		PARAMS ((tree));
  static void visit_assignment		PARAMS ((tree));
+ static void add_var_to_ssa_edges_worklist PARAMS ((tree));
  static void add_outgoing_control_edges	PARAMS ((basic_block));
  static void add_control_edge		PARAMS ((edge));
  static void def_to_undefined		PARAMS ((tree));
  static void def_to_varying		PARAMS ((tree));
  static void set_lattice_value		PARAMS ((tree, value));
  static void simulate_block		PARAMS ((basic_block));
! static void simulate_stmt		PARAMS ((tree));
  static void substitute_and_fold		PARAMS ((void));
  static value evaluate_stmt		PARAMS ((tree));
  static void dump_lattice_value		PARAMS ((FILE *, const char *, value));
*************** tree_ssa_ccp (fndecl)
*** 159,169 ****
           drain the entire worklist each iteration through this loop.  */
        while (VARRAY_ACTIVE_SIZE (ssa_edges) > 0)
  	{
! 	  /* Pull the next reference off the worklist.  The SSA edges
! 	     worklist stores the origination definition for each edge.  */
! 	  tree def = VARRAY_TOP_TREE (ssa_edges);
  	  VARRAY_POP (ssa_edges);
! 	  simulate_def_use_edges (def);
  	}
      }
  
--- 160,176 ----
           drain the entire worklist each iteration through this loop.  */
        while (VARRAY_ACTIVE_SIZE (ssa_edges) > 0)
  	{
! 	  /* Pull the statement to simulate off the worklist.  */
! 	  tree stmt = VARRAY_TOP_TREE (ssa_edges);
  	  VARRAY_POP (ssa_edges);
! 
! 	  /* visit_stmt can "cancel" reevaluation of some statements.
! 	     If it does, then in_ccp_worklist will be zero.  */
! 	  if (stmt_ann (stmt)->in_ccp_worklist)
! 	    {
! 	      stmt_ann (stmt)->in_ccp_worklist = 0;
! 	      simulate_stmt (stmt);
! 	    }
  	}
      }
  
*************** simulate_block (block)
*** 240,277 ****
     statements reached by it.  */
  
  static void
! simulate_def_use_edges (def_stmt)
!      tree def_stmt;
  {
!   size_t i;
!   varray_type imm_uses;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
!       fprintf (dump_file, "\nSimulating def-use edges for statement: ");
!       print_generic_stmt (dump_file, def_stmt, 0);
      }
  
!   imm_uses = immediate_uses (def_stmt);
!   if (imm_uses)
!     for (i = 0; i < VARRAY_ACTIVE_SIZE (imm_uses); i++)
!       {
! 	tree use_stmt = VARRAY_TREE (imm_uses, i);
! 	basic_block use_bb = bb_for_stmt (use_stmt);
! 
! 	if (TREE_CODE (use_stmt) == PHI_NODE)
! 	  {
! 	    /* PHI nodes are always visited, regardless of whether or not the
! 	      destination block is executable.  */
! 	    visit_phi_node (use_stmt);
! 	  }
! 	else if (TEST_BIT (executable_blocks, use_bb->index))
! 	  {
! 	    /* Otherwise, visit the statement containing the use reached by
! 	      DEF, only if the destination block is marked executable.  */
! 	    visit_stmt (use_stmt);
! 	  }
!       }
  }
  
  
--- 247,275 ----
     statements reached by it.  */
  
  static void
! simulate_stmt (use_stmt)
!      tree use_stmt;
  {
!   basic_block use_bb = bb_for_stmt (use_stmt);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
!       fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
!       print_generic_stmt (dump_file, use_stmt, 0);
      }
  
!   if (TREE_CODE (use_stmt) == PHI_NODE)
!     {
!       /* PHI nodes are always visited, regardless of whether or not the
!          destination block is executable.  */
!       visit_phi_node (use_stmt);
!     }
!   else if (TEST_BIT (executable_blocks, use_bb->index))
!     {
!       /* Otherwise, visit the statement containing the use reached by
!          DEF, only if the destination block is marked executable.  */
!       visit_stmt (use_stmt);
!     }
  }
  
  
*************** visit_stmt (stmt)
*** 477,482 ****
--- 475,487 ----
        fprintf (dump_file, "\n");
      }
    
+   /* If this statement is already in the worklist then "cancel" it.  The
+      reevaluation implied by the worklist entry will produce the same
+      value we generate here and thus reevaluting it again from the
+      worklist is pointless.  */
+   if (stmt_ann (stmt)->in_ccp_worklist)
+     stmt_ann (stmt)->in_ccp_worklist = 0;
+ 
    /* Now examine the statement.  If the statement produces an output
       value, evaluate it to see if the lattice value of its output has
       changed.  */
*************** finalize ()
*** 796,801 ****
--- 801,829 ----
    htab_delete (const_values);
  }
  
+ /* We have just definited a new value for VAR.  Add all immediate uses
+    of VAR to the ssa_edges worklist.  */
+ static void
+ add_var_to_ssa_edges_worklist (var)
+      tree var;
+ {
+   varray_type imm_uses = immediate_uses (SSA_NAME_DEF_STMT (var));
+   if (imm_uses)
+     {
+       unsigned int i;
+ 
+       for (i = 0; i < VARRAY_ACTIVE_SIZE (imm_uses); i++)
+ 	{
+ 	  tree use = VARRAY_TREE (imm_uses, i);
+ 
+ 	  if (stmt_ann (use)->in_ccp_worklist == 0)
+ 	    {
+ 	      stmt_ann (use)->in_ccp_worklist = 1;
+ 	      VARRAY_PUSH_TREE (ssa_edges, use);
+ 	    }
+ 	}
+     }
+ }
  
  /* Set the lattice value for the variable VAR to UNDEFINED.  */
  
*************** def_to_undefined (var)
*** 812,818 ****
       Thus, it can appear that we get a VARYING -> UNDEFINED transition
       when all that is really happening is we are setting the initial
       value for the object to UNDEFINED.  */
-      VARYING
    if (value->lattice_val == CONSTANT)
      abort ();
  #endif
--- 840,845 ----
*************** def_to_undefined (var)
*** 822,828 ****
        if (dump_file && (dump_flags & TDF_DETAILS))
  	fprintf (dump_file, "Lattice value changed.  Adding definition to SSA edges.\n");
  
!       VARRAY_PUSH_TREE (ssa_edges, SSA_NAME_DEF_STMT (var));
        value->lattice_val = UNDEFINED;
        value->const_val = NULL_TREE;
      }
--- 849,855 ----
        if (dump_file && (dump_flags & TDF_DETAILS))
  	fprintf (dump_file, "Lattice value changed.  Adding definition to SSA edges.\n");
  
!       add_var_to_ssa_edges_worklist (var);
        value->lattice_val = UNDEFINED;
        value->const_val = NULL_TREE;
      }
*************** def_to_varying (var)
*** 843,849 ****
        if (dump_file && (dump_flags & TDF_DETAILS))
  	fprintf (dump_file, "Lattice value changed.  Adding definition to SSA edges.\n");
  
!       VARRAY_PUSH_TREE (ssa_edges, SSA_NAME_DEF_STMT (var));
        value->lattice_val = VARYING;
        value->const_val = NULL_TREE;
      }
--- 870,876 ----
        if (dump_file && (dump_flags & TDF_DETAILS))
  	fprintf (dump_file, "Lattice value changed.  Adding definition to SSA edges.\n");
  
!       add_var_to_ssa_edges_worklist (var);
        value->lattice_val = VARYING;
        value->const_val = NULL_TREE;
      }
*************** set_lattice_value (var, val)
*** 878,883 ****
--- 905,912 ----
  	      fprintf (dump_file, ".  Adding definition to SSA edges.\n");
  	    }
  
+           add_var_to_ssa_edges_worklist (var);
+ 
  #ifdef ENABLE_CHECKING
  	  /* VARYING -> CONSTANT is an invalid state transition.  */
  	  if (old_val->lattice_val == VARYING)
*************** set_lattice_value (var, val)
*** 897,903 ****
  	      old_val->const_val = val.const_val;
  	    }
  
- 	  VARRAY_PUSH_TREE (ssa_edges, SSA_NAME_DEF_STMT (var));
  	}
      }
  }
--- 926,931 ----