@@ -4,6 +4,9 @@
/* some side effect to stop branches from being pruned */
int x = 0;
+int id (int x) { return x; }
+int inv (int x) { return !x; }
+
/* || works */
void
mcdc001a (int a, int b)
@@ -395,6 +398,15 @@ mcdc009a (int a, int b)
x = a--;
}
+/* Multi-term loop condition with empty body, which can give neighborhoods of
+ size 1. */
+void
+mcdc009b (int a, int b)
+{
+ while (a-- > 0 && b) {} /* conditions(2/4) true(0 1) */
+ /* conditions(end) */
+}
+
/* for loop */
void
mcdc010a (int a, int b)
@@ -537,6 +549,21 @@ mcdc015c (int a, int b)
}
}
+/* Early returns, gotos can create candidate sets where the neighborhood
+ internally shares dominator nodes that are not the first-in-expression which
+ implies the neighborhood belongs to some other boolean expression. When
+ this happens, the candidate set must be properly tidied up. */
+void
+mcdc015d (int a, int b, int c)
+{
+ if (a) return; /* conditions(1/2) false(0) */
+ /* conditions(end) */
+ if (id (b)) return; /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+ if (id (c)) return; /* conditions(0/2) true(0) false(0) */
+ /* conditions(end) */
+}
+
/* check nested loops */
void
@@ -639,9 +666,6 @@ mcdc017c (int a, int b)
} while (n-- > 0); /* conditions(2/2) */
}
-int id (int x) { return x; }
-int inv (int x) { return !x; }
-
/* collection of odd cases lifted-and-adapted from real-world code */
int mcdc018a (int a, int b, int c, int d, int e, int f, int g, int len)
{
@@ -1332,6 +1356,9 @@ int main ()
mcdc009a (0, 0);
mcdc009a (1, 1);
+ mcdc009b (0, 0);
+ mcdc009b (1, 0);
+
mcdc010a (0, 0);
mcdc010a (0, 9);
mcdc010a (2, 1);
@@ -1369,6 +1396,8 @@ int main ()
mcdc015c (0, 5);
mcdc015c (6, 1);
+ mcdc015d (1, 0, 0);
+
mcdc016a (5, 5);
mcdc016b (5, 5);
@@ -759,6 +759,10 @@ isolate_expression (conds_ctx &ctx, basic_block p, vec<basic_block>& out)
if (bitmap_count_bits (expr) == 2)
break;
+ /* This can happen for loops with no body. */
+ if (bitmap_count_bits (expr) == 1 && bb_loop_header_p (p))
+ break;
+
/* If the neighborhood does not change between iterations (a fixed
point) we cannot understand the graph properly, and this would loop
infinitely. If this should happen, we should bail out and give up
@@ -768,21 +772,32 @@ isolate_expression (conds_ctx &ctx, basic_block p, vec<basic_block>& out)
gcc_assert (false);
bitmap_copy (prev, expr);
- for (unsigned i = 0; i != NG.length () - 1; i++)
+ const unsigned NGlen = NG.length ();
+ for (unsigned i = 0; i != NGlen - 1; i++)
{
- for (unsigned j = i+1; j != NG.length (); j++)
+ for (unsigned j = i+1; j != NGlen; j++)
{
- auto b = nearest_common_dominator (CDI_DOMINATORS, NG[i], NG[j]);
+ basic_block 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);
+ bitmap_clear_bit (expr, NG[i]->index);
+ bitmap_clear_bit (expr, NG[j]->index);
+ bitmap_set_bit (expr, b->index);
+ NG.safe_push (b);
+ /* It could be that the predecessor edge from the ancestor
+ was contracted past, in which case we need to mark it to
+ make sure its ancestors_of do not immediately terminate. */
+ for (edge e : b->preds)
+ if (ctx.index_map[e->src->index] > ctx.index_map[p->index])
+ bitmap_set_bit (reachable, e->src->index);
}
}
}
- bitmap_copy (expr, reachable);
+ for (unsigned i = 0; i != NG.length (); i++)
+ if (!bitmap_bit_p (expr, NG[i]->index))
+ NG.unordered_remove (i--);
+ bitmap_copy (expr, reachable);
for (const basic_block neighbor : NG)
{
bitmap_clear (ancestors);