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

[Nathan Sidwell]

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?)

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?)

nathan