Phantom conditions

This post is based on an interesting case NASA brought me; a small test program with a phantom condition. In the example, timed_out() is always true, which means checkout() cannot satisfy MC/DC, but let’s pretend it does something interesting. The function has one decision with two conditions, and four outcomes. Let’s measure MC/DC and confirm:

bool reset;
int count;

bool timed_out() {
     return true;
}

void checkout() {
    if (timed_out() && reset) {
        count = 0;
        reset = false;
    }
}

int main() {
    reset = true;
    count = 0;
    checkout();
    checkout();
}

$ gcc --coverage -fcondition-coverage checkout.cc -o checkout
$ ./checkout
$ gcov --conditions --stdout checkout.gcno
        -:    0:Source:checkout.cc
        -:    0:Graph:checkout.gcno
        -:    0:Data:checkout.gcda
        -:    0:Runs:1
        -:    1:bool reset;
        -:    2:int count;
        -:    3:
        2:    4:bool timed_out() {
        2:    5:    return true;
        -:    6:}
        -:    7:
        2:    8:void checkout() {
        2:    9:    if (timed_out() && reset) {
condition outcomes covered 3/4
condition  0 not covered (false)
condition outcomes covered 2/2
        1:   10:        count = 0;
        1:   11:        reset = false;
        -:   12:    }
        2:   13:}
        -:   14:
        1:   15:int main() {
        1:   16:    reset = true;
        1:   17:    count = 0;
        1:   18:    checkout();
        1:   19:    checkout();
        1:   20:}

Ok? There’s clearly just the one decision (if), but gcov reports two (the condition outcomes covered line). This is a ghost; a conditional jump we can measure with our tools which is absent from the code. The code is fine. The only thing that stands out, really, is the function call, so let’s replace it with a value. Now we get the one decision we would expect.

        2:    8:void checkout() {
        2:    9:    const bool expired = timed_out();
        2:   10:    if (expired && reset) {
condition outcomes covered 3/4
condition  0 not covered (false)
        1:   11:        count = 0;
        1:   12:        reset = false;
        -:   13:    }
        2:   14:}

The function-call-as-term obviously has an effect. Let’s also verify that it isn’t important that the function call is the first term. We swap the terms, and repeat the test, and still observe the mysterious second decision.

        2:    8:void checkout() {
        2:    9:    if (reset && timed_out()) {
condition outcomes covered 3/4
condition  1 not covered (false)
condition outcomes covered 2/2
        1:   10:        count = 0;
        1:   11:        reset = false;
        -:   12:    }
        2:   13:}

Let’s take a step back and revisit our assumptions about what it is we’re measuring and running. GCC does not actually use the source code much when it instruments for MC/DC, it mainly uses the control flow graph. This is very accurate with respect to what is executed¹, but come with some surprises in the gcov report. To be fair, this is a hard problem in gcov because it really only has source annotations to work with. To get a richer look at the report, let’s have a look at the report in zcov:

Quite interesting, indeed. Clearly, according to GCC there are two decisions here; blocks 3 through 5,6 and blocks 7 through 8,9. Blocks 3 through 5,6 has the shape we would expect from the Boolean expression, too. Note that the then/else blocks are successors of the later decision. This is a clue, another piece of the puzzle. It seems like GCC splits the decision in two; it first computes the result of timed_out() && reset, and stores it in temporary value, and jumps to the then/else after testing the temporary. The temporary is not explicit in the source, but the generated code is (rightly) attributed to the Boolean expression which the temporary is used to compute.

To confirm we can either check the assembly or dump the intermediate representation (gimple). Gimple is reasonably C-like, so we opt for that. The gimple confirms this theory; GCC uses the iftmp.1 for the “real” branch, and the mystery is solved. As to why GCC chooses to use a temporary, I simply don’t know.

$ gcc --coverage -fcondition-coverage checkout.cc -fdump-tree-gimple
void checkout ()
{
  bool retval.0;
  bool iftmp.1;

  _1 = timed_out ();
  if (_1 != 0) goto <D.2834>; else goto <D.2832>;
  <D.2834>:
  reset.2_2 = reset;
  if (reset.2_2 != 0) goto <D.2835>; else goto <D.2832>;
  <D.2835>:
  iftmp.1 = 1;
  goto <D.2833>;
  <D.2832>:
  iftmp.1 = 0;
  <D.2833>:
  retval.0 = iftmp.1;
  if (retval.0 != 0) goto <D.2836>; else goto <D.2837>;
  <D.2836>:
  count = 0;
  reset = 0;
  goto <D.2838>;
  <D.2837>:
  <D.2838>:
}

This was an interesting case and a reminder to be well aware of what we measure. At the end of the day, it is not really the source code that is executed, but a set of instructions equivalent to the semantics of the source code after a series of compiler transformations. A consequence of GCC analyzing the control flow graph to instrument for MC/DC is that sometimes other compiler details leak into the coverage, as we saw here. While the use of the temporary here is confusing, it is largely harmless. GCC still accurately measured MC/DC and require the same test vectors for full coverage. The extra one-term decision is a physical manifestation of the decision/jump in the source.

There are more details on measuring MC/DC based on control flow graphs in my paper on MC/DC in GCC. NASA gave me permission to write about this case.