[Bug tree-optimization/65068] New: Improve rewriting for address type induction variables in IVOPT

[amker at gcc dot gnu.org]

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

            Bug ID: 65068
           Summary: Improve rewriting for address type induction variables
                    in IVOPT
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: amker at gcc dot gnu.org

For below example
extern int listXsize[8];
void foo (int len, int list_offset)
{
  int list;
  if (list_offset < 0)
    list_offset = 0;
  else if (list_offset == 0)
    list_offset = 1;
  else
    list_offset = 2;

  for (list = 0; list < len; list++)
    listXsize[list+list_offset]++;
}

The dump after IVOPTs is as below with compiling options "-O2" on aarch64

  <bb 8>:
  # ivtmp.4_12 = PHI <0(7), ivtmp.4_3(10)>
  _2 = (sizetype) list_offset_1;
  _17 = _2 + ivtmp.4_12;
  _18 = _17 * 4;
  _8 = MEM[symbol: listXsize, index: _18, offset: 0B];
  _9 = _8 + 1;
  _19 = (sizetype) list_offset_1;
  _20 = ivtmp.4_12 + _19;
  _21 = _20 * 4;
  MEM[symbol: listXsize, index: _21, offset: 0B] = _9;
  ivtmp.4_3 = ivtmp.4_12 + 1;
  list_22 = (int) ivtmp.4_3;
  if (len_6(D) > list_22)
    goto <bb 10>;
  else
    goto <bb 9>;

  <bb 10>:
  goto <bb 8>;

The address of memory reference is in the form of 

  listXsize + (ivtmp + list_offset) * 4

It consists of two parts as below

  base: listXsize + list_offset * 4    ;; loop invariant
  step: ivtmp

But in the dump, IVOPTs rewrites it into below form

  tmp = ivtmp + list_offset
  MEM_REF[listXsize, tmp, 0];


Apparently, the loop invariant expression is split and can't be hoist out of
loop.

Moreover, IVOPTs now computes the loop invariant part of address expression in
loop and depends on the following loop-invariant pass.  Generally this works
fine except for one problem: If different address expression have common sub
expression, the shared part expression is computed multiple times.  This not
only complicates loop invariant pass, but also CSE optimization.  I see cases
in which CSE are missed.

I think the rewriting of address type induction variable should be refined to
take at lease two factors into consideration:

a) Proper re-association of loop invariant/variant expressions.
b) Share common expression making CSE easier.