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