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
