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