@@ -1036,6 +1036,10 @@ mcdc023g (int a, int b, int c, int d, int e, int f, int g, int h, int i, int k,
x = b + c;
}
+/* Gotos, return, labels can make odd graphs. It is important that conditions
+ are assigned to the right expression, and that there are no miscounts. In
+ these tests values may be re-used, as checking things like masking an
+ independence is done in other test cases and not so useful here. */
void
mcdc024a (int a, int b)
{
@@ -1117,6 +1121,123 @@ label4:
}
}
+int
+mcdc024d (int a, int b, int c)
+{
+ /* Graphs can get complicated with the innermost returns and else-less if,
+ so we must make sure these conditions are counted correctly. */
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (c) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 1;
+ else
+ return 2;
+ }
+
+ if (a) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 3;
+ }
+
+ return 5;
+}
+
+/* Nested else-less ifs with inner returns needs to be counted right, which
+ puts some pressure on the expression isolation. The fallthrough from inner
+ expressions into the next if cause the cfg to have edges from deeper in
+ subexpression to the next block sequence, which can confuse the expression
+ isolation. */
+int
+mcdc024e (int a, int b, int c)
+{
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (c) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ if (a) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 1;
+ else
+ return 2;
+ }
+
+ if (a) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 3;
+ }
+
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ return 4;
+ }
+ return 5;
+}
+
+int
+mcdc024f (int a, int b, int c)
+{
+ if (b) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ return 0;
+
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+ b += 2;
+ if (b & 0xFF) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ c++;
+
+ return c;
+ }
+ c += 10;
+ }
+}
+
+
+int
+mcdc024g (int a, int b, int c)
+{
+ if (b) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ goto inner;
+
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ ++a;
+
+
+ if (a) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ {
+ if (b) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ {
+inner:
+ b += 2;
+ if (b & 0xFF) /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ c++;
+
+ return c;
+ }
+ c += 10;
+ }
+}
+
int main ()
{
mcdc001a (0, 1);
@@ -1313,6 +1434,10 @@ int main ()
mcdc024a (0, 0);
mcdc024b (0, 0);
mcdc024c (0, 0);
+ mcdc024d (0, 0, 0);
+ mcdc024e (0, 0, 0);
+ mcdc024f (0, 0, 0);
+ mcdc024g (0, 0, 0);
}
/* { dg-final { run-gcov conditions { --conditions gcov-19.c } } } */
@@ -5,6 +5,7 @@
jmp_buf buf;
void noop() {}
+int identity(int x) { return x; }
/* This function is a test to verify that the expression isolation does not
break on a CFG with the right set of complex edges. The (_ && setjmp)
@@ -30,10 +31,40 @@ pathological001 (int a, int b, int c)
noop ();
}
+///* Adapted from freetype-2.13.0 gxvalid/gxvmod.c classic_kern_validate */
+int
+pathological002 (int a)
+{
+ int error = identity(a);
+
+ if (error) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ goto Exit;
+
+ if (a+1) /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ {
+ noop ();
+ if (setjmp (buf)) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ noop ();
+
+ if (error) /* conditions(1/2) true(0) */
+ /* conditions(end) */
+ noop ();
+ }
+
+ error--;
+
+Exit:
+ return error;
+}
+
int
main ()
{
pathological001 (0, 1, 0);
+ pathological002 (0);
}
@@ -292,6 +292,8 @@ contract_edge (edge e)
return source;
if (block_conditional_p (dest))
return e;
+ if (dest->index == EXIT_BLOCK)
+ return source;
e = single_edge (dest->succs);
if (!e)
@@ -360,6 +362,8 @@ merge_split_outcome (basic_block b)
edge e = single_edge (b->succs);
for (edge pred : e->dest->preds)
{
+ if (!(pred->flags & EDGE_FALLTHRU))
+ return b;
if (!single (pred->src->preds))
return b;
if (!(single_edge (pred->src->preds)->flags & flag))
@@ -727,7 +731,13 @@ neighborhood (const vec<basic_block>& blocks, sbitmap G, vec<basic_block>& out)
the expression B, but the walk may include expressions from the then/else
blocks if they start with conditions. Only the subgraph B is the ancestor
of *both* the then/else outcome, which means B is the intersection of the
- ancestors of the nodes in the neighborhood N(G). */
+ ancestors of the nodes in the neighborhood N(G).
+
+ In complex graphs this may capture more than the expression proper. In that
+ case, perform the algorithm again but on the neighborhood N(B) rather than
+ N(G). Unless there is complex control flow with deep early returns, gotos
+ and else-less ifs N(B) will be the two outcome nodes, otherwise search again
+ after replacing nodes with their common dominator. */
void
isolate_expression (conds_ctx &ctx, basic_block p, vec<basic_block>& out)
{
@@ -765,6 +775,90 @@ isolate_expression (conds_ctx &ctx, basic_block p, vec<basic_block>& out)
if (bitmap_bit_p (expr, b->index))
out.safe_push (b);
out.sort (cmp_index_map, &ctx.index_map);
+
+
+ /* In a lot of programs we would be done now, but in complex CFGs with
+ gotos or returns from nested then-blocks we need some post processing.
+
+ Essentially, perform another step of the algorithm - find the
+ neighborhood NG' of the candidate expression B. If |B| == 2 we have the
+ two outcome nodes and are done. If not, we know the previous step must
+ have captured something in a nested expression (probably because of a
+ fallthrough from the then-block being merged into the next block. If
+ two nodes are dominated by some node lower (according to topsort) in the
+ CFG then the dominating node is the first term in some conditional
+ expression, which means it cannot be a part of the expression we're
+ searching for. We redo the ancestor filtering, but now use a more
+ precise neighborhood that is unaffected. */
+
+ NG.truncate (0);
+ neighborhood (out, expr, NG);
+ if (NG.length () == 2)
+ return;
+
+ /* Names are reused in this section and generally mean the same thing. */
+ bitmap_clear (reachable);
+ for (const basic_block b : NG)
+ bitmap_set_bit (reachable, b->index);
+
+ /* If a pair of nodes has a shared dominator *that is not the root*
+ then that dominator must be the first term of another boolean
+ expression or some other structure outside the expression. */
+ gcc_assert (!NG.is_empty ());
+ for (unsigned i = 0; i != NG.length () - 1; i++)
+ {
+ for (unsigned j = i+1; j != NG.length (); j++)
+ {
+ auto b = nearest_common_dominator (CDI_DOMINATORS, NG[i], NG[j]);
+ if (ctx.index_map[b->index] > ctx.index_map[p->index])
+ {
+ bitmap_clear_bit (reachable, NG[i]->index);
+ bitmap_clear_bit (reachable, NG[j]->index);
+ bitmap_set_bit (reachable, b->index);
+ }
+ }
+ }
+
+ NG.truncate (0);
+ for (basic_block b : G)
+ if (bitmap_bit_p (reachable, b->index))
+ NG.safe_push (b);
+
+ bitmap_copy (reachable, expr);
+ for (const basic_block neighbor : NG)
+ {
+ bitmap_clear (ancestors);
+ for (edge e : neighbor->preds)
+ {
+ /* The e edge might have been contracted past when doing the
+ first scan, so we must make sure its bit is set to not think it
+ is outside of our candidate set. */
+ bitmap_set_bit (reachable, e->src->index);
+ ancestors_of (e->src, p, reachable, ancestors);
+ }
+ bitmap_and (expr, expr, ancestors);
+ }
+
+ out.truncate (0);
+ for (const basic_block b : G)
+ if (bitmap_bit_p (expr, b->index))
+ out.safe_push (b);
+ out.sort (cmp_index_map, &ctx.index_map);
+
+ bitmap_clear (expr);
+ for (const basic_block b : out)
+ bitmap_set_bit (expr, b->index);
+
+ /* Perform a final step as a sanity check - if the neighborhood is still
+ larger than the outcome set (|NG| == 2) the graph is too complex and we
+ give up instrumentation. Any graph that exhibit this behaviour should
+ be studied as it might reveal an implementation error. */
+ NG.truncate (0);
+ neighborhood (out, expr, NG);
+ bitmap_clear (expr);
+ for (const basic_block b : NG)
+ bitmap_set_bit (expr, b->index);
+ gcc_assert (bitmap_count_bits (expr) == 2);
}
/* Emit lhs = op1 <op> op2 on edges. This emits non-atomic instructions and