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