[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |dcb314 at hotmail dot com

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> 2011-12-21 20:49:23 UTC ---
*** Bug 40711 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2009-09-17 09:51 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[reichelt at gcc dot gnu dot org]

------- Comment #10 from reichelt at gcc dot gnu dot org  2009-09-17 07:34 -------
Honza, can this PR be closed?


-- 

reichelt at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |reichelt at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[hjl at gcc dot gnu dot org]

------- Comment #9 from hjl at gcc dot gnu dot org  2009-07-23 17:51 -------
Subject: Bug 40676

Author: hjl
Date: Thu Jul 23 17:50:56 2009
New Revision: 150020

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=150020
Log:
2009-07-23  H.J. Lu  <hongjiu.lu@intel.com>

        Backport from mainline:
        2009-07-22  Richard Guenther  <rguenther@suse.de>

        PR c++/40799
        * g++.dg/lookup/using21.C: New testcase.

        2009-07-19  Jan Hubicka  <jh@suse.cz>

        PR tree-optimization/40676
        * gcc.c-torture/compile/pr40676.c: New testcase.

        2009-07-15  Richard Guenther  <rguenther@suse.de>

        PR middle-end/40753
        * gcc.c-torture/compile/pr40753.c: New testcase.

        2009-07-14  Dodji Seketeli  <dodji@redhat.com>

        PR debug/40705
        * g++.dg/debug/dwarf2/typedef1.C: New test.

        PR c++/40357
        * g++.dg/other/typedef3.C: New test.

        2009-07-10  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/40496
        * g++.dg/opt/pr40496.C: New testcase.

        2009-07-09  Jakub Jelinek  <jakub@redhat.com>

        PR middle-end/40692
        * gcc.c-torture/compile/pr40692.c: New test.

        2009-07-08  Jerry DeLisle  <jvdelisle@gcc.gnu.org>

        PR libfortran/40330
        PR libfortran/40662
        * gfortran.dg/fmt_cache_1.f: New test.

Added:
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/debug/dwarf2/typedef1.C
      - copied unchanged from r150018,
trunk/gcc/testsuite/g++.dg/debug/dwarf2/typedef1.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/lookup/using21.C
      - copied unchanged from r150018,
trunk/gcc/testsuite/g++.dg/lookup/using21.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/opt/pr40496.C
      - copied unchanged from r150018, trunk/gcc/testsuite/g++.dg/opt/pr40496.C
    branches/gcc-4_4-branch/gcc/testsuite/g++.dg/other/typedef3.C
      - copied unchanged from r150018,
trunk/gcc/testsuite/g++.dg/other/typedef3.C
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr40676.c
      - copied unchanged from r150018,
trunk/gcc/testsuite/gcc.c-torture/compile/pr40676.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr40692.c
      - copied unchanged from r150018,
trunk/gcc/testsuite/gcc.c-torture/compile/pr40692.c
    branches/gcc-4_4-branch/gcc/testsuite/gcc.c-torture/compile/pr40753.c
      - copied unchanged from r150018,
trunk/gcc/testsuite/gcc.c-torture/compile/pr40753.c
    branches/gcc-4_4-branch/gcc/testsuite/gfortran.dg/fmt_cache_1.f
      - copied unchanged from r150018,
trunk/gcc/testsuite/gfortran.dg/fmt_cache_1.f
Modified:
    branches/gcc-4_4-branch/gcc/testsuite/ChangeLog


-- 


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[hubicka at gcc dot gnu dot org]

------- Comment #8 from hubicka at gcc dot gnu dot org  2009-07-19 10:27 -------
Subject: Bug 40676

Author: hubicka
Date: Sun Jul 19 10:27:07 2009
New Revision: 149789

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=149789
Log:
        PR tree-optimization/40676
        * tree-ssa-dce.c (eliminate_unnecessary_stmts): Do renaming on all
        virtual PHIs in empty BBs.

        * gcc.c-torture/compile/pr40676.c: New testcase.


Added:
    trunk/gcc/testsuite/gcc.c-torture/compile/pr40676.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-dce.c


-- 


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[hubicka at ucw dot cz]

------- Comment #7 from hubicka at ucw dot cz  2009-07-12 16:18 -------
Subject: Re:  [4.5 Regression] internal compiler error: verify_ssa error:
definition in block 5 does not dominate use in block 7

Hi,
there is interesting difficulty with this plan.

When we have something like

BB1: if (test) goto BB2 else BB3;
BB2:
BB3: A=PHI (0 from BB1, 1 from BB2)

we end up forwarding edge BB1->BB2 to BB3 resulting in wrong code
problem.  This is because how control dependency is formulated.
When visiting BB we first mark live its control dependent BBs (that
contains conditionals deciding if BB will be executed at all) and when
visiting PHI we mark control dependency BB of source BBs of edges
leading to PHI.

In this case control dependent BB2 is BB1, so we correctly mark the test
as neccesary, but we never mark BB2 as neccesary in any way.

I checked original Cytron formulation of the CD-DCE and it is not
forwarding edges of all branches, only of branches being removed just as
current mainline does.  I saw the forwarding of all branches on some
slides presenting CD-DCE but I am not sure if this can be cheaply done
correctly (one would need control dependence relation not only for BBs,
but also for edges, or implicit split edge BBs of every edge that leads
to PHI).

The following patch fixes ICE by implementing #2 from my previous comment.
Wihtout #1 we end up with some unnecesary virtuals being sent for
renaming (those virtuals that exist in otherwise empty BBs), but I doubt
it is that big deal.

I am regtesting&bootstrapping this fix.

Honza

Index: tree-ssa-dce.c
===================================================================
--- tree-ssa-dce.c      (revision 149499)
+++ tree-ssa-dce.c      (working copy)
@@ -1137,7 +1162,7 @@ eliminate_unnecessary_stmts (void)
       for (bb = ENTRY_BLOCK_PTR->next_bb; bb != EXIT_BLOCK_PTR; bb = next_bb)
        {
          next_bb = bb->next_bb;
-         if (!(bb->flags & BB_REACHABLE))
+         if (!TEST_BIT (bb_contains_live_stmts, bb->index))
            {
              for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next
(&gsi))
                if (!is_gimple_reg (gimple_phi_result (gsi_stmt (gsi))))
@@ -1159,8 +1184,11 @@ eliminate_unnecessary_stmts (void)
                    if (found)
                      mark_virtual_phi_result_for_renaming (gsi_stmt (gsi));
                  }
-             delete_basic_block (bb);
+             if (!(bb->flags & BB_REACHABLE))
+               delete_basic_block (bb);
            }
+         else
+           gcc_assert (bb->flags & BB_REACHABLE);
        }
     }
   FOR_EACH_BB (bb)


-- 


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2009-07-12 08:31 -------
Sounds sane.


-- 


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[hubicka at ucw dot cz]

------- Comment #5 from hubicka at ucw dot cz  2009-07-11 22:45 -------
Subject: Re:  [4.5 Regression] internal compiler error: verify_ssa error:
definition in block 5 does not dominate use in block 7

Thinking about this more, we change here dominance relation in
not-so-obvious way.  It is not really textbook case with presence of
both abnormal edges that might prevent forwarding consistently
everything across the empty BBs and virtual operands that may remain in
the BBs otherwise empty.

I think we need
1) forward the edges in the tree-ssa-dce itself (i.e. don't do the edge
forwarding only when control flow stmt becomes dead but for every edge
leading to dead BB that is not abnormal)
2) for empty BBs that remains in the program (only reason would be
because they are destination of abnormal edge), send all virtual PHIs
for updating since we can not be sure dominance relations are preserved.

Sounds sane?  If so, I will give it a try tomorrow.

Honza


-- 


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[hubicka at gcc dot gnu dot org]

------- Comment #4 from hubicka at gcc dot gnu dot org  2009-07-11 22:34 -------
OK,
this is interesting case.  We have:

  # BLOCK 6
  # PRED: 2 [61.0%]  (true,exec) 3 [61.0%]  (true,exec) 4 [39.0%]  (true,exec)
5 [100.0%]  (fallthru,exec)
  # D.2735_12 = PHI <0(2), 0(3), 0(4), 1(5)>
  # .MEM_21 = PHI <.MEM_22(2), .MEM_25(3), .MEM_27(4), .MEM_27(5)>
  goto <bb 8>;
  # SUCC: 8 [100.0%]  (fallthru,exec)

This block exists only because of D.2735_12 def that gets removed.  Now we 
also eliminate conditional of BB 4:

  # BLOCK 4
  # PRED: 3 [39.0%]  (false,exec)
  # .MEM_26 = VDEF <.MEM_25>
  xmsih.2_10 = f1 ();
  # .MEM_27 = VDEF <.MEM_26>
  xmsih = xmsih.2_10;
  # VUSE <.MEM_27>
  xmsih.3_11 = xmsih;
  if (xmsih.3_11 == 0)
    goto <bb 6>;
  else
    goto <bb 5>;
  # SUCC: 6 [39.0%]  (true,exec) 5 [61.0%]  (false,exec)

and redirect it to the first live post dominator, that is BB 8 skipping BB 6
that is on the way but dead since it contains dead PHI and virtual PHI ignored
for liveness.

Now everythign would go well, since BB 6 would get removed and result of its
virtual PHI would be eliminated and symbol sent for renaming by previously
discussed if (cfg_altered) code, if we didn't had the other two live
predecestors BB 2 and 3.  Those don't contain dead control flow statement and
thus does not get updated.

The BB becomes dead later during cleanup_cfg done before update_ssa and
update_ssa fails.

I see two ways to fix this:

1) Make SSA DCE to forward every control flow edge in program to first live
post dominator (this is in original formulation of program) so we can rely on
fact that code removing unreachable BB in tree-ssa-dce will handle the PHIs.
I am bit affraid that it will be difficult to handle well all the corner cases
where edges gets identified and such, but I can give it a try.
2) Move the if (cfg_altered) code into unreachable blocks removal.  Unreachable
blocks removal is run on SSA prepared for updating in other cases too, so it
would make sense.

Honza


-- 


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2009-07-09 15:50 -------
Caused by honzas CD-DCE changes.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hubicka at gcc dot gnu dot
                   |                            |org
           Priority|P3                          |P1


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2009-07-08 08:25 -------
Confirmed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-07-08 08:25:08
               date|                            |


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

[Bug tree-optimization/40676] [4.5 Regression] internal compiler error: verify_ssa error: definition in block 5 does not dominate use in block 7

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
          Component|c                           |tree-optimization
           Keywords|                            |ice-on-valid-code
            Summary|internal compiler error:    |[4.5 Regression] internal
                   |verify_ssa error: definition|compiler error: verify_ssa
                   |in block 5 does not dominate|error: definition in block 5
                   |use in block 7              |does not dominate use in
                   |                            |block 7
   Target Milestone|---                         |4.5.0


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