1 /* Lower GIMPLE_SWITCH expressions to something more efficient than
3 Copyright (C) 2006-2014 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3, or (at your option) any
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
22 /* This file handles the lowering of GIMPLE_SWITCH to an indexed
23 load, or a series of bit-test-and-branch expressions. */
27 #include "coretypes.h"
34 #include "stor-layout.h"
35 #include "basic-block.h"
36 #include "tree-ssa-alias.h"
37 #include "internal-fn.h"
38 #include "gimple-expr.h"
42 #include "gimple-iterator.h"
43 #include "gimplify-me.h"
44 #include "gimple-ssa.h"
47 #include "tree-phinodes.h"
48 #include "stringpool.h"
49 #include "tree-ssanames.h"
50 #include "tree-pass.h"
51 #include "gimple-pretty-print.h"
54 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
55 type in the GIMPLE type system that is language-independent? */
56 #include "langhooks.h"
58 /* Need to include expr.h and optabs.h for lshift_cheap_p. */
62 /* Maximum number of case bit tests.
63 FIXME: This should be derived from PARAM_CASE_VALUES_THRESHOLD and
64 targetm.case_values_threshold(), or be its own param. */
65 #define MAX_CASE_BIT_TESTS 3
67 /* Split the basic block at the statement pointed to by GSIP, and insert
68 a branch to the target basic block of E_TRUE conditional on tree
71 It is assumed that there is already an edge from the to-be-split
72 basic block to E_TRUE->dest block. This edge is removed, and the
73 profile information on the edge is re-used for the new conditional
76 The CFG is updated. The dominator tree will not be valid after
77 this transformation, but the immediate dominators are updated if
78 UPDATE_DOMINATORS is true.
80 Returns the newly created basic block. */
83 hoist_edge_and_branch_if_true (gimple_stmt_iterator
*gsip
,
84 tree cond
, edge e_true
,
85 bool update_dominators
)
90 basic_block new_bb
, split_bb
= gsi_bb (*gsip
);
91 bool dominated_e_true
= false;
93 gcc_assert (e_true
->src
== split_bb
);
96 && get_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
) == split_bb
)
97 dominated_e_true
= true;
99 tmp
= force_gimple_operand_gsi (gsip
, cond
, /*simple=*/true, NULL
,
100 /*before=*/true, GSI_SAME_STMT
);
101 cond_stmt
= gimple_build_cond_from_tree (tmp
, NULL_TREE
, NULL_TREE
);
102 gsi_insert_before (gsip
, cond_stmt
, GSI_SAME_STMT
);
104 e_false
= split_block (split_bb
, cond_stmt
);
105 new_bb
= e_false
->dest
;
106 redirect_edge_pred (e_true
, split_bb
);
108 e_true
->flags
&= ~EDGE_FALLTHRU
;
109 e_true
->flags
|= EDGE_TRUE_VALUE
;
111 e_false
->flags
&= ~EDGE_FALLTHRU
;
112 e_false
->flags
|= EDGE_FALSE_VALUE
;
113 e_false
->probability
= REG_BR_PROB_BASE
- e_true
->probability
;
114 e_false
->count
= split_bb
->count
- e_true
->count
;
115 new_bb
->count
= e_false
->count
;
117 if (update_dominators
)
119 if (dominated_e_true
)
120 set_immediate_dominator (CDI_DOMINATORS
, e_true
->dest
, split_bb
);
121 set_immediate_dominator (CDI_DOMINATORS
, e_false
->dest
, split_bb
);
128 /* Return true if a switch should be expanded as a bit test.
129 RANGE is the difference between highest and lowest case.
130 UNIQ is number of unique case node targets, not counting the default case.
131 COUNT is the number of comparisons needed, not counting the default case. */
134 expand_switch_using_bit_tests_p (tree range
,
136 unsigned int count
, bool speed_p
)
138 return (((uniq
== 1 && count
>= 3)
139 || (uniq
== 2 && count
>= 5)
140 || (uniq
== 3 && count
>= 6))
141 && lshift_cheap_p (speed_p
)
142 && compare_tree_int (range
, GET_MODE_BITSIZE (word_mode
)) < 0
143 && compare_tree_int (range
, 0) > 0);
146 /* Implement switch statements with bit tests
148 A GIMPLE switch statement can be expanded to a short sequence of bit-wise
149 comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
150 where CST and MINVAL are integer constants. This is better than a series
151 of compare-and-banch insns in some cases, e.g. we can implement:
153 if ((x==4) || (x==6) || (x==9) || (x==11))
155 as a single bit test:
157 if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
159 This transformation is only applied if the number of case targets is small,
160 if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
161 performed in "word_mode".
163 The following example shows the code the transformation generates:
169 case '0': case '1': case '2': case '3': case '4':
170 case '5': case '6': case '7': case '8': case '9':
171 case 'A': case 'B': case 'C': case 'D': case 'E':
183 if (tmp1 > (70 - 48)) goto L2;
185 tmp3 = 0b11111100000001111111111;
186 if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
193 TODO: There are still some improvements to this transformation that could
196 * A narrower mode than word_mode could be used if that is cheaper, e.g.
197 for x86_64 where a narrower-mode shift may result in smaller code.
199 * The compounded constant could be shifted rather than the one. The
200 test would be either on the sign bit or on the least significant bit,
201 depending on the direction of the shift. On some machines, the test
202 for the branch would be free if the bit to test is already set by the
205 This transformation was contributed by Roger Sayle, see this e-mail:
206 http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
209 /* A case_bit_test represents a set of case nodes that may be
210 selected from using a bit-wise comparison. HI and LO hold
211 the integer to be tested against, TARGET_EDGE contains the
212 edge to the basic block to jump to upon success and BITS
213 counts the number of case nodes handled by this test,
214 typically the number of bits set in HI:LO. The LABEL field
215 is used to quickly identify all cases in this set without
216 looking at label_to_block for every case label. */
226 /* Comparison function for qsort to order bit tests by decreasing
227 probability of execution. Our best guess comes from a measured
228 profile. If the profile counts are equal, break even on the
229 number of case nodes, i.e. the node with the most cases gets
232 TODO: Actually this currently runs before a profile is available.
233 Therefore the case-as-bit-tests transformation should be done
234 later in the pass pipeline, or something along the lines of
235 "Efficient and effective branch reordering using profile data"
236 (Yang et. al., 2002) should be implemented (although, how good
237 is a paper is called "Efficient and effective ..." when the
238 latter is implied by the former, but oh well...). */
241 case_bit_test_cmp (const void *p1
, const void *p2
)
243 const struct case_bit_test
*const d1
= (const struct case_bit_test
*) p1
;
244 const struct case_bit_test
*const d2
= (const struct case_bit_test
*) p2
;
246 if (d2
->target_edge
->count
!= d1
->target_edge
->count
)
247 return d2
->target_edge
->count
- d1
->target_edge
->count
;
248 if (d2
->bits
!= d1
->bits
)
249 return d2
->bits
- d1
->bits
;
251 /* Stabilize the sort. */
252 return LABEL_DECL_UID (d2
->label
) - LABEL_DECL_UID (d1
->label
);
255 /* Expand a switch statement by a short sequence of bit-wise
256 comparisons. "switch(x)" is effectively converted into
257 "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
260 INDEX_EXPR is the value being switched on.
262 MINVAL is the lowest case value of in the case nodes,
263 and RANGE is highest value minus MINVAL. MINVAL and RANGE
264 are not guaranteed to be of the same type as INDEX_EXPR
265 (the gimplifier doesn't change the type of case label values,
266 and MINVAL and RANGE are derived from those values).
267 MAXVAL is MINVAL + RANGE.
269 There *MUST* be MAX_CASE_BIT_TESTS or less unique case
273 emit_case_bit_tests (gimple swtch
, tree index_expr
,
274 tree minval
, tree range
, tree maxval
)
276 struct case_bit_test test
[MAX_CASE_BIT_TESTS
];
277 unsigned int i
, j
, k
;
280 basic_block switch_bb
= gimple_bb (swtch
);
281 basic_block default_bb
, new_default_bb
, new_bb
;
283 bool update_dom
= dom_info_available_p (CDI_DOMINATORS
);
285 vec
<basic_block
> bbs_to_fix_dom
= vNULL
;
287 tree index_type
= TREE_TYPE (index_expr
);
288 tree unsigned_index_type
= unsigned_type_for (index_type
);
289 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
291 gimple_stmt_iterator gsi
;
295 tree word_type_node
= lang_hooks
.types
.type_for_mode (word_mode
, 1);
296 tree word_mode_zero
= fold_convert (word_type_node
, integer_zero_node
);
297 tree word_mode_one
= fold_convert (word_type_node
, integer_one_node
);
298 int prec
= TYPE_PRECISION (word_type_node
);
299 wide_int wone
= wi::one (prec
);
301 memset (&test
, 0, sizeof (test
));
303 /* Get the edge for the default case. */
304 tmp
= gimple_switch_default_label (swtch
);
305 default_bb
= label_to_block (CASE_LABEL (tmp
));
306 default_edge
= find_edge (switch_bb
, default_bb
);
308 /* Go through all case labels, and collect the case labels, profile
309 counts, and other information we need to build the branch tests. */
311 for (i
= 1; i
< branch_num
; i
++)
314 tree cs
= gimple_switch_label (swtch
, i
);
315 tree label
= CASE_LABEL (cs
);
316 edge e
= find_edge (switch_bb
, label_to_block (label
));
317 for (k
= 0; k
< count
; k
++)
318 if (e
== test
[k
].target_edge
)
323 gcc_checking_assert (count
< MAX_CASE_BIT_TESTS
);
324 test
[k
].mask
= wi::zero (prec
);
325 test
[k
].target_edge
= e
;
326 test
[k
].label
= label
;
333 lo
= tree_to_uhwi (int_const_binop (MINUS_EXPR
,
334 CASE_LOW (cs
), minval
));
335 if (CASE_HIGH (cs
) == NULL_TREE
)
338 hi
= tree_to_uhwi (int_const_binop (MINUS_EXPR
,
339 CASE_HIGH (cs
), minval
));
341 for (j
= lo
; j
<= hi
; j
++)
342 test
[k
].mask
|= wi::lshift (wone
, j
);
345 qsort (test
, count
, sizeof (*test
), case_bit_test_cmp
);
347 /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
348 the minval subtractions, but it might make the mask constants more
349 expensive. So, compare the costs. */
350 if (compare_tree_int (minval
, 0) > 0
351 && compare_tree_int (maxval
, GET_MODE_BITSIZE (word_mode
)) < 0)
354 HOST_WIDE_INT m
= tree_to_uhwi (minval
);
355 rtx reg
= gen_raw_REG (word_mode
, 10000);
356 bool speed_p
= optimize_bb_for_speed_p (gimple_bb (swtch
));
357 cost_diff
= set_rtx_cost (gen_rtx_PLUS (word_mode
, reg
,
358 GEN_INT (-m
)), speed_p
);
359 for (i
= 0; i
< count
; i
++)
361 rtx r
= immed_wide_int_const (test
[i
].mask
, word_mode
);
362 cost_diff
+= set_src_cost (gen_rtx_AND (word_mode
, reg
, r
), speed_p
);
363 r
= immed_wide_int_const (wi::lshift (test
[i
].mask
, m
), word_mode
);
364 cost_diff
-= set_src_cost (gen_rtx_AND (word_mode
, reg
, r
), speed_p
);
368 for (i
= 0; i
< count
; i
++)
369 test
[i
].mask
= wi::lshift (test
[i
].mask
, m
);
370 minval
= build_zero_cst (TREE_TYPE (minval
));
375 /* We generate two jumps to the default case label.
376 Split the default edge, so that we don't have to do any PHI node
378 new_default_bb
= split_edge (default_edge
);
382 bbs_to_fix_dom
.create (10);
383 bbs_to_fix_dom
.quick_push (switch_bb
);
384 bbs_to_fix_dom
.quick_push (default_bb
);
385 bbs_to_fix_dom
.quick_push (new_default_bb
);
388 /* Now build the test-and-branch code. */
390 gsi
= gsi_last_bb (switch_bb
);
392 /* idx = (unsigned)x - minval. */
393 idx
= fold_convert (unsigned_index_type
, index_expr
);
394 idx
= fold_build2 (MINUS_EXPR
, unsigned_index_type
, idx
,
395 fold_convert (unsigned_index_type
, minval
));
396 idx
= force_gimple_operand_gsi (&gsi
, idx
,
397 /*simple=*/true, NULL_TREE
,
398 /*before=*/true, GSI_SAME_STMT
);
400 /* if (idx > range) goto default */
401 range
= force_gimple_operand_gsi (&gsi
,
402 fold_convert (unsigned_index_type
, range
),
403 /*simple=*/true, NULL_TREE
,
404 /*before=*/true, GSI_SAME_STMT
);
405 tmp
= fold_build2 (GT_EXPR
, boolean_type_node
, idx
, range
);
406 new_bb
= hoist_edge_and_branch_if_true (&gsi
, tmp
, default_edge
, update_dom
);
408 bbs_to_fix_dom
.quick_push (new_bb
);
409 gcc_assert (gimple_bb (swtch
) == new_bb
);
410 gsi
= gsi_last_bb (new_bb
);
412 /* Any blocks dominated by the GIMPLE_SWITCH, but that are not successors
413 of NEW_BB, are still immediately dominated by SWITCH_BB. Make it so. */
416 vec
<basic_block
> dom_bbs
;
419 dom_bbs
= get_dominated_by (CDI_DOMINATORS
, new_bb
);
420 FOR_EACH_VEC_ELT (dom_bbs
, i
, dom_son
)
422 edge e
= find_edge (new_bb
, dom_son
);
423 if (e
&& single_pred_p (e
->dest
))
425 set_immediate_dominator (CDI_DOMINATORS
, dom_son
, switch_bb
);
426 bbs_to_fix_dom
.safe_push (dom_son
);
431 /* csui = (1 << (word_mode) idx) */
432 csui
= make_ssa_name (word_type_node
, NULL
);
433 tmp
= fold_build2 (LSHIFT_EXPR
, word_type_node
, word_mode_one
,
434 fold_convert (word_type_node
, idx
));
435 tmp
= force_gimple_operand_gsi (&gsi
, tmp
,
436 /*simple=*/false, NULL_TREE
,
437 /*before=*/true, GSI_SAME_STMT
);
438 shift_stmt
= gimple_build_assign (csui
, tmp
);
439 gsi_insert_before (&gsi
, shift_stmt
, GSI_SAME_STMT
);
440 update_stmt (shift_stmt
);
442 /* for each unique set of cases:
443 if (const & csui) goto target */
444 for (k
= 0; k
< count
; k
++)
446 tmp
= wide_int_to_tree (word_type_node
, test
[k
].mask
);
447 tmp
= fold_build2 (BIT_AND_EXPR
, word_type_node
, csui
, tmp
);
448 tmp
= force_gimple_operand_gsi (&gsi
, tmp
,
449 /*simple=*/true, NULL_TREE
,
450 /*before=*/true, GSI_SAME_STMT
);
451 tmp
= fold_build2 (NE_EXPR
, boolean_type_node
, tmp
, word_mode_zero
);
452 new_bb
= hoist_edge_and_branch_if_true (&gsi
, tmp
, test
[k
].target_edge
,
455 bbs_to_fix_dom
.safe_push (new_bb
);
456 gcc_assert (gimple_bb (swtch
) == new_bb
);
457 gsi
= gsi_last_bb (new_bb
);
460 /* We should have removed all edges now. */
461 gcc_assert (EDGE_COUNT (gsi_bb (gsi
)->succs
) == 0);
463 /* If nothing matched, go to the default label. */
464 make_edge (gsi_bb (gsi
), new_default_bb
, EDGE_FALLTHRU
);
466 /* The GIMPLE_SWITCH is now redundant. */
467 gsi_remove (&gsi
, true);
471 /* Fix up the dominator tree. */
472 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
473 bbs_to_fix_dom
.release ();
478 Switch initialization conversion
480 The following pass changes simple initializations of scalars in a switch
481 statement into initializations from a static array. Obviously, the values
482 must be constant and known at compile time and a default branch must be
483 provided. For example, the following code:
507 a_5 = PHI <a_1, a_2, a_3, a_4>
508 b_5 = PHI <b_1, b_2, b_3, b_4>
513 static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
514 static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
517 if (((unsigned) argc) - 1 < 11)
519 a_6 = CSWTCH02[argc - 1];
520 b_6 = CSWTCH01[argc - 1];
530 There are further constraints. Specifically, the range of values across all
531 case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
532 eight) times the number of the actual switch branches.
534 This transformation was contributed by Martin Jambor, see this e-mail:
535 http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
537 /* The main structure of the pass. */
538 struct switch_conv_info
540 /* The expression used to decide the switch branch. */
543 /* The following integer constants store the minimum and maximum value
544 covered by the case labels. */
548 /* The difference between the above two numbers. Stored here because it
549 is used in all the conversion heuristics, as well as for some of the
550 transformation, and it is expensive to re-compute it all the time. */
553 /* Basic block that contains the actual GIMPLE_SWITCH. */
554 basic_block switch_bb
;
556 /* Basic block that is the target of the default case. */
557 basic_block default_bb
;
559 /* The single successor block of all branches out of the GIMPLE_SWITCH,
560 if such a block exists. Otherwise NULL. */
561 basic_block final_bb
;
563 /* The probability of the default edge in the replaced switch. */
566 /* The count of the default edge in the replaced switch. */
567 gcov_type default_count
;
569 /* Combined count of all other (non-default) edges in the replaced switch. */
570 gcov_type other_count
;
572 /* Number of phi nodes in the final bb (that we'll be replacing). */
575 /* Array of default values, in the same order as phi nodes. */
576 tree
*default_values
;
578 /* Constructors of new static arrays. */
579 vec
<constructor_elt
, va_gc
> **constructors
;
581 /* Array of ssa names that are initialized with a value from a new static
583 tree
*target_inbound_names
;
585 /* Array of ssa names that are initialized with the default value if the
586 switch expression is out of range. */
587 tree
*target_outbound_names
;
589 /* The first load statement that loads a temporary from a new static array.
591 gimple arr_ref_first
;
593 /* The last load statement that loads a temporary from a new static array. */
596 /* String reason why the case wasn't a good candidate that is written to the
597 dump file, if there is one. */
600 /* Parameters for expand_switch_using_bit_tests. Should be computed
601 the same way as in expand_case. */
606 /* Collect information about GIMPLE_SWITCH statement SWTCH into INFO. */
609 collect_switch_conv_info (gimple swtch
, struct switch_conv_info
*info
)
611 unsigned int branch_num
= gimple_switch_num_labels (swtch
);
612 tree min_case
, max_case
;
613 unsigned int count
, i
;
617 memset (info
, 0, sizeof (*info
));
619 /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
620 is a default label which is the first in the vector.
621 Collect the bits we can deduce from the CFG. */
622 info
->index_expr
= gimple_switch_index (swtch
);
623 info
->switch_bb
= gimple_bb (swtch
);
625 label_to_block (CASE_LABEL (gimple_switch_default_label (swtch
)));
626 e_default
= find_edge (info
->switch_bb
, info
->default_bb
);
627 info
->default_prob
= e_default
->probability
;
628 info
->default_count
= e_default
->count
;
629 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
631 info
->other_count
+= e
->count
;
633 /* See if there is one common successor block for all branch
634 targets. If it exists, record it in FINAL_BB.
635 Start with the destination of the default case as guess
636 or its destination in case it is a forwarder block. */
637 if (! single_pred_p (e_default
->dest
))
638 info
->final_bb
= e_default
->dest
;
639 else if (single_succ_p (e_default
->dest
)
640 && ! single_pred_p (single_succ (e_default
->dest
)))
641 info
->final_bb
= single_succ (e_default
->dest
);
642 /* Require that all switch destinations are either that common
643 FINAL_BB or a forwarder to it. */
645 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
647 if (e
->dest
== info
->final_bb
)
650 if (single_pred_p (e
->dest
)
651 && single_succ_p (e
->dest
)
652 && single_succ (e
->dest
) == info
->final_bb
)
655 info
->final_bb
= NULL
;
659 /* Get upper and lower bounds of case values, and the covered range. */
660 min_case
= gimple_switch_label (swtch
, 1);
661 max_case
= gimple_switch_label (swtch
, branch_num
- 1);
663 info
->range_min
= CASE_LOW (min_case
);
664 if (CASE_HIGH (max_case
) != NULL_TREE
)
665 info
->range_max
= CASE_HIGH (max_case
);
667 info
->range_max
= CASE_LOW (max_case
);
670 int_const_binop (MINUS_EXPR
, info
->range_max
, info
->range_min
);
672 /* Get a count of the number of case labels. Single-valued case labels
673 simply count as one, but a case range counts double, since it may
674 require two compares if it gets lowered as a branching tree. */
676 for (i
= 1; i
< branch_num
; i
++)
678 tree elt
= gimple_switch_label (swtch
, i
);
681 && ! tree_int_cst_equal (CASE_LOW (elt
), CASE_HIGH (elt
)))
686 /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
687 block. Assume a CFG cleanup would have already removed degenerate
688 switch statements, this allows us to just use EDGE_COUNT. */
689 info
->uniq
= EDGE_COUNT (gimple_bb (swtch
)->succs
) - 1;
692 /* Checks whether the range given by individual case statements of the SWTCH
693 switch statement isn't too big and whether the number of branches actually
694 satisfies the size of the new array. */
697 check_range (struct switch_conv_info
*info
)
699 gcc_assert (info
->range_size
);
700 if (!tree_fits_uhwi_p (info
->range_size
))
702 info
->reason
= "index range way too large or otherwise unusable";
706 if (tree_to_uhwi (info
->range_size
)
707 > ((unsigned) info
->count
* SWITCH_CONVERSION_BRANCH_RATIO
))
709 info
->reason
= "the maximum range-branch ratio exceeded";
716 /* Checks whether all but the FINAL_BB basic blocks are empty. */
719 check_all_empty_except_final (struct switch_conv_info
*info
)
724 FOR_EACH_EDGE (e
, ei
, info
->switch_bb
->succs
)
726 if (e
->dest
== info
->final_bb
)
729 if (!empty_block_p (e
->dest
))
731 info
->reason
= "bad case - a non-final BB not empty";
739 /* This function checks whether all required values in phi nodes in final_bb
740 are constants. Required values are those that correspond to a basic block
741 which is a part of the examined switch statement. It returns true if the
742 phi nodes are OK, otherwise false. */
745 check_final_bb (struct switch_conv_info
*info
)
747 gimple_stmt_iterator gsi
;
750 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
752 gimple phi
= gsi_stmt (gsi
);
757 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
759 basic_block bb
= gimple_phi_arg_edge (phi
, i
)->src
;
761 if (bb
== info
->switch_bb
762 || (single_pred_p (bb
) && single_pred (bb
) == info
->switch_bb
))
766 val
= gimple_phi_arg_def (phi
, i
);
767 if (!is_gimple_ip_invariant (val
))
769 info
->reason
= "non-invariant value from a case";
770 return false; /* Non-invariant argument. */
772 reloc
= initializer_constant_valid_p (val
, TREE_TYPE (val
));
773 if ((flag_pic
&& reloc
!= null_pointer_node
)
774 || (!flag_pic
&& reloc
== NULL_TREE
))
778 = "value from a case would need runtime relocations";
781 = "value from a case is not a valid initializer";
791 /* The following function allocates default_values, target_{in,out}_names and
792 constructors arrays. The last one is also populated with pointers to
793 vectors that will become constructors of new arrays. */
796 create_temp_arrays (struct switch_conv_info
*info
)
800 info
->default_values
= XCNEWVEC (tree
, info
->phi_count
* 3);
801 /* ??? Macros do not support multi argument templates in their
802 argument list. We create a typedef to work around that problem. */
803 typedef vec
<constructor_elt
, va_gc
> *vec_constructor_elt_gc
;
804 info
->constructors
= XCNEWVEC (vec_constructor_elt_gc
, info
->phi_count
);
805 info
->target_inbound_names
= info
->default_values
+ info
->phi_count
;
806 info
->target_outbound_names
= info
->target_inbound_names
+ info
->phi_count
;
807 for (i
= 0; i
< info
->phi_count
; i
++)
808 vec_alloc (info
->constructors
[i
], tree_to_uhwi (info
->range_size
) + 1);
811 /* Free the arrays created by create_temp_arrays(). The vectors that are
812 created by that function are not freed here, however, because they have
813 already become constructors and must be preserved. */
816 free_temp_arrays (struct switch_conv_info
*info
)
818 XDELETEVEC (info
->constructors
);
819 XDELETEVEC (info
->default_values
);
822 /* Populate the array of default values in the order of phi nodes.
823 DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch. */
826 gather_default_values (tree default_case
, struct switch_conv_info
*info
)
828 gimple_stmt_iterator gsi
;
829 basic_block bb
= label_to_block (CASE_LABEL (default_case
));
833 gcc_assert (CASE_LOW (default_case
) == NULL_TREE
);
835 if (bb
== info
->final_bb
)
836 e
= find_edge (info
->switch_bb
, bb
);
838 e
= single_succ_edge (bb
);
840 for (gsi
= gsi_start_phis (info
->final_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
842 gimple phi
= gsi_stmt (gsi
);
843 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
845 info
->default_values
[i
++] = val
;
849 /* The following function populates the vectors in the constructors array with
850 future contents of the static arrays. The vectors are populated in the
851 order of phi nodes. SWTCH is the switch statement being converted. */
854 build_constructors (gimple swtch
, struct switch_conv_info
*info
)
856 unsigned i
, branch_num
= gimple_switch_num_labels (swtch
);
857 tree pos
= info
->range_min
;
859 for (i
= 1; i
< branch_num
; i
++)
861 tree cs
= gimple_switch_label (swtch
, i
);
862 basic_block bb
= label_to_block (CASE_LABEL (cs
));
865 gimple_stmt_iterator gsi
;
868 if (bb
== info
->final_bb
)
869 e
= find_edge (info
->switch_bb
, bb
);
871 e
= single_succ_edge (bb
);
874 while (tree_int_cst_lt (pos
, CASE_LOW (cs
)))
877 for (k
= 0; k
< info
->phi_count
; k
++)
881 elt
.index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
883 = unshare_expr_without_location (info
->default_values
[k
]);
884 info
->constructors
[k
]->quick_push (elt
);
887 pos
= int_const_binop (PLUS_EXPR
, pos
,
888 build_int_cst (TREE_TYPE (pos
), 1));
890 gcc_assert (tree_int_cst_equal (pos
, CASE_LOW (cs
)));
894 high
= CASE_HIGH (cs
);
896 high
= CASE_LOW (cs
);
897 for (gsi
= gsi_start_phis (info
->final_bb
);
898 !gsi_end_p (gsi
); gsi_next (&gsi
))
900 gimple phi
= gsi_stmt (gsi
);
901 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
902 tree low
= CASE_LOW (cs
);
909 elt
.index
= int_const_binop (MINUS_EXPR
, pos
, info
->range_min
);
910 elt
.value
= unshare_expr_without_location (val
);
911 info
->constructors
[j
]->quick_push (elt
);
913 pos
= int_const_binop (PLUS_EXPR
, pos
,
914 build_int_cst (TREE_TYPE (pos
), 1));
915 } while (!tree_int_cst_lt (high
, pos
)
916 && tree_int_cst_lt (low
, pos
));
922 /* If all values in the constructor vector are the same, return the value.
923 Otherwise return NULL_TREE. Not supposed to be called for empty
927 constructor_contains_same_values_p (vec
<constructor_elt
, va_gc
> *vec
)
930 tree prev
= NULL_TREE
;
931 constructor_elt
*elt
;
933 FOR_EACH_VEC_SAFE_ELT (vec
, i
, elt
)
937 else if (!operand_equal_p (elt
->value
, prev
, OEP_ONLY_CONST
))
943 /* Return type which should be used for array elements, either TYPE,
944 or for integral type some smaller integral type that can still hold
945 all the constants. */
948 array_value_type (gimple swtch
, tree type
, int num
,
949 struct switch_conv_info
*info
)
951 unsigned int i
, len
= vec_safe_length (info
->constructors
[num
]);
952 constructor_elt
*elt
;
953 enum machine_mode mode
;
957 if (!INTEGRAL_TYPE_P (type
))
960 mode
= GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type
)));
961 if (GET_MODE_SIZE (TYPE_MODE (type
)) <= GET_MODE_SIZE (mode
))
964 if (len
< (optimize_bb_for_size_p (gimple_bb (swtch
)) ? 2 : 32))
967 FOR_EACH_VEC_SAFE_ELT (info
->constructors
[num
], i
, elt
)
971 if (TREE_CODE (elt
->value
) != INTEGER_CST
)
977 unsigned int prec
= GET_MODE_BITSIZE (mode
);
978 if (prec
> HOST_BITS_PER_WIDE_INT
)
981 if (sign
>= 0 && cst
== wi::zext (cst
, prec
))
983 if (sign
== 0 && cst
== wi::sext (cst
, prec
))
988 if (sign
<= 0 && cst
== wi::sext (cst
, prec
))
997 mode
= GET_MODE_WIDER_MODE (mode
);
999 || GET_MODE_SIZE (mode
) >= GET_MODE_SIZE (TYPE_MODE (type
)))
1005 sign
= TYPE_UNSIGNED (type
) ? 1 : -1;
1006 smaller_type
= lang_hooks
.types
.type_for_mode (mode
, sign
>= 0);
1007 if (GET_MODE_SIZE (TYPE_MODE (type
))
1008 <= GET_MODE_SIZE (TYPE_MODE (smaller_type
)))
1011 return smaller_type
;
1014 /* Create an appropriate array type and declaration and assemble a static array
1015 variable. Also create a load statement that initializes the variable in
1016 question with a value from the static array. SWTCH is the switch statement
1017 being converted, NUM is the index to arrays of constructors, default values
1018 and target SSA names for this particular array. ARR_INDEX_TYPE is the type
1019 of the index of the new array, PHI is the phi node of the final BB that
1020 corresponds to the value that will be loaded from the created array. TIDX
1021 is an ssa name of a temporary variable holding the index for loads from the
1025 build_one_array (gimple swtch
, int num
, tree arr_index_type
, gimple phi
,
1026 tree tidx
, struct switch_conv_info
*info
)
1030 gimple_stmt_iterator gsi
= gsi_for_stmt (swtch
);
1031 location_t loc
= gimple_location (swtch
);
1033 gcc_assert (info
->default_values
[num
]);
1035 name
= copy_ssa_name (PHI_RESULT (phi
), NULL
);
1036 info
->target_inbound_names
[num
] = name
;
1038 cst
= constructor_contains_same_values_p (info
->constructors
[num
]);
1040 load
= gimple_build_assign (name
, cst
);
1043 tree array_type
, ctor
, decl
, value_type
, fetch
, default_type
;
1045 default_type
= TREE_TYPE (info
->default_values
[num
]);
1046 value_type
= array_value_type (swtch
, default_type
, num
, info
);
1047 array_type
= build_array_type (value_type
, arr_index_type
);
1048 if (default_type
!= value_type
)
1051 constructor_elt
*elt
;
1053 FOR_EACH_VEC_SAFE_ELT (info
->constructors
[num
], i
, elt
)
1054 elt
->value
= fold_convert (value_type
, elt
->value
);
1056 ctor
= build_constructor (array_type
, info
->constructors
[num
]);
1057 TREE_CONSTANT (ctor
) = true;
1058 TREE_STATIC (ctor
) = true;
1060 decl
= build_decl (loc
, VAR_DECL
, NULL_TREE
, array_type
);
1061 TREE_STATIC (decl
) = 1;
1062 DECL_INITIAL (decl
) = ctor
;
1064 DECL_NAME (decl
) = create_tmp_var_name ("CSWTCH");
1065 DECL_ARTIFICIAL (decl
) = 1;
1066 TREE_CONSTANT (decl
) = 1;
1067 TREE_READONLY (decl
) = 1;
1068 varpool_node::finalize_decl (decl
);
1070 fetch
= build4 (ARRAY_REF
, value_type
, decl
, tidx
, NULL_TREE
,
1072 if (default_type
!= value_type
)
1074 fetch
= fold_convert (default_type
, fetch
);
1075 fetch
= force_gimple_operand_gsi (&gsi
, fetch
, true, NULL_TREE
,
1076 true, GSI_SAME_STMT
);
1078 load
= gimple_build_assign (name
, fetch
);
1081 gsi_insert_before (&gsi
, load
, GSI_SAME_STMT
);
1083 info
->arr_ref_last
= load
;
1086 /* Builds and initializes static arrays initialized with values gathered from
1087 the SWTCH switch statement. Also creates statements that load values from
1091 build_arrays (gimple swtch
, struct switch_conv_info
*info
)
1093 tree arr_index_type
;
1094 tree tidx
, sub
, utype
;
1096 gimple_stmt_iterator gsi
;
1098 location_t loc
= gimple_location (swtch
);
1100 gsi
= gsi_for_stmt (swtch
);
1102 /* Make sure we do not generate arithmetics in a subrange. */
1103 utype
= TREE_TYPE (info
->index_expr
);
1104 if (TREE_TYPE (utype
))
1105 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (TREE_TYPE (utype
)), 1);
1107 utype
= lang_hooks
.types
.type_for_mode (TYPE_MODE (utype
), 1);
1109 arr_index_type
= build_index_type (info
->range_size
);
1110 tidx
= make_ssa_name (utype
, NULL
);
1111 sub
= fold_build2_loc (loc
, MINUS_EXPR
, utype
,
1112 fold_convert_loc (loc
, utype
, info
->index_expr
),
1113 fold_convert_loc (loc
, utype
, info
->range_min
));
1114 sub
= force_gimple_operand_gsi (&gsi
, sub
,
1115 false, NULL
, true, GSI_SAME_STMT
);
1116 stmt
= gimple_build_assign (tidx
, sub
);
1118 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1120 info
->arr_ref_first
= stmt
;
1122 for (gsi
= gsi_start_phis (info
->final_bb
), i
= 0;
1123 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
1124 build_one_array (swtch
, i
, arr_index_type
, gsi_stmt (gsi
), tidx
, info
);
1127 /* Generates and appropriately inserts loads of default values at the position
1128 given by BSI. Returns the last inserted statement. */
1131 gen_def_assigns (gimple_stmt_iterator
*gsi
, struct switch_conv_info
*info
)
1134 gimple assign
= NULL
;
1136 for (i
= 0; i
< info
->phi_count
; i
++)
1138 tree name
= copy_ssa_name (info
->target_inbound_names
[i
], NULL
);
1139 info
->target_outbound_names
[i
] = name
;
1140 assign
= gimple_build_assign (name
, info
->default_values
[i
]);
1141 gsi_insert_before (gsi
, assign
, GSI_SAME_STMT
);
1142 update_stmt (assign
);
1147 /* Deletes the unused bbs and edges that now contain the switch statement and
1148 its empty branch bbs. BBD is the now dead BB containing the original switch
1149 statement, FINAL is the last BB of the converted switch statement (in terms
1153 prune_bbs (basic_block bbd
, basic_block final
)
1158 for (ei
= ei_start (bbd
->succs
); (e
= ei_safe_edge (ei
)); )
1164 delete_basic_block (bb
);
1166 delete_basic_block (bbd
);
1169 /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
1170 from the basic block loading values from an array and E2F from the basic
1171 block loading default values. BBF is the last switch basic block (see the
1172 bbf description in the comment below). */
1175 fix_phi_nodes (edge e1f
, edge e2f
, basic_block bbf
,
1176 struct switch_conv_info
*info
)
1178 gimple_stmt_iterator gsi
;
1181 for (gsi
= gsi_start_phis (bbf
), i
= 0;
1182 !gsi_end_p (gsi
); gsi_next (&gsi
), i
++)
1184 gimple phi
= gsi_stmt (gsi
);
1185 add_phi_arg (phi
, info
->target_inbound_names
[i
], e1f
, UNKNOWN_LOCATION
);
1186 add_phi_arg (phi
, info
->target_outbound_names
[i
], e2f
, UNKNOWN_LOCATION
);
1190 /* Creates a check whether the switch expression value actually falls into the
1191 range given by all the cases. If it does not, the temporaries are loaded
1192 with default values instead. SWTCH is the switch statement being converted.
1194 bb0 is the bb with the switch statement, however, we'll end it with a
1197 bb1 is the bb to be used when the range check went ok. It is derived from
1200 bb2 is the bb taken when the expression evaluated outside of the range
1201 covered by the created arrays. It is populated by loads of default
1204 bbF is a fall through for both bb1 and bb2 and contains exactly what
1205 originally followed the switch statement.
1207 bbD contains the switch statement (in the end). It is unreachable but we
1208 still need to strip off its edges.
1212 gen_inbound_check (gimple swtch
, struct switch_conv_info
*info
)
1214 tree label_decl1
= create_artificial_label (UNKNOWN_LOCATION
);
1215 tree label_decl2
= create_artificial_label (UNKNOWN_LOCATION
);
1216 tree label_decl3
= create_artificial_label (UNKNOWN_LOCATION
);
1217 gimple label1
, label2
, label3
;
1224 gimple_stmt_iterator gsi
;
1225 basic_block bb0
, bb1
, bb2
, bbf
, bbd
;
1226 edge e01
, e02
, e21
, e1d
, e1f
, e2f
;
1227 location_t loc
= gimple_location (swtch
);
1229 gcc_assert (info
->default_values
);
1231 bb0
= gimple_bb (swtch
);
1233 tidx
= gimple_assign_lhs (info
->arr_ref_first
);
1234 utype
= TREE_TYPE (tidx
);
1236 /* (end of) block 0 */
1237 gsi
= gsi_for_stmt (info
->arr_ref_first
);
1240 bound
= fold_convert_loc (loc
, utype
, info
->range_size
);
1241 cond_stmt
= gimple_build_cond (LE_EXPR
, tidx
, bound
, NULL_TREE
, NULL_TREE
);
1242 gsi_insert_before (&gsi
, cond_stmt
, GSI_SAME_STMT
);
1243 update_stmt (cond_stmt
);
1246 label2
= gimple_build_label (label_decl2
);
1247 gsi_insert_before (&gsi
, label2
, GSI_SAME_STMT
);
1248 last_assign
= gen_def_assigns (&gsi
, info
);
1251 label1
= gimple_build_label (label_decl1
);
1252 gsi_insert_before (&gsi
, label1
, GSI_SAME_STMT
);
1255 gsi
= gsi_start_bb (info
->final_bb
);
1256 label3
= gimple_build_label (label_decl3
);
1257 gsi_insert_before (&gsi
, label3
, GSI_SAME_STMT
);
1260 e02
= split_block (bb0
, cond_stmt
);
1263 e21
= split_block (bb2
, last_assign
);
1267 e1d
= split_block (bb1
, info
->arr_ref_last
);
1271 /* flags and profiles of the edge for in-range values */
1272 e01
= make_edge (bb0
, bb1
, EDGE_TRUE_VALUE
);
1273 e01
->probability
= REG_BR_PROB_BASE
- info
->default_prob
;
1274 e01
->count
= info
->other_count
;
1276 /* flags and profiles of the edge taking care of out-of-range values */
1277 e02
->flags
&= ~EDGE_FALLTHRU
;
1278 e02
->flags
|= EDGE_FALSE_VALUE
;
1279 e02
->probability
= info
->default_prob
;
1280 e02
->count
= info
->default_count
;
1282 bbf
= info
->final_bb
;
1284 e1f
= make_edge (bb1
, bbf
, EDGE_FALLTHRU
);
1285 e1f
->probability
= REG_BR_PROB_BASE
;
1286 e1f
->count
= info
->other_count
;
1288 e2f
= make_edge (bb2
, bbf
, EDGE_FALLTHRU
);
1289 e2f
->probability
= REG_BR_PROB_BASE
;
1290 e2f
->count
= info
->default_count
;
1292 /* frequencies of the new BBs */
1293 bb1
->frequency
= EDGE_FREQUENCY (e01
);
1294 bb2
->frequency
= EDGE_FREQUENCY (e02
);
1295 bbf
->frequency
= EDGE_FREQUENCY (e1f
) + EDGE_FREQUENCY (e2f
);
1297 /* Tidy blocks that have become unreachable. */
1298 prune_bbs (bbd
, info
->final_bb
);
1300 /* Fixup the PHI nodes in bbF. */
1301 fix_phi_nodes (e1f
, e2f
, bbf
, info
);
1303 /* Fix the dominator tree, if it is available. */
1304 if (dom_info_available_p (CDI_DOMINATORS
))
1306 vec
<basic_block
> bbs_to_fix_dom
;
1308 set_immediate_dominator (CDI_DOMINATORS
, bb1
, bb0
);
1309 set_immediate_dominator (CDI_DOMINATORS
, bb2
, bb0
);
1310 if (! get_immediate_dominator (CDI_DOMINATORS
, bbf
))
1311 /* If bbD was the immediate dominator ... */
1312 set_immediate_dominator (CDI_DOMINATORS
, bbf
, bb0
);
1314 bbs_to_fix_dom
.create (4);
1315 bbs_to_fix_dom
.quick_push (bb0
);
1316 bbs_to_fix_dom
.quick_push (bb1
);
1317 bbs_to_fix_dom
.quick_push (bb2
);
1318 bbs_to_fix_dom
.quick_push (bbf
);
1320 iterate_fix_dominators (CDI_DOMINATORS
, bbs_to_fix_dom
, true);
1321 bbs_to_fix_dom
.release ();
1325 /* The following function is invoked on every switch statement (the current one
1326 is given in SWTCH) and runs the individual phases of switch conversion on it
1327 one after another until one fails or the conversion is completed.
1328 Returns NULL on success, or a pointer to a string with the reason why the
1329 conversion failed. */
1332 process_switch (gimple swtch
)
1334 struct switch_conv_info info
;
1336 /* Group case labels so that we get the right results from the heuristics
1337 that decide on the code generation approach for this switch. */
1338 group_case_labels_stmt (swtch
);
1340 /* If this switch is now a degenerate case with only a default label,
1341 there is nothing left for us to do. */
1342 if (gimple_switch_num_labels (swtch
) < 2)
1343 return "switch is a degenerate case";
1345 collect_switch_conv_info (swtch
, &info
);
1347 /* No error markers should reach here (they should be filtered out
1348 during gimplification). */
1349 gcc_checking_assert (TREE_TYPE (info
.index_expr
) != error_mark_node
);
1351 /* A switch on a constant should have been optimized in tree-cfg-cleanup. */
1352 gcc_checking_assert (! TREE_CONSTANT (info
.index_expr
));
1354 if (info
.uniq
<= MAX_CASE_BIT_TESTS
)
1356 if (expand_switch_using_bit_tests_p (info
.range_size
,
1357 info
.uniq
, info
.count
,
1358 optimize_bb_for_speed_p
1359 (gimple_bb (swtch
))))
1362 fputs (" expanding as bit test is preferable\n", dump_file
);
1363 emit_case_bit_tests (swtch
, info
.index_expr
, info
.range_min
,
1364 info
.range_size
, info
.range_max
);
1365 loops_state_set (LOOPS_NEED_FIXUP
);
1370 /* This will be expanded as a decision tree in stmt.c:expand_case. */
1371 return " expanding as jumps is preferable";
1374 /* If there is no common successor, we cannot do the transformation. */
1375 if (! info
.final_bb
)
1376 return "no common successor to all case label target blocks found";
1378 /* Check the case label values are within reasonable range: */
1379 if (!check_range (&info
))
1381 gcc_assert (info
.reason
);
1385 /* For all the cases, see whether they are empty, the assignments they
1386 represent constant and so on... */
1387 if (! check_all_empty_except_final (&info
))
1389 gcc_assert (info
.reason
);
1392 if (!check_final_bb (&info
))
1394 gcc_assert (info
.reason
);
1398 /* At this point all checks have passed and we can proceed with the
1401 create_temp_arrays (&info
);
1402 gather_default_values (gimple_switch_default_label (swtch
), &info
);
1403 build_constructors (swtch
, &info
);
1405 build_arrays (swtch
, &info
); /* Build the static arrays and assignments. */
1406 gen_inbound_check (swtch
, &info
); /* Build the bounds check. */
1409 free_temp_arrays (&info
);
1413 /* The main function of the pass scans statements for switches and invokes
1414 process_switch on them. */
1418 const pass_data pass_data_convert_switch
=
1420 GIMPLE_PASS
, /* type */
1421 "switchconv", /* name */
1422 OPTGROUP_NONE
, /* optinfo_flags */
1423 TV_TREE_SWITCH_CONVERSION
, /* tv_id */
1424 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1425 0, /* properties_provided */
1426 0, /* properties_destroyed */
1427 0, /* todo_flags_start */
1428 TODO_update_ssa
, /* todo_flags_finish */
1431 class pass_convert_switch
: public gimple_opt_pass
1434 pass_convert_switch (gcc::context
*ctxt
)
1435 : gimple_opt_pass (pass_data_convert_switch
, ctxt
)
1438 /* opt_pass methods: */
1439 virtual bool gate (function
*) { return flag_tree_switch_conversion
!= 0; }
1440 virtual unsigned int execute (function
*);
1442 }; // class pass_convert_switch
1445 pass_convert_switch::execute (function
*fun
)
1449 FOR_EACH_BB_FN (bb
, fun
)
1451 const char *failure_reason
;
1452 gimple stmt
= last_stmt (bb
);
1453 if (stmt
&& gimple_code (stmt
) == GIMPLE_SWITCH
)
1457 expanded_location loc
= expand_location (gimple_location (stmt
));
1459 fprintf (dump_file
, "beginning to process the following "
1460 "SWITCH statement (%s:%d) : ------- \n",
1461 loc
.file
, loc
.line
);
1462 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
1463 putc ('\n', dump_file
);
1466 failure_reason
= process_switch (stmt
);
1467 if (! failure_reason
)
1471 fputs ("Switch converted\n", dump_file
);
1472 fputs ("--------------------------------\n", dump_file
);
1475 /* Make no effort to update the post-dominator tree. It is actually not
1476 that hard for the transformations we have performed, but it is not
1477 supported by iterate_fix_dominators. */
1478 free_dominance_info (CDI_POST_DOMINATORS
);
1484 fputs ("Bailing out - ", dump_file
);
1485 fputs (failure_reason
, dump_file
);
1486 fputs ("\n--------------------------------\n", dump_file
);
1498 make_pass_convert_switch (gcc::context
*ctxt
)
1500 return new pass_convert_switch (ctxt
);