Branch data Line data Source code
1 : : /* Tree switch conversion for GNU compiler.
2 : : Copyright (C) 2017-2024 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 : 313327 : 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 : 2064 : virtual bool is_single_value_p ()
79 : : {
80 : 2064 : return false;
81 : : }
82 : :
83 : : /* Return range of a cluster. If value would overflow in type of LOW,
84 : : then return 0. */
85 : 13630894 : static unsigned HOST_WIDE_INT get_range (tree low, tree high)
86 : : {
87 : 13630894 : wide_int w = wi::to_wide (high) - wi::to_wide (low);
88 : 13630894 : if (wi::neg_p (w, TYPE_SIGN (TREE_TYPE (low))) || !wi::fits_uhwi_p (w))
89 : : return 0;
90 : 13623960 : return w.to_uhwi () + 1;
91 : 13630894 : }
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 : 20457 : cluster () {}
112 : : };
113 : :
114 : 292870 : cluster::cluster (tree case_label_expr, basic_block case_bb,
115 : 292870 : profile_probability prob, profile_probability subtree_prob):
116 : 292870 : m_case_label_expr (case_label_expr), m_case_bb (case_bb), m_prob (prob),
117 : 292870 : m_subtree_prob (subtree_prob),
118 : 292870 : 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 : 292870 : ~simple_cluster ()
135 : 292870 : {}
136 : :
137 : : cluster_type
138 : 374855 : get_type () final override
139 : : {
140 : 374855 : return SIMPLE_CASE;
141 : : }
142 : :
143 : : tree
144 : 14045115 : get_low () final override
145 : : {
146 : 204310 : return m_low;
147 : : }
148 : :
149 : : tree
150 : 13958338 : get_high () final override
151 : : {
152 : 397669 : return m_high;
153 : : }
154 : :
155 : 1175 : void set_high (tree high)
156 : : {
157 : 1175 : m_high = high;
158 : : }
159 : :
160 : : void
161 : 0 : debug () final override
162 : : {
163 : 0 : dump (stderr);
164 : 0 : }
165 : :
166 : : void
167 : 113 : dump (FILE *f, bool details ATTRIBUTE_UNUSED = false) final override
168 : : {
169 : 113 : PRINT_CASE (f, get_low ());
170 : 113 : if (get_low () != get_high ())
171 : : {
172 : 8 : fprintf (f, "-");
173 : 8 : PRINT_CASE (f, get_high ());
174 : : }
175 : 113 : fprintf (f, " ");
176 : 113 : }
177 : :
178 : 0 : void emit (tree, tree, tree, basic_block, location_t) final override
179 : : {
180 : 0 : gcc_unreachable ();
181 : : }
182 : :
183 : 72811 : bool is_single_value_p () final override
184 : : {
185 : 72811 : return tree_int_cst_equal (get_low (), get_high ());
186 : : }
187 : :
188 : : /* Return number of comparisons needed for the case. */
189 : : unsigned
190 : 17706673 : get_comparison_count ()
191 : : {
192 : 17706673 : 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 : 292870 : simple_cluster::simple_cluster (tree low, tree high, tree case_label_expr,
209 : : basic_block case_bb, profile_probability prob,
210 : 292870 : bool has_forward_bb):
211 : : cluster (case_label_expr, case_bb, prob, prob),
212 : 292870 : m_low (low), m_high (high), m_has_forward_bb (has_forward_bb)
213 : : {
214 : 292870 : m_range_p = m_high != NULL;
215 : 292870 : if (m_high == NULL)
216 : 205982 : m_high = m_low;
217 : 292870 : }
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 : 20945 : get_low () final override
233 : : {
234 : 20945 : return m_cases[0]->get_low ();
235 : : }
236 : :
237 : : tree
238 : 20945 : get_high () final override
239 : : {
240 : 41890 : 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 : 16411 : jump_table_cluster (vec<cluster *> &clusters, unsigned start, unsigned end)
265 : 16411 : : group_cluster (clusters, start, end)
266 : : {}
267 : :
268 : : cluster_type
269 : 32368 : get_type () final override
270 : : {
271 : 32368 : 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 : 4046 : bit_test_cluster (vec<cluster *> &clusters, unsigned start, unsigned end,
369 : : bool handles_entire_switch)
370 : 4046 : :group_cluster (clusters, start, end),
371 : 4046 : m_handles_entire_switch (handles_entire_switch)
372 : : {}
373 : :
374 : : cluster_type
375 : 11660 : get_type () final override
376 : : {
377 : 11660 : 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 : 65655 : static inline bool is_enabled (void)
444 : : {
445 : 65655 : 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 : 564067 : min_cluster_item (unsigned count, unsigned start, unsigned non_jt_cases):
463 : 694032 : 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 : 46032 : bool has_child ()
486 : : {
487 : 46032 : 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 : 90501 : case_tree_node::case_tree_node ():
505 : 90501 : m_left (NULL), m_right (NULL), m_parent (NULL), m_c (NULL)
506 : : {
507 : : }
508 : :
509 : : unsigned int
510 : 8910290 : jump_table_cluster::case_values_threshold (void)
511 : : {
512 : 8910290 : unsigned int threshold = param_case_values_threshold;
513 : :
514 : 8910290 : if (threshold == 0)
515 : 8909912 : threshold = targetm.case_values_threshold ();
516 : :
517 : 8910290 : return threshold;
518 : : }
519 : :
520 : : /* Return whether jump table expansion is allowed. */
521 : 2289849 : 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 : 2289849 : if (!targetm.have_casesi () && !targetm.have_tablejump ())
526 : : return false;
527 : 2289849 : 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 : 9942 : 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 : 42929 : switch_decision_tree (gswitch *swtch): m_switch (swtch), m_phi_mapping (),
565 : 42929 : m_case_bbs (), m_case_node_pool ("struct case_node pool"),
566 : 42929 : m_case_list (NULL)
567 : : {
568 : 42929 : }
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 : 101648 : switch_decision_tree::reset_out_edges_aux (gswitch *swtch)
907 : : {
908 : 101648 : basic_block bb = gimple_bb (swtch);
909 : 101648 : edge e;
910 : 101648 : edge_iterator ei;
911 : 696573 : FOR_EACH_EDGE (e, ei, bb->succs)
912 : 594925 : e->aux = (void *) 0;
913 : 101648 : }
914 : :
915 : : /* Release CLUSTERS vector and destruct all dynamically allocated items. */
916 : :
917 : : inline void
918 : 66217 : release_clusters (vec<cluster *> &clusters)
919 : : {
920 : 411244 : for (unsigned i = 0; i < clusters.length (); i++)
921 : 139405 : delete clusters[i];
922 : 66217 : clusters.release ();
923 : 66217 : }
924 : :
925 : : } // tree_switch_conversion namespace
926 : :
927 : : #endif // TREE_SWITCH_CONVERSION_H
|
