gcc/tree-outof-ssa.c

   1 /* Convert a program in SSA form into Normal form.
   2    Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3    Contributed by Andrew Macleod <amacleod@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "ggc.h"
  27 #include "basic-block.h"
  28 #include "diagnostic.h"
  29 #include "bitmap.h"
  30 #include "tree-flow.h"
  31 #include "timevar.h"
  32 #include "tree-dump.h"
  33 #include "tree-ssa-live.h"
  34 #include "tree-pass.h"
  35 #include "toplev.h"
  36
  37
  38 /* Used to hold all the components required to do SSA PHI elimination.
  39    The node and pred/succ list is a simple linear list of nodes and
  40    edges represented as pairs of nodes.
  41
  42    The predecessor and successor list:  Nodes are entered in pairs, where
  43    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
  44    predecessors, all the odd elements are successors.
  45
  46    Rationale:
  47    When implemented as bitmaps, very large programs SSA->Normal times were
  48    being dominated by clearing the interference graph.
  49
  50    Typically this list of edges is extremely small since it only includes
  51    PHI results and uses from a single edge which have not coalesced with
  52    each other.  This means that no virtual PHI nodes are included, and
  53    empirical evidence suggests that the number of edges rarely exceed
  54    3, and in a bootstrap of GCC, the maximum size encountered was 7.
  55    This also limits the number of possible nodes that are involved to
  56    rarely more than 6, and in the bootstrap of gcc, the maximum number
  57    of nodes encountered was 12.  */
  58
  59 typedef struct _elim_graph {
  60   /* Size of the elimination vectors.  */
  61   int size;
  62
  63   /* List of nodes in the elimination graph.  */
  64   VEC(tree,heap) *nodes;
  65
  66   /*  The predecessor and successor edge list.  */
  67   VEC(int,heap) *edge_list;
  68
  69   /* Visited vector.  */
  70   sbitmap visited;
  71
  72   /* Stack for visited nodes.  */
  73   VEC(int,heap) *stack;
  74
  75   /* The variable partition map.  */
  76   var_map map;
  77
  78   /* Edge being eliminated by this graph.  */
  79   edge e;
  80
  81   /* List of constant copies to emit.  These are pushed on in pairs.  */
  82   VEC(tree,heap) *const_copies;
  83 } *elim_graph;
  84
  85
  86 /* Create a temporary variable based on the type of variable T.  Use T's name
  87    as the prefix.  */
  88
  89 static tree
  90 create_temp (tree t)
  91 {
  92   tree tmp;
  93   const char *name = NULL;
  94   tree type;
  95
  96   if (TREE_CODE (t) == SSA_NAME)
  97     t = SSA_NAME_VAR (t);
  98
  99   gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
 100
 101   type = TREE_TYPE (t);
 102   tmp = DECL_NAME (t);
 103   if (tmp)
 104     name = IDENTIFIER_POINTER (tmp);
 105
 106   if (name == NULL)
 107     name = "temp";
 108   tmp = create_tmp_var (type, name);
 109
 110   if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t))
 111     {
 112       SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t));
 113       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
 114     }
 115   else if (!DECL_IGNORED_P (t))
 116     {
 117       SET_DECL_DEBUG_EXPR (tmp, t);
 118       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
 119     }
 120   DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
 121   DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
 122   add_referenced_var (tmp);
 123
 124   /* add_referenced_var will create the annotation and set up some
 125      of the flags in the annotation.  However, some flags we need to
 126      inherit from our original variable.  */
 127   set_symbol_mem_tag (tmp, symbol_mem_tag (t));
 128   if (is_call_clobbered (t))
 129     mark_call_clobbered (tmp, var_ann (t)->escape_mask);
 130
 131   return tmp;
 132 }
 133
 134
 135 /* This helper function fill insert a copy from a constant or variable SRC to
 136    variable DEST on edge E.  */
 137
 138 static void
 139 insert_copy_on_edge (edge e, tree dest, tree src)
 140 {
 141   tree copy;
 142
 143   copy = build_gimple_modify_stmt (dest, src);
 144   set_is_used (dest);
 145
 146   if (TREE_CODE (src) == ADDR_EXPR)
 147     src = TREE_OPERAND (src, 0);
 148   if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
 149     set_is_used (src);
 150
 151   if (dump_file && (dump_flags & TDF_DETAILS))
 152     {
 153       fprintf (dump_file,
 154                "Inserting a copy on edge BB%d->BB%d :",
 155                e->src->index,
 156                e->dest->index);
 157       print_generic_expr (dump_file, copy, dump_flags);
 158       fprintf (dump_file, "\n");
 159     }
 160
 161   bsi_insert_on_edge (e, copy);
 162 }
 163
 164
 165 /* Create an elimination graph with SIZE nodes and associated data
 166    structures.  */
 167
 168 static elim_graph
 169 new_elim_graph (int size)
 170 {
 171   elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
 172
 173   g->nodes = VEC_alloc (tree, heap, 30);
 174   g->const_copies = VEC_alloc (tree, heap, 20);
 175   g->edge_list = VEC_alloc (int, heap, 20);
 176   g->stack = VEC_alloc (int, heap, 30);
 177
 178   g->visited = sbitmap_alloc (size);
 179
 180   return g;
 181 }
 182
 183
 184 /* Empty elimination graph G.  */
 185
 186 static inline void
 187 clear_elim_graph (elim_graph g)
 188 {
 189   VEC_truncate (tree, g->nodes, 0);
 190   VEC_truncate (int, g->edge_list, 0);
 191 }
 192
 193
 194 /* Delete elimination graph G.  */
 195
 196 static inline void
 197 delete_elim_graph (elim_graph g)
 198 {
 199   sbitmap_free (g->visited);
 200   VEC_free (int, heap, g->stack);
 201   VEC_free (int, heap, g->edge_list);
 202   VEC_free (tree, heap, g->const_copies);
 203   VEC_free (tree, heap, g->nodes);
 204   free (g);
 205 }
 206
 207
 208 /* Return the number of nodes in graph G.  */
 209
 210 static inline int
 211 elim_graph_size (elim_graph g)
 212 {
 213   return VEC_length (tree, g->nodes);
 214 }
 215
 216
 217 /* Add NODE to graph G, if it doesn't exist already.  */
 218
 219 static inline void
 220 elim_graph_add_node (elim_graph g, tree node)
 221 {
 222   int x;
 223   tree t;
 224
 225   for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
 226     if (t == node)
 227       return;
 228   VEC_safe_push (tree, heap, g->nodes, node);
 229 }
 230
 231
 232 /* Add the edge PRED->SUCC to graph G.  */
 233
 234 static inline void
 235 elim_graph_add_edge (elim_graph g, int pred, int succ)
 236 {
 237   VEC_safe_push (int, heap, g->edge_list, pred);
 238   VEC_safe_push (int, heap, g->edge_list, succ);
 239 }
 240
 241
 242 /* Remove an edge from graph G for which NODE is the predecessor, and
 243    return the successor node.  -1 is returned if there is no such edge.  */
 244
 245 static inline int
 246 elim_graph_remove_succ_edge (elim_graph g, int node)
 247 {
 248   int y;
 249   unsigned x;
 250   for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
 251     if (VEC_index (int, g->edge_list, x) == node)
 252       {
 253         VEC_replace (int, g->edge_list, x, -1);
 254         y = VEC_index (int, g->edge_list, x + 1);
 255         VEC_replace (int, g->edge_list, x + 1, -1);
 256         return y;
 257       }
 258   return -1;
 259 }
 260
 261
 262 /* Find all the nodes in GRAPH which are successors to NODE in the
 263    edge list.  VAR will hold the partition number found.  CODE is the
 264    code fragment executed for every node found.  */
 265
 266 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE)                \
 267 do {                                                                    \
 268   unsigned x_;                                                          \
 269   int y_;                                                               \
 270   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
 271     {                                                                   \
 272       y_ = VEC_index (int, (GRAPH)->edge_list, x_);                     \
 273       if (y_ != (NODE))                                                 \
 274         continue;                                                       \
 275       (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1);              \
 276       CODE;                                                             \
 277     }                                                                   \
 278 } while (0)
 279
 280
 281 /* Find all the nodes which are predecessors of NODE in the edge list for
 282    GRAPH.  VAR will hold the partition number found.  CODE is the
 283    code fragment executed for every node found.  */
 284
 285 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE)                \
 286 do {                                                                    \
 287   unsigned x_;                                                          \
 288   int y_;                                                               \
 289   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
 290     {                                                                   \
 291       y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1);                 \
 292       if (y_ != (NODE))                                                 \
 293         continue;                                                       \
 294       (VAR) = VEC_index (int, (GRAPH)->edge_list, x_);                  \
 295       CODE;                                                             \
 296     }                                                                   \
 297 } while (0)
 298
 299
 300 /* Add T to elimination graph G.  */
 301
 302 static inline void
 303 eliminate_name (elim_graph g, tree T)
 304 {
 305   elim_graph_add_node (g, T);
 306 }
 307
 308
 309 /* Build elimination graph G for basic block BB on incoming PHI edge
 310    G->e.  */
 311
 312 static void
 313 eliminate_build (elim_graph g, basic_block B)
 314 {
 315   tree phi;
 316   tree T0, Ti;
 317   int p0, pi;
 318
 319   clear_elim_graph (g);
 320
 321   for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
 322     {
 323       T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
 324
 325       /* Ignore results which are not in partitions.  */
 326       if (T0 == NULL_TREE)
 327         continue;
 328
 329       Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
 330
 331       /* If this argument is a constant, or a SSA_NAME which is being
 332          left in SSA form, just queue a copy to be emitted on this
 333          edge.  */
 334       if (!phi_ssa_name_p (Ti)
 335           || (TREE_CODE (Ti) == SSA_NAME
 336               && var_to_partition (g->map, Ti) == NO_PARTITION))
 337         {
 338           /* Save constant copies until all other copies have been emitted
 339              on this edge.  */
 340           VEC_safe_push (tree, heap, g->const_copies, T0);
 341           VEC_safe_push (tree, heap, g->const_copies, Ti);
 342         }
 343       else
 344         {
 345           Ti = var_to_partition_to_var (g->map, Ti);
 346           if (T0 != Ti)
 347             {
 348               eliminate_name (g, T0);
 349               eliminate_name (g, Ti);
 350               p0 = var_to_partition (g->map, T0);
 351               pi = var_to_partition (g->map, Ti);
 352               elim_graph_add_edge (g, p0, pi);
 353             }
 354         }
 355     }
 356 }
 357
 358
 359 /* Push successors of T onto the elimination stack for G.  */
 360
 361 static void
 362 elim_forward (elim_graph g, int T)
 363 {
 364   int S;
 365   SET_BIT (g->visited, T);
 366   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
 367     {
 368       if (!TEST_BIT (g->visited, S))
 369         elim_forward (g, S);
 370     });
 371   VEC_safe_push (int, heap, g->stack, T);
 372 }
 373
 374
 375 /* Return 1 if there unvisited predecessors of T in graph G.  */
 376
 377 static int
 378 elim_unvisited_predecessor (elim_graph g, int T)
 379 {
 380   int P;
 381   FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 382     {
 383       if (!TEST_BIT (g->visited, P))
 384         return 1;
 385     });
 386   return 0;
 387 }
 388
 389 /* Process predecessors first, and insert a copy.  */
 390
 391 static void
 392 elim_backward (elim_graph g, int T)
 393 {
 394   int P;
 395   SET_BIT (g->visited, T);
 396   FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 397     {
 398       if (!TEST_BIT (g->visited, P))
 399         {
 400           elim_backward (g, P);
 401           insert_copy_on_edge (g->e,
 402                                partition_to_var (g->map, P),
 403                                partition_to_var (g->map, T));
 404         }
 405     });
 406 }
 407
 408 /* Insert required copies for T in graph G.  Check for a strongly connected
 409    region, and create a temporary to break the cycle if one is found.  */
 410
 411 static void
 412 elim_create (elim_graph g, int T)
 413 {
 414   tree U;
 415   int P, S;
 416
 417   if (elim_unvisited_predecessor (g, T))
 418     {
 419       U = create_temp (partition_to_var (g->map, T));
 420       insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
 421       FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 422         {
 423           if (!TEST_BIT (g->visited, P))
 424             {
 425               elim_backward (g, P);
 426               insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
 427             }
 428         });
 429     }
 430   else
 431     {
 432       S = elim_graph_remove_succ_edge (g, T);
 433       if (S != -1)
 434         {
 435           SET_BIT (g->visited, T);
 436           insert_copy_on_edge (g->e,
 437                                partition_to_var (g->map, T),
 438                                partition_to_var (g->map, S));
 439         }
 440     }
 441
 442 }
 443
 444
 445 /* Eliminate all the phi nodes on edge E in graph G.  */
 446
 447 static void
 448 eliminate_phi (edge e, elim_graph g)
 449 {
 450   int x;
 451   basic_block B = e->dest;
 452
 453   gcc_assert (VEC_length (tree, g->const_copies) == 0);
 454
 455   /* Abnormal edges already have everything coalesced.  */
 456   if (e->flags & EDGE_ABNORMAL)
 457     return;
 458
 459   g->e = e;
 460
 461   eliminate_build (g, B);
 462
 463   if (elim_graph_size (g) != 0)
 464     {
 465       tree var;
 466
 467       sbitmap_zero (g->visited);
 468       VEC_truncate (int, g->stack, 0);
 469
 470       for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
 471         {
 472           int p = var_to_partition (g->map, var);
 473           if (!TEST_BIT (g->visited, p))
 474             elim_forward (g, p);
 475         }
 476
 477       sbitmap_zero (g->visited);
 478       while (VEC_length (int, g->stack) > 0)
 479         {
 480           x = VEC_pop (int, g->stack);
 481           if (!TEST_BIT (g->visited, x))
 482             elim_create (g, x);
 483         }
 484     }
 485
 486   /* If there are any pending constant copies, issue them now.  */
 487   while (VEC_length (tree, g->const_copies) > 0)
 488     {
 489       tree src, dest;
 490       src = VEC_pop (tree, g->const_copies);
 491       dest = VEC_pop (tree, g->const_copies);
 492       insert_copy_on_edge (e, dest, src);
 493     }
 494 }
 495
 496
 497 /* Take the ssa-name var_map MAP, and assign real variables to each
 498    partition.  */
 499
 500 static void
 501 assign_vars (var_map map)
 502 {
 503   int x, num;
 504   tree var, root;
 505   var_ann_t ann;
 506
 507   num = num_var_partitions (map);
 508   for (x = 0; x < num; x++)
 509     {
 510       var = partition_to_var (map, x);
 511       if (TREE_CODE (var) != SSA_NAME)
 512         {
 513           ann = var_ann (var);
 514           /* It must already be coalesced.  */
 515           gcc_assert (ann->out_of_ssa_tag == 1);
 516           if (dump_file && (dump_flags & TDF_DETAILS))
 517             {
 518               fprintf (dump_file, "partition %d already has variable ", x);
 519               print_generic_expr (dump_file, var, TDF_SLIM);
 520               fprintf (dump_file, " assigned to it.\n");
 521             }
 522         }
 523       else
 524         {
 525           root = SSA_NAME_VAR (var);
 526           ann = var_ann (root);
 527           /* If ROOT is already associated, create a new one.  */
 528           if (ann->out_of_ssa_tag)
 529             {
 530               root = create_temp (root);
 531               ann = var_ann (root);
 532             }
 533           /* ROOT has not been coalesced yet, so use it.  */
 534           if (dump_file && (dump_flags & TDF_DETAILS))
 535             {
 536               fprintf (dump_file, "Partition %d is assigned to var ", x);
 537               print_generic_stmt (dump_file, root, TDF_SLIM);
 538             }
 539           change_partition_var (map, root, x);
 540         }
 541     }
 542 }
 543
 544
 545 /* Replace use operand P with whatever variable it has been rewritten to based
 546    on the partitions in MAP.  EXPR is an optional expression vector over SSA
 547    versions which is used to replace P with an expression instead of a variable.
 548    If the stmt is changed, return true.  */
 549
 550 static inline bool
 551 replace_use_variable (var_map map, use_operand_p p, tree *expr)
 552 {
 553   tree new_var;
 554   tree var = USE_FROM_PTR (p);
 555
 556   /* Check if we are replacing this variable with an expression.  */
 557   if (expr)
 558     {
 559       int version = SSA_NAME_VERSION (var);
 560       if (expr[version])
 561         {
 562           tree new_expr = GIMPLE_STMT_OPERAND (expr[version], 1);
 563           SET_USE (p, new_expr);
 564
 565           /* Clear the stmt's RHS, or GC might bite us.  */
 566           GIMPLE_STMT_OPERAND (expr[version], 1) = NULL_TREE;
 567           return true;
 568         }
 569     }
 570
 571   new_var = var_to_partition_to_var (map, var);
 572   if (new_var)
 573     {
 574       SET_USE (p, new_var);
 575       set_is_used (new_var);
 576       return true;
 577     }
 578   return false;
 579 }
 580
 581
 582 /* Replace def operand DEF_P with whatever variable it has been rewritten to
 583    based on the partitions in MAP.  EXPR is an optional expression vector over
 584    SSA versions which is used to replace DEF_P with an expression instead of a
 585    variable.  If the stmt is changed, return true.  */
 586
 587 static inline bool
 588 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
 589 {
 590   tree new_var;
 591   tree var = DEF_FROM_PTR (def_p);
 592
 593   /* Do nothing if we are replacing this variable with an expression.  */
 594   if (expr && expr[SSA_NAME_VERSION (var)])
 595     return true;
 596
 597   new_var = var_to_partition_to_var (map, var);
 598   if (new_var)
 599     {
 600       SET_DEF (def_p, new_var);
 601       set_is_used (new_var);
 602       return true;
 603     }
 604   return false;
 605 }
 606
 607
 608 /* Remove any PHI node which is a virtual PHI.  */
 609
 610 static void
 611 eliminate_virtual_phis (void)
 612 {
 613   basic_block bb;
 614   tree phi, next;
 615
 616   FOR_EACH_BB (bb)
 617     {
 618       for (phi = phi_nodes (bb); phi; phi = next)
 619         {
 620           next = PHI_CHAIN (phi);
 621           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
 622             {
 623 #ifdef ENABLE_CHECKING
 624               int i;
 625               /* There should be no arguments of this PHI which are in
 626                  the partition list, or we get incorrect results.  */
 627               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 628                 {
 629                   tree arg = PHI_ARG_DEF (phi, i);
 630                   if (TREE_CODE (arg) == SSA_NAME
 631                       && is_gimple_reg (SSA_NAME_VAR (arg)))
 632                     {
 633                       fprintf (stderr, "Argument of PHI is not virtual (");
 634                       print_generic_expr (stderr, arg, TDF_SLIM);
 635                       fprintf (stderr, "), but the result is :");
 636                       print_generic_stmt (stderr, phi, TDF_SLIM);
 637                       internal_error ("SSA corruption");
 638                     }
 639                 }
 640 #endif
 641               remove_phi_node (phi, NULL_TREE, true);
 642             }
 643         }
 644     }
 645 }
 646
 647
 648 /* This function will rewrite the current program using the variable mapping
 649    found in MAP.  If the replacement vector VALUES is provided, any
 650    occurrences of partitions with non-null entries in the vector will be
 651    replaced with the expression in the vector instead of its mapped
 652    variable.  */
 653
 654 static void
 655 rewrite_trees (var_map map, tree *values)
 656 {
 657   elim_graph g;
 658   basic_block bb;
 659   block_stmt_iterator si;
 660   edge e;
 661   tree phi;
 662   bool changed;
 663
 664 #ifdef ENABLE_CHECKING
 665   /* Search for PHIs where the destination has no partition, but one
 666      or more arguments has a partition.  This should not happen and can
 667      create incorrect code.  */
 668   FOR_EACH_BB (bb)
 669     {
 670       tree phi;
 671       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 672         {
 673           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
 674           if (T0 == NULL_TREE)
 675             {
 676               int i;
 677               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 678                 {
 679                   tree arg = PHI_ARG_DEF (phi, i);
 680
 681                   if (TREE_CODE (arg) == SSA_NAME
 682                       && var_to_partition (map, arg) != NO_PARTITION)
 683                     {
 684                       fprintf (stderr, "Argument of PHI is in a partition :(");
 685                       print_generic_expr (stderr, arg, TDF_SLIM);
 686                       fprintf (stderr, "), but the result is not :");
 687                       print_generic_stmt (stderr, phi, TDF_SLIM);
 688                       internal_error ("SSA corruption");
 689                     }
 690                 }
 691             }
 692         }
 693     }
 694 #endif
 695
 696   /* Replace PHI nodes with any required copies.  */
 697   g = new_elim_graph (map->num_partitions);
 698   g->map = map;
 699   FOR_EACH_BB (bb)
 700     {
 701       for (si = bsi_start (bb); !bsi_end_p (si); )
 702         {
 703           tree stmt = bsi_stmt (si);
 704           use_operand_p use_p, copy_use_p;
 705           def_operand_p def_p;
 706           bool remove = false, is_copy = false;
 707           int num_uses = 0;
 708           stmt_ann_t ann;
 709           ssa_op_iter iter;
 710
 711           ann = stmt_ann (stmt);
 712           changed = false;
 713
 714           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 715               && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == SSA_NAME))
 716             is_copy = true;
 717
 718           copy_use_p = NULL_USE_OPERAND_P;
 719           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
 720             {
 721               if (replace_use_variable (map, use_p, values))
 722                 changed = true;
 723               copy_use_p = use_p;
 724               num_uses++;
 725             }
 726
 727           if (num_uses != 1)
 728             is_copy = false;
 729
 730           def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
 731
 732           if (def_p != NULL)
 733             {
 734               /* Mark this stmt for removal if it is the list of replaceable
 735                  expressions.  */
 736               if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
 737                 remove = true;
 738               else
 739                 {
 740                   if (replace_def_variable (map, def_p, NULL))
 741                     changed = true;
 742                   /* If both SSA_NAMEs coalesce to the same variable,
 743                      mark the now redundant copy for removal.  */
 744                   if (is_copy)
 745                     {
 746                       gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
 747                       if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
 748                         remove = true;
 749                     }
 750                 }
 751             }
 752           else
 753             FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
 754               if (replace_def_variable (map, def_p, NULL))
 755                 changed = true;
 756
 757           /* Remove any stmts marked for removal.  */
 758           if (remove)
 759             bsi_remove (&si, true);
 760           else
 761             bsi_next (&si);
 762         }
 763
 764       phi = phi_nodes (bb);
 765       if (phi)
 766         {
 767           edge_iterator ei;
 768           FOR_EACH_EDGE (e, ei, bb->preds)
 769             eliminate_phi (e, g);
 770         }
 771     }
 772
 773   delete_elim_graph (g);
 774 }
 775
 776 /* These are the local work structures used to determine the best place to
 777    insert the copies that were placed on edges by the SSA->normal pass..  */
 778 static VEC(edge,heap) *edge_leader;
 779 static VEC(tree,heap) *stmt_list;
 780 static bitmap leader_has_match = NULL;
 781 static edge leader_match = NULL;
 782
 783
 784 /* Pass this function to make_forwarder_block so that all the edges with
 785    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  E is the
 786    edge to test for a match.  */
 787
 788 static inline bool
 789 same_stmt_list_p (edge e)
 790 {
 791   return (e->aux == (PTR) leader_match) ? true : false;
 792 }
 793
 794
 795 /* Return TRUE if S1 and S2 are equivalent copies.  */
 796
 797 static inline bool
 798 identical_copies_p (tree s1, tree s2)
 799 {
 800 #ifdef ENABLE_CHECKING
 801   gcc_assert (TREE_CODE (s1) == GIMPLE_MODIFY_STMT);
 802   gcc_assert (TREE_CODE (s2) == GIMPLE_MODIFY_STMT);
 803   gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s1, 0)));
 804   gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s2, 0)));
 805 #endif
 806
 807   if (GIMPLE_STMT_OPERAND (s1, 0) != GIMPLE_STMT_OPERAND (s2, 0))
 808     return false;
 809
 810   s1 = GIMPLE_STMT_OPERAND (s1, 1);
 811   s2 = GIMPLE_STMT_OPERAND (s2, 1);
 812
 813   if (s1 != s2)
 814     return false;
 815
 816   return true;
 817 }
 818
 819
 820 /* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists
 821    contain the same sequence of copies.  */
 822
 823 static inline bool
 824 identical_stmt_lists_p (edge e1, edge e2)
 825 {
 826   tree t1 = PENDING_STMT (e1);
 827   tree t2 = PENDING_STMT (e2);
 828   tree_stmt_iterator tsi1, tsi2;
 829
 830   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
 831   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
 832
 833   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
 834        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
 835        tsi_next (&tsi1), tsi_next (&tsi2))
 836     {
 837       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
 838         break;
 839     }
 840
 841   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
 842     return false;
 843
 844   return true;
 845 }
 846
 847
 848 /* Allocate data structures used in analyze_edges_for_bb.   */
 849
 850 static void
 851 init_analyze_edges_for_bb (void)
 852 {
 853   edge_leader = VEC_alloc (edge, heap, 25);
 854   stmt_list = VEC_alloc (tree, heap, 25);
 855   leader_has_match = BITMAP_ALLOC (NULL);
 856 }
 857
 858
 859 /* Free data structures used in analyze_edges_for_bb.   */
 860
 861 static void
 862 fini_analyze_edges_for_bb (void)
 863 {
 864   VEC_free (edge, heap, edge_leader);
 865   VEC_free (tree, heap, stmt_list);
 866   BITMAP_FREE (leader_has_match);
 867 }
 868
 869
 870 /* Look at all the incoming edges to block BB, and decide where the best place
 871    to insert the stmts on each edge are, and perform those insertions.  */
 872
 873 static void
 874 analyze_edges_for_bb (basic_block bb)
 875 {
 876   edge e;
 877   edge_iterator ei;
 878   int count;
 879   unsigned int x;
 880   bool have_opportunity;
 881   block_stmt_iterator bsi;
 882   tree stmt;
 883   edge single_edge = NULL;
 884   bool is_label;
 885   edge leader;
 886
 887   count = 0;
 888
 889   /* Blocks which contain at least one abnormal edge cannot use
 890      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
 891      found on edges in these block.  */
 892   have_opportunity = true;
 893   FOR_EACH_EDGE (e, ei, bb->preds)
 894     if (e->flags & EDGE_ABNORMAL)
 895       {
 896         have_opportunity = false;
 897         break;
 898       }
 899
 900   if (!have_opportunity)
 901     {
 902       FOR_EACH_EDGE (e, ei, bb->preds)
 903         if (PENDING_STMT (e))
 904           bsi_commit_one_edge_insert (e, NULL);
 905       return;
 906     }
 907
 908   /* Find out how many edges there are with interesting pending stmts on them.
 909      Commit the stmts on edges we are not interested in.  */
 910   FOR_EACH_EDGE (e, ei, bb->preds)
 911     {
 912       if (PENDING_STMT (e))
 913         {
 914           gcc_assert (!(e->flags & EDGE_ABNORMAL));
 915           if (e->flags & EDGE_FALLTHRU)
 916             {
 917               bsi = bsi_start (e->src);
 918               if (!bsi_end_p (bsi))
 919                 {
 920                   stmt = bsi_stmt (bsi);
 921                   bsi_next (&bsi);
 922                   gcc_assert (stmt != NULL_TREE);
 923                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
 924                   /* Punt if it has non-label stmts, or isn't local.  */
 925                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
 926                       || !bsi_end_p (bsi))
 927                     {
 928                       bsi_commit_one_edge_insert (e, NULL);
 929                       continue;
 930                     }
 931                 }
 932             }
 933           single_edge = e;
 934           count++;
 935         }
 936     }
 937
 938   /* If there aren't at least 2 edges, no sharing will happen.  */
 939   if (count < 2)
 940     {
 941       if (single_edge)
 942         bsi_commit_one_edge_insert (single_edge, NULL);
 943       return;
 944     }
 945
 946   /* Ensure that we have empty worklists.  */
 947 #ifdef ENABLE_CHECKING
 948   gcc_assert (VEC_length (edge, edge_leader) == 0);
 949   gcc_assert (VEC_length (tree, stmt_list) == 0);
 950   gcc_assert (bitmap_empty_p (leader_has_match));
 951 #endif
 952
 953   /* Find the "leader" block for each set of unique stmt lists.  Preference is
 954      given to FALLTHRU blocks since they would need a GOTO to arrive at another
 955      block.  The leader edge destination is the block which all the other edges
 956      with the same stmt list will be redirected to.  */
 957   have_opportunity = false;
 958   FOR_EACH_EDGE (e, ei, bb->preds)
 959     {
 960       if (PENDING_STMT (e))
 961         {
 962           bool found = false;
 963
 964           /* Look for the same stmt list in edge leaders list.  */
 965           for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
 966             {
 967               if (identical_stmt_lists_p (leader, e))
 968                 {
 969                   /* Give this edge the same stmt list pointer.  */
 970                   PENDING_STMT (e) = NULL;
 971                   e->aux = leader;
 972                   bitmap_set_bit (leader_has_match, x);
 973                   have_opportunity = found = true;
 974                   break;
 975                 }
 976             }
 977
 978           /* If no similar stmt list, add this edge to the leader list.  */
 979           if (!found)
 980             {
 981               VEC_safe_push (edge, heap, edge_leader, e);
 982               VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
 983             }
 984         }
 985      }
 986
 987   /* If there are no similar lists, just issue the stmts.  */
 988   if (!have_opportunity)
 989     {
 990       for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
 991         bsi_commit_one_edge_insert (leader, NULL);
 992       VEC_truncate (edge, edge_leader, 0);
 993       VEC_truncate (tree, stmt_list, 0);
 994       bitmap_clear (leader_has_match);
 995       return;
 996     }
 997
 998   if (dump_file)
 999     fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
1000              bb->index);
1001
1002   /* For each common list, create a forwarding block and issue the stmt's
1003      in that block.  */
1004   for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1005     if (bitmap_bit_p (leader_has_match, x))
1006       {
1007         edge new_edge;
1008         block_stmt_iterator bsi;
1009         tree curr_stmt_list;
1010
1011         leader_match = leader;
1012
1013         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
1014            for various PHI manipulations, so it gets cleared when calls are
1015            made to make_forwarder_block(). So make sure the edge is clear,
1016            and use the saved stmt list.  */
1017         PENDING_STMT (leader) = NULL;
1018         leader->aux = leader;
1019         curr_stmt_list = VEC_index (tree, stmt_list, x);
1020
1021         new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
1022                                          NULL);
1023         bb = new_edge->dest;
1024         if (dump_file)
1025           {
1026             fprintf (dump_file, "Splitting BB %d for Common stmt list.  ",
1027                      leader->dest->index);
1028             fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
1029             print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS);
1030           }
1031
1032         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
1033           {
1034             e->aux = NULL;
1035             if (dump_file)
1036               fprintf (dump_file, "  Edge (%d->%d) lands here.\n",
1037                        e->src->index, e->dest->index);
1038           }
1039
1040         bsi = bsi_last (leader->dest);
1041         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
1042
1043         leader_match = NULL;
1044         /* We should never get a new block now.  */
1045       }
1046     else
1047       {
1048         PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
1049         bsi_commit_one_edge_insert (leader, NULL);
1050       }
1051
1052
1053   /* Clear the working data structures.  */
1054   VEC_truncate (edge, edge_leader, 0);
1055   VEC_truncate (tree, stmt_list, 0);
1056   bitmap_clear (leader_has_match);
1057 }
1058
1059
1060 /* This function will analyze the insertions which were performed on edges,
1061    and decide whether they should be left on that edge, or whether it is more
1062    efficient to emit some subset of them in a single block.  All stmts are
1063    inserted somewhere.  */
1064
1065 static void
1066 perform_edge_inserts (void)
1067 {
1068   basic_block bb;
1069
1070   if (dump_file)
1071     fprintf(dump_file, "Analyzing Edge Insertions.\n");
1072
1073   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
1074      incrementally update the dominator information.  Since we don't
1075      need dominator information after this pass, go ahead and free the
1076      dominator information.  */
1077   free_dominance_info (CDI_DOMINATORS);
1078   free_dominance_info (CDI_POST_DOMINATORS);
1079
1080   /* Allocate data structures used in analyze_edges_for_bb.   */
1081   init_analyze_edges_for_bb ();
1082
1083   FOR_EACH_BB (bb)
1084     analyze_edges_for_bb (bb);
1085
1086   analyze_edges_for_bb (EXIT_BLOCK_PTR);
1087
1088   /* Free data structures used in analyze_edges_for_bb.   */
1089   fini_analyze_edges_for_bb ();
1090
1091 #ifdef ENABLE_CHECKING
1092   {
1093     edge_iterator ei;
1094     edge e;
1095     FOR_EACH_BB (bb)
1096       {
1097         FOR_EACH_EDGE (e, ei, bb->preds)
1098           {
1099             if (PENDING_STMT (e))
1100               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
1101                      e->src->index, e->dest->index);
1102           }
1103         FOR_EACH_EDGE (e, ei, bb->succs)
1104           {
1105             if (PENDING_STMT (e))
1106               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
1107                      e->src->index, e->dest->index);
1108           }
1109       }
1110     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1111       {
1112         if (PENDING_STMT (e))
1113           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
1114                  e->src->index, e->dest->index);
1115       }
1116     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1117       {
1118         if (PENDING_STMT (e))
1119           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
1120                  e->src->index, e->dest->index);
1121       }
1122   }
1123 #endif
1124 }
1125
1126
1127 /* Remove the ssa-names in the current function and translate them into normal
1128    compiler variables.  PERFORM_TER is true if Temporary Expression Replacement
1129    should also be used.  */
1130
1131 static void
1132 remove_ssa_form (bool perform_ter)
1133 {
1134   basic_block bb;
1135   tree phi, next;
1136   tree *values = NULL;
1137   var_map map;
1138
1139   map = coalesce_ssa_name ();
1140
1141   /* Return to viewing the variable list as just all reference variables after
1142      coalescing has been performed.  */
1143   partition_view_normal (map, false);
1144
1145   if (dump_file && (dump_flags & TDF_DETAILS))
1146     {
1147       fprintf (dump_file, "After Coalescing:\n");
1148       dump_var_map (dump_file, map);
1149     }
1150
1151   if (perform_ter)
1152     {
1153       values = find_replaceable_exprs (map);
1154       if (values && dump_file && (dump_flags & TDF_DETAILS))
1155         dump_replaceable_exprs (dump_file, values);
1156     }
1157
1158   /* Assign real variables to the partitions now.  */
1159   assign_vars (map);
1160
1161   if (dump_file && (dump_flags & TDF_DETAILS))
1162     {
1163       fprintf (dump_file, "After Base variable replacement:\n");
1164       dump_var_map (dump_file, map);
1165     }
1166
1167   rewrite_trees (map, values);
1168
1169   if (values)
1170     free (values);
1171
1172   /* Remove PHI nodes which have been translated back to real variables.  */
1173   FOR_EACH_BB (bb)
1174     {
1175       for (phi = phi_nodes (bb); phi; phi = next)
1176         {
1177           next = PHI_CHAIN (phi);
1178           remove_phi_node (phi, NULL_TREE, true);
1179         }
1180     }
1181
1182   /* If any copies were inserted on edges, analyze and insert them now.  */
1183   perform_edge_inserts ();
1184
1185   delete_var_map (map);
1186 }
1187
1188
1189 /* Search every PHI node for arguments associated with backedges which
1190    we can trivially determine will need a copy (the argument is either
1191    not an SSA_NAME or the argument has a different underlying variable
1192    than the PHI result).
1193
1194    Insert a copy from the PHI argument to a new destination at the
1195    end of the block with the backedge to the top of the loop.  Update
1196    the PHI argument to reference this new destination.  */
1197
1198 static void
1199 insert_backedge_copies (void)
1200 {
1201   basic_block bb;
1202
1203   FOR_EACH_BB (bb)
1204     {
1205       tree phi;
1206
1207       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1208         {
1209           tree result = PHI_RESULT (phi);
1210           tree result_var;
1211           int i;
1212
1213           if (!is_gimple_reg (result))
1214             continue;
1215
1216           result_var = SSA_NAME_VAR (result);
1217           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1218             {
1219               tree arg = PHI_ARG_DEF (phi, i);
1220               edge e = PHI_ARG_EDGE (phi, i);
1221
1222               /* If the argument is not an SSA_NAME, then we will need a
1223                  constant initialization.  If the argument is an SSA_NAME with
1224                  a different underlying variable then a copy statement will be
1225                  needed.  */
1226               if ((e->flags & EDGE_DFS_BACK)
1227                   && (TREE_CODE (arg) != SSA_NAME
1228                       || SSA_NAME_VAR (arg) != result_var))
1229                 {
1230                   tree stmt, name, last = NULL;
1231                   block_stmt_iterator bsi;
1232
1233                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
1234                   if (!bsi_end_p (bsi))
1235                     last = bsi_stmt (bsi);
1236
1237                   /* In theory the only way we ought to get back to the
1238                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
1239                      However, better safe than sorry.
1240                      If the block ends with a control statement or
1241                      something that might throw, then we have to
1242                      insert this assignment before the last
1243                      statement.  Else insert it after the last statement.  */
1244                   if (last && stmt_ends_bb_p (last))
1245                     {
1246                       /* If the last statement in the block is the definition
1247                          site of the PHI argument, then we can't insert
1248                          anything after it.  */
1249                       if (TREE_CODE (arg) == SSA_NAME
1250                           && SSA_NAME_DEF_STMT (arg) == last)
1251                         continue;
1252                     }
1253
1254                   /* Create a new instance of the underlying variable of the
1255                      PHI result.  */
1256                   stmt = build_gimple_modify_stmt (NULL_TREE,
1257                                                    PHI_ARG_DEF (phi, i));
1258                   name = make_ssa_name (result_var, stmt);
1259                   GIMPLE_STMT_OPERAND (stmt, 0) = name;
1260
1261                   /* Insert the new statement into the block and update
1262                      the PHI node.  */
1263                   if (last && stmt_ends_bb_p (last))
1264                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
1265                   else
1266                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
1267                   SET_PHI_ARG_DEF (phi, i, name);
1268                 }
1269             }
1270         }
1271     }
1272 }
1273
1274 /* Take the current function out of SSA form, translating PHIs as described in
1275    R. Morgan, ``Building an Optimizing Compiler'',
1276    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
1277
1278 static unsigned int
1279 rewrite_out_of_ssa (void)
1280 {
1281   /* If elimination of a PHI requires inserting a copy on a backedge,
1282      then we will have to split the backedge which has numerous
1283      undesirable performance effects.
1284
1285      A significant number of such cases can be handled here by inserting
1286      copies into the loop itself.  */
1287   insert_backedge_copies ();
1288
1289   eliminate_virtual_phis ();
1290
1291   if (dump_file && (dump_flags & TDF_DETAILS))
1292     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1293
1294   remove_ssa_form (flag_tree_ter && !flag_mudflap);
1295
1296   if (dump_file && (dump_flags & TDF_DETAILS))
1297     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1298
1299   cfun->gimple_df->in_ssa_p = false;
1300   return 0;
1301 }
1302
1303
1304 /* Define the parameters of the out of SSA pass.  */
1305
1306 struct tree_opt_pass pass_del_ssa =
1307 {
1308   "optimized",                          /* name */
1309   NULL,                                 /* gate */
1310   rewrite_out_of_ssa,                   /* execute */
1311   NULL,                                 /* sub */
1312   NULL,                                 /* next */
1313   0,                                    /* static_pass_number */
1314   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
1315   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1316   0,                                    /* properties_provided */
1317   /* ??? If TER is enabled, we also kill gimple.  */
1318   PROP_ssa,                             /* properties_destroyed */
1319   TODO_verify_ssa | TODO_verify_flow
1320     | TODO_verify_stmts,                /* todo_flags_start */
1321   TODO_dump_func
1322   | TODO_ggc_collect
1323   | TODO_remove_unused_locals,          /* todo_flags_finish */
1324   0                                     /* letter */
1325 };