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

Subversion Repositories openrisc

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

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

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

powered by: WebSVN 2.1.0

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