[tree-ssa] Speed up constant propagation [patch]

Diego Novillo dnovillo@redhat.com
Tue Jun 17 04:26:00 GMT 2003


This patch speeds up CCP times by not simulating statements that are
either not interesting for constant propagation or statements that in a
previous pass have been deemed VARYING.

The only statements that are worth simulating in CCP are statements that
produce a value (i.e., non-aliased stores and PHI nodes), and
conditional branches.  Anything else need not be simulated.  Previously
we were simulating everything.

The other optimization is to stop simulating statements once they are
known to produce a VARYING value.  This is particularly effective for
PHI nodes, which are simulated over and over again (even if the basic
block had been executed before).  For regular statements, this may
happen if the statement is added to the list of SSA edges after a
simulation of the statement's inputs changed their lattice values.

Since VARYING is the bottom value in the constant propagation lattice,
once a statement evaluates to VARYING, it cannot change back to CONSTANT
or UNDEFINED.

To avoid repeated hash table lookups, the patch uses the TREE_VISITED
flag to mark those statements that should not be visited again.

Richard, this patch sped up CCP in FieldCentering.cmpl.ii by a factor of
12, reducing compile time by about 22 secs.  Could you try compiling the
rest of POOMA to see whether this happens across the board?  I've gotten
POOMA's sources but I still haven't gotten around to
configuring/compiling it.

Gerald, this sped up CCP for PR8361 by a factor of 2.  The effects are
not as noticeable here, but Jeff, Jason and Andrew have been making
other changes to other parts of the optimizer.  Maybe we are doing a bit
better now.  But PR8361 is uniformly nasty, the only things that are
notorious are parsing and CSE time.


Bootstrapped and tested x86, amd64, ia64 and ppc32.


Diego.

	* tree-ssa-ccp.c (DONT_SIMULATE_AGAIN): Define.
	(visit_phi_node): Don't do anything if the PHI node doesn't need to
	be simulated.
	If the PHI variable does not have real references, consider it
	VARYING.
	If the PHI node has a lattice value of VARYING, set
	DONT_SIMULATE_AGAIN.
	(visit_stmt): Don't do anything if the statement doesn't need to be
	simulated.
	Only visit conditional branches COND_EXPR and SWITCH_EXPR.
	If the statement doesn't produce a result mark it with
	DONT_SIMULATE_AGAIN.
	(visit_assignment): Remove unnecessary def_op() check.
	If the value is VARYING, mark the statement with
	DONT_SIMULATE_AGAIN.
	(visit_cond_stmt): Remove unnecessary is_ctrl_stmt() check.
	If the predicate is VARYING, mark the statement with
	DONT_SIMULATE_AGAIN.
	(initialize): Clear DONT_SIMULATE_AGAIN flag for every statement
	and PHI node.
	(likely_value): Get statement operands after checking if it makes
	aliased loads or has volatile operands.

Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.73
diff -d -c -p -r1.1.2.73 tree-ssa-ccp.c
*** tree-ssa-ccp.c	15 Jun 2003 07:18:01 -0000	1.1.2.73
--- tree-ssa-ccp.c	16 Jun 2003 20:32:45 -0000
*************** typedef enum
*** 61,66 ****
--- 61,69 ----
    VARYING
  } latticevalue;
  
+ /* Use the TREE_VISITED bitflag to mark statements and PHI nodes that have
+    been deemed VARYING and shouldn't be simulated again.  */
+ #define DONT_SIMULATE_AGAIN(T)	TREE_VISITED (T)
  
  /* Main structure for CCP.  Contains the lattice value and, if it's a
      constant, the constant value.  */
*************** visit_phi_node (tree phi)
*** 351,356 ****
--- 354,364 ----
    int i;
    value phi_val;
  
+   /* If the PHI node has already been deemed to be VARYING, don't simulate
+      it again.  */
+   if (DONT_SIMULATE_AGAIN (phi))
+     return;
+ 
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
        fprintf (dump_file, "\nVisiting PHI node: ");
*************** visit_phi_node (tree phi)
*** 360,369 ****
    phi_val.lattice_val = UNDEFINED;
    phi_val.const_val = NULL_TREE;
  
!   /* If the variable is volatile or we have already determined it
!      to be varying, then consider it VARYING.  */
    if (TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi)))
!       || get_value (PHI_RESULT (phi))->lattice_val == VARYING)
      phi_val.lattice_val = VARYING;
    else
      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
--- 368,377 ----
    phi_val.lattice_val = UNDEFINED;
    phi_val.const_val = NULL_TREE;
  
!   /* If the variable is volatile or the variable is never referenced in a
!      real operand, then consider the PHI node VARYING.  */
    if (TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi)))
!       || !var_ann (SSA_NAME_VAR (PHI_RESULT (phi)))->has_real_refs)
      phi_val.lattice_val = VARYING;
    else
      for (i = 0; i < PHI_NUM_ARGS (phi); i++)
*************** visit_phi_node (tree phi)
*** 406,411 ****
--- 414,421 ----
      }
  
    set_lattice_value (PHI_RESULT (phi), phi_val);
+   if (phi_val.lattice_val == VARYING)
+     DONT_SIMULATE_AGAIN (phi) = 1;
  }
  
  
*************** cp_lattice_meet (value val1, value val2)
*** 466,479 ****
  static void
  visit_stmt (tree stmt)
  {
!   varray_type ops;
!   size_t i;
! 
! #if defined ENABLE_CHECKING
!   /* FIXME: This is lame.  All statements should be in GIMPLE form.  */
!   if (TREE_NOT_GIMPLE (stmt))
      return;
- #endif
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
--- 476,485 ----
  static void
  visit_stmt (tree stmt)
  {
!   /* If the statement has already been deemed to be VARYING, don't simulate
!      it again.  */
!   if (DONT_SIMULATE_AGAIN (stmt))
      return;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      {
*************** visit_stmt (tree stmt)
*** 481,487 ****
        print_generic_stmt (dump_file, stmt, TDF_SLIM);
        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
--- 487,493 ----
        print_generic_stmt (dump_file, stmt, TDF_SLIM);
        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
*************** visit_stmt (tree stmt)
*** 495,514 ****
    if (def_op (stmt))
      visit_assignment (stmt);
  
!   /* If STMT is a control statement, see if we can determine which branch
       will be taken.  */
!   else if (is_ctrl_stmt (stmt))
      visit_cond_stmt (stmt);
  
!   /* If STMT is a computed goto, mark all the output edges
!      executable.  */
!   else if (is_computed_goto (stmt))
!     add_outgoing_control_edges (bb_for_stmt (stmt));
  
    /* Mark all VDEF operands VARYING.  */
!   ops = vdef_ops (stmt);
!   for (i = 0; ops && i < VARRAY_ACTIVE_SIZE (ops); i++)
!     def_to_varying (VDEF_RESULT (VARRAY_TREE (ops, i)));
  }
  
  
--- 501,534 ----
    if (def_op (stmt))
      visit_assignment (stmt);
  
!   /* If STMT is a conditional branch, see if we can determine which branch
       will be taken.  */
!   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
      visit_cond_stmt (stmt);
  
!   /* Any other kind of statement is not interesting for constant
!      propagation and, therefore, not worth simulating.  */
!   else
!     {
!       DONT_SIMULATE_AGAIN (stmt) = 1;
! 
!       /* If STMT is a control statement or a computed goto, then mark all
! 	 the output edges executable.  */
!       if (is_ctrl_stmt (stmt) || is_computed_goto (stmt))
! 	add_outgoing_control_edges (bb_for_stmt (stmt));
!     }
  
    /* Mark all VDEF operands VARYING.  */
!   {
!     size_t i;
!     varray_type ops = vdef_ops (stmt);
!     if (ops)
!       {
! 	DONT_SIMULATE_AGAIN (stmt) = 1;
! 	for (i = 0; i < VARRAY_ACTIVE_SIZE (ops); i++)
! 	  def_to_varying (VDEF_RESULT (VARRAY_TREE (ops, i)));
!       }
!   }
  }
  
  
*************** visit_assignment (tree stmt)
*** 521,531 ****
    value val;
    tree lhs, rhs;
  
- #if defined ENABLE_CHECKING
-   if (!def_op (stmt))
-     abort ();
- #endif
- 
    lhs = TREE_OPERAND (stmt, 0);
    rhs = TREE_OPERAND (stmt, 1);
  
--- 541,546 ----
*************** visit_assignment (tree stmt)
*** 571,576 ****
--- 586,593 ----
  
    /* Set the lattice value of the statement's output.  */
    set_lattice_value (*(def_op (stmt)), val);
+   if (val.lattice_val == VARYING)
+     DONT_SIMULATE_AGAIN (stmt) = 1;
  }
  
  
*************** visit_cond_stmt (tree stmt)
*** 584,594 ****
    value val;
    basic_block block;
  
- #if defined ENABLE_CHECKING
-   if (!is_ctrl_stmt (stmt))
-     abort ();
- #endif
- 
    block = bb_for_stmt (stmt);
    val = evaluate_stmt (stmt);
  
--- 601,606 ----
*************** visit_cond_stmt (tree stmt)
*** 599,605 ****
    if (e)
      add_control_edge (e);
    else
!     add_outgoing_control_edges (block);
  }
  
  
--- 611,620 ----
    if (e)
      add_control_edge (e);
    else
!     {
!       DONT_SIMULATE_AGAIN (stmt) = 1;
!       add_outgoing_control_edges (block);
!     }
  }
  
  
*************** initialize (void)
*** 943,952 ****
    executable_blocks = sbitmap_alloc (last_basic_block);
    sbitmap_zero (executable_blocks);
  
!   /* Mark all edges not executable.  */
    FOR_EACH_BB (bb)
!     for (e = bb->succ; e; e = e->succ_next)
!       e->flags &= ~EDGE_EXECUTABLE;
  
    VARRAY_GENERIC_PTR_INIT (cfg_edges, 20, "cfg_edges");
  
--- 958,979 ----
    executable_blocks = sbitmap_alloc (last_basic_block);
    sbitmap_zero (executable_blocks);
  
!   /* Initialize simulation flags for PHI nodes, statements and edges.  */
    FOR_EACH_BB (bb)
!     {
!       block_stmt_iterator i;
!       tree phi;
! 
!       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
! 	DONT_SIMULATE_AGAIN (phi) = 0;
! 
!       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
! 	DONT_SIMULATE_AGAIN (bsi_stmt (i)) = 0;
! 
!       for (e = bb->succ; e; e = e->succ_next)
! 	e->flags &= ~EDGE_EXECUTABLE;
!     }
! 
  
    VARRAY_GENERIC_PTR_INIT (cfg_edges, 20, "cfg_edges");
  
*************** set_lattice_value (tree var, value val)
*** 1088,1094 ****
  	      old_val->lattice_val = CONSTANT;
  	      old_val->const_val = val.const_val;
  	    }
- 
  	}
      }
  }
--- 1115,1120 ----
*************** likely_value (tree stmt)
*** 1140,1152 ****
    int found_constant = 0;
    stmt_ann_t ann;
  
-   get_stmt_operands (stmt);
- 
    /* If the statement makes aliased loads or has volatile operands, it
       won't fold to a constant value.  */
    ann = stmt_ann (stmt);
    if (ann->makes_aliased_loads || ann->has_volatile_ops)
      return VARYING;
  
    uses = use_ops (stmt);
    for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
--- 1166,1178 ----
    int found_constant = 0;
    stmt_ann_t ann;
  
    /* If the statement makes aliased loads or has volatile operands, it
       won't fold to a constant value.  */
    ann = stmt_ann (stmt);
    if (ann->makes_aliased_loads || ann->has_volatile_ops)
      return VARYING;
+ 
+   get_stmt_operands (stmt);
  
    uses = use_ops (stmt);
    for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)




More information about the Gcc-patches mailing list