[PATCH] PR middle-end/38857: ICE in selective scheduler

[Alexander Monakov <amonakov at ispras dot ru>]

Hi,

PR38857 shows an assert failure in selective scheduler.  Here's an
explanation, slightly reworded from bugzilla version:

In order to avoid cost of re-initialization of various structures when
scheduling an instruction (which is generally removing original instruction(s)
and issuing a copy at the scheduling fence), scheduler tries to move an
instruction from its original location to the scheduling fence by
adjusting its PREV_INSN/NEXT_INSN links, like Haifa scheduler does.  This is not
always possible, because selective scheduler supports instruction
transformations.

The assert that fails is checking whether the instruction that we are going to
insert into insn stream at scheduling fence was actually disconnected from
stream somewhere below and its associated structures are already initialized.
The conditions to decide whether it is appropriate to move an instruction are
different at the points when original instruction is found and when an
instruction has to be issued at the scheduling fence, because different
scheduler data is available there.  The testcase gives an example when these
conditions do not agree.

Proposed patch changes it so that decision is made at instruction's original
location and saved until we issue it at the scheduling boundary in should_move
parameter and by setting uid field of struct moveop_static_params to -1.

Bootstrapped & regtested on ia64-linux.  OK for trunk?

As Steven Bosscher noted in audit trail, patch contains unrelated changes.
They are:
	* sel-sched.c (count_occurrences_1): Check that *cur_rtx is a hard
	register.
	(code_motion_process_successors): Do not call after_merge_succs
	callback if original expression was not found when traversing any of
	the branches.
	(code_motion_path_driver): Change return type.  Update prototype.

As above changes are minor, I hope they can go in with the PR fix.  The patch
was also bootstrapped/regtested without these changes.

gcc/ChangeLog:

2009-01-25  Andrey Belevantsev  <abel@ispras.ru>

	PR middle-end/38857
	* sel-sched.c (count_occurrences_1): Check that *cur_rtx is a hard
	register.
	(move_exprs_to_boundary): Change return type and pass through
	should_move from move_op.  Relax assert.  Update usage ...
	(schedule_expr_on_boundary): ... here.  Use should_move instead of
	cant_move.
	(move_op_orig_expr_found): Indicate that insn was disconnected from
	stream.
	(code_motion_process_successors): Do not call after_merge_succs
	callback if original expression was not found when traversing any of
	the branches.
	(code_motion_path_driver): Change return type.  Update prototype.
	(move_op): Update comment.  Add a new parameter (should_move).  Update
	prototype.  Set *should_move based on indication provided by
	move_op_orig_expr_found.

gcc/testsute/ChangeLog:

2009-01-25  Andrey Belevantsev  <abel@ispras.ru>
	    Steve Ellcey  <sje@cup.hp.com>

	PR middle-end/38857
	* gcc.c-torture/compile/pr38857.c: New test.

Index: sel-sched.c
===================================================================
--- sel-sched.c (revision 143664)
+++ sel-sched.c (working copy)
@@ -562,9 +562,9 @@ static rtx get_dest_from_orig_ops (av_se
 static basic_block generate_bookkeeping_insn (expr_t, edge, edge);
 static bool find_used_regs (insn_t, av_set_t, regset, struct reg_rename *, 
                             def_list_t *);
-static bool move_op (insn_t, av_set_t, expr_t, rtx, expr_t);
-static bool code_motion_path_driver (insn_t, av_set_t, ilist_t,
-                                     cmpd_local_params_p, void *);
+static bool move_op (insn_t, av_set_t, expr_t, rtx, expr_t, bool*);
+static int code_motion_path_driver (insn_t, av_set_t, ilist_t,
+                                    cmpd_local_params_p, void *);
 static void sel_sched_region_1 (void);
 static void sel_sched_region_2 (int);
 static av_set_t compute_av_set_inside_bb (insn_t, ilist_t, int, bool);
@@ -819,6 +819,7 @@ count_occurrences_1 (rtx *cur_rtx, void 
     {
       /* Bail out if we occupy more than one register.  */
       if (REG_P (*cur_rtx)
+          && HARD_REGISTER_P (*cur_rtx)
           && hard_regno_nregs[REGNO(*cur_rtx)][GET_MODE (*cur_rtx)] > 1)
         {
           p->n = 0;
@@ -4947,11 +4948,11 @@ prepare_place_to_insert (bnd_t bnd)
 
 /* Find original instructions for EXPR_SEQ and move it to BND boundary.  
    Return the expression to emit in C_EXPR.  */
-static void
+static bool
 move_exprs_to_boundary (bnd_t bnd, expr_t expr_vliw, 
                         av_set_t expr_seq, expr_t c_expr)
 {
-  bool b;
+  bool b, should_move;
   unsigned book_uid;
   bitmap_iterator bi;
   int n_bookkeeping_copies_before_moveop;
@@ -4966,11 +4967,11 @@ move_exprs_to_boundary (bnd_t bnd, expr_
   bitmap_clear (current_originators);
 
   b = move_op (BND_TO (bnd), expr_seq, expr_vliw, 
-               get_dest_from_orig_ops (expr_seq), c_expr);
+               get_dest_from_orig_ops (expr_seq), c_expr, &should_move);
 
   /* We should be able to find the expression we've chosen for 
      scheduling.  */
-  gcc_assert (b == 1);
+  gcc_assert (b);
   
   if (stat_bookkeeping_copies > n_bookkeeping_copies_before_moveop)
     stat_insns_needed_bookkeeping++;
@@ -4984,6 +4985,8 @@ move_exprs_to_boundary (bnd_t bnd, expr_
       bitmap_copy (INSN_ORIGINATORS_BY_UID (book_uid), 
                    current_originators);
     }
+
+  return should_move;
 }
 
 
@@ -5130,7 +5133,7 @@ schedule_expr_on_boundary (bnd_t bnd, ex
   expr_t c_expr = XALLOCA (expr_def);
   insn_t place_to_insert;
   insn_t insn;
-  bool cant_move;
+  bool should_move;
 
   expr_seq = find_sequential_best_exprs (bnd, expr_vliw, true);
 
@@ -5147,13 +5150,9 @@ schedule_expr_on_boundary (bnd_t bnd, ex
         move_cond_jump (insn, bnd);
     }
 
-  /* Calculate cant_move now as EXPR_WAS_RENAMED can change after move_op 
-     meaning that there was *any* renaming somewhere.  */
-  cant_move = EXPR_WAS_CHANGED (expr_vliw) || EXPR_WAS_RENAMED (expr_vliw);
-
   /* Find a place for C_EXPR to schedule.  */
   place_to_insert = prepare_place_to_insert (bnd);
-  move_exprs_to_boundary (bnd, expr_vliw, expr_seq, c_expr);
+  should_move = move_exprs_to_boundary (bnd, expr_vliw, expr_seq, c_expr);
   clear_expr (c_expr);
             
   /* Add the instruction.  The corner case to care about is when 
@@ -5166,13 +5165,13 @@ schedule_expr_on_boundary (bnd_t bnd, ex
       
       vinsn_new = vinsn_copy (EXPR_VINSN (expr_vliw), false);
       change_vinsn_in_expr (expr_vliw, vinsn_new);
-      cant_move = 1;
+      should_move = false;
     }
-  if (cant_move)
+  if (should_move)
+    insn = sel_move_insn (expr_vliw, seqno, place_to_insert);
+  else
     insn = emit_insn_from_expr_after (expr_vliw, NULL, seqno, 
                                       place_to_insert);
-  else
-    insn = sel_move_insn (expr_vliw, seqno, place_to_insert);
 
   /* Return the nops generated for preserving of data sets back
      into pool.  */
@@ -5671,6 +5670,10 @@ move_op_orig_expr_found (insn_t insn, ex
   insn_emitted = handle_emitting_transformations (insn, expr, params);
   only_disconnect = (params->uid == INSN_UID (insn)
                      && ! insn_emitted  && ! EXPR_WAS_CHANGED (expr));
+
+  /* Mark that we've disconnected an insn.  */
+  if (only_disconnect)
+    params->uid = -1;
   remove_insn_from_stream (insn, only_disconnect);
 }
 
@@ -6053,7 +6056,7 @@ code_motion_process_successors (insn_t i
 #endif
   
   /* Merge data, clean up, etc.  */
-  if (code_motion_path_driver_info->after_merge_succs)
+  if (res != -1 && code_motion_path_driver_info->after_merge_succs)
     code_motion_path_driver_info->after_merge_succs (&lparams, static_params);
 
   return res;
@@ -6081,7 +6084,7 @@ code_motion_path_driver_cleanup (av_set_
 
    Returns whether original instructions were found.  Note that top-level
    code_motion_path_driver always returns true.  */
-static bool
+static int
 code_motion_path_driver (insn_t insn, av_set_t orig_ops, ilist_t path, 
 			 cmpd_local_params_p local_params_in, 
 			 void *static_params)
@@ -6315,12 +6318,14 @@ code_motion_path_driver (insn_t insn, av
    DEST is the register chosen for scheduling the current expr.  Insert
    bookkeeping code in the join points.  EXPR_VLIW is the chosen expression,
    C_EXPR is how it looks like at the given cfg point.  
+   Write true to *SHOULD_MOVE when we have only disconnected one of 
+   insns found.
 
    Returns whether original instructions were found, which is asserted 
    to be true in the caller.  */
 static bool
 move_op (insn_t insn, av_set_t orig_ops, expr_t expr_vliw,
-         rtx dest, expr_t c_expr)
+         rtx dest, expr_t c_expr, bool *should_move)
 {
   struct moveop_static_params sparams;
   struct cmpd_local_params lparams;
@@ -6346,6 +6351,8 @@ move_op (insn_t insn, av_set_t orig_ops,
   if (sparams.was_renamed)
     EXPR_WAS_RENAMED (expr_vliw) = true;
 
+  *should_move = (sparams.uid == -1);
+
   return res;
 }
 
 Index: gcc.c-torture/compile/pr38857.c
===================================================================
--- gcc.c-torture/compile/pr38857.c   (revision 0)
+++ gcc.c-torture/compile/pr38857.c   (revision 0)
@@ -0,0 +1,22 @@
+static const int vs_total_ac_bits = 2680;
+typedef struct EncBlockInfo {
+      short mb[64];
+      unsigned char next[64];
+} EncBlockInfo;
+inline void dv_guess_qnos(EncBlockInfo* blks, int* qnos) {
+      int size[5];
+      int j, k, a, prev;
+      EncBlockInfo* b;
+      for(a=2; a==2 || vs_total_ac_bits < size[0]; a+=a){
+        for (j=0; j<6*5; j++, b++) {
+            for (k= b->next[prev]; k<64; k= b->next[k]) {
+                if(b->mb[k] < a && b->mb[k] > -a){
+                    b->next[prev] = b->next[k];
+                }
+                else{
+                    prev = k;
+                }
+            }
+        }
+     }
+}