OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-switch-conversion.c] - Blame information for rev 729

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Switch Conversion converts variable initializations based on switch
2
   statements to initializations from a static array.
3
   Copyright (C) 2006, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
4
   Contributed by Martin Jambor <jamborm@suse.cz>
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it
9
under the terms of the GNU General Public License as published by the
10
Free Software Foundation; either version 3, or (at your option) any
11
later version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT
14
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not, write to the Free
20
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21
02110-1301, USA.  */
22
 
23
/*
24
     Switch initialization conversion
25
 
26
The following pass changes simple initializations of scalars in a switch
27
statement into initializations from a static array.  Obviously, the values must
28
be constant and known at compile time and a default branch must be
29
provided.  For example, the following code:
30
 
31
        int a,b;
32
 
33
        switch (argc)
34
        {
35
         case 1:
36
         case 2:
37
                a_1 = 8;
38
                b_1 = 6;
39
                break;
40
         case 3:
41
                a_2 = 9;
42
                b_2 = 5;
43
                break;
44
         case 12:
45
                a_3 = 10;
46
                b_3 = 4;
47
                break;
48
         default:
49
                a_4 = 16;
50
                b_4 = 1;
51
        }
52
        a_5 = PHI <a_1, a_2, a_3, a_4>
53
        b_5 = PHI <b_1, b_2, b_3, b_4>
54
 
55
 
56
is changed into:
57
 
58
        static const int = CSWTCH01[] = {6, 6, 5, 1, 1, 1, 1, 1, 1, 1, 1, 4};
59
        static const int = CSWTCH02[] = {8, 8, 9, 16, 16, 16, 16, 16, 16, 16,
60
                                 16, 16, 10};
61
 
62
        if (((unsigned) argc) - 1 < 11)
63
          {
64
            a_6 = CSWTCH02[argc - 1];
65
            b_6 = CSWTCH01[argc - 1];
66
          }
67
        else
68
          {
69
            a_7 = 16;
70
            b_7 = 1;
71
          }
72
          a_5 = PHI <a_6, a_7>
73
          b_b = PHI <b_6, b_7>
74
 
75
There are further constraints.  Specifically, the range of values across all
76
case labels must not be bigger than SWITCH_CONVERSION_BRANCH_RATIO (default
77
eight) times the number of the actual switch branches. */
78
 
79
#include "config.h"
80
#include "system.h"
81
#include "coretypes.h"
82
#include "tm.h"
83
#include "line-map.h"
84
#include "params.h"
85
#include "flags.h"
86
#include "tree.h"
87
#include "basic-block.h"
88
#include "tree-flow.h"
89
#include "tree-flow-inline.h"
90
#include "tree-ssa-operands.h"
91
#include "output.h"
92
#include "input.h"
93
#include "tree-pass.h"
94
#include "gimple-pretty-print.h"
95
#include "tree-dump.h"
96
#include "timevar.h"
97
#include "langhooks.h"
98
 
99
/* The main structure of the pass.  */
100
struct switch_conv_info
101
{
102
  /* The expression used to decide the switch branch.  (It is subsequently used
103
     as the index to the created array.) */
104
  tree index_expr;
105
 
106
  /* The following integer constants store the minimum value covered by the
107
     cases.  */
108
  tree range_min;
109
 
110
  /* The difference between the above two numbers, i.e. The size of the array
111
     that would have to be created by the transformation.  */
112
  tree range_size;
113
 
114
  /* Basic block that contains the actual SWITCH_EXPR.  */
115
  basic_block switch_bb;
116
 
117
  /* All branches of the switch statement must have a single successor stored in
118
     the following variable.  */
119
  basic_block final_bb;
120
 
121
  /* Number of phi nodes in the final bb (that we'll be replacing).  */
122
  int phi_count;
123
 
124
  /* Array of default values, in the same order as phi nodes.  */
125
  tree *default_values;
126
 
127
  /* Constructors of new static arrays.  */
128
  VEC (constructor_elt, gc) **constructors;
129
 
130
  /* Array of ssa names that are initialized with a value from a new static
131
     array.  */
132
  tree *target_inbound_names;
133
 
134
  /* Array of ssa names that are initialized with the default value if the
135
     switch expression is out of range.  */
136
  tree *target_outbound_names;
137
 
138
  /* The probability of the default edge in the replaced switch.  */
139
  int default_prob;
140
 
141
  /* The count of the default edge in the replaced switch.  */
142
  gcov_type default_count;
143
 
144
  /* Combined count of all other (non-default) edges in the replaced switch.  */
145
  gcov_type other_count;
146
 
147
  /* The first load statement that loads a temporary from a new static array.
148
   */
149
  gimple arr_ref_first;
150
 
151
  /* The last load statement that loads a temporary from a new static array.  */
152
  gimple arr_ref_last;
153
 
154
  /* String reason why the case wasn't a good candidate that is written to the
155
     dump file, if there is one.  */
156
  const char *reason;
157
 
158
  /* Parameters for expand_switch_using_bit_tests.  Should be computed
159
     the same way as in expand_case.  */
160
  unsigned int bit_test_uniq;
161
  unsigned int bit_test_count;
162
  basic_block bit_test_bb[2];
163
};
164
 
165
/* Global pass info.  */
166
static struct switch_conv_info info;
167
 
168
 
169
/* Checks whether the range given by individual case statements of the SWTCH
170
   switch statement isn't too big and whether the number of branches actually
171
   satisfies the size of the new array.  */
172
 
173
static bool
174
check_range (gimple swtch)
175
{
176
  tree min_case, max_case;
177
  unsigned int branch_num = gimple_switch_num_labels (swtch);
178
  tree range_max;
179
 
180
  /* The gimplifier has already sorted the cases by CASE_LOW and ensured there
181
     is a default label which is the first in the vector.  */
182
 
183
  min_case = gimple_switch_label (swtch, 1);
184
  info.range_min = CASE_LOW (min_case);
185
 
186
  gcc_assert (branch_num > 1);
187
  gcc_assert (CASE_LOW (gimple_switch_label (swtch, 0)) == NULL_TREE);
188
  max_case = gimple_switch_label (swtch, branch_num - 1);
189
  if (CASE_HIGH (max_case) != NULL_TREE)
190
    range_max = CASE_HIGH (max_case);
191
  else
192
    range_max = CASE_LOW (max_case);
193
 
194
  gcc_assert (info.range_min);
195
  gcc_assert (range_max);
196
 
197
  info.range_size = int_const_binop (MINUS_EXPR, range_max, info.range_min);
198
 
199
  gcc_assert (info.range_size);
200
  if (!host_integerp (info.range_size, 1))
201
    {
202
      info.reason = "index range way too large or otherwise unusable.\n";
203
      return false;
204
    }
205
 
206
  if ((unsigned HOST_WIDE_INT) tree_low_cst (info.range_size, 1)
207
      > ((unsigned) branch_num * SWITCH_CONVERSION_BRANCH_RATIO))
208
    {
209
      info.reason = "the maximum range-branch ratio exceeded.\n";
210
      return false;
211
    }
212
 
213
  return true;
214
}
215
 
216
/* Checks the given CS switch case whether it is suitable for conversion
217
   (whether all but the default basic blocks are empty and so on).  If it is,
218
   adds the case to the branch list along with values for the defined variables
219
   and returns true.  Otherwise returns false.  */
220
 
221
static bool
222
check_process_case (tree cs)
223
{
224
  tree ldecl;
225
  basic_block label_bb, following_bb;
226
  edge e;
227
 
228
  ldecl = CASE_LABEL (cs);
229
  label_bb = label_to_block (ldecl);
230
 
231
  e = find_edge (info.switch_bb, label_bb);
232
  gcc_assert (e);
233
 
234
  if (CASE_LOW (cs) == NULL_TREE)
235
    {
236
      /* Default branch.  */
237
      info.default_prob = e->probability;
238
      info.default_count = e->count;
239
    }
240
  else
241
    {
242
      int i;
243
      info.other_count += e->count;
244
      for (i = 0; i < 2; i++)
245
        if (info.bit_test_bb[i] == label_bb)
246
          break;
247
        else if (info.bit_test_bb[i] == NULL)
248
          {
249
            info.bit_test_bb[i] = label_bb;
250
            info.bit_test_uniq++;
251
            break;
252
          }
253
      if (i == 2)
254
        info.bit_test_uniq = 3;
255
      if (CASE_HIGH (cs) != NULL_TREE
256
          && ! tree_int_cst_equal (CASE_LOW (cs), CASE_HIGH (cs)))
257
        info.bit_test_count += 2;
258
      else
259
        info.bit_test_count++;
260
    }
261
 
262
  if (!label_bb)
263
    {
264
      info.reason = "  Bad case - cs BB  label is NULL\n";
265
      return false;
266
    }
267
 
268
  if (!single_pred_p (label_bb))
269
    {
270
      if (info.final_bb && info.final_bb != label_bb)
271
        {
272
          info.reason = "  Bad case - a non-final BB has two predecessors\n";
273
          return false; /* sth complex going on in this branch  */
274
        }
275
 
276
      following_bb = label_bb;
277
    }
278
  else
279
    {
280
      if (!empty_block_p (label_bb))
281
        {
282
          info.reason = "  Bad case - a non-final BB not empty\n";
283
          return false;
284
        }
285
 
286
      e = single_succ_edge (label_bb);
287
      following_bb = single_succ (label_bb);
288
    }
289
 
290
  if (!info.final_bb)
291
    info.final_bb = following_bb;
292
  else if (info.final_bb != following_bb)
293
    {
294
      info.reason = "  Bad case - different final BB\n";
295
      return false; /* the only successor is not common for all the branches */
296
    }
297
 
298
  return true;
299
}
300
 
301
/* This function checks whether all required values in phi nodes in final_bb
302
   are constants.  Required values are those that correspond to a basic block
303
   which is a part of the examined switch statement.  It returns true if the
304
   phi nodes are OK, otherwise false.  */
305
 
306
static bool
307
check_final_bb (void)
308
{
309
  gimple_stmt_iterator gsi;
310
 
311
  info.phi_count = 0;
312
  for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
313
    {
314
      gimple phi = gsi_stmt (gsi);
315
      unsigned int i;
316
 
317
      info.phi_count++;
318
 
319
      for (i = 0; i < gimple_phi_num_args (phi); i++)
320
        {
321
          basic_block bb = gimple_phi_arg_edge (phi, i)->src;
322
 
323
          if (bb == info.switch_bb
324
              || (single_pred_p (bb) && single_pred (bb) == info.switch_bb))
325
            {
326
              tree reloc, val;
327
 
328
              val = gimple_phi_arg_def (phi, i);
329
              if (!is_gimple_ip_invariant (val))
330
                {
331
                  info.reason = "   Non-invariant value from a case\n";
332
                  return false; /* Non-invariant argument.  */
333
                }
334
              reloc = initializer_constant_valid_p (val, TREE_TYPE (val));
335
              if ((flag_pic && reloc != null_pointer_node)
336
                  || (!flag_pic && reloc == NULL_TREE))
337
                {
338
                  if (reloc)
339
                    info.reason
340
                      = "   Value from a case would need runtime relocations\n";
341
                  else
342
                    info.reason
343
                      = "   Value from a case is not a valid initializer\n";
344
                  return false;
345
                }
346
            }
347
        }
348
    }
349
 
350
  return true;
351
}
352
 
353
/* The following function allocates default_values, target_{in,out}_names and
354
   constructors arrays.  The last one is also populated with pointers to
355
   vectors that will become constructors of new arrays.  */
356
 
357
static void
358
create_temp_arrays (void)
359
{
360
  int i;
361
 
362
  info.default_values = XCNEWVEC (tree, info.phi_count * 3);
363
  info.constructors = XCNEWVEC (VEC (constructor_elt, gc) *, info.phi_count);
364
  info.target_inbound_names = info.default_values + info.phi_count;
365
  info.target_outbound_names = info.target_inbound_names + info.phi_count;
366
  for (i = 0; i < info.phi_count; i++)
367
    info.constructors[i]
368
      = VEC_alloc (constructor_elt, gc, tree_low_cst (info.range_size, 1) + 1);
369
}
370
 
371
/* Free the arrays created by create_temp_arrays().  The vectors that are
372
   created by that function are not freed here, however, because they have
373
   already become constructors and must be preserved.  */
374
 
375
static void
376
free_temp_arrays (void)
377
{
378
  XDELETEVEC (info.constructors);
379
  XDELETEVEC (info.default_values);
380
}
381
 
382
/* Populate the array of default values in the order of phi nodes.
383
   DEFAULT_CASE is the CASE_LABEL_EXPR for the default switch branch.  */
384
 
385
static void
386
gather_default_values (tree default_case)
387
{
388
  gimple_stmt_iterator gsi;
389
  basic_block bb = label_to_block (CASE_LABEL (default_case));
390
  edge e;
391
  int i = 0;
392
 
393
  gcc_assert (CASE_LOW (default_case) == NULL_TREE);
394
 
395
  if (bb == info.final_bb)
396
    e = find_edge (info.switch_bb, bb);
397
  else
398
    e = single_succ_edge (bb);
399
 
400
  for (gsi = gsi_start_phis (info.final_bb); !gsi_end_p (gsi); gsi_next (&gsi))
401
    {
402
      gimple phi = gsi_stmt (gsi);
403
      tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
404
      gcc_assert (val);
405
      info.default_values[i++] = val;
406
    }
407
}
408
 
409
/* The following function populates the vectors in the constructors array with
410
   future contents of the static arrays.  The vectors are populated in the
411
   order of phi nodes.  SWTCH is the switch statement being converted.  */
412
 
413
static void
414
build_constructors (gimple swtch)
415
{
416
  unsigned i, branch_num = gimple_switch_num_labels (swtch);
417
  tree pos = info.range_min;
418
 
419
  for (i = 1; i < branch_num; i++)
420
    {
421
      tree cs = gimple_switch_label (swtch, i);
422
      basic_block bb = label_to_block (CASE_LABEL (cs));
423
      edge e;
424
      tree high;
425
      gimple_stmt_iterator gsi;
426
      int j;
427
 
428
      if (bb == info.final_bb)
429
        e = find_edge (info.switch_bb, bb);
430
      else
431
        e = single_succ_edge (bb);
432
      gcc_assert (e);
433
 
434
      while (tree_int_cst_lt (pos, CASE_LOW (cs)))
435
        {
436
          int k;
437
          for (k = 0; k < info.phi_count; k++)
438
            {
439
              constructor_elt *elt;
440
 
441
              elt = VEC_quick_push (constructor_elt,
442
                                    info.constructors[k], NULL);
443
              elt->index = int_const_binop (MINUS_EXPR, pos,
444
                                            info.range_min);
445
              elt->value = info.default_values[k];
446
            }
447
 
448
          pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
449
        }
450
      gcc_assert (tree_int_cst_equal (pos, CASE_LOW (cs)));
451
 
452
      j = 0;
453
      if (CASE_HIGH (cs))
454
        high = CASE_HIGH (cs);
455
      else
456
        high = CASE_LOW (cs);
457
      for (gsi = gsi_start_phis (info.final_bb);
458
           !gsi_end_p (gsi); gsi_next (&gsi))
459
        {
460
          gimple phi = gsi_stmt (gsi);
461
          tree val = PHI_ARG_DEF_FROM_EDGE (phi, e);
462
          tree low = CASE_LOW (cs);
463
          pos = CASE_LOW (cs);
464
 
465
          do
466
            {
467
              constructor_elt *elt;
468
 
469
              elt = VEC_quick_push (constructor_elt,
470
                                    info.constructors[j], NULL);
471
              elt->index = int_const_binop (MINUS_EXPR, pos, info.range_min);
472
              elt->value = val;
473
 
474
              pos = int_const_binop (PLUS_EXPR, pos, integer_one_node);
475
            } while (!tree_int_cst_lt (high, pos)
476
                     && tree_int_cst_lt (low, pos));
477
          j++;
478
        }
479
    }
480
}
481
 
482
/* If all values in the constructor vector are the same, return the value.
483
   Otherwise return NULL_TREE.  Not supposed to be called for empty
484
   vectors.  */
485
 
486
static tree
487
constructor_contains_same_values_p (VEC (constructor_elt, gc) *vec)
488
{
489
  unsigned int i;
490
  tree prev = NULL_TREE;
491
  constructor_elt *elt;
492
 
493
  FOR_EACH_VEC_ELT (constructor_elt, vec, i, elt)
494
    {
495
      if (!prev)
496
        prev = elt->value;
497
      else if (!operand_equal_p (elt->value, prev, OEP_ONLY_CONST))
498
        return NULL_TREE;
499
    }
500
  return prev;
501
}
502
 
503
/* Return type which should be used for array elements, either TYPE,
504
   or for integral type some smaller integral type that can still hold
505
   all the constants.  */
506
 
507
static tree
508
array_value_type (gimple swtch, tree type, int num)
509
{
510
  unsigned int i, len = VEC_length (constructor_elt, info.constructors[num]);
511
  constructor_elt *elt;
512
  enum machine_mode mode;
513
  int sign = 0;
514
  tree smaller_type;
515
 
516
  if (!INTEGRAL_TYPE_P (type))
517
    return type;
518
 
519
  mode = GET_CLASS_NARROWEST_MODE (GET_MODE_CLASS (TYPE_MODE (type)));
520
  if (GET_MODE_SIZE (TYPE_MODE (type)) <= GET_MODE_SIZE (mode))
521
    return type;
522
 
523
  if (len < (optimize_bb_for_size_p (gimple_bb (swtch)) ? 2 : 32))
524
    return type;
525
 
526
  FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt)
527
    {
528
      double_int cst;
529
 
530
      if (TREE_CODE (elt->value) != INTEGER_CST)
531
        return type;
532
 
533
      cst = TREE_INT_CST (elt->value);
534
      while (1)
535
        {
536
          unsigned int prec = GET_MODE_BITSIZE (mode);
537
          if (prec > HOST_BITS_PER_WIDE_INT)
538
            return type;
539
 
540
          if (sign >= 0
541
              && double_int_equal_p (cst, double_int_zext (cst, prec)))
542
            {
543
              if (sign == 0
544
                  && double_int_equal_p (cst, double_int_sext (cst, prec)))
545
                break;
546
              sign = 1;
547
              break;
548
            }
549
          if (sign <= 0
550
              && double_int_equal_p (cst, double_int_sext (cst, prec)))
551
            {
552
              sign = -1;
553
              break;
554
            }
555
 
556
          if (sign == 1)
557
            sign = 0;
558
 
559
          mode = GET_MODE_WIDER_MODE (mode);
560
          if (mode == VOIDmode
561
              || GET_MODE_SIZE (mode) >= GET_MODE_SIZE (TYPE_MODE (type)))
562
            return type;
563
        }
564
    }
565
 
566
  if (sign == 0)
567
    sign = TYPE_UNSIGNED (type) ? 1 : -1;
568
  smaller_type = lang_hooks.types.type_for_mode (mode, sign >= 0);
569
  if (GET_MODE_SIZE (TYPE_MODE (type))
570
      <= GET_MODE_SIZE (TYPE_MODE (smaller_type)))
571
    return type;
572
 
573
  return smaller_type;
574
}
575
 
576
/* Create an appropriate array type and declaration and assemble a static array
577
   variable.  Also create a load statement that initializes the variable in
578
   question with a value from the static array.  SWTCH is the switch statement
579
   being converted, NUM is the index to arrays of constructors, default values
580
   and target SSA names for this particular array.  ARR_INDEX_TYPE is the type
581
   of the index of the new array, PHI is the phi node of the final BB that
582
   corresponds to the value that will be loaded from the created array.  TIDX
583
   is an ssa name of a temporary variable holding the index for loads from the
584
   new array.  */
585
 
586
static void
587
build_one_array (gimple swtch, int num, tree arr_index_type, gimple phi,
588
                 tree tidx)
589
{
590
  tree name, cst;
591
  gimple load;
592
  gimple_stmt_iterator gsi = gsi_for_stmt (swtch);
593
  location_t loc = gimple_location (swtch);
594
 
595
  gcc_assert (info.default_values[num]);
596
 
597
  name = make_ssa_name (SSA_NAME_VAR (PHI_RESULT (phi)), NULL);
598
  info.target_inbound_names[num] = name;
599
 
600
  cst = constructor_contains_same_values_p (info.constructors[num]);
601
  if (cst)
602
    load = gimple_build_assign (name, cst);
603
  else
604
    {
605
      tree array_type, ctor, decl, value_type, fetch, default_type;
606
 
607
      default_type = TREE_TYPE (info.default_values[num]);
608
      value_type = array_value_type (swtch, default_type, num);
609
      array_type = build_array_type (value_type, arr_index_type);
610
      if (default_type != value_type)
611
        {
612
          unsigned int i;
613
          constructor_elt *elt;
614
 
615
          FOR_EACH_VEC_ELT (constructor_elt, info.constructors[num], i, elt)
616
            elt->value = fold_convert (value_type, elt->value);
617
        }
618
      ctor = build_constructor (array_type, info.constructors[num]);
619
      TREE_CONSTANT (ctor) = true;
620
      TREE_STATIC (ctor) = true;
621
 
622
      decl = build_decl (loc, VAR_DECL, NULL_TREE, array_type);
623
      TREE_STATIC (decl) = 1;
624
      DECL_INITIAL (decl) = ctor;
625
 
626
      DECL_NAME (decl) = create_tmp_var_name ("CSWTCH");
627
      DECL_ARTIFICIAL (decl) = 1;
628
      TREE_CONSTANT (decl) = 1;
629
      TREE_READONLY (decl) = 1;
630
      add_referenced_var (decl);
631
      varpool_mark_needed_node (varpool_node (decl));
632
      varpool_finalize_decl (decl);
633
 
634
      fetch = build4 (ARRAY_REF, value_type, decl, tidx, NULL_TREE,
635
                      NULL_TREE);
636
      if (default_type != value_type)
637
        {
638
          fetch = fold_convert (default_type, fetch);
639
          fetch = force_gimple_operand_gsi (&gsi, fetch, true, NULL_TREE,
640
                                            true, GSI_SAME_STMT);
641
        }
642
      load = gimple_build_assign (name, fetch);
643
    }
644
 
645
  SSA_NAME_DEF_STMT (name) = load;
646
  gsi_insert_before (&gsi, load, GSI_SAME_STMT);
647
  update_stmt (load);
648
  info.arr_ref_last = load;
649
}
650
 
651
/* Builds and initializes static arrays initialized with values gathered from
652
   the SWTCH switch statement.  Also creates statements that load values from
653
   them.  */
654
 
655
static void
656
build_arrays (gimple swtch)
657
{
658
  tree arr_index_type;
659
  tree tidx, sub, tmp, utype;
660
  gimple stmt;
661
  gimple_stmt_iterator gsi;
662
  int i;
663
  location_t loc = gimple_location (swtch);
664
 
665
  gsi = gsi_for_stmt (swtch);
666
 
667
  /* Make sure we do not generate arithmetics in a subrange.  */
668
  utype = TREE_TYPE (info.index_expr);
669
  if (TREE_TYPE (utype))
670
    utype = lang_hooks.types.type_for_mode (TYPE_MODE (TREE_TYPE (utype)), 1);
671
  else
672
    utype = lang_hooks.types.type_for_mode (TYPE_MODE (utype), 1);
673
 
674
  arr_index_type = build_index_type (info.range_size);
675
  tmp = create_tmp_var (utype, "csui");
676
  add_referenced_var (tmp);
677
  tidx = make_ssa_name (tmp, NULL);
678
  sub = fold_build2_loc (loc, MINUS_EXPR, utype,
679
                         fold_convert_loc (loc, utype, info.index_expr),
680
                         fold_convert_loc (loc, utype, info.range_min));
681
  sub = force_gimple_operand_gsi (&gsi, sub,
682
                                  false, NULL, true, GSI_SAME_STMT);
683
  stmt = gimple_build_assign (tidx, sub);
684
  SSA_NAME_DEF_STMT (tidx) = stmt;
685
 
686
  gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
687
  update_stmt (stmt);
688
  info.arr_ref_first = stmt;
689
 
690
  for (gsi = gsi_start_phis (info.final_bb), i = 0;
691
       !gsi_end_p (gsi); gsi_next (&gsi), i++)
692
    build_one_array (swtch, i, arr_index_type, gsi_stmt (gsi), tidx);
693
}
694
 
695
/* Generates and appropriately inserts loads of default values at the position
696
   given by BSI.  Returns the last inserted statement.  */
697
 
698
static gimple
699
gen_def_assigns (gimple_stmt_iterator *gsi)
700
{
701
  int i;
702
  gimple assign = NULL;
703
 
704
  for (i = 0; i < info.phi_count; i++)
705
    {
706
      tree name
707
        = make_ssa_name (SSA_NAME_VAR (info.target_inbound_names[i]), NULL);
708
 
709
      info.target_outbound_names[i] = name;
710
      assign = gimple_build_assign (name, info.default_values[i]);
711
      SSA_NAME_DEF_STMT (name) = assign;
712
      gsi_insert_before (gsi, assign, GSI_SAME_STMT);
713
      update_stmt (assign);
714
    }
715
  return assign;
716
}
717
 
718
/* Deletes the unused bbs and edges that now contain the switch statement and
719
   its empty branch bbs.  BBD is the now dead BB containing the original switch
720
   statement, FINAL is the last BB of the converted switch statement (in terms
721
   of succession).  */
722
 
723
static void
724
prune_bbs (basic_block bbd, basic_block final)
725
{
726
  edge_iterator ei;
727
  edge e;
728
 
729
  for (ei = ei_start (bbd->succs); (e = ei_safe_edge (ei)); )
730
    {
731
      basic_block bb;
732
      bb = e->dest;
733
      remove_edge (e);
734
      if (bb != final)
735
        delete_basic_block (bb);
736
    }
737
  delete_basic_block (bbd);
738
}
739
 
740
/* Add values to phi nodes in final_bb for the two new edges.  E1F is the edge
741
   from the basic block loading values from an array and E2F from the basic
742
   block loading default values.  BBF is the last switch basic block (see the
743
   bbf description in the comment below).  */
744
 
745
static void
746
fix_phi_nodes (edge e1f, edge e2f, basic_block bbf)
747
{
748
  gimple_stmt_iterator gsi;
749
  int i;
750
 
751
  for (gsi = gsi_start_phis (bbf), i = 0;
752
       !gsi_end_p (gsi); gsi_next (&gsi), i++)
753
    {
754
      gimple phi = gsi_stmt (gsi);
755
      add_phi_arg (phi, info.target_inbound_names[i], e1f, UNKNOWN_LOCATION);
756
      add_phi_arg (phi, info.target_outbound_names[i], e2f, UNKNOWN_LOCATION);
757
    }
758
 
759
}
760
 
761
/* Creates a check whether the switch expression value actually falls into the
762
   range given by all the cases.  If it does not, the temporaries are loaded
763
   with default values instead.  SWTCH is the switch statement being converted.
764
 
765
   bb0 is the bb with the switch statement, however, we'll end it with a
766
       condition instead.
767
 
768
   bb1 is the bb to be used when the range check went ok.  It is derived from
769
       the switch BB
770
 
771
   bb2 is the bb taken when the expression evaluated outside of the range
772
       covered by the created arrays.  It is populated by loads of default
773
       values.
774
 
775
   bbF is a fall through for both bb1 and bb2 and contains exactly what
776
       originally followed the switch statement.
777
 
778
   bbD contains the switch statement (in the end).  It is unreachable but we
779
       still need to strip off its edges.
780
*/
781
 
782
static void
783
gen_inbound_check (gimple swtch)
784
{
785
  tree label_decl1 = create_artificial_label (UNKNOWN_LOCATION);
786
  tree label_decl2 = create_artificial_label (UNKNOWN_LOCATION);
787
  tree label_decl3 = create_artificial_label (UNKNOWN_LOCATION);
788
  gimple label1, label2, label3;
789
  tree utype, tidx;
790
  tree bound;
791
 
792
  gimple cond_stmt;
793
 
794
  gimple last_assign;
795
  gimple_stmt_iterator gsi;
796
  basic_block bb0, bb1, bb2, bbf, bbd;
797
  edge e01, e02, e21, e1d, e1f, e2f;
798
  location_t loc = gimple_location (swtch);
799
 
800
  gcc_assert (info.default_values);
801
  bb0 = gimple_bb (swtch);
802
 
803
  tidx = gimple_assign_lhs (info.arr_ref_first);
804
  utype = TREE_TYPE (tidx);
805
 
806
  /* (end of) block 0 */
807
  gsi = gsi_for_stmt (info.arr_ref_first);
808
  gsi_next (&gsi);
809
 
810
  bound = fold_convert_loc (loc, utype, info.range_size);
811
  cond_stmt = gimple_build_cond (LE_EXPR, tidx, bound, NULL_TREE, NULL_TREE);
812
  gsi_insert_before (&gsi, cond_stmt, GSI_SAME_STMT);
813
  update_stmt (cond_stmt);
814
 
815
  /* block 2 */
816
  label2 = gimple_build_label (label_decl2);
817
  gsi_insert_before (&gsi, label2, GSI_SAME_STMT);
818
  last_assign = gen_def_assigns (&gsi);
819
 
820
  /* block 1 */
821
  label1 = gimple_build_label (label_decl1);
822
  gsi_insert_before (&gsi, label1, GSI_SAME_STMT);
823
 
824
  /* block F */
825
  gsi = gsi_start_bb (info.final_bb);
826
  label3 = gimple_build_label (label_decl3);
827
  gsi_insert_before (&gsi, label3, GSI_SAME_STMT);
828
 
829
  /* cfg fix */
830
  e02 = split_block (bb0, cond_stmt);
831
  bb2 = e02->dest;
832
 
833
  e21 = split_block (bb2, last_assign);
834
  bb1 = e21->dest;
835
  remove_edge (e21);
836
 
837
  e1d = split_block (bb1, info.arr_ref_last);
838
  bbd = e1d->dest;
839
  remove_edge (e1d);
840
 
841
  /* flags and profiles of the edge for in-range values */
842
  e01 = make_edge (bb0, bb1, EDGE_TRUE_VALUE);
843
  e01->probability = REG_BR_PROB_BASE - info.default_prob;
844
  e01->count = info.other_count;
845
 
846
  /* flags and profiles of the edge taking care of out-of-range values */
847
  e02->flags &= ~EDGE_FALLTHRU;
848
  e02->flags |= EDGE_FALSE_VALUE;
849
  e02->probability = info.default_prob;
850
  e02->count = info.default_count;
851
 
852
  bbf = info.final_bb;
853
 
854
  e1f = make_edge (bb1, bbf, EDGE_FALLTHRU);
855
  e1f->probability = REG_BR_PROB_BASE;
856
  e1f->count = info.other_count;
857
 
858
  e2f = make_edge (bb2, bbf, EDGE_FALLTHRU);
859
  e2f->probability = REG_BR_PROB_BASE;
860
  e2f->count = info.default_count;
861
 
862
  /* frequencies of the new BBs */
863
  bb1->frequency = EDGE_FREQUENCY (e01);
864
  bb2->frequency = EDGE_FREQUENCY (e02);
865
  bbf->frequency = EDGE_FREQUENCY (e1f) + EDGE_FREQUENCY (e2f);
866
 
867
  prune_bbs (bbd, info.final_bb); /* To keep calc_dfs_tree() in dominance.c
868
                                     happy.  */
869
 
870
  fix_phi_nodes (e1f, e2f, bbf);
871
 
872
  free_dominance_info (CDI_DOMINATORS);
873
  free_dominance_info (CDI_POST_DOMINATORS);
874
}
875
 
876
/* The following function is invoked on every switch statement (the current one
877
   is given in SWTCH) and runs the individual phases of switch conversion on it
878
   one after another until one fails or the conversion is completed.  */
879
 
880
static bool
881
process_switch (gimple swtch)
882
{
883
  unsigned int i, branch_num = gimple_switch_num_labels (swtch);
884
  tree index_type;
885
 
886
  /* Operand 2 is either NULL_TREE or a vector of cases (stmt.c).  */
887
  if (branch_num < 2)
888
    {
889
      info.reason = "switch has no labels\n";
890
      return false;
891
    }
892
 
893
  info.final_bb = NULL;
894
  info.switch_bb = gimple_bb (swtch);
895
  info.index_expr = gimple_switch_index (swtch);
896
  index_type = TREE_TYPE (info.index_expr);
897
  info.arr_ref_first = NULL;
898
  info.arr_ref_last = NULL;
899
  info.default_prob = 0;
900
  info.default_count = 0;
901
  info.other_count = 0;
902
  info.bit_test_uniq = 0;
903
  info.bit_test_count = 0;
904
  info.bit_test_bb[0] = NULL;
905
  info.bit_test_bb[1] = NULL;
906
 
907
  /* An ERROR_MARK occurs for various reasons including invalid data type.
908
     (comment from stmt.c) */
909
  if (index_type == error_mark_node)
910
    {
911
      info.reason = "index error.\n";
912
      return false;
913
    }
914
 
915
  /* Check the case label values are within reasonable range:  */
916
  if (!check_range (swtch))
917
    return false;
918
 
919
  /* For all the cases, see whether they are empty, the assignments they
920
     represent constant and so on...  */
921
  for (i = 0; i < branch_num; i++)
922
    if (!check_process_case (gimple_switch_label (swtch, i)))
923
      {
924
        if (dump_file)
925
          fprintf (dump_file, "Processing of case %i failed\n", i);
926
        return false;
927
      }
928
 
929
  if (info.bit_test_uniq <= 2)
930
    {
931
      rtl_profile_for_bb (gimple_bb (swtch));
932
      if (expand_switch_using_bit_tests_p (gimple_switch_index (swtch),
933
                                           info.range_size, info.bit_test_uniq,
934
                                           info.bit_test_count))
935
        {
936
          info.reason = "  Expanding as bit test is preferable\n";
937
          return false;
938
        }
939
    }
940
 
941
  if (!check_final_bb ())
942
    return false;
943
 
944
  /* At this point all checks have passed and we can proceed with the
945
     transformation.  */
946
 
947
  create_temp_arrays ();
948
  gather_default_values (gimple_switch_label (swtch, 0));
949
  build_constructors (swtch);
950
 
951
  build_arrays (swtch); /* Build the static arrays and assignments.   */
952
  gen_inbound_check (swtch);    /* Build the bounds check.  */
953
 
954
  /* Cleanup:  */
955
  free_temp_arrays ();
956
  return true;
957
}
958
 
959
/* The main function of the pass scans statements for switches and invokes
960
   process_switch on them.  */
961
 
962
static unsigned int
963
do_switchconv (void)
964
{
965
  basic_block bb;
966
 
967
  FOR_EACH_BB (bb)
968
  {
969
    gimple stmt = last_stmt (bb);
970
    if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
971
      {
972
        if (dump_file)
973
          {
974
            expanded_location loc = expand_location (gimple_location (stmt));
975
 
976
            fprintf (dump_file, "beginning to process the following "
977
                     "SWITCH statement (%s:%d) : ------- \n",
978
                     loc.file, loc.line);
979
            print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
980
            putc ('\n', dump_file);
981
          }
982
 
983
        info.reason = NULL;
984
        if (process_switch (stmt))
985
          {
986
            if (dump_file)
987
              {
988
                fputs ("Switch converted\n", dump_file);
989
                fputs ("--------------------------------\n", dump_file);
990
              }
991
          }
992
        else
993
          {
994
            if (dump_file)
995
              {
996
                gcc_assert (info.reason);
997
                fputs ("Bailing out - ", dump_file);
998
                fputs (info.reason, dump_file);
999
                fputs ("--------------------------------\n", dump_file);
1000
              }
1001
          }
1002
      }
1003
  }
1004
 
1005
  return 0;
1006
}
1007
 
1008
/* The pass gate. */
1009
 
1010
static bool
1011
switchconv_gate (void)
1012
{
1013
  return flag_tree_switch_conversion != 0;
1014
}
1015
 
1016
struct gimple_opt_pass pass_convert_switch =
1017
{
1018
 {
1019
  GIMPLE_PASS,
1020
  "switchconv",                         /* name */
1021
  switchconv_gate,                      /* gate */
1022
  do_switchconv,                        /* execute */
1023
  NULL,                                 /* sub */
1024
  NULL,                                 /* next */
1025
  0,                                     /* static_pass_number */
1026
  TV_TREE_SWITCH_CONVERSION,            /* tv_id */
1027
  PROP_cfg | PROP_ssa,                  /* properties_required */
1028
  0,                                     /* properties_provided */
1029
  0,                                     /* properties_destroyed */
1030
  0,                                     /* todo_flags_start */
1031
  TODO_update_ssa
1032
  | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
1033
 }
1034
};

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.