diff mbox

Scheduler tweaks relating to speculation

Message ID 4DE4DE28.20006@codesourcery.com
State New
Headers show

Commit Message

Bernd Schmidt May 31, 2011, 12:25 p.m. UTC 
I'm working on a patch to allow the scheduler to move more insns
backwards across a jump by using predication. Currently I'm using a
slightly extended form of the speculation support, adding another bit to
TODO_SPEC. The following preliminary patch makes a few changes in that
area in preparation, and also cleans up a few things:

* Remove pointless use of "*ts", replace with computing a local
  variable and storing it in TODO_SPEC when done.
* TODO_SPEC can have only three forms, either it is zero, or
  HARD_DEP, or it contains bits in SPECULATIVE (but not HARD_DEP).
  The current code sometimes goes through logical operations to
  compute a known value, HARD_DEP or zero. I found that hard to
  read and understand initially, so I've changed it.
* New function dep_spec_p which decides which of the lists a dep
  should be on.
* Allow insns to be scheduled before all their dependencies are
  resolved (i.e. don't crash when freeing the deps).
* Using that, don't delete deps for debug insns, resolve them
  instead, and remove the big pointless comment about how we're not
  freeing dependencies during scheduling. This is intended for later
  improving backtracking in the presence of debug insns.
* When not using USE_DEPS_LIST (why aren't we using it always?) or
  DO_SPECULATION, we should use zero to initialize DEP_STATUS, so
  that there aren't any bits in SPECULATIVE.

Bootstrapped and tested on i686-linux. I've also built a cross-compiler
to ia64-linux to verify that generated code is identical (using both -O2
and -O2 -fselective-scheduling -fselective-scheduling2). Ok?


Bernd
* haifa-sched.c (schedule_insns): Don't delete debug insn
	dependencies, resolve them normally.  Remove outdated comment.
	(schedule_block): When computing a known value for TODO_SPEC,
	just set it rather than using logical operations.
	(try_ready): Likewise.  Use a local variable rather than a
	pointer to TODO_SPEC.  Reorder an if statement to move the
	easy case to the then block.
	* sched-deps.c (dep_spec_p): New static function.
	(update_dep): Use it to decide whether to call
	change_spec_dep_to_hard.
	(get_back_and_forw_lists): Use it.
	(sd_resolve_dep): Likewise.
	(init_dep): If !USE_DEPS_LIST, use zero to initialize status.
	(haifa_note_mem_dep): Likewise.
	(check_dep): Likewise.
	(sd_add_dep): Also clear SPECULATIVE bits if not DO_SPECULATION.
	(sched_free_deps): Free in two passes.
diff mbox

Patch

Index: trunk/gcc/haifa-sched.c
===================================================================
--- trunk.orig/gcc/haifa-sched.c
+++ trunk/gcc/haifa-sched.c
@@ -1722,10 +1722,7 @@  schedule_insn (rtx insn)
 	  }
 	INSN_REG_USE_LIST (dbg) = NULL;
 
-	/* We delete rather than resolve these deps, otherwise we
-	   crash in sched_free_deps(), because forward deps are
-	   expected to be released before backward deps.  */
-	sd_delete_dep (sd_it);
+	sd_resolve_dep (sd_it);
       }
 
   gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
@@ -1778,18 +1775,6 @@  schedule_insn (rtx insn)
 	}
     }
 
-  /* This is the place where scheduler doesn't *basically* need backward and
-     forward dependencies for INSN anymore.  Nevertheless they are used in
-     heuristics in rank_for_schedule (), early_queue_to_ready () and in
-     some targets (e.g. rs6000).  Thus the earliest place where we *can*
-     remove dependencies is after targetm.sched.finish () call in
-     schedule_block ().  But, on the other side, the safest place to remove
-     dependencies is when we are finishing scheduling entire region.  As we
-     don't generate [many] dependencies during scheduling itself, we won't
-     need memory until beginning of next region.
-     Bottom line: Dependencies are removed for all insns in the end of
-     scheduling the region.  */
-
   /* Annotate the instruction with issue information -- TImode
      indicates that the instruction is expected not to be able
      to issue on the same cycle as the previous insn.  A machine
@@ -3217,7 +3202,7 @@  schedule_block (basic_block *target_bb)
 	    /* We normally get here only if we don't want to move
 	       insn from the split block.  */
 	    {
-	      TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP;
+	      TODO_SPEC (insn) = HARD_DEP;
 	      goto restart_choose_ready;
 	    }
 
@@ -3292,7 +3277,7 @@  schedule_block (basic_block *target_bb)
 
 	  x = ready_element (&ready, i);
 	  QUEUE_INDEX (x) = QUEUE_NOWHERE;
-	  TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
+	  TODO_SPEC (x) = HARD_DEP;
 	}
 
       if (q_size)
@@ -3305,7 +3290,7 @@  schedule_block (basic_block *target_bb)
 
 		x = XEXP (link, 0);
 		QUEUE_INDEX (x) = QUEUE_NOWHERE;
-		TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP;
+		TODO_SPEC (x) = HARD_DEP;
 	      }
 	    free_INSN_LIST_list (&insn_queue[i]);
 	  }
@@ -3721,10 +3706,9 @@  static int haifa_speculate_insn (rtx, ds
 int
 try_ready (rtx next)
 {
-  ds_t old_ts, *ts;
+  ds_t old_ts, new_ts;
 
-  ts = &TODO_SPEC (next);
-  old_ts = *ts;
+  old_ts = TODO_SPEC (next);
 
   gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP))
 	      && ((old_ts & HARD_DEP)
@@ -3732,22 +3716,15 @@  try_ready (rtx next)
 
   if (sd_lists_empty_p (next, SD_LIST_BACK))
     /* NEXT has all its dependencies resolved.  */
-    {
-      /* Remove HARD_DEP bit from NEXT's status.  */
-      *ts &= ~HARD_DEP;
-
-      if (current_sched_info->flags & DO_SPECULATION)
-	/* Remove all speculative bits from NEXT's status.  */
-	*ts &= ~SPECULATIVE;
-    }
+    new_ts = 0;
   else
     {
       /* One of the NEXT's dependencies has been resolved.
 	 Recalculate NEXT's status.  */
 
-      *ts &= ~SPECULATIVE & ~HARD_DEP;
-
-      if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
+      if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK))
+	new_ts = HARD_DEP;
+      else
 	/* Now we've got NEXT with speculative deps only.
 	   1. Look at the deps to see what we have to do.
 	   2. Check if we can do 'todo'.  */
@@ -3756,6 +3733,8 @@  try_ready (rtx next)
 	  dep_t dep;
 	  bool first_p = true;
 
+	  new_ts = 0;
+
 	  FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
 	    {
 	      ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
@@ -3768,25 +3747,23 @@  try_ready (rtx next)
 		{
 		  first_p = false;
 
-		  *ts = ds;
+		  new_ts = ds;
 		}
 	      else
-		*ts = ds_merge (*ts, ds);
+		new_ts = ds_merge (new_ts, ds);
 	    }
 
-	  if (ds_weak (*ts) < spec_info->data_weakness_cutoff)
+	  if (ds_weak (new_ts) < spec_info->data_weakness_cutoff)
 	    /* Too few points.  */
-	    *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+	    new_ts = HARD_DEP;
 	}
-      else
-	*ts |= HARD_DEP;
     }
 
-  if (*ts & HARD_DEP)
-    gcc_assert (*ts == old_ts
+  if (new_ts & HARD_DEP)
+    gcc_assert (new_ts == HARD_DEP && new_ts == old_ts
 		&& QUEUE_INDEX (next) == QUEUE_NOWHERE);
   else if (current_sched_info->new_ready)
-    *ts = current_sched_info->new_ready (next, *ts);
+    new_ts = current_sched_info->new_ready (next, new_ts);
 
   /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
      have its original pattern or changed (speculative) one.  This is due
@@ -3794,29 +3771,29 @@  try_ready (rtx next)
      * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
      has speculative pattern.
 
-     We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because
+     We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
      control-speculative NEXT could have been discarded by sched-rgn.c
      (the same case as when discarded by can_schedule_ready_p ()).  */
 
-  if ((*ts & SPECULATIVE)
-      /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't
+  if ((new_ts & SPECULATIVE)
+      /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
 	 need to change anything.  */
-      && *ts != old_ts)
+      && new_ts != old_ts)
     {
       int res;
       rtx new_pat;
 
-      gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE));
+      gcc_assert (!(new_ts & ~SPECULATIVE));
 
-      res = haifa_speculate_insn (next, *ts, &new_pat);
+      res = haifa_speculate_insn (next, new_ts, &new_pat);
 
       switch (res)
 	{
 	case -1:
 	  /* It would be nice to change DEP_STATUS of all dependences,
-	     which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP,
+	     which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
 	     so we won't reanalyze anything.  */
-	  *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+	  new_ts = HARD_DEP;
 	  break;
 
 	case 0:
@@ -3840,14 +3817,16 @@  try_ready (rtx next)
 	}
     }
 
-  /* We need to restore pattern only if (*ts == 0), because otherwise it is
-     either correct (*ts & SPECULATIVE),
-     or we simply don't care (*ts & HARD_DEP).  */
+  /* We need to restore pattern only if (new_ts == 0), because otherwise it is
+     either correct (new_ts & SPECULATIVE),
+     or we simply don't care (new_ts & HARD_DEP).  */
 
   gcc_assert (!ORIG_PAT (next)
 	      || !IS_SPECULATION_BRANCHY_CHECK_P (next));
 
-  if (*ts & HARD_DEP)
+  TODO_SPEC (next) = new_ts;
+
+  if (new_ts & HARD_DEP)
     {
       /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
 	 control-speculative NEXT could have been discarded by sched-rgn.c
@@ -3857,7 +3836,8 @@  try_ready (rtx next)
       change_queue_index (next, QUEUE_NOWHERE);
       return -1;
     }
-  else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
+  else if (!(new_ts & BEGIN_SPEC)
+	   && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next))
     /* We should change pattern of every previously speculative
        instruction - and we determine if NEXT was speculative by using
        ORIG_PAT field.  Except one case - speculation checks have ORIG_PAT
@@ -3869,18 +3849,16 @@  try_ready (rtx next)
 
   if (sched_verbose >= 2)
     {
-      int s = TODO_SPEC (next);
-
       fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s",
                (*current_sched_info->print_insn) (next, 0));
 
       if (spec_info && spec_info->dump)
         {
-          if (s & BEGIN_DATA)
+          if (new_ts & BEGIN_DATA)
             fprintf (spec_info->dump, "; data-spec;");
-          if (s & BEGIN_CONTROL)
+          if (new_ts & BEGIN_CONTROL)
             fprintf (spec_info->dump, "; control-spec;");
-          if (s & BE_IN_CONTROL)
+          if (new_ts & BE_IN_CONTROL)
             fprintf (spec_info->dump, "; in-control-spec;");
         }
 
Index: trunk/gcc/sched-deps.c
===================================================================
--- trunk.orig/gcc/sched-deps.c
+++ trunk/gcc/sched-deps.c
@@ -120,7 +120,7 @@  init_dep (dep_t dep, rtx pro, rtx con, e
   if ((current_sched_info->flags & USE_DEPS_LIST))
     ds = dk_to_ds (kind);
   else
-    ds = -1;
+    ds = 0;
 
   init_dep_1 (dep, pro, con, kind, ds);
 }
@@ -413,6 +413,16 @@  clear_deps_list (deps_list_t l)
   while (1);
 }
 
+/* Decide whether a dependency should be treated as a hard or a speculative
+   dependency.  */
+static bool
+dep_spec_p (dep_t dep)
+{
+  if (current_sched_info->flags & DO_SPECULATION)
+    return (DEP_STATUS (dep) & SPECULATIVE) != 0;
+  return false;
+}
+
 static regset reg_pending_sets;
 static regset reg_pending_clobbers;
 static regset reg_pending_uses;
@@ -1063,6 +1073,7 @@  update_dep (dep_t dep, dep_t new_dep,
 {
   enum DEPS_ADJUST_RESULT res = DEP_PRESENT;
   enum reg_note old_type = DEP_TYPE (dep);
+  bool was_spec = dep_spec_p (dep);
 
   /* If this is a more restrictive type of dependence than the
      existing one, then change the existing dependence to this
@@ -1081,20 +1092,13 @@  update_dep (dep_t dep, dep_t new_dep,
       ds_t new_status = ds | dep_status;
 
       if (new_status & SPECULATIVE)
-	/* Either existing dep or a dep we're adding or both are
-	   speculative.  */
 	{
+	  /* Either existing dep or a dep we're adding or both are
+	     speculative.  */
 	  if (!(ds & SPECULATIVE)
 	      || !(dep_status & SPECULATIVE))
 	    /* The new dep can't be speculative.  */
-	    {
-	      new_status &= ~SPECULATIVE;
-
-	      if (dep_status & SPECULATIVE)
-		/* The old dep was speculative, but now it
-		   isn't.  */
-		change_spec_dep_to_hard (sd_it);
-	    }
+	    new_status &= ~SPECULATIVE;
 	  else
 	    {
 	      /* Both are speculative.  Merge probabilities.  */
@@ -1119,6 +1123,10 @@  update_dep (dep_t dep, dep_t new_dep,
 	}
     }
 
+  if (was_spec && !dep_spec_p (dep))
+    /* The old dep was speculative, but now it isn't.  */
+    change_spec_dep_to_hard (sd_it);
+
   if (true_dependency_cache != NULL
       && res == DEP_CHANGED)
     update_dependency_caches (dep, old_type);
@@ -1219,8 +1227,7 @@  get_back_and_forw_lists (dep_t dep, bool
 
   if (!resolved_p)
     {
-      if ((current_sched_info->flags & DO_SPECULATION)
-	  && (DEP_STATUS (dep) & SPECULATIVE))
+      if (dep_spec_p (dep))
 	*back_list_ptr = INSN_SPEC_BACK_DEPS (con);
       else
 	*back_list_ptr = INSN_HARD_BACK_DEPS (con);
@@ -1247,8 +1254,8 @@  sd_add_dep (dep_t dep, bool resolved_p)
 
   gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem);
 
-  if ((current_sched_info->flags & DO_SPECULATION)
-      && !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
+  if ((current_sched_info->flags & DO_SPECULATION) == 0
+      || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep)))
     DEP_STATUS (dep) &= ~SPECULATIVE;
 
   copy_dep (DEP_NODE_DEP (n), dep);
@@ -1288,8 +1295,7 @@  sd_resolve_dep (sd_iterator_def sd_it)
   rtx pro = DEP_PRO (dep);
   rtx con = DEP_CON (dep);
 
-  if ((current_sched_info->flags & DO_SPECULATION)
-      && (DEP_STATUS (dep) & SPECULATIVE))
+  if (dep_spec_p (dep))
     move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con),
 		   INSN_RESOLVED_BACK_DEPS (con));
   else
@@ -1682,7 +1688,7 @@  haifa_note_mem_dep (rtx mem, rtx pending
     dep_def _dep, *dep = &_dep;
 
     init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds),
-                current_sched_info->flags & USE_DEPS_LIST ? ds : -1);
+                current_sched_info->flags & USE_DEPS_LIST ? ds : 0);
     maybe_add_or_update_dep_1 (dep, false, pending_mem, mem);
   }
 
@@ -3489,18 +3495,23 @@  sched_free_deps (rtx head, rtx tail, boo
   rtx insn;
   rtx next_tail = NEXT_INSN (tail);
 
+  /* We make two passes since some insns may be scheduled before its
+     dependencies are resolved.  */
   for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
     if (INSN_P (insn) && INSN_LUID (insn) > 0)
       {
-	/* Clear resolved back deps together with its dep_nodes.  */
-	delete_dep_nodes_in_back_deps (insn, resolved_p);
-
 	/* Clear forward deps and leave the dep_nodes to the
 	   corresponding back_deps list.  */
 	if (resolved_p)
 	  clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn));
 	else
 	  clear_deps_list (INSN_FORW_DEPS (insn));
+      }
+  for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
+    if (INSN_P (insn) && INSN_LUID (insn) > 0)
+      {
+	/* Clear resolved back deps together with its dep_nodes.  */
+	delete_dep_nodes_in_back_deps (insn, resolved_p);
 
 	sd_finish_insn (insn);
       }
@@ -4141,7 +4152,7 @@  check_dep (dep_t dep, bool relaxed_p)
 
   if (!(current_sched_info->flags & USE_DEPS_LIST))
     {
-      gcc_assert (ds == -1);
+      gcc_assert (ds == 0);
       return;
     }