This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[pre-patch] stmt.c: case clustering, need help
- From: DJ Delorie <dj at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Tue, 27 Jul 2004 14:32:33 -0400
- Subject: [pre-patch] stmt.c: case clustering, need help
Ok, I'm working on a patch [below] to produce hybrid decision-tree and
jump-table switch statements for when the cases are "clumpy" (like 1,
2, 3, 101, 102, 103). I've got it producing the right insns, but
unfortunately, the cfg fails consistency checks at cfgrtl.c:2060
because the addr_vec is inside the BB instead of just after it. Am I
doing something wrong, or is the BB code wrong? While my patch makes
it more likely to emit jump tables at random times, I couldn't see
anything in the old code that marked them for the BB code, and it
seemed like the BBs hadn't been set up at the point where this code
runs.
/* ./cc1 dj2.c -Os */
foo(int i)
{
switch (i) {
case 6: return 2;
case 67: return 12;
case 70: return 14;
case 75: return 13;
case 82: return 9;
case 83: return 23;
case 84: return 34;
case 85: return 35;
}
}
(note 2 0 9 NOTE_INSN_DELETED)
(note 9 2 6 11 [bb 11] NOTE_INSN_BASIC_BLOCK)
(insn 6 9 7 11 (set (reg/v:SI 60 [ i ])
(mem/i:SI (reg/f:SI 53 virtual-incoming-args) [2 i+0 S4 A32])) -1 (nil)
(expr_list:REG_EQUIV (mem/i:SI (reg/f:SI 53 virtual-incoming-args) [2 i+0 S4 A32])
(nil)))
(note 7 6 8 11 NOTE_INSN_FUNCTION_BEG)
(note 8 7 10 11 NOTE_INSN_DELETED)
(note 10 8 12 [bb 0] NOTE_INSN_BASIC_BLOCK)
(insn 12 10 13 (set (reg:CCZ 17 flags)
(compare:CCZ (reg/v:SI 60 [ i ])
(const_int 6 [0x6]))) -1 (nil)
(nil))
(jump_insn 13 12 14 (set (pc)
(if_then_else (eq (reg:CCZ 17 flags)
(const_int 0 [0x0]))
(label_ref 0)
(pc))) -1 (nil)
(nil))
(insn 14 13 15 (set (reg:CCGC 17 flags)
(compare:CCGC (reg/v:SI 60 [ i ])
(const_int 6 [0x6]))) -1 (nil)
(nil))
(jump_insn 15 14 16 (set (pc)
(if_then_else (lt (reg:CCGC 17 flags)
(const_int 0 [0x0]))
(label_ref 0)
(pc))) -1 (nil)
(nil))
(insn 16 15 17 (parallel [
(set (reg:SI 61)
(plus:SI (reg/v:SI 60 [ i ])
(const_int -67 [0xffffffbd])))
(clobber (reg:CC 17 flags))
]) -1 (nil)
(nil))
(insn 17 16 18 (set (reg:CC 17 flags)
(compare:CC (reg:SI 61)
(const_int 18 [0x12]))) -1 (nil)
(nil))
(jump_insn 18 17 19 (set (pc)
(if_then_else (gtu (reg:CC 17 flags)
(const_int 0 [0x0]))
(label_ref 0)
(pc))) -1 (nil)
(nil))
(insn 19 18 20 (set (reg/f:SI 62)
(label_ref:SI 23)) -1 (nil)
(nil))
(insn 20 19 21 (set (reg:SI 63)
(mem/u/c:SI (plus:SI (mult:SI (reg:SI 61)
(const_int 4 [0x4]))
(reg/f:SI 62)) [0 S4 A8])) -1 (nil)
(nil))
(jump_insn 21 20 22 (parallel [
(set (pc)
(reg:SI 63))
(use (label_ref 23))
]) -1 (nil)
(nil))
(barrier 22 21 23)
(code_label 23 22 24 11 "" [0 uses])
(jump_insn 24 23 25 (addr_vec:SI [
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
(label_ref:SI 0)
]) -1 (nil)
(nil))
(barrier 25 24 26)
(jump_insn 26 25 27 (set (pc)
(label_ref 0)) -1 (nil)
(nil))
(barrier 27 26 0)
(nil)
-------------------- consistency check is here --------------------
(barrier 25 24 26)
dj2.c: In function `foo':
dj2.c:13: internal compiler error: Segmentation fault
Please submit a full bug report,
with preprocessed source if appropriate.
See <URL:http://gcc.gnu.org/bugs.html> for instructions.
Index: stmt.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/stmt.c,v
retrieving revision 1.381
diff -p -U1 -r1.381 stmt.c
--- stmt.c 21 Jul 2004 19:23:02 -0000 1.381
+++ stmt.c 27 Jul 2004 18:23:50 -0000
@@ -95,2 +95,3 @@ struct case_node GTY(())
struct case_node *right; /* Right son in binary tree; also node chain */
+ int table_set; /* 0 means binary test, else grouped by val */
struct case_node *parent; /* Parent of node in binary tree */
@@ -272,3 +273,6 @@ static int node_has_high_bound (case_nod
static int node_is_bounded (case_node_ptr, tree);
-static void emit_case_nodes (rtx, case_node_ptr, rtx, tree);
+static int emit_case_nodes (rtx, tree, case_node_ptr, rtx, tree);
+static void dj_emit_case_table (tree, case_node_ptr, rtx, tree);
+static void dj_scan_for_case_clusters (case_node *, tree);
+static void dj_dump_case_nodes (struct case_node *, int);
@@ -2705,2 +2709,19 @@ emit_case_bit_tests (tree index_type, tr
+static void
+dj_dump_case_nodes(struct case_node *root, int indent)
+{
+ int h, l;
+ if (root == 0)
+ return;
+ dj_dump_case_nodes (root->left, indent+3);
+ h = (int)TREE_INT_CST_LOW(root->high);
+ l = (int)TREE_INT_CST_LOW(root->low);
+ if (h == l)
+ printf("%*s%d", indent, "", l);
+ else
+ printf("%*s%d .. %d", indent, "", l, h);
+ printf(" (%d)\n", root->table_set);
+ dj_dump_case_nodes (root->right, indent+3);
+}
+
/* Terminate a case (Pascal) or switch (C) statement
@@ -2719,6 +2740,2 @@ expand_end_case_type (tree orig_index, t
rtx index;
- rtx table_label;
- int ncases;
- rtx *labelvec;
- int i;
rtx before_case, end, lab;
@@ -2934,6 +2951,9 @@ expand_end_case_type (tree orig_index, t
&& estimate_case_costs (thiscase->data.case_stmt.case_list));
+ dj_scan_for_case_clusters (thiscase->data.case_stmt.case_list, index_type);
balance_case_nodes (&thiscase->data.case_stmt.case_list, NULL);
- emit_case_nodes (index, thiscase->data.case_stmt.case_list,
- default_label, index_type);
- emit_jump (default_label);
+ printf("\n----- final tree\n");
+ dj_dump_case_nodes (thiscase->data.case_stmt.case_list, 0);
+ if (emit_case_nodes (index, index_expr, thiscase->data.case_stmt.case_list,
+ default_label, index_type))
+ emit_jump (default_label);
}
@@ -2942,2 +2962,6 @@ expand_end_case_type (tree orig_index, t
{
+#if 1
+ dj_emit_case_table (index_expr, thiscase->data.case_stmt.case_list,
+ default_label, index_type);
+#else
table_label = gen_label_rtx ();
@@ -3012,2 +3036,3 @@ expand_end_case_type (tree orig_index, t
#endif
+#endif
}
@@ -3020,2 +3045,3 @@ expand_end_case_type (tree orig_index, t
thiscase->data.case_stmt.start);
+ debug_rtx_range (get_insns(), 0);
}
@@ -3136,2 +3162,52 @@ same_case_target_p (rtx l1, rtx l2)
+/* Scan a list of case values, group them into clusters which should
+ be emitted as tablejumps even when the overall case list indicates
+ a desicion tree. */
+
+static void
+dj_scan_for_case_clusters (case_node *list, tree index_type)
+{
+ case_node *n, *l, *last_in_cluster;
+ unsigned int count;
+ tree min_case;
+ int table_set = 0;
+
+ list->parent = 0;
+ for (n=list; n; n=n->right)
+ {
+ n->table_set = 0;
+ if (n->right)
+ n->right->parent = n;
+ }
+
+ for (n=list; n; n=n->right)
+ {
+ min_case = n->low;
+ count = 0;
+ last_in_cluster = 0;
+ for (l=n; l; l=l->right)
+ {
+ count ++;
+ if (count > case_values_threshold ()
+ && compare_tree_int (fold (build (MINUS_EXPR, index_type, l->high, min_case)),
+ (int)(optimize_size ? 3 : 10) * count) < 0)
+ last_in_cluster = l;
+ else if (last_in_cluster)
+ break;
+ }
+ if (last_in_cluster)
+ {
+ table_set ++;
+ for (l=n; l;)
+ {
+ l->table_set = table_set;
+ if (l == last_in_cluster)
+ break;
+ l = l->right;
+ }
+ n = last_in_cluster;
+ }
+ }
+}
+
/* Take an ordered list of case nodes
@@ -3160,2 +3236,10 @@ balance_case_nodes (case_node_ptr *head,
+#if 0
+ for (np2=np; np2->right; np2=np2->right);
+ printf("\nbalance_case_nodes (%d .. %d)\n",
+ TREE_INT_CST_LOW(np->low),
+ TREE_INT_CST_LOW(np2->low));
+ dj_dump_case_nodes(*head, 0);
+#endif
+
/* Count the number of entries on branch. Also count the ranges. */
@@ -3232,2 +3316,47 @@ balance_case_nodes (case_node_ptr *head,
}
+ /*printf("dj: split at %d\n", TREE_INT_CST_LOW((*npp)->low));*/
+ if ((*npp)->table_set)
+ {
+ int set = (*npp)->table_set;
+ int near_start=0, near_end=0;
+ case_node *start_node, *end_node;
+ for (start_node = *npp;
+ start_node->parent != parent
+ && start_node->parent
+ && start_node->parent->table_set == set;
+ start_node = start_node->parent)
+ near_start ++;
+ for (end_node = *npp;
+ end_node->right
+ && end_node->right->table_set == set;
+ end_node = end_node->right)
+ near_end ++;
+ /*printf("start %d dist %d end %d dist %d\n",
+ TREE_INT_CST_LOW(start_node->low), near_start,
+ TREE_INT_CST_LOW(end_node->low), near_end);*/
+
+ if (start_node->parent
+ && start_node->parent != parent
+ && start_node->parent->table_set == 0)
+ start_node = start_node->parent;
+
+ if (!start_node->parent || start_node->parent == parent)
+ start_node = 0;
+ if (!end_node->right)
+ end_node = 0;
+
+ if (!start_node && !end_node)
+ {
+ /*printf("dj: nothing left but the table\n");*/
+ return;
+ }
+
+ if (!start_node || (near_end < near_start && end_node->right))
+ npp = &(end_node->right);
+ else if (!start_node)
+ npp = head;
+ else
+ npp = &(start_node->parent->right);
+ /*printf("dj: split moved to %d\n", TREE_INT_CST_LOW((*npp)->low));*/
+ }
*head = np = *npp;
@@ -3359,2 +3488,92 @@ node_is_bounded (case_node_ptr node, tre
+
+static void
+dj_emit_case_table (tree index_expr, case_node_ptr node, rtx default_label,
+ tree index_type)
+{
+ rtx table_label;
+ case_node *n;
+ int ncases;
+ rtx *labelvec;
+ int i;
+ tree minval, maxval, range;
+
+ for (n=node; n->right; n=n->right);
+ printf("dj: dj_emit_case_table %d..%d\n", TREE_INT_CST_LOW(node->low), TREE_INT_CST_LOW(n->low));
+
+ minval = node->low;
+ maxval = n->high;
+ range = fold (build (MINUS_EXPR, index_type, maxval, minval));
+
+ table_label = gen_label_rtx ();
+ if (! try_casesi (index_type, index_expr, minval, range,
+ table_label, default_label))
+ {
+
+ /* Index jumptables from zero for suitable values of
+ minval to avoid a subtraction. */
+ if (! optimize_size
+ && compare_tree_int (minval, 0) > 0
+ && compare_tree_int (minval, 3) < 0)
+ {
+ minval = integer_zero_node;
+ range = maxval;
+ }
+
+ if (! try_tablejump (index_type, index_expr, minval, range,
+ table_label, default_label))
+ abort ();
+ }
+
+ /* Get table of labels to jump to, in order of case index. */
+
+ ncases = tree_low_cst (range, 0) + 1;
+ labelvec = alloca (ncases * sizeof (rtx));
+ memset (labelvec, 0, ncases * sizeof (rtx));
+
+ for (n = node; n; n = n->right)
+ {
+ /* Compute the low and high bounds relative to the minimum
+ value since that should fit in a HOST_WIDE_INT while the
+ actual values may not. */
+ HOST_WIDE_INT i_low
+ = tree_low_cst (fold (build (MINUS_EXPR, index_type,
+ n->low, minval)), 1);
+ HOST_WIDE_INT i_high
+ = tree_low_cst (fold (build (MINUS_EXPR, index_type,
+ n->high, minval)), 1);
+ HOST_WIDE_INT i;
+
+ for (i = i_low; i <= i_high; i ++)
+ labelvec[i]
+ = gen_rtx_LABEL_REF (Pmode, label_rtx (n->code_label));
+ }
+
+ /* Fill in the gaps with the default. */
+ for (i = 0; i < ncases; i++)
+ if (labelvec[i] == 0)
+ labelvec[i] = gen_rtx_LABEL_REF (Pmode, default_label);
+
+ /* Output the table. */
+ emit_label (table_label);
+
+ if (CASE_VECTOR_PC_RELATIVE || flag_pic)
+ emit_jump_insn (gen_rtx_ADDR_DIFF_VEC (CASE_VECTOR_MODE,
+ gen_rtx_LABEL_REF (Pmode, table_label),
+ gen_rtvec_v (ncases, labelvec),
+ const0_rtx, const0_rtx));
+ else
+ emit_jump_insn (gen_rtx_ADDR_VEC (CASE_VECTOR_MODE,
+ gen_rtvec_v (ncases, labelvec)));
+
+ /* If the case insn drops through the table,
+ after the table we must jump to the default-label.
+ Otherwise record no drop-through after the table. */
+#ifdef CASE_DROPS_THROUGH
+ emit_jump (default_label);
+#else
+ emit_barrier ();
+#endif
+}
+
/* Emit step-by-step code to select a case for the value of INDEX.
@@ -3385,4 +3604,4 @@ node_is_bounded (case_node_ptr node, tre
-static void
-emit_case_nodes (rtx index, case_node_ptr node, rtx default_label,
+static int
+emit_case_nodes (rtx index, tree index_expr, case_node_ptr node, rtx default_label,
tree index_type)
@@ -3394,2 +3613,28 @@ emit_case_nodes (rtx index, case_node_pt
+ /* If node->table_set is nonzero, then that node and all the
+ node->right in the chain represent a cluster of case nodes which
+ are appropriate for a tablejump. Note that node->left may also
+ have a cluster, so test for that too. */
+ if (node->table_set != 0 && node->right && node->table_set == node->right->table_set)
+ {
+ if (node->left)
+ {
+ tree test_label = build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
+
+ /* See if the value is on the right. */
+ emit_cmp_and_jump_insns (index,
+ convert_modes
+ (mode, imode,
+ expand_expr (node->low, NULL_RTX,
+ VOIDmode, 0),
+ unsignedp),
+ GE, NULL_RTX, mode, unsignedp,
+ label_rtx (test_label));
+ emit_case_nodes (index, index_expr, node->left, default_label, index_type);
+ expand_label (test_label);
+ }
+ dj_emit_case_table (index_expr, node, default_label, index_type);
+ return 0;
+ }
+
/* See if our parents have already tested everything for us.
@@ -3429,3 +3674,3 @@ emit_case_nodes (rtx index, case_node_pt
label_rtx (node->right->code_label));
- emit_case_nodes (index, node->left, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->left, default_label, index_type);
}
@@ -3442,3 +3687,3 @@ emit_case_nodes (rtx index, case_node_pt
label_rtx (node->left->code_label));
- emit_case_nodes (index, node->right, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->right, default_label, index_type);
}
@@ -3500,3 +3745,3 @@ emit_case_nodes (rtx index, case_node_pt
Handle the left-hand subtree. */
- emit_case_nodes (index, node->left, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->left, default_label, index_type);
/* If left-hand subtree does nothing,
@@ -3507,3 +3752,3 @@ emit_case_nodes (rtx index, case_node_pt
expand_label (test_label);
- emit_case_nodes (index, node->right, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->right, default_label, index_type);
}
@@ -3534,3 +3779,3 @@ emit_case_nodes (rtx index, case_node_pt
- emit_case_nodes (index, node->right, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->right, default_label, index_type);
}
@@ -3567,3 +3812,3 @@ emit_case_nodes (rtx index, case_node_pt
- emit_case_nodes (index, node->left, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->left, default_label, index_type);
}
@@ -3636,3 +3881,3 @@ emit_case_nodes (rtx index, case_node_pt
/* Handle the left-hand subtree. */
- emit_case_nodes (index, node->left, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->left, default_label, index_type);
@@ -3647,3 +3892,3 @@ emit_case_nodes (rtx index, case_node_pt
expand_label (test_label);
- emit_case_nodes (index, node->right, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->right, default_label, index_type);
}
@@ -3678,3 +3923,3 @@ emit_case_nodes (rtx index, case_node_pt
- emit_case_nodes (index, node->right, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->right, default_label, index_type);
}
@@ -3708,3 +3953,3 @@ emit_case_nodes (rtx index, case_node_pt
- emit_case_nodes (index, node->left, default_label, index_type);
+ emit_case_nodes (index, index_expr, node->left, default_label, index_type);
}
@@ -3767,2 +4012,3 @@ emit_case_nodes (rtx index, case_node_pt
}
+ return 1;
}