From patchwork Tue May 31 12:25:12 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bernd Schmidt X-Patchwork-Id: 98025 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 A3EC2B6F74 for ; Tue, 31 May 2011 22:25:40 +1000 (EST) Received: (qmail 1946 invoked by alias); 31 May 2011 12:25:38 -0000 Received: (qmail 1926 invoked by uid 22791); 31 May 2011 12:25:36 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail.codesourcery.com (HELO mail.codesourcery.com) (38.113.113.100) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 31 May 2011 12:25:18 +0000 Received: (qmail 1947 invoked from network); 31 May 2011 12:25:16 -0000 Received: from unknown (HELO ?84.152.158.122?) (bernds@127.0.0.2) by mail.codesourcery.com with ESMTPA; 31 May 2011 12:25:16 -0000 Message-ID: <4DE4DE28.20006@codesourcery.com> Date: Tue, 31 May 2011 14:25:12 +0200 From: Bernd Schmidt User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110516 Lightning/1.0b3pre Thunderbird/3.1.10 MIME-Version: 1.0 To: GCC Patches Subject: Scheduler tweaks relating to speculation 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 I'm working on a patch to allow the scheduler to move more insns backwards across a jump by using predication. Currently I'm using a slightly extended form of the speculation support, adding another bit to TODO_SPEC. The following preliminary patch makes a few changes in that area in preparation, and also cleans up a few things: * Remove pointless use of "*ts", replace with computing a local variable and storing it in TODO_SPEC when done. * TODO_SPEC can have only three forms, either it is zero, or HARD_DEP, or it contains bits in SPECULATIVE (but not HARD_DEP). The current code sometimes goes through logical operations to compute a known value, HARD_DEP or zero. I found that hard to read and understand initially, so I've changed it. * New function dep_spec_p which decides which of the lists a dep should be on. * Allow insns to be scheduled before all their dependencies are resolved (i.e. don't crash when freeing the deps). * Using that, don't delete deps for debug insns, resolve them instead, and remove the big pointless comment about how we're not freeing dependencies during scheduling. This is intended for later improving backtracking in the presence of debug insns. * When not using USE_DEPS_LIST (why aren't we using it always?) or DO_SPECULATION, we should use zero to initialize DEP_STATUS, so that there aren't any bits in SPECULATIVE. Bootstrapped and tested on i686-linux. I've also built a cross-compiler to ia64-linux to verify that generated code is identical (using both -O2 and -O2 -fselective-scheduling -fselective-scheduling2). Ok? Bernd * haifa-sched.c (schedule_insns): Don't delete debug insn dependencies, resolve them normally. Remove outdated comment. (schedule_block): When computing a known value for TODO_SPEC, just set it rather than using logical operations. (try_ready): Likewise. Use a local variable rather than a pointer to TODO_SPEC. Reorder an if statement to move the easy case to the then block. * sched-deps.c (dep_spec_p): New static function. (update_dep): Use it to decide whether to call change_spec_dep_to_hard. (get_back_and_forw_lists): Use it. (sd_resolve_dep): Likewise. (init_dep): If !USE_DEPS_LIST, use zero to initialize status. (haifa_note_mem_dep): Likewise. (check_dep): Likewise. (sd_add_dep): Also clear SPECULATIVE bits if not DO_SPECULATION. (sched_free_deps): Free in two passes. Index: trunk/gcc/haifa-sched.c =================================================================== --- trunk.orig/gcc/haifa-sched.c +++ trunk/gcc/haifa-sched.c @@ -1722,10 +1722,7 @@ schedule_insn (rtx insn) } INSN_REG_USE_LIST (dbg) = NULL; - /* We delete rather than resolve these deps, otherwise we - crash in sched_free_deps(), because forward deps are - expected to be released before backward deps. */ - sd_delete_dep (sd_it); + sd_resolve_dep (sd_it); } gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE); @@ -1778,18 +1775,6 @@ schedule_insn (rtx insn) } } - /* This is the place where scheduler doesn't *basically* need backward and - forward dependencies for INSN anymore. Nevertheless they are used in - heuristics in rank_for_schedule (), early_queue_to_ready () and in - some targets (e.g. rs6000). Thus the earliest place where we *can* - remove dependencies is after targetm.sched.finish () call in - schedule_block (). But, on the other side, the safest place to remove - dependencies is when we are finishing scheduling entire region. As we - don't generate [many] dependencies during scheduling itself, we won't - need memory until beginning of next region. - Bottom line: Dependencies are removed for all insns in the end of - scheduling the region. */ - /* Annotate the instruction with issue information -- TImode indicates that the instruction is expected not to be able to issue on the same cycle as the previous insn. A machine @@ -3217,7 +3202,7 @@ schedule_block (basic_block *target_bb) /* We normally get here only if we don't want to move insn from the split block. */ { - TODO_SPEC (insn) = (TODO_SPEC (insn) & ~SPECULATIVE) | HARD_DEP; + TODO_SPEC (insn) = HARD_DEP; goto restart_choose_ready; } @@ -3292,7 +3277,7 @@ schedule_block (basic_block *target_bb) x = ready_element (&ready, i); QUEUE_INDEX (x) = QUEUE_NOWHERE; - TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP; + TODO_SPEC (x) = HARD_DEP; } if (q_size) @@ -3305,7 +3290,7 @@ schedule_block (basic_block *target_bb) x = XEXP (link, 0); QUEUE_INDEX (x) = QUEUE_NOWHERE; - TODO_SPEC (x) = (TODO_SPEC (x) & ~SPECULATIVE) | HARD_DEP; + TODO_SPEC (x) = HARD_DEP; } free_INSN_LIST_list (&insn_queue[i]); } @@ -3721,10 +3706,9 @@ static int haifa_speculate_insn (rtx, ds int try_ready (rtx next) { - ds_t old_ts, *ts; + ds_t old_ts, new_ts; - ts = &TODO_SPEC (next); - old_ts = *ts; + old_ts = TODO_SPEC (next); gcc_assert (!(old_ts & ~(SPECULATIVE | HARD_DEP)) && ((old_ts & HARD_DEP) @@ -3732,22 +3716,15 @@ try_ready (rtx next) if (sd_lists_empty_p (next, SD_LIST_BACK)) /* NEXT has all its dependencies resolved. */ - { - /* Remove HARD_DEP bit from NEXT's status. */ - *ts &= ~HARD_DEP; - - if (current_sched_info->flags & DO_SPECULATION) - /* Remove all speculative bits from NEXT's status. */ - *ts &= ~SPECULATIVE; - } + new_ts = 0; else { /* One of the NEXT's dependencies has been resolved. Recalculate NEXT's status. */ - *ts &= ~SPECULATIVE & ~HARD_DEP; - - if (sd_lists_empty_p (next, SD_LIST_HARD_BACK)) + if (!sd_lists_empty_p (next, SD_LIST_HARD_BACK)) + new_ts = HARD_DEP; + else /* Now we've got NEXT with speculative deps only. 1. Look at the deps to see what we have to do. 2. Check if we can do 'todo'. */ @@ -3756,6 +3733,8 @@ try_ready (rtx next) dep_t dep; bool first_p = true; + new_ts = 0; + FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep) { ds_t ds = DEP_STATUS (dep) & SPECULATIVE; @@ -3768,25 +3747,23 @@ try_ready (rtx next) { first_p = false; - *ts = ds; + new_ts = ds; } else - *ts = ds_merge (*ts, ds); + new_ts = ds_merge (new_ts, ds); } - if (ds_weak (*ts) < spec_info->data_weakness_cutoff) + if (ds_weak (new_ts) < spec_info->data_weakness_cutoff) /* Too few points. */ - *ts = (*ts & ~SPECULATIVE) | HARD_DEP; + new_ts = HARD_DEP; } - else - *ts |= HARD_DEP; } - if (*ts & HARD_DEP) - gcc_assert (*ts == old_ts + if (new_ts & HARD_DEP) + gcc_assert (new_ts == HARD_DEP && new_ts == old_ts && QUEUE_INDEX (next) == QUEUE_NOWHERE); else if (current_sched_info->new_ready) - *ts = current_sched_info->new_ready (next, *ts); + new_ts = current_sched_info->new_ready (next, new_ts); /* * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might have its original pattern or changed (speculative) one. This is due @@ -3794,29 +3771,29 @@ try_ready (rtx next) * But if (old_ts & SPECULATIVE), then we are pretty sure that insn has speculative pattern. - We can't assert (!(*ts & HARD_DEP) || *ts == old_ts) here because + We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because control-speculative NEXT could have been discarded by sched-rgn.c (the same case as when discarded by can_schedule_ready_p ()). */ - if ((*ts & SPECULATIVE) - /* If (old_ts == *ts), then (old_ts & SPECULATIVE) and we don't + if ((new_ts & SPECULATIVE) + /* If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't need to change anything. */ - && *ts != old_ts) + && new_ts != old_ts) { int res; rtx new_pat; - gcc_assert ((*ts & SPECULATIVE) && !(*ts & ~SPECULATIVE)); + gcc_assert (!(new_ts & ~SPECULATIVE)); - res = haifa_speculate_insn (next, *ts, &new_pat); + res = haifa_speculate_insn (next, new_ts, &new_pat); switch (res) { case -1: /* It would be nice to change DEP_STATUS of all dependences, - which have ((DEP_STATUS & SPECULATIVE) == *ts) to HARD_DEP, + which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP, so we won't reanalyze anything. */ - *ts = (*ts & ~SPECULATIVE) | HARD_DEP; + new_ts = HARD_DEP; break; case 0: @@ -3840,14 +3817,16 @@ try_ready (rtx next) } } - /* We need to restore pattern only if (*ts == 0), because otherwise it is - either correct (*ts & SPECULATIVE), - or we simply don't care (*ts & HARD_DEP). */ + /* We need to restore pattern only if (new_ts == 0), because otherwise it is + either correct (new_ts & SPECULATIVE), + or we simply don't care (new_ts & HARD_DEP). */ gcc_assert (!ORIG_PAT (next) || !IS_SPECULATION_BRANCHY_CHECK_P (next)); - if (*ts & HARD_DEP) + TODO_SPEC (next) = new_ts; + + if (new_ts & HARD_DEP) { /* We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because control-speculative NEXT could have been discarded by sched-rgn.c @@ -3857,7 +3836,8 @@ try_ready (rtx next) change_queue_index (next, QUEUE_NOWHERE); return -1; } - else if (!(*ts & BEGIN_SPEC) && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next)) + else if (!(new_ts & BEGIN_SPEC) + && ORIG_PAT (next) && !IS_SPECULATION_CHECK_P (next)) /* We should change pattern of every previously speculative instruction - and we determine if NEXT was speculative by using ORIG_PAT field. Except one case - speculation checks have ORIG_PAT @@ -3869,18 +3849,16 @@ try_ready (rtx next) if (sched_verbose >= 2) { - int s = TODO_SPEC (next); - fprintf (sched_dump, ";;\t\tdependencies resolved: insn %s", (*current_sched_info->print_insn) (next, 0)); if (spec_info && spec_info->dump) { - if (s & BEGIN_DATA) + if (new_ts & BEGIN_DATA) fprintf (spec_info->dump, "; data-spec;"); - if (s & BEGIN_CONTROL) + if (new_ts & BEGIN_CONTROL) fprintf (spec_info->dump, "; control-spec;"); - if (s & BE_IN_CONTROL) + if (new_ts & BE_IN_CONTROL) fprintf (spec_info->dump, "; in-control-spec;"); } Index: trunk/gcc/sched-deps.c =================================================================== --- trunk.orig/gcc/sched-deps.c +++ trunk/gcc/sched-deps.c @@ -120,7 +120,7 @@ init_dep (dep_t dep, rtx pro, rtx con, e if ((current_sched_info->flags & USE_DEPS_LIST)) ds = dk_to_ds (kind); else - ds = -1; + ds = 0; init_dep_1 (dep, pro, con, kind, ds); } @@ -413,6 +413,16 @@ clear_deps_list (deps_list_t l) while (1); } +/* Decide whether a dependency should be treated as a hard or a speculative + dependency. */ +static bool +dep_spec_p (dep_t dep) +{ + if (current_sched_info->flags & DO_SPECULATION) + return (DEP_STATUS (dep) & SPECULATIVE) != 0; + return false; +} + static regset reg_pending_sets; static regset reg_pending_clobbers; static regset reg_pending_uses; @@ -1063,6 +1073,7 @@ update_dep (dep_t dep, dep_t new_dep, { enum DEPS_ADJUST_RESULT res = DEP_PRESENT; enum reg_note old_type = DEP_TYPE (dep); + bool was_spec = dep_spec_p (dep); /* If this is a more restrictive type of dependence than the existing one, then change the existing dependence to this @@ -1081,20 +1092,13 @@ update_dep (dep_t dep, dep_t new_dep, ds_t new_status = ds | dep_status; if (new_status & SPECULATIVE) - /* Either existing dep or a dep we're adding or both are - speculative. */ { + /* Either existing dep or a dep we're adding or both are + speculative. */ if (!(ds & SPECULATIVE) || !(dep_status & SPECULATIVE)) /* The new dep can't be speculative. */ - { - new_status &= ~SPECULATIVE; - - if (dep_status & SPECULATIVE) - /* The old dep was speculative, but now it - isn't. */ - change_spec_dep_to_hard (sd_it); - } + new_status &= ~SPECULATIVE; else { /* Both are speculative. Merge probabilities. */ @@ -1119,6 +1123,10 @@ update_dep (dep_t dep, dep_t new_dep, } } + if (was_spec && !dep_spec_p (dep)) + /* The old dep was speculative, but now it isn't. */ + change_spec_dep_to_hard (sd_it); + if (true_dependency_cache != NULL && res == DEP_CHANGED) update_dependency_caches (dep, old_type); @@ -1219,8 +1227,7 @@ get_back_and_forw_lists (dep_t dep, bool if (!resolved_p) { - if ((current_sched_info->flags & DO_SPECULATION) - && (DEP_STATUS (dep) & SPECULATIVE)) + if (dep_spec_p (dep)) *back_list_ptr = INSN_SPEC_BACK_DEPS (con); else *back_list_ptr = INSN_HARD_BACK_DEPS (con); @@ -1247,8 +1254,8 @@ sd_add_dep (dep_t dep, bool resolved_p) gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem); - if ((current_sched_info->flags & DO_SPECULATION) - && !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep))) + if ((current_sched_info->flags & DO_SPECULATION) == 0 + || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep))) DEP_STATUS (dep) &= ~SPECULATIVE; copy_dep (DEP_NODE_DEP (n), dep); @@ -1288,8 +1295,7 @@ sd_resolve_dep (sd_iterator_def sd_it) rtx pro = DEP_PRO (dep); rtx con = DEP_CON (dep); - if ((current_sched_info->flags & DO_SPECULATION) - && (DEP_STATUS (dep) & SPECULATIVE)) + if (dep_spec_p (dep)) move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con), INSN_RESOLVED_BACK_DEPS (con)); else @@ -1682,7 +1688,7 @@ haifa_note_mem_dep (rtx mem, rtx pending dep_def _dep, *dep = &_dep; init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds), - current_sched_info->flags & USE_DEPS_LIST ? ds : -1); + current_sched_info->flags & USE_DEPS_LIST ? ds : 0); maybe_add_or_update_dep_1 (dep, false, pending_mem, mem); } @@ -3489,18 +3495,23 @@ sched_free_deps (rtx head, rtx tail, boo rtx insn; rtx next_tail = NEXT_INSN (tail); + /* We make two passes since some insns may be scheduled before its + dependencies are resolved. */ for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) if (INSN_P (insn) && INSN_LUID (insn) > 0) { - /* Clear resolved back deps together with its dep_nodes. */ - delete_dep_nodes_in_back_deps (insn, resolved_p); - /* Clear forward deps and leave the dep_nodes to the corresponding back_deps list. */ if (resolved_p) clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn)); else clear_deps_list (INSN_FORW_DEPS (insn)); + } + for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) + if (INSN_P (insn) && INSN_LUID (insn) > 0) + { + /* Clear resolved back deps together with its dep_nodes. */ + delete_dep_nodes_in_back_deps (insn, resolved_p); sd_finish_insn (insn); } @@ -4141,7 +4152,7 @@ check_dep (dep_t dep, bool relaxed_p) if (!(current_sched_info->flags & USE_DEPS_LIST)) { - gcc_assert (ds == -1); + gcc_assert (ds == 0); return; }