]>
Commit | Line | Data |
---|---|---|
789410e4 | 1 | /* Tree switch conversion for GNU compiler. |
a945c346 | 2 | Copyright (C) 2017-2024 Free Software Foundation, Inc. |
789410e4 ML |
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 | ||
dc223ad4 ML |
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 | ||
2f928c1b ML |
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). */ | |
dc223ad4 | 46 | |
6c1dae73 | 47 | class cluster |
dc223ad4 | 48 | { |
6c1dae73 | 49 | public: |
dc223ad4 | 50 | /* Constructor. */ |
03eb0929 ML |
51 | inline cluster (tree case_label_expr, basic_block case_bb, |
52 | profile_probability prob, profile_probability subtree_prob); | |
dc223ad4 ML |
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. */ | |
4ede02a5 | 74 | virtual void emit (tree, tree, tree, basic_block, location_t) = 0; |
dc223ad4 | 75 | |
bb79aba4 ML |
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 | ||
dc223ad4 ML |
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 | { | |
e46858e4 ML |
87 | wide_int w = wi::to_wide (high) - wi::to_wide (low); |
88 | if (wi::neg_p (w, TYPE_SIGN (TREE_TYPE (low))) || !wi::fits_uhwi_p (w)) | |
dc223ad4 | 89 | return 0; |
e46858e4 | 90 | return w.to_uhwi () + 1; |
dc223ad4 ML |
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 | ||
4fa25a7e ML |
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 | ||
dc223ad4 ML |
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), | |
4fa25a7e ML |
117 | m_subtree_prob (subtree_prob), |
118 | m_default_prob (profile_probability::uninitialized ()) | |
dc223ad4 ML |
119 | { |
120 | } | |
121 | ||
122 | /* Subclass of cluster representing a simple contiguous range | |
123 | from [low..high]. */ | |
124 | ||
6c1dae73 | 125 | class simple_cluster: public cluster |
dc223ad4 | 126 | { |
6c1dae73 | 127 | public: |
dc223ad4 | 128 | /* Constructor. */ |
03eb0929 ML |
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); | |
dc223ad4 ML |
132 | |
133 | /* Destructor. */ | |
134 | ~simple_cluster () | |
135 | {} | |
136 | ||
137 | cluster_type | |
a2f2e0ff | 138 | get_type () final override |
dc223ad4 ML |
139 | { |
140 | return SIMPLE_CASE; | |
141 | } | |
142 | ||
143 | tree | |
a2f2e0ff | 144 | get_low () final override |
dc223ad4 ML |
145 | { |
146 | return m_low; | |
147 | } | |
148 | ||
149 | tree | |
a2f2e0ff | 150 | get_high () final override |
dc223ad4 ML |
151 | { |
152 | return m_high; | |
153 | } | |
154 | ||
03eb0929 ML |
155 | void set_high (tree high) |
156 | { | |
157 | m_high = high; | |
158 | } | |
159 | ||
dc223ad4 | 160 | void |
a2f2e0ff | 161 | debug () final override |
dc223ad4 ML |
162 | { |
163 | dump (stderr); | |
164 | } | |
165 | ||
166 | void | |
a2f2e0ff | 167 | dump (FILE *f, bool details ATTRIBUTE_UNUSED = false) final override |
dc223ad4 ML |
168 | { |
169 | PRINT_CASE (f, get_low ()); | |
170 | if (get_low () != get_high ()) | |
171 | { | |
172 | fprintf (f, "-"); | |
173 | PRINT_CASE (f, get_high ()); | |
174 | } | |
175 | fprintf (f, " "); | |
176 | } | |
177 | ||
a2f2e0ff | 178 | void emit (tree, tree, tree, basic_block, location_t) final override |
dc223ad4 ML |
179 | { |
180 | gcc_unreachable (); | |
181 | } | |
182 | ||
a2f2e0ff | 183 | bool is_single_value_p () final override |
bb79aba4 ML |
184 | { |
185 | return tree_int_cst_equal (get_low (), get_high ()); | |
186 | } | |
187 | ||
c517cf2e ML |
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 | ||
dc223ad4 ML |
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; | |
03eb0929 ML |
203 | |
204 | /* True if the case will use a forwarder BB. */ | |
205 | bool m_has_forward_bb; | |
dc223ad4 ML |
206 | }; |
207 | ||
208 | simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr, | |
03eb0929 ML |
209 | basic_block case_bb, profile_probability prob, |
210 | bool has_forward_bb): | |
dc223ad4 | 211 | cluster (case_label_expr, case_bb, prob, prob), |
03eb0929 | 212 | m_low (low), m_high (high), m_has_forward_bb (has_forward_bb) |
dc223ad4 ML |
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 | ||
6c1dae73 | 222 | class group_cluster: public cluster |
dc223ad4 | 223 | { |
6c1dae73 | 224 | public: |
dc223ad4 ML |
225 | /* Constructor. */ |
226 | group_cluster (vec<cluster *> &clusters, unsigned start, unsigned end); | |
227 | ||
228 | /* Destructor. */ | |
229 | ~group_cluster (); | |
230 | ||
231 | tree | |
a2f2e0ff | 232 | get_low () final override |
dc223ad4 ML |
233 | { |
234 | return m_cases[0]->get_low (); | |
235 | } | |
236 | ||
237 | tree | |
a2f2e0ff | 238 | get_high () final override |
dc223ad4 ML |
239 | { |
240 | return m_cases[m_cases.length () - 1]->get_high (); | |
241 | } | |
242 | ||
243 | void | |
a2f2e0ff | 244 | debug () final override |
dc223ad4 ML |
245 | { |
246 | dump (stderr); | |
247 | } | |
248 | ||
a2f2e0ff | 249 | void dump (FILE *f, bool details = false) final override; |
dc223ad4 ML |
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. | |
3104a9fa | 257 | The "emit" vfunc generates a nested switch statement which |
dc223ad4 ML |
258 | is later lowered to a jump table. */ |
259 | ||
6c1dae73 | 260 | class jump_table_cluster: public group_cluster |
dc223ad4 | 261 | { |
6c1dae73 | 262 | public: |
dc223ad4 ML |
263 | /* Constructor. */ |
264 | jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end) | |
265 | : group_cluster (clusters, start, end) | |
266 | {} | |
267 | ||
268 | cluster_type | |
a2f2e0ff | 269 | get_type () final override |
dc223ad4 ML |
270 | { |
271 | return JUMP_TABLE; | |
272 | } | |
273 | ||
274 | void emit (tree index_expr, tree index_type, | |
a2f2e0ff DM |
275 | tree default_label_expr, basic_block default_bb, location_t loc) |
276 | final override; | |
dc223ad4 | 277 | |
2f928c1b ML |
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 | ||
dc223ad4 | 282 | /* Return true when cluster starting at START and ending at END (inclusive) |
c517cf2e ML |
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). */ | |
dc223ad4 | 286 | static bool can_be_handled (const vec<cluster *> &clusters, unsigned start, |
c517cf2e ML |
287 | unsigned end, unsigned HOST_WIDE_INT max_ratio, |
288 | unsigned HOST_WIDE_INT comparison_count); | |
dc223ad4 ML |
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); | |
5885a1bd ML |
298 | |
299 | /* Return whether jump table expansion is allowed. */ | |
03eb0929 | 300 | static inline bool is_enabled (void); |
dc223ad4 ML |
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 | |
fcb38196 | 306 | of compare-and-branch insns in some cases, e.g. we can implement: |
dc223ad4 ML |
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 | ||
6c1dae73 | 364 | class bit_test_cluster: public group_cluster |
dc223ad4 | 365 | { |
6c1dae73 | 366 | public: |
dc223ad4 | 367 | /* Constructor. */ |
377afcd5 ML |
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) | |
dc223ad4 ML |
372 | {} |
373 | ||
374 | cluster_type | |
a2f2e0ff | 375 | get_type () final override |
dc223ad4 ML |
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, | |
a2f2e0ff DM |
397 | tree default_label_expr, basic_block default_bb, location_t loc) |
398 | final override; | |
dc223ad4 | 399 | |
2f928c1b ML |
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 | ||
dc223ad4 ML |
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, | |
377afcd5 | 438 | basic_block case_bb, |
bc86a86a RB |
439 | profile_probability prob, |
440 | location_t); | |
377afcd5 | 441 | |
9b11203e ML |
442 | /* Return whether bit test expansion is allowed. */ |
443 | static inline bool is_enabled (void) | |
444 | { | |
445 | return flag_bit_tests; | |
446 | } | |
447 | ||
377afcd5 ML |
448 | /* True when the jump table handles an entire switch statement. */ |
449 | bool m_handles_entire_switch; | |
dc223ad4 ML |
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 | ||
6c1dae73 | 458 | class min_cluster_item |
dc223ad4 | 459 | { |
6c1dae73 | 460 | public: |
dc223ad4 ML |
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 | ||
6c1dae73 | 478 | class case_tree_node |
dc223ad4 | 479 | { |
6c1dae73 | 480 | public: |
dc223ad4 ML |
481 | /* Empty Constructor. */ |
482 | case_tree_node (); | |
483 | ||
bb79aba4 ML |
484 | /* Return true when it has a child. */ |
485 | bool has_child () | |
486 | { | |
487 | return m_left != NULL || m_right != NULL; | |
488 | } | |
489 | ||
dc223ad4 ML |
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 | { | |
028d4092 | 512 | unsigned int threshold = param_case_values_threshold; |
dc223ad4 ML |
513 | |
514 | if (threshold == 0) | |
515 | threshold = targetm.case_values_threshold (); | |
516 | ||
517 | return threshold; | |
518 | } | |
519 | ||
5885a1bd ML |
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 | ||
dc223ad4 ML |
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 | ||
6c1dae73 | 546 | class case_bit_test |
dc223ad4 | 547 | { |
6c1dae73 | 548 | public: |
dc223ad4 ML |
549 | wide_int mask; |
550 | basic_block target_bb; | |
551 | tree label; | |
552 | int bits; | |
4fa25a7e | 553 | profile_probability prob; |
dc223ad4 ML |
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 | ||
6c1dae73 | 560 | class switch_decision_tree |
dc223ad4 | 561 | { |
6c1dae73 | 562 | public: |
dc223ad4 ML |
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); | |
dc223ad4 ML |
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, | |
4359b631 | 606 | tree index_type, location_t); |
dc223ad4 ML |
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, | |
4359b631 EB |
634 | profile_probability prob, |
635 | location_t); | |
dc223ad4 | 636 | |
bb79aba4 ML |
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, | |
4359b631 EB |
641 | profile_probability prob, |
642 | location_t); | |
bb79aba4 | 643 | |
dbdfaaba ML |
644 | /* Reset the aux field of all outgoing edges of switch basic block. */ |
645 | static inline void reset_out_edges_aux (gswitch *swtch); | |
646 | ||
dc223ad4 ML |
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 | ||
789410e4 ML |
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 | |
028d4092 ML |
720 | case labels must not be bigger than param_switch_conversion_branch_ratio |
721 | (default eight) times the number of the actual switch branches. | |
789410e4 ML |
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. */ | |
6c1dae73 | 727 | class switch_conversion |
789410e4 | 728 | { |
6c1dae73 | 729 | public: |
789410e4 ML |
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 | ||
767d4551 ML |
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); | |
789410e4 ML |
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 | ||
789410e4 ML |
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 | ||
dc223ad4 ML |
895 | /* Number of uniq labels for non-default edges. */ |
896 | unsigned int m_uniq; | |
897 | ||
789410e4 ML |
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 | ||
dc223ad4 | 905 | void |
dbdfaaba | 906 | switch_decision_tree::reset_out_edges_aux (gswitch *swtch) |
dc223ad4 | 907 | { |
dbdfaaba | 908 | basic_block bb = gimple_bb (swtch); |
dc223ad4 ML |
909 | edge e; |
910 | edge_iterator ei; | |
911 | FOR_EACH_EDGE (e, ei, bb->succs) | |
912 | e->aux = (void *) 0; | |
913 | } | |
914 | ||
57d1b68d ML |
915 | /* Release CLUSTERS vector and destruct all dynamically allocated items. */ |
916 | ||
cb3e0eac | 917 | inline void |
57d1b68d ML |
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 | ||
789410e4 ML |
925 | } // tree_switch_conversion namespace |
926 | ||
927 | #endif // TREE_SWITCH_CONVERSION_H |