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, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, 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 "errors.h"
  36 #include "expr.h"
  37 #include "function.h"
  38 #include "diagnostic.h"
  39 #include "bitmap.h"
  40 #include "tree-flow.h"
  41 #include "tree-gimple.h"
  42 #include "tree-inline.h"
  43 #include "varray.h"
  44 #include "timevar.h"
  45 #include "hashtab.h"
  46 #include "tree-dump.h"
  47 #include "tree-ssa-live.h"
  48 #include "tree-pass.h"
  49
  50 /* Flags to pass to remove_ssa_form.  */
  51
  52 #define SSANORM_PERFORM_TER             0x1
  53 #define SSANORM_COMBINE_TEMPS           0x2
  54 #define SSANORM_REMOVE_ALL_PHIS         0x4
  55 #define SSANORM_COALESCE_PARTITIONS     0x8
  56 #define SSANORM_USE_COALESCE_LIST       0x10
  57
  58 /* Used to hold all the components required to do SSA PHI elimination.
  59    The node and pred/succ list is a simple linear list of nodes and
  60    edges represented as pairs of nodes.
  61
  62    The predecessor and successor list:  Nodes are entered in pairs, where
  63    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
  64    predecessors, all the odd elements are successors.
  65
  66    Rationale:
  67    When implemented as bitmaps, very large programs SSA->Normal times were
  68    being dominated by clearing the interference graph.
  69
  70    Typically this list of edges is extremely small since it only includes
  71    PHI results and uses from a single edge which have not coalesced with
  72    each other.  This means that no virtual PHI nodes are included, and
  73    empirical evidence suggests that the number of edges rarely exceed
  74    3, and in a bootstrap of GCC, the maximum size encountered was 7.
  75    This also limits the number of possible nodes that are involved to
  76    rarely more than 6, and in the bootstrap of gcc, the maximum number
  77    of nodes encountered was 12.  */
  78
  79 typedef struct _elim_graph {
  80   /* Size of the elimination vectors.  */
  81   int size;
  82
  83   /* List of nodes in the elimination graph.  */
  84   varray_type nodes;
  85
  86   /*  The predecessor and successor edge list.  */
  87   varray_type edge_list;
  88
  89   /* Visited vector.  */
  90   sbitmap visited;
  91
  92   /* Stack for visited nodes.  */
  93   varray_type stack;
  94
  95   /* The variable partition map.  */
  96   var_map map;
  97
  98   /* Edge being eliminated by this graph.  */
  99   edge e;
 100
 101   /* List of constant copies to emit.  These are pushed on in pairs.  */
 102   varray_type  const_copies;
 103 } *elim_graph;
 104
 105
 106 /* Local functions.  */
 107 static tree create_temp (tree);
 108 static void insert_copy_on_edge (edge, tree, tree);
 109 static elim_graph new_elim_graph (int);
 110 static inline void delete_elim_graph (elim_graph);
 111 static inline void clear_elim_graph (elim_graph);
 112 static inline int elim_graph_size (elim_graph);
 113 static inline void elim_graph_add_node (elim_graph, tree);
 114 static inline void elim_graph_add_edge (elim_graph, int, int);
 115 static inline int elim_graph_remove_succ_edge (elim_graph, int);
 116
 117 static inline void eliminate_name (elim_graph, tree);
 118 static void eliminate_build (elim_graph, basic_block);
 119 static void elim_forward (elim_graph, int);
 120 static int elim_unvisited_predecessor (elim_graph, int);
 121 static void elim_backward (elim_graph, int);
 122 static void elim_create (elim_graph, int);
 123 static void eliminate_phi (edge, elim_graph);
 124 static tree_live_info_p coalesce_ssa_name (var_map, int);
 125 static void assign_vars (var_map);
 126 static bool replace_use_variable (var_map, use_operand_p, tree *);
 127 static bool replace_def_variable (var_map, def_operand_p, tree *);
 128 static void eliminate_virtual_phis (void);
 129 static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
 130 static void print_exprs (FILE *, const char *, tree, const char *, tree,
 131                          const char *);
 132 static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
 133                               tree);
 134
 135
 136 /* Create a temporary variable based on the type of variable T.  Use T's name
 137    as the prefix.  */
 138
 139 static tree
 140 create_temp (tree t)
 141 {
 142   tree tmp;
 143   const char *name = NULL;
 144   tree type;
 145
 146   if (TREE_CODE (t) == SSA_NAME)
 147     t = SSA_NAME_VAR (t);
 148
 149   gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
 150
 151   type = TREE_TYPE (t);
 152   tmp = DECL_NAME (t);
 153   if (tmp)
 154     name = IDENTIFIER_POINTER (tmp);
 155
 156   if (name == NULL)
 157     name = "temp";
 158   tmp = create_tmp_var (type, name);
 159
 160   if (DECL_DEBUG_ALIAS_OF (t))
 161     DECL_DEBUG_ALIAS_OF (tmp) = DECL_DEBUG_ALIAS_OF (t);
 162   else if (!DECL_IGNORED_P (t))
 163     DECL_DEBUG_ALIAS_OF (tmp) = t;
 164   DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
 165   DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
 166   add_referenced_tmp_var (tmp);
 167
 168   /* add_referenced_tmp_var will create the annotation and set up some
 169      of the flags in the annotation.  However, some flags we need to
 170      inherit from our original variable.  */
 171   var_ann (tmp)->type_mem_tag = var_ann (t)->type_mem_tag;
 172   if (is_call_clobbered (t))
 173     mark_call_clobbered (tmp);
 174
 175   return tmp;
 176 }
 177
 178
 179 /* This helper function fill insert a copy from a constant or variable SRC to
 180    variable DEST on edge E.  */
 181
 182 static void
 183 insert_copy_on_edge (edge e, tree dest, tree src)
 184 {
 185   tree copy;
 186
 187   copy = build (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
 188   set_is_used (dest);
 189
 190   if (TREE_CODE (src) == ADDR_EXPR)
 191     src = TREE_OPERAND (src, 0);
 192   if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
 193     set_is_used (src);
 194
 195   if (dump_file && (dump_flags & TDF_DETAILS))
 196     {
 197       fprintf (dump_file,
 198                "Inserting a copy on edge BB%d->BB%d :",
 199                e->src->index,
 200                e->dest->index);
 201       print_generic_expr (dump_file, copy, dump_flags);
 202       fprintf (dump_file, "\n");
 203     }
 204
 205   bsi_insert_on_edge (e, copy);
 206 }
 207
 208
 209 /* Create an elimination graph with SIZE nodes and associated data
 210    structures.  */
 211
 212 static elim_graph
 213 new_elim_graph (int size)
 214 {
 215   elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
 216
 217   VARRAY_TREE_INIT (g->nodes, 30, "Elimination Node List");
 218   VARRAY_TREE_INIT (g->const_copies, 20, "Elimination Constant Copies");
 219   VARRAY_INT_INIT (g->edge_list, 20, "Elimination Edge List");
 220   VARRAY_INT_INIT (g->stack, 30, " Elimination Stack");
 221
 222   g->visited = sbitmap_alloc (size);
 223
 224   return g;
 225 }
 226
 227
 228 /* Empty elimination graph G.  */
 229
 230 static inline void
 231 clear_elim_graph (elim_graph g)
 232 {
 233   VARRAY_POP_ALL (g->nodes);
 234   VARRAY_POP_ALL (g->edge_list);
 235 }
 236
 237
 238 /* Delete elimination graph G.  */
 239
 240 static inline void
 241 delete_elim_graph (elim_graph g)
 242 {
 243   sbitmap_free (g->visited);
 244   free (g);
 245 }
 246
 247
 248 /* Return the number of nodes in graph G.  */
 249
 250 static inline int
 251 elim_graph_size (elim_graph g)
 252 {
 253   return VARRAY_ACTIVE_SIZE (g->nodes);
 254 }
 255
 256
 257 /* Add NODE to graph G, if it doesn't exist already.  */
 258
 259 static inline void
 260 elim_graph_add_node (elim_graph g, tree node)
 261 {
 262   int x;
 263   for (x = 0; x < elim_graph_size (g); x++)
 264     if (VARRAY_TREE (g->nodes, x) == node)
 265       return;
 266   VARRAY_PUSH_TREE (g->nodes, node);
 267 }
 268
 269
 270 /* Add the edge PRED->SUCC to graph G.  */
 271
 272 static inline void
 273 elim_graph_add_edge (elim_graph g, int pred, int succ)
 274 {
 275   VARRAY_PUSH_INT (g->edge_list, pred);
 276   VARRAY_PUSH_INT (g->edge_list, succ);
 277 }
 278
 279
 280 /* Remove an edge from graph G for which NODE is the predecessor, and
 281    return the successor node.  -1 is returned if there is no such edge.  */
 282
 283 static inline int
 284 elim_graph_remove_succ_edge (elim_graph g, int node)
 285 {
 286   int y;
 287   unsigned x;
 288   for (x = 0; x < VARRAY_ACTIVE_SIZE (g->edge_list); x += 2)
 289     if (VARRAY_INT (g->edge_list, x) == node)
 290       {
 291         VARRAY_INT (g->edge_list, x) = -1;
 292         y = VARRAY_INT (g->edge_list, x + 1);
 293         VARRAY_INT (g->edge_list, x + 1) = -1;
 294         return y;
 295       }
 296   return -1;
 297 }
 298
 299
 300 /* Find all the nodes in GRAPH which are successors to NODE in the
 301    edge list.  VAR will hold the partition number found.  CODE is the
 302    code fragment executed for every node found.  */
 303
 304 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE)                \
 305 do {                                                                    \
 306   unsigned x_;                                                          \
 307   int y_;                                                               \
 308   for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2)   \
 309     {                                                                   \
 310       y_ = VARRAY_INT ((GRAPH)->edge_list, x_);                         \
 311       if (y_ != (NODE))                                                 \
 312         continue;                                                       \
 313       (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_ + 1);                  \
 314       CODE;                                                             \
 315     }                                                                   \
 316 } while (0)
 317
 318
 319 /* Find all the nodes which are predecessors of NODE in the edge list for
 320    GRAPH.  VAR will hold the partition number found.  CODE is the
 321    code fragment executed for every node found.  */
 322
 323 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE)                \
 324 do {                                                                    \
 325   unsigned x_;                                                          \
 326   int y_;                                                               \
 327   for (x_ = 0; x_ < VARRAY_ACTIVE_SIZE ((GRAPH)->edge_list); x_ += 2)   \
 328     {                                                                   \
 329       y_ = VARRAY_INT ((GRAPH)->edge_list, x_ + 1);                     \
 330       if (y_ != (NODE))                                                 \
 331         continue;                                                       \
 332       (VAR) = VARRAY_INT ((GRAPH)->edge_list, x_);                      \
 333       CODE;                                                             \
 334     }                                                                   \
 335 } while (0)
 336
 337
 338 /* Add T to elimination graph G.  */
 339
 340 static inline void
 341 eliminate_name (elim_graph g, tree T)
 342 {
 343   elim_graph_add_node (g, T);
 344 }
 345
 346
 347 /* Build elimination graph G for basic block BB on incoming PHI edge
 348    G->e.  */
 349
 350 static void
 351 eliminate_build (elim_graph g, basic_block B)
 352 {
 353   tree phi;
 354   tree T0, Ti;
 355   int p0, pi;
 356
 357   clear_elim_graph (g);
 358
 359   for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
 360     {
 361       T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
 362
 363       /* Ignore results which are not in partitions.  */
 364       if (T0 == NULL_TREE)
 365         continue;
 366
 367       Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
 368
 369       /* If this argument is a constant, or a SSA_NAME which is being
 370          left in SSA form, just queue a copy to be emitted on this
 371          edge.  */
 372       if (!phi_ssa_name_p (Ti)
 373           || (TREE_CODE (Ti) == SSA_NAME
 374               && var_to_partition (g->map, Ti) == NO_PARTITION))
 375         {
 376           /* Save constant copies until all other copies have been emitted
 377              on this edge.  */
 378           VARRAY_PUSH_TREE (g->const_copies, T0);
 379           VARRAY_PUSH_TREE (g->const_copies, Ti);
 380         }
 381       else
 382         {
 383           Ti = var_to_partition_to_var (g->map, Ti);
 384           if (T0 != Ti)
 385             {
 386               eliminate_name (g, T0);
 387               eliminate_name (g, Ti);
 388               p0 = var_to_partition (g->map, T0);
 389               pi = var_to_partition (g->map, Ti);
 390               elim_graph_add_edge (g, p0, pi);
 391             }
 392         }
 393     }
 394 }
 395
 396
 397 /* Push successors of T onto the elimination stack for G.  */
 398
 399 static void
 400 elim_forward (elim_graph g, int T)
 401 {
 402   int S;
 403   SET_BIT (g->visited, T);
 404   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
 405     {
 406       if (!TEST_BIT (g->visited, S))
 407         elim_forward (g, S);
 408     });
 409   VARRAY_PUSH_INT (g->stack, T);
 410 }
 411
 412
 413 /* Return 1 if there unvisited predecessors of T in graph G.  */
 414
 415 static int
 416 elim_unvisited_predecessor (elim_graph g, int T)
 417 {
 418   int P;
 419   FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 420     {
 421       if (!TEST_BIT (g->visited, P))
 422         return 1;
 423     });
 424   return 0;
 425 }
 426
 427 /* Process predecessors first, and insert a copy.  */
 428
 429 static void
 430 elim_backward (elim_graph g, int T)
 431 {
 432   int P;
 433   SET_BIT (g->visited, T);
 434   FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 435     {
 436       if (!TEST_BIT (g->visited, P))
 437         {
 438           elim_backward (g, P);
 439           insert_copy_on_edge (g->e,
 440                                partition_to_var (g->map, P),
 441                                partition_to_var (g->map, T));
 442         }
 443     });
 444 }
 445
 446 /* Insert required copies for T in graph G.  Check for a strongly connected
 447    region, and create a temporary to break the cycle if one is found.  */
 448
 449 static void
 450 elim_create (elim_graph g, int T)
 451 {
 452   tree U;
 453   int P, S;
 454
 455   if (elim_unvisited_predecessor (g, T))
 456     {
 457       U = create_temp (partition_to_var (g->map, T));
 458       insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
 459       FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 460         {
 461           if (!TEST_BIT (g->visited, P))
 462             {
 463               elim_backward (g, P);
 464               insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
 465             }
 466         });
 467     }
 468   else
 469     {
 470       S = elim_graph_remove_succ_edge (g, T);
 471       if (S != -1)
 472         {
 473           SET_BIT (g->visited, T);
 474           insert_copy_on_edge (g->e,
 475                                partition_to_var (g->map, T),
 476                                partition_to_var (g->map, S));
 477         }
 478     }
 479
 480 }
 481
 482 /* Eliminate all the phi nodes on edge E in graph G.  */
 483
 484 static void
 485 eliminate_phi (edge e, elim_graph g)
 486 {
 487   int num_nodes = 0;
 488   int x;
 489   basic_block B = e->dest;
 490
 491   gcc_assert (VARRAY_ACTIVE_SIZE (g->const_copies) == 0);
 492
 493   /* Abnormal edges already have everything coalesced, or the coalescer
 494      would have aborted.  */
 495   if (e->flags & EDGE_ABNORMAL)
 496     return;
 497
 498   num_nodes = num_var_partitions (g->map);
 499   g->e = e;
 500
 501   eliminate_build (g, B);
 502
 503   if (elim_graph_size (g) != 0)
 504     {
 505       sbitmap_zero (g->visited);
 506       VARRAY_POP_ALL (g->stack);
 507
 508       for (x = 0; x < elim_graph_size (g); x++)
 509         {
 510           tree var = VARRAY_TREE (g->nodes, x);
 511           int p = var_to_partition (g->map, var);
 512           if (!TEST_BIT (g->visited, p))
 513             elim_forward (g, p);
 514         }
 515
 516       sbitmap_zero (g->visited);
 517       while (VARRAY_ACTIVE_SIZE (g->stack) > 0)
 518         {
 519           x = VARRAY_TOP_INT (g->stack);
 520           VARRAY_POP (g->stack);
 521           if (!TEST_BIT (g->visited, x))
 522             elim_create (g, x);
 523         }
 524     }
 525
 526   /* If there are any pending constant copies, issue them now.  */
 527   while (VARRAY_ACTIVE_SIZE (g->const_copies) > 0)
 528     {
 529       tree src, dest;
 530       src = VARRAY_TOP_TREE (g->const_copies);
 531       VARRAY_POP (g->const_copies);
 532       dest = VARRAY_TOP_TREE (g->const_copies);
 533       VARRAY_POP (g->const_copies);
 534       insert_copy_on_edge (e, dest, src);
 535     }
 536 }
 537
 538
 539 /* Shortcut routine to print messages to file F of the form:
 540    "STR1 EXPR1 STR2 EXPR2 STR3."  */
 541
 542 static void
 543 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
 544              tree expr2, const char *str3)
 545 {
 546   fprintf (f, "%s", str1);
 547   print_generic_expr (f, expr1, TDF_SLIM);
 548   fprintf (f, "%s", str2);
 549   print_generic_expr (f, expr2, TDF_SLIM);
 550   fprintf (f, "%s", str3);
 551 }
 552
 553
 554 /* Shortcut routine to print abnormal edge messages to file F of the form:
 555    "STR1 EXPR1 STR2 EXPR2 across edge E.  */
 556
 557 static void
 558 print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1,
 559                   const char *str2, tree expr2)
 560 {
 561   print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge");
 562   fprintf (f, " from BB%d->BB%d\n", e->src->index,
 563                e->dest->index);
 564 }
 565
 566
 567 /* Coalesce partitions in MAP which are live across abnormal edges in GRAPH.
 568    RV is the root variable groupings of the partitions in MAP.  Since code
 569    cannot be inserted on these edges, failure to coalesce something across
 570    an abnormal edge is an error.  */
 571
 572 static void
 573 coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv)
 574 {
 575   basic_block bb;
 576   edge e;
 577   tree phi, var, tmp;
 578   int x, y, z;
 579   edge_iterator ei;
 580
 581   /* Code cannot be inserted on abnormal edges. Look for all abnormal
 582      edges, and coalesce any PHI results with their arguments across
 583      that edge.  */
 584
 585   FOR_EACH_BB (bb)
 586     FOR_EACH_EDGE (e, ei, bb->succs)
 587       if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
 588         for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 589           {
 590             /* Visit each PHI on the destination side of this abnormal
 591                edge, and attempt to coalesce the argument with the result.  */
 592             var = PHI_RESULT (phi);
 593             x = var_to_partition (map, var);
 594
 595             /* Ignore results which are not relevant.  */
 596             if (x == NO_PARTITION)
 597               continue;
 598
 599             tmp = PHI_ARG_DEF (phi, e->dest_idx);
 600 #ifdef ENABLE_CHECKING
 601             if (!phi_ssa_name_p (tmp))
 602               {
 603                 print_exprs_edge (stderr, e,
 604                                   "\nConstant argument in PHI. Can't insert :",
 605                                   var, " = ", tmp);
 606                 internal_error ("SSA corruption");
 607               }
 608 #else
 609             gcc_assert (phi_ssa_name_p (tmp));
 610 #endif
 611             y = var_to_partition (map, tmp);
 612             gcc_assert (x != NO_PARTITION);
 613             gcc_assert (y != NO_PARTITION);
 614 #ifdef ENABLE_CHECKING
 615             if (root_var_find (rv, x) != root_var_find (rv, y))
 616               {
 617                 print_exprs_edge (stderr, e, "\nDifferent root vars: ",
 618                                   root_var (rv, root_var_find (rv, x)),
 619                                   " and ",
 620                                   root_var (rv, root_var_find (rv, y)));
 621                 internal_error ("SSA corruption");
 622               }
 623 #else
 624             gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
 625 #endif
 626
 627             if (x != y)
 628               {
 629 #ifdef ENABLE_CHECKING
 630                 if (conflict_graph_conflict_p (graph, x, y))
 631                   {
 632                     print_exprs_edge (stderr, e, "\n Conflict ",
 633                                       partition_to_var (map, x),
 634                                       " and ", partition_to_var (map, y));
 635                     internal_error ("SSA corruption");
 636                   }
 637 #else
 638                 gcc_assert (!conflict_graph_conflict_p (graph, x, y));
 639 #endif
 640
 641                 /* Now map the partitions back to their real variables.  */
 642                 var = partition_to_var (map, x);
 643                 tmp = partition_to_var (map, y);
 644                 if (dump_file && (dump_flags & TDF_DETAILS))
 645                   {
 646                     print_exprs_edge (dump_file, e,
 647                                       "ABNORMAL: Coalescing ",
 648                                       var, " and ", tmp);
 649                   }
 650                 z = var_union (map, var, tmp);
 651 #ifdef ENABLE_CHECKING
 652                 if (z == NO_PARTITION)
 653                   {
 654                     print_exprs_edge (stderr, e, "\nUnable to coalesce",
 655                                       partition_to_var (map, x), " and ",
 656                                       partition_to_var (map, y));
 657                     internal_error ("SSA corruption");
 658                   }
 659 #else
 660                 gcc_assert (z != NO_PARTITION);
 661 #endif
 662                 gcc_assert (z == x || z == y);
 663                 if (z == x)
 664                   conflict_graph_merge_regs (graph, x, y);
 665                 else
 666                   conflict_graph_merge_regs (graph, y, x);
 667               }
 668           }
 669 }
 670
 671
 672 /* Reduce the number of live ranges in MAP.  Live range information is
 673    returned if FLAGS indicates that we are combining temporaries, otherwise
 674    NULL is returned.  The only partitions which are associated with actual
 675    variables at this point are those which are forced to be coalesced for
 676    various reason. (live on entry, live across abnormal edges, etc.).  */
 677
 678 static tree_live_info_p
 679 coalesce_ssa_name (var_map map, int flags)
 680 {
 681   unsigned num, x, i;
 682   sbitmap live;
 683   tree var, phi;
 684   root_var_p rv;
 685   tree_live_info_p liveinfo;
 686   var_ann_t ann;
 687   conflict_graph graph;
 688   basic_block bb;
 689   coalesce_list_p cl = NULL;
 690
 691   if (num_var_partitions (map) <= 1)
 692     return NULL;
 693
 694   /* If no preference given, use cheap coalescing of all partitions.  */
 695   if ((flags & (SSANORM_COALESCE_PARTITIONS | SSANORM_USE_COALESCE_LIST)) == 0)
 696     flags |= SSANORM_COALESCE_PARTITIONS;
 697
 698   liveinfo = calculate_live_on_entry (map);
 699   calculate_live_on_exit (liveinfo);
 700   rv = root_var_init (map);
 701
 702   /* Remove single element variable from the list.  */
 703   root_var_compact (rv);
 704
 705   if (flags & SSANORM_USE_COALESCE_LIST)
 706     {
 707       cl = create_coalesce_list (map);
 708
 709       /* Add all potential copies via PHI arguments to the list.  */
 710       FOR_EACH_BB (bb)
 711         {
 712           for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 713             {
 714               tree res = PHI_RESULT (phi);
 715               int p = var_to_partition (map, res);
 716               if (p == NO_PARTITION)
 717                 continue;
 718               for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
 719                 {
 720                   tree arg = PHI_ARG_DEF (phi, x);
 721                   int p2;
 722
 723                   if (TREE_CODE (arg) != SSA_NAME)
 724                     continue;
 725                   if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
 726                     continue;
 727                   p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
 728                   if (p2 != NO_PARTITION)
 729                     add_coalesce (cl, p, p2, 1);
 730                 }
 731             }
 732         }
 733
 734       /* Coalesce all the result decls together.  */
 735       var = NULL_TREE;
 736       i = 0;
 737       for (x = 0; x < num_var_partitions (map); x++)
 738         {
 739           tree p = partition_to_var (map, x);
 740           if (TREE_CODE (SSA_NAME_VAR(p)) == RESULT_DECL)
 741             {
 742               if (var == NULL_TREE)
 743                 {
 744                   var = p;
 745                   i = x;
 746                 }
 747               else
 748                 add_coalesce (cl, i, x, 1);
 749             }
 750         }
 751     }
 752
 753   /* Build a conflict graph.  */
 754   graph = build_tree_conflict_graph (liveinfo, rv, cl);
 755
 756   if (cl)
 757     {
 758       if (dump_file && (dump_flags & TDF_DETAILS))
 759         {
 760           fprintf (dump_file, "Before sorting:\n");
 761           dump_coalesce_list (dump_file, cl);
 762         }
 763
 764       sort_coalesce_list (cl);
 765
 766       if (dump_file && (dump_flags & TDF_DETAILS))
 767         {
 768           fprintf (dump_file, "\nAfter sorting:\n");
 769           dump_coalesce_list (dump_file, cl);
 770         }
 771     }
 772
 773   /* Put the single element variables back in.  */
 774   root_var_decompact (rv);
 775
 776   /* First, coalesce all live on entry variables to their root variable.
 777      This will ensure the first use is coming from the correct location.  */
 778
 779   live = sbitmap_alloc (num_var_partitions (map));
 780   sbitmap_zero (live);
 781
 782   /* Set 'live' vector to indicate live on entry partitions.  */
 783   num = num_var_partitions (map);
 784   for (x = 0 ; x < num; x++)
 785     {
 786       var = partition_to_var (map, x);
 787       if (default_def (SSA_NAME_VAR (var)) == var)
 788         SET_BIT (live, x);
 789     }
 790
 791   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
 792     {
 793       delete_tree_live_info (liveinfo);
 794       liveinfo = NULL;
 795     }
 796
 797   /* Assign root variable as partition representative for each live on entry
 798      partition.  */
 799   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x,
 800     {
 801       var = root_var (rv, root_var_find (rv, x));
 802       ann = var_ann (var);
 803       /* If these aren't already coalesced...  */
 804       if (partition_to_var (map, x) != var)
 805         {
 806           /* This root variable should have not already been assigned
 807              to another partition which is not coalesced with this one.  */
 808           gcc_assert (!ann->out_of_ssa_tag);
 809
 810           if (dump_file && (dump_flags & TDF_DETAILS))
 811             {
 812               print_exprs (dump_file, "Must coalesce ",
 813                            partition_to_var (map, x),
 814                            " with the root variable ", var, ".\n");
 815             }
 816
 817           change_partition_var (map, var, x);
 818         }
 819     });
 820
 821   sbitmap_free (live);
 822
 823   /* Coalesce partitions live across abnormal edges.  */
 824   coalesce_abnormal_edges (map, graph, rv);
 825
 826   if (dump_file && (dump_flags & TDF_DETAILS))
 827     dump_var_map (dump_file, map);
 828
 829   /* Coalesce partitions.  */
 830   if (flags & SSANORM_USE_COALESCE_LIST)
 831     coalesce_tpa_members (rv, graph, map, cl,
 832                           ((dump_flags & TDF_DETAILS) ? dump_file
 833                                                            : NULL));
 834
 835
 836   if (flags & SSANORM_COALESCE_PARTITIONS)
 837     coalesce_tpa_members (rv, graph, map, NULL,
 838                           ((dump_flags & TDF_DETAILS) ? dump_file
 839                                                            : NULL));
 840   if (cl)
 841     delete_coalesce_list (cl);
 842   root_var_delete (rv);
 843   conflict_graph_delete (graph);
 844
 845   return liveinfo;
 846 }
 847
 848
 849 /* Take the ssa-name var_map MAP, and assign real variables to each
 850    partition.  */
 851
 852 static void
 853 assign_vars (var_map map)
 854 {
 855   int x, i, num, rep;
 856   tree t, var;
 857   var_ann_t ann;
 858   root_var_p rv;
 859
 860   rv = root_var_init (map);
 861   if (!rv)
 862     return;
 863
 864   /* Coalescing may already have forced some partitions to their root
 865      variable. Find these and tag them.  */
 866
 867   num = num_var_partitions (map);
 868   for (x = 0; x < num; x++)
 869     {
 870       var = partition_to_var (map, x);
 871       if (TREE_CODE (var) != SSA_NAME)
 872         {
 873           /* Coalescing will already have verified that more than one
 874              partition doesn't have the same root variable. Simply marked
 875              the variable as assigned.  */
 876           ann = var_ann (var);
 877           ann->out_of_ssa_tag = 1;
 878           if (dump_file && (dump_flags & TDF_DETAILS))
 879             {
 880               fprintf (dump_file, "partition %d has variable ", x);
 881               print_generic_expr (dump_file, var, TDF_SLIM);
 882               fprintf (dump_file, " assigned to it.\n");
 883             }
 884
 885         }
 886     }
 887
 888   num = root_var_num (rv);
 889   for (x = 0; x < num; x++)
 890     {
 891       var = root_var (rv, x);
 892       ann = var_ann (var);
 893       for (i = root_var_first_partition (rv, x);
 894            i != ROOT_VAR_NONE;
 895            i = root_var_next_partition (rv, i))
 896         {
 897           t = partition_to_var (map, i);
 898
 899           if (t == var || TREE_CODE (t) != SSA_NAME)
 900             continue;
 901
 902           rep = var_to_partition (map, t);
 903
 904           if (!ann->out_of_ssa_tag)
 905             {
 906               if (dump_file && (dump_flags & TDF_DETAILS))
 907                 print_exprs (dump_file, "", t, "  --> ", var, "\n");
 908               change_partition_var (map, var, rep);
 909               continue;
 910             }
 911
 912           if (dump_file && (dump_flags & TDF_DETAILS))
 913             print_exprs (dump_file, "", t, " not coalesced with ", var,
 914                          "");
 915
 916           var = create_temp (t);
 917           change_partition_var (map, var, rep);
 918           ann = var_ann (var);
 919
 920           if (dump_file && (dump_flags & TDF_DETAILS))
 921             {
 922               fprintf (dump_file, " -->  New temp:  '");
 923               print_generic_expr (dump_file, var, TDF_SLIM);
 924               fprintf (dump_file, "'\n");
 925             }
 926         }
 927     }
 928
 929   root_var_delete (rv);
 930 }
 931
 932
 933 /* Replace use operand P with whatever variable it has been rewritten to based
 934    on the partitions in MAP.  EXPR is an optional expression vector over SSA
 935    versions which is used to replace P with an expression instead of a variable.
 936    If the stmt is changed, return true.  */
 937
 938 static inline bool
 939 replace_use_variable (var_map map, use_operand_p p, tree *expr)
 940 {
 941   tree new_var;
 942   tree var = USE_FROM_PTR (p);
 943
 944   /* Check if we are replacing this variable with an expression.  */
 945   if (expr)
 946     {
 947       int version = SSA_NAME_VERSION (var);
 948       if (expr[version])
 949         {
 950           tree new_expr = TREE_OPERAND (expr[version], 1);
 951           SET_USE (p, new_expr);
 952           /* Clear the stmt's RHS, or GC might bite us.  */
 953           TREE_OPERAND (expr[version], 1) = NULL_TREE;
 954           return true;
 955         }
 956     }
 957
 958   new_var = var_to_partition_to_var (map, var);
 959   if (new_var)
 960     {
 961       SET_USE (p, new_var);
 962       set_is_used (new_var);
 963       return true;
 964     }
 965   return false;
 966 }
 967
 968
 969 /* Replace def operand DEF_P with whatever variable it has been rewritten to
 970    based on the partitions in MAP.  EXPR is an optional expression vector over
 971    SSA versions which is used to replace DEF_P with an expression instead of a
 972    variable.  If the stmt is changed, return true.  */
 973
 974 static inline bool
 975 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
 976 {
 977   tree new_var;
 978   tree var = DEF_FROM_PTR (def_p);
 979
 980   /* Check if we are replacing this variable with an expression.  */
 981   if (expr)
 982     {
 983       int version = SSA_NAME_VERSION (var);
 984       if (expr[version])
 985         {
 986           tree new_expr = TREE_OPERAND (expr[version], 1);
 987           SET_DEF (def_p, new_expr);
 988           /* Clear the stmt's RHS, or GC might bite us.  */
 989           TREE_OPERAND (expr[version], 1) = NULL_TREE;
 990           return true;
 991         }
 992     }
 993
 994   new_var = var_to_partition_to_var (map, var);
 995   if (new_var)
 996     {
 997       SET_DEF (def_p, new_var);
 998       set_is_used (new_var);
 999       return true;
1000     }
1001   return false;
1002 }
1003
1004
1005 /* Remove any PHI node which is a virtual PHI.  */
1006
1007 static void
1008 eliminate_virtual_phis (void)
1009 {
1010   basic_block bb;
1011   tree phi, next;
1012
1013   FOR_EACH_BB (bb)
1014     {
1015       for (phi = phi_nodes (bb); phi; phi = next)
1016         {
1017           next = PHI_CHAIN (phi);
1018           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1019             {
1020 #ifdef ENABLE_CHECKING
1021               int i;
1022               /* There should be no arguments of this PHI which are in
1023                  the partition list, or we get incorrect results.  */
1024               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1025                 {
1026                   tree arg = PHI_ARG_DEF (phi, i);
1027                   if (TREE_CODE (arg) == SSA_NAME
1028                       && is_gimple_reg (SSA_NAME_VAR (arg)))
1029                     {
1030                       fprintf (stderr, "Argument of PHI is not virtual (");
1031                       print_generic_expr (stderr, arg, TDF_SLIM);
1032                       fprintf (stderr, "), but the result is :");
1033                       print_generic_stmt (stderr, phi, TDF_SLIM);
1034                       internal_error ("SSA corruption");
1035                     }
1036                 }
1037 #endif
1038               remove_phi_node (phi, NULL_TREE, bb);
1039             }
1040         }
1041     }
1042 }
1043
1044
1045 /* This routine will coalesce variables in MAP of the same type which do not
1046    interfere with each other. LIVEINFO is the live range info for variables
1047    of interest.  This will both reduce the memory footprint of the stack, and
1048    allow us to coalesce together local copies of globals and scalarized
1049    component refs.  */
1050
1051 static void
1052 coalesce_vars (var_map map, tree_live_info_p liveinfo)
1053 {
1054   basic_block bb;
1055   type_var_p tv;
1056   tree var;
1057   unsigned x, p, p2;
1058   coalesce_list_p cl;
1059   conflict_graph graph;
1060
1061   cl = create_coalesce_list (map);
1062
1063   /* Merge all the live on entry vectors for coalesced partitions.  */
1064   for (x = 0; x < num_var_partitions (map); x++)
1065     {
1066       var = partition_to_var (map, x);
1067       p = var_to_partition (map, var);
1068       if (p != x)
1069         live_merge_and_clear (liveinfo, p, x);
1070     }
1071
1072   /* When PHI nodes are turned into copies, the result of each PHI node
1073      becomes live on entry to the block. Mark these now.  */
1074   FOR_EACH_BB (bb)
1075     {
1076       tree phi, arg;
1077       unsigned p;
1078
1079       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1080         {
1081           p = var_to_partition (map, PHI_RESULT (phi));
1082
1083           /* Skip virtual PHI nodes.  */
1084           if (p == (unsigned)NO_PARTITION)
1085             continue;
1086
1087           make_live_on_entry (liveinfo, bb, p);
1088
1089           /* Each argument is a potential copy operation. Add any arguments
1090              which are not coalesced to the result to the coalesce list.  */
1091           for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
1092             {
1093               arg = PHI_ARG_DEF (phi, x);
1094               if (!phi_ssa_name_p (arg))
1095                 continue;
1096               p2 = var_to_partition (map, arg);
1097               if (p2 == (unsigned)NO_PARTITION)
1098                 continue;
1099               if (p != p2)
1100                 add_coalesce (cl, p, p2, 1);
1101             }
1102         }
1103    }
1104
1105
1106   /* Re-calculate live on exit info.  */
1107   calculate_live_on_exit (liveinfo);
1108
1109   if (dump_file && (dump_flags & TDF_DETAILS))
1110     {
1111       fprintf (dump_file, "Live range info for variable memory coalescing.\n");
1112       dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL);
1113
1114       fprintf (dump_file, "Coalesce list from phi nodes:\n");
1115       dump_coalesce_list (dump_file, cl);
1116     }
1117
1118
1119   tv = type_var_init (map);
1120   if (dump_file)
1121     type_var_dump (dump_file, tv);
1122   type_var_compact (tv);
1123   if (dump_file)
1124     type_var_dump (dump_file, tv);
1125
1126   graph = build_tree_conflict_graph (liveinfo, tv, cl);
1127
1128   type_var_decompact (tv);
1129   if (dump_file && (dump_flags & TDF_DETAILS))
1130     {
1131       fprintf (dump_file, "type var list now looks like:n");
1132       type_var_dump (dump_file, tv);
1133
1134       fprintf (dump_file, "Coalesce list after conflict graph build:\n");
1135       dump_coalesce_list (dump_file, cl);
1136     }
1137
1138   sort_coalesce_list (cl);
1139   if (dump_file && (dump_flags & TDF_DETAILS))
1140     {
1141       fprintf (dump_file, "Coalesce list after sorting:\n");
1142       dump_coalesce_list (dump_file, cl);
1143     }
1144
1145   coalesce_tpa_members (tv, graph, map, cl,
1146                         ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1147
1148   type_var_delete (tv);
1149   delete_coalesce_list (cl);
1150 }
1151
1152
1153 /* Temporary Expression Replacement (TER)
1154
1155    Replace SSA version variables during out-of-ssa with their defining
1156    expression if there is only one use of the variable.
1157
1158    A pass is made through the function, one block at a time.  No cross block
1159    information is tracked.
1160
1161    Variables which only have one use, and whose defining stmt is considered
1162    a replaceable expression (see check_replaceable) are entered into
1163    consideration by adding a list of dependent partitions to the version_info
1164    vector for that ssa_name_version.  This information comes from the partition
1165    mapping for each USE.  At the same time, the partition_dep_list vector for
1166    these partitions have this version number entered into their lists.
1167
1168    When the use of a replaceable ssa_variable is encountered, the dependence
1169    list in version_info[] is moved to the "pending_dependence" list in case
1170    the current expression is also replaceable. (To be determined later in
1171    processing this stmt.) version_info[] for the version is then updated to
1172    point to the defining stmt and the 'replaceable' bit is set.
1173
1174    Any partition which is defined by a statement 'kills' any expression which
1175    is dependent on this partition.  Every ssa version in the partitions'
1176    dependence list is removed from future consideration.
1177
1178    All virtual references are lumped together.  Any expression which is
1179    dependent on any virtual variable (via a VUSE) has a dependence added
1180    to the special partition defined by VIRTUAL_PARTITION.
1181
1182    Whenever a V_MAY_DEF is seen, all expressions dependent this
1183    VIRTUAL_PARTITION are removed from consideration.
1184
1185    At the end of a basic block, all expression are removed from consideration
1186    in preparation for the next block.
1187
1188    The end result is a vector over SSA_NAME_VERSION which is passed back to
1189    rewrite_out_of_ssa.  As the SSA variables are being rewritten, instead of
1190    replacing the SSA_NAME tree element with the partition it was assigned,
1191    it is replaced with the RHS of the defining expression.  */
1192
1193
1194 /* Dependency list element.  This can contain either a partition index or a
1195    version number, depending on which list it is in.  */
1196
1197 typedef struct value_expr_d
1198 {
1199   int value;
1200   struct value_expr_d *next;
1201 } *value_expr_p;
1202
1203
1204 /* Temporary Expression Replacement (TER) table information.  */
1205
1206 typedef struct temp_expr_table_d
1207 {
1208   var_map map;
1209   void **version_info;
1210   value_expr_p *partition_dep_list;
1211   bitmap replaceable;
1212   bool saw_replaceable;
1213   int virtual_partition;
1214   bitmap partition_in_use;
1215   value_expr_p free_list;
1216   value_expr_p pending_dependence;
1217 } *temp_expr_table_p;
1218
1219 /* Used to indicate a dependency on V_MAY_DEFs.  */
1220 #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
1221
1222 static temp_expr_table_p new_temp_expr_table (var_map);
1223 static tree *free_temp_expr_table (temp_expr_table_p);
1224 static inline value_expr_p new_value_expr (temp_expr_table_p);
1225 static inline void free_value_expr (temp_expr_table_p, value_expr_p);
1226 static inline value_expr_p find_value_in_list (value_expr_p, int,
1227                                                value_expr_p *);
1228 static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
1229 static inline void add_info_to_list (temp_expr_table_p, value_expr_p *,
1230                                      value_expr_p);
1231 static value_expr_p remove_value_from_list (value_expr_p *, int);
1232 static void add_dependance (temp_expr_table_p, int, tree);
1233 static bool check_replaceable (temp_expr_table_p, tree);
1234 static void finish_expr (temp_expr_table_p, int, bool);
1235 static void mark_replaceable (temp_expr_table_p, tree);
1236 static inline void kill_expr (temp_expr_table_p, int, bool);
1237 static inline void kill_virtual_exprs (temp_expr_table_p, bool);
1238 static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
1239 static tree *find_replaceable_exprs (var_map);
1240 static void dump_replaceable_exprs (FILE *, tree *);
1241
1242
1243 /* Create a new TER table for MAP.  */
1244
1245 static temp_expr_table_p
1246 new_temp_expr_table (var_map map)
1247 {
1248   temp_expr_table_p t;
1249
1250   t = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
1251   t->map = map;
1252
1253   t->version_info = xcalloc (num_ssa_names + 1, sizeof (void *));
1254   t->partition_dep_list = xcalloc (num_var_partitions (map) + 1,
1255                                    sizeof (value_expr_p));
1256
1257   t->replaceable = BITMAP_XMALLOC ();
1258   t->partition_in_use = BITMAP_XMALLOC ();
1259
1260   t->saw_replaceable = false;
1261   t->virtual_partition = num_var_partitions (map);
1262   t->free_list = NULL;
1263   t->pending_dependence = NULL;
1264
1265   return t;
1266 }
1267
1268
1269 /* Free TER table T.  If there are valid replacements, return the expression
1270    vector.  */
1271
1272 static tree *
1273 free_temp_expr_table (temp_expr_table_p t)
1274 {
1275   value_expr_p p;
1276   tree *ret = NULL;
1277
1278 #ifdef ENABLE_CHECKING
1279   unsigned x;
1280   for (x = 0; x <= num_var_partitions (t->map); x++)
1281     gcc_assert (!t->partition_dep_list[x]);
1282 #endif
1283
1284   while ((p = t->free_list))
1285     {
1286       t->free_list = p->next;
1287       free (p);
1288     }
1289
1290   BITMAP_XFREE (t->partition_in_use);
1291   BITMAP_XFREE (t->replaceable);
1292
1293   free (t->partition_dep_list);
1294   if (t->saw_replaceable)
1295     ret = (tree *)t->version_info;
1296   else
1297     free (t->version_info);
1298
1299   free (t);
1300   return ret;
1301 }
1302
1303
1304 /* Allocate a new value list node. Take it from the free list in TABLE if
1305    possible.  */
1306
1307 static inline value_expr_p
1308 new_value_expr (temp_expr_table_p table)
1309 {
1310   value_expr_p p;
1311   if (table->free_list)
1312     {
1313       p = table->free_list;
1314       table->free_list = p->next;
1315     }
1316   else
1317     p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
1318
1319   return p;
1320 }
1321
1322
1323 /* Add value list node P to the free list in TABLE.  */
1324
1325 static inline void
1326 free_value_expr (temp_expr_table_p table, value_expr_p p)
1327 {
1328   p->next = table->free_list;
1329   table->free_list = p;
1330 }
1331
1332
1333 /* Find VALUE if it's in LIST.  Return a pointer to the list object if found,
1334    else return NULL.  If LAST_PTR is provided, it will point to the previous
1335    item upon return, or NULL if this is the first item in the list.  */
1336
1337 static inline value_expr_p
1338 find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
1339 {
1340   value_expr_p curr;
1341   value_expr_p last = NULL;
1342
1343   for (curr = list; curr; last = curr, curr = curr->next)
1344     {
1345       if (curr->value == value)
1346         break;
1347     }
1348   if (last_ptr)
1349     *last_ptr = last;
1350   return curr;
1351 }
1352
1353
1354 /* Add VALUE to LIST, if it isn't already present.  TAB is the expression
1355    table */
1356
1357 static inline void
1358 add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
1359 {
1360   value_expr_p info;
1361
1362   if (!find_value_in_list (*list, value, NULL))
1363     {
1364       info = new_value_expr (tab);
1365       info->value = value;
1366       info->next = *list;
1367       *list = info;
1368     }
1369 }
1370
1371
1372 /* Add value node INFO if it's value isn't already in LIST.  Free INFO if
1373    it is already in the list. TAB is the expression table.  */
1374
1375 static inline void
1376 add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
1377 {
1378   if (find_value_in_list (*list, info->value, NULL))
1379     free_value_expr (tab, info);
1380   else
1381     {
1382       info->next = *list;
1383       *list = info;
1384     }
1385 }
1386
1387
1388 /* Look for VALUE in LIST.  If found, remove it from the list and return it's
1389    pointer.  */
1390
1391 static value_expr_p
1392 remove_value_from_list (value_expr_p *list, int value)
1393 {
1394   value_expr_p info, last;
1395
1396   info = find_value_in_list (*list, value, &last);
1397   if (!info)
1398     return NULL;
1399   if (!last)
1400     *list = info->next;
1401   else
1402     last->next = info->next;
1403
1404   return info;
1405 }
1406
1407
1408 /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is
1409    replaceable by an expression, add a dependence each of the elements of the
1410    expression.  These are contained in the pending list.  TAB is the
1411    expression table.  */
1412
1413 static void
1414 add_dependance (temp_expr_table_p tab, int version, tree var)
1415 {
1416   int i, x;
1417   value_expr_p info;
1418
1419   i = SSA_NAME_VERSION (var);
1420   if (bitmap_bit_p (tab->replaceable, i))
1421     {
1422       /* This variable is being substituted, so use whatever dependences
1423          were queued up when we marked this as replaceable earlier.  */
1424       while ((info = tab->pending_dependence))
1425         {
1426           tab->pending_dependence = info->next;
1427           /* Get the partition this variable was dependent on. Reuse this
1428              object to represent the current  expression instead.  */
1429           x = info->value;
1430           info->value = version;
1431           add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
1432           add_value_to_list (tab,
1433                              (value_expr_p *)&(tab->version_info[version]), x);
1434           bitmap_set_bit (tab->partition_in_use, x);
1435         }
1436     }
1437   else
1438     {
1439       i = var_to_partition (tab->map, var);
1440       gcc_assert (i != NO_PARTITION);
1441       add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
1442       add_value_to_list (tab,
1443                          (value_expr_p *)&(tab->version_info[version]), i);
1444       bitmap_set_bit (tab->partition_in_use, i);
1445     }
1446 }
1447
1448
1449 /* Check if expression STMT is suitable for replacement in table TAB.  If so,
1450    create an expression entry.  Return true if this stmt is replaceable.  */
1451
1452 static bool
1453 check_replaceable (temp_expr_table_p tab, tree stmt)
1454 {
1455   stmt_ann_t ann;
1456   vuse_optype vuseops;
1457   def_optype defs;
1458   use_optype uses;
1459   tree var, def;
1460   int num_use_ops, version;
1461   var_map map = tab->map;
1462   ssa_op_iter iter;
1463   tree call_expr;
1464
1465   if (TREE_CODE (stmt) != MODIFY_EXPR)
1466     return false;
1467
1468   ann = stmt_ann (stmt);
1469   defs = DEF_OPS (ann);
1470
1471   /* Punt if there is more than 1 def, or more than 1 use.  */
1472   if (NUM_DEFS (defs) != 1)
1473     return false;
1474   def = DEF_OP (defs, 0);
1475   if (version_ref_count (map, def) != 1)
1476     return false;
1477
1478   /* There must be no V_MAY_DEFS.  */
1479   if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) != 0)
1480     return false;
1481
1482   /* There must be no V_MUST_DEFS.  */
1483   if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) != 0)
1484     return false;
1485
1486   /* Float expressions must go through memory if float-store is on.  */
1487   if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1488     return false;
1489
1490   /* Calls to functions with side-effects cannot be replaced.  */
1491   if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
1492     {
1493       int call_flags = call_expr_flags (call_expr);
1494       if (TREE_SIDE_EFFECTS (call_expr)
1495           && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1496         return false;
1497     }
1498
1499   uses = USE_OPS (ann);
1500   num_use_ops = NUM_USES (uses);
1501   vuseops = VUSE_OPS (ann);
1502
1503   /* Any expression which has no virtual operands and no real operands
1504      should have been propagated if it's possible to do anything with them.
1505      If this happens here, it probably exists that way for a reason, so we
1506      won't touch it.   An example is:
1507          b_4 = &tab
1508      There are no virtual uses nor any real uses, so we just leave this
1509      alone to be safe.  */
1510
1511   if (num_use_ops == 0 && NUM_VUSES (vuseops) == 0)
1512     return false;
1513
1514   version = SSA_NAME_VERSION (def);
1515
1516   /* Add this expression to the dependency list for each use partition.  */
1517   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1518     {
1519       add_dependance (tab, version, var);
1520     }
1521
1522   /* If there are VUSES, add a dependence on virtual defs.  */
1523   if (NUM_VUSES (vuseops) != 0)
1524     {
1525       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
1526                          VIRTUAL_PARTITION (tab));
1527       add_value_to_list (tab,
1528                          &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]),
1529                          version);
1530       bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1531     }
1532
1533   return true;
1534 }
1535
1536
1537 /* This function will remove the expression for VERSION from replacement
1538    consideration.n table TAB  If 'replace' is true, it is marked as
1539    replaceable, otherwise not.  */
1540
1541 static void
1542 finish_expr (temp_expr_table_p tab, int version, bool replace)
1543 {
1544   value_expr_p info, tmp;
1545   int partition;
1546
1547   /* Remove this expression from its dependent lists.  The partition dependence
1548      list is retained and transfered later to whomever uses this version.  */
1549   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1550     {
1551       partition = info->value;
1552       gcc_assert (tab->partition_dep_list[partition]);
1553       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
1554                                     version);
1555       gcc_assert (tmp);
1556       free_value_expr (tab, tmp);
1557       /* Only clear the bit when the dependency list is emptied via
1558          a replacement. Otherwise kill_expr will take care of it.  */
1559       if (!(tab->partition_dep_list[partition]) && replace)
1560         bitmap_clear_bit (tab->partition_in_use, partition);
1561       tmp = info->next;
1562       if (!replace)
1563         free_value_expr (tab, info);
1564     }
1565
1566   if (replace)
1567     {
1568       tab->saw_replaceable = true;
1569       bitmap_set_bit (tab->replaceable, version);
1570     }
1571   else
1572     {
1573       gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1574       tab->version_info[version] = NULL;
1575     }
1576 }
1577
1578
1579 /* Mark the expression associated with VAR as replaceable, and enter
1580    the defining stmt into the version_info table TAB.  */
1581
1582 static void
1583 mark_replaceable (temp_expr_table_p tab, tree var)
1584 {
1585   value_expr_p info;
1586   int version = SSA_NAME_VERSION (var);
1587   finish_expr (tab, version, true);
1588
1589   /* Move the dependence list to the pending list.  */
1590   if (tab->version_info[version])
1591     {
1592       info = (value_expr_p) tab->version_info[version];
1593       for ( ; info->next; info = info->next)
1594         continue;
1595       info->next = tab->pending_dependence;
1596       tab->pending_dependence = (value_expr_p)tab->version_info[version];
1597     }
1598
1599   tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1600 }
1601
1602
1603 /* This function marks any expression in TAB which is dependent on PARTITION
1604    as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
1605    should have its bit cleared.  Since this routine can be called within an
1606    EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
1607
1608 static inline void
1609 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1610 {
1611   value_expr_p ptr;
1612
1613   /* Mark every active expr dependent on this var as not replaceable.  */
1614   while ((ptr = tab->partition_dep_list[partition]) != NULL)
1615     finish_expr (tab, ptr->value, false);
1616
1617   if (clear_bit)
1618     bitmap_clear_bit (tab->partition_in_use, partition);
1619 }
1620
1621
1622 /* This function kills all expressions in TAB which are dependent on virtual
1623    DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
1624
1625 static inline void
1626 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1627 {
1628   kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1629 }
1630
1631
1632 /* This function processes basic block BB, and looks for variables which can
1633    be replaced by their expressions.  Results are stored in TAB.  */
1634
1635 static void
1636 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1637 {
1638   block_stmt_iterator bsi;
1639   tree stmt, def;
1640   stmt_ann_t ann;
1641   int partition;
1642   var_map map = tab->map;
1643   value_expr_p p;
1644   ssa_op_iter iter;
1645
1646   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1647     {
1648       stmt = bsi_stmt (bsi);
1649       ann = stmt_ann (stmt);
1650
1651       /* Determine if this stmt finishes an existing expression.  */
1652       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE)
1653         {
1654           if (tab->version_info[SSA_NAME_VERSION (def)])
1655             {
1656               /* Mark expression as replaceable unless stmt is volatile.  */
1657               if (!ann->has_volatile_ops)
1658                 mark_replaceable (tab, def);
1659               else
1660                 finish_expr (tab, SSA_NAME_VERSION (def), false);
1661             }
1662         }
1663
1664       /* Next, see if this stmt kills off an active expression.  */
1665       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1666         {
1667           partition = var_to_partition (map, def);
1668           if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1669             kill_expr (tab, partition, true);
1670         }
1671
1672       /* Now see if we are creating a new expression or not.  */
1673       if (!ann->has_volatile_ops)
1674         check_replaceable (tab, stmt);
1675
1676       /* Free any unused dependency lists.  */
1677       while ((p = tab->pending_dependence))
1678         {
1679           tab->pending_dependence = p->next;
1680           free_value_expr (tab, p);
1681         }
1682
1683       /* A V_MAY_DEF kills any expression using a virtual operand.  */
1684       if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0)
1685         kill_virtual_exprs (tab, true);
1686
1687       /* A V_MUST_DEF kills any expression using a virtual operand.  */
1688       if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0)
1689         kill_virtual_exprs (tab, true);
1690     }
1691 }
1692
1693
1694 /* This function is the driver routine for replacement of temporary expressions
1695    in the SSA->normal phase, operating on MAP.  If there are replaceable
1696    expressions, a table is returned which maps SSA versions to the
1697    expressions they should be replaced with.  A NULL_TREE indicates no
1698    replacement should take place.  If there are no replacements at all,
1699    NULL is returned by the function, otherwise an expression vector indexed
1700    by SSA_NAME version numbers.  */
1701
1702 static tree *
1703 find_replaceable_exprs (var_map map)
1704 {
1705   basic_block bb;
1706   unsigned i;
1707   temp_expr_table_p table;
1708   tree *ret;
1709
1710   table = new_temp_expr_table (map);
1711   FOR_EACH_BB (bb)
1712     {
1713       bitmap_iterator bi;
1714
1715       find_replaceable_in_bb (table, bb);
1716       EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
1717         {
1718           kill_expr (table, i, false);
1719         }
1720     }
1721
1722   ret = free_temp_expr_table (table);
1723   return ret;
1724 }
1725
1726
1727 /* Dump TER expression table EXPR to file F.  */
1728
1729 static void
1730 dump_replaceable_exprs (FILE *f, tree *expr)
1731 {
1732   tree stmt, var;
1733   int x;
1734   fprintf (f, "\nReplacing Expressions\n");
1735   for (x = 0; x < (int)num_ssa_names + 1; x++)
1736     if (expr[x])
1737       {
1738         stmt = expr[x];
1739         var = DEF_OP (STMT_DEF_OPS (stmt), 0);
1740         print_generic_expr (f, var, TDF_SLIM);
1741         fprintf (f, " replace with --> ");
1742         print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1743         fprintf (f, "\n");
1744       }
1745   fprintf (f, "\n");
1746 }
1747
1748
1749 /* Helper function for discover_nonconstant_array_refs.
1750    Look for ARRAY_REF nodes with non-constant indexes and mark them
1751    addressable.  */
1752
1753 static tree
1754 discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
1755                                    void *data ATTRIBUTE_UNUSED)
1756 {
1757   tree t = *tp;
1758
1759   if (IS_TYPE_OR_DECL_P (t))
1760     *walk_subtrees = 0;
1761   else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1762     {
1763       while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1764               && is_gimple_min_invariant (TREE_OPERAND (t, 1))
1765               && (!TREE_OPERAND (t, 2)
1766                   || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1767              || (TREE_CODE (t) == COMPONENT_REF
1768                  && (!TREE_OPERAND (t,2)
1769                      || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1770              || TREE_CODE (t) == BIT_FIELD_REF
1771              || TREE_CODE (t) == REALPART_EXPR
1772              || TREE_CODE (t) == IMAGPART_EXPR
1773              || TREE_CODE (t) == VIEW_CONVERT_EXPR
1774              || TREE_CODE (t) == NOP_EXPR
1775              || TREE_CODE (t) == CONVERT_EXPR)
1776         t = TREE_OPERAND (t, 0);
1777
1778       if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1779         {
1780           t = get_base_address (t);
1781           if (t && DECL_P (t))
1782             TREE_ADDRESSABLE (t) = 1;
1783         }
1784
1785       *walk_subtrees = 0;
1786     }
1787
1788   return NULL_TREE;
1789 }
1790
1791
1792 /* RTL expansion is not able to compile array references with variable
1793    offsets for arrays stored in single register.  Discover such
1794    expressions and mark variables as addressable to avoid this
1795    scenario.  */
1796
1797 static void
1798 discover_nonconstant_array_refs (void)
1799 {
1800   basic_block bb;
1801   block_stmt_iterator bsi;
1802
1803   FOR_EACH_BB (bb)
1804     {
1805       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1806         walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
1807                    NULL , NULL);
1808     }
1809 }
1810
1811
1812 /* This function will rewrite the current program using the variable mapping
1813    found in MAP.  If the replacement vector VALUES is provided, any
1814    occurrences of partitions with non-null entries in the vector will be
1815    replaced with the expression in the vector instead of its mapped
1816    variable.  */
1817
1818 static void
1819 rewrite_trees (var_map map, tree *values)
1820 {
1821   elim_graph g;
1822   basic_block bb;
1823   block_stmt_iterator si;
1824   edge e;
1825   tree phi;
1826   bool changed;
1827
1828 #ifdef ENABLE_CHECKING
1829   /* Search for PHIs where the destination has no partition, but one
1830      or more arguments has a partition.  This should not happen and can
1831      create incorrect code.  */
1832   FOR_EACH_BB (bb)
1833     {
1834       tree phi;
1835
1836       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1837         {
1838           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1839
1840           if (T0 == NULL_TREE)
1841             {
1842               int i;
1843
1844               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1845                 {
1846                   tree arg = PHI_ARG_DEF (phi, i);
1847
1848                   if (TREE_CODE (arg) == SSA_NAME
1849                       && var_to_partition (map, arg) != NO_PARTITION)
1850                     {
1851                       fprintf (stderr, "Argument of PHI is in a partition :(");
1852                       print_generic_expr (stderr, arg, TDF_SLIM);
1853                       fprintf (stderr, "), but the result is not :");
1854                       print_generic_stmt (stderr, phi, TDF_SLIM);
1855                       internal_error ("SSA corruption");
1856                     }
1857                 }
1858             }
1859         }
1860     }
1861 #endif
1862
1863   /* Replace PHI nodes with any required copies.  */
1864   g = new_elim_graph (map->num_partitions);
1865   g->map = map;
1866   FOR_EACH_BB (bb)
1867     {
1868       for (si = bsi_start (bb); !bsi_end_p (si); )
1869         {
1870           size_t num_uses, num_defs;
1871           use_optype uses;
1872           def_optype defs;
1873           tree stmt = bsi_stmt (si);
1874           use_operand_p use_p;
1875           def_operand_p def_p;
1876           int remove = 0, is_copy = 0;
1877           stmt_ann_t ann;
1878           ssa_op_iter iter;
1879
1880           get_stmt_operands (stmt);
1881           ann = stmt_ann (stmt);
1882           changed = false;
1883
1884           if (TREE_CODE (stmt) == MODIFY_EXPR
1885               && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1886             is_copy = 1;
1887
1888           uses = USE_OPS (ann);
1889           num_uses = NUM_USES (uses);
1890           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1891             {
1892               if (replace_use_variable (map, use_p, values))
1893                 changed = true;
1894             }
1895
1896           defs = DEF_OPS (ann);
1897           num_defs = NUM_DEFS (defs);
1898
1899           /* Mark this stmt for removal if it is the list of replaceable
1900              expressions.  */
1901           if (values && num_defs == 1)
1902             {
1903               tree def = DEF_OP (defs, 0);
1904               tree val;
1905               val = values[SSA_NAME_VERSION (def)];
1906               if (val)
1907                 remove = 1;
1908             }
1909           if (!remove)
1910             {
1911               FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1912                 {
1913                   if (replace_def_variable (map, def_p, NULL))
1914                     changed = true;
1915
1916                   /* If both SSA_NAMEs coalesce to the same variable,
1917                      mark the now redundant copy for removal.  */
1918                   if (is_copy
1919                       && num_uses == 1
1920                       && (DEF_FROM_PTR (def_p) == USE_OP (uses, 0)))
1921                     remove = 1;
1922                 }
1923               if (changed & !remove)
1924                 modify_stmt (stmt);
1925             }
1926
1927           /* Remove any stmts marked for removal.  */
1928           if (remove)
1929             bsi_remove (&si);
1930           else
1931             bsi_next (&si);
1932         }
1933
1934       phi = phi_nodes (bb);
1935       if (phi)
1936         {
1937           edge_iterator ei;
1938           FOR_EACH_EDGE (e, ei, bb->preds)
1939             eliminate_phi (e, g);
1940         }
1941     }
1942
1943   delete_elim_graph (g);
1944 }
1945
1946
1947 /* These are the local work structures used to determine the best place to
1948    insert the copies that were placed on edges by the SSA->normal pass..  */
1949 static varray_type edge_leader = NULL;
1950 static varray_type GTY(()) stmt_list = NULL;
1951 static bitmap leader_has_match = NULL;
1952 static edge leader_match = NULL;
1953
1954
1955 /* Pass this function to make_forwarder_block so that all the edges with
1956    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
1957 static bool
1958 same_stmt_list_p (edge e)
1959 {
1960   return (e->aux == (PTR) leader_match) ? true : false;
1961 }
1962
1963
1964 /* Return TRUE if S1 and S2 are equivalent copies.  */
1965 static inline bool
1966 identical_copies_p (tree s1, tree s2)
1967 {
1968 #ifdef ENABLE_CHECKING
1969   gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
1970   gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
1971   gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
1972   gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
1973 #endif
1974
1975   if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
1976     return false;
1977
1978   s1 = TREE_OPERAND (s1, 1);
1979   s2 = TREE_OPERAND (s2, 1);
1980
1981   if (s1 != s2)
1982     return false;
1983
1984   return true;
1985 }
1986
1987
1988 /* Compare the PENDING_STMT list for two edges, and return true if the lists
1989    contain the same sequence of copies.  */
1990
1991 static inline bool
1992 identical_stmt_lists_p (edge e1, edge e2)
1993 {
1994   tree t1 = PENDING_STMT (e1);
1995   tree t2 = PENDING_STMT (e2);
1996   tree_stmt_iterator tsi1, tsi2;
1997
1998   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
1999   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
2000
2001   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
2002        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
2003        tsi_next (&tsi1), tsi_next (&tsi2))
2004     {
2005       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
2006         break;
2007     }
2008
2009   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
2010     return false;
2011
2012   return true;
2013 }
2014
2015
2016 /* Look at all the incoming edges to block BB, and decide where the best place
2017    to insert the stmts on each edge are, and perform those insertions.   Output
2018    any debug information to DEBUG_FILE.  Return true if anything other than a
2019    standard edge insertion is done.  */
2020
2021 static bool
2022 analyze_edges_for_bb (basic_block bb, FILE *debug_file)
2023 {
2024   edge e;
2025   edge_iterator ei;
2026   int count;
2027   unsigned int x;
2028   bool have_opportunity;
2029   block_stmt_iterator bsi;
2030   tree stmt;
2031   edge single_edge = NULL;
2032   bool is_label;
2033
2034   count = 0;
2035
2036   /* Blocks which contain at least one abnormal edge cannot use
2037      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
2038      found on edges in these block.  */
2039   have_opportunity = true;
2040   FOR_EACH_EDGE (e, ei, bb->preds)
2041     if (e->flags & EDGE_ABNORMAL)
2042       {
2043         have_opportunity = false;
2044         break;
2045       }
2046
2047   if (!have_opportunity)
2048     {
2049       FOR_EACH_EDGE (e, ei, bb->preds)
2050         if (PENDING_STMT (e))
2051           bsi_commit_one_edge_insert (e, NULL);
2052       return false;
2053     }
2054   /* Find out how many edges there are with interesting pending stmts on them.
2055      Commit the stmts on edges we are not interested in.  */
2056   FOR_EACH_EDGE (e, ei, bb->preds)
2057     {
2058       if (PENDING_STMT (e))
2059         {
2060           gcc_assert (!(e->flags & EDGE_ABNORMAL));
2061           if (e->flags & EDGE_FALLTHRU)
2062             {
2063               bsi = bsi_start (e->src);
2064               if (!bsi_end_p (bsi))
2065                 {
2066                   stmt = bsi_stmt (bsi);
2067                   bsi_next (&bsi);
2068                   gcc_assert (stmt != NULL_TREE);
2069                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
2070                   /* Punt if it has non-label stmts, or isn't local.  */
2071                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
2072                       || !bsi_end_p (bsi))
2073                     {
2074                       bsi_commit_one_edge_insert (e, NULL);
2075                       continue;
2076                     }
2077                 }
2078             }
2079           single_edge = e;
2080           count++;
2081         }
2082     }
2083
2084   /* If there aren't at least 2 edges, no sharing will happen.  */
2085   if (count < 2)
2086     {
2087       if (single_edge)
2088         bsi_commit_one_edge_insert (single_edge, NULL);
2089       return false;
2090     }
2091
2092   /* Ensure that we have empty worklists.  */
2093   if (edge_leader == NULL)
2094     {
2095       VARRAY_EDGE_INIT (edge_leader, 25, "edge_leader");
2096       VARRAY_TREE_INIT (stmt_list, 25, "stmt_list");
2097       leader_has_match = BITMAP_XMALLOC ();
2098     }
2099   else
2100     {
2101 #ifdef ENABLE_CHECKING
2102       gcc_assert (VARRAY_ACTIVE_SIZE (edge_leader) == 0);
2103       gcc_assert (VARRAY_ACTIVE_SIZE (stmt_list) == 0);
2104       gcc_assert (bitmap_empty_p (leader_has_match));
2105 #endif
2106     }
2107
2108   /* Find the "leader" block for each set of unique stmt lists.  Preference is
2109      given to FALLTHRU blocks since they would need a GOTO to arrive at another
2110      block.  The leader edge destination is the block which all the other edges
2111      with the same stmt list will be redirected to.  */
2112   have_opportunity = false;
2113   FOR_EACH_EDGE (e, ei, bb->preds)
2114     {
2115       if (PENDING_STMT (e))
2116         {
2117           bool found = false;
2118
2119           /* Look for the same stmt list in edge leaders list.  */
2120           for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2121             {
2122               edge leader = VARRAY_EDGE (edge_leader, x);
2123               if (identical_stmt_lists_p (leader, e))
2124                 {
2125                   /* Give this edge the same stmt list pointer.  */
2126                   PENDING_STMT (e) = NULL;
2127                   e->aux = leader;
2128                   bitmap_set_bit (leader_has_match, x);
2129                   have_opportunity = found = true;
2130                   break;
2131                 }
2132             }
2133
2134           /* If no similar stmt list, add this edge to the leader list.  */
2135           if (!found)
2136             {
2137               VARRAY_PUSH_EDGE (edge_leader, e);
2138               VARRAY_PUSH_TREE (stmt_list, PENDING_STMT (e));
2139             }
2140         }
2141      }
2142
2143   /* If there are no similar lists, just issue the stmts.  */
2144   if (!have_opportunity)
2145     {
2146       for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2147         bsi_commit_one_edge_insert (VARRAY_EDGE (edge_leader, x), NULL);
2148       VARRAY_POP_ALL (edge_leader);
2149       VARRAY_POP_ALL (stmt_list);
2150       bitmap_clear (leader_has_match);
2151       return false;
2152     }
2153
2154
2155   if (debug_file)
2156     fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
2157              bb->index);
2158
2159
2160   /* For each common list, create a forwarding block and issue the stmt's
2161      in that block.  */
2162   for (x = 0 ; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2163     if (bitmap_bit_p (leader_has_match, x))
2164       {
2165         edge new_edge, leader_edge;
2166         block_stmt_iterator bsi;
2167         tree curr_stmt_list;
2168
2169         leader_match = leader_edge = VARRAY_EDGE (edge_leader, x);
2170
2171         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
2172            for various PHI manipulations, so it gets cleared whhen calls are
2173            made to make_forwarder_block(). So make sure the edge is clear,
2174            and use the saved stmt list.  */
2175         PENDING_STMT (leader_edge) = NULL;
2176         leader_edge->aux = leader_edge;
2177         curr_stmt_list = VARRAY_TREE (stmt_list, x);
2178
2179         new_edge = make_forwarder_block (leader_edge->dest, same_stmt_list_p,
2180                                          NULL);
2181         bb = new_edge->dest;
2182         if (debug_file)
2183           {
2184             fprintf (debug_file, "Splitting BB %d for Common stmt list.  ",
2185                      leader_edge->dest->index);
2186             fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
2187             print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
2188           }
2189
2190         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
2191           {
2192             e->aux = NULL;
2193             if (debug_file)
2194               fprintf (debug_file, "  Edge (%d->%d) lands here.\n",
2195                        e->src->index, e->dest->index);
2196           }
2197
2198         bsi = bsi_last (leader_edge->dest);
2199         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
2200
2201         leader_match = NULL;
2202         /* We should never get a new block now.  */
2203       }
2204     else
2205       {
2206         e = VARRAY_EDGE (edge_leader, x);
2207         PENDING_STMT (e) = VARRAY_TREE (stmt_list, x);
2208         bsi_commit_one_edge_insert (e, NULL);
2209       }
2210
2211
2212   /* Clear the working data structures.  */
2213   VARRAY_POP_ALL (edge_leader);
2214   VARRAY_POP_ALL (stmt_list);
2215   bitmap_clear (leader_has_match);
2216
2217   return true;
2218 }
2219
2220
2221 /* This function will analyze the insertions which were performed on edges,
2222    and decide whether they should be left on that edge, or whether it is more
2223    efficient to emit some subset of them in a single block.  All stmts are
2224    inserted somewhere, and if non-NULL, debug information is printed via
2225    DUMP_FILE.  */
2226
2227 static void
2228 perform_edge_inserts (FILE *dump_file)
2229 {
2230   basic_block bb;
2231   bool changed = false;
2232
2233   if (dump_file)
2234     fprintf(dump_file, "Analyzing Edge Insertions.\n");
2235
2236   FOR_EACH_BB (bb)
2237     changed |= analyze_edges_for_bb (bb, dump_file);
2238
2239   changed |= analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
2240
2241   /* Clear out any tables which were created.  */
2242   edge_leader = NULL;
2243   BITMAP_XFREE (leader_has_match);
2244
2245   if (changed)
2246     {
2247       free_dominance_info (CDI_DOMINATORS);
2248       free_dominance_info (CDI_POST_DOMINATORS);
2249     }
2250
2251 #ifdef ENABLE_CHECKING
2252   {
2253     edge_iterator ei;
2254     edge e;
2255     FOR_EACH_BB (bb)
2256       {
2257         FOR_EACH_EDGE (e, ei, bb->preds)
2258           {
2259             if (PENDING_STMT (e))
2260               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
2261                      e->src->index, e->dest->index);
2262           }
2263         FOR_EACH_EDGE (e, ei, bb->succs)
2264           {
2265             if (PENDING_STMT (e))
2266               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
2267                      e->src->index, e->dest->index);
2268           }
2269       }
2270     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2271       {
2272         if (PENDING_STMT (e))
2273           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
2274                  e->src->index, e->dest->index);
2275       }
2276     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
2277       {
2278         if (PENDING_STMT (e))
2279           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
2280                  e->src->index, e->dest->index);
2281       }
2282   }
2283 #endif
2284 }
2285
2286
2287 /* Remove the variables specified in MAP from SSA form.  Any debug information
2288    is sent to DUMP.  FLAGS indicate what options should be used.  */
2289
2290 static void
2291 remove_ssa_form (FILE *dump, var_map map, int flags)
2292 {
2293   tree_live_info_p liveinfo;
2294   basic_block bb;
2295   tree phi, next;
2296   FILE *save;
2297   tree *values = NULL;
2298
2299   save = dump_file;
2300   dump_file = dump;
2301
2302   /* If we are not combining temps, don't calculate live ranges for variables
2303      with only one SSA version.  */
2304   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2305     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
2306   else
2307     compact_var_map (map, VARMAP_NORMAL);
2308
2309   if (dump_file && (dump_flags & TDF_DETAILS))
2310     dump_var_map (dump_file, map);
2311
2312   liveinfo = coalesce_ssa_name (map, flags);
2313
2314   /* Make sure even single occurrence variables are in the list now.  */
2315   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2316     compact_var_map (map, VARMAP_NORMAL);
2317
2318   if (dump_file && (dump_flags & TDF_DETAILS))
2319     {
2320       fprintf (dump_file, "After Coalescing:\n");
2321       dump_var_map (dump_file, map);
2322     }
2323
2324   if (flags & SSANORM_PERFORM_TER)
2325     {
2326       values = find_replaceable_exprs (map);
2327       if (values && dump_file && (dump_flags & TDF_DETAILS))
2328         dump_replaceable_exprs (dump_file, values);
2329     }
2330
2331   /* Assign real variables to the partitions now.  */
2332   assign_vars (map);
2333
2334   if (dump_file && (dump_flags & TDF_DETAILS))
2335     {
2336       fprintf (dump_file, "After Root variable replacement:\n");
2337       dump_var_map (dump_file, map);
2338     }
2339
2340   if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
2341     {
2342       coalesce_vars (map, liveinfo);
2343       if (dump_file && (dump_flags & TDF_DETAILS))
2344         {
2345           fprintf (dump_file, "After variable memory coalescing:\n");
2346           dump_var_map (dump_file, map);
2347         }
2348     }
2349
2350   if (liveinfo)
2351     delete_tree_live_info (liveinfo);
2352
2353   rewrite_trees (map, values);
2354
2355   if (values)
2356     free (values);
2357
2358   /* Remove phi nodes which have been translated back to real variables.  */
2359   FOR_EACH_BB (bb)
2360     {
2361       for (phi = phi_nodes (bb); phi; phi = next)
2362         {
2363           next = PHI_CHAIN (phi);
2364           if ((flags & SSANORM_REMOVE_ALL_PHIS)
2365               || var_to_partition (map, PHI_RESULT (phi)) != NO_PARTITION)
2366             remove_phi_node (phi, NULL_TREE, bb);
2367         }
2368     }
2369
2370   /* If any copies were inserted on edges, analyze and insert them now.  */
2371   perform_edge_inserts (dump_file);
2372
2373   dump_file = save;
2374 }
2375
2376 /* Search every PHI node for arguments associated with backedges which
2377    we can trivially determine will need a copy (the argument is either
2378    not an SSA_NAME or the argument has a different underlying variable
2379    than the PHI result).
2380
2381    Insert a copy from the PHI argument to a new destination at the
2382    end of the block with the backedge to the top of the loop.  Update
2383    the PHI argument to reference this new destination.  */
2384
2385 static void
2386 insert_backedge_copies (void)
2387 {
2388   basic_block bb;
2389
2390   FOR_EACH_BB (bb)
2391     {
2392       tree phi;
2393
2394       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2395         {
2396           tree result = PHI_RESULT (phi);
2397           tree result_var;
2398           int i;
2399
2400           if (!is_gimple_reg (result))
2401             continue;
2402
2403           result_var = SSA_NAME_VAR (result);
2404           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2405             {
2406               tree arg = PHI_ARG_DEF (phi, i);
2407               edge e = PHI_ARG_EDGE (phi, i);
2408
2409               /* If the argument is not an SSA_NAME, then we will
2410                  need a constant initialization.  If the argument is
2411                  an SSA_NAME with a different underlying variable and
2412                  we are not combining temporaries, then we will
2413                  need a copy statement.  */
2414               if ((e->flags & EDGE_DFS_BACK)
2415                   && (TREE_CODE (arg) != SSA_NAME
2416                       || (!flag_tree_combine_temps
2417                           && SSA_NAME_VAR (arg) != result_var)))
2418                 {
2419                   tree stmt, name, last = NULL;
2420                   block_stmt_iterator bsi;
2421
2422                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
2423                   if (!bsi_end_p (bsi))
2424                     last = bsi_stmt (bsi);
2425
2426                   /* In theory the only way we ought to get back to the
2427                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
2428                      However, better safe than sorry.
2429
2430                      If the block ends with a control statement or
2431                      something that might throw, then we have to
2432                      insert this assignment before the last
2433                      statement.  Else insert it after the last statement.  */
2434                   if (last && stmt_ends_bb_p (last))
2435                     {
2436                       /* If the last statement in the block is the definition
2437                          site of the PHI argument, then we can't insert
2438                          anything after it.  */
2439                       if (TREE_CODE (arg) == SSA_NAME
2440                           && SSA_NAME_DEF_STMT (arg) == last)
2441                         continue;
2442                     }
2443
2444                   /* Create a new instance of the underlying
2445                      variable of the PHI result.  */
2446                   stmt = build (MODIFY_EXPR, TREE_TYPE (result_var),
2447                                 NULL, PHI_ARG_DEF (phi, i));
2448                   name = make_ssa_name (result_var, stmt);
2449                   TREE_OPERAND (stmt, 0) = name;
2450
2451                   /* Insert the new statement into the block and update
2452                      the PHI node.  */
2453                   if (last && stmt_ends_bb_p (last))
2454                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2455                   else
2456                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2457                   modify_stmt (stmt);
2458                   SET_PHI_ARG_DEF (phi, i, name);
2459                 }
2460             }
2461         }
2462     }
2463 }
2464
2465 /* Take the current function out of SSA form, as described in
2466    R. Morgan, ``Building an Optimizing Compiler'',
2467    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
2468
2469 static void
2470 rewrite_out_of_ssa (void)
2471 {
2472   var_map map;
2473   int var_flags = 0;
2474   int ssa_flags = (SSANORM_REMOVE_ALL_PHIS | SSANORM_USE_COALESCE_LIST);
2475
2476   /* If elimination of a PHI requires inserting a copy on a backedge,
2477      then we will have to split the backedge which has numerous
2478      undesirable performance effects.
2479
2480      A significant number of such cases can be handled here by inserting
2481      copies into the loop itself.  */
2482   insert_backedge_copies ();
2483
2484   if (!flag_tree_live_range_split)
2485     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2486
2487   eliminate_virtual_phis ();
2488
2489   if (dump_file && (dump_flags & TDF_DETAILS))
2490     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2491
2492   /* We cannot allow unssa to un-gimplify trees before we instrument them.  */
2493   if (flag_tree_ter && !flag_mudflap)
2494     var_flags = SSA_VAR_MAP_REF_COUNT;
2495
2496   map = create_ssa_var_map (var_flags);
2497
2498   if (flag_tree_combine_temps)
2499     ssa_flags |= SSANORM_COMBINE_TEMPS;
2500   if (flag_tree_ter && !flag_mudflap)
2501     ssa_flags |= SSANORM_PERFORM_TER;
2502
2503   remove_ssa_form (dump_file, map, ssa_flags);
2504
2505   if (dump_file && (dump_flags & TDF_DETAILS))
2506     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2507
2508   /* Do some cleanups which reduce the amount of data the
2509      tree->rtl expanders deal with.  */
2510   cfg_remove_useless_stmts ();
2511
2512   /* Flush out flow graph and SSA data.  */
2513   delete_var_map (map);
2514
2515   /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE.  */
2516   discover_nonconstant_array_refs ();
2517 }
2518
2519
2520 /* Define the parameters of the out of SSA pass.  */
2521
2522 struct tree_opt_pass pass_del_ssa =
2523 {
2524   "optimized",                          /* name */
2525   NULL,                                 /* gate */
2526   rewrite_out_of_ssa,                   /* execute */
2527   NULL,                                 /* sub */
2528   NULL,                                 /* next */
2529   0,                                    /* static_pass_number */
2530   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
2531   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2532   0,                                    /* properties_provided */
2533   /* ??? If TER is enabled, we also kill gimple.  */
2534   PROP_ssa,                             /* properties_destroyed */
2535   TODO_verify_ssa | TODO_verify_flow
2536     | TODO_verify_stmts,                /* todo_flags_start */
2537   TODO_dump_func | TODO_ggc_collect,    /* todo_flags_finish */
2538   0                                     /* letter */
2539 };