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

[Martin LiÅka <mliska at suse dot cz>]

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

Attachment: PR63968.changelog
Description: Text document

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<K,V>::insert (K key, V *data)
   /* Create the new node.  */
   fibonacci_node<K,V> *node = new fibonacci_node_t ();
 
+  return insert (node, key, data);
+}
+
+/* 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 (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<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
 				       V *data)
 {
-  V *odata;
   K okey;
   fibonacci_node<K,V> *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<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
 /* Extract minimum node in the heap.  */
 template<class K, class V>
 V*
-fibonacci_heap<K,V>::extract_min ()
+fibonacci_heap<K,V>::extract_min (bool release)
 {
   fibonacci_node<K,V> *z;
   V *ret = NULL;
@@ -397,28 +421,30 @@ fibonacci_heap<K,V>::extract_min ()
        node's data.  */
       z = extract_minimum_node ();
       ret = z->m_data;
-      delete (z);
+
+      if (release)
+        delete (z);
     }
 
   return ret;
 }
 
-/* Delete NODE in the heap.  */
+/* Delete NODE in the heap, if RELEASE is specified memory is released.  */
 
 template<class K, class V>
 V*
-fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node)
+fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
 {
   V *ret = node->m_data;
 
   /* To perform delete, we just make it the min key, and extract.  */
-  decrease_key (node, m_global_min_key);
+  replace_key (node, m_global_min_key);
   if (node != m_min)
     {
       fprintf (stderr, "Can't force minimum on fibheap.\n");
       abort ();
     }
-  extract_min ();
+  extract_min (release);
 
   return ret;
 }