From 4a91004954f29d8f7c05da3cf70ace12eaeb891b Mon Sep 17 00:00:00 2001 From: Martin Liska Date: Tue, 18 Nov 2014 17:09:11 +0100 Subject: [PATCH] New template fibonacci_heap class introduced. * fibonacci_heap.h: New file. (fibonacci_heap::insert): Created from fibheap_insert. (fibonacci_heap::empty): Created from fibheap_empty. (fibonacci_heap::nodes): Created from fibheap_nodes. (fibonacci_heap::min_key): Created from fibheap_min_key. (fibonacci_heap::decrease_key): Created from fibheap_replace_key. (fibonacci_heap::replace_key_data): Created from fibheap_replace_key_data. (fibonacci_heap::extract_min): Created from fibheap_extract_min. (fibonacci_heap::min): Created from fibheap_min. (fibonacci_heap::replace_data): Created from fibheap_replace_data. (fibonacci_heap::delete_node): Created from fibheap_delete_node. (fibonacci_heap::union_with): Created from fibheap_union. * ipa-inline.c (update_edge_key): New heap API is used. (update_caller_keys): Likewise. (update_callee_keys): Likewise. (lookup_recursive_calls): Likewise. (recursive_inlining): Likewise. (add_new_edges_to_heap): Likewise. (heap_edge_removal_hook): Likewise. (inline_small_functions): Likewise. From-SVN: r217720 --- gcc/ChangeLog | 23 ++ gcc/fibonacci_heap.h | 608 +++++++++++++++++++++++++++++++++++++++++++ gcc/ipa-inline.c | 107 ++++---- 3 files changed, 682 insertions(+), 56 deletions(-) create mode 100644 gcc/fibonacci_heap.h diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 1e1d355b589..9c5f5fccace 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,26 @@ +2014-11-18 Martin Liska + + * fibonacci_heap.h: New file. + (fibonacci_heap::insert): Created from fibheap_insert. + (fibonacci_heap::empty): Created from fibheap_empty. + (fibonacci_heap::nodes): Created from fibheap_nodes. + (fibonacci_heap::min_key): Created from fibheap_min_key. + (fibonacci_heap::decrease_key): Created from fibheap_replace_key. + (fibonacci_heap::replace_key_data): Created from fibheap_replace_key_data. + (fibonacci_heap::extract_min): Created from fibheap_extract_min. + (fibonacci_heap::min): Created from fibheap_min. + (fibonacci_heap::replace_data): Created from fibheap_replace_data. + (fibonacci_heap::delete_node): Created from fibheap_delete_node. + (fibonacci_heap::union_with): Created from fibheap_union. + * ipa-inline.c (update_edge_key): New heap API is used. + (update_caller_keys): Likewise. + (update_callee_keys): Likewise. + (lookup_recursive_calls): Likewise. + (recursive_inlining): Likewise. + (add_new_edges_to_heap): Likewise. + (heap_edge_removal_hook): Likewise. + (inline_small_functions): Likewise. + 2014-11-18 Marek Polacek PR sanitizer/63866 diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h new file mode 100644 index 00000000000..ecb92f8b01f --- /dev/null +++ b/gcc/fibonacci_heap.h @@ -0,0 +1,608 @@ +/* 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 + +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 +. */ + +/* 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(1) amortized. + Union: O(1) amortized. */ + +#ifndef GCC_FIBONACCI_HEAP_H +#define GCC_FIBONACCI_HEAP_H + +/* Forward definition. */ + +template +class fibonacci_heap; + +/* Fibonacci heap node class. */ + +template +class fibonacci_node +{ + typedef fibonacci_node fibonacci_node_t; + friend class fibonacci_heap; + +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 given 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 fibonacci_heap +{ + typedef fibonacci_node fibonacci_node_t; + friend class fibonacci_node; + +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 decrease_key (fibonacci_node_t *node, K key) + { + K okey = node->m_key; + gcc_assert (key <= okey); + + 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 +fibonacci_node * +fibonacci_node::remove () +{ + fibonacci_node *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 +void +fibonacci_node::link (fibonacci_node *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 +void +fibonacci_node::insert_after (fibonacci_node *b) +{ + fibonacci_node *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 +fibonacci_node* +fibonacci_heap::insert (K key, V *data) +{ + /* Create the new node. */ + fibonacci_node *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 +V* +fibonacci_heap::replace_key_data (fibonacci_node *node, K key, + V *data) +{ + V *odata; + K okey; + fibonacci_node *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 +V* +fibonacci_heap::extract_min () +{ + fibonacci_node *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 +V* +fibonacci_heap::delete_node (fibonacci_node *node) +{ + V *ret = node->m_data; + + /* To perform delete, we just make it the min key, and extract. */ + decrease_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 +fibonacci_heap* +fibonacci_heap::union_with (fibonacci_heap *heapb) +{ + fibonacci_heap *heapa = this; + + fibonacci_node *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 +void +fibonacci_heap::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 +void +fibonacci_heap::cut (fibonacci_node *node, + fibonacci_node *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 +void +fibonacci_heap::cascading_cut (fibonacci_node *y) +{ + fibonacci_node *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 +fibonacci_node* +fibonacci_heap::extract_minimum_node () +{ + fibonacci_node *ret = m_min; + fibonacci_node *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 +void +fibonacci_heap::remove_root (fibonacci_node *node) +{ + if (node->m_left == node) + m_root = NULL; + else + m_root = node->remove (); +} + +/* Consolidate heap. */ + +template +void fibonacci_heap::consolidate () +{ + int D = 1 + 8 * sizeof (long); + auto_vec *> a (D); + a.safe_grow_cleared (D); + fibonacci_node *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) + std::swap (x, y); + 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 diff --git a/gcc/ipa-inline.c b/gcc/ipa-inline.c index 5c9781584e1..ca50ad5268c 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" @@ -138,6 +137,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 edge_heap_t; +typedef fibonacci_node edge_heap_node_t; /* Statistics we collect about inlining algorithm. */ static int overall_size; @@ -1076,19 +1079,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 +1101,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->decrease_key (n, badness); + gcc_checking_assert (n->get_key () == badness); } } else @@ -1117,7 +1120,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 +1183,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 +1214,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 +1229,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 +1258,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 +1283,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 +1295,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 +1314,7 @@ recursive_inlining (struct cgraph_edge *edge, vec *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 +1331,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 +1341,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 +1405,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 +1455,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 new_edges) +add_new_edges_to_heap (edge_heap_t *heap, vec new_edges) { while (new_edges.length () > 0) { @@ -1469,7 +1465,7 @@ add_new_edges_to_heap (fibheap_t heap, vec 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 +1478,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 +1536,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 +1568,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 new_indirect_edges; @@ -1583,7 +1579,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 +1658,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 +1673,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 +1683,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 +1713,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 +1753,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 +1777,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 +1813,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 +1822,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 +1839,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 +1863,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", -- 2.30.2