From patchwork Thu Nov 17 13:34:02 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Monakov X-Patchwork-Id: 126219 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id E7909B7205 for ; Fri, 18 Nov 2011 00:34:28 +1100 (EST) Received: (qmail 16993 invoked by alias); 17 Nov 2011 13:34:24 -0000 Received: (qmail 16687 invoked by uid 22791); 17 Nov 2011 13:34:21 -0000 X-SWARE-Spam-Status: No, hits=-2.4 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD, TW_CF X-Spam-Check-By: sourceware.org Received: from smtp.ispras.ru (HELO smtp.ispras.ru) (83.149.198.202) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 17 Nov 2011 13:34:04 +0000 Received: from ispserv.ispras.ru (ispserv.ispras.ru [83.149.198.72]) by smtp.ispras.ru (Postfix) with ESMTP id DCBFE5D4042; Thu, 17 Nov 2011 16:17:36 +0300 (MSK) Received: from monoid.intra.ispras.ru (winnie.ispras.ru [83.149.198.236]) by ispserv.ispras.ru (Postfix) with ESMTP id 552583FC48; Thu, 17 Nov 2011 16:34:02 +0300 (MSK) Date: Thu, 17 Nov 2011 17:34:02 +0400 (MSK) From: Alexander Monakov To: Andrey Belevantsev cc: gcc-patches@gcc.gnu.org, "Vladimir N. Makarov" Subject: Re: [PATCH 1/3] Transformation replay mechanism In-Reply-To: <4EC2177F.2020406@ispras.ru> Message-ID: References: <4EC2177F.2020406@ispras.ru> User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org On Tue, 15 Nov 2011, Andrey Belevantsev wrote: > > 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 > > @@ -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)); > Why do we need this? Upon returning from move_exprs_to_boundary (in > schedule_expr_on_boundary), we immediately call clear_expr on c_expr which in > turn calls free_history_vect. So the history vector would be cleared anyways, > no? In this case we don't have to export free_history_vect, too. Indeed, thanks for noticing this. Updated patch below (retested on amd64-linux). 2011-11-17 Alexander Monakov * sel-sched-ir.c (free_history_vect): Remove unneeded declaration. (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): Declare. (insert_in_history_vect): Adjust prototype. * sel-sched.c (undo_transformations): Adjust. (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 a4fb9ac..d394019 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); @@ -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 @@ -1803,7 +1805,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 ede08e4..0a428f0 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; @@ -1538,6 +1541,7 @@ 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 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); @@ -1548,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 2af01ae..3cabfdd 100644 --- a/gcc/sel-sched.c +++ b/gcc/sel-sched.c @@ -1959,7 +1959,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; @@ -2403,7 +2403,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); @@ -2558,7 +2558,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) @@ -5993,6 +5993,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) @@ -6143,19 +6144,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);