From patchwork Wed Oct 3 01:09:36 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Easwaran Raman X-Patchwork-Id: 188692 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 8D9952C0097 for ; Wed, 3 Oct 2012 11:09:55 +1000 (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=1349831396; h=Comment: DomainKey-Signature:Received:Received:Received:Received: MIME-Version:Received:Received:Date:Message-ID:Subject:From:To: Cc:Content-Type:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=Gd3tJ1I zbknEIgPOenIfdTXUE4I=; b=AZr11fkr1n6BULSHUFCiCet+P3SBNIZa/I7/O5h 3FOLHGC1iKV6C5EYB4XGJvaJykYzqKi8keNfGOeDTSqlKpKzaVOLp5Ml/hB3pR13 KuK2lDvB+i4ZE9ypv9KnuUV8FS0JemsjPc1TlT8KTo4+Nmjm4Kv+oynojRm2tOCr Y3RA= 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:MIME-Version:Received:Received:Date:Message-ID:Subject:From:To:Cc:Content-Type:X-System-Of-Record:X-Gm-Message-State:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=hOtBM51o96s8+QxBMl970DGfFToAX0Yw36edHWNJTWehzEhH5RDcnT9M5R2gbI K8uXEOpOxGzkQtfuJ3EB/J/zkxz3pwM2+zUhML8ygzI0aGpMmaowuY8WmJjEkHQG jM5DNQuYSFQUj9AILo7eHjBa1+etX+LqAr31yanbFqQNM=; Received: (qmail 8079 invoked by alias); 3 Oct 2012 01:09:50 -0000 Received: (qmail 8060 invoked by uid 22791); 3 Oct 2012 01:09:46 -0000 X-SWARE-Spam-Status: No, hits=-6.0 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, KHOP_RCVD_TRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, RP_MATCHES_RCVD, TW_TM X-Spam-Check-By: sourceware.org Received: from mail-ie0-f175.google.com (HELO mail-ie0-f175.google.com) (209.85.223.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 03 Oct 2012 01:09:37 +0000 Received: by iebc13 with SMTP id c13so19000110ieb.20 for ; Tue, 02 Oct 2012 18:09:36 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:date:message-id:subject:from:to:cc:content-type :x-system-of-record:x-gm-message-state; bh=1m95eEnoYNGEgU0QrX1aSdnxH9FtFnZ+9cw6MIMrIXw=; b=Gx1wlSkB4QEdOumQfBz7OQZv9foRJmzj5kPvAS0xEIwa5n40eWSzYp6rext8TVZz2Z 2/q6WwPs38TLCK0tyF1BhBrKOU0HCDB0206mHhoZE49mYuQUegBpaXRM0QexDUijdFkG LS0ajNt+q3+dkZMruWKWW0kwiH1ajRQbiJi35Ln+KYms4ii1EI+JnVv8JGFc0bvMN8LD IsPgaGbMucsSu4Tjx+rUQ229Jrgp4NGEcNe1uuwjZ5NO9adER3baeb+kXJnJdxoZLWzh R7eiDc8t2DLcBTREbY2CB58ed0Rfj6P2S70Dg2HQhfVfe/xZz3/+shMkP1QD2cIZqD2w Texg== MIME-Version: 1.0 Received: by 10.50.185.230 with SMTP id ff6mr11407436igc.0.1349226576270; Tue, 02 Oct 2012 18:09:36 -0700 (PDT) Received: by 10.50.45.132 with HTTP; Tue, 2 Oct 2012 18:09:36 -0700 (PDT) Date: Tue, 2 Oct 2012 18:09:36 -0700 Message-ID: Subject: Propagate profile counts during switch expansion From: Easwaran Raman To: gcc-patches@gcc.gnu.org Cc: Jan Hubicka , Steven Bosscher , David Li X-System-Of-Record: true X-Gm-Message-State: ALoCoQmN9+iFMblVp1QG8m1gc8SqrNZAgztI15HugAQa+eNrcM4nFOB/2QqkIxrXlg2OZCRQl8rojkkSySglD5R/k22tTY6EvSL/CAGmrqlZWXt1J1VluH9s9l6nyHRwbP7As/3xdf3KIYsStyt1TsJcOe9jOIyu8PPYUwDnQDZaM3Y8f1OAXR2fMm6RGwidTIjIs4kZ5HIh 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 Hi, This patch propagates the profile counts during RTL expansion. In many cases, there is no way to determine the exact count of an edge generated during the expansion. So this patch uses some simple heuristics to estimate the edge counts but ensures that the counts of the basic blocks corresponding to the cases are (nearly the) same as at the gimple level. Bootstrapped and profile-bootstrapped on an x86_64/linux machine. OK for trunk? - Easwaran ------ 2012-10-02 Easwaran Raman * cfgbuild.c (gen_probabilities_from_existing_counts): New function. (compute_outgoing_frequencies): If at least one successor of a BB has non-zero profile count, use the counts to compute probabilities. * 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. (do_jump_if_equal): Pass probability for REG_BR_PROB note. (add_case_node): Pass execution count of the case node and use it to initialize COUNT field. (emit_case_decision_tree): Pass default_count to emit_case_nodes. (get_outgoing_edge_counts): New function. (add_prob_note_to_last_insn): Likewise. (case_probability): New macro. (emit_case_dispatch_table): Compute probability of jumping to default label and apply note to the jump. (expand_case): Compute and propagate default edge count to emit_case_dispatch_table. (expand_sjlj_dispatch_table): Update calls to add_case_node and emit_case_dispatch_table. (balance_case_nodes): Update subtree_counts. (emit_case_nodes): Compute edge probabilities and add note. gcc/testsuite/ChangeLog: 2012-10-02 Easwaran Raman * gcc.dg/tree-prof/switch-case-1.c: New test case. * gcc.dg/tree-prof/switch-case-2.c: New test case. @@ -1956,6 +2018,7 @@ expand_case (gimple stmt) tree index_expr = gimple_switch_index (stmt); tree index_type = TREE_TYPE (index_expr); tree elt; + basic_block bb = gimple_bb (stmt); /* A list of case labels; it is first built as a list and it may then be rearranged into a nearly balanced binary tree. */ @@ -1981,6 +2044,8 @@ expand_case (gimple stmt) /* Find the default case target label. */ default_label = label_rtx (CASE_LABEL (gimple_switch_default_label (stmt))); + edge default_edge = EDGE_SUCC(bb, 0); + gcov_type default_count = default_edge->count; /* Get upper and lower bounds of case values. */ elt = gimple_switch_label (stmt, 1); @@ -1999,7 +2064,7 @@ expand_case (gimple stmt) uniq = 0; count = 0; struct pointer_set_t *seen_labels = pointer_set_create (); - for (i = gimple_switch_num_labels (stmt) - 1; i >= 1; --i) + for (i = ncases - 1; i >= 1; --i) { elt = gimple_switch_label (stmt, i); tree low = CASE_LOW (elt); @@ -2041,8 +2106,10 @@ expand_case (gimple stmt) TREE_INT_CST_LOW (high), TREE_INT_CST_HIGH (high)); + basic_block case_bb = label_to_block_fn (cfun, lab); + edge case_edge = find_edge (bb, case_bb); case_list = add_case_node (case_list, low, high, lab, - case_node_pool); + case_edge->count, case_node_pool); } pointer_set_destroy (seen_labels); @@ -2060,11 +2127,12 @@ expand_case (gimple stmt) if (expand_switch_as_decision_tree_p (range, uniq, count)) emit_case_decision_tree (index_expr, index_type, - case_list, default_label); + case_list, default_label, + default_count); else emit_case_dispatch_table (index_expr, index_type, case_list, default_label, - minval, maxval, range); + minval, maxval, range, bb); reorder_insns (NEXT_INSN (before_case), get_last_insn (), before_case); @@ -2126,7 +2194,7 @@ expand_sjlj_dispatch_table (rtx dispatch_index, { tree elt = VEC_index (tree, dispatch_table, i); rtx lab = label_rtx (CASE_LABEL (elt)); - do_jump_if_equal (index_mode, index, zero, lab, 0); + do_jump_if_equal (index_mode, index, zero, lab, 0, -1); force_expand_binop (index_mode, sub_optab, index, CONST1_RTX (index_mode), index, 0, OPTAB_DIRECT); @@ -2150,12 +2218,12 @@ expand_sjlj_dispatch_table (rtx dispatch_index, tree elt = VEC_index (tree, dispatch_table, i); tree low = CASE_LOW (elt); tree lab = CASE_LABEL (elt); - case_list = add_case_node (case_list, low, low, lab, case_node_pool); + case_list = add_case_node (case_list, low, low, lab, 0, case_node_pool); } emit_case_dispatch_table (index_expr, index_type, case_list, default_label, - minval, maxval, range); + minval, maxval, range, NULL); emit_label (default_label); free_alloc_pool (case_node_pool); } @@ -2237,6 +2305,9 @@ balance_case_nodes (case_node_ptr *head, case_node /* Optimize each of the two split parts. */ balance_case_nodes (&np->left, np); balance_case_nodes (&np->right, np); + np->subtree_count = np->count; + np->subtree_count += np->left->subtree_count; + np->subtree_count += np->right->subtree_count; } else { @@ -2244,8 +2315,12 @@ balance_case_nodes (case_node_ptr *head, case_node but fill in `parent' fields. */ np = *head; np->parent = parent; + np->subtree_count = np->count; for (; np->right; np = np->right) - np->right->parent = np; + { + np->right->parent = np; + (*head)->subtree_count += np->right->subtree_count; + } } } } @@ -2358,6 +2433,20 @@ node_is_bounded (case_node_ptr node, tree index_ty && 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. @@ -2386,10 +2475,12 @@ node_is_bounded (case_node_ptr node, tree index_ty static void emit_case_nodes (rtx index, case_node_ptr node, rtx default_label, - tree index_type) + gcov_type 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); @@ -2404,15 +2495,17 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. @@ -2430,7 +2523,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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)) @@ -2442,7 +2539,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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 @@ -2460,21 +2560,25 @@ emit_case_nodes (rtx index, case_node_ptr node, rt /* 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 @@ -2494,10 +2598,18 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) @@ -2505,7 +2617,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rt /* 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); } } @@ -2530,21 +2642,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) { @@ -2561,20 +2681,29 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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 @@ -2593,15 +2722,20 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. @@ -2616,6 +2750,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. */ @@ -2627,9 +2765,11 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. */ @@ -2641,7 +2781,7 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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); } } @@ -2658,6 +2798,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. */ @@ -2669,8 +2813,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) @@ -2686,6 +2832,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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. */ @@ -2697,8 +2847,10 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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 @@ -2718,6 +2870,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) @@ -2729,6 +2884,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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) { @@ -2750,6 +2908,9 @@ emit_case_nodes (rtx index, case_node_ptr node, rt 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)); Index: gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c =================================================================== --- gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-prof/switch-case-1.c (revision 0) @@ -0,0 +1,40 @@ +/* { dg-options "-O2 -fdump-rtl-expand-all" } */ +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" } } */ Index: gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c =================================================================== --- gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c (revision 0) +++ gcc/testsuite/gcc.dg/tree-prof/switch-case-2.c (revision 0) @@ -0,0 +1,40 @@ +/* { dg-options "-O2 -fdump-rtl-expand-all" } */ +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" } } */ Index: gcc/expr.c =================================================================== --- gcc/expr.c (revision 191879) +++ gcc/expr.c (working copy) @@ -154,7 +154,7 @@ static rtx do_store_flag (sepops, rtx, enum machin #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); @@ -10894,7 +10894,7 @@ try_casesi (tree index_type, tree index_expr, tree 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; @@ -10910,9 +10910,17 @@ do_tablejump (rtx index, enum machine_mode mode, r 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. */ if (mode != Pmode) @@ -10954,7 +10962,7 @@ do_tablejump (rtx index, enum machine_mode mode, r 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; @@ -10972,7 +10980,7 @@ try_tablejump (tree index_type, tree index_expr, t 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; } Index: gcc/cfgbuild.c =================================================================== --- gcc/cfgbuild.c (revision 191879) +++ gcc/cfgbuild.c (working copy) @@ -533,6 +533,23 @@ find_bb_boundaries (basic_block bb) purge_dead_tablejump_edges (bb, table); } +/* If there is at least one edge in EDGES with a non-zero count, then + compute probabilities based on the existing counts. */ + +static bool +gen_probabilities_from_existing_counts ( VEC(edge,gc) *edges) { + edge e; + edge_iterator ei; + gcov_type count_sum = 0; + FOR_EACH_EDGE(e, ei, edges) + count_sum += e->count; + if (count_sum == 0) + return false; + FOR_EACH_EDGE(e, ei, edges) + e->probability = e->count * REG_BR_PROB_BASE / count_sum; + return true; +} + /* Assume that frequency of basic block B is known. Compute frequencies and probabilities of outgoing edges. */ @@ -560,7 +577,6 @@ compute_outgoing_frequencies (basic_block b) return; } } - if (single_succ_p (b)) { e = single_succ_edge (b); @@ -568,7 +584,10 @@ compute_outgoing_frequencies (basic_block b) e->count = b->count; return; } - guess_outgoing_edge_probabilities (b); + else if (!gen_probabilities_from_existing_counts (b->succs)){ + /* All outgoing edges of B have zero count. Guess probabilities. */ + guess_outgoing_edge_probabilities (b); + } if (b->count) FOR_EACH_EDGE (e, ei, b->succs) e->count = ((b->count * e->probability + REG_BR_PROB_BASE / 2) Index: gcc/expr.h =================================================================== --- gcc/expr.h (revision 191879) +++ gcc/expr.h (working copy) @@ -486,7 +486,7 @@ extern void do_compare_rtx_and_jump (rtx, rtx, enu /* 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" Index: gcc/stmt.c =================================================================== --- gcc/stmt.c (revision 191879) +++ gcc/stmt.c (working copy) @@ -94,11 +94,13 @@ 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; typedef struct case_node *case_node_ptr; +extern basic_block label_to_block_fn (struct function *, tree); static int n_occurrences (int, const char *); static bool tree_conflicts_with_clobbers_p (tree, HARD_REG_SET *); @@ -112,7 +114,7 @@ static void balance_case_nodes (case_node_ptr *, c 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, gcov_type, tree); /* Return the rtx-label that corresponds to a LABEL_DECL, creating it if necessary. */ @@ -1648,13 +1650,15 @@ expand_stack_restore (tree var) fixup_args_size_notes (prev, get_last_insn (), 0); } -/* 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) { + gcc_assert (prob <= REG_BR_PROB_BASE); do_compare_rtx_and_jump (op0, op1, EQ, unsignedp, mode, - NULL_RTX, NULL_RTX, label, -1); + NULL_RTX, NULL_RTX, label, prob); } /* Do the insertion of a case label into case_list. The labels are @@ -1664,7 +1668,7 @@ do_jump_if_equal (enum machine_mode mode, rtx op0, static struct case_node * add_case_node (struct case_node *head, tree low, tree high, - tree label, alloc_pool case_node_pool) + tree label, gcov_type count, alloc_pool case_node_pool) { struct case_node *r; @@ -1677,6 +1681,8 @@ add_case_node (struct case_node *head, tree low, t r->high = high; r->code_label = label; r->parent = r->left = NULL; + r->count = count; + r->subtree_count = count; r->right = head; return r; } @@ -1803,7 +1809,8 @@ expand_switch_as_decision_tree_p (tree range, static void emit_case_decision_tree (tree index_expr, tree index_type, - struct case_node *case_list, rtx default_label) + struct case_node *case_list, rtx default_label, + gcov_type default_count) { rtx index = expand_normal (index_expr); @@ -1839,15 +1846,29 @@ emit_case_decision_tree (tree index_expr, tree ind dump_case_nodes (dump_file, case_list, indent_step, 0); } - emit_case_nodes (index, case_list, default_label, index_type); + emit_case_nodes (index, case_list, default_label, default_count, index_type); if (default_label) emit_jump (default_label); } +static gcov_type +get_outgoing_edge_counts (basic_block bb) +{ + edge e; + edge_iterator ei; + gcov_type count_sum = 0; + FOR_EACH_EDGE(e, ei, bb->succs) + count_sum += e->count; + return count_sum; +} + +#define case_probability(x, y) \ + ((y) ? (gcc_assert (x <= y), (x) * REG_BR_PROB_BASE / (y)) : -1) + /* Generate a dispatch tabler, switching on INDEX_EXPR and jumping to one of the labels in CASE_LIST or to the DEFAULT_LABEL. MINVAL, MAXVAL, and RANGE are the extrema and range of the case - labels in CASE_LIST. + labels in CASE_LIST. STMT_BB is the basic block containing the statement. First, a jump insn is emitted. First we try "casesi". If that fails, try "tablejump". A target *must* have one of them (or both). @@ -1860,19 +1881,23 @@ emit_case_decision_tree (tree index_expr, tree ind static void emit_case_dispatch_table (tree index_expr, tree index_type, struct case_node *case_list, rtx default_label, - tree minval, tree maxval, tree range) + tree minval, tree maxval, tree range, + basic_block stmt_bb) { int i, ncases; struct case_node *n; rtx *labelvec; rtx fallback_label = label_rtx (case_list->code_label); rtx table_label = gen_label_rtx (); + bool has_gaps = false; + edge default_edge = EDGE_SUCC(stmt_bb, 0); + gcov_type default_count = default_edge->count; + gcov_type count = get_outgoing_edge_counts (stmt_bb); + bool try_with_tablejump = false; if (! try_casesi (index_type, index_expr, minval, range, table_label, default_label, fallback_label)) { - bool ok; - /* Index jumptables from zero for suitable values of minval to avoid a subtraction. For the rationale see: "http://gcc.gnu.org/ml/gcc-patches/2001-10/msg01234.html". */ @@ -1882,11 +1907,9 @@ emit_case_dispatch_table (tree index_expr, tree in { minval = build_int_cst (index_type, 0); range = maxval; + has_gaps = true; } - - ok = try_tablejump (index_type, index_expr, minval, range, - table_label, default_label); - gcc_assert (ok); + try_with_tablejump = true; } /* Get table of labels to jump to, in order of case index. */ @@ -1921,8 +1944,47 @@ emit_case_dispatch_table (tree index_expr, tree in default_label = fallback_label; for (i = 0; i < ncases; i++) if (labelvec[i] == 0) - labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); + { + has_gaps = true; + labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label); + } + int default_probability; + 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, + count); + default_count /= 2; + count -= default_count; + } + else + { + default_probability = case_probability (default_count, + count); + count -= default_count; + default_count = 0; + } + + default_edge->count = default_count; + if (count) + { + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, stmt_bb->succs) + e->probability = e->count * REG_BR_PROB_BASE / count; + } + + if (try_with_tablejump) + { + bool ok = try_tablejump (index_type, index_expr, minval, range, + table_label, default_label, default_probability); + gcc_assert (ok); + } /* Output the table. */ emit_label (table_label);