new file mode 100644
@@ -0,0 +1,612 @@
+/* Vector API for GNU compiler.
+ Copyright (C) 1998-2014 Free Software Foundation, Inc.
+ Contributed by Daniel Berlin (dan@cgsoftware.com).
+ Re-implemented in C++ by Martin Liska <mliska@suse.cz>
+
+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/>. */
+
+/* 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 GCC_FIBONACCI_HEAP_H
+#define GCC_FIBONACCI_HEAP_H
+
+/* Forward definition. */
+
+template<class K, class V>
+class fibonacci_heap;
+
+/* Fibonacci heap node class. */
+
+template<class K, class V>
+class fibonacci_node
+{
+ typedef fibonacci_node<K,V> fibonacci_node_t;
+ friend class fibonacci_heap<K,V>;
+
+public:
+ /* Default constructor. */
+ fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
+ m_right (this), m_degree (0), m_mark (0)
+ {
+ }
+
+ /* Constructor for a node with givek KEY. */
+ fibonacci_node (K key): m_parent (NULL), m_child (NULL), m_left (this),
+ m_right (this), m_key (key),
+ m_degree (0), m_mark (0)
+ {
+ }
+
+ /* Compare fibonacci node with OTHER node. */
+ int compare (fibonacci_node_t *other)
+ {
+ if (m_key < other->m_key)
+ return -1;
+ if (m_key > other->m_key)
+ return 1;
+ return 0;
+ }
+
+ /* Compare the node with a given KEY. */
+ int compare_data (K key)
+ {
+ return fibonacci_node_t (key).compare (this);
+ }
+
+ /* Remove fibonacci heap node. */
+ fibonacci_node_t *remove ();
+
+ /* Link the node with PARENT. */
+ void link (fibonacci_node_t *parent);
+
+ /* Return key associated with the node. */
+ K get_key ()
+ {
+ return m_key;
+ }
+
+ /* Return data associated with the node. */
+ V *get_data ()
+ {
+ return m_data;
+ }
+
+private:
+ /* Put node B after this node. */
+ void insert_after (fibonacci_node_t *b);
+
+ /* Insert fibonacci node B after this node. */
+ void insert_before (fibonacci_node_t *b)
+ {
+ m_left->insert_after (b);
+ }
+
+ /* Parent node. */
+ fibonacci_node *m_parent;
+ /* Child node. */
+ fibonacci_node *m_child;
+ /* Left sibling. */
+ fibonacci_node *m_left;
+ /* Right node. */
+ fibonacci_node *m_right;
+ /* Key associated with node. */
+ K m_key;
+ /* Data associated with node. */
+ V *m_data;
+
+#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
+ /* Degree of the node. */
+ __extension__ unsigned long int m_degree : 31;
+ /* Mark of the node. */
+ __extension__ unsigned long int m_mark : 1;
+#else
+ /* Degree of the node. */
+ unsigned int m_degree : 31;
+ /* Mark of the node. */
+ unsigned int m_mark : 1;
+#endif
+};
+
+/* Fibonacci heap class. */
+template<class K, class V>
+class fibonacci_heap
+{
+ typedef fibonacci_node<K,V> fibonacci_node_t;
+ friend class fibonacci_node<K,V>;
+
+public:
+ /* Default constructor. */
+ fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL),
+ m_global_min_key (global_min_key)
+ {
+ }
+
+ /* Destructor. */
+ ~fibonacci_heap ()
+ {
+ while (m_min != NULL)
+ delete (extract_minimum_node ());
+ }
+
+ /* Insert new node given by KEY and DATA associated with the key. */
+ fibonacci_node_t *insert (K key, V *data);
+
+ /* Return true if no entry is present. */
+ bool empty ()
+ {
+ return m_nodes == 0;
+ }
+
+ /* Return the number of nodes. */
+ size_t nodes ()
+ {
+ return m_nodes;
+ }
+
+ /* Return minimal key presented in the heap. */
+ K min_key ()
+ {
+ if (m_min == NULL)
+ gcc_unreachable ();
+
+ return m_min->m_key;
+ }
+
+ /* For given NODE, set new KEY value. */
+ K replace_key (fibonacci_node_t *node, K key)
+ {
+ K okey = node->m_key;
+ replace_key_data (node, key, node->m_data);
+ return okey;
+ }
+
+ /* For given NODE, set new KEY and DATA value. */
+ V *replace_key_data (fibonacci_node_t *node, K key, V *data);
+
+ /* Extract minimum node in the heap. */
+ V *extract_min ();
+
+ /* Return value associated with minimum node in the heap. */
+ V *min ()
+ {
+ if (m_min == NULL)
+ return NULL;
+
+ return m_min->data;
+ }
+
+ /* Replace data associated with NODE and replace it with DATA. */
+ V *replace_data (fibonacci_node_t *node, V *data)
+ {
+ return replace_key_data (node, node->m_key, data);
+ }
+
+ /* Delete NODE in the heap. */
+ V *delete_node (fibonacci_node_t *node);
+
+ /* Union the heap with HEAPB. */
+ fibonacci_heap *union_with (fibonacci_heap *heapb);
+
+private:
+ /* Insert it into the root list. */
+ void insert_root (fibonacci_node_t *node);
+
+ /* Remove NODE from PARENT's child list. */
+ void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
+
+ /* Process cut of node Y and do it recursivelly. */
+ void cascading_cut (fibonacci_node_t *y);
+
+ /* Extract minimum node from the heap. */
+ fibonacci_node_t * extract_minimum_node ();
+
+ /* Remove root NODE from the heap. */
+ void remove_root (fibonacci_node_t *node);
+
+ /* Consolidate heap. */
+ void consolidate ();
+
+ /* Number of nodes. */
+ size_t m_nodes;
+ /* Minimum node of the heap. */
+ fibonacci_node_t *m_min;
+ /* Root node of the heap. */
+ fibonacci_node_t *m_root;
+ /* Global minimum given in the heap construction. */
+ K m_global_min_key;
+};
+
+/* Remove fibonacci heap node. */
+
+template<class K, class V>
+fibonacci_node<K,V> *
+fibonacci_node<K,V>::remove ()
+{
+ fibonacci_node<K,V> *ret;
+
+ if (this == m_left)
+ ret = NULL;
+ else
+ ret = m_left;
+
+ if (m_parent != NULL && m_parent->m_child == this)
+ m_parent->m_child = ret;
+
+ m_right->m_left = m_left;
+ m_left->m_right = m_right;
+
+ m_parent = NULL;
+ m_left = this;
+ m_right = this;
+
+ return ret;
+}
+
+/* Link the node with PARENT. */
+
+template<class K, class V>
+void
+fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
+{
+ if (parent->m_child == NULL)
+ parent->m_child = this;
+ else
+ parent->m_child->insert_before (this);
+ m_parent = parent;
+ parent->m_degree++;
+ m_mark = 0;
+}
+
+/* Put node B after this node. */
+
+template<class K, class V>
+void
+fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
+{
+ fibonacci_node<K,V> *a = this;
+
+ if (a == a->m_right)
+ {
+ a->m_right = b;
+ a->m_left = b;
+ b->m_right = a;
+ b->m_left = a;
+ }
+ else
+ {
+ b->m_right = a->m_right;
+ a->m_right->m_left = b;
+ a->m_right = b;
+ b->m_left = a;
+ }
+}
+
+/* Insert new node given by KEY and DATA associated with the key. */
+
+template<class K, class V>
+fibonacci_node<K,V>*
+fibonacci_heap<K,V>::insert (K key, V *data)
+{
+ /* Create the new node. */
+ fibonacci_node<K,V> *node = new fibonacci_node_t ();
+
+ /* Set the node's data. */
+ node->m_data = data;
+ node->m_key = key;
+
+ /* Insert it into the root list. */
+ insert_root (node);
+
+ /* If their was no minimum, or this key is less than the min,
+ it's the new min. */
+ if (m_min == NULL || node->m_key < m_min->m_key)
+ m_min = node;
+
+ m_nodes++;
+
+ return node;
+}
+
+/* For given NODE, set new KEY and DATA value. */
+template<class K, class V>
+V*
+fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
+ V *data)
+{
+ V *odata;
+ K okey;
+ fibonacci_node<K,V> *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 (node->compare_data (key) > 0)
+ return NULL;
+
+ odata = node->m_data;
+ okey = node->m_key;
+ node->m_data = data;
+ node->m_key = key;
+ y = node->m_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 != m_global_min_key)
+ 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 && node->compare (y) <= 0)
+ {
+ cut (node, y);
+ cascading_cut (y);
+ }
+
+ if (node->compare (m_min) <= 0)
+ m_min = node;
+
+ return odata;
+}
+
+/* Extract minimum node in the heap. */
+template<class K, class V>
+V*
+fibonacci_heap<K,V>::extract_min ()
+{
+ fibonacci_node<K,V> *z;
+ V *ret = NULL;
+
+ /* If we don't have a min set, it means we have no nodes. */
+ if (m_min != NULL)
+ {
+ /* Otherwise, extract the min node, free the node, and return the
+ node's data. */
+ z = extract_minimum_node ();
+ ret = z->m_data;
+ delete (z);
+ }
+
+ return ret;
+}
+
+/* Delete NODE in the heap. */
+
+template<class K, class V>
+V*
+fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node)
+{
+ V *ret = node->m_data;
+
+ /* To perform delete, we just make it the min key, and extract. */
+ replace_key (node, m_global_min_key);
+ if (node != m_min)
+ {
+ fprintf (stderr, "Can't force minimum on fibheap.\n");
+ abort ();
+ }
+ extract_min ();
+
+ return ret;
+}
+
+/* Union the heap with HEAPB. */
+
+template<class K, class V>
+fibonacci_heap<K,V>*
+fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
+{
+ fibonacci_heap<K,V> *heapa = this;
+
+ fibonacci_node<K,V> *a_root, *b_root, *temp;
+
+ /* If one of the heaps is empty, the union is just the other heap. */
+ if ((a_root = heapa->m_root) == NULL)
+ {
+ delete (heapa);
+ return heapb;
+ }
+ if ((b_root = heapb->m_root) == NULL)
+ {
+ delete (heapb);
+ return heapa;
+ }
+
+ /* Merge them to the next nodes on the opposite chain. */
+ a_root->m_left->m_right = b_root;
+ b_root->m_left->m_right = a_root;
+ temp = a_root->m_left;
+ a_root->m_left = b_root->m_left;
+ b_root->m_left = temp;
+ heapa->m_nodes += heapb->m_nodes;
+
+ /* And set the new minimum, if it's changed. */
+ if (heapb->min->compare (heapa->min) < 0)
+ heapa->m_min = heapb->m_min;
+
+ delete (heapb);
+ return heapa;
+}
+
+/* Insert it into the root list. */
+
+template<class K, class V>
+void
+fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
+{
+ /* If the heap is currently empty, the new node becomes the singleton
+ circular root list. */
+ if (m_root == NULL)
+ {
+ m_root = node;
+ node->m_left = node;
+ node->m_right = node;
+ return;
+ }
+
+ /* Otherwise, insert it in the circular root list between the root
+ and it's right node. */
+ m_root->insert_after (node);
+}
+
+/* Remove NODE from PARENT's child list. */
+
+template<class K, class V>
+void
+fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
+ fibonacci_node<K,V> *parent)
+{
+ node->remove ();
+ parent->m_degree--;
+ insert_root (node);
+ node->m_parent = NULL;
+ node->m_mark = 0;
+}
+
+/* Process cut of node Y and do it recursivelly. */
+
+template<class K, class V>
+void
+fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
+{
+ fibonacci_node<K,V> *z;
+
+ while ((z = y->m_parent) != NULL)
+ {
+ if (y->m_mark == 0)
+ {
+ y->m_mark = 1;
+ return;
+ }
+ else
+ {
+ cut (y, z);
+ y = z;
+ }
+ }
+}
+
+/* Extract minimum node from the heap. */
+template<class K, class V>
+fibonacci_node<K,V>*
+fibonacci_heap<K,V>::extract_minimum_node ()
+{
+ fibonacci_node<K,V> *ret = m_min;
+ fibonacci_node<K,V> *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->m_child, orig = NULL; x != orig && x != NULL; x = y)
+ {
+ if (orig == NULL)
+ orig = x;
+ y = x->m_right;
+ x->m_parent = NULL;
+ insert_root (x);
+ }
+
+ /* Remove the old root. */
+ remove_root (ret);
+ m_nodes--;
+
+ /* If we are left with no nodes, then the min is NULL. */
+ if (m_nodes == 0)
+ m_min = NULL;
+ else
+ {
+ /* Otherwise, consolidate to find new minimum, as well as do the reorg
+ work that needs to be done. */
+ m_min = ret->m_right;
+ consolidate ();
+ }
+
+ return ret;
+}
+
+/* Remove root NODE from the heap. */
+
+template<class K, class V>
+void
+fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
+{
+ if (node->m_left == node)
+ m_root = NULL;
+ else
+ m_root = node->remove ();
+}
+
+/* Consolidate heap. */
+
+template<class K, class V>
+void fibonacci_heap<K,V>::consolidate ()
+{
+ int D = 1 + 8 * sizeof (long);
+ auto_vec<fibonacci_node<K,V> *> a (D);
+ a.safe_grow_cleared (D);
+ fibonacci_node<K,V> *w, *x, *y;
+ int i, d;
+
+ while ((w = m_root) != NULL)
+ {
+ x = w;
+ remove_root (w);
+ d = x->m_degree;
+ while (a[d] != NULL)
+ {
+ y = a[d];
+ if (x->compare (y) > 0)
+ {
+ /* TODO: swap */
+ fibonacci_node_t *temp;
+ temp = x;
+ x = y;
+ y = temp;
+ }
+ y->link (x);
+ a[d] = NULL;
+ d++;
+ }
+ a[d] = x;
+ }
+ m_min = NULL;
+ for (i = 0; i < D; i++)
+ if (a[i] != NULL)
+ {
+ insert_root (a[i]);
+ if (m_min == NULL || a[i]->compare (m_min) < 0)
+ m_min = a[i];
+ }
+}
+
+#endif // GCC_FIBONACCI_HEAP_H
@@ -138,6 +138,10 @@ along with GCC; see the file COPYING3. If not see
#include "auto-profile.h"
#include "cilk.h"
#include "builtins.h"
+#include "fibonacci_heap.h"
+
+typedef fibonacci_heap <long, cgraph_edge> edge_heap_t;
+typedef fibonacci_node <long, cgraph_edge> edge_heap_node_t;
/* Statistics we collect about inlining algorithm. */
static int overall_size;
@@ -1076,19 +1080,19 @@ edge_badness (struct cgraph_edge *edge, bool dump)
/* Recompute badness of EDGE and update its key in HEAP if needed. */
static inline void
-update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
+update_edge_key (edge_heap_t *heap, struct cgraph_edge *edge)
{
int badness = edge_badness (edge, false);
if (edge->aux)
{
- fibnode_t n = (fibnode_t) edge->aux;
- gcc_checking_assert (n->data == edge);
+ edge_heap_node_t *n = (edge_heap_node_t *) edge->aux;
+ gcc_checking_assert (n->get_data () == edge);
- /* fibheap_replace_key only decrease the keys.
+ /* fibonacci_heap::replace_key only decrease the keys.
When we increase the key we do not update heap
and instead re-insert the element once it becomes
a minimum of heap. */
- if (badness < n->key)
+ if (badness < n->get_key ())
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
@@ -1098,11 +1102,11 @@ update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
edge->caller->order,
xstrdup (edge->callee->name ()),
edge->callee->order,
- (int)n->key,
+ (int)n->get_key (),
badness);
}
- fibheap_replace_key (heap, n, badness);
- gcc_checking_assert (n->key == badness);
+ heap->replace_key (n, badness);
+ gcc_checking_assert (n->get_key () == badness);
}
}
else
@@ -1117,7 +1121,7 @@ update_edge_key (fibheap_t heap, struct cgraph_edge *edge)
edge->callee->order,
badness);
}
- edge->aux = fibheap_insert (heap, badness, edge);
+ edge->aux = heap->insert (badness, edge);
}
}
@@ -1180,7 +1184,7 @@ reset_edge_caches (struct cgraph_node *node)
it is inlinable. Otherwise check all edges. */
static void
-update_caller_keys (fibheap_t heap, struct cgraph_node *node,
+update_caller_keys (edge_heap_t *heap, struct cgraph_node *node,
bitmap updated_nodes,
struct cgraph_edge *check_inlinablity_for)
{
@@ -1211,7 +1215,7 @@ update_caller_keys (fibheap_t heap, struct cgraph_node *node,
else if (edge->aux)
{
report_inline_failed_reason (edge);
- fibheap_delete_node (heap, (fibnode_t) edge->aux);
+ heap->delete_node ((edge_heap_node_t *) edge->aux);
edge->aux = NULL;
}
}
@@ -1226,7 +1230,7 @@ update_caller_keys (fibheap_t heap, struct cgraph_node *node,
created edges into heap. */
static void
-update_callee_keys (fibheap_t heap, struct cgraph_node *node,
+update_callee_keys (edge_heap_t *heap, struct cgraph_node *node,
bitmap updated_nodes)
{
struct cgraph_edge *e = node->callees;
@@ -1255,7 +1259,7 @@ update_callee_keys (fibheap_t heap, struct cgraph_node *node,
else if (e->aux)
{
report_inline_failed_reason (e);
- fibheap_delete_node (heap, (fibnode_t) e->aux);
+ heap->delete_node ((edge_heap_node_t *) e->aux);
e->aux = NULL;
}
}
@@ -1280,7 +1284,7 @@ update_callee_keys (fibheap_t heap, struct cgraph_node *node,
static void
lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
- fibheap_t heap)
+ edge_heap_t *heap)
{
struct cgraph_edge *e;
enum availability avail;
@@ -1292,10 +1296,9 @@ lookup_recursive_calls (struct cgraph_node *node, struct cgraph_node *where,
{
/* When profile feedback is available, prioritize by expected number
of calls. */
- fibheap_insert (heap,
- !max_count ? -e->frequency
- : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
- e);
+ heap->insert (!max_count ? -e->frequency
+ : -(e->count / ((max_count + (1<<24) - 1) / (1<<24))),
+ e);
}
for (e = where->callees; e; e = e->next_callee)
if (!e->inline_failed)
@@ -1312,7 +1315,7 @@ recursive_inlining (struct cgraph_edge *edge,
vec<cgraph_edge *> *new_edges)
{
int limit = PARAM_VALUE (PARAM_MAX_INLINE_INSNS_RECURSIVE_AUTO);
- fibheap_t heap;
+ edge_heap_t heap (LONG_MIN);
struct cgraph_node *node;
struct cgraph_edge *e;
struct cgraph_node *master_clone = NULL, *next;
@@ -1329,13 +1332,9 @@ recursive_inlining (struct cgraph_edge *edge,
/* Make sure that function is small enough to be considered for inlining. */
if (estimate_size_after_inlining (node, edge) >= limit)
return false;
- heap = fibheap_new ();
- lookup_recursive_calls (node, node, heap);
- if (fibheap_empty (heap))
- {
- fibheap_delete (heap);
- return false;
- }
+ lookup_recursive_calls (node, node, &heap);
+ if (heap.empty ())
+ return false;
if (dump_file)
fprintf (dump_file,
@@ -1343,10 +1342,9 @@ recursive_inlining (struct cgraph_edge *edge,
node->name ());
/* Do the inlining and update list of recursive call during process. */
- while (!fibheap_empty (heap))
+ while (!heap.empty ())
{
- struct cgraph_edge *curr
- = (struct cgraph_edge *) fibheap_extract_min (heap);
+ struct cgraph_edge *curr = heap.extract_min ();
struct cgraph_node *cnode, *dest = curr->callee;
if (!can_inline_edge_p (curr, true))
@@ -1408,13 +1406,12 @@ recursive_inlining (struct cgraph_edge *edge,
}
inline_call (curr, false, new_edges, &overall_size, true);
- lookup_recursive_calls (node, curr->callee, heap);
+ lookup_recursive_calls (node, curr->callee, &heap);
n++;
}
- if (!fibheap_empty (heap) && dump_file)
+ if (!heap.empty () && dump_file)
fprintf (dump_file, " Recursive inlining growth limit met.\n");
- fibheap_delete (heap);
if (!master_clone)
return false;
@@ -1459,7 +1456,7 @@ compute_max_insns (int insns)
/* Compute badness of all edges in NEW_EDGES and add them to the HEAP. */
static void
-add_new_edges_to_heap (fibheap_t heap, vec<cgraph_edge *> new_edges)
+add_new_edges_to_heap (edge_heap_t *heap, vec<cgraph_edge *> new_edges)
{
while (new_edges.length () > 0)
{
@@ -1469,7 +1466,7 @@ add_new_edges_to_heap (fibheap_t heap, vec<cgraph_edge *> new_edges)
if (edge->inline_failed
&& can_inline_edge_p (edge, true)
&& want_inline_small_function_p (edge, true))
- edge->aux = fibheap_insert (heap, edge_badness (edge, false), edge);
+ edge->aux = heap->insert (edge_badness (edge, false), edge);
}
}
@@ -1482,7 +1479,7 @@ heap_edge_removal_hook (struct cgraph_edge *e, void *data)
reset_node_growth_cache (e->callee);
if (e->aux)
{
- fibheap_delete_node ((fibheap_t)data, (fibnode_t)e->aux);
+ ((edge_heap_t *)data)->delete_node ((edge_heap_node_t *)e->aux);
e->aux = NULL;
}
}
@@ -1540,7 +1537,7 @@ speculation_useful_p (struct cgraph_edge *e, bool anticipate_inlining)
See if we can remove speculation. */
static void
-resolve_noninline_speculation (fibheap_t edge_heap, struct cgraph_edge *edge)
+resolve_noninline_speculation (edge_heap_t *edge_heap, struct cgraph_edge *edge)
{
if (edge->speculative && !speculation_useful_p (edge, false))
{
@@ -1572,7 +1569,7 @@ inline_small_functions (void)
{
struct cgraph_node *node;
struct cgraph_edge *edge;
- fibheap_t edge_heap = fibheap_new ();
+ edge_heap_t edge_heap (LONG_MIN);
bitmap updated_nodes = BITMAP_ALLOC (NULL);
int min_size, max_size;
auto_vec<cgraph_edge *> new_indirect_edges;
@@ -1583,7 +1580,7 @@ inline_small_functions (void)
new_indirect_edges.create (8);
edge_removal_hook_holder
- = symtab->add_edge_removal_hook (&heap_edge_removal_hook, edge_heap);
+ = symtab->add_edge_removal_hook (&heap_edge_removal_hook, &edge_heap);
/* Compute overall unit size and other global parameters used by badness
metrics. */
@@ -1662,7 +1659,7 @@ inline_small_functions (void)
&& edge->inline_failed)
{
gcc_assert (!edge->aux);
- update_edge_key (edge_heap, edge);
+ update_edge_key (&edge_heap, edge);
}
if (edge->speculative && !speculation_useful_p (edge, edge->aux != NULL))
{
@@ -1677,7 +1674,7 @@ inline_small_functions (void)
inline_update_overall_summary (where);
reset_node_growth_cache (where);
reset_edge_caches (where);
- update_caller_keys (edge_heap, where,
+ update_caller_keys (&edge_heap, where,
updated_nodes, NULL);
bitmap_clear (updated_nodes);
}
@@ -1687,16 +1684,16 @@ inline_small_functions (void)
|| !max_count
|| (profile_info && flag_branch_probabilities));
- while (!fibheap_empty (edge_heap))
+ while (!edge_heap.empty ())
{
int old_size = overall_size;
struct cgraph_node *where, *callee;
- int badness = fibheap_min_key (edge_heap);
+ int badness = edge_heap.min_key ();
int current_badness;
int cached_badness;
int growth;
- edge = (struct cgraph_edge *) fibheap_extract_min (edge_heap);
+ edge = edge_heap.extract_min ();
gcc_assert (edge->aux);
edge->aux = NULL;
if (!edge->inline_failed || !edge->callee->analyzed)
@@ -1717,13 +1714,13 @@ inline_small_functions (void)
gcc_assert (current_badness >= badness);
if (current_badness != badness)
{
- edge->aux = fibheap_insert (edge_heap, current_badness, edge);
+ edge->aux = edge_heap.insert (current_badness, edge);
continue;
}
if (!can_inline_edge_p (edge, true))
{
- resolve_noninline_speculation (edge_heap, edge);
+ resolve_noninline_speculation (&edge_heap, edge);
continue;
}
@@ -1757,13 +1754,13 @@ inline_small_functions (void)
{
edge->inline_failed = CIF_INLINE_UNIT_GROWTH_LIMIT;
report_inline_failed_reason (edge);
- resolve_noninline_speculation (edge_heap, edge);
+ resolve_noninline_speculation (&edge_heap, edge);
continue;
}
if (!want_inline_small_function_p (edge, true))
{
- resolve_noninline_speculation (edge_heap, edge);
+ resolve_noninline_speculation (&edge_heap, edge);
continue;
}
@@ -1781,15 +1778,15 @@ inline_small_functions (void)
? &new_indirect_edges : NULL))
{
edge->inline_failed = CIF_RECURSIVE_INLINING;
- resolve_noninline_speculation (edge_heap, edge);
+ resolve_noninline_speculation (&edge_heap, edge);
continue;
}
reset_edge_caches (where);
/* Recursive inliner inlines all recursive calls of the function
at once. Consequently we need to update all callee keys. */
if (flag_indirect_inlining)
- add_new_edges_to_heap (edge_heap, new_indirect_edges);
- update_callee_keys (edge_heap, where, updated_nodes);
+ add_new_edges_to_heap (&edge_heap, new_indirect_edges);
+ update_callee_keys (&edge_heap, where, updated_nodes);
bitmap_clear (updated_nodes);
}
else
@@ -1817,7 +1814,7 @@ inline_small_functions (void)
edge->inline_failed
= (DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl)
? CIF_RECURSIVE_INLINING : CIF_UNSPECIFIED);
- resolve_noninline_speculation (edge_heap, edge);
+ resolve_noninline_speculation (&edge_heap, edge);
continue;
}
else if (depth && dump_file)
@@ -1826,12 +1823,12 @@ inline_small_functions (void)
gcc_checking_assert (!callee->global.inlined_to);
inline_call (edge, true, &new_indirect_edges, &overall_size, true);
if (flag_indirect_inlining)
- add_new_edges_to_heap (edge_heap, new_indirect_edges);
+ add_new_edges_to_heap (&edge_heap, new_indirect_edges);
reset_edge_caches (edge->callee);
reset_node_growth_cache (callee);
- update_callee_keys (edge_heap, where, updated_nodes);
+ update_callee_keys (&edge_heap, where, updated_nodes);
}
where = edge->caller;
if (where->global.inlined_to)
@@ -1843,7 +1840,7 @@ inline_small_functions (void)
inlined into (since it's body size changed) and for the functions
called by function we inlined (since number of it inlinable callers
might change). */
- update_caller_keys (edge_heap, where, updated_nodes, NULL);
+ update_caller_keys (&edge_heap, where, updated_nodes, NULL);
bitmap_clear (updated_nodes);
if (dump_file)
@@ -1867,7 +1864,6 @@ inline_small_functions (void)
}
free_growth_caches ();
- fibheap_delete (edge_heap);
if (dump_file)
fprintf (dump_file,
"Unit growth for small function inlining: %i->%i (%i%%)\n",