gcc/tree-outof-ssa.c

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