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