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