[Bug target/26726] -fivopts producing out of bounds array refs

["ubizjak at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>]

------- Comment #18 from ubizjak at gmail dot com  2007-10-29 13:22 -------
Perhaps this analysis will help someone...:

We start with following loop:

void bar() ()
{
  unsigned int ivtmp.19;
  int pretmp.14;
  struct Foo * pretmp.13;
  struct Foo x[4];
  int D.1669;
  struct Foo * D.1668;

<bb 2>:

<bb 3>:
  # ivtmp.19_2 = PHI <ivtmp.19_1(4), 4(2)>
  # D.1669_34 = PHI <D.1669_7(4), 3(2)>
  # D.1668_33 = PHI <D.1668_6(4), &x[0](2)>
  D.1668_33->s = 1;
  D.1668_6 = D.1668_33 + 4;
  D.1669_7 = D.1669_34 + -1;
  ivtmp.19_1 = ivtmp.19_2 - 1;
  if (ivtmp.19_1 != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  goto <bb 3>;

...

General ivs in BB are found in tree-ssa-loop-ivopts.c via find_givs_in_bb().

find_givs_in_stmt() is entered with "D.1668_6 = D.1668_33 + 4". For this stmt,
find_givs_in_stmt_scev() returns iv.base = &x[1] and iv.step = 4.

Digging a bit further, find_givs_in_stmt_scev() calls simple_iv() in
tree-scalar-evolution.c() to determine iv base and step. simple_iv() is called
with op = "D.1668_33 + 4" and this op is furhter passed to
analyze_scalar_evolution_in_loop(). This function returns "{&x[1], +, 4}_1".

analyze_scalar_evolution_in_loop() calls analyze_scalar_evolution() with
"D.1668_33 + 4". This expression is further passed to
analyze_scalar_evolution_1(). As the expression is not SSA_NAME, it is passed
to interpret_rhs_modify_stmt() as POINTER_PLUS_EXPR.

interpret_rhs_modify_stmt() decomposes expression into "{&x[0], +, 4}_1" and
"4". These two are summed in chrec_fold_plus() in tree-chrec.c to the final
"{&x[1], +, 4}_1" expression.

This results in:

  struct FooD.1649 xD.1666[4];
  intD.2 D.1669;
  struct FooD.1649 * D.1668;

  ivtmp.24D.1709_11 = (unsigned intD.6) &xD.1666[1];


  # BLOCK 3 freq:8000
  ...
  MEM[index: ivtmp.24D.1709_9, offset: 0x0fffffffc]{D.1668->sD.1653} = 1;
  ivtmp.24D.1709_10 = ivtmp.24D.1709_9 + 4;
  ...

and on i686:

        leal    -12(%ebp), %eax
        leal    4(%ebp), %edx
.L2:
        movl    $1, -4(%eax)
        addl    $4, %eax
        cmpl    %edx, %eax
        jne     .L2
        ...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26726