[Bug tree-optimization/42245] New: ICE in verify_backedges for 197.parser with sel-sched

[Bug tree-optimization/42245] New: ICE in verify_backedges for 197.parser with sel-sched

[janis at gcc dot gnu dot org]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1841 bytes --]

GCC trunk gets an internal compiler error when building SPEC CPU2000 test
197.parser with "-O2 -fselective-scheduling -fsel-sched-pipelining" on
powerpc-linux, as demonstrated by this minimized testcase:

-----------------------------------------------------------------------
extern int N_words;
typedef struct DIS_node_struct DIS_node;
typedef struct CON_list_struct CON_list;

struct DIS_node_struct
{
  CON_list *cl;
};

void
build_DIS_CON_tree (void)
{
  int w;
  DIS_node *dnroot, *dn;
  CON_list *child, *xchild;
  for (w = 0; w < N_words; w++)
    {
      if (dnroot == ((void *) 0))
        {
          dnroot = dn;
          for (child = dn->cl; child != ((void *) 0); child = xchild)
            {
            }
        }
    }
}
-----------------------------------------------------------------------

elm3b149% /home/janis/tools/gcc-trunk-anonsvn/bin/gcc -O2
-fselective-scheduling -fsel-sched-pipelining -c bug.c
bug.c: In function ‘build_DIS_CON_tree’:
bug.c:26:1: internal compiler error: in verify_backedges, at
sel-sched-ir.c:3498
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

The failure starts with this very large patch (Expand from SSA):

    http://gcc.gnu.org/viewcvs?view=rev&rev=146817

    r146817 | matz | 2009-04-26 19:35:04 +0000 (Sun, 26 Apr 2009)


-- 
           Summary: ICE in verify_backedges for 197.parser with sel-sched
           Product: gcc
           Version: 4.5.0
            Status: UNCONFIRMED
          Keywords: ice-on-valid-code
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: janis at gcc dot gnu dot org
GCC target triplet: powerpc-linux


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

[Bug middle-end/42245] [4.5 Regression] ICE in verify_backedges for 197.parser with sel-sched

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matz at gcc dot gnu dot org
          Component|tree-optimization           |middle-end
           Priority|P3                          |P1
            Summary|ICE in verify_backedges for |[4.5 Regression] ICE in
                   |197.parser with sel-sched   |verify_backedges for
                   |                            |197.parser with sel-sched
   Target Milestone|---                         |4.5.0


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2009-12-02 12:04 -------
actually selective scheduling is new, so not a regression


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |abel at ispras dot ru
           Priority|P1                          |P3
            Summary|[4.5 Regression] ICE in     |ICE in verify_backedges for
                   |verify_backedges for        |197.parser with sel-sched
                   |197.parser with sel-sched   |
   Target Milestone|4.5.0                       |---


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[amonakov at gcc dot gnu dot org]

------- Comment #2 from amonakov at gcc dot gnu dot org  2009-12-04 18:00 -------
(In reply to comment #0)

Janis,

Thank you for the testcase.  This bug and PR42249 are fixed by Andrey's old
patch:

http://gcc.gnu.org/ml/gcc-patches/2008-09/msg01930.html

The patch in that message still applies cleanly.  I'm working on re-testing it
with current mainline.  If you could test that patch in your environment, it
would be very appreciated.


-- 

amonakov at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amonakov at gcc dot gnu dot
                   |                            |org
         AssignedTo|unassigned at gcc dot gnu   |amonakov at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-12-04 18:00:57
               date|                            |


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[abel at gcc dot gnu dot org]

------- Comment #3 from abel at gcc dot gnu dot org  2009-12-28 12:06 -------
The patch mentioned by Alexander is not enough to fix the bug after applying
all other patches for sel-sched bugs.  The actual problem is that when
redirecting an edge, the topological order of blocks in the currently
scheduling region may be broken.  I had a patch to fix this, but didn't apply
it to trunk so got beaten by it.  We will post it shortly.

        * sel-sched-ir.c (sel_redirect_edge_and_branch): Recompute
        topological order after redirecting an edge if needed.

diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index 645093a..2baa461 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -5394,6 +5394,27 @@ sel_redirect_edge_and_branch (edge e, basic_block to)
       gcc_assert (loop_latch_edge (current_loop_nest));
     }

+  /* In rare situations, the topological relation between the blocks connected
+     by the redirected edge can change.  Update block_to_bb/bb_to_block.  */
+  if (CONTAINING_RGN (e->src->index) == CONTAINING_RGN (to->index)
+      && BLOCK_TO_BB (e->src->index) > BLOCK_TO_BB (to->index))
+    {
+      int i, n, rgn;
+      int *postorder, n_blocks;
+
+      postorder = XALLOCAVEC (int, n_basic_blocks);
+      n_blocks = post_order_compute (postorder, false, false);
+
+      rgn = CONTAINING_RGN (e->src->index);
+      for (n = 0, i = n_blocks - 1; i >= 0; i--)
+        if (CONTAINING_RGN (postorder[i]) == rgn)
+          {
+            BLOCK_TO_BB (postorder[i]) = n;
+            BB_TO_BLOCK (n) = postorder[i];
+            n++;
+          }
+    }
+
   jump = find_new_jump (src, NULL, prev_max_uid);
   if (jump)
     sel_init_new_insn (jump, INSN_INIT_TODO_LUID | INSN_INIT_TODO_SIMPLEJUMP);


-- 

abel at gcc dot gnu dot org changed:

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


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[steven at gcc dot gnu dot org]

------- Comment #4 from steven at gcc dot gnu dot org  2009-12-28 12:34 -------
Re. comment #3 - do you have an example of when/how this can happen? Perhaps
you can add it to the comment.


-- 


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[amonakov at gcc dot gnu dot org]

------- Comment #5 from amonakov at gcc dot gnu dot org  2009-12-28 14:23 -------
(In reply to comment #4)
> Re. comment #3 - do you have an example of when/how this can happen? Perhaps
> you can add it to the comment.
> 

Here, we are scheduling a loop that looks like this:

      +---+
      | 4 |<--+
      +-+-+   |
        |     |
        v     |
      +---+   |
      | 5 +-+ |
      +-+-+ | |
        |   | |
        v   | |
      +---+ | |
exit<-+ 6 | | |
      +---+ | |
        |   | |
        v   | |
      +---+ | |
    +-+ 7 | | |
    | +---+ | |
    |       | |
    |       | |
    | +---+ | |
    | | 8 |<+ |
    | +-+-+   |
    |   |     |
    |   v     |
    | +---+   |
    ->| 9 +---+
      +---+

The order of blocks as given by prev_bb/next_bb corresponds to the figure, but
in rev_top_order_index BB8 goes before BB6 (which is OK since they are
topologically independent).  When BB8 becomes empty in the process of
scheduling, in the preparation to delete it we redirect BB7->BB9 branch to BB8
(essentially eliminating a now unneeded jump instruction in the end of BB7). 
The corresponding comment reads in sel-sched-ir.c reads:

/* Check if there is an unnecessary jump in previous basic block leading to
next basic block left after removing INSN from stream.  If it is so, remove
that jump and redirect edge to current basic block (where there was INSN before
deletion).  This way when NOP will be deleted several instructions later with
its basic block we will not get a jump to next instruction, which can be
harmful.  */

This makes BB6 and BB8 topologically dependent.  We then merge BB7 and BB8,
creating BB6->BB8 branch, which appears to be a backedge (since topological
order has not been recomputed).

Since the explanation is quite lengthy, we'd prefer to just leave a reference
to this PR in the comment.


-- 


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[janis at gcc dot gnu dot org]

------- Comment #6 from janis at gcc dot gnu dot org  2010-01-06 18:44 -------
With the patch at http://gcc.gnu.org/ml/gcc-patches/2009-12/msg01209.html the
testcase in the submitter's description no longer fails, but there is other
code in 197.parser that gets the same ICE with the same options.  Here's a
minimized testcase for that:

int
strictly_smaller_name (char *s, char *t)
{
  int ss, tt;
  while ((*s != '\0') || (*t != '\0'))
    {
      if (*s == '\0')
        ss = '*';
      else
        ss = *s++;
      if (*t != '\0')
        tt = *t;
      if (ss == tt)
        return 0;
    }
}

This failure occurs with and without the patch cited above.


-- 


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[amonakov at gcc dot gnu dot org]

------- Comment #7 from amonakov at gcc dot gnu dot org  2010-01-11 15:04 -------
Our previous patch (http://gcc.gnu.org/ml/gcc-patches/2009-12/msg01215.html)
failed to correctly fix the problem, and the new testcase uncovers a flaw in
that implementation.

We 'forgot' to recompute topological order if it was invalidated in
tidy_control_flow but not in maybe_tidy_empty_bb called from that function. 
Fixed by passing recompute_toporder_p to the latter on top of the mentioned
previous patch as below (the patch also makes maybe_tidy_empty_bb static by
moving the only caller into the same file).

        * sel-sched-ir.c (maybe_tidy_empty_bb): Make static.  Add new
        argument.  Update all callers.
        (purge_empty_blocks): Export and move from...
        * sel-sched.c (purge_empty_blocks): ... here.  Delete.
        * sel-sched-ir.h (maybe_tidy_empty_bb): Delete prototype.
        (purge_empty_blocks): Declare.

diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index cffee1c..e20df17 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -3538,13 +3538,13 @@ sel_recompute_toporder (void)
 }

 /* Tidy the possibly empty block BB.  */
-bool
-maybe_tidy_empty_bb (basic_block bb)
+static bool
+maybe_tidy_empty_bb (basic_block bb, bool recompute_toporder_p)
 {
   basic_block succ_bb, pred_bb;
   edge e;
   edge_iterator ei;
-  bool rescan_p, recompute_toporder_p = false;
+  bool rescan_p;

   /* Keep empty bb only if this block immediately precedes EXIT and
      has incoming non-fallthrough edge, or it has no predecessors or
@@ -3630,7 +3630,7 @@ tidy_control_flow (basic_block xbb, bool full_tidying)
   insn_t first, last;

   /* First check whether XBB is empty.  */
-  changed = maybe_tidy_empty_bb (xbb);
+  changed = maybe_tidy_empty_bb (xbb, false);
   if (changed || !full_tidying)
     return changed;

@@ -3694,7 +3694,7 @@ tidy_control_flow (basic_block xbb, bool full_tidying)
          that contained that jump, becomes empty too.  In such case
          remove it too.  */
       if (sel_bb_empty_p (xbb->prev_bb))
-        changed = maybe_tidy_empty_bb (xbb->prev_bb);
+        changed = maybe_tidy_empty_bb (xbb->prev_bb, recompute_toporder_p);
       else if (recompute_toporder_p)
        sel_recompute_toporder ();
     }
@@ -3702,6 +3702,24 @@ tidy_control_flow (basic_block xbb, bool full_tidying)
   return changed;
 }

+/* Purge meaningless empty blocks in the middle of a region.  */
+void
+purge_empty_blocks (void)
+{
+  /* Do not attempt to delete preheader.  */
+  int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
+
+  while (i < current_nr_blocks)
+    {
+      basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
+
+      if (maybe_tidy_empty_bb (b, false))
+       continue;
+
+      i++;
+    }
+}
+
 /* Rip-off INSN from the insn stream.  When ONLY_DISCONNECT is true,
    do not delete insn's data, because it will be later re-emitted.
    Return true if we have removed some blocks afterwards.  */
diff --git a/gcc/sel-sched-ir.h b/gcc/sel-sched-ir.h
index 317258c..b5121c0 100644
--- a/gcc/sel-sched-ir.h
+++ b/gcc/sel-sched-ir.h
@@ -1619,7 +1619,7 @@ extern bool tidy_control_flow (basic_block, bool);
 extern void free_bb_note_pool (void);

 extern void sel_remove_empty_bb (basic_block, bool, bool);
-extern bool maybe_tidy_empty_bb (basic_block bb);
+extern void purge_empty_blocks (void);
 extern basic_block sel_split_edge (edge);
 extern basic_block sel_create_recovery_block (insn_t);
 extern void sel_merge_blocks (basic_block, basic_block);
diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
index 37be754..9271b80 100644
--- a/gcc/sel-sched.c
+++ b/gcc/sel-sched.c
@@ -6790,24 +6790,6 @@ setup_current_loop_nest (int rgn)
   gcc_assert (LOOP_MARKED_FOR_PIPELINING_P (current_loop_nest));
 }

-/* Purge meaningless empty blocks in the middle of a region.  */
-static void
-purge_empty_blocks (void)
-{
-  /* Do not attempt to delete preheader.  */
-  int i = sel_is_loop_preheader_p (BASIC_BLOCK (BB_TO_BLOCK (0))) ? 1 : 0;
-
-  while (i < current_nr_blocks)
-    {
-      basic_block b = BASIC_BLOCK (BB_TO_BLOCK (i));
-
-      if (maybe_tidy_empty_bb (b))
-       continue;
-
-      i++;
-    }
-}
-
 /* Compute instruction priorities for current region.  */
 static void
 sel_compute_priorities (int rgn)


-- 


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[janis at gcc dot gnu dot org]

------- Comment #8 from janis at gcc dot gnu dot org  2010-01-11 22:10 -------
I bootstrapped on powerpc64-linux c,c++,fortran with the earlier big
selective-scheduling patch plus the patch in comment #7 of this PR and the
patch in comment #4 of PR42246.  The resulting GCC gets no failures for SPEC
CPU2000 using several combinations of selective-scheduling options.  Thanks for
being so responsive!


-- 


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[amonakov at gcc dot gnu dot org]

------- Comment #9 from amonakov at gcc dot gnu dot org  2010-01-14 10:29 -------
Subject: Bug 42245

Author: amonakov
Date: Thu Jan 14 10:28:47 2010
New Revision: 155890

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155890
Log:
2010-01-14  Andrey Belevantsev  <abel@ispras.ru>
            Alexander Monakov  <amonakov@ispras.ru>

        PR middle-end/42245
        * sel-sched-ir.c (sel_recompute_toporder): New.  Use it...
        (maybe_tidy_empty_bb): ... here.  Make static.  Add new
        argument.  Update all callers.
        (tidy_control_flow): ... and here.  Recompute topological order
        of basic blocks in region if necessary.
        (sel_redirect_edge_and_branch): Change return type.  Return true
        if topological order might have been invalidated.
        (purge_empty_blocks): Export and move from...
        * sel-sched.c (purge_empty_blocks): ... here.
        * sel-sched-ir.h (sel_redirect_edge_and_branch): Update prototype.
        (maybe_tidy_empty_bb): Delete prototype.
        (purge_empty_blocks): Declare.

        * gcc.dg/pr42245.c: New.
        * gcc.dg/pr42245-2.c: New.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/sel-sched-ir.c
    trunk/gcc/sel-sched-ir.h
    trunk/gcc/sel-sched.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[amonakov at gcc dot gnu dot org]

------- Comment #10 from amonakov at gcc dot gnu dot org  2010-01-14 10:38 -------
Subject: Bug 42245

Author: amonakov
Date: Thu Jan 14 10:38:14 2010
New Revision: 155891

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155891
Log:
Add tests missing from previous commit.

        PR middle-end/42245
        * gcc.dg/pr42245.c: New.
        * gcc.dg/pr42245-2.c: New.

Added:
    trunk/gcc/testsuite/gcc.dg/pr42245-2.c
    trunk/gcc/testsuite/gcc.dg/pr42245.c


-- 


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[amonakov at gcc dot gnu dot org]

------- Comment #11 from amonakov at gcc dot gnu dot org  2010-01-14 10:41 -------
Fixed by revision 155890


-- 

amonakov at gcc dot gnu dot org changed:

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


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

[Bug middle-end/42245] ICE in verify_backedges for 197.parser with sel-sched

[abel at gcc dot gnu dot org]

------- Comment #12 from abel at gcc dot gnu dot org  2010-08-24 08:57 -------
Subject: Bug 42245

Author: abel
Date: Tue Aug 24 08:57:18 2010
New Revision: 163504

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=163504
Log:
Backport from mainline:
 2010-01-14  Andrey Belevantsev  <abel@ispras.ru>
            Alexander Monakov  <amonakov@ispras.ru>

        PR middle-end/42245
        * sel-sched-ir.c (sel_recompute_toporder): New.  Use it...
        (maybe_tidy_empty_bb): ... here.  Make static.  Add new
        argument.  Update all callers.
        (tidy_control_flow): ... and here.  Recompute topological order
        of basic blocks in region if necessary.
        (sel_redirect_edge_and_branch): Change return type.  Return true
        if topological order might have been invalidated.
        (purge_empty_blocks): Export and move from...
        * sel-sched.c (purge_empty_blocks): ... here.
        * sel-sched-ir.h (sel_redirect_edge_and_branch): Update prototype.
        (maybe_tidy_empty_bb): Delete prototype.
        (purge_empty_blocks): Declare.


Modified:
    branches/gcc-4_4-branch/gcc/ChangeLog
    branches/gcc-4_4-branch/gcc/sel-sched-ir.c
    branches/gcc-4_4-branch/gcc/sel-sched-ir.h
    branches/gcc-4_4-branch/gcc/sel-sched.c
    branches/gcc-4_4-branch/gcc/testsuite/ChangeLog


-- 


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