Bug 14784 - [Tree-ssa] alias analysis deficiency
Summary: [Tree-ssa] alias analysis deficiency
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: tree-ssa
: P2 enhancement
Target Milestone: 4.3.0
Assignee: Daniel Berlin
URL: http://gcc.gnu.org/ml/gcc-patches/200...
Keywords: alias, missed-optimization, patch
: 29904 (view as bug list)
Depends on:
Blocks:
 
Reported: 2004-03-30 16:02 UTC by Zdenek Dvorak
Modified: 2006-12-13 07:37 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-12-24 20:17:29


Attachments
A testcase (47.07 KB, application/octet-stream)
2006-10-31 21:48 UTC, H.J. Lu
Details
A smaller testcase (2.11 KB, application/octet-stream)
2006-10-31 22:22 UTC, H.J. Lu
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Zdenek Dvorak 2004-03-30 16:02:59 UTC
Tree-ssa alias analysis does not take information about structure
fields into account.  Consequently head->using_obstack and bitmap_free
accesses in the following testcase are believed to alias, which prevents
further optimizations (load motion, unswitching) on tree level.

typedef struct bitmap_element_def
{
  unsigned int indx;
} bitmap_element;

typedef struct bitmap_head_def {
  bitmap_element *first;
  int using_obstack;
} bitmap_head;
typedef struct bitmap_head_def *bitmap;

bitmap_element *bitmap_free;

void foo (bitmap head, bitmap_element *elt)
{
  while (1)
    {
      if (head->using_obstack)
        bitmap_free = elt;
    }
}
Comment 1 Andrew Pinski 2004-03-30 16:08:54 UTC
Confirmed, related to bug 13761.
Comment 2 Andrew Pinski 2005-01-13 01:02:36 UTC
This is struct aliasing related so reassigning to Daniel Berlin.
Comment 3 Daniel Berlin 2005-01-20 21:38:43 UTC
You can track the plans and status for structure aliasing on the gcc wiki, at
[[Improved alias analysis]]
Comment 4 Andrew Pinski 2006-02-16 21:40:28 UTC
We get:
  # bitmap_free_7 = PHI <bitmap_free_1(4), bitmap_free_6(5)>;
<L0>:;

  # bitmap_free_1 = PHI <bitmap_free_7(3), bitmap_free_2(2)>;
<L4>:;
  #   VUSE <bitmap_free_1>;
  D.1534_4 = head_3->using_obstack;
  if (D.1534_4 != 0) goto <L1>; else goto <L0>;

<L1>:;
  #   bitmap_free_6 = V_MUST_DEF <bitmap_free_1>;
  bitmap_free = elt_5;
  goto <bb 3> (<L0>);

I cannot figure out why Daniel's recent patches did not fix this one.
Comment 5 Daniel Berlin 2006-02-17 01:04:15 UTC
Subject: Re:  [Tree-ssa] alias analysis
	deficiency

On Thu, 2006-02-16 at 21:40 +0000, pinskia at gcc dot gnu dot org wrote:
> 
> ------- Comment #4 from pinskia at gcc dot gnu dot org  2006-02-16 21:40 -------
> We get:
>   # bitmap_free_7 = PHI <bitmap_free_1(4), bitmap_free_6(5)>;
> <L0>:;
> 
>   # bitmap_free_1 = PHI <bitmap_free_7(3), bitmap_free_2(2)>;
> <L4>:;
>   #   VUSE <bitmap_free_1>;
>   D.1534_4 = head_3->using_obstack;
>   if (D.1534_4 != 0) goto <L1>; else goto <L0>;
> 
> <L1>:;
>   #   bitmap_free_6 = V_MUST_DEF <bitmap_free_1>;
>   bitmap_free = elt_5;
>   goto <bb 3> (<L0>);
> 
> I cannot figure out why Daniel's recent patches did not fix this one.

Probably the !POINTER_TYPE_P check

> 
> 

Comment 6 Zdenek Dvorak 2006-10-23 09:23:10 UTC
Patch:
http://gcc.gnu.org/ml/gcc-patches/2006-10/msg01156.html
Comment 7 Zdenek Dvorak 2006-10-24 00:12:27 UTC
Subject: Bug 14784

Author: rakdver
Date: Tue Oct 24 00:12:16 2006
New Revision: 117986

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=117986
Log:
	PR tree-optimization/14784
	* tree-flow.h (struct var_ann_d): Add is_heapvar bit.
	* tree-ssa-structalias.c (get_constraint_for,
	intra_create_variable_infos): Set is_heapvar.
	* tree-ssa-operands.c (access_can_touch_variable): Do not handle
	non-heapvar pointer variables specially.

	* gcc.dg/alias-10.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/alias-10.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-flow.h
    trunk/gcc/tree-ssa-operands.c
    trunk/gcc/tree-ssa-structalias.c

Comment 8 Andrew Pinski 2006-10-26 13:00:46 UTC
Fixed.
Comment 9 H.J. Lu 2006-10-31 14:59:56 UTC
FYI, the fix for this bug miscompiles gcc in SPEC CPU 2006 on both x86 and
x86-64.
Comment 10 H.J. Lu 2006-10-31 15:02:02 UTC
It miscompiles dwarf2out.c in gcc in SPEC CPU 2006.
Comment 11 Daniel Berlin 2006-10-31 15:05:07 UTC
Subject: Re:  [Tree-ssa] alias analysis deficiency

Details, source, etc needed.


On 31 Oct 2006 15:02:02 -0000, hjl at lucon dot org
<gcc-bugzilla@gcc.gnu.org> wrote:
>
>
> ------- Comment #10 from hjl at lucon dot org  2006-10-31 15:02 -------
> It miscompiles dwarf2out.c in gcc in SPEC CPU 2006.
>
Comment 12 H.J. Lu 2006-10-31 21:48:54 UTC
Created attachment 12521 [details]
A testcase

Here is a testcase. Both bad.s and good.s are compiled with -O2. The
difference in assembly output is

[hjl@gnu-25 xxx]$ diff -up bad.s good.s
--- bad.s       2006-10-31 13:22:44.000000000 -0800
+++ good.s      2006-10-31 13:22:44.000000000 -0800
@@ -31,14 +31,14 @@ add_fde_cfi:
        pushq   %rbx
 .LCFI2:
        movq    %rdi, %rbx
-       je      .L36
+       je      .L35
        movl    fde_table_in_use(%rip), %eax
        subl    $1, %eax
        leaq    (%rax,%rax,4), %rax
        leaq    0(,%rax,8), %rbp
        addq    fde_table(%rip), %rbp
        cmpb    $0, (%rdi)
-       je      .L37
+       je      .L36
 .L16:
        movq    8(%rbp), %rsi
        testq   %rsi, %rsi
@@ -46,7 +46,7 @@ add_fde_cfi:
        movq    %rbx, %rdi
        call    strcmp
        testl   %eax, %eax
-       je      .L38
+       je      .L20
 .L18:
        movq    %rbx, %rdi
        call    xstrdup
@@ -55,54 +55,50 @@ add_fde_cfi:
        call    new_cfi
        movq    %rbx, 16(%rax)
        movq    24(%rbp), %rdx
-       leaq    24(%rbp), %rsi
+       leaq    24(%rbp), %rcx
        movl    $4, 8(%rax)
        testq   %rdx, %rdx
-       movq    %rdx, %rcx
-       je      .L24
+       je      .L23
        .p2align 4,,7
-.L25:
-       movq    %rcx, %rsi
-       movq    (%rcx), %rcx
-       testq   %rcx, %rcx
-       jne     .L25
-.L24:
-       movq    %rax, (%rsi)
-.L21:
+.L30:
+       movq    %rdx, %rcx
+       movq    (%rdx), %rdx
        testq   %rdx, %rdx
+       jne     .L30
+.L23:
+       movq    %rax, (%rcx)
+.L20:
+       movq    24(%rbp), %rdx
        leaq    24(%rbp), %rax
-       je      .L28
+       testq   %rdx, %rdx
+       je      .L26
        .p2align 4,,7
-.L32:
+.L31:
        movq    %rdx, %rax
        movq    (%rdx), %rdx
        testq   %rdx, %rdx
-       jne     .L32
-.L28:
+       jne     .L31
+.L26:
        movq    %r12, (%rax)
        popq    %rbx
        popq    %rbp
        popq    %r12
        ret
-.L38:
-       movq    24(%rbp), %rdx
-       jmp     .L21
-.L37:
+.L36:
        call    dwarf2out_cfi_label
        movq    %rax, %rbx
-       .p2align 4,,4
        jmp     .L16
-.L36:
+.L35:
        movq    cie_cfi_head(%rip), %rax
        movl    $cie_cfi_head, %edx
        testq   %rax, %rax
        je      .L15
        .p2align 4,,7
-.L31:
+.L29:
        movq    %rax, %rdx
        movq    (%rax), %rax
        testq   %rax, %rax
-       jne     .L31
+       jne     .L29
 .L15:
        movq    %r12, (%rdx)
        popq    %rbx
@@ -220,5 +216,5 @@ add_fde_cfi:
        .uleb128 0x3
        .align 8
 .LEFDE3:
-       .ident  "GCC: (GNU) 4.3.0 20061023 (experimental) [trunk revision 117986]"
+       .ident  "GCC: (GNU) 4.3.0 20061023 (experimental) [trunk revision 117985]"
        .section        .note.GNU-stack,"",@progbits
Comment 13 H.J. Lu 2006-10-31 22:22:07 UTC
Created attachment 12522 [details]
A smaller testcase

Here is a smaller testcase.
Comment 14 Zdenek Dvorak 2006-11-13 12:37:43 UTC
Subject: Bug 14784

Author: rakdver
Date: Mon Nov 13 12:37:29 2006
New Revision: 118754

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=118754
Log:
	PR tree-optimization/29680
	* tree-ssa-operands.c (access_can_touch_variable): Revert fix for
	PR 14784.

	* gcc.dg/alias-11.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/alias-11.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-operands.c

Comment 15 Andrew Pinski 2006-11-13 13:54:32 UTC
Reopening since part of the patch was reverted.
Comment 16 Andrew Pinski 2006-11-20 02:37:08 UTC
*** Bug 29904 has been marked as a duplicate of this bug. ***
Comment 17 Zdenek Dvorak 2006-12-05 18:26:32 UTC
Subject: Bug 14784

Author: rakdver
Date: Tue Dec  5 18:26:20 2006
New Revision: 119549

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=119549
Log:
	PR tree-optimization/14784
	* tree-ssa-operands.c (access_can_touch_variable): Unrevert the fix.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-operands.c

Comment 18 Andrew Pinski 2006-12-13 07:37:33 UTC
Fixed.