diff options
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/ChangeLog | 18 | ||||
| -rw-r--r-- | gcc/Makefile.in | 3 | ||||
| -rw-r--r-- | gcc/asan.c | 1 | ||||
| -rw-r--r-- | gcc/inchash.c | 75 | ||||
| -rw-r--r-- | gcc/inchash.h | 129 | ||||
| -rw-r--r-- | gcc/ipa-devirt.c | 1 | ||||
| -rw-r--r-- | gcc/lto-streamer-out.c | 1 | ||||
| -rw-r--r-- | gcc/lto/ChangeLog | 4 | ||||
| -rw-r--r-- | gcc/lto/lto.c | 1 | ||||
| -rw-r--r-- | gcc/tree-ssa-dom.c | 1 | ||||
| -rw-r--r-- | gcc/tree-ssa-pre.c | 1 | ||||
| -rw-r--r-- | gcc/tree-ssa-sccvn.c | 1 | ||||
| -rw-r--r-- | gcc/tree-ssa-tail-merge.c | 1 | ||||
| -rw-r--r-- | gcc/tree.c | 51 | ||||
| -rw-r--r-- | gcc/tree.h | 3 |
15 files changed, 237 insertions, 54 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 268c40a6a5e..9f42d856d6e 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,21 @@ +2014-07-25 Andi Kleen <ak@linux.intel.com> + + * Makefile.in (OBJS): Add inchash.o. + (PLUGIN_HEADERS): Add inchash.h. + * ipa-devirt.c: Include inchash.h. + * lto-streamer-out.c: Dito. + * tree-ssa-dom.c: Dito. + * tree-ssa-pre.c: Dito. + * tree-ssa-sccvn.c: Dito. + * tree-ssa-tail-merge.c: Dito. + * asan.c: Dito. + * tree.c (iterative_hash_hashval_t): Move to ... + (iterative_hash_host_wide_int): Move to ... + * inchash.c: Here. New file. + * tree.h (iterative_hash_hashval_t): Move to ... + (iterative_hash_host_wide_int): Move to ... + * inchash.h: Here. New file. + 2014-07-25 Richard Biener <rguenther@suse.de> PR middle-end/61762 diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 187e6b66202..4c578b37981 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1268,6 +1268,7 @@ OBJS = \ hwint.o \ ifcvt.o \ ree.o \ + inchash.o \ incpath.o \ init-regs.o \ internal-fn.o \ @@ -3162,7 +3163,7 @@ PLUGIN_HEADERS = $(TREE_H) $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ tree-parloops.h tree-ssa-address.h tree-ssa-coalesce.h tree-ssa-dom.h \ tree-ssa-loop.h tree-ssa-loop-ivopts.h tree-ssa-loop-manip.h \ tree-ssa-loop-niter.h tree-ssa-ter.h tree-ssa-threadedge.h \ - tree-ssa-threadupdate.h + tree-ssa-threadupdate.h inchash.h # generate the 'build fragment' b-header-vars s-header-vars: Makefile diff --git a/gcc/asan.c b/gcc/asan.c index 59ec904ccc3..475dd824fa3 100644 --- a/gcc/asan.c +++ b/gcc/asan.c @@ -29,6 +29,7 @@ along with GCC; see the file COPYING3. If not see #include "internal-fn.h" #include "gimple-expr.h" #include "is-a.h" +#include "inchash.h" #include "gimple.h" #include "gimplify.h" #include "gimple-iterator.h" diff --git a/gcc/inchash.c b/gcc/inchash.c new file mode 100644 index 00000000000..0f8583eab5f --- /dev/null +++ b/gcc/inchash.c @@ -0,0 +1,75 @@ +/* Incremential hashing for jhash. + Copyright (C) 2014 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "hashtab.h" +#include "inchash.h" + +/* 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. */ +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 VAL and VAL2. */ + +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; + } +} diff --git a/gcc/inchash.h b/gcc/inchash.h new file mode 100644 index 00000000000..7af0baaddbd --- /dev/null +++ b/gcc/inchash.h @@ -0,0 +1,129 @@ +/* An incremental hash abstract data type. + Copyright (C) 2014 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef INCHASH_H +#define INCHASH_H 1 + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "hashtab.h" + +/* This file implements an incremential hash function ADT, to be used + by code that incrementially hashes a lot of unrelated data + (not in a single memory block) into a single value. The goal + is to make it easy to plug in efficient hash algorithms. + Currently it just implements the plain old jhash based + incremental hash from gcc's tree.c. */ + +extern hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t); +extern hashval_t iterative_hash_hashval_t (hashval_t, hashval_t); + +class inchash +{ + public: + + /* Start incremential hashing, optionally with SEED. */ + inchash (hashval_t seed = 0) + { + val = seed; + bits = 0; + } + + /* End incremential hashing and provide the final value. */ + hashval_t end () + { + return val; + } + + /* Add unsigned value V. */ + void add_int (unsigned v) + { + val = iterative_hash_hashval_t (v, val); + } + + /* Add HOST_WIDE_INT value V. */ + void add_wide_int (HOST_WIDE_INT v) + { + val = iterative_hash_host_wide_int (v, val); + } + + /* Hash in pointer PTR. */ + void add_ptr (void *ptr) + { + add (&ptr, sizeof (ptr)); + } + + /* Add a memory block DATA with size LEN. */ + void add (const void *data, size_t len) + { + val = iterative_hash (data, len, val); + } + + /* Merge hash value OTHER. */ + void merge_hash (hashval_t other) + { + val = iterative_hash_hashval_t (other, val); + } + + /* Hash in state from other inchash OTHER. */ + void merge (inchash &other) + { + merge_hash (other.val); + } + + /* Support for accumulating boolean flags */ + + void add_flag (bool flag) + { + bits = (bits << 1) | flag; + } + + void commit_flag () + { + add_int (bits); + bits = 0; + } + + /* Support for commutative hashing. Add A and B in a defined order + based on their value. This is useful for hashing commutative + expressions, so that A+B and B+A get the same hash. */ + + void add_commutative (inchash &a, inchash &b) + { + if (a.end() > b.end()) + { + merge (b); + merge (a); + } + else + { + merge (a); + merge (b); + } + } + + private: + hashval_t val; + unsigned bits; +}; + +#define add_object(o) add (&(o), sizeof (o)) + +#endif diff --git a/gcc/ipa-devirt.c b/gcc/ipa-devirt.c index 7c4151a1857..127d58d775d 100644 --- a/gcc/ipa-devirt.c +++ b/gcc/ipa-devirt.c @@ -118,6 +118,7 @@ along with GCC; see the file COPYING3. If not see #include "pointer-set.h" #include "target.h" #include "hash-table.h" +#include "inchash.h" #include "tree-pretty-print.h" #include "ipa-utils.h" #include "tree-ssa-alias.h" diff --git a/gcc/lto-streamer-out.c b/gcc/lto-streamer-out.c index 355ceeaaf08..9f9a0138bbc 100644 --- a/gcc/lto-streamer-out.c +++ b/gcc/lto-streamer-out.c @@ -44,6 +44,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-pass.h" #include "function.h" #include "diagnostic-core.h" +#include "inchash.h" #include "except.h" #include "lto-symtab.h" #include "lto-streamer.h" diff --git a/gcc/lto/ChangeLog b/gcc/lto/ChangeLog index 8fd21ea828f..0510a12b0ea 100644 --- a/gcc/lto/ChangeLog +++ b/gcc/lto/ChangeLog @@ -1,3 +1,7 @@ +2014-07-25 Andi Kleen <ak@linux.intel.com> + + * lto.c: Include inchash.h + 2014-07-14 Jan Hubicka <hubicka@ucw.cz> * lto.c (mentions_vars_p_decl_non_common): Skip diff --git a/gcc/lto/lto.c b/gcc/lto/lto.c index 683120c0081..7fcea913135 100644 --- a/gcc/lto/lto.c +++ b/gcc/lto/lto.c @@ -33,6 +33,7 @@ along with GCC; see the file COPYING3. If not see #include "langhooks.h" #include "bitmap.h" #include "hash-map.h" +#include "inchash.h" #include "ipa-prop.h" #include "common.h" #include "debug.h" diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index c4ec4e5415c..08fd2faf452 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -29,6 +29,7 @@ along with GCC; see the file COPYING3. If not see #include "tm_p.h" #include "basic-block.h" #include "cfgloop.h" +#include "inchash.h" #include "function.h" #include "gimple-pretty-print.h" #include "tree-ssa-alias.h" diff --git a/gcc/tree-ssa-pre.c b/gcc/tree-ssa-pre.c index 128c215954c..8b4d2badb6f 100644 --- a/gcc/tree-ssa-pre.c +++ b/gcc/tree-ssa-pre.c @@ -27,6 +27,7 @@ along with GCC; see the file COPYING3. If not see #include "basic-block.h" #include "gimple-pretty-print.h" #include "tree-inline.h" +#include "inchash.h" #include "hash-table.h" #include "tree-ssa-alias.h" #include "internal-fn.h" diff --git a/gcc/tree-ssa-sccvn.c b/gcc/tree-ssa-sccvn.c index 139ac3bbc72..93314fc70e8 100644 --- a/gcc/tree-ssa-sccvn.c +++ b/gcc/tree-ssa-sccvn.c @@ -30,6 +30,7 @@ along with GCC; see the file COPYING3. If not see #include "hash-table.h" #include "tree-ssa-alias.h" #include "internal-fn.h" +#include "inchash.h" #include "gimple-fold.h" #include "tree-eh.h" #include "gimple-expr.h" diff --git a/gcc/tree-ssa-tail-merge.c b/gcc/tree-ssa-tail-merge.c index 7245223ae8c..9600e283cac 100644 --- a/gcc/tree-ssa-tail-merge.c +++ b/gcc/tree-ssa-tail-merge.c @@ -192,6 +192,7 @@ along with GCC; see the file COPYING3. If not see #include "tree.h" #include "stor-layout.h" #include "trans-mem.h" +#include "inchash.h" #include "tm_p.h" #include "basic-block.h" #include "flags.h" diff --git a/gcc/tree.c b/gcc/tree.c index 51ef63b6bb2..3625bf5a0ce 100644 --- a/gcc/tree.c +++ b/gcc/tree.c @@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see #include "obstack.h" #include "toplev.h" /* get_random_seed */ #include "hashtab.h" +#include "inchash.h" #include "filenames.h" #include "output.h" #include "target.h" @@ -4582,56 +4583,6 @@ 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. */ -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 VAL and VAL2. */ -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 and its qualifiers are QUALS. diff --git a/gcc/tree.h b/gcc/tree.h index 0b98de8b1e0..190428ab885 100644 --- a/gcc/tree.h +++ b/gcc/tree.h @@ -4284,9 +4284,6 @@ extern int tree_floor_log2 (const_tree); extern unsigned int tree_ctz (const_tree); extern int simple_cst_equal (const_tree, const_tree); extern hashval_t iterative_hash_expr (const_tree, hashval_t); -extern hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t); -extern hashval_t iterative_hash_hashval_t (hashval_t, hashval_t); -extern hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t); extern int compare_tree_int (const_tree, unsigned HOST_WIDE_INT); extern int type_list_equal (const_tree, const_tree); extern int chain_member (const_tree, const_tree); |