[PATCH] PR lto/63968: 175.vpr from cpu2000 fails to build with LTO

[Martin Liška]

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
-------------- next part --------------
gcc/ChangeLog:

2014-11-20  Martin Liska  <mliska@suse.cz>

	* 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.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PR63968.patch
Type: text/x-patch
Size: 4757 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20141120/91ed1930/attachment.bin>