This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Fix scheduler priorities update
- From: Maxim Kuvyrkov <mkuvyrkov at ispras dot ru>
- To: Vladimir Makarov <vmakarov at redhat dot com>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Wed, 11 Apr 2007 11:53:25 +0400
- Subject: [PATCH]: Fix scheduler priorities update
Hi!
While testing my other patch I came across a bug in IA64 speculation
support in scheduler. The problem is in priorities update mechanism
that is used to calculate proper priorities after speculative movement
of an instruction. The speculative movement discards some of the insn's
dependencies which in turn might affect the priorities of insn's former
producers. The bug is that not all producers get their priorities updated.
The attached patch fixes this problem and was bootstrapped and now being
regtested on {x86_64, ia64}-linux-gnu.
:ADDPATCH scheduler:
Thanks,
Maxim
2007-04-11 Maxim Kuvyrkov <mkuvyrkov@ispras.ru>
* haifa-sched.c (vec.h): New include.
(rtx_vec_t): New typedef.
(contributes_to_priority_p): Extract piece of priority () into new
static function.
(priority): Add assertion.
(rank_for_schedule, set_priorities): Add assertion to check that
insn's priority is initialized.
(clear_priorities, calc_priorities): Change signature. Make it update
all relevant insns. Update all callers.
* sched-int.h (struct haifa_insn_data): Change type of 'priority_known'
field from a 1-bit field to 'signed char'.
(INSN_PRIORITY_KNOWN_P): New macro.
* config/rs6000.c (rs6000_sched_reorder2): Use it instead of
INSN_PRIORITY_KNOWN ().
* Makefile.in (haifa-sched.o): New dependency.
--- haifa-sched.c (/mirror/endeed/trunk/gcc) (revision 1062)
+++ haifa-sched.c (/mirror/endeed/calc-priorities/gcc) (revision 1062)
@@ -144,6 +144,7 @@ Software Foundation, 51 Franklin Street,
#include "target.h"
#include "output.h"
#include "params.h"
+#include "vec.h"
#ifdef INSN_SCHEDULING
@@ -487,6 +488,9 @@ haifa_classify_insn (rtx insn)
return insn_class;
}
+/* A typedef for rtx vector. */
+typedef VEC(rtx, heap) *rtx_vec_t;
+
/* Forward declarations. */
static int priority (rtx);
@@ -575,9 +579,9 @@ static void init_glat1 (basic_block);
static void attach_life_info1 (basic_block);
static void free_glat (void);
static void sched_remove_insn (rtx);
-static void clear_priorities (rtx);
+static void clear_priorities (rtx, rtx_vec_t *);
+static void calc_priorities (rtx_vec_t);
static void add_jump_dependencies (rtx, rtx);
-static void calc_priorities (rtx);
#ifdef ENABLE_CHECKING
static int has_edge_p (VEC(edge,gc) *, int);
static void check_cfg (rtx, rtx);
@@ -703,8 +707,30 @@ dep_cost (dep_t link)
return cost;
}
-/* Compute the priority number for INSN. */
+/* Return 'true' if DEP should be included in priority calculations. */
+static bool
+contributes_to_priority_p (dep_t dep)
+{
+ /* Critical path is meaningful in block boundaries only. */
+ if (!current_sched_info->contributes_to_priority (DEP_CON (dep),
+ DEP_PRO (dep)))
+ return false;
+
+ /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
+ then speculative instructions will less likely be
+ scheduled. That is because the priority of
+ their producers will increase, and, thus, the
+ producers will more likely be scheduled, thus,
+ resolving the dependence. */
+ if ((current_sched_info->flags & DO_SPECULATION)
+ && !(spec_info->flags & COUNT_SPEC_IN_CRITICAL_PATH)
+ && (DEP_STATUS (dep) & SPECULATIVE))
+ return false;
+ return true;
+}
+
+/* Compute the priority number for INSN. */
static int
priority (rtx insn)
{
@@ -713,7 +739,10 @@ priority (rtx insn)
if (! INSN_P (insn))
return 0;
- if (! INSN_PRIORITY_KNOWN (insn))
+ /* We should not be insterested in priority of an already scheduled insn. */
+ gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
+
+ if (!INSN_PRIORITY_KNOWN_P (insn))
{
int this_priority = 0;
@@ -760,20 +789,7 @@ priority (rtx insn)
{
int cost;
- /* Critical path is meaningful in block boundaries
- only. */
- if (! (*current_sched_info->contributes_to_priority)
- (next, insn)
- /* If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
- then speculative instructions will less likely be
- scheduled. That is because the priority of
- their producers will increase, and, thus, the
- producers will more likely be scheduled, thus,
- resolving the dependence. */
- || ((current_sched_info->flags & DO_SPECULATION)
- && (DEP_STATUS (dep) & SPECULATIVE)
- && !(spec_info->flags
- & COUNT_SPEC_IN_CRITICAL_PATH)))
+ if (!contributes_to_priority_p (dep))
continue;
if (twin == insn)
@@ -832,6 +848,9 @@ rank_for_schedule (const void *x, const
if (SCHED_GROUP_P (tmp) != SCHED_GROUP_P (tmp2))
return SCHED_GROUP_P (tmp2) ? 1 : -1;
+ /* Make sure that priority of TMP and TMP2 are initialized. */
+ gcc_assert (INSN_PRIORITY_KNOWN_P (tmp) && INSN_PRIORITY_KNOWN_P (tmp2));
+
/* Prefer insn with higher priority. */
priority_val = INSN_PRIORITY (tmp2) - INSN_PRIORITY (tmp);
@@ -2541,9 +2560,10 @@ set_priorities (rtx head, rtx tail)
n_insn++;
(void) priority (insn);
- if (INSN_PRIORITY_KNOWN (insn))
- sched_max_insns_priority =
- MAX (sched_max_insns_priority, INSN_PRIORITY (insn));
+ gcc_assert (INSN_PRIORITY_KNOWN_P (insn));
+
+ sched_max_insns_priority = MAX (sched_max_insns_priority,
+ INSN_PRIORITY (insn));
}
current_sched_info->sched_max_insns_priority = sched_max_insns_priority;
@@ -3224,6 +3244,7 @@ add_to_speculative_block (rtx insn)
ds_t ts;
dep_link_t link;
rtx twins = NULL;
+ rtx_vec_t priorities_roots;
ts = TODO_SPEC (insn);
gcc_assert (!(ts & ~BE_IN_SPEC));
@@ -3255,7 +3276,8 @@ add_to_speculative_block (rtx insn)
link = DEP_LINK_NEXT (link);
}
- clear_priorities (insn);
+ priorities_roots = NULL;
+ clear_priorities (insn, &priorities_roots);
do
{
@@ -3342,13 +3364,15 @@ add_to_speculative_block (rtx insn)
rtx twin;
twin = XEXP (twins, 0);
- calc_priorities (twin);
add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT);
twin = XEXP (twins, 1);
free_INSN_LIST_node (twins);
twins = twin;
}
+
+ calc_priorities (priorities_roots);
+ VEC_free (rtx, heap, priorities_roots);
}
/* Extends and fills with zeros (only the new part) array pointed to by P. */
@@ -3793,8 +3817,11 @@ create_check_block_twin (rtx insn, bool
/* Fix priorities. If MUTATE_P is nonzero, this is not necessary,
because it'll be done later in add_to_speculative_block. */
{
- clear_priorities (twin);
- calc_priorities (twin);
+ rtx_vec_t priorities_roots = NULL;
+
+ clear_priorities (twin, &priorities_roots);
+ calc_priorities (priorities_roots);
+ VEC_free (rtx, heap, priorities_roots);
}
}
@@ -4281,42 +4308,50 @@ sched_remove_insn (rtx insn)
remove_insn (insn);
}
-/* Clear priorities of all instructions, that are
- forward dependent on INSN. */
+/* Clear priorities of all instructions, that are forward dependent on INSN.
+ Store in vector pointed to by ROOTS_PTR insns on which priority () should
+ be invoked to initialize all cleared priorities. */
static void
-clear_priorities (rtx insn)
+clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
{
dep_link_t link;
+ bool insn_is_root_p = true;
+
+ gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
{
- rtx pro = DEP_LINK_PRO (link);
+ dep_t dep = DEP_LINK_DEP (link);
+ rtx pro = DEP_PRO (dep);
- if (INSN_PRIORITY_KNOWN (pro))
+ if (INSN_PRIORITY_KNOWN (pro) >= 0
+ && QUEUE_INDEX (insn) != QUEUE_SCHEDULED)
{
- INSN_PRIORITY_KNOWN (pro) = 0;
- clear_priorities (pro);
+ /* If DEP doesn't contribute to priority then INSN itself should
+ be added to priority roots. */
+ if (contributes_to_priority_p (dep))
+ insn_is_root_p = false;
+
+ INSN_PRIORITY_KNOWN (pro) = -1;
+ clear_priorities (pro, roots_ptr);
}
}
+
+ if (insn_is_root_p)
+ VEC_safe_push (rtx, heap, *roots_ptr, insn);
}
/* Recompute priorities of instructions, whose priorities might have been
- changed due to changes in INSN. */
+ changed. ROOTS is a vector of instructions whose priority computation will
+ trigger initialization of all cleared priorities. */
static void
-calc_priorities (rtx insn)
+calc_priorities (rtx_vec_t roots)
{
- dep_link_t link;
-
- FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
- {
- rtx pro = DEP_LINK_PRO (link);
+ int i;
+ rtx insn;
- if (!INSN_PRIORITY_KNOWN (pro))
- {
- priority (pro);
- calc_priorities (pro);
- }
- }
+ for (i = 0; VEC_iterate (rtx, roots, i, insn); i++)
+ priority (insn);
}
--- sched-int.h (/mirror/endeed/trunk/gcc) (revision 1062)
+++ sched-int.h (/mirror/endeed/calc-priorities/gcc) (revision 1062)
@@ -532,8 +532,10 @@ struct haifa_insn_data
unsigned int fed_by_spec_load : 1;
unsigned int is_load_insn : 1;
- /* Nonzero if priority has been computed already. */
- unsigned int priority_known : 1;
+ /* '> 0' if priority is valid,
+ '== 0' if priority was not yet computed,
+ '< 0' if priority in invalid and should be recomputed. */
+ signed char priority_known;
/* Nonzero if instruction has internal dependence
(e.g. add_dependence was invoked with (insn == elem)). */
@@ -570,6 +572,8 @@ extern regset *glat_start, *glat_end;
#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count)
#define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority)
#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
+#define INSN_PRIORITY_KNOWN_P(INSN) \
+ (h_i_d[INSN_UID (INSN)].priority_known > 0)
#define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight)
#define HAS_INTERNAL_DEP(INSN) (h_i_d[INSN_UID (INSN)].has_internal_dep)
#define TODO_SPEC(INSN) (h_i_d[INSN_UID (INSN)].todo_spec)
--- Makefile.in (/mirror/endeed/trunk/gcc) (revision 1062)
+++ Makefile.in (/mirror/endeed/calc-priorities/gcc) (revision 1062)
@@ -2702,7 +2702,7 @@ modulo-sched.o : modulo-sched.c $(DDG_H)
haifa-sched.o : haifa-sched.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(SCHED_INT_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \
$(FUNCTION_H) $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h $(TM_P_H) \
- $(TARGET_H) output.h $(PARAMS_H)
+ $(TARGET_H) output.h $(PARAMS_H) vec.h
sched-deps.o : sched-deps.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(SCHED_INT_H) $(REGS_H) hard-reg-set.h $(FLAGS_H) insn-config.h \
$(FUNCTION_H) $(INSN_ATTR_H) toplev.h $(RECOG_H) except.h cselib.h \
--- config/rs6000/rs6000.c (/mirror/endeed/trunk/gcc) (revision 1062)
+++ config/rs6000/rs6000.c (/mirror/endeed/calc-priorities/gcc) (revision 1062)
@@ -17851,7 +17851,7 @@ rs6000_sched_reorder2 (FILE *dump, int s
for (i=pos; i<*pn_ready-1; i++)
ready[i] = ready[i + 1];
ready[*pn_ready-1] = tmp;
- if INSN_PRIORITY_KNOWN (tmp)
+ if (INSN_PRIORITY_KNOWN_P (tmp))
INSN_PRIORITY (tmp)++;
break;
}
@@ -17868,7 +17868,7 @@ rs6000_sched_reorder2 (FILE *dump, int s
while (pos >= 0)
{
if (is_load_insn (ready[pos])
- && INSN_PRIORITY_KNOWN (ready[pos]))
+ && INSN_PRIORITY_KNOWN_P (ready[pos]))
{
INSN_PRIORITY (ready[pos])++;
@@ -17910,7 +17910,7 @@ rs6000_sched_reorder2 (FILE *dump, int s
for (i=pos; i<*pn_ready-1; i++)
ready[i] = ready[i + 1];
ready[*pn_ready-1] = tmp;
- if INSN_PRIORITY_KNOWN (tmp)
+ if (INSN_PRIORITY_KNOWN_P (tmp))
INSN_PRIORITY (tmp)++;
first_store_pos = -1;
@@ -17930,7 +17930,7 @@ rs6000_sched_reorder2 (FILE *dump, int s
for (i=first_store_pos; i<*pn_ready-1; i++)
ready[i] = ready[i + 1];
ready[*pn_ready-1] = tmp;
- if INSN_PRIORITY_KNOWN (tmp)
+ if (INSN_PRIORITY_KNOWN_P (tmp))
INSN_PRIORITY (tmp)++;
}
}
@@ -17944,7 +17944,7 @@ rs6000_sched_reorder2 (FILE *dump, int s
while (pos >= 0)
{
if (is_store_insn (ready[pos])
- && INSN_PRIORITY_KNOWN (ready[pos]))
+ && INSN_PRIORITY_KNOWN_P (ready[pos]))
{
INSN_PRIORITY (ready[pos])++;