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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [tree-switch-conversion.c] - Blame information for rev 280

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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