[Bug tree-optimization/16913] New: [3.5] Regression in alias analysis

[Bug tree-optimization/16913] New: [3.5] Regression in alias analysis

[martin at mpa-garching dot mpg dot de]

for the following C code the current mainline produces worse code than
the current 3.4 branch. Mainline doesn't seem to recognize that the pointers
a and b may not alias.

#define N 200

void foo ( float * restrict a, float * restrict b, int n, int j)
  {
  int i;
  for( i=0; i<n; ++i )
    a[i] = (b[j+N/4] + b[j-N/4]) * 0.5f;
  }

Compiling with mainline using -O3 -fstrict-alilasing -std=c99 -S produces
the following assembler for the loop:

.L4:
	flds	(%eax)
	fadds	(%ecx)
	fmul	%st(1), %st
	fstps	(%esi,%edx,4)
	incl	%edx
	cmpl	%edx, %ebx
	jg	.L4


The current 3.4 version produces: 
.L5:
	fsts	(%ecx,%eax,4)
	incl	%eax
	cmpl	%edx, %eax
	jl	.L5

In this case, all floating point computations are hoisted out of the loop.

-- 
           Summary: [3.5] Regression in alias analysis
           Product: gcc
           Version: 3.5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: martin at mpa-garching dot mpg dot de
                CC: gcc-bugs at gcc dot gnu dot org,martin at mpa-garching
                    dot mpg dot de
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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

[Bug tree-optimization/16913] [3.5] Regression in alias analysis

[martin at mpa-garching dot mpg dot de]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |alias
      Known to fail|                            |3.5.0
      Known to work|                            |3.4.2


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

[Bug tree-optimization/16913] [3.5 Regression] restrict does not make a different

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-08-07 22:18 -------
Really this a RTL problem but this is also a missed-optimization from the tree level too.

Confirmed a regression.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2004-08-07 22:18:16
               date|                            |
            Summary|[3.5] Regression in alias   |[3.5 Regression] restrict
                   |analysis                    |does not make a different
   Target Milestone|---                         |3.5.0


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

[Bug tree-optimization/16913] [3.5 Regression] restrict does not make a different

[zhangjie at magima dot com dot cn]

------- Additional Comments From zhangjie at magima dot com dot cn  2004-08-18 03:33 -------
I'm investigating this. It seems that gcc failed to get the correct alias set
for b[j+N/4]. Current get_alias_set () uses find_base_decl () to find the base
pointer that the address pointer expression depends on. But when the pointer
expression has been gimplified, find_base_decl () cannot follow the ud chains to
find the true base pointer. My initial thought is replace find_base_decl with
something that can walk ud chains to find the true base pointer.

And When I looked tts t04.generic dump

foo (a, b, n, j)
{
  unsigned int i.0;
  unsigned int T.1;
  float * restrict T.2;
  float * restrict T.3;
  unsigned int j.4;
  unsigned int T.5;
  float * restrict T.6;
  float * restrict T.7;
  float * restrict T.8;
  float T.9;
  float * restrict T.10;
  float T.11;
  float T.12;
  float T.13;
  int i;

  i = 0;
  goto <D1042>;
  <D1041>:;
  i.0 = (unsigned int)i;
  T.1 = i.0 * 4;
  T.2 = (float * restrict)T.1;
  T.3 = T.2 + a;
  j.4 = (unsigned int)j;
  T.5 = j.4 * 4;
  T.6 = (float * restrict)T.5;
  T.7 = T.6 + b;
  T.8 = T.7 + 200B;
  T.9 = *T.8;
  j.4 = (unsigned int)j;
  T.5 = j.4 * 4;
  T.6 = (float * restrict)T.5;
  T.7 = T.6 + b;
  T.10 = T.7 - 200B;
  T.11 = *T.10;
  T.12 = T.9 + T.11;
  T.13 = T.12 * 5.0e-1;
  *T.3 = T.13;
  i = i + 1;
  <D1042>:;
  if (i < n)
    {
      goto <D1041>;
    }
  else
    {
      goto <D1043>;
    }
  <D1043>:;
}

I found it was rather weird that "T.1" was first cast to (float * restrict)
before it was added with "a". I think it's  better to directly add the index to
"a" without the cast. I asked this on the gcc mailing list with a simpler case
<http://gcc.gnu.org/ml/gcc/2004-08/msg00700.html>.

-- 


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

[Bug tree-optimization/16913] [3.5 Regression] restrict does not make a different

[martin at mpa-garching dot mpg dot de]

------- Additional Comments From martin at mpa-garching dot mpg dot de  2004-08-18 08:22 -------
BTW, the original testcase is part of a more comprehensive test given by
Arch Robison in
http://www.cuj.com/documents/s=8050/cuj9907robison/
Maybe the whole program given in Listing 1 should be added to the gcc testsuite
to see how well gcc deals with restricted pointers.
What do you think?


-- 


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

[Bug tree-optimization/16913] [3.5 Regression] restrict does not make a different

[zhangjie at magima dot com dot cn]

------- Additional Comments From zhangjie at magima dot com dot cn  2004-08-19 03:12 -------
Yeah, it should be added into testsuite. But I don't know how to add such
optimization test.

And I find it will be difficult to write something to replace find_base_decl ()
if we cast the index to pointer before add it to the base pointer. I'm thinking
how to remove the cast, but I'm not familiar with the C type system in GCC.

Could someone give some comments before I go ahead? Thanks.

-- 


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

[Bug tree-optimization/16913] [4.0 Regression] restrict does not make a different

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-11-22 07:12 -------
The way to fix this is before going out of SSA to have another HOST_WIDE_INT in INDIRECT_REF to say 
the aliasing set for that tree.
And also add this patch which looks at the use defs:
Index: alias.c
===============================================================
====
RCS file: /cvs/gcc/gcc/gcc/alias.c,v
retrieving revision 1.246
diff -u -p -r1.246 alias.c
--- alias.c     11 Nov 2004 23:08:55 -0000      1.246
+++ alias.c     22 Nov 2004 07:08:29 -0000
@@ -347,6 +347,15 @@ find_base_decl (tree t)
 
   if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
     return 0;
+    
+  if (TREE_CODE (t) == SSA_NAME)
+    {
+      d0 = SSA_NAME_DEF_STMT (t);
+      if (TREE_CODE (d0) == MODIFY_EXPR)
+       return find_base_decl (TREE_OPERAND (d0, 1));
+      else
+        return 0;
+    }
 
   /* If this is a declaration, return it.  */
   if (DECL_P (t))

Currently if I use the following optimizations I get the optimization:
-fno-tree-pre -fno-tree-loop-im -fno-tree-dominator-opts -fno-ivopts
The reason why PRE and loop-im is needed is because we would pull out the b[j] out of the loop.
the reason why dominator-opts is need is because we would combine b[j] for the INDIRECT's.
The reason why -fno-ivopts is needed is because we would change a[i] into *iv.opt


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2004-10-08 14:53:59         |2004-11-22 07:12:49
               date|                            |


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

[Bug tree-optimization/16913] [4.0 Regression] restrict does not make a difference

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-10 10:50 -------
The real problem here is that the tree alias analyses do not take full 
advantage of 'restrict'.  There are more PRs about this, and it is also *the* 
major source of regressions in a well-known commercial benchmark. 
 
But this is not fixable for GCC 4.0, it's too late for that now I think. 
 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dnovillo at gcc dot gnu dot
                   |                            |org, mark at codesourcery
                   |                            |dot com


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

[Bug tree-optimization/16913] [4.0 Regression] restrict does not make a difference

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-10 10:55 -------
Add some dependencies to other restrict-related problem reports. 

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |14187, 14192, 16306


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

[Bug tree-optimization/16913] [4.0/4.1 Regression] restrict does not make a difference

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.0                       |4.0.1


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

[Bug tree-optimization/16913] [4.0/4.1 Regression] restrict does not make a difference

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.1                       |4.0.2


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

[Bug tree-optimization/16913] [4.0/4.1 Regression] restrict does not make a difference

[mmitchel at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.0.2                       |4.0.3


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