From patchwork Wed Oct 26 17:26:56 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Alexander Monakov X-Patchwork-Id: 121950 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 75475B6F84 for ; Thu, 27 Oct 2011 04:27:18 +1100 (EST) Received: (qmail 1941 invoked by alias); 26 Oct 2011 17:27:16 -0000 Received: (qmail 1920 invoked by uid 22791); 26 Oct 2011 17:27:14 -0000 X-SWARE-Spam-Status: No, hits=-2.0 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; Wed, 26 Oct 2011 17:26:58 +0000 Received: from ispserv.ispras.ru (ispserv.ispras.ru [83.149.198.72]) by smtp.ispras.ru (Postfix) with ESMTP id 713125D4034; Wed, 26 Oct 2011 21:12:04 +0400 (MSD) Received: from monoid.intra.ispras.ru (winnie.ispras.ru [83.149.198.236]) by ispserv.ispras.ru (Postfix) with ESMTP id AF8CD3FC48; Wed, 26 Oct 2011 21:26:56 +0400 (MSD) Date: Wed, 26 Oct 2011 21:26:56 +0400 (MSD) From: Alexander Monakov To: gcc-patches@gcc.gnu.org cc: "Vladimir N. Makarov" Subject: Re: [PATCH 1/3] Transformation replay mechanism In-Reply-To: Message-ID: References: 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 (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 * 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);