Re: [PATCH] PR lto/63968: 175.vpr from cpu2000 fails to build with LTO
> >Can you verify that the implementation is correct? I tend to remember that I > >introduced the > >lazy incerementation to inliner both for perofrmance and correctness > >reasons. I used to get > >odd orders when keys was increased. > > > >Honza > > Hello. > > What kind of correctness do you mean? Old implementation didn't > support increment operation and the fact was hushed up. I see, you patch actually implement the variant of busy (and thus suboptimal) method of increasing key by combination of removal&insertion. I guess O(log n) is good enough for everything except for inliner that does the lazy increases instead. Doing lazy increases probably means to store pair of keys per node that is wasteful, so the patch is OK as it is. Honza > > Martin
Re: [PATCH] PR lto/63968: 175.vpr from cpu2000 fails to build with LTO
On 11/20/2014 10:13 PM, Jan Hubicka wrote:
Hello.
As I reimplemented fibheap to C++ template, Honza told me that replace_key
method actually
supports just decrement operation. Old implementation suppress any feedback if
we try to increase key:
fibheap.c:
...
/* 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;
...
My reimplementation added assert for such kind operation, as this PR shows we
try to do increment in reorder-bb.
Thus, I added fibonacci_heap::replace_key method that can increment key (it
deletes the node and new key
is associated with the node).
The patch can bootstrap on x86_64-linux-pc and no new regression was introduced.
I would like to ask someone if the increase operation for bb-reorder is valid
or not?
Can you verify that the implementation is correct? I tend to remember that I
introduced the
lazy incerementation to inliner both for perofrmance and correctness reasons. I
used to get
odd orders when keys was increased.
Honza
Hello.
What kind of correctness do you mean? Old implementation didn't support
increment operation and the fact was hushed up.
Martin
Thanks,
Martin
gcc/ChangeLog:
2014-11-20 Martin Liska
* bb-reorder.c (find_traces_1_round): decreate_key is replaced
with replace_key method.
* fibonacci_heap.h (fibonacci_heap::insert): New argument.
(fibonacci_heap::replace_key_data): Likewise.
(fibonacci_heap::replace_key): New method that can even increment key,
this operation costs O(log N).
(fibonacci_heap::extract_min): New argument.
(fibonacci_heap::delete_node): Likewise.
diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
index 689d7b6..b568114 100644
--- a/gcc/bb-reorder.c
+++ b/gcc/bb-reorder.c
@@ -644,7 +644,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type
count_th,
(long) bbd[e->dest->index].node->get_key (),
key);
}
- bbd[e->dest->index].heap->decrease_key
+ bbd[e->dest->index].heap->replace_key
(bbd[e->dest->index].node, key);
}
}
@@ -812,7 +812,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type
count_th,
e->dest->index,
(long) bbd[e->dest->index].node->get_key (),
key);
}
- bbd[e->dest->index].heap->decrease_key
+ bbd[e->dest->index].heap->replace_key
(bbd[e->dest->index].node, key);
}
}
diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
index ecb92f8..3fce370 100644
--- a/gcc/fibonacci_heap.h
+++ b/gcc/fibonacci_heap.h
@@ -183,20 +183,27 @@ public:
}
/* For given NODE, set new KEY value. */
- K decrease_key (fibonacci_node_t *node, K key)
+ K replace_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, decrease value to new KEY. */
+ K decrease_key (fibonacci_node_t *node, K key)
+ {
+gcc_assert (key <= node->m_key);
+return replace_key (node, key);
+ }
+
/* 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 ();
+ /* Extract minimum node in the heap. If RELEASE is specified,
+ memory is released. */
+ V *extract_min (bool release = true);
/* Return value associated with minimum node in the heap. */
V *min ()
@@ -214,12 +221,15 @@ public:
}
/* Delete NODE in the heap. */
- V *delete_node (fibonacci_node_t *node);
+ V *delete_node (fibonacci_node_t *node, bool release = true);
/* Union the heap with HEAPB. */
fibonacci_heap *union_with (fibonacci_heap *heapb);
private:
+ /* Insert new NODE given by KEY and DATA associated with the key. */
+ fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
+
/* Insert it into the root list. */
void insert_root (fibonacci_node_t *node);
@@ -322,6 +332,15 @@ fibonacci_heap::insert (K key, V *data)
/* Create the new node. */
fibonacci_node *node = new fibonacci_node_t ();
+ return insert (node, key, data);
+}
+
+/* Insert new NODE given by KEY and DATA associated with the key. */
+
+template
+fibonacci_node*
+fibonacci_heap::insert (fibonacci_node_t *node, K key, V *data)
+{
/* Set the node's data. */
node->m_data = data;
node->m_key = key;
@@ -345,17 +364,22 @@ V*
fibonacci_heap::replace_key_data (fibonacci_node *node, K key,
V *data)
{
Re: [PATCH] PR lto/63968: 175.vpr from cpu2000 fails to build with LTO
> Hello.
>
> As I reimplemented fibheap to C++ template, Honza told me that replace_key
> method actually
> supports just decrement operation. Old implementation suppress any feedback
> if we try to increase key:
>
> fibheap.c:
> ...
> /* 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;
> ...
>
> My reimplementation added assert for such kind operation, as this PR shows we
> try to do increment in reorder-bb.
> Thus, I added fibonacci_heap::replace_key method that can increment key (it
> deletes the node and new key
> is associated with the node).
>
> The patch can bootstrap on x86_64-linux-pc and no new regression was
> introduced.
> I would like to ask someone if the increase operation for bb-reorder is valid
> or not?
Can you verify that the implementation is correct? I tend to remember that I
introduced the
lazy incerementation to inliner both for perofrmance and correctness reasons. I
used to get
odd orders when keys was increased.
Honza
>
> Thanks,
> Martin
> gcc/ChangeLog:
>
> 2014-11-20 Martin Liska
>
> * bb-reorder.c (find_traces_1_round): decreate_key is replaced
> with replace_key method.
> * fibonacci_heap.h (fibonacci_heap::insert): New argument.
> (fibonacci_heap::replace_key_data): Likewise.
> (fibonacci_heap::replace_key): New method that can even increment key,
> this operation costs O(log N).
> (fibonacci_heap::extract_min): New argument.
> (fibonacci_heap::delete_node): Likewise.
> diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
> index 689d7b6..b568114 100644
> --- a/gcc/bb-reorder.c
> +++ b/gcc/bb-reorder.c
> @@ -644,7 +644,7 @@ find_traces_1_round (int branch_th, int exec_th,
> gcov_type count_th,
> (long) bbd[e->dest->index].node->get_key (),
> key);
> }
> - bbd[e->dest->index].heap->decrease_key
> + bbd[e->dest->index].heap->replace_key
> (bbd[e->dest->index].node, key);
> }
> }
> @@ -812,7 +812,7 @@ find_traces_1_round (int branch_th, int exec_th,
> gcov_type count_th,
> e->dest->index,
> (long) bbd[e->dest->index].node->get_key (),
> key);
> }
> - bbd[e->dest->index].heap->decrease_key
> + bbd[e->dest->index].heap->replace_key
> (bbd[e->dest->index].node, key);
> }
> }
> diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
> index ecb92f8..3fce370 100644
> --- a/gcc/fibonacci_heap.h
> +++ b/gcc/fibonacci_heap.h
> @@ -183,20 +183,27 @@ public:
>}
>
>/* For given NODE, set new KEY value. */
> - K decrease_key (fibonacci_node_t *node, K key)
> + K replace_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, decrease value to new KEY. */
> + K decrease_key (fibonacci_node_t *node, K key)
> + {
> +gcc_assert (key <= node->m_key);
> +return replace_key (node, key);
> + }
> +
>/* 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 ();
> + /* Extract minimum node in the heap. If RELEASE is specified,
> + memory is released. */
> + V *extract_min (bool release = true);
>
>/* Return value associated with minimum node in the heap. */
>V *min ()
> @@ -214,12 +221,15 @@ public:
>}
>
>/* Delete NODE in the heap. */
> - V *delete_node (fibonacci_node_t *node);
> + V *delete_node (fibonacci_node_t *node, bool release = true);
>
>/* Union the heap with HEAPB. */
>fibonacci_heap *union_with (fibonacci_heap *heapb);
>
> private:
> + /* Insert new NODE given by KEY and DATA associated with the key. */
> + fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
> +
>/* Insert it into the root list. */
>void insert_root (fibonacci_node_t *node);
>
> @@ -322,6 +332,15 @@ fibonacci_heap::insert (K key, V *data)
>/* Create the new node. */
>fibonacci_node *node = new fibonacci_node_t ();
>
> + return insert (node, key, data);
> +}
> +
> +/* Insert new NODE given by KEY and DATA associated with the key. */
> +
> +template
> +fibonacci_node*
> +fibonacci_heap::insert (fibonacci_node_t *node, K key, V *data)
> +{
>/* Set the node's data. */
>node->m_data = data;
>node->m_key = key;
> @@ -345,17 +364,22 @@ V*
> fibonacci_heap::replace_key_data (fibonacci_node *node, K key,
>
[PATCH] PR lto/63968: 175.vpr from cpu2000 fails to build with LTO
Hello.
As I reimplemented fibheap to C++ template, Honza told me that replace_key
method actually
supports just decrement operation. Old implementation suppress any feedback if
we try to increase key:
fibheap.c:
...
/* 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;
...
My reimplementation added assert for such kind operation, as this PR shows we
try to do increment in reorder-bb.
Thus, I added fibonacci_heap::replace_key method that can increment key (it
deletes the node and new key
is associated with the node).
The patch can bootstrap on x86_64-linux-pc and no new regression was introduced.
I would like to ask someone if the increase operation for bb-reorder is valid
or not?
Thanks,
Martin
gcc/ChangeLog:
2014-11-20 Martin Liska
* bb-reorder.c (find_traces_1_round): decreate_key is replaced
with replace_key method.
* fibonacci_heap.h (fibonacci_heap::insert): New argument.
(fibonacci_heap::replace_key_data): Likewise.
(fibonacci_heap::replace_key): New method that can even increment key,
this operation costs O(log N).
(fibonacci_heap::extract_min): New argument.
(fibonacci_heap::delete_node): Likewise.
diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c
index 689d7b6..b568114 100644
--- a/gcc/bb-reorder.c
+++ b/gcc/bb-reorder.c
@@ -644,7 +644,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
(long) bbd[e->dest->index].node->get_key (),
key);
}
- bbd[e->dest->index].heap->decrease_key
+ bbd[e->dest->index].heap->replace_key
(bbd[e->dest->index].node, key);
}
}
@@ -812,7 +812,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
e->dest->index,
(long) bbd[e->dest->index].node->get_key (), key);
}
- bbd[e->dest->index].heap->decrease_key
+ bbd[e->dest->index].heap->replace_key
(bbd[e->dest->index].node, key);
}
}
diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
index ecb92f8..3fce370 100644
--- a/gcc/fibonacci_heap.h
+++ b/gcc/fibonacci_heap.h
@@ -183,20 +183,27 @@ public:
}
/* For given NODE, set new KEY value. */
- K decrease_key (fibonacci_node_t *node, K key)
+ K replace_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, decrease value to new KEY. */
+ K decrease_key (fibonacci_node_t *node, K key)
+ {
+gcc_assert (key <= node->m_key);
+return replace_key (node, key);
+ }
+
/* 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 ();
+ /* Extract minimum node in the heap. If RELEASE is specified,
+ memory is released. */
+ V *extract_min (bool release = true);
/* Return value associated with minimum node in the heap. */
V *min ()
@@ -214,12 +221,15 @@ public:
}
/* Delete NODE in the heap. */
- V *delete_node (fibonacci_node_t *node);
+ V *delete_node (fibonacci_node_t *node, bool release = true);
/* Union the heap with HEAPB. */
fibonacci_heap *union_with (fibonacci_heap *heapb);
private:
+ /* Insert new NODE given by KEY and DATA associated with the key. */
+ fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
+
/* Insert it into the root list. */
void insert_root (fibonacci_node_t *node);
@@ -322,6 +332,15 @@ fibonacci_heap::insert (K key, V *data)
/* Create the new node. */
fibonacci_node *node = new fibonacci_node_t ();
+ return insert (node, key, data);
+}
+
+/* Insert new NODE given by KEY and DATA associated with the key. */
+
+template
+fibonacci_node*
+fibonacci_heap::insert (fibonacci_node_t *node, K key, V *data)
+{
/* Set the node's data. */
node->m_data = data;
node->m_key = key;
@@ -345,17 +364,22 @@ V*
fibonacci_heap::replace_key_data (fibonacci_node *node, K key,
V *data)
{
- V *odata;
K okey;
fibonacci_node *y;
+ V *odata = node->m_data;
- /* 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 we wanted to, we do a real increase by redeleting and
+ inserting. */
if (node->compare_data (key) > 0)
-return NULL;
+{
+ delete_node (node, false);
+
+ node = new (node) fibonacci_node_t ();
+ insert (node, key, data);
+
+ return odata;
+}
- odata = node->m_data;
okey = node->m_key;
node->m_data = data;
node->m_key = key;
@@ -385,7 +409,7 @@ fibonacci_heap::replace_key_data (fibonacci_node *node, K key,
/
