RE: [4.5] Find more autoinc addressing for induction variables

RE: [4.5] Find more autoinc addressing for induction variables

[Rahul Kharche]

Hi,

I am trialing this patch on a private GCC port that I'm working on.
The patch works well with several test cases we have. However, fails
on the following

int
main ()
{
  const int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  int i;

  for (i = 0; i < 10; i++)
    {
      printf("arr[%d] : %d\n", i, arr[i]);
    }
}

Looking at the pass dump it seems the SSA re-scan of the symbol 'arr'
marks its use inside the loop as volatile

<bb 2>:
  arr[0] = 1;
  arr[1] = 2;
  arr[2] = 3;
  arr[3] = 4;
  arr[4] = 5;
  arr[5] = 6;
  arr[6] = 7;
  arr[7] = 8;
  arr[8] = 9;
  arr[9] = 10;
  __builtin_loop_start (1, 9);
  ivtmp.42_23 = (long unsigned int) &arr[1];

<bb 3>:
  # i_19 = PHI <i_6(4), 0(2)>
  # prephitmp.14_18 = PHI <pretmp.13_1(4), 1(2)>
  # ivtmp.42_21 = PHI <ivtmp.42_22(4), ivtmp.42_23(2)>
  __builtin_loop_iteration (1);
  printf (&"arr[%d] == var : %d\n"[0], i_19, prephitmp.14_18);
  i_6 = i_19 + 1;
  if (i_6 != 10)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  pretmp.13_1 ={v} MEM[index: ivtmp.42_21];
  ivtmp.42_22 = ivtmp.42_21 + 4;
  goto <bb 3>;

<bb 5>:
  return;


And subsequently dead code elimination removes the array initialization
completely.

<bb 2>:
  __builtin_loop_start (1, 9);
  ivtmp.42_23 = (long unsigned int) &arr[1];

<bb 3>:
  # i_19 = PHI <i_6(4), 0(2)>
  # prephitmp.14_18 = PHI <pretmp.13_1(4), 1(2)>
  # ivtmp.42_21 = PHI <ivtmp.42_22(4), ivtmp.42_23(2)>
  __builtin_loop_iteration (1);
  printf (&"arr[%d] == var : %d\n"[0], i_19, prephitmp.14_18);
  i_6 = i_19 + 1;
  if (i_6 != 10)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  pretmp.13_1 ={v} MEM[index: ivtmp.42_21];
  ivtmp.42_22 = ivtmp.42_21 + 4;
  goto <bb 3>;

<bb 5>:
  return;

}

Rahul


-----Original Message-----
From: gcc-patches-owner@gcc.gnu.org
[mailto:gcc-patches-owner@gcc.gnu.org] On Behalf Of Bernd Schmidt
Sent: 16 May 2009 01:05
To: Steven Bosscher
Cc: GCC Patches; F. Kenneth Zadeck; Zdenek Dvorak
Subject: Re: [4.5] Find more autoinc addressing for induction variables

I wrote:

> I'll see whether I can achieve a similar effect by modifying 
> tree-ssa-loop-ivopts instead.  Maybe I can add new candidates that get

> incremented in suitable basic blocks other than just the last one.

So here's a draft of what that would look like.  For every use/cand pair
for which autoinc is possible (which now requires that the use's block
is not in a nested loop, and dominates the latch), we create a new
candidate which is incremented at the point of the use, and compute its
cost without including the cost of the step.  This also gets rid of the
special handling in iv_ca_recount_cost.

That could be extended later to have candidates that are incremented
several times, e.g. to create two 16-bit postinc addressing modes for a
candidate that's incremented by 4.

Does this look like an approach that everyone can live with?


Bernd
--
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif

Re: [4.5] Find more autoinc addressing for induction variables

[Bernd Schmidt]

Hi,

Rahul Kharche wrote:
> I am trialing this patch on a private GCC port that I'm working on.
> The patch works well with several test cases we have. However, fails
> on the following
> 
> int
> main ()
> {
>   const int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
>   int i;
> 
>   for (i = 0; i < 10; i++)
>     {
>       printf("arr[%d] : %d\n", i, arr[i]);
>     }
> }

I'm not getting anything that looks like the dump you sent.  What 
version of gcc is your port based on?


Bernd
-- 
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif

RE: [4.5] Find more autoinc addressing for induction variables

[Rahul Kharche]

4.4.1, GCC 4.4 branch. Will I need dependent changes from the 4.5
branch?

Many Thanks,
Rahul


-----Original Message-----
From: Bernd Schmidt [mailto:bernds_cb1@t-online.de] 
Sent: 22 May 2009 16:56
To: Rahul Kharche
Cc: gcc@gcc.gnu.org; sdkteam-all
Subject: Re: [4.5] Find more autoinc addressing for induction variables

Hi,

Rahul Kharche wrote:
> I am trialing this patch on a private GCC port that I'm working on.
> The patch works well with several test cases we have. However, fails
> on the following
> 
> int
> main ()
> {
>   const int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
>   int i;
> 
>   for (i = 0; i < 10; i++)
>     {
>       printf("arr[%d] : %d\n", i, arr[i]);
>     }
> }

I'm not getting anything that looks like the dump you sent.  What 
version of gcc is your port based on?


Bernd
-- 
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif

RE: [4.5] Find more autoinc addressing for induction variables

[Rahul Kharche]

Hi,

Its fixed for me. I was missing get_ref_tag () in copy_ref_info () when
I patched against 4.5.

Thanks again,
Rahul

-----Original Message-----
From: Bernd Schmidt [mailto:bernds_cb1@t-online.de] 
Sent: 22 May 2009 16:56
To: Rahul Kharche
Cc: gcc@gcc.gnu.org; sdkteam-all
Subject: Re: [4.5] Find more autoinc addressing for induction variables

Hi,

Rahul Kharche wrote:
> I am trialing this patch on a private GCC port that I'm working on.
> The patch works well with several test cases we have. However, fails
> on the following
> 
> int
> main ()
> {
>   const int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
>   int i;
> 
>   for (i = 0; i < 10; i++)
>     {
>       printf("arr[%d] : %d\n", i, arr[i]);
>     }
> }

I'm not getting anything that looks like the dump you sent.  What 
version of gcc is your port based on?


Bernd
-- 
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif