gcc/tree-outof-ssa.c

   1 /* Convert a program in SSA form into Normal form.
   2    Copyright (C) 2004, 2005 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 "flags.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "ggc.h"
  31 #include "langhooks.h"
  32 #include "hard-reg-set.h"
  33 #include "basic-block.h"
  34 #include "output.h"
  35 #include "expr.h"
  36 #include "function.h"
  37 #include "diagnostic.h"
  38 #include "bitmap.h"
  39 #include "tree-flow.h"
  40 #include "tree-gimple.h"
  41 #include "tree-inline.h"
  42 #include "varray.h"
  43 #include "timevar.h"
  44 #include "hashtab.h"
  45 #include "tree-dump.h"
  46 #include "tree-ssa-live.h"
  47 #include "tree-pass.h"
  48 #include "toplev.h"
  49 #include "vecprim.h"
  50
  51 /* Flags to pass to remove_ssa_form.  */
  52
  53 #define SSANORM_PERFORM_TER             0x1
  54 #define SSANORM_COALESCE_PARTITIONS     0x4
  55
  56 /* Used to hold all the components required to do SSA PHI elimination.
  57    The node and pred/succ list is a simple linear list of nodes and
  58    edges represented as pairs of nodes.
  59
  60    The predecessor and successor list:  Nodes are entered in pairs, where
  61    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
  62    predecessors, all the odd elements are successors.
  63
  64    Rationale:
  65    When implemented as bitmaps, very large programs SSA->Normal times were
  66    being dominated by clearing the interference graph.
  67
  68    Typically this list of edges is extremely small since it only includes
  69    PHI results and uses from a single edge which have not coalesced with
  70    each other.  This means that no virtual PHI nodes are included, and
  71    empirical evidence suggests that the number of edges rarely exceed
  72    3, and in a bootstrap of GCC, the maximum size encountered was 7.
  73    This also limits the number of possible nodes that are involved to
  74    rarely more than 6, and in the bootstrap of gcc, the maximum number
  75    of nodes encountered was 12.  */
  76
  77 typedef struct _elim_graph {
  78   /* Size of the elimination vectors.  */
  79   int size;
  80
  81   /* List of nodes in the elimination graph.  */
  82   VEC(tree,heap) *nodes;
  83
  84   /*  The predecessor and successor edge list.  */
  85   VEC(int,heap) *edge_list;
  86
  87   /* Visited vector.  */
  88   sbitmap visited;
  89
  90   /* Stack for visited nodes.  */
  91   VEC(int,heap) *stack;
  92
  93   /* The variable partition map.  */
  94   var_map map;
  95
  96   /* Edge being eliminated by this graph.  */
  97   edge e;
  98
  99   /* List of constant copies to emit.  These are pushed on in pairs.  */
 100   VEC(tree,heap) *const_copies;
 101 } *elim_graph;
 102
 103
 104 /* Local functions.  */
 105 static tree create_temp (tree);
 106 static void insert_copy_on_edge (edge, tree, tree);
 107 static elim_graph new_elim_graph (int);
 108 static inline void delete_elim_graph (elim_graph);
 109 static inline void clear_elim_graph (elim_graph);
 110 static inline int elim_graph_size (elim_graph);
 111 static inline void elim_graph_add_node (elim_graph, tree);
 112 static inline void elim_graph_add_edge (elim_graph, int, int);
 113 static inline int elim_graph_remove_succ_edge (elim_graph, int);
 114
 115 static inline void eliminate_name (elim_graph, tree);
 116 static void eliminate_build (elim_graph, basic_block);
 117 static void elim_forward (elim_graph, int);
 118 static int elim_unvisited_predecessor (elim_graph, int);
 119 static void elim_backward (elim_graph, int);
 120 static void elim_create (elim_graph, int);
 121 static void eliminate_phi (edge, elim_graph);
 122 static tree_live_info_p coalesce_ssa_name (var_map, int);
 123 static void assign_vars (var_map);
 124 static bool replace_use_variable (var_map, use_operand_p, tree *);
 125 static bool replace_def_variable (var_map, def_operand_p, tree *);
 126 static void eliminate_virtual_phis (void);
 127 static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
 128 static void print_exprs (FILE *, const char *, tree, const char *, tree,
 129                          const char *);
 130 static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
 131                               tree);
 132
 133
 134 /* Create a temporary variable based on the type of variable T.  Use T's name
 135    as the prefix.  */
 136
 137 static tree
 138 create_temp (tree t)
 139 {
 140   tree tmp;
 141   const char *name = NULL;
 142   tree type;
 143
 144   if (TREE_CODE (t) == SSA_NAME)
 145     t = SSA_NAME_VAR (t);
 146
 147   gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
 148
 149   type = TREE_TYPE (t);
 150   tmp = DECL_NAME (t);
 151   if (tmp)
 152     name = IDENTIFIER_POINTER (tmp);
 153
 154   if (name == NULL)
 155     name = "temp";
 156   tmp = create_tmp_var (type, name);
 157
 158   if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t))
 159     {
 160       SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t));
 161       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
 162     }
 163   else if (!DECL_IGNORED_P (t))
 164     {
 165       SET_DECL_DEBUG_EXPR (tmp, t);
 166       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
 167     }
 168   DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
 169   DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
 170   add_referenced_var (tmp);
 171
 172   /* add_referenced_var will create the annotation and set up some
 173      of the flags in the annotation.  However, some flags we need to
 174      inherit from our original variable.  */
 175   var_ann (tmp)->symbol_mem_tag = var_ann (t)->symbol_mem_tag;
 176   if (is_call_clobbered (t))
 177     mark_call_clobbered (tmp, var_ann (t)->escape_mask);
 178
 179   return tmp;
 180 }
 181
 182
 183 /* This helper function fill insert a copy from a constant or variable SRC to
 184    variable DEST on edge E.  */
 185
 186 static void
 187 insert_copy_on_edge (edge e, tree dest, tree src)
 188 {
 189   tree copy;
 190
 191   copy = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (dest), dest, src);
 192   set_is_used (dest);
 193
 194   if (TREE_CODE (src) == ADDR_EXPR)
 195     src = TREE_OPERAND (src, 0);
 196   if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
 197     set_is_used (src);
 198
 199   if (dump_file && (dump_flags & TDF_DETAILS))
 200     {
 201       fprintf (dump_file,
 202                "Inserting a copy on edge BB%d->BB%d :",
 203                e->src->index,
 204                e->dest->index);
 205       print_generic_expr (dump_file, copy, dump_flags);
 206       fprintf (dump_file, "\n");
 207     }
 208
 209   bsi_insert_on_edge (e, copy);
 210 }
 211
 212
 213 /* Create an elimination graph with SIZE nodes and associated data
 214    structures.  */
 215
 216 static elim_graph
 217 new_elim_graph (int size)
 218 {
 219   elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
 220
 221   g->nodes = VEC_alloc (tree, heap, 30);
 222   g->const_copies = VEC_alloc (tree, heap, 20);
 223   g->edge_list = VEC_alloc (int, heap, 20);
 224   g->stack = VEC_alloc (int, heap, 30);
 225
 226   g->visited = sbitmap_alloc (size);
 227
 228   return g;
 229 }
 230
 231
 232 /* Empty elimination graph G.  */
 233
 234 static inline void
 235 clear_elim_graph (elim_graph g)
 236 {
 237   VEC_truncate (tree, g->nodes, 0);
 238   VEC_truncate (int, g->edge_list, 0);
 239 }
 240
 241
 242 /* Delete elimination graph G.  */
 243
 244 static inline void
 245 delete_elim_graph (elim_graph g)
 246 {
 247   sbitmap_free (g->visited);
 248   VEC_free (int, heap, g->stack);
 249   VEC_free (int, heap, g->edge_list);
 250   VEC_free (tree, heap, g->const_copies);
 251   VEC_free (tree, heap, g->nodes);
 252   free (g);
 253 }
 254
 255
 256 /* Return the number of nodes in graph G.  */
 257
 258 static inline int
 259 elim_graph_size (elim_graph g)
 260 {
 261   return VEC_length (tree, g->nodes);
 262 }
 263
 264
 265 /* Add NODE to graph G, if it doesn't exist already.  */
 266
 267 static inline void
 268 elim_graph_add_node (elim_graph g, tree node)
 269 {
 270   int x;
 271   tree t;
 272
 273   for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
 274     if (t == node)
 275       return;
 276   VEC_safe_push (tree, heap, g->nodes, node);
 277 }
 278
 279
 280 /* Add the edge PRED->SUCC to graph G.  */
 281
 282 static inline void
 283 elim_graph_add_edge (elim_graph g, int pred, int succ)
 284 {
 285   VEC_safe_push (int, heap, g->edge_list, pred);
 286   VEC_safe_push (int, heap, g->edge_list, succ);
 287 }
 288
 289
 290 /* Remove an edge from graph G for which NODE is the predecessor, and
 291    return the successor node.  -1 is returned if there is no such edge.  */
 292
 293 static inline int
 294 elim_graph_remove_succ_edge (elim_graph g, int node)
 295 {
 296   int y;
 297   unsigned x;
 298   for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
 299     if (VEC_index (int, g->edge_list, x) == node)
 300       {
 301         VEC_replace (int, g->edge_list, x, -1);
 302         y = VEC_index (int, g->edge_list, x + 1);
 303         VEC_replace (int, g->edge_list, x + 1, -1);
 304         return y;
 305       }
 306   return -1;
 307 }
 308
 309
 310 /* Find all the nodes in GRAPH which are successors to NODE in the
 311    edge list.  VAR will hold the partition number found.  CODE is the
 312    code fragment executed for every node found.  */
 313
 314 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE)                \
 315 do {                                                                    \
 316   unsigned x_;                                                          \
 317   int y_;                                                               \
 318   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
 319     {                                                                   \
 320       y_ = VEC_index (int, (GRAPH)->edge_list, x_);                     \
 321       if (y_ != (NODE))                                                 \
 322         continue;                                                       \
 323       (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1);              \
 324       CODE;                                                             \
 325     }                                                                   \
 326 } while (0)
 327
 328
 329 /* Find all the nodes which are predecessors of NODE in the edge list for
 330    GRAPH.  VAR will hold the partition number found.  CODE is the
 331    code fragment executed for every node found.  */
 332
 333 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE)                \
 334 do {                                                                    \
 335   unsigned x_;                                                          \
 336   int y_;                                                               \
 337   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
 338     {                                                                   \
 339       y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1);                 \
 340       if (y_ != (NODE))                                                 \
 341         continue;                                                       \
 342       (VAR) = VEC_index (int, (GRAPH)->edge_list, x_);                  \
 343       CODE;                                                             \
 344     }                                                                   \
 345 } while (0)
 346
 347
 348 /* Add T to elimination graph G.  */
 349
 350 static inline void
 351 eliminate_name (elim_graph g, tree T)
 352 {
 353   elim_graph_add_node (g, T);
 354 }
 355
 356
 357 /* Build elimination graph G for basic block BB on incoming PHI edge
 358    G->e.  */
 359
 360 static void
 361 eliminate_build (elim_graph g, basic_block B)
 362 {
 363   tree phi;
 364   tree T0, Ti;
 365   int p0, pi;
 366
 367   clear_elim_graph (g);
 368
 369   for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
 370     {
 371       T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
 372
 373       /* Ignore results which are not in partitions.  */
 374       if (T0 == NULL_TREE)
 375         continue;
 376
 377       Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
 378
 379       /* If this argument is a constant, or a SSA_NAME which is being
 380          left in SSA form, just queue a copy to be emitted on this
 381          edge.  */
 382       if (!phi_ssa_name_p (Ti)
 383           || (TREE_CODE (Ti) == SSA_NAME
 384               && var_to_partition (g->map, Ti) == NO_PARTITION))
 385         {
 386           /* Save constant copies until all other copies have been emitted
 387              on this edge.  */
 388           VEC_safe_push (tree, heap, g->const_copies, T0);
 389           VEC_safe_push (tree, heap, g->const_copies, Ti);
 390         }
 391       else
 392         {
 393           Ti = var_to_partition_to_var (g->map, Ti);
 394           if (T0 != Ti)
 395             {
 396               eliminate_name (g, T0);
 397               eliminate_name (g, Ti);
 398               p0 = var_to_partition (g->map, T0);
 399               pi = var_to_partition (g->map, Ti);
 400               elim_graph_add_edge (g, p0, pi);
 401             }
 402         }
 403     }
 404 }
 405
 406
 407 /* Push successors of T onto the elimination stack for G.  */
 408
 409 static void
 410 elim_forward (elim_graph g, int T)
 411 {
 412   int S;
 413   SET_BIT (g->visited, T);
 414   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
 415     {
 416       if (!TEST_BIT (g->visited, S))
 417         elim_forward (g, S);
 418     });
 419   VEC_safe_push (int, heap, g->stack, T);
 420 }
 421
 422
 423 /* Return 1 if there unvisited predecessors of T in graph G.  */
 424
 425 static int
 426 elim_unvisited_predecessor (elim_graph g, int T)
 427 {
 428   int P;
 429   FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 430     {
 431       if (!TEST_BIT (g->visited, P))
 432         return 1;
 433     });
 434   return 0;
 435 }
 436
 437 /* Process predecessors first, and insert a copy.  */
 438
 439 static void
 440 elim_backward (elim_graph g, int T)
 441 {
 442   int P;
 443   SET_BIT (g->visited, T);
 444   FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 445     {
 446       if (!TEST_BIT (g->visited, P))
 447         {
 448           elim_backward (g, P);
 449           insert_copy_on_edge (g->e,
 450                                partition_to_var (g->map, P),
 451                                partition_to_var (g->map, T));
 452         }
 453     });
 454 }
 455
 456 /* Insert required copies for T in graph G.  Check for a strongly connected
 457    region, and create a temporary to break the cycle if one is found.  */
 458
 459 static void
 460 elim_create (elim_graph g, int T)
 461 {
 462   tree U;
 463   int P, S;
 464
 465   if (elim_unvisited_predecessor (g, T))
 466     {
 467       U = create_temp (partition_to_var (g->map, T));
 468       insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
 469       FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 470         {
 471           if (!TEST_BIT (g->visited, P))
 472             {
 473               elim_backward (g, P);
 474               insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
 475             }
 476         });
 477     }
 478   else
 479     {
 480       S = elim_graph_remove_succ_edge (g, T);
 481       if (S != -1)
 482         {
 483           SET_BIT (g->visited, T);
 484           insert_copy_on_edge (g->e,
 485                                partition_to_var (g->map, T),
 486                                partition_to_var (g->map, S));
 487         }
 488     }
 489
 490 }
 491
 492 /* Eliminate all the phi nodes on edge E in graph G.  */
 493
 494 static void
 495 eliminate_phi (edge e, elim_graph g)
 496 {
 497   int x;
 498   basic_block B = e->dest;
 499
 500   gcc_assert (VEC_length (tree, g->const_copies) == 0);
 501
 502   /* Abnormal edges already have everything coalesced.  */
 503   if (e->flags & EDGE_ABNORMAL)
 504     return;
 505
 506   g->e = e;
 507
 508   eliminate_build (g, B);
 509
 510   if (elim_graph_size (g) != 0)
 511     {
 512       tree var;
 513
 514       sbitmap_zero (g->visited);
 515       VEC_truncate (int, g->stack, 0);
 516
 517       for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
 518         {
 519           int p = var_to_partition (g->map, var);
 520           if (!TEST_BIT (g->visited, p))
 521             elim_forward (g, p);
 522         }
 523
 524       sbitmap_zero (g->visited);
 525       while (VEC_length (int, g->stack) > 0)
 526         {
 527           x = VEC_pop (int, g->stack);
 528           if (!TEST_BIT (g->visited, x))
 529             elim_create (g, x);
 530         }
 531     }
 532
 533   /* If there are any pending constant copies, issue them now.  */
 534   while (VEC_length (tree, g->const_copies) > 0)
 535     {
 536       tree src, dest;
 537       src = VEC_pop (tree, g->const_copies);
 538       dest = VEC_pop (tree, g->const_copies);
 539       insert_copy_on_edge (e, dest, src);
 540     }
 541 }
 542
 543
 544 /* Shortcut routine to print messages to file F of the form:
 545    "STR1 EXPR1 STR2 EXPR2 STR3."  */
 546
 547 static void
 548 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
 549              tree expr2, const char *str3)
 550 {
 551   fprintf (f, "%s", str1);
 552   print_generic_expr (f, expr1, TDF_SLIM);
 553   fprintf (f, "%s", str2);
 554   print_generic_expr (f, expr2, TDF_SLIM);
 555   fprintf (f, "%s", str3);
 556 }
 557
 558
 559 /* Shortcut routine to print abnormal edge messages to file F of the form:
 560    "STR1 EXPR1 STR2 EXPR2 across edge E.  */
 561
 562 static void
 563 print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1,
 564                   const char *str2, tree expr2)
 565 {
 566   print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge");
 567   fprintf (f, " from BB%d->BB%d\n", e->src->index,
 568                e->dest->index);
 569 }
 570
 571
 572 /* Coalesce partitions in MAP which are live across abnormal edges in GRAPH.
 573    RV is the root variable groupings of the partitions in MAP.  Since code
 574    cannot be inserted on these edges, failure to coalesce something across
 575    an abnormal edge is an error.  */
 576
 577 static void
 578 coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv)
 579 {
 580   basic_block bb;
 581   edge e;
 582   tree phi, var, tmp;
 583   int x, y, z;
 584   edge_iterator ei;
 585
 586   /* Code cannot be inserted on abnormal edges. Look for all abnormal
 587      edges, and coalesce any PHI results with their arguments across
 588      that edge.  */
 589
 590   FOR_EACH_BB (bb)
 591     FOR_EACH_EDGE (e, ei, bb->succs)
 592       if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
 593         for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 594           {
 595             /* Visit each PHI on the destination side of this abnormal
 596                edge, and attempt to coalesce the argument with the result.  */
 597             var = PHI_RESULT (phi);
 598             x = var_to_partition (map, var);
 599
 600             /* Ignore results which are not relevant.  */
 601             if (x == NO_PARTITION)
 602               continue;
 603
 604             tmp = PHI_ARG_DEF (phi, e->dest_idx);
 605 #ifdef ENABLE_CHECKING
 606             if (!phi_ssa_name_p (tmp))
 607               {
 608                 print_exprs_edge (stderr, e,
 609                                   "\nConstant argument in PHI. Can't insert :",
 610                                   var, " = ", tmp);
 611                 internal_error ("SSA corruption");
 612               }
 613 #else
 614             gcc_assert (phi_ssa_name_p (tmp));
 615 #endif
 616             y = var_to_partition (map, tmp);
 617             gcc_assert (x != NO_PARTITION);
 618             gcc_assert (y != NO_PARTITION);
 619 #ifdef ENABLE_CHECKING
 620             if (root_var_find (rv, x) != root_var_find (rv, y))
 621               {
 622                 print_exprs_edge (stderr, e, "\nDifferent root vars: ",
 623                                   root_var (rv, root_var_find (rv, x)),
 624                                   " and ",
 625                                   root_var (rv, root_var_find (rv, y)));
 626                 internal_error ("SSA corruption");
 627               }
 628 #else
 629             gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
 630 #endif
 631
 632             if (x != y)
 633               {
 634 #ifdef ENABLE_CHECKING
 635                 if (conflict_graph_conflict_p (graph, x, y))
 636                   {
 637                     print_exprs_edge (stderr, e, "\n Conflict ",
 638                                       partition_to_var (map, x),
 639                                       " and ", partition_to_var (map, y));
 640                     internal_error ("SSA corruption");
 641                   }
 642 #else
 643                 gcc_assert (!conflict_graph_conflict_p (graph, x, y));
 644 #endif
 645
 646                 /* Now map the partitions back to their real variables.  */
 647                 var = partition_to_var (map, x);
 648                 tmp = partition_to_var (map, y);
 649                 if (dump_file && (dump_flags & TDF_DETAILS))
 650                   {
 651                     print_exprs_edge (dump_file, e,
 652                                       "ABNORMAL: Coalescing ",
 653                                       var, " and ", tmp);
 654                   }
 655                 z = var_union (map, var, tmp);
 656 #ifdef ENABLE_CHECKING
 657                 if (z == NO_PARTITION)
 658                   {
 659                     print_exprs_edge (stderr, e, "\nUnable to coalesce",
 660                                       partition_to_var (map, x), " and ",
 661                                       partition_to_var (map, y));
 662                     internal_error ("SSA corruption");
 663                   }
 664 #else
 665                 gcc_assert (z != NO_PARTITION);
 666 #endif
 667                 gcc_assert (z == x || z == y);
 668                 if (z == x)
 669                   conflict_graph_merge_regs (graph, x, y);
 670                 else
 671                   conflict_graph_merge_regs (graph, y, x);
 672               }
 673           }
 674 }
 675
 676 /* Coalesce potential copies via PHI arguments.  */
 677
 678 static void
 679 coalesce_phi_operands (var_map map, coalesce_list_p cl)
 680 {
 681   basic_block bb;
 682   tree phi;
 683
 684   FOR_EACH_BB (bb)
 685     {
 686       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 687         {
 688           tree res = PHI_RESULT (phi);
 689           int p = var_to_partition (map, res);
 690           int x;
 691
 692           if (p == NO_PARTITION)
 693             continue;
 694
 695           for (x = 0; x < PHI_NUM_ARGS (phi); x++)
 696             {
 697               tree arg = PHI_ARG_DEF (phi, x);
 698               int p2;
 699
 700               if (TREE_CODE (arg) != SSA_NAME)
 701                 continue;
 702               if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
 703                 continue;
 704               p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
 705               if (p2 != NO_PARTITION)
 706                 {
 707                   edge e = PHI_ARG_EDGE (phi, x);
 708                   add_coalesce (cl, p, p2,
 709                                 coalesce_cost (EDGE_FREQUENCY (e),
 710                                                maybe_hot_bb_p (bb),
 711                                                EDGE_CRITICAL_P (e)));
 712                 }
 713             }
 714         }
 715     }
 716 }
 717
 718 /* Coalesce all the result decls together.  */
 719
 720 static void
 721 coalesce_result_decls (var_map map, coalesce_list_p cl)
 722 {
 723   unsigned int i, x;
 724   tree var = NULL;
 725
 726   for (i = x = 0; x < num_var_partitions (map); x++)
 727     {
 728       tree p = partition_to_var (map, x);
 729       if (TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL)
 730         {
 731           if (var == NULL_TREE)
 732             {
 733               var = p;
 734               i = x;
 735             }
 736           else
 737             add_coalesce (cl, i, x,
 738                           coalesce_cost (EXIT_BLOCK_PTR->frequency,
 739                                          maybe_hot_bb_p (EXIT_BLOCK_PTR),
 740                                          false));
 741         }
 742     }
 743 }
 744
 745 /* Coalesce matching constraints in asms.  */
 746
 747 static void
 748 coalesce_asm_operands (var_map map, coalesce_list_p cl)
 749 {
 750   basic_block bb;
 751
 752   FOR_EACH_BB (bb)
 753     {
 754       block_stmt_iterator bsi;
 755       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 756         {
 757           tree stmt = bsi_stmt (bsi);
 758           unsigned long noutputs, i;
 759           tree *outputs, link;
 760
 761           if (TREE_CODE (stmt) != ASM_EXPR)
 762             continue;
 763
 764           noutputs = list_length (ASM_OUTPUTS (stmt));
 765           outputs = (tree *) alloca (noutputs * sizeof (tree));
 766           for (i = 0, link = ASM_OUTPUTS (stmt); link;
 767                ++i, link = TREE_CHAIN (link))
 768             outputs[i] = TREE_VALUE (link);
 769
 770           for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
 771             {
 772               const char *constraint
 773                 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
 774               tree input = TREE_VALUE (link);
 775               char *end;
 776               unsigned long match;
 777               int p1, p2;
 778
 779               if (TREE_CODE (input) != SSA_NAME && !DECL_P (input))
 780                 continue;
 781
 782               match = strtoul (constraint, &end, 10);
 783               if (match >= noutputs || end == constraint)
 784                 continue;
 785
 786               if (TREE_CODE (outputs[match]) != SSA_NAME
 787                   && !DECL_P (outputs[match]))
 788                 continue;
 789
 790               p1 = var_to_partition (map, outputs[match]);
 791               if (p1 == NO_PARTITION)
 792                 continue;
 793               p2 = var_to_partition (map, input);
 794               if (p2 == NO_PARTITION)
 795                 continue;
 796
 797               add_coalesce (cl, p1, p2, coalesce_cost (REG_BR_PROB_BASE,
 798                                                        maybe_hot_bb_p (bb),
 799                                                        false));
 800             }
 801         }
 802     }
 803 }
 804
 805 /* Reduce the number of live ranges in MAP.  Live range information is
 806    returned if FLAGS indicates that we are combining temporaries, otherwise
 807    NULL is returned.  The only partitions which are associated with actual
 808    variables at this point are those which are forced to be coalesced for
 809    various reason. (live on entry, live across abnormal edges, etc.).  */
 810
 811 static tree_live_info_p
 812 coalesce_ssa_name (var_map map, int flags)
 813 {
 814   unsigned num, x;
 815   sbitmap live;
 816   root_var_p rv;
 817   tree_live_info_p liveinfo;
 818   conflict_graph graph;
 819   coalesce_list_p cl = NULL;
 820   sbitmap_iterator sbi;
 821
 822   if (num_var_partitions (map) <= 1)
 823     return NULL;
 824
 825   liveinfo = calculate_live_ranges (map);
 826   rv = root_var_init (map);
 827
 828   /* Remove single element variable from the list.  */
 829   root_var_compact (rv);
 830
 831   cl = create_coalesce_list (map);
 832
 833   coalesce_phi_operands (map, cl);
 834   coalesce_result_decls (map, cl);
 835   coalesce_asm_operands (map, cl);
 836
 837   /* Build a conflict graph.  */
 838   graph = build_tree_conflict_graph (liveinfo, rv, cl);
 839
 840   if (cl)
 841     {
 842       if (dump_file && (dump_flags & TDF_DETAILS))
 843         {
 844           fprintf (dump_file, "Before sorting:\n");
 845           dump_coalesce_list (dump_file, cl);
 846         }
 847
 848       sort_coalesce_list (cl);
 849
 850       if (dump_file && (dump_flags & TDF_DETAILS))
 851         {
 852           fprintf (dump_file, "\nAfter sorting:\n");
 853           dump_coalesce_list (dump_file, cl);
 854         }
 855     }
 856
 857   /* Put the single element variables back in.  */
 858   root_var_decompact (rv);
 859
 860   /* First, coalesce all live on entry variables to their root variable.
 861      This will ensure the first use is coming from the correct location.  */
 862
 863   num = num_var_partitions (map);
 864   live = sbitmap_alloc (num);
 865   sbitmap_zero (live);
 866
 867   /* Set 'live' vector to indicate live on entry partitions.  */
 868   for (x = 0 ; x < num; x++)
 869     {
 870       tree var = partition_to_var (map, x);
 871       if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
 872         SET_BIT (live, x);
 873     }
 874
 875   delete_tree_live_info (liveinfo);
 876   liveinfo = NULL;
 877
 878   /* Assign root variable as partition representative for each live on entry
 879      partition.  */
 880   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, sbi)
 881     {
 882       tree var = root_var (rv, root_var_find (rv, x));
 883       var_ann_t ann = var_ann (var);
 884       /* If these aren't already coalesced...  */
 885       if (partition_to_var (map, x) != var)
 886         {
 887           /* This root variable should have not already been assigned
 888              to another partition which is not coalesced with this one.  */
 889           gcc_assert (!ann->out_of_ssa_tag);
 890
 891           if (dump_file && (dump_flags & TDF_DETAILS))
 892             {
 893               print_exprs (dump_file, "Must coalesce ",
 894                            partition_to_var (map, x),
 895                            " with the root variable ", var, ".\n");
 896             }
 897
 898           change_partition_var (map, var, x);
 899         }
 900     }
 901
 902   sbitmap_free (live);
 903
 904   /* Coalesce partitions live across abnormal edges.  */
 905   coalesce_abnormal_edges (map, graph, rv);
 906
 907   if (dump_file && (dump_flags & TDF_DETAILS))
 908     dump_var_map (dump_file, map);
 909
 910   /* Coalesce partitions.  */
 911   coalesce_tpa_members (rv, graph, map, cl,
 912                         ((dump_flags & TDF_DETAILS) ? dump_file
 913                          : NULL));
 914
 915   if (flags & SSANORM_COALESCE_PARTITIONS)
 916     coalesce_tpa_members (rv, graph, map, NULL,
 917                           ((dump_flags & TDF_DETAILS) ? dump_file
 918                            : NULL));
 919   if (cl)
 920     delete_coalesce_list (cl);
 921   root_var_delete (rv);
 922   conflict_graph_delete (graph);
 923
 924   return liveinfo;
 925 }
 926
 927
 928 /* Take the ssa-name var_map MAP, and assign real variables to each
 929    partition.  */
 930
 931 static void
 932 assign_vars (var_map map)
 933 {
 934   int x, i, num, rep;
 935   tree t, var;
 936   var_ann_t ann;
 937   root_var_p rv;
 938
 939   rv = root_var_init (map);
 940   if (!rv)
 941     return;
 942
 943   /* Coalescing may already have forced some partitions to their root
 944      variable. Find these and tag them.  */
 945
 946   num = num_var_partitions (map);
 947   for (x = 0; x < num; x++)
 948     {
 949       var = partition_to_var (map, x);
 950       if (TREE_CODE (var) != SSA_NAME)
 951         {
 952           /* Coalescing will already have verified that more than one
 953              partition doesn't have the same root variable. Simply marked
 954              the variable as assigned.  */
 955           ann = var_ann (var);
 956           ann->out_of_ssa_tag = 1;
 957           if (dump_file && (dump_flags & TDF_DETAILS))
 958             {
 959               fprintf (dump_file, "partition %d has variable ", x);
 960               print_generic_expr (dump_file, var, TDF_SLIM);
 961               fprintf (dump_file, " assigned to it.\n");
 962             }
 963
 964         }
 965     }
 966
 967   num = root_var_num (rv);
 968   for (x = 0; x < num; x++)
 969     {
 970       var = root_var (rv, x);
 971       ann = var_ann (var);
 972       for (i = root_var_first_partition (rv, x);
 973            i != ROOT_VAR_NONE;
 974            i = root_var_next_partition (rv, i))
 975         {
 976           t = partition_to_var (map, i);
 977
 978           if (t == var || TREE_CODE (t) != SSA_NAME)
 979             continue;
 980
 981           rep = var_to_partition (map, t);
 982
 983           if (!ann->out_of_ssa_tag)
 984             {
 985               if (dump_file && (dump_flags & TDF_DETAILS))
 986                 print_exprs (dump_file, "", t, "  --> ", var, "\n");
 987               change_partition_var (map, var, rep);
 988               continue;
 989             }
 990
 991           if (dump_file && (dump_flags & TDF_DETAILS))
 992             print_exprs (dump_file, "", t, " not coalesced with ", var,
 993                          "");
 994
 995           var = create_temp (t);
 996           change_partition_var (map, var, rep);
 997           ann = var_ann (var);
 998
 999           if (dump_file && (dump_flags & TDF_DETAILS))
1000             {
1001               fprintf (dump_file, " -->  New temp:  '");
1002               print_generic_expr (dump_file, var, TDF_SLIM);
1003               fprintf (dump_file, "'\n");
1004             }
1005         }
1006     }
1007
1008   root_var_delete (rv);
1009 }
1010
1011
1012 /* Replace use operand P with whatever variable it has been rewritten to based
1013    on the partitions in MAP.  EXPR is an optional expression vector over SSA
1014    versions which is used to replace P with an expression instead of a variable.
1015    If the stmt is changed, return true.  */
1016
1017 static inline bool
1018 replace_use_variable (var_map map, use_operand_p p, tree *expr)
1019 {
1020   tree new_var;
1021   tree var = USE_FROM_PTR (p);
1022
1023   /* Check if we are replacing this variable with an expression.  */
1024   if (expr)
1025     {
1026       int version = SSA_NAME_VERSION (var);
1027       if (expr[version])
1028         {
1029           tree new_expr = GIMPLE_STMT_OPERAND (expr[version], 1);
1030           SET_USE (p, new_expr);
1031           /* Clear the stmt's RHS, or GC might bite us.  */
1032           GIMPLE_STMT_OPERAND (expr[version], 1) = NULL_TREE;
1033           return true;
1034         }
1035     }
1036
1037   new_var = var_to_partition_to_var (map, var);
1038   if (new_var)
1039     {
1040       SET_USE (p, new_var);
1041       set_is_used (new_var);
1042       return true;
1043     }
1044   return false;
1045 }
1046
1047
1048 /* Replace def operand DEF_P with whatever variable it has been rewritten to
1049    based on the partitions in MAP.  EXPR is an optional expression vector over
1050    SSA versions which is used to replace DEF_P with an expression instead of a
1051    variable.  If the stmt is changed, return true.  */
1052
1053 static inline bool
1054 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
1055 {
1056   tree new_var;
1057   tree var = DEF_FROM_PTR (def_p);
1058
1059   /* Check if we are replacing this variable with an expression.  */
1060   if (expr)
1061     {
1062       int version = SSA_NAME_VERSION (var);
1063       if (expr[version])
1064         {
1065           tree new_expr = TREE_OPERAND (expr[version], 1);
1066           SET_DEF (def_p, new_expr);
1067           /* Clear the stmt's RHS, or GC might bite us.  */
1068           TREE_OPERAND (expr[version], 1) = NULL_TREE;
1069           return true;
1070         }
1071     }
1072
1073   new_var = var_to_partition_to_var (map, var);
1074   if (new_var)
1075     {
1076       SET_DEF (def_p, new_var);
1077       set_is_used (new_var);
1078       return true;
1079     }
1080   return false;
1081 }
1082
1083
1084 /* Remove any PHI node which is a virtual PHI.  */
1085
1086 static void
1087 eliminate_virtual_phis (void)
1088 {
1089   basic_block bb;
1090   tree phi, next;
1091
1092   FOR_EACH_BB (bb)
1093     {
1094       for (phi = phi_nodes (bb); phi; phi = next)
1095         {
1096           next = PHI_CHAIN (phi);
1097           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1098             {
1099 #ifdef ENABLE_CHECKING
1100               int i;
1101               /* There should be no arguments of this PHI which are in
1102                  the partition list, or we get incorrect results.  */
1103               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1104                 {
1105                   tree arg = PHI_ARG_DEF (phi, i);
1106                   if (TREE_CODE (arg) == SSA_NAME
1107                       && is_gimple_reg (SSA_NAME_VAR (arg)))
1108                     {
1109                       fprintf (stderr, "Argument of PHI is not virtual (");
1110                       print_generic_expr (stderr, arg, TDF_SLIM);
1111                       fprintf (stderr, "), but the result is :");
1112                       print_generic_stmt (stderr, phi, TDF_SLIM);
1113                       internal_error ("SSA corruption");
1114                     }
1115                 }
1116 #endif
1117               remove_phi_node (phi, NULL_TREE);
1118             }
1119         }
1120     }
1121 }
1122
1123
1124 /* This function will rewrite the current program using the variable mapping
1125    found in MAP.  If the replacement vector VALUES is provided, any
1126    occurrences of partitions with non-null entries in the vector will be
1127    replaced with the expression in the vector instead of its mapped
1128    variable.  */
1129
1130 static void
1131 rewrite_trees (var_map map, tree *values)
1132 {
1133   elim_graph g;
1134   basic_block bb;
1135   block_stmt_iterator si;
1136   edge e;
1137   tree phi;
1138   bool changed;
1139
1140 #ifdef ENABLE_CHECKING
1141   /* Search for PHIs where the destination has no partition, but one
1142      or more arguments has a partition.  This should not happen and can
1143      create incorrect code.  */
1144   FOR_EACH_BB (bb)
1145     {
1146       tree phi;
1147
1148       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1149         {
1150           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1151
1152           if (T0 == NULL_TREE)
1153             {
1154               int i;
1155
1156               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1157                 {
1158                   tree arg = PHI_ARG_DEF (phi, i);
1159
1160                   if (TREE_CODE (arg) == SSA_NAME
1161                       && var_to_partition (map, arg) != NO_PARTITION)
1162                     {
1163                       fprintf (stderr, "Argument of PHI is in a partition :(");
1164                       print_generic_expr (stderr, arg, TDF_SLIM);
1165                       fprintf (stderr, "), but the result is not :");
1166                       print_generic_stmt (stderr, phi, TDF_SLIM);
1167                       internal_error ("SSA corruption");
1168                     }
1169                 }
1170             }
1171         }
1172     }
1173 #endif
1174
1175   /* Replace PHI nodes with any required copies.  */
1176   g = new_elim_graph (map->num_partitions);
1177   g->map = map;
1178   FOR_EACH_BB (bb)
1179     {
1180       for (si = bsi_start (bb); !bsi_end_p (si); )
1181         {
1182           tree stmt = bsi_stmt (si);
1183           use_operand_p use_p, copy_use_p;
1184           def_operand_p def_p;
1185           bool remove = false, is_copy = false;
1186           int num_uses = 0;
1187           stmt_ann_t ann;
1188           ssa_op_iter iter;
1189
1190           ann = stmt_ann (stmt);
1191           changed = false;
1192
1193           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
1194               && (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == SSA_NAME))
1195             is_copy = true;
1196
1197           copy_use_p = NULL_USE_OPERAND_P;
1198           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1199             {
1200               if (replace_use_variable (map, use_p, values))
1201                 changed = true;
1202               copy_use_p = use_p;
1203               num_uses++;
1204             }
1205
1206           if (num_uses != 1)
1207             is_copy = false;
1208
1209           def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
1210
1211           if (def_p != NULL)
1212             {
1213               /* Mark this stmt for removal if it is the list of replaceable
1214                  expressions.  */
1215               if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
1216                 remove = true;
1217               else
1218                 {
1219                   if (replace_def_variable (map, def_p, NULL))
1220                     changed = true;
1221                   /* If both SSA_NAMEs coalesce to the same variable,
1222                      mark the now redundant copy for removal.  */
1223                   if (is_copy)
1224                     {
1225                       gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
1226                       if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
1227                         remove = true;
1228                     }
1229                 }
1230             }
1231           else
1232             FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1233               if (replace_def_variable (map, def_p, NULL))
1234                 changed = true;
1235
1236           /* Remove any stmts marked for removal.  */
1237           if (remove)
1238             bsi_remove (&si, true);
1239           else
1240             bsi_next (&si);
1241         }
1242
1243       phi = phi_nodes (bb);
1244       if (phi)
1245         {
1246           edge_iterator ei;
1247           FOR_EACH_EDGE (e, ei, bb->preds)
1248             eliminate_phi (e, g);
1249         }
1250     }
1251
1252   delete_elim_graph (g);
1253 }
1254
1255 /* These are the local work structures used to determine the best place to
1256    insert the copies that were placed on edges by the SSA->normal pass..  */
1257 static VEC(edge,heap) *edge_leader;
1258 static VEC(tree,heap) *stmt_list;
1259 static bitmap leader_has_match = NULL;
1260 static edge leader_match = NULL;
1261
1262
1263 /* Pass this function to make_forwarder_block so that all the edges with
1264    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
1265 static bool
1266 same_stmt_list_p (edge e)
1267 {
1268   return (e->aux == (PTR) leader_match) ? true : false;
1269 }
1270
1271
1272 /* Return TRUE if S1 and S2 are equivalent copies.  */
1273 static inline bool
1274 identical_copies_p (tree s1, tree s2)
1275 {
1276 #ifdef ENABLE_CHECKING
1277   gcc_assert (TREE_CODE (s1) == GIMPLE_MODIFY_STMT);
1278   gcc_assert (TREE_CODE (s2) == GIMPLE_MODIFY_STMT);
1279   gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s1, 0)));
1280   gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s2, 0)));
1281 #endif
1282
1283   if (GIMPLE_STMT_OPERAND (s1, 0) != GIMPLE_STMT_OPERAND (s2, 0))
1284     return false;
1285
1286   s1 = GIMPLE_STMT_OPERAND (s1, 1);
1287   s2 = GIMPLE_STMT_OPERAND (s2, 1);
1288
1289   if (s1 != s2)
1290     return false;
1291
1292   return true;
1293 }
1294
1295
1296 /* Compare the PENDING_STMT list for two edges, and return true if the lists
1297    contain the same sequence of copies.  */
1298
1299 static inline bool
1300 identical_stmt_lists_p (edge e1, edge e2)
1301 {
1302   tree t1 = PENDING_STMT (e1);
1303   tree t2 = PENDING_STMT (e2);
1304   tree_stmt_iterator tsi1, tsi2;
1305
1306   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
1307   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
1308
1309   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
1310        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
1311        tsi_next (&tsi1), tsi_next (&tsi2))
1312     {
1313       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
1314         break;
1315     }
1316
1317   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
1318     return false;
1319
1320   return true;
1321 }
1322
1323
1324 /* Allocate data structures used in analyze_edges_for_bb.   */
1325
1326 static void
1327 init_analyze_edges_for_bb (void)
1328 {
1329   edge_leader = VEC_alloc (edge, heap, 25);
1330   stmt_list = VEC_alloc (tree, heap, 25);
1331   leader_has_match = BITMAP_ALLOC (NULL);
1332 }
1333
1334
1335 /* Free data structures used in analyze_edges_for_bb.   */
1336
1337 static void
1338 fini_analyze_edges_for_bb (void)
1339 {
1340   VEC_free (edge, heap, edge_leader);
1341   VEC_free (tree, heap, stmt_list);
1342   BITMAP_FREE (leader_has_match);
1343 }
1344
1345
1346 /* Look at all the incoming edges to block BB, and decide where the best place
1347    to insert the stmts on each edge are, and perform those insertions.  */
1348
1349 static void
1350 analyze_edges_for_bb (basic_block bb)
1351 {
1352   edge e;
1353   edge_iterator ei;
1354   int count;
1355   unsigned int x;
1356   bool have_opportunity;
1357   block_stmt_iterator bsi;
1358   tree stmt;
1359   edge single_edge = NULL;
1360   bool is_label;
1361   edge leader;
1362
1363   count = 0;
1364
1365   /* Blocks which contain at least one abnormal edge cannot use
1366      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
1367      found on edges in these block.  */
1368   have_opportunity = true;
1369   FOR_EACH_EDGE (e, ei, bb->preds)
1370     if (e->flags & EDGE_ABNORMAL)
1371       {
1372         have_opportunity = false;
1373         break;
1374       }
1375
1376   if (!have_opportunity)
1377     {
1378       FOR_EACH_EDGE (e, ei, bb->preds)
1379         if (PENDING_STMT (e))
1380           bsi_commit_one_edge_insert (e, NULL);
1381       return;
1382     }
1383   /* Find out how many edges there are with interesting pending stmts on them.
1384      Commit the stmts on edges we are not interested in.  */
1385   FOR_EACH_EDGE (e, ei, bb->preds)
1386     {
1387       if (PENDING_STMT (e))
1388         {
1389           gcc_assert (!(e->flags & EDGE_ABNORMAL));
1390           if (e->flags & EDGE_FALLTHRU)
1391             {
1392               bsi = bsi_start (e->src);
1393               if (!bsi_end_p (bsi))
1394                 {
1395                   stmt = bsi_stmt (bsi);
1396                   bsi_next (&bsi);
1397                   gcc_assert (stmt != NULL_TREE);
1398                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
1399                   /* Punt if it has non-label stmts, or isn't local.  */
1400                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
1401                       || !bsi_end_p (bsi))
1402                     {
1403                       bsi_commit_one_edge_insert (e, NULL);
1404                       continue;
1405                     }
1406                 }
1407             }
1408           single_edge = e;
1409           count++;
1410         }
1411     }
1412
1413   /* If there aren't at least 2 edges, no sharing will happen.  */
1414   if (count < 2)
1415     {
1416       if (single_edge)
1417         bsi_commit_one_edge_insert (single_edge, NULL);
1418       return;
1419     }
1420
1421   /* Ensure that we have empty worklists.  */
1422 #ifdef ENABLE_CHECKING
1423   gcc_assert (VEC_length (edge, edge_leader) == 0);
1424   gcc_assert (VEC_length (tree, stmt_list) == 0);
1425   gcc_assert (bitmap_empty_p (leader_has_match));
1426 #endif
1427
1428   /* Find the "leader" block for each set of unique stmt lists.  Preference is
1429      given to FALLTHRU blocks since they would need a GOTO to arrive at another
1430      block.  The leader edge destination is the block which all the other edges
1431      with the same stmt list will be redirected to.  */
1432   have_opportunity = false;
1433   FOR_EACH_EDGE (e, ei, bb->preds)
1434     {
1435       if (PENDING_STMT (e))
1436         {
1437           bool found = false;
1438
1439           /* Look for the same stmt list in edge leaders list.  */
1440           for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1441             {
1442               if (identical_stmt_lists_p (leader, e))
1443                 {
1444                   /* Give this edge the same stmt list pointer.  */
1445                   PENDING_STMT (e) = NULL;
1446                   e->aux = leader;
1447                   bitmap_set_bit (leader_has_match, x);
1448                   have_opportunity = found = true;
1449                   break;
1450                 }
1451             }
1452
1453           /* If no similar stmt list, add this edge to the leader list.  */
1454           if (!found)
1455             {
1456               VEC_safe_push (edge, heap, edge_leader, e);
1457               VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
1458             }
1459         }
1460      }
1461
1462   /* If there are no similar lists, just issue the stmts.  */
1463   if (!have_opportunity)
1464     {
1465       for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1466         bsi_commit_one_edge_insert (leader, NULL);
1467       VEC_truncate (edge, edge_leader, 0);
1468       VEC_truncate (tree, stmt_list, 0);
1469       bitmap_clear (leader_has_match);
1470       return;
1471     }
1472
1473
1474   if (dump_file)
1475     fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
1476              bb->index);
1477
1478
1479   /* For each common list, create a forwarding block and issue the stmt's
1480      in that block.  */
1481   for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
1482     if (bitmap_bit_p (leader_has_match, x))
1483       {
1484         edge new_edge;
1485         block_stmt_iterator bsi;
1486         tree curr_stmt_list;
1487
1488         leader_match = leader;
1489
1490         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
1491            for various PHI manipulations, so it gets cleared when calls are
1492            made to make_forwarder_block(). So make sure the edge is clear,
1493            and use the saved stmt list.  */
1494         PENDING_STMT (leader) = NULL;
1495         leader->aux = leader;
1496         curr_stmt_list = VEC_index (tree, stmt_list, x);
1497
1498         new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
1499                                          NULL);
1500         bb = new_edge->dest;
1501         if (dump_file)
1502           {
1503             fprintf (dump_file, "Splitting BB %d for Common stmt list.  ",
1504                      leader->dest->index);
1505             fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
1506             print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS);
1507           }
1508
1509         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
1510           {
1511             e->aux = NULL;
1512             if (dump_file)
1513               fprintf (dump_file, "  Edge (%d->%d) lands here.\n",
1514                        e->src->index, e->dest->index);
1515           }
1516
1517         bsi = bsi_last (leader->dest);
1518         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
1519
1520         leader_match = NULL;
1521         /* We should never get a new block now.  */
1522       }
1523     else
1524       {
1525         PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
1526         bsi_commit_one_edge_insert (leader, NULL);
1527       }
1528
1529
1530   /* Clear the working data structures.  */
1531   VEC_truncate (edge, edge_leader, 0);
1532   VEC_truncate (tree, stmt_list, 0);
1533   bitmap_clear (leader_has_match);
1534 }
1535
1536
1537 /* This function will analyze the insertions which were performed on edges,
1538    and decide whether they should be left on that edge, or whether it is more
1539    efficient to emit some subset of them in a single block.  All stmts are
1540    inserted somewhere.  */
1541
1542 static void
1543 perform_edge_inserts (void)
1544 {
1545   basic_block bb;
1546
1547   if (dump_file)
1548     fprintf(dump_file, "Analyzing Edge Insertions.\n");
1549
1550   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
1551      incrementally update the dominator information.  Since we don't
1552      need dominator information after this pass, go ahead and free the
1553      dominator information.  */
1554   free_dominance_info (CDI_DOMINATORS);
1555   free_dominance_info (CDI_POST_DOMINATORS);
1556
1557   /* Allocate data structures used in analyze_edges_for_bb.   */
1558   init_analyze_edges_for_bb ();
1559
1560   FOR_EACH_BB (bb)
1561     analyze_edges_for_bb (bb);
1562
1563   analyze_edges_for_bb (EXIT_BLOCK_PTR);
1564
1565   /* Free data structures used in analyze_edges_for_bb.   */
1566   fini_analyze_edges_for_bb ();
1567
1568 #ifdef ENABLE_CHECKING
1569   {
1570     edge_iterator ei;
1571     edge e;
1572     FOR_EACH_BB (bb)
1573       {
1574         FOR_EACH_EDGE (e, ei, bb->preds)
1575           {
1576             if (PENDING_STMT (e))
1577               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
1578                      e->src->index, e->dest->index);
1579           }
1580         FOR_EACH_EDGE (e, ei, bb->succs)
1581           {
1582             if (PENDING_STMT (e))
1583               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
1584                      e->src->index, e->dest->index);
1585           }
1586       }
1587     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1588       {
1589         if (PENDING_STMT (e))
1590           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
1591                  e->src->index, e->dest->index);
1592       }
1593     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
1594       {
1595         if (PENDING_STMT (e))
1596           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
1597                  e->src->index, e->dest->index);
1598       }
1599   }
1600 #endif
1601 }
1602
1603
1604 /* Remove the variables specified in MAP from SSA form.  FLAGS indicate what
1605    options should be used.  */
1606
1607 static void
1608 remove_ssa_form (var_map map, int flags)
1609 {
1610   tree_live_info_p liveinfo;
1611   basic_block bb;
1612   tree phi, next;
1613   tree *values = NULL;
1614
1615   /* If we are not combining temps, don't calculate live ranges for variables
1616      with only one SSA version.  */
1617   compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
1618
1619   if (dump_file && (dump_flags & TDF_DETAILS))
1620     dump_var_map (dump_file, map);
1621
1622   liveinfo = coalesce_ssa_name (map, flags);
1623
1624   /* Make sure even single occurrence variables are in the list now.  */
1625   compact_var_map (map, VARMAP_NORMAL);
1626
1627   if (dump_file && (dump_flags & TDF_DETAILS))
1628     {
1629       fprintf (dump_file, "After Coalescing:\n");
1630       dump_var_map (dump_file, map);
1631     }
1632
1633   if (flags & SSANORM_PERFORM_TER)
1634     {
1635       values = find_replaceable_exprs (map);
1636       if (values && dump_file && (dump_flags & TDF_DETAILS))
1637         dump_replaceable_exprs (dump_file, values);
1638     }
1639
1640   /* Assign real variables to the partitions now.  */
1641   assign_vars (map);
1642
1643   if (dump_file && (dump_flags & TDF_DETAILS))
1644     {
1645       fprintf (dump_file, "After Root variable replacement:\n");
1646       dump_var_map (dump_file, map);
1647     }
1648
1649   if (liveinfo)
1650     delete_tree_live_info (liveinfo);
1651
1652   rewrite_trees (map, values);
1653
1654   if (values)
1655     free (values);
1656
1657   /* Remove phi nodes which have been translated back to real variables.  */
1658   FOR_EACH_BB (bb)
1659     {
1660       for (phi = phi_nodes (bb); phi; phi = next)
1661         {
1662           next = PHI_CHAIN (phi);
1663           remove_phi_node (phi, NULL_TREE);
1664         }
1665     }
1666
1667   /* we no longer maintain the SSA operand cache at this point.  */
1668   fini_ssa_operands ();
1669
1670   /* If any copies were inserted on edges, analyze and insert them now.  */
1671   perform_edge_inserts ();
1672 }
1673
1674 /* Search every PHI node for arguments associated with backedges which
1675    we can trivially determine will need a copy (the argument is either
1676    not an SSA_NAME or the argument has a different underlying variable
1677    than the PHI result).
1678
1679    Insert a copy from the PHI argument to a new destination at the
1680    end of the block with the backedge to the top of the loop.  Update
1681    the PHI argument to reference this new destination.  */
1682
1683 static void
1684 insert_backedge_copies (void)
1685 {
1686   basic_block bb;
1687
1688   FOR_EACH_BB (bb)
1689     {
1690       tree phi;
1691
1692       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1693         {
1694           tree result = PHI_RESULT (phi);
1695           tree result_var;
1696           int i;
1697
1698           if (!is_gimple_reg (result))
1699             continue;
1700
1701           result_var = SSA_NAME_VAR (result);
1702           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1703             {
1704               tree arg = PHI_ARG_DEF (phi, i);
1705               edge e = PHI_ARG_EDGE (phi, i);
1706
1707               /* If the argument is not an SSA_NAME, then we will
1708                  need a constant initialization.  If the argument is
1709                  an SSA_NAME with a different underlying variable and
1710                  we are not combining temporaries, then we will
1711                  need a copy statement.  */
1712               if ((e->flags & EDGE_DFS_BACK)
1713                   && (TREE_CODE (arg) != SSA_NAME
1714                       || SSA_NAME_VAR (arg) != result_var))
1715                 {
1716                   tree stmt, name, last = NULL;
1717                   block_stmt_iterator bsi;
1718
1719                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
1720                   if (!bsi_end_p (bsi))
1721                     last = bsi_stmt (bsi);
1722
1723                   /* In theory the only way we ought to get back to the
1724                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
1725                      However, better safe than sorry.
1726
1727                      If the block ends with a control statement or
1728                      something that might throw, then we have to
1729                      insert this assignment before the last
1730                      statement.  Else insert it after the last statement.  */
1731                   if (last && stmt_ends_bb_p (last))
1732                     {
1733                       /* If the last statement in the block is the definition
1734                          site of the PHI argument, then we can't insert
1735                          anything after it.  */
1736                       if (TREE_CODE (arg) == SSA_NAME
1737                           && SSA_NAME_DEF_STMT (arg) == last)
1738                         continue;
1739                     }
1740
1741                   /* Create a new instance of the underlying
1742                      variable of the PHI result.  */
1743                   stmt = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (result_var),
1744                                  NULL_TREE, PHI_ARG_DEF (phi, i));
1745                   name = make_ssa_name (result_var, stmt);
1746                   GIMPLE_STMT_OPERAND (stmt, 0) = name;
1747
1748                   /* Insert the new statement into the block and update
1749                      the PHI node.  */
1750                   if (last && stmt_ends_bb_p (last))
1751                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
1752                   else
1753                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
1754                   SET_PHI_ARG_DEF (phi, i, name);
1755                 }
1756             }
1757         }
1758     }
1759 }
1760
1761 /* Take the current function out of SSA form, as described in
1762    R. Morgan, ``Building an Optimizing Compiler'',
1763    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
1764
1765 static unsigned int
1766 rewrite_out_of_ssa (void)
1767 {
1768   var_map map;
1769   int ssa_flags = 0;
1770
1771   /* If elimination of a PHI requires inserting a copy on a backedge,
1772      then we will have to split the backedge which has numerous
1773      undesirable performance effects.
1774
1775      A significant number of such cases can be handled here by inserting
1776      copies into the loop itself.  */
1777   insert_backedge_copies ();
1778
1779   if (!flag_tree_live_range_split)
1780     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
1781
1782   eliminate_virtual_phis ();
1783
1784   if (dump_file && (dump_flags & TDF_DETAILS))
1785     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1786
1787   map = create_ssa_var_map ();
1788
1789   if (flag_tree_ter && !flag_mudflap)
1790     ssa_flags |= SSANORM_PERFORM_TER;
1791
1792   remove_ssa_form (map, ssa_flags);
1793
1794   if (dump_file && (dump_flags & TDF_DETAILS))
1795     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1796
1797   /* Flush out flow graph and SSA data.  */
1798   delete_var_map (map);
1799
1800   cfun->gimple_df->in_ssa_p = false;
1801   return 0;
1802 }
1803
1804
1805 /* Define the parameters of the out of SSA pass.  */
1806
1807 struct tree_opt_pass pass_del_ssa =
1808 {
1809   "optimized",                          /* name */
1810   NULL,                                 /* gate */
1811   rewrite_out_of_ssa,                   /* execute */
1812   NULL,                                 /* sub */
1813   NULL,                                 /* next */
1814   0,                                    /* static_pass_number */
1815   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
1816   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
1817   0,                                    /* properties_provided */
1818   /* ??? If TER is enabled, we also kill gimple.  */
1819   PROP_ssa,                             /* properties_destroyed */
1820   TODO_verify_ssa | TODO_verify_flow
1821     | TODO_verify_stmts,                /* todo_flags_start */
1822   TODO_dump_func
1823   | TODO_ggc_collect
1824   | TODO_remove_unused_locals,          /* todo_flags_finish */
1825   0                                     /* letter */
1826 };