[PATCH 1/3] Transformation replay mechanism
Alexander Monakov
amonakov@ispras.ru
Wed Oct 26 17:38:00 GMT 2011
(Note, this is a prerequisite for predication support but also is an
improvement on its own. This patch can be installed separately.)
This patch implements transformation replay mechanism (redo_transformations).
Currently, after choosing an expression to schedule and finding its original
expressions below the scheduling fence in move_op, we need to move the
original expressions up (e.g. to correctly generate bookkeeping copies). That
moving up would call moveup_expr_cached.
The patch slightly optimizes this by performing lookups in the history vector
of the chosen expression, which must contain all transformations of all
original expressions. Not much changes are needed: the most notable is
perhaps that for speculation transformation, both old and new speculative
statuses are saved.
This patch is needed by the following predication patch, which uses
redo_transformations to correctly apply inverted/non-inverted predicate on
jumps without needing to remember the branch from which the expression
originated.
2011-10-26 Alexander Monakov <amonakov@ispras.ru>
* sel-sched-ir.c (free_history_vect): Export.
(insert_in_history_vect): Rename argument spec_ds to old_spec_ds, add
new argument (new_spec_ds). Record it in the history vector. Update
all callers.
(init_expr): Assert that initial history is empty. Simplify code.
(copy_history_of_changes): Split out from copy_expr.
* sel-sched-ir.h (struct expr_history_def_1): Rename spec_ds to
old_spec_ds. Add new member (new_spec_ds).
(copy_history_of_changes, free_history_vect): Declare.
(insert_in_history_vect): Adjust prototype.
* sel-sched.c (undo_transformations): Adjust.
(move_exprs_to_boundary): Discard history of expression to be
scheduled.
(move_op_orig_expr_found): Populate history vector of c_expr for use
in redo_transformations.
(redo_transformations): New.
(move_op_ascend): Use redo_transformations.
diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index 1bbc3ed..1a73308 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -149,7 +149,6 @@ static expr_t set_insn_init (expr_t, vinsn_t, int);
static void cfg_preds (basic_block, insn_t **, int *);
static void prepare_insn_expr (insn_t, int);
-static void free_history_vect (VEC (expr_history_def, heap) **);
static void move_bb_info (basic_block, basic_block);
static void remove_empty_bb (basic_block, bool);
@@ -1503,13 +1502,13 @@ find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
/* Insert new element in a sorted history vector pointed to by PVECT,
if it is not there already. The element is searched using
- UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN and SPEC_DS save
- the history of a transformation. */
+ UID/NEW_EXPR_VINSN pair. TYPE, OLD_EXPR_VINSN, OLD_SPEC_DS and
+ NEW_SPEC_DS save the history of a transformation. */
void
insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
unsigned uid, enum local_trans_type type,
vinsn_t old_expr_vinsn, vinsn_t new_expr_vinsn,
- ds_t spec_ds)
+ ds_t old_spec_ds, ds_t new_spec_ds)
{
VEC(expr_history_def, heap) *vect = *pvect;
expr_history_def temp;
@@ -1525,15 +1524,16 @@ insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
/* It is possible that speculation types of expressions that were
propagated through different paths will be different here. In this
case, merge the status to get the correct check later. */
- if (phist->spec_ds != spec_ds)
- phist->spec_ds = ds_max_merge (phist->spec_ds, spec_ds);
+ if (phist->old_spec_ds != old_spec_ds)
+ phist->old_spec_ds = ds_max_merge (phist->old_spec_ds, old_spec_ds);
return;
}
temp.uid = uid;
temp.old_expr_vinsn = old_expr_vinsn;
temp.new_expr_vinsn = new_expr_vinsn;
- temp.spec_ds = spec_ds;
+ temp.old_spec_ds = old_spec_ds;
+ temp.new_spec_ds = new_spec_ds;
temp.type = type;
vinsn_attach (old_expr_vinsn);
@@ -1543,7 +1543,7 @@ insert_in_history_vect (VEC (expr_history_def, heap) **pvect,
}
/* Free history vector PVECT. */
-static void
+void
free_history_vect (VEC (expr_history_def, heap) **pvect)
{
unsigned i;
@@ -1576,7 +1576,7 @@ merge_history_vect (VEC (expr_history_def, heap) **pvect,
for (i = 0; VEC_iterate (expr_history_def, from, i, phist); i++)
insert_in_history_vect (pvect, phist->uid, phist->type,
phist->old_expr_vinsn, phist->new_expr_vinsn,
- phist->spec_ds);
+ phist->old_spec_ds, phist->new_spec_ds);
}
/* Compare two vinsns as rhses if possible and as vinsns otherwise. */
@@ -1632,10 +1632,8 @@ init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
- if (history)
- EXPR_HISTORY_OF_CHANGES (expr) = history;
- else
- EXPR_HISTORY_OF_CHANGES (expr) = NULL;
+ gcc_assert (!history);
+ EXPR_HISTORY_OF_CHANGES (expr) = history;
EXPR_TARGET_AVAILABLE (expr) = target_available;
EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
@@ -1644,35 +1642,39 @@ init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
EXPR_CANT_MOVE (expr) = cant_move;
}
-/* Make a copy of the expr FROM into the expr TO. */
+/* Copy history vector of the expr FROM to the expr TO. */
void
-copy_expr (expr_t to, expr_t from)
+copy_history_of_changes (expr_t to, expr_t from)
{
- VEC(expr_history_def, heap) *temp = NULL;
-
if (EXPR_HISTORY_OF_CHANGES (from))
{
unsigned i;
expr_history_def *phist;
- temp = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
- for (i = 0;
- VEC_iterate (expr_history_def, temp, i, phist);
- i++)
+ EXPR_HISTORY_OF_CHANGES (to)
+ = VEC_copy (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (from));
+ FOR_EACH_VEC_ELT (expr_history_def, EXPR_HISTORY_OF_CHANGES (to), i,
+ phist)
{
vinsn_attach (phist->old_expr_vinsn);
vinsn_attach (phist->new_expr_vinsn);
}
}
+}
+/* Make a copy of the expr FROM into the expr TO. */
+void
+copy_expr (expr_t to, expr_t from)
+{
init_expr (to, EXPR_VINSN (from), EXPR_SPEC (from),
EXPR_USEFULNESS (from), EXPR_PRIORITY (from),
EXPR_SCHED_TIMES (from), EXPR_ORIG_BB_INDEX (from),
EXPR_SPEC_DONE_DS (from), EXPR_SPEC_TO_CHECK_DS (from),
- EXPR_ORIG_SCHED_CYCLE (from), temp,
+ EXPR_ORIG_SCHED_CYCLE (from), NULL,
EXPR_TARGET_AVAILABLE (from), EXPR_WAS_SUBSTITUTED (from),
EXPR_WAS_RENAMED (from), EXPR_NEEDS_SPEC_CHECK_P (from),
EXPR_CANT_MOVE (from));
+ copy_history_of_changes (to, from);
}
/* Same, but the final expr will not ever be in av sets, so don't copy
@@ -1798,7 +1800,7 @@ update_speculative_bits (expr_t to, expr_t from, insn_t split_point)
insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
INSN_UID (split_point), TRANS_SPECULATION,
EXPR_VINSN (from), EXPR_VINSN (to),
- record_ds);
+ record_ds, EXPR_SPEC_DONE_DS (to));
}
}
}
diff --git a/gcc/sel-sched-ir.h b/gcc/sel-sched-ir.h
index c8f8be6..bcb47c6 100644
--- a/gcc/sel-sched-ir.h
+++ b/gcc/sel-sched-ir.h
@@ -89,8 +89,11 @@ struct expr_history_def_1
/* How the expression looks after the transformation. */
vinsn_t new_expr_vinsn;
- /* And its speculative status. */
- ds_t spec_ds;
+ /* Its previous speculative status. */
+ ds_t old_spec_ds;
+
+ /* Its new speculative status. */
+ ds_t new_spec_ds;
/* Type of the transformation. */
enum local_trans_type type;
@@ -1537,6 +1540,8 @@ extern bool vinsn_equal_p (vinsn_t, vinsn_t);
/* EXPR functions. */
extern void copy_expr (expr_t, expr_t);
+extern void copy_history_of_changes (expr_t, expr_t);
+extern void free_history_vect (VEC (expr_history_def, heap) **);
extern void copy_expr_onside (expr_t, expr_t);
extern void merge_expr_data (expr_t, expr_t, insn_t);
extern void merge_expr (expr_t, expr_t, insn_t);
@@ -1547,7 +1552,7 @@ extern int find_in_history_vect (VEC(expr_history_def, heap) *,
rtx, vinsn_t, bool);
extern void insert_in_history_vect (VEC(expr_history_def, heap) **,
unsigned, enum local_trans_type,
- vinsn_t, vinsn_t, ds_t);
+ vinsn_t, vinsn_t, ds_t, ds_t);
extern void mark_unavailable_targets (av_set_t, av_set_t, regset);
extern int speculate_expr (expr_t, ds_t);
diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
index f11faca..91fb0fe 100644
--- a/gcc/sel-sched.c
+++ b/gcc/sel-sched.c
@@ -1965,7 +1965,7 @@ undo_transformations (av_set_t *av_ptr, rtx insn)
and in the case of merging different probabilities of the
same speculative status along different paths we do not
record this in the history vector. */
- old_ds = phist->spec_ds;
+ old_ds = phist->old_spec_ds;
new_ds = EXPR_SPEC_DONE_DS (expr);
old_ds &= SPECULATIVE;
@@ -2409,7 +2409,7 @@ try_transformation_cache (expr_t expr, insn_t insn,
insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
INSN_UID (insn), pti->type,
pti->vinsn_old, pti->vinsn_new,
- EXPR_SPEC_DONE_DS (expr));
+ EXPR_SPEC_DONE_DS (expr), pti->ds);
if (INSN_IN_STREAM_P (VINSN_INSN_RTX (pti->vinsn_new)))
pti->vinsn_new = vinsn_copy (pti->vinsn_new, true);
@@ -2564,7 +2564,7 @@ moveup_expr_cached (expr_t expr, insn_t insn, bool inside_insn_group)
insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (expr),
INSN_UID (insn), trans_type,
expr_old_vinsn, EXPR_VINSN (expr),
- expr_old_spec_ds);
+ expr_old_spec_ds, EXPR_SPEC_DONE_DS (expr));
update_transformation_cache (expr, insn, inside_insn_group,
trans_type, expr_old_vinsn);
if (sched_verbose >= 6)
@@ -5234,6 +5234,7 @@ move_exprs_to_boundary (bnd_t bnd, expr_t expr_vliw,
b = move_op (BND_TO (bnd), expr_seq, expr_vliw,
get_dest_from_orig_ops (expr_seq), c_expr, &should_move);
+ free_history_vect (&EXPR_HISTORY_OF_CHANGES (c_expr));
/* We should be able to find the expression we've chosen for
scheduling. */
@@ -5999,6 +6000,7 @@ move_op_orig_expr_found (insn_t insn, expr_t expr,
moveop_static_params_p params = (moveop_static_params_p) static_params;
copy_expr_onside (params->c_expr, INSN_EXPR (insn));
+ copy_history_of_changes (params->c_expr, expr);
track_scheduled_insns_and_blocks (insn);
insn_emitted = handle_emitting_transformations (insn, expr, params);
only_disconnect = (params->uid == INSN_UID (insn)
@@ -6149,19 +6151,78 @@ fur_at_first_insn (insn_t insn,
|| AV_LEVEL (insn) == -1);
}
+/* Redo the transformation that moveup_expr performed on EXPR for INSN, as
+ recorded in EXPR's history vector. */
+static void
+redo_transformations (expr_t expr, insn_t insn)
+{
+ unsigned i, insn_uid = INSN_UID (insn);
+ rtx orig_expr_lhs = EXPR_LHS (expr);
+ expr_history_def *hist;
+ VEC(expr_history_def, heap) *vect = EXPR_HISTORY_OF_CHANGES (expr);
+
+ if (sched_verbose >= 6)
+ {
+ sel_print ("Moving ");
+ dump_expr (expr);
+ sel_print (" through %d: ", INSN_UID (insn));
+ }
+
+ FOR_EACH_VEC_ELT (expr_history_def, vect, i, hist)
+ if (hist->uid == insn_uid)
+ {
+ if (vinsn_equal_p (EXPR_VINSN (expr), hist->old_expr_vinsn))
+ {
+ switch (hist->type)
+ {
+ case TRANS_SPECULATION:
+ EXPR_SPEC_DONE_DS (expr) = hist->new_spec_ds;
+ /* Fallthru. */
+ case TRANS_SUBSTITUTION:
+ change_vinsn_in_expr (expr, hist->new_expr_vinsn);
+ break;
+ default:
+ gcc_unreachable ();
+ }
+
+ if (EXPR_LHS (expr) != orig_expr_lhs && expr_dest_reg (expr))
+ replace_dest_with_reg_in_expr (expr, orig_expr_lhs);
+
+ if (sched_verbose >= 6)
+ {
+ sel_print ("changed (redoing): ");
+ dump_expr (expr);
+ sel_print ("\n");
+ }
+ return;
+ }
+ else
+ {
+ /* We cannot assert the following; consider:
+ r1 = r3;
+ r2 = r3;
+ r4 = r1;
+ r5 = r2;
+ We choose to schedule r4 = r3, find it at r4 = r1, and
+ attempt to redo transformation on r2 = r3, which was recorded,
+ because r5 = r2 was moved through it and unified afterwards. */
+ /* gcc_assert (vinsn_equal_p (EXPR_VINSN (expr), hist->new_expr_vinsn)); */
+ break;
+ }
+ }
+ if (sched_verbose >= 6)
+ sel_print ("unchanged (redoing)\n");
+}
+
/* Called on the backward stage of recursion to call moveup_expr for insn
and sparams->c_expr. */
static void
move_op_ascend (insn_t insn, void *static_params)
{
- enum MOVEUP_EXPR_CODE res;
moveop_static_params_p sparams = (moveop_static_params_p) static_params;
if (! INSN_NOP_P (insn))
- {
- res = moveup_expr_cached (sparams->c_expr, insn, false);
- gcc_assert (res != MOVEUP_EXPR_NULL);
- }
+ redo_transformations (sparams->c_expr, insn);
/* Update liveness for this insn as it was invalidated. */
update_liveness_on_insn (insn);
More information about the Gcc-patches
mailing list