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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-outof-ssa.c] - Blame information for rev 720

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

Line No. Rev Author Line
1 684 jeremybenn
/* Convert a program in SSA form into Normal form.
2
   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
3
   Free Software Foundation, Inc.
4
   Contributed by Andrew Macleod <amacleod@redhat.com>
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify
9
it under the terms of the GNU General Public License as published by
10
the Free Software Foundation; either version 3, or (at your option)
11
any later version.
12
 
13
GCC is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
GNU General Public License 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 see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
#include "config.h"
23
#include "system.h"
24
#include "coretypes.h"
25
#include "tm.h"
26
#include "tree.h"
27
#include "ggc.h"
28
#include "basic-block.h"
29
#include "tree-pretty-print.h"
30
#include "gimple-pretty-print.h"
31
#include "bitmap.h"
32
#include "tree-flow.h"
33
#include "timevar.h"
34
#include "tree-dump.h"
35
#include "tree-pass.h"
36
#include "diagnostic-core.h"
37
#include "ssaexpand.h"
38
 
39
/* FIXME: A lot of code here deals with expanding to RTL.  All that code
40
   should be in cfgexpand.c.  */
41
#include "expr.h"
42
 
43
 
44
DEF_VEC_I(source_location);
45
DEF_VEC_ALLOC_I(source_location,heap);
46
 
47
/* Used to hold all the components required to do SSA PHI elimination.
48
   The node and pred/succ list is a simple linear list of nodes and
49
   edges represented as pairs of nodes.
50
 
51
   The predecessor and successor list:  Nodes are entered in pairs, where
52
   [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
53
   predecessors, all the odd elements are successors.
54
 
55
   Rationale:
56
   When implemented as bitmaps, very large programs SSA->Normal times were
57
   being dominated by clearing the interference graph.
58
 
59
   Typically this list of edges is extremely small since it only includes
60
   PHI results and uses from a single edge which have not coalesced with
61
   each other.  This means that no virtual PHI nodes are included, and
62
   empirical evidence suggests that the number of edges rarely exceed
63
   3, and in a bootstrap of GCC, the maximum size encountered was 7.
64
   This also limits the number of possible nodes that are involved to
65
   rarely more than 6, and in the bootstrap of gcc, the maximum number
66
   of nodes encountered was 12.  */
67
 
68
typedef struct _elim_graph {
69
  /* Size of the elimination vectors.  */
70
  int size;
71
 
72
  /* List of nodes in the elimination graph.  */
73
  VEC(int,heap) *nodes;
74
 
75
  /*  The predecessor and successor edge list.  */
76
  VEC(int,heap) *edge_list;
77
 
78
  /* Source locus on each edge */
79
  VEC(source_location,heap) *edge_locus;
80
 
81
  /* Visited vector.  */
82
  sbitmap visited;
83
 
84
  /* Stack for visited nodes.  */
85
  VEC(int,heap) *stack;
86
 
87
  /* The variable partition map.  */
88
  var_map map;
89
 
90
  /* Edge being eliminated by this graph.  */
91
  edge e;
92
 
93
  /* List of constant copies to emit.  These are pushed on in pairs.  */
94
  VEC(int,heap) *const_dests;
95
  VEC(tree,heap) *const_copies;
96
 
97
  /* Source locations for any constant copies.  */
98
  VEC(source_location,heap) *copy_locus;
99
} *elim_graph;
100
 
101
 
102
/* For an edge E find out a good source location to associate with
103
   instructions inserted on edge E.  If E has an implicit goto set,
104
   use its location.  Otherwise search instructions in predecessors
105
   of E for a location, and use that one.  That makes sense because
106
   we insert on edges for PHI nodes, and effects of PHIs happen on
107
   the end of the predecessor conceptually.  */
108
 
109
static void
110
set_location_for_edge (edge e)
111
{
112
  if (e->goto_locus)
113
    {
114
      set_curr_insn_source_location (e->goto_locus);
115
      set_curr_insn_block (e->goto_block);
116
    }
117
  else
118
    {
119
      basic_block bb = e->src;
120
      gimple_stmt_iterator gsi;
121
 
122
      do
123
        {
124
          for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
125
            {
126
              gimple stmt = gsi_stmt (gsi);
127
              if (is_gimple_debug (stmt))
128
                continue;
129
              if (gimple_has_location (stmt) || gimple_block (stmt))
130
                {
131
                  set_curr_insn_source_location (gimple_location (stmt));
132
                  set_curr_insn_block (gimple_block (stmt));
133
                  return;
134
                }
135
            }
136
          /* Nothing found in this basic block.  Make a half-assed attempt
137
             to continue with another block.  */
138
          if (single_pred_p (bb))
139
            bb = single_pred (bb);
140
          else
141
            bb = e->src;
142
        }
143
      while (bb != e->src);
144
    }
145
}
146
 
147
/* Emit insns to copy SRC into DEST converting SRC if necessary.  As
148
   SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
149
   which we deduce the size to copy in that case.  */
150
 
151
static inline rtx
152
emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
153
{
154
  rtx seq;
155
 
156
  start_sequence ();
157
 
158
  if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
159
    src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
160
  if (GET_MODE (src) == BLKmode)
161
    {
162
      gcc_assert (GET_MODE (dest) == BLKmode);
163
      emit_block_move (dest, src, expr_size (sizeexp), BLOCK_OP_NORMAL);
164
    }
165
  else
166
    emit_move_insn (dest, src);
167
 
168
  seq = get_insns ();
169
  end_sequence ();
170
 
171
  return seq;
172
}
173
 
174
/* Insert a copy instruction from partition SRC to DEST onto edge E.  */
175
 
176
static void
177
insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus)
178
{
179
  tree var;
180
  rtx seq;
181
  if (dump_file && (dump_flags & TDF_DETAILS))
182
    {
183
      fprintf (dump_file,
184
               "Inserting a partition copy on edge BB%d->BB%d :"
185
               "PART.%d = PART.%d",
186
               e->src->index,
187
               e->dest->index, dest, src);
188
      fprintf (dump_file, "\n");
189
    }
190
 
191
  gcc_assert (SA.partition_to_pseudo[dest]);
192
  gcc_assert (SA.partition_to_pseudo[src]);
193
 
194
  set_location_for_edge (e);
195
  /* If a locus is provided, override the default.  */
196
  if (locus)
197
    set_curr_insn_source_location (locus);
198
 
199
  var = partition_to_var (SA.map, src);
200
  seq = emit_partition_copy (SA.partition_to_pseudo[dest],
201
                             SA.partition_to_pseudo[src],
202
                             TYPE_UNSIGNED (TREE_TYPE (var)),
203
                             var);
204
 
205
  insert_insn_on_edge (seq, e);
206
}
207
 
208
/* Insert a copy instruction from expression SRC to partition DEST
209
   onto edge E.  */
210
 
211
static void
212
insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus)
213
{
214
  rtx seq, x;
215
  enum machine_mode dest_mode, src_mode;
216
  int unsignedp;
217
  tree var;
218
 
219
  if (dump_file && (dump_flags & TDF_DETAILS))
220
    {
221
      fprintf (dump_file,
222
               "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
223
               e->src->index,
224
               e->dest->index, dest);
225
      print_generic_expr (dump_file, src, TDF_SLIM);
226
      fprintf (dump_file, "\n");
227
    }
228
 
229
  gcc_assert (SA.partition_to_pseudo[dest]);
230
 
231
  set_location_for_edge (e);
232
  /* If a locus is provided, override the default.  */
233
  if (locus)
234
    set_curr_insn_source_location (locus);
235
 
236
  start_sequence ();
237
 
238
  var = SSA_NAME_VAR (partition_to_var (SA.map, dest));
239
  src_mode = TYPE_MODE (TREE_TYPE (src));
240
  dest_mode = GET_MODE (SA.partition_to_pseudo[dest]);
241
  gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (var)));
242
  gcc_assert (!REG_P (SA.partition_to_pseudo[dest])
243
              || dest_mode == promote_decl_mode (var, &unsignedp));
244
 
245
  if (src_mode != dest_mode)
246
    {
247
      x = expand_expr (src, NULL, src_mode, EXPAND_NORMAL);
248
      x = convert_modes (dest_mode, src_mode, x, unsignedp);
249
    }
250
  else if (src_mode == BLKmode)
251
    {
252
      x = SA.partition_to_pseudo[dest];
253
      store_expr (src, x, 0, false);
254
    }
255
  else
256
    x = expand_expr (src, SA.partition_to_pseudo[dest],
257
                     dest_mode, EXPAND_NORMAL);
258
 
259
  if (x != SA.partition_to_pseudo[dest])
260
    emit_move_insn (SA.partition_to_pseudo[dest], x);
261
  seq = get_insns ();
262
  end_sequence ();
263
 
264
  insert_insn_on_edge (seq, e);
265
}
266
 
267
/* Insert a copy instruction from RTL expression SRC to partition DEST
268
   onto edge E.  */
269
 
270
static void
271
insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
272
                            source_location locus)
273
{
274
  rtx seq;
275
  if (dump_file && (dump_flags & TDF_DETAILS))
276
    {
277
      fprintf (dump_file,
278
               "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
279
               e->src->index,
280
               e->dest->index, dest);
281
      print_simple_rtl (dump_file, src);
282
      fprintf (dump_file, "\n");
283
    }
284
 
285
  gcc_assert (SA.partition_to_pseudo[dest]);
286
 
287
  set_location_for_edge (e);
288
  /* If a locus is provided, override the default.  */
289
  if (locus)
290
    set_curr_insn_source_location (locus);
291
 
292
  /* We give the destination as sizeexp in case src/dest are BLKmode
293
     mems.  Usually we give the source.  As we result from SSA names
294
     the left and right size should be the same (and no WITH_SIZE_EXPR
295
     involved), so it doesn't matter.  */
296
  seq = emit_partition_copy (SA.partition_to_pseudo[dest],
297
                             src, unsignedsrcp,
298
                             partition_to_var (SA.map, dest));
299
 
300
  insert_insn_on_edge (seq, e);
301
}
302
 
303
/* Insert a copy instruction from partition SRC to RTL lvalue DEST
304
   onto edge E.  */
305
 
306
static void
307
insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus)
308
{
309
  tree var;
310
  rtx seq;
311
  if (dump_file && (dump_flags & TDF_DETAILS))
312
    {
313
      fprintf (dump_file,
314
               "Inserting a temp copy on edge BB%d->BB%d : ",
315
               e->src->index,
316
               e->dest->index);
317
      print_simple_rtl (dump_file, dest);
318
      fprintf (dump_file, "= PART.%d\n", src);
319
    }
320
 
321
  gcc_assert (SA.partition_to_pseudo[src]);
322
 
323
  set_location_for_edge (e);
324
  /* If a locus is provided, override the default.  */
325
  if (locus)
326
    set_curr_insn_source_location (locus);
327
 
328
  var = partition_to_var (SA.map, src);
329
  seq = emit_partition_copy (dest,
330
                             SA.partition_to_pseudo[src],
331
                             TYPE_UNSIGNED (TREE_TYPE (var)),
332
                             var);
333
 
334
  insert_insn_on_edge (seq, e);
335
}
336
 
337
 
338
/* Create an elimination graph with SIZE nodes and associated data
339
   structures.  */
340
 
341
static elim_graph
342
new_elim_graph (int size)
343
{
344
  elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
345
 
346
  g->nodes = VEC_alloc (int, heap, 30);
347
  g->const_dests = VEC_alloc (int, heap, 20);
348
  g->const_copies = VEC_alloc (tree, heap, 20);
349
  g->copy_locus = VEC_alloc (source_location, heap, 10);
350
  g->edge_list = VEC_alloc (int, heap, 20);
351
  g->edge_locus = VEC_alloc (source_location, heap, 10);
352
  g->stack = VEC_alloc (int, heap, 30);
353
 
354
  g->visited = sbitmap_alloc (size);
355
 
356
  return g;
357
}
358
 
359
 
360
/* Empty elimination graph G.  */
361
 
362
static inline void
363
clear_elim_graph (elim_graph g)
364
{
365
  VEC_truncate (int, g->nodes, 0);
366
  VEC_truncate (int, g->edge_list, 0);
367
  VEC_truncate (source_location, g->edge_locus, 0);
368
}
369
 
370
 
371
/* Delete elimination graph G.  */
372
 
373
static inline void
374
delete_elim_graph (elim_graph g)
375
{
376
  sbitmap_free (g->visited);
377
  VEC_free (int, heap, g->stack);
378
  VEC_free (int, heap, g->edge_list);
379
  VEC_free (tree, heap, g->const_copies);
380
  VEC_free (int, heap, g->const_dests);
381
  VEC_free (int, heap, g->nodes);
382
  VEC_free (source_location, heap, g->copy_locus);
383
  VEC_free (source_location, heap, g->edge_locus);
384
 
385
  free (g);
386
}
387
 
388
 
389
/* Return the number of nodes in graph G.  */
390
 
391
static inline int
392
elim_graph_size (elim_graph g)
393
{
394
  return VEC_length (int, g->nodes);
395
}
396
 
397
 
398
/* Add NODE to graph G, if it doesn't exist already.  */
399
 
400
static inline void
401
elim_graph_add_node (elim_graph g, int node)
402
{
403
  int x;
404
  int t;
405
 
406
  FOR_EACH_VEC_ELT (int, g->nodes, x, t)
407
    if (t == node)
408
      return;
409
  VEC_safe_push (int, heap, g->nodes, node);
410
}
411
 
412
 
413
/* Add the edge PRED->SUCC to graph G.  */
414
 
415
static inline void
416
elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus)
417
{
418
  VEC_safe_push (int, heap, g->edge_list, pred);
419
  VEC_safe_push (int, heap, g->edge_list, succ);
420
  VEC_safe_push (source_location, heap, g->edge_locus, locus);
421
}
422
 
423
 
424
/* Remove an edge from graph G for which NODE is the predecessor, and
425
   return the successor node.  -1 is returned if there is no such edge.  */
426
 
427
static inline int
428
elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus)
429
{
430
  int y;
431
  unsigned x;
432
  for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
433
    if (VEC_index (int, g->edge_list, x) == node)
434
      {
435
        VEC_replace (int, g->edge_list, x, -1);
436
        y = VEC_index (int, g->edge_list, x + 1);
437
        VEC_replace (int, g->edge_list, x + 1, -1);
438
        *locus = VEC_index (source_location, g->edge_locus, x / 2);
439
        VEC_replace (source_location, g->edge_locus, x / 2, UNKNOWN_LOCATION);
440
        return y;
441
      }
442
  *locus = UNKNOWN_LOCATION;
443
  return -1;
444
}
445
 
446
 
447
/* Find all the nodes in GRAPH which are successors to NODE in the
448
   edge list.  VAR will hold the partition number found.  CODE is the
449
   code fragment executed for every node found.  */
450
 
451
#define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE)         \
452
do {                                                                    \
453
  unsigned x_;                                                          \
454
  int y_;                                                               \
455
  for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)       \
456
    {                                                                   \
457
      y_ = VEC_index (int, (GRAPH)->edge_list, x_);                     \
458
      if (y_ != (NODE))                                                 \
459
        continue;                                                       \
460
      (void) ((VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1));     \
461
      (void) ((LOCUS) = VEC_index (source_location,                     \
462
                                   (GRAPH)->edge_locus, x_ / 2));       \
463
      CODE;                                                             \
464
    }                                                                   \
465
} while (0)
466
 
467
 
468
/* Find all the nodes which are predecessors of NODE in the edge list for
469
   GRAPH.  VAR will hold the partition number found.  CODE is the
470
   code fragment executed for every node found.  */
471
 
472
#define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE)         \
473
do {                                                                    \
474
  unsigned x_;                                                          \
475
  int y_;                                                               \
476
  for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)       \
477
    {                                                                   \
478
      y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1);                 \
479
      if (y_ != (NODE))                                                 \
480
        continue;                                                       \
481
      (void) ((VAR) = VEC_index (int, (GRAPH)->edge_list, x_));         \
482
      (void) ((LOCUS) = VEC_index (source_location,                     \
483
                                   (GRAPH)->edge_locus, x_ / 2));       \
484
      CODE;                                                             \
485
    }                                                                   \
486
} while (0)
487
 
488
 
489
/* Add T to elimination graph G.  */
490
 
491
static inline void
492
eliminate_name (elim_graph g, int T)
493
{
494
  elim_graph_add_node (g, T);
495
}
496
 
497
 
498
/* Build elimination graph G for basic block BB on incoming PHI edge
499
   G->e.  */
500
 
501
static void
502
eliminate_build (elim_graph g)
503
{
504
  tree Ti;
505
  int p0, pi;
506
  gimple_stmt_iterator gsi;
507
 
508
  clear_elim_graph (g);
509
 
510
  for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
511
    {
512
      gimple phi = gsi_stmt (gsi);
513
      source_location locus;
514
 
515
      p0 = var_to_partition (g->map, gimple_phi_result (phi));
516
      /* Ignore results which are not in partitions.  */
517
      if (p0 == NO_PARTITION)
518
        continue;
519
 
520
      Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
521
      locus = gimple_phi_arg_location_from_edge (phi, g->e);
522
 
523
      /* If this argument is a constant, or a SSA_NAME which is being
524
         left in SSA form, just queue a copy to be emitted on this
525
         edge.  */
526
      if (!phi_ssa_name_p (Ti)
527
          || (TREE_CODE (Ti) == SSA_NAME
528
              && var_to_partition (g->map, Ti) == NO_PARTITION))
529
        {
530
          /* Save constant copies until all other copies have been emitted
531
             on this edge.  */
532
          VEC_safe_push (int, heap, g->const_dests, p0);
533
          VEC_safe_push (tree, heap, g->const_copies, Ti);
534
          VEC_safe_push (source_location, heap, g->copy_locus, locus);
535
        }
536
      else
537
        {
538
          pi = var_to_partition (g->map, Ti);
539
          if (p0 != pi)
540
            {
541
              eliminate_name (g, p0);
542
              eliminate_name (g, pi);
543
              elim_graph_add_edge (g, p0, pi, locus);
544
            }
545
        }
546
    }
547
}
548
 
549
 
550
/* Push successors of T onto the elimination stack for G.  */
551
 
552
static void
553
elim_forward (elim_graph g, int T)
554
{
555
  int S;
556
  source_location locus;
557
 
558
  SET_BIT (g->visited, T);
559
  FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus,
560
    {
561
      if (!TEST_BIT (g->visited, S))
562
        elim_forward (g, S);
563
    });
564
  VEC_safe_push (int, heap, g->stack, T);
565
}
566
 
567
 
568
/* Return 1 if there unvisited predecessors of T in graph G.  */
569
 
570
static int
571
elim_unvisited_predecessor (elim_graph g, int T)
572
{
573
  int P;
574
  source_location locus;
575
 
576
  FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
577
    {
578
      if (!TEST_BIT (g->visited, P))
579
        return 1;
580
    });
581
  return 0;
582
}
583
 
584
/* Process predecessors first, and insert a copy.  */
585
 
586
static void
587
elim_backward (elim_graph g, int T)
588
{
589
  int P;
590
  source_location locus;
591
 
592
  SET_BIT (g->visited, T);
593
  FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
594
    {
595
      if (!TEST_BIT (g->visited, P))
596
        {
597
          elim_backward (g, P);
598
          insert_partition_copy_on_edge (g->e, P, T, locus);
599
        }
600
    });
601
}
602
 
603
/* Allocate a new pseudo register usable for storing values sitting
604
   in NAME (a decl or SSA name), i.e. with matching mode and attributes.  */
605
 
606
static rtx
607
get_temp_reg (tree name)
608
{
609
  tree var = TREE_CODE (name) == SSA_NAME ? SSA_NAME_VAR (name) : name;
610
  tree type = TREE_TYPE (var);
611
  int unsignedp;
612
  enum machine_mode reg_mode = promote_decl_mode (var, &unsignedp);
613
  rtx x = gen_reg_rtx (reg_mode);
614
  if (POINTER_TYPE_P (type))
615
    mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
616
  return x;
617
}
618
 
619
/* Insert required copies for T in graph G.  Check for a strongly connected
620
   region, and create a temporary to break the cycle if one is found.  */
621
 
622
static void
623
elim_create (elim_graph g, int T)
624
{
625
  int P, S;
626
  source_location locus;
627
 
628
  if (elim_unvisited_predecessor (g, T))
629
    {
630
      tree var = partition_to_var (g->map, T);
631
      rtx U = get_temp_reg (var);
632
      int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
633
 
634
      insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
635
      FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
636
        {
637
          if (!TEST_BIT (g->visited, P))
638
            {
639
              elim_backward (g, P);
640
              insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
641
            }
642
        });
643
    }
644
  else
645
    {
646
      S = elim_graph_remove_succ_edge (g, T, &locus);
647
      if (S != -1)
648
        {
649
          SET_BIT (g->visited, T);
650
          insert_partition_copy_on_edge (g->e, T, S, locus);
651
        }
652
    }
653
}
654
 
655
 
656
/* Eliminate all the phi nodes on edge E in graph G.  */
657
 
658
static void
659
eliminate_phi (edge e, elim_graph g)
660
{
661
  int x;
662
 
663
  gcc_assert (VEC_length (tree, g->const_copies) == 0);
664
  gcc_assert (VEC_length (source_location, g->copy_locus) == 0);
665
 
666
  /* Abnormal edges already have everything coalesced.  */
667
  if (e->flags & EDGE_ABNORMAL)
668
    return;
669
 
670
  g->e = e;
671
 
672
  eliminate_build (g);
673
 
674
  if (elim_graph_size (g) != 0)
675
    {
676
      int part;
677
 
678
      sbitmap_zero (g->visited);
679
      VEC_truncate (int, g->stack, 0);
680
 
681
      FOR_EACH_VEC_ELT (int, g->nodes, x, part)
682
        {
683
          if (!TEST_BIT (g->visited, part))
684
            elim_forward (g, part);
685
        }
686
 
687
      sbitmap_zero (g->visited);
688
      while (VEC_length (int, g->stack) > 0)
689
        {
690
          x = VEC_pop (int, g->stack);
691
          if (!TEST_BIT (g->visited, x))
692
            elim_create (g, x);
693
        }
694
    }
695
 
696
  /* If there are any pending constant copies, issue them now.  */
697
  while (VEC_length (tree, g->const_copies) > 0)
698
    {
699
      int dest;
700
      tree src;
701
      source_location locus;
702
 
703
      src = VEC_pop (tree, g->const_copies);
704
      dest = VEC_pop (int, g->const_dests);
705
      locus = VEC_pop (source_location, g->copy_locus);
706
      insert_value_copy_on_edge (e, dest, src, locus);
707
    }
708
}
709
 
710
 
711
/* Remove each argument from PHI.  If an arg was the last use of an SSA_NAME,
712
   check to see if this allows another PHI node to be removed.  */
713
 
714
static void
715
remove_gimple_phi_args (gimple phi)
716
{
717
  use_operand_p arg_p;
718
  ssa_op_iter iter;
719
 
720
  if (dump_file && (dump_flags & TDF_DETAILS))
721
    {
722
      fprintf (dump_file, "Removing Dead PHI definition: ");
723
      print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
724
    }
725
 
726
  FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
727
    {
728
      tree arg = USE_FROM_PTR (arg_p);
729
      if (TREE_CODE (arg) == SSA_NAME)
730
        {
731
          /* Remove the reference to the existing argument.  */
732
          SET_USE (arg_p, NULL_TREE);
733
          if (has_zero_uses (arg))
734
            {
735
              gimple stmt;
736
              gimple_stmt_iterator gsi;
737
 
738
              stmt = SSA_NAME_DEF_STMT (arg);
739
 
740
              /* Also remove the def if it is a PHI node.  */
741
              if (gimple_code (stmt) == GIMPLE_PHI)
742
                {
743
                  remove_gimple_phi_args (stmt);
744
                  gsi = gsi_for_stmt (stmt);
745
                  remove_phi_node (&gsi, true);
746
                }
747
 
748
            }
749
        }
750
    }
751
}
752
 
753
/* Remove any PHI node which is a virtual PHI, or a PHI with no uses.  */
754
 
755
static void
756
eliminate_useless_phis (void)
757
{
758
  basic_block bb;
759
  gimple_stmt_iterator gsi;
760
  tree result;
761
 
762
  FOR_EACH_BB (bb)
763
    {
764
      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
765
        {
766
          gimple phi = gsi_stmt (gsi);
767
          result = gimple_phi_result (phi);
768
          if (!is_gimple_reg (SSA_NAME_VAR (result)))
769
            {
770
#ifdef ENABLE_CHECKING
771
              size_t i;
772
              /* There should be no arguments which are not virtual, or the
773
                 results will be incorrect.  */
774
              for (i = 0; i < gimple_phi_num_args (phi); i++)
775
                {
776
                  tree arg = PHI_ARG_DEF (phi, i);
777
                  if (TREE_CODE (arg) == SSA_NAME
778
                      && is_gimple_reg (SSA_NAME_VAR (arg)))
779
                    {
780
                      fprintf (stderr, "Argument of PHI is not virtual (");
781
                      print_generic_expr (stderr, arg, TDF_SLIM);
782
                      fprintf (stderr, "), but the result is :");
783
                      print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
784
                      internal_error ("SSA corruption");
785
                    }
786
                }
787
#endif
788
              remove_phi_node (&gsi, true);
789
            }
790
          else
791
            {
792
              /* Also remove real PHIs with no uses.  */
793
              if (has_zero_uses (result))
794
                {
795
                  remove_gimple_phi_args (phi);
796
                  remove_phi_node (&gsi, true);
797
                }
798
              else
799
                gsi_next (&gsi);
800
            }
801
        }
802
    }
803
}
804
 
805
 
806
/* This function will rewrite the current program using the variable mapping
807
   found in MAP.  If the replacement vector VALUES is provided, any
808
   occurrences of partitions with non-null entries in the vector will be
809
   replaced with the expression in the vector instead of its mapped
810
   variable.  */
811
 
812
static void
813
rewrite_trees (var_map map ATTRIBUTE_UNUSED)
814
{
815
#ifdef ENABLE_CHECKING
816
  basic_block bb;
817
  /* Search for PHIs where the destination has no partition, but one
818
     or more arguments has a partition.  This should not happen and can
819
     create incorrect code.  */
820
  FOR_EACH_BB (bb)
821
    {
822
      gimple_stmt_iterator gsi;
823
      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
824
        {
825
          gimple phi = gsi_stmt (gsi);
826
          tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
827
          if (T0 == NULL_TREE)
828
            {
829
              size_t i;
830
              for (i = 0; i < gimple_phi_num_args (phi); i++)
831
                {
832
                  tree arg = PHI_ARG_DEF (phi, i);
833
 
834
                  if (TREE_CODE (arg) == SSA_NAME
835
                      && var_to_partition (map, arg) != NO_PARTITION)
836
                    {
837
                      fprintf (stderr, "Argument of PHI is in a partition :(");
838
                      print_generic_expr (stderr, arg, TDF_SLIM);
839
                      fprintf (stderr, "), but the result is not :");
840
                      print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
841
                      internal_error ("SSA corruption");
842
                    }
843
                }
844
            }
845
        }
846
    }
847
#endif
848
}
849
 
850
/* Given the out-of-ssa info object SA (with prepared partitions)
851
   eliminate all phi nodes in all basic blocks.  Afterwards no
852
   basic block will have phi nodes anymore and there are possibly
853
   some RTL instructions inserted on edges.  */
854
 
855
void
856
expand_phi_nodes (struct ssaexpand *sa)
857
{
858
  basic_block bb;
859
  elim_graph g = new_elim_graph (sa->map->num_partitions);
860
  g->map = sa->map;
861
 
862
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
863
    if (!gimple_seq_empty_p (phi_nodes (bb)))
864
      {
865
        edge e;
866
        edge_iterator ei;
867
        FOR_EACH_EDGE (e, ei, bb->preds)
868
          eliminate_phi (e, g);
869
        set_phi_nodes (bb, NULL);
870
        /* We can't redirect EH edges in RTL land, so we need to do this
871
           here.  Redirection happens only when splitting is necessary,
872
           which it is only for critical edges, normally.  For EH edges
873
           it might also be necessary when the successor has more than
874
           one predecessor.  In that case the edge is either required to
875
           be fallthru (which EH edges aren't), or the predecessor needs
876
           to end with a jump (which again, isn't the case with EH edges).
877
           Hence, split all EH edges on which we inserted instructions
878
           and whose successor has multiple predecessors.  */
879
        for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
880
          {
881
            if (e->insns.r && (e->flags & EDGE_EH)
882
                && !single_pred_p (e->dest))
883
              {
884
                rtx insns = e->insns.r;
885
                basic_block bb;
886
                e->insns.r = NULL_RTX;
887
                bb = split_edge (e);
888
                single_pred_edge (bb)->insns.r = insns;
889
              }
890
            else
891
              ei_next (&ei);
892
          }
893
      }
894
 
895
  delete_elim_graph (g);
896
}
897
 
898
 
899
/* Remove the ssa-names in the current function and translate them into normal
900
   compiler variables.  PERFORM_TER is true if Temporary Expression Replacement
901
   should also be used.  */
902
 
903
static void
904
remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
905
{
906
  bitmap values = NULL;
907
  var_map map;
908
  unsigned i;
909
 
910
  map = coalesce_ssa_name ();
911
 
912
  /* Return to viewing the variable list as just all reference variables after
913
     coalescing has been performed.  */
914
  partition_view_normal (map, false);
915
 
916
  if (dump_file && (dump_flags & TDF_DETAILS))
917
    {
918
      fprintf (dump_file, "After Coalescing:\n");
919
      dump_var_map (dump_file, map);
920
    }
921
 
922
  if (perform_ter)
923
    {
924
      values = find_replaceable_exprs (map);
925
      if (values && dump_file && (dump_flags & TDF_DETAILS))
926
        dump_replaceable_exprs (dump_file, values);
927
    }
928
 
929
  rewrite_trees (map);
930
 
931
  sa->map = map;
932
  sa->values = values;
933
  sa->partition_has_default_def = BITMAP_ALLOC (NULL);
934
  for (i = 1; i < num_ssa_names; i++)
935
    {
936
      tree t = ssa_name (i);
937
      if (t && SSA_NAME_IS_DEFAULT_DEF (t))
938
        {
939
          int p = var_to_partition (map, t);
940
          if (p != NO_PARTITION)
941
            bitmap_set_bit (sa->partition_has_default_def, p);
942
        }
943
    }
944
}
945
 
946
 
947
/* If not already done so for basic block BB, assign increasing uids
948
   to each of its instructions.  */
949
 
950
static void
951
maybe_renumber_stmts_bb (basic_block bb)
952
{
953
  unsigned i = 0;
954
  gimple_stmt_iterator gsi;
955
 
956
  if (!bb->aux)
957
    return;
958
  bb->aux = NULL;
959
  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
960
    {
961
      gimple stmt = gsi_stmt (gsi);
962
      gimple_set_uid (stmt, i);
963
      i++;
964
    }
965
}
966
 
967
 
968
/* Return true if we can determine that the SSA_NAMEs RESULT (a result
969
   of a PHI node) and ARG (one of its arguments) conflict.  Return false
970
   otherwise, also when we simply aren't sure.  */
971
 
972
static bool
973
trivially_conflicts_p (basic_block bb, tree result, tree arg)
974
{
975
  use_operand_p use;
976
  imm_use_iterator imm_iter;
977
  gimple defa = SSA_NAME_DEF_STMT (arg);
978
 
979
  /* If ARG isn't defined in the same block it's too complicated for
980
     our little mind.  */
981
  if (gimple_bb (defa) != bb)
982
    return false;
983
 
984
  FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
985
    {
986
      gimple use_stmt = USE_STMT (use);
987
      if (is_gimple_debug (use_stmt))
988
        continue;
989
      /* Now, if there's a use of RESULT that lies outside this basic block,
990
         then there surely is a conflict with ARG.  */
991
      if (gimple_bb (use_stmt) != bb)
992
        return true;
993
      if (gimple_code (use_stmt) == GIMPLE_PHI)
994
        continue;
995
      /* The use now is in a real stmt of BB, so if ARG was defined
996
         in a PHI node (like RESULT) both conflict.  */
997
      if (gimple_code (defa) == GIMPLE_PHI)
998
        return true;
999
      maybe_renumber_stmts_bb (bb);
1000
      /* If the use of RESULT occurs after the definition of ARG,
1001
         the two conflict too.  */
1002
      if (gimple_uid (defa) < gimple_uid (use_stmt))
1003
        return true;
1004
    }
1005
 
1006
  return false;
1007
}
1008
 
1009
 
1010
/* Search every PHI node for arguments associated with backedges which
1011
   we can trivially determine will need a copy (the argument is either
1012
   not an SSA_NAME or the argument has a different underlying variable
1013
   than the PHI result).
1014
 
1015
   Insert a copy from the PHI argument to a new destination at the
1016
   end of the block with the backedge to the top of the loop.  Update
1017
   the PHI argument to reference this new destination.  */
1018
 
1019
static void
1020
insert_backedge_copies (void)
1021
{
1022
  basic_block bb;
1023
  gimple_stmt_iterator gsi;
1024
 
1025
  mark_dfs_back_edges ();
1026
 
1027
  FOR_EACH_BB (bb)
1028
    {
1029
      /* Mark block as possibly needing calculation of UIDs.  */
1030
      bb->aux = &bb->aux;
1031
 
1032
      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1033
        {
1034
          gimple phi = gsi_stmt (gsi);
1035
          tree result = gimple_phi_result (phi);
1036
          tree result_var;
1037
          size_t i;
1038
 
1039
          if (!is_gimple_reg (result))
1040
            continue;
1041
 
1042
          result_var = SSA_NAME_VAR (result);
1043
          for (i = 0; i < gimple_phi_num_args (phi); i++)
1044
            {
1045
              tree arg = gimple_phi_arg_def (phi, i);
1046
              edge e = gimple_phi_arg_edge (phi, i);
1047
 
1048
              /* If the argument is not an SSA_NAME, then we will need a
1049
                 constant initialization.  If the argument is an SSA_NAME with
1050
                 a different underlying variable then a copy statement will be
1051
                 needed.  */
1052
              if ((e->flags & EDGE_DFS_BACK)
1053
                  && (TREE_CODE (arg) != SSA_NAME
1054
                      || SSA_NAME_VAR (arg) != result_var
1055
                      || trivially_conflicts_p (bb, result, arg)))
1056
                {
1057
                  tree name;
1058
                  gimple stmt, last = NULL;
1059
                  gimple_stmt_iterator gsi2;
1060
 
1061
                  gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1062
                  if (!gsi_end_p (gsi2))
1063
                    last = gsi_stmt (gsi2);
1064
 
1065
                  /* In theory the only way we ought to get back to the
1066
                     start of a loop should be with a COND_EXPR or GOTO_EXPR.
1067
                     However, better safe than sorry.
1068
                     If the block ends with a control statement or
1069
                     something that might throw, then we have to
1070
                     insert this assignment before the last
1071
                     statement.  Else insert it after the last statement.  */
1072
                  if (last && stmt_ends_bb_p (last))
1073
                    {
1074
                      /* If the last statement in the block is the definition
1075
                         site of the PHI argument, then we can't insert
1076
                         anything after it.  */
1077
                      if (TREE_CODE (arg) == SSA_NAME
1078
                          && SSA_NAME_DEF_STMT (arg) == last)
1079
                        continue;
1080
                    }
1081
 
1082
                  /* Create a new instance of the underlying variable of the
1083
                     PHI result.  */
1084
                  stmt = gimple_build_assign (result_var,
1085
                                              gimple_phi_arg_def (phi, i));
1086
                  name = make_ssa_name (result_var, stmt);
1087
                  gimple_assign_set_lhs (stmt, name);
1088
 
1089
                  /* copy location if present.  */
1090
                  if (gimple_phi_arg_has_location (phi, i))
1091
                    gimple_set_location (stmt,
1092
                                         gimple_phi_arg_location (phi, i));
1093
 
1094
                  /* Insert the new statement into the block and update
1095
                     the PHI node.  */
1096
                  if (last && stmt_ends_bb_p (last))
1097
                    gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1098
                  else
1099
                    gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1100
                  SET_PHI_ARG_DEF (phi, i, name);
1101
                }
1102
            }
1103
        }
1104
 
1105
      /* Unmark this block again.  */
1106
      bb->aux = NULL;
1107
    }
1108
}
1109
 
1110
/* Free all memory associated with going out of SSA form.  SA is
1111
   the outof-SSA info object.  */
1112
 
1113
void
1114
finish_out_of_ssa (struct ssaexpand *sa)
1115
{
1116
  free (sa->partition_to_pseudo);
1117
  if (sa->values)
1118
    BITMAP_FREE (sa->values);
1119
  delete_var_map (sa->map);
1120
  BITMAP_FREE (sa->partition_has_default_def);
1121
  memset (sa, 0, sizeof *sa);
1122
}
1123
 
1124
/* Take the current function out of SSA form, translating PHIs as described in
1125
   R. Morgan, ``Building an Optimizing Compiler'',
1126
   Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
1127
 
1128
unsigned int
1129
rewrite_out_of_ssa (struct ssaexpand *sa)
1130
{
1131
  /* If elimination of a PHI requires inserting a copy on a backedge,
1132
     then we will have to split the backedge which has numerous
1133
     undesirable performance effects.
1134
 
1135
     A significant number of such cases can be handled here by inserting
1136
     copies into the loop itself.  */
1137
  insert_backedge_copies ();
1138
 
1139
 
1140
  /* Eliminate PHIs which are of no use, such as virtual or dead phis.  */
1141
  eliminate_useless_phis ();
1142
 
1143
  if (dump_file && (dump_flags & TDF_DETAILS))
1144
    gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1145
 
1146
  remove_ssa_form (flag_tree_ter, sa);
1147
 
1148
  if (dump_file && (dump_flags & TDF_DETAILS))
1149
    gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1150
 
1151
  return 0;
1152
}

powered by: WebSVN 2.1.0

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