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);
