From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 117491 invoked by alias); 23 Sep 2015 22:09:26 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 117482 invoked by uid 89); 23 Sep 2015 22:09:25 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=0.1 required=5.0 tests=AWL,BAYES_50,KAM_LAZY_DOMAIN_SECURITY,RP_MATCHES_RCVD autolearn=no version=3.3.2 X-HELO: gcc1-power7.osuosl.org Received: from gcc1-power7.osuosl.org (HELO gcc1-power7.osuosl.org) (140.211.15.137) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with (AES256-GCM-SHA384 encrypted) ESMTPS; Wed, 23 Sep 2015 22:09:24 +0000 Received: from gcc1-power7.osuosl.org (localhost [127.0.0.1]) by gcc1-power7.osuosl.org (8.14.6/8.14.6) with ESMTP id t8NM9ML1056882; Wed, 23 Sep 2015 15:09:22 -0700 Received: (from segher@localhost) by gcc1-power7.osuosl.org (8.14.6/8.14.6/Submit) id t8NM9MjW056878; Wed, 23 Sep 2015 15:09:22 -0700 From: Segher Boessenkool To: gcc-patches@gcc.gnu.org Cc: Segher Boessenkool Subject: [PATCH 2/4] bb-reorder: Add the "simple" algorithm Date: Wed, 23 Sep 2015 22:10:00 -0000 Message-Id: In-Reply-To: References: In-Reply-To: References: X-IsSubscribed: yes X-SW-Source: 2015-09/txt/msg01801.txt.bz2 This is the meat of this series: a new algorithm to do basic block reordering. It uses the simple greedy approach to maximum weighted matching, where the weights are the predicted execution frequency of the edges. This always finds a solution that is within a factor two of optimal, if you disregard loops (which we cannot allow) and the complications of block partitioning. 2015-09-23 Segher Boessenkool * bb-reorder.c (reorder_basic_blocks_software_trace_cache): Print a header to the dump file. (edge_order): New function. (reorder_basic_blocks_simple): New function. (reorder_basic_blocks): Choose between the STC and the simple algorithms (always choose the former). --- gcc/bb-reorder.c | 160 ++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 159 insertions(+), 1 deletion(-) diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c index 725cdc3..40e9e50 100644 --- a/gcc/bb-reorder.c +++ b/gcc/bb-reorder.c @@ -2231,6 +2231,9 @@ update_crossing_jump_flags (void) static void reorder_basic_blocks_software_trace_cache (void) { + if (dump_file) + fprintf (dump_file, "\nReordering with the STC algorithm.\n\n"); + int n_traces; int i; struct trace *traces; @@ -2261,6 +2264,158 @@ reorder_basic_blocks_software_trace_cache (void) FREE (bbd); } +/* Return true if edge E1 is more desirable as a fallthrough edge than + edge E2 is. */ + +static bool +edge_order (edge e1, edge e2) +{ + return EDGE_FREQUENCY (e1) > EDGE_FREQUENCY (e2); +} + +/* Reorder basic blocks using the "simple" algorithm. This tries to + maximize the dynamic number of branches that are fallthrough, without + copying instructions. The algorithm is greedy, looking at the most + frequently executed branch first. */ + +static void +reorder_basic_blocks_simple (void) +{ + if (dump_file) + fprintf (dump_file, "\nReordering with the \"simple\" algorithm.\n\n"); + + edge *edges = new edge[2 * n_basic_blocks_for_fn (cfun)]; + + /* First, collect all edges that can be optimized by reordering blocks: + simple jumps and conditional jumps, as well as the function entry edge. */ + + int n = 0; + edges[n++] = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0); + + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + { + rtx_insn *end = BB_END (bb); + + if (computed_jump_p (end) || tablejump_p (end, NULL, NULL)) + continue; + + if (any_condjump_p (end)) + { + edges[n++] = EDGE_SUCC (bb, 0); + edges[n++] = EDGE_SUCC (bb, 1); + } + else if (single_succ_p (bb)) + edges[n++] = EDGE_SUCC (bb, 0); + } + + /* Sort the edges, the most desirable first. */ + + std::stable_sort (edges, edges + n, edge_order); + + /* Now decide which of those edges to make fallthrough edges. We set + BB_VISITED if a block already has a fallthrough successor assigned + to it. We make ->AUX of an endpoint point to the opposite endpoint + of a sequence of blocks that fall through, and ->AUX will be NULL + for a block that is in such a sequence but not an endpoint anymore. + + To start with, everything points to itself, nothing is assigned yet. */ + + FOR_ALL_BB_FN (bb, cfun) + bb->aux = bb; + + EXIT_BLOCK_PTR_FOR_FN (cfun)->aux = 0; + + /* Now for all edges, the most desirable first, see if that edge can + connect two sequences. If it can, update AUX and BB_VISITED; if it + cannot, zero out the edge in the table. */ + + int j; + for (j = 0; j < n; j++) + { + edge e = edges[j]; + + basic_block tail_a = e->src; + basic_block head_b = e->dest; + basic_block head_a = (basic_block) tail_a->aux; + basic_block tail_b = (basic_block) head_b->aux; + + /* An edge cannot connect two sequences if: + - it crosses partitions; + - its src is not a current endpoint; + - its dest is not a current endpoint; + - or, it would create a loop. */ + + if (e->flags & EDGE_CROSSING + || tail_a->flags & BB_VISITED + || !tail_b + || (!(head_b->flags & BB_VISITED) && head_b != tail_b) + || tail_a == tail_b) + { + edges[j] = 0; + continue; + } + + tail_a->aux = 0; + head_b->aux = 0; + head_a->aux = tail_b; + tail_b->aux = head_a; + tail_a->flags |= BB_VISITED; + } + + /* Put the pieces together, in the same order that the start blocks of + the sequences already had. The hot/cold partitioning gives a little + complication: as a first pass only do this for blocks in the same + partition as the start block, and (if there is anything left to do) + in a second pass handle the other partition. */ + + basic_block last_tail = (basic_block) ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux; + + int current_partition = BB_PARTITION (last_tail); + bool need_another_pass = true; + + for (int pass = 0; pass < 2 && need_another_pass; pass++) + { + need_another_pass = false; + + FOR_EACH_BB_FN (bb, cfun) + if ((bb->flags & BB_VISITED && bb->aux) || bb->aux == bb) + { + if (BB_PARTITION (bb) != current_partition) + { + need_another_pass = true; + continue; + } + + last_tail->aux = bb; + last_tail = (basic_block) bb->aux; + } + + current_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION; + } + + last_tail->aux = 0; + + /* Finally, link all the chosen fallthrough edges. */ + + for (j = 0; j < n; j++) + if (edges[j]) + edges[j]->src->aux = edges[j]->dest; + + delete[] edges; + + /* If the entry edge no longer falls through we have to make a new + block so it can do so again. */ + + edge e = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0); + if (e->dest != ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux) + { + force_nonfallthru (e); + e->src->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux; + BB_COPY_PARTITION (e->src, e->dest); + } +} + /* Reorder basic blocks. The main entry point to this file. */ static void @@ -2274,7 +2429,10 @@ reorder_basic_blocks (void) set_edge_can_fallthru_flag (); mark_dfs_back_edges (); - reorder_basic_blocks_software_trace_cache (); + if (1) + reorder_basic_blocks_software_trace_cache (); + else + reorder_basic_blocks_simple (); relink_block_chain (/*stay_in_cfglayout_mode=*/true); -- 1.8.1.4