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             {
 762               if (changed)
 763                 if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
 764                   tree_purge_dead_eh_edges (bb);
 765               bsi_next (&si);
 766             }
 767         }
 768
 769       phi = phi_nodes (bb);
 770       if (phi)
 771         {
 772           edge_iterator ei;
 773           FOR_EACH_EDGE (e, ei, bb->preds)
 774             eliminate_phi (e, g);
 775         }
 776     }
 777
 778   delete_elim_graph (g);
 779 }
 780
 781 /* These are the local work structures used to determine the best place to
 782    insert the copies that were placed on edges by the SSA->normal pass..  */
 783 static VEC(edge,heap) *edge_leader;
 784 static VEC(tree,heap) *stmt_list;
 785 static bitmap leader_has_match = NULL;
 786 static edge leader_match = NULL;
 787
 788
 789 /* Pass this function to make_forwarder_block so that all the edges with
 790    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  E is the
 791    edge to test for a match.  */
 792
 793 static inline bool
 794 same_stmt_list_p (edge e)
 795 {
 796   return (e->aux == (PTR) leader_match) ? true : false;
 797 }
 798
 799
 800 /* Return TRUE if S1 and S2 are equivalent copies.  */
 801
 802 static inline bool
 803 identical_copies_p (const_tree s1, const_tree s2)
 804 {
 805 #ifdef ENABLE_CHECKING
 806   gcc_assert (TREE_CODE (s1) == GIMPLE_MODIFY_STMT);
 807   gcc_assert (TREE_CODE (s2) == GIMPLE_MODIFY_STMT);
 808   gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s1, 0)));
 809   gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s2, 0)));
 810 #endif
 811
 812   if (GIMPLE_STMT_OPERAND (s1, 0) != GIMPLE_STMT_OPERAND (s2, 0))
 813     return false;
 814
 815   s1 = GIMPLE_STMT_OPERAND (s1, 1);
 816   s2 = GIMPLE_STMT_OPERAND (s2, 1);
 817
 818   if (s1 != s2)
 819     return false;
 820
 821   return true;
 822 }
 823
 824
 825 /* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists
 826    contain the same sequence of copies.  */
 827
 828 static inline bool
 829 identical_stmt_lists_p (const_edge e1, const_edge e2)
 830 {
 831   tree t1 = PENDING_STMT (e1);
 832   tree t2 = PENDING_STMT (e2);
 833   tree_stmt_iterator tsi1, tsi2;
 834
 835   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
 836   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
 837
 838   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
 839        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
 840        tsi_next (&tsi1), tsi_next (&tsi2))
 841     {
 842       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
 843         break;
 844     }
 845
 846   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
 847     return false;
 848
 849   return true;
 850 }
 851
 852
 853 /* Allocate data structures used in analyze_edges_for_bb.   */
 854
 855 static void
 856 init_analyze_edges_for_bb (void)
 857 {
 858   edge_leader = VEC_alloc (edge, heap, 25);
 859   stmt_list = VEC_alloc (tree, heap, 25);
 860   leader_has_match = BITMAP_ALLOC (NULL);
 861 }
 862
 863
 864 /* Free data structures used in analyze_edges_for_bb.   */
 865
 866 static void
 867 fini_analyze_edges_for_bb (void)
 868 {
 869   VEC_free (edge, heap, edge_leader);
 870   VEC_free (tree, heap, stmt_list);
 871   BITMAP_FREE (leader_has_match);
 872 }
 873
 874
 875 /* Look at all the incoming edges to block BB, and decide where the best place
 876    to insert the stmts on each edge are, and perform those insertions.  */
 877
 878 static void
 879 analyze_edges_for_bb (basic_block bb)
 880 {
 881   edge e;
 882   edge_iterator ei;
 883   int count;
 884   unsigned int x;
 885   bool have_opportunity;
 886   block_stmt_iterator bsi;
 887   tree stmt;
 888   edge single_edge = NULL;
 889   bool is_label;
 890   edge leader;
 891
 892   count = 0;
 893
 894   /* Blocks which contain at least one abnormal edge cannot use
 895      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
 896      found on edges in these block.  */
 897   have_opportunity = true;
 898   FOR_EACH_EDGE (e, ei, bb->preds)
 899     if (e->flags & EDGE_ABNORMAL)
 900       {
 901         have_opportunity = false;
 902         break;
 903       }
 904
 905   if (!have_opportunity)
 906     {
 907       FOR_EACH_EDGE (e, ei, bb->preds)
 908         if (PENDING_STMT (e))
 909           bsi_commit_one_edge_insert (e, NULL);
 910       return;
 911     }
 912
 913   /* Find out how many edges there are with interesting pending stmts on them.
 914      Commit the stmts on edges we are not interested in.  */
 915   FOR_EACH_EDGE (e, ei, bb->preds)
 916     {
 917       if (PENDING_STMT (e))
 918         {
 919           gcc_assert (!(e->flags & EDGE_ABNORMAL));
 920           if (e->flags & EDGE_FALLTHRU)
 921             {
 922               bsi = bsi_start (e->src);
 923               if (!bsi_end_p (bsi))
 924                 {
 925                   stmt = bsi_stmt (bsi);
 926                   bsi_next (&bsi);
 927                   gcc_assert (stmt != NULL_TREE);
 928                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
 929                   /* Punt if it has non-label stmts, or isn't local.  */
 930                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
 931                       || !bsi_end_p (bsi))
 932                     {
 933                       bsi_commit_one_edge_insert (e, NULL);
 934                       continue;
 935                     }
 936                 }
 937             }
 938           single_edge = e;
 939           count++;
 940         }
 941     }
 942
 943   /* If there aren't at least 2 edges, no sharing will happen.  */
 944   if (count < 2)
 945     {
 946       if (single_edge)
 947         bsi_commit_one_edge_insert (single_edge, NULL);
 948       return;
 949     }
 950
 951   /* Ensure that we have empty worklists.  */
 952 #ifdef ENABLE_CHECKING
 953   gcc_assert (VEC_length (edge, edge_leader) == 0);
 954   gcc_assert (VEC_length (tree, stmt_list) == 0);
 955   gcc_assert (bitmap_empty_p (leader_has_match));
 956 #endif
 957
 958   /* Find the "leader" block for each set of unique stmt lists.  Preference is
 959      given to FALLTHRU blocks since they would need a GOTO to arrive at another
 960      block.  The leader edge destination is the block which all the other edges
 961      with the same stmt list will be redirected to.  */
 962   have_opportunity = false;
 963   FOR_EACH_EDGE (e, ei, bb->preds)
 964     {
 965       if (PENDING_STMT (e))
 966         {
 967           bool found = false;
 968
 969           /* Look for the same stmt list in edge leaders list.  */
 970           for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
 971             {
 972               if (identical_stmt_lists_p (leader, e))
 973                 {
 974                   /* Give this edge the same stmt list pointer.  */
 975                   PENDING_STMT (e) = NULL;
 976                   e->aux = leader;
 977                   bitmap_set_bit (leader_has_match, x);
 978                   have_opportunity = found = true;
 979                   break;
 980                 }
 981             }
 982
 983           /* If no similar stmt list, add this edge to the leader list.  */
 984           if (!found)
 985             {
 986               VEC_safe_push (edge, heap, edge_leader, e);
 987               VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
 988             }
 989         }
 990      }
 991
 992   /* If there are no similar lists, just issue the stmts.  */
 993   if (!have_opportunity)
 994     {
 995       for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
 996         bsi_commit_one_edge_insert (leader, NULL);
 997       VEC_truncate (edge, edge_leader, 0);
 998       VEC_truncate (tree, stmt_list, 0);
 999       bitmap_clear (leader_has_match);
1000       return;
1001     }
1002
1003   if (dump_file)
1004     fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
1005              bb->index);
1006
1007   /* For each common list, create a forwarding block and issue the stmt's
1008      in that block.  */
1009   for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1010     if (bitmap_bit_p (leader_has_match, x))
1011       {
1012         edge new_edge;
1013         block_stmt_iterator bsi;
1014         tree curr_stmt_list;
1015
1016         leader_match = leader;
1017
1018         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
1019            for various PHI manipulations, so it gets cleared when calls are
1020            made to make_forwarder_block(). So make sure the edge is clear,
1021            and use the saved stmt list.  */
1022         PENDING_STMT (leader) = NULL;
1023         leader->aux = leader;
1024         curr_stmt_list = VEC_index (tree, stmt_list, x);
1025
1026         new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
1027                                          NULL);
1028         bb = new_edge->dest;
1029         if (dump_file)
1030           {
1031             fprintf (dump_file, "Splitting BB %d for Common stmt list.  ",
1032                      leader->dest->index);
1033             fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
1034             print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS);
1035           }
1036
1037         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
1038           {
1039             e->aux = NULL;
1040             if (dump_file)
1041               fprintf (dump_file, "  Edge (%d->%d) lands here.\n",
1042                        e->src->index, e->dest->index);
1043           }
1044
1045         bsi = bsi_last (leader->dest);
1046         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
1047
1048         leader_match = NULL;
1049         /* We should never get a new block now.  */
1050       }
1051     else
1052       {
1053         PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
1054         bsi_commit_one_edge_insert (leader, NULL);
1055       }
1056
1057
1058   /* Clear the working data structures.  */
1059   VEC_truncate (edge, edge_leader, 0);
1060   VEC_truncate (tree, stmt_list, 0);
1061   bitmap_clear (leader_has_match);
1062 }
1063
1064
1065 /* This function will analyze the insertions which were performed on edges,
1066    and decide whether they should be left on that edge, or whether it is more
1067    efficient to emit some subset of them in a single block.  All stmts are
1068    inserted somewhere.  */
1069
1070 static void
1071 perform_edge_inserts (void)
1072 {
1073   basic_block bb;
1074
1075   if (dump_file)
1076     fprintf(dump_file, "Analyzing Edge Insertions.\n");
1077
1078   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
1079      incrementally update the dominator information.  Since we don't
1080      need dominator information after this pass, go ahead and free the
1081      dominator information.  */
1082   free_dominance_info (CDI_DOMINATORS);
1083   free_dominance_info (CDI_POST_DOMINATORS);
1084
1085   /* Allocate data structures used in analyze_edges_for_bb.   */
1086   init_analyze_edges_for_bb ();
1087
1088   FOR_EACH_BB (bb)
1089     analyze_edges_for_bb (bb);
1090
1091   analyze_edges_for_bb (EXIT_BLOCK_PTR);
1092
1093   /* Free data structures used in analyze_edges_for_bb.   */
1094   fini_analyze_edges_for_bb ();
1095
1096 #ifdef ENABLE_CHECKING
1097   {
1098     edge_iterator ei;
1099     edge e;
1100     FOR_EACH_BB (bb)
1101       {
1102         FOR_EACH_EDGE (e, ei, bb->preds)
1103           {
1104             if (PENDING_STMT (e))
1105               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
1106                      e->src->index, e->dest->index);
1107           }
1108         FOR_EACH_EDGE (e, ei, bb->succs)
1109           {
1110             if (PENDING_STMT (e))
1111               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
1112                      e->src->index, e->dest->index);
1113           }
1114       }
1115     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1116       {
1117         if (PENDING_STMT (e))
1118           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
1119                  e->src->index, e->dest->index);
1120       }
1121     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1122       {
1123         if (PENDING_STMT (e))
1124           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
1125                  e->src->index, e->dest->index);
1126       }
1127   }
1128 #endif
1129 }
1130
1131
1132 /* Remove the ssa-names in the current function and translate them into normal
1133    compiler variables.  PERFORM_TER is true if Temporary Expression Replacement
1134    should also be used.  */
1135
1136 static void
1137 remove_ssa_form (bool perform_ter)
1138 {
1139   basic_block bb;
1140   tree phi, next;
1141   tree *values = NULL;
1142   var_map map;
1143
1144   map = coalesce_ssa_name ();
1145
1146   /* Return to viewing the variable list as just all reference variables after
1147      coalescing has been performed.  */
1148   partition_view_normal (map, false);
1149
1150   if (dump_file && (dump_flags & TDF_DETAILS))
1151     {
1152       fprintf (dump_file, "After Coalescing:\n");
1153       dump_var_map (dump_file, map);
1154     }
1155
1156   if (perform_ter)
1157     {
1158       values = find_replaceable_exprs (map);
1159       if (values && dump_file && (dump_flags & TDF_DETAILS))
1160         dump_replaceable_exprs (dump_file, values);
1161     }
1162
1163   /* Assign real variables to the partitions now.  */
1164   assign_vars (map);
1165
1166   if (dump_file && (dump_flags & TDF_DETAILS))
1167     {
1168       fprintf (dump_file, "After Base variable replacement:\n");
1169       dump_var_map (dump_file, map);
1170     }
1171
1172   rewrite_trees (map, values);
1173
1174   if (values)
1175     free (values);
1176
1177   /* Remove PHI nodes which have been translated back to real variables.  */
1178   FOR_EACH_BB (bb)
1179     {
1180       for (phi = phi_nodes (bb); phi; phi = next)
1181         {
1182           next = PHI_CHAIN (phi);
1183           remove_phi_node (phi, NULL_TREE, true);
1184         }
1185     }
1186
1187   /* If any copies were inserted on edges, analyze and insert them now.  */
1188   perform_edge_inserts ();
1189
1190   delete_var_map (map);
1191 }
1192
1193
1194 /* Search every PHI node for arguments associated with backedges which
1195    we can trivially determine will need a copy (the argument is either
1196    not an SSA_NAME or the argument has a different underlying variable
1197    than the PHI result).
1198
1199    Insert a copy from the PHI argument to a new destination at the
1200    end of the block with the backedge to the top of the loop.  Update
1201    the PHI argument to reference this new destination.  */
1202
1203 static void
1204 insert_backedge_copies (void)
1205 {
1206   basic_block bb;
1207
1208   FOR_EACH_BB (bb)
1209     {
1210       tree phi;
1211
1212       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1213         {
1214           tree result = PHI_RESULT (phi);
1215           tree result_var;
1216           int i;
1217
1218           if (!is_gimple_reg (result))
1219             continue;
1220
1221           result_var = SSA_NAME_VAR (result);
1222           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1223             {
1224               tree arg = PHI_ARG_DEF (phi, i);
1225               edge e = PHI_ARG_EDGE (phi, i);
1226
1227               /* If the argument is not an SSA_NAME, then we will need a
1228                  constant initialization.  If the argument is an SSA_NAME with
1229                  a different underlying variable then a copy statement will be
1230                  needed.  */
1231               if ((e->flags & EDGE_DFS_BACK)
1232                   && (TREE_CODE (arg) != SSA_NAME
1233                       || SSA_NAME_VAR (arg) != result_var))
1234                 {
1235                   tree stmt, name, last = NULL;
1236                   block_stmt_iterator bsi;
1237
1238                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
1239                   if (!bsi_end_p (bsi))
1240                     last = bsi_stmt (bsi);
1241
1242                   /* In theory the only way we ought to get back to the
1243                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
1244                      However, better safe than sorry.
1245                      If the block ends with a control statement or
1246                      something that might throw, then we have to
1247                      insert this assignment before the last
1248                      statement.  Else insert it after the last statement.  */
1249                   if (last && stmt_ends_bb_p (last))
1250                     {
1251                       /* If the last statement in the block is the definition
1252                          site of the PHI argument, then we can't insert
1253                          anything after it.  */
1254                       if (TREE_CODE (arg) == SSA_NAME
1255                           && SSA_NAME_DEF_STMT (arg) == last)
1256                         continue;
1257                     }
1258
1259                   /* Create a new instance of the underlying variable of the
1260                      PHI result.  */
1261                   stmt = build_gimple_modify_stmt (NULL_TREE,
1262                                                    PHI_ARG_DEF (phi, i));
1263                   name = make_ssa_name (result_var, stmt);
1264                   GIMPLE_STMT_OPERAND (stmt, 0) = name;
1265
1266                   /* Insert the new statement into the block and update
1267                      the PHI node.  */
1268                   if (last && stmt_ends_bb_p (last))
1269                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
1270                   else
1271                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
1272                   SET_PHI_ARG_DEF (phi, i, name);
1273                 }
1274             }
1275         }
1276     }
1277 }
1278
1279 /* Take the current function out of SSA form, translating PHIs as described in
1280    R. Morgan, ``Building an Optimizing Compiler'',
1281    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
1282
1283 static unsigned int
1284 rewrite_out_of_ssa (void)
1285 {
1286   /* If elimination of a PHI requires inserting a copy on a backedge,
1287      then we will have to split the backedge which has numerous
1288      undesirable performance effects.
1289
1290      A significant number of such cases can be handled here by inserting
1291      copies into the loop itself.  */
1292   insert_backedge_copies ();
1293
1294   eliminate_virtual_phis ();
1295
1296   if (dump_file && (dump_flags & TDF_DETAILS))
1297     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1298
1299   remove_ssa_form (flag_tree_ter && !flag_mudflap);
1300
1301   if (dump_file && (dump_flags & TDF_DETAILS))
1302     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1303
1304   cfun->gimple_df->in_ssa_p = false;
1305   return 0;
1306 }
1307
1308
1309 /* Define the parameters of the out of SSA pass.  */
1310
1311 struct tree_opt_pass pass_del_ssa =
1312 {
1313   "optimized",                          /* name */
1314   NULL,                                 /* gate */
1315   rewrite_out_of_ssa,                   /* execute */
1316   NULL,                                 /* sub */
1317   NULL,                                 /* next */
1318   0,                                    /* static_pass_number */
1319   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
1320   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1321   0,                                    /* properties_provided */
1322   /* ??? If TER is enabled, we also kill gimple.  */
1323   PROP_ssa,                             /* properties_destroyed */
1324   TODO_verify_ssa | TODO_verify_flow
1325     | TODO_verify_stmts,                /* todo_flags_start */
1326   TODO_dump_func
1327   | TODO_ggc_collect
1328   | TODO_remove_unused_locals,          /* todo_flags_finish */
1329   0                                     /* letter */
1330 };