1 | /* Tree switch conversion for GNU compiler. |
2 | Copyright (C) 2017-2023 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 | 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 | virtual bool is_single_value_p () |
79 | { |
80 | return false; |
81 | } |
82 | |
83 | /* Return range of a cluster. If value would overflow in type of LOW, |
84 | then return 0. */ |
85 | static unsigned HOST_WIDE_INT get_range (tree low, tree high) |
86 | { |
87 | wide_int w = wi::to_wide (t: high) - wi::to_wide (t: low); |
88 | if (wi::neg_p (x: w, TYPE_SIGN (TREE_TYPE (low))) || !wi::fits_uhwi_p (x: w)) |
89 | return 0; |
90 | return w.to_uhwi () + 1; |
91 | } |
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 | cluster () {} |
112 | }; |
113 | |
114 | cluster::cluster (tree case_label_expr, basic_block case_bb, |
115 | profile_probability prob, profile_probability subtree_prob): |
116 | m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob), |
117 | m_subtree_prob (subtree_prob), |
118 | 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 | ~simple_cluster () |
135 | {} |
136 | |
137 | cluster_type |
138 | get_type () final override |
139 | { |
140 | return SIMPLE_CASE; |
141 | } |
142 | |
143 | tree |
144 | get_low () final override |
145 | { |
146 | return m_low; |
147 | } |
148 | |
149 | tree |
150 | get_high () final override |
151 | { |
152 | return m_high; |
153 | } |
154 | |
155 | void set_high (tree high) |
156 | { |
157 | m_high = high; |
158 | } |
159 | |
160 | void |
161 | debug () final override |
162 | { |
163 | dump (stderr); |
164 | } |
165 | |
166 | void |
167 | dump (FILE *f, bool details ATTRIBUTE_UNUSED = false) final override |
168 | { |
169 | PRINT_CASE (f, get_low ()); |
170 | if (get_low () != get_high ()) |
171 | { |
172 | fprintf (stream: f, format: "-" ); |
173 | PRINT_CASE (f, get_high ()); |
174 | } |
175 | fprintf (stream: f, format: " " ); |
176 | } |
177 | |
178 | void emit (tree, tree, tree, basic_block, location_t) final override |
179 | { |
180 | gcc_unreachable (); |
181 | } |
182 | |
183 | bool is_single_value_p () final override |
184 | { |
185 | return tree_int_cst_equal (get_low (), get_high ()); |
186 | } |
187 | |
188 | /* Return number of comparisons needed for the case. */ |
189 | unsigned |
190 | get_comparison_count () |
191 | { |
192 | 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 | simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr, |
209 | basic_block case_bb, profile_probability prob, |
210 | bool has_forward_bb): |
211 | cluster (case_label_expr, case_bb, prob, prob), |
212 | m_low (low), m_high (high), m_has_forward_bb (has_forward_bb) |
213 | { |
214 | m_range_p = m_high != NULL; |
215 | if (m_high == NULL) |
216 | m_high = m_low; |
217 | } |
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 | get_low () final override |
233 | { |
234 | return m_cases[0]->get_low (); |
235 | } |
236 | |
237 | tree |
238 | get_high () final override |
239 | { |
240 | return m_cases[m_cases.length () - 1]->get_high (); |
241 | } |
242 | |
243 | void |
244 | debug () final override |
245 | { |
246 | dump (stderr); |
247 | } |
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 | jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end) |
265 | : group_cluster (clusters, start, end) |
266 | {} |
267 | |
268 | cluster_type |
269 | get_type () final override |
270 | { |
271 | 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 | bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end, |
369 | bool handles_entire_switch) |
370 | :group_cluster (clusters, start, end), |
371 | m_handles_entire_switch (handles_entire_switch) |
372 | {} |
373 | |
374 | cluster_type |
375 | get_type () final override |
376 | { |
377 | 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 |
401 | are of type simple_cluster. New clusters are returned. */ |
402 | static vec<cluster *> find_bit_tests (vec<cluster *> &clusters); |
403 | |
404 | /* Return true when RANGE of case values with UNIQ labels |
405 | can build a bit test. */ |
406 | static bool can_be_handled (unsigned HOST_WIDE_INT range, unsigned uniq); |
407 | |
408 | /* Return true when cluster starting at START and ending at END (inclusive) |
409 | can build a bit test. */ |
410 | static bool can_be_handled (const vec<cluster *> &clusters, unsigned start, |
411 | unsigned end); |
412 | |
413 | /* Return true when COUNT of cases of UNIQ labels is beneficial for bit test |
414 | transformation. */ |
415 | static bool is_beneficial (unsigned count, unsigned uniq); |
416 | |
417 | /* Return true if cluster starting at START and ending at END (inclusive) |
418 | is profitable transformation. */ |
419 | static bool is_beneficial (const vec<cluster *> &clusters, unsigned start, |
420 | unsigned end); |
421 | |
422 | /* Split the basic block at the statement pointed to by GSIP, and insert |
423 | a branch to the target basic block of E_TRUE conditional on tree |
424 | expression COND. |
425 | |
426 | It is assumed that there is already an edge from the to-be-split |
427 | basic block to E_TRUE->dest block. This edge is removed, and the |
428 | profile information on the edge is re-used for the new conditional |
429 | jump. |
430 | |
431 | The CFG is updated. The dominator tree will not be valid after |
432 | this transformation, but the immediate dominators are updated if |
433 | UPDATE_DOMINATORS is true. |
434 | |
435 | Returns the newly created basic block. */ |
436 | static basic_block hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip, |
437 | tree cond, |
438 | basic_block case_bb, |
439 | profile_probability prob, |
440 | location_t); |
441 | |
442 | /* Return whether bit test expansion is allowed. */ |
443 | static inline bool is_enabled (void) |
444 | { |
445 | return flag_bit_tests; |
446 | } |
447 | |
448 | /* True when the jump table handles an entire switch statement. */ |
449 | bool m_handles_entire_switch; |
450 | |
451 | /* Maximum number of different basic blocks that can be handled by |
452 | a bit test. */ |
453 | static const int m_max_case_bit_tests = 3; |
454 | }; |
455 | |
456 | /* Helper struct to find minimal clusters. */ |
457 | |
458 | class min_cluster_item |
459 | { |
460 | public: |
461 | /* Constructor. */ |
462 | min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases): |
463 | m_count (count), m_start (start), m_non_jt_cases (non_jt_cases) |
464 | {} |
465 | |
466 | /* Count of clusters. */ |
467 | unsigned m_count; |
468 | |
469 | /* Index where is cluster boundary. */ |
470 | unsigned m_start; |
471 | |
472 | /* Total number of cases that will not be in a jump table. */ |
473 | unsigned m_non_jt_cases; |
474 | }; |
475 | |
476 | /* Helper struct to represent switch decision tree. */ |
477 | |
478 | class case_tree_node |
479 | { |
480 | public: |
481 | /* Empty Constructor. */ |
482 | case_tree_node (); |
483 | |
484 | /* Return true when it has a child. */ |
485 | bool has_child () |
486 | { |
487 | return m_left != NULL || m_right != NULL; |
488 | } |
489 | |
490 | /* Left son in binary tree. */ |
491 | case_tree_node *m_left; |
492 | |
493 | /* Right son in binary tree; also node chain. */ |
494 | case_tree_node *m_right; |
495 | |
496 | /* Parent of node in binary tree. */ |
497 | case_tree_node *m_parent; |
498 | |
499 | /* Cluster represented by this tree node. */ |
500 | cluster *m_c; |
501 | }; |
502 | |
503 | inline |
504 | case_tree_node::case_tree_node (): |
505 | m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL) |
506 | { |
507 | } |
508 | |
509 | unsigned int |
510 | jump_table_cluster::case_values_threshold (void) |
511 | { |
512 | unsigned int threshold = param_case_values_threshold; |
513 | |
514 | if (threshold == 0) |
515 | threshold = targetm.case_values_threshold (); |
516 | |
517 | return threshold; |
518 | } |
519 | |
520 | /* Return whether jump table expansion is allowed. */ |
521 | bool jump_table_cluster::is_enabled (void) |
522 | { |
523 | /* If neither casesi or tablejump is available, or flag_jump_tables |
524 | over-ruled us, we really have no choice. */ |
525 | if (!targetm.have_casesi () && !targetm.have_tablejump ()) |
526 | return false; |
527 | if (!flag_jump_tables) |
528 | return false; |
529 | #ifndef ASM_OUTPUT_ADDR_DIFF_ELT |
530 | if (flag_pic) |
531 | return false; |
532 | #endif |
533 | |
534 | return true; |
535 | } |
536 | |
537 | /* A case_bit_test represents a set of case nodes that may be |
538 | selected from using a bit-wise comparison. HI and LO hold |
539 | the integer to be tested against, TARGET_EDGE contains the |
540 | edge to the basic block to jump to upon success and BITS |
541 | counts the number of case nodes handled by this test, |
542 | typically the number of bits set in HI:LO. The LABEL field |
543 | is used to quickly identify all cases in this set without |
544 | looking at label_to_block for every case label. */ |
545 | |
546 | class case_bit_test |
547 | { |
548 | public: |
549 | wide_int mask; |
550 | basic_block target_bb; |
551 | tree label; |
552 | int bits; |
553 | profile_probability prob; |
554 | |
555 | /* Comparison function for qsort to order bit tests by decreasing |
556 | probability of execution. */ |
557 | static int cmp (const void *p1, const void *p2); |
558 | }; |
559 | |
560 | class switch_decision_tree |
561 | { |
562 | public: |
563 | /* Constructor. */ |
564 | switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (), |
565 | m_case_bbs (), m_case_node_pool ("struct case_node pool" ), |
566 | m_case_list (NULL) |
567 | { |
568 | } |
569 | |
570 | /* Analyze switch statement and return true when the statement is expanded |
571 | as decision tree. */ |
572 | bool analyze_switch_statement (); |
573 | |
574 | /* Attempt to expand CLUSTERS as a decision tree. Return true when |
575 | expanded. */ |
576 | bool try_switch_expansion (vec<cluster *> &clusters); |
577 | /* Compute the number of case labels that correspond to each outgoing edge of |
578 | switch statement. Record this information in the aux field of the edge. |
579 | */ |
580 | void compute_cases_per_edge (); |
581 | |
582 | /* Before switch transformation, record all SSA_NAMEs defined in switch BB |
583 | and used in a label basic block. */ |
584 | void record_phi_operand_mapping (); |
585 | |
586 | /* Append new operands to PHI statements that were introduced due to |
587 | addition of new edges to case labels. */ |
588 | void fix_phi_operands_for_edges (); |
589 | |
590 | /* Generate a decision tree, switching on INDEX_EXPR and jumping to |
591 | one of the labels in CASE_LIST or to the DEFAULT_LABEL. |
592 | |
593 | We generate a binary decision tree to select the appropriate target |
594 | code. */ |
595 | void emit (basic_block bb, tree index_expr, |
596 | profile_probability default_prob, tree index_type); |
597 | |
598 | /* Emit step-by-step code to select a case for the value of INDEX. |
599 | The thus generated decision tree follows the form of the |
600 | case-node binary tree NODE, whose nodes represent test conditions. |
601 | DEFAULT_PROB is probability of cases leading to default BB. |
602 | INDEX_TYPE is the type of the index of the switch. */ |
603 | basic_block emit_case_nodes (basic_block bb, tree index, |
604 | case_tree_node *node, |
605 | profile_probability default_prob, |
606 | tree index_type, location_t); |
607 | |
608 | /* Take an ordered list of case nodes |
609 | and transform them into a near optimal binary tree, |
610 | on the assumption that any target code selection value is as |
611 | likely as any other. |
612 | |
613 | The transformation is performed by splitting the ordered |
614 | list into two equal sections plus a pivot. The parts are |
615 | then attached to the pivot as left and right branches. Each |
616 | branch is then transformed recursively. */ |
617 | static void balance_case_nodes (case_tree_node **head, |
618 | case_tree_node *parent); |
619 | |
620 | /* Dump ROOT, a list or tree of case nodes, to file F. */ |
621 | static void dump_case_nodes (FILE *f, case_tree_node *root, int indent_step, |
622 | int indent_level); |
623 | |
624 | /* Add an unconditional jump to CASE_BB that happens in basic block BB. */ |
625 | static void emit_jump (basic_block bb, basic_block case_bb); |
626 | |
627 | /* Generate code to compare OP0 with OP1 so that the condition codes are |
628 | set and to jump to LABEL_BB if the condition is true. |
629 | COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.). |
630 | PROB is the probability of jumping to LABEL_BB. */ |
631 | static basic_block emit_cmp_and_jump_insns (basic_block bb, tree op0, |
632 | tree op1, tree_code comparison, |
633 | basic_block label_bb, |
634 | profile_probability prob, |
635 | location_t); |
636 | |
637 | /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE. |
638 | PROB is the probability of jumping to LABEL_BB. */ |
639 | static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1, |
640 | basic_block label_bb, |
641 | profile_probability prob, |
642 | location_t); |
643 | |
644 | /* Reset the aux field of all outgoing edges of switch basic block. */ |
645 | static inline void reset_out_edges_aux (gswitch *swtch); |
646 | |
647 | /* Switch statement. */ |
648 | gswitch *m_switch; |
649 | |
650 | /* Map of PHI nodes that have to be fixed after expansion. */ |
651 | hash_map<tree, tree> m_phi_mapping; |
652 | |
653 | /* List of basic blocks that belong to labels of the switch. */ |
654 | auto_vec<basic_block> m_case_bbs; |
655 | |
656 | /* Basic block with default label. */ |
657 | basic_block m_default_bb; |
658 | |
659 | /* A pool for case nodes. */ |
660 | object_allocator<case_tree_node> m_case_node_pool; |
661 | |
662 | /* Balanced tree of case nodes. */ |
663 | case_tree_node *m_case_list; |
664 | }; |
665 | |
666 | /* |
667 | Switch initialization conversion |
668 | |
669 | The following pass changes simple initializations of scalars in a switch |
670 | statement into initializations from a static array. Obviously, the values |
671 | must be constant and known at compile time and a default branch must be |
672 | provided. For example, the following code: |
673 | |
674 | int a,b; |
675 | |
676 | switch (argc) |
677 | { |
678 | case 1: |
679 | case 2: |
680 | a_1 = 8; |
681 | b_1 = 6; |
682 | break; |
683 | case 3: |
684 | a_2 = 9; |
685 | b_2 = 5; |
686 | break; |
687 | case 12: |
688 | a_3 = 10; |
689 | b_3 = 4; |
690 | break; |
691 | default: |
692 | a_4 = 16; |
693 | b_4 = 1; |
694 | break; |
695 | } |
696 | a_5 = PHI <a_1, a_2, a_3, a_4> |
697 | b_5 = PHI <b_1, b_2, b_3, b_4> |
698 | |
699 | |
700 | is changed into: |
701 | |
702 | static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4}; |
703 | static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16, |
704 | 16, 16, 10}; |
705 | |
706 | if (((unsigned) argc) - 1 < 11) |
707 | { |
708 | a_6 = CSWTCH02[argc - 1]; |
709 | b_6 = CSWTCH01[argc - 1]; |
710 | } |
711 | else |
712 | { |
713 | a_7 = 16; |
714 | b_7 = 1; |
715 | } |
716 | a_5 = PHI <a_6, a_7> |
717 | b_b = PHI <b_6, b_7> |
718 | |
719 | There are further constraints. Specifically, the range of values across all |
720 | case labels must not be bigger than param_switch_conversion_branch_ratio |
721 | (default eight) times the number of the actual switch branches. |
722 | |
723 | This transformation was contributed by Martin Jambor, see this e-mail: |
724 | http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00011.html */ |
725 | |
726 | /* The main structure of the pass. */ |
727 | class switch_conversion |
728 | { |
729 | public: |
730 | /* Constructor. */ |
731 | switch_conversion (); |
732 | |
733 | /* Destructor. */ |
734 | ~switch_conversion (); |
735 | |
736 | /* The following function is invoked on every switch statement (the current |
737 | one is given in SWTCH) and runs the individual phases of switch |
738 | conversion on it one after another until one fails or the conversion |
739 | is completed. On success, NULL is in m_reason, otherwise points |
740 | to a string with the reason why the conversion failed. */ |
741 | void expand (gswitch *swtch); |
742 | |
743 | /* Collection information about SWTCH statement. */ |
744 | void collect (gswitch *swtch); |
745 | |
746 | /* Checks whether the range given by individual case statements of the switch |
747 | switch statement isn't too big and whether the number of branches actually |
748 | satisfies the size of the new array. */ |
749 | bool check_range (); |
750 | |
751 | /* Checks whether all but the final BB basic blocks are empty. */ |
752 | bool check_all_empty_except_final (); |
753 | |
754 | /* This function checks whether all required values in phi nodes in final_bb |
755 | are constants. Required values are those that correspond to a basic block |
756 | which is a part of the examined switch statement. It returns true if the |
757 | phi nodes are OK, otherwise false. */ |
758 | bool check_final_bb (); |
759 | |
760 | /* The following function allocates default_values, target_{in,out}_names and |
761 | constructors arrays. The last one is also populated with pointers to |
762 | vectors that will become constructors of new arrays. */ |
763 | void create_temp_arrays (); |
764 | |
765 | /* Populate the array of default values in the order of phi nodes. |
766 | DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch |
767 | if the range is non-contiguous or the default case has standard |
768 | structure, otherwise it is the first non-default case instead. */ |
769 | void gather_default_values (tree default_case); |
770 | |
771 | /* The following function populates the vectors in the constructors array with |
772 | future contents of the static arrays. The vectors are populated in the |
773 | order of phi nodes. */ |
774 | void build_constructors (); |
775 | |
776 | /* If all values in the constructor vector are products of a linear function |
777 | a * x + b, then return true. When true, COEFF_A and COEFF_B and |
778 | coefficients of the linear function. Note that equal values are special |
779 | case of a linear function with a and b equal to zero. */ |
780 | bool contains_linear_function_p (vec<constructor_elt, va_gc> *vec, |
781 | wide_int *coeff_a, wide_int *coeff_b); |
782 | |
783 | /* Return type which should be used for array elements, either TYPE's |
784 | main variant or, for integral types, some smaller integral type |
785 | that can still hold all the constants. */ |
786 | tree array_value_type (tree type, int num); |
787 | |
788 | /* Create an appropriate array type and declaration and assemble a static |
789 | array variable. Also create a load statement that initializes |
790 | the variable in question with a value from the static array. SWTCH is |
791 | the switch statement being converted, NUM is the index to |
792 | arrays of constructors, default values and target SSA names |
793 | for this particular array. ARR_INDEX_TYPE is the type of the index |
794 | of the new array, PHI is the phi node of the final BB that corresponds |
795 | to the value that will be loaded from the created array. TIDX |
796 | is an ssa name of a temporary variable holding the index for loads from the |
797 | new array. */ |
798 | void build_one_array (int num, tree arr_index_type, |
799 | gphi *phi, tree tidx); |
800 | |
801 | /* Builds and initializes static arrays initialized with values gathered from |
802 | the switch statement. Also creates statements that load values from |
803 | them. */ |
804 | void build_arrays (); |
805 | |
806 | /* Generates and appropriately inserts loads of default values at the position |
807 | given by GSI. Returns the last inserted statement. */ |
808 | gassign *gen_def_assigns (gimple_stmt_iterator *gsi); |
809 | |
810 | /* Deletes the unused bbs and edges that now contain the switch statement and |
811 | its empty branch bbs. BBD is the now dead BB containing |
812 | the original switch statement, FINAL is the last BB of the converted |
813 | switch statement (in terms of succession). */ |
814 | void prune_bbs (basic_block bbd, basic_block final, basic_block default_bb); |
815 | |
816 | /* Add values to phi nodes in final_bb for the two new edges. E1F is the edge |
817 | from the basic block loading values from an array and E2F from the basic |
818 | block loading default values. BBF is the last switch basic block (see the |
819 | bbf description in the comment below). */ |
820 | void fix_phi_nodes (edge e1f, edge e2f, basic_block bbf); |
821 | |
822 | /* Creates a check whether the switch expression value actually falls into the |
823 | range given by all the cases. If it does not, the temporaries are loaded |
824 | with default values instead. */ |
825 | void gen_inbound_check (); |
826 | |
827 | /* Switch statement for which switch conversion takes place. */ |
828 | gswitch *m_switch; |
829 | |
830 | /* The expression used to decide the switch branch. */ |
831 | tree m_index_expr; |
832 | |
833 | /* The following integer constants store the minimum and maximum value |
834 | covered by the case labels. */ |
835 | tree m_range_min; |
836 | tree m_range_max; |
837 | |
838 | /* The difference between the above two numbers. Stored here because it |
839 | is used in all the conversion heuristics, as well as for some of the |
840 | transformation, and it is expensive to re-compute it all the time. */ |
841 | tree m_range_size; |
842 | |
843 | /* Basic block that contains the actual GIMPLE_SWITCH. */ |
844 | basic_block m_switch_bb; |
845 | |
846 | /* Basic block that is the target of the default case. */ |
847 | basic_block m_default_bb; |
848 | |
849 | /* The single successor block of all branches out of the GIMPLE_SWITCH, |
850 | if such a block exists. Otherwise NULL. */ |
851 | basic_block m_final_bb; |
852 | |
853 | /* The probability of the default edge in the replaced switch. */ |
854 | profile_probability m_default_prob; |
855 | |
856 | /* Number of phi nodes in the final bb (that we'll be replacing). */ |
857 | int m_phi_count; |
858 | |
859 | /* Constructors of new static arrays. */ |
860 | vec<constructor_elt, va_gc> **m_constructors; |
861 | |
862 | /* Array of default values, in the same order as phi nodes. */ |
863 | tree *m_default_values; |
864 | |
865 | /* Array of ssa names that are initialized with a value from a new static |
866 | array. */ |
867 | tree *m_target_inbound_names; |
868 | |
869 | /* Array of ssa names that are initialized with the default value if the |
870 | switch expression is out of range. */ |
871 | tree *m_target_outbound_names; |
872 | |
873 | /* VOP SSA_NAME. */ |
874 | tree m_target_vop; |
875 | |
876 | /* The first load statement that loads a temporary from a new static array. |
877 | */ |
878 | gimple *m_arr_ref_first; |
879 | |
880 | /* The last load statement that loads a temporary from a new static array. */ |
881 | gimple *m_arr_ref_last; |
882 | |
883 | /* String reason why the case wasn't a good candidate that is written to the |
884 | dump file, if there is one. */ |
885 | const char *m_reason; |
886 | |
887 | /* True if default case is not used for any value between range_min and |
888 | range_max inclusive. */ |
889 | bool m_contiguous_range; |
890 | |
891 | /* True if default case does not have the required shape for other case |
892 | labels. */ |
893 | bool m_default_case_nonstandard; |
894 | |
895 | /* Number of uniq labels for non-default edges. */ |
896 | unsigned int m_uniq; |
897 | |
898 | /* Count is number of non-default edges. */ |
899 | unsigned int m_count; |
900 | |
901 | /* True if CFG has been changed. */ |
902 | bool m_cfg_altered; |
903 | }; |
904 | |
905 | void |
906 | switch_decision_tree::reset_out_edges_aux (gswitch *swtch) |
907 | { |
908 | basic_block bb = gimple_bb (g: swtch); |
909 | edge e; |
910 | edge_iterator ei; |
911 | FOR_EACH_EDGE (e, ei, bb->succs) |
912 | e->aux = (void *) 0; |
913 | } |
914 | |
915 | /* Release CLUSTERS vector and destruct all dynamically allocated items. */ |
916 | |
917 | inline void |
918 | release_clusters (vec<cluster *> &clusters) |
919 | { |
920 | for (unsigned i = 0; i < clusters.length (); i++) |
921 | delete clusters[i]; |
922 | clusters.release (); |
923 | } |
924 | |
925 | } // tree_switch_conversion namespace |
926 | |
927 | #endif // TREE_SWITCH_CONVERSION_H |
928 | |