[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #1 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-08-24 21:32:34 UTC ---
Created attachment 25096
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25096
Profile data for grd2c.fppized.f

[Bug tree-optimization/50183] New: ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

             Bug #: 50183
           Summary: ICE in verify_ssa for 416.gamess when optimizing using
                    profile data
    Classification: Unclassified
           Product: gcc
           Version: 4.6.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: wschmidt@gcc.gnu.org
                CC: bergner@gcc.gnu.org
              Host: powerpc64-linux
            Target: powerpc64-linux
             Build: powerpc64-linux


Created attachment 25095
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=25095
Test case

The following occurs on powerpc64-linux in gcc-4_6-branch and
ibm/gcc-4_6-branch, but not on trunk.  The options listed are the minimum
required to exhibit the bug.  The full test case is attached, together with the
profile data.  Because profile data contains location information, reducing the
test case isn't practical.


> /home/wschmidt/gcc/install/gcc-4_6-branch/libexec/gcc/powerpc64-linux/4.6.2/f951 -O3 -fprofile-use -ffast-math -floop-interchange grd2c.fppized.f
grd2c.fppized.f:1105.21:

         CALL JKGNMV(GNM,NUMG*NROOTS*3,NMAX,MMAX,                       
                     1
Warning: Type mismatch in argument 'gnm' at (1); passed REAL(8) to REAL(4)
grd2c.fppized.f:1116.21:

         CALL JKXYZV(GIJKL,GIJKL,GNKL,GNKL,GNKL,GNM,GNM,                
                     1
Warning: Type mismatch in argument 'gijkl' at (1); passed REAL(8) to REAL(4)
grd2c.fppized.f:1129.21:

         CALL JDXYZV(GIJKL,GIJKL,GIJKL,GIJKL,GIJKL,GIJKL,GIJKL,GIJKL,   
                     1
Warning: Type mismatch in argument 'gi' at (1); passed REAL(8) to REAL(4)
grd2c.fppized.f:1150.33:

         CALL DSPDFV(NUMG,NROOTS,IJKLG,GINT,FINT,SINT,GIJKL,            
                                 1
Warning: Rank mismatch in argument 'ijklg' at (1) (scalar and rank-2)
 jkdout jkdinv dspdfv dspdfs jkdzer jdxyzv jdxyzs jkxyzv spec_jkxyzs jkgnmv
jkgnms jkbcdf jkwrys jkdspd jkxyzs
Analyzing compilation unit
Performing interprocedural optimizations
 <*free_lang_data> <visibility> <early_local_cleanups> {GC 5613k -> 3437k} {GC
5396k -> 4027k} <tree_profile_ipa> <increase_alignment> <whole-program>
<ipa-profile> <cp> <inline> <pure-const> <static-var>Assembling functions:
 jkdout
grd2c.fppized.f: In function ‘jkdout’:
grd2c.fppized.f:784:0: error: missing definition
for SSA_NAME: err2.395_561 in statement:
err2_lsm.820_574 = PHI <err2.395_561(73)>
PHI argument
err2.395_561
for PHI node
err2_lsm.820_574 = PHI <err2.395_561(73)>
grd2c.fppized.f:784:0: internal compiler error: verify_ssa failed
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |spop at gcc dot gnu.org

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-25 07:19:09 UTC ---
Does it reproduce without -floop-interchange?

I bet it's graphite producing invalid SSA, but it doesn't verify it.  Apply

Index: gcc/tree-ssa-loop.c
===================================================================
--- gcc/tree-ssa-loop.c (revision 177782)
+++ gcc/tree-ssa-loop.c (working copy)
@@ -308,7 +308,8 @@ struct gimple_opt_pass pass_graphite_tra
   0,                                   /* properties_provided */
   0,                                   /* properties_destroyed */
   0,                                   /* todo_flags_start */
-  TODO_dump_func                       /* todo_flags_finish */
+  TODO_dump_func
+  | TODO_verify_ssa | TODO_verify_stmts /* todo_flags_finish */
  }
 };

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #3 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-08-25 13:39:54 UTC ---
Thanks.  -floop-interchange is required to cause the problem, and
graphite_transforms was in the stack at the time of the verify failure.  I
believe there was an explicit call to verify_ssa in there somewhere rather than
a TODO.  I took a priority interrupt at that point and haven't had time yet to
dig deeper.

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #4 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-08-25 21:02:02 UTC ---
Here's the backtrace from the failure.

(gdb) bt
#0  internal_error (gmsgid=0x10e73c80 "verify_ssa failed") at
/home/wschmidt/gcc/gcc-4_6-branch/gcc/diagnostic.c:838
#1  0x000000001071b964 in verify_ssa (check_modified_stmt=<value optimized
out>) at /home/wschmidt/gcc/gcc-4_6-branch/gcc/tree-ssa.c:1119
#2  0x00000000106b44e4 in verify_loop_closed_ssa (verify_ssa_p=<value optimized
out>) at /home/wschmidt/gcc/gcc-4_6-branch/gcc/tree-ssa-loop-manip.c:456
#3  0x0000000010a56adc in rewrite_commutative_reductions_out_of_ssa
(scop=0x116311a0) at
/home/wschmidt/gcc/gcc-4_6-branch/gcc/graphite-sese-to-poly.c:3218
#4  build_poly_scop (scop=0x116311a0) at
/home/wschmidt/gcc/gcc-4_6-branch/gcc/graphite-sese-to-poly.c:3281
#5  0x0000000010a39110 in graphite_transform_loops () at
/home/wschmidt/gcc/gcc-4_6-branch/gcc/graphite.c:272
#6  0x00000000106bf3d8 in graphite_transforms () at
/home/wschmidt/gcc/gcc-4_6-branch/gcc/tree-ssa-loop.c:256
#7  0x00000000104dddf8 in execute_one_pass (pass=0x11132640) at
/home/wschmidt/gcc/gcc-4_6-branch/gcc/passes.c:1556

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #5 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-08-30 21:07:03 UTC ---
Here's the relevant gimple following 103t.copyprop5:

==========================================================================

<bb 39>:
  err2 = 0.0;
  err2_lsm.820_567 = err2;

<bb 40>:
  # n_33 = PHI <1(39), n_223(44)>
  # err2_lsm.820_313 = PHI <err2_lsm.820_567(39), err2_lsm.820_573(44)>
  D.6172_213 = (integer(kind=8)) n_33;
  D.6219_214 = D.6172_213 * 12;

<bb 41>:
  # m_27 = PHI <1(40), m_221(42)>
  # err2_lsm.820_353 = PHI <err2_lsm.820_313(40), err2.395_219(42)>
  D.6218_212 = (integer(kind=8)) m_27;
  D.6220_215 = D.6218_212 + D.6219_214;
  D.6221_216 = D.6220_215 + -13;
  D.6242_217 = s[D.6221_216];
  err2.395_219 = D.6242_217 + err2_lsm.820_353;
  m_221 = m_27 + 1;
  if (m_27 == 12)
    goto <bb 43>;
  else
    goto <bb 42>;

<bb 42>:
  goto <bb 41>;

<bb 43>:
  # err2.395_561 = PHI <err2.395_219(41)>
  # err2_lsm.820_573 = PHI <err2.395_219(41)>
  n_223 = n_33 + 1;
  if (n_33 == 12)
    goto <bb 45>;
  else
    goto <bb 44>;

<bb 44>:
  goto <bb 40>;

<bb 45>:
  # err2.395_571 = PHI <err2.395_561(43)>
  # err2_lsm.820_574 = PHI <err2_lsm.820_573(43)>
  err2 = err2_lsm.820_574;
  D.6247_225 = ABS_EXPR <err2.395_571>;
  if (D.6247_225 >
1.00000000000000003643219731549774157916554706559963960899e-10)
    goto <bb 46>;
  else
    goto <bb 54>;

==========================================================================

At the time of the verify_ssa failure, this has been changed to:

==========================================================================

<bb 39>:

<bb 74>:
  # .MEM_352 = VDEF <.MEM_351>
  err2 = 0.0;
  # VUSE <.MEM_352>
  err2_lsm.820_567 = err2;
  # .MEM_170 = VDEF <.MEM_352>
  Commutative_Associative_Reduction.822[0] = err2_lsm.820_567;

<bb 40>:
  # n_33 = PHI <1(74), n_223(44)>
  # .MEM_291 = PHI <.MEM_170(74), .MEM_575(44)>
  D.6172_213 = (integer(kind=8)) n_33;
  D.6219_214 = D.6172_213 * 12;

<bb 41>:
  # m_27 = PHI <1(40), m_221(42)>
  # .MEM_292 = PHI <.MEM_291(40), .MEM_575(42)>
  # VUSE <.MEM_292>
  err2_lsm.820_353 = Commutative_Associative_Reduction.822[0];
  D.6218_212 = (integer(kind=8)) m_27;
  D.6220_215 = D.6218_212 + D.6219_214;
  D.6221_216 = D.6220_215 + -13;
  # VUSE <.MEM_292>
  D.6242_217 = s[D.6221_216];
  err2.395_219 = D.6242_217 + err2_lsm.820_353;
  # .MEM_575 = VDEF <.MEM_292>
  Commutative_Associative_Reduction.822[0] = err2.395_219;
  m_221 = m_27 + 1;
  if (m_27 == 12)
    goto <bb 43>;
  else
    goto <bb 42>;

<bb 42>:
  goto <bb 41>;

<bb 43>:

<bb 73>:
  n_223 = n_33 + 1;
  if (n_33 == 12)
    goto <bb 45>;
  else
    goto <bb 44>;

<bb 44>:
  goto <bb 40>;

<bb 45>:
  # err2_lsm.820_574 = PHI <err2.395_561(73)>
  # VUSE <.MEM_575>
  D.6815_562 = Commutative_Associative_Reduction.822[0];
  err2.395_571 = D.6815_562;

<bb 72>:
  # .MEM_569 = VDEF <.MEM_575>
  err2 = err2_lsm.820_574;
  D.6247_225 = ABS_EXPR <err2.395_571>;
  if (D.6247_225 >
1.00000000000000003643219731549774157916554706559963960899e-10)
    goto <bb 46>;
  else
    goto <bb 54>;

==========================================================================

The PHI in block 45 is left without a definition.

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #6 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-09-01 21:41:19 UTC ---
This PHI:

<bb 43>:
  # err2.395_561 = PHI <err2.395_219(41)>

is removed by the second call to remove_phi in
translate_scalar_reduction_to_array (graphite-sese-to-poly.c).  There appears
to be an implicit assumption in remove_phi that the PHI result is only used in
debug statements.  This is not the case here because of the immediate use:

<bb 45>:
  # err2.395_571 = PHI <err2.395_561(43)>

I don't know anything about the graphite code, so it's not clear to me whether
the existence of this immediate use should have kept this from being a
candidate for transformation, or whether remove_phi needs additional logic.  My
guess is the former.

At this point I think we need a domain expert to look into this one...

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #7 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-09-12 19:18:07 UTC ---
Slogging through the code, it appears to me that the code added in block 45 to
define err2.395_571:

  D.6815_562 = Commutative_Associative_Reduction.822[0];
  err2.395_571 = D.6815_562;

...should have instead been added in block 43 to define err2.395_561.  The
removal of the close_phi would then have been correct.  I'll step through the
code to see where the wrong phi is getting selected for this.

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #8 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-09-12 20:15:59 UTC ---
Previous comment is incorrect.  The statement:

  # err2.395_571 = PHI <err2.395_561(43)>

is the close_phi for the outer loop, while:

  # err2.395_561 = PHI <err2.395_219(41)>

is the close_phi for the inner loop.  Deleting the second one is fine under the
assumption that the first one will become dead code after an assignment to
err2.395_571 is introduced following it.  However, somewhere along the way the
LHS of the first one was replaced, and that assumption no longer holds. 
Continuing to dig.

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #9 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-09-13 15:24:08 UTC ---
OK, the problem appears to originate earlier, sometime during
canonicalize_loop_closed_ssa_form ().  After canonicalization, we have:

<bb 45>:
  # err2.395_571 = PHI <err2.395_561(73)>
  # err2_lsm.820_574 = PHI <err2.395_561(73)>

This violates the last documented condition of canonicalized loop-closed SSA
form:

/* Converts the current loop closed SSA form to a canonical form
   expected by the Graphite code generation.

   The loop closed SSA form has the following invariant: a variable
   defined in a loop that is used outside the loop appears only in the
   phi nodes in the destination of the loop exit.  These phi nodes are
   called close phi nodes.

   The canonical loop closed SSA form contains the extra invariants:

   - when the loop contains only one exit, the close phi nodes contain
   only one argument.  That implies that the basic block that contains
   the close phi nodes has only one predecessor, that is a basic block
   in the loop.

   - the basic block containing the close phi nodes does not contain
   other statements.

   - there exist only one phi node per definition in the loop.
*/

The definition of err2.395_561 in block 43 reaches both of these PHIs. 
Furthermore, the PHIs indicate the definition is in the newly introduced block
73, which is not the case:

<bb 43>:
  # err2.395_561 = PHI <err2.395_219(41)>

<bb 73>:
  n_223 = n_33 + 1;
  if (n_33 == 12)
    goto <bb 45>;
  else
    goto <bb 44>;

I'll dig into the canonicalization code to see what's going on.

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

--- Comment #10 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-09-13 16:40:05 UTC ---
The problem arises during canonicalization in the presence of nested loops. 
Loops are processed outward-in.  When each loop is processed, its single exit
edge's destination block is cleansed of duplicate close-phis.  The problem in
this case is that subsequent processing of the inner loop reintroduces
duplicate close-phis that are not then cleansed.

Specifically, block 43 contains the close-phis for the inner loop, and block 45
contains the close-phis for the outer loop:

<bb 43>:
  # err2.395_561 = PHI <err2.395_219(41)>
  # err2_lsm.820_573 = PHI <err2.395_219(41)>

...

<bb 45>:
  # err2.395_571 = PHI <err2.395_561(43)>
  # err2_lsm.820_574 = PHI <err2_lsm.820_573(43)>

...

When the outer loop is processed, the two close-phis are not duplicates (they
have different phi-arguments).  When the inner loop is processed, the two
close-phis are found to be duplicates.  The first is chosen as the
representative.  All immediate uses of err2_lsm.820_573 are replaced with uses
of err2.395_561, and the second phi in block 43 is removed.

The result is that block 45 now contains two duplicate close-phis.

I believe this can be easily fixed by checking whether a replaced immediate use
is itself a PHI statement with a single argument (a close-phi).  If so,
make_close_phi_nodes_unique () should be called again for the block containing
the replaced use.

I'll experiment with this.

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2011-09-13
         AssignedTo|unassigned at gcc dot       |wschmidt at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #11 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-09-13 17:19:56 UTC ---
Tentative fix resolves this problem.  I'll regtest and publish a patch.

[Bug tree-optimization/50183] ICE in verify_ssa for 416.gamess when optimizing using profile data

[wschmidt at gcc dot gnu.org]

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

William J. Schmidt <wschmidt at gcc dot gnu.org> changed:

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

--- Comment #12 from William J. Schmidt <wschmidt at gcc dot gnu.org> 2011-09-29 14:15:30 UTC ---
2011-09-29  Bill Schmidt  <wschmidt@linux.vnet.ibm.com>

    * graphite-scop-detection.c (make_close_phi_nodes_unique):  New
    forward declaration.
    (remove_duplicate_close_phi): Detect and repair creation of
    duplicate close-phis for a containing loop.

Fixed in rev 179351 (trunk), 179352 (4_6-branch), 179353 (ibm-4_6-branch).