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