Re: Fill more delay slots in conditional returns

[Steven Bosscher <stevenb dot gcc at gmail dot com>]

On Tue, Apr 9, 2013 at 6:15 PM, Eric Botcazou wrote:
>> If you wanted to get ambitious, rewriting reorg.c to compute and use
>> dependency links to drive its candidate selection instead of the insane
>> tracking code it uses would be a huge step forward, both in terms of
>> cleanliness.  It'd also help compile-time performance; we do a lot of
>> work to track resources that would be totally unnecessary.
>
> Yes, I agree that it's quite convoluted but, as Steven already said, rewriting
> it to use a more modern framework is hard because of SEQUENCEs and, frankly, I
> have neither the real incentive nor the time to start such an endeavor.

I've actually picked up the idea again. This is just last week-end's
work so don't expect much of it yet ;-)

But I'm near the point where I want to see if I can actually make it
fill some slots from the containing basic block and pushing it through
verify_flow_info somehow.

After that, the hard parts: branches and annulling.

Ciao!
Steven

Index: reorg.c
===================================================================
--- reorg.c     (revision 197610)
+++ reorg.c     (working copy)
@@ -3847,6 +3847,10 @@
   free (uid_to_ruid);
   crtl->dbr_scheduled_p = true;
 }
+
+#include "sched-deps-graph.c"
+#include "sched-dbr.c"
+
 #endif /* DELAY_SLOTS */

 static bool
@@ -3865,6 +3869,7 @@
 rest_of_handle_delay_slots (void)
 {
 #ifdef DELAY_SLOTS
+  fill_delay_slots ();
   dbr_schedule (get_insns ());
 #endif
   return 0;

#include "sched-int.h"

/* ??? That means dbr_schedule would come to depend on INSN_SCHEDULING?!  */
//#ifdef INSN_SCHEDULING

/* Bah, sched-deps needs this.  That's a bug, but what the heck...  */
static struct haifa_sched_info sched_dbr_info =
{
  NULL,
  NULL,
  NULL,
  NULL,
  NULL,
  NULL,
  NULL,
  NULL,
  NULL, NULL,
  NULL, NULL,
  0, 0,
  NULL, NULL, NULL, NULL,
  NULL, NULL,
  0
};

static struct sched_deps_info_def dbr_sched_deps_info =
{
  NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
  0, 0, 0
};

static struct common_sched_info_def dbr_common_sched_info;

static void
fill_delay_slots_from_bb (basic_block bb)
{
  rtx head, tail;
  struct deps_desc tmp_deps;

  /* Compute dependencies.  */
  get_ebb_head_tail (bb, bb, &head, &tail);
  init_deps_global ();
  init_deps (&tmp_deps, false);
  sched_analyze (&tmp_deps, head, tail);
  free_deps (&tmp_deps);
  finish_deps_global ();

  /* Print dependency information.  */
  if (dump_file && sched_dump)
    {
      fprintf (sched_dump, ";;   --------------- forward dependences: ------------ \n");
      fprintf (sched_dump, "\n;;   --- DBR Dependences --- for bb%d \n", bb->index);
      debug_dependencies (head, tail);
    }

  print_dependencies_graph (stderr, cfun, bb);

  rtx insn;
  FOR_BB_INSNS (bb, insn)
    {
      if (! NONDEBUG_INSN_P (insn)
	  || (GET_CODE (PATTERN (insn)) == USE
	      || GET_CODE (PATTERN (insn)) == CLOBBER))
	continue;

      INSN_FROM_TARGET_P (insn) = 0;
      if (JUMP_P (insn))
	INSN_ANNULLED_BRANCH_P (insn) = 0;
      int slots_to_fill = num_delay_slots (insn);
      if (slots_to_fill > 0)
        {
	  int flags;
	  if (JUMP_P (insn))
	    flags = get_jump_flags (insn, JUMP_LABEL (insn));
	  else
	    flags = get_jump_flags (insn, NULL_RTX);
	  fprintf (stderr,
		   "// insn %d has %d delay slots to fill\n",
		   INSN_UID (insn), slots_to_fill);
	  for (rtx cand_insn = PREV_INSN (insn);
	       cand_insn != BB_HEAD (bb);
	       cand_insn = PREV_INSN (cand_insn))
	    {
	      sd_iterator_def sd_it;
	      dep_t dep;
	      int n_forw_deps = 0;
	      bool cand_feeds_call_insn = false;
	      bool cand_deps_cross_insn = false;

	      /* TRIAL must be a CALL_INSN or INSN.  Skip USE and CLOBBER.  */
	      if (! NONDEBUG_INSN_P (cand_insn)
		  || (GET_CODE (PATTERN (cand_insn)) == USE
		      || GET_CODE (PATTERN (cand_insn)) == CLOBBER))
		continue;

	      if (! eligible_for_delay (insn, 0, cand_insn, flags))
		{
		  fprintf (stderr,
			   "//\tinsn %d not eligible for delay slots of insn %d\n",
			   INSN_UID (cand_insn), INSN_UID (insn));
		  continue;
		}

	      rtx set = single_set (cand_insn);
	      if (! set || multiple_sets (cand_insn))
		continue;

	      FOR_EACH_DEP (cand_insn, SD_LIST_FORW, sd_it, dep)
		{
		  n_forw_deps++;
		  if (DF_INSN_LUID (insn) < DF_INSN_LUID (DEP_CON (dep)))
		    cand_deps_cross_insn = true;
		  else if (DF_INSN_LUID (insn) == DF_INSN_LUID (DEP_CON (dep))
			   && CALL_P (insn) && df_reg_used (insn, SET_DEST (set)))
		    cand_feeds_call_insn = true;
		  else // not a deps leaf, not a call arg setter
		    {
		      fprintf (stderr,
			       "//\tinsn %d is not suitable, blocked by insn %d\n",
			       INSN_UID (cand_insn), INSN_UID (DEP_CON (dep)));
		      n_forw_deps = -1;
		      break;
		    }
		}

	      if (n_forw_deps < 0)
		continue;

	      if (n_forw_deps == 0)
		{
		  fprintf (stderr,
			   "//\tinsn %d is an obvious candidate, dependencies leaf\n",
			   INSN_UID (cand_insn));
		  fprintf (stderr,
			   "\tfn_%d_insn_uid_%d:e -> fn_%d_insn_uid_%d:e "
			   "[style=\"dotted\",color=\"green\",constraint=false];\n",
			   cfun->funcdef_no, INSN_UID (cand_insn),
			   cfun->funcdef_no, INSN_UID (insn));
		}
	      else if (cand_feeds_call_insn && cand_deps_cross_insn)
		{
		  fprintf (stderr,
			   "//\tinsn %d may be suitable, feeds branching insn and dependencies cross over insn\n",
			   INSN_UID (cand_insn));
		  fprintf (stderr,
			   "\tfn_%d_insn_uid_%d:e -> fn_%d_insn_uid_%d:e "
			   "[style=\"dotted\",color=\"red\",constraint=false];\n",
			   cfun->funcdef_no, INSN_UID (cand_insn),
			   cfun->funcdef_no, INSN_UID (insn));
		}
	      else if (cand_feeds_call_insn)
		{
		  fprintf (stderr,
			   "//\tinsn %d is a candidate, sets call arg register\n",
			   INSN_UID (cand_insn));
		  fprintf (stderr,
			   "\tfn_%d_insn_uid_%d:e -> fn_%d_insn_uid_%d:e "
			   "[style=\"dotted\",color=\"red\",constraint=false];\n",
			   cfun->funcdef_no, INSN_UID (cand_insn),
			   cfun->funcdef_no, INSN_UID (insn));
		}
	      else if (cand_deps_cross_insn)
		{
		  fprintf (stderr,
			   "//\tinsn %d may be suitable, dependencies cross over insn\n",
			   INSN_UID (cand_insn));
		  fprintf (stderr,
			   "\tfn_%d_insn_uid_%d:e -> fn_%d_insn_uid_%d:e "
			   "[style=\"dotted\",color=\"red\",constraint=false];\n",
			   cfun->funcdef_no, INSN_UID (cand_insn),
			   cfun->funcdef_no, INSN_UID (insn));
		}
	    }
	}
    }

  /* Free dependencies.  */
  sched_free_deps (head, tail, false);
}

/* The main entry point in this file.  */

static void
fill_delay_slots (void)
{
  basic_block bb;

  /* Set up the various scheduler hooks.  */
  memcpy (&dbr_common_sched_info, &haifa_common_sched_info,
	  sizeof (dbr_common_sched_info));
  common_sched_info = &dbr_common_sched_info;
  sched_deps_info = &dbr_sched_deps_info;
  current_sched_info = &sched_dbr_info;

  compute_bb_for_insn ();
  df_analyze ();

  haifa_sched_init ();

  /* Try to fill delay slots with insns from the same basic block as
     the one that contains the insns with the delay slots.  */
  start_dependencies_graph_dump (stderr);
  FOR_EACH_BB (bb)
    {
      if (bb->flags & BB_DISABLE_SCHEDULE)
	continue;
      fill_delay_slots_from_bb (bb);
    }
  end_dependencies_graph_dump (stderr);

  free_bb_for_insn ();
  haifa_sched_finish ();
}

/* Output routines for graphical representation of scheduler dependencies.
   Copyright (C) 2013 Free Software Foundation, Inc.
   Contributed by Steven Bosscher, 2012.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "pointer-set.h"
#include "dumpfile.h"
#include "pretty-print.h"
#include "sched-int.h"

/* Return a pretty-print buffer for output to file FP.  */

static pretty_printer *
init_deps_pretty_print (FILE *fp)
{
  static bool initialized = false;
  static pretty_printer graph_slim_pp;

  if (! initialized)
    {
      pp_construct (&graph_slim_pp, /*prefix=*/NULL, /*linewidth=*/0);
      initialized = true;
    }
  else
    gcc_assert (! pp_last_position_in_text (&graph_slim_pp));

  graph_slim_pp.buffer->stream = fp;
  return &graph_slim_pp;
}

static void
mark_transitive_deps (sd_list_types_def list_type, rtx insn, bitmap transitive_deps)
{
  sd_iterator_def sd_it;
  dep_t dep;

  FOR_EACH_DEP (insn, list_type, sd_it, dep)
    {
      rtx dep_insn = (list_type == SD_LIST_FORW) ? DEP_CON (dep) : DEP_PRO (dep);
      if (bitmap_set_bit (transitive_deps, INSN_UID (dep_insn)))
	mark_transitive_deps (list_type, dep_insn, transitive_deps);
    }
}

/* Draw all forward dependence edges for a region belonging to the function FUN
   containing REGION_INSNS.  */
static void
draw_dependence_edges (pretty_printer *pp, struct function *fun, vec<rtx> &region_insns)
{
  bitmap transitive_deps = BITMAP_ALLOC (NULL);
  unsigned i;
  rtx insn;

  FOR_EACH_VEC_ELT (region_insns, i, insn)
    {
      sd_iterator_def sd_it;
      dep_t dep;

      bitmap_clear (transitive_deps);
      FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
	mark_transitive_deps (SD_LIST_FORW, DEP_CON (dep), transitive_deps);
      FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
	if (! bitmap_bit_p (transitive_deps, INSN_UID (DEP_CON (dep))))
	  pp_printf (pp,
		     "\tfn_%d_insn_uid_%d:s -> fn_%d_insn_uid_%d:n "
		     "[style=\"solid,bold\",color=\"black\",weight=%d];\n",
		     fun->funcdef_no, INSN_UID (insn),
		     fun->funcdef_no, INSN_UID (DEP_CON (dep)),
		     1 + (DEP_COST (dep) > 0 ? 100 * DEP_COST (dep) : 0));

//      bitmap_clear (transitive_deps);
//      FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
//	mark_transitive_deps (SD_LIST_BACK, DEP_PRO (dep), transitive_deps);
//      FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
//	if (! bitmap_bit_p (transitive_deps, INSN_UID (DEP_PRO (dep))))
//	  pp_printf (pp,
//		     "\tfn_%d_insn_uid_%d:n -> fn_%d_insn_uid_%d:s "
//		     "[style=\"dotted\",color=\"red\",constraint=false];\n",
//		     fun->funcdef_no, INSN_UID (insn),
//		     fun->funcdef_no, INSN_UID (DEP_PRO (dep)));

    }
  BITMAP_FREE (transitive_deps);
  pp_flush (pp);
}

/* Draw all insns for a region of function FUN containing REGION_INSNS.  */
static void
draw_dependence_nodes (pretty_printer *pp, struct function *fun, vec<rtx> &region_insns)
{
  const char *fillcolors[3] = { "grey88", "grey77", "grey66" };
  static int region_no = 1;
  unsigned i;
  rtx insn;

  pp_printf (pp,
	     "\tsubgraph cluster_%d_%d {\n"
	     "\tstyle=\"filled\";\n"
	     "\tcolor=\"darkgreen\";\n"
	     "\tfillcolor=\"%s\";\n"
	     "\tlabel=\"region %d\";\n"
	     "\tlabeljust=l;\n"
	     "\tpenwidth=2;\n",
	     fun->funcdef_no, region_no,
	     fillcolors[(region_no - 1) % 3],
	     region_no);
  pp_write_text_to_stream (pp);
  region_no++;

  FOR_EACH_VEC_ELT (region_insns, i, insn)
    {
      pp_printf (pp,
		 "\tfn_%d_insn_uid_%d "
		 "[shape=\"record\",style=\"filled\",fillcolor=\"white\","
		 "label=\"{",
		 fun->funcdef_no, INSN_UID (insn));
      pp_write_text_to_stream (pp);
      print_insn (pp, insn, /*verbose=*/ 1);
      pp_newline (pp);
      pp_write_text_as_dot_label_to_stream (pp, /*for_record=*/true);
      pp_string (pp, "}\"];\n\n");
      pp_flush (pp);
    }

  pp_printf (pp, "\t}\n");
  pp_flush (pp);
}

/* Print a graphical representation of the dependencies graph
   for the region starting from FROM_BB.  */

static void
print_dependencies_graph (FILE *outf, struct function *fun, basic_block bb)
{
  pretty_printer *pp = init_deps_pretty_print (outf);
  pp_printf (pp, "subgraph \"%s\" {\n"
	         "\tcolor=\"black\";\n"
		 "\tlabel=\"%s\";\n",
		 function_name (fun), function_name (fun));

  vec<rtx> region_insns = vNULL;
//  for (int bb = from_bb; bb < current_nr_blocks; bb++)
    { 
      rtx insn, head, tail;
 //     get_ebb_head_tail (EBB_FIRST_BB (bb), EBB_LAST_BB (bb), &head, &tail);
      get_ebb_head_tail (bb, bb, &head, &tail);
      for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
	if (NONDEBUG_INSN_P (insn))
	  region_insns.safe_push (insn);
    }

  draw_dependence_nodes (pp, fun, region_insns);
  draw_dependence_edges (pp, fun, region_insns);
  pp_printf (pp, "}\n");
  pp_flush (pp);
}

/* Start the dump of a graph.  */
static void
start_dependencies_graph_dump (FILE *outf)
{
  pretty_printer *pp = init_deps_pretty_print (outf);
  pp_flush (pp);
  pp_string (pp, "digraph \"dependencies_graph\" {\n");
  pp_string (pp, "overlap=false;\n");
  pp_flush (pp);
}

/* End the dump of a graph.  */
static void
end_dependencies_graph_dump (FILE *outf)
{
  pretty_printer *pp = init_deps_pretty_print (outf);
  pp_string (pp, "}\n");
  pp_flush (pp);
}