From 3d2d7de7064f0629b185af2a221b499b108d4f7a Mon Sep 17 00:00:00 2001
From: bonzini <bonzini@138bc75d-0d04-0410-961f-82ee72b054a4>
Date: Fri, 6 Feb 2009 07:33:05 +0000
Subject: 2009-02-06 Paolo Bonzini <bonzini@gnu.org>
PR tree-optimization/35659
* tree-ssa-sccvn.c (vn_constant_eq, vn_reference_eq, vn_nary_op_eq
vn_phi_eq): Shortcut if hashcode does not match.
(vn_reference_op_compute_hash): Do not call iterative_hash_expr for
NULL operands.
* tree-ssa-pre.c (pre_expr_hash): Look at hashcode if available,
and avoid iterative_hash_expr.
(FOR_EACH_VALUE_ID_IN_SET): New.
(value_id_compare): Remove.
(sorted_array_from_bitmap_set): Use FOR_EACH_VALUE_ID_IN_SET to
sort expressions by value id.
git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@143980 138bc75d-0d04-0410-961f-82ee72b054a4
---
gcc/ChangeLog | 14 ++++++++++++++
gcc/tree-ssa-pre.c | 48 ++++++++++++++++++++++++++----------------------
gcc/tree-ssa-sccvn.c | 23 ++++++++++++++++++++---
3 files changed, 60 insertions(+), 25 deletions(-)
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index f0822dc4e07..8a7a3187c4f 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2009-02-06 Paolo Bonzini <bonzini@gnu.org>
+
+ PR tree-optimization/35659
+ * tree-ssa-sccvn.c (vn_constant_eq, vn_reference_eq, vn_nary_op_eq
+ vn_phi_eq): Shortcut if hashcode does not match.
+ (vn_reference_op_compute_hash): Do not call iterative_hash_expr for
+ NULL operands.
+ * tree-ssa-pre.c (pre_expr_hash): Look at hashcode if available,
+ and avoid iterative_hash_expr.
+ (FOR_EACH_VALUE_ID_IN_SET): New.
+ (value_id_compare): Remove.
+ (sorted_array_from_bitmap_set): Use FOR_EACH_VALUE_ID_IN_SET to
+ sort expressions by value id.
+
2009-02-05 Kaz Kojima <kkojima@gcc.gnu.org>
PR target/38991
diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c
index a3f91f07d58..32c557cc0fb 100644
--- a/gcc/tree-ssa-pre.c
+++ b/gcc/tree-ssa-pre.c
@@ -216,11 +216,11 @@ pre_expr_hash (const void *p1)
case CONSTANT:
return vn_hash_constant_with_type (PRE_EXPR_CONSTANT (e));
case NAME:
- return iterative_hash_expr (PRE_EXPR_NAME (e), 0);
+ return iterative_hash_hashval_t (SSA_NAME_VERSION (PRE_EXPR_NAME (e)), 0);
case NARY:
- return vn_nary_op_compute_hash (PRE_EXPR_NARY (e));
+ return PRE_EXPR_NARY (e)->hashcode;
case REFERENCE:
- return vn_reference_compute_hash (PRE_EXPR_REFERENCE (e));
+ return PRE_EXPR_REFERENCE (e)->hashcode;
default:
abort ();
}
@@ -337,6 +337,9 @@ typedef struct bitmap_set
#define FOR_EACH_EXPR_ID_IN_SET(set, id, bi) \
EXECUTE_IF_SET_IN_BITMAP((set)->expressions, 0, (id), (bi))
+#define FOR_EACH_VALUE_ID_IN_SET(set, id, bi) \
+ EXECUTE_IF_SET_IN_BITMAP((set)->values, 0, (id), (bi))
+
/* Mapping from value id to expressions with that value_id. */
DEF_VEC_P (bitmap_set_t);
DEF_VEC_ALLOC_P (bitmap_set_t, heap);
@@ -672,33 +675,34 @@ bitmap_set_free (bitmap_set_t set)
}
-/* A comparison function for use in qsort to top sort a bitmap set. Simply
- subtracts value ids, since they are created with leaves before
- their parent users (IE topological order). */
-
-static int
-value_id_compare (const void *pa, const void *pb)
-{
- const unsigned int vha = get_expr_value_id (*((const pre_expr *)pa));
- const unsigned int vhb = get_expr_value_id (*((const pre_expr *)pb));
-
- return vha - vhb;
-}
-
/* Generate an topological-ordered array of bitmap set SET. */
static VEC(pre_expr, heap) *
sorted_array_from_bitmap_set (bitmap_set_t set)
{
- unsigned int i;
- bitmap_iterator bi;
+ unsigned int i, j;
+ bitmap_iterator bi, bj;
VEC(pre_expr, heap) *result = NULL;
- FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
- VEC_safe_push (pre_expr, heap, result, expression_for_id (i));
+ FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
+ {
+ /* The number of expressions having a given value is usually
+ relatively small. Thus, rather than making a vector of all
+ the expressions and sorting it by value-id, we walk the values
+ and check in the reverse mapping that tells us what expressions
+ have a given value, to filter those in our set. As a result,
+ the expressions are inserted in value-id order, which means
+ topological order.
- qsort (VEC_address (pre_expr, result), VEC_length (pre_expr, result),
- sizeof (pre_expr), value_id_compare);
+ If this is somehow a significant lose for some cases, we can
+ choose which set to walk based on the set size. */
+ bitmap_set_t exprset = VEC_index (bitmap_set_t, value_expressions, i);
+ FOR_EACH_EXPR_ID_IN_SET (exprset, j, bj)
+ {
+ if (bitmap_bit_p (set->expressions, j))
+ VEC_safe_push (pre_expr, heap, result, expression_for_id (j));
+ }
+ }
return result;
}
diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c
index 87ddcb6872c..5f4d1c599d1 100644
--- a/gcc/tree-ssa-sccvn.c
+++ b/gcc/tree-ssa-sccvn.c
@@ -316,6 +316,9 @@ vn_constant_eq (const void *p1, const void *p2)
const struct vn_constant_s *vc1 = (const struct vn_constant_s *) p1;
const struct vn_constant_s *vc2 = (const struct vn_constant_s *) p2;
+ if (vc1->hashcode != vc2->hashcode)
+ return false;
+
return vn_constant_eq_with_type (vc1->constant, vc2->constant);
}
@@ -386,6 +389,7 @@ vn_reference_op_eq (const void *p1, const void *p2)
{
const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1;
const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2;
+
return vro1->opcode == vro2->opcode
&& types_compatible_p (vro1->type, vro2->type)
&& expressions_equal_p (vro1->op0, vro2->op0)
@@ -398,9 +402,14 @@ vn_reference_op_eq (const void *p1, const void *p2)
static hashval_t
vn_reference_op_compute_hash (const vn_reference_op_t vro1)
{
- return iterative_hash_expr (vro1->op0, vro1->opcode)
- + iterative_hash_expr (vro1->op1, vro1->opcode)
- + iterative_hash_expr (vro1->op2, vro1->opcode);
+ hashval_t result = 0;
+ if (vro1->op0)
+ result += iterative_hash_expr (vro1->op0, vro1->opcode);
+ if (vro1->op1)
+ result += iterative_hash_expr (vro1->op1, vro1->opcode);
+ if (vro1->op2)
+ result += iterative_hash_expr (vro1->op2, vro1->opcode);
+ return result;
}
/* Return the hashcode for a given reference operation P1. */
@@ -442,6 +451,8 @@ vn_reference_eq (const void *p1, const void *p2)
const_vn_reference_t const vr1 = (const_vn_reference_t) p1;
const_vn_reference_t const vr2 = (const_vn_reference_t) p2;
+ if (vr1->hashcode != vr2->hashcode)
+ return false;
if (vr1->vuses == vr2->vuses
&& vr1->operands == vr2->operands)
@@ -1183,6 +1194,9 @@ vn_nary_op_eq (const void *p1, const void *p2)
const_vn_nary_op_t const vno2 = (const_vn_nary_op_t) p2;
unsigned i;
+ if (vno1->hashcode != vno2->hashcode)
+ return false;
+
if (vno1->opcode != vno2->opcode
|| !types_compatible_p (vno1->type, vno2->type))
return false;
@@ -1449,6 +1463,9 @@ vn_phi_eq (const void *p1, const void *p2)
const_vn_phi_t const vp1 = (const_vn_phi_t) p1;
const_vn_phi_t const vp2 = (const_vn_phi_t) p2;
+ if (vp1->hashcode != vp2->hashcode)
+ return false;
+
if (vp1->block == vp2->block)
{
int i;
--
cgit v1.2.1