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> ®ion_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> ®ion_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);
}
