Built-in analysis fails to converge on simple loops

[ymand]

A number of (likely-related) simple loops cause the analysis to fail to converge. Below are a series of examples reduced from real code. I suspect they are all the same problem:

TEST(PointerNullabilityTest, NonConvergeBools1) {
  EXPECT_TRUE(checkDiagnostics(R"cc(
    bool cond();
    void target() {
      bool a = false;
      bool b = cond();
      while (!a || !b) {
        if (!cond()) return;
        if (cond()) {
          if (a) return;
          a = cond();
        } else {
          if (b) return;
          b = true;
        }
      }
    }
  )cc"));
}

TEST(PointerNullabilityTest, NonConvergeBools2) {
  EXPECT_TRUE(checkDiagnostics(R"cc(
    bool cond();
    void target() {
      bool c = false;
      while (cond() || cond()) {
        c = (3 == 4);
      }
    }
  )cc"));
}

TEST(PointerNullabilityTest, NonConvergeBools3) {
  EXPECT_TRUE(checkDiagnostics(R"cc(
    bool cond();
    void target() {
      if (cond())
        ;
      while (cond() || cond())
        ;
    }
  )cc"));
}

TEST(PointerNullabilityTest, NonConvergeBools4) {
  EXPECT_TRUE(checkDiagnostics(R"cc(
    bool cond();

    void target(int m, int n, bool b) {
      bool g = m == 0 ;
      while (cond() || cond() || g) {
        bool c = m == 0 ;
        g = false;
      }
    }
  )cc"));
}

[martinboehme]

I believe the issue here is that the atomic bool produced for cond() doesn't get widened away. Here's why:

• We don't produce a BoolValue for the cond() call (because, in general, we don't produce Values for CallExprs)
• In TerminatorVisitor::extendFlowCondition(), we notice that we don't have a BoolValue and therefore produce a fresh atomic for it
• This atomic doesn't get widened away because TerminatorVisitor::extendFlowCondition() happens after the widening has already happened.

(I think we discussed this F2F a while ago.)

I have a draft patch lying around that moves the creation of the atomic to within transferCFGBlock(), so that the widening can widen it away. At the time, it wasn't clear whether this was actually needed, which is why I haven't submitted the patch yet, but I think this means I should pick it up again.

[ymand]

Thanks! Yes, I very much remember that discussion, but it didn't occur to me as the cause. Good catch! The patch would be very much appreciated.

[martinboehme]

Turns out I was wrong -- the fix I talked about above doesn't fix this issue.

Instead, the problem is that for a loop condition like while (cond() || cond()), we can reach the loop body without going through the loop head, and we therefore don't perform any widening.

Here's a screenshot of an example in the HTML visualizer:

Some notes:

• B5 is the block containing the first cond().
• B4 is the block containing the second cond(). It is considered the loop head, as its terminator is the while statement that consumes the loop condition.
• B3 is the loop body.
• B4, the loop head, converges, but this doesn't help us because there is an edge from B5 directly to B3, and neither of these blocks converges (because we don't perform widening after B5).

What is the solution here? I'm not sure, but I think we need to perform widening in more places. When we've got a short-circuited loop condition as in this case, we would need to perform widening after each of the blocks that can short-circuit the loop condition.

[ymand]

Nice diagnosis! I think we can widen based on an incoming back edge. In this case, that would mean in B5 we see an incoming edge from B2, and always apply the widening there. Also, small optimization: since we're already moving widening to before the block, we can detect the backedge while iterating through the block predecessors. So, it won't even cost an extra iteration over block predecessors.