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]

speedup TER (28071 again)


The second patch for PR 28071, this patch addresses a timing problem
with TER.  Again, not so sure its stage 3 material, but maybe a hair
more so than the live range patch...

When tracking dependences, TER was utilizing a linked list of values.
This was never expected to get very large, so no further thought really
went into it.  Large testcase with a lot of replacements could cause
these lists to be very large, and dominate the timings in out-of-ssa.  

It also turns out that the lists are really just tracking either ssa
version numbers, or out-of-ssa partition numbers, both are integers.
This patch replaces those lists with bitmaps instead.  The results speak
for themselves.

little change is seen in most cases, but the testcase from PR 28071:

at -O2 timings go from:
   tree SSA to normal    :  30.79 (19%) usr   0.06 ( 2%) sys  31.89 (19%) wall
to
   tree SSA to normal    :   1.33 ( 1%) usr   0.02 ( 1%) sys   1.86 ( 1%) wall


and at -O3:
   tree SSA to normal    :  32.08 (35%) usr   0.08 ( 1%) sys  32.92 (28%) wall
to
   tree SSA to normal    :  18.75 (24%) usr   0.06 ( 1%) sys  18.83 (23%) wall


When combined with earlier live range patch the -O2 time goes from:
   tree SSA to normal    :  30.79 (19%) usr   0.06 ( 2%) sys  31.89 (19%) wall
to
   tree SSA to normal    :   1.16 ( 1%) usr   0.01 ( 0%) sys   1.17 ( 1%) wall

T
he -O3 time goes from:
   tree SSA to normal    :  32.08 (35%) usr   0.08 ( 1%) sys  32.92 (28%) wall
to
   tree SSA to normal    :   2.50 ( 4%) usr   0.08 ( 1%) sys   2.61 ( 2%) wall


This patch has been bootstrapped on 1686-pc-linux-gnu with no new
regressions.


Andrew

2006-08-24  Andrew MacLeod  <amacleod@redhat.com>

	* tree-outof-ssa.c (struct value_expr_d): Remove.
	(struct temp_expr_table_d): Change value_expr_p's to bitmap.  Delete
	free_list.
	(new_temp_expr_table, free_temp_expr_table): Update.
	(new_value_expr, free_value_expr, find_value_in_list, add_value_to_list,
	add_info_to_list, remove_value_from_list): Delete.
	(add_value_to_version_list): New.  Set bit in version list, allocating 
	a bitmap if need be.
	(add_value_to_partition_list): New.  Set bit in the partition list, 
	allocating a bitmap if need be.
	(remove_value_from_partition_list): New.  Remove a bit from the
	partition list, free the bitmap if it is empty.
	(add_dependence, check_replaceable, finish_expr, mark_replaceable,
	kill_expr, find_replaceable_in_bb, find_replaceable_exprs): Use bitmap 
	routines and new functions.

Index: tree-outof-ssa.c
===================================================================
*** tree-outof-ssa.c	(revision 116309)
--- tree-outof-ssa.c	(working copy)
*************** coalesce_vars (var_map map, tree_live_in
*** 1282,1297 ****
     it is replaced with the RHS of the defining expression.  */
  
  
- /* Dependency list element.  This can contain either a partition index or a
-    version number, depending on which list it is in.  */
- 
- typedef struct value_expr_d 
- {
-   int value;
-   struct value_expr_d *next;
- } *value_expr_p;
- 
- 
  /* Temporary Expression Replacement (TER) table information.  */
  
  typedef struct temp_expr_table_d 
--- 1282,1287 ----
*************** typedef struct temp_expr_table_d 
*** 1299,1311 ****
    var_map map;
    void **version_info;
    bitmap *expr_vars;
!   value_expr_p *partition_dep_list;
    bitmap replaceable;
    bool saw_replaceable;
    int virtual_partition;
    bitmap partition_in_use;
!   value_expr_p free_list;
!   value_expr_p pending_dependence;
  } *temp_expr_table_p;
  
  /* Used to indicate a dependency on V_MAY_DEFs.  */
--- 1289,1300 ----
    var_map map;
    void **version_info;
    bitmap *expr_vars;
!   bitmap *partition_dep_list;
    bitmap replaceable;
    bool saw_replaceable;
    int virtual_partition;
    bitmap partition_in_use;
!   bitmap pending_dependence;
  } *temp_expr_table_p;
  
  /* Used to indicate a dependency on V_MAY_DEFs.  */
*************** typedef struct temp_expr_table_d 
*** 1313,1326 ****
  
  static temp_expr_table_p new_temp_expr_table (var_map);
  static tree *free_temp_expr_table (temp_expr_table_p);
! static inline value_expr_p new_value_expr (temp_expr_table_p);
! static inline void free_value_expr (temp_expr_table_p, value_expr_p);
! static inline value_expr_p find_value_in_list (value_expr_p, int, 
! 					       value_expr_p *);
! static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
! static inline void add_info_to_list (temp_expr_table_p, value_expr_p *, 
! 				     value_expr_p);
! static value_expr_p remove_value_from_list (value_expr_p *, int);
  static void add_dependence (temp_expr_table_p, int, tree);
  static bool check_replaceable (temp_expr_table_p, tree);
  static void finish_expr (temp_expr_table_p, int, bool);
--- 1302,1310 ----
  
  static temp_expr_table_p new_temp_expr_table (var_map);
  static tree *free_temp_expr_table (temp_expr_table_p);
! static inline void add_value_to_version_list (temp_expr_table_p, int, int);
! static inline void add_value_to_partition_list (temp_expr_table_p, int, int);
! static inline void remove_value_from_partition_list (temp_expr_table_p, int, int);
  static void add_dependence (temp_expr_table_p, int, tree);
  static bool check_replaceable (temp_expr_table_p, tree);
  static void finish_expr (temp_expr_table_p, int, bool);
*************** new_temp_expr_table (var_map map)
*** 1344,1350 ****
  
    t->version_info = XCNEWVEC (void *, num_ssa_names + 1);
    t->expr_vars = XCNEWVEC (bitmap, num_ssa_names + 1);
!   t->partition_dep_list = XCNEWVEC (value_expr_p,
                                      num_var_partitions (map) + 1);
  
    t->replaceable = BITMAP_ALLOC (NULL);
--- 1328,1334 ----
  
    t->version_info = XCNEWVEC (void *, num_ssa_names + 1);
    t->expr_vars = XCNEWVEC (bitmap, num_ssa_names + 1);
!   t->partition_dep_list = XCNEWVEC (bitmap,
                                      num_var_partitions (map) + 1);
  
    t->replaceable = BITMAP_ALLOC (NULL);
*************** new_temp_expr_table (var_map map)
*** 1352,1359 ****
  
    t->saw_replaceable = false;
    t->virtual_partition = num_var_partitions (map);
!   t->free_list = NULL;
!   t->pending_dependence = NULL;
  
    return t;
  }
--- 1336,1342 ----
  
    t->saw_replaceable = false;
    t->virtual_partition = num_var_partitions (map);
!   t->pending_dependence = BITMAP_ALLOC (NULL);
  
    return t;
  }
*************** new_temp_expr_table (var_map map)
*** 1365,1371 ****
  static tree *
  free_temp_expr_table (temp_expr_table_p t)
  {
-   value_expr_p p;
    tree *ret = NULL;
    unsigned i;
  
--- 1348,1353 ----
*************** free_temp_expr_table (temp_expr_table_p 
*** 1375,1386 ****
      gcc_assert (!t->partition_dep_list[x]);
  #endif
  
-   while ((p = t->free_list))
-     {
-       t->free_list = p->next;
-       free (p);
-     }
- 
    BITMAP_FREE (t->partition_in_use);
    BITMAP_FREE (t->replaceable);
  
--- 1357,1362 ----
*************** free_temp_expr_table (temp_expr_table_p 
*** 1400,1509 ****
  }
  
  
! /* Allocate a new value list node. Take it from the free list in TABLE if 
!    possible.  */
! 
! static inline value_expr_p
! new_value_expr (temp_expr_table_p table)
! {
!   value_expr_p p;
!   if (table->free_list)
!     {
!       p = table->free_list;
!       table->free_list = p->next;
!     }
!   else
!     p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
! 
!   return p;
! }
! 
! 
! /* Add value list node P to the free list in TABLE.  */
  
  static inline void
! free_value_expr (temp_expr_table_p table, value_expr_p p)
  {
-   p->next = table->free_list;
-   table->free_list = p;
- }
- 
  
! /* Find VALUE if it's in LIST.  Return a pointer to the list object if found,  
!    else return NULL.  If LAST_PTR is provided, it will point to the previous 
!    item upon return, or NULL if this is the first item in the list.  */
  
! static inline value_expr_p
! find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
! {
!   value_expr_p curr;
!   value_expr_p last = NULL;
! 
!   for (curr = list; curr; last = curr, curr = curr->next)
!     {
!       if (curr->value == value)
!         break;
!     }
!   if (last_ptr)
!     *last_ptr = last;
!   return curr;
  }
  
  
! /* Add VALUE to LIST, if it isn't already present.  TAB is the expression 
!    table */
  
  static inline void
! add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
  {
-   value_expr_p info;
  
!   if (!find_value_in_list (*list, value, NULL))
!     {
!       info = new_value_expr (tab);
!       info->value = value;
!       info->next = *list;
!       *list = info;
!     }
  }
  
  
! /* Add value node INFO if it's value isn't already in LIST.  Free INFO if
!    it is already in the list. TAB is the expression table.  */
  
! static inline void
! add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
  {
!   if (find_value_in_list (*list, info->value, NULL))
!     free_value_expr (tab, info);
!   else
      {
!       info->next = *list;
!       *list = info;
      }
  }
  
  
- /* Look for VALUE in LIST.  If found, remove it from the list and return it's 
-    pointer.  */
- 
- static value_expr_p
- remove_value_from_list (value_expr_p *list, int value)
- {
-   value_expr_p info, last;
- 
-   info = find_value_in_list (*list, value, &last);
-   if (!info)
-     return NULL;
-   if (!last)
-     *list = info->next;
-   else
-     last->next = info->next;
-  
-   return info;
- }
- 
- 
  /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is 
     replaceable by an expression, add a dependence each of the elements of the 
     expression.  These are contained in the pending list.  TAB is the
--- 1376,1422 ----
  }
  
  
! /* Add VALUE to the version list for LIST.  TAB is the expression table */
  
  static inline void
! add_value_to_version_list (temp_expr_table_p tab, int list, int value)
  {
  
!   if (!tab->version_info[list])
!     tab->version_info[list] = BITMAP_ALLOC (NULL);
  
!   bitmap_set_bit (tab->version_info[list], value);
  }
  
  
! /* Add VALUE to the partition list for LIST.  TAB is the expression table */
  
  static inline void
! add_value_to_partition_list (temp_expr_table_p tab, int list, int value)
  {
  
!   if (!tab->partition_dep_list[list])
!     tab->partition_dep_list[list] = BITMAP_ALLOC (NULL);
! 
!   bitmap_set_bit (tab->partition_dep_list[list], value);
  }
  
  
! /* Remove VALUE from the partition list for LIST.  TAB is the expression 
!    table.  */
  
! static inline void 
! remove_value_from_partition_list (temp_expr_table_p tab, int list, int value)
  {
!   bitmap_clear_bit (tab->partition_dep_list[list], value);
!   if (bitmap_empty_p (tab->partition_dep_list[list]))
      {
!       BITMAP_FREE (tab->partition_dep_list[list]);
!       tab->partition_dep_list[list] = NULL;
      }
  }
  
  
  /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is 
     replaceable by an expression, add a dependence each of the elements of the 
     expression.  These are contained in the pending list.  TAB is the
*************** remove_value_from_list (value_expr_p *li
*** 1512,1545 ****
  static void
  add_dependence (temp_expr_table_p tab, int version, tree var)
  {
!   int i, x;
!   value_expr_p info;
  
    i = SSA_NAME_VERSION (var);
    if (bitmap_bit_p (tab->replaceable, i))
      {
        /* This variable is being substituted, so use whatever dependences
           were queued up when we marked this as replaceable earlier.  */
!       while ((info = tab->pending_dependence))
          {
! 	  tab->pending_dependence = info->next;
! 	  /* Get the partition this variable was dependent on. Reuse this
! 	     object to represent the current  expression instead.  */
! 	  x = info->value;
! 	  info->value = version;
! 	  add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
!           add_value_to_list (tab, 
! 			     (value_expr_p *)&(tab->version_info[version]), x);
! 	  bitmap_set_bit (tab->partition_in_use, x);
  	}
      }
    else
      {
        i = var_to_partition (tab->map, var);
        gcc_assert (i != NO_PARTITION);
!       add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
!       add_value_to_list (tab, 
! 			 (value_expr_p *)&(tab->version_info[version]), i);
        bitmap_set_bit (tab->partition_in_use, i);
      }
  }
--- 1425,1459 ----
  static void
  add_dependence (temp_expr_table_p tab, int version, tree var)
  {
!   int i;
!   bitmap_iterator bi;
!   unsigned x;
  
    i = SSA_NAME_VERSION (var);
    if (bitmap_bit_p (tab->replaceable, i))
      {
        /* This variable is being substituted, so use whatever dependences
           were queued up when we marked this as replaceable earlier.  */
!       EXECUTE_IF_SET_IN_BITMAP (tab->pending_dependence, 0, x, bi)
          {
! 	  /* Version is now dependant on each pending dep partition.  */
! 	  add_value_to_partition_list (tab, x, version);
  	}
+       /* Rather than set version and inuse lists bit by bit, simply OR in
+          the pending_dependence bits.  */
+       if (!tab->version_info[version])
+         tab->version_info[version] = BITMAP_ALLOC (NULL);
+       bitmap_ior_into (tab->version_info[version], tab->pending_dependence);
+       bitmap_ior_into (tab->partition_in_use, tab->pending_dependence);
+ 
+       bitmap_clear (tab->pending_dependence);
      }
    else
      {
        i = var_to_partition (tab->map, var);
        gcc_assert (i != NO_PARTITION);
!       add_value_to_partition_list (tab, i, version);
!       add_value_to_version_list (tab, version, i);
        bitmap_set_bit (tab->partition_in_use, i);
      }
  }
*************** check_replaceable (temp_expr_table_p tab
*** 1595,1601 ****
    FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
      {
        add_dependence (tab, version, var);
- 
        use_vars = tab->expr_vars[SSA_NAME_VERSION (var)];
        if (use_vars)
  	bitmap_ior_into (def_vars, use_vars);
--- 1509,1514 ----
*************** check_replaceable (temp_expr_table_p tab
*** 1605,1615 ****
    /* If there are VUSES, add a dependence on virtual defs.  */
    if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
      {
!       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]), 
! 			 VIRTUAL_PARTITION (tab));
!       add_value_to_list (tab, 
! 			 &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]), 
! 			 version);
        bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
      }
  
--- 1518,1525 ----
    /* If there are VUSES, add a dependence on virtual defs.  */
    if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
      {
!       add_value_to_version_list (tab, version, VIRTUAL_PARTITION (tab));
!       add_value_to_partition_list (tab, VIRTUAL_PARTITION (tab), version);
        bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
      }
  
*************** check_replaceable (temp_expr_table_p tab
*** 1624,1651 ****
  static void
  finish_expr (temp_expr_table_p tab, int version, bool replace)
  {
-   value_expr_p info, tmp;
    int partition;
  
    /* Remove this expression from its dependent lists.  The partition dependence
       list is retained and transfered later to whomever uses this version.  */
!   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
      {
!       partition = info->value;
        gcc_assert (tab->partition_dep_list[partition]);
!       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]), 
! 				    version);
!       gcc_assert (tmp);
!       free_value_expr (tab, tmp);
        /* Only clear the bit when the dependency list is emptied via 
           a replacement. Otherwise kill_expr will take care of it.  */
!       if (!(tab->partition_dep_list[partition]) && replace)
!         bitmap_clear_bit (tab->partition_in_use, partition);
!       tmp = info->next;
!       if (!replace)
!         free_value_expr (tab, info);
      }
- 
    if (replace)
      {
        tab->saw_replaceable = true;
--- 1534,1556 ----
  static void
  finish_expr (temp_expr_table_p tab, int version, bool replace)
  {
    int partition;
+   unsigned i;
+   bitmap_iterator bi;
  
+   gcc_assert (tab->version_info[version]);
    /* Remove this expression from its dependent lists.  The partition dependence
       list is retained and transfered later to whomever uses this version.  */
!   EXECUTE_IF_SET_IN_BITMAP (tab->version_info[version], 0, i, bi)
      {
!       partition = i;
        gcc_assert (tab->partition_dep_list[partition]);
!       remove_value_from_partition_list (tab, partition, version);
        /* Only clear the bit when the dependency list is emptied via 
           a replacement. Otherwise kill_expr will take care of it.  */
!       if (!tab->partition_dep_list[partition] && replace)
! 	bitmap_clear_bit (tab->partition_in_use, partition);
      }
    if (replace)
      {
        tab->saw_replaceable = true;
*************** finish_expr (temp_expr_table_p tab, int 
*** 1654,1660 ****
    else
      {
        gcc_assert (!bitmap_bit_p (tab->replaceable, version));
!       tab->version_info[version] = NULL;
      }
  }
  
--- 1559,1565 ----
    else
      {
        gcc_assert (!bitmap_bit_p (tab->replaceable, version));
!       BITMAP_FREE (tab->version_info[version]);
      }
  }
  
*************** finish_expr (temp_expr_table_p tab, int 
*** 1665,1684 ****
  static void
  mark_replaceable (temp_expr_table_p tab, tree var)
  {
-   value_expr_p info;
    int version = SSA_NAME_VERSION (var);
    finish_expr (tab, version, true);
  
    /* Move the dependence list to the pending list.  */
    if (tab->version_info[version])
      {
!       info = (value_expr_p) tab->version_info[version]; 
!       for ( ; info->next; info = info->next)
! 	continue;
!       info->next = tab->pending_dependence;
!       tab->pending_dependence = (value_expr_p)tab->version_info[version];
      }
! 
    tab->version_info[version] = SSA_NAME_DEF_STMT (var);
  }
  
--- 1570,1586 ----
  static void
  mark_replaceable (temp_expr_table_p tab, tree var)
  {
    int version = SSA_NAME_VERSION (var);
    finish_expr (tab, version, true);
  
    /* Move the dependence list to the pending list.  */
    if (tab->version_info[version])
      {
!       bitmap_ior_into (tab->pending_dependence, tab->version_info[version]);
!       BITMAP_FREE (tab->version_info[version]);
      }
!   
!   /* Set it to the replaceable expression.  */
    tab->version_info[version] = SSA_NAME_DEF_STMT (var);
  }
  
*************** mark_replaceable (temp_expr_table_p tab,
*** 1691,1701 ****
  static inline void
  kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
  {
!   value_expr_p ptr;
  
!   /* Mark every active expr dependent on this var as not replaceable.  */
!   while ((ptr = tab->partition_dep_list[partition]) != NULL)
!     finish_expr (tab, ptr->value, false);
  
    if (clear_bit)
      bitmap_clear_bit (tab->partition_in_use, partition);
--- 1593,1609 ----
  static inline void
  kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
  {
!   unsigned i;
  
!   /* Mark every active expr dependent on this var as not replaceable.  
!      finish_expr can modify the bitmap, so we can't execute over it.  */
!   while (tab->partition_dep_list[partition])
!     {
!       i = bitmap_first_set_bit (tab->partition_dep_list[partition]);
!       finish_expr (tab, i, false);
!     }
! 
!   gcc_assert (!tab->partition_dep_list[partition]);
  
    if (clear_bit)
      bitmap_clear_bit (tab->partition_in_use, partition);
*************** find_replaceable_in_bb (temp_expr_table_
*** 1723,1729 ****
    stmt_ann_t ann;
    int partition;
    var_map map = tab->map;
-   value_expr_p p;
    ssa_op_iter iter;
  
    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
--- 1631,1636 ----
*************** find_replaceable_in_bb (temp_expr_table_
*** 1776,1786 ****
  	check_replaceable (tab, stmt);
  
        /* Free any unused dependency lists.  */
!       while ((p = tab->pending_dependence))
! 	{
! 	  tab->pending_dependence = p->next;
! 	  free_value_expr (tab, p);
! 	}
  
        /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand.  */
        if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
--- 1683,1689 ----
  	check_replaceable (tab, stmt);
  
        /* Free any unused dependency lists.  */
!       bitmap_clear (tab->pending_dependence);
  
        /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand.  */
        if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
*************** find_replaceable_exprs (var_map map)
*** 1812,1820 ****
  
        find_replaceable_in_bb (table, bb);
        EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
!         {
! 	  kill_expr (table, i, false);
! 	}
      }
  
    ret = free_temp_expr_table (table);
--- 1715,1730 ----
  
        find_replaceable_in_bb (table, bb);
        EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
! 	kill_expr (table, i, false);
!       bitmap_clear (table->partition_in_use);
! 
! #ifdef ENABLE_CHECKING
!   for (i = 0; i < num_ssa_names + 1; i++)
!     if (bitmap_bit_p (table->replaceable, i))
!       gcc_assert (table->version_info[i] != NULL);
!     else
!       gcc_assert (table->version_info[i] == NULL);
! #endif
      }
  
    ret = free_temp_expr_table (table);

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