[Bug tree-optimization/66678] New: loop counter not accurately described by vrp

["vries at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66678

            Bug ID: 66678
           Summary: loop counter not accurately described by vrp
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Severity: minor
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: vries at gcc dot gnu.org
  Target Milestone: ---

consider testcase:
...
void
f (unsigned int n, unsigned int *__restrict__ a, unsigned int *__restrict__ b,
   unsigned int *__restrict__ c)
{
  unsigned int i;

  for (i = 0; i < n; ++i)
    c[i] = a[i] + b[i];
}
...

After vrp1 we have:
...
f (unsigned intD.9 nD.2874, unsigned intD.9 * restrict aD.2875, unsigned intD.9
* restrict bD.2876, unsigned intD.9 * restrict cD.2877)
{
  unsigned intD.9 iD.2880;
  long unsigned intD.10 _5;
  long unsigned intD.10 _6;
  unsigned intD.9 * _8;
  unsigned intD.9 * _10;
  unsigned intD.9 _11;
  unsigned intD.9 * _13;
  unsigned intD.9 _14;
  unsigned intD.9 _15;

;;   basic block 2, loop depth 0, count 0, freq 900, maybe hot
;;    prev block 0, next block 3, flags: (NEW, REACHABLE)
;;    pred:       ENTRY [100.0%]  (FALLTHRU,EXECUTABLE)
  goto <bb 4>;
;;    succ:       4 [100.0%]  (FALLTHRU,EXECUTABLE)

;;   basic block 3, loop depth 1, count 0, freq 9100, maybe hot
;;    prev block 2, next block 4, flags: (NEW, REACHABLE)
;;    pred:       4 [91.0%]  (TRUE_VALUE,EXECUTABLE)
  # RANGE [0, 18446744073709551615] NONZERO 4294967295
  _5 = (long unsigned intD.10) i_1;
  # RANGE [0, 18446744073709551615] NONZERO 18446744073709551612
  _6 = _5 * 4;
  # PT = { D.2900 } (nonlocal)
  _8 = c_7(D) + _6;
  # PT = { D.2898 } (nonlocal)
  _10 = a_9(D) + _6;
  # VUSE <.MEM_2>
  _11 = MEM[(unsigned intD.9 *)_10 clique 1 base 2];
  # PT = { D.2899 } (nonlocal)
  _13 = b_12(D) + _6;
  # VUSE <.MEM_2>
  _14 = MEM[(unsigned intD.9 *)_13 clique 1 base 3];
  # RANGE [0, 4294967295]
  _15 = _11 + _14;
  # .MEM_16 = VDEF <.MEM_2>
  MEM[(unsigned intD.9 *)_8 clique 1 base 1] = _15;
  # RANGE [0, 4294967295]
  i_17 = i_1 + 1;
;;    succ:       4 [100.0%]  (FALLTHRU,DFS_BACK,EXECUTABLE)

;;   basic block 4, loop depth 1, count 0, freq 10000, maybe hot
;;    prev block 3, next block 5, flags: (NEW, REACHABLE)
;;    pred:       2 [100.0%]  (FALLTHRU,EXECUTABLE)
;;                3 [100.0%]  (FALLTHRU,DFS_BACK,EXECUTABLE)
  # i_1 = PHI <0(2), i_17(3)>
  # .MEM_2 = PHI <.MEM_3(D)(2), .MEM_16(3)>
  if (i_1 < n_4(D))
    goto <bb 3>;
  else
    goto <bb 5>;
;;    succ:       3 [91.0%]  (TRUE_VALUE,EXECUTABLE)
;;                5 [9.0%]  (FALSE_VALUE,EXECUTABLE)

;;   basic block 5, loop depth 0, count 0, freq 900, maybe hot
;;    prev block 4, next block 1, flags: (NEW, REACHABLE)
;;    pred:       4 [9.0%]  (FALSE_VALUE,EXECUTABLE)
  # VUSE <.MEM_2>
  return;
;;    succ:       EXIT [100.0%] 

}
...

AFAIU:
- the loop iv i_1 has range [0, 4294967294], and 
- the loop iv increment i_17 has range [1, 4294967295]

But in the dump resulting from vrp1, i_1 has no range assigned, and i_17 has
RANGE [0, 4294967295] (which is equivalent to no range assigned).


During vrp the pass inserts an assert at the start of bb 3:
...
;;   basic block 3, loop depth 1, count 0, freq 9100, maybe hot
;;    prev block 2, next block 4, flags: (NEW, REACHABLE)
;;    pred:       4 [91.0%]  (TRUE_VALUE,EXECUTABLE)
  i_18 = ASSERT_EXPR <i_1, i_1 < n_4(D)>;
  # RANGE [0, 18446744073709551615] NONZERO 4294967295
  _5 = (long unsigned intD.10) i_18;
  # RANGE [0, 18446744073709551615] NONZERO 18446744073709551612
  _6 = _5 * 4;
  # PT = { D.2900 } (nonlocal)
  _8 = c_7(D) + _6;
  # PT = { D.2898 } (nonlocal)
  _10 = a_9(D) + _6;
  # VUSE <.MEM_2>
  _11 = MEM[(unsigned intD.9 *)_10 clique 1 base 2];
  # PT = { D.2899 } (nonlocal)
  _13 = b_12(D) + _6;
  # VUSE <.MEM_2>
  _14 = MEM[(unsigned intD.9 *)_13 clique 1 base 3];
  _15 = _11 + _14;
  # .MEM_16 = VDEF <.MEM_2>
  MEM[(unsigned intD.9 *)_8 clique 1 base 1] = _15;
  i_17 = i_18 + 1;
;;    succ:       4 [100.0%]  (FALLTHRU,DFS_BACK,EXECUTABLE)

;;   basic block 4, loop depth 1, count 0, freq 10000, maybe hot
;;    prev block 3, next block 5, flags: (NEW, REACHABLE)
;;    pred:       2 [100.0%]  (FALLTHRU,EXECUTABLE)
;;                3 [100.0%]  (FALLTHRU,DFS_BACK,EXECUTABLE)
  # i_1 = PHI <0(2), i_17(3)>
  # .MEM_2 = PHI <.MEM_3(D)(2), .MEM_16(3)>
  if (i_1 < n_4(D))
    goto <bb 3>;
  else
    goto <bb 5>;
...

When visiting the assert we get:
...
Visiting statement:
i_18 = ASSERT_EXPR <i_1, i_1 < n_4(D)>;
Intersecting
  [0, n_4(D) + 4294967295]  EQUIVALENCES: { i_1 } (1 elements)
and
  [0, 0]
to
  [0, n_4(D) + 4294967295]  EQUIVALENCES: { i_1 } (1 elements)
Found new range for i_18: [0, n_4(D) + 4294967295]
...

AFAIU, if we have no information on n_4, then range
  [0, n_4(D) + 4294967295]
is equal to 
  [0, 4294967295]

>From the assert however we can also derive a range of
  [0, 4294967294 ]
given that i_1 < n_4 and n_4 is at most 4294967295.

So, a more accurate range is
  [0, MIN (n_4(D) + 4294967295, 4294967294) ].