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_tmp_var (tmp);
 172
 173   /* add_referenced_tmp_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 = BITMAP_ALLOC (NULL), 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   bitmap_set_bit (def_vars, DECL_UID (basevar));
1592
1593   /* Add this expression to the dependency list for each use partition.  */
1594   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1595     {
1596       add_dependence (tab, version, var);
1597
1598       use_vars = tab->expr_vars[SSA_NAME_VERSION (var)];
1599       if (use_vars)
1600         bitmap_ior_into (def_vars, use_vars);
1601     }
1602   tab->expr_vars[version] = def_vars;
1603
1604   /* If there are VUSES, add a dependence on virtual defs.  */
1605   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
1606     {
1607       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
1608                          VIRTUAL_PARTITION (tab));
1609       add_value_to_list (tab,
1610                          &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]),
1611                          version);
1612       bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1613     }
1614
1615   return true;
1616 }
1617
1618
1619 /* This function will remove the expression for VERSION from replacement
1620    consideration.n table TAB  If 'replace' is true, it is marked as
1621    replaceable, otherwise not.  */
1622
1623 static void
1624 finish_expr (temp_expr_table_p tab, int version, bool replace)
1625 {
1626   value_expr_p info, tmp;
1627   int partition;
1628
1629   /* Remove this expression from its dependent lists.  The partition dependence
1630      list is retained and transfered later to whomever uses this version.  */
1631   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1632     {
1633       partition = info->value;
1634       gcc_assert (tab->partition_dep_list[partition]);
1635       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
1636                                     version);
1637       gcc_assert (tmp);
1638       free_value_expr (tab, tmp);
1639       /* Only clear the bit when the dependency list is emptied via
1640          a replacement. Otherwise kill_expr will take care of it.  */
1641       if (!(tab->partition_dep_list[partition]) && replace)
1642         bitmap_clear_bit (tab->partition_in_use, partition);
1643       tmp = info->next;
1644       if (!replace)
1645         free_value_expr (tab, info);
1646     }
1647
1648   if (replace)
1649     {
1650       tab->saw_replaceable = true;
1651       bitmap_set_bit (tab->replaceable, version);
1652     }
1653   else
1654     {
1655       gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1656       tab->version_info[version] = NULL;
1657     }
1658 }
1659
1660
1661 /* Mark the expression associated with VAR as replaceable, and enter
1662    the defining stmt into the version_info table TAB.  */
1663
1664 static void
1665 mark_replaceable (temp_expr_table_p tab, tree var)
1666 {
1667   value_expr_p info;
1668   int version = SSA_NAME_VERSION (var);
1669   finish_expr (tab, version, true);
1670
1671   /* Move the dependence list to the pending list.  */
1672   if (tab->version_info[version])
1673     {
1674       info = (value_expr_p) tab->version_info[version];
1675       for ( ; info->next; info = info->next)
1676         continue;
1677       info->next = tab->pending_dependence;
1678       tab->pending_dependence = (value_expr_p)tab->version_info[version];
1679     }
1680
1681   tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1682 }
1683
1684
1685 /* This function marks any expression in TAB which is dependent on PARTITION
1686    as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
1687    should have its bit cleared.  Since this routine can be called within an
1688    EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
1689
1690 static inline void
1691 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1692 {
1693   value_expr_p ptr;
1694
1695   /* Mark every active expr dependent on this var as not replaceable.  */
1696   while ((ptr = tab->partition_dep_list[partition]) != NULL)
1697     finish_expr (tab, ptr->value, false);
1698
1699   if (clear_bit)
1700     bitmap_clear_bit (tab->partition_in_use, partition);
1701 }
1702
1703
1704 /* This function kills all expressions in TAB which are dependent on virtual
1705    DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
1706
1707 static inline void
1708 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1709 {
1710   kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1711 }
1712
1713
1714 /* This function processes basic block BB, and looks for variables which can
1715    be replaced by their expressions.  Results are stored in TAB.  */
1716
1717 static void
1718 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1719 {
1720   block_stmt_iterator bsi;
1721   tree stmt, def, use;
1722   stmt_ann_t ann;
1723   int partition;
1724   var_map map = tab->map;
1725   value_expr_p p;
1726   ssa_op_iter iter;
1727
1728   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1729     {
1730       stmt = bsi_stmt (bsi);
1731       ann = stmt_ann (stmt);
1732
1733       /* Determine if this stmt finishes an existing expression.  */
1734       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
1735         {
1736           unsigned ver = SSA_NAME_VERSION (use);
1737
1738           if (tab->version_info[ver])
1739             {
1740               bool same_root_var = false;
1741               ssa_op_iter iter2;
1742               bitmap vars = tab->expr_vars[ver];
1743
1744               /* See if the root variables are the same.  If they are, we
1745                  do not want to do the replacement to avoid problems with
1746                  code size, see PR tree-optimization/17549.  */
1747               FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
1748                 {
1749                   if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
1750                     {
1751                       same_root_var = true;
1752                       break;
1753                     }
1754                 }
1755
1756               /* Mark expression as replaceable unless stmt is volatile
1757                  or DEF sets the same root variable as STMT.  */
1758               if (!ann->has_volatile_ops && !same_root_var)
1759                 mark_replaceable (tab, use);
1760               else
1761                 finish_expr (tab, ver, false);
1762             }
1763         }
1764
1765       /* Next, see if this stmt kills off an active expression.  */
1766       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1767         {
1768           partition = var_to_partition (map, def);
1769           if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1770             kill_expr (tab, partition, true);
1771         }
1772
1773       /* Now see if we are creating a new expression or not.  */
1774       if (!ann->has_volatile_ops)
1775         check_replaceable (tab, stmt);
1776
1777       /* Free any unused dependency lists.  */
1778       while ((p = tab->pending_dependence))
1779         {
1780           tab->pending_dependence = p->next;
1781           free_value_expr (tab, p);
1782         }
1783
1784       /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand.  */
1785       if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
1786         kill_virtual_exprs (tab, true);
1787     }
1788 }
1789
1790
1791 /* This function is the driver routine for replacement of temporary expressions
1792    in the SSA->normal phase, operating on MAP.  If there are replaceable
1793    expressions, a table is returned which maps SSA versions to the
1794    expressions they should be replaced with.  A NULL_TREE indicates no
1795    replacement should take place.  If there are no replacements at all,
1796    NULL is returned by the function, otherwise an expression vector indexed
1797    by SSA_NAME version numbers.  */
1798
1799 static tree *
1800 find_replaceable_exprs (var_map map)
1801 {
1802   basic_block bb;
1803   unsigned i;
1804   temp_expr_table_p table;
1805   tree *ret;
1806
1807   table = new_temp_expr_table (map);
1808   FOR_EACH_BB (bb)
1809     {
1810       bitmap_iterator bi;
1811
1812       find_replaceable_in_bb (table, bb);
1813       EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
1814         {
1815           kill_expr (table, i, false);
1816         }
1817     }
1818
1819   ret = free_temp_expr_table (table);
1820   return ret;
1821 }
1822
1823
1824 /* Dump TER expression table EXPR to file F.  */
1825
1826 static void
1827 dump_replaceable_exprs (FILE *f, tree *expr)
1828 {
1829   tree stmt, var;
1830   int x;
1831   fprintf (f, "\nReplacing Expressions\n");
1832   for (x = 0; x < (int)num_ssa_names + 1; x++)
1833     if (expr[x])
1834       {
1835         stmt = expr[x];
1836         var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
1837         gcc_assert (var != NULL_TREE);
1838         print_generic_expr (f, var, TDF_SLIM);
1839         fprintf (f, " replace with --> ");
1840         print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1841         fprintf (f, "\n");
1842       }
1843   fprintf (f, "\n");
1844 }
1845
1846
1847 /* This function will rewrite the current program using the variable mapping
1848    found in MAP.  If the replacement vector VALUES is provided, any
1849    occurrences of partitions with non-null entries in the vector will be
1850    replaced with the expression in the vector instead of its mapped
1851    variable.  */
1852
1853 static void
1854 rewrite_trees (var_map map, tree *values)
1855 {
1856   elim_graph g;
1857   basic_block bb;
1858   block_stmt_iterator si;
1859   edge e;
1860   tree phi;
1861   bool changed;
1862
1863 #ifdef ENABLE_CHECKING
1864   /* Search for PHIs where the destination has no partition, but one
1865      or more arguments has a partition.  This should not happen and can
1866      create incorrect code.  */
1867   FOR_EACH_BB (bb)
1868     {
1869       tree phi;
1870
1871       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1872         {
1873           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1874
1875           if (T0 == NULL_TREE)
1876             {
1877               int i;
1878
1879               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1880                 {
1881                   tree arg = PHI_ARG_DEF (phi, i);
1882
1883                   if (TREE_CODE (arg) == SSA_NAME
1884                       && var_to_partition (map, arg) != NO_PARTITION)
1885                     {
1886                       fprintf (stderr, "Argument of PHI is in a partition :(");
1887                       print_generic_expr (stderr, arg, TDF_SLIM);
1888                       fprintf (stderr, "), but the result is not :");
1889                       print_generic_stmt (stderr, phi, TDF_SLIM);
1890                       internal_error ("SSA corruption");
1891                     }
1892                 }
1893             }
1894         }
1895     }
1896 #endif
1897
1898   /* Replace PHI nodes with any required copies.  */
1899   g = new_elim_graph (map->num_partitions);
1900   g->map = map;
1901   FOR_EACH_BB (bb)
1902     {
1903       for (si = bsi_start (bb); !bsi_end_p (si); )
1904         {
1905           tree stmt = bsi_stmt (si);
1906           use_operand_p use_p, copy_use_p;
1907           def_operand_p def_p;
1908           bool remove = false, is_copy = false;
1909           int num_uses = 0;
1910           stmt_ann_t ann;
1911           ssa_op_iter iter;
1912
1913           ann = stmt_ann (stmt);
1914           changed = false;
1915
1916           if (TREE_CODE (stmt) == MODIFY_EXPR
1917               && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1918             is_copy = true;
1919
1920           copy_use_p = NULL_USE_OPERAND_P;
1921           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1922             {
1923               if (replace_use_variable (map, use_p, values))
1924                 changed = true;
1925               copy_use_p = use_p;
1926               num_uses++;
1927             }
1928
1929           if (num_uses != 1)
1930             is_copy = false;
1931
1932           def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
1933
1934           if (def_p != NULL)
1935             {
1936               /* Mark this stmt for removal if it is the list of replaceable
1937                  expressions.  */
1938               if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
1939                 remove = true;
1940               else
1941                 {
1942                   if (replace_def_variable (map, def_p, NULL))
1943                     changed = true;
1944                   /* If both SSA_NAMEs coalesce to the same variable,
1945                      mark the now redundant copy for removal.  */
1946                   if (is_copy)
1947                     {
1948                       gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
1949                       if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
1950                         remove = true;
1951                     }
1952                 }
1953             }
1954           else
1955             FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1956               if (replace_def_variable (map, def_p, NULL))
1957                 changed = true;
1958
1959           /* Remove any stmts marked for removal.  */
1960           if (remove)
1961             bsi_remove (&si, true);
1962           else
1963             bsi_next (&si);
1964         }
1965
1966       phi = phi_nodes (bb);
1967       if (phi)
1968         {
1969           edge_iterator ei;
1970           FOR_EACH_EDGE (e, ei, bb->preds)
1971             eliminate_phi (e, g);
1972         }
1973     }
1974
1975   delete_elim_graph (g);
1976 }
1977
1978
1979 DEF_VEC_ALLOC_P(edge,heap);
1980
1981 /* These are the local work structures used to determine the best place to
1982    insert the copies that were placed on edges by the SSA->normal pass..  */
1983 static VEC(edge,heap) *edge_leader;
1984 static VEC(tree,heap) *stmt_list;
1985 static bitmap leader_has_match = NULL;
1986 static edge leader_match = NULL;
1987
1988
1989 /* Pass this function to make_forwarder_block so that all the edges with
1990    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
1991 static bool
1992 same_stmt_list_p (edge e)
1993 {
1994   return (e->aux == (PTR) leader_match) ? true : false;
1995 }
1996
1997
1998 /* Return TRUE if S1 and S2 are equivalent copies.  */
1999 static inline bool
2000 identical_copies_p (tree s1, tree s2)
2001 {
2002 #ifdef ENABLE_CHECKING
2003   gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
2004   gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
2005   gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
2006   gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
2007 #endif
2008
2009   if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
2010     return false;
2011
2012   s1 = TREE_OPERAND (s1, 1);
2013   s2 = TREE_OPERAND (s2, 1);
2014
2015   if (s1 != s2)
2016     return false;
2017
2018   return true;
2019 }
2020
2021
2022 /* Compare the PENDING_STMT list for two edges, and return true if the lists
2023    contain the same sequence of copies.  */
2024
2025 static inline bool
2026 identical_stmt_lists_p (edge e1, edge e2)
2027 {
2028   tree t1 = PENDING_STMT (e1);
2029   tree t2 = PENDING_STMT (e2);
2030   tree_stmt_iterator tsi1, tsi2;
2031
2032   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
2033   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
2034
2035   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
2036        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
2037        tsi_next (&tsi1), tsi_next (&tsi2))
2038     {
2039       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
2040         break;
2041     }
2042
2043   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
2044     return false;
2045
2046   return true;
2047 }
2048
2049
2050 /* Allocate data structures used in analyze_edges_for_bb.   */
2051
2052 static void
2053 init_analyze_edges_for_bb (void)
2054 {
2055   edge_leader = VEC_alloc (edge, heap, 25);
2056   stmt_list = VEC_alloc (tree, heap, 25);
2057   leader_has_match = BITMAP_ALLOC (NULL);
2058 }
2059
2060
2061 /* Free data structures used in analyze_edges_for_bb.   */
2062
2063 static void
2064 fini_analyze_edges_for_bb (void)
2065 {
2066   VEC_free (edge, heap, edge_leader);
2067   VEC_free (tree, heap, stmt_list);
2068   BITMAP_FREE (leader_has_match);
2069 }
2070
2071
2072 /* Look at all the incoming edges to block BB, and decide where the best place
2073    to insert the stmts on each edge are, and perform those insertions.  */
2074
2075 static void
2076 analyze_edges_for_bb (basic_block bb)
2077 {
2078   edge e;
2079   edge_iterator ei;
2080   int count;
2081   unsigned int x;
2082   bool have_opportunity;
2083   block_stmt_iterator bsi;
2084   tree stmt;
2085   edge single_edge = NULL;
2086   bool is_label;
2087   edge leader;
2088
2089   count = 0;
2090
2091   /* Blocks which contain at least one abnormal edge cannot use
2092      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
2093      found on edges in these block.  */
2094   have_opportunity = true;
2095   FOR_EACH_EDGE (e, ei, bb->preds)
2096     if (e->flags & EDGE_ABNORMAL)
2097       {
2098         have_opportunity = false;
2099         break;
2100       }
2101
2102   if (!have_opportunity)
2103     {
2104       FOR_EACH_EDGE (e, ei, bb->preds)
2105         if (PENDING_STMT (e))
2106           bsi_commit_one_edge_insert (e, NULL);
2107       return;
2108     }
2109   /* Find out how many edges there are with interesting pending stmts on them.
2110      Commit the stmts on edges we are not interested in.  */
2111   FOR_EACH_EDGE (e, ei, bb->preds)
2112     {
2113       if (PENDING_STMT (e))
2114         {
2115           gcc_assert (!(e->flags & EDGE_ABNORMAL));
2116           if (e->flags & EDGE_FALLTHRU)
2117             {
2118               bsi = bsi_start (e->src);
2119               if (!bsi_end_p (bsi))
2120                 {
2121                   stmt = bsi_stmt (bsi);
2122                   bsi_next (&bsi);
2123                   gcc_assert (stmt != NULL_TREE);
2124                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
2125                   /* Punt if it has non-label stmts, or isn't local.  */
2126                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
2127                       || !bsi_end_p (bsi))
2128                     {
2129                       bsi_commit_one_edge_insert (e, NULL);
2130                       continue;
2131                     }
2132                 }
2133             }
2134           single_edge = e;
2135           count++;
2136         }
2137     }
2138
2139   /* If there aren't at least 2 edges, no sharing will happen.  */
2140   if (count < 2)
2141     {
2142       if (single_edge)
2143         bsi_commit_one_edge_insert (single_edge, NULL);
2144       return;
2145     }
2146
2147   /* Ensure that we have empty worklists.  */
2148 #ifdef ENABLE_CHECKING
2149   gcc_assert (VEC_length (edge, edge_leader) == 0);
2150   gcc_assert (VEC_length (tree, stmt_list) == 0);
2151   gcc_assert (bitmap_empty_p (leader_has_match));
2152 #endif
2153
2154   /* Find the "leader" block for each set of unique stmt lists.  Preference is
2155      given to FALLTHRU blocks since they would need a GOTO to arrive at another
2156      block.  The leader edge destination is the block which all the other edges
2157      with the same stmt list will be redirected to.  */
2158   have_opportunity = false;
2159   FOR_EACH_EDGE (e, ei, bb->preds)
2160     {
2161       if (PENDING_STMT (e))
2162         {
2163           bool found = false;
2164
2165           /* Look for the same stmt list in edge leaders list.  */
2166           for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2167             {
2168               if (identical_stmt_lists_p (leader, e))
2169                 {
2170                   /* Give this edge the same stmt list pointer.  */
2171                   PENDING_STMT (e) = NULL;
2172                   e->aux = leader;
2173                   bitmap_set_bit (leader_has_match, x);
2174                   have_opportunity = found = true;
2175                   break;
2176                 }
2177             }
2178
2179           /* If no similar stmt list, add this edge to the leader list.  */
2180           if (!found)
2181             {
2182               VEC_safe_push (edge, heap, edge_leader, e);
2183               VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
2184             }
2185         }
2186      }
2187
2188   /* If there are no similar lists, just issue the stmts.  */
2189   if (!have_opportunity)
2190     {
2191       for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2192         bsi_commit_one_edge_insert (leader, NULL);
2193       VEC_truncate (edge, edge_leader, 0);
2194       VEC_truncate (tree, stmt_list, 0);
2195       bitmap_clear (leader_has_match);
2196       return;
2197     }
2198
2199
2200   if (dump_file)
2201     fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
2202              bb->index);
2203
2204
2205   /* For each common list, create a forwarding block and issue the stmt's
2206      in that block.  */
2207   for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2208     if (bitmap_bit_p (leader_has_match, x))
2209       {
2210         edge new_edge;
2211         block_stmt_iterator bsi;
2212         tree curr_stmt_list;
2213
2214         leader_match = leader;
2215
2216         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
2217            for various PHI manipulations, so it gets cleared whhen calls are
2218            made to make_forwarder_block(). So make sure the edge is clear,
2219            and use the saved stmt list.  */
2220         PENDING_STMT (leader) = NULL;
2221         leader->aux = leader;
2222         curr_stmt_list = VEC_index (tree, stmt_list, x);
2223
2224         new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
2225                                          NULL);
2226         bb = new_edge->dest;
2227         if (dump_file)
2228           {
2229             fprintf (dump_file, "Splitting BB %d for Common stmt list.  ",
2230                      leader->dest->index);
2231             fprintf (dump_file, "Original block is now BB%d.\n", bb->index);
2232             print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS);
2233           }
2234
2235         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
2236           {
2237             e->aux = NULL;
2238             if (dump_file)
2239               fprintf (dump_file, "  Edge (%d->%d) lands here.\n",
2240                        e->src->index, e->dest->index);
2241           }
2242
2243         bsi = bsi_last (leader->dest);
2244         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
2245
2246         leader_match = NULL;
2247         /* We should never get a new block now.  */
2248       }
2249     else
2250       {
2251         PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
2252         bsi_commit_one_edge_insert (leader, NULL);
2253       }
2254
2255
2256   /* Clear the working data structures.  */
2257   VEC_truncate (edge, edge_leader, 0);
2258   VEC_truncate (tree, stmt_list, 0);
2259   bitmap_clear (leader_has_match);
2260 }
2261
2262
2263 /* This function will analyze the insertions which were performed on edges,
2264    and decide whether they should be left on that edge, or whether it is more
2265    efficient to emit some subset of them in a single block.  All stmts are
2266    inserted somewhere.  */
2267
2268 static void
2269 perform_edge_inserts (void)
2270 {
2271   basic_block bb;
2272
2273   if (dump_file)
2274     fprintf(dump_file, "Analyzing Edge Insertions.\n");
2275
2276   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
2277      incrementally update the dominator information.  Since we don't
2278      need dominator information after this pass, go ahead and free the
2279      dominator information.  */
2280   free_dominance_info (CDI_DOMINATORS);
2281   free_dominance_info (CDI_POST_DOMINATORS);
2282
2283   /* Allocate data structures used in analyze_edges_for_bb.   */
2284   init_analyze_edges_for_bb ();
2285
2286   FOR_EACH_BB (bb)
2287     analyze_edges_for_bb (bb);
2288
2289   analyze_edges_for_bb (EXIT_BLOCK_PTR);
2290
2291   /* Free data structures used in analyze_edges_for_bb.   */
2292   fini_analyze_edges_for_bb ();
2293
2294 #ifdef ENABLE_CHECKING
2295   {
2296     edge_iterator ei;
2297     edge e;
2298     FOR_EACH_BB (bb)
2299       {
2300         FOR_EACH_EDGE (e, ei, bb->preds)
2301           {
2302             if (PENDING_STMT (e))
2303               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
2304                      e->src->index, e->dest->index);
2305           }
2306         FOR_EACH_EDGE (e, ei, bb->succs)
2307           {
2308             if (PENDING_STMT (e))
2309               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
2310                      e->src->index, e->dest->index);
2311           }
2312       }
2313     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2314       {
2315         if (PENDING_STMT (e))
2316           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
2317                  e->src->index, e->dest->index);
2318       }
2319     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
2320       {
2321         if (PENDING_STMT (e))
2322           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
2323                  e->src->index, e->dest->index);
2324       }
2325   }
2326 #endif
2327 }
2328
2329
2330 /* Remove the variables specified in MAP from SSA form.  FLAGS indicate what
2331    options should be used.  */
2332
2333 static void
2334 remove_ssa_form (var_map map, int flags)
2335 {
2336   tree_live_info_p liveinfo;
2337   basic_block bb;
2338   tree phi, next;
2339   tree *values = NULL;
2340
2341   /* If we are not combining temps, don't calculate live ranges for variables
2342      with only one SSA version.  */
2343   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2344     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
2345   else
2346     compact_var_map (map, VARMAP_NORMAL);
2347
2348   if (dump_file && (dump_flags & TDF_DETAILS))
2349     dump_var_map (dump_file, map);
2350
2351   liveinfo = coalesce_ssa_name (map, flags);
2352
2353   /* Make sure even single occurrence variables are in the list now.  */
2354   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2355     compact_var_map (map, VARMAP_NORMAL);
2356
2357   if (dump_file && (dump_flags & TDF_DETAILS))
2358     {
2359       fprintf (dump_file, "After Coalescing:\n");
2360       dump_var_map (dump_file, map);
2361     }
2362
2363   if (flags & SSANORM_PERFORM_TER)
2364     {
2365       values = find_replaceable_exprs (map);
2366       if (values && dump_file && (dump_flags & TDF_DETAILS))
2367         dump_replaceable_exprs (dump_file, values);
2368     }
2369
2370   /* Assign real variables to the partitions now.  */
2371   assign_vars (map);
2372
2373   if (dump_file && (dump_flags & TDF_DETAILS))
2374     {
2375       fprintf (dump_file, "After Root variable replacement:\n");
2376       dump_var_map (dump_file, map);
2377     }
2378
2379   if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
2380     {
2381       coalesce_vars (map, liveinfo);
2382       if (dump_file && (dump_flags & TDF_DETAILS))
2383         {
2384           fprintf (dump_file, "After variable memory coalescing:\n");
2385           dump_var_map (dump_file, map);
2386         }
2387     }
2388
2389   if (liveinfo)
2390     delete_tree_live_info (liveinfo);
2391
2392   rewrite_trees (map, values);
2393
2394   if (values)
2395     free (values);
2396
2397   /* Remove phi nodes which have been translated back to real variables.  */
2398   FOR_EACH_BB (bb)
2399     {
2400       for (phi = phi_nodes (bb); phi; phi = next)
2401         {
2402           next = PHI_CHAIN (phi);
2403           remove_phi_node (phi, NULL_TREE);
2404         }
2405     }
2406
2407   /* we no longer maintain the SSA operand cache at this point.  */
2408   fini_ssa_operands ();
2409
2410   /* If any copies were inserted on edges, analyze and insert them now.  */
2411   perform_edge_inserts ();
2412 }
2413
2414 /* Search every PHI node for arguments associated with backedges which
2415    we can trivially determine will need a copy (the argument is either
2416    not an SSA_NAME or the argument has a different underlying variable
2417    than the PHI result).
2418
2419    Insert a copy from the PHI argument to a new destination at the
2420    end of the block with the backedge to the top of the loop.  Update
2421    the PHI argument to reference this new destination.  */
2422
2423 static void
2424 insert_backedge_copies (void)
2425 {
2426   basic_block bb;
2427
2428   FOR_EACH_BB (bb)
2429     {
2430       tree phi;
2431
2432       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2433         {
2434           tree result = PHI_RESULT (phi);
2435           tree result_var;
2436           int i;
2437
2438           if (!is_gimple_reg (result))
2439             continue;
2440
2441           result_var = SSA_NAME_VAR (result);
2442           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2443             {
2444               tree arg = PHI_ARG_DEF (phi, i);
2445               edge e = PHI_ARG_EDGE (phi, i);
2446
2447               /* If the argument is not an SSA_NAME, then we will
2448                  need a constant initialization.  If the argument is
2449                  an SSA_NAME with a different underlying variable and
2450                  we are not combining temporaries, then we will
2451                  need a copy statement.  */
2452               if ((e->flags & EDGE_DFS_BACK)
2453                   && (TREE_CODE (arg) != SSA_NAME
2454                       || (!flag_tree_combine_temps
2455                           && SSA_NAME_VAR (arg) != result_var)))
2456                 {
2457                   tree stmt, name, last = NULL;
2458                   block_stmt_iterator bsi;
2459
2460                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
2461                   if (!bsi_end_p (bsi))
2462                     last = bsi_stmt (bsi);
2463
2464                   /* In theory the only way we ought to get back to the
2465                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
2466                      However, better safe than sorry.
2467
2468                      If the block ends with a control statement or
2469                      something that might throw, then we have to
2470                      insert this assignment before the last
2471                      statement.  Else insert it after the last statement.  */
2472                   if (last && stmt_ends_bb_p (last))
2473                     {
2474                       /* If the last statement in the block is the definition
2475                          site of the PHI argument, then we can't insert
2476                          anything after it.  */
2477                       if (TREE_CODE (arg) == SSA_NAME
2478                           && SSA_NAME_DEF_STMT (arg) == last)
2479                         continue;
2480                     }
2481
2482                   /* Create a new instance of the underlying
2483                      variable of the PHI result.  */
2484                   stmt = build2 (MODIFY_EXPR, TREE_TYPE (result_var),
2485                                  NULL_TREE, PHI_ARG_DEF (phi, i));
2486                   name = make_ssa_name (result_var, stmt);
2487                   TREE_OPERAND (stmt, 0) = name;
2488
2489                   /* Insert the new statement into the block and update
2490                      the PHI node.  */
2491                   if (last && stmt_ends_bb_p (last))
2492                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2493                   else
2494                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2495                   SET_PHI_ARG_DEF (phi, i, name);
2496                 }
2497             }
2498         }
2499     }
2500 }
2501
2502 /* Take the current function out of SSA form, as described in
2503    R. Morgan, ``Building an Optimizing Compiler'',
2504    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
2505
2506 static unsigned int
2507 rewrite_out_of_ssa (void)
2508 {
2509   var_map map;
2510   int var_flags = 0;
2511   int ssa_flags = 0;
2512
2513   /* If elimination of a PHI requires inserting a copy on a backedge,
2514      then we will have to split the backedge which has numerous
2515      undesirable performance effects.
2516
2517      A significant number of such cases can be handled here by inserting
2518      copies into the loop itself.  */
2519   insert_backedge_copies ();
2520
2521   if (!flag_tree_live_range_split)
2522     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2523
2524   eliminate_virtual_phis ();
2525
2526   if (dump_file && (dump_flags & TDF_DETAILS))
2527     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2528
2529   /* We cannot allow unssa to un-gimplify trees before we instrument them.  */
2530   if (flag_tree_ter && !flag_mudflap)
2531     var_flags = SSA_VAR_MAP_REF_COUNT;
2532
2533   map = create_ssa_var_map (var_flags);
2534
2535   if (flag_tree_combine_temps)
2536     ssa_flags |= SSANORM_COMBINE_TEMPS;
2537   if (flag_tree_ter && !flag_mudflap)
2538     ssa_flags |= SSANORM_PERFORM_TER;
2539
2540   remove_ssa_form (map, ssa_flags);
2541
2542   if (dump_file && (dump_flags & TDF_DETAILS))
2543     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2544
2545   /* Flush out flow graph and SSA data.  */
2546   delete_var_map (map);
2547
2548   in_ssa_p = false;
2549   return 0;
2550 }
2551
2552
2553 /* Define the parameters of the out of SSA pass.  */
2554
2555 struct tree_opt_pass pass_del_ssa =
2556 {
2557   "optimized",                          /* name */
2558   NULL,                                 /* gate */
2559   rewrite_out_of_ssa,                   /* execute */
2560   NULL,                                 /* sub */
2561   NULL,                                 /* next */
2562   0,                                    /* static_pass_number */
2563   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
2564   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2565   0,                                    /* properties_provided */
2566   /* ??? If TER is enabled, we also kill gimple.  */
2567   PROP_ssa,                             /* properties_destroyed */
2568   TODO_verify_ssa | TODO_verify_flow
2569     | TODO_verify_stmts,                /* todo_flags_start */
2570   TODO_dump_func
2571   | TODO_ggc_collect
2572   | TODO_remove_unused_locals,          /* todo_flags_finish */
2573   0                                     /* letter */
2574 };