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

Subversion Repositories openrisc_me

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

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

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