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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-into-ssa.c] - Blame information for rev 816

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Rewrite a program in Normal form into SSA.
2
   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007
3
   Free Software Foundation, Inc.
4
   Contributed by Diego Novillo <dnovillo@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 "flags.h"
28
#include "rtl.h"
29
#include "tm_p.h"
30
#include "langhooks.h"
31
#include "hard-reg-set.h"
32
#include "basic-block.h"
33
#include "output.h"
34
#include "expr.h"
35
#include "function.h"
36
#include "diagnostic.h"
37
#include "bitmap.h"
38
#include "tree-flow.h"
39
#include "tree-gimple.h"
40
#include "tree-inline.h"
41
#include "varray.h"
42
#include "timevar.h"
43
#include "hashtab.h"
44
#include "tree-dump.h"
45
#include "tree-pass.h"
46
#include "cfgloop.h"
47
#include "domwalk.h"
48
#include "ggc.h"
49
#include "params.h"
50
#include "vecprim.h"
51
 
52
/* This file builds the SSA form for a function as described in:
53
   R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
54
   Computing Static Single Assignment Form and the Control Dependence
55
   Graph. ACM Transactions on Programming Languages and Systems,
56
   13(4):451-490, October 1991.  */
57
 
58
/* True if the code is in ssa form.  */
59
bool in_ssa_p;
60
 
61
/* Structure to map a variable VAR to the set of blocks that contain
62
   definitions for VAR.  */
63
struct def_blocks_d
64
{
65
  /* The variable.  */
66
  tree var;
67
 
68
  /* Blocks that contain definitions of VAR.  Bit I will be set if the
69
     Ith block contains a definition of VAR.  */
70
  bitmap def_blocks;
71
 
72
  /* Blocks that contain a PHI node for VAR.  */
73
  bitmap phi_blocks;
74
 
75
  /* Blocks where VAR is live-on-entry.  Similar semantics as
76
     DEF_BLOCKS.  */
77
  bitmap livein_blocks;
78
};
79
 
80
 
81
/* Each entry in DEF_BLOCKS contains an element of type STRUCT
82
   DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
83
   basic blocks where VAR is defined (assigned a new value).  It also
84
   contains a bitmap of all the blocks where VAR is live-on-entry
85
   (i.e., there is a use of VAR in block B without a preceding
86
   definition in B).  The live-on-entry information is used when
87
   computing PHI pruning heuristics.  */
88
static htab_t def_blocks;
89
 
90
/* Stack of trees used to restore the global currdefs to its original
91
   state after completing rewriting of a block and its dominator
92
   children.  Its elements have the following properties:
93
 
94
   - An SSA_NAME indicates that the current definition of the
95
     underlying variable should be set to the given SSA_NAME.
96
 
97
   - A _DECL node indicates that the underlying variable has no
98
     current definition.
99
 
100
   - A NULL node is used to mark the last node associated with the
101
     current block.
102
 
103
   - A NULL node at the top entry is used to mark the last node
104
     associated with the current block.  */
105
static VEC(tree,heap) *block_defs_stack;
106
 
107
/* Set of existing SSA names being replaced by update_ssa.  */
108
static sbitmap old_ssa_names;
109
 
110
/* Set of new SSA names being added by update_ssa.  Note that both
111
   NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
112
   the operations done on them are presence tests.  */
113
static sbitmap new_ssa_names;
114
 
115
/* Symbols whose SSA form needs to be updated or created for the first
116
   time.  */
117
static bitmap syms_to_rename;
118
 
119
/* Set of SSA names that have been marked to be released after they
120
   were registered in the replacement table.  They will be finally
121
   released after we finish updating the SSA web.  */
122
static bitmap names_to_release;
123
 
124
/* For each block, the phi nodes that need to be rewritten are stored into
125
   these vectors.  */
126
 
127
typedef VEC(tree, heap) *tree_vec;
128
DEF_VEC_P (tree_vec);
129
DEF_VEC_ALLOC_P (tree_vec, heap);
130
 
131
static VEC(tree_vec, heap) *phis_to_rewrite;
132
 
133
/* The bitmap of non-NULL elements of PHIS_TO_REWRITE.  */
134
 
135
static bitmap blocks_with_phis_to_rewrite;
136
 
137
/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES.  These sets need
138
   to grow as the callers to register_new_name_mapping will typically
139
   create new names on the fly.  FIXME.  Currently set to 1/3 to avoid
140
   frequent reallocations but still need to find a reasonable growth
141
   strategy.  */
142
#define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
143
 
144
/* Tuple used to represent replacement mappings.  */
145
struct repl_map_d
146
{
147
  tree name;
148
  bitmap set;
149
};
150
 
151
/* NEW -> OLD_SET replacement table.  If we are replacing several
152
   existing SSA names O_1, O_2, ..., O_j with a new name N_i,
153
   then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }.  */
154
static htab_t repl_tbl;
155
 
156
/* true if register_new_name_mapping needs to initialize the data
157
   structures needed by update_ssa.  */
158
static bool need_to_initialize_update_ssa_p = true;
159
 
160
/* true if update_ssa needs to update virtual operands.  */
161
static bool need_to_update_vops_p = false;
162
 
163
/* Statistics kept by update_ssa to use in the virtual mapping
164
   heuristic.  If the number of virtual mappings is beyond certain
165
   threshold, the updater will switch from using the mappings into
166
   renaming the virtual symbols from scratch.  In some cases, the
167
   large number of name mappings for virtual names causes significant
168
   slowdowns in the PHI insertion code.  */
169
struct update_ssa_stats_d
170
{
171
  unsigned num_virtual_mappings;
172
  unsigned num_total_mappings;
173
  bitmap virtual_symbols;
174
  unsigned num_virtual_symbols;
175
};
176
static struct update_ssa_stats_d update_ssa_stats;
177
 
178
/* Global data to attach to the main dominator walk structure.  */
179
struct mark_def_sites_global_data
180
{
181
  /* This bitmap contains the variables which are set before they
182
     are used in a basic block.  */
183
  bitmap kills;
184
 
185
  /* Bitmap of names to rename.  */
186
  sbitmap names_to_rename;
187
 
188
  /* Set of blocks that mark_def_sites deems interesting for the
189
     renamer to process.  */
190
  sbitmap interesting_blocks;
191
};
192
 
193
 
194
/* Information stored for SSA names.  */
195
struct ssa_name_info
196
{
197
  /* The actual definition of the ssa name.  */
198
  tree current_def;
199
 
200
  /* This field indicates whether or not the variable may need PHI nodes.
201
     See the enum's definition for more detailed information about the
202
     states.  */
203
  ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
204
 
205
  /* Age of this record (so that info_for_ssa_name table can be cleared
206
     quicky); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
207
     are assumed to be null.  */
208
  unsigned age;
209
};
210
 
211
/* The information associated with names.  */
212
typedef struct ssa_name_info *ssa_name_info_p;
213
DEF_VEC_P (ssa_name_info_p);
214
DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
215
 
216
static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
217
static unsigned current_info_for_ssa_name_age;
218
 
219
/* The set of blocks affected by update_ssa.  */
220
 
221
static bitmap blocks_to_update;
222
 
223
/* The main entry point to the SSA renamer (rewrite_blocks) may be
224
   called several times to do different, but related, tasks.
225
   Initially, we need it to rename the whole program into SSA form.
226
   At other times, we may need it to only rename into SSA newly
227
   exposed symbols.  Finally, we can also call it to incrementally fix
228
   an already built SSA web.  */
229
enum rewrite_mode {
230
    /* Convert the whole function into SSA form.  */
231
    REWRITE_ALL,
232
 
233
    /* Incrementally update the SSA web by replacing existing SSA
234
       names with new ones.  See update_ssa for details.  */
235
    REWRITE_UPDATE
236
};
237
 
238
 
239
/* Use TREE_VISITED to keep track of which statements we want to
240
   rename.  When renaming a subset of the variables, not all
241
   statements will be processed.  This is decided in mark_def_sites.  */
242
#define REWRITE_THIS_STMT(T)    TREE_VISITED (T)
243
 
244
/* Use the unsigned flag to keep track of which statements we want to
245
   visit when marking new definition sites.  This is slightly
246
   different than REWRITE_THIS_STMT: it's used by update_ssa to
247
   distinguish statements that need to have both uses and defs
248
   processed from those that only need to have their defs processed.
249
   Statements that define new SSA names only need to have their defs
250
   registered, but they don't need to have their uses renamed.  */
251
#define REGISTER_DEFS_IN_THIS_STMT(T)   (T)->common.unsigned_flag
252
 
253
 
254
/* Prototypes for debugging functions.  */
255
extern void dump_tree_ssa (FILE *);
256
extern void debug_tree_ssa (void);
257
extern void debug_def_blocks (void);
258
extern void dump_tree_ssa_stats (FILE *);
259
extern void debug_tree_ssa_stats (void);
260
void dump_update_ssa (FILE *);
261
void debug_update_ssa (void);
262
void dump_names_replaced_by (FILE *, tree);
263
void debug_names_replaced_by (tree);
264
 
265
/* Get the information associated with NAME.  */
266
 
267
static inline struct ssa_name_info *
268
get_ssa_name_ann (tree name)
269
{
270
  unsigned ver = SSA_NAME_VERSION (name);
271
  unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
272
  struct ssa_name_info *info;
273
 
274
  if (ver >= len)
275
    {
276
      unsigned new_len = num_ssa_names;
277
 
278
      VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
279
      while (len++ < new_len)
280
        {
281
          struct ssa_name_info *info = XCNEW (struct ssa_name_info);
282
          info->age = current_info_for_ssa_name_age;
283
          VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
284
        }
285
    }
286
 
287
  info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
288
  if (info->age < current_info_for_ssa_name_age)
289
    {
290
      info->need_phi_state = 0;
291
      info->current_def = NULL_TREE;
292
      info->age = current_info_for_ssa_name_age;
293
    }
294
 
295
  return info;
296
}
297
 
298
/* Clears info for ssa names.  */
299
 
300
static void
301
clear_ssa_name_info (void)
302
{
303
  current_info_for_ssa_name_age++;
304
}
305
 
306
/* Gets phi_state field for VAR.  */
307
 
308
static inline enum need_phi_state
309
get_phi_state (tree var)
310
{
311
  if (TREE_CODE (var) == SSA_NAME)
312
    return get_ssa_name_ann (var)->need_phi_state;
313
  else
314
    return var_ann (var)->need_phi_state;
315
}
316
 
317
 
318
/* Sets phi_state field for VAR to STATE.  */
319
 
320
static inline void
321
set_phi_state (tree var, enum need_phi_state state)
322
{
323
  if (TREE_CODE (var) == SSA_NAME)
324
    get_ssa_name_ann (var)->need_phi_state = state;
325
  else
326
    var_ann (var)->need_phi_state = state;
327
}
328
 
329
 
330
/* Return the current definition for VAR.  */
331
 
332
tree
333
get_current_def (tree var)
334
{
335
  if (TREE_CODE (var) == SSA_NAME)
336
    return get_ssa_name_ann (var)->current_def;
337
  else
338
    return var_ann (var)->current_def;
339
}
340
 
341
 
342
/* Sets current definition of VAR to DEF.  */
343
 
344
void
345
set_current_def (tree var, tree def)
346
{
347
  if (TREE_CODE (var) == SSA_NAME)
348
    get_ssa_name_ann (var)->current_def = def;
349
  else
350
    var_ann (var)->current_def = def;
351
}
352
 
353
 
354
/* Compute global livein information given the set of blockx where
355
   an object is locally live at the start of the block (LIVEIN)
356
   and the set of blocks where the object is defined (DEF_BLOCKS).
357
 
358
   Note: This routine augments the existing local livein information
359
   to include global livein (i.e., it modifies the underlying bitmap
360
   for LIVEIN).  */
361
 
362
void
363
compute_global_livein (bitmap livein, bitmap def_blocks)
364
{
365
  basic_block bb, *worklist, *tos;
366
  unsigned i;
367
  bitmap_iterator bi;
368
 
369
  tos = worklist
370
    = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
371
 
372
  EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
373
    {
374
      *tos++ = BASIC_BLOCK (i);
375
    }
376
 
377
  /* Iterate until the worklist is empty.  */
378
  while (tos != worklist)
379
    {
380
      edge e;
381
      edge_iterator ei;
382
 
383
      /* Pull a block off the worklist.  */
384
      bb = *--tos;
385
 
386
      /* For each predecessor block.  */
387
      FOR_EACH_EDGE (e, ei, bb->preds)
388
        {
389
          basic_block pred = e->src;
390
          int pred_index = pred->index;
391
 
392
          /* None of this is necessary for the entry block.  */
393
          if (pred != ENTRY_BLOCK_PTR
394
              && ! bitmap_bit_p (livein, pred_index)
395
              && ! bitmap_bit_p (def_blocks, pred_index))
396
            {
397
              *tos++ = pred;
398
              bitmap_set_bit (livein, pred_index);
399
            }
400
        }
401
    }
402
 
403
  free (worklist);
404
}
405
 
406
 
407
/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
408
   all statements in basic block BB.  */
409
 
410
static void
411
initialize_flags_in_bb (basic_block bb)
412
{
413
  tree phi, stmt;
414
  block_stmt_iterator bsi;
415
 
416
  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
417
    {
418
      REWRITE_THIS_STMT (phi) = 0;
419
      REGISTER_DEFS_IN_THIS_STMT (phi) = 0;
420
    }
421
 
422
  for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
423
    {
424
      stmt = bsi_stmt (bsi);
425
      /* We are going to use the operand cache API, such as
426
         SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST.  The operand
427
         cache for each statement should be up-to-date.  */
428
      gcc_assert (!stmt_modified_p (stmt));
429
      REWRITE_THIS_STMT (stmt) = 0;
430
      REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
431
    }
432
}
433
 
434
/* Mark block BB as interesting for update_ssa.  */
435
 
436
static void
437
mark_block_for_update (basic_block bb)
438
{
439
  gcc_assert (blocks_to_update != NULL);
440
  if (bitmap_bit_p (blocks_to_update, bb->index))
441
    return;
442
  bitmap_set_bit (blocks_to_update, bb->index);
443
  initialize_flags_in_bb (bb);
444
}
445
 
446
/* Return the set of blocks where variable VAR is defined and the blocks
447
   where VAR is live on entry (livein).  If no entry is found in
448
   DEF_BLOCKS, a new one is created and returned.  */
449
 
450
static inline struct def_blocks_d *
451
get_def_blocks_for (tree var)
452
{
453
  struct def_blocks_d db, *db_p;
454
  void **slot;
455
 
456
  db.var = var;
457
  slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
458
  if (*slot == NULL)
459
    {
460
      db_p = XNEW (struct def_blocks_d);
461
      db_p->var = var;
462
      db_p->def_blocks = BITMAP_ALLOC (NULL);
463
      db_p->phi_blocks = BITMAP_ALLOC (NULL);
464
      db_p->livein_blocks = BITMAP_ALLOC (NULL);
465
      *slot = (void *) db_p;
466
    }
467
  else
468
    db_p = (struct def_blocks_d *) *slot;
469
 
470
  return db_p;
471
}
472
 
473
 
474
/* Mark block BB as the definition site for variable VAR.  PHI_P is true if
475
   VAR is defined by a PHI node.  */
476
 
477
static void
478
set_def_block (tree var, basic_block bb, bool phi_p)
479
{
480
  struct def_blocks_d *db_p;
481
  enum need_phi_state state;
482
 
483
  state = get_phi_state (var);
484
  db_p = get_def_blocks_for (var);
485
 
486
  /* Set the bit corresponding to the block where VAR is defined.  */
487
  bitmap_set_bit (db_p->def_blocks, bb->index);
488
  if (phi_p)
489
    bitmap_set_bit (db_p->phi_blocks, bb->index);
490
 
491
  /* Keep track of whether or not we may need to insert PHI nodes.
492
 
493
     If we are in the UNKNOWN state, then this is the first definition
494
     of VAR.  Additionally, we have not seen any uses of VAR yet, so
495
     we do not need a PHI node for this variable at this time (i.e.,
496
     transition to NEED_PHI_STATE_NO).
497
 
498
     If we are in any other state, then we either have multiple definitions
499
     of this variable occurring in different blocks or we saw a use of the
500
     variable which was not dominated by the block containing the
501
     definition(s).  In this case we may need a PHI node, so enter
502
     state NEED_PHI_STATE_MAYBE.  */
503
  if (state == NEED_PHI_STATE_UNKNOWN)
504
    set_phi_state (var, NEED_PHI_STATE_NO);
505
  else
506
    set_phi_state (var, NEED_PHI_STATE_MAYBE);
507
}
508
 
509
 
510
/* Mark block BB as having VAR live at the entry to BB.  */
511
 
512
static void
513
set_livein_block (tree var, basic_block bb)
514
{
515
  struct def_blocks_d *db_p;
516
  enum need_phi_state state = get_phi_state (var);
517
 
518
  db_p = get_def_blocks_for (var);
519
 
520
  /* Set the bit corresponding to the block where VAR is live in.  */
521
  bitmap_set_bit (db_p->livein_blocks, bb->index);
522
 
523
  /* Keep track of whether or not we may need to insert PHI nodes.
524
 
525
     If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
526
     by the single block containing the definition(s) of this variable.  If
527
     it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
528
     NEED_PHI_STATE_MAYBE.  */
529
  if (state == NEED_PHI_STATE_NO)
530
    {
531
      int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
532
 
533
      if (def_block_index == -1
534
          || ! dominated_by_p (CDI_DOMINATORS, bb,
535
                               BASIC_BLOCK (def_block_index)))
536
        set_phi_state (var, NEED_PHI_STATE_MAYBE);
537
    }
538
  else
539
    set_phi_state (var, NEED_PHI_STATE_MAYBE);
540
}
541
 
542
 
543
/* Return true if symbol SYM is marked for renaming.  */
544
 
545
static inline bool
546
symbol_marked_for_renaming (tree sym)
547
{
548
  gcc_assert (DECL_P (sym));
549
  return bitmap_bit_p (syms_to_rename, DECL_UID (sym));
550
}
551
 
552
 
553
/* Return true if NAME is in OLD_SSA_NAMES.  */
554
 
555
static inline bool
556
is_old_name (tree name)
557
{
558
  unsigned ver = SSA_NAME_VERSION (name);
559
  return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
560
}
561
 
562
 
563
/* Return true if NAME is in NEW_SSA_NAMES.  */
564
 
565
static inline bool
566
is_new_name (tree name)
567
{
568
  unsigned ver = SSA_NAME_VERSION (name);
569
  return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
570
}
571
 
572
 
573
/* Hashing and equality functions for REPL_TBL.  */
574
 
575
static hashval_t
576
repl_map_hash (const void *p)
577
{
578
  return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
579
}
580
 
581
static int
582
repl_map_eq (const void *p1, const void *p2)
583
{
584
  return ((const struct repl_map_d *)p1)->name
585
         == ((const struct repl_map_d *)p2)->name;
586
}
587
 
588
static void
589
repl_map_free (void *p)
590
{
591
  BITMAP_FREE (((struct repl_map_d *)p)->set);
592
  free (p);
593
}
594
 
595
 
596
/* Return the names replaced by NEW (i.e., REPL_TBL[NEW].SET).  */
597
 
598
static inline bitmap
599
names_replaced_by (tree new)
600
{
601
  struct repl_map_d m;
602
  void **slot;
603
 
604
  m.name = new;
605
  slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
606
 
607
  /* If N was not registered in the replacement table, return NULL.  */
608
  if (slot == NULL || *slot == NULL)
609
    return NULL;
610
 
611
  return ((struct repl_map_d *) *slot)->set;
612
}
613
 
614
 
615
/* Add OLD to REPL_TBL[NEW].SET.  */
616
 
617
static inline void
618
add_to_repl_tbl (tree new, tree old)
619
{
620
  struct repl_map_d m, *mp;
621
  void **slot;
622
 
623
  m.name = new;
624
  slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
625
  if (*slot == NULL)
626
    {
627
      mp = XNEW (struct repl_map_d);
628
      mp->name = new;
629
      mp->set = BITMAP_ALLOC (NULL);
630
      *slot = (void *) mp;
631
    }
632
  else
633
    mp = (struct repl_map_d *) *slot;
634
 
635
  bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
636
}
637
 
638
 
639
/* Add a new mapping NEW -> OLD REPL_TBL.  Every entry N_i in REPL_TBL
640
   represents the set of names O_1 ... O_j replaced by N_i.  This is
641
   used by update_ssa and its helpers to introduce new SSA names in an
642
   already formed SSA web.  */
643
 
644
static void
645
add_new_name_mapping (tree new, tree old)
646
{
647
  timevar_push (TV_TREE_SSA_INCREMENTAL);
648
 
649
  /* OLD and NEW must be different SSA names for the same symbol.  */
650
  gcc_assert (new != old && SSA_NAME_VAR (new) == SSA_NAME_VAR (old));
651
 
652
  /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
653
     caller may have created new names since the set was created.  */
654
  if (new_ssa_names->n_bits <= num_ssa_names - 1)
655
    {
656
      unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
657
      new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
658
      old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
659
    }
660
 
661
  /* If this mapping is for virtual names, we will need to update
662
     virtual operands.  */
663
  if (!is_gimple_reg (new))
664
    {
665
      tree sym;
666
      size_t uid;
667
 
668
      need_to_update_vops_p = true;
669
 
670
      /* Keep counts of virtual mappings and symbols to use in the
671
         virtual mapping heuristic.  If we have large numbers of
672
         virtual mappings for a relatively low number of symbols, it
673
         will make more sense to rename the symbols from scratch.
674
         Otherwise, the insertion of PHI nodes for each of the old
675
         names in these mappings will be very slow.  */
676
      sym = SSA_NAME_VAR (new);
677
      uid = DECL_UID (sym);
678
      update_ssa_stats.num_virtual_mappings++;
679
      if (!bitmap_bit_p (update_ssa_stats.virtual_symbols, uid))
680
        {
681
          bitmap_set_bit (update_ssa_stats.virtual_symbols, uid);
682
          update_ssa_stats.num_virtual_symbols++;
683
        }
684
    }
685
 
686
  /* Update the REPL_TBL table.  */
687
  add_to_repl_tbl (new, old);
688
 
689
  /* If OLD had already been registered as a new name, then all the
690
     names that OLD replaces should also be replaced by NEW.  */
691
  if (is_new_name (old))
692
    bitmap_ior_into (names_replaced_by (new), names_replaced_by (old));
693
 
694
  /* Register NEW and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
695
     respectively.  */
696
  SET_BIT (new_ssa_names, SSA_NAME_VERSION (new));
697
  SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
698
 
699
  /* Update mapping counter to use in the virtual mapping heuristic.  */
700
  update_ssa_stats.num_total_mappings++;
701
 
702
  timevar_pop (TV_TREE_SSA_INCREMENTAL);
703
}
704
 
705
 
706
/* Call back for walk_dominator_tree used to collect definition sites
707
   for every variable in the function.  For every statement S in block
708
   BB:
709
 
710
   1- Variables defined by S in the DEFS of S are marked in the bitmap
711
      WALK_DATA->GLOBAL_DATA->KILLS.
712
 
713
   2- If S uses a variable VAR and there is no preceding kill of VAR,
714
      then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
715
 
716
   This information is used to determine which variables are live
717
   across block boundaries to reduce the number of PHI nodes
718
   we create.  */
719
 
720
static void
721
mark_def_sites (struct dom_walk_data *walk_data,
722
                basic_block bb,
723
                block_stmt_iterator bsi)
724
{
725
  struct mark_def_sites_global_data *gd =
726
     (struct mark_def_sites_global_data *) walk_data->global_data;
727
  bitmap kills = gd->kills;
728
  tree stmt, def;
729
  use_operand_p use_p;
730
  def_operand_p def_p;
731
  ssa_op_iter iter;
732
 
733
  stmt = bsi_stmt (bsi);
734
  update_stmt_if_modified (stmt);
735
 
736
  gcc_assert (blocks_to_update == NULL);
737
  REGISTER_DEFS_IN_THIS_STMT (stmt) = 0;
738
  REWRITE_THIS_STMT (stmt) = 0;
739
 
740
  /* If a variable is used before being set, then the variable is live
741
     across a block boundary, so mark it live-on-entry to BB.  */
742
  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
743
                            SSA_OP_USE | SSA_OP_VUSE | SSA_OP_VMUSTKILL)
744
    {
745
      tree sym = USE_FROM_PTR (use_p);
746
      gcc_assert (DECL_P (sym));
747
      if (!bitmap_bit_p (kills, DECL_UID (sym)))
748
        set_livein_block (sym, bb);
749
      REWRITE_THIS_STMT (stmt) = 1;
750
    }
751
 
752
  /* Note that virtual definitions are irrelevant for computing KILLS
753
     because a V_MAY_DEF does not constitute a killing definition of the
754
     variable.  However, the operand of a virtual definitions is a use
755
     of the variable, so it may cause the variable to be considered
756
     live-on-entry.  */
757
  FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
758
    {
759
      tree sym = USE_FROM_PTR (use_p);
760
      gcc_assert (DECL_P (sym));
761
      set_livein_block (sym, bb);
762
      set_def_block (sym, bb, false);
763
      REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
764
      REWRITE_THIS_STMT (stmt) = 1;
765
    }
766
 
767
  /* Now process the defs and must-defs made by this statement.  */
768
  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF | SSA_OP_VMUSTDEF)
769
    {
770
      gcc_assert (DECL_P (def));
771
      set_def_block (def, bb, false);
772
      bitmap_set_bit (kills, DECL_UID (def));
773
      REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
774
    }
775
 
776
  /* If we found the statement interesting then also mark the block BB
777
     as interesting.  */
778
  if (REWRITE_THIS_STMT (stmt) || REGISTER_DEFS_IN_THIS_STMT (stmt))
779
    SET_BIT (gd->interesting_blocks, bb->index);
780
}
781
 
782
/* Structure used by prune_unused_phi_nodes to record bounds of the intervals
783
   in the dfs numbering of the dominance tree.  */
784
 
785
struct dom_dfsnum
786
{
787
  /* Basic block whose index this entry corresponds to.  */
788
  unsigned bb_index;
789
 
790
  /* The dfs number of this node.  */
791
  unsigned dfs_num;
792
};
793
 
794
/* Compares two entries of type struct dom_dfsnum by dfs_num field.  Callback
795
   for qsort.  */
796
 
797
static int
798
cmp_dfsnum (const void *a, const void *b)
799
{
800
  const struct dom_dfsnum *da = a;
801
  const struct dom_dfsnum *db = b;
802
 
803
  return (int) da->dfs_num - (int) db->dfs_num;
804
}
805
 
806
/* Among the intervals starting at the N points specified in DEFS, find
807
   the one that contains S, and return its bb_index.  */
808
 
809
static unsigned
810
find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
811
{
812
  unsigned f = 0, t = n, m;
813
 
814
  while (t > f + 1)
815
    {
816
      m = (f + t) / 2;
817
      if (defs[m].dfs_num <= s)
818
        f = m;
819
      else
820
        t = m;
821
    }
822
 
823
  return defs[f].bb_index;
824
}
825
 
826
/* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
827
   KILLS is a bitmap of blocks where the value is defined before any use.  */
828
 
829
static void
830
prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
831
{
832
  VEC(int, heap) *worklist;
833
  bitmap_iterator bi;
834
  unsigned i, b, p, u, top;
835
  bitmap live_phis;
836
  basic_block def_bb, use_bb;
837
  edge e;
838
  edge_iterator ei;
839
  bitmap to_remove;
840
  struct dom_dfsnum *defs;
841
  unsigned n_defs, adef;
842
 
843
  if (bitmap_empty_p (uses))
844
    {
845
      bitmap_clear (phis);
846
      return;
847
    }
848
 
849
  /* The phi must dominate a use, or an argument of a live phi.  Also, we
850
     do not create any phi nodes in def blocks, unless they are also livein.  */
851
  to_remove = BITMAP_ALLOC (NULL);
852
  bitmap_and_compl (to_remove, kills, uses);
853
  bitmap_and_compl_into (phis, to_remove);
854
  if (bitmap_empty_p (phis))
855
    {
856
      BITMAP_FREE (to_remove);
857
      return;
858
    }
859
 
860
  /* We want to remove the unnecessary phi nodes, but we do not want to compute
861
     liveness information, as that may be linear in the size of CFG, and if
862
     there are lot of different variables to rewrite, this may lead to quadratic
863
     behavior.
864
 
865
     Instead, we basically emulate standard dce.  We put all uses to worklist,
866
     then for each of them find the nearest def that dominates them.  If this
867
     def is a phi node, we mark it live, and if it was not live before, we
868
     add the predecessors of its basic block to the worklist.
869
 
870
     To quickly locate the nearest def that dominates use, we use dfs numbering
871
     of the dominance tree (that is already available in order to speed up
872
     queries).  For each def, we have the interval given by the dfs number on
873
     entry to and on exit from the corresponding subtree in the dominance tree.
874
     The nearest dominator for a given use is the smallest of these intervals
875
     that contains entry and exit dfs numbers for the basic block with the use.
876
     If we store the bounds for all the uses to an array and sort it, we can
877
     locate the nearest dominating def in logarithmic time by binary search.*/
878
  bitmap_ior (to_remove, kills, phis);
879
  n_defs = bitmap_count_bits (to_remove);
880
  defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
881
  defs[0].bb_index = 1;
882
  defs[0].dfs_num = 0;
883
  adef = 1;
884
  EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
885
    {
886
      def_bb = BASIC_BLOCK (i);
887
      defs[adef].bb_index = i;
888
      defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
889
      defs[adef + 1].bb_index = i;
890
      defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
891
      adef += 2;
892
    }
893
  BITMAP_FREE (to_remove);
894
  gcc_assert (adef == 2 * n_defs + 1);
895
  qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
896
  gcc_assert (defs[0].bb_index == 1);
897
 
898
  /* Now each DEFS entry contains the number of the basic block to that the
899
     dfs number corresponds.  Change them to the number of basic block that
900
     corresponds to the interval following the dfs number.  Also, for the
901
     dfs_out numbers, increase the dfs number by one (so that it corresponds
902
     to the start of the following interval, not to the end of the current
903
     one).  We use WORKLIST as a stack.  */
904
  worklist = VEC_alloc (int, heap, n_defs + 1);
905
  VEC_quick_push (int, worklist, 1);
906
  top = 1;
907
  n_defs = 1;
908
  for (i = 1; i < adef; i++)
909
    {
910
      b = defs[i].bb_index;
911
      if (b == top)
912
        {
913
          /* This is a closing element.  Interval corresponding to the top
914
             of the stack after removing it follows.  */
915
          VEC_pop (int, worklist);
916
          top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
917
          defs[n_defs].bb_index = top;
918
          defs[n_defs].dfs_num = defs[i].dfs_num + 1;
919
        }
920
      else
921
        {
922
          /* Opening element.  Nothing to do, just push it to the stack and move
923
             it to the correct position.  */
924
          defs[n_defs].bb_index = defs[i].bb_index;
925
          defs[n_defs].dfs_num = defs[i].dfs_num;
926
          VEC_quick_push (int, worklist, b);
927
          top = b;
928
        }
929
 
930
      /* If this interval starts at the same point as the previous one, cancel
931
         the previous one.  */
932
      if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
933
        defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
934
      else
935
        n_defs++;
936
    }
937
  VEC_pop (int, worklist);
938
  gcc_assert (VEC_empty (int, worklist));
939
 
940
  /* Now process the uses.  */
941
  live_phis = BITMAP_ALLOC (NULL);
942
  EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
943
    {
944
      VEC_safe_push (int, heap, worklist, i);
945
    }
946
 
947
  while (!VEC_empty (int, worklist))
948
    {
949
      b = VEC_pop (int, worklist);
950
      if (b == ENTRY_BLOCK)
951
        continue;
952
 
953
      /* If there is a phi node in USE_BB, it is made live.  Otherwise,
954
         find the def that dominates the immediate dominator of USE_BB
955
         (the kill in USE_BB does not dominate the use).  */
956
      if (bitmap_bit_p (phis, b))
957
        p = b;
958
      else
959
        {
960
          use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
961
          p = find_dfsnum_interval (defs, n_defs,
962
                                    bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
963
          if (!bitmap_bit_p (phis, p))
964
            continue;
965
        }
966
 
967
      /* If the phi node is already live, there is nothing to do.  */
968
      if (bitmap_bit_p (live_phis, p))
969
        continue;
970
 
971
      /* Mark the phi as live, and add the new uses to the worklist.  */
972
      bitmap_set_bit (live_phis, p);
973
      def_bb = BASIC_BLOCK (p);
974
      FOR_EACH_EDGE (e, ei, def_bb->preds)
975
        {
976
          u = e->src->index;
977
          if (bitmap_bit_p (uses, u))
978
            continue;
979
 
980
          /* In case there is a kill directly in the use block, do not record
981
             the use (this is also necessary for correctness, as we assume that
982
             uses dominated by a def directly in their block have been filtered
983
             out before).  */
984
          if (bitmap_bit_p (kills, u))
985
            continue;
986
 
987
          bitmap_set_bit (uses, u);
988
          VEC_safe_push (int, heap, worklist, u);
989
        }
990
    }
991
 
992
  VEC_free (int, heap, worklist);
993
  bitmap_copy (phis, live_phis);
994
  BITMAP_FREE (live_phis);
995
  free (defs);
996
}
997
 
998
/* Given a set of blocks with variable definitions (DEF_BLOCKS),
999
   return a bitmap with all the blocks in the iterated dominance
1000
   frontier of the blocks in DEF_BLOCKS.  DFS contains dominance
1001
   frontier information as returned by compute_dominance_frontiers.
1002
 
1003
   The resulting set of blocks are the potential sites where PHI nodes
1004
   are needed.  The caller is responsible from freeing the memory
1005
   allocated for the return value.  */
1006
 
1007
static bitmap
1008
find_idf (bitmap def_blocks, bitmap *dfs)
1009
{
1010
  bitmap_iterator bi;
1011
  unsigned bb_index;
1012
  VEC(int,heap) *work_stack;
1013
  bitmap phi_insertion_points;
1014
 
1015
  work_stack = VEC_alloc (int, heap, n_basic_blocks);
1016
  phi_insertion_points = BITMAP_ALLOC (NULL);
1017
 
1018
  /* Seed the work list with all the blocks in DEF_BLOCKS.  */
1019
  EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
1020
    /* We use VEC_quick_push here for speed.  This is safe because we
1021
       know that the number of definition blocks is no greater than
1022
       the number of basic blocks, which is the initial capacity of
1023
       WORK_STACK.  */
1024
    VEC_quick_push (int, work_stack, bb_index);
1025
 
1026
  /* Pop a block off the worklist, add every block that appears in
1027
     the original block's DF that we have not already processed to
1028
     the worklist.  Iterate until the worklist is empty.   Blocks
1029
     which are added to the worklist are potential sites for
1030
     PHI nodes.  */
1031
  while (VEC_length (int, work_stack) > 0)
1032
    {
1033
      bb_index = VEC_pop (int, work_stack);
1034
 
1035
      /* Since the registration of NEW -> OLD name mappings is done
1036
         separately from the call to update_ssa, when updating the SSA
1037
         form, the basic blocks where new and/or old names are defined
1038
         may have disappeared by CFG cleanup calls.  In this case,
1039
         we may pull a non-existing block from the work stack.  */
1040
      gcc_assert (bb_index < (unsigned) last_basic_block);
1041
 
1042
      EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
1043
                                      0, bb_index, bi)
1044
        {
1045
          /* Use a safe push because if there is a definition of VAR
1046
             in every basic block, then WORK_STACK may eventually have
1047
             more than N_BASIC_BLOCK entries.  */
1048
          VEC_safe_push (int, heap, work_stack, bb_index);
1049
          bitmap_set_bit (phi_insertion_points, bb_index);
1050
        }
1051
    }
1052
 
1053
  VEC_free (int, heap, work_stack);
1054
 
1055
  return phi_insertion_points;
1056
}
1057
 
1058
 
1059
/* Return the set of blocks where variable VAR is defined and the blocks
1060
   where VAR is live on entry (livein).  Return NULL, if no entry is
1061
   found in DEF_BLOCKS.  */
1062
 
1063
static inline struct def_blocks_d *
1064
find_def_blocks_for (tree var)
1065
{
1066
  struct def_blocks_d dm;
1067
  dm.var = var;
1068
  return (struct def_blocks_d *) htab_find (def_blocks, &dm);
1069
}
1070
 
1071
 
1072
/* Retrieve or create a default definition for symbol SYM.  */
1073
 
1074
static inline tree
1075
get_default_def_for (tree sym)
1076
{
1077
  tree ddef = default_def (sym);
1078
 
1079
  if (ddef == NULL_TREE)
1080
    {
1081
      ddef = make_ssa_name (sym, build_empty_stmt ());
1082
      set_default_def (sym, ddef);
1083
    }
1084
 
1085
  return ddef;
1086
}
1087
 
1088
 
1089
/* Marks phi node PHI in basic block BB for rewrite.  */
1090
 
1091
static void
1092
mark_phi_for_rewrite (basic_block bb, tree phi)
1093
{
1094
  tree_vec phis;
1095
  unsigned i, idx = bb->index;
1096
 
1097
  if (REWRITE_THIS_STMT (phi))
1098
    return;
1099
  REWRITE_THIS_STMT (phi) = 1;
1100
 
1101
  if (!blocks_with_phis_to_rewrite)
1102
    return;
1103
 
1104
  bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
1105
  VEC_reserve (tree_vec, heap, phis_to_rewrite, last_basic_block + 1);
1106
  for (i = VEC_length (tree_vec, phis_to_rewrite); i <= idx; i++)
1107
    VEC_quick_push (tree_vec, phis_to_rewrite, NULL);
1108
 
1109
  phis = VEC_index (tree_vec, phis_to_rewrite, idx);
1110
  if (!phis)
1111
    phis = VEC_alloc (tree, heap, 10);
1112
 
1113
  VEC_safe_push (tree, heap, phis, phi);
1114
  VEC_replace (tree_vec, phis_to_rewrite, idx, phis);
1115
}
1116
 
1117
/* Insert PHI nodes for variable VAR using the iterated dominance
1118
   frontier given in PHI_INSERTION_POINTS.  If UPDATE_P is true, this
1119
   function assumes that the caller is incrementally updating the SSA
1120
   form, in which case (1) VAR is assumed to be an SSA name, (2) a new
1121
   SSA name is created for VAR's symbol, and, (3) all the arguments
1122
   for the newly created PHI node are set to VAR.
1123
 
1124
   PHI_INSERTION_POINTS is updated to reflect nodes that already had a
1125
   PHI node for VAR.  On exit, only the nodes that received a PHI node
1126
   for VAR will be present in PHI_INSERTION_POINTS.  */
1127
 
1128
static void
1129
insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
1130
{
1131
  unsigned bb_index;
1132
  edge e;
1133
  tree phi;
1134
  basic_block bb;
1135
  bitmap_iterator bi;
1136
  struct def_blocks_d *def_map;
1137
 
1138
  def_map = find_def_blocks_for (var);
1139
  gcc_assert (def_map);
1140
 
1141
  /* Remove the blocks where we already have PHI nodes for VAR.  */
1142
  bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
1143
 
1144
  /* Remove obviously useless phi nodes.  */
1145
  prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
1146
                          def_map->livein_blocks);
1147
 
1148
  /* And insert the PHI nodes.  */
1149
  EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
1150
    {
1151
      bb = BASIC_BLOCK (bb_index);
1152
      if (update_p)
1153
        mark_block_for_update (bb);
1154
 
1155
      if (update_p && TREE_CODE (var) == SSA_NAME)
1156
        {
1157
          /* If we are rewriting SSA names, create the LHS of the PHI
1158
             node by duplicating VAR.  This is useful in the case of
1159
             pointers, to also duplicate pointer attributes (alias
1160
             information, in particular).  */
1161
          edge_iterator ei;
1162
          tree new_lhs;
1163
 
1164
          phi = create_phi_node (var, bb);
1165
          new_lhs = duplicate_ssa_name (var, phi);
1166
          SET_PHI_RESULT (phi, new_lhs);
1167
          add_new_name_mapping (new_lhs, var);
1168
 
1169
          /* Add VAR to every argument slot of PHI.  We need VAR in
1170
             every argument so that rewrite_update_phi_arguments knows
1171
             which name is this PHI node replacing.  If VAR is a
1172
             symbol marked for renaming, this is not necessary, the
1173
             renamer will use the symbol on the LHS to get its
1174
             reaching definition.  */
1175
          FOR_EACH_EDGE (e, ei, bb->preds)
1176
            add_phi_arg (phi, var, e);
1177
        }
1178
      else
1179
        {
1180
          tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
1181
          phi = create_phi_node (sym, bb);
1182
        }
1183
 
1184
      /* Mark this PHI node as interesting for update_ssa.  */
1185
      REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
1186
      mark_phi_for_rewrite (bb, phi);
1187
    }
1188
}
1189
 
1190
 
1191
/* Insert PHI nodes at the dominance frontier of blocks with variable
1192
   definitions.  DFS contains the dominance frontier information for
1193
   the flowgraph.  PHI nodes will only be inserted at the dominance
1194
   frontier of definition blocks for variables whose NEED_PHI_STATE
1195
   annotation is marked as ``maybe'' or ``unknown'' (computed by
1196
   mark_def_sites).  */
1197
 
1198
static void
1199
insert_phi_nodes (bitmap *dfs)
1200
{
1201
  referenced_var_iterator rvi;
1202
  tree var;
1203
 
1204
  timevar_push (TV_TREE_INSERT_PHI_NODES);
1205
 
1206
  FOR_EACH_REFERENCED_VAR (var, rvi)
1207
    {
1208
      struct def_blocks_d *def_map;
1209
      bitmap idf;
1210
 
1211
      def_map = find_def_blocks_for (var);
1212
      if (def_map == NULL)
1213
        continue;
1214
 
1215
      if (get_phi_state (var) != NEED_PHI_STATE_NO)
1216
        {
1217
          idf = find_idf (def_map->def_blocks, dfs);
1218
          insert_phi_nodes_for (var, idf, false);
1219
          BITMAP_FREE (idf);
1220
        }
1221
    }
1222
 
1223
  timevar_pop (TV_TREE_INSERT_PHI_NODES);
1224
}
1225
 
1226
 
1227
/* Register DEF (an SSA_NAME) to be a new definition for its underlying
1228
   variable (SSA_NAME_VAR (DEF)) and push VAR's current reaching definition
1229
   into the stack pointed to by BLOCK_DEFS_P.  */
1230
 
1231
void
1232
register_new_def (tree def, VEC(tree,heap) **block_defs_p)
1233
{
1234
  tree var = SSA_NAME_VAR (def);
1235
  tree currdef;
1236
 
1237
  /* If this variable is set in a single basic block and all uses are
1238
     dominated by the set(s) in that single basic block, then there is
1239
     no reason to record anything for this variable in the block local
1240
     definition stacks.  Doing so just wastes time and memory.
1241
 
1242
     This is the same test to prune the set of variables which may
1243
     need PHI nodes.  So we just use that information since it's already
1244
     computed and available for us to use.  */
1245
  if (get_phi_state (var) == NEED_PHI_STATE_NO)
1246
    {
1247
      set_current_def (var, def);
1248
      return;
1249
    }
1250
 
1251
  currdef = get_current_def (var);
1252
 
1253
  /* Push the current reaching definition into *BLOCK_DEFS_P.  This stack is
1254
     later used by the dominator tree callbacks to restore the reaching
1255
     definitions for all the variables defined in the block after a recursive
1256
     visit to all its immediately dominated blocks.  If there is no current
1257
     reaching definition, then just record the underlying _DECL node.  */
1258
  VEC_safe_push (tree, heap, *block_defs_p, currdef ? currdef : var);
1259
 
1260
  /* Set the current reaching definition for VAR to be DEF.  */
1261
  set_current_def (var, def);
1262
}
1263
 
1264
 
1265
/* Perform a depth-first traversal of the dominator tree looking for
1266
   variables to rename.  BB is the block where to start searching.
1267
   Renaming is a five step process:
1268
 
1269
   1- Every definition made by PHI nodes at the start of the blocks is
1270
      registered as the current definition for the corresponding variable.
1271
 
1272
   2- Every statement in BB is rewritten.  USE and VUSE operands are
1273
      rewritten with their corresponding reaching definition.  DEF and
1274
      VDEF targets are registered as new definitions.
1275
 
1276
   3- All the PHI nodes in successor blocks of BB are visited.  The
1277
      argument corresponding to BB is replaced with its current reaching
1278
      definition.
1279
 
1280
   4- Recursively rewrite every dominator child block of BB.
1281
 
1282
   5- Restore (in reverse order) the current reaching definition for every
1283
      new definition introduced in this block.  This is done so that when
1284
      we return from the recursive call, all the current reaching
1285
      definitions are restored to the names that were valid in the
1286
      dominator parent of BB.  */
1287
 
1288
/* SSA Rewriting Step 1.  Initialization, create a block local stack
1289
   of reaching definitions for new SSA names produced in this block
1290
   (BLOCK_DEFS).  Register new definitions for every PHI node in the
1291
   block.  */
1292
 
1293
static void
1294
rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1295
                          basic_block bb)
1296
{
1297
  tree phi;
1298
 
1299
  if (dump_file && (dump_flags & TDF_DETAILS))
1300
    fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
1301
 
1302
  /* Mark the unwind point for this block.  */
1303
  VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1304
 
1305
  /* Step 1.  Register new definitions for every PHI node in the block.
1306
     Conceptually, all the PHI nodes are executed in parallel and each PHI
1307
     node introduces a new version for the associated variable.  */
1308
  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1309
    {
1310
      tree result = PHI_RESULT (phi);
1311
      register_new_def (result, &block_defs_stack);
1312
    }
1313
}
1314
 
1315
 
1316
/* Return the current definition for variable VAR.  If none is found,
1317
   create a new SSA name to act as the zeroth definition for VAR.  If VAR
1318
   is call clobbered and there exists a more recent definition of
1319
   GLOBAL_VAR, return the definition for GLOBAL_VAR.  This means that VAR
1320
   has been clobbered by a function call since its last assignment.  */
1321
 
1322
static tree
1323
get_reaching_def (tree var)
1324
{
1325
  tree currdef_var, avar;
1326
 
1327
  /* Lookup the current reaching definition for VAR.  */
1328
  currdef_var = get_current_def (var);
1329
 
1330
  /* If there is no reaching definition for VAR, create and register a
1331
     default definition for it (if needed).  */
1332
  if (currdef_var == NULL_TREE)
1333
    {
1334
      avar = DECL_P (var) ? var : SSA_NAME_VAR (var);
1335
      currdef_var = get_default_def_for (avar);
1336
      set_current_def (var, currdef_var);
1337
    }
1338
 
1339
  /* Return the current reaching definition for VAR, or the default
1340
     definition, if we had to create one.  */
1341
  return currdef_var;
1342
}
1343
 
1344
 
1345
/* SSA Rewriting Step 2.  Rewrite every variable used in each statement in
1346
   the block with its immediate reaching definitions.  Update the current
1347
   definition of a variable when a new real or virtual definition is found.  */
1348
 
1349
static void
1350
rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1351
              basic_block bb ATTRIBUTE_UNUSED,
1352
              block_stmt_iterator si)
1353
{
1354
  tree stmt;
1355
  use_operand_p use_p;
1356
  def_operand_p def_p;
1357
  ssa_op_iter iter;
1358
 
1359
  stmt = bsi_stmt (si);
1360
 
1361
  /* If mark_def_sites decided that we don't need to rewrite this
1362
     statement, ignore it.  */
1363
  gcc_assert (blocks_to_update == NULL);
1364
  if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
1365
    return;
1366
 
1367
  if (dump_file && (dump_flags & TDF_DETAILS))
1368
    {
1369
      fprintf (dump_file, "Renaming statement ");
1370
      print_generic_stmt (dump_file, stmt, TDF_SLIM);
1371
      fprintf (dump_file, "\n");
1372
    }
1373
 
1374
  /* Step 1.  Rewrite USES and VUSES in the statement.  */
1375
  if (REWRITE_THIS_STMT (stmt))
1376
    FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1377
                              SSA_OP_ALL_USES|SSA_OP_ALL_KILLS)
1378
      {
1379
        tree var = USE_FROM_PTR (use_p);
1380
        gcc_assert (DECL_P (var));
1381
        SET_USE (use_p, get_reaching_def (var));
1382
      }
1383
 
1384
  /* Step 2.  Register the statement's DEF and VDEF operands.  */
1385
  if (REGISTER_DEFS_IN_THIS_STMT (stmt))
1386
    FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
1387
      {
1388
        tree var = DEF_FROM_PTR (def_p);
1389
        gcc_assert (DECL_P (var));
1390
        SET_DEF (def_p, make_ssa_name (var, stmt));
1391
        register_new_def (DEF_FROM_PTR (def_p), &block_defs_stack);
1392
      }
1393
}
1394
 
1395
 
1396
/* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
1397
   PHI nodes.  For every PHI node found, add a new argument containing the
1398
   current reaching definition for the variable and the edge through which
1399
   that definition is reaching the PHI node.  */
1400
 
1401
static void
1402
rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1403
                           basic_block bb)
1404
{
1405
  edge e;
1406
  edge_iterator ei;
1407
 
1408
  FOR_EACH_EDGE (e, ei, bb->succs)
1409
    {
1410
      tree phi;
1411
 
1412
      for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
1413
        {
1414
          tree currdef;
1415
          currdef = get_reaching_def (SSA_NAME_VAR (PHI_RESULT (phi)));
1416
          add_phi_arg (phi, currdef, e);
1417
        }
1418
    }
1419
}
1420
 
1421
 
1422
/* Called after visiting basic block BB.  Restore CURRDEFS to its
1423
   original value.  */
1424
 
1425
static void
1426
rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1427
                        basic_block bb ATTRIBUTE_UNUSED)
1428
{
1429
  /* Restore CURRDEFS to its original state.  */
1430
  while (VEC_length (tree, block_defs_stack) > 0)
1431
    {
1432
      tree tmp = VEC_pop (tree, block_defs_stack);
1433
      tree saved_def, var;
1434
 
1435
      if (tmp == NULL_TREE)
1436
        break;
1437
 
1438
      /* If we recorded an SSA_NAME, then make the SSA_NAME the current
1439
         definition of its underlying variable.  If we recorded anything
1440
         else, it must have been an _DECL node and its current reaching
1441
         definition must have been NULL.  */
1442
      if (TREE_CODE (tmp) == SSA_NAME)
1443
        {
1444
          saved_def = tmp;
1445
          var = SSA_NAME_VAR (saved_def);
1446
        }
1447
      else
1448
        {
1449
          saved_def = NULL;
1450
          var = tmp;
1451
        }
1452
 
1453
      set_current_def (var, saved_def);
1454
    }
1455
}
1456
 
1457
 
1458
/* Dump SSA information to FILE.  */
1459
 
1460
void
1461
dump_tree_ssa (FILE *file)
1462
{
1463
  basic_block bb;
1464
  const char *funcname
1465
    = lang_hooks.decl_printable_name (current_function_decl, 2);
1466
 
1467
  fprintf (file, "SSA information for %s\n\n", funcname);
1468
 
1469
  FOR_EACH_BB (bb)
1470
    {
1471
      dump_bb (bb, file, 0);
1472
      fputs ("    ", file);
1473
      print_generic_stmt (file, phi_nodes (bb), dump_flags);
1474
      fputs ("\n\n", file);
1475
    }
1476
}
1477
 
1478
 
1479
/* Dump SSA information to stderr.  */
1480
 
1481
void
1482
debug_tree_ssa (void)
1483
{
1484
  dump_tree_ssa (stderr);
1485
}
1486
 
1487
 
1488
/* Dump statistics for the hash table HTAB.  */
1489
 
1490
static void
1491
htab_statistics (FILE *file, htab_t htab)
1492
{
1493
  fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
1494
           (long) htab_size (htab),
1495
           (long) htab_elements (htab),
1496
           htab_collisions (htab));
1497
}
1498
 
1499
 
1500
/* Dump SSA statistics on FILE.  */
1501
 
1502
void
1503
dump_tree_ssa_stats (FILE *file)
1504
{
1505
  fprintf (file, "\nHash table statistics:\n");
1506
 
1507
  fprintf (file, "    def_blocks: ");
1508
  htab_statistics (file, def_blocks);
1509
 
1510
  fprintf (file, "\n");
1511
}
1512
 
1513
 
1514
/* Dump SSA statistics on stderr.  */
1515
 
1516
void
1517
debug_tree_ssa_stats (void)
1518
{
1519
  dump_tree_ssa_stats (stderr);
1520
}
1521
 
1522
 
1523
/* Hashing and equality functions for DEF_BLOCKS.  */
1524
 
1525
static hashval_t
1526
def_blocks_hash (const void *p)
1527
{
1528
  return htab_hash_pointer
1529
        ((const void *)((const struct def_blocks_d *)p)->var);
1530
}
1531
 
1532
static int
1533
def_blocks_eq (const void *p1, const void *p2)
1534
{
1535
  return ((const struct def_blocks_d *)p1)->var
1536
         == ((const struct def_blocks_d *)p2)->var;
1537
}
1538
 
1539
 
1540
/* Free memory allocated by one entry in DEF_BLOCKS.  */
1541
 
1542
static void
1543
def_blocks_free (void *p)
1544
{
1545
  struct def_blocks_d *entry = (struct def_blocks_d *) p;
1546
  BITMAP_FREE (entry->def_blocks);
1547
  BITMAP_FREE (entry->phi_blocks);
1548
  BITMAP_FREE (entry->livein_blocks);
1549
  free (entry);
1550
}
1551
 
1552
 
1553
/* Callback for htab_traverse to dump the DEF_BLOCKS hash table.  */
1554
 
1555
static int
1556
debug_def_blocks_r (void **slot, void *data ATTRIBUTE_UNUSED)
1557
{
1558
  struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
1559
 
1560
  fprintf (stderr, "VAR: ");
1561
  print_generic_expr (stderr, db_p->var, dump_flags);
1562
  bitmap_print (stderr, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
1563
  bitmap_print (stderr, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}\n");
1564
 
1565
  return 1;
1566
}
1567
 
1568
 
1569
/* Dump the DEF_BLOCKS hash table on stderr.  */
1570
 
1571
void
1572
debug_def_blocks (void)
1573
{
1574
  htab_traverse (def_blocks, debug_def_blocks_r, NULL);
1575
}
1576
 
1577
 
1578
/* Register NEW_NAME to be the new reaching definition for OLD_NAME.  */
1579
 
1580
static inline void
1581
register_new_update_single (tree new_name, tree old_name)
1582
{
1583
  tree currdef = get_current_def (old_name);
1584
 
1585
  /* Push the current reaching definition into *BLOCK_DEFS_P.
1586
     This stack is later used by the dominator tree callbacks to
1587
     restore the reaching definitions for all the variables
1588
     defined in the block after a recursive visit to all its
1589
     immediately dominated blocks.  */
1590
  VEC_reserve (tree, heap, block_defs_stack, 2);
1591
  VEC_quick_push (tree, block_defs_stack, currdef);
1592
  VEC_quick_push (tree, block_defs_stack, old_name);
1593
 
1594
  /* Set the current reaching definition for OLD_NAME to be
1595
     NEW_NAME.  */
1596
  set_current_def (old_name, new_name);
1597
}
1598
 
1599
 
1600
/* Register NEW_NAME to be the new reaching definition for all the
1601
   names in OLD_NAMES.  Used by the incremental SSA update routines to
1602
   replace old SSA names with new ones.  */
1603
 
1604
static inline void
1605
register_new_update_set (tree new_name, bitmap old_names)
1606
{
1607
  bitmap_iterator bi;
1608
  unsigned i;
1609
 
1610
  EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
1611
    register_new_update_single (new_name, ssa_name (i));
1612
}
1613
 
1614
 
1615
/* Initialization of block data structures for the incremental SSA
1616
   update pass.  Create a block local stack of reaching definitions
1617
   for new SSA names produced in this block (BLOCK_DEFS).  Register
1618
   new definitions for every PHI node in the block.  */
1619
 
1620
static void
1621
rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1622
                           basic_block bb)
1623
{
1624
  edge e;
1625
  edge_iterator ei;
1626
  tree phi;
1627
  bool is_abnormal_phi;
1628
 
1629
  if (dump_file && (dump_flags & TDF_DETAILS))
1630
    fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
1631
             bb->index);
1632
 
1633
  /* Mark the unwind point for this block.  */
1634
  VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
1635
 
1636
  if (!bitmap_bit_p (blocks_to_update, bb->index))
1637
    return;
1638
 
1639
  /* Mark the LHS if any of the arguments flows through an abnormal
1640
     edge.  */
1641
  is_abnormal_phi = false;
1642
  FOR_EACH_EDGE (e, ei, bb->preds)
1643
    if (e->flags & EDGE_ABNORMAL)
1644
      {
1645
        is_abnormal_phi = true;
1646
        break;
1647
      }
1648
 
1649
  /* If any of the PHI nodes is a replacement for a name in
1650
     OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
1651
     register it as a new definition for its corresponding name.  Also
1652
     register definitions for names whose underlying symbols are
1653
     marked for renaming.  */
1654
 
1655
  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1656
    {
1657
      tree lhs, lhs_sym;
1658
 
1659
      if (!REGISTER_DEFS_IN_THIS_STMT (phi))
1660
        continue;
1661
 
1662
      lhs = PHI_RESULT (phi);
1663
      lhs_sym = SSA_NAME_VAR (lhs);
1664
 
1665
      if (symbol_marked_for_renaming (lhs_sym))
1666
        register_new_update_single (lhs, lhs_sym);
1667
      else
1668
        {
1669
          /* If LHS is a new name, register a new definition for all
1670
             the names replaced by LHS.  */
1671
          if (is_new_name (lhs))
1672
            register_new_update_set (lhs, names_replaced_by (lhs));
1673
 
1674
          /* If LHS is an OLD name, register it as a new definition
1675
             for itself.  */
1676
          if (is_old_name (lhs))
1677
            register_new_update_single (lhs, lhs);
1678
        }
1679
 
1680
      if (is_abnormal_phi)
1681
        SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
1682
    }
1683
}
1684
 
1685
 
1686
/* Called after visiting block BB.  Unwind BLOCK_DEFS_STACK to restore
1687
   the current reaching definition of every name re-written in BB to
1688
   the original reaching definition before visiting BB.  This
1689
   unwinding must be done in the opposite order to what is done in
1690
   register_new_update_set.  */
1691
 
1692
static void
1693
rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1694
                           basic_block bb ATTRIBUTE_UNUSED)
1695
{
1696
  while (VEC_length (tree, block_defs_stack) > 0)
1697
    {
1698
      tree var = VEC_pop (tree, block_defs_stack);
1699
      tree saved_def;
1700
 
1701
      /* NULL indicates the unwind stop point for this block (see
1702
         rewrite_update_init_block).  */
1703
      if (var == NULL)
1704
        return;
1705
 
1706
      saved_def = VEC_pop (tree, block_defs_stack);
1707
      set_current_def (var, saved_def);
1708
    }
1709
}
1710
 
1711
 
1712
/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
1713
   it is a symbol marked for renaming, replace it with USE_P's current
1714
   reaching definition.  */
1715
 
1716
static inline void
1717
maybe_replace_use (use_operand_p use_p)
1718
{
1719
  tree rdef = NULL_TREE;
1720
  tree use = USE_FROM_PTR (use_p);
1721
  tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
1722
 
1723
  if (symbol_marked_for_renaming (sym))
1724
    rdef = get_reaching_def (sym);
1725
  else if (is_old_name (use))
1726
    rdef = get_reaching_def (use);
1727
 
1728
  if (rdef && rdef != use)
1729
    SET_USE (use_p, rdef);
1730
}
1731
 
1732
 
1733
/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
1734
   or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
1735
   register it as the current definition for the names replaced by
1736
   DEF_P.  */
1737
 
1738
static inline void
1739
maybe_register_def (def_operand_p def_p, tree stmt)
1740
{
1741
  tree def = DEF_FROM_PTR (def_p);
1742
  tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
1743
 
1744
  /* If DEF is a naked symbol that needs renaming, create a
1745
     new name for it.  */
1746
  if (symbol_marked_for_renaming (sym))
1747
    {
1748
      if (DECL_P (def))
1749
        {
1750
          def = make_ssa_name (def, stmt);
1751
          SET_DEF (def_p, def);
1752
        }
1753
 
1754
      register_new_update_single (def, sym);
1755
    }
1756
  else
1757
    {
1758
      /* If DEF is a new name, register it as a new definition
1759
         for all the names replaced by DEF.  */
1760
      if (is_new_name (def))
1761
        register_new_update_set (def, names_replaced_by (def));
1762
 
1763
      /* If DEF is an old name, register DEF as a new
1764
         definition for itself.  */
1765
      if (is_old_name (def))
1766
        register_new_update_single (def, def);
1767
    }
1768
}
1769
 
1770
 
1771
/* Update every variable used in the statement pointed-to by SI.  The
1772
   statement is assumed to be in SSA form already.  Names in
1773
   OLD_SSA_NAMES used by SI will be updated to their current reaching
1774
   definition.  Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
1775
   will be registered as a new definition for their corresponding name
1776
   in OLD_SSA_NAMES.  */
1777
 
1778
static void
1779
rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1780
                     basic_block bb ATTRIBUTE_UNUSED,
1781
                     block_stmt_iterator si)
1782
{
1783
  stmt_ann_t ann;
1784
  tree stmt;
1785
  use_operand_p use_p;
1786
  def_operand_p def_p;
1787
  ssa_op_iter iter;
1788
 
1789
  stmt = bsi_stmt (si);
1790
  ann = stmt_ann (stmt);
1791
 
1792
  gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
1793
 
1794
  /* Only update marked statements.  */
1795
  if (!REWRITE_THIS_STMT (stmt) && !REGISTER_DEFS_IN_THIS_STMT (stmt))
1796
    return;
1797
 
1798
  if (dump_file && (dump_flags & TDF_DETAILS))
1799
    {
1800
      fprintf (dump_file, "Updating SSA information for statement ");
1801
      print_generic_stmt (dump_file, stmt, TDF_SLIM);
1802
      fprintf (dump_file, "\n");
1803
    }
1804
 
1805
  /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
1806
     symbol is marked for renaming.  */
1807
  if (REWRITE_THIS_STMT (stmt))
1808
    {
1809
      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1810
        maybe_replace_use (use_p);
1811
 
1812
      if (need_to_update_vops_p)
1813
        FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
1814
                                  SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
1815
          maybe_replace_use (use_p);
1816
    }
1817
 
1818
  /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
1819
     Also register definitions for names whose underlying symbol is
1820
     marked for renaming.  */
1821
  if (REGISTER_DEFS_IN_THIS_STMT (stmt))
1822
    {
1823
      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1824
        maybe_register_def (def_p, stmt);
1825
 
1826
      if (need_to_update_vops_p)
1827
        FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
1828
          maybe_register_def (def_p, stmt);
1829
    }
1830
}
1831
 
1832
 
1833
/* Replace the operand pointed to by USE_P with USE's current reaching
1834
   definition.  */
1835
 
1836
static inline void
1837
replace_use (use_operand_p use_p, tree use)
1838
{
1839
  tree rdef = get_reaching_def (use);
1840
  if (rdef != use)
1841
    SET_USE (use_p, rdef);
1842
}
1843
 
1844
 
1845
/* Visit all the successor blocks of BB looking for PHI nodes.  For
1846
   every PHI node found, check if any of its arguments is in
1847
   OLD_SSA_NAMES.  If so, and if the argument has a current reaching
1848
   definition, replace it.  */
1849
 
1850
static void
1851
rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
1852
                              basic_block bb)
1853
{
1854
  edge e;
1855
  edge_iterator ei;
1856
  unsigned i;
1857
 
1858
  FOR_EACH_EDGE (e, ei, bb->succs)
1859
    {
1860
      tree phi;
1861
      tree_vec phis;
1862
 
1863
      if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
1864
        continue;
1865
 
1866
      phis = VEC_index (tree_vec, phis_to_rewrite, e->dest->index);
1867
      for (i = 0; VEC_iterate (tree, phis, i, phi); i++)
1868
        {
1869
          tree arg;
1870
          use_operand_p arg_p;
1871
 
1872
          gcc_assert (REWRITE_THIS_STMT (phi));
1873
 
1874
          arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
1875
          arg = USE_FROM_PTR (arg_p);
1876
 
1877
          if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
1878
            continue;
1879
 
1880
          if (arg == NULL_TREE)
1881
            {
1882
              /* When updating a PHI node for a recently introduced
1883
                 symbol we may find NULL arguments.  That's why we
1884
                 take the symbol from the LHS of the PHI node.  */
1885
              replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi)));
1886
            }
1887
          else
1888
            {
1889
              tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
1890
 
1891
              if (symbol_marked_for_renaming (sym))
1892
                replace_use (arg_p, sym);
1893
              else if (is_old_name (arg))
1894
                replace_use (arg_p, arg);
1895
            }
1896
 
1897
          if (e->flags & EDGE_ABNORMAL)
1898
            SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
1899
        }
1900
    }
1901
}
1902
 
1903
 
1904
/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
1905
   form.
1906
 
1907
   ENTRY indicates the block where to start.  Every block dominated by
1908
      ENTRY will be rewritten.
1909
 
1910
   WHAT indicates what actions will be taken by the renamer (see enum
1911
      rewrite_mode).
1912
 
1913
   BLOCKS are the set of interesting blocks for the dominator walker
1914
      to process.  If this set is NULL, then all the nodes dominated
1915
      by ENTRY are walked.  Otherwise, blocks dominated by ENTRY that
1916
      are not present in BLOCKS are ignored.  */
1917
 
1918
static void
1919
rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
1920
{
1921
  struct dom_walk_data walk_data;
1922
 
1923
  /* Rewrite all the basic blocks in the program.  */
1924
  timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
1925
 
1926
  /* Setup callbacks for the generic dominator tree walker.  */
1927
  memset (&walk_data, 0, sizeof (walk_data));
1928
 
1929
  walk_data.dom_direction = CDI_DOMINATORS;
1930
  walk_data.interesting_blocks = blocks;
1931
 
1932
  if (what == REWRITE_UPDATE)
1933
    walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
1934
  else
1935
    walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
1936
 
1937
  if (what == REWRITE_ALL)
1938
    walk_data.before_dom_children_walk_stmts = rewrite_stmt;
1939
  else if (what == REWRITE_UPDATE)
1940
    walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
1941
  else
1942
    gcc_unreachable ();
1943
 
1944
  if (what == REWRITE_ALL)
1945
    walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
1946
  else if (what == REWRITE_UPDATE)
1947
    walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
1948
  else
1949
    gcc_unreachable ();
1950
 
1951
  if (what == REWRITE_ALL)
1952
    walk_data.after_dom_children_after_stmts =  rewrite_finalize_block;
1953
  else if (what == REWRITE_UPDATE)
1954
    walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
1955
  else
1956
    gcc_unreachable ();
1957
 
1958
  block_defs_stack = VEC_alloc (tree, heap, 10);
1959
 
1960
  /* Initialize the dominator walker.  */
1961
  init_walk_dominator_tree (&walk_data);
1962
 
1963
  /* Recursively walk the dominator tree rewriting each statement in
1964
     each basic block.  */
1965
  walk_dominator_tree (&walk_data, entry);
1966
 
1967
  /* Finalize the dominator walker.  */
1968
  fini_walk_dominator_tree (&walk_data);
1969
 
1970
  /* Debugging dumps.  */
1971
  if (dump_file && (dump_flags & TDF_STATS))
1972
    {
1973
      dump_dfa_stats (dump_file);
1974
      if (def_blocks)
1975
        dump_tree_ssa_stats (dump_file);
1976
    }
1977
 
1978
  if (def_blocks)
1979
    {
1980
      htab_delete (def_blocks);
1981
      def_blocks = NULL;
1982
    }
1983
 
1984
  VEC_free (tree, heap, block_defs_stack);
1985
 
1986
  timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
1987
}
1988
 
1989
 
1990
/* Block initialization routine for mark_def_sites.  Clear the
1991
   KILLS bitmap at the start of each block.  */
1992
 
1993
static void
1994
mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
1995
                                 basic_block bb ATTRIBUTE_UNUSED)
1996
{
1997
  struct mark_def_sites_global_data *gd =
1998
     (struct mark_def_sites_global_data *) walk_data->global_data;
1999
  bitmap kills = gd->kills;
2000
  bitmap_clear (kills);
2001
}
2002
 
2003
 
2004
/* Mark the definition site blocks for each variable, so that we know
2005
   where the variable is actually live.
2006
 
2007
   INTERESTING_BLOCKS will be filled in with all the blocks that
2008
      should be processed by the renamer.  It is assumed to be
2009
      initialized and zeroed by the caller.  */
2010
 
2011
static void
2012
mark_def_site_blocks (sbitmap interesting_blocks)
2013
{
2014
  struct dom_walk_data walk_data;
2015
  struct mark_def_sites_global_data mark_def_sites_global_data;
2016
  referenced_var_iterator rvi;
2017
  tree var;
2018
 
2019
  /* Allocate memory for the DEF_BLOCKS hash table.  */
2020
  def_blocks = htab_create (num_referenced_vars,
2021
                            def_blocks_hash, def_blocks_eq, def_blocks_free);
2022
  FOR_EACH_REFERENCED_VAR(var, rvi)
2023
    set_current_def (var, NULL_TREE);
2024
 
2025
  /* Setup callbacks for the generic dominator tree walker to find and
2026
     mark definition sites.  */
2027
  walk_data.walk_stmts_backward = false;
2028
  walk_data.dom_direction = CDI_DOMINATORS;
2029
  walk_data.initialize_block_local_data = NULL;
2030
  walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
2031
  walk_data.before_dom_children_walk_stmts = mark_def_sites;
2032
  walk_data.before_dom_children_after_stmts = NULL;
2033
  walk_data.after_dom_children_before_stmts =  NULL;
2034
  walk_data.after_dom_children_walk_stmts =  NULL;
2035
  walk_data.after_dom_children_after_stmts =  NULL;
2036
  walk_data.interesting_blocks = NULL;
2037
 
2038
  /* Notice that this bitmap is indexed using variable UIDs, so it must be
2039
     large enough to accommodate all the variables referenced in the
2040
     function, not just the ones we are renaming.  */
2041
  mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
2042
 
2043
  /* Create the set of interesting blocks that will be filled by
2044
     mark_def_sites.  */
2045
  mark_def_sites_global_data.interesting_blocks = interesting_blocks;
2046
  walk_data.global_data = &mark_def_sites_global_data;
2047
 
2048
  /* We do not have any local data.  */
2049
  walk_data.block_local_data_size = 0;
2050
 
2051
  /* Initialize the dominator walker.  */
2052
  init_walk_dominator_tree (&walk_data);
2053
 
2054
  /* Recursively walk the dominator tree.  */
2055
  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
2056
 
2057
  /* Finalize the dominator walker.  */
2058
  fini_walk_dominator_tree (&walk_data);
2059
 
2060
  /* We no longer need this bitmap, clear and free it.  */
2061
  BITMAP_FREE (mark_def_sites_global_data.kills);
2062
}
2063
 
2064
 
2065
/* Main entry point into the SSA builder.  The renaming process
2066
   proceeds in four main phases:
2067
 
2068
   1- Compute dominance frontier and immediate dominators, needed to
2069
      insert PHI nodes and rename the function in dominator tree
2070
      order.
2071
 
2072
   2- Find and mark all the blocks that define variables
2073
      (mark_def_site_blocks).
2074
 
2075
   3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
2076
 
2077
   4- Rename all the blocks (rewrite_blocks) and statements in the program.
2078
 
2079
   Steps 3 and 4 are done using the dominator tree walker
2080
   (walk_dominator_tree).  */
2081
 
2082
static unsigned int
2083
rewrite_into_ssa (void)
2084
{
2085
  bitmap *dfs;
2086
  basic_block bb;
2087
  sbitmap interesting_blocks;
2088
 
2089
  timevar_push (TV_TREE_SSA_OTHER);
2090
 
2091
  /* Initialize operand data structures.  */
2092
  init_ssa_operands ();
2093
 
2094
  /* Initialize the set of interesting blocks.  The callback
2095
     mark_def_sites will add to this set those blocks that the renamer
2096
     should process.  */
2097
  interesting_blocks = sbitmap_alloc (last_basic_block);
2098
  sbitmap_zero (interesting_blocks);
2099
 
2100
  /* Initialize dominance frontier.  */
2101
  dfs = (bitmap *) xmalloc (last_basic_block * sizeof (bitmap));
2102
  FOR_EACH_BB (bb)
2103
    dfs[bb->index] = BITMAP_ALLOC (NULL);
2104
 
2105
  /* 1- Compute dominance frontiers.  */
2106
  calculate_dominance_info (CDI_DOMINATORS);
2107
  compute_dominance_frontiers (dfs);
2108
 
2109
  /* 2- Find and mark definition sites.  */
2110
  mark_def_site_blocks (interesting_blocks);
2111
 
2112
  /* 3- Insert PHI nodes at dominance frontiers of definition blocks.  */
2113
  insert_phi_nodes (dfs);
2114
 
2115
  /* 4- Rename all the blocks.  */
2116
  rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
2117
 
2118
  /* Free allocated memory.  */
2119
  FOR_EACH_BB (bb)
2120
    BITMAP_FREE (dfs[bb->index]);
2121
  free (dfs);
2122
  sbitmap_free (interesting_blocks);
2123
 
2124
  timevar_pop (TV_TREE_SSA_OTHER);
2125
  in_ssa_p = true;
2126
  return 0;
2127
}
2128
 
2129
 
2130
struct tree_opt_pass pass_build_ssa =
2131
{
2132
  "ssa",                                /* name */
2133
  NULL,                                 /* gate */
2134
  rewrite_into_ssa,                     /* execute */
2135
  NULL,                                 /* sub */
2136
  NULL,                                 /* next */
2137
  0,                                     /* static_pass_number */
2138
  0,                                     /* tv_id */
2139
  PROP_cfg | PROP_referenced_vars,      /* properties_required */
2140
  PROP_ssa,                             /* properties_provided */
2141
  0,                                     /* properties_destroyed */
2142
  0,                                     /* todo_flags_start */
2143
  TODO_dump_func
2144
    | TODO_verify_ssa
2145
    | TODO_remove_unused_locals,        /* todo_flags_finish */
2146
 
2147
};
2148
 
2149
 
2150
/* Mark the definition of VAR at STMT and BB as interesting for the
2151
   renamer.  BLOCKS is the set of blocks that need updating.  */
2152
 
2153
static void
2154
mark_def_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
2155
{
2156
  gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
2157
  REGISTER_DEFS_IN_THIS_STMT (stmt) = 1;
2158
 
2159
  if (insert_phi_p)
2160
    {
2161
      bool is_phi_p = TREE_CODE (stmt) == PHI_NODE;
2162
 
2163
      set_def_block (var, bb, is_phi_p);
2164
 
2165
      /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
2166
         site for both itself and all the old names replaced by it.  */
2167
      if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
2168
        {
2169
          bitmap_iterator bi;
2170
          unsigned i;
2171
          bitmap set = names_replaced_by (var);
2172
          if (set)
2173
            EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2174
              set_def_block (ssa_name (i), bb, is_phi_p);
2175
        }
2176
    }
2177
}
2178
 
2179
 
2180
/* Mark the use of VAR at STMT and BB as interesting for the
2181
   renamer.  INSERT_PHI_P is true if we are going to insert new PHI
2182
   nodes.  */
2183
 
2184
static inline void
2185
mark_use_interesting (tree var, tree stmt, basic_block bb, bool insert_phi_p)
2186
{
2187
  basic_block def_bb = bb_for_stmt (stmt);
2188
 
2189
  mark_block_for_update (def_bb);
2190
  mark_block_for_update (bb);
2191
 
2192
  if (TREE_CODE (stmt) == PHI_NODE)
2193
    mark_phi_for_rewrite (def_bb, stmt);
2194
  else
2195
    REWRITE_THIS_STMT (stmt) = 1;
2196
 
2197
  /* If VAR has not been defined in BB, then it is live-on-entry
2198
     to BB.  Note that we cannot just use the block holding VAR's
2199
     definition because if VAR is one of the names in OLD_SSA_NAMES,
2200
     it will have several definitions (itself and all the names that
2201
     replace it).  */
2202
  if (insert_phi_p)
2203
    {
2204
      struct def_blocks_d *db_p = get_def_blocks_for (var);
2205
      if (!bitmap_bit_p (db_p->def_blocks, bb->index))
2206
        set_livein_block (var, bb);
2207
    }
2208
}
2209
 
2210
 
2211
/* Do a dominator walk starting at BB processing statements that
2212
   reference symbols in SYMS_TO_RENAME.  This is very similar to
2213
   mark_def_sites, but the scan handles statements whose operands may
2214
   already be SSA names.
2215
 
2216
   If INSERT_PHI_P is true, mark those uses as live in the
2217
   corresponding block.  This is later used by the PHI placement
2218
   algorithm to make PHI pruning decisions.  */
2219
 
2220
static void
2221
prepare_block_for_update (basic_block bb, bool insert_phi_p)
2222
{
2223
  basic_block son;
2224
  block_stmt_iterator si;
2225
  tree phi;
2226
  edge e;
2227
  edge_iterator ei;
2228
 
2229
  mark_block_for_update (bb);
2230
 
2231
  /* Process PHI nodes marking interesting those that define or use
2232
     the symbols that we are interested in.  */
2233
  for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2234
    {
2235
      tree lhs_sym, lhs = PHI_RESULT (phi);
2236
 
2237
      lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
2238
 
2239
      if (!symbol_marked_for_renaming (lhs_sym))
2240
        continue;
2241
      mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
2242
 
2243
      /* Mark the uses in phi nodes as interesting.  It would be more correct
2244
         to process the arguments of the phi nodes of the successor edges of
2245
         BB at the end of prepare_block_for_update, however, that turns out
2246
         to be significantly more expensive.  Doing it here is conservatively
2247
         correct -- it may only cause us to believe a value to be live in a
2248
         block that also contains its definition, and thus insert a few more
2249
         phi nodes for it.  */
2250
      FOR_EACH_EDGE (e, ei, bb->preds)
2251
        {
2252
          mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
2253
        }
2254
    }
2255
 
2256
  /* Process the statements.  */
2257
  for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
2258
    {
2259
      tree stmt;
2260
      ssa_op_iter i;
2261
      use_operand_p use_p;
2262
      def_operand_p def_p;
2263
 
2264
      stmt = bsi_stmt (si);
2265
 
2266
      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
2267
        {
2268
          tree use = USE_FROM_PTR (use_p);
2269
          tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2270
          if (symbol_marked_for_renaming (sym))
2271
            mark_use_interesting (use, stmt, bb, insert_phi_p);
2272
        }
2273
 
2274
      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
2275
        {
2276
          tree def = DEF_FROM_PTR (def_p);
2277
          tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2278
 
2279
          if (symbol_marked_for_renaming (sym))
2280
            mark_def_interesting (def, stmt, bb, insert_phi_p);
2281
        }
2282
 
2283
      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_VIRTUAL_DEFS)
2284
        {
2285
          tree def = DEF_FROM_PTR (def_p);
2286
          tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
2287
 
2288
          if (symbol_marked_for_renaming (sym))
2289
            {
2290
              mark_use_interesting (sym, stmt, bb, insert_phi_p);
2291
              mark_def_interesting (sym, stmt, bb, insert_phi_p);
2292
            }
2293
        }
2294
 
2295
      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_VUSE)
2296
        {
2297
          tree use = USE_FROM_PTR (use_p);
2298
          tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
2299
 
2300
          if (symbol_marked_for_renaming (sym))
2301
            mark_use_interesting (sym, stmt, bb, insert_phi_p);
2302
        }
2303
    }
2304
 
2305
  /* Now visit all the blocks dominated by BB.  */
2306
  for (son = first_dom_son (CDI_DOMINATORS, bb);
2307
      son;
2308
      son = next_dom_son (CDI_DOMINATORS, son))
2309
    prepare_block_for_update (son, insert_phi_p);
2310
}
2311
 
2312
 
2313
/* Helper for prepare_names_to_update.  Mark all the use sites for
2314
   NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
2315
   prepare_names_to_update.  */
2316
 
2317
static void
2318
prepare_use_sites_for (tree name, bool insert_phi_p)
2319
{
2320
  use_operand_p use_p;
2321
  imm_use_iterator iter;
2322
 
2323
  FOR_EACH_IMM_USE_FAST (use_p, iter, name)
2324
    {
2325
      tree stmt = USE_STMT (use_p);
2326
      basic_block bb = bb_for_stmt (stmt);
2327
 
2328
      if (TREE_CODE (stmt) == PHI_NODE)
2329
        {
2330
          int ix = PHI_ARG_INDEX_FROM_USE (use_p);
2331
          edge e = PHI_ARG_EDGE (stmt, ix);
2332
          mark_use_interesting (name, stmt, e->src, insert_phi_p);
2333
        }
2334
      else
2335
        {
2336
          /* For regular statements, mark this as an interesting use
2337
             for NAME.  */
2338
          mark_use_interesting (name, stmt, bb, insert_phi_p);
2339
        }
2340
    }
2341
}
2342
 
2343
 
2344
/* Helper for prepare_names_to_update.  Mark the definition site for
2345
   NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
2346
   prepare_names_to_update.  */
2347
 
2348
static void
2349
prepare_def_site_for (tree name, bool insert_phi_p)
2350
{
2351
  tree stmt;
2352
  basic_block bb;
2353
 
2354
  gcc_assert (names_to_release == NULL
2355
              || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
2356
 
2357
  stmt = SSA_NAME_DEF_STMT (name);
2358
  bb = bb_for_stmt (stmt);
2359
  if (bb)
2360
    {
2361
      gcc_assert (bb->index < last_basic_block);
2362
      mark_block_for_update (bb);
2363
      mark_def_interesting (name, stmt, bb, insert_phi_p);
2364
    }
2365
}
2366
 
2367
 
2368
/* Mark definition and use sites of names in NEW_SSA_NAMES and
2369
   OLD_SSA_NAMES.  INSERT_PHI_P is true if the caller wants to insert
2370
   PHI nodes for newly created names.  */
2371
 
2372
static void
2373
prepare_names_to_update (bool insert_phi_p)
2374
{
2375
  unsigned i = 0;
2376
  bitmap_iterator bi;
2377
  sbitmap_iterator sbi;
2378
 
2379
  /* If a name N from NEW_SSA_NAMES is also marked to be released,
2380
     remove it from NEW_SSA_NAMES so that we don't try to visit its
2381
     defining basic block (which most likely doesn't exist).  Notice
2382
     that we cannot do the same with names in OLD_SSA_NAMES because we
2383
     want to replace existing instances.  */
2384
  if (names_to_release)
2385
    EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2386
      RESET_BIT (new_ssa_names, i);
2387
 
2388
  /* First process names in NEW_SSA_NAMES.  Otherwise, uses of old
2389
     names may be considered to be live-in on blocks that contain
2390
     definitions for their replacements.  */
2391
  EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2392
    prepare_def_site_for (ssa_name (i), insert_phi_p);
2393
 
2394
  /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
2395
     OLD_SSA_NAMES, but we have to ignore its definition site.  */
2396
  EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2397
    {
2398
      if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
2399
        prepare_def_site_for (ssa_name (i), insert_phi_p);
2400
      prepare_use_sites_for (ssa_name (i), insert_phi_p);
2401
    }
2402
}
2403
 
2404
 
2405
/* Dump all the names replaced by NAME to FILE.  */
2406
 
2407
void
2408
dump_names_replaced_by (FILE *file, tree name)
2409
{
2410
  unsigned i;
2411
  bitmap old_set;
2412
  bitmap_iterator bi;
2413
 
2414
  print_generic_expr (file, name, 0);
2415
  fprintf (file, " -> { ");
2416
 
2417
  old_set = names_replaced_by (name);
2418
  EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
2419
    {
2420
      print_generic_expr (file, ssa_name (i), 0);
2421
      fprintf (file, " ");
2422
    }
2423
 
2424
  fprintf (file, "}\n");
2425
}
2426
 
2427
 
2428
/* Dump all the names replaced by NAME to stderr.  */
2429
 
2430
void
2431
debug_names_replaced_by (tree name)
2432
{
2433
  dump_names_replaced_by (stderr, name);
2434
}
2435
 
2436
 
2437
/* Dump SSA update information to FILE.  */
2438
 
2439
void
2440
dump_update_ssa (FILE *file)
2441
{
2442
  unsigned i = 0;
2443
  bitmap_iterator bi;
2444
 
2445
  if (!need_ssa_update_p ())
2446
    return;
2447
 
2448
  if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
2449
    {
2450
      sbitmap_iterator sbi;
2451
 
2452
      fprintf (file, "\nSSA replacement table\n");
2453
      fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
2454
                     "O_1, ..., O_j\n\n");
2455
 
2456
      EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2457
        dump_names_replaced_by (file, ssa_name (i));
2458
 
2459
      fprintf (file, "\n");
2460
      fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
2461
               update_ssa_stats.num_virtual_mappings);
2462
      fprintf (file, "Number of real NEW -> OLD mappings:    %7u\n",
2463
               update_ssa_stats.num_total_mappings
2464
               - update_ssa_stats.num_virtual_mappings);
2465
      fprintf (file, "Number of total NEW -> OLD mappings:   %7u\n",
2466
               update_ssa_stats.num_total_mappings);
2467
 
2468
      fprintf (file, "\nNumber of virtual symbols: %u\n",
2469
               update_ssa_stats.num_virtual_symbols);
2470
    }
2471
 
2472
  if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
2473
    {
2474
      fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
2475
      EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
2476
        {
2477
          print_generic_expr (file, referenced_var (i), 0);
2478
          fprintf (file, " ");
2479
        }
2480
    }
2481
 
2482
  if (names_to_release && !bitmap_empty_p (names_to_release))
2483
    {
2484
      fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
2485
      EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2486
        {
2487
          print_generic_expr (file, ssa_name (i), 0);
2488
          fprintf (file, " ");
2489
        }
2490
    }
2491
 
2492
  fprintf (file, "\n\n");
2493
}
2494
 
2495
 
2496
/* Dump SSA update information to stderr.  */
2497
 
2498
void
2499
debug_update_ssa (void)
2500
{
2501
  dump_update_ssa (stderr);
2502
}
2503
 
2504
 
2505
/* Initialize data structures used for incremental SSA updates.  */
2506
 
2507
static void
2508
init_update_ssa (void)
2509
{
2510
  /* Reserve more space than the current number of names.  The calls to
2511
     add_new_name_mapping are typically done after creating new SSA
2512
     names, so we'll need to reallocate these arrays.  */
2513
  old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2514
  sbitmap_zero (old_ssa_names);
2515
 
2516
  new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
2517
  sbitmap_zero (new_ssa_names);
2518
 
2519
  repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
2520
  need_to_initialize_update_ssa_p = false;
2521
  need_to_update_vops_p = false;
2522
  syms_to_rename = BITMAP_ALLOC (NULL);
2523
  names_to_release = NULL;
2524
  memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
2525
  update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
2526
}
2527
 
2528
 
2529
/* Deallocate data structures used for incremental SSA updates.  */
2530
 
2531
void
2532
delete_update_ssa (void)
2533
{
2534
  unsigned i;
2535
  bitmap_iterator bi;
2536
 
2537
  sbitmap_free (old_ssa_names);
2538
  old_ssa_names = NULL;
2539
 
2540
  sbitmap_free (new_ssa_names);
2541
  new_ssa_names = NULL;
2542
 
2543
  htab_delete (repl_tbl);
2544
  repl_tbl = NULL;
2545
 
2546
  need_to_initialize_update_ssa_p = true;
2547
  need_to_update_vops_p = false;
2548
  BITMAP_FREE (syms_to_rename);
2549
  BITMAP_FREE (update_ssa_stats.virtual_symbols);
2550
 
2551
  if (names_to_release)
2552
    {
2553
      EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
2554
        release_ssa_name (ssa_name (i));
2555
      BITMAP_FREE (names_to_release);
2556
    }
2557
 
2558
  clear_ssa_name_info ();
2559
}
2560
 
2561
 
2562
/* Create a new name for OLD_NAME in statement STMT and replace the
2563
   operand pointed to by DEF_P with the newly created name.  Return
2564
   the new name and register the replacement mapping <NEW, OLD> in
2565
   update_ssa's tables.  */
2566
 
2567
tree
2568
create_new_def_for (tree old_name, tree stmt, def_operand_p def)
2569
{
2570
  tree new_name = duplicate_ssa_name (old_name, stmt);
2571
 
2572
  SET_DEF (def, new_name);
2573
 
2574
  if (TREE_CODE (stmt) == PHI_NODE)
2575
    {
2576
      edge e;
2577
      edge_iterator ei;
2578
      basic_block bb = bb_for_stmt (stmt);
2579
 
2580
      /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
2581
      FOR_EACH_EDGE (e, ei, bb->preds)
2582
        if (e->flags & EDGE_ABNORMAL)
2583
          {
2584
            SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
2585
            break;
2586
          }
2587
    }
2588
 
2589
  register_new_name_mapping (new_name, old_name);
2590
 
2591
  /* For the benefit of passes that will be updating the SSA form on
2592
     their own, set the current reaching definition of OLD_NAME to be
2593
     NEW_NAME.  */
2594
  set_current_def (old_name, new_name);
2595
 
2596
  return new_name;
2597
}
2598
 
2599
 
2600
/* Register name NEW to be a replacement for name OLD.  This function
2601
   must be called for every replacement that should be performed by
2602
   update_ssa.  */
2603
 
2604
void
2605
register_new_name_mapping (tree new, tree old)
2606
{
2607
  if (need_to_initialize_update_ssa_p)
2608
    init_update_ssa ();
2609
 
2610
  add_new_name_mapping (new, old);
2611
}
2612
 
2613
 
2614
/* Register symbol SYM to be renamed by update_ssa.  */
2615
 
2616
void
2617
mark_sym_for_renaming (tree sym)
2618
{
2619
  if (need_to_initialize_update_ssa_p)
2620
    init_update_ssa ();
2621
 
2622
  bitmap_set_bit (syms_to_rename, DECL_UID (sym));
2623
 
2624
  if (!is_gimple_reg (sym))
2625
    need_to_update_vops_p = true;
2626
}
2627
 
2628
 
2629
/* Register all the symbols in SET to be renamed by update_ssa.  */
2630
 
2631
void
2632
mark_set_for_renaming (bitmap set)
2633
{
2634
  bitmap_iterator bi;
2635
  unsigned i;
2636
 
2637
  if (bitmap_empty_p (set))
2638
    return;
2639
 
2640
  if (need_to_initialize_update_ssa_p)
2641
    init_update_ssa ();
2642
 
2643
  bitmap_ior_into (syms_to_rename, set);
2644
 
2645
  EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
2646
    if (!is_gimple_reg (referenced_var (i)))
2647
      {
2648
        need_to_update_vops_p = true;
2649
        break;
2650
      }
2651
}
2652
 
2653
 
2654
/* Return true if there is any work to be done by update_ssa.  */
2655
 
2656
bool
2657
need_ssa_update_p (void)
2658
{
2659
  return syms_to_rename || old_ssa_names || new_ssa_names;
2660
}
2661
 
2662
 
2663
/* Return true if name N has been registered in the replacement table.  */
2664
 
2665
bool
2666
name_registered_for_update_p (tree n)
2667
{
2668
  if (!need_ssa_update_p ())
2669
    return false;
2670
 
2671
  return is_new_name (n)
2672
         || is_old_name (n)
2673
         || symbol_marked_for_renaming (SSA_NAME_VAR (n));
2674
}
2675
 
2676
 
2677
/* Return the set of all the SSA names marked to be replaced.  */
2678
 
2679
bitmap
2680
ssa_names_to_replace (void)
2681
{
2682
  unsigned i = 0;
2683
  bitmap ret;
2684
  sbitmap_iterator sbi;
2685
 
2686
  ret = BITMAP_ALLOC (NULL);
2687
  EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2688
    bitmap_set_bit (ret, i);
2689
 
2690
  return ret;
2691
}
2692
 
2693
 
2694
/* Mark NAME to be released after update_ssa has finished.  */
2695
 
2696
void
2697
release_ssa_name_after_update_ssa (tree name)
2698
{
2699
  gcc_assert (!need_to_initialize_update_ssa_p);
2700
 
2701
  if (names_to_release == NULL)
2702
    names_to_release = BITMAP_ALLOC (NULL);
2703
 
2704
  bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
2705
}
2706
 
2707
 
2708
/* Insert new PHI nodes to replace VAR.  DFS contains dominance
2709
   frontier information.  BLOCKS is the set of blocks to be updated.
2710
 
2711
   This is slightly different than the regular PHI insertion
2712
   algorithm.  The value of UPDATE_FLAGS controls how PHI nodes for
2713
   real names (i.e., GIMPLE registers) are inserted:
2714
 
2715
   - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
2716
     nodes inside the region affected by the block that defines VAR
2717
     and the blocks that define all its replacements.  All these
2718
     definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
2719
 
2720
     First, we compute the entry point to the region (ENTRY).  This is
2721
     given by the nearest common dominator to all the definition
2722
     blocks. When computing the iterated dominance frontier (IDF), any
2723
     block not strictly dominated by ENTRY is ignored.
2724
 
2725
     We then call the standard PHI insertion algorithm with the pruned
2726
     IDF.
2727
 
2728
   - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
2729
     names is not pruned.  PHI nodes are inserted at every IDF block.  */
2730
 
2731
static void
2732
insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
2733
                              unsigned update_flags)
2734
{
2735
  basic_block entry;
2736
  struct def_blocks_d *db;
2737
  bitmap idf, pruned_idf;
2738
  bitmap_iterator bi;
2739
  unsigned i;
2740
 
2741
#if defined ENABLE_CHECKING
2742
  if (TREE_CODE (var) == SSA_NAME)
2743
    gcc_assert (is_old_name (var));
2744
  else
2745
    gcc_assert (symbol_marked_for_renaming (var));
2746
#endif
2747
 
2748
  /* Get all the definition sites for VAR.  */
2749
  db = find_def_blocks_for (var);
2750
 
2751
  /* No need to do anything if there were no definitions to VAR.  */
2752
  if (db == NULL || bitmap_empty_p (db->def_blocks))
2753
    return;
2754
 
2755
  /* Compute the initial iterated dominance frontier.  */
2756
  idf = find_idf (db->def_blocks, dfs);
2757
  pruned_idf = BITMAP_ALLOC (NULL);
2758
 
2759
  if (TREE_CODE (var) == SSA_NAME)
2760
    {
2761
      if (update_flags == TODO_update_ssa)
2762
        {
2763
          /* If doing regular SSA updates for GIMPLE registers, we are
2764
             only interested in IDF blocks dominated by the nearest
2765
             common dominator of all the definition blocks.  */
2766
          entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
2767
                                                    db->def_blocks);
2768
 
2769
          if (entry != ENTRY_BLOCK_PTR)
2770
            EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
2771
              if (BASIC_BLOCK (i) != entry
2772
                  && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
2773
                bitmap_set_bit (pruned_idf, i);
2774
        }
2775
      else
2776
        {
2777
          /* Otherwise, do not prune the IDF for VAR.  */
2778
          gcc_assert (update_flags == TODO_update_ssa_full_phi);
2779
          bitmap_copy (pruned_idf, idf);
2780
        }
2781
    }
2782
  else
2783
    {
2784
      /* Otherwise, VAR is a symbol that needs to be put into SSA form
2785
         for the first time, so we need to compute the full IDF for
2786
         it.  */
2787
      bitmap_copy (pruned_idf, idf);
2788
    }
2789
 
2790
  if (!bitmap_empty_p (pruned_idf))
2791
    {
2792
      /* Make sure that PRUNED_IDF blocks and all their feeding blocks
2793
         are included in the region to be updated.  The feeding blocks
2794
         are important to guarantee that the PHI arguments are renamed
2795
         properly.  */
2796
      bitmap_ior_into (blocks, pruned_idf);
2797
      EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
2798
        {
2799
          edge e;
2800
          edge_iterator ei;
2801
          basic_block bb = BASIC_BLOCK (i);
2802
 
2803
          FOR_EACH_EDGE (e, ei, bb->preds)
2804
            if (e->src->index >= 0)
2805
              bitmap_set_bit (blocks, e->src->index);
2806
        }
2807
 
2808
      insert_phi_nodes_for (var, pruned_idf, true);
2809
    }
2810
 
2811
  BITMAP_FREE (pruned_idf);
2812
  BITMAP_FREE (idf);
2813
}
2814
 
2815
 
2816
/* Heuristic to determine whether SSA name mappings for virtual names
2817
   should be discarded and their symbols rewritten from scratch.  When
2818
   there is a large number of mappings for virtual names, the
2819
   insertion of PHI nodes for the old names in the mappings takes
2820
   considerable more time than if we inserted PHI nodes for the
2821
   symbols instead.
2822
 
2823
   Currently the heuristic takes these stats into account:
2824
 
2825
        - Number of mappings for virtual SSA names.
2826
        - Number of distinct virtual symbols involved in those mappings.
2827
 
2828
   If the number of virtual mappings is much larger than the number of
2829
   virtual symbols, then it will be faster to compute PHI insertion
2830
   spots for the symbols.  Even if this involves traversing the whole
2831
   CFG, which is what happens when symbols are renamed from scratch.  */
2832
 
2833
static bool
2834
switch_virtuals_to_full_rewrite_p (void)
2835
{
2836
  if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
2837
    return false;
2838
 
2839
  if (update_ssa_stats.num_virtual_mappings
2840
      > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
2841
        * update_ssa_stats.num_virtual_symbols)
2842
    return true;
2843
 
2844
  return false;
2845
}
2846
 
2847
 
2848
/* Remove every virtual mapping and mark all the affected virtual
2849
   symbols for renaming.  */
2850
 
2851
static void
2852
switch_virtuals_to_full_rewrite (void)
2853
{
2854
  unsigned i = 0;
2855
  sbitmap_iterator sbi;
2856
 
2857
  if (dump_file)
2858
    {
2859
      fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
2860
      fprintf (dump_file, "\tNumber of virtual mappings:       %7u\n",
2861
               update_ssa_stats.num_virtual_mappings);
2862
      fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
2863
               update_ssa_stats.num_virtual_symbols);
2864
      fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
2865
                          "faster than processing\nthe name mappings.\n\n");
2866
    }
2867
 
2868
  /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
2869
     Note that it is not really necessary to remove the mappings from
2870
     REPL_TBL, that would only waste time.  */
2871
  EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
2872
    if (!is_gimple_reg (ssa_name (i)))
2873
      RESET_BIT (new_ssa_names, i);
2874
 
2875
  EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
2876
    if (!is_gimple_reg (ssa_name (i)))
2877
      RESET_BIT (old_ssa_names, i);
2878
 
2879
  bitmap_ior_into (syms_to_rename, update_ssa_stats.virtual_symbols);
2880
}
2881
 
2882
 
2883
/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
2884
   existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
2885
 
2886
   1- The names in OLD_SSA_NAMES dominated by the definitions of
2887
      NEW_SSA_NAMES are all re-written to be reached by the
2888
      appropriate definition from NEW_SSA_NAMES.
2889
 
2890
   2- If needed, new PHI nodes are added to the iterated dominance
2891
      frontier of the blocks where each of NEW_SSA_NAMES are defined.
2892
 
2893
   The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
2894
   calling register_new_name_mapping for every pair of names that the
2895
   caller wants to replace.
2896
 
2897
   The caller identifies the new names that have been inserted and the
2898
   names that need to be replaced by calling register_new_name_mapping
2899
   for every pair <NEW, OLD>.  Note that the function assumes that the
2900
   new names have already been inserted in the IL.
2901
 
2902
   For instance, given the following code:
2903
 
2904
     1  L0:
2905
     2  x_1 = PHI (0, x_5)
2906
     3  if (x_1 < 10)
2907
     4    if (x_1 > 7)
2908
     5      y_2 = 0
2909
     6    else
2910
     7      y_3 = x_1 + x_7
2911
     8    endif
2912
     9    x_5 = x_1 + 1
2913
     10   goto L0;
2914
     11 endif
2915
 
2916
   Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
2917
 
2918
     1  L0:
2919
     2  x_1 = PHI (0, x_5)
2920
     3  if (x_1 < 10)
2921
     4    x_10 = ...
2922
     5    if (x_1 > 7)
2923
     6      y_2 = 0
2924
     7    else
2925
     8      x_11 = ...
2926
     9      y_3 = x_1 + x_7
2927
     10   endif
2928
     11   x_5 = x_1 + 1
2929
     12   goto L0;
2930
     13 endif
2931
 
2932
   We want to replace all the uses of x_1 with the new definitions of
2933
   x_10 and x_11.  Note that the only uses that should be replaced are
2934
   those at lines 5, 9 and 11.  Also, the use of x_7 at line 9 should
2935
   *not* be replaced (this is why we cannot just mark symbol 'x' for
2936
   renaming).
2937
 
2938
   Additionally, we may need to insert a PHI node at line 11 because
2939
   that is a merge point for x_10 and x_11.  So the use of x_1 at line
2940
   11 will be replaced with the new PHI node.  The insertion of PHI
2941
   nodes is optional.  They are not strictly necessary to preserve the
2942
   SSA form, and depending on what the caller inserted, they may not
2943
   even be useful for the optimizers.  UPDATE_FLAGS controls various
2944
   aspects of how update_ssa operates, see the documentation for
2945
   TODO_update_ssa*.  */
2946
 
2947
void
2948
update_ssa (unsigned update_flags)
2949
{
2950
  basic_block bb, start_bb;
2951
  bitmap_iterator bi;
2952
  unsigned i = 0;
2953
  sbitmap tmp;
2954
  bool insert_phi_p;
2955
  sbitmap_iterator sbi;
2956
 
2957
  if (!need_ssa_update_p ())
2958
    return;
2959
 
2960
  timevar_push (TV_TREE_SSA_INCREMENTAL);
2961
 
2962
  blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
2963
  if (!phis_to_rewrite)
2964
    phis_to_rewrite = VEC_alloc (tree_vec, heap, last_basic_block);
2965
  blocks_to_update = BITMAP_ALLOC (NULL);
2966
 
2967
  /* Ensure that the dominance information is up-to-date.  */
2968
  calculate_dominance_info (CDI_DOMINATORS);
2969
 
2970
  /* Only one update flag should be set.  */
2971
  gcc_assert (update_flags == TODO_update_ssa
2972
              || update_flags == TODO_update_ssa_no_phi
2973
              || update_flags == TODO_update_ssa_full_phi
2974
              || update_flags == TODO_update_ssa_only_virtuals);
2975
 
2976
  /* If we only need to update virtuals, remove all the mappings for
2977
     real names before proceeding.  The caller is responsible for
2978
     having dealt with the name mappings before calling update_ssa.  */
2979
  if (update_flags == TODO_update_ssa_only_virtuals)
2980
    {
2981
      sbitmap_zero (old_ssa_names);
2982
      sbitmap_zero (new_ssa_names);
2983
      htab_empty (repl_tbl);
2984
    }
2985
 
2986
  insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
2987
 
2988
  if (insert_phi_p)
2989
    {
2990
      /* If the caller requested PHI nodes to be added, initialize
2991
         live-in information data structures (DEF_BLOCKS).  */
2992
 
2993
      /* For each SSA name N, the DEF_BLOCKS table describes where the
2994
         name is defined, which blocks have PHI nodes for N, and which
2995
         blocks have uses of N (i.e., N is live-on-entry in those
2996
         blocks).  */
2997
      def_blocks = htab_create (num_ssa_names, def_blocks_hash,
2998
                                def_blocks_eq, def_blocks_free);
2999
    }
3000
  else
3001
    {
3002
      def_blocks = NULL;
3003
    }
3004
 
3005
  /* Heuristic to avoid massive slow downs when the replacement
3006
     mappings include lots of virtual names.  */
3007
  if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
3008
    switch_virtuals_to_full_rewrite ();
3009
 
3010
  /* If there are names defined in the replacement table, prepare
3011
     definition and use sites for all the names in NEW_SSA_NAMES and
3012
     OLD_SSA_NAMES.  */
3013
  if (sbitmap_first_set_bit (new_ssa_names) >= 0)
3014
    {
3015
      prepare_names_to_update (insert_phi_p);
3016
 
3017
      /* If all the names in NEW_SSA_NAMES had been marked for
3018
         removal, and there are no symbols to rename, then there's
3019
         nothing else to do.  */
3020
      if (sbitmap_first_set_bit (new_ssa_names) < 0
3021
          && bitmap_empty_p (syms_to_rename))
3022
        goto done;
3023
    }
3024
 
3025
  /* Next, determine the block at which to start the renaming process.  */
3026
  if (!bitmap_empty_p (syms_to_rename))
3027
    {
3028
      /* If we have to rename some symbols from scratch, we need to
3029
         start the process at the root of the CFG.  FIXME, it should
3030
         be possible to determine the nearest block that had a
3031
         definition for each of the symbols that are marked for
3032
         updating.  For now this seems more work than it's worth.  */
3033
      start_bb = ENTRY_BLOCK_PTR;
3034
 
3035
      /* Traverse the CFG looking for definitions and uses of symbols
3036
         in SYMS_TO_RENAME.  Mark interesting blocks and statements
3037
         and set local live-in information for the PHI placement
3038
         heuristics.  */
3039
      prepare_block_for_update (start_bb, insert_phi_p);
3040
    }
3041
  else
3042
    {
3043
      /* Otherwise, the entry block to the region is the nearest
3044
         common dominator for the blocks in BLOCKS.  */
3045
      start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3046
                                                   blocks_to_update);
3047
    }
3048
 
3049
  /* If requested, insert PHI nodes at the iterated dominance frontier
3050
     of every block, creating new definitions for names in OLD_SSA_NAMES
3051
     and for symbols in SYMS_TO_RENAME.  */
3052
  if (insert_phi_p)
3053
    {
3054
      bitmap *dfs;
3055
 
3056
      /* If the caller requested PHI nodes to be added, compute
3057
         dominance frontiers.  */
3058
      dfs = XNEWVEC (bitmap, last_basic_block);
3059
      FOR_EACH_BB (bb)
3060
        dfs[bb->index] = BITMAP_ALLOC (NULL);
3061
      compute_dominance_frontiers (dfs);
3062
 
3063
      if (sbitmap_first_set_bit (old_ssa_names) >= 0)
3064
        {
3065
          sbitmap_iterator sbi;
3066
 
3067
          /* insert_update_phi_nodes_for will call add_new_name_mapping
3068
             when inserting new PHI nodes, so the set OLD_SSA_NAMES
3069
             will grow while we are traversing it (but it will not
3070
             gain any new members).  Copy OLD_SSA_NAMES to a temporary
3071
             for traversal.  */
3072
          sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
3073
          sbitmap_copy (tmp, old_ssa_names);
3074
          EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
3075
            insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
3076
                                          update_flags);
3077
          sbitmap_free (tmp);
3078
        }
3079
 
3080
      EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
3081
        insert_updated_phi_nodes_for (referenced_var (i), dfs,
3082
                                      blocks_to_update, update_flags);
3083
 
3084
      FOR_EACH_BB (bb)
3085
        BITMAP_FREE (dfs[bb->index]);
3086
      free (dfs);
3087
 
3088
      /* Insertion of PHI nodes may have added blocks to the region.
3089
         We need to re-compute START_BB to include the newly added
3090
         blocks.  */
3091
      if (start_bb != ENTRY_BLOCK_PTR)
3092
        start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
3093
                                                     blocks_to_update);
3094
    }
3095
 
3096
  /* Reset the current definition for name and symbol before renaming
3097
     the sub-graph.  */
3098
  EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
3099
    set_current_def (ssa_name (i), NULL_TREE);
3100
 
3101
  EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
3102
    set_current_def (referenced_var (i), NULL_TREE);
3103
 
3104
  /* Now start the renaming process at START_BB.  */
3105
  tmp = sbitmap_alloc (last_basic_block);
3106
  sbitmap_zero (tmp);
3107
  EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3108
    SET_BIT (tmp, i);
3109
 
3110
  rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
3111
 
3112
  sbitmap_free (tmp);
3113
 
3114
  /* Debugging dumps.  */
3115
  if (dump_file)
3116
    {
3117
      int c;
3118
      unsigned i;
3119
 
3120
      dump_update_ssa (dump_file);
3121
 
3122
      fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
3123
               start_bb->index);
3124
 
3125
      c = 0;
3126
      EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3127
        c++;
3128
      fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
3129
      fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
3130
               c, PERCENT (c, last_basic_block));
3131
 
3132
      if (dump_flags & TDF_DETAILS)
3133
        {
3134
          fprintf (dump_file, "Affected blocks: ");
3135
          EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
3136
            fprintf (dump_file, "%u ", i);
3137
          fprintf (dump_file, "\n");
3138
        }
3139
 
3140
      fprintf (dump_file, "\n\n");
3141
    }
3142
 
3143
  /* Free allocated memory.  */
3144
done:
3145
  EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
3146
    {
3147
      tree_vec phis = VEC_index (tree_vec, phis_to_rewrite, i);
3148
 
3149
      VEC_free (tree, heap, phis);
3150
      VEC_replace (tree_vec, phis_to_rewrite, i, NULL);
3151
    }
3152
  BITMAP_FREE (blocks_with_phis_to_rewrite);
3153
  BITMAP_FREE (blocks_to_update);
3154
  delete_update_ssa ();
3155
 
3156
  timevar_pop (TV_TREE_SSA_INCREMENTAL);
3157
}

powered by: WebSVN 2.1.0

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