@@ -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;
@@ -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"
@@ -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"
@@ -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"
@@ -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"
@@ -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"
deleted file mode 100644
@@ -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 (dan@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_ */
@@ -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
deleted file mode 100644
@@ -1,486 +0,0 @@
-/* A Fibonacci heap datatype.
- Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
- Contributed by Daniel Berlin (dan@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;
-}