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