[PATCH] Speed up FRE (~10% on PR34683)

[Daniel Berlin]

On Jan 7, 2008 12:05 PM, Richard Guenther <rguenther@suse.de> wrote:
>
> This speeds up compile of PR34683 (-O -fstrict-aliasing
> -fno-tree-loop-optimize) by ~10% by avoiding to sort already
> sorted VUSEs -- which requires changing sort order from SSA_NAME versions
> to DECL_UIDs, the same as the operand scanner uses.  The patch
> cuts the number of qsorts of a vector of 256 elements by an order
> of magnitude.
>
> Danny, was there a particular reason for the sort order of VOPs in
> tree-vn?

To compare the vops arrays in linear time.

If you only sort by DECL_UID, now two lists of vops, like

SMT.3_4
SMT.3_7

SMT.3_7
SMT.3_4

won't be sorted right anymore, no?


If so you may see a speed up from doing what you are doing simply
because we incorrectly claim two arrays are not equal when they are.


> Bootstrapped and tested on x86_64-unknown-linux-gnu, I am going to
> apply this later (I messed up the vuses_to_vec change with the
> last commit, so that is necessary anyway).
>
> Thanks,
> Richard.
>
> 2008-01-07  Richard Guenther  <rguenther@suse.de>
>
>         PR tree-optimization/34683
>         * tree-ssa-operands.c (operand_build_cmp): Export.
>         * tree-ssa-operands.h (operand_build_cmp): Declare.
>         * tree-vn.c (vuses_compare): Remove.
>         (sort_vuses): Use operand_build_cmp.
>         (sort_vuses_heap): Likewise.
>         * tree-ssa-sccvn.c (vuses_to_vec): Use VEC_reserve, not VEC_alloc
>         to re-use old VEC if available.  Do not sort already sorted VUSEs.
>         (vdefs_to_vec): Do not sort already sorted VDEFs.
>
> Index: tree-ssa-operands.c
> ===================================================================
> *** tree-ssa-operands.c (revision 131374)
> --- tree-ssa-operands.c (working copy)
> *************** get_name_decl (const_tree t)
> *** 210,216 ****
>
>   /* Comparison function for qsort used in operand_build_sort_virtual.  */
>
> ! static int
>   operand_build_cmp (const void *p, const void *q)
>   {
>     const_tree const e1 = *((const_tree const *)p);
> --- 210,216 ----
>
>   /* Comparison function for qsort used in operand_build_sort_virtual.  */
>
> ! int
>   operand_build_cmp (const void *p, const void *q)
>   {
>     const_tree const e1 = *((const_tree const *)p);
> Index: tree-ssa-operands.h
> ===================================================================
> *** tree-ssa-operands.h (revision 131374)
> --- tree-ssa-operands.h (working copy)
> *************** extern void free_stmt_operands (tree);
> *** 210,215 ****
> --- 210,216 ----
>   extern bool verify_imm_links (FILE *f, tree var);
>
>   extern void copy_virtual_operands (tree, tree);
> + extern int operand_build_cmp (const void *, const void *);
>   extern void create_ssa_artificial_load_stmt (tree, tree, bool);
>
>   extern void dump_immediate_uses (FILE *file);
> Index: tree-vn.c
> ===================================================================
> *** tree-vn.c   (revision 131374)
> --- tree-vn.c   (working copy)
> *************** set_value_handle (tree e, tree v)
> *** 107,125 ****
>       gcc_assert (is_gimple_min_invariant (e));
>   }
>
> - /* A comparison function for use in qsort to compare vuses.  Simply
> -    subtracts version numbers.  */
> -
> - static int
> - vuses_compare (const void *pa, const void *pb)
> - {
> -   const tree vusea = *((const tree *)pa);
> -   const tree vuseb = *((const tree *)pb);
> -   int sn = SSA_NAME_VERSION (vusea) - SSA_NAME_VERSION (vuseb);
> -
> -   return sn;
> - }
> -
>   /* Print out the "Created value <x> for <Y>" statement to the
>      dump_file.
>      This is factored because both versions of lookup use it, and it
> --- 107,112 ----
> *************** sort_vuses (VEC (tree,gc) *vuses)
> *** 161,167 ****
>       qsort (VEC_address (tree, vuses),
>            VEC_length (tree, vuses),
>            sizeof (tree),
> !          vuses_compare);
>   }
>
>   /* Sort the VUSE array so that we can do equality comparisons
> --- 148,154 ----
>       qsort (VEC_address (tree, vuses),
>            VEC_length (tree, vuses),
>            sizeof (tree),
> !          operand_build_cmp);
>   }
>
>   /* Sort the VUSE array so that we can do equality comparisons
> *************** sort_vuses_heap (VEC (tree,heap) *vuses)
> *** 174,180 ****
>       qsort (VEC_address (tree, vuses),
>            VEC_length (tree, vuses),
>            sizeof (tree),
> !          vuses_compare);
>   }
>   /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
>      EXPR to the value set for value VAL.  */
> --- 161,167 ----
>       qsort (VEC_address (tree, vuses),
>            VEC_length (tree, vuses),
>            sizeof (tree),
> !          operand_build_cmp);
>   }
>   /* Insert EXPR into VALUE_TABLE with value VAL, and add expression
>      EXPR to the value set for value VAL.  */
> Index: tree-ssa-sccvn.c
> ===================================================================
> *** tree-ssa-sccvn.c    (revision 131375)
> --- tree-ssa-sccvn.c    (working copy)
> *************** vuses_to_vec (tree stmt, VEC (tree, gc)
> *** 389,401 ****
>     if (!stmt)
>       return;
>
> !   *result = VEC_alloc (tree, gc, num_ssa_operands (stmt, SSA_OP_VIRTUAL_USES));
>
>     FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
>       VEC_quick_push (tree, *result, vuse);
> -
> -   if (VEC_length (tree, *result) > 1)
> -     sort_vuses (*result);
>   }
>
>
> --- 389,399 ----
>     if (!stmt)
>       return;
>
> !   VEC_reserve_exact (tree, gc, *result,
> !                    num_ssa_operands (stmt, SSA_OP_VIRTUAL_USES));
>
>     FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, iter, SSA_OP_VIRTUAL_USES)
>       VEC_quick_push (tree, *result, vuse);
>   }
>
>
> *************** vdefs_to_vec (tree stmt, VEC (tree, gc)
> *** 427,435 ****
>
>     FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, iter, SSA_OP_VIRTUAL_DEFS)
>       VEC_quick_push (tree, *result, vdef);
> -
> -   if (VEC_length (tree, *result) > 1)
> -     sort_vuses (*result);
>   }
>
>   /* Copy the names of vdef results in STMT into a vector, and return
> --- 425,430 ----
>