From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-bugs-return-477299-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 6872 invoked by alias); 15 Feb 2015 09:31:38 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Received: (qmail 6839 invoked by uid 48); 15 Feb 2015 09:31:33 -0000
From: "amker at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/65068] New: Improve rewriting for address type induction variables in IVOPT
Date: Sun, 15 Feb 2015 09:31:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: amker at gcc dot gnu.org
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter
Message-ID: <bug-65068-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-02/txt/msg01632.txt.bz2

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.