gcc/tree-outof-ssa.c

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