On Sun, Mar 27, 2016 at 2:58 PM, Patrick Palka <patr...@parcs.ath.cx> wrote:
> In unrolling of the inner loop in the test case below we introduce
> unreachable code that otherwise contains out-of-bounds array accesses.
> This is because the estimation of the maximum number of iterations of
> the inner loop is too conservative: we assume 6 iterations instead of
> the actual 4.
>
> Nonetheless, VRP should be able to tell that the code is unreachable so
> that it doesn't warn about it. The only thing holding VRP back is that
> it doesn't look through conditionals of the form
>
> if (j_10 != CST1) where j_10 = j_9 + CST2
>
> so that it could add the assertion
>
> j_9 != (CST1 - CST2)
>
> This patch teaches VRP to detect such conditionals and to add such
> assertions, so that it could remove instead of warn about the
> unreachable code created during loop unrolling.
>
> What this addition does with the test case below is something like this:
>
> ASSERT_EXPR (i <= 5);
> for (i = 1; i < 6; i++)
> {
> j = i - 1;
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 1)
> bar[j] = baz[j];
>
> j = i - 2
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 2)
> bar[j] = baz[j];
>
> j = i - 3
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 3)
> bar[j] = baz[j];
>
> j = i - 4
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 4)
> bar[j] = baz[j];
>
> j = i - 5
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 5)
> bar[j] = baz[j];
>
> j = i - 6
> if (j == 0)
> break;
> // ASSERT_EXPR (i != 6)
> bar[j] = baz[j]; // unreachable because (i != 6 && i <= 5) is always false
> }
Er, sorry, this illustration is wrong. First off, break; should say
continue;. Second, we actually find that the second-to-last bar[j] =
baz[j]; assignment is unreachable, since VRP can use the ASSERT_EXPRs
to determine that i == 5 when evaluating the conditional immediately
preceding the second-to-last array access. And because the
second-to-last assignment is unreachable then so is the last
assignment. So we remove two unreachable array accesses (and their
enclosing basic blocks) and thus suppress the two -Warray-bounds
warnings.
