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