gcc/tree-outof-ssa.c

   1 /* Convert a program in SSA form into Normal form.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4    Contributed by Andrew Macleod <amacleod@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "ggc.h"
  28 #include "basic-block.h"
  29 #include "diagnostic.h"
  30 #include "tree-pretty-print.h"
  31 #include "gimple-pretty-print.h"
  32 #include "bitmap.h"
  33 #include "tree-flow.h"
  34 #include "timevar.h"
  35 #include "tree-dump.h"
  36 #include "tree-pass.h"
  37 #include "toplev.h"
  38 #include "expr.h"
  39 #include "ssaexpand.h"
  40
  41
  42 DEF_VEC_I(source_location);
  43 DEF_VEC_ALLOC_I(source_location,heap);
  44
  45 /* Used to hold all the components required to do SSA PHI elimination.
  46    The node and pred/succ list is a simple linear list of nodes and
  47    edges represented as pairs of nodes.
  48
  49    The predecessor and successor list:  Nodes are entered in pairs, where
  50    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
  51    predecessors, all the odd elements are successors.
  52
  53    Rationale:
  54    When implemented as bitmaps, very large programs SSA->Normal times were
  55    being dominated by clearing the interference graph.
  56
  57    Typically this list of edges is extremely small since it only includes
  58    PHI results and uses from a single edge which have not coalesced with
  59    each other.  This means that no virtual PHI nodes are included, and
  60    empirical evidence suggests that the number of edges rarely exceed
  61    3, and in a bootstrap of GCC, the maximum size encountered was 7.
  62    This also limits the number of possible nodes that are involved to
  63    rarely more than 6, and in the bootstrap of gcc, the maximum number
  64    of nodes encountered was 12.  */
  65
  66 typedef struct _elim_graph {
  67   /* Size of the elimination vectors.  */
  68   int size;
  69
  70   /* List of nodes in the elimination graph.  */
  71   VEC(int,heap) *nodes;
  72
  73   /*  The predecessor and successor edge list.  */
  74   VEC(int,heap) *edge_list;
  75
  76   /* Source locus on each edge */
  77   VEC(source_location,heap) *edge_locus;
  78
  79   /* Visited vector.  */
  80   sbitmap visited;
  81
  82   /* Stack for visited nodes.  */
  83   VEC(int,heap) *stack;
  84
  85   /* The variable partition map.  */
  86   var_map map;
  87
  88   /* Edge being eliminated by this graph.  */
  89   edge e;
  90
  91   /* List of constant copies to emit.  These are pushed on in pairs.  */
  92   VEC(int,heap) *const_dests;
  93   VEC(tree,heap) *const_copies;
  94
  95   /* Source locations for any constant copies.  */
  96   VEC(source_location,heap) *copy_locus;
  97 } *elim_graph;
  98
  99
 100 /* For an edge E find out a good source location to associate with
 101    instructions inserted on edge E.  If E has an implicit goto set,
 102    use its location.  Otherwise search instructions in predecessors
 103    of E for a location, and use that one.  That makes sense because
 104    we insert on edges for PHI nodes, and effects of PHIs happen on
 105    the end of the predecessor conceptually.  */
 106
 107 static void
 108 set_location_for_edge (edge e)
 109 {
 110   if (e->goto_locus)
 111     {
 112       set_curr_insn_source_location (e->goto_locus);
 113       set_curr_insn_block (e->goto_block);
 114     }
 115   else
 116     {
 117       basic_block bb = e->src;
 118       gimple_stmt_iterator gsi;
 119
 120       do
 121         {
 122           for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
 123             {
 124               gimple stmt = gsi_stmt (gsi);
 125               if (is_gimple_debug (stmt))
 126                 continue;
 127               if (gimple_has_location (stmt) || gimple_block (stmt))
 128                 {
 129                   set_curr_insn_source_location (gimple_location (stmt));
 130                   set_curr_insn_block (gimple_block (stmt));
 131                   return;
 132                 }
 133             }
 134           /* Nothing found in this basic block.  Make a half-assed attempt
 135              to continue with another block.  */
 136           if (single_pred_p (bb))
 137             bb = single_pred (bb);
 138           else
 139             bb = e->src;
 140         }
 141       while (bb != e->src);
 142     }
 143 }
 144
 145 /* Emit insns to copy SRC into DEST converting SRC if necessary.  As
 146    SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
 147    which we deduce the size to copy in that case.  */
 148
 149 static inline rtx
 150 emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
 151 {
 152   rtx seq;
 153
 154   start_sequence ();
 155
 156   if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
 157     src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
 158   if (GET_MODE (src) == BLKmode)
 159     {
 160       gcc_assert (GET_MODE (dest) == BLKmode);
 161       emit_block_move (dest, src, expr_size (sizeexp), BLOCK_OP_NORMAL);
 162     }
 163   else
 164     emit_move_insn (dest, src);
 165
 166   seq = get_insns ();
 167   end_sequence ();
 168
 169   return seq;
 170 }
 171
 172 /* Insert a copy instruction from partition SRC to DEST onto edge E.  */
 173
 174 static void
 175 insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus)
 176 {
 177   tree var;
 178   rtx seq;
 179   if (dump_file && (dump_flags & TDF_DETAILS))
 180     {
 181       fprintf (dump_file,
 182                "Inserting a partition copy on edge BB%d->BB%d :"
 183                "PART.%d = PART.%d",
 184                e->src->index,
 185                e->dest->index, dest, src);
 186       fprintf (dump_file, "\n");
 187     }
 188
 189   gcc_assert (SA.partition_to_pseudo[dest]);
 190   gcc_assert (SA.partition_to_pseudo[src]);
 191
 192   set_location_for_edge (e);
 193   /* If a locus is provided, override the default.  */
 194   if (locus)
 195     set_curr_insn_source_location (locus);
 196
 197   var = partition_to_var (SA.map, src);
 198   seq = emit_partition_copy (SA.partition_to_pseudo[dest],
 199                              SA.partition_to_pseudo[src],
 200                              TYPE_UNSIGNED (TREE_TYPE (var)),
 201                              var);
 202
 203   insert_insn_on_edge (seq, e);
 204 }
 205
 206 /* Insert a copy instruction from expression SRC to partition DEST
 207    onto edge E.  */
 208
 209 static void
 210 insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus)
 211 {
 212   rtx seq, x;
 213   enum machine_mode dest_mode, src_mode;
 214   int unsignedp;
 215   tree var;
 216
 217   if (dump_file && (dump_flags & TDF_DETAILS))
 218     {
 219       fprintf (dump_file,
 220                "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
 221                e->src->index,
 222                e->dest->index, dest);
 223       print_generic_expr (dump_file, src, TDF_SLIM);
 224       fprintf (dump_file, "\n");
 225     }
 226
 227   gcc_assert (SA.partition_to_pseudo[dest]);
 228
 229   set_location_for_edge (e);
 230   /* If a locus is provided, override the default.  */
 231   if (locus)
 232     set_curr_insn_source_location (locus);
 233
 234   start_sequence ();
 235
 236   var = SSA_NAME_VAR (partition_to_var (SA.map, dest));
 237   src_mode = TYPE_MODE (TREE_TYPE (src));
 238   dest_mode = promote_decl_mode (var, &unsignedp);
 239   gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (var)));
 240   gcc_assert (dest_mode == GET_MODE (SA.partition_to_pseudo[dest]));
 241
 242   if (src_mode != dest_mode)
 243     {
 244       x = expand_expr (src, NULL, src_mode, EXPAND_NORMAL);
 245       x = convert_modes (dest_mode, src_mode, x, unsignedp);
 246     }
 247   else if (src_mode == BLKmode)
 248     {
 249       x = SA.partition_to_pseudo[dest];
 250       store_expr (src, x, 0, false);
 251     }
 252   else
 253     x = expand_expr (src, SA.partition_to_pseudo[dest],
 254                      dest_mode, EXPAND_NORMAL);
 255
 256   if (x != SA.partition_to_pseudo[dest])
 257     emit_move_insn (SA.partition_to_pseudo[dest], x);
 258   seq = get_insns ();
 259   end_sequence ();
 260
 261   insert_insn_on_edge (seq, e);
 262 }
 263
 264 /* Insert a copy instruction from RTL expression SRC to partition DEST
 265    onto edge E.  */
 266
 267 static void
 268 insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
 269                             source_location locus)
 270 {
 271   rtx seq;
 272   if (dump_file && (dump_flags & TDF_DETAILS))
 273     {
 274       fprintf (dump_file,
 275                "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
 276                e->src->index,
 277                e->dest->index, dest);
 278       print_simple_rtl (dump_file, src);
 279       fprintf (dump_file, "\n");
 280     }
 281
 282   gcc_assert (SA.partition_to_pseudo[dest]);
 283
 284   set_location_for_edge (e);
 285   /* If a locus is provided, override the default.  */
 286   if (locus)
 287     set_curr_insn_source_location (locus);
 288
 289   /* We give the destination as sizeexp in case src/dest are BLKmode
 290      mems.  Usually we give the source.  As we result from SSA names
 291      the left and right size should be the same (and no WITH_SIZE_EXPR
 292      involved), so it doesn't matter.  */
 293   seq = emit_partition_copy (SA.partition_to_pseudo[dest],
 294                              src, unsignedsrcp,
 295                              partition_to_var (SA.map, dest));
 296
 297   insert_insn_on_edge (seq, e);
 298 }
 299
 300 /* Insert a copy instruction from partition SRC to RTL lvalue DEST
 301    onto edge E.  */
 302
 303 static void
 304 insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus)
 305 {
 306   tree var;
 307   rtx seq;
 308   if (dump_file && (dump_flags & TDF_DETAILS))
 309     {
 310       fprintf (dump_file,
 311                "Inserting a temp copy on edge BB%d->BB%d : ",
 312                e->src->index,
 313                e->dest->index);
 314       print_simple_rtl (dump_file, dest);
 315       fprintf (dump_file, "= PART.%d\n", src);
 316     }
 317
 318   gcc_assert (SA.partition_to_pseudo[src]);
 319
 320   set_location_for_edge (e);
 321   /* If a locus is provided, override the default.  */
 322   if (locus)
 323     set_curr_insn_source_location (locus);
 324
 325   var = partition_to_var (SA.map, src);
 326   seq = emit_partition_copy (dest,
 327                              SA.partition_to_pseudo[src],
 328                              TYPE_UNSIGNED (TREE_TYPE (var)),
 329                              var);
 330
 331   insert_insn_on_edge (seq, e);
 332 }
 333
 334
 335 /* Create an elimination graph with SIZE nodes and associated data
 336    structures.  */
 337
 338 static elim_graph
 339 new_elim_graph (int size)
 340 {
 341   elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
 342
 343   g->nodes = VEC_alloc (int, heap, 30);
 344   g->const_dests = VEC_alloc (int, heap, 20);
 345   g->const_copies = VEC_alloc (tree, heap, 20);
 346   g->copy_locus = VEC_alloc (source_location, heap, 10);
 347   g->edge_list = VEC_alloc (int, heap, 20);
 348   g->edge_locus = VEC_alloc (source_location, heap, 10);
 349   g->stack = VEC_alloc (int, heap, 30);
 350
 351   g->visited = sbitmap_alloc (size);
 352
 353   return g;
 354 }
 355
 356
 357 /* Empty elimination graph G.  */
 358
 359 static inline void
 360 clear_elim_graph (elim_graph g)
 361 {
 362   VEC_truncate (int, g->nodes, 0);
 363   VEC_truncate (int, g->edge_list, 0);
 364   VEC_truncate (source_location, g->edge_locus, 0);
 365 }
 366
 367
 368 /* Delete elimination graph G.  */
 369
 370 static inline void
 371 delete_elim_graph (elim_graph g)
 372 {
 373   sbitmap_free (g->visited);
 374   VEC_free (int, heap, g->stack);
 375   VEC_free (int, heap, g->edge_list);
 376   VEC_free (tree, heap, g->const_copies);
 377   VEC_free (int, heap, g->const_dests);
 378   VEC_free (int, heap, g->nodes);
 379   VEC_free (source_location, heap, g->copy_locus);
 380   VEC_free (source_location, heap, g->edge_locus);
 381
 382   free (g);
 383 }
 384
 385
 386 /* Return the number of nodes in graph G.  */
 387
 388 static inline int
 389 elim_graph_size (elim_graph g)
 390 {
 391   return VEC_length (int, g->nodes);
 392 }
 393
 394
 395 /* Add NODE to graph G, if it doesn't exist already.  */
 396
 397 static inline void
 398 elim_graph_add_node (elim_graph g, int node)
 399 {
 400   int x;
 401   int t;
 402
 403   for (x = 0; VEC_iterate (int, g->nodes, x, t); x++)
 404     if (t == node)
 405       return;
 406   VEC_safe_push (int, heap, g->nodes, node);
 407 }
 408
 409
 410 /* Add the edge PRED->SUCC to graph G.  */
 411
 412 static inline void
 413 elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus)
 414 {
 415   VEC_safe_push (int, heap, g->edge_list, pred);
 416   VEC_safe_push (int, heap, g->edge_list, succ);
 417   VEC_safe_push (source_location, heap, g->edge_locus, locus);
 418 }
 419
 420
 421 /* Remove an edge from graph G for which NODE is the predecessor, and
 422    return the successor node.  -1 is returned if there is no such edge.  */
 423
 424 static inline int
 425 elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus)
 426 {
 427   int y;
 428   unsigned x;
 429   for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
 430     if (VEC_index (int, g->edge_list, x) == node)
 431       {
 432         VEC_replace (int, g->edge_list, x, -1);
 433         y = VEC_index (int, g->edge_list, x + 1);
 434         VEC_replace (int, g->edge_list, x + 1, -1);
 435         *locus = VEC_index (source_location, g->edge_locus, x / 2);
 436         VEC_replace (source_location, g->edge_locus, x / 2, UNKNOWN_LOCATION);
 437         return y;
 438       }
 439   *locus = UNKNOWN_LOCATION;
 440   return -1;
 441 }
 442
 443
 444 /* Find all the nodes in GRAPH which are successors to NODE in the
 445    edge list.  VAR will hold the partition number found.  CODE is the
 446    code fragment executed for every node found.  */
 447
 448 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE)         \
 449 do {                                                                    \
 450   unsigned x_;                                                          \
 451   int y_;                                                               \
 452   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
 453     {                                                                   \
 454       y_ = VEC_index (int, (GRAPH)->edge_list, x_);                     \
 455       if (y_ != (NODE))                                                 \
 456         continue;                                                       \
 457       (void) ((VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1));     \
 458       (void) ((LOCUS) = VEC_index (source_location,                     \
 459                                    (GRAPH)->edge_locus, x_ / 2));       \
 460       CODE;                                                             \
 461     }                                                                   \
 462 } while (0)
 463
 464
 465 /* Find all the nodes which are predecessors of NODE in the edge list for
 466    GRAPH.  VAR will hold the partition number found.  CODE is the
 467    code fragment executed for every node found.  */
 468
 469 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE)         \
 470 do {                                                                    \
 471   unsigned x_;                                                          \
 472   int y_;                                                               \
 473   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
 474     {                                                                   \
 475       y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1);                 \
 476       if (y_ != (NODE))                                                 \
 477         continue;                                                       \
 478       (void) ((VAR) = VEC_index (int, (GRAPH)->edge_list, x_));         \
 479       (void) ((LOCUS) = VEC_index (source_location,                     \
 480                                    (GRAPH)->edge_locus, x_ / 2));       \
 481       CODE;                                                             \
 482     }                                                                   \
 483 } while (0)
 484
 485
 486 /* Add T to elimination graph G.  */
 487
 488 static inline void
 489 eliminate_name (elim_graph g, int T)
 490 {
 491   elim_graph_add_node (g, T);
 492 }
 493
 494
 495 /* Build elimination graph G for basic block BB on incoming PHI edge
 496    G->e.  */
 497
 498 static void
 499 eliminate_build (elim_graph g)
 500 {
 501   tree Ti;
 502   int p0, pi;
 503   gimple_stmt_iterator gsi;
 504
 505   clear_elim_graph (g);
 506
 507   for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
 508     {
 509       gimple phi = gsi_stmt (gsi);
 510       source_location locus;
 511
 512       p0 = var_to_partition (g->map, gimple_phi_result (phi));
 513       /* Ignore results which are not in partitions.  */
 514       if (p0 == NO_PARTITION)
 515         continue;
 516
 517       Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
 518       locus = gimple_phi_arg_location_from_edge (phi, g->e);
 519
 520       /* If this argument is a constant, or a SSA_NAME which is being
 521          left in SSA form, just queue a copy to be emitted on this
 522          edge.  */
 523       if (!phi_ssa_name_p (Ti)
 524           || (TREE_CODE (Ti) == SSA_NAME
 525               && var_to_partition (g->map, Ti) == NO_PARTITION))
 526         {
 527           /* Save constant copies until all other copies have been emitted
 528              on this edge.  */
 529           VEC_safe_push (int, heap, g->const_dests, p0);
 530           VEC_safe_push (tree, heap, g->const_copies, Ti);
 531           VEC_safe_push (source_location, heap, g->copy_locus, locus);
 532         }
 533       else
 534         {
 535           pi = var_to_partition (g->map, Ti);
 536           if (p0 != pi)
 537             {
 538               eliminate_name (g, p0);
 539               eliminate_name (g, pi);
 540               elim_graph_add_edge (g, p0, pi, locus);
 541             }
 542         }
 543     }
 544 }
 545
 546
 547 /* Push successors of T onto the elimination stack for G.  */
 548
 549 static void
 550 elim_forward (elim_graph g, int T)
 551 {
 552   int S;
 553   source_location locus;
 554
 555   SET_BIT (g->visited, T);
 556   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus,
 557     {
 558       if (!TEST_BIT (g->visited, S))
 559         elim_forward (g, S);
 560     });
 561   VEC_safe_push (int, heap, g->stack, T);
 562 }
 563
 564
 565 /* Return 1 if there unvisited predecessors of T in graph G.  */
 566
 567 static int
 568 elim_unvisited_predecessor (elim_graph g, int T)
 569 {
 570   int P;
 571   source_location locus;
 572
 573   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
 574     {
 575       if (!TEST_BIT (g->visited, P))
 576         return 1;
 577     });
 578   return 0;
 579 }
 580
 581 /* Process predecessors first, and insert a copy.  */
 582
 583 static void
 584 elim_backward (elim_graph g, int T)
 585 {
 586   int P;
 587   source_location locus;
 588
 589   SET_BIT (g->visited, T);
 590   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
 591     {
 592       if (!TEST_BIT (g->visited, P))
 593         {
 594           elim_backward (g, P);
 595           insert_partition_copy_on_edge (g->e, P, T, locus);
 596         }
 597     });
 598 }
 599
 600 /* Allocate a new pseudo register usable for storing values sitting
 601    in NAME (a decl or SSA name), i.e. with matching mode and attributes.  */
 602
 603 static rtx
 604 get_temp_reg (tree name)
 605 {
 606   tree var = TREE_CODE (name) == SSA_NAME ? SSA_NAME_VAR (name) : name;
 607   tree type = TREE_TYPE (var);
 608   int unsignedp;
 609   enum machine_mode reg_mode = promote_decl_mode (var, &unsignedp);
 610   rtx x = gen_reg_rtx (reg_mode);
 611   if (POINTER_TYPE_P (type))
 612     mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var))));
 613   return x;
 614 }
 615
 616 /* Insert required copies for T in graph G.  Check for a strongly connected
 617    region, and create a temporary to break the cycle if one is found.  */
 618
 619 static void
 620 elim_create (elim_graph g, int T)
 621 {
 622   int P, S;
 623   source_location locus;
 624
 625   if (elim_unvisited_predecessor (g, T))
 626     {
 627       tree var = partition_to_var (g->map, T);
 628       rtx U = get_temp_reg (var);
 629       int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
 630
 631       insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
 632       FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
 633         {
 634           if (!TEST_BIT (g->visited, P))
 635             {
 636               elim_backward (g, P);
 637               insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
 638             }
 639         });
 640     }
 641   else
 642     {
 643       S = elim_graph_remove_succ_edge (g, T, &locus);
 644       if (S != -1)
 645         {
 646           SET_BIT (g->visited, T);
 647           insert_partition_copy_on_edge (g->e, T, S, locus);
 648         }
 649     }
 650 }
 651
 652
 653 /* Eliminate all the phi nodes on edge E in graph G.  */
 654
 655 static void
 656 eliminate_phi (edge e, elim_graph g)
 657 {
 658   int x;
 659
 660   gcc_assert (VEC_length (tree, g->const_copies) == 0);
 661   gcc_assert (VEC_length (source_location, g->copy_locus) == 0);
 662
 663   /* Abnormal edges already have everything coalesced.  */
 664   if (e->flags & EDGE_ABNORMAL)
 665     return;
 666
 667   g->e = e;
 668
 669   eliminate_build (g);
 670
 671   if (elim_graph_size (g) != 0)
 672     {
 673       int part;
 674
 675       sbitmap_zero (g->visited);
 676       VEC_truncate (int, g->stack, 0);
 677
 678       for (x = 0; VEC_iterate (int, g->nodes, x, part); x++)
 679         {
 680           if (!TEST_BIT (g->visited, part))
 681             elim_forward (g, part);
 682         }
 683
 684       sbitmap_zero (g->visited);
 685       while (VEC_length (int, g->stack) > 0)
 686         {
 687           x = VEC_pop (int, g->stack);
 688           if (!TEST_BIT (g->visited, x))
 689             elim_create (g, x);
 690         }
 691     }
 692
 693   /* If there are any pending constant copies, issue them now.  */
 694   while (VEC_length (tree, g->const_copies) > 0)
 695     {
 696       int dest;
 697       tree src;
 698       source_location locus;
 699
 700       src = VEC_pop (tree, g->const_copies);
 701       dest = VEC_pop (int, g->const_dests);
 702       locus = VEC_pop (source_location, g->copy_locus);
 703       insert_value_copy_on_edge (e, dest, src, locus);
 704     }
 705 }
 706
 707
 708 /* Remove each argument from PHI.  If an arg was the last use of an SSA_NAME,
 709    check to see if this allows another PHI node to be removed.  */
 710
 711 static void
 712 remove_gimple_phi_args (gimple phi)
 713 {
 714   use_operand_p arg_p;
 715   ssa_op_iter iter;
 716
 717   if (dump_file && (dump_flags & TDF_DETAILS))
 718     {
 719       fprintf (dump_file, "Removing Dead PHI definition: ");
 720       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
 721     }
 722
 723   FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
 724     {
 725       tree arg = USE_FROM_PTR (arg_p);
 726       if (TREE_CODE (arg) == SSA_NAME)
 727         {
 728           /* Remove the reference to the existing argument.  */
 729           SET_USE (arg_p, NULL_TREE);
 730           if (has_zero_uses (arg))
 731             {
 732               gimple stmt;
 733               gimple_stmt_iterator gsi;
 734
 735               stmt = SSA_NAME_DEF_STMT (arg);
 736
 737               /* Also remove the def if it is a PHI node.  */
 738               if (gimple_code (stmt) == GIMPLE_PHI)
 739                 {
 740                   remove_gimple_phi_args (stmt);
 741                   gsi = gsi_for_stmt (stmt);
 742                   remove_phi_node (&gsi, true);
 743                 }
 744
 745             }
 746         }
 747     }
 748 }
 749
 750 /* Remove any PHI node which is a virtual PHI, or a PHI with no uses.  */
 751
 752 static void
 753 eliminate_useless_phis (void)
 754 {
 755   basic_block bb;
 756   gimple_stmt_iterator gsi;
 757   tree result;
 758
 759   FOR_EACH_BB (bb)
 760     {
 761       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
 762         {
 763           gimple phi = gsi_stmt (gsi);
 764           result = gimple_phi_result (phi);
 765           if (!is_gimple_reg (SSA_NAME_VAR (result)))
 766             {
 767 #ifdef ENABLE_CHECKING
 768               size_t i;
 769               /* There should be no arguments which are not virtual, or the
 770                  results will be incorrect.  */
 771               for (i = 0; i < gimple_phi_num_args (phi); i++)
 772                 {
 773                   tree arg = PHI_ARG_DEF (phi, i);
 774                   if (TREE_CODE (arg) == SSA_NAME
 775                       && is_gimple_reg (SSA_NAME_VAR (arg)))
 776                     {
 777                       fprintf (stderr, "Argument of PHI is not virtual (");
 778                       print_generic_expr (stderr, arg, TDF_SLIM);
 779                       fprintf (stderr, "), but the result is :");
 780                       print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
 781                       internal_error ("SSA corruption");
 782                     }
 783                 }
 784 #endif
 785               remove_phi_node (&gsi, true);
 786             }
 787           else
 788             {
 789               /* Also remove real PHIs with no uses.  */
 790               if (has_zero_uses (result))
 791                 {
 792                   remove_gimple_phi_args (phi);
 793                   remove_phi_node (&gsi, true);
 794                 }
 795               else
 796                 gsi_next (&gsi);
 797             }
 798         }
 799     }
 800 }
 801
 802
 803 /* This function will rewrite the current program using the variable mapping
 804    found in MAP.  If the replacement vector VALUES is provided, any
 805    occurrences of partitions with non-null entries in the vector will be
 806    replaced with the expression in the vector instead of its mapped
 807    variable.  */
 808
 809 static void
 810 rewrite_trees (var_map map ATTRIBUTE_UNUSED)
 811 {
 812 #ifdef ENABLE_CHECKING
 813   basic_block bb;
 814   /* Search for PHIs where the destination has no partition, but one
 815      or more arguments has a partition.  This should not happen and can
 816      create incorrect code.  */
 817   FOR_EACH_BB (bb)
 818     {
 819       gimple_stmt_iterator gsi;
 820       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 821         {
 822           gimple phi = gsi_stmt (gsi);
 823           tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
 824           if (T0 == NULL_TREE)
 825             {
 826               size_t i;
 827               for (i = 0; i < gimple_phi_num_args (phi); i++)
 828                 {
 829                   tree arg = PHI_ARG_DEF (phi, i);
 830
 831                   if (TREE_CODE (arg) == SSA_NAME
 832                       && var_to_partition (map, arg) != NO_PARTITION)
 833                     {
 834                       fprintf (stderr, "Argument of PHI is in a partition :(");
 835                       print_generic_expr (stderr, arg, TDF_SLIM);
 836                       fprintf (stderr, "), but the result is not :");
 837                       print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
 838                       internal_error ("SSA corruption");
 839                     }
 840                 }
 841             }
 842         }
 843     }
 844 #endif
 845 }
 846
 847 /* Given the out-of-ssa info object SA (with prepared partitions)
 848    eliminate all phi nodes in all basic blocks.  Afterwards no
 849    basic block will have phi nodes anymore and there are possibly
 850    some RTL instructions inserted on edges.  */
 851
 852 void
 853 expand_phi_nodes (struct ssaexpand *sa)
 854 {
 855   basic_block bb;
 856   elim_graph g = new_elim_graph (sa->map->num_partitions);
 857   g->map = sa->map;
 858
 859   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb)
 860     if (!gimple_seq_empty_p (phi_nodes (bb)))
 861       {
 862         edge e;
 863         edge_iterator ei;
 864         FOR_EACH_EDGE (e, ei, bb->preds)
 865           eliminate_phi (e, g);
 866         set_phi_nodes (bb, NULL);
 867         /* We can't redirect EH edges in RTL land, so we need to do this
 868            here.  Redirection happens only when splitting is necessary,
 869            which it is only for critical edges, normally.  For EH edges
 870            it might also be necessary when the successor has more than
 871            one predecessor.  In that case the edge is either required to
 872            be fallthru (which EH edges aren't), or the predecessor needs
 873            to end with a jump (which again, isn't the case with EH edges).
 874            Hence, split all EH edges on which we inserted instructions
 875            and whose successor has multiple predecessors.  */
 876         for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 877           {
 878             if (e->insns.r && (e->flags & EDGE_EH)
 879                 && !single_pred_p (e->dest))
 880               {
 881                 rtx insns = e->insns.r;
 882                 basic_block bb;
 883                 e->insns.r = NULL_RTX;
 884                 bb = split_edge (e);
 885                 single_pred_edge (bb)->insns.r = insns;
 886               }
 887             else
 888               ei_next (&ei);
 889           }
 890       }
 891
 892   delete_elim_graph (g);
 893 }
 894
 895
 896 /* Remove the ssa-names in the current function and translate them into normal
 897    compiler variables.  PERFORM_TER is true if Temporary Expression Replacement
 898    should also be used.  */
 899
 900 static void
 901 remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
 902 {
 903   bitmap values = NULL;
 904   var_map map;
 905   unsigned i;
 906
 907   map = coalesce_ssa_name ();
 908
 909   /* Return to viewing the variable list as just all reference variables after
 910      coalescing has been performed.  */
 911   partition_view_normal (map, false);
 912
 913   if (dump_file && (dump_flags & TDF_DETAILS))
 914     {
 915       fprintf (dump_file, "After Coalescing:\n");
 916       dump_var_map (dump_file, map);
 917     }
 918
 919   if (perform_ter)
 920     {
 921       values = find_replaceable_exprs (map);
 922       if (values && dump_file && (dump_flags & TDF_DETAILS))
 923         dump_replaceable_exprs (dump_file, values);
 924     }
 925
 926   rewrite_trees (map);
 927
 928   sa->map = map;
 929   sa->values = values;
 930   sa->partition_has_default_def = BITMAP_ALLOC (NULL);
 931   for (i = 1; i < num_ssa_names; i++)
 932     {
 933       tree t = ssa_name (i);
 934       if (t && SSA_NAME_IS_DEFAULT_DEF (t))
 935         {
 936           int p = var_to_partition (map, t);
 937           if (p != NO_PARTITION)
 938             bitmap_set_bit (sa->partition_has_default_def, p);
 939         }
 940     }
 941 }
 942
 943
 944 /* If not already done so for basic block BB, assign increasing uids
 945    to each of its instructions.  */
 946
 947 static void
 948 maybe_renumber_stmts_bb (basic_block bb)
 949 {
 950   unsigned i = 0;
 951   gimple_stmt_iterator gsi;
 952
 953   if (!bb->aux)
 954     return;
 955   bb->aux = NULL;
 956   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 957     {
 958       gimple stmt = gsi_stmt (gsi);
 959       gimple_set_uid (stmt, i);
 960       i++;
 961     }
 962 }
 963
 964
 965 /* Return true if we can determine that the SSA_NAMEs RESULT (a result
 966    of a PHI node) and ARG (one of its arguments) conflict.  Return false
 967    otherwise, also when we simply aren't sure.  */
 968
 969 static bool
 970 trivially_conflicts_p (basic_block bb, tree result, tree arg)
 971 {
 972   use_operand_p use;
 973   imm_use_iterator imm_iter;
 974   gimple defa = SSA_NAME_DEF_STMT (arg);
 975
 976   /* If ARG isn't defined in the same block it's too complicated for
 977      our little mind.  */
 978   if (gimple_bb (defa) != bb)
 979     return false;
 980
 981   FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
 982     {
 983       gimple use_stmt = USE_STMT (use);
 984       if (is_gimple_debug (use_stmt))
 985         continue;
 986       /* Now, if there's a use of RESULT that lies outside this basic block,
 987          then there surely is a conflict with ARG.  */
 988       if (gimple_bb (use_stmt) != bb)
 989         return true;
 990       if (gimple_code (use_stmt) == GIMPLE_PHI)
 991         continue;
 992       /* The use now is in a real stmt of BB, so if ARG was defined
 993          in a PHI node (like RESULT) both conflict.  */
 994       if (gimple_code (defa) == GIMPLE_PHI)
 995         return true;
 996       maybe_renumber_stmts_bb (bb);
 997       /* If the use of RESULT occurs after the definition of ARG,
 998          the two conflict too.  */
 999       if (gimple_uid (defa) < gimple_uid (use_stmt))
1000         return true;
1001     }
1002
1003   return false;
1004 }
1005
1006
1007 /* Search every PHI node for arguments associated with backedges which
1008    we can trivially determine will need a copy (the argument is either
1009    not an SSA_NAME or the argument has a different underlying variable
1010    than the PHI result).
1011
1012    Insert a copy from the PHI argument to a new destination at the
1013    end of the block with the backedge to the top of the loop.  Update
1014    the PHI argument to reference this new destination.  */
1015
1016 static void
1017 insert_backedge_copies (void)
1018 {
1019   basic_block bb;
1020   gimple_stmt_iterator gsi;
1021
1022   FOR_EACH_BB (bb)
1023     {
1024       /* Mark block as possibly needing calculation of UIDs.  */
1025       bb->aux = &bb->aux;
1026
1027       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1028         {
1029           gimple phi = gsi_stmt (gsi);
1030           tree result = gimple_phi_result (phi);
1031           tree result_var;
1032           size_t i;
1033
1034           if (!is_gimple_reg (result))
1035             continue;
1036
1037           result_var = SSA_NAME_VAR (result);
1038           for (i = 0; i < gimple_phi_num_args (phi); i++)
1039             {
1040               tree arg = gimple_phi_arg_def (phi, i);
1041               edge e = gimple_phi_arg_edge (phi, i);
1042
1043               /* If the argument is not an SSA_NAME, then we will need a
1044                  constant initialization.  If the argument is an SSA_NAME with
1045                  a different underlying variable then a copy statement will be
1046                  needed.  */
1047               if ((e->flags & EDGE_DFS_BACK)
1048                   && (TREE_CODE (arg) != SSA_NAME
1049                       || SSA_NAME_VAR (arg) != result_var
1050                       || trivially_conflicts_p (bb, result, arg)))
1051                 {
1052                   tree name;
1053                   gimple stmt, last = NULL;
1054                   gimple_stmt_iterator gsi2;
1055
1056                   gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
1057                   if (!gsi_end_p (gsi2))
1058                     last = gsi_stmt (gsi2);
1059
1060                   /* In theory the only way we ought to get back to the
1061                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
1062                      However, better safe than sorry.
1063                      If the block ends with a control statement or
1064                      something that might throw, then we have to
1065                      insert this assignment before the last
1066                      statement.  Else insert it after the last statement.  */
1067                   if (last && stmt_ends_bb_p (last))
1068                     {
1069                       /* If the last statement in the block is the definition
1070                          site of the PHI argument, then we can't insert
1071                          anything after it.  */
1072                       if (TREE_CODE (arg) == SSA_NAME
1073                           && SSA_NAME_DEF_STMT (arg) == last)
1074                         continue;
1075                     }
1076
1077                   /* Create a new instance of the underlying variable of the
1078                      PHI result.  */
1079                   stmt = gimple_build_assign (result_var,
1080                                               gimple_phi_arg_def (phi, i));
1081                   name = make_ssa_name (result_var, stmt);
1082                   gimple_assign_set_lhs (stmt, name);
1083
1084                   /* copy location if present.  */
1085                   if (gimple_phi_arg_has_location (phi, i))
1086                     gimple_set_location (stmt,
1087                                          gimple_phi_arg_location (phi, i));
1088
1089                   /* Insert the new statement into the block and update
1090                      the PHI node.  */
1091                   if (last && stmt_ends_bb_p (last))
1092                     gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
1093                   else
1094                     gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
1095                   SET_PHI_ARG_DEF (phi, i, name);
1096                 }
1097             }
1098         }
1099
1100       /* Unmark this block again.  */
1101       bb->aux = NULL;
1102     }
1103 }
1104
1105 /* Free all memory associated with going out of SSA form.  SA is
1106    the outof-SSA info object.  */
1107
1108 void
1109 finish_out_of_ssa (struct ssaexpand *sa)
1110 {
1111   free (sa->partition_to_pseudo);
1112   if (sa->values)
1113     BITMAP_FREE (sa->values);
1114   delete_var_map (sa->map);
1115   BITMAP_FREE (sa->partition_has_default_def);
1116   memset (sa, 0, sizeof *sa);
1117 }
1118
1119 /* Take the current function out of SSA form, translating PHIs as described in
1120    R. Morgan, ``Building an Optimizing Compiler'',
1121    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
1122
1123 unsigned int
1124 rewrite_out_of_ssa (struct ssaexpand *sa)
1125 {
1126   /* If elimination of a PHI requires inserting a copy on a backedge,
1127      then we will have to split the backedge which has numerous
1128      undesirable performance effects.
1129
1130      A significant number of such cases can be handled here by inserting
1131      copies into the loop itself.  */
1132   insert_backedge_copies ();
1133
1134
1135   /* Eliminate PHIs which are of no use, such as virtual or dead phis.  */
1136   eliminate_useless_phis ();
1137
1138   if (dump_file && (dump_flags & TDF_DETAILS))
1139     gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1140
1141   remove_ssa_form (flag_tree_ter, sa);
1142
1143   if (dump_file && (dump_flags & TDF_DETAILS))
1144     gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
1145
1146   return 0;
1147 }