This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[sel-sched] Add tracking of changes happened with an expression
- From: Andrey Belevantsev <abel at ispras dot ru>
- To: GCC Patches <gcc-patches at gcc dot gnu dot org>
- Date: Fri, 28 Dec 2007 14:45:46 +0300
- Subject: [sel-sched] Add tracking of changes happened with an expression
Hello,
This patch is an initial attempt in tracking a history of changes of an
expression. For each expression, we save its old form in case when a
transformation has been applied to it. When undoing transformations, we
avoid extra work by just retrieving the old vinsn from the history
vector. In case of speculation, we also save the old speculative
status, as this is the only thing we need for undoing.
The tricky part is that we can remove the instruction on which an
expression has been previously changed. In this case, we have to undo
the transformation on a bookkeeping copy. We keep a bitmap of original
insns in bookkeeping copies for this purpose.
Committed to sel-sched branch.
Andrey
2007-12-28 Andrey Belevantsev <abel@ispras.ru>
* config/ia64/ia64.c (ia64_speculate_insn): Use ds_get_speculation_types
when determining whether we need to change the pattern.
* sched-int.h (LUID_BY_UID): New accessor macro.
* sched-rgn.c (compute_block_dependences): Do not call add_branch_dependences
for selective scheduling.
(free_rgn_deps): Tidy.
* sel-sched-ir.c (vinsn_attach, vinsn_detach): Export.
(find_in_hash_vect{,_1}): Rename to find_in_history_vect{,_1}.
Rewrite to use a history vector.
(insert_in_hash_vect): Likewise. Rename to insert_in_history_vect.
(init_expr): Change CHANGED_ON parameter to be a history vector.
Update all callers.
(merge_expr_data): Update for history vectors.
(clear_expr): Likewise.
(free_first_time_insn_data): Handle INSN_ORIGINATORS.
(is_ineligible_successor): Do not check the path for back edges.
(bb_ends_ebb_p, clear_outdated_rtx_info): Tidy.
* sel-sched-ir.h (enum local_trans_type): New.
(struct expr_history_def_1, expr_history_def): New.
(struct _expr): Rename changed_on_insns vector to history_of_changes.
Make it of expr_history_def type.
(EXPR_CHANGED_ON_INSNS): Rename to EXPR_HISTORY_OF_CHANGES.
(struct _sel_insn_data): Fix comments. New field originators.
(SID_BY_UID, INSN_ORIGINATORS, INSN_ORIGINATORS_BY_UID): New accessor
macros.
* sel-sched.c (un_substitute): Mark as unused.
(apply_spec_to_expr): Inline to ...
(speculate_expr): ... here. Change return value to int.
Do not copy a pattern when no changes were made.
(un_speculate): Mark as unused.
(undo_transformations): Perform unspeculation and unsubstitution
by looking into the history vector.
(moveup_rhs): Add PTRANS_TYPE parameter, adjust all callers. Return
the type of transformation being done. Assert that we don't do
speculation and substitution on the same insn.
(moveup_set_rhs): Record the performed transformation into the history
vector of an expression.
(current_copies, current_originators): New static variables.
(generate_bookkeeping_insn): Record the generated insn in
current_copies. Always set SCHED_TIMES of a bookkeeping insn to 0.
(fill_insns): Clear current_* bitmaps before move_op.
When some bookkeeping insns were generated, allocate INSN_ORIGINATORS
for them and set it to the copy of current_originators.
(move_op): Add dest parameter. Pass it explicitly instead of
calculating from original operations. When an original insn was
found, adjust current_copies and current_originators accordingly.
(sel_region_init): Initialize current_* bitmaps.
(sel_region_finish): Free them.
Index: gcc/sel-sched.c
===================================================================
--- gcc/sel-sched.c (revision 131205)
+++ gcc/sel-sched.c (working copy)
@@ -226,10 +226,11 @@ static int stat_substitutions_total;
static bool rtx_search (rtx, rtx);
static int sel_rank_for_schedule (const void *, const void *);
static bool equal_after_moveup_path_p (rhs_t, ilist_t, rhs_t);
+static rtx get_dest_from_orig_ops (av_set_t);
static basic_block generate_bookkeeping_insn (rhs_t, insn_t, edge, edge);
static bool find_used_regs (insn_t, av_set_t, regset, struct reg_rename *,
def_list_t *);
-static bool move_op (insn_t, av_set_t, ilist_t, edge, edge, expr_t);
+static bool move_op (insn_t, av_set_t, ilist_t, edge, edge, rtx, expr_t);
static void sel_sched_region_1 (void);
static void sel_sched_region_2 (sel_sched_region_2_data_t);
@@ -517,7 +518,7 @@ rtx_search (rtx what, rtx where)
/* if INSN is a copy x:=y and if there is an rhs r in AV that uses y,
it adds all variants of r to AV derived by replacing one or more
occurrences of y by x. */
-static void
+ATTRIBUTE_UNUSED static void
un_substitute (rhs_t rhs, rtx insn, av_set_t *new_set_ptr)
{
rtx pat, src_reg, dst_reg;
@@ -1468,7 +1469,7 @@ find_best_reg_for_rhs (rhs_t rhs, blist_
/* Flag to enable / disable ia64 speculation. */
static bool sel_speculation_p = true;
-static bool speculate_expr (expr_t, ds_t);
+static int speculate_expr (expr_t, ds_t);
static ds_t get_spec_check_type_for_insn (insn_t, expr_t);
/* Return true if dependence described by DS can be overcomed. */
@@ -1579,14 +1580,20 @@ create_speculation_check (expr_t c_rhs,
return insn;
}
-/* Try to transform EXPR to data speculative version. Return true on
- success. */
-static bool
-apply_spec_to_expr (expr_t expr, ds_t ds)
+/* Try to make EXPR speculative. Return true when EXPR's pattern
+ had to be changed. */
+static int
+speculate_expr (expr_t expr, ds_t ds)
{
int res;
rtx orig_insn_rtx;
rtx spec_pat;
+ ds_t target_ds, current_ds;
+
+ /* Obtain the status we need to put on EXPR. */
+ target_ds = (ds & SPECULATIVE);
+ current_ds = EXPR_SPEC_DONE_DS (expr);
+ ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
orig_insn_rtx = EXPR_INSN_RTX (expr);
@@ -1595,10 +1602,9 @@ apply_spec_to_expr (expr_t expr, ds_t ds
switch (res)
{
case 0:
- spec_pat = copy_rtx (PATTERN (orig_insn_rtx));
-
- /* FALLTHRU */
-
+ EXPR_SPEC_DONE_DS (expr) = ds;
+ return 0;
+
case 1:
{
rtx spec_insn_rtx = create_insn_rtx_from_pattern (spec_pat, NULL_RTX);
@@ -1609,45 +1615,22 @@ apply_spec_to_expr (expr_t expr, ds_t ds
/* Do not allow clobbering the address register of speculative
insns. */
- if (res == 1
- && bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
- expr_dest_regno (expr)))
+ if (bitmap_bit_p (VINSN_REG_USES (EXPR_VINSN (expr)),
+ expr_dest_regno (expr)))
EXPR_TARGET_AVAILABLE (expr) = false;
- return true;
+ return 1;
}
case -1:
- return false;
+ return -1;
default:
gcc_unreachable ();
- return false;
+ return -1;
}
}
-/* Try to make EXPR speculative and on success remove from DSP those
- dependencies that were overcame. Return true on success. */
-static bool
-speculate_expr (expr_t expr, ds_t ds)
-{
- ds_t target_ds = (ds & SPECULATIVE);
- ds_t current_ds = EXPR_SPEC_DONE_DS (expr);
- ds_t combined_ds = ds_full_merge (current_ds, target_ds, NULL_RTX, NULL_RTX);
-
- /* ??? Do not allow both kind of speculations when pipelining. */
- if (pipelining_p
- && (combined_ds & DATA_SPEC)
- && (combined_ds & CONTROL_SPEC))
- return false;
-
- if (apply_spec_to_expr (expr, combined_ds))
- /* We already have all necessary speculations. */
- return true;
-
- return false;
-}
-
/* Return true if there is a speculative dependence between INSN and EXPR. */
static ds_t
has_spec_dependence_p (expr_t expr, insn_t insn)
@@ -1672,7 +1655,7 @@ has_spec_dependence_p (expr_t expr, insn
/* Record speculations that EXPR should perform in order to be moved through
INSN. */
-static void
+ATTRIBUTE_UNUSED static void
un_speculate (expr_t expr, insn_t insn)
{
ds_t expr_spec_done_ds;
@@ -1724,7 +1707,6 @@ undo_transformations (av_set_t *av_ptr,
{
av_set_iterator av_iter;
rhs_t rhs;
- unsigned hash;
av_set_t new_set = NULL;
/* First, kill any RHS that uses registers set by an insn. This is
@@ -1743,21 +1725,64 @@ undo_transformations (av_set_t *av_ptr,
av_set_iter_remove (&av_iter);
}
- hash = VINSN_HASH (INSN_VINSN (insn));
/* FIXME: we need to determine whether RHS was changed on this insn
just once. */
FOR_EACH_RHS (rhs, av_iter, *av_ptr)
{
- if (find_in_hash_vect (EXPR_CHANGED_ON_INSNS (rhs), hash) >= 0)
- un_speculate (rhs, insn);
+ int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (rhs),
+ insn, EXPR_VINSN (rhs), true);
+
+ if (index >= 0 && VEC_index (expr_history_def,
+ EXPR_HISTORY_OF_CHANGES (rhs),
+ index)->type == TRANS_SPECULATION)
+ {
+ ds_t old_ds, new_ds;
+
+ old_ds = VEC_index (expr_history_def,
+ EXPR_HISTORY_OF_CHANGES (rhs),
+ index)->spec_ds;
+ new_ds = EXPR_SPEC_DONE_DS (rhs);
+ gcc_assert (spec_info && sel_speculation_p
+ && new_ds
+ && (old_ds & SPECULATIVE) != (new_ds & SPECULATIVE));
+
+ old_ds &= SPECULATIVE;
+ new_ds &= SPECULATIVE;
+ new_ds &= ~old_ds;
+
+ EXPR_SPEC_TO_CHECK_DS (rhs) |= new_ds;
+ }
}
new_set = NULL;
FOR_EACH_RHS (rhs, av_iter, *av_ptr)
{
- if (find_in_hash_vect (EXPR_CHANGED_ON_INSNS (rhs), hash) >= 0)
- un_substitute (rhs, insn, &new_set);
+ int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (rhs),
+ insn, EXPR_VINSN (rhs), true);
+
+ if (index >= 0 && VEC_index (expr_history_def,
+ EXPR_HISTORY_OF_CHANGES (rhs),
+ index)->type == TRANS_SUBSTITUTION)
+ {
+ expr_def _tmp_rhs, *tmp_rhs = &_tmp_rhs;
+ vinsn_t new_vi;
+
+
+ new_vi = VEC_index (expr_history_def,
+ EXPR_HISTORY_OF_CHANGES (rhs),
+ index)->old_expr_vinsn;
+
+ gcc_assert (VINSN_SEPARABLE_P (new_vi)
+ == EXPR_SEPARABLE_P (rhs));
+
+ copy_expr (tmp_rhs, rhs);
+ change_vinsn_in_expr (tmp_rhs, new_vi);
+
+ av_set_add (&new_set, tmp_rhs);
+ clear_expr (tmp_rhs);
+ }
+
}
av_set_union_and_clear (av_ptr, &new_set);
@@ -1823,13 +1848,15 @@ moveup_rhs_inside_insn_group (rhs_t insn
&& !sel_insn_is_speculation_check (through_insn))
/* Modifies INSN_TO_MOVE_UP so it can be moved through the THROUGH_INSN,
- performing necessary transformations. When INSIDE_INSN_GROUP,
+ performing necessary transformations. Record the type of transformation
+ made in PTRANS_TYPE, when it is not NULL. When INSIDE_INSN_GROUP,
permit all dependencies except true ones, and try to remove those
too via forward substitution. All cases when a non-eliminable
non-zero cost dependency exists inside an insn group will be fixed
in tick_check_p instead. */
static enum MOVEUP_RHS_CODE
-moveup_rhs (rhs_t insn_to_move_up, insn_t through_insn, bool inside_insn_group)
+moveup_rhs (rhs_t insn_to_move_up, insn_t through_insn, bool inside_insn_group,
+ enum local_trans_type *ptrans_type)
{
vinsn_t vi = RHS_VINSN (insn_to_move_up);
insn_t insn = VINSN_INSN (vi);
@@ -1904,11 +1931,16 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
if (full_ds != 0 && can_overcome_dep_p (full_ds))
{
- if (speculate_expr (insn_to_move_up, full_ds))
- /* Speculation was successful. */
+ int res;
+
+ res = speculate_expr (insn_to_move_up, full_ds);
+ if (res >= 0)
{
- full_ds = 0;
- was_changed = true;
+ /* Speculation was successful. */
+ full_ds = 0;
+ was_changed = (res == 1);
+ if (ptrans_type)
+ *ptrans_type = TRANS_SPECULATION;
sel_clear_has_dependence ();
}
}
@@ -1953,11 +1985,16 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
if (can_overcome_dep_p (*rhs_dsp))
{
- if (speculate_expr (insn_to_move_up, *rhs_dsp))
+ int res;
+
+ res = speculate_expr (insn_to_move_up, *rhs_dsp);
+ if (res >= 0)
{
/* Speculation was successful. */
*rhs_dsp = 0;
- was_changed = true;
+ was_changed = (res == 1);
+ if (ptrans_type)
+ *ptrans_type = TRANS_SPECULATION;
}
else
return MOVEUP_RHS_NULL;
@@ -1966,27 +2003,17 @@ moveup_rhs (rhs_t insn_to_move_up, insn_
&& insn_eligible_for_subst_p (through_insn))
{
/* Substitute in vinsn. */
- line_start ();
- print ("Substituting in moveup_rhs:\nBefore: ");
- sel_print_rtl (insn);
- print ("Moving through: ");
- sel_print_rtl (through_insn);
- print ("After: ");
-
if (substitute_reg_in_rhs (insn_to_move_up, through_insn))
- {
- EXPR_WAS_SUBSTITUTED (insn_to_move_up) = true;
- sel_print_rtl (EXPR_INSN_RTX (insn_to_move_up));
- }
+ EXPR_WAS_SUBSTITUTED (insn_to_move_up) = true;
else
- {
- print ("Can't move up due to architecture constraints.\n");
- line_finish ();
- return MOVEUP_RHS_NULL;
- }
+ return MOVEUP_RHS_NULL;
+ /* ??? We cannot perform substitution AND speculation on the same
+ insn. */
+ gcc_assert (!was_changed);
was_changed = true;
- line_finish ();
+ if (ptrans_type)
+ *ptrans_type = TRANS_SUBSTITUTION;
}
else
return MOVEUP_RHS_NULL;
@@ -2018,8 +2045,11 @@ moveup_set_rhs (av_set_t *avp, insn_t in
FOR_EACH_RHS_1 (rhs, i, avp)
{
- int rhs_uid = INSN_UID (EXPR_INSN_RTX (rhs));
- bool unique_p = VINSN_UNIQUE_P (RHS_VINSN (rhs));
+ vinsn_t expr_old_vinsn = EXPR_VINSN (rhs);
+ ds_t expr_old_spec_ds = EXPR_SPEC_DONE_DS (rhs);
+ int rhs_uid = INSN_UID (VINSN_INSN (expr_old_vinsn));
+ bool unique_p = VINSN_UNIQUE_P (expr_old_vinsn);
+ enum local_trans_type trans_type;
line_start ();
dump_rhs (rhs);
@@ -2046,8 +2076,11 @@ moveup_set_rhs (av_set_t *avp, insn_t in
line_finish ();
continue;
}
-
- switch (moveup_rhs (rhs, insn, inside_insn_group))
+
+ /* ??? Invent something better than this. We can't allow old_vinsn
+ to go, we need it for the history vector. */
+ vinsn_attach (expr_old_vinsn);
+ switch (moveup_rhs (rhs, insn, inside_insn_group, &trans_type))
{
case MOVEUP_RHS_NULL:
/* Cache that there is a hard dependence. */
@@ -2063,8 +2096,10 @@ moveup_set_rhs (av_set_t *avp, insn_t in
gcc_assert (INSN_UID (EXPR_INSN_RTX (rhs)) != rhs_uid);
/* Mark that this insn changed this expr. */
- insert_in_hash_vect (&EXPR_CHANGED_ON_INSNS (rhs),
- VINSN_HASH (INSN_VINSN (insn)));
+ insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (rhs),
+ INSN_UID (insn), trans_type,
+ expr_old_vinsn, EXPR_VINSN (rhs),
+ expr_old_spec_ds);
rhs = merge_with_other_exprs (avp, &i, rhs);
print (" result: ");
@@ -2090,6 +2125,7 @@ moveup_set_rhs (av_set_t *avp, insn_t in
gcc_unreachable ();
}
+ vinsn_detach (expr_old_vinsn);
line_finish ();
}
@@ -2138,7 +2174,8 @@ equal_after_moveup_path_p_1 (rhs_t rhs,
res = true;
if (res)
- res = (moveup_rhs (rhs, ILIST_INSN (path), true) != MOVEUP_RHS_NULL);
+ res = (moveup_rhs (rhs, ILIST_INSN (path), true, NULL)
+ != MOVEUP_RHS_NULL);
return res;
}
@@ -3831,6 +3868,11 @@ find_best_expr (av_set_t *av_vliw_ptr, b
/* Functions that implement the core of the scheduler. */
+/* These bitmaps record original instructions scheduled on the current
+ iteration and bookkeeping copies created by them. */
+static bitmap current_originators = NULL;
+static bitmap current_copies = NULL;
+
/* Emit an instruction from EXPR with SEQNO after PLACE_TO_INSERT. */
static insn_t
gen_insn_from_expr_after (expr_t expr, int seqno, insn_t place_to_insert)
@@ -4075,6 +4117,10 @@ generate_bookkeeping_insn (rhs_t c_rhs,
change_vinsn_in_expr (new_expr, new_vinsn);
new_insn = gen_insn_from_expr_after (new_expr, new_seqno, place_to_insert);
+ INSN_SCHED_TIMES (new_insn) = 0;
+ bitmap_set_bit (current_copies, INSN_UID (new_insn));
+ clear_expr (new_expr);
+
/* When inserting bookkeeping insn in new block, av sets should be
following: old basic block (that now holds bookkeeping) data sets are
the same as was before generation of bookkeeping, and new basic block
@@ -4087,25 +4133,6 @@ generate_bookkeeping_insn (rhs_t c_rhs,
exchange_data_sets (BLOCK_FOR_INSN (new_insn),
BLOCK_FOR_INSN (join_point));
- /* Not obvoius. Set sched times of bookkeeping to sched times of join
- point if join point is not header of loop while pipelining (in this
- case set it to zero). This is done to correctly handle inserting of
- bookkeeping in already scheduled code: when bookkeeping is inserted in
- code not yet scheduled (including preheader when pipelining) it will
- recieve zero sched times (as join point is not scheduled)
- and when bookkeeping is inserted in scheduled code there will not be a
- gap of sched times in scheduled code, so is_ineligible_successor_p of
- path going through bookkeeping will not say that join point is
- ineligible. */
- INSN_SCHED_TIMES (new_insn) =
- (pipelining_p
- && ((flag_sel_sched_pipelining_outer_loops
- && join_point == NEXT_INSN (bb_note (EBB_FIRST_BB (1))))
- || (join_point == NEXT_INSN (bb_note (EBB_FIRST_BB (0))))))
- ? 0 : INSN_SCHED_TIMES (join_point);
-
- clear_expr (new_expr);
-
gcc_assert ((src == NULL && BB_END (bb) == new_insn
&& sel_bb_head_p (new_insn))
|| (src == NULL && control_flow_insn_p (BB_END (other_block))
@@ -4326,10 +4353,6 @@ fill_insns (fence_t fence, int seqno, il
av_set_clear (&BND_AV (bnd));
BND_AV (bnd) = compute_av_set (BND_TO (bnd), NULL, 0, true);
-#if 0
- mark_unavailable_targets
- (BND_AV (bnd), BB_LV_SET (BLOCK_FOR_INSN (BND_TO (bnd))));
-#endif
av_set_clear (&BND_AV1 (bnd));
BND_AV1 (bnd) = av_set_copy (BND_AV (bnd));
@@ -4596,12 +4619,30 @@ fill_insns (fence_t fence, int seqno, il
at before BND_TO (BND). */
n_bookkeeping_copies_before_moveop = stat_bookkeeping_copies;
max_uid_before_move_op = get_max_uid ();
+ bitmap_clear (current_copies);
+ bitmap_clear (current_originators);
- b = move_op (BND_TO (bnd), rhs_seq, NULL, NULL, NULL, c_rhs);
+ b = move_op (BND_TO (bnd), rhs_seq, NULL, NULL, NULL,
+ get_dest_from_orig_ops (rhs_seq), c_rhs);
if (stat_bookkeeping_copies > n_bookkeeping_copies_before_moveop)
stat_insns_needed_bookkeeping++;
+ {
+ unsigned book_uid;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (current_copies, 0, book_uid, bi)
+ {
+ /* We allocate these bitmaps lazily. */
+ if (! INSN_ORIGINATORS_BY_UID (book_uid))
+ INSN_ORIGINATORS_BY_UID (book_uid) = BITMAP_ALLOC (NULL);
+
+ bitmap_copy (INSN_ORIGINATORS_BY_UID (book_uid),
+ current_originators);
+ }
+ }
+
/* We should be able to find the expression we've chosen for
scheduling. */
gcc_assert (b);
@@ -4817,11 +4858,10 @@ get_dest_from_orig_ops (av_set_t orig_op
bookkeeping code in the join points. Return the current rhs. */
static bool
move_op (insn_t insn, av_set_t orig_ops, ilist_t path, edge e1, edge e2,
- rhs_t c_rhs)
+ rtx dest, rhs_t c_rhs)
{
rhs_t rhs;
bool c_rhs_inited_p;
- rtx dest;
bool generated_nop_p = false;
basic_block book_block = NULL;
@@ -4872,8 +4912,6 @@ move_op (insn_t insn, av_set_t orig_ops,
/*av_set_leave_one (&orig_ops);*/
}
- dest = get_dest_from_orig_ops (orig_ops);
-
/* Look at the insn and decide if it could be an ancestor of currently
scheduling operation. If it is so, then the insn "dest = op" could
either be replaced with "dest = reg", because REG now holds the result
@@ -4897,28 +4935,15 @@ move_op (insn_t insn, av_set_t orig_ops,
copy_expr_onside (c_rhs, INSN_EXPR (insn));
c_rhs_inited_p = true;
-
- /* When an insn we found is not equal to the insn from the orig_ops
- set, this means that we've found previously created bookeeping copy.
- We cannot return original insn in C_RHS because it was already
- scheduled, and using it would break an assert saying that
- insn should not be in stream. We need to replace it in C_RHS with
- the exact insn that we found.
-
- Our infrastructure handles this such case with setting AV_LEVEL ()
- to -1 in generate_bookkeeping_insn ().
-
- But when there is identical instructions one of which dominates the
- other we have the same assert failing. */
- if (RHS_INSN (c_rhs) != insn)
- {
- /* We now copy INSN_EXPR (insn) to C_RHS, hence the condition is
- always false. */
- gcc_unreachable ();
-
- change_vinsn_in_expr (c_rhs, INSN_VINSN (insn));
- }
+ /* This can be previously created bookkeeping copy; do not count
+ these. */
+ if (!bitmap_bit_p (current_copies, INSN_UID (insn)))
+ bitmap_set_bit (current_originators, INSN_UID (insn));
+ else
+ bitmap_clear_bit (current_copies, INSN_UID (insn));
+
+
/* For instructions we must immediately remove insn from the
stream, so subsequent update_data_sets () won't include this
insn into av_set.
@@ -5041,7 +5066,7 @@ move_op (insn_t insn, av_set_t orig_ops,
&& succ_i.e2->dest == BLOCK_FOR_INSN (succ));
}
- b = move_op (succ, orig_ops, path, succ_i.e1, succ_i.e2, x);
+ b = move_op (succ, orig_ops, path, succ_i.e1, succ_i.e2, dest, x);
if (b)
{
@@ -5052,7 +5077,7 @@ move_op (insn_t insn, av_set_t orig_ops,
dump_rhs (x);
line_finish ();
- res = moveup_rhs (x, insn, false);
+ res = moveup_rhs (x, insn, false, NULL);
gcc_assert (res != MOVEUP_RHS_NULL);
if (!c_rhs_inited_p)
@@ -5440,6 +5465,8 @@ sel_region_init (int rgn)
bitmap_clear (forced_ebb_heads);
setup_nop_vinsn ();
+ current_copies = BITMAP_ALLOC (NULL);
+ current_originators = BITMAP_ALLOC (NULL);
return false;
}
@@ -5456,9 +5483,11 @@ sel_region_finish (void)
free_nop_pool ();
- /* Free the sort vector. */
+ /* Free the vectors. */
if (vec_av_set)
VEC_free (rhs_t, heap, vec_av_set);
+ BITMAP_FREE (current_copies);
+ BITMAP_FREE (current_originators);
/* If LV_SET of the region head should be updated, do it now because
there will be no other chance. */
@@ -5772,7 +5801,7 @@ sel_sched_region_2 (sel_sched_region_2_d
else if (max_f < seqno)
max_f = seqno;
}
-
+
fences1 = fences;
do
{
Index: gcc/sel-sched-ir.c
===================================================================
--- gcc/sel-sched-ir.c (revision 131205)
+++ gcc/sel-sched-ir.c (working copy)
@@ -915,8 +915,10 @@ free_regset_pool (void)
the data sets. When update is finished, NOPs are deleted. */
static void set_insn_init (expr_t, vinsn_t, int);
+#if 0
static void vinsn_attach (vinsn_t);
static void vinsn_detach (vinsn_t);
+#endif
/* A vinsn that is used to represent a nop. This vinsn is shared among all
nops sel-sched generates. */
@@ -1376,7 +1378,7 @@ vinsn_init (vinsn_t vi, insn_t insn, boo
}
/* Indicate that VI has become the part of an rtx object. */
-static void
+void
vinsn_attach (vinsn_t vi)
{
/* Assert that VI is not pending for deletion. */
@@ -1417,7 +1419,7 @@ vinsn_delete (vinsn_t vi)
/* Indicate that VI is no longer a part of some rtx object.
Remove VI if it is no longer needed. */
-static void
+void
vinsn_detach (vinsn_t vi)
{
gcc_assert (VINSN_COUNT (vi) > 0);
@@ -1555,10 +1557,11 @@ sel_gen_insn_from_expr_after (rhs_t expr
when found. Write to INDP the index on which the search has stopped,
such that inserting HASH at INDP will retain VECT's sort order. */
static bool
-find_in_hash_vect_1 (VEC(unsigned, heap) *vect, unsigned hash, int *indp)
+find_in_history_vect_1 (VEC(expr_history_def, heap) *vect,
+ unsigned uid, vinsn_t new_vinsn, int *indp)
{
- unsigned *arr;
- int i, j, len = VEC_length (unsigned, vect);
+ expr_history_def *arr;
+ int i, j, len = VEC_length (expr_history_def, vect);
if (len == 0)
{
@@ -1566,51 +1569,51 @@ find_in_hash_vect_1 (VEC(unsigned, heap)
return false;
}
- arr = VEC_address (unsigned, vect);
+ arr = VEC_address (expr_history_def, vect);
i = 0, j = len - 1;
while (i <= j)
{
-#if 0
- int k = (i + j) / 2;
-
- if (arr[k] == hash)
- {
- *indp = k;
- return true;
- }
-
- if (arr[k] < hash)
- i = k + 1;
- else
- j = k - 1;
-#else
- unsigned ahash = arr[i];
+ unsigned auid = arr[i].uid;
+ vinsn_t avinsn = arr[i].new_expr_vinsn;
- if (ahash == hash)
+ if (auid == uid
+ && (avinsn == new_vinsn
+ || vinsns_correlate_as_rhses_p (avinsn, new_vinsn)))
{
*indp = i;
return true;
}
- else if (ahash > hash)
+ else if (auid > uid)
break;
i++;
-#endif
}
*indp = i;
return false;
}
-/* Search for a hash value HASH in a sorted vector VECT. Return
- the position found or -1, if no such value is in vector. */
+/* Search for a uid of INSN a sorted vector VECT. Return
+ the position found or -1, if no such value is in vector.
+ Search also for UIDs of insn's originators, if ORIGINATORS_P is true. */
int
-find_in_hash_vect (VEC(unsigned, heap) *vect, unsigned hash)
+find_in_history_vect (VEC(expr_history_def, heap) *vect, rtx insn,
+ vinsn_t new_vinsn, bool originators_p)
{
int ind;
- if (find_in_hash_vect_1 (vect, hash, &ind))
+ if (find_in_history_vect_1 (vect, INSN_UID (insn), new_vinsn, &ind))
return ind;
+
+ if (INSN_ORIGINATORS (insn) && originators_p)
+ {
+ unsigned uid;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (INSN_ORIGINATORS (insn), 0, uid, bi)
+ if (find_in_history_vect_1 (vect, uid, new_vinsn, &ind))
+ return ind;
+ }
return -1;
}
@@ -1618,16 +1621,40 @@ find_in_hash_vect (VEC(unsigned, heap) *
/* Insert HASH in a sorted vector pointed to by PVECT, if HASH is
not there already. */
void
-insert_in_hash_vect (VEC (unsigned, heap) **pvect, unsigned hash)
+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)
{
- VEC(unsigned, heap) *vect = *pvect;
+ VEC(expr_history_def, heap) *vect = *pvect;
+ expr_history_def temp;
+ bool res;
int ind;
- if (! find_in_hash_vect_1 (vect, hash, &ind))
+ res = find_in_history_vect_1 (vect, uid, new_expr_vinsn, &ind);
+
+ if (res)
{
- VEC_safe_insert (unsigned, heap, vect, ind, hash);
- *pvect = vect;
+ expr_history_def *phist = VEC_index (expr_history_def, vect, ind);
+
+ gcc_assert (phist->spec_ds == spec_ds
+ && (phist->old_expr_vinsn == old_expr_vinsn
+ || (phist->new_expr_vinsn != new_expr_vinsn
+ && (vinsns_correlate_as_rhses_p
+ (phist->old_expr_vinsn, old_expr_vinsn)))));
+ return;
}
+
+ temp.uid = uid;
+ temp.old_expr_vinsn = old_expr_vinsn;
+ temp.new_expr_vinsn = new_expr_vinsn;
+ temp.spec_ds = spec_ds;
+ temp.type = type;
+
+ vinsn_attach (old_expr_vinsn);
+ vinsn_attach (new_expr_vinsn);
+ VEC_safe_insert (expr_history_def, heap, vect, ind, &temp);
+ *pvect = vect;
}
/* Compare two vinsns as rhses if possible and as vinsns otherwise. */
@@ -1661,7 +1688,7 @@ static void
init_expr (expr_t expr, vinsn_t vi, int spec, int use, int priority,
int sched_times, int orig_bb_index, ds_t spec_done_ds,
ds_t spec_to_check_ds, int orig_sched_cycle,
- VEC(unsigned, heap) *changed_on, bool target_available,
+ VEC(expr_history_def, heap) *history, bool target_available,
bool was_substituted, bool was_renamed)
{
vinsn_attach (vi);
@@ -1676,10 +1703,10 @@ init_expr (expr_t expr, vinsn_t vi, int
EXPR_SPEC_DONE_DS (expr) = spec_done_ds;
EXPR_SPEC_TO_CHECK_DS (expr) = spec_to_check_ds;
- if (changed_on)
- EXPR_CHANGED_ON_INSNS (expr) = changed_on;
+ if (history)
+ EXPR_HISTORY_OF_CHANGES (expr) = history;
else
- EXPR_CHANGED_ON_INSNS (expr) = NULL;
+ EXPR_HISTORY_OF_CHANGES (expr) = NULL;
EXPR_TARGET_AVAILABLE (expr) = target_available;
EXPR_WAS_SUBSTITUTED (expr) = was_substituted;
@@ -1690,9 +1717,23 @@ init_expr (expr_t expr, vinsn_t vi, int
void
copy_expr (expr_t to, expr_t from)
{
- VEC(unsigned, heap) *temp;
+ 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++)
+ {
+ vinsn_attach (phist->old_expr_vinsn);
+ vinsn_attach (phist->new_expr_vinsn);
+ }
+ }
- temp = VEC_copy (unsigned, heap, EXPR_CHANGED_ON_INSNS (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),
@@ -1720,8 +1761,8 @@ void
merge_expr_data (expr_t to, expr_t from, bool join_point_p)
{
int i;
- unsigned hash;
-
+ expr_history_def *phist;
+
/* For now, we just set the spec of resulting rhs to be minimum of the specs
of merged rhses. */
if (RHS_SPEC (to) > RHS_SPEC (from))
@@ -1788,9 +1829,13 @@ merge_expr_data (expr_t to, expr_t from,
/* We keep this vector sorted. */
for (i = 0;
- VEC_iterate (unsigned, EXPR_CHANGED_ON_INSNS (from), i, hash);
+ VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (from),
+ i, phist);
i++)
- insert_in_hash_vect (&EXPR_CHANGED_ON_INSNS (to), hash);
+ insert_in_history_vect (&EXPR_HISTORY_OF_CHANGES (to),
+ phist->uid, phist->type,
+ phist->old_expr_vinsn, phist->new_expr_vinsn,
+ phist->spec_ds);
EXPR_WAS_SUBSTITUTED (to) |= EXPR_WAS_SUBSTITUTED (from);
EXPR_WAS_RENAMED (to) |= EXPR_WAS_RENAMED (to);
@@ -1821,9 +1866,27 @@ merge_expr (expr_t to, expr_t from, bool
void
clear_expr (rhs_t rhs)
{
+
vinsn_detach (RHS_VINSN (rhs));
RHS_VINSN (rhs) = NULL;
- VEC_free (unsigned, heap, EXPR_CHANGED_ON_INSNS (rhs));
+
+ if (EXPR_HISTORY_OF_CHANGES (rhs))
+ {
+ unsigned i;
+ expr_history_def *phist;
+
+ for (i = 0;
+ VEC_iterate (expr_history_def, EXPR_HISTORY_OF_CHANGES (rhs),
+ i, phist);
+ i++)
+ {
+ vinsn_detach (phist->old_expr_vinsn);
+ vinsn_detach (phist->new_expr_vinsn);
+ }
+
+ VEC_free (expr_history_def, heap, EXPR_HISTORY_OF_CHANGES (rhs));
+ EXPR_HISTORY_OF_CHANGES (rhs) = NULL;
+ }
}
/* For a given LV_SET, mark EXPR having unavailable target register. */
@@ -2480,6 +2543,10 @@ free_first_time_insn_data (insn_t insn)
BITMAP_FREE (INSN_ANALYZED_DEPS (insn));
BITMAP_FREE (INSN_FOUND_DEPS (insn));
+
+ /* This is allocated only for bookkeeping insns. */
+ if (INSN_ORIGINATORS (insn))
+ BITMAP_FREE (INSN_ORIGINATORS (insn));
free_deps (&INSN_DEPS_CONTEXT (insn));
}
@@ -4345,8 +4412,9 @@ is_ineligible_successor (insn_t insn, il
/* An insn from another fence could also be
scheduled earlier even if this insn is not in
a fence list right now. Check INSN_SCHED_CYCLE instead. */
- || ((!pipelining_p || !path_contains_back_edge_p (p))
- && path_contains_switch_of_sched_times_p (insn, p)))
+ || (!pipelining_p
+ && INSN_SCHED_TIMES (insn) > 0))
+
return true;
else
return false;
@@ -4364,7 +4432,7 @@ bb_ends_ebb_p (basic_block bb)
if (next_bb == EXIT_BLOCK_PTR
|| bitmap_bit_p (forced_ebb_heads, next_bb->index)
|| (LABEL_P (BB_HEAD (next_bb))
- /* NB: LABEL_NUSES () is not maintained outside of jump.c .
+ /* NB: LABEL_NUSES () is not maintained outside of jump.c.
Work around that. */
&& !single_pred_p (next_bb)))
return true;
@@ -4449,7 +4517,6 @@ clear_outdated_rtx_info (basic_block bb)
}
typedef VEC(rtx, heap) *rtx_vec_t;
-
static rtx_vec_t bb_note_pool;
/* Add BB_NOTE to the pool of available basic block notes. */
Index: gcc/sel-sched-ir.h
===================================================================
--- gcc/sel-sched-ir.h (revision 131184)
+++ gcc/sel-sched-ir.h (working copy)
@@ -78,6 +78,39 @@ typedef _xlist_t ilist_t;
#define ILIST_INSN(L) (_XLIST_X (L))
#define ILIST_NEXT(L) (_XLIST_NEXT (L))
+/* This lists possible transformations that done locally, i.e. in
+ moveup_expr. */
+enum local_trans_type
+ {
+ TRANS_SUBSTITUTION,
+ TRANS_SPECULATION
+ };
+
+/* This struct is used to record the history of expression's
+ transformations. */
+struct expr_history_def_1
+{
+ /* UID of the insn. */
+ unsigned uid;
+
+ /* How the expression looked like. */
+ vinsn_t old_expr_vinsn;
+
+ /* How the expression looks after the transformation. */
+ vinsn_t new_expr_vinsn;
+
+ /* And its speculative status. */
+ ds_t spec_ds;
+
+ /* Type of the transformation. */
+ enum local_trans_type type;
+};
+
+typedef struct expr_history_def_1 expr_history_def;
+
+DEF_VEC_O (expr_history_def);
+DEF_VEC_ALLOC_O (expr_history_def, heap);
+
/* Right hand side information. */
struct _expr
{
@@ -117,11 +150,8 @@ struct _expr
been scheduled or more than one originator. */
int orig_sched_cycle;
- /* A vector of insn's hashes on which this expr was changed when
- moving up. We can't use bitmap here, because the recorded insn
- could be scheduled, and its bookkeeping copies should be checked
- instead. */
- VEC(unsigned, heap) *changed_on_insns;
+ /* This vector contains the history of insn's transformations. */
+ VEC(expr_history_def, heap) *history_of_changes;
/* True (1) when original target (register or memory) of this instruction
is available for scheduling, false otherwise. -1 means we're not sure;
@@ -158,7 +188,7 @@ typedef expr_t rhs_t;
#define EXPR_ORIG_SCHED_CYCLE(EXPR) ((EXPR)->orig_sched_cycle)
#define EXPR_SPEC_DONE_DS(EXPR) ((EXPR)->spec_done_ds)
#define EXPR_SPEC_TO_CHECK_DS(EXPR) ((EXPR)->spec_to_check_ds)
-#define EXPR_CHANGED_ON_INSNS(EXPR) ((EXPR)->changed_on_insns)
+#define EXPR_HISTORY_OF_CHANGES(EXPR) ((EXPR)->history_of_changes)
#define EXPR_TARGET_AVAILABLE(EXPR) ((EXPR)->target_available)
#define EXPR_WAS_SUBSTITUTED(EXPR) ((EXPR)->was_substituted)
#define EXPR_WAS_RENAMED(EXPR) ((EXPR)->was_renamed)
@@ -635,14 +665,18 @@ struct _sel_insn_data
int seqno;
- /* An INSN_LUID bit is set when deps analysis result is already known. */
+ /* An INSN_UID bit is set when deps analysis result is already known. */
bitmap analyzed_deps;
- /* An INSN_LUID bit is set when a hard dep was found, not set when
+ /* An INSN_UID bit is set when a hard dep was found, not set when
no dependence is found. This is meaningful only when the analyzed_deps
bitmap has its bit set. */
bitmap found_deps;
+ /* An INSN_UID bit is set when this is a bookkeeping insn generated from
+ a parent with this uid. */
+ bitmap originators;
+
/* A context incapsulating this insn. */
struct deps deps_context;
@@ -678,6 +712,7 @@ extern VEC (sel_insn_data_def, heap) *s_
/* Accessor macros for s_i_d. */
#define SID(INSN) (VEC_index (sel_insn_data_def, s_i_d, INSN_LUID (INSN)))
+#define SID_BY_UID(UID) (VEC_index (sel_insn_data_def, s_i_d, LUID_BY_UID (UID)))
extern sel_insn_data_def insn_sid (insn_t);
@@ -686,6 +721,9 @@ extern sel_insn_data_def insn_sid (insn_
#define INSN_ANALYZED_DEPS(INSN) (SID (INSN)->analyzed_deps)
#define INSN_FOUND_DEPS(INSN) (SID (INSN)->found_deps)
#define INSN_DEPS_CONTEXT(INSN) (SID (INSN)->deps_context)
+#define INSN_ORIGINATORS(INSN) (SID (INSN)->originators)
+#define INSN_ORIGINATORS_BY_UID(UID) (SID_BY_UID (UID)->originators)
+
#define INSN_EXPR(INSN) (&SID (INSN)->_expr)
#define INSN_VINSN(INSN) (RHS_VINSN (INSN_EXPR (INSN)))
@@ -934,6 +972,9 @@ extern int sel_vinsn_cost (vinsn_t);
extern insn_t sel_gen_insn_from_rtx_after (rtx, expr_t, int, insn_t);
extern insn_t sel_gen_recovery_insn_from_rtx_after (rtx, expr_t, int, insn_t);
extern insn_t sel_gen_insn_from_expr_after (expr_t, int, insn_t);
+extern void vinsn_attach (vinsn_t);
+extern void vinsn_detach (vinsn_t);
+
/* RHS functions. */
extern bool vinsns_correlate_as_rhses_p (vinsn_t, vinsn_t);
@@ -944,8 +985,11 @@ extern void merge_expr (expr_t, expr_t,
extern void clear_expr (expr_t);
extern unsigned expr_dest_regno (expr_t);
extern rtx expr_dest_reg (expr_t);
-extern int find_in_hash_vect (VEC(unsigned, heap) *, unsigned);
-extern void insert_in_hash_vect (VEC(unsigned, heap) **, unsigned);
+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);
extern void mark_unavailable_targets (av_set_t, av_set_t, regset);
/* Av set functions. */
Index: gcc/sched-int.h
===================================================================
--- gcc/sched-int.h (revision 131205)
+++ gcc/sched-int.h (working copy)
@@ -129,6 +129,8 @@ extern regset *glat_start, *glat_end;
structures should be indexed by luid. */
extern VEC (int, heap) *sched_luids;
#define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN)))
+#define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID))
+
#define SET_INSN_LUID(INSN, LUID) \
(VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID)))
Index: gcc/sched-rgn.c
===================================================================
--- gcc/sched-rgn.c (revision 131205)
+++ gcc/sched-rgn.c (working copy)
@@ -2615,7 +2615,9 @@ compute_block_dependences (int bb)
}
#endif
- add_branch_dependences (head, tail);
+ /* Selective scheduling handles control dependencies by itself. */
+ if (!SEL_SCHED_P)
+ add_branch_dependences (head, tail);
if (current_nr_blocks > 1)
propagate_deps (bb, &tmp_deps);
@@ -2767,7 +2769,6 @@ free_rgn_deps (void)
{
int bb;
-
for (bb = 0; bb < current_nr_blocks; bb++)
{
rtx head, tail;
Index: gcc/config/ia64/ia64.c
===================================================================
--- gcc/config/ia64/ia64.c (revision 131205)
+++ gcc/config/ia64/ia64.c (working copy)
@@ -7519,7 +7519,7 @@ ia64_speculate_insn (rtx insn, ds_t ts,
point operation that might trap. */
return -1;
- if (ia64_get_insn_spec_ds (insn) == ts)
+ if (ia64_get_insn_spec_ds (insn) == ds_get_speculation_types (ts))
res = 0;
else
{