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

2014-11-21 Thread Martin Liška 

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  mli...@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.



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_heapK,V::insert (K key, V *data)
/* Create the new node.  */
fibonacci_nodeK,V *node = new fibonacci_node_t ();

+  return insert (node, key, data);
+}
+
+/* Insert new NODE given by KEY and DATA associated with the key.  */
+
+templateclass K, class V
+fibonacci_nodeK,V*
+fibonacci_heapK,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_heapK,V::replace_key_data (fibonacci_nodeK,V *node, K key,

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

2014-11-21 Thread Jan Hubicka 
 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 removalinsertion.  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

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

2014-11-20 Thread 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
gcc/ChangeLog:

2014-11-20  Martin Liska  mli...@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.
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_heapK,V::insert (K key, V *data)
   /* Create the new node.  */
   fibonacci_nodeK,V *node = new fibonacci_node_t ();
 
+  return insert (node, key, data);
+}
+
+/* Insert new NODE given by KEY and DATA associated with the key.  */
+
+templateclass K, class V
+fibonacci_nodeK,V*
+fibonacci_heapK,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_heapK,V::replace_key_data (fibonacci_nodeK,V *node, K key,
    V *data)
 {
-  V *odata;
   K okey;
   fibonacci_nodeK,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_heapK,V::replace_key_data

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

2014-11-20 Thread Jan Hubicka 
 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  mli...@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.

 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_heapK,V::insert (K key, V *data)
/* Create the new node.  */
fibonacci_nodeK,V *node = new fibonacci_node_t ();
  
 +  return insert (node, key, data);
 +}
 +
 +/* Insert new NODE given by KEY and DATA associated with the key.  */
 +
 +templateclass K, class V
 +fibonacci_nodeK,V*
 +fibonacci_heapK,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_heapK,V::replace_key_data (fibonacci_nodeK,V *node, K key,
  V *data)
  {
 -  V *odata;
K okey;
fibonacci_nodeK,V *y;
 +  V *odata = node-m_data;
  
 -  /* If we wanted