From patchwork Fri Mar 23 17:43:10 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Easwaran Raman X-Patchwork-Id: 148476 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 A4EDCB6EE6 for ; Sat, 24 Mar 2012 04:44:00 +1100 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1333129442; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:Received:To:Subject:Message-Id:Date: From:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=nwTMWX6 rL6bugSwFmJgPEUjTuP8=; b=DAjtfwPQ89of+HwPxkWDmrJvHvnP0VxVZ8vncrx ltNA5toYF//2IDsz/BgDTFfURxtpCwnMFrEhffdoJSacY0xQr18d5HkymwSy3pti X/b7t4Veo9EmXCwAE1cPM5eJsvRMTwTBxXkCplLoyMTvIEUudkWH+MUPIVdVbTHj +1OI= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:X-Google-DKIM-Signature:Received:Received:Received:Received:Received:To:Subject:Message-Id:Date:From:X-Gm-Message-State:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=BON9SwJi7TKhG2pmXQCCBsTGNeywUQKQi0PBqQG7G3KMMXKKnrCauOMJ8pmbs+ UmnfXbgGni3ajlnZoxtxP7gW4ejIsfY7mV5witNM8y9yF5+GftZFffU7y7CRm5KU s0vPGPC7hWELTJrY9TZAikNUlvkmxiA6WlK1+ZwWcCSfc=; Received: (qmail 12106 invoked by alias); 23 Mar 2012 17:43:52 -0000 Received: (qmail 11741 invoked by uid 22791); 23 Mar 2012 17:43:45 -0000 X-SWARE-Spam-Status: No, hits=-2.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, RCVD_IN_DNSWL_LOW, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-vx0-f201.google.com (HELO mail-vx0-f201.google.com) (209.85.220.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 23 Mar 2012 17:43:12 +0000 Received: by vcqp1 with SMTP id p1so524904vcq.2 for ; Fri, 23 Mar 2012 10:43:11 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=to:subject:message-id:date:from:x-gm-message-state; bh=+5eBIQYiCygImDf7NUgtspamZ+zJj2glH9bHGnnwJz4=; b=lCuFnv9ppYzvrsfkAkjOh5lL9fn20UeKwL1OOT+ZgAeM9BB7wW8wxUjzYJ4jXquISD ZOMV9oEC8ZnVaH3vDEo876pL+N7hIf+KSntPXPW0SDsHRioHPewTrvMShPqFq+nzpI7Z aLCHWXtoclAP7WcQhCps9E8T+iCeTF7ChXTlWMF28nR9P4WEsKzERuKG0Qss7r3rkfNr bjMSv95SrUbcQpC5WMVn0209DiJRet6/pum9mREpvkFlHg/alfeESDi27+4eJJdbB+ej uYMnBvxuVMFzONyJ4+7uo0fgo+lf55jA5oU+kPDxZZBRaqTX8Rfj3ZaJ3Unh2dBpNXM3 rYuw== Received: by 10.101.121.13 with SMTP id y13mr5565212anm.3.1332524591137; Fri, 23 Mar 2012 10:43:11 -0700 (PDT) Received: by 10.101.121.13 with SMTP id y13mr5565204anm.3.1332524591039; Fri, 23 Mar 2012 10:43:11 -0700 (PDT) Received: from wpzn3.hot.corp.google.com (216-239-44-65.google.com [216.239.44.65]) by gmr-mx.google.com with ESMTPS id y53si5462973yhe.4.2012.03.23.10.43.11 (version=TLSv1/SSLv3 cipher=AES128-SHA); Fri, 23 Mar 2012 10:43:11 -0700 (PDT) Received: from agni2.mtv.corp.google.com (agni2.mtv.corp.google.com [172.18.110.219]) by wpzn3.hot.corp.google.com (Postfix) with ESMTP id BBF8E10004D; Fri, 23 Mar 2012 10:43:10 -0700 (PDT) Received: by agni2.mtv.corp.google.com (Postfix, from userid 93554) id 64276220E1C; Fri, 23 Mar 2012 10:43:10 -0700 (PDT) To: reply@codereview.appspotmail.com,gcc-patches@gcc.gnu.org Subject: Propagate profile counts after switch case expansion (issue5896043) Message-Id: <20120323174310.64276220E1C@agni2.mtv.corp.google.com> Date: Fri, 23 Mar 2012 10:43:10 -0700 (PDT) From: eraman@google.com (Easwaran Raman) X-Gm-Message-State: ALoCoQnnfULKQxx2pAjXxxT3PterxFUYjOJbBpUhiuNmM8SRAv1aXJ2PVI/WyWep+mdqdWlE9z15hSuPRQorEDmV3/xgn5Es6pWyogqJXxI/auvz8fm1wMcjjQMjcqmoI4KXX1I+v0jz8i0GtrxRULH1n1sQMmJN+sSGLBngLLiIQ+UVhh6FCgg= X-IsSubscribed: yes 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 This patch propagates execution count of thee case labels of a switch-case statement after its expansion. Bootstraps and all tests pass. OK for trunk? 2012-03-23 Easwaran Raman * cfgbuild.c (non_zero_profile_counts): New function. (compute_outgoing_frequencies): If at least one successor of a BB has non-zero profile count, retain the counts. * expr.c (do_tablejump): Add a REG_BR_PROB note on the jump to default label. (try_tablejump): Add a parameter to specify the probability of jumping to the default label. * expr.h (try_tablejump): Add a new parameter. * stmt.c (case_node): Add new fields COUNT and SUBTREE_COUNT. (add_case_node): Pass execution count of the case node and use it to initialize COUNT field. (case_probability): New macro. (expand_case): Propagate execution counts to generated branches using REG_BR_PROB notes. (emit_case_nodes): Likewise. (do_jump_if_equal): Pass probability for REG_BR_PROB note. (compute_subtree_counts): New function to compute SUBTREE_COUNT fields of case nodes. (add_prob_note_to_last_insn): Add a REG_BR_PROB note with the given probability to the last generated instruction. gcc/testsuite/ChangeLog: 2012-03-23 Easwaran Raman * gcc.dg/tree-prof/switch-case-1.c: New test case. * gcc.dg/tree-prof/switch-case-2.c: New test case. --- This patch is available for review at http://codereview.appspot.com/5896043 diff --git a/gcc/cfgbuild.c b/gcc/cfgbuild.c index 692fea8..d75fbda 100644 --- a/gcc/cfgbuild.c +++ b/gcc/cfgbuild.c @@ -534,6 +534,21 @@ find_bb_boundaries (basic_block bb) purge_dead_tablejump_edges (bb, table); } +/* Check if there is at least one edge in EDGES with a non-zero count + field. */ + +static bool +non_zero_profile_counts ( VEC(edge,gc) *edges) { + edge e; + edge_iterator ei; + FOR_EACH_EDGE(e, ei, edges) + { + if (e->count > 0) + return true; + } + return false; +} + /* Assume that frequency of basic block B is known. Compute frequencies and probabilities of outgoing edges. */ @@ -569,6 +584,10 @@ compute_outgoing_frequencies (basic_block b) e->count = b->count; return; } + else if (non_zero_profile_counts (b->succs)){ + /*Profile counts already set, but REG_NOTE missing. Retain the counts. */ + return; + } guess_outgoing_edge_probabilities (b); if (b->count) FOR_EACH_EDGE (e, ei, b->succs) diff --git a/gcc/expr.c b/gcc/expr.c index f9de908..fb8eef9 100644 --- a/gcc/expr.c +++ b/gcc/expr.c @@ -156,7 +156,7 @@ static rtx do_store_flag (sepops, rtx, enum machine_mode); #ifdef PUSH_ROUNDING static void emit_single_push_insn (enum machine_mode, rtx, tree); #endif -static void do_tablejump (rtx, enum machine_mode, rtx, rtx, rtx); +static void do_tablejump (rtx, enum machine_mode, rtx, rtx, rtx, int); static rtx const_vector_from_tree (tree); static void write_complex_part (rtx, rtx, bool); @@ -10694,11 +10694,13 @@ try_casesi (tree index_type, tree index_expr, tree minval, tree range, TABLE_LABEL is a CODE_LABEL rtx for the table itself. DEFAULT_LABEL is a CODE_LABEL rtx to jump to if the - index value is out of range. */ + index value is out of range. + DEFAULT_PROBABILITY is the probability of jumping to the + DEFAULT_LABEL. */ static void do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label, - rtx default_label) + rtx default_label, int default_probability) { rtx temp, vector; @@ -10714,8 +10716,16 @@ do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label, the maximum value of the range. */ if (default_label) - emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1, - default_label); + { + emit_cmp_and_jump_insns (index, range, GTU, NULL_RTX, mode, 1, + default_label); + if (default_probability != -1) + { + rtx jump_insn = get_last_insn(); + add_reg_note (jump_insn, REG_BR_PROB, GEN_INT (default_probability)); + } + } + /* If index is in range, it must fit in Pmode. Convert to Pmode so we can index with it. */ @@ -10758,7 +10768,7 @@ do_tablejump (rtx index, enum machine_mode mode, rtx range, rtx table_label, int try_tablejump (tree index_type, tree index_expr, tree minval, tree range, - rtx table_label, rtx default_label) + rtx table_label, rtx default_label, int default_probability) { rtx index; @@ -10776,7 +10786,7 @@ try_tablejump (tree index_type, tree index_expr, tree minval, tree range, TYPE_MODE (TREE_TYPE (range)), expand_normal (range), TYPE_UNSIGNED (TREE_TYPE (range))), - table_label, default_label); + table_label, default_label, default_probability); return 1; } diff --git a/gcc/expr.h b/gcc/expr.h index 0096367..9691041 100644 --- a/gcc/expr.h +++ b/gcc/expr.h @@ -484,7 +484,7 @@ extern void do_compare_rtx_and_jump (rtx, rtx, enum rtx_code, int, /* Two different ways of generating switch statements. */ extern int try_casesi (tree, tree, tree, tree, rtx, rtx, rtx); -extern int try_tablejump (tree, tree, tree, tree, rtx, rtx); +extern int try_tablejump (tree, tree, tree, tree, rtx, rtx, int); /* Functions from alias.c */ #include "alias.h" diff --git a/gcc/stmt.c b/gcc/stmt.c index 93d643a..9c6e211 100644 --- a/gcc/stmt.c +++ b/gcc/stmt.c @@ -54,6 +54,7 @@ along with GCC; see the file COPYING3. If not see #include "pretty-print.h" #include "bitmap.h" #include "params.h" +#include "tree-flow.h" /* Functions and data structures for expanding case statements. */ @@ -93,6 +94,7 @@ struct case_node tree low; /* Lowest index value for this label */ tree high; /* Highest index value for this label */ tree code_label; /* Label to jump to when node matches */ + gcov_type subtree_count, count; /* Execution counts */ }; typedef struct case_node case_node; @@ -122,12 +124,14 @@ static bool lshift_cheap_p (void); static int case_bit_test_cmp (const void *, const void *); static void emit_case_bit_tests (tree, tree, tree, tree, case_node_ptr, rtx); static void balance_case_nodes (case_node_ptr *, case_node_ptr); +static void compute_subtree_counts(case_node_ptr); static int node_has_low_bound (case_node_ptr, tree); static int node_has_high_bound (case_node_ptr, tree); static int node_is_bounded (case_node_ptr, tree); -static void emit_case_nodes (rtx, case_node_ptr, rtx, tree); +static void emit_case_nodes (rtx, case_node_ptr, rtx, int, tree); static struct case_node *add_case_node (struct case_node *, tree, - tree, tree, tree, alloc_pool); + tree, tree, tree, gcov_type, + alloc_pool); /* Return the rtx-label that corresponds to a LABEL_DECL, @@ -1929,11 +1933,12 @@ expand_stack_restore (tree var) fed to us in descending order from the sorted vector of case labels used in the tree part of the middle end. So the list we construct is sorted in ascending order. The bounds on the case range, LOW and HIGH, - are converted to case's index type TYPE. */ + are converted to case's index type TYPE. COUNT is the expected number + of executions of the case label. */ static struct case_node * add_case_node (struct case_node *head, tree type, tree low, tree high, - tree label, alloc_pool case_node_pool) + tree label, gcov_type count, alloc_pool case_node_pool) { tree min_value, max_value; struct case_node *r; @@ -1992,6 +1997,7 @@ add_case_node (struct case_node *head, tree type, tree low, tree high, TREE_INT_CST_HIGH (high)); r->code_label = label; r->parent = r->left = NULL; + r->count = count; r->right = head; return r; } @@ -2189,6 +2195,8 @@ case_values_threshold (void) return threshold; } +#define case_probability(x, y) ((y) ? ((x) * REG_BR_PROB_BASE / (y)) : -1) + /* Terminate a case (Pascal/Ada) or switch (C) statement in which ORIG_INDEX is the expression to be tested. If ORIG_TYPE is not NULL, it is the original ORIG_INDEX @@ -2212,6 +2220,7 @@ expand_case (gimple stmt) tree index_expr = gimple_switch_index (stmt); tree index_type = TREE_TYPE (index_expr); int unsignedp = TYPE_UNSIGNED (index_type); + basic_block bb = gimple_bb (stmt); /* The insn after which the case dispatch should finally be emitted. Zero for a dummy. */ @@ -2224,6 +2233,8 @@ expand_case (gimple stmt) /* Label to jump to if no case matches. */ tree default_label_decl = NULL_TREE; + gcov_type default_count = 0; + alloc_pool case_node_pool = create_alloc_pool ("struct case_node pool", sizeof (struct case_node), 100); @@ -2235,7 +2246,9 @@ expand_case (gimple stmt) { tree elt; bitmap label_bitmap; + edge case_edge = NULL, default_edge = NULL; int stopi = 0; + bool has_gaps = false; /* cleanup_tree_cfg removes all SWITCH_EXPR with their index expressions being INTEGER_CST. */ @@ -2246,12 +2259,17 @@ expand_case (gimple stmt) if (!CASE_LOW (elt) && !CASE_HIGH (elt)) { default_label_decl = CASE_LABEL (elt); + case_edge = EDGE_SUCC(bb, 0); + default_edge = case_edge; + default_count = case_edge->count; stopi = 1; } for (i = gimple_switch_num_labels (stmt) - 1; i >= stopi; --i) { tree low, high; + basic_block case_bb; + edge case_edge; elt = gimple_switch_label (stmt, i); low = CASE_LOW (elt); @@ -2261,9 +2279,11 @@ expand_case (gimple stmt) /* Discard empty ranges. */ if (high && tree_int_cst_lt (high, low)) continue; - + case_bb = label_to_block (CASE_LABEL(elt)); + case_edge = find_edge (bb, case_bb); case_list = add_case_node (case_list, index_type, low, high, - CASE_LABEL (elt), case_node_pool); + CASE_LABEL (elt), case_edge->count, + case_node_pool); } @@ -2287,6 +2307,15 @@ expand_case (gimple stmt) } else { + tree min_minus_one = fold_build2 (MINUS_EXPR, index_type, + n->low, + build_int_cst (index_type, 1)); + /* case_list is sorted in increasing order. If the minval - 1 of + this node is greater than the previous maxval, then there is a + gap. If jump table expansion is used, this gap will be filled + with the default label. */ + if (tree_int_cst_lt (maxval, min_minus_one)) + has_gaps = true; if (tree_int_cst_lt (n->low, minval)) minval = n->low; if (tree_int_cst_lt (maxval, n->high)) @@ -2398,18 +2427,24 @@ expand_case (gimple stmt) use_cost_table = estimate_case_costs (case_list); balance_case_nodes (&case_list, NULL); - emit_case_nodes (index, case_list, default_label, index_type); + compute_subtree_counts (case_list); + emit_case_nodes (index, case_list, default_label, default_count, + index_type); if (default_label) emit_jump (default_label); } else { rtx fallback_label = label_rtx (case_list->code_label); + edge e; + edge_iterator ei; + gcov_type count = bb->count; table_label = gen_label_rtx (); if (! try_casesi (index_type, index_expr, minval, range, table_label, default_label, fallback_label)) { bool ok; + int default_probability; /* Index jumptables from zero for suitable values of minval to avoid a subtraction. */ @@ -2419,12 +2454,40 @@ expand_case (gimple stmt) { minval = build_int_cst (index_type, 0); range = maxval; + has_gaps = true; } + if (has_gaps) + { + /* There is at least one entry in the jump table that jumps + to default label. The default label can either be reached + through the indirect jump or the direct conditional jump + before that. Split the probability of reaching the + default label among these two jumps. */ + default_probability = case_probability (default_count/2, + bb->count); + default_count /= 2; + count -= default_count; + } + else + { + default_probability = case_probability (default_count, + bb->count); + count -= default_count; + default_count = 0; + } ok = try_tablejump (index_type, index_expr, minval, range, - table_label, default_label); + table_label, default_label, + default_probability); gcc_assert (ok); } + if (default_edge) + { + default_edge->count = default_count; + if (count) + FOR_EACH_EDGE (e, ei, bb->succs) + e->probability = e->count * REG_BR_PROB_BASE / count; + } /* Get table of labels to jump to, in order of case index. */ @@ -2485,14 +2548,15 @@ expand_case (gimple stmt) free_alloc_pool (case_node_pool); } -/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. */ +/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. + PROB is the probability of jumping to LABEL. */ static void do_jump_if_equal (enum machine_mode mode, rtx op0, rtx op1, rtx label, - int unsignedp) + int unsignedp, int prob) { do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, - NULL_RTX, NULL_RTX, label, -1); + NULL_RTX, NULL_RTX, label, prob); } /* Not all case values are encountered equally. This function @@ -2575,6 +2639,26 @@ estimate_case_costs (case_node_ptr node) return 1; } +/* Compute the SUBTREE_COUNT of all nodes in the tree rooted at NODE. */ + +static void +compute_subtree_counts (case_node_ptr node) +{ + if (node == NULL) + return; + node->subtree_count = node->count; + if (node->left) + { + compute_subtree_counts (node->left); + node->subtree_count += node->left->subtree_count; + } + if (node->right) + { + compute_subtree_counts (node->right); + node->subtree_count += node->right->subtree_count; + } +} + /* Take an ordered list of case nodes and transform them into a near optimal binary tree, on the assumption that any target code selection value is as @@ -2800,6 +2886,20 @@ node_is_bounded (case_node_ptr node, tree index_type) && node_has_high_bound (node, index_type)); } + +/* Attach a REG_BR_PROB note to the last created RTX instruction if + PROBABILITY is not -1. */ + +static void +add_prob_note_to_last_insn(int probability) +{ + if (probability != -1) + { + rtx jump_insn = get_last_insn(); + add_reg_note (jump_insn, REG_BR_PROB, GEN_INT (probability)); + } +} + /* Emit step-by-step code to select a case for the value of INDEX. The thus generated decision tree follows the form of the case-node binary tree NODE, whose nodes represent test conditions. @@ -2828,10 +2928,12 @@ node_is_bounded (case_node_ptr node, tree index_type) static void emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, - tree index_type) + int default_count, tree index_type) { /* If INDEX has an unsigned type, we must make unsigned branches. */ int unsignedp = TYPE_UNSIGNED (index_type); + int probability; + gcov_type count = node->count, subtree_count = node->subtree_count; enum machine_mode mode = GET_MODE (index); enum machine_mode imode = TYPE_MODE (index_type); @@ -2846,15 +2948,17 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, else if (tree_int_cst_equal (node->low, node->high)) { + probability = case_probability (count, subtree_count + default_count); /* Node is single valued. First see if the index expression matches this node and then check our children, if any. */ - do_jump_if_equal (mode, index, convert_modes (mode, imode, expand_normal (node->low), unsignedp), - label_rtx (node->code_label), unsignedp); - + label_rtx (node->code_label), unsignedp, probability); + /* Since this case is taken at this point, reduce its weight from + subtree_weight. */ + subtree_count -= count; if (node->right != 0 && node->left != 0) { /* This node has children on both sides. @@ -2872,7 +2976,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), GT, NULL_RTX, mode, unsignedp, label_rtx (node->right->code_label)); - emit_case_nodes (index, node->left, default_label, index_type); + probability = case_probability (node->right->count, + subtree_count + default_count); + add_prob_note_to_last_insn (probability); + emit_case_nodes (index, node->left, default_label, default_count, + index_type); } else if (node_is_bounded (node->left, index_type)) @@ -2884,7 +2992,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), LT, NULL_RTX, mode, unsignedp, label_rtx (node->left->code_label)); - emit_case_nodes (index, node->right, default_label, index_type); + probability = case_probability (node->left->count, + subtree_count + default_count); + add_prob_note_to_last_insn (probability); + emit_case_nodes (index, node->right, default_label, default_count, index_type); } /* If both children are single-valued cases with no @@ -2902,21 +3013,25 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, /* See if the value matches what the right hand side wants. */ + probability = case_probability (node->right->count, + subtree_count + default_count); do_jump_if_equal (mode, index, convert_modes (mode, imode, expand_normal (node->right->low), unsignedp), label_rtx (node->right->code_label), - unsignedp); + unsignedp, probability); /* See if the value matches what the left hand side wants. */ + probability = case_probability (node->left->count, + subtree_count + default_count); do_jump_if_equal (mode, index, convert_modes (mode, imode, expand_normal (node->left->low), unsignedp), label_rtx (node->left->code_label), - unsignedp); + unsignedp, probability); } else @@ -2936,10 +3051,18 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), GT, NULL_RTX, mode, unsignedp, label_rtx (test_label)); + /* The default label could be reached either through the right + subtree or the left subtree. Divide the probability + equally. */ + probability = case_probability ( + node->right->subtree_count + default_count/2, + subtree_count + default_count); + default_count /= 2; + add_prob_note_to_last_insn (probability); /* Value must be on the left. Handle the left-hand subtree. */ - emit_case_nodes (index, node->left, default_label, index_type); + emit_case_nodes (index, node->left, default_label, default_count, index_type); /* If left-hand subtree does nothing, go to default. */ if (default_label) @@ -2947,7 +3070,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, /* Code branches here for the right-hand subtree. */ expand_label (test_label); - emit_case_nodes (index, node->right, default_label, index_type); + emit_case_nodes (index, node->right, default_label, default_count, index_type); } } @@ -2972,21 +3095,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), LT, NULL_RTX, mode, unsignedp, default_label); + probability = case_probability (default_count/2, + subtree_count + default_count); + default_count /= 2; + add_prob_note_to_last_insn (probability); } - emit_case_nodes (index, node->right, default_label, index_type); + emit_case_nodes (index, node->right, default_label, default_count, index_type); } else - /* We cannot process node->right normally - since we haven't ruled out the numbers less than - this node's value. So handle node->right explicitly. */ - do_jump_if_equal (mode, index, - convert_modes - (mode, imode, - expand_normal (node->right->low), - unsignedp), - label_rtx (node->right->code_label), unsignedp); - } + { + probability = case_probability (node->right->subtree_count, + subtree_count + default_count); + /* We cannot process node->right normally + since we haven't ruled out the numbers less than + this node's value. So handle node->right explicitly. */ + do_jump_if_equal (mode, index, + convert_modes + (mode, imode, + expand_normal (node->right->low), + unsignedp), + label_rtx (node->right->code_label), unsignedp, probability); + } + } else if (node->right == 0 && node->left != 0) { @@ -3003,20 +3134,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), GT, NULL_RTX, mode, unsignedp, default_label); + probability = case_probability ( + default_count/2, subtree_count + default_count); + default_count /= 2; + add_prob_note_to_last_insn (probability); } - emit_case_nodes (index, node->left, default_label, index_type); + emit_case_nodes (index, node->left, default_label, + default_count, index_type); } else - /* We cannot process node->left normally - since we haven't ruled out the numbers less than - this node's value. So handle node->left explicitly. */ - do_jump_if_equal (mode, index, - convert_modes - (mode, imode, - expand_normal (node->left->low), - unsignedp), - label_rtx (node->left->code_label), unsignedp); + { + probability = case_probability (node->left->subtree_count, + subtree_count + default_count); + /* We cannot process node->left normally + since we haven't ruled out the numbers less than + this node's value. So handle node->left explicitly. */ + do_jump_if_equal (mode, index, + convert_modes + (mode, imode, + expand_normal (node->left->low), + unsignedp), + label_rtx (node->left->code_label), unsignedp, probability); + } } } else @@ -3035,15 +3175,20 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, tree test_label = 0; if (node_is_bounded (node->right, index_type)) - /* Right hand node is fully bounded so we can eliminate any - testing and branch directly to the target code. */ - emit_cmp_and_jump_insns (index, - convert_modes - (mode, imode, - expand_normal (node->high), - unsignedp), - GT, NULL_RTX, mode, unsignedp, - label_rtx (node->right->code_label)); + { + /* Right hand node is fully bounded so we can eliminate any + testing and branch directly to the target code. */ + emit_cmp_and_jump_insns (index, + convert_modes + (mode, imode, + expand_normal (node->high), + unsignedp), + GT, NULL_RTX, mode, unsignedp, + label_rtx (node->right->code_label)); + probability = case_probability (node->right->subtree_count, + subtree_count + default_count); + add_prob_note_to_last_insn (probability); + } else { /* Right hand node requires testing. @@ -3058,6 +3203,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), GT, NULL_RTX, mode, unsignedp, label_rtx (test_label)); + probability = case_probability (node->right->subtree_count + default_count/2, + subtree_count + default_count); + default_count /= 2; + add_prob_note_to_last_insn (probability); } /* Value belongs to this node or to the left-hand subtree. */ @@ -3069,9 +3218,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), GE, NULL_RTX, mode, unsignedp, label_rtx (node->code_label)); + probability = case_probability (count, subtree_count + default_count); + add_prob_note_to_last_insn (probability); /* Handle the left-hand subtree. */ - emit_case_nodes (index, node->left, default_label, index_type); + emit_case_nodes (index, node->left, default_label, default_count, index_type); /* If right node had to be handled later, do that now. */ @@ -3083,7 +3234,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, emit_jump (default_label); expand_label (test_label); - emit_case_nodes (index, node->right, default_label, index_type); + emit_case_nodes (index, node->right, default_label, default_count, index_type); } } @@ -3100,6 +3251,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), LT, NULL_RTX, mode, unsignedp, default_label); + probability = case_probability (default_count/2, + subtree_count + default_count); + default_count /= 2; + add_prob_note_to_last_insn (probability); } /* Value belongs to this node or to the right-hand subtree. */ @@ -3111,8 +3266,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), LE, NULL_RTX, mode, unsignedp, label_rtx (node->code_label)); + probability = case_probability (count, subtree_count + default_count); + add_prob_note_to_last_insn (probability); - emit_case_nodes (index, node->right, default_label, index_type); + emit_case_nodes (index, node->right, default_label, default_count, index_type); } else if (node->right == 0 && node->left != 0) @@ -3128,6 +3285,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), GT, NULL_RTX, mode, unsignedp, default_label); + probability = case_probability (default_count/2, + subtree_count + default_count); + default_count /= 2; + add_prob_note_to_last_insn (probability); } /* Value belongs to this node or to the left-hand subtree. */ @@ -3139,8 +3300,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), GE, NULL_RTX, mode, unsignedp, label_rtx (node->code_label)); + probability = case_probability (count, subtree_count + default_count); + add_prob_note_to_last_insn (probability); - emit_case_nodes (index, node->left, default_label, index_type); + emit_case_nodes (index, node->left, default_label, default_count, index_type); } else @@ -3160,6 +3323,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), GT, NULL_RTX, mode, unsignedp, default_label); + probability = case_probability (default_count, + subtree_count + default_count); + add_prob_note_to_last_insn (probability); } else if (!low_bound && high_bound) @@ -3171,6 +3337,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, unsignedp), LT, NULL_RTX, mode, unsignedp, default_label); + probability = case_probability (default_count, + subtree_count + default_count); + add_prob_note_to_last_insn (probability); } else if (!low_bound && !high_bound) { @@ -3192,6 +3361,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX, mode, 1, default_label); + probability = case_probability (default_count, + subtree_count + default_count); + add_prob_note_to_last_insn (probability); } emit_jump (label_rtx (node->code_label)); diff --git a/gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c b/gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c new file mode 100644 index 0000000..ef094fa --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c @@ -0,0 +1,40 @@ +/* { dg-options "-O2 -fdump-rtl-expand-blocks" } */ +int g; + +__attribute__((noinline)) void foo (int n) +{ + switch (n) + { + case 1: + g++; break; + case 2: + g += 2; break; + case 3: + g += 1; break; + case 4: + g += 3; break; + case 5: + g += 4; break; + case 6: + g += 5; break; + case 7: + g += 6; break; + case 8: + g += 7; break; + case 9: + g += 8; break; + default: + g += 8; break; + } +} + +int main () +{ + int i; + for (i = 0; i < 10000; i++) + foo ((i * i) % 5); + return 0; +} +/* { dg-final-use { scan-rtl-dump-times "Basic block\[^\\n\]*count 4000" 2 "expand"} } */ +/* { dg-final-use { scan-rtl-dump-times "Basic block\[^\\n\]*count 2000" 1 "expand"} } */ +/* { dg-final-use { cleanup-rtl-dump "expand" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c b/gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c new file mode 100644 index 0000000..8adc380 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c @@ -0,0 +1,40 @@ +/* { dg-options "-O2 -fdump-rtl-expand-blocks" } */ +int g; + +__attribute__((noinline)) void foo (int n) +{ + switch (n) + { + case 99: + g += 2; break; + case 1: + g++; break; + case 100: + g += 1; break; + case 4: + g += 3; break; + case 5: + g += 4; break; + case 6: + g += 5; break; + case 7: + g += 6; break; + case 8: + g += 7; break; + case 9: + g += 8; break; + default: + g += 8; break; + } +} + +int main () +{ + int i; + for (i = 0; i < 10000; i++) + foo ((i * i) % 5); + return 0; +} +/* { dg-final-use { scan-rtl-dump-times "Basic block\[^\\n\]*count 4000" 2 "expand"} } */ +/* { dg-final-use { scan-rtl-dump-times "Basic block\[^\\n\]*count 2000" 1 "expand"} } */ +/* { dg-final-use { cleanup-rtl-dump "expand" } } */