Line data Source code
1 : /* Tree switch conversion for GNU compiler.
2 : Copyright (C) 2017-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #ifndef TREE_SWITCH_CONVERSION_H
21 : #define TREE_SWITCH_CONVERSION_H
22 :
23 : namespace tree_switch_conversion {
24 :
25 : /* Type of cluster. */
26 :
27 : enum cluster_type
28 : {
29 : SIMPLE_CASE,
30 : JUMP_TABLE,
31 : BIT_TEST
32 : };
33 :
34 : #define PRINT_CASE(f,c) print_generic_expr (f, c)
35 :
36 : /* Abstract base class for representing a cluster of cases.
37 :
38 : Here is the inheritance hierarachy, and the enum_cluster_type
39 : values for the concrete subclasses:
40 :
41 : cluster
42 : |-simple_cluster (SIMPLE_CASE)
43 : `-group_cluster
44 : |-jump_table_cluster (JUMP_TABLE)
45 : `-bit_test_cluster (BIT_TEST). */
46 :
47 : class cluster
48 : {
49 : public:
50 : /* Constructor. */
51 : inline cluster (tree case_label_expr, basic_block case_bb,
52 : profile_probability prob, profile_probability subtree_prob);
53 :
54 : /* Destructor. */
55 320443 : virtual ~cluster ()
56 : {}
57 :
58 : /* Return type. */
59 : virtual cluster_type get_type () = 0;
60 :
61 : /* Get low value covered by a cluster. */
62 : virtual tree get_low () = 0;
63 :
64 : /* Get high value covered by a cluster. */
65 : virtual tree get_high () = 0;
66 :
67 : /* Debug content of a cluster. */
68 : virtual void debug () = 0;
69 :
70 : /* Dump content of a cluster. */
71 : virtual void dump (FILE *f, bool details = false) = 0;
72 :
73 : /* Emit GIMPLE code to handle the cluster. */
74 : virtual void emit (tree, tree, tree, basic_block, location_t) = 0;
75 :
76 : /* Return true if a cluster handles only a single case value and the
77 : value is not a range. */
78 2280 : virtual bool is_single_value_p ()
79 : {
80 2280 : return false;
81 : }
82 :
83 : /* Return range of a cluster. If value would overflow in type of LOW,
84 : then return 0. */
85 5114260 : static unsigned HOST_WIDE_INT get_range (tree low, tree high)
86 : {
87 5114260 : wide_int w = wi::to_wide (high) - wi::to_wide (low);
88 5114260 : if (wi::neg_p (w, TYPE_SIGN (TREE_TYPE (low))) || !wi::fits_uhwi_p (w))
89 : return 0;
90 5110372 : return w.to_uhwi () + 1;
91 5114260 : }
92 :
93 : /* Case label. */
94 : tree m_case_label_expr;
95 :
96 : /* Basic block of the case. */
97 : basic_block m_case_bb;
98 :
99 : /* Probability of taking this cluster. */
100 : profile_probability m_prob;
101 :
102 : /* Probability of reaching subtree rooted at this node. */
103 : profile_probability m_subtree_prob;
104 :
105 : /* Probability of default case when reaching the node.
106 : It is used by bit-test right now. */
107 : profile_probability m_default_prob;
108 :
109 : protected:
110 : /* Default constructor. */
111 12552 : cluster () {}
112 : };
113 :
114 307891 : cluster::cluster (tree case_label_expr, basic_block case_bb,
115 307891 : profile_probability prob, profile_probability subtree_prob):
116 307891 : m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob),
117 307891 : m_subtree_prob (subtree_prob),
118 307891 : m_default_prob (profile_probability::uninitialized ())
119 : {
120 : }
121 :
122 : /* Subclass of cluster representing a simple contiguous range
123 : from [low..high]. */
124 :
125 : class simple_cluster: public cluster
126 : {
127 : public:
128 : /* Constructor. */
129 : inline simple_cluster (tree low, tree high, tree case_label_expr,
130 : basic_block case_bb, profile_probability prob,
131 : bool has_forward_bb = false);
132 :
133 : /* Destructor. */
134 307891 : ~simple_cluster ()
135 307891 : {}
136 :
137 : cluster_type
138 564514 : get_type () final override
139 : {
140 564514 : return SIMPLE_CASE;
141 : }
142 :
143 : tree
144 5734239 : get_low () final override
145 : {
146 130510 : return m_low;
147 : }
148 :
149 : tree
150 5617596 : get_high () final override
151 : {
152 346019 : return m_high;
153 : }
154 :
155 1347 : void set_high (tree high)
156 : {
157 1347 : m_high = high;
158 : }
159 :
160 : void
161 0 : debug () final override
162 : {
163 0 : dump (stderr);
164 0 : }
165 :
166 : void
167 120 : dump (FILE *f, bool details ATTRIBUTE_UNUSED = false) final override
168 : {
169 120 : PRINT_CASE (f, get_low ());
170 120 : if (get_low () != get_high ())
171 : {
172 8 : fprintf (f, "-");
173 8 : PRINT_CASE (f, get_high ());
174 : }
175 120 : fprintf (f, " ");
176 120 : }
177 :
178 0 : void emit (tree, tree, tree, basic_block, location_t) final override
179 : {
180 0 : gcc_unreachable ();
181 : }
182 :
183 158650 : bool is_single_value_p () final override
184 : {
185 158650 : return tree_int_cst_equal (get_low (), get_high ());
186 : }
187 :
188 : /* Return number of comparisons needed for the case. */
189 : unsigned
190 13277243 : get_comparison_count ()
191 : {
192 13277243 : return m_range_p ? 2 : 1;
193 : }
194 :
195 : /* Low value of the case. */
196 : tree m_low;
197 :
198 : /* High value of the case. */
199 : tree m_high;
200 :
201 : /* True if case is a range. */
202 : bool m_range_p;
203 :
204 : /* True if the case will use a forwarder BB. */
205 : bool m_has_forward_bb;
206 : };
207 :
208 307891 : simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr,
209 : basic_block case_bb, profile_probability prob,
210 307891 : bool has_forward_bb):
211 : cluster (case_label_expr, case_bb, prob, prob),
212 307891 : m_low (low), m_high (high), m_has_forward_bb (has_forward_bb)
213 : {
214 307891 : m_range_p = m_high != NULL;
215 307891 : if (m_high == NULL)
216 213279 : m_high = m_low;
217 307891 : }
218 :
219 : /* Abstract subclass of jump table and bit test cluster,
220 : handling a collection of simple_cluster instances. */
221 :
222 : class group_cluster: public cluster
223 : {
224 : public:
225 : /* Constructor. */
226 : group_cluster (vec<cluster *> &clusters, unsigned start, unsigned end);
227 :
228 : /* Destructor. */
229 : ~group_cluster ();
230 :
231 : tree
232 12874 : get_low () final override
233 : {
234 12874 : return m_cases[0]->get_low ();
235 : }
236 :
237 : tree
238 12874 : get_high () final override
239 : {
240 25748 : return m_cases[m_cases.length () - 1]->get_high ();
241 : }
242 :
243 : void
244 0 : debug () final override
245 : {
246 0 : dump (stderr);
247 0 : }
248 :
249 : void dump (FILE *f, bool details = false) final override;
250 :
251 : /* List of simple clusters handled by the group. */
252 : vec<simple_cluster *> m_cases;
253 : };
254 :
255 : /* Concrete subclass of group_cluster representing a collection
256 : of cases to be implemented as a jump table.
257 : The "emit" vfunc generates a nested switch statement which
258 : is later lowered to a jump table. */
259 :
260 : class jump_table_cluster: public group_cluster
261 : {
262 : public:
263 : /* Constructor. */
264 7643 : jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
265 7643 : : group_cluster (clusters, start, end)
266 : {}
267 :
268 : cluster_type
269 14746 : get_type () final override
270 : {
271 14746 : return JUMP_TABLE;
272 : }
273 :
274 : void emit (tree index_expr, tree index_type,
275 : tree default_label_expr, basic_block default_bb, location_t loc)
276 : final override;
277 :
278 : /* Find jump tables of given CLUSTERS, where all members of the vector
279 : are of type simple_cluster. New clusters are returned. */
280 : static vec<cluster *> find_jump_tables (vec<cluster *> &clusters);
281 :
282 : /* Return true when cluster starting at START and ending at END (inclusive)
283 : can build a jump-table. COMPARISON_COUNT is number of comparison
284 : operations needed if the clusters are expanded as decision tree.
285 : MAX_RATIO tells about the maximum code growth (in percent). */
286 : static bool can_be_handled (const vec<cluster *> &clusters, unsigned start,
287 : unsigned end, unsigned HOST_WIDE_INT max_ratio,
288 : unsigned HOST_WIDE_INT comparison_count);
289 :
290 : /* Return true if cluster starting at START and ending at END (inclusive)
291 : is profitable transformation. */
292 : static bool is_beneficial (const vec<cluster *> &clusters, unsigned start,
293 : unsigned end);
294 :
295 : /* Return the smallest number of different values for which it is best
296 : to use a jump-table instead of a tree of conditional branches. */
297 : static inline unsigned int case_values_threshold (void);
298 :
299 : /* Return whether jump table expansion is allowed. */
300 : static inline bool is_enabled (void);
301 : };
302 :
303 : /* A GIMPLE switch statement can be expanded to a short sequence of bit-wise
304 : comparisons. "switch(x)" is converted into "if ((1 << (x-MINVAL)) & CST)"
305 : where CST and MINVAL are integer constants. This is better than a series
306 : of compare-and-branch insns in some cases, e.g. we can implement:
307 :
308 : if ((x==4) || (x==6) || (x==9) || (x==11))
309 :
310 : as a single bit test:
311 :
312 : if ((1<<x) & ((1<<4)|(1<<6)|(1<<9)|(1<<11)))
313 :
314 : This transformation is only applied if the number of case targets is small,
315 : if CST constains at least 3 bits, and "1 << x" is cheap. The bit tests are
316 : performed in "word_mode".
317 :
318 : The following example shows the code the transformation generates:
319 :
320 : int bar(int x)
321 : {
322 : switch (x)
323 : {
324 : case '0': case '1': case '2': case '3': case '4':
325 : case '5': case '6': case '7': case '8': case '9':
326 : case 'A': case 'B': case 'C': case 'D': case 'E':
327 : case 'F':
328 : return 1;
329 : }
330 : return 0;
331 : }
332 :
333 : ==>
334 :
335 : bar (int x)
336 : {
337 : tmp1 = x - 48;
338 : if (tmp1 > (70 - 48)) goto L2;
339 : tmp2 = 1 << tmp1;
340 : tmp3 = 0b11111100000001111111111;
341 : if ((tmp2 & tmp3) != 0) goto L1 ; else goto L2;
342 : L1:
343 : return 1;
344 : L2:
345 : return 0;
346 : }
347 :
348 : TODO: There are still some improvements to this transformation that could
349 : be implemented:
350 :
351 : * A narrower mode than word_mode could be used if that is cheaper, e.g.
352 : for x86_64 where a narrower-mode shift may result in smaller code.
353 :
354 : * The compounded constant could be shifted rather than the one. The
355 : test would be either on the sign bit or on the least significant bit,
356 : depending on the direction of the shift. On some machines, the test
357 : for the branch would be free if the bit to test is already set by the
358 : shift operation.
359 :
360 : This transformation was contributed by Roger Sayle, see this e-mail:
361 : http://gcc.gnu.org/ml/gcc-patches/2003-01/msg01950.html
362 : */
363 :
364 : class bit_test_cluster: public group_cluster
365 : {
366 : public:
367 : /* Constructor. */
368 4909 : bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end,
369 : bool handles_entire_switch)
370 4909 : :group_cluster (clusters, start, end),
371 4909 : m_handles_entire_switch (handles_entire_switch)
372 : {}
373 :
374 : cluster_type
375 13576 : get_type () final override
376 : {
377 13576 : return BIT_TEST;
378 : }
379 :
380 : /* Expand a switch statement by a short sequence of bit-wise
381 : comparisons. "switch(x)" is effectively converted into
382 : "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
383 : integer constants.
384 :
385 : INDEX_EXPR is the value being switched on.
386 :
387 : MINVAL is the lowest case value of in the case nodes,
388 : and RANGE is highest value minus MINVAL. MINVAL and RANGE
389 : are not guaranteed to be of the same type as INDEX_EXPR
390 : (the gimplifier doesn't change the type of case label values,
391 : and MINVAL and RANGE are derived from those values).
392 : MAXVAL is MINVAL + RANGE.
393 :
394 : There *MUST* be max_case_bit_tests or less unique case
395 : node targets. */
396 : void emit (tree index_expr, tree index_type,
397 : tree default_label_expr, basic_block default_bb, location_t loc)
398 : final override;
399 :
400 : /* Find bit tests of given CLUSTERS, where all members of the vector are of
401 : type simple_cluster. Use a fast algorithm that might not find the optimal
402 : solution (minimal number of clusters on the output). New clusters are
403 : returned.
404 :
405 : You should call find_bit_tests () instead of calling this function
406 : directly. */
407 : static vec<cluster *> find_bit_tests_fast (vec<cluster *> &clusters);
408 :
409 : /* Find bit tests of given CLUSTERS, where all members of the vector
410 : are of type simple_cluster. Use a slow (quadratic) algorithm that always
411 : finds the optimal solution (minimal number of clusters on the output). New
412 : clusters are returned.
413 :
414 : You should call find_bit_tests () instead of calling this function
415 : directly. */
416 : static vec<cluster *> find_bit_tests_slow (vec<cluster *> &clusters);
417 :
418 : /* Find bit tests of given CLUSTERS, where all members of the vector
419 : are of type simple_cluster. New clusters are returned. */
420 : static vec<cluster *> find_bit_tests (vec<cluster *> &clusters, int max_c);
421 :
422 : /* Return true when RANGE of case values with UNIQ labels
423 : can build a bit test. */
424 : static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq);
425 :
426 : /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
427 : transformation. */
428 : static bool is_beneficial (unsigned count, unsigned uniq);
429 :
430 : /* Split the basic block at the statement pointed to by GSIP, and insert
431 : a branch to the target basic block of E_TRUE conditional on tree
432 : expression COND.
433 :
434 : It is assumed that there is already an edge from the to-be-split
435 : basic block to E_TRUE->dest block. This edge is removed, and the
436 : profile information on the edge is re-used for the new conditional
437 : jump.
438 :
439 : The CFG is updated. The dominator tree will not be valid after
440 : this transformation, but the immediate dominators are updated if
441 : UPDATE_DOMINATORS is true.
442 :
443 : Returns the newly created basic block. */
444 : static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
445 : tree cond,
446 : basic_block case_bb,
447 : profile_probability prob,
448 : location_t);
449 :
450 : /* Return whether bit test expansion is allowed. */
451 72215 : static inline bool is_enabled (void)
452 : {
453 72215 : return flag_bit_tests;
454 : }
455 :
456 : /* True when the jump table handles an entire switch statement. */
457 : bool m_handles_entire_switch;
458 :
459 : /* Maximum number of different basic blocks that can be handled by
460 : a bit test. */
461 : static const int m_max_case_bit_tests = 3;
462 : };
463 :
464 : /* Helper struct to find minimal clusters. */
465 :
466 : class min_cluster_item
467 : {
468 : public:
469 : /* Constructor. */
470 200543 : min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases):
471 363277 : m_count (count), m_start (start), m_non_jt_cases (non_jt_cases)
472 : {}
473 :
474 : /* Count of clusters. */
475 : unsigned m_count;
476 :
477 : /* Index where is cluster boundary. */
478 : unsigned m_start;
479 :
480 : /* Total number of cases that will not be in a jump table. */
481 : unsigned m_non_jt_cases;
482 : };
483 :
484 : /* Helper struct to represent switch decision tree. */
485 :
486 : class case_tree_node
487 : {
488 : public:
489 : /* Empty Constructor. */
490 : case_tree_node ();
491 :
492 : /* Return true when it has a child. */
493 120050 : bool has_child ()
494 : {
495 120050 : return m_left != NULL || m_right != NULL;
496 : }
497 :
498 : /* Left son in binary tree. */
499 : case_tree_node *m_left;
500 :
501 : /* Right son in binary tree; also node chain. */
502 : case_tree_node *m_right;
503 :
504 : /* Parent of node in binary tree. */
505 : case_tree_node *m_parent;
506 :
507 : /* Cluster represented by this tree node. */
508 : cluster *m_c;
509 : };
510 :
511 : inline
512 168231 : case_tree_node::case_tree_node ():
513 168231 : m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
514 : {
515 : }
516 :
517 : unsigned int
518 6686983 : jump_table_cluster::case_values_threshold (void)
519 : {
520 6686983 : unsigned int threshold = param_case_values_threshold;
521 :
522 6686983 : if (threshold == 0)
523 6686581 : threshold = targetm.case_values_threshold ();
524 :
525 6686983 : return threshold;
526 : }
527 :
528 : /* Return whether jump table expansion is allowed. */
529 2483022 : bool jump_table_cluster::is_enabled (void)
530 : {
531 : /* If neither casesi or tablejump is available, or flag_jump_tables
532 : over-ruled us, we really have no choice. */
533 2483022 : if (!targetm.have_casesi () && !targetm.have_tablejump ())
534 : return false;
535 2483022 : if (!flag_jump_tables)
536 : return false;
537 : #ifndef ASM_OUTPUT_ADDR_DIFF_ELT
538 : if (flag_pic)
539 : return false;
540 : #endif
541 :
542 : return true;
543 : }
544 :
545 : /* A case_bit_test represents a set of case nodes that may be
546 : selected from using a bit-wise comparison. HI and LO hold
547 : the integer to be tested against, TARGET_EDGE contains the
548 : edge to the basic block to jump to upon success and BITS
549 : counts the number of case nodes handled by this test,
550 : typically the number of bits set in HI:LO. The LABEL field
551 : is used to quickly identify all cases in this set without
552 : looking at label_to_block for every case label. */
553 :
554 11775 : class case_bit_test
555 : {
556 : public:
557 : wide_int mask;
558 : basic_block target_bb;
559 : tree label;
560 : int bits;
561 : profile_probability prob;
562 :
563 : /* Comparison function for qsort to order bit tests by decreasing
564 : probability of execution. */
565 : static int cmp (const void *p1, const void *p2);
566 : };
567 :
568 : class switch_decision_tree
569 : {
570 : public:
571 : /* Constructor. */
572 45255 : switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (),
573 45255 : m_case_bbs (), m_case_node_pool ("struct case_node pool"),
574 45255 : m_case_list (NULL)
575 : {
576 45255 : }
577 :
578 : /* Analyze switch statement and return true when the statement is expanded
579 : as decision tree. */
580 : bool analyze_switch_statement ();
581 :
582 : /* Attempt to expand CLUSTERS as a decision tree. Return true when
583 : expanded. */
584 : bool try_switch_expansion (vec<cluster *> &clusters);
585 : /* Compute the number of case labels that correspond to each outgoing edge of
586 : switch statement. Record this information in the aux field of the edge.
587 : Returns approx max number of cases per edge.
588 : */
589 : int compute_cases_per_edge ();
590 :
591 : /* Before switch transformation, record all SSA_NAMEs defined in switch BB
592 : and used in a label basic block. */
593 : void record_phi_operand_mapping ();
594 :
595 : /* Append new operands to PHI statements that were introduced due to
596 : addition of new edges to case labels. */
597 : void fix_phi_operands_for_edges ();
598 :
599 : /* Generate a decision tree, switching on INDEX_EXPR and jumping to
600 : one of the labels in CASE_LIST or to the DEFAULT_LABEL.
601 :
602 : We generate a binary decision tree to select the appropriate target
603 : code. */
604 : void emit (basic_block bb, tree index_expr,
605 : profile_probability default_prob, tree index_type);
606 :
607 : /* Emit step-by-step code to select a case for the value of INDEX.
608 : The thus generated decision tree follows the form of the
609 : case-node binary tree NODE, whose nodes represent test conditions.
610 : DEFAULT_PROB is probability of cases leading to default BB.
611 : INDEX_TYPE is the type of the index of the switch. */
612 : basic_block emit_case_nodes (basic_block bb, tree index,
613 : case_tree_node *node,
614 : profile_probability default_prob,
615 : tree index_type, location_t);
616 :
617 : /* Take an ordered list of case nodes
618 : and transform them into a near optimal binary tree,
619 : on the assumption that any target code selection value is as
620 : likely as any other.
621 :
622 : The transformation is performed by splitting the ordered
623 : list into two equal sections plus a pivot. The parts are
624 : then attached to the pivot as left and right branches. Each
625 : branch is then transformed recursively. */
626 : static void balance_case_nodes (case_tree_node **head,
627 : case_tree_node *parent);
628 :
629 : /* Dump ROOT, a list or tree of case nodes, to file F. */
630 : static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step,
631 : int indent_level);
632 :
633 : /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
634 : static void emit_jump (basic_block bb, basic_block case_bb);
635 :
636 : /* Generate code to compare OP0 with OP1 so that the condition codes are
637 : set and to jump to LABEL_BB if the condition is true.
638 : COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
639 : PROB is the probability of jumping to LABEL_BB. */
640 : static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0,
641 : tree op1, tree_code comparison,
642 : basic_block label_bb,
643 : profile_probability prob,
644 : location_t);
645 :
646 : /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
647 : PROB is the probability of jumping to LABEL_BB. */
648 : static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1,
649 : basic_block label_bb,
650 : profile_probability prob,
651 : location_t);
652 :
653 : /* Reset the aux field of all outgoing edges of switch basic block. */
654 : static inline void reset_out_edges_aux (gswitch *swtch);
655 :
656 : /* Switch statement. */
657 : gswitch *m_switch;
658 :
659 : /* Map of PHI nodes that have to be fixed after expansion. */
660 : hash_map<tree, tree> m_phi_mapping;
661 :
662 : /* List of basic blocks that belong to labels of the switch. */
663 : auto_vec<basic_block> m_case_bbs;
664 :
665 : /* Basic block with default label. */
666 : basic_block m_default_bb;
667 :
668 : /* A pool for case nodes. */
669 : object_allocator<case_tree_node> m_case_node_pool;
670 :
671 : /* Balanced tree of case nodes. */
672 : case_tree_node *m_case_list;
673 : };
674 :
675 : /*
676 : Switch initialization conversion
677 :
678 : The following pass changes simple initializations of scalars in a switch
679 : statement into initializations from a static array. Obviously, the values
680 : must be constant and known at compile time and a default branch must be
681 : provided. For example, the following code:
682 :
683 : int a,b;
684 :
685 : switch (argc)
686 : {
687 : case 1:
688 : case 2:
689 : a_1 = 8;
690 : b_1 = 6;
691 : break;
692 : case 3:
693 : a_2 = 9;
694 : b_2 = 5;
695 : break;
696 : case 12:
697 : a_3 = 10;
698 : b_3 = 4;
699 : break;
700 : default:
701 : a_4 = 16;
702 : b_4 = 1;
703 : break;
704 : }
705 : a_5 = PHI <a_1, a_2, a_3, a_4>
706 : b_5 = PHI <b_1, b_2, b_3, b_4>
707 :
708 :
709 : is changed into:
710 :
711 : static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
712 : static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
713 : 16, 16, 10};
714 :
715 : if (((unsigned) argc) - 1 < 11)
716 : {
717 : a_6 = CSWTCH02[argc - 1];
718 : b_6 = CSWTCH01[argc - 1];
719 : }
720 : else
721 : {
722 : a_7 = 16;
723 : b_7 = 1;
724 : }
725 : a_5 = PHI <a_6, a_7>
726 : b_b = PHI <b_6, b_7>
727 :
728 : There are further constraints. Specifically, the range of values across all
729 : case labels must not be bigger than param_switch_conversion_branch_ratio
730 : (default eight) times the number of the actual switch branches.
731 :
732 : This transformation was contributed by Martin Jambor, see this e-mail:
733 : http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
734 :
735 : /* The main structure of the pass. */
736 : class switch_conversion
737 : {
738 : public:
739 : /* Constructor. */
740 : switch_conversion ();
741 :
742 : /* Destructor. */
743 : ~switch_conversion ();
744 :
745 : /* The following function is invoked on every switch statement (the current
746 : one is given in SWTCH) and runs the individual phases of switch
747 : conversion on it one after another until one fails or the conversion
748 : is completed. On success, NULL is in m_reason, otherwise points
749 : to a string with the reason why the conversion failed. */
750 : void expand (gswitch *swtch);
751 :
752 : /* Collection information about SWTCH statement. */
753 : void collect (gswitch *swtch);
754 :
755 : /* Check that the 'exponential index transform' can be applied.
756 :
757 : See the comment at the function definition for more details. */
758 : bool is_exp_index_transform_viable (gswitch *swtch);
759 :
760 : /* Perform the 'exponential index transform'.
761 :
762 : The exponential index transform shrinks the range of case numbers which
763 : helps switch conversion convert switches it otherwise could not.
764 :
765 : See the comment at the function definition for more details. */
766 : void exp_index_transform (gswitch *swtch);
767 :
768 : /* Checks whether the range given by individual case statements of the switch
769 : switch statement isn't too big and whether the number of branches actually
770 : satisfies the size of the new array. */
771 : bool check_range ();
772 :
773 : /* Checks whether all but the final BB basic blocks are empty. */
774 : bool check_all_empty_except_final ();
775 :
776 : /* This function checks whether all required values in phi nodes in final_bb
777 : are constants. Required values are those that correspond to a basic block
778 : which is a part of the examined switch statement. It returns true if the
779 : phi nodes are OK, otherwise false. */
780 : bool check_final_bb ();
781 :
782 : /* The following function allocates default_values, target_{in,out}_names and
783 : constructors arrays. The last one is also populated with pointers to
784 : vectors that will become constructors of new arrays. */
785 : void create_temp_arrays ();
786 :
787 : /* Populate the array of default values in the order of phi nodes.
788 : DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
789 : if the range is non-contiguous or the default case has standard
790 : structure, otherwise it is the first non-default case instead. */
791 : void gather_default_values (tree default_case);
792 :
793 : /* The following function populates the vectors in the constructors array with
794 : future contents of the static arrays. The vectors are populated in the
795 : order of phi nodes. */
796 : void build_constructors ();
797 :
798 : /* If all values in the constructor vector are products of a linear function
799 : a * x + b, then return true. When true, COEFF_A and COEFF_B and
800 : coefficients of the linear function. Note that equal values are special
801 : case of a linear function with a and b equal to zero. */
802 : bool contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
803 : wide_int *coeff_a, wide_int *coeff_b);
804 :
805 : /* Return type which should be used for array elements, either TYPE's
806 : main variant or, for integral types, some smaller integral type
807 : that can still hold all the constants. */
808 : tree array_value_type (tree type, int num);
809 :
810 : /* Create an appropriate array type and declaration and assemble a static
811 : array variable. Also create a load statement that initializes
812 : the variable in question with a value from the static array. SWTCH is
813 : the switch statement being converted, NUM is the index to
814 : arrays of constructors, default values and target SSA names
815 : for this particular array. ARR_INDEX_TYPE is the type of the index
816 : of the new array, PHI is the phi node of the final BB that corresponds
817 : to the value that will be loaded from the created array. TIDX
818 : is an ssa name of a temporary variable holding the index for loads from the
819 : new array. */
820 : void build_one_array (int num, tree arr_index_type,
821 : gphi *phi, tree tidx);
822 :
823 : /* Builds and initializes static arrays initialized with values gathered from
824 : the switch statement. Also creates statements that load values from
825 : them. */
826 : void build_arrays ();
827 :
828 : /* Generates and appropriately inserts loads of default values at the position
829 : given by GSI. Returns the last inserted statement. */
830 : gassign *gen_def_assigns (gimple_stmt_iterator *gsi);
831 :
832 : /* Deletes the unused bbs and edges that now contain the switch statement and
833 : its empty branch bbs. BBD is the now dead BB containing
834 : the original switch statement, FINAL is the last BB of the converted
835 : switch statement (in terms of succession). */
836 : void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb);
837 :
838 : /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
839 : from the basic block loading values from an array and E2F from the basic
840 : block loading default values. BBF is the last switch basic block (see the
841 : bbf description in the comment below). */
842 : void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf);
843 :
844 : /* Creates a check whether the switch expression value actually falls into the
845 : range given by all the cases. If it does not, the temporaries are loaded
846 : with default values instead. */
847 : void gen_inbound_check ();
848 :
849 : /* Switch statement for which switch conversion takes place. */
850 : gswitch *m_switch;
851 :
852 : /* The expression used to decide the switch branch. */
853 : tree m_index_expr;
854 :
855 : /* The following integer constants store the minimum and maximum value
856 : covered by the case labels. */
857 : tree m_range_min;
858 : tree m_range_max;
859 :
860 : /* The difference between the above two numbers. Stored here because it
861 : is used in all the conversion heuristics, as well as for some of the
862 : transformation, and it is expensive to re-compute it all the time. */
863 : tree m_range_size;
864 :
865 : /* Basic block that contains the actual GIMPLE_SWITCH. */
866 : basic_block m_switch_bb;
867 :
868 : /* Basic block that is the target of the default case. */
869 : basic_block m_default_bb;
870 :
871 : /* The single successor block of all branches out of the GIMPLE_SWITCH,
872 : if such a block exists. Otherwise NULL. */
873 : basic_block m_final_bb;
874 :
875 : /* The probability of the default edge in the replaced switch. */
876 : profile_probability m_default_prob;
877 :
878 : /* Number of phi nodes in the final bb (that we'll be replacing). */
879 : int m_phi_count;
880 :
881 : /* Constructors of new static arrays. */
882 : vec<constructor_elt, va_gc> **m_constructors;
883 :
884 : /* Array of default values, in the same order as phi nodes. */
885 : tree *m_default_values;
886 :
887 : /* Array of ssa names that are initialized with a value from a new static
888 : array. */
889 : tree *m_target_inbound_names;
890 :
891 : /* Array of ssa names that are initialized with the default value if the
892 : switch expression is out of range. */
893 : tree *m_target_outbound_names;
894 :
895 : /* VOP SSA_NAME. */
896 : tree m_target_vop;
897 :
898 : /* The first load statement that loads a temporary from a new static array.
899 : */
900 : gimple *m_arr_ref_first;
901 :
902 : /* The last load statement that loads a temporary from a new static array. */
903 : gimple *m_arr_ref_last;
904 :
905 : /* String reason why the case wasn't a good candidate that is written to the
906 : dump file, if there is one. */
907 : const char *m_reason;
908 :
909 : /* True if default case is not used for any value between range_min and
910 : range_max inclusive. */
911 : bool m_contiguous_range;
912 :
913 : /* True if default case does not have the required shape for other case
914 : labels. */
915 : bool m_default_case_nonstandard;
916 :
917 : /* Number of uniq labels for non-default edges. */
918 : unsigned int m_uniq;
919 :
920 : /* Count is number of non-default edges. */
921 : unsigned int m_count;
922 :
923 : /* True if CFG has been changed. */
924 : bool m_cfg_altered;
925 :
926 : /* True if exponential index transform has been applied. See the comment at
927 : the definition of exp_index_transform for details about the
928 : transformation. */
929 : bool m_exp_index_transform_applied;
930 :
931 : /* If switch conversion decided exponential index transform is viable, here
932 : will be stored the type to which index variable has to be converted
933 : before the logarithm operation which is a part of the transform. */
934 : tree m_exp_index_transform_log2_type;
935 : };
936 :
937 : void
938 97492 : switch_decision_tree::reset_out_edges_aux (gswitch *swtch)
939 : {
940 97492 : basic_block bb = gimple_bb (swtch);
941 97492 : edge e;
942 97492 : edge_iterator ei;
943 641898 : FOR_EACH_EDGE (e, ei, bb->succs)
944 544406 : e->aux = (void *) 0;
945 97492 : }
946 :
947 : /* Release CLUSTERS vector and destruct all dynamically allocated items. */
948 :
949 : inline void
950 72812 : release_clusters (vec<cluster *> &clusters)
951 : {
952 297986 : for (unsigned i = 0; i < clusters.length (); i++)
953 225174 : delete clusters[i];
954 72812 : clusters.release ();
955 72812 : }
956 :
957 : } // tree_switch_conversion namespace
958 :
959 : #endif // TREE_SWITCH_CONVERSION_H
|
