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 306320 : 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 2186 : virtual bool is_single_value_p ()
79 : {
80 2186 : return false;
81 : }
82 :
83 : /* Return range of a cluster. If value would overflow in type of LOW,
84 : then return 0. */
85 5086027 : static unsigned HOST_WIDE_INT get_range (tree low, tree high)
86 : {
87 5086027 : wide_int w = wi::to_wide (high) - wi::to_wide (low);
88 5086027 : if (wi::neg_p (w, TYPE_SIGN (TREE_TYPE (low))) || !wi::fits_uhwi_p (w))
89 : return 0;
90 5082139 : return w.to_uhwi () + 1;
91 5086027 : }
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 11270 : cluster () {}
112 : };
113 :
114 295050 : cluster::cluster (tree case_label_expr, basic_block case_bb,
115 295050 : profile_probability prob, profile_probability subtree_prob):
116 295050 : m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob),
117 295050 : m_subtree_prob (subtree_prob),
118 295050 : 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 295050 : ~simple_cluster ()
135 295050 : {}
136 :
137 : cluster_type
138 549241 : get_type () final override
139 : {
140 549241 : return SIMPLE_CASE;
141 : }
142 :
143 : tree
144 5694800 : get_low () final override
145 : {
146 120985 : return m_low;
147 : }
148 :
149 : tree
150 5581689 : get_high () final override
151 : {
152 332612 : return m_high;
153 : }
154 :
155 1341 : void set_high (tree high)
156 : {
157 1341 : 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 156283 : bool is_single_value_p () final override
184 : {
185 156283 : return tree_int_cst_equal (get_low (), get_high ());
186 : }
187 :
188 : /* Return number of comparisons needed for the case. */
189 : unsigned
190 13192761 : get_comparison_count ()
191 : {
192 13192761 : 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 295050 : simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr,
209 : basic_block case_bb, profile_probability prob,
210 295050 : bool has_forward_bb):
211 : cluster (case_label_expr, case_bb, prob, prob),
212 295050 : m_low (low), m_high (high), m_has_forward_bb (has_forward_bb)
213 : {
214 295050 : m_range_p = m_high != NULL;
215 295050 : if (m_high == NULL)
216 204031 : m_high = m_low;
217 295050 : }
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 11596 : get_low () final override
233 : {
234 11596 : return m_cases[0]->get_low ();
235 : }
236 :
237 : tree
238 11596 : get_high () final override
239 : {
240 23192 : 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 6499 : jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
265 6499 : : group_cluster (clusters, start, end)
266 : {}
267 :
268 : cluster_type
269 12425 : get_type () final override
270 : {
271 12425 : 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 4771 : bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end,
369 : bool handles_entire_switch)
370 4771 : :group_cluster (clusters, start, end),
371 4771 : m_handles_entire_switch (handles_entire_switch)
372 : {}
373 :
374 : cluster_type
375 13315 : get_type () final override
376 : {
377 13315 : 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 69228 : static inline bool is_enabled (void)
452 : {
453 69228 : 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 187582 : min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases):
471 341415 : 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 118473 : bool has_child ()
494 : {
495 118473 : 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 164629 : case_tree_node::case_tree_node ():
513 164629 : m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
514 : {
515 : }
516 :
517 : unsigned int
518 6641940 : jump_table_cluster::case_values_threshold (void)
519 : {
520 6641940 : unsigned int threshold = param_case_values_threshold;
521 :
522 6641940 : if (threshold == 0)
523 6641538 : threshold = targetm.case_values_threshold ();
524 :
525 6641940 : return threshold;
526 : }
527 :
528 : /* Return whether jump table expansion is allowed. */
529 2502937 : 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 2502937 : if (!targetm.have_casesi () && !targetm.have_tablejump ())
534 : return false;
535 2502937 : 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 11550 : class case_bit_test
555 : {
556 : public:
557 : wide_int mask;
558 : basic_block target_bb;
559 : int bits;
560 : profile_probability prob;
561 :
562 : /* Comparison function for qsort to order bit tests by decreasing
563 : probability of execution. */
564 : static int cmp (const void *p1, const void *p2);
565 : };
566 :
567 : class switch_decision_tree
568 : {
569 : public:
570 : /* Constructor. */
571 43305 : switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (),
572 43305 : m_case_bbs (), m_case_node_pool ("struct case_node pool"),
573 43305 : m_case_list (NULL)
574 : {
575 43305 : }
576 :
577 : /* Analyze switch statement and return true when the statement is expanded
578 : as decision tree. */
579 : bool analyze_switch_statement ();
580 :
581 : /* Attempt to expand CLUSTERS as a decision tree. Return true when
582 : expanded. */
583 : bool try_switch_expansion (vec<cluster *> &clusters);
584 : /* Compute the number of case labels that correspond to each outgoing edge of
585 : switch statement. Record this information in the aux field of the edge.
586 : Returns approx max number of cases per edge.
587 : */
588 : int compute_cases_per_edge ();
589 :
590 : /* Before switch transformation, record all SSA_NAMEs defined in switch BB
591 : and used in a label basic block. */
592 : void record_phi_operand_mapping ();
593 :
594 : /* Append new operands to PHI statements that were introduced due to
595 : addition of new edges to case labels. */
596 : void fix_phi_operands_for_edges ();
597 :
598 : /* Generate a decision tree, switching on INDEX_EXPR and jumping to
599 : one of the labels in CASE_LIST or to the DEFAULT_LABEL.
600 :
601 : We generate a binary decision tree to select the appropriate target
602 : code. */
603 : void emit (basic_block bb, tree index_expr,
604 : profile_probability default_prob, tree index_type);
605 :
606 : /* Emit step-by-step code to select a case for the value of INDEX.
607 : The thus generated decision tree follows the form of the
608 : case-node binary tree NODE, whose nodes represent test conditions.
609 : DEFAULT_PROB is probability of cases leading to default BB.
610 : INDEX_TYPE is the type of the index of the switch. */
611 : basic_block emit_case_nodes (basic_block bb, tree index,
612 : case_tree_node *node,
613 : profile_probability default_prob,
614 : tree index_type, location_t);
615 :
616 : /* Take an ordered list of case nodes
617 : and transform them into a near optimal binary tree,
618 : on the assumption that any target code selection value is as
619 : likely as any other.
620 :
621 : The transformation is performed by splitting the ordered
622 : list into two equal sections plus a pivot. The parts are
623 : then attached to the pivot as left and right branches. Each
624 : branch is then transformed recursively. */
625 : static void balance_case_nodes (case_tree_node **head,
626 : case_tree_node *parent);
627 :
628 : /* Dump ROOT, a list or tree of case nodes, to file F. */
629 : static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step,
630 : int indent_level);
631 :
632 : /* Add an unconditional jump to CASE_BB that happens in basic block BB. */
633 : static void emit_jump (basic_block bb, basic_block case_bb);
634 :
635 : /* Generate code to compare OP0 with OP1 so that the condition codes are
636 : set and to jump to LABEL_BB if the condition is true.
637 : COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
638 : PROB is the probability of jumping to LABEL_BB. */
639 : static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0,
640 : tree op1, tree_code comparison,
641 : basic_block label_bb,
642 : profile_probability prob,
643 : location_t);
644 :
645 : /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
646 : PROB is the probability of jumping to LABEL_BB. */
647 : static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1,
648 : basic_block label_bb,
649 : profile_probability prob,
650 : location_t);
651 :
652 : /* Reset the aux field of all outgoing edges of switch basic block. */
653 : static inline void reset_out_edges_aux (gswitch *swtch);
654 :
655 : /* Switch statement. */
656 : gswitch *m_switch;
657 :
658 : /* Map of PHI nodes that have to be fixed after expansion. */
659 : hash_map<tree, tree> m_phi_mapping;
660 :
661 : /* List of basic blocks that belong to labels of the switch. */
662 : auto_vec<basic_block> m_case_bbs;
663 :
664 : /* Basic block with default label. */
665 : basic_block m_default_bb;
666 :
667 : /* A pool for case nodes. */
668 : object_allocator<case_tree_node> m_case_node_pool;
669 :
670 : /* Balanced tree of case nodes. */
671 : case_tree_node *m_case_list;
672 : };
673 :
674 : /*
675 : Switch initialization conversion
676 :
677 : The following pass changes simple initializations of scalars in a switch
678 : statement into initializations from a static array. Obviously, the values
679 : must be constant and known at compile time and a default branch must be
680 : provided. For example, the following code:
681 :
682 : int a,b;
683 :
684 : switch (argc)
685 : {
686 : case 1:
687 : case 2:
688 : a_1 = 8;
689 : b_1 = 6;
690 : break;
691 : case 3:
692 : a_2 = 9;
693 : b_2 = 5;
694 : break;
695 : case 12:
696 : a_3 = 10;
697 : b_3 = 4;
698 : break;
699 : default:
700 : a_4 = 16;
701 : b_4 = 1;
702 : break;
703 : }
704 : a_5 = PHI <a_1, a_2, a_3, a_4>
705 : b_5 = PHI <b_1, b_2, b_3, b_4>
706 :
707 :
708 : is changed into:
709 :
710 : static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
711 : static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
712 : 16, 16, 10};
713 :
714 : if (((unsigned) argc) - 1 < 11)
715 : {
716 : a_6 = CSWTCH02[argc - 1];
717 : b_6 = CSWTCH01[argc - 1];
718 : }
719 : else
720 : {
721 : a_7 = 16;
722 : b_7 = 1;
723 : }
724 : a_5 = PHI <a_6, a_7>
725 : b_b = PHI <b_6, b_7>
726 :
727 : There are further constraints. Specifically, the range of values across all
728 : case labels must not be bigger than param_switch_conversion_branch_ratio
729 : (default eight) times the number of the actual switch branches.
730 :
731 : This transformation was contributed by Martin Jambor, see this e-mail:
732 : http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */
733 :
734 : /* The main structure of the pass. */
735 : class switch_conversion
736 : {
737 : public:
738 : /* Constructor. */
739 : switch_conversion ();
740 :
741 : /* Destructor. */
742 : ~switch_conversion ();
743 :
744 : /* The following function is invoked on every switch statement (the current
745 : one is given in SWTCH) and runs the individual phases of switch
746 : conversion on it one after another until one fails or the conversion
747 : is completed. On success, NULL is in m_reason, otherwise points
748 : to a string with the reason why the conversion failed. */
749 : void expand (gswitch *swtch);
750 :
751 : /* Collection information about SWTCH statement. */
752 : void collect (gswitch *swtch);
753 :
754 : /* Check that the 'exponential index transform' can be applied.
755 :
756 : See the comment at the function definition for more details. */
757 : bool is_exp_index_transform_viable (gswitch *swtch);
758 :
759 : /* Perform the 'exponential index transform'.
760 :
761 : The exponential index transform shrinks the range of case numbers which
762 : helps switch conversion convert switches it otherwise could not.
763 :
764 : See the comment at the function definition for more details. */
765 : void exp_index_transform (gswitch *swtch);
766 :
767 : /* Checks whether the range given by individual case statements of the switch
768 : switch statement isn't too big and whether the number of branches actually
769 : satisfies the size of the new array. */
770 : bool check_range ();
771 :
772 : /* Checks whether all but the final BB basic blocks are empty. */
773 : bool check_all_empty_except_final ();
774 :
775 : /* This function checks whether all required values in phi nodes in final_bb
776 : are constants. Required values are those that correspond to a basic block
777 : which is a part of the examined switch statement. It returns true if the
778 : phi nodes are OK, otherwise false. */
779 : bool check_final_bb ();
780 :
781 : /* The following function allocates default_values, target_{in,out}_names and
782 : constructors arrays. The last one is also populated with pointers to
783 : vectors that will become constructors of new arrays. */
784 : void create_temp_arrays ();
785 :
786 : /* Populate the array of default values in the order of phi nodes.
787 : DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch
788 : if the range is non-contiguous or the default case has standard
789 : structure, otherwise it is the first non-default case instead. */
790 : void gather_default_values (tree default_case);
791 :
792 : /* The following function populates the vectors in the constructors array with
793 : future contents of the static arrays. The vectors are populated in the
794 : order of phi nodes. */
795 : void build_constructors ();
796 :
797 : /* If all values in the constructor vector are products of a linear function
798 : a * x + b, then return true. When true, COEFF_A and COEFF_B and
799 : coefficients of the linear function. Note that equal values are special
800 : case of a linear function with a and b equal to zero. */
801 : bool contains_linear_function_p (vec<constructor_elt, va_gc> *vec,
802 : wide_int *coeff_a, wide_int *coeff_b);
803 :
804 : /* Return type which should be used for array elements, either TYPE's
805 : main variant or, for integral types, some smaller integral type
806 : that can still hold all the constants. */
807 : tree array_value_type (tree type, int num);
808 :
809 : /* Create an appropriate array type and declaration and assemble a static
810 : array variable. Also create a load statement that initializes
811 : the variable in question with a value from the static array. SWTCH is
812 : the switch statement being converted, NUM is the index to
813 : arrays of constructors, default values and target SSA names
814 : for this particular array. ARR_INDEX_TYPE is the type of the index
815 : of the new array, PHI is the phi node of the final BB that corresponds
816 : to the value that will be loaded from the created array. TIDX
817 : is an ssa name of a temporary variable holding the index for loads from the
818 : new array. */
819 : void build_one_array (int num, tree arr_index_type,
820 : gphi *phi, tree tidx);
821 :
822 : /* Builds and initializes static arrays initialized with values gathered from
823 : the switch statement. Also creates statements that load values from
824 : them. */
825 : void build_arrays ();
826 :
827 : /* Generates and appropriately inserts loads of default values at the position
828 : given by GSI. Returns the last inserted statement. */
829 : gassign *gen_def_assigns (gimple_stmt_iterator *gsi);
830 :
831 : /* Deletes the unused bbs and edges that now contain the switch statement and
832 : its empty branch bbs. BBD is the now dead BB containing
833 : the original switch statement, FINAL is the last BB of the converted
834 : switch statement (in terms of succession). */
835 : void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb);
836 :
837 : /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge
838 : from the basic block loading values from an array and E2F from the basic
839 : block loading default values. BBF is the last switch basic block (see the
840 : bbf description in the comment below). */
841 : void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf);
842 :
843 : /* Creates a check whether the switch expression value actually falls into the
844 : range given by all the cases. If it does not, the temporaries are loaded
845 : with default values instead. */
846 : void gen_inbound_check ();
847 :
848 : /* Switch statement for which switch conversion takes place. */
849 : gswitch *m_switch;
850 :
851 : /* The expression used to decide the switch branch. */
852 : tree m_index_expr;
853 :
854 : /* The following integer constants store the minimum and maximum value
855 : covered by the case labels. */
856 : tree m_range_min;
857 : tree m_range_max;
858 :
859 : /* The difference between the above two numbers. Stored here because it
860 : is used in all the conversion heuristics, as well as for some of the
861 : transformation, and it is expensive to re-compute it all the time. */
862 : tree m_range_size;
863 :
864 : /* Basic block that contains the actual GIMPLE_SWITCH. */
865 : basic_block m_switch_bb;
866 :
867 : /* Basic block that is the target of the default case. */
868 : basic_block m_default_bb;
869 :
870 : /* The single successor block of all branches out of the GIMPLE_SWITCH,
871 : if such a block exists. Otherwise NULL. */
872 : basic_block m_final_bb;
873 :
874 : /* The probability of the default edge in the replaced switch. */
875 : profile_probability m_default_prob;
876 :
877 : /* Number of phi nodes in the final bb (that we'll be replacing). */
878 : int m_phi_count;
879 :
880 : /* Constructors of new static arrays. */
881 : vec<constructor_elt, va_gc> **m_constructors;
882 :
883 : /* Array of default values, in the same order as phi nodes. */
884 : tree *m_default_values;
885 :
886 : /* Array of ssa names that are initialized with a value from a new static
887 : array. */
888 : tree *m_target_inbound_names;
889 :
890 : /* Array of ssa names that are initialized with the default value if the
891 : switch expression is out of range. */
892 : tree *m_target_outbound_names;
893 :
894 : /* VOP SSA_NAME. */
895 : tree m_target_vop;
896 :
897 : /* The first load statement that loads a temporary from a new static array.
898 : */
899 : gimple *m_arr_ref_first;
900 :
901 : /* The last load statement that loads a temporary from a new static array. */
902 : gimple *m_arr_ref_last;
903 :
904 : /* String reason why the case wasn't a good candidate that is written to the
905 : dump file, if there is one. */
906 : const char *m_reason;
907 :
908 : /* True if default case is not used for any value between range_min and
909 : range_max inclusive. */
910 : bool m_contiguous_range;
911 :
912 : /* True if default case does not have the required shape for other case
913 : labels. */
914 : bool m_default_case_nonstandard;
915 :
916 : /* Number of uniq labels for non-default edges. */
917 : unsigned int m_uniq;
918 :
919 : /* Count is number of non-default edges. */
920 : unsigned int m_count;
921 :
922 : /* True if CFG has been changed. */
923 : bool m_cfg_altered;
924 :
925 : /* True if exponential index transform has been applied. See the comment at
926 : the definition of exp_index_transform for details about the
927 : transformation. */
928 : bool m_exp_index_transform_applied;
929 :
930 : /* If switch conversion decided exponential index transform is viable, here
931 : will be stored the type to which index variable has to be converted
932 : before the logarithm operation which is a part of the transform. */
933 : tree m_exp_index_transform_log2_type;
934 : };
935 :
936 : void
937 92458 : switch_decision_tree::reset_out_edges_aux (gswitch *swtch)
938 : {
939 92458 : basic_block bb = gimple_bb (swtch);
940 92458 : edge e;
941 92458 : edge_iterator ei;
942 605223 : FOR_EACH_EDGE (e, ei, bb->succs)
943 512765 : e->aux = (void *) 0;
944 92458 : }
945 :
946 : /* Release CLUSTERS vector and destruct all dynamically allocated items. */
947 :
948 : inline void
949 69815 : release_clusters (vec<cluster *> &clusters)
950 : {
951 289365 : for (unsigned i = 0; i < clusters.length (); i++)
952 219550 : delete clusters[i];
953 69815 : clusters.release ();
954 69815 : }
955 :
956 : } // tree_switch_conversion namespace
957 :
958 : #endif // TREE_SWITCH_CONVERSION_H
|
