This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] More PR56113 PTA speedups


This reduces the work done for single predecessor nodes for
assigning pointer equivalence classes in label_visit.  For
the PR56113 testcase with n = 40000 this reduces PTA time from

 tree PTA                : 119.59 (34%) usr

to

 tree PTA                :  51.62 (18%) usr

(the percentages are with the domwalk fix applied).

Easy optimization with a surprisingly big effect.  On the way
I also reduce the work done for non-direct nodes.

Bootstrap and regtest pending on x86_64-unknown-linux-gnu.

Richard.

2013-02-01  Richard Biener  <rguenther@suse.de>

	* tree-ssa-structalias.c (label_visit): Reduce work for
	single-predecessor nodes.

Index: gcc/tree-ssa-structalias.c
===================================================================
*** gcc/tree-ssa-structalias.c	(revision 195641)
--- gcc/tree-ssa-structalias.c	(working copy)
*************** condense_visit (constraint_graph_t graph
*** 2107,2120 ****
  static void
  label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
  {
!   unsigned int i;
    bitmap_iterator bi;
-   bitmap_set_bit (si->visited, n);
  
!   if (!graph->points_to[n])
!     graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
  
    /* Label and union our incoming edges's points to sets.  */
    EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
      {
        unsigned int w = si->node_mapping[i];
--- 2108,2120 ----
  static void
  label_visit (constraint_graph_t graph, struct scc_info *si, unsigned int n)
  {
!   unsigned int i, first_pred;
    bitmap_iterator bi;
  
!   bitmap_set_bit (si->visited, n);
  
    /* Label and union our incoming edges's points to sets.  */
+   first_pred = -1U;
    EXECUTE_IF_IN_NONNULL_BITMAP (graph->preds[n], 0, i, bi)
      {
        unsigned int w = si->node_mapping[i];
*************** label_visit (constraint_graph_t graph, s
*** 2126,2136 ****
  	continue;
  
        if (graph->points_to[w])
! 	bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
      }
!   /* Indirect nodes get fresh variables.  */
    if (!bitmap_bit_p (graph->direct_nodes, n))
!     bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
  
    if (!bitmap_empty_p (graph->points_to[n]))
      {
--- 2126,2170 ----
  	continue;
  
        if (graph->points_to[w])
! 	{
! 	  if (first_pred == -1U)
! 	    first_pred = w;
! 	  else if (!graph->points_to[n])
! 	    {
! 	      graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
! 	      bitmap_ior (graph->points_to[n],
! 			  graph->points_to[first_pred], graph->points_to[w]);
! 	    }
! 	  else
! 	    bitmap_ior_into(graph->points_to[n], graph->points_to[w]);
! 	}
      }
! 
!   /* Indirect nodes get fresh variables and a new pointer equiv class.  */
    if (!bitmap_bit_p (graph->direct_nodes, n))
!     {
!       if (!graph->points_to[n])
! 	{
! 	  graph->points_to[n] = BITMAP_ALLOC (&predbitmap_obstack);
! 	  if (first_pred != -1U)
! 	    bitmap_copy (graph->points_to[n], graph->points_to[first_pred]);
! 	}
!       bitmap_set_bit (graph->points_to[n], FIRST_REF_NODE + n);
!       graph->pointer_label[n] = pointer_equiv_class++;
!       return;
!     }
! 
!   /* If there was only a single non-empty predecessor the pointer equiv
!      class is the same.  */
!   if (!graph->points_to[n])
!     {
!       if (first_pred != -1U)
! 	{
! 	  graph->pointer_label[n] = graph->pointer_label[first_pred];
! 	  graph->points_to[n] = graph->points_to[first_pred];
! 	}
!       return;
!     }
  
    if (!bitmap_empty_p (graph->points_to[n]))
      {


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]