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 (MODIFY_EXPR, 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_on_entry (map);
 826   calculate_live_on_exit (liveinfo);
 827   rv = root_var_init (map);
 828
 829   /* Remove single element variable from the list.  */
 830   root_var_compact (rv);
 831
 832   cl = create_coalesce_list (map);
 833
 834   coalesce_phi_operands (map, cl);
 835   coalesce_result_decls (map, cl);
 836   coalesce_asm_operands (map, cl);
 837
 838   /* Build a conflict graph.  */
 839   graph = build_tree_conflict_graph (liveinfo, rv, cl);
 840
 841   if (cl)
 842     {
 843       if (dump_file && (dump_flags & TDF_DETAILS))
 844         {
 845           fprintf (dump_file, "Before sorting:\n");
 846           dump_coalesce_list (dump_file, cl);
 847         }
 848
 849       sort_coalesce_list (cl);
 850
 851       if (dump_file && (dump_flags & TDF_DETAILS))
 852         {
 853           fprintf (dump_file, "\nAfter sorting:\n");
 854           dump_coalesce_list (dump_file, cl);
 855         }
 856     }
 857
 858   /* Put the single element variables back in.  */
 859   root_var_decompact (rv);
 860
 861   /* First, coalesce all live on entry variables to their root variable.
 862      This will ensure the first use is coming from the correct location.  */
 863
 864   num = num_var_partitions (map);
 865   live = sbitmap_alloc (num);
 866   sbitmap_zero (live);
 867
 868   /* Set 'live' vector to indicate live on entry partitions.  */
 869   for (x = 0 ; x < num; x++)
 870     {
 871       tree var = partition_to_var (map, x);
 872       if (gimple_default_def (cfun, SSA_NAME_VAR (var)) == var)
 873         SET_BIT (live, x);
 874     }
 875
 876   delete_tree_live_info (liveinfo);
 877   liveinfo = NULL;
 878
 879   /* Assign root variable as partition representative for each live on entry
 880      partition.  */
 881   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, sbi)
 882     {
 883       tree var = root_var (rv, root_var_find (rv, x));
 884       var_ann_t ann = var_ann (var);
 885       /* If these aren't already coalesced...  */
 886       if (partition_to_var (map, x) != var)
 887         {
 888           /* This root variable should have not already been assigned
 889              to another partition which is not coalesced with this one.  */
 890           gcc_assert (!ann->out_of_ssa_tag);
 891
 892           if (dump_file && (dump_flags & TDF_DETAILS))
 893             {
 894               print_exprs (dump_file, "Must coalesce ",
 895                            partition_to_var (map, x),
 896                            " with the root variable ", var, ".\n");
 897             }
 898
 899           change_partition_var (map, var, x);
 900         }
 901     }
 902
 903   sbitmap_free (live);
 904
 905   /* Coalesce partitions live across abnormal edges.  */
 906   coalesce_abnormal_edges (map, graph, rv);
 907
 908   if (dump_file && (dump_flags & TDF_DETAILS))
 909     dump_var_map (dump_file, map);
 910
 911   /* Coalesce partitions.  */
 912   coalesce_tpa_members (rv, graph, map, cl,
 913                         ((dump_flags & TDF_DETAILS) ? dump_file
 914                          : NULL));
 915
 916   if (flags & SSANORM_COALESCE_PARTITIONS)
 917     coalesce_tpa_members (rv, graph, map, NULL,
 918                           ((dump_flags & TDF_DETAILS) ? dump_file
 919                            : NULL));
 920   if (cl)
 921     delete_coalesce_list (cl);
 922   root_var_delete (rv);
 923   conflict_graph_delete (graph);
 924
 925   return liveinfo;
 926 }
 927
 928
 929 /* Take the ssa-name var_map MAP, and assign real variables to each
 930    partition.  */
 931
 932 static void
 933 assign_vars (var_map map)
 934 {
 935   int x, i, num, rep;
 936   tree t, var;
 937   var_ann_t ann;
 938   root_var_p rv;
 939
 940   rv = root_var_init (map);
 941   if (!rv)
 942     return;
 943
 944   /* Coalescing may already have forced some partitions to their root
 945      variable. Find these and tag them.  */
 946
 947   num = num_var_partitions (map);
 948   for (x = 0; x < num; x++)
 949     {
 950       var = partition_to_var (map, x);
 951       if (TREE_CODE (var) != SSA_NAME)
 952         {
 953           /* Coalescing will already have verified that more than one
 954              partition doesn't have the same root variable. Simply marked
 955              the variable as assigned.  */
 956           ann = var_ann (var);
 957           ann->out_of_ssa_tag = 1;
 958           if (dump_file && (dump_flags & TDF_DETAILS))
 959             {
 960               fprintf (dump_file, "partition %d has variable ", x);
 961               print_generic_expr (dump_file, var, TDF_SLIM);
 962               fprintf (dump_file, " assigned to it.\n");
 963             }
 964
 965         }
 966     }
 967
 968   num = root_var_num (rv);
 969   for (x = 0; x < num; x++)
 970     {
 971       var = root_var (rv, x);
 972       ann = var_ann (var);
 973       for (i = root_var_first_partition (rv, x);
 974            i != ROOT_VAR_NONE;
 975            i = root_var_next_partition (rv, i))
 976         {
 977           t = partition_to_var (map, i);
 978
 979           if (t == var || TREE_CODE (t) != SSA_NAME)
 980             continue;
 981
 982           rep = var_to_partition (map, t);
 983
 984           if (!ann->out_of_ssa_tag)
 985             {
 986               if (dump_file && (dump_flags & TDF_DETAILS))
 987                 print_exprs (dump_file, "", t, "  --> ", var, "\n");
 988               change_partition_var (map, var, rep);
 989               continue;
 990             }
 991
 992           if (dump_file && (dump_flags & TDF_DETAILS))
 993             print_exprs (dump_file, "", t, " not coalesced with ", var,
 994                          "");
 995
 996           var = create_temp (t);
 997           change_partition_var (map, var, rep);
 998           ann = var_ann (var);
 999
1000           if (dump_file && (dump_flags & TDF_DETAILS))
1001             {
1002               fprintf (dump_file, " -->  New temp:  '");
1003               print_generic_expr (dump_file, var, TDF_SLIM);
1004               fprintf (dump_file, "'\n");
1005             }
1006         }
1007     }
1008
1009   root_var_delete (rv);
1010 }
1011
1012
1013 /* Replace use operand P with whatever variable it has been rewritten to based
1014    on the partitions in MAP.  EXPR is an optional expression vector over SSA
1015    versions which is used to replace P with an expression instead of a variable.
1016    If the stmt is changed, return true.  */
1017
1018 static inline bool
1019 replace_use_variable (var_map map, use_operand_p p, tree *expr)
1020 {
1021   tree new_var;
1022   tree var = USE_FROM_PTR (p);
1023
1024   /* Check if we are replacing this variable with an expression.  */
1025   if (expr)
1026     {
1027       int version = SSA_NAME_VERSION (var);
1028       if (expr[version])
1029         {
1030           tree new_expr = TREE_OPERAND (expr[version], 1);
1031           SET_USE (p, new_expr);
1032           /* Clear the stmt's RHS, or GC might bite us.  */
1033           TREE_OPERAND (expr[version], 1) = NULL_TREE;
1034           return true;
1035         }
1036     }
1037
1038   new_var = var_to_partition_to_var (map, var);
1039   if (new_var)
1040     {
1041       SET_USE (p, new_var);
1042       set_is_used (new_var);
1043       return true;
1044     }
1045   return false;
1046 }
1047
1048
1049 /* Replace def operand DEF_P with whatever variable it has been rewritten to
1050    based on the partitions in MAP.  EXPR is an optional expression vector over
1051    SSA versions which is used to replace DEF_P with an expression instead of a
1052    variable.  If the stmt is changed, return true.  */
1053
1054 static inline bool
1055 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
1056 {
1057   tree new_var;
1058   tree var = DEF_FROM_PTR (def_p);
1059
1060   /* Check if we are replacing this variable with an expression.  */
1061   if (expr)
1062     {
1063       int version = SSA_NAME_VERSION (var);
1064       if (expr[version])
1065         {
1066           tree new_expr = TREE_OPERAND (expr[version], 1);
1067           SET_DEF (def_p, new_expr);
1068           /* Clear the stmt's RHS, or GC might bite us.  */
1069           TREE_OPERAND (expr[version], 1) = NULL_TREE;
1070           return true;
1071         }
1072     }
1073
1074   new_var = var_to_partition_to_var (map, var);
1075   if (new_var)
1076     {
1077       SET_DEF (def_p, new_var);
1078       set_is_used (new_var);
1079       return true;
1080     }
1081   return false;
1082 }
1083
1084
1085 /* Remove any PHI node which is a virtual PHI.  */
1086
1087 static void
1088 eliminate_virtual_phis (void)
1089 {
1090   basic_block bb;
1091   tree phi, next;
1092
1093   FOR_EACH_BB (bb)
1094     {
1095       for (phi = phi_nodes (bb); phi; phi = next)
1096         {
1097           next = PHI_CHAIN (phi);
1098           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1099             {
1100 #ifdef ENABLE_CHECKING
1101               int i;
1102               /* There should be no arguments of this PHI which are in
1103                  the partition list, or we get incorrect results.  */
1104               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1105                 {
1106                   tree arg = PHI_ARG_DEF (phi, i);
1107                   if (TREE_CODE (arg) == SSA_NAME
1108                       && is_gimple_reg (SSA_NAME_VAR (arg)))
1109                     {
1110                       fprintf (stderr, "Argument of PHI is not virtual (");
1111                       print_generic_expr (stderr, arg, TDF_SLIM);
1112                       fprintf (stderr, "), but the result is :");
1113                       print_generic_stmt (stderr, phi, TDF_SLIM);
1114                       internal_error ("SSA corruption");
1115                     }
1116                 }
1117 #endif
1118               remove_phi_node (phi, NULL_TREE);
1119             }
1120         }
1121     }
1122 }
1123
1124
1125 /* Temporary Expression Replacement (TER)
1126
1127    Replace SSA version variables during out-of-ssa with their defining
1128    expression if there is only one use of the variable.
1129
1130    A pass is made through the function, one block at a time.  No cross block
1131    information is tracked.
1132
1133    Variables which only have one use, and whose defining stmt is considered
1134    a replaceable expression (see check_replaceable) are entered into
1135    consideration by adding a list of dependent partitions to the version_info
1136    vector for that ssa_name_version.  This information comes from the partition
1137    mapping for each USE.  At the same time, the partition_dep_list vector for
1138    these partitions have this version number entered into their lists.
1139
1140    When the use of a replaceable ssa_variable is encountered, the dependence
1141    list in version_info[] is moved to the "pending_dependence" list in case
1142    the current expression is also replaceable. (To be determined later in
1143    processing this stmt.) version_info[] for the version is then updated to
1144    point to the defining stmt and the 'replaceable' bit is set.
1145
1146    Any partition which is defined by a statement 'kills' any expression which
1147    is dependent on this partition.  Every ssa version in the partitions'
1148    dependence list is removed from future consideration.
1149
1150    All virtual references are lumped together.  Any expression which is
1151    dependent on any virtual variable (via a VUSE) has a dependence added
1152    to the special partition defined by VIRTUAL_PARTITION.
1153
1154    Whenever a V_MAY_DEF is seen, all expressions dependent this
1155    VIRTUAL_PARTITION are removed from consideration.
1156
1157    At the end of a basic block, all expression are removed from consideration
1158    in preparation for the next block.
1159
1160    The end result is a vector over SSA_NAME_VERSION which is passed back to
1161    rewrite_out_of_ssa.  As the SSA variables are being rewritten, instead of
1162    replacing the SSA_NAME tree element with the partition it was assigned,
1163    it is replaced with the RHS of the defining expression.  */
1164
1165
1166 /* Dependency list element.  This can contain either a partition index or a
1167    version number, depending on which list it is in.  */
1168
1169 typedef struct value_expr_d
1170 {
1171   int value;
1172   struct value_expr_d *next;
1173 } *value_expr_p;
1174
1175
1176 /* Temporary Expression Replacement (TER) table information.  */
1177
1178 typedef struct temp_expr_table_d
1179 {
1180   var_map map;
1181   void **version_info;
1182   bitmap *expr_vars;
1183   value_expr_p *partition_dep_list;
1184   bitmap replaceable;
1185   bool saw_replaceable;
1186   int virtual_partition;
1187   bitmap partition_in_use;
1188   value_expr_p free_list;
1189   value_expr_p pending_dependence;
1190 } *temp_expr_table_p;
1191
1192 /* Used to indicate a dependency on V_MAY_DEFs.  */
1193 #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
1194
1195 static temp_expr_table_p new_temp_expr_table (var_map);
1196 static tree *free_temp_expr_table (temp_expr_table_p);
1197 static inline value_expr_p new_value_expr (temp_expr_table_p);
1198 static inline void free_value_expr (temp_expr_table_p, value_expr_p);
1199 static inline value_expr_p find_value_in_list (value_expr_p, int,
1200                                                value_expr_p *);
1201 static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
1202 static inline void add_info_to_list (temp_expr_table_p, value_expr_p *,
1203                                      value_expr_p);
1204 static value_expr_p remove_value_from_list (value_expr_p *, int);
1205 static void add_dependence (temp_expr_table_p, int, tree);
1206 static bool check_replaceable (temp_expr_table_p, tree);
1207 static void finish_expr (temp_expr_table_p, int, bool);
1208 static void mark_replaceable (temp_expr_table_p, tree);
1209 static inline void kill_expr (temp_expr_table_p, int, bool);
1210 static inline void kill_virtual_exprs (temp_expr_table_p, bool);
1211 static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
1212 static tree *find_replaceable_exprs (var_map);
1213 static void dump_replaceable_exprs (FILE *, tree *);
1214
1215
1216 /* Create a new TER table for MAP.  */
1217
1218 static temp_expr_table_p
1219 new_temp_expr_table (var_map map)
1220 {
1221   temp_expr_table_p t;
1222
1223   t = XNEW (struct temp_expr_table_d);
1224   t->map = map;
1225
1226   t->version_info = XCNEWVEC (void *, num_ssa_names + 1);
1227   t->expr_vars = XCNEWVEC (bitmap, num_ssa_names + 1);
1228   t->partition_dep_list = XCNEWVEC (value_expr_p,
1229                                     num_var_partitions (map) + 1);
1230
1231   t->replaceable = BITMAP_ALLOC (NULL);
1232   t->partition_in_use = BITMAP_ALLOC (NULL);
1233
1234   t->saw_replaceable = false;
1235   t->virtual_partition = num_var_partitions (map);
1236   t->free_list = NULL;
1237   t->pending_dependence = NULL;
1238
1239   return t;
1240 }
1241
1242
1243 /* Free TER table T.  If there are valid replacements, return the expression
1244    vector.  */
1245
1246 static tree *
1247 free_temp_expr_table (temp_expr_table_p t)
1248 {
1249   value_expr_p p;
1250   tree *ret = NULL;
1251   unsigned i;
1252
1253 #ifdef ENABLE_CHECKING
1254   unsigned x;
1255   for (x = 0; x <= num_var_partitions (t->map); x++)
1256     gcc_assert (!t->partition_dep_list[x]);
1257 #endif
1258
1259   while ((p = t->free_list))
1260     {
1261       t->free_list = p->next;
1262       free (p);
1263     }
1264
1265   BITMAP_FREE (t->partition_in_use);
1266   BITMAP_FREE (t->replaceable);
1267
1268   for (i = 0; i <= num_ssa_names; i++)
1269     if (t->expr_vars[i])
1270       BITMAP_FREE (t->expr_vars[i]);
1271   free (t->expr_vars);
1272
1273   free (t->partition_dep_list);
1274   if (t->saw_replaceable)
1275     ret = (tree *)t->version_info;
1276   else
1277     free (t->version_info);
1278
1279   free (t);
1280   return ret;
1281 }
1282
1283
1284 /* Allocate a new value list node. Take it from the free list in TABLE if
1285    possible.  */
1286
1287 static inline value_expr_p
1288 new_value_expr (temp_expr_table_p table)
1289 {
1290   value_expr_p p;
1291   if (table->free_list)
1292     {
1293       p = table->free_list;
1294       table->free_list = p->next;
1295     }
1296   else
1297     p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
1298
1299   return p;
1300 }
1301
1302
1303 /* Add value list node P to the free list in TABLE.  */
1304
1305 static inline void
1306 free_value_expr (temp_expr_table_p table, value_expr_p p)
1307 {
1308   p->next = table->free_list;
1309   table->free_list = p;
1310 }
1311
1312
1313 /* Find VALUE if it's in LIST.  Return a pointer to the list object if found,
1314    else return NULL.  If LAST_PTR is provided, it will point to the previous
1315    item upon return, or NULL if this is the first item in the list.  */
1316
1317 static inline value_expr_p
1318 find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
1319 {
1320   value_expr_p curr;
1321   value_expr_p last = NULL;
1322
1323   for (curr = list; curr; last = curr, curr = curr->next)
1324     {
1325       if (curr->value == value)
1326         break;
1327     }
1328   if (last_ptr)
1329     *last_ptr = last;
1330   return curr;
1331 }
1332
1333
1334 /* Add VALUE to LIST, if it isn't already present.  TAB is the expression
1335    table */
1336
1337 static inline void
1338 add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
1339 {
1340   value_expr_p info;
1341
1342   if (!find_value_in_list (*list, value, NULL))
1343     {
1344       info = new_value_expr (tab);
1345       info->value = value;
1346       info->next = *list;
1347       *list = info;
1348     }
1349 }
1350
1351
1352 /* Add value node INFO if it's value isn't already in LIST.  Free INFO if
1353    it is already in the list. TAB is the expression table.  */
1354
1355 static inline void
1356 add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
1357 {
1358   if (find_value_in_list (*list, info->value, NULL))
1359     free_value_expr (tab, info);
1360   else
1361     {
1362       info->next = *list;
1363       *list = info;
1364     }
1365 }
1366
1367
1368 /* Look for VALUE in LIST.  If found, remove it from the list and return it's
1369    pointer.  */
1370
1371 static value_expr_p
1372 remove_value_from_list (value_expr_p *list, int value)
1373 {
1374   value_expr_p info, last;
1375
1376   info = find_value_in_list (*list, value, &last);
1377   if (!info)
1378     return NULL;
1379   if (!last)
1380     *list = info->next;
1381   else
1382     last->next = info->next;
1383
1384   return info;
1385 }
1386
1387
1388 /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is
1389    replaceable by an expression, add a dependence each of the elements of the
1390    expression.  These are contained in the pending list.  TAB is the
1391    expression table.  */
1392
1393 static void
1394 add_dependence (temp_expr_table_p tab, int version, tree var)
1395 {
1396   int i, x;
1397   value_expr_p info;
1398
1399   i = SSA_NAME_VERSION (var);
1400   if (bitmap_bit_p (tab->replaceable, i))
1401     {
1402       /* This variable is being substituted, so use whatever dependences
1403          were queued up when we marked this as replaceable earlier.  */
1404       while ((info = tab->pending_dependence))
1405         {
1406           tab->pending_dependence = info->next;
1407           /* Get the partition this variable was dependent on. Reuse this
1408              object to represent the current  expression instead.  */
1409           x = info->value;
1410           info->value = version;
1411           add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
1412           add_value_to_list (tab,
1413                              (value_expr_p *)&(tab->version_info[version]), x);
1414           bitmap_set_bit (tab->partition_in_use, x);
1415         }
1416     }
1417   else
1418     {
1419       i = var_to_partition (tab->map, var);
1420       gcc_assert (i != NO_PARTITION);
1421       add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
1422       add_value_to_list (tab,
1423                          (value_expr_p *)&(tab->version_info[version]), i);
1424       bitmap_set_bit (tab->partition_in_use, i);
1425     }
1426 }
1427
1428
1429 /* Check if expression STMT is suitable for replacement in table TAB.  If so,
1430    create an expression entry.  Return true if this stmt is replaceable.  */
1431
1432 static bool
1433 check_replaceable (temp_expr_table_p tab, tree stmt)
1434 {
1435   tree var, def, basevar;
1436   int version;
1437   ssa_op_iter iter;
1438   tree call_expr;
1439   bitmap def_vars, use_vars;
1440
1441   if (TREE_CODE (stmt) != MODIFY_EXPR)
1442     return false;
1443
1444   /* Punt if there is more than 1 def, or more than 1 use.  */
1445   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
1446   if (!def)
1447     return false;
1448
1449   if (num_imm_uses (def) != 1)
1450     return false;
1451
1452   /* There must be no V_MAY_DEFS or V_MUST_DEFS.  */
1453   if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF))))
1454     return false;
1455
1456   /* Float expressions must go through memory if float-store is on.  */
1457   if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1458     return false;
1459
1460   /* Calls to functions with side-effects cannot be replaced.  */
1461   if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
1462     {
1463       int call_flags = call_expr_flags (call_expr);
1464       if (TREE_SIDE_EFFECTS (call_expr)
1465           && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1466         return false;
1467     }
1468
1469   version = SSA_NAME_VERSION (def);
1470   basevar = SSA_NAME_VAR (def);
1471   def_vars = BITMAP_ALLOC (NULL);
1472   bitmap_set_bit (def_vars, DECL_UID (basevar));
1473
1474   /* Add this expression to the dependency list for each use partition.  */
1475   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1476     {
1477       add_dependence (tab, version, var);
1478
1479       use_vars = tab->expr_vars[SSA_NAME_VERSION (var)];
1480       if (use_vars)
1481         bitmap_ior_into (def_vars, use_vars);
1482     }
1483   tab->expr_vars[version] = def_vars;
1484
1485   /* If there are VUSES, add a dependence on virtual defs.  */
1486   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
1487     {
1488       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
1489                          VIRTUAL_PARTITION (tab));
1490       add_value_to_list (tab,
1491                          &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]),
1492                          version);
1493       bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1494     }
1495
1496   return true;
1497 }
1498
1499
1500 /* This function will remove the expression for VERSION from replacement
1501    consideration.n table TAB  If 'replace' is true, it is marked as
1502    replaceable, otherwise not.  */
1503
1504 static void
1505 finish_expr (temp_expr_table_p tab, int version, bool replace)
1506 {
1507   value_expr_p info, tmp;
1508   int partition;
1509
1510   /* Remove this expression from its dependent lists.  The partition dependence
1511      list is retained and transfered later to whomever uses this version.  */
1512   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1513     {
1514       partition = info->value;
1515       gcc_assert (tab->partition_dep_list[partition]);
1516       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
1517                                     version);
1518       gcc_assert (tmp);
1519       free_value_expr (tab, tmp);
1520       /* Only clear the bit when the dependency list is emptied via
1521          a replacement. Otherwise kill_expr will take care of it.  */
1522       if (!(tab->partition_dep_list[partition]) && replace)
1523         bitmap_clear_bit (tab->partition_in_use, partition);
1524       tmp = info->next;
1525       if (!replace)
1526         free_value_expr (tab, info);
1527     }
1528
1529   if (replace)
1530     {
1531       tab->saw_replaceable = true;
1532       bitmap_set_bit (tab->replaceable, version);
1533     }
1534   else
1535     {
1536       gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1537       tab->version_info[version] = NULL;
1538     }
1539 }
1540
1541
1542 /* Mark the expression associated with VAR as replaceable, and enter
1543    the defining stmt into the version_info table TAB.  */
1544
1545 static void
1546 mark_replaceable (temp_expr_table_p tab, tree var)
1547 {
1548   value_expr_p info;
1549   int version = SSA_NAME_VERSION (var);
1550   finish_expr (tab, version, true);
1551
1552   /* Move the dependence list to the pending list.  */
1553   if (tab->version_info[version])
1554     {
1555       info = (value_expr_p) tab->version_info[version];
1556       for ( ; info->next; info = info->next)
1557         continue;
1558       info->next = tab->pending_dependence;
1559       tab->pending_dependence = (value_expr_p)tab->version_info[version];
1560     }
1561
1562   tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1563 }
1564
1565
1566 /* This function marks any expression in TAB which is dependent on PARTITION
1567    as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
1568    should have its bit cleared.  Since this routine can be called within an
1569    EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
1570
1571 static inline void
1572 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1573 {
1574   value_expr_p ptr;
1575
1576   /* Mark every active expr dependent on this var as not replaceable.  */
1577   while ((ptr = tab->partition_dep_list[partition]) != NULL)
1578     finish_expr (tab, ptr->value, false);
1579
1580   if (clear_bit)
1581     bitmap_clear_bit (tab->partition_in_use, partition);
1582 }
1583
1584
1585 /* This function kills all expressions in TAB which are dependent on virtual
1586    DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
1587
1588 static inline void
1589 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1590 {
1591   kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1592 }
1593
1594
1595 /* This function processes basic block BB, and looks for variables which can
1596    be replaced by their expressions.  Results are stored in TAB.  */
1597
1598 static void
1599 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1600 {
1601   block_stmt_iterator bsi;
1602   tree stmt, def, use;
1603   stmt_ann_t ann;
1604   int partition;
1605   var_map map = tab->map;
1606   value_expr_p p;
1607   ssa_op_iter iter;
1608
1609   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1610     {
1611       stmt = bsi_stmt (bsi);
1612       ann = stmt_ann (stmt);
1613
1614       /* Determine if this stmt finishes an existing expression.  */
1615       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1616         {
1617           unsigned ver = SSA_NAME_VERSION (use);
1618
1619           if (tab->version_info[ver])
1620             {
1621               bool same_root_var = false;
1622               ssa_op_iter iter2;
1623               bitmap vars = tab->expr_vars[ver];
1624
1625               /* See if the root variables are the same.  If they are, we
1626                  do not want to do the replacement to avoid problems with
1627                  code size, see PR tree-optimization/17549.  */
1628               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
1629                 {
1630                   if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
1631                     {
1632                       same_root_var = true;
1633                       break;
1634                     }
1635                 }
1636
1637               /* Mark expression as replaceable unless stmt is volatile
1638                  or DEF sets the same root variable as STMT.  */
1639               if (!ann->has_volatile_ops && !same_root_var)
1640                 mark_replaceable (tab, use);
1641               else
1642                 finish_expr (tab, ver, false);
1643             }
1644         }
1645
1646       /* Next, see if this stmt kills off an active expression.  */
1647       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1648         {
1649           partition = var_to_partition (map, def);
1650           if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1651             kill_expr (tab, partition, true);
1652         }
1653
1654       /* Now see if we are creating a new expression or not.  */
1655       if (!ann->has_volatile_ops)
1656         check_replaceable (tab, stmt);
1657
1658       /* Free any unused dependency lists.  */
1659       while ((p = tab->pending_dependence))
1660         {
1661           tab->pending_dependence = p->next;
1662           free_value_expr (tab, p);
1663         }
1664
1665       /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand.  */
1666       if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
1667         kill_virtual_exprs (tab, true);
1668     }
1669 }
1670
1671
1672 /* This function is the driver routine for replacement of temporary expressions
1673    in the SSA->normal phase, operating on MAP.  If there are replaceable
1674    expressions, a table is returned which maps SSA versions to the
1675    expressions they should be replaced with.  A NULL_TREE indicates no
1676    replacement should take place.  If there are no replacements at all,
1677    NULL is returned by the function, otherwise an expression vector indexed
1678    by SSA_NAME version numbers.  */
1679
1680 static tree *
1681 find_replaceable_exprs (var_map map)
1682 {
1683   basic_block bb;
1684   unsigned i;
1685   temp_expr_table_p table;
1686   tree *ret;
1687
1688   table = new_temp_expr_table (map);
1689   FOR_EACH_BB (bb)
1690     {
1691       bitmap_iterator bi;
1692
1693       find_replaceable_in_bb (table, bb);
1694       EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
1695         {
1696           kill_expr (table, i, false);
1697         }
1698     }
1699
1700   ret = free_temp_expr_table (table);
1701   return ret;
1702 }
1703
1704
1705 /* Dump TER expression table EXPR to file F.  */
1706
1707 static void
1708 dump_replaceable_exprs (FILE *f, tree *expr)
1709 {
1710   tree stmt, var;
1711   int x;
1712   fprintf (f, "\nReplacing Expressions\n");
1713   for (x = 0; x < (int)num_ssa_names + 1; x++)
1714     if (expr[x])
1715       {
1716         stmt = expr[x];
1717         var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
1718         gcc_assert (var != NULL_TREE);
1719         print_generic_expr (f, var, TDF_SLIM);
1720         fprintf (f, " replace with --> ");
1721         print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1722         fprintf (f, "\n");
1723       }
1724   fprintf (f, "\n");
1725 }
1726
1727
1728 /* This function will rewrite the current program using the variable mapping
1729    found in MAP.  If the replacement vector VALUES is provided, any
1730    occurrences of partitions with non-null entries in the vector will be
1731    replaced with the expression in the vector instead of its mapped
1732    variable.  */
1733
1734 static void
1735 rewrite_trees (var_map map, tree *values)
1736 {
1737   elim_graph g;
1738   basic_block bb;
1739   block_stmt_iterator si;
1740   edge e;
1741   tree phi;
1742   bool changed;
1743
1744 #ifdef ENABLE_CHECKING
1745   /* Search for PHIs where the destination has no partition, but one
1746      or more arguments has a partition.  This should not happen and can
1747      create incorrect code.  */
1748   FOR_EACH_BB (bb)
1749     {
1750       tree phi;
1751
1752       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1753         {
1754           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1755
1756           if (T0 == NULL_TREE)
1757             {
1758               int i;
1759
1760               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1761                 {
1762                   tree arg = PHI_ARG_DEF (phi, i);
1763
1764                   if (TREE_CODE (arg) == SSA_NAME
1765                       && var_to_partition (map, arg) != NO_PARTITION)
1766                     {
1767                       fprintf (stderr, "Argument of PHI is in a partition :(");
1768                       print_generic_expr (stderr, arg, TDF_SLIM);
1769                       fprintf (stderr, "), but the result is not :");
1770                       print_generic_stmt (stderr, phi, TDF_SLIM);
1771                       internal_error ("SSA corruption");
1772                     }
1773                 }
1774             }
1775         }
1776     }
1777 #endif
1778
1779   /* Replace PHI nodes with any required copies.  */
1780   g = new_elim_graph (map->num_partitions);
1781   g->map = map;
1782   FOR_EACH_BB (bb)
1783     {
1784       for (si = bsi_start (bb); !bsi_end_p (si); )
1785         {
1786           tree stmt = bsi_stmt (si);
1787           use_operand_p use_p, copy_use_p;
1788           def_operand_p def_p;
1789           bool remove = false, is_copy = false;
1790           int num_uses = 0;
1791           stmt_ann_t ann;
1792           ssa_op_iter iter;
1793
1794           ann = stmt_ann (stmt);
1795           changed = false;
1796
1797           if (TREE_CODE (stmt) == MODIFY_EXPR
1798               && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1799             is_copy = true;
1800
1801           copy_use_p = NULL_USE_OPERAND_P;
1802           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1803             {
1804               if (replace_use_variable (map, use_p, values))
1805                 changed = true;
1806               copy_use_p = use_p;
1807               num_uses++;
1808             }
1809
1810           if (num_uses != 1)
1811             is_copy = false;
1812
1813           def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
1814
1815           if (def_p != NULL)
1816             {
1817               /* Mark this stmt for removal if it is the list of replaceable
1818                  expressions.  */
1819               if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
1820                 remove = true;
1821               else
1822                 {
1823                   if (replace_def_variable (map, def_p, NULL))
1824                     changed = true;
1825                   /* If both SSA_NAMEs coalesce to the same variable,
1826                      mark the now redundant copy for removal.  */
1827                   if (is_copy)
1828                     {
1829                       gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
1830                       if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
1831                         remove = true;
1832                     }
1833                 }
1834             }
1835           else
1836             FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1837               if (replace_def_variable (map, def_p, NULL))
1838                 changed = true;
1839
1840           /* Remove any stmts marked for removal.  */
1841           if (remove)
1842             bsi_remove (&si, true);
1843           else
1844             bsi_next (&si);
1845         }
1846
1847       phi = phi_nodes (bb);
1848       if (phi)
1849         {
1850           edge_iterator ei;
1851           FOR_EACH_EDGE (e, ei, bb->preds)
1852             eliminate_phi (e, g);
1853         }
1854     }
1855
1856   delete_elim_graph (g);
1857 }
1858
1859 /* These are the local work structures used to determine the best place to
1860    insert the copies that were placed on edges by the SSA->normal pass..  */
1861 static VEC(edge,heap) *edge_leader;
1862 static VEC(tree,heap) *stmt_list;
1863 static bitmap leader_has_match = NULL;
1864 static edge leader_match = NULL;
1865
1866
1867 /* Pass this function to make_forwarder_block so that all the edges with
1868    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
1869 static bool
1870 same_stmt_list_p (edge e)
1871 {
1872   return (e->aux == (PTR) leader_match) ? true : false;
1873 }
1874
1875
1876 /* Return TRUE if S1 and S2 are equivalent copies.  */
1877 static inline bool
1878 identical_copies_p (tree s1, tree s2)
1879 {
1880 #ifdef ENABLE_CHECKING
1881   gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
1882   gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
1883   gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
1884   gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
1885 #endif
1886
1887   if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
1888     return false;
1889
1890   s1 = TREE_OPERAND (s1, 1);
1891   s2 = TREE_OPERAND (s2, 1);
1892
1893   if (s1 != s2)
1894     return false;
1895
1896   return true;
1897 }
1898
1899
1900 /* Compare the PENDING_STMT list for two edges, and return true if the lists
1901    contain the same sequence of copies.  */
1902
1903 static inline bool
1904 identical_stmt_lists_p (edge e1, edge e2)
1905 {
1906   tree t1 = PENDING_STMT (e1);
1907   tree t2 = PENDING_STMT (e2);
1908   tree_stmt_iterator tsi1, tsi2;
1909
1910   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
1911   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
1912
1913   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
1914        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
1915        tsi_next (&tsi1), tsi_next (&tsi2))
1916     {
1917       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
1918         break;
1919     }
1920
1921   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
1922     return false;
1923
1924   return true;
1925 }
1926
1927
1928 /* Allocate data structures used in analyze_edges_for_bb.   */
1929
1930 static void
1931 init_analyze_edges_for_bb (void)
1932 {
1933   edge_leader = VEC_alloc (edge, heap, 25);
1934   stmt_list = VEC_alloc (tree, heap, 25);
1935   leader_has_match = BITMAP_ALLOC (NULL);
1936 }
1937
1938
1939 /* Free data structures used in analyze_edges_for_bb.   */
1940
1941 static void
1942 fini_analyze_edges_for_bb (void)
1943 {
1944   VEC_free (edge, heap, edge_leader);
1945   VEC_free (tree, heap, stmt_list);
1946   BITMAP_FREE (leader_has_match);
1947 }
1948
1949
1950 /* Look at all the incoming edges to block BB, and decide where the best place
1951    to insert the stmts on each edge are, and perform those insertions.  */
1952
1953 static void
1954 analyze_edges_for_bb (basic_block bb)
1955 {
1956   edge e;
1957   edge_iterator ei;
1958   int count;
1959   unsigned int x;
1960   bool have_opportunity;
1961   block_stmt_iterator bsi;
1962   tree stmt;
1963   edge single_edge = NULL;
1964   bool is_label;
1965   edge leader;
1966
1967   count = 0;
1968
1969   /* Blocks which contain at least one abnormal edge cannot use
1970      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
1971      found on edges in these block.  */
1972   have_opportunity = true;
1973   FOR_EACH_EDGE (e, ei, bb->preds)
1974     if (e->flags & EDGE_ABNORMAL)
1975       {
1976         have_opportunity = false;
1977         break;
1978       }
1979
1980   if (!have_opportunity)
1981     {
1982       FOR_EACH_EDGE (e, ei, bb->preds)
1983         if (PENDING_STMT (e))
1984           bsi_commit_one_edge_insert (e, NULL);
1985       return;
1986     }
1987   /* Find out how many edges there are with interesting pending stmts on them.
1988      Commit the stmts on edges we are not interested in.  */
1989   FOR_EACH_EDGE (e, ei, bb->preds)
1990     {
1991       if (PENDING_STMT (e))
1992         {
1993           gcc_assert (!(e->flags & EDGE_ABNORMAL));
1994           if (e->flags & EDGE_FALLTHRU)
1995             {
1996               bsi = bsi_start (e->src);
1997               if (!bsi_end_p (bsi))
1998                 {
1999                   stmt = bsi_stmt (bsi);
2000                   bsi_next (&bsi);
2001                   gcc_assert (stmt != NULL_TREE);
2002                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
2003                   /* Punt if it has non-label stmts, or isn't local.  */
2004                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
2005                       || !bsi_end_p (bsi))
2006                     {
2007                       bsi_commit_one_edge_insert (e, NULL);
2008                       continue;
2009                     }
2010                 }
2011             }
2012           single_edge = e;
2013           count++;
2014         }
2015     }
2016
2017   /* If there aren't at least 2 edges, no sharing will happen.  */
2018   if (count < 2)
2019     {
2020       if (single_edge)
2021         bsi_commit_one_edge_insert (single_edge, NULL);
2022       return;
2023     }
2024
2025   /* Ensure that we have empty worklists.  */
2026 #ifdef ENABLE_CHECKING
2027   gcc_assert (VEC_length (edge, edge_leader) == 0);
2028   gcc_assert (VEC_length (tree, stmt_list) == 0);
2029   gcc_assert (bitmap_empty_p (leader_has_match));
2030 #endif
2031
2032   /* Find the "leader" block for each set of unique stmt lists.  Preference is
2033      given to FALLTHRU blocks since they would need a GOTO to arrive at another
2034      block.  The leader edge destination is the block which all the other edges
2035      with the same stmt list will be redirected to.  */
2036   have_opportunity = false;
2037   FOR_EACH_EDGE (e, ei, bb->preds)
2038     {
2039       if (PENDING_STMT (e))
2040         {
2041           bool found = false;
2042
2043           /* Look for the same stmt list in edge leaders list.  */
2044           for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2045             {
2046               if (identical_stmt_lists_p (leader, e))
2047                 {
2048                   /* Give this edge the same stmt list pointer.  */
2049                   PENDING_STMT (e) = NULL;
2050                   e->aux = leader;
2051                   bitmap_set_bit (leader_has_match, x);
2052                   have_opportunity = found = true;
2053                   break;
2054                 }
2055             }
2056
2057           /* If no similar stmt list, add this edge to the leader list.  */
2058           if (!found)
2059             {
2060               VEC_safe_push (edge, heap, edge_leader, e);
2061               VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
2062             }
2063         }
2064      }
2065
2066   /* If there are no similar lists, just issue the stmts.  */
2067   if (!have_opportunity)
2068     {
2069       for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2070         bsi_commit_one_edge_insert (leader, NULL);
2071       VEC_truncate (edge, edge_leader, 0);
2072       VEC_truncate (tree, stmt_list, 0);
2073       bitmap_clear (leader_has_match);
2074       return;
2075     }
2076
2077
2078   if (dump_file)
2079     fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
2080              bb->index);
2081
2082
2083   /* For each common list, create a forwarding block and issue the stmt's
2084      in that block.  */
2085   for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2086     if (bitmap_bit_p (leader_has_match, x))
2087       {
2088         edge new_edge;
2089         block_stmt_iterator bsi;
2090         tree curr_stmt_list;
2091
2092         leader_match = leader;
2093
2094         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
2095            for various PHI manipulations, so it gets cleared when calls are
2096            made to make_forwarder_block(). So make sure the edge is clear,
2097            and use the saved stmt list.  */
2098         PENDING_STMT (leader) = NULL;
2099         leader->aux = leader;
2100         curr_stmt_list = VEC_index (tree, stmt_list, x);
2101
2102         new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
2103                                          NULL);
2104         bb = new_edge->dest;
2105         if (dump_file)
2106           {
2107             fprintf (dump_file, "Splitting BB %d for Common stmt list.  ",
2108                      leader->dest->index);
2109             fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
2110             print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS);
2111           }
2112
2113         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
2114           {
2115             e->aux = NULL;
2116             if (dump_file)
2117               fprintf (dump_file, "  Edge (%d->%d) lands here.\n",
2118                        e->src->index, e->dest->index);
2119           }
2120
2121         bsi = bsi_last (leader->dest);
2122         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
2123
2124         leader_match = NULL;
2125         /* We should never get a new block now.  */
2126       }
2127     else
2128       {
2129         PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
2130         bsi_commit_one_edge_insert (leader, NULL);
2131       }
2132
2133
2134   /* Clear the working data structures.  */
2135   VEC_truncate (edge, edge_leader, 0);
2136   VEC_truncate (tree, stmt_list, 0);
2137   bitmap_clear (leader_has_match);
2138 }
2139
2140
2141 /* This function will analyze the insertions which were performed on edges,
2142    and decide whether they should be left on that edge, or whether it is more
2143    efficient to emit some subset of them in a single block.  All stmts are
2144    inserted somewhere.  */
2145
2146 static void
2147 perform_edge_inserts (void)
2148 {
2149   basic_block bb;
2150
2151   if (dump_file)
2152     fprintf(dump_file, "Analyzing Edge Insertions.\n");
2153
2154   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
2155      incrementally update the dominator information.  Since we don't
2156      need dominator information after this pass, go ahead and free the
2157      dominator information.  */
2158   free_dominance_info (CDI_DOMINATORS);
2159   free_dominance_info (CDI_POST_DOMINATORS);
2160
2161   /* Allocate data structures used in analyze_edges_for_bb.   */
2162   init_analyze_edges_for_bb ();
2163
2164   FOR_EACH_BB (bb)
2165     analyze_edges_for_bb (bb);
2166
2167   analyze_edges_for_bb (EXIT_BLOCK_PTR);
2168
2169   /* Free data structures used in analyze_edges_for_bb.   */
2170   fini_analyze_edges_for_bb ();
2171
2172 #ifdef ENABLE_CHECKING
2173   {
2174     edge_iterator ei;
2175     edge e;
2176     FOR_EACH_BB (bb)
2177       {
2178         FOR_EACH_EDGE (e, ei, bb->preds)
2179           {
2180             if (PENDING_STMT (e))
2181               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
2182                      e->src->index, e->dest->index);
2183           }
2184         FOR_EACH_EDGE (e, ei, bb->succs)
2185           {
2186             if (PENDING_STMT (e))
2187               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
2188                      e->src->index, e->dest->index);
2189           }
2190       }
2191     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2192       {
2193         if (PENDING_STMT (e))
2194           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
2195                  e->src->index, e->dest->index);
2196       }
2197     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
2198       {
2199         if (PENDING_STMT (e))
2200           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
2201                  e->src->index, e->dest->index);
2202       }
2203   }
2204 #endif
2205 }
2206
2207
2208 /* Remove the variables specified in MAP from SSA form.  FLAGS indicate what
2209    options should be used.  */
2210
2211 static void
2212 remove_ssa_form (var_map map, int flags)
2213 {
2214   tree_live_info_p liveinfo;
2215   basic_block bb;
2216   tree phi, next;
2217   tree *values = NULL;
2218
2219   /* If we are not combining temps, don't calculate live ranges for variables
2220      with only one SSA version.  */
2221   compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
2222
2223   if (dump_file && (dump_flags & TDF_DETAILS))
2224     dump_var_map (dump_file, map);
2225
2226   liveinfo = coalesce_ssa_name (map, flags);
2227
2228   /* Make sure even single occurrence variables are in the list now.  */
2229   compact_var_map (map, VARMAP_NORMAL);
2230
2231   if (dump_file && (dump_flags & TDF_DETAILS))
2232     {
2233       fprintf (dump_file, "After Coalescing:\n");
2234       dump_var_map (dump_file, map);
2235     }
2236
2237   if (flags & SSANORM_PERFORM_TER)
2238     {
2239       values = find_replaceable_exprs (map);
2240       if (values && dump_file && (dump_flags & TDF_DETAILS))
2241         dump_replaceable_exprs (dump_file, values);
2242     }
2243
2244   /* Assign real variables to the partitions now.  */
2245   assign_vars (map);
2246
2247   if (dump_file && (dump_flags & TDF_DETAILS))
2248     {
2249       fprintf (dump_file, "After Root variable replacement:\n");
2250       dump_var_map (dump_file, map);
2251     }
2252
2253   if (liveinfo)
2254     delete_tree_live_info (liveinfo);
2255
2256   rewrite_trees (map, values);
2257
2258   if (values)
2259     free (values);
2260
2261   /* Remove phi nodes which have been translated back to real variables.  */
2262   FOR_EACH_BB (bb)
2263     {
2264       for (phi = phi_nodes (bb); phi; phi = next)
2265         {
2266           next = PHI_CHAIN (phi);
2267           remove_phi_node (phi, NULL_TREE);
2268         }
2269     }
2270
2271   /* we no longer maintain the SSA operand cache at this point.  */
2272   fini_ssa_operands ();
2273
2274   /* If any copies were inserted on edges, analyze and insert them now.  */
2275   perform_edge_inserts ();
2276 }
2277
2278 /* Search every PHI node for arguments associated with backedges which
2279    we can trivially determine will need a copy (the argument is either
2280    not an SSA_NAME or the argument has a different underlying variable
2281    than the PHI result).
2282
2283    Insert a copy from the PHI argument to a new destination at the
2284    end of the block with the backedge to the top of the loop.  Update
2285    the PHI argument to reference this new destination.  */
2286
2287 static void
2288 insert_backedge_copies (void)
2289 {
2290   basic_block bb;
2291
2292   FOR_EACH_BB (bb)
2293     {
2294       tree phi;
2295
2296       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2297         {
2298           tree result = PHI_RESULT (phi);
2299           tree result_var;
2300           int i;
2301
2302           if (!is_gimple_reg (result))
2303             continue;
2304
2305           result_var = SSA_NAME_VAR (result);
2306           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2307             {
2308               tree arg = PHI_ARG_DEF (phi, i);
2309               edge e = PHI_ARG_EDGE (phi, i);
2310
2311               /* If the argument is not an SSA_NAME, then we will
2312                  need a constant initialization.  If the argument is
2313                  an SSA_NAME with a different underlying variable and
2314                  we are not combining temporaries, then we will
2315                  need a copy statement.  */
2316               if ((e->flags & EDGE_DFS_BACK)
2317                   && (TREE_CODE (arg) != SSA_NAME
2318                       || SSA_NAME_VAR (arg) != result_var))
2319                 {
2320                   tree stmt, name, last = NULL;
2321                   block_stmt_iterator bsi;
2322
2323                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
2324                   if (!bsi_end_p (bsi))
2325                     last = bsi_stmt (bsi);
2326
2327                   /* In theory the only way we ought to get back to the
2328                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
2329                      However, better safe than sorry.
2330
2331                      If the block ends with a control statement or
2332                      something that might throw, then we have to
2333                      insert this assignment before the last
2334                      statement.  Else insert it after the last statement.  */
2335                   if (last && stmt_ends_bb_p (last))
2336                     {
2337                       /* If the last statement in the block is the definition
2338                          site of the PHI argument, then we can't insert
2339                          anything after it.  */
2340                       if (TREE_CODE (arg) == SSA_NAME
2341                           && SSA_NAME_DEF_STMT (arg) == last)
2342                         continue;
2343                     }
2344
2345                   /* Create a new instance of the underlying
2346                      variable of the PHI result.  */
2347                   stmt = build2 (MODIFY_EXPR, TREE_TYPE (result_var),
2348                                  NULL_TREE, PHI_ARG_DEF (phi, i));
2349                   name = make_ssa_name (result_var, stmt);
2350                   TREE_OPERAND (stmt, 0) = name;
2351
2352                   /* Insert the new statement into the block and update
2353                      the PHI node.  */
2354                   if (last && stmt_ends_bb_p (last))
2355                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2356                   else
2357                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2358                   SET_PHI_ARG_DEF (phi, i, name);
2359                 }
2360             }
2361         }
2362     }
2363 }
2364
2365 /* Take the current function out of SSA form, as described in
2366    R. Morgan, ``Building an Optimizing Compiler'',
2367    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
2368
2369 static unsigned int
2370 rewrite_out_of_ssa (void)
2371 {
2372   var_map map;
2373   int ssa_flags = 0;
2374
2375   /* If elimination of a PHI requires inserting a copy on a backedge,
2376      then we will have to split the backedge which has numerous
2377      undesirable performance effects.
2378
2379      A significant number of such cases can be handled here by inserting
2380      copies into the loop itself.  */
2381   insert_backedge_copies ();
2382
2383   if (!flag_tree_live_range_split)
2384     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2385
2386   eliminate_virtual_phis ();
2387
2388   if (dump_file && (dump_flags & TDF_DETAILS))
2389     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2390
2391   map = create_ssa_var_map ();
2392
2393   if (flag_tree_ter && !flag_mudflap)
2394     ssa_flags |= SSANORM_PERFORM_TER;
2395
2396   remove_ssa_form (map, ssa_flags);
2397
2398   if (dump_file && (dump_flags & TDF_DETAILS))
2399     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2400
2401   /* Flush out flow graph and SSA data.  */
2402   delete_var_map (map);
2403
2404   cfun->gimple_df->in_ssa_p = false;
2405   return 0;
2406 }
2407
2408
2409 /* Define the parameters of the out of SSA pass.  */
2410
2411 struct tree_opt_pass pass_del_ssa =
2412 {
2413   "optimized",                          /* name */
2414   NULL,                                 /* gate */
2415   rewrite_out_of_ssa,                   /* execute */
2416   NULL,                                 /* sub */
2417   NULL,                                 /* next */
2418   0,                                    /* static_pass_number */
2419   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
2420   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2421   0,                                    /* properties_provided */
2422   /* ??? If TER is enabled, we also kill gimple.  */
2423   PROP_ssa,                             /* properties_destroyed */
2424   TODO_verify_ssa | TODO_verify_flow
2425     | TODO_verify_stmts,                /* todo_flags_start */
2426   TODO_dump_func
2427   | TODO_ggc_collect
2428   | TODO_remove_unused_locals,          /* todo_flags_finish */
2429   0                                     /* letter */
2430 };