gcc/ChangeLog: 2014-11-13 Martin Liska <mli...@suse.cz>
* bb-reorder.c (find_traces_1_round): Old fibheap_t type removed. * bt-load.c: Include of fibheap.h is removed. * cgraphunit.c: Likewise. * config/i386/i386.c: Likewise. * ipa-inline.c: Likewise. * var-tracking.c: Likewise. include/ChangeLog: 2014-11-13 Martin Liska <mli...@suse.cz> * fibheap.h: Remove. libiberty/ChangeLog: 2014-11-13 Martin Liska <mli...@suse.cz> * Makefile.in: Remove. * fibheap.c: Remove. --- gcc/bb-reorder.c | 7 +- gcc/bt-load.c | 1 - gcc/cgraphunit.c | 1 - gcc/config/i386/i386.c | 1 - gcc/ipa-inline.c | 1 - gcc/var-tracking.c | 1 - include/fibheap.h | 95 ---------- libiberty/Makefile.in | 15 +- libiberty/fibheap.c | 486 ------------------------------------------------- 9 files changed, 5 insertions(+), 603 deletions(-) delete mode 100644 include/fibheap.h delete mode 100644 libiberty/fibheap.c diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c index b1223a7..a1f352cc 100644 --- a/gcc/bb-reorder.c +++ b/gcc/bb-reorder.c @@ -87,7 +87,6 @@ #include "regs.h" #include "flags.h" #include "output.h" -#include "fibheap.h" #include "target.h" #include "hashtab.h" #include "hash-set.h" @@ -216,7 +215,7 @@ static void mark_bb_visited (basic_block, int); static void find_traces_1_round (int, int, gcov_type, struct trace *, int *, int, bb_heap_t **, int); static basic_block copy_bb (basic_block, edge, basic_block, int); -static fibheapkey_t bb_to_key (basic_block); +static long bb_to_key (basic_block); static bool better_edge_p (const_basic_block, const_edge, int, int, int, int, const_edge); static bool connect_better_edge_p (const_edge, bool, int, const_edge, @@ -484,7 +483,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th, basic_block bb; struct trace *trace; edge best_edge, e; - fibheapkey_t key; + long key; edge_iterator ei; bb = (*heap)->extract_min (); @@ -885,7 +884,7 @@ copy_bb (basic_block old_bb, edge e, basic_block bb, int trace) /* Compute and return the key (for the heap) of the basic block BB. */ -static fibheapkey_t +static long bb_to_key (basic_block bb) { edge e; diff --git a/gcc/bt-load.c b/gcc/bt-load.c index a9064bd..3002b62 100644 --- a/gcc/bt-load.c +++ b/gcc/bt-load.c @@ -25,7 +25,6 @@ along with GCC; see the file COPYING3. If not see #include "rtl.h" #include "hard-reg-set.h" #include "regs.h" -#include "fibheap.h" #include "target.h" #include "expr.h" #include "flags.h" diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c index 25af234..87f0900 100644 --- a/gcc/cgraphunit.c +++ b/gcc/cgraphunit.c @@ -197,7 +197,6 @@ along with GCC; see the file COPYING3. If not see #include "target.h" #include "diagnostic.h" #include "params.h" -#include "fibheap.h" #include "intl.h" #include "hash-map.h" #include "plugin-api.h" diff --git a/gcc/config/i386/i386.c b/gcc/config/i386/i386.c index b70c56c..bac58b6 100644 --- a/gcc/config/i386/i386.c +++ b/gcc/config/i386/i386.c @@ -86,7 +86,6 @@ along with GCC; see the file COPYING3. If not see #include "debug.h" #include "sched-int.h" #include "sbitmap.h" -#include "fibheap.h" #include "opts.h" #include "diagnostic.h" #include "dumpfile.h" diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c index 1ce856f..aa5d029 100644 --- a/gcc/ipa-inline.c +++ b/gcc/ipa-inline.c @@ -102,7 +102,6 @@ along with GCC; see the file COPYING3. If not see #include "diagnostic.h" #include "gimple-pretty-print.h" #include "params.h" -#include "fibheap.h" #include "intl.h" #include "tree-pass.h" #include "coverage.h" diff --git a/gcc/var-tracking.c b/gcc/var-tracking.c index 2278815..e7d4ff1 100644 --- a/gcc/var-tracking.c +++ b/gcc/var-tracking.c @@ -114,7 +114,6 @@ #include "reload.h" #include "sbitmap.h" #include "alloc-pool.h" -#include "fibheap.h" #include "regs.h" #include "expr.h" #include "tree-pass.h" diff --git a/include/fibheap.h b/include/fibheap.h deleted file mode 100644 index a3d09dd..0000000 --- a/include/fibheap.h +++ /dev/null @@ -1,95 +0,0 @@ -/* A Fibonacci heap datatype. - Copyright 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2009 - Free Software Foundation, Inc. - Contributed by Daniel Berlin (d...@cgsoftware.com). - -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 2, 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 COPYING. If not, write to -the Free Software Foundation, 51 Franklin Street - Fifth Floor, -Boston, MA 02110-1301, USA. */ - -/* Fibonacci heaps are somewhat complex, but, there's an article in - DDJ that explains them pretty well: - - http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms - - Introduction to algorithms by Corman and Rivest also goes over them. - - The original paper that introduced them is "Fibonacci heaps and their - uses in improved network optimization algorithms" by Tarjan and - Fredman (JACM 34(3), July 1987). - - Amortized and real worst case time for operations: - - ExtractMin: O(lg n) amortized. O(n) worst case. - DecreaseKey: O(1) amortized. O(lg n) worst case. - Insert: O(2) amortized. O(1) actual. - Union: O(1) amortized. O(1) actual. */ - -#ifndef _FIBHEAP_H_ -#define _FIBHEAP_H_ - -#include "ansidecl.h" - -#ifdef __cplusplus -extern "C" { -#endif - -typedef long fibheapkey_t; - -typedef struct fibheap -{ - size_t nodes; - struct fibnode *min; - struct fibnode *root; -} *fibheap_t; - -typedef struct fibnode -{ - struct fibnode *parent; - struct fibnode *child; - struct fibnode *left; - struct fibnode *right; - fibheapkey_t key; - void *data; -#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4) - __extension__ unsigned long int degree : 31; - __extension__ unsigned long int mark : 1; -#else - unsigned int degree : 31; - unsigned int mark : 1; -#endif -} *fibnode_t; - -extern fibheap_t fibheap_new (void); -extern fibnode_t fibheap_insert (fibheap_t, fibheapkey_t, void *); -extern int fibheap_empty (fibheap_t); -extern fibheapkey_t fibheap_min_key (fibheap_t); -extern fibheapkey_t fibheap_replace_key (fibheap_t, fibnode_t, - fibheapkey_t); -extern void *fibheap_replace_key_data (fibheap_t, fibnode_t, - fibheapkey_t, void *); -extern void *fibheap_extract_min (fibheap_t); -extern void *fibheap_min (fibheap_t); -extern void *fibheap_replace_data (fibheap_t, fibnode_t, void *); -extern void *fibheap_delete_node (fibheap_t, fibnode_t); -extern void fibheap_delete (fibheap_t); -extern fibheap_t fibheap_union (fibheap_t, fibheap_t); - -#ifdef __cplusplus -} -#endif - -#endif /* _FIBHEAP_H_ */ diff --git a/libiberty/Makefile.in b/libiberty/Makefile.in index 1b0d8ae..39ceb3c 100644 --- a/libiberty/Makefile.in +++ b/libiberty/Makefile.in @@ -128,7 +128,7 @@ CFILES = alloca.c argv.c asprintf.c atexit.c \ calloc.c choose-temp.c clock.c concat.c cp-demangle.c \ cp-demint.c cplus-dem.c crc32.c \ d-demangle.c dwarfnames.c dyn-string.c \ - fdmatch.c ffs.c fibheap.c filename_cmp.c floatformat.c \ + fdmatch.c ffs.c filename_cmp.c floatformat.c \ fnmatch.c fopen_unlocked.c \ getcwd.c getopt.c getopt1.c getpagesize.c getpwd.c getruntime.c \ gettimeofday.c \ @@ -169,7 +169,7 @@ REQUIRED_OFILES = \ ./choose-temp.$(objext) ./concat.$(objext) \ ./cp-demint.$(objext) ./crc32.$(objext) ./d-demangle.$(objext) \ ./dwarfnames.$(objext) ./dyn-string.$(objext) \ - ./fdmatch.$(objext) ./fibheap.$(objext) \ + ./fdmatch.$(objext) \ ./filename_cmp.$(objext) ./floatformat.$(objext) \ ./fnmatch.$(objext) ./fopen_unlocked.$(objext) \ ./getopt.$(objext) ./getopt1.$(objext) ./getpwd.$(objext) \ @@ -230,7 +230,6 @@ INSTALLED_HEADERS = \ $(INCDIR)/ansidecl.h \ $(INCDIR)/demangle.h \ $(INCDIR)/dyn-string.h \ - $(INCDIR)/fibheap.h \ $(INCDIR)/floatformat.h \ $(INCDIR)/hashtab.h \ $(INCDIR)/libiberty.h \ @@ -744,16 +743,6 @@ $(CONFIGURED_OFILES): stamp-picdir stamp-noasandir else true; fi $(COMPILE.c) $(srcdir)/ffs.c $(OUTPUT_OPTION) -./fibheap.$(objext): $(srcdir)/fibheap.c config.h $(INCDIR)/ansidecl.h \ - $(INCDIR)/fibheap.h $(INCDIR)/libiberty.h - if [ x"$(PICFLAG)" != x ]; then \ - $(COMPILE.c) $(PICFLAG) $(srcdir)/fibheap.c -o pic/$@; \ - else true; fi - if [ x"$(NOASANFLAG)" != x ]; then \ - $(COMPILE.c) $(PICFLAG) $(NOASANFLAG) $(srcdir)/fibheap.c -o noasan/$@; \ - else true; fi - $(COMPILE.c) $(srcdir)/fibheap.c $(OUTPUT_OPTION) - ./filename_cmp.$(objext): $(srcdir)/filename_cmp.c config.h $(INCDIR)/ansidecl.h \ $(INCDIR)/filenames.h $(INCDIR)/hashtab.h \ $(INCDIR)/safe-ctype.h diff --git a/libiberty/fibheap.c b/libiberty/fibheap.c deleted file mode 100644 index a37ee4e..0000000 --- a/libiberty/fibheap.c +++ /dev/null @@ -1,486 +0,0 @@ -/* A Fibonacci heap datatype. - Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. - Contributed by Daniel Berlin (d...@cgsoftware.com). - -This file is part of GNU CC. - -GNU CC 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 2, or (at your option) -any later version. - -GNU CC 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 GNU CC; see the file COPYING. If not, write to -the Free Software Foundation, 51 Franklin Street - Fifth Floor, -Boston, MA 02110-1301, USA. */ - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif -#ifdef HAVE_LIMITS_H -#include <limits.h> -#endif -#ifdef HAVE_STDLIB_H -#include <stdlib.h> -#endif -#ifdef HAVE_STRING_H -#include <string.h> -#endif -#include "libiberty.h" -#include "fibheap.h" - - -#define FIBHEAPKEY_MIN LONG_MIN - -static void fibheap_ins_root (fibheap_t, fibnode_t); -static void fibheap_rem_root (fibheap_t, fibnode_t); -static void fibheap_consolidate (fibheap_t); -static void fibheap_link (fibheap_t, fibnode_t, fibnode_t); -static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); -static void fibheap_cascading_cut (fibheap_t, fibnode_t); -static fibnode_t fibheap_extr_min_node (fibheap_t); -static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); -static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); -static fibnode_t fibnode_new (void); -static void fibnode_insert_after (fibnode_t, fibnode_t); -#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) -static fibnode_t fibnode_remove (fibnode_t); - - -/* Create a new fibonacci heap. */ -fibheap_t -fibheap_new (void) -{ - return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); -} - -/* Create a new fibonacci heap node. */ -static fibnode_t -fibnode_new (void) -{ - fibnode_t node; - - node = (fibnode_t) xcalloc (1, sizeof *node); - node->left = node; - node->right = node; - - return node; -} - -static inline int -fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) -{ - if (a->key < b->key) - return -1; - if (a->key > b->key) - return 1; - return 0; -} - -static inline int -fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) -{ - struct fibnode a; - - a.key = key; - a.data = data; - - return fibheap_compare (heap, &a, b); -} - -/* Insert DATA, with priority KEY, into HEAP. */ -fibnode_t -fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) -{ - fibnode_t node; - - /* Create the new node. */ - node = fibnode_new (); - - /* Set the node's data. */ - node->data = data; - node->key = key; - - /* Insert it into the root list. */ - fibheap_ins_root (heap, node); - - /* If their was no minimum, or this key is less than the min, - it's the new min. */ - if (heap->min == NULL || node->key < heap->min->key) - heap->min = node; - - heap->nodes++; - - return node; -} - -/* Return the data of the minimum node (if we know it). */ -void * -fibheap_min (fibheap_t heap) -{ - /* If there is no min, we can't easily return it. */ - if (heap->min == NULL) - return NULL; - return heap->min->data; -} - -/* Return the key of the minimum node (if we know it). */ -fibheapkey_t -fibheap_min_key (fibheap_t heap) -{ - /* If there is no min, we can't easily return it. */ - if (heap->min == NULL) - return 0; - return heap->min->key; -} - -/* Union HEAPA and HEAPB into a new heap. */ -fibheap_t -fibheap_union (fibheap_t heapa, fibheap_t heapb) -{ - fibnode_t a_root, b_root, temp; - - /* If one of the heaps is empty, the union is just the other heap. */ - if ((a_root = heapa->root) == NULL) - { - free (heapa); - return heapb; - } - if ((b_root = heapb->root) == NULL) - { - free (heapb); - return heapa; - } - - /* Merge them to the next nodes on the opposite chain. */ - a_root->left->right = b_root; - b_root->left->right = a_root; - temp = a_root->left; - a_root->left = b_root->left; - b_root->left = temp; - heapa->nodes += heapb->nodes; - - /* And set the new minimum, if it's changed. */ - if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) - heapa->min = heapb->min; - - free (heapb); - return heapa; -} - -/* Extract the data of the minimum node from HEAP. */ -void * -fibheap_extract_min (fibheap_t heap) -{ - fibnode_t z; - void *ret = NULL; - - /* If we don't have a min set, it means we have no nodes. */ - if (heap->min != NULL) - { - /* Otherwise, extract the min node, free the node, and return the - node's data. */ - z = fibheap_extr_min_node (heap); - ret = z->data; - free (z); - } - - return ret; -} - -/* Replace both the KEY and the DATA associated with NODE. */ -void * -fibheap_replace_key_data (fibheap_t heap, fibnode_t node, - fibheapkey_t key, void *data) -{ - void *odata; - fibheapkey_t okey; - fibnode_t y; - - /* If we wanted to, we could actually do a real increase by redeleting and - inserting. However, this would require O (log n) time. So just bail out - for now. */ - if (fibheap_comp_data (heap, key, data, node) > 0) - return NULL; - - odata = node->data; - okey = node->key; - node->data = data; - node->key = key; - y = node->parent; - - /* Short-circuit if the key is the same, as we then don't have to - do anything. Except if we're trying to force the new node to - be the new minimum for delete. */ - if (okey == key && okey != FIBHEAPKEY_MIN) - return odata; - - /* These two compares are specifically <= 0 to make sure that in the case - of equality, a node we replaced the data on, becomes the new min. This - is needed so that delete's call to extractmin gets the right node. */ - if (y != NULL && fibheap_compare (heap, node, y) <= 0) - { - fibheap_cut (heap, node, y); - fibheap_cascading_cut (heap, y); - } - - if (fibheap_compare (heap, node, heap->min) <= 0) - heap->min = node; - - return odata; -} - -/* Replace the DATA associated with NODE. */ -void * -fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) -{ - return fibheap_replace_key_data (heap, node, node->key, data); -} - -/* Replace the KEY associated with NODE. */ -fibheapkey_t -fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) -{ - int okey = node->key; - fibheap_replace_key_data (heap, node, key, node->data); - return okey; -} - -/* Delete NODE from HEAP. */ -void * -fibheap_delete_node (fibheap_t heap, fibnode_t node) -{ - void *ret = node->data; - - /* To perform delete, we just make it the min key, and extract. */ - fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); - if (node != heap->min) - { - fprintf (stderr, "Can't force minimum on fibheap.\n"); - abort (); - } - fibheap_extract_min (heap); - - return ret; -} - -/* Delete HEAP. */ -void -fibheap_delete (fibheap_t heap) -{ - while (heap->min != NULL) - free (fibheap_extr_min_node (heap)); - - free (heap); -} - -/* Determine if HEAP is empty. */ -int -fibheap_empty (fibheap_t heap) -{ - return heap->nodes == 0; -} - -/* Extract the minimum node of the heap. */ -static fibnode_t -fibheap_extr_min_node (fibheap_t heap) -{ - fibnode_t ret = heap->min; - fibnode_t x, y, orig; - - /* Attach the child list of the minimum node to the root list of the heap. - If there is no child list, we don't do squat. */ - for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) - { - if (orig == NULL) - orig = x; - y = x->right; - x->parent = NULL; - fibheap_ins_root (heap, x); - } - - /* Remove the old root. */ - fibheap_rem_root (heap, ret); - heap->nodes--; - - /* If we are left with no nodes, then the min is NULL. */ - if (heap->nodes == 0) - heap->min = NULL; - else - { - /* Otherwise, consolidate to find new minimum, as well as do the reorg - work that needs to be done. */ - heap->min = ret->right; - fibheap_consolidate (heap); - } - - return ret; -} - -/* Insert NODE into the root list of HEAP. */ -static void -fibheap_ins_root (fibheap_t heap, fibnode_t node) -{ - /* If the heap is currently empty, the new node becomes the singleton - circular root list. */ - if (heap->root == NULL) - { - heap->root = node; - node->left = node; - node->right = node; - return; - } - - /* Otherwise, insert it in the circular root list between the root - and it's right node. */ - fibnode_insert_after (heap->root, node); -} - -/* Remove NODE from the rootlist of HEAP. */ -static void -fibheap_rem_root (fibheap_t heap, fibnode_t node) -{ - if (node->left == node) - heap->root = NULL; - else - heap->root = fibnode_remove (node); -} - -/* Consolidate the heap. */ -static void -fibheap_consolidate (fibheap_t heap) -{ - fibnode_t a[1 + 8 * sizeof (long)]; - fibnode_t w; - fibnode_t y; - fibnode_t x; - int i; - int d; - int D; - - D = 1 + 8 * sizeof (long); - - memset (a, 0, sizeof (fibnode_t) * D); - - while ((w = heap->root) != NULL) - { - x = w; - fibheap_rem_root (heap, w); - d = x->degree; - while (a[d] != NULL) - { - y = a[d]; - if (fibheap_compare (heap, x, y) > 0) - { - fibnode_t temp; - temp = x; - x = y; - y = temp; - } - fibheap_link (heap, y, x); - a[d] = NULL; - d++; - } - a[d] = x; - } - heap->min = NULL; - for (i = 0; i < D; i++) - if (a[i] != NULL) - { - fibheap_ins_root (heap, a[i]); - if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) - heap->min = a[i]; - } -} - -/* Make NODE a child of PARENT. */ -static void -fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, - fibnode_t node, fibnode_t parent) -{ - if (parent->child == NULL) - parent->child = node; - else - fibnode_insert_before (parent->child, node); - node->parent = parent; - parent->degree++; - node->mark = 0; -} - -/* Remove NODE from PARENT's child list. */ -static void -fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) -{ - fibnode_remove (node); - parent->degree--; - fibheap_ins_root (heap, node); - node->parent = NULL; - node->mark = 0; -} - -static void -fibheap_cascading_cut (fibheap_t heap, fibnode_t y) -{ - fibnode_t z; - - while ((z = y->parent) != NULL) - { - if (y->mark == 0) - { - y->mark = 1; - return; - } - else - { - fibheap_cut (heap, y, z); - y = z; - } - } -} - -static void -fibnode_insert_after (fibnode_t a, fibnode_t b) -{ - if (a == a->right) - { - a->right = b; - a->left = b; - b->right = a; - b->left = a; - } - else - { - b->right = a->right; - a->right->left = b; - a->right = b; - b->left = a; - } -} - -static fibnode_t -fibnode_remove (fibnode_t node) -{ - fibnode_t ret; - - if (node == node->left) - ret = NULL; - else - ret = node->left; - - if (node->parent != NULL && node->parent->child == node) - node->parent->child = ret; - - node->right->left = node->left; - node->left->right = node->right; - - node->parent = NULL; - node->left = node; - node->right = node; - - return ret; -} -- 2.1.2