[Bug tree-optimization/47737] New: [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[Bug tree-optimization/47737] New: [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[zsojka at seznam dot cz]

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

           Summary: [4.6 Regression] wrong code with -funswitch-loops
                    -fno-tree-dominator-opts -fgraphite-identity
           Product: gcc
           Version: 4.6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: zsojka@seznam.cz
                CC: spop@gcc.gnu.org
              Host: x86_64-pc-linux-gnu
            Target: x86_64-pc-linux-gnu


Created attachment 23339
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=23339
reduced testcase

Output:
$ gcc -v                                                     
Using built-in specs.
COLLECT_GCC=/mnt/svn/gcc-trunk/binary-latest/bin/gcc
COLLECT_LTO_WRAPPER=/mnt/svn/gcc-trunk/binary-170138-lto-fortran-checking-yes-rtl-df/libexec/gcc/x86_64-unknown-linux-gnu/4.6.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: /mnt/svn/gcc-trunk//configure --enable-checking=yes,rtl,df
--enable-languages=c,c++,lto,fortran
--prefix=/mnt/svn/gcc-trunk/binary-170138-lto-fortran-checking-yes-rtl-df/
--with-cloog --with-ppl --with-cloog-include=/usr/include/cloog-ppl/
Thread model: posix
gcc version 4.6.0 20110214 (experimental) (GCC) 

$ gcc -O -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity
testcase.c
$ ./a.out 
Aborted

Tested revisions:
r170138 - fail
4.5.2 - OK

[Bug tree-optimization/47737] [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.6.0

[Bug tree-optimization/47737] [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2011.02.17 20:40:52
                 CC|                            |law at redhat dot com
     Ever Confirmed|0                           |1

--- Comment #1 from Jeffrey A. Law <law at redhat dot com> 2011-02-17 20:40:52 UTC ---
Looks like a bug in invariant code motion.  Evaluating further.

[Bug tree-optimization/47737] [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2011-02-17 20:40:52         |
                 CC|                            |rguenther at suse dot de

--- Comment #2 from Jeffrey A. Law <law at redhat dot com> 2011-02-17 20:53:16 UTC ---
Looks like a bug in invariant code motion of PHIs related to:

http://gcc.gnu.org/ml/gcc-patches/2010-05/msg00121.html

[Bug tree-optimization/47737] [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot       |rguenther at suse dot de
                   |gnu.org                     |

--- Comment #3 from Jeffrey A. Law <law at redhat dot com> 2011-02-17 22:31:39 UTC ---
I can't see any way this code is correct:

  /* We have to verify that one edge into the PHI node is dominated
     by the true edge of the predicate block and the other edge
     dominated by the false edge.  This ensures that the PHI argument
     we are going to take is completely determined by the path we
     take from the predicate block.  */


Consider this CFG fragment.


             5
            / \
           6-->7
            \ /
             8


ie edges (5,6) (5,7) (6,7) (6,8) (7,8) 

Assume we have a PHI with two constant args in block #8 and DOM is block #5. 
Assume true_edge is (5,7) and false_edge is (5,6).

Clearly one can see that the edge (5,7) does _not_ dominate (7,8).  However,
the code in question gets it wrong.

  tem = EDGE_PRED (bb, 0);
  if (tem == true_edge
      || tem->src == true_edge->dest
      || dominated_by_p (CDI_DOMINATORS,
                         tem->src, true_edge->dest))
    arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
  else if (tem == false_edge
           || tem->src == false_edge->dest
           || dominated_by_p (CDI_DOMINATORS,
                              tem->src, false_edge->dest))
    arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
  else

Assume tem is the edge (7,8).  Obviously it is not true_edge (5,7).  However
tem->src == true_edge->dest and we record arg0 and believe we had a dominance
relationship between true_edge and tem.

Richard, how was this supposed to work?

[Bug tree-optimization/47737] [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|rguenther at suse dot de    |rguenth at gcc dot gnu.org

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-18 11:00:47 UTC ---
Looking.

[Bug tree-optimization/47737] [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-18 11:41:40 UTC ---
The code tries to use existing dominance information to answer the edge
dominance question but indeed gets it wrong by using the dest/src blocks
of the edges without verifying that doing so will not affect the dominance
check.

I am testing a fix along

Index: tree-ssa-loop-im.c
===================================================================
--- tree-ssa-loop-im.c  (revision 170249)
+++ tree-ssa-loop-im.c  (working copy)
@@ -676,31 +676,38 @@ extract_true_false_args_from_phi (basic_
      by the true edge of the predicate block and the other edge
      dominated by the false edge.  This ensures that the PHI argument
      we are going to take is completely determined by the path we
-     take from the predicate block.  */
+     take from the predicate block.
+     We can only use BB dominance checks below if the destination of
+     the true/false edges are dominated by their edge, thus only
+     have a single predecessor.  */
   extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
   tem = EDGE_PRED (bb, 0);
   if (tem == true_edge
-      || tem->src == true_edge->dest
-      || dominated_by_p (CDI_DOMINATORS,
-                        tem->src, true_edge->dest))
+      || (single_pred_p (true_edge->dest)
+         && (tem->src == true_edge->dest
+             || dominated_by_p (CDI_DOMINATORS,
+                                tem->src, true_edge->dest))))
     arg0 = PHI_ARG_DEF (phi, tem->dest_idx);

...

[Bug tree-optimization/47737] [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-18 13:22:21 UTC ---
Author: rguenth
Date: Fri Feb 18 13:22:17 2011
New Revision: 170272

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=170272
Log:
2011-02-18  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/47737
    * tree-ssa-loop-im.c (extract_true_false_args_from_phi): Fix
    edge dominance check.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-loop-im.c

[Bug tree-optimization/47737] [4.6 Regression] wrong code with -funswitch-loops -fno-tree-dominator-opts -fgraphite-identity

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-18 13:23:06 UTC ---
Fixed.