From caf29de78e1a609a86f4f883db628e97f51b96c8 Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Sat, 4 Sep 2004 10:42:06 +0200 Subject: [PATCH] tree.c (iterate_hash_expr): Optimize, avoid use of iterative_hash_object. * tree.c (iterate_hash_expr): Optimize, avoid use of iterative_hash_object. (mix): New macro copied from hashtab.c (iterative_hash_hashval_t, iterative_hash_pointer, iterative_hash_host_wide_int): New functions based on hashtab.c implementation. From-SVN: r87078 --- gcc/ChangeLog | 8 ++ gcc/tree.c | 221 ++++++++++++++++++++++++++++++++------------------ 2 files changed, 150 insertions(+), 79 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 1bb969c7fc9..93ed7fde8d7 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,11 @@ +2004-09-04 Jan Hubicka + + * tree.c (iterate_hash_expr): Optimize, avoid use of iterative_hash_object. + (mix): New macro copied from hashtab.c + (iterative_hash_hashval_t, iterative_hash_pointer, + iterative_hash_host_wide_int): New functions based on hashtab.c + implementation. + 2004-09-04 Richard Sandiford * config/mips/mips.md (mask): New mode attribute. diff --git a/gcc/tree.c b/gcc/tree.c index de6b8ec60f4..95f5ccbecb1 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -2766,6 +2766,74 @@ build_decl_attribute_variant (tree ddecl, tree attribute) return ddecl; } +/* Borrowed from hashtab.c iterative_hash implementation. */ +#define mix(a,b,c) \ +{ \ + a -= b; a -= c; a ^= (c>>13); \ + b -= c; b -= a; b ^= (a<< 8); \ + c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ + a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ + b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ + c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ + a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ + b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ + c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ +} + + +/* Produce good hash value combining VAL and VAL2. */ +static inline hashval_t +iterative_hash_hashval_t (hashval_t val, hashval_t val2) +{ + /* the golden ratio; an arbitrary value. */ + hashval_t a = 0x9e3779b9; + + mix (a, val, val2); + return val2; +} + +/* Produce good hash value combining PTR and VAL2. */ +static inline hashval_t +iterative_hash_pointer (void *ptr, hashval_t val2) +{ + if (sizeof (ptr) == sizeof (hashval_t)) + return iterative_hash_hashval_t ((size_t) ptr, val2); + else + { + hashval_t a = (hashval_t) (size_t) ptr; + /* Avoid warnings about shifting of more than the width of the type on + hosts that won't execute this path. */ + int zero = 0; + hashval_t b = (hashval_t) ((size_t) ptr >> (sizeof (hashval_t) * 8 + zero)); + mix (a, b, val2); + return val2; + } +} + +/* Produce good hash value combining VAL and VAL2. */ +static inline hashval_t +iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2) +{ + if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t)) + return iterative_hash_hashval_t (val, val2); + else + { + hashval_t a = (hashval_t) val; + /* Avoid warnings about shifting of more than the width of the type on + hosts that won't execute this path. */ + int zero = 0; + hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero)); + mix (a, b, val2); + if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t)) + { + hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero)); + hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero)); + mix (a, b, val2); + } + return val2; + } +} + /* Return a type like TTYPE except that its TYPE_ATTRIBUTE is ATTRIBUTE. @@ -3908,97 +3976,92 @@ iterative_hash_expr (tree t, hashval_t val) char class; if (t == NULL_TREE) - return iterative_hash_object (t, val); + return iterative_hash_pointer (t, val); code = TREE_CODE (t); - class = TREE_CODE_CLASS (code); - if (class == 'd' - || TREE_CODE (t) == VALUE_HANDLE) - { - /* Decls we can just compare by pointer. */ - val = iterative_hash_object (t, val); - } - else if (class == 'c') + switch (code) { - /* Alas, constants aren't shared, so we can't rely on pointer - identity. */ - if (code == INTEGER_CST) - { - val = iterative_hash_object (TREE_INT_CST_LOW (t), val); - val = iterative_hash_object (TREE_INT_CST_HIGH (t), val); - } - else if (code == REAL_CST) - { - unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t)); + /* Alas, constants aren't shared, so we can't rely on pointer + identity. */ + case INTEGER_CST: + val = iterative_hash_host_wide_int (TREE_INT_CST_LOW (t), val); + return iterative_hash_host_wide_int (TREE_INT_CST_HIGH (t), val); + case REAL_CST: + { + unsigned int val2 = real_hash (TREE_REAL_CST_PTR (t)); - val = iterative_hash (&val2, sizeof (unsigned int), val); - } - else if (code == STRING_CST) - val = iterative_hash (TREE_STRING_POINTER (t), - TREE_STRING_LENGTH (t), val); - else if (code == COMPLEX_CST) + return iterative_hash_hashval_t (val2, val); + } + case STRING_CST: + return iterative_hash (TREE_STRING_POINTER (t), + TREE_STRING_LENGTH (t), val); + case COMPLEX_CST: + val = iterative_hash_expr (TREE_REALPART (t), val); + return iterative_hash_expr (TREE_IMAGPART (t), val); + case VECTOR_CST: + return iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val); + + case SSA_NAME: + case VALUE_HANDLE: + /* we can just compare by pointer. */ + return iterative_hash_pointer (t, val); + + case TREE_LIST: + /* A list of expressions, for a CALL_EXPR or as the elements of a + VECTOR_CST. */ + for (; t; t = TREE_CHAIN (t)) + val = iterative_hash_expr (TREE_VALUE (t), val); + return val; + default: + class = TREE_CODE_CLASS (code); + + if (class == 'd') { - val = iterative_hash_expr (TREE_REALPART (t), val); - val = iterative_hash_expr (TREE_IMAGPART (t), val); + /* Decls we can just compare by pointer. */ + val = iterative_hash_pointer (t, val); } - else if (code == VECTOR_CST) - val = iterative_hash_expr (TREE_VECTOR_CST_ELTS (t), val); - else - abort (); - } - else if (IS_EXPR_CODE_CLASS (class)) - { - val = iterative_hash_object (code, val); - - /* Don't hash the type, that can lead to having nodes which - compare equal according to operand_equal_p, but which - have different hash codes. */ - if (code == NOP_EXPR - || code == CONVERT_EXPR - || code == NON_LVALUE_EXPR) + else if (IS_EXPR_CODE_CLASS (class)) { - /* Make sure to include signness in the hash computation. */ - val += TYPE_UNSIGNED (TREE_TYPE (t)); - val = iterative_hash_expr (TREE_OPERAND (t, 0), val); - } + val = iterative_hash_object (code, val); + + /* Don't hash the type, that can lead to having nodes which + compare equal according to operand_equal_p, but which + have different hash codes. */ + if (code == NOP_EXPR + || code == CONVERT_EXPR + || code == NON_LVALUE_EXPR) + { + /* Make sure to include signness in the hash computation. */ + val += TYPE_UNSIGNED (TREE_TYPE (t)); + val = iterative_hash_expr (TREE_OPERAND (t, 0), val); + } - if (commutative_tree_code (code)) - { - /* It's a commutative expression. We want to hash it the same - however it appears. We do this by first hashing both operands - and then rehashing based on the order of their independent - hashes. */ - hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0); - hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0); - hashval_t t; - - if (one > two) - t = one, one = two, two = t; - - val = iterative_hash_object (one, val); - val = iterative_hash_object (two, val); + else if (commutative_tree_code (code)) + { + /* It's a commutative expression. We want to hash it the same + however it appears. We do this by first hashing both operands + and then rehashing based on the order of their independent + hashes. */ + hashval_t one = iterative_hash_expr (TREE_OPERAND (t, 0), 0); + hashval_t two = iterative_hash_expr (TREE_OPERAND (t, 1), 0); + hashval_t t; + + if (one > two) + t = one, one = two, two = t; + + val = iterative_hash_hashval_t (one, val); + val = iterative_hash_hashval_t (two, val); + } + else + for (i = first_rtl_op (code) - 1; i >= 0; --i) + val = iterative_hash_expr (TREE_OPERAND (t, i), val); } else - for (i = first_rtl_op (code) - 1; i >= 0; --i) - val = iterative_hash_expr (TREE_OPERAND (t, i), val); - } - else if (code == TREE_LIST) - { - /* A list of expressions, for a CALL_EXPR or as the elements of a - VECTOR_CST. */ - for (; t; t = TREE_CHAIN (t)) - val = iterative_hash_expr (TREE_VALUE (t), val); - } - else if (code == SSA_NAME) - { - val = iterative_hash_object (SSA_NAME_VERSION (t), val); - val = iterative_hash_expr (SSA_NAME_VAR (t), val); + abort (); + return val; + break; } - else - abort (); - - return val; } /* Constructors for pointer, array and function types. -- 2.30.2