1 /* SSA Dominator optimizations for trees 2 Copyright (C) 2001-2013 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "tree.h" 26 #include "flags.h" 27 #include "tm_p.h" 28 #include "basic-block.h" 29 #include "cfgloop.h" 30 #include "function.h" 31 #include "gimple-pretty-print.h" 32 #include "tree-flow.h" 33 #include "domwalk.h" 34 #include "tree-pass.h" 35 #include "tree-ssa-propagate.h" 36 #include "langhooks.h" 37 #include "params.h" 38 39 /* This file implements optimizations on the dominator tree. */ 40 41 /* Representation of a "naked" right-hand-side expression, to be used 42 in recording available expressions in the expression hash table. */ 43 44 enum expr_kind 45 { 46 EXPR_SINGLE, 47 EXPR_UNARY, 48 EXPR_BINARY, 49 EXPR_TERNARY, 50 EXPR_CALL, 51 EXPR_PHI 52 }; 53 54 struct hashable_expr 55 { 56 tree type; 57 enum expr_kind kind; 58 union { 59 struct { tree rhs; } single; 60 struct { enum tree_code op; tree opnd; } unary; 61 struct { enum tree_code op; tree opnd0, opnd1; } binary; 62 struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary; 63 struct { gimple fn_from; bool pure; size_t nargs; tree *args; } call; 64 struct { size_t nargs; tree *args; } phi; 65 } ops; 66 }; 67 68 /* Structure for recording known values of a conditional expression 69 at the exits from its block. */ 70 71 typedef struct cond_equivalence_s 72 { 73 struct hashable_expr cond; 74 tree value; 75 } cond_equivalence; 76 77 78 /* Structure for recording edge equivalences as well as any pending 79 edge redirections during the dominator optimizer. 80 81 Computing and storing the edge equivalences instead of creating 82 them on-demand can save significant amounts of time, particularly 83 for pathological cases involving switch statements. 84 85 These structures live for a single iteration of the dominator 86 optimizer in the edge's AUX field. At the end of an iteration we 87 free each of these structures and update the AUX field to point 88 to any requested redirection target (the code for updating the 89 CFG and SSA graph for edge redirection expects redirection edge 90 targets to be in the AUX field for each edge. */ 91 92 struct edge_info 93 { 94 /* If this edge creates a simple equivalence, the LHS and RHS of 95 the equivalence will be stored here. */ 96 tree lhs; 97 tree rhs; 98 99 /* Traversing an edge may also indicate one or more particular conditions 100 are true or false. */ 101 vec<cond_equivalence> cond_equivalences; 102 }; 103 104 /* Hash table with expressions made available during the renaming process. 105 When an assignment of the form X_i = EXPR is found, the statement is 106 stored in this table. If the same expression EXPR is later found on the 107 RHS of another statement, it is replaced with X_i (thus performing 108 global redundancy elimination). Similarly as we pass through conditionals 109 we record the conditional itself as having either a true or false value 110 in this table. */ 111 static htab_t avail_exprs; 112 113 /* Stack of available expressions in AVAIL_EXPRs. Each block pushes any 114 expressions it enters into the hash table along with a marker entry 115 (null). When we finish processing the block, we pop off entries and 116 remove the expressions from the global hash table until we hit the 117 marker. */ 118 typedef struct expr_hash_elt * expr_hash_elt_t; 119 120 static vec<expr_hash_elt_t> avail_exprs_stack; 121 122 /* Structure for entries in the expression hash table. */ 123 124 struct expr_hash_elt 125 { 126 /* The value (lhs) of this expression. */ 127 tree lhs; 128 129 /* The expression (rhs) we want to record. */ 130 struct hashable_expr expr; 131 132 /* The stmt pointer if this element corresponds to a statement. */ 133 gimple stmt; 134 135 /* The hash value for RHS. */ 136 hashval_t hash; 137 138 /* A unique stamp, typically the address of the hash 139 element itself, used in removing entries from the table. */ 140 struct expr_hash_elt *stamp; 141 }; 142 143 /* Stack of dest,src pairs that need to be restored during finalization. 144 145 A NULL entry is used to mark the end of pairs which need to be 146 restored during finalization of this block. */ 147 static vec<tree> const_and_copies_stack; 148 149 /* Track whether or not we have changed the control flow graph. */ 150 static bool cfg_altered; 151 152 /* Bitmap of blocks that have had EH statements cleaned. We should 153 remove their dead edges eventually. */ 154 static bitmap need_eh_cleanup; 155 156 /* Statistics for dominator optimizations. */ 157 struct opt_stats_d 158 { 159 long num_stmts; 160 long num_exprs_considered; 161 long num_re; 162 long num_const_prop; 163 long num_copy_prop; 164 }; 165 166 static struct opt_stats_d opt_stats; 167 168 /* Local functions. */ 169 static void optimize_stmt (basic_block, gimple_stmt_iterator); 170 static tree lookup_avail_expr (gimple, bool); 171 static hashval_t avail_expr_hash (const void *); 172 static hashval_t real_avail_expr_hash (const void *); 173 static int avail_expr_eq (const void *, const void *); 174 static void htab_statistics (FILE *, htab_t); 175 static void record_cond (cond_equivalence *); 176 static void record_const_or_copy (tree, tree); 177 static void record_equality (tree, tree); 178 static void record_equivalences_from_phis (basic_block); 179 static void record_equivalences_from_incoming_edge (basic_block); 180 static void eliminate_redundant_computations (gimple_stmt_iterator *); 181 static void record_equivalences_from_stmt (gimple, int); 182 static void dom_thread_across_edge (struct dom_walk_data *, edge); 183 static void dom_opt_leave_block (struct dom_walk_data *, basic_block); 184 static void dom_opt_enter_block (struct dom_walk_data *, basic_block); 185 static void remove_local_expressions_from_table (void); 186 static void restore_vars_to_original_value (void); 187 static edge single_incoming_edge_ignoring_loop_edges (basic_block); 188 189 190 /* Given a statement STMT, initialize the hash table element pointed to 191 by ELEMENT. */ 192 193 static void 194 initialize_hash_element (gimple stmt, tree lhs, 195 struct expr_hash_elt *element) 196 { 197 enum gimple_code code = gimple_code (stmt); 198 struct hashable_expr *expr = &element->expr; 199 200 if (code == GIMPLE_ASSIGN) 201 { 202 enum tree_code subcode = gimple_assign_rhs_code (stmt); 203 204 switch (get_gimple_rhs_class (subcode)) 205 { 206 case GIMPLE_SINGLE_RHS: 207 expr->kind = EXPR_SINGLE; 208 expr->type = TREE_TYPE (gimple_assign_rhs1 (stmt)); 209 expr->ops.single.rhs = gimple_assign_rhs1 (stmt); 210 break; 211 case GIMPLE_UNARY_RHS: 212 expr->kind = EXPR_UNARY; 213 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 214 expr->ops.unary.op = subcode; 215 expr->ops.unary.opnd = gimple_assign_rhs1 (stmt); 216 break; 217 case GIMPLE_BINARY_RHS: 218 expr->kind = EXPR_BINARY; 219 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 220 expr->ops.binary.op = subcode; 221 expr->ops.binary.opnd0 = gimple_assign_rhs1 (stmt); 222 expr->ops.binary.opnd1 = gimple_assign_rhs2 (stmt); 223 break; 224 case GIMPLE_TERNARY_RHS: 225 expr->kind = EXPR_TERNARY; 226 expr->type = TREE_TYPE (gimple_assign_lhs (stmt)); 227 expr->ops.ternary.op = subcode; 228 expr->ops.ternary.opnd0 = gimple_assign_rhs1 (stmt); 229 expr->ops.ternary.opnd1 = gimple_assign_rhs2 (stmt); 230 expr->ops.ternary.opnd2 = gimple_assign_rhs3 (stmt); 231 break; 232 default: 233 gcc_unreachable (); 234 } 235 } 236 else if (code == GIMPLE_COND) 237 { 238 expr->type = boolean_type_node; 239 expr->kind = EXPR_BINARY; 240 expr->ops.binary.op = gimple_cond_code (stmt); 241 expr->ops.binary.opnd0 = gimple_cond_lhs (stmt); 242 expr->ops.binary.opnd1 = gimple_cond_rhs (stmt); 243 } 244 else if (code == GIMPLE_CALL) 245 { 246 size_t nargs = gimple_call_num_args (stmt); 247 size_t i; 248 249 gcc_assert (gimple_call_lhs (stmt)); 250 251 expr->type = TREE_TYPE (gimple_call_lhs (stmt)); 252 expr->kind = EXPR_CALL; 253 expr->ops.call.fn_from = stmt; 254 255 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)) 256 expr->ops.call.pure = true; 257 else 258 expr->ops.call.pure = false; 259 260 expr->ops.call.nargs = nargs; 261 expr->ops.call.args = XCNEWVEC (tree, nargs); 262 for (i = 0; i < nargs; i++) 263 expr->ops.call.args[i] = gimple_call_arg (stmt, i); 264 } 265 else if (code == GIMPLE_SWITCH) 266 { 267 expr->type = TREE_TYPE (gimple_switch_index (stmt)); 268 expr->kind = EXPR_SINGLE; 269 expr->ops.single.rhs = gimple_switch_index (stmt); 270 } 271 else if (code == GIMPLE_GOTO) 272 { 273 expr->type = TREE_TYPE (gimple_goto_dest (stmt)); 274 expr->kind = EXPR_SINGLE; 275 expr->ops.single.rhs = gimple_goto_dest (stmt); 276 } 277 else if (code == GIMPLE_PHI) 278 { 279 size_t nargs = gimple_phi_num_args (stmt); 280 size_t i; 281 282 expr->type = TREE_TYPE (gimple_phi_result (stmt)); 283 expr->kind = EXPR_PHI; 284 expr->ops.phi.nargs = nargs; 285 expr->ops.phi.args = XCNEWVEC (tree, nargs); 286 287 for (i = 0; i < nargs; i++) 288 expr->ops.phi.args[i] = gimple_phi_arg_def (stmt, i); 289 } 290 else 291 gcc_unreachable (); 292 293 element->lhs = lhs; 294 element->stmt = stmt; 295 element->hash = avail_expr_hash (element); 296 element->stamp = element; 297 } 298 299 /* Given a conditional expression COND as a tree, initialize 300 a hashable_expr expression EXPR. The conditional must be a 301 comparison or logical negation. A constant or a variable is 302 not permitted. */ 303 304 static void 305 initialize_expr_from_cond (tree cond, struct hashable_expr *expr) 306 { 307 expr->type = boolean_type_node; 308 309 if (COMPARISON_CLASS_P (cond)) 310 { 311 expr->kind = EXPR_BINARY; 312 expr->ops.binary.op = TREE_CODE (cond); 313 expr->ops.binary.opnd0 = TREE_OPERAND (cond, 0); 314 expr->ops.binary.opnd1 = TREE_OPERAND (cond, 1); 315 } 316 else if (TREE_CODE (cond) == TRUTH_NOT_EXPR) 317 { 318 expr->kind = EXPR_UNARY; 319 expr->ops.unary.op = TRUTH_NOT_EXPR; 320 expr->ops.unary.opnd = TREE_OPERAND (cond, 0); 321 } 322 else 323 gcc_unreachable (); 324 } 325 326 /* Given a hashable_expr expression EXPR and an LHS, 327 initialize the hash table element pointed to by ELEMENT. */ 328 329 static void 330 initialize_hash_element_from_expr (struct hashable_expr *expr, 331 tree lhs, 332 struct expr_hash_elt *element) 333 { 334 element->expr = *expr; 335 element->lhs = lhs; 336 element->stmt = NULL; 337 element->hash = avail_expr_hash (element); 338 element->stamp = element; 339 } 340 341 /* Compare two hashable_expr structures for equivalence. 342 They are considered equivalent when the the expressions 343 they denote must necessarily be equal. The logic is intended 344 to follow that of operand_equal_p in fold-const.c */ 345 346 static bool 347 hashable_expr_equal_p (const struct hashable_expr *expr0, 348 const struct hashable_expr *expr1) 349 { 350 tree type0 = expr0->type; 351 tree type1 = expr1->type; 352 353 /* If either type is NULL, there is nothing to check. */ 354 if ((type0 == NULL_TREE) ^ (type1 == NULL_TREE)) 355 return false; 356 357 /* If both types don't have the same signedness, precision, and mode, 358 then we can't consider them equal. */ 359 if (type0 != type1 360 && (TREE_CODE (type0) == ERROR_MARK 361 || TREE_CODE (type1) == ERROR_MARK 362 || TYPE_UNSIGNED (type0) != TYPE_UNSIGNED (type1) 363 || TYPE_PRECISION (type0) != TYPE_PRECISION (type1) 364 || TYPE_MODE (type0) != TYPE_MODE (type1))) 365 return false; 366 367 if (expr0->kind != expr1->kind) 368 return false; 369 370 switch (expr0->kind) 371 { 372 case EXPR_SINGLE: 373 return operand_equal_p (expr0->ops.single.rhs, 374 expr1->ops.single.rhs, 0); 375 376 case EXPR_UNARY: 377 if (expr0->ops.unary.op != expr1->ops.unary.op) 378 return false; 379 380 if ((CONVERT_EXPR_CODE_P (expr0->ops.unary.op) 381 || expr0->ops.unary.op == NON_LVALUE_EXPR) 382 && TYPE_UNSIGNED (expr0->type) != TYPE_UNSIGNED (expr1->type)) 383 return false; 384 385 return operand_equal_p (expr0->ops.unary.opnd, 386 expr1->ops.unary.opnd, 0); 387 388 case EXPR_BINARY: 389 if (expr0->ops.binary.op != expr1->ops.binary.op) 390 return false; 391 392 if (operand_equal_p (expr0->ops.binary.opnd0, 393 expr1->ops.binary.opnd0, 0) 394 && operand_equal_p (expr0->ops.binary.opnd1, 395 expr1->ops.binary.opnd1, 0)) 396 return true; 397 398 /* For commutative ops, allow the other order. */ 399 return (commutative_tree_code (expr0->ops.binary.op) 400 && operand_equal_p (expr0->ops.binary.opnd0, 401 expr1->ops.binary.opnd1, 0) 402 && operand_equal_p (expr0->ops.binary.opnd1, 403 expr1->ops.binary.opnd0, 0)); 404 405 case EXPR_TERNARY: 406 if (expr0->ops.ternary.op != expr1->ops.ternary.op 407 || !operand_equal_p (expr0->ops.ternary.opnd2, 408 expr1->ops.ternary.opnd2, 0)) 409 return false; 410 411 if (operand_equal_p (expr0->ops.ternary.opnd0, 412 expr1->ops.ternary.opnd0, 0) 413 && operand_equal_p (expr0->ops.ternary.opnd1, 414 expr1->ops.ternary.opnd1, 0)) 415 return true; 416 417 /* For commutative ops, allow the other order. */ 418 return (commutative_ternary_tree_code (expr0->ops.ternary.op) 419 && operand_equal_p (expr0->ops.ternary.opnd0, 420 expr1->ops.ternary.opnd1, 0) 421 && operand_equal_p (expr0->ops.ternary.opnd1, 422 expr1->ops.ternary.opnd0, 0)); 423 424 case EXPR_CALL: 425 { 426 size_t i; 427 428 /* If the calls are to different functions, then they 429 clearly cannot be equal. */ 430 if (!gimple_call_same_target_p (expr0->ops.call.fn_from, 431 expr1->ops.call.fn_from)) 432 return false; 433 434 if (! expr0->ops.call.pure) 435 return false; 436 437 if (expr0->ops.call.nargs != expr1->ops.call.nargs) 438 return false; 439 440 for (i = 0; i < expr0->ops.call.nargs; i++) 441 if (! operand_equal_p (expr0->ops.call.args[i], 442 expr1->ops.call.args[i], 0)) 443 return false; 444 445 return true; 446 } 447 448 case EXPR_PHI: 449 { 450 size_t i; 451 452 if (expr0->ops.phi.nargs != expr1->ops.phi.nargs) 453 return false; 454 455 for (i = 0; i < expr0->ops.phi.nargs; i++) 456 if (! operand_equal_p (expr0->ops.phi.args[i], 457 expr1->ops.phi.args[i], 0)) 458 return false; 459 460 return true; 461 } 462 463 default: 464 gcc_unreachable (); 465 } 466 } 467 468 /* Compute a hash value for a hashable_expr value EXPR and a 469 previously accumulated hash value VAL. If two hashable_expr 470 values compare equal with hashable_expr_equal_p, they must 471 hash to the same value, given an identical value of VAL. 472 The logic is intended to follow iterative_hash_expr in tree.c. */ 473 474 static hashval_t 475 iterative_hash_hashable_expr (const struct hashable_expr *expr, hashval_t val) 476 { 477 switch (expr->kind) 478 { 479 case EXPR_SINGLE: 480 val = iterative_hash_expr (expr->ops.single.rhs, val); 481 break; 482 483 case EXPR_UNARY: 484 val = iterative_hash_object (expr->ops.unary.op, val); 485 486 /* Make sure to include signedness in the hash computation. 487 Don't hash the type, that can lead to having nodes which 488 compare equal according to operand_equal_p, but which 489 have different hash codes. */ 490 if (CONVERT_EXPR_CODE_P (expr->ops.unary.op) 491 || expr->ops.unary.op == NON_LVALUE_EXPR) 492 val += TYPE_UNSIGNED (expr->type); 493 494 val = iterative_hash_expr (expr->ops.unary.opnd, val); 495 break; 496 497 case EXPR_BINARY: 498 val = iterative_hash_object (expr->ops.binary.op, val); 499 if (commutative_tree_code (expr->ops.binary.op)) 500 val = iterative_hash_exprs_commutative (expr->ops.binary.opnd0, 501 expr->ops.binary.opnd1, val); 502 else 503 { 504 val = iterative_hash_expr (expr->ops.binary.opnd0, val); 505 val = iterative_hash_expr (expr->ops.binary.opnd1, val); 506 } 507 break; 508 509 case EXPR_TERNARY: 510 val = iterative_hash_object (expr->ops.ternary.op, val); 511 if (commutative_ternary_tree_code (expr->ops.ternary.op)) 512 val = iterative_hash_exprs_commutative (expr->ops.ternary.opnd0, 513 expr->ops.ternary.opnd1, val); 514 else 515 { 516 val = iterative_hash_expr (expr->ops.ternary.opnd0, val); 517 val = iterative_hash_expr (expr->ops.ternary.opnd1, val); 518 } 519 val = iterative_hash_expr (expr->ops.ternary.opnd2, val); 520 break; 521 522 case EXPR_CALL: 523 { 524 size_t i; 525 enum tree_code code = CALL_EXPR; 526 gimple fn_from; 527 528 val = iterative_hash_object (code, val); 529 fn_from = expr->ops.call.fn_from; 530 if (gimple_call_internal_p (fn_from)) 531 val = iterative_hash_hashval_t 532 ((hashval_t) gimple_call_internal_fn (fn_from), val); 533 else 534 val = iterative_hash_expr (gimple_call_fn (fn_from), val); 535 for (i = 0; i < expr->ops.call.nargs; i++) 536 val = iterative_hash_expr (expr->ops.call.args[i], val); 537 } 538 break; 539 540 case EXPR_PHI: 541 { 542 size_t i; 543 544 for (i = 0; i < expr->ops.phi.nargs; i++) 545 val = iterative_hash_expr (expr->ops.phi.args[i], val); 546 } 547 break; 548 549 default: 550 gcc_unreachable (); 551 } 552 553 return val; 554 } 555 556 /* Print a diagnostic dump of an expression hash table entry. */ 557 558 static void 559 print_expr_hash_elt (FILE * stream, const struct expr_hash_elt *element) 560 { 561 if (element->stmt) 562 fprintf (stream, "STMT "); 563 else 564 fprintf (stream, "COND "); 565 566 if (element->lhs) 567 { 568 print_generic_expr (stream, element->lhs, 0); 569 fprintf (stream, " = "); 570 } 571 572 switch (element->expr.kind) 573 { 574 case EXPR_SINGLE: 575 print_generic_expr (stream, element->expr.ops.single.rhs, 0); 576 break; 577 578 case EXPR_UNARY: 579 fprintf (stream, "%s ", tree_code_name[element->expr.ops.unary.op]); 580 print_generic_expr (stream, element->expr.ops.unary.opnd, 0); 581 break; 582 583 case EXPR_BINARY: 584 print_generic_expr (stream, element->expr.ops.binary.opnd0, 0); 585 fprintf (stream, " %s ", tree_code_name[element->expr.ops.binary.op]); 586 print_generic_expr (stream, element->expr.ops.binary.opnd1, 0); 587 break; 588 589 case EXPR_TERNARY: 590 fprintf (stream, " %s <", tree_code_name[element->expr.ops.ternary.op]); 591 print_generic_expr (stream, element->expr.ops.ternary.opnd0, 0); 592 fputs (", ", stream); 593 print_generic_expr (stream, element->expr.ops.ternary.opnd1, 0); 594 fputs (", ", stream); 595 print_generic_expr (stream, element->expr.ops.ternary.opnd2, 0); 596 fputs (">", stream); 597 break; 598 599 case EXPR_CALL: 600 { 601 size_t i; 602 size_t nargs = element->expr.ops.call.nargs; 603 gimple fn_from; 604 605 fn_from = element->expr.ops.call.fn_from; 606 if (gimple_call_internal_p (fn_from)) 607 fputs (internal_fn_name (gimple_call_internal_fn (fn_from)), 608 stream); 609 else 610 print_generic_expr (stream, gimple_call_fn (fn_from), 0); 611 fprintf (stream, " ("); 612 for (i = 0; i < nargs; i++) 613 { 614 print_generic_expr (stream, element->expr.ops.call.args[i], 0); 615 if (i + 1 < nargs) 616 fprintf (stream, ", "); 617 } 618 fprintf (stream, ")"); 619 } 620 break; 621 622 case EXPR_PHI: 623 { 624 size_t i; 625 size_t nargs = element->expr.ops.phi.nargs; 626 627 fprintf (stream, "PHI <"); 628 for (i = 0; i < nargs; i++) 629 { 630 print_generic_expr (stream, element->expr.ops.phi.args[i], 0); 631 if (i + 1 < nargs) 632 fprintf (stream, ", "); 633 } 634 fprintf (stream, ">"); 635 } 636 break; 637 } 638 fprintf (stream, "\n"); 639 640 if (element->stmt) 641 { 642 fprintf (stream, " "); 643 print_gimple_stmt (stream, element->stmt, 0, 0); 644 } 645 } 646 647 /* Delete variable sized pieces of the expr_hash_elt ELEMENT. */ 648 649 static void 650 free_expr_hash_elt_contents (struct expr_hash_elt *element) 651 { 652 if (element->expr.kind == EXPR_CALL) 653 free (element->expr.ops.call.args); 654 else if (element->expr.kind == EXPR_PHI) 655 free (element->expr.ops.phi.args); 656 } 657 658 /* Delete an expr_hash_elt and reclaim its storage. */ 659 660 static void 661 free_expr_hash_elt (void *elt) 662 { 663 struct expr_hash_elt *element = ((struct expr_hash_elt *)elt); 664 free_expr_hash_elt_contents (element); 665 free (element); 666 } 667 668 /* Allocate an EDGE_INFO for edge E and attach it to E. 669 Return the new EDGE_INFO structure. */ 670 671 static struct edge_info * 672 allocate_edge_info (edge e) 673 { 674 struct edge_info *edge_info; 675 676 edge_info = XCNEW (struct edge_info); 677 678 e->aux = edge_info; 679 return edge_info; 680 } 681 682 /* Free all EDGE_INFO structures associated with edges in the CFG. 683 If a particular edge can be threaded, copy the redirection 684 target from the EDGE_INFO structure into the edge's AUX field 685 as required by code to update the CFG and SSA graph for 686 jump threading. */ 687 688 static void 689 free_all_edge_infos (void) 690 { 691 basic_block bb; 692 edge_iterator ei; 693 edge e; 694 695 FOR_EACH_BB (bb) 696 { 697 FOR_EACH_EDGE (e, ei, bb->preds) 698 { 699 struct edge_info *edge_info = (struct edge_info *) e->aux; 700 701 if (edge_info) 702 { 703 edge_info->cond_equivalences.release (); 704 free (edge_info); 705 e->aux = NULL; 706 } 707 } 708 } 709 } 710 711 /* Jump threading, redundancy elimination and const/copy propagation. 712 713 This pass may expose new symbols that need to be renamed into SSA. For 714 every new symbol exposed, its corresponding bit will be set in 715 VARS_TO_RENAME. */ 716 717 static unsigned int 718 tree_ssa_dominator_optimize (void) 719 { 720 struct dom_walk_data walk_data; 721 722 memset (&opt_stats, 0, sizeof (opt_stats)); 723 724 /* Create our hash tables. */ 725 avail_exprs = htab_create (1024, real_avail_expr_hash, avail_expr_eq, free_expr_hash_elt); 726 avail_exprs_stack.create (20); 727 const_and_copies_stack.create (20); 728 need_eh_cleanup = BITMAP_ALLOC (NULL); 729 730 /* Setup callbacks for the generic dominator tree walker. */ 731 walk_data.dom_direction = CDI_DOMINATORS; 732 walk_data.initialize_block_local_data = NULL; 733 walk_data.before_dom_children = dom_opt_enter_block; 734 walk_data.after_dom_children = dom_opt_leave_block; 735 /* Right now we only attach a dummy COND_EXPR to the global data pointer. 736 When we attach more stuff we'll need to fill this out with a real 737 structure. */ 738 walk_data.global_data = NULL; 739 walk_data.block_local_data_size = 0; 740 741 /* Now initialize the dominator walker. */ 742 init_walk_dominator_tree (&walk_data); 743 744 calculate_dominance_info (CDI_DOMINATORS); 745 cfg_altered = false; 746 747 /* We need to know loop structures in order to avoid destroying them 748 in jump threading. Note that we still can e.g. thread through loop 749 headers to an exit edge, or through loop header to the loop body, assuming 750 that we update the loop info. */ 751 loop_optimizer_init (LOOPS_HAVE_SIMPLE_LATCHES); 752 753 /* Initialize the value-handle array. */ 754 threadedge_initialize_values (); 755 756 /* We need accurate information regarding back edges in the CFG 757 for jump threading; this may include back edges that are not part of 758 a single loop. */ 759 mark_dfs_back_edges (); 760 761 /* Recursively walk the dominator tree optimizing statements. */ 762 walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); 763 764 { 765 gimple_stmt_iterator gsi; 766 basic_block bb; 767 FOR_EACH_BB (bb) 768 { 769 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 770 update_stmt_if_modified (gsi_stmt (gsi)); 771 } 772 } 773 774 /* If we exposed any new variables, go ahead and put them into 775 SSA form now, before we handle jump threading. This simplifies 776 interactions between rewriting of _DECL nodes into SSA form 777 and rewriting SSA_NAME nodes into SSA form after block 778 duplication and CFG manipulation. */ 779 update_ssa (TODO_update_ssa); 780 781 free_all_edge_infos (); 782 783 /* Thread jumps, creating duplicate blocks as needed. */ 784 cfg_altered |= thread_through_all_blocks (first_pass_instance); 785 786 if (cfg_altered) 787 free_dominance_info (CDI_DOMINATORS); 788 789 /* Removal of statements may make some EH edges dead. Purge 790 such edges from the CFG as needed. */ 791 if (!bitmap_empty_p (need_eh_cleanup)) 792 { 793 unsigned i; 794 bitmap_iterator bi; 795 796 /* Jump threading may have created forwarder blocks from blocks 797 needing EH cleanup; the new successor of these blocks, which 798 has inherited from the original block, needs the cleanup. 799 Don't clear bits in the bitmap, as that can break the bitmap 800 iterator. */ 801 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi) 802 { 803 basic_block bb = BASIC_BLOCK (i); 804 if (bb == NULL) 805 continue; 806 while (single_succ_p (bb) 807 && (single_succ_edge (bb)->flags & EDGE_EH) == 0) 808 bb = single_succ (bb); 809 if (bb == EXIT_BLOCK_PTR) 810 continue; 811 if ((unsigned) bb->index != i) 812 bitmap_set_bit (need_eh_cleanup, bb->index); 813 } 814 815 gimple_purge_all_dead_eh_edges (need_eh_cleanup); 816 bitmap_clear (need_eh_cleanup); 817 } 818 819 statistics_counter_event (cfun, "Redundant expressions eliminated", 820 opt_stats.num_re); 821 statistics_counter_event (cfun, "Constants propagated", 822 opt_stats.num_const_prop); 823 statistics_counter_event (cfun, "Copies propagated", 824 opt_stats.num_copy_prop); 825 826 /* Debugging dumps. */ 827 if (dump_file && (dump_flags & TDF_STATS)) 828 dump_dominator_optimization_stats (dump_file); 829 830 loop_optimizer_finalize (); 831 832 /* Delete our main hashtable. */ 833 htab_delete (avail_exprs); 834 835 /* And finalize the dominator walker. */ 836 fini_walk_dominator_tree (&walk_data); 837 838 /* Free asserted bitmaps and stacks. */ 839 BITMAP_FREE (need_eh_cleanup); 840 841 avail_exprs_stack.release (); 842 const_and_copies_stack.release (); 843 844 /* Free the value-handle array. */ 845 threadedge_finalize_values (); 846 ssa_name_values.release (); 847 848 return 0; 849 } 850 851 static bool 852 gate_dominator (void) 853 { 854 return flag_tree_dom != 0; 855 } 856 857 struct gimple_opt_pass pass_dominator = 858 { 859 { 860 GIMPLE_PASS, 861 "dom", /* name */ 862 OPTGROUP_NONE, /* optinfo_flags */ 863 gate_dominator, /* gate */ 864 tree_ssa_dominator_optimize, /* execute */ 865 NULL, /* sub */ 866 NULL, /* next */ 867 0, /* static_pass_number */ 868 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ 869 PROP_cfg | PROP_ssa, /* properties_required */ 870 0, /* properties_provided */ 871 0, /* properties_destroyed */ 872 0, /* todo_flags_start */ 873 TODO_cleanup_cfg 874 | TODO_update_ssa 875 | TODO_verify_ssa 876 | TODO_verify_flow /* todo_flags_finish */ 877 } 878 }; 879 880 881 /* Given a conditional statement CONDSTMT, convert the 882 condition to a canonical form. */ 883 884 static void 885 canonicalize_comparison (gimple condstmt) 886 { 887 tree op0; 888 tree op1; 889 enum tree_code code; 890 891 gcc_assert (gimple_code (condstmt) == GIMPLE_COND); 892 893 op0 = gimple_cond_lhs (condstmt); 894 op1 = gimple_cond_rhs (condstmt); 895 896 code = gimple_cond_code (condstmt); 897 898 /* If it would be profitable to swap the operands, then do so to 899 canonicalize the statement, enabling better optimization. 900 901 By placing canonicalization of such expressions here we 902 transparently keep statements in canonical form, even 903 when the statement is modified. */ 904 if (tree_swap_operands_p (op0, op1, false)) 905 { 906 /* For relationals we need to swap the operands 907 and change the code. */ 908 if (code == LT_EXPR 909 || code == GT_EXPR 910 || code == LE_EXPR 911 || code == GE_EXPR) 912 { 913 code = swap_tree_comparison (code); 914 915 gimple_cond_set_code (condstmt, code); 916 gimple_cond_set_lhs (condstmt, op1); 917 gimple_cond_set_rhs (condstmt, op0); 918 919 update_stmt (condstmt); 920 } 921 } 922 } 923 924 /* Initialize local stacks for this optimizer and record equivalences 925 upon entry to BB. Equivalences can come from the edge traversed to 926 reach BB or they may come from PHI nodes at the start of BB. */ 927 928 /* Remove all the expressions in LOCALS from TABLE, stopping when there are 929 LIMIT entries left in LOCALs. */ 930 931 static void 932 remove_local_expressions_from_table (void) 933 { 934 /* Remove all the expressions made available in this block. */ 935 while (avail_exprs_stack.length () > 0) 936 { 937 expr_hash_elt_t victim = avail_exprs_stack.pop (); 938 void **slot; 939 940 if (victim == NULL) 941 break; 942 943 /* This must precede the actual removal from the hash table, 944 as ELEMENT and the table entry may share a call argument 945 vector which will be freed during removal. */ 946 if (dump_file && (dump_flags & TDF_DETAILS)) 947 { 948 fprintf (dump_file, "<<<< "); 949 print_expr_hash_elt (dump_file, victim); 950 } 951 952 slot = htab_find_slot_with_hash (avail_exprs, 953 victim, victim->hash, NO_INSERT); 954 gcc_assert (slot && *slot == (void *) victim); 955 htab_clear_slot (avail_exprs, slot); 956 } 957 } 958 959 /* Use the source/dest pairs in CONST_AND_COPIES_STACK to restore 960 CONST_AND_COPIES to its original state, stopping when we hit a 961 NULL marker. */ 962 963 static void 964 restore_vars_to_original_value (void) 965 { 966 while (const_and_copies_stack.length () > 0) 967 { 968 tree prev_value, dest; 969 970 dest = const_and_copies_stack.pop (); 971 972 if (dest == NULL) 973 break; 974 975 if (dump_file && (dump_flags & TDF_DETAILS)) 976 { 977 fprintf (dump_file, "<<<< COPY "); 978 print_generic_expr (dump_file, dest, 0); 979 fprintf (dump_file, " = "); 980 print_generic_expr (dump_file, SSA_NAME_VALUE (dest), 0); 981 fprintf (dump_file, "\n"); 982 } 983 984 prev_value = const_and_copies_stack.pop (); 985 set_ssa_name_value (dest, prev_value); 986 } 987 } 988 989 /* A trivial wrapper so that we can present the generic jump 990 threading code with a simple API for simplifying statements. */ 991 static tree 992 simplify_stmt_for_jump_threading (gimple stmt, 993 gimple within_stmt ATTRIBUTE_UNUSED) 994 { 995 return lookup_avail_expr (stmt, false); 996 } 997 998 /* Wrapper for common code to attempt to thread an edge. For example, 999 it handles lazily building the dummy condition and the bookkeeping 1000 when jump threading is successful. */ 1001 1002 static void 1003 dom_thread_across_edge (struct dom_walk_data *walk_data, edge e) 1004 { 1005 if (! walk_data->global_data) 1006 { 1007 gimple dummy_cond = 1008 gimple_build_cond (NE_EXPR, 1009 integer_zero_node, integer_zero_node, 1010 NULL, NULL); 1011 walk_data->global_data = dummy_cond; 1012 } 1013 1014 thread_across_edge ((gimple) walk_data->global_data, e, false, 1015 &const_and_copies_stack, 1016 simplify_stmt_for_jump_threading); 1017 } 1018 1019 /* PHI nodes can create equivalences too. 1020 1021 Ignoring any alternatives which are the same as the result, if 1022 all the alternatives are equal, then the PHI node creates an 1023 equivalence. */ 1024 1025 static void 1026 record_equivalences_from_phis (basic_block bb) 1027 { 1028 gimple_stmt_iterator gsi; 1029 1030 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1031 { 1032 gimple phi = gsi_stmt (gsi); 1033 1034 tree lhs = gimple_phi_result (phi); 1035 tree rhs = NULL; 1036 size_t i; 1037 1038 for (i = 0; i < gimple_phi_num_args (phi); i++) 1039 { 1040 tree t = gimple_phi_arg_def (phi, i); 1041 1042 /* Ignore alternatives which are the same as our LHS. Since 1043 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we 1044 can simply compare pointers. */ 1045 if (lhs == t) 1046 continue; 1047 1048 /* If we have not processed an alternative yet, then set 1049 RHS to this alternative. */ 1050 if (rhs == NULL) 1051 rhs = t; 1052 /* If we have processed an alternative (stored in RHS), then 1053 see if it is equal to this one. If it isn't, then stop 1054 the search. */ 1055 else if (! operand_equal_for_phi_arg_p (rhs, t)) 1056 break; 1057 } 1058 1059 /* If we had no interesting alternatives, then all the RHS alternatives 1060 must have been the same as LHS. */ 1061 if (!rhs) 1062 rhs = lhs; 1063 1064 /* If we managed to iterate through each PHI alternative without 1065 breaking out of the loop, then we have a PHI which may create 1066 a useful equivalence. We do not need to record unwind data for 1067 this, since this is a true assignment and not an equivalence 1068 inferred from a comparison. All uses of this ssa name are dominated 1069 by this assignment, so unwinding just costs time and space. */ 1070 if (i == gimple_phi_num_args (phi) && may_propagate_copy (lhs, rhs)) 1071 set_ssa_name_value (lhs, rhs); 1072 } 1073 } 1074 1075 /* Ignoring loop backedges, if BB has precisely one incoming edge then 1076 return that edge. Otherwise return NULL. */ 1077 static edge 1078 single_incoming_edge_ignoring_loop_edges (basic_block bb) 1079 { 1080 edge retval = NULL; 1081 edge e; 1082 edge_iterator ei; 1083 1084 FOR_EACH_EDGE (e, ei, bb->preds) 1085 { 1086 /* A loop back edge can be identified by the destination of 1087 the edge dominating the source of the edge. */ 1088 if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest)) 1089 continue; 1090 1091 /* If we have already seen a non-loop edge, then we must have 1092 multiple incoming non-loop edges and thus we return NULL. */ 1093 if (retval) 1094 return NULL; 1095 1096 /* This is the first non-loop incoming edge we have found. Record 1097 it. */ 1098 retval = e; 1099 } 1100 1101 return retval; 1102 } 1103 1104 /* Record any equivalences created by the incoming edge to BB. If BB 1105 has more than one incoming edge, then no equivalence is created. */ 1106 1107 static void 1108 record_equivalences_from_incoming_edge (basic_block bb) 1109 { 1110 edge e; 1111 basic_block parent; 1112 struct edge_info *edge_info; 1113 1114 /* If our parent block ended with a control statement, then we may be 1115 able to record some equivalences based on which outgoing edge from 1116 the parent was followed. */ 1117 parent = get_immediate_dominator (CDI_DOMINATORS, bb); 1118 1119 e = single_incoming_edge_ignoring_loop_edges (bb); 1120 1121 /* If we had a single incoming edge from our parent block, then enter 1122 any data associated with the edge into our tables. */ 1123 if (e && e->src == parent) 1124 { 1125 unsigned int i; 1126 1127 edge_info = (struct edge_info *) e->aux; 1128 1129 if (edge_info) 1130 { 1131 tree lhs = edge_info->lhs; 1132 tree rhs = edge_info->rhs; 1133 cond_equivalence *eq; 1134 1135 if (lhs) 1136 record_equality (lhs, rhs); 1137 1138 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i) 1139 record_cond (eq); 1140 } 1141 } 1142 } 1143 1144 /* Dump SSA statistics on FILE. */ 1145 1146 void 1147 dump_dominator_optimization_stats (FILE *file) 1148 { 1149 fprintf (file, "Total number of statements: %6ld\n\n", 1150 opt_stats.num_stmts); 1151 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n", 1152 opt_stats.num_exprs_considered); 1153 1154 fprintf (file, "\nHash table statistics:\n"); 1155 1156 fprintf (file, " avail_exprs: "); 1157 htab_statistics (file, avail_exprs); 1158 } 1159 1160 1161 /* Dump SSA statistics on stderr. */ 1162 1163 DEBUG_FUNCTION void 1164 debug_dominator_optimization_stats (void) 1165 { 1166 dump_dominator_optimization_stats (stderr); 1167 } 1168 1169 1170 /* Dump statistics for the hash table HTAB. */ 1171 1172 static void 1173 htab_statistics (FILE *file, htab_t htab) 1174 { 1175 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", 1176 (long) htab_size (htab), 1177 (long) htab_elements (htab), 1178 htab_collisions (htab)); 1179 } 1180 1181 1182 /* Enter condition equivalence into the expression hash table. 1183 This indicates that a conditional expression has a known 1184 boolean value. */ 1185 1186 static void 1187 record_cond (cond_equivalence *p) 1188 { 1189 struct expr_hash_elt *element = XCNEW (struct expr_hash_elt); 1190 void **slot; 1191 1192 initialize_hash_element_from_expr (&p->cond, p->value, element); 1193 1194 slot = htab_find_slot_with_hash (avail_exprs, (void *)element, 1195 element->hash, INSERT); 1196 if (*slot == NULL) 1197 { 1198 *slot = (void *) element; 1199 1200 if (dump_file && (dump_flags & TDF_DETAILS)) 1201 { 1202 fprintf (dump_file, "1>>> "); 1203 print_expr_hash_elt (dump_file, element); 1204 } 1205 1206 avail_exprs_stack.safe_push (element); 1207 } 1208 else 1209 free_expr_hash_elt (element); 1210 } 1211 1212 /* Build a cond_equivalence record indicating that the comparison 1213 CODE holds between operands OP0 and OP1 and push it to **P. */ 1214 1215 static void 1216 build_and_record_new_cond (enum tree_code code, 1217 tree op0, tree op1, 1218 vec<cond_equivalence> *p) 1219 { 1220 cond_equivalence c; 1221 struct hashable_expr *cond = &c.cond; 1222 1223 gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison); 1224 1225 cond->type = boolean_type_node; 1226 cond->kind = EXPR_BINARY; 1227 cond->ops.binary.op = code; 1228 cond->ops.binary.opnd0 = op0; 1229 cond->ops.binary.opnd1 = op1; 1230 1231 c.value = boolean_true_node; 1232 p->safe_push (c); 1233 } 1234 1235 /* Record that COND is true and INVERTED is false into the edge information 1236 structure. Also record that any conditions dominated by COND are true 1237 as well. 1238 1239 For example, if a < b is true, then a <= b must also be true. */ 1240 1241 static void 1242 record_conditions (struct edge_info *edge_info, tree cond, tree inverted) 1243 { 1244 tree op0, op1; 1245 cond_equivalence c; 1246 1247 if (!COMPARISON_CLASS_P (cond)) 1248 return; 1249 1250 op0 = TREE_OPERAND (cond, 0); 1251 op1 = TREE_OPERAND (cond, 1); 1252 1253 switch (TREE_CODE (cond)) 1254 { 1255 case LT_EXPR: 1256 case GT_EXPR: 1257 if (FLOAT_TYPE_P (TREE_TYPE (op0))) 1258 { 1259 build_and_record_new_cond (ORDERED_EXPR, op0, op1, 1260 &edge_info->cond_equivalences); 1261 build_and_record_new_cond (LTGT_EXPR, op0, op1, 1262 &edge_info->cond_equivalences); 1263 } 1264 1265 build_and_record_new_cond ((TREE_CODE (cond) == LT_EXPR 1266 ? LE_EXPR : GE_EXPR), 1267 op0, op1, &edge_info->cond_equivalences); 1268 build_and_record_new_cond (NE_EXPR, op0, op1, 1269 &edge_info->cond_equivalences); 1270 break; 1271 1272 case GE_EXPR: 1273 case LE_EXPR: 1274 if (FLOAT_TYPE_P (TREE_TYPE (op0))) 1275 { 1276 build_and_record_new_cond (ORDERED_EXPR, op0, op1, 1277 &edge_info->cond_equivalences); 1278 } 1279 break; 1280 1281 case EQ_EXPR: 1282 if (FLOAT_TYPE_P (TREE_TYPE (op0))) 1283 { 1284 build_and_record_new_cond (ORDERED_EXPR, op0, op1, 1285 &edge_info->cond_equivalences); 1286 } 1287 build_and_record_new_cond (LE_EXPR, op0, op1, 1288 &edge_info->cond_equivalences); 1289 build_and_record_new_cond (GE_EXPR, op0, op1, 1290 &edge_info->cond_equivalences); 1291 break; 1292 1293 case UNORDERED_EXPR: 1294 build_and_record_new_cond (NE_EXPR, op0, op1, 1295 &edge_info->cond_equivalences); 1296 build_and_record_new_cond (UNLE_EXPR, op0, op1, 1297 &edge_info->cond_equivalences); 1298 build_and_record_new_cond (UNGE_EXPR, op0, op1, 1299 &edge_info->cond_equivalences); 1300 build_and_record_new_cond (UNEQ_EXPR, op0, op1, 1301 &edge_info->cond_equivalences); 1302 build_and_record_new_cond (UNLT_EXPR, op0, op1, 1303 &edge_info->cond_equivalences); 1304 build_and_record_new_cond (UNGT_EXPR, op0, op1, 1305 &edge_info->cond_equivalences); 1306 break; 1307 1308 case UNLT_EXPR: 1309 case UNGT_EXPR: 1310 build_and_record_new_cond ((TREE_CODE (cond) == UNLT_EXPR 1311 ? UNLE_EXPR : UNGE_EXPR), 1312 op0, op1, &edge_info->cond_equivalences); 1313 build_and_record_new_cond (NE_EXPR, op0, op1, 1314 &edge_info->cond_equivalences); 1315 break; 1316 1317 case UNEQ_EXPR: 1318 build_and_record_new_cond (UNLE_EXPR, op0, op1, 1319 &edge_info->cond_equivalences); 1320 build_and_record_new_cond (UNGE_EXPR, op0, op1, 1321 &edge_info->cond_equivalences); 1322 break; 1323 1324 case LTGT_EXPR: 1325 build_and_record_new_cond (NE_EXPR, op0, op1, 1326 &edge_info->cond_equivalences); 1327 build_and_record_new_cond (ORDERED_EXPR, op0, op1, 1328 &edge_info->cond_equivalences); 1329 break; 1330 1331 default: 1332 break; 1333 } 1334 1335 /* Now store the original true and false conditions into the first 1336 two slots. */ 1337 initialize_expr_from_cond (cond, &c.cond); 1338 c.value = boolean_true_node; 1339 edge_info->cond_equivalences.safe_push (c); 1340 1341 /* It is possible for INVERTED to be the negation of a comparison, 1342 and not a valid RHS or GIMPLE_COND condition. This happens because 1343 invert_truthvalue may return such an expression when asked to invert 1344 a floating-point comparison. These comparisons are not assumed to 1345 obey the trichotomy law. */ 1346 initialize_expr_from_cond (inverted, &c.cond); 1347 c.value = boolean_false_node; 1348 edge_info->cond_equivalences.safe_push (c); 1349 } 1350 1351 /* A helper function for record_const_or_copy and record_equality. 1352 Do the work of recording the value and undo info. */ 1353 1354 static void 1355 record_const_or_copy_1 (tree x, tree y, tree prev_x) 1356 { 1357 set_ssa_name_value (x, y); 1358 1359 if (dump_file && (dump_flags & TDF_DETAILS)) 1360 { 1361 fprintf (dump_file, "0>>> COPY "); 1362 print_generic_expr (dump_file, x, 0); 1363 fprintf (dump_file, " = "); 1364 print_generic_expr (dump_file, y, 0); 1365 fprintf (dump_file, "\n"); 1366 } 1367 1368 const_and_copies_stack.reserve (2); 1369 const_and_copies_stack.quick_push (prev_x); 1370 const_and_copies_stack.quick_push (x); 1371 } 1372 1373 /* Return the loop depth of the basic block of the defining statement of X. 1374 This number should not be treated as absolutely correct because the loop 1375 information may not be completely up-to-date when dom runs. However, it 1376 will be relatively correct, and as more passes are taught to keep loop info 1377 up to date, the result will become more and more accurate. */ 1378 1379 int 1380 loop_depth_of_name (tree x) 1381 { 1382 gimple defstmt; 1383 basic_block defbb; 1384 1385 /* If it's not an SSA_NAME, we have no clue where the definition is. */ 1386 if (TREE_CODE (x) != SSA_NAME) 1387 return 0; 1388 1389 /* Otherwise return the loop depth of the defining statement's bb. 1390 Note that there may not actually be a bb for this statement, if the 1391 ssa_name is live on entry. */ 1392 defstmt = SSA_NAME_DEF_STMT (x); 1393 defbb = gimple_bb (defstmt); 1394 if (!defbb) 1395 return 0; 1396 1397 return bb_loop_depth (defbb); 1398 } 1399 1400 /* Record that X is equal to Y in const_and_copies. Record undo 1401 information in the block-local vector. */ 1402 1403 static void 1404 record_const_or_copy (tree x, tree y) 1405 { 1406 tree prev_x = SSA_NAME_VALUE (x); 1407 1408 gcc_assert (TREE_CODE (x) == SSA_NAME); 1409 1410 if (TREE_CODE (y) == SSA_NAME) 1411 { 1412 tree tmp = SSA_NAME_VALUE (y); 1413 if (tmp) 1414 y = tmp; 1415 } 1416 1417 record_const_or_copy_1 (x, y, prev_x); 1418 } 1419 1420 /* Similarly, but assume that X and Y are the two operands of an EQ_EXPR. 1421 This constrains the cases in which we may treat this as assignment. */ 1422 1423 static void 1424 record_equality (tree x, tree y) 1425 { 1426 tree prev_x = NULL, prev_y = NULL; 1427 1428 if (TREE_CODE (x) == SSA_NAME) 1429 prev_x = SSA_NAME_VALUE (x); 1430 if (TREE_CODE (y) == SSA_NAME) 1431 prev_y = SSA_NAME_VALUE (y); 1432 1433 /* If one of the previous values is invariant, or invariant in more loops 1434 (by depth), then use that. 1435 Otherwise it doesn't matter which value we choose, just so 1436 long as we canonicalize on one value. */ 1437 if (is_gimple_min_invariant (y)) 1438 ; 1439 else if (is_gimple_min_invariant (x) 1440 || (loop_depth_of_name (x) <= loop_depth_of_name (y))) 1441 prev_x = x, x = y, y = prev_x, prev_x = prev_y; 1442 else if (prev_x && is_gimple_min_invariant (prev_x)) 1443 x = y, y = prev_x, prev_x = prev_y; 1444 else if (prev_y) 1445 y = prev_y; 1446 1447 /* After the swapping, we must have one SSA_NAME. */ 1448 if (TREE_CODE (x) != SSA_NAME) 1449 return; 1450 1451 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a 1452 variable compared against zero. If we're honoring signed zeros, 1453 then we cannot record this value unless we know that the value is 1454 nonzero. */ 1455 if (HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (x))) 1456 && (TREE_CODE (y) != REAL_CST 1457 || REAL_VALUES_EQUAL (dconst0, TREE_REAL_CST (y)))) 1458 return; 1459 1460 record_const_or_copy_1 (x, y, prev_x); 1461 } 1462 1463 /* Returns true when STMT is a simple iv increment. It detects the 1464 following situation: 1465 1466 i_1 = phi (..., i_2) 1467 i_2 = i_1 +/- ... */ 1468 1469 bool 1470 simple_iv_increment_p (gimple stmt) 1471 { 1472 enum tree_code code; 1473 tree lhs, preinc; 1474 gimple phi; 1475 size_t i; 1476 1477 if (gimple_code (stmt) != GIMPLE_ASSIGN) 1478 return false; 1479 1480 lhs = gimple_assign_lhs (stmt); 1481 if (TREE_CODE (lhs) != SSA_NAME) 1482 return false; 1483 1484 code = gimple_assign_rhs_code (stmt); 1485 if (code != PLUS_EXPR 1486 && code != MINUS_EXPR 1487 && code != POINTER_PLUS_EXPR) 1488 return false; 1489 1490 preinc = gimple_assign_rhs1 (stmt); 1491 if (TREE_CODE (preinc) != SSA_NAME) 1492 return false; 1493 1494 phi = SSA_NAME_DEF_STMT (preinc); 1495 if (gimple_code (phi) != GIMPLE_PHI) 1496 return false; 1497 1498 for (i = 0; i < gimple_phi_num_args (phi); i++) 1499 if (gimple_phi_arg_def (phi, i) == lhs) 1500 return true; 1501 1502 return false; 1503 } 1504 1505 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current 1506 known value for that SSA_NAME (or NULL if no value is known). 1507 1508 Propagate values from CONST_AND_COPIES into the PHI nodes of the 1509 successors of BB. */ 1510 1511 static void 1512 cprop_into_successor_phis (basic_block bb) 1513 { 1514 edge e; 1515 edge_iterator ei; 1516 1517 FOR_EACH_EDGE (e, ei, bb->succs) 1518 { 1519 int indx; 1520 gimple_stmt_iterator gsi; 1521 1522 /* If this is an abnormal edge, then we do not want to copy propagate 1523 into the PHI alternative associated with this edge. */ 1524 if (e->flags & EDGE_ABNORMAL) 1525 continue; 1526 1527 gsi = gsi_start_phis (e->dest); 1528 if (gsi_end_p (gsi)) 1529 continue; 1530 1531 indx = e->dest_idx; 1532 for ( ; !gsi_end_p (gsi); gsi_next (&gsi)) 1533 { 1534 tree new_val; 1535 use_operand_p orig_p; 1536 tree orig_val; 1537 gimple phi = gsi_stmt (gsi); 1538 1539 /* The alternative may be associated with a constant, so verify 1540 it is an SSA_NAME before doing anything with it. */ 1541 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx); 1542 orig_val = get_use_from_ptr (orig_p); 1543 if (TREE_CODE (orig_val) != SSA_NAME) 1544 continue; 1545 1546 /* If we have *ORIG_P in our constant/copy table, then replace 1547 ORIG_P with its value in our constant/copy table. */ 1548 new_val = SSA_NAME_VALUE (orig_val); 1549 if (new_val 1550 && new_val != orig_val 1551 && (TREE_CODE (new_val) == SSA_NAME 1552 || is_gimple_min_invariant (new_val)) 1553 && may_propagate_copy (orig_val, new_val)) 1554 propagate_value (orig_p, new_val); 1555 } 1556 } 1557 } 1558 1559 /* We have finished optimizing BB, record any information implied by 1560 taking a specific outgoing edge from BB. */ 1561 1562 static void 1563 record_edge_info (basic_block bb) 1564 { 1565 gimple_stmt_iterator gsi = gsi_last_bb (bb); 1566 struct edge_info *edge_info; 1567 1568 if (! gsi_end_p (gsi)) 1569 { 1570 gimple stmt = gsi_stmt (gsi); 1571 location_t loc = gimple_location (stmt); 1572 1573 if (gimple_code (stmt) == GIMPLE_SWITCH) 1574 { 1575 tree index = gimple_switch_index (stmt); 1576 1577 if (TREE_CODE (index) == SSA_NAME) 1578 { 1579 int i; 1580 int n_labels = gimple_switch_num_labels (stmt); 1581 tree *info = XCNEWVEC (tree, last_basic_block); 1582 edge e; 1583 edge_iterator ei; 1584 1585 for (i = 0; i < n_labels; i++) 1586 { 1587 tree label = gimple_switch_label (stmt, i); 1588 basic_block target_bb = label_to_block (CASE_LABEL (label)); 1589 if (CASE_HIGH (label) 1590 || !CASE_LOW (label) 1591 || info[target_bb->index]) 1592 info[target_bb->index] = error_mark_node; 1593 else 1594 info[target_bb->index] = label; 1595 } 1596 1597 FOR_EACH_EDGE (e, ei, bb->succs) 1598 { 1599 basic_block target_bb = e->dest; 1600 tree label = info[target_bb->index]; 1601 1602 if (label != NULL && label != error_mark_node) 1603 { 1604 tree x = fold_convert_loc (loc, TREE_TYPE (index), 1605 CASE_LOW (label)); 1606 edge_info = allocate_edge_info (e); 1607 edge_info->lhs = index; 1608 edge_info->rhs = x; 1609 } 1610 } 1611 free (info); 1612 } 1613 } 1614 1615 /* A COND_EXPR may create equivalences too. */ 1616 if (gimple_code (stmt) == GIMPLE_COND) 1617 { 1618 edge true_edge; 1619 edge false_edge; 1620 1621 tree op0 = gimple_cond_lhs (stmt); 1622 tree op1 = gimple_cond_rhs (stmt); 1623 enum tree_code code = gimple_cond_code (stmt); 1624 1625 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 1626 1627 /* Special case comparing booleans against a constant as we 1628 know the value of OP0 on both arms of the branch. i.e., we 1629 can record an equivalence for OP0 rather than COND. */ 1630 if ((code == EQ_EXPR || code == NE_EXPR) 1631 && TREE_CODE (op0) == SSA_NAME 1632 && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE 1633 && is_gimple_min_invariant (op1)) 1634 { 1635 if (code == EQ_EXPR) 1636 { 1637 edge_info = allocate_edge_info (true_edge); 1638 edge_info->lhs = op0; 1639 edge_info->rhs = (integer_zerop (op1) 1640 ? boolean_false_node 1641 : boolean_true_node); 1642 1643 edge_info = allocate_edge_info (false_edge); 1644 edge_info->lhs = op0; 1645 edge_info->rhs = (integer_zerop (op1) 1646 ? boolean_true_node 1647 : boolean_false_node); 1648 } 1649 else 1650 { 1651 edge_info = allocate_edge_info (true_edge); 1652 edge_info->lhs = op0; 1653 edge_info->rhs = (integer_zerop (op1) 1654 ? boolean_true_node 1655 : boolean_false_node); 1656 1657 edge_info = allocate_edge_info (false_edge); 1658 edge_info->lhs = op0; 1659 edge_info->rhs = (integer_zerop (op1) 1660 ? boolean_false_node 1661 : boolean_true_node); 1662 } 1663 } 1664 else if (is_gimple_min_invariant (op0) 1665 && (TREE_CODE (op1) == SSA_NAME 1666 || is_gimple_min_invariant (op1))) 1667 { 1668 tree cond = build2 (code, boolean_type_node, op0, op1); 1669 tree inverted = invert_truthvalue_loc (loc, cond); 1670 bool can_infer_simple_equiv 1671 = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op0))) 1672 && real_zerop (op0)); 1673 struct edge_info *edge_info; 1674 1675 edge_info = allocate_edge_info (true_edge); 1676 record_conditions (edge_info, cond, inverted); 1677 1678 if (can_infer_simple_equiv && code == EQ_EXPR) 1679 { 1680 edge_info->lhs = op1; 1681 edge_info->rhs = op0; 1682 } 1683 1684 edge_info = allocate_edge_info (false_edge); 1685 record_conditions (edge_info, inverted, cond); 1686 1687 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) 1688 { 1689 edge_info->lhs = op1; 1690 edge_info->rhs = op0; 1691 } 1692 } 1693 1694 else if (TREE_CODE (op0) == SSA_NAME 1695 && (TREE_CODE (op1) == SSA_NAME 1696 || is_gimple_min_invariant (op1))) 1697 { 1698 tree cond = build2 (code, boolean_type_node, op0, op1); 1699 tree inverted = invert_truthvalue_loc (loc, cond); 1700 bool can_infer_simple_equiv 1701 = !(HONOR_SIGNED_ZEROS (TYPE_MODE (TREE_TYPE (op1))) 1702 && (TREE_CODE (op1) == SSA_NAME || real_zerop (op1))); 1703 struct edge_info *edge_info; 1704 1705 edge_info = allocate_edge_info (true_edge); 1706 record_conditions (edge_info, cond, inverted); 1707 1708 if (can_infer_simple_equiv && code == EQ_EXPR) 1709 { 1710 edge_info->lhs = op0; 1711 edge_info->rhs = op1; 1712 } 1713 1714 edge_info = allocate_edge_info (false_edge); 1715 record_conditions (edge_info, inverted, cond); 1716 1717 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) 1718 { 1719 edge_info->lhs = op0; 1720 edge_info->rhs = op1; 1721 } 1722 } 1723 } 1724 1725 /* ??? TRUTH_NOT_EXPR can create an equivalence too. */ 1726 } 1727 } 1728 1729 static void 1730 dom_opt_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, 1731 basic_block bb) 1732 { 1733 gimple_stmt_iterator gsi; 1734 1735 if (dump_file && (dump_flags & TDF_DETAILS)) 1736 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); 1737 1738 /* Push a marker on the stacks of local information so that we know how 1739 far to unwind when we finalize this block. */ 1740 avail_exprs_stack.safe_push (NULL); 1741 const_and_copies_stack.safe_push (NULL_TREE); 1742 1743 record_equivalences_from_incoming_edge (bb); 1744 1745 /* PHI nodes can create equivalences too. */ 1746 record_equivalences_from_phis (bb); 1747 1748 /* Create equivalences from redundant PHIs. PHIs are only truly 1749 redundant when they exist in the same block, so push another 1750 marker and unwind right afterwards. */ 1751 avail_exprs_stack.safe_push (NULL); 1752 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1753 eliminate_redundant_computations (&gsi); 1754 remove_local_expressions_from_table (); 1755 1756 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1757 optimize_stmt (bb, gsi); 1758 1759 /* Now prepare to process dominated blocks. */ 1760 record_edge_info (bb); 1761 cprop_into_successor_phis (bb); 1762 } 1763 1764 /* We have finished processing the dominator children of BB, perform 1765 any finalization actions in preparation for leaving this node in 1766 the dominator tree. */ 1767 1768 static void 1769 dom_opt_leave_block (struct dom_walk_data *walk_data, basic_block bb) 1770 { 1771 gimple last; 1772 1773 /* If we have an outgoing edge to a block with multiple incoming and 1774 outgoing edges, then we may be able to thread the edge, i.e., we 1775 may be able to statically determine which of the outgoing edges 1776 will be traversed when the incoming edge from BB is traversed. */ 1777 if (single_succ_p (bb) 1778 && (single_succ_edge (bb)->flags & EDGE_ABNORMAL) == 0 1779 && potentially_threadable_block (single_succ (bb))) 1780 { 1781 /* Push a marker on the stack, which thread_across_edge expects 1782 and will remove. */ 1783 const_and_copies_stack.safe_push (NULL_TREE); 1784 dom_thread_across_edge (walk_data, single_succ_edge (bb)); 1785 } 1786 else if ((last = last_stmt (bb)) 1787 && gimple_code (last) == GIMPLE_COND 1788 && EDGE_COUNT (bb->succs) == 2 1789 && (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL) == 0 1790 && (EDGE_SUCC (bb, 1)->flags & EDGE_ABNORMAL) == 0) 1791 { 1792 edge true_edge, false_edge; 1793 1794 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 1795 1796 /* Only try to thread the edge if it reaches a target block with 1797 more than one predecessor and more than one successor. */ 1798 if (potentially_threadable_block (true_edge->dest)) 1799 { 1800 struct edge_info *edge_info; 1801 unsigned int i; 1802 1803 /* Push a marker onto the available expression stack so that we 1804 unwind any expressions related to the TRUE arm before processing 1805 the false arm below. */ 1806 avail_exprs_stack.safe_push (NULL); 1807 const_and_copies_stack.safe_push (NULL_TREE); 1808 1809 edge_info = (struct edge_info *) true_edge->aux; 1810 1811 /* If we have info associated with this edge, record it into 1812 our equivalence tables. */ 1813 if (edge_info) 1814 { 1815 cond_equivalence *eq; 1816 tree lhs = edge_info->lhs; 1817 tree rhs = edge_info->rhs; 1818 1819 /* If we have a simple NAME = VALUE equivalence, record it. */ 1820 if (lhs && TREE_CODE (lhs) == SSA_NAME) 1821 record_const_or_copy (lhs, rhs); 1822 1823 /* If we have 0 = COND or 1 = COND equivalences, record them 1824 into our expression hash tables. */ 1825 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i) 1826 record_cond (eq); 1827 } 1828 1829 dom_thread_across_edge (walk_data, true_edge); 1830 1831 /* And restore the various tables to their state before 1832 we threaded this edge. */ 1833 remove_local_expressions_from_table (); 1834 } 1835 1836 /* Similarly for the ELSE arm. */ 1837 if (potentially_threadable_block (false_edge->dest)) 1838 { 1839 struct edge_info *edge_info; 1840 unsigned int i; 1841 1842 const_and_copies_stack.safe_push (NULL_TREE); 1843 edge_info = (struct edge_info *) false_edge->aux; 1844 1845 /* If we have info associated with this edge, record it into 1846 our equivalence tables. */ 1847 if (edge_info) 1848 { 1849 cond_equivalence *eq; 1850 tree lhs = edge_info->lhs; 1851 tree rhs = edge_info->rhs; 1852 1853 /* If we have a simple NAME = VALUE equivalence, record it. */ 1854 if (lhs && TREE_CODE (lhs) == SSA_NAME) 1855 record_const_or_copy (lhs, rhs); 1856 1857 /* If we have 0 = COND or 1 = COND equivalences, record them 1858 into our expression hash tables. */ 1859 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i) 1860 record_cond (eq); 1861 } 1862 1863 /* Now thread the edge. */ 1864 dom_thread_across_edge (walk_data, false_edge); 1865 1866 /* No need to remove local expressions from our tables 1867 or restore vars to their original value as that will 1868 be done immediately below. */ 1869 } 1870 } 1871 1872 remove_local_expressions_from_table (); 1873 restore_vars_to_original_value (); 1874 } 1875 1876 /* Search for redundant computations in STMT. If any are found, then 1877 replace them with the variable holding the result of the computation. 1878 1879 If safe, record this expression into the available expression hash 1880 table. */ 1881 1882 static void 1883 eliminate_redundant_computations (gimple_stmt_iterator* gsi) 1884 { 1885 tree expr_type; 1886 tree cached_lhs; 1887 tree def; 1888 bool insert = true; 1889 bool assigns_var_p = false; 1890 1891 gimple stmt = gsi_stmt (*gsi); 1892 1893 if (gimple_code (stmt) == GIMPLE_PHI) 1894 def = gimple_phi_result (stmt); 1895 else 1896 def = gimple_get_lhs (stmt); 1897 1898 /* Certain expressions on the RHS can be optimized away, but can not 1899 themselves be entered into the hash tables. */ 1900 if (! def 1901 || TREE_CODE (def) != SSA_NAME 1902 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) 1903 || gimple_vdef (stmt) 1904 /* Do not record equivalences for increments of ivs. This would create 1905 overlapping live ranges for a very questionable gain. */ 1906 || simple_iv_increment_p (stmt)) 1907 insert = false; 1908 1909 /* Check if the expression has been computed before. */ 1910 cached_lhs = lookup_avail_expr (stmt, insert); 1911 1912 opt_stats.num_exprs_considered++; 1913 1914 /* Get the type of the expression we are trying to optimize. */ 1915 if (is_gimple_assign (stmt)) 1916 { 1917 expr_type = TREE_TYPE (gimple_assign_lhs (stmt)); 1918 assigns_var_p = true; 1919 } 1920 else if (gimple_code (stmt) == GIMPLE_COND) 1921 expr_type = boolean_type_node; 1922 else if (is_gimple_call (stmt)) 1923 { 1924 gcc_assert (gimple_call_lhs (stmt)); 1925 expr_type = TREE_TYPE (gimple_call_lhs (stmt)); 1926 assigns_var_p = true; 1927 } 1928 else if (gimple_code (stmt) == GIMPLE_SWITCH) 1929 expr_type = TREE_TYPE (gimple_switch_index (stmt)); 1930 else if (gimple_code (stmt) == GIMPLE_PHI) 1931 /* We can't propagate into a phi, so the logic below doesn't apply. 1932 Instead record an equivalence between the cached LHS and the 1933 PHI result of this statement, provided they are in the same block. 1934 This should be sufficient to kill the redundant phi. */ 1935 { 1936 if (def && cached_lhs) 1937 record_const_or_copy (def, cached_lhs); 1938 return; 1939 } 1940 else 1941 gcc_unreachable (); 1942 1943 if (!cached_lhs) 1944 return; 1945 1946 /* It is safe to ignore types here since we have already done 1947 type checking in the hashing and equality routines. In fact 1948 type checking here merely gets in the way of constant 1949 propagation. Also, make sure that it is safe to propagate 1950 CACHED_LHS into the expression in STMT. */ 1951 if ((TREE_CODE (cached_lhs) != SSA_NAME 1952 && (assigns_var_p 1953 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))) 1954 || may_propagate_copy_into_stmt (stmt, cached_lhs)) 1955 { 1956 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME 1957 || is_gimple_min_invariant (cached_lhs)); 1958 1959 if (dump_file && (dump_flags & TDF_DETAILS)) 1960 { 1961 fprintf (dump_file, " Replaced redundant expr '"); 1962 print_gimple_expr (dump_file, stmt, 0, dump_flags); 1963 fprintf (dump_file, "' with '"); 1964 print_generic_expr (dump_file, cached_lhs, dump_flags); 1965 fprintf (dump_file, "'\n"); 1966 } 1967 1968 opt_stats.num_re++; 1969 1970 if (assigns_var_p 1971 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))) 1972 cached_lhs = fold_convert (expr_type, cached_lhs); 1973 1974 propagate_tree_value_into_stmt (gsi, cached_lhs); 1975 1976 /* Since it is always necessary to mark the result as modified, 1977 perhaps we should move this into propagate_tree_value_into_stmt 1978 itself. */ 1979 gimple_set_modified (gsi_stmt (*gsi), true); 1980 } 1981 } 1982 1983 /* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either 1984 the available expressions table or the const_and_copies table. 1985 Detect and record those equivalences. */ 1986 /* We handle only very simple copy equivalences here. The heavy 1987 lifing is done by eliminate_redundant_computations. */ 1988 1989 static void 1990 record_equivalences_from_stmt (gimple stmt, int may_optimize_p) 1991 { 1992 tree lhs; 1993 enum tree_code lhs_code; 1994 1995 gcc_assert (is_gimple_assign (stmt)); 1996 1997 lhs = gimple_assign_lhs (stmt); 1998 lhs_code = TREE_CODE (lhs); 1999 2000 if (lhs_code == SSA_NAME 2001 && gimple_assign_single_p (stmt)) 2002 { 2003 tree rhs = gimple_assign_rhs1 (stmt); 2004 2005 /* If the RHS of the assignment is a constant or another variable that 2006 may be propagated, register it in the CONST_AND_COPIES table. We 2007 do not need to record unwind data for this, since this is a true 2008 assignment and not an equivalence inferred from a comparison. All 2009 uses of this ssa name are dominated by this assignment, so unwinding 2010 just costs time and space. */ 2011 if (may_optimize_p 2012 && (TREE_CODE (rhs) == SSA_NAME 2013 || is_gimple_min_invariant (rhs))) 2014 { 2015 if (dump_file && (dump_flags & TDF_DETAILS)) 2016 { 2017 fprintf (dump_file, "==== ASGN "); 2018 print_generic_expr (dump_file, lhs, 0); 2019 fprintf (dump_file, " = "); 2020 print_generic_expr (dump_file, rhs, 0); 2021 fprintf (dump_file, "\n"); 2022 } 2023 2024 set_ssa_name_value (lhs, rhs); 2025 } 2026 } 2027 2028 /* A memory store, even an aliased store, creates a useful 2029 equivalence. By exchanging the LHS and RHS, creating suitable 2030 vops and recording the result in the available expression table, 2031 we may be able to expose more redundant loads. */ 2032 if (!gimple_has_volatile_ops (stmt) 2033 && gimple_references_memory_p (stmt) 2034 && gimple_assign_single_p (stmt) 2035 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME 2036 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) 2037 && !is_gimple_reg (lhs)) 2038 { 2039 tree rhs = gimple_assign_rhs1 (stmt); 2040 gimple new_stmt; 2041 2042 /* Build a new statement with the RHS and LHS exchanged. */ 2043 if (TREE_CODE (rhs) == SSA_NAME) 2044 { 2045 /* NOTE tuples. The call to gimple_build_assign below replaced 2046 a call to build_gimple_modify_stmt, which did not set the 2047 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so 2048 may cause an SSA validation failure, as the LHS may be a 2049 default-initialized name and should have no definition. I'm 2050 a bit dubious of this, as the artificial statement that we 2051 generate here may in fact be ill-formed, but it is simply 2052 used as an internal device in this pass, and never becomes 2053 part of the CFG. */ 2054 gimple defstmt = SSA_NAME_DEF_STMT (rhs); 2055 new_stmt = gimple_build_assign (rhs, lhs); 2056 SSA_NAME_DEF_STMT (rhs) = defstmt; 2057 } 2058 else 2059 new_stmt = gimple_build_assign (rhs, lhs); 2060 2061 gimple_set_vuse (new_stmt, gimple_vdef (stmt)); 2062 2063 /* Finally enter the statement into the available expression 2064 table. */ 2065 lookup_avail_expr (new_stmt, true); 2066 } 2067 } 2068 2069 /* Replace *OP_P in STMT with any known equivalent value for *OP_P from 2070 CONST_AND_COPIES. */ 2071 2072 static void 2073 cprop_operand (gimple stmt, use_operand_p op_p) 2074 { 2075 tree val; 2076 tree op = USE_FROM_PTR (op_p); 2077 2078 /* If the operand has a known constant value or it is known to be a 2079 copy of some other variable, use the value or copy stored in 2080 CONST_AND_COPIES. */ 2081 val = SSA_NAME_VALUE (op); 2082 if (val && val != op) 2083 { 2084 /* Do not replace hard register operands in asm statements. */ 2085 if (gimple_code (stmt) == GIMPLE_ASM 2086 && !may_propagate_copy_into_asm (op)) 2087 return; 2088 2089 /* Certain operands are not allowed to be copy propagated due 2090 to their interaction with exception handling and some GCC 2091 extensions. */ 2092 if (!may_propagate_copy (op, val)) 2093 return; 2094 2095 /* Do not propagate addresses that point to volatiles into memory 2096 stmts without volatile operands. */ 2097 if (POINTER_TYPE_P (TREE_TYPE (val)) 2098 && TYPE_VOLATILE (TREE_TYPE (TREE_TYPE (val))) 2099 && gimple_has_mem_ops (stmt) 2100 && !gimple_has_volatile_ops (stmt)) 2101 return; 2102 2103 /* Do not propagate copies if the propagated value is at a deeper loop 2104 depth than the propagatee. Otherwise, this may move loop variant 2105 variables outside of their loops and prevent coalescing 2106 opportunities. If the value was loop invariant, it will be hoisted 2107 by LICM and exposed for copy propagation. */ 2108 if (loop_depth_of_name (val) > loop_depth_of_name (op)) 2109 return; 2110 2111 /* Do not propagate copies into simple IV increment statements. 2112 See PR23821 for how this can disturb IV analysis. */ 2113 if (TREE_CODE (val) != INTEGER_CST 2114 && simple_iv_increment_p (stmt)) 2115 return; 2116 2117 /* Dump details. */ 2118 if (dump_file && (dump_flags & TDF_DETAILS)) 2119 { 2120 fprintf (dump_file, " Replaced '"); 2121 print_generic_expr (dump_file, op, dump_flags); 2122 fprintf (dump_file, "' with %s '", 2123 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); 2124 print_generic_expr (dump_file, val, dump_flags); 2125 fprintf (dump_file, "'\n"); 2126 } 2127 2128 if (TREE_CODE (val) != SSA_NAME) 2129 opt_stats.num_const_prop++; 2130 else 2131 opt_stats.num_copy_prop++; 2132 2133 propagate_value (op_p, val); 2134 2135 /* And note that we modified this statement. This is now 2136 safe, even if we changed virtual operands since we will 2137 rescan the statement and rewrite its operands again. */ 2138 gimple_set_modified (stmt, true); 2139 } 2140 } 2141 2142 /* CONST_AND_COPIES is a table which maps an SSA_NAME to the current 2143 known value for that SSA_NAME (or NULL if no value is known). 2144 2145 Propagate values from CONST_AND_COPIES into the uses, vuses and 2146 vdef_ops of STMT. */ 2147 2148 static void 2149 cprop_into_stmt (gimple stmt) 2150 { 2151 use_operand_p op_p; 2152 ssa_op_iter iter; 2153 2154 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE) 2155 cprop_operand (stmt, op_p); 2156 } 2157 2158 /* Optimize the statement pointed to by iterator SI. 2159 2160 We try to perform some simplistic global redundancy elimination and 2161 constant propagation: 2162 2163 1- To detect global redundancy, we keep track of expressions that have 2164 been computed in this block and its dominators. If we find that the 2165 same expression is computed more than once, we eliminate repeated 2166 computations by using the target of the first one. 2167 2168 2- Constant values and copy assignments. This is used to do very 2169 simplistic constant and copy propagation. When a constant or copy 2170 assignment is found, we map the value on the RHS of the assignment to 2171 the variable in the LHS in the CONST_AND_COPIES table. */ 2172 2173 static void 2174 optimize_stmt (basic_block bb, gimple_stmt_iterator si) 2175 { 2176 gimple stmt, old_stmt; 2177 bool may_optimize_p; 2178 bool modified_p = false; 2179 2180 old_stmt = stmt = gsi_stmt (si); 2181 2182 if (dump_file && (dump_flags & TDF_DETAILS)) 2183 { 2184 fprintf (dump_file, "Optimizing statement "); 2185 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2186 } 2187 2188 if (gimple_code (stmt) == GIMPLE_COND) 2189 canonicalize_comparison (stmt); 2190 2191 update_stmt_if_modified (stmt); 2192 opt_stats.num_stmts++; 2193 2194 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */ 2195 cprop_into_stmt (stmt); 2196 2197 /* If the statement has been modified with constant replacements, 2198 fold its RHS before checking for redundant computations. */ 2199 if (gimple_modified_p (stmt)) 2200 { 2201 tree rhs = NULL; 2202 2203 /* Try to fold the statement making sure that STMT is kept 2204 up to date. */ 2205 if (fold_stmt (&si)) 2206 { 2207 stmt = gsi_stmt (si); 2208 gimple_set_modified (stmt, true); 2209 2210 if (dump_file && (dump_flags & TDF_DETAILS)) 2211 { 2212 fprintf (dump_file, " Folded to: "); 2213 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2214 } 2215 } 2216 2217 /* We only need to consider cases that can yield a gimple operand. */ 2218 if (gimple_assign_single_p (stmt)) 2219 rhs = gimple_assign_rhs1 (stmt); 2220 else if (gimple_code (stmt) == GIMPLE_GOTO) 2221 rhs = gimple_goto_dest (stmt); 2222 else if (gimple_code (stmt) == GIMPLE_SWITCH) 2223 /* This should never be an ADDR_EXPR. */ 2224 rhs = gimple_switch_index (stmt); 2225 2226 if (rhs && TREE_CODE (rhs) == ADDR_EXPR) 2227 recompute_tree_invariant_for_addr_expr (rhs); 2228 2229 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called, 2230 even if fold_stmt updated the stmt already and thus cleared 2231 gimple_modified_p flag on it. */ 2232 modified_p = true; 2233 } 2234 2235 /* Check for redundant computations. Do this optimization only 2236 for assignments that have no volatile ops and conditionals. */ 2237 may_optimize_p = (!gimple_has_side_effects (stmt) 2238 && (is_gimple_assign (stmt) 2239 || (is_gimple_call (stmt) 2240 && gimple_call_lhs (stmt) != NULL_TREE) 2241 || gimple_code (stmt) == GIMPLE_COND 2242 || gimple_code (stmt) == GIMPLE_SWITCH)); 2243 2244 if (may_optimize_p) 2245 { 2246 if (gimple_code (stmt) == GIMPLE_CALL) 2247 { 2248 /* Resolve __builtin_constant_p. If it hasn't been 2249 folded to integer_one_node by now, it's fairly 2250 certain that the value simply isn't constant. */ 2251 tree callee = gimple_call_fndecl (stmt); 2252 if (callee 2253 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL 2254 && DECL_FUNCTION_CODE (callee) == BUILT_IN_CONSTANT_P) 2255 { 2256 propagate_tree_value_into_stmt (&si, integer_zero_node); 2257 stmt = gsi_stmt (si); 2258 } 2259 } 2260 2261 update_stmt_if_modified (stmt); 2262 eliminate_redundant_computations (&si); 2263 stmt = gsi_stmt (si); 2264 2265 /* Perform simple redundant store elimination. */ 2266 if (gimple_assign_single_p (stmt) 2267 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME) 2268 { 2269 tree lhs = gimple_assign_lhs (stmt); 2270 tree rhs = gimple_assign_rhs1 (stmt); 2271 tree cached_lhs; 2272 gimple new_stmt; 2273 if (TREE_CODE (rhs) == SSA_NAME) 2274 { 2275 tree tem = SSA_NAME_VALUE (rhs); 2276 if (tem) 2277 rhs = tem; 2278 } 2279 /* Build a new statement with the RHS and LHS exchanged. */ 2280 if (TREE_CODE (rhs) == SSA_NAME) 2281 { 2282 gimple defstmt = SSA_NAME_DEF_STMT (rhs); 2283 new_stmt = gimple_build_assign (rhs, lhs); 2284 SSA_NAME_DEF_STMT (rhs) = defstmt; 2285 } 2286 else 2287 new_stmt = gimple_build_assign (rhs, lhs); 2288 gimple_set_vuse (new_stmt, gimple_vuse (stmt)); 2289 cached_lhs = lookup_avail_expr (new_stmt, false); 2290 if (cached_lhs 2291 && rhs == cached_lhs) 2292 { 2293 basic_block bb = gimple_bb (stmt); 2294 unlink_stmt_vdef (stmt); 2295 if (gsi_remove (&si, true)) 2296 { 2297 bitmap_set_bit (need_eh_cleanup, bb->index); 2298 if (dump_file && (dump_flags & TDF_DETAILS)) 2299 fprintf (dump_file, " Flagged to clear EH edges.\n"); 2300 } 2301 release_defs (stmt); 2302 return; 2303 } 2304 } 2305 } 2306 2307 /* Record any additional equivalences created by this statement. */ 2308 if (is_gimple_assign (stmt)) 2309 record_equivalences_from_stmt (stmt, may_optimize_p); 2310 2311 /* If STMT is a COND_EXPR and it was modified, then we may know 2312 where it goes. If that is the case, then mark the CFG as altered. 2313 2314 This will cause us to later call remove_unreachable_blocks and 2315 cleanup_tree_cfg when it is safe to do so. It is not safe to 2316 clean things up here since removal of edges and such can trigger 2317 the removal of PHI nodes, which in turn can release SSA_NAMEs to 2318 the manager. 2319 2320 That's all fine and good, except that once SSA_NAMEs are released 2321 to the manager, we must not call create_ssa_name until all references 2322 to released SSA_NAMEs have been eliminated. 2323 2324 All references to the deleted SSA_NAMEs can not be eliminated until 2325 we remove unreachable blocks. 2326 2327 We can not remove unreachable blocks until after we have completed 2328 any queued jump threading. 2329 2330 We can not complete any queued jump threads until we have taken 2331 appropriate variables out of SSA form. Taking variables out of 2332 SSA form can call create_ssa_name and thus we lose. 2333 2334 Ultimately I suspect we're going to need to change the interface 2335 into the SSA_NAME manager. */ 2336 if (gimple_modified_p (stmt) || modified_p) 2337 { 2338 tree val = NULL; 2339 2340 update_stmt_if_modified (stmt); 2341 2342 if (gimple_code (stmt) == GIMPLE_COND) 2343 val = fold_binary_loc (gimple_location (stmt), 2344 gimple_cond_code (stmt), boolean_type_node, 2345 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); 2346 else if (gimple_code (stmt) == GIMPLE_SWITCH) 2347 val = gimple_switch_index (stmt); 2348 2349 if (val && TREE_CODE (val) == INTEGER_CST && find_taken_edge (bb, val)) 2350 cfg_altered = true; 2351 2352 /* If we simplified a statement in such a way as to be shown that it 2353 cannot trap, update the eh information and the cfg to match. */ 2354 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) 2355 { 2356 bitmap_set_bit (need_eh_cleanup, bb->index); 2357 if (dump_file && (dump_flags & TDF_DETAILS)) 2358 fprintf (dump_file, " Flagged to clear EH edges.\n"); 2359 } 2360 } 2361 } 2362 2363 /* Search for an existing instance of STMT in the AVAIL_EXPRS table. 2364 If found, return its LHS. Otherwise insert STMT in the table and 2365 return NULL_TREE. 2366 2367 Also, when an expression is first inserted in the table, it is also 2368 is also added to AVAIL_EXPRS_STACK, so that it can be removed when 2369 we finish processing this block and its children. */ 2370 2371 static tree 2372 lookup_avail_expr (gimple stmt, bool insert) 2373 { 2374 void **slot; 2375 tree lhs; 2376 tree temp; 2377 struct expr_hash_elt element; 2378 2379 /* Get LHS of phi, assignment, or call; else NULL_TREE. */ 2380 if (gimple_code (stmt) == GIMPLE_PHI) 2381 lhs = gimple_phi_result (stmt); 2382 else 2383 lhs = gimple_get_lhs (stmt); 2384 2385 initialize_hash_element (stmt, lhs, &element); 2386 2387 if (dump_file && (dump_flags & TDF_DETAILS)) 2388 { 2389 fprintf (dump_file, "LKUP "); 2390 print_expr_hash_elt (dump_file, &element); 2391 } 2392 2393 /* Don't bother remembering constant assignments and copy operations. 2394 Constants and copy operations are handled by the constant/copy propagator 2395 in optimize_stmt. */ 2396 if (element.expr.kind == EXPR_SINGLE 2397 && (TREE_CODE (element.expr.ops.single.rhs) == SSA_NAME 2398 || is_gimple_min_invariant (element.expr.ops.single.rhs))) 2399 return NULL_TREE; 2400 2401 /* Finally try to find the expression in the main expression hash table. */ 2402 slot = htab_find_slot_with_hash (avail_exprs, &element, element.hash, 2403 (insert ? INSERT : NO_INSERT)); 2404 if (slot == NULL) 2405 { 2406 free_expr_hash_elt_contents (&element); 2407 return NULL_TREE; 2408 } 2409 else if (*slot == NULL) 2410 { 2411 struct expr_hash_elt *element2 = XNEW (struct expr_hash_elt); 2412 *element2 = element; 2413 element2->stamp = element2; 2414 *slot = (void *) element2; 2415 2416 if (dump_file && (dump_flags & TDF_DETAILS)) 2417 { 2418 fprintf (dump_file, "2>>> "); 2419 print_expr_hash_elt (dump_file, element2); 2420 } 2421 2422 avail_exprs_stack.safe_push (element2); 2423 return NULL_TREE; 2424 } 2425 else 2426 free_expr_hash_elt_contents (&element); 2427 2428 /* Extract the LHS of the assignment so that it can be used as the current 2429 definition of another variable. */ 2430 lhs = ((struct expr_hash_elt *)*slot)->lhs; 2431 2432 /* See if the LHS appears in the CONST_AND_COPIES table. If it does, then 2433 use the value from the const_and_copies table. */ 2434 if (TREE_CODE (lhs) == SSA_NAME) 2435 { 2436 temp = SSA_NAME_VALUE (lhs); 2437 if (temp) 2438 lhs = temp; 2439 } 2440 2441 if (dump_file && (dump_flags & TDF_DETAILS)) 2442 { 2443 fprintf (dump_file, "FIND: "); 2444 print_generic_expr (dump_file, lhs, 0); 2445 fprintf (dump_file, "\n"); 2446 } 2447 2448 return lhs; 2449 } 2450 2451 /* Hashing and equality functions for AVAIL_EXPRS. We compute a value number 2452 for expressions using the code of the expression and the SSA numbers of 2453 its operands. */ 2454 2455 static hashval_t 2456 avail_expr_hash (const void *p) 2457 { 2458 gimple stmt = ((const struct expr_hash_elt *)p)->stmt; 2459 const struct hashable_expr *expr = &((const struct expr_hash_elt *)p)->expr; 2460 tree vuse; 2461 hashval_t val = 0; 2462 2463 val = iterative_hash_hashable_expr (expr, val); 2464 2465 /* If the hash table entry is not associated with a statement, then we 2466 can just hash the expression and not worry about virtual operands 2467 and such. */ 2468 if (!stmt) 2469 return val; 2470 2471 /* Add the SSA version numbers of the vuse operand. This is important 2472 because compound variables like arrays are not renamed in the 2473 operands. Rather, the rename is done on the virtual variable 2474 representing all the elements of the array. */ 2475 if ((vuse = gimple_vuse (stmt))) 2476 val = iterative_hash_expr (vuse, val); 2477 2478 return val; 2479 } 2480 2481 static hashval_t 2482 real_avail_expr_hash (const void *p) 2483 { 2484 return ((const struct expr_hash_elt *)p)->hash; 2485 } 2486 2487 static int 2488 avail_expr_eq (const void *p1, const void *p2) 2489 { 2490 gimple stmt1 = ((const struct expr_hash_elt *)p1)->stmt; 2491 const struct hashable_expr *expr1 = &((const struct expr_hash_elt *)p1)->expr; 2492 const struct expr_hash_elt *stamp1 = ((const struct expr_hash_elt *)p1)->stamp; 2493 gimple stmt2 = ((const struct expr_hash_elt *)p2)->stmt; 2494 const struct hashable_expr *expr2 = &((const struct expr_hash_elt *)p2)->expr; 2495 const struct expr_hash_elt *stamp2 = ((const struct expr_hash_elt *)p2)->stamp; 2496 2497 /* This case should apply only when removing entries from the table. */ 2498 if (stamp1 == stamp2) 2499 return true; 2500 2501 /* FIXME tuples: 2502 We add stmts to a hash table and them modify them. To detect the case 2503 that we modify a stmt and then search for it, we assume that the hash 2504 is always modified by that change. 2505 We have to fully check why this doesn't happen on trunk or rewrite 2506 this in a more reliable (and easier to understand) way. */ 2507 if (((const struct expr_hash_elt *)p1)->hash 2508 != ((const struct expr_hash_elt *)p2)->hash) 2509 return false; 2510 2511 /* In case of a collision, both RHS have to be identical and have the 2512 same VUSE operands. */ 2513 if (hashable_expr_equal_p (expr1, expr2) 2514 && types_compatible_p (expr1->type, expr2->type)) 2515 { 2516 /* Note that STMT1 and/or STMT2 may be NULL. */ 2517 return ((stmt1 ? gimple_vuse (stmt1) : NULL_TREE) 2518 == (stmt2 ? gimple_vuse (stmt2) : NULL_TREE)); 2519 } 2520 2521 return false; 2522 } 2523 2524 /* PHI-ONLY copy and constant propagation. This pass is meant to clean 2525 up degenerate PHIs created by or exposed by jump threading. */ 2526 2527 /* Given PHI, return its RHS if the PHI is a degenerate, otherwise return 2528 NULL. */ 2529 2530 tree 2531 degenerate_phi_result (gimple phi) 2532 { 2533 tree lhs = gimple_phi_result (phi); 2534 tree val = NULL; 2535 size_t i; 2536 2537 /* Ignoring arguments which are the same as LHS, if all the remaining 2538 arguments are the same, then the PHI is a degenerate and has the 2539 value of that common argument. */ 2540 for (i = 0; i < gimple_phi_num_args (phi); i++) 2541 { 2542 tree arg = gimple_phi_arg_def (phi, i); 2543 2544 if (arg == lhs) 2545 continue; 2546 else if (!arg) 2547 break; 2548 else if (!val) 2549 val = arg; 2550 else if (arg == val) 2551 continue; 2552 /* We bring in some of operand_equal_p not only to speed things 2553 up, but also to avoid crashing when dereferencing the type of 2554 a released SSA name. */ 2555 else if (TREE_CODE (val) != TREE_CODE (arg) 2556 || TREE_CODE (val) == SSA_NAME 2557 || !operand_equal_p (arg, val, 0)) 2558 break; 2559 } 2560 return (i == gimple_phi_num_args (phi) ? val : NULL); 2561 } 2562 2563 /* Given a statement STMT, which is either a PHI node or an assignment, 2564 remove it from the IL. */ 2565 2566 static void 2567 remove_stmt_or_phi (gimple stmt) 2568 { 2569 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); 2570 2571 if (gimple_code (stmt) == GIMPLE_PHI) 2572 remove_phi_node (&gsi, true); 2573 else 2574 { 2575 gsi_remove (&gsi, true); 2576 release_defs (stmt); 2577 } 2578 } 2579 2580 /* Given a statement STMT, which is either a PHI node or an assignment, 2581 return the "rhs" of the node, in the case of a non-degenerate 2582 phi, NULL is returned. */ 2583 2584 static tree 2585 get_rhs_or_phi_arg (gimple stmt) 2586 { 2587 if (gimple_code (stmt) == GIMPLE_PHI) 2588 return degenerate_phi_result (stmt); 2589 else if (gimple_assign_single_p (stmt)) 2590 return gimple_assign_rhs1 (stmt); 2591 else 2592 gcc_unreachable (); 2593 } 2594 2595 2596 /* Given a statement STMT, which is either a PHI node or an assignment, 2597 return the "lhs" of the node. */ 2598 2599 static tree 2600 get_lhs_or_phi_result (gimple stmt) 2601 { 2602 if (gimple_code (stmt) == GIMPLE_PHI) 2603 return gimple_phi_result (stmt); 2604 else if (is_gimple_assign (stmt)) 2605 return gimple_assign_lhs (stmt); 2606 else 2607 gcc_unreachable (); 2608 } 2609 2610 /* Propagate RHS into all uses of LHS (when possible). 2611 2612 RHS and LHS are derived from STMT, which is passed in solely so 2613 that we can remove it if propagation is successful. 2614 2615 When propagating into a PHI node or into a statement which turns 2616 into a trivial copy or constant initialization, set the 2617 appropriate bit in INTERESTING_NAMEs so that we will visit those 2618 nodes as well in an effort to pick up secondary optimization 2619 opportunities. */ 2620 2621 static void 2622 propagate_rhs_into_lhs (gimple stmt, tree lhs, tree rhs, bitmap interesting_names) 2623 { 2624 /* First verify that propagation is valid and isn't going to move a 2625 loop variant variable outside its loop. */ 2626 if (! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) 2627 && (TREE_CODE (rhs) != SSA_NAME 2628 || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs)) 2629 && may_propagate_copy (lhs, rhs) 2630 && loop_depth_of_name (lhs) >= loop_depth_of_name (rhs)) 2631 { 2632 use_operand_p use_p; 2633 imm_use_iterator iter; 2634 gimple use_stmt; 2635 bool all = true; 2636 2637 /* Dump details. */ 2638 if (dump_file && (dump_flags & TDF_DETAILS)) 2639 { 2640 fprintf (dump_file, " Replacing '"); 2641 print_generic_expr (dump_file, lhs, dump_flags); 2642 fprintf (dump_file, "' with %s '", 2643 (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable")); 2644 print_generic_expr (dump_file, rhs, dump_flags); 2645 fprintf (dump_file, "'\n"); 2646 } 2647 2648 /* Walk over every use of LHS and try to replace the use with RHS. 2649 At this point the only reason why such a propagation would not 2650 be successful would be if the use occurs in an ASM_EXPR. */ 2651 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 2652 { 2653 /* Leave debug stmts alone. If we succeed in propagating 2654 all non-debug uses, we'll drop the DEF, and propagation 2655 into debug stmts will occur then. */ 2656 if (gimple_debug_bind_p (use_stmt)) 2657 continue; 2658 2659 /* It's not always safe to propagate into an ASM_EXPR. */ 2660 if (gimple_code (use_stmt) == GIMPLE_ASM 2661 && ! may_propagate_copy_into_asm (lhs)) 2662 { 2663 all = false; 2664 continue; 2665 } 2666 2667 /* It's not ok to propagate into the definition stmt of RHS. 2668 <bb 9>: 2669 # prephitmp.12_36 = PHI <g_67.1_6(9)> 2670 g_67.1_6 = prephitmp.12_36; 2671 goto <bb 9>; 2672 While this is strictly all dead code we do not want to 2673 deal with this here. */ 2674 if (TREE_CODE (rhs) == SSA_NAME 2675 && SSA_NAME_DEF_STMT (rhs) == use_stmt) 2676 { 2677 all = false; 2678 continue; 2679 } 2680 2681 /* Dump details. */ 2682 if (dump_file && (dump_flags & TDF_DETAILS)) 2683 { 2684 fprintf (dump_file, " Original statement:"); 2685 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); 2686 } 2687 2688 /* Propagate the RHS into this use of the LHS. */ 2689 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 2690 propagate_value (use_p, rhs); 2691 2692 /* Special cases to avoid useless calls into the folding 2693 routines, operand scanning, etc. 2694 2695 Propagation into a PHI may cause the PHI to become 2696 a degenerate, so mark the PHI as interesting. No other 2697 actions are necessary. */ 2698 if (gimple_code (use_stmt) == GIMPLE_PHI) 2699 { 2700 tree result; 2701 2702 /* Dump details. */ 2703 if (dump_file && (dump_flags & TDF_DETAILS)) 2704 { 2705 fprintf (dump_file, " Updated statement:"); 2706 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); 2707 } 2708 2709 result = get_lhs_or_phi_result (use_stmt); 2710 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); 2711 continue; 2712 } 2713 2714 /* From this point onward we are propagating into a 2715 real statement. Folding may (or may not) be possible, 2716 we may expose new operands, expose dead EH edges, 2717 etc. */ 2718 /* NOTE tuples. In the tuples world, fold_stmt_inplace 2719 cannot fold a call that simplifies to a constant, 2720 because the GIMPLE_CALL must be replaced by a 2721 GIMPLE_ASSIGN, and there is no way to effect such a 2722 transformation in-place. We might want to consider 2723 using the more general fold_stmt here. */ 2724 { 2725 gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt); 2726 fold_stmt_inplace (&gsi); 2727 } 2728 2729 /* Sometimes propagation can expose new operands to the 2730 renamer. */ 2731 update_stmt (use_stmt); 2732 2733 /* Dump details. */ 2734 if (dump_file && (dump_flags & TDF_DETAILS)) 2735 { 2736 fprintf (dump_file, " Updated statement:"); 2737 print_gimple_stmt (dump_file, use_stmt, 0, dump_flags); 2738 } 2739 2740 /* If we replaced a variable index with a constant, then 2741 we would need to update the invariant flag for ADDR_EXPRs. */ 2742 if (gimple_assign_single_p (use_stmt) 2743 && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR) 2744 recompute_tree_invariant_for_addr_expr 2745 (gimple_assign_rhs1 (use_stmt)); 2746 2747 /* If we cleaned up EH information from the statement, 2748 mark its containing block as needing EH cleanups. */ 2749 if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt)) 2750 { 2751 bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index); 2752 if (dump_file && (dump_flags & TDF_DETAILS)) 2753 fprintf (dump_file, " Flagged to clear EH edges.\n"); 2754 } 2755 2756 /* Propagation may expose new trivial copy/constant propagation 2757 opportunities. */ 2758 if (gimple_assign_single_p (use_stmt) 2759 && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME 2760 && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME 2761 || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt)))) 2762 { 2763 tree result = get_lhs_or_phi_result (use_stmt); 2764 bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result)); 2765 } 2766 2767 /* Propagation into these nodes may make certain edges in 2768 the CFG unexecutable. We want to identify them as PHI nodes 2769 at the destination of those unexecutable edges may become 2770 degenerates. */ 2771 else if (gimple_code (use_stmt) == GIMPLE_COND 2772 || gimple_code (use_stmt) == GIMPLE_SWITCH 2773 || gimple_code (use_stmt) == GIMPLE_GOTO) 2774 { 2775 tree val; 2776 2777 if (gimple_code (use_stmt) == GIMPLE_COND) 2778 val = fold_binary_loc (gimple_location (use_stmt), 2779 gimple_cond_code (use_stmt), 2780 boolean_type_node, 2781 gimple_cond_lhs (use_stmt), 2782 gimple_cond_rhs (use_stmt)); 2783 else if (gimple_code (use_stmt) == GIMPLE_SWITCH) 2784 val = gimple_switch_index (use_stmt); 2785 else 2786 val = gimple_goto_dest (use_stmt); 2787 2788 if (val && is_gimple_min_invariant (val)) 2789 { 2790 basic_block bb = gimple_bb (use_stmt); 2791 edge te = find_taken_edge (bb, val); 2792 if (!te) 2793 continue; 2794 2795 edge_iterator ei; 2796 edge e; 2797 gimple_stmt_iterator gsi, psi; 2798 2799 /* Remove all outgoing edges except TE. */ 2800 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));) 2801 { 2802 if (e != te) 2803 { 2804 /* Mark all the PHI nodes at the destination of 2805 the unexecutable edge as interesting. */ 2806 for (psi = gsi_start_phis (e->dest); 2807 !gsi_end_p (psi); 2808 gsi_next (&psi)) 2809 { 2810 gimple phi = gsi_stmt (psi); 2811 2812 tree result = gimple_phi_result (phi); 2813 int version = SSA_NAME_VERSION (result); 2814 2815 bitmap_set_bit (interesting_names, version); 2816 } 2817 2818 te->probability += e->probability; 2819 2820 te->count += e->count; 2821 remove_edge (e); 2822 cfg_altered = true; 2823 } 2824 else 2825 ei_next (&ei); 2826 } 2827 2828 gsi = gsi_last_bb (gimple_bb (use_stmt)); 2829 gsi_remove (&gsi, true); 2830 2831 /* And fixup the flags on the single remaining edge. */ 2832 te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); 2833 te->flags &= ~EDGE_ABNORMAL; 2834 te->flags |= EDGE_FALLTHRU; 2835 if (te->probability > REG_BR_PROB_BASE) 2836 te->probability = REG_BR_PROB_BASE; 2837 } 2838 } 2839 } 2840 2841 /* Ensure there is nothing else to do. */ 2842 gcc_assert (!all || has_zero_uses (lhs)); 2843 2844 /* If we were able to propagate away all uses of LHS, then 2845 we can remove STMT. */ 2846 if (all) 2847 remove_stmt_or_phi (stmt); 2848 } 2849 } 2850 2851 /* STMT is either a PHI node (potentially a degenerate PHI node) or 2852 a statement that is a trivial copy or constant initialization. 2853 2854 Attempt to eliminate T by propagating its RHS into all uses of 2855 its LHS. This may in turn set new bits in INTERESTING_NAMES 2856 for nodes we want to revisit later. 2857 2858 All exit paths should clear INTERESTING_NAMES for the result 2859 of STMT. */ 2860 2861 static void 2862 eliminate_const_or_copy (gimple stmt, bitmap interesting_names) 2863 { 2864 tree lhs = get_lhs_or_phi_result (stmt); 2865 tree rhs; 2866 int version = SSA_NAME_VERSION (lhs); 2867 2868 /* If the LHS of this statement or PHI has no uses, then we can 2869 just eliminate it. This can occur if, for example, the PHI 2870 was created by block duplication due to threading and its only 2871 use was in the conditional at the end of the block which was 2872 deleted. */ 2873 if (has_zero_uses (lhs)) 2874 { 2875 bitmap_clear_bit (interesting_names, version); 2876 remove_stmt_or_phi (stmt); 2877 return; 2878 } 2879 2880 /* Get the RHS of the assignment or PHI node if the PHI is a 2881 degenerate. */ 2882 rhs = get_rhs_or_phi_arg (stmt); 2883 if (!rhs) 2884 { 2885 bitmap_clear_bit (interesting_names, version); 2886 return; 2887 } 2888 2889 propagate_rhs_into_lhs (stmt, lhs, rhs, interesting_names); 2890 2891 /* Note that STMT may well have been deleted by now, so do 2892 not access it, instead use the saved version # to clear 2893 T's entry in the worklist. */ 2894 bitmap_clear_bit (interesting_names, version); 2895 } 2896 2897 /* The first phase in degenerate PHI elimination. 2898 2899 Eliminate the degenerate PHIs in BB, then recurse on the 2900 dominator children of BB. */ 2901 2902 static void 2903 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names) 2904 { 2905 gimple_stmt_iterator gsi; 2906 basic_block son; 2907 2908 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 2909 { 2910 gimple phi = gsi_stmt (gsi); 2911 2912 eliminate_const_or_copy (phi, interesting_names); 2913 } 2914 2915 /* Recurse into the dominator children of BB. */ 2916 for (son = first_dom_son (CDI_DOMINATORS, bb); 2917 son; 2918 son = next_dom_son (CDI_DOMINATORS, son)) 2919 eliminate_degenerate_phis_1 (son, interesting_names); 2920 } 2921 2922 2923 /* A very simple pass to eliminate degenerate PHI nodes from the 2924 IL. This is meant to be fast enough to be able to be run several 2925 times in the optimization pipeline. 2926 2927 Certain optimizations, particularly those which duplicate blocks 2928 or remove edges from the CFG can create or expose PHIs which are 2929 trivial copies or constant initializations. 2930 2931 While we could pick up these optimizations in DOM or with the 2932 combination of copy-prop and CCP, those solutions are far too 2933 heavy-weight for our needs. 2934 2935 This implementation has two phases so that we can efficiently 2936 eliminate the first order degenerate PHIs and second order 2937 degenerate PHIs. 2938 2939 The first phase performs a dominator walk to identify and eliminate 2940 the vast majority of the degenerate PHIs. When a degenerate PHI 2941 is identified and eliminated any affected statements or PHIs 2942 are put on a worklist. 2943 2944 The second phase eliminates degenerate PHIs and trivial copies 2945 or constant initializations using the worklist. This is how we 2946 pick up the secondary optimization opportunities with minimal 2947 cost. */ 2948 2949 static unsigned int 2950 eliminate_degenerate_phis (void) 2951 { 2952 bitmap interesting_names; 2953 bitmap interesting_names1; 2954 2955 /* Bitmap of blocks which need EH information updated. We can not 2956 update it on-the-fly as doing so invalidates the dominator tree. */ 2957 need_eh_cleanup = BITMAP_ALLOC (NULL); 2958 2959 /* INTERESTING_NAMES is effectively our worklist, indexed by 2960 SSA_NAME_VERSION. 2961 2962 A set bit indicates that the statement or PHI node which 2963 defines the SSA_NAME should be (re)examined to determine if 2964 it has become a degenerate PHI or trivial const/copy propagation 2965 opportunity. 2966 2967 Experiments have show we generally get better compilation 2968 time behavior with bitmaps rather than sbitmaps. */ 2969 interesting_names = BITMAP_ALLOC (NULL); 2970 interesting_names1 = BITMAP_ALLOC (NULL); 2971 2972 calculate_dominance_info (CDI_DOMINATORS); 2973 cfg_altered = false; 2974 2975 /* First phase. Eliminate degenerate PHIs via a dominator 2976 walk of the CFG. 2977 2978 Experiments have indicated that we generally get better 2979 compile-time behavior by visiting blocks in the first 2980 phase in dominator order. Presumably this is because walking 2981 in dominator order leaves fewer PHIs for later examination 2982 by the worklist phase. */ 2983 eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR, interesting_names); 2984 2985 /* Second phase. Eliminate second order degenerate PHIs as well 2986 as trivial copies or constant initializations identified by 2987 the first phase or this phase. Basically we keep iterating 2988 until our set of INTERESTING_NAMEs is empty. */ 2989 while (!bitmap_empty_p (interesting_names)) 2990 { 2991 unsigned int i; 2992 bitmap_iterator bi; 2993 2994 /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap 2995 changed during the loop. Copy it to another bitmap and 2996 use that. */ 2997 bitmap_copy (interesting_names1, interesting_names); 2998 2999 EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi) 3000 { 3001 tree name = ssa_name (i); 3002 3003 /* Ignore SSA_NAMEs that have been released because 3004 their defining statement was deleted (unreachable). */ 3005 if (name) 3006 eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)), 3007 interesting_names); 3008 } 3009 } 3010 3011 if (cfg_altered) 3012 { 3013 free_dominance_info (CDI_DOMINATORS); 3014 /* If we changed the CFG schedule loops for fixup by cfgcleanup. */ 3015 if (current_loops) 3016 loops_state_set (LOOPS_NEED_FIXUP); 3017 } 3018 3019 /* Propagation of const and copies may make some EH edges dead. Purge 3020 such edges from the CFG as needed. */ 3021 if (!bitmap_empty_p (need_eh_cleanup)) 3022 { 3023 gimple_purge_all_dead_eh_edges (need_eh_cleanup); 3024 BITMAP_FREE (need_eh_cleanup); 3025 } 3026 3027 BITMAP_FREE (interesting_names); 3028 BITMAP_FREE (interesting_names1); 3029 return 0; 3030 } 3031 3032 struct gimple_opt_pass pass_phi_only_cprop = 3033 { 3034 { 3035 GIMPLE_PASS, 3036 "phicprop", /* name */ 3037 OPTGROUP_NONE, /* optinfo_flags */ 3038 gate_dominator, /* gate */ 3039 eliminate_degenerate_phis, /* execute */ 3040 NULL, /* sub */ 3041 NULL, /* next */ 3042 0, /* static_pass_number */ 3043 TV_TREE_PHI_CPROP, /* tv_id */ 3044 PROP_cfg | PROP_ssa, /* properties_required */ 3045 0, /* properties_provided */ 3046 0, /* properties_destroyed */ 3047 0, /* todo_flags_start */ 3048 TODO_cleanup_cfg 3049 | TODO_ggc_collect 3050 | TODO_verify_ssa 3051 | TODO_verify_stmts 3052 | TODO_update_ssa /* todo_flags_finish */ 3053 } 3054 }; 3055