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
>
>From 24cd47f44e9958bd7fd0c40af849cedc567d6341 Mon Sep 17 00:00:00 2001
From: marxin <mli...@suse.cz>
Date: Thu, 4 Aug 2016 12:34:08 +0200
Subject: [PATCH] gcov tool: Implement Hawick's algorithm for cycle detection,
(PR gcov-profile/67992)
gcc/ChangeLog:
2016-08-04 Martin Liska <mli...@suse.cz>
Joshua Cranmer <pidgeo...@gmail.com>
* gcov.c (line_t::has_block): New function.
(enum loop_type): New enum.
(handle_cycle): New function.
(unblock): Likewise.
(circuit): Likewise.
(get_cycles_count): Likewise.
(accumulate_line_counts): Use new loop detection algorithm.
---
gcc/gcov.c | 290 ++++++++++++++++++++++++++++++++++++++++---------------------
1 file changed, 189 insertions(+), 101 deletions(-)
diff --git a/gcc/gcov.c b/gcc/gcov.c
index 40701a1..9c9eccf 100644
--- a/gcc/gcov.c
+++ b/gcc/gcov.c
@@ -41,6 +41,11 @@ along with Gcov; see the file COPYING3. If not see
#include <getopt.h>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
#define IN_GCOV 1
#include "gcov-io.h"
#include "gcov-io.c"
@@ -222,6 +227,9 @@ typedef struct coverage_info
typedef struct line_info
{
+ /* Return true when NEEDLE is one of basic blocks the line belongs to. */
+ bool has_block (block_t *needle);
+
gcov_type count; /* execution count */
union
{
@@ -235,6 +243,16 @@ typedef struct line_info
unsigned unexceptional : 1;
} line_t;
+bool
+line_t::has_block (block_t *needle)
+{
+ for (block_t *n = u.blocks; n; n = n->chain)
+ if (n == needle)
+ return true;
+
+ return false;
+}
+
/* Describes a file mentioned in the block graph. Contains an array
of line info. */
@@ -407,6 +425,167 @@ static void release_structures (void);
static void release_function (function_t *);
extern int main (int, char **);
+/* Cycle detection!
+ There are a bajillion algorithms that do this. Boost's function is named
+ hawick_cycles, so I used the algorithm by K. A. Hawick and H. A. James in
+ "Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs"
+ (url at <http://complexity.massey.ac.nz/cstn/013/cstn-013.pdf>).
+
+ The basic algorithm is simple: effectively, we're finding all simple paths
+ in a subgraph (that shrinks every iteration). Duplicates are filtered by
+ "blocking" a path when a node is added to the path (this also prevents non-
+ simple paths)--the node is unblocked only when it participates in a cycle.
+ */
+
+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. Returns type of loop. */
+
+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. */
+ int64_t cycle_count = INT64_MAX;
+ for (unsigned i = 0; i < edges.size (); i++)
+ {
+ int64_t ecount = edges[i]->cs_count;
+ if (cycle_count > ecount)
+ cycle_count = ecount;
+ }
+ count += cycle_count;
+ for (unsigned i = 0; i < edges.size (); i++)
+ edges[i]->cs_count -= cycle_count;
+
+ 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 (const block_t *u, block_vector_t &blocked,
+ vector<block_vector_t > &block_lists)
+{
+ 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 (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++)
+ unblock (u, blocked, block_lists);
+
+ block_lists.erase (block_lists.begin () + index);
+}
+
+/* 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.
+ Returns what type of loop it contains. */
+
+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)
+{
+ 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 (block_vector_t ());
+
+ for (arc_t *arc = v->succ; arc; arc = arc->succ_next)
+ {
+ block_t *w = arc->dst;
+ if (w < start || !linfo.has_block (w))
+ continue;
+
+ path.push_back (arc);
+ if (w == start)
+ {
+ /* Cycle has been found. */
+ loop_type cresult = handle_cycle (path, count);
+ if (cresult > result)
+ result = cresult;
+ }
+ else if (find (blocked.begin (), blocked.end (), w) == blocked.end ())
+ {
+ loop_type cresult = circuit (w, path, start, blocked, block_lists,
+ linfo, count);
+ if (cresult > result)
+ result = cresult;
+ }
+
+ path.pop_back ();
+ }
+
+ if (result != NO_LOOP)
+ unblock (v, blocked, block_lists);
+ else
+ for (arc_t *arc = v->succ; arc; arc = arc->succ_next)
+ {
+ block_t *w = arc->dst;
+ if (w < start || !linfo.has_block (w))
+ continue;
+
+ size_t index
+ = find (blocked.begin (), blocked.end (), w) - blocked.begin ();
+ gcc_assert (index < blocked.size ());
+ block_vector_t &list = block_lists[index];
+ if (find (list.begin (), list.end (), v) == list.end ())
+ list.push_back (v);
+ }
+
+ return result;
+}
+
+/* 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
+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
+ (except for reducing counts, but that shouldn't matter anyways).
+ 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)
+ {
+ 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);
+
+ return count;
+}
+
int
main (int argc, char **argv)
{
@@ -2201,113 +2380,22 @@ accumulate_line_counts (source_t *src)
arc_t *arc;
for (arc = block->pred; arc; arc = arc->pred_next)
- {
- if (arc->src->u.cycle.ident != ix)
- count += arc->count;
- if (flag_branches)
- add_branch_counts (&src->coverage, arc);
- }
-
- /* Initialize the cs_count. */
- for (arc = block->succ; arc; arc = arc->succ_next)
- arc->cs_count = arc->count;
+ if (flag_branches)
+ add_branch_counts (&src->coverage, arc);
}
- /* Find the loops. This uses the algorithm described in
- Tiernan 'An Efficient Search Algorithm to Find the
- Elementary Circuits of a Graph', CACM Dec 1970. We hold
- the P array by having each block point to the arc that
- connects to the previous block. The H array is implicitly
- held because of the arc ordering, and the block's
- previous arc pointer.
-
- Although the algorithm is O(N^3) for highly connected
- graphs, at worst we'll have O(N^2), as most blocks have
- only one or two exits. Most graphs will be small.
-
- For each loop we find, locate the arc with the smallest
- transition count, and add that to the cumulative
- count. Decrease flow over the cycle and remove the arc
- from consideration. */
+ /* Cycle detection. */
for (block = line->u.blocks; block; block = block->chain)
{
- block_t *head = block;
- arc_t *arc;
-
- next_vertex:;
- arc = head->succ;
- current_vertex:;
- while (arc)
- {
- block_t *dst = arc->dst;
- if (/* Already used that arc. */
- arc->cycle
- /* Not to same graph, or before first vertex. */
- || dst->u.cycle.ident != ix
- /* Already in path. */
- || dst->u.cycle.arc)
- {
- arc = arc->succ_next;
- continue;
- }
-
- if (dst == block)
- {
- /* Found a closing arc. */
- gcov_type cycle_count = arc->cs_count;
- arc_t *cycle_arc = arc;
- arc_t *probe_arc;
-
- /* Locate the smallest arc count of the loop. */
- for (dst = head; (probe_arc = dst->u.cycle.arc);
- dst = probe_arc->src)
- if (cycle_count > probe_arc->cs_count)
- {
- cycle_count = probe_arc->cs_count;
- cycle_arc = probe_arc;
- }
-
- count += cycle_count;
- cycle_arc->cycle = 1;
-
- /* Remove the flow from the cycle. */
- arc->cs_count -= cycle_count;
- for (dst = head; (probe_arc = dst->u.cycle.arc);
- dst = probe_arc->src)
- probe_arc->cs_count -= cycle_count;
-
- /* Unwind to the cyclic arc. */
- while (head != cycle_arc->src)
- {
- arc = head->u.cycle.arc;
- head->u.cycle.arc = NULL;
- head = arc->src;
- }
- /* Move on. */
- arc = arc->succ_next;
- continue;
- }
-
- /* Add new block to chain. */
- dst->u.cycle.arc = arc;
- head = dst;
- goto next_vertex;
- }
- /* We could not add another vertex to the path. Remove
- the last vertex from the list. */
- arc = head->u.cycle.arc;
- if (arc)
- {
- /* It was not the first vertex. Move onto next arc. */
- head->u.cycle.arc = NULL;
- head = arc->src;
- arc = arc->succ_next;
- goto current_vertex;
- }
- /* Mark this block as unusable. */
- block->u.cycle.ident = ~0U;
+ for (arc_t *arc = block->pred; arc; arc = arc->pred_next)
+ if (!line->has_block (arc->src))
+ count += arc->count;
+ for (arc_t *arc = block->succ; arc; arc = arc->succ_next)
+ arc->cs_count = arc->count;
}
+ /* Now, add the count of loops entirely on this line. */
+ count += get_cycles_count (*line);
line->count = count;
}
--
2.9.2
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;
}
