diff mbox

gcov tool: Implement Hawick's algorithm for cycle detection, (PR gcov-profile/67992)

Message ID a8f46bfd-32ce-abfb-d544-bc4fefa28602@suse.cz
State New
Headers show

Commit Message

Martin Liška Aug. 4, 2016, 2:42 p.m. UTC 
On 08/04/2016 03:15 PM, Nathan Sidwell wrote:
> On 08/04/16 06:41, Martin Liška wrote:
>> On 08/03/2016 04:22 PM, Nathan Sidwell wrote:
>>> Martin,
>>>> As I've going through all PRs related to gcov-profile, I've noticed this PR.
>>>> Current implementation of cycle detection in gcov is very poor, leading to extreme run time
>>>> for cases like mentioned in the PR (which does not contain a cycle). Thank to Joshua, I've
>>>> grabbed his patch and removed the scaffolding (classes: Arc, Block, ...) he did. After doing that
>>>> the patch is quite subtle and fast (of course).
>>>
>>> sorry to be a pain, but could you split the patch into
>>> a) formatting changes
>>> b) the clever  bits
>>>
>>> the formatting changes can then (probably) be applied as obvious.
>>>
>>> nathan
>>
>> This is second part which is the change of loop detection algorithm.
> 
> typedefs for arc and block pointer vectors would be useful to add.  They're used in a lot of  places:
> 
> typedef vector<arc_t *> arc_vector_t;
> typedef vector<block_t *> block_vector_t;
> 
> (question, should those be  'const T *' template parms?)

const block_t works for me, arc_t doesn't:
../../gcc/gcov.c:470:27: error: assignment of member ‘arc_info::cs_count’ in read-only object
     edges[i]->cs_count -= cycle_count;


> 
> No need for vector of block vectors typedef, unless you think otherwise.
> 
> +/* Flag that drives cycle detection after a negative cycle is seen.  */
> +static bool did_negate = false;
> 
> That's ugly, and I think unnecessary.  Use +1 for loop, -1 for negated loop, 0 for no loop  (or a tri-valued enum with the right properties)
> 
> 1) have handle_cycle return +1 (not negated) or -1 (negated) appropriately.
> 
> 2) have circuit return an int similarly. Then
>   if (w == start)
>     found |= handle_cycle (path, count);
>   else if (...)
>     found |= circuit (...)
> will DTRT there
> 
> 3) finally have find_cycles merge the results from its circuit calls and determine whether to repeat itself -- rather than have the caller do it. (or have another reference parm to tell the caller?)

I decided to use a new enum, hope it's better?

Martin

> 
> nathan
>

Comments

Nathan Sidwell Aug. 4, 2016, 3:13 p.m. UTC | #1 
On 08/04/16 10:42, Martin Liška wrote:

> I decided to use a new enum, hope it's better?

that's fine.  But you know, if you set the enum values appropriately you could 
use the | trick rather than the compare you've done (c++ enum type safety would 
require an overloaded | operator though).  I don't mind either way,


+get_cycles_count (line_t &linfo, bool handle_negative_cycles = true)
...
+  for (block_t *block = linfo.u.blocks; block; block = block->chain)
+    {
+      arc_vector_t path;
+      block_vector_t blocked;
+      vector<block_vector_t > block_lists;
+      result = circuit (block, path, block, blocked, block_lists, linfo, count);
+    }
+
+  /* If we have a negative cycle, repeat the find_cycles routine.  */
+  if (result == NEGATIVE_LOOP && handle_negative_cycles)
+    count += get_cycles_count (linfo, false);

The retry will depend on the result of the final call of circuit.  Before  it 
happened if any loop was negated.  Is this change intentional?

nathan
diff mbox

Patch

diff --git a/gcc/gcov.c b/gcc/gcov.c
index f39a731..9c9eccf 100644
--- a/gcc/gcov.c
+++ b/gcc/gcov.c
@@ -437,15 +437,24 @@  extern int main (int, char **);
    simple paths)--the node is unblocked only when it participates in a cycle.
    */
 
-/* Flag that drives cycle detection after a negative cycle is seen.  */
-static bool did_negate = false;
+typedef vector<arc_t *> arc_vector_t;
+typedef vector<const block_t *> block_vector_t;
+
+/* Enum with types of loop in CFG.  */
+
+enum loop_type
+{
+  NO_LOOP,
+  LOOP,
+  NEGATIVE_LOOP
+};
 
 /* Handle cycle identified by EDGES, where the function finds minimum cs_count
    and subtract the value from all counts.  The subtracted value is added
-   to COUNT.  */
+   to COUNT.  Returns type of loop.  */
 
-static void
-handle_cycle (const vector<arc_t *> &edges, int64_t &count)
+static loop_type
+handle_cycle (const arc_vector_t &edges, int64_t &count)
 {
   /* Find the minimum edge of the cycle, and reduce all nodes in the cycle by
      that amount.  */
@@ -460,25 +469,24 @@  handle_cycle (const vector<arc_t *> &edges, int64_t &count)
   for (unsigned i = 0; i < edges.size (); i++)
     edges[i]->cs_count -= cycle_count;
 
-  if (cycle_count < 0)
-    did_negate = true;
+  return cycle_count < 0 ? NEGATIVE_LOOP : LOOP;
 }
 
 /* Unblock a block U from BLOCKED.  Apart from that, iterate all blocks
    blocked by U in BLOCK_LISTS.  */
 
 static void
-unblock (block_t *u, vector<block_t *> &blocked,
-	 vector<vector<block_t *> > &block_lists)
+unblock (const block_t *u, block_vector_t &blocked,
+	 vector<block_vector_t > &block_lists)
 {
-  vector<block_t *>::iterator it = find (blocked.begin (), blocked.end (), u);
+  block_vector_t::iterator it = find (blocked.begin (), blocked.end (), u);
   if (it == blocked.end ())
     return;
 
   unsigned index = it - blocked.begin ();
   blocked.erase (it);
 
-  for (vector<block_t *>::iterator it2 = block_lists[index].begin ();
+  for (block_vector_t::iterator it2 = block_lists[index].begin ();
        it2 != block_lists[index].end (); it2++)
     unblock (*it2, blocked, block_lists);
   for (unsigned j = 0; j < block_lists[index].size (); j++)
@@ -489,19 +497,20 @@  unblock (block_t *u, vector<block_t *> &blocked,
 
 /* Find circuit going to block V, PATH is provisional seen cycle.
    BLOCKED is vector of blocked vertices, BLOCK_LISTS contains vertices
-   blocked by a block.  COUNT is accumulated count of the current LINE.  */
+   blocked by a block.  COUNT is accumulated count of the current LINE.
+   Returns what type of loop it contains.  */
 
-static bool
-circuit (block_t *v, vector<arc_t *> &path, block_t *start,
-	 vector<block_t *> &blocked, vector<vector<block_t *>> &block_lists,
+static loop_type
+circuit (block_t *v, arc_vector_t &path, block_t *start,
+	 block_vector_t &blocked, vector<block_vector_t> &block_lists,
 	 line_t &linfo, int64_t &count)
 {
-  bool found = false;
+  loop_type result = NO_LOOP;
 
   /* Add v to the block list.  */
   gcc_assert (find (blocked.begin (), blocked.end (), v) == blocked.end ());
   blocked.push_back (v);
-  block_lists.push_back (vector<block_t *> ());
+  block_lists.push_back (block_vector_t ());
 
   for (arc_t *arc = v->succ; arc; arc = arc->succ_next)
     {
@@ -513,16 +522,22 @@  circuit (block_t *v, vector<arc_t *> &path, block_t *start,
       if (w == start)
 	{
 	  /* Cycle has been found.  */
-	  handle_cycle (path, count);
-	  found = true;
+	  loop_type cresult = handle_cycle (path, count);
+	  if (cresult > result)
+	    result = cresult;
 	}
       else if (find (blocked.begin (), blocked.end (), w) == blocked.end ())
-	found |= circuit (w, path, start, blocked, block_lists, linfo, count);
+	{
+	  loop_type cresult = circuit (w, path, start, blocked, block_lists,
+				       linfo, count);
+	  if (cresult > result)
+	    result = cresult;
+	}
 
       path.pop_back ();
     }
 
-  if (found)
+  if (result != NO_LOOP)
     unblock (v, blocked, block_lists);
   else
     for (arc_t *arc = v->succ; arc; arc = arc->succ_next)
@@ -534,18 +549,19 @@  circuit (block_t *v, vector<arc_t *> &path, block_t *start,
 	size_t index
 	  = find (blocked.begin (), blocked.end (), w) - blocked.begin ();
 	gcc_assert (index < blocked.size ());
-	vector<block_t *> &list = block_lists[index];
+	block_vector_t &list = block_lists[index];
 	if (find (list.begin (), list.end (), v) == list.end ())
 	  list.push_back (v);
       }
 
-  return found;
+  return result;
 }
 
-/* Find cycles for a LINFO.  */
+/* Find cycles for a LINFO.  If HANDLE_NEGATIVE_CYCLES is set and the line
+   contains a negative loop, then perform the same function once again.  */
 
 static gcov_type
-find_cycles (line_t &linfo)
+get_cycles_count (line_t &linfo, bool handle_negative_cycles = true)
 {
   /* Note that this algorithm works even if blocks aren't in sorted order.
      Each iteration of the circuit detection is completely independent
@@ -553,32 +569,19 @@  find_cycles (line_t &linfo)
      Therefore, operating on a permuted order (i.e., non-sorted) only
      has the effect of permuting the output cycles.  */
 
+  loop_type result = NO_LOOP;
   gcov_type count = 0;
   for (block_t *block = linfo.u.blocks; block; block = block->chain)
     {
-      vector<arc_t *> path;
-      vector<block_t *> blocked;
-      vector<vector<block_t *> > block_lists;
-      circuit (block, path, block, blocked, block_lists, linfo, count);
+      arc_vector_t path;
+      block_vector_t blocked;
+      vector<block_vector_t > block_lists;
+      result = circuit (block, path, block, blocked, block_lists, linfo, count);
     }
 
-  return count;
-}
-
-/* Get cycle count for a LINFO.  */
-
-static gcov_type
-get_cycles_count (line_t &linfo)
-{
-  gcov_type count = 0;
-
-  /* Bug compatibility with gcc's broken cycle-finder: if a negative cycle
-     exists, run the algorithm again.  */
-
-  did_negate = false;
-  count = find_cycles (linfo);
-  if (did_negate)
-    count += find_cycles (linfo);
+  /* If we have a negative cycle, repeat the find_cycles routine.  */
+  if (result == NEGATIVE_LOOP && handle_negative_cycles)
+    count += get_cycles_count (linfo, false);
 
   return count;
 }