gcc/tree-outof-ssa.c

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