> 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?)
What about trying to get naming scheme consistent with rest of GCC which call those bbs and edges? I know it is hard wired into -fprofile-arcs name but it may be nice to get types more consistent. Honza > > 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
