1/* SSA Dominator optimizations for trees 2 Copyright (C) 2001-2022 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "backend.h" 25#include "tree.h" 26#include "gimple.h" 27#include "tree-pass.h" 28#include "ssa.h" 29#include "gimple-pretty-print.h" 30#include "fold-const.h" 31#include "cfganal.h" 32#include "cfgloop.h" 33#include "gimple-fold.h" 34#include "tree-eh.h" 35#include "tree-inline.h" 36#include "gimple-iterator.h" 37#include "tree-cfg.h" 38#include "tree-into-ssa.h" 39#include "domwalk.h" 40#include "tree-ssa-propagate.h" 41#include "tree-ssa-threadupdate.h" 42#include "tree-ssa-scopedtables.h" 43#include "tree-ssa-threadedge.h" 44#include "tree-ssa-dom.h" 45#include "gimplify.h" 46#include "tree-cfgcleanup.h" 47#include "dbgcnt.h" 48#include "alloc-pool.h" 49#include "tree-vrp.h" 50#include "vr-values.h" 51#include "gimple-ssa-evrp-analyze.h" 52#include "alias.h" 53 54/* This file implements optimizations on the dominator tree. */ 55 56/* Structure for recording edge equivalences. 57 58 Computing and storing the edge equivalences instead of creating 59 them on-demand can save significant amounts of time, particularly 60 for pathological cases involving switch statements. 61 62 These structures live for a single iteration of the dominator 63 optimizer in the edge's AUX field. At the end of an iteration we 64 free each of these structures. */ 65class edge_info 66{ 67 public: 68 typedef std::pair <tree, tree> equiv_pair; 69 edge_info (edge); 70 ~edge_info (); 71 72 /* Record a simple LHS = RHS equivalence. This may trigger 73 calls to derive_equivalences. */ 74 void record_simple_equiv (tree, tree); 75 76 /* If traversing this edge creates simple equivalences, we store 77 them as LHS/RHS pairs within this vector. */ 78 vec<equiv_pair> simple_equivalences; 79 80 /* Traversing an edge may also indicate one or more particular conditions 81 are true or false. */ 82 vec<cond_equivalence> cond_equivalences; 83 84 private: 85 /* Derive equivalences by walking the use-def chains. */ 86 void derive_equivalences (tree, tree, int); 87}; 88 89/* Track whether or not we have changed the control flow graph. */ 90static bool cfg_altered; 91 92/* Bitmap of blocks that have had EH statements cleaned. We should 93 remove their dead edges eventually. */ 94static bitmap need_eh_cleanup; 95static vec<gimple *> need_noreturn_fixup; 96 97/* Statistics for dominator optimizations. */ 98struct opt_stats_d 99{ 100 long num_stmts; 101 long num_exprs_considered; 102 long num_re; 103 long num_const_prop; 104 long num_copy_prop; 105}; 106 107static struct opt_stats_d opt_stats; 108 109/* Local functions. */ 110static void record_equality (tree, tree, class const_and_copies *); 111static void record_equivalences_from_phis (basic_block); 112static void record_equivalences_from_incoming_edge (basic_block, 113 class const_and_copies *, 114 class avail_exprs_stack *); 115static void eliminate_redundant_computations (gimple_stmt_iterator *, 116 class const_and_copies *, 117 class avail_exprs_stack *); 118static void record_equivalences_from_stmt (gimple *, int, 119 class avail_exprs_stack *); 120static void dump_dominator_optimization_stats (FILE *file, 121 hash_table<expr_elt_hasher> *); 122 123/* Constructor for EDGE_INFO. An EDGE_INFO instance is always 124 associated with an edge E. */ 125 126edge_info::edge_info (edge e) 127{ 128 /* Free the old one associated with E, if it exists and 129 associate our new object with E. */ 130 free_dom_edge_info (e); 131 e->aux = this; 132 133 /* And initialize the embedded vectors. */ 134 simple_equivalences = vNULL; 135 cond_equivalences = vNULL; 136} 137 138/* Destructor just needs to release the vectors. */ 139 140edge_info::~edge_info (void) 141{ 142 this->cond_equivalences.release (); 143 this->simple_equivalences.release (); 144} 145 146/* NAME is known to have the value VALUE, which must be a constant. 147 148 Walk through its use-def chain to see if there are other equivalences 149 we might be able to derive. 150 151 RECURSION_LIMIT controls how far back we recurse through the use-def 152 chains. */ 153 154void 155edge_info::derive_equivalences (tree name, tree value, int recursion_limit) 156{ 157 if (TREE_CODE (name) != SSA_NAME || TREE_CODE (value) != INTEGER_CST) 158 return; 159 160 /* This records the equivalence for the toplevel object. Do 161 this before checking the recursion limit. */ 162 simple_equivalences.safe_push (equiv_pair (name, value)); 163 164 /* Limit how far up the use-def chains we are willing to walk. */ 165 if (recursion_limit == 0) 166 return; 167 168 /* We can walk up the use-def chains to potentially find more 169 equivalences. */ 170 gimple *def_stmt = SSA_NAME_DEF_STMT (name); 171 if (is_gimple_assign (def_stmt)) 172 { 173 enum tree_code code = gimple_assign_rhs_code (def_stmt); 174 switch (code) 175 { 176 /* If the result of an OR is zero, then its operands are, too. */ 177 case BIT_IOR_EXPR: 178 if (integer_zerop (value)) 179 { 180 tree rhs1 = gimple_assign_rhs1 (def_stmt); 181 tree rhs2 = gimple_assign_rhs2 (def_stmt); 182 183 value = build_zero_cst (TREE_TYPE (rhs1)); 184 derive_equivalences (rhs1, value, recursion_limit - 1); 185 value = build_zero_cst (TREE_TYPE (rhs2)); 186 derive_equivalences (rhs2, value, recursion_limit - 1); 187 } 188 break; 189 190 /* If the result of an AND is nonzero, then its operands are, too. */ 191 case BIT_AND_EXPR: 192 if (!integer_zerop (value)) 193 { 194 tree rhs1 = gimple_assign_rhs1 (def_stmt); 195 tree rhs2 = gimple_assign_rhs2 (def_stmt); 196 197 /* If either operand has a boolean range, then we 198 know its value must be one, otherwise we just know it 199 is nonzero. The former is clearly useful, I haven't 200 seen cases where the latter is helpful yet. */ 201 if (TREE_CODE (rhs1) == SSA_NAME) 202 { 203 if (ssa_name_has_boolean_range (rhs1)) 204 { 205 value = build_one_cst (TREE_TYPE (rhs1)); 206 derive_equivalences (rhs1, value, recursion_limit - 1); 207 } 208 } 209 if (TREE_CODE (rhs2) == SSA_NAME) 210 { 211 if (ssa_name_has_boolean_range (rhs2)) 212 { 213 value = build_one_cst (TREE_TYPE (rhs2)); 214 derive_equivalences (rhs2, value, recursion_limit - 1); 215 } 216 } 217 } 218 break; 219 220 /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was 221 set via a widening type conversion, then we may be able to record 222 additional equivalences. */ 223 case NOP_EXPR: 224 case CONVERT_EXPR: 225 { 226 tree rhs = gimple_assign_rhs1 (def_stmt); 227 tree rhs_type = TREE_TYPE (rhs); 228 if (INTEGRAL_TYPE_P (rhs_type) 229 && (TYPE_PRECISION (TREE_TYPE (name)) 230 >= TYPE_PRECISION (rhs_type)) 231 && int_fits_type_p (value, rhs_type)) 232 derive_equivalences (rhs, 233 fold_convert (rhs_type, value), 234 recursion_limit - 1); 235 break; 236 } 237 238 /* We can invert the operation of these codes trivially if 239 one of the RHS operands is a constant to produce a known 240 value for the other RHS operand. */ 241 case POINTER_PLUS_EXPR: 242 case PLUS_EXPR: 243 { 244 tree rhs1 = gimple_assign_rhs1 (def_stmt); 245 tree rhs2 = gimple_assign_rhs2 (def_stmt); 246 247 /* If either argument is a constant, then we can compute 248 a constant value for the nonconstant argument. */ 249 if (TREE_CODE (rhs1) == INTEGER_CST 250 && TREE_CODE (rhs2) == SSA_NAME) 251 derive_equivalences (rhs2, 252 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), 253 value, rhs1), 254 recursion_limit - 1); 255 else if (TREE_CODE (rhs2) == INTEGER_CST 256 && TREE_CODE (rhs1) == SSA_NAME) 257 derive_equivalences (rhs1, 258 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), 259 value, rhs2), 260 recursion_limit - 1); 261 break; 262 } 263 264 /* If one of the operands is a constant, then we can compute 265 the value of the other operand. If both operands are 266 SSA_NAMEs, then they must be equal if the result is zero. */ 267 case MINUS_EXPR: 268 { 269 tree rhs1 = gimple_assign_rhs1 (def_stmt); 270 tree rhs2 = gimple_assign_rhs2 (def_stmt); 271 272 /* If either argument is a constant, then we can compute 273 a constant value for the nonconstant argument. */ 274 if (TREE_CODE (rhs1) == INTEGER_CST 275 && TREE_CODE (rhs2) == SSA_NAME) 276 derive_equivalences (rhs2, 277 fold_binary (MINUS_EXPR, TREE_TYPE (rhs1), 278 rhs1, value), 279 recursion_limit - 1); 280 else if (TREE_CODE (rhs2) == INTEGER_CST 281 && TREE_CODE (rhs1) == SSA_NAME) 282 derive_equivalences (rhs1, 283 fold_binary (PLUS_EXPR, TREE_TYPE (rhs1), 284 value, rhs2), 285 recursion_limit - 1); 286 else if (integer_zerop (value)) 287 { 288 tree cond = build2 (EQ_EXPR, boolean_type_node, 289 gimple_assign_rhs1 (def_stmt), 290 gimple_assign_rhs2 (def_stmt)); 291 tree inverted = invert_truthvalue (cond); 292 record_conditions (&this->cond_equivalences, cond, inverted); 293 } 294 break; 295 } 296 297 case EQ_EXPR: 298 case NE_EXPR: 299 { 300 if ((code == EQ_EXPR && integer_onep (value)) 301 || (code == NE_EXPR && integer_zerop (value))) 302 { 303 tree rhs1 = gimple_assign_rhs1 (def_stmt); 304 tree rhs2 = gimple_assign_rhs2 (def_stmt); 305 306 /* If either argument is a constant, then record the 307 other argument as being the same as that constant. 308 309 If neither operand is a constant, then we have a 310 conditional name == name equivalence. */ 311 if (TREE_CODE (rhs1) == INTEGER_CST) 312 derive_equivalences (rhs2, rhs1, recursion_limit - 1); 313 else if (TREE_CODE (rhs2) == INTEGER_CST) 314 derive_equivalences (rhs1, rhs2, recursion_limit - 1); 315 } 316 else 317 { 318 tree cond = build2 (code, boolean_type_node, 319 gimple_assign_rhs1 (def_stmt), 320 gimple_assign_rhs2 (def_stmt)); 321 tree inverted = invert_truthvalue (cond); 322 if (integer_zerop (value)) 323 std::swap (cond, inverted); 324 record_conditions (&this->cond_equivalences, cond, inverted); 325 } 326 break; 327 } 328 329 /* For BIT_NOT and NEGATE, we can just apply the operation to the 330 VALUE to get the new equivalence. It will always be a constant 331 so we can recurse. */ 332 case BIT_NOT_EXPR: 333 case NEGATE_EXPR: 334 { 335 tree rhs = gimple_assign_rhs1 (def_stmt); 336 tree res; 337 /* If this is a NOT and the operand has a boolean range, then we 338 know its value must be zero or one. We are not supposed to 339 have a BIT_NOT_EXPR for boolean types with precision > 1 in 340 the general case, see e.g. the handling of TRUTH_NOT_EXPR in 341 the gimplifier, but it can be generated by match.pd out of 342 a BIT_XOR_EXPR wrapped in a BIT_AND_EXPR. Now the handling 343 of BIT_AND_EXPR above already forces a specific semantics for 344 boolean types with precision > 1 so we must do the same here, 345 otherwise we could change the semantics of TRUTH_NOT_EXPR for 346 boolean types with precision > 1. */ 347 if (code == BIT_NOT_EXPR 348 && TREE_CODE (rhs) == SSA_NAME 349 && ssa_name_has_boolean_range (rhs)) 350 { 351 if ((TREE_INT_CST_LOW (value) & 1) == 0) 352 res = build_one_cst (TREE_TYPE (rhs)); 353 else 354 res = build_zero_cst (TREE_TYPE (rhs)); 355 } 356 else 357 res = fold_build1 (code, TREE_TYPE (rhs), value); 358 derive_equivalences (rhs, res, recursion_limit - 1); 359 break; 360 } 361 362 default: 363 { 364 if (TREE_CODE_CLASS (code) == tcc_comparison) 365 { 366 tree cond = build2 (code, boolean_type_node, 367 gimple_assign_rhs1 (def_stmt), 368 gimple_assign_rhs2 (def_stmt)); 369 tree inverted = invert_truthvalue (cond); 370 if (integer_zerop (value)) 371 std::swap (cond, inverted); 372 record_conditions (&this->cond_equivalences, cond, inverted); 373 break; 374 } 375 break; 376 } 377 } 378 } 379} 380 381void 382edge_info::record_simple_equiv (tree lhs, tree rhs) 383{ 384 /* If the RHS is a constant, then we may be able to derive 385 further equivalences. Else just record the name = name 386 equivalence. */ 387 if (TREE_CODE (rhs) == INTEGER_CST) 388 derive_equivalences (lhs, rhs, 4); 389 else 390 simple_equivalences.safe_push (equiv_pair (lhs, rhs)); 391} 392 393/* Free the edge_info data attached to E, if it exists. */ 394 395void 396free_dom_edge_info (edge e) 397{ 398 class edge_info *edge_info = (class edge_info *)e->aux; 399 400 if (edge_info) 401 delete edge_info; 402} 403 404/* Free all EDGE_INFO structures associated with edges in the CFG. 405 If a particular edge can be threaded, copy the redirection 406 target from the EDGE_INFO structure into the edge's AUX field 407 as required by code to update the CFG and SSA graph for 408 jump threading. */ 409 410static void 411free_all_edge_infos (void) 412{ 413 basic_block bb; 414 edge_iterator ei; 415 edge e; 416 417 FOR_EACH_BB_FN (bb, cfun) 418 { 419 FOR_EACH_EDGE (e, ei, bb->preds) 420 { 421 free_dom_edge_info (e); 422 e->aux = NULL; 423 } 424 } 425} 426 427/* We have finished optimizing BB, record any information implied by 428 taking a specific outgoing edge from BB. */ 429 430static void 431record_edge_info (basic_block bb) 432{ 433 gimple_stmt_iterator gsi = gsi_last_bb (bb); 434 class edge_info *edge_info; 435 436 if (! gsi_end_p (gsi)) 437 { 438 gimple *stmt = gsi_stmt (gsi); 439 location_t loc = gimple_location (stmt); 440 441 if (gimple_code (stmt) == GIMPLE_SWITCH) 442 { 443 gswitch *switch_stmt = as_a <gswitch *> (stmt); 444 tree index = gimple_switch_index (switch_stmt); 445 446 if (TREE_CODE (index) == SSA_NAME) 447 { 448 int i; 449 int n_labels = gimple_switch_num_labels (switch_stmt); 450 tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun)); 451 edge e; 452 edge_iterator ei; 453 454 for (i = 0; i < n_labels; i++) 455 { 456 tree label = gimple_switch_label (switch_stmt, i); 457 basic_block target_bb 458 = label_to_block (cfun, CASE_LABEL (label)); 459 if (CASE_HIGH (label) 460 || !CASE_LOW (label) 461 || info[target_bb->index]) 462 info[target_bb->index] = error_mark_node; 463 else 464 info[target_bb->index] = label; 465 } 466 467 FOR_EACH_EDGE (e, ei, bb->succs) 468 { 469 basic_block target_bb = e->dest; 470 tree label = info[target_bb->index]; 471 472 if (label != NULL && label != error_mark_node) 473 { 474 tree x = fold_convert_loc (loc, TREE_TYPE (index), 475 CASE_LOW (label)); 476 edge_info = new class edge_info (e); 477 edge_info->record_simple_equiv (index, x); 478 } 479 } 480 free (info); 481 } 482 } 483 484 /* A COND_EXPR may create equivalences too. */ 485 if (gimple_code (stmt) == GIMPLE_COND) 486 { 487 edge true_edge; 488 edge false_edge; 489 490 tree op0 = gimple_cond_lhs (stmt); 491 tree op1 = gimple_cond_rhs (stmt); 492 enum tree_code code = gimple_cond_code (stmt); 493 494 extract_true_false_edges_from_block (bb, &true_edge, &false_edge); 495 496 /* Special case comparing booleans against a constant as we 497 know the value of OP0 on both arms of the branch. i.e., we 498 can record an equivalence for OP0 rather than COND. 499 500 However, don't do this if the constant isn't zero or one. 501 Such conditionals will get optimized more thoroughly during 502 the domwalk. */ 503 if ((code == EQ_EXPR || code == NE_EXPR) 504 && TREE_CODE (op0) == SSA_NAME 505 && ssa_name_has_boolean_range (op0) 506 && is_gimple_min_invariant (op1) 507 && (integer_zerop (op1) || integer_onep (op1))) 508 { 509 tree true_val = constant_boolean_node (true, TREE_TYPE (op0)); 510 tree false_val = constant_boolean_node (false, TREE_TYPE (op0)); 511 512 if (code == EQ_EXPR) 513 { 514 edge_info = new class edge_info (true_edge); 515 edge_info->record_simple_equiv (op0, 516 (integer_zerop (op1) 517 ? false_val : true_val)); 518 edge_info = new class edge_info (false_edge); 519 edge_info->record_simple_equiv (op0, 520 (integer_zerop (op1) 521 ? true_val : false_val)); 522 } 523 else 524 { 525 edge_info = new class edge_info (true_edge); 526 edge_info->record_simple_equiv (op0, 527 (integer_zerop (op1) 528 ? true_val : false_val)); 529 edge_info = new class edge_info (false_edge); 530 edge_info->record_simple_equiv (op0, 531 (integer_zerop (op1) 532 ? false_val : true_val)); 533 } 534 } 535 /* This can show up in the IL as a result of copy propagation 536 it will eventually be canonicalized, but we have to cope 537 with this case within the pass. */ 538 else if (is_gimple_min_invariant (op0) 539 && TREE_CODE (op1) == SSA_NAME) 540 { 541 tree cond = build2 (code, boolean_type_node, op0, op1); 542 tree inverted = invert_truthvalue_loc (loc, cond); 543 bool can_infer_simple_equiv 544 = !(HONOR_SIGNED_ZEROS (op0) && real_maybe_zerop (op0)) 545 && !DECIMAL_FLOAT_MODE_P (element_mode (TREE_TYPE (op0))); 546 class edge_info *edge_info; 547 548 edge_info = new class edge_info (true_edge); 549 record_conditions (&edge_info->cond_equivalences, cond, inverted); 550 551 if (can_infer_simple_equiv && code == EQ_EXPR) 552 edge_info->record_simple_equiv (op1, op0); 553 554 edge_info = new class edge_info (false_edge); 555 record_conditions (&edge_info->cond_equivalences, inverted, cond); 556 557 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) 558 edge_info->record_simple_equiv (op1, op0); 559 } 560 561 else if (TREE_CODE (op0) == SSA_NAME 562 && (TREE_CODE (op1) == SSA_NAME 563 || is_gimple_min_invariant (op1))) 564 { 565 tree cond = build2 (code, boolean_type_node, op0, op1); 566 tree inverted = invert_truthvalue_loc (loc, cond); 567 bool can_infer_simple_equiv 568 = !(HONOR_SIGNED_ZEROS (op1) && real_maybe_zerop (op1)) 569 && !DECIMAL_FLOAT_MODE_P (element_mode (TREE_TYPE (op1))); 570 class edge_info *edge_info; 571 572 edge_info = new class edge_info (true_edge); 573 record_conditions (&edge_info->cond_equivalences, cond, inverted); 574 575 if (can_infer_simple_equiv && code == EQ_EXPR) 576 edge_info->record_simple_equiv (op0, op1); 577 578 edge_info = new class edge_info (false_edge); 579 record_conditions (&edge_info->cond_equivalences, inverted, cond); 580 581 if (can_infer_simple_equiv && TREE_CODE (inverted) == EQ_EXPR) 582 edge_info->record_simple_equiv (op0, op1); 583 } 584 } 585 } 586} 587 588class dom_jt_state : public jt_state 589{ 590public: 591 dom_jt_state (const_and_copies *copies, avail_exprs_stack *avails, 592 evrp_range_analyzer *evrp) 593 : m_copies (copies), m_avails (avails), m_evrp (evrp) 594 { 595 } 596 void push (edge e) override 597 { 598 m_copies->push_marker (); 599 m_avails->push_marker (); 600 m_evrp->push_marker (); 601 jt_state::push (e); 602 } 603 void pop () override 604 { 605 m_copies->pop_to_marker (); 606 m_avails->pop_to_marker (); 607 m_evrp->pop_to_marker (); 608 jt_state::pop (); 609 } 610 void register_equivs_edge (edge e) override 611 { 612 record_temporary_equivalences (e, m_copies, m_avails); 613 } 614 void record_ranges_from_stmt (gimple *stmt, bool temporary) override 615 { 616 m_evrp->record_ranges_from_stmt (stmt, temporary); 617 } 618 void register_equiv (tree dest, tree src, bool update) override; 619private: 620 const_and_copies *m_copies; 621 avail_exprs_stack *m_avails; 622 evrp_range_analyzer *m_evrp; 623}; 624 625void 626dom_jt_state::register_equiv (tree dest, tree src, bool update) 627{ 628 m_copies->record_const_or_copy (dest, src); 629 630 /* If requested, update the value range associated with DST, using 631 the range from SRC. */ 632 if (update) 633 { 634 /* Get new VR we can pass to push_value_range. */ 635 value_range_equiv *new_vr = m_evrp->allocate_value_range_equiv (); 636 new (new_vr) value_range_equiv (); 637 638 /* There are three cases to consider: 639 640 First if SRC is an SSA_NAME, then we can copy the value range 641 from SRC into NEW_VR. 642 643 Second if SRC is an INTEGER_CST, then we can just set NEW_VR 644 to a singleton range. Note that even if SRC is a constant we 645 need to set a suitable output range so that VR_UNDEFINED 646 ranges do not leak through. 647 648 Otherwise set NEW_VR to varying. This may be overly 649 conservative. */ 650 if (TREE_CODE (src) == SSA_NAME) 651 new_vr->deep_copy (m_evrp->get_value_range (src)); 652 else if (TREE_CODE (src) == INTEGER_CST) 653 new_vr->set (src); 654 else 655 new_vr->set_varying (TREE_TYPE (src)); 656 657 /* This is a temporary range for DST, so push it. */ 658 m_evrp->push_value_range (dest, new_vr); 659 } 660} 661 662class dom_jt_simplifier : public jt_simplifier 663{ 664public: 665 dom_jt_simplifier (vr_values *v, avail_exprs_stack *avails) 666 : m_vr_values (v), m_avails (avails) { } 667 668private: 669 tree simplify (gimple *, gimple *, basic_block, jt_state *) override; 670 vr_values *m_vr_values; 671 avail_exprs_stack *m_avails; 672}; 673 674tree 675dom_jt_simplifier::simplify (gimple *stmt, gimple *within_stmt, 676 basic_block, jt_state *) 677{ 678 /* First see if the conditional is in the hash table. */ 679 tree cached_lhs = m_avails->lookup_avail_expr (stmt, false, true); 680 if (cached_lhs) 681 return cached_lhs; 682 683 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt)) 684 { 685 simplify_using_ranges simplifier (m_vr_values); 686 return simplifier.vrp_evaluate_conditional (gimple_cond_code (cond_stmt), 687 gimple_cond_lhs (cond_stmt), 688 gimple_cond_rhs (cond_stmt), 689 within_stmt); 690 } 691 if (gswitch *switch_stmt = dyn_cast <gswitch *> (stmt)) 692 { 693 tree op = gimple_switch_index (switch_stmt); 694 if (TREE_CODE (op) != SSA_NAME) 695 return NULL_TREE; 696 697 const value_range_equiv *vr = m_vr_values->get_value_range (op); 698 return find_case_label_range (switch_stmt, vr); 699 } 700 if (gassign *assign_stmt = dyn_cast <gassign *> (stmt)) 701 { 702 tree lhs = gimple_assign_lhs (assign_stmt); 703 if (TREE_CODE (lhs) == SSA_NAME 704 && (INTEGRAL_TYPE_P (TREE_TYPE (lhs)) 705 || POINTER_TYPE_P (TREE_TYPE (lhs))) 706 && stmt_interesting_for_vrp (stmt)) 707 { 708 edge dummy_e; 709 tree dummy_tree; 710 value_range_equiv new_vr; 711 m_vr_values->extract_range_from_stmt (stmt, &dummy_e, &dummy_tree, 712 &new_vr); 713 tree singleton; 714 if (new_vr.singleton_p (&singleton)) 715 return singleton; 716 } 717 } 718 return NULL; 719} 720 721class dom_opt_dom_walker : public dom_walker 722{ 723public: 724 dom_opt_dom_walker (cdi_direction direction, 725 jump_threader *threader, 726 jt_state *state, 727 evrp_range_analyzer *analyzer, 728 const_and_copies *const_and_copies, 729 avail_exprs_stack *avail_exprs_stack) 730 : dom_walker (direction, REACHABLE_BLOCKS) 731 { 732 m_evrp_range_analyzer = analyzer; 733 m_state = state; 734 m_dummy_cond = gimple_build_cond (NE_EXPR, integer_zero_node, 735 integer_zero_node, NULL, NULL); 736 m_const_and_copies = const_and_copies; 737 m_avail_exprs_stack = avail_exprs_stack; 738 m_threader = threader; 739 } 740 741 virtual edge before_dom_children (basic_block); 742 virtual void after_dom_children (basic_block); 743 744private: 745 746 /* Unwindable equivalences, both const/copy and expression varieties. */ 747 class const_and_copies *m_const_and_copies; 748 class avail_exprs_stack *m_avail_exprs_stack; 749 750 /* Dummy condition to avoid creating lots of throw away statements. */ 751 gcond *m_dummy_cond; 752 753 /* Optimize a single statement within a basic block using the 754 various tables mantained by DOM. Returns the taken edge if 755 the statement is a conditional with a statically determined 756 value. */ 757 edge optimize_stmt (basic_block, gimple_stmt_iterator *, bool *); 758 759 760 void test_for_singularity (gimple *, avail_exprs_stack *); 761 762 jump_threader *m_threader; 763 evrp_range_analyzer *m_evrp_range_analyzer; 764 jt_state *m_state; 765}; 766 767/* Jump threading, redundancy elimination and const/copy propagation. 768 769 This pass may expose new symbols that need to be renamed into SSA. For 770 every new symbol exposed, its corresponding bit will be set in 771 VARS_TO_RENAME. */ 772 773namespace { 774 775const pass_data pass_data_dominator = 776{ 777 GIMPLE_PASS, /* type */ 778 "dom", /* name */ 779 OPTGROUP_NONE, /* optinfo_flags */ 780 TV_TREE_SSA_DOMINATOR_OPTS, /* tv_id */ 781 ( PROP_cfg | PROP_ssa ), /* properties_required */ 782 0, /* properties_provided */ 783 0, /* properties_destroyed */ 784 0, /* todo_flags_start */ 785 ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */ 786}; 787 788class pass_dominator : public gimple_opt_pass 789{ 790public: 791 pass_dominator (gcc::context *ctxt) 792 : gimple_opt_pass (pass_data_dominator, ctxt), 793 may_peel_loop_headers_p (false) 794 {} 795 796 /* opt_pass methods: */ 797 opt_pass * clone () { return new pass_dominator (m_ctxt); } 798 void set_pass_param (unsigned int n, bool param) 799 { 800 gcc_assert (n == 0); 801 may_peel_loop_headers_p = param; 802 } 803 virtual bool gate (function *) { return flag_tree_dom != 0; } 804 virtual unsigned int execute (function *); 805 806 private: 807 /* This flag is used to prevent loops from being peeled repeatedly in jump 808 threading; it will be removed once we preserve loop structures throughout 809 the compilation -- we will be able to mark the affected loops directly in 810 jump threading, and avoid peeling them next time. */ 811 bool may_peel_loop_headers_p; 812}; // class pass_dominator 813 814unsigned int 815pass_dominator::execute (function *fun) 816{ 817 memset (&opt_stats, 0, sizeof (opt_stats)); 818 819 /* Create our hash tables. */ 820 hash_table<expr_elt_hasher> *avail_exprs 821 = new hash_table<expr_elt_hasher> (1024); 822 class avail_exprs_stack *avail_exprs_stack 823 = new class avail_exprs_stack (avail_exprs); 824 class const_and_copies *const_and_copies = new class const_and_copies (); 825 need_eh_cleanup = BITMAP_ALLOC (NULL); 826 need_noreturn_fixup.create (0); 827 828 calculate_dominance_info (CDI_DOMINATORS); 829 cfg_altered = false; 830 831 /* We need to know loop structures in order to avoid destroying them 832 in jump threading. Note that we still can e.g. thread through loop 833 headers to an exit edge, or through loop header to the loop body, assuming 834 that we update the loop info. 835 836 TODO: We don't need to set LOOPS_HAVE_PREHEADERS generally, but due 837 to several overly conservative bail-outs in jump threading, case 838 gcc.dg/tree-ssa/pr21417.c can't be threaded if loop preheader is 839 missing. We should improve jump threading in future then 840 LOOPS_HAVE_PREHEADERS won't be needed here. */ 841 loop_optimizer_init (LOOPS_HAVE_PREHEADERS | LOOPS_HAVE_SIMPLE_LATCHES 842 | LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS); 843 844 /* We need accurate information regarding back edges in the CFG 845 for jump threading; this may include back edges that are not part of 846 a single loop. */ 847 mark_dfs_back_edges (); 848 849 /* We want to create the edge info structures before the dominator walk 850 so that they'll be in place for the jump threader, particularly when 851 threading through a join block. 852 853 The conditions will be lazily updated with global equivalences as 854 we reach them during the dominator walk. */ 855 basic_block bb; 856 FOR_EACH_BB_FN (bb, fun) 857 record_edge_info (bb); 858 859 /* Recursively walk the dominator tree optimizing statements. */ 860 evrp_range_analyzer analyzer (true); 861 dom_jt_simplifier simplifier (&analyzer, avail_exprs_stack); 862 dom_jt_state state (const_and_copies, avail_exprs_stack, &analyzer); 863 jump_threader threader (&simplifier, &state); 864 dom_opt_dom_walker walker (CDI_DOMINATORS, 865 &threader, 866 &state, 867 &analyzer, 868 const_and_copies, 869 avail_exprs_stack); 870 walker.walk (fun->cfg->x_entry_block_ptr); 871 872 /* Look for blocks where we cleared EDGE_EXECUTABLE on an outgoing 873 edge. When found, remove jump threads which contain any outgoing 874 edge from the affected block. */ 875 if (cfg_altered) 876 { 877 FOR_EACH_BB_FN (bb, fun) 878 { 879 edge_iterator ei; 880 edge e; 881 882 /* First see if there are any edges without EDGE_EXECUTABLE 883 set. */ 884 bool found = false; 885 FOR_EACH_EDGE (e, ei, bb->succs) 886 { 887 if ((e->flags & EDGE_EXECUTABLE) == 0) 888 { 889 found = true; 890 break; 891 } 892 } 893 894 /* If there were any such edges found, then remove jump threads 895 containing any edge leaving BB. */ 896 if (found) 897 FOR_EACH_EDGE (e, ei, bb->succs) 898 threader.remove_jump_threads_including (e); 899 } 900 } 901 902 { 903 gimple_stmt_iterator gsi; 904 basic_block bb; 905 FOR_EACH_BB_FN (bb, fun) 906 { 907 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 908 update_stmt_if_modified (gsi_stmt (gsi)); 909 } 910 } 911 912 /* If we exposed any new variables, go ahead and put them into 913 SSA form now, before we handle jump threading. This simplifies 914 interactions between rewriting of _DECL nodes into SSA form 915 and rewriting SSA_NAME nodes into SSA form after block 916 duplication and CFG manipulation. */ 917 update_ssa (TODO_update_ssa); 918 919 free_all_edge_infos (); 920 921 /* Thread jumps, creating duplicate blocks as needed. */ 922 cfg_altered |= threader.thread_through_all_blocks (may_peel_loop_headers_p); 923 924 if (cfg_altered) 925 free_dominance_info (CDI_DOMINATORS); 926 927 /* Removal of statements may make some EH edges dead. Purge 928 such edges from the CFG as needed. */ 929 if (!bitmap_empty_p (need_eh_cleanup)) 930 { 931 unsigned i; 932 bitmap_iterator bi; 933 934 /* Jump threading may have created forwarder blocks from blocks 935 needing EH cleanup; the new successor of these blocks, which 936 has inherited from the original block, needs the cleanup. 937 Don't clear bits in the bitmap, as that can break the bitmap 938 iterator. */ 939 EXECUTE_IF_SET_IN_BITMAP (need_eh_cleanup, 0, i, bi) 940 { 941 basic_block bb = BASIC_BLOCK_FOR_FN (fun, i); 942 if (bb == NULL) 943 continue; 944 while (single_succ_p (bb) 945 && (single_succ_edge (bb)->flags 946 & (EDGE_EH|EDGE_DFS_BACK)) == 0) 947 bb = single_succ (bb); 948 if (bb == EXIT_BLOCK_PTR_FOR_FN (fun)) 949 continue; 950 if ((unsigned) bb->index != i) 951 bitmap_set_bit (need_eh_cleanup, bb->index); 952 } 953 954 gimple_purge_all_dead_eh_edges (need_eh_cleanup); 955 bitmap_clear (need_eh_cleanup); 956 } 957 958 /* Fixup stmts that became noreturn calls. This may require splitting 959 blocks and thus isn't possible during the dominator walk or before 960 jump threading finished. Do this in reverse order so we don't 961 inadvertedly remove a stmt we want to fixup by visiting a dominating 962 now noreturn call first. */ 963 while (!need_noreturn_fixup.is_empty ()) 964 { 965 gimple *stmt = need_noreturn_fixup.pop (); 966 if (dump_file && dump_flags & TDF_DETAILS) 967 { 968 fprintf (dump_file, "Fixing up noreturn call "); 969 print_gimple_stmt (dump_file, stmt, 0); 970 fprintf (dump_file, "\n"); 971 } 972 fixup_noreturn_call (stmt); 973 } 974 975 statistics_counter_event (fun, "Redundant expressions eliminated", 976 opt_stats.num_re); 977 statistics_counter_event (fun, "Constants propagated", 978 opt_stats.num_const_prop); 979 statistics_counter_event (fun, "Copies propagated", 980 opt_stats.num_copy_prop); 981 982 /* Debugging dumps. */ 983 if (dump_file && (dump_flags & TDF_STATS)) 984 dump_dominator_optimization_stats (dump_file, avail_exprs); 985 986 loop_optimizer_finalize (); 987 988 /* Delete our main hashtable. */ 989 delete avail_exprs; 990 avail_exprs = NULL; 991 992 /* Free asserted bitmaps and stacks. */ 993 BITMAP_FREE (need_eh_cleanup); 994 need_noreturn_fixup.release (); 995 delete avail_exprs_stack; 996 delete const_and_copies; 997 998 return 0; 999} 1000 1001} // anon namespace 1002 1003gimple_opt_pass * 1004make_pass_dominator (gcc::context *ctxt) 1005{ 1006 return new pass_dominator (ctxt); 1007} 1008 1009/* Valueize hook for gimple_fold_stmt_to_constant_1. */ 1010 1011static tree 1012dom_valueize (tree t) 1013{ 1014 if (TREE_CODE (t) == SSA_NAME) 1015 { 1016 tree tem = SSA_NAME_VALUE (t); 1017 if (tem) 1018 return tem; 1019 } 1020 return t; 1021} 1022 1023/* We have just found an equivalence for LHS on an edge E. 1024 Look backwards to other uses of LHS and see if we can derive 1025 additional equivalences that are valid on edge E. */ 1026static void 1027back_propagate_equivalences (tree lhs, edge e, 1028 class const_and_copies *const_and_copies, 1029 bitmap *domby) 1030{ 1031 use_operand_p use_p; 1032 imm_use_iterator iter; 1033 basic_block dest = e->dest; 1034 bool domok = (dom_info_state (CDI_DOMINATORS) == DOM_OK); 1035 1036 /* Iterate over the uses of LHS to see if any dominate E->dest. 1037 If so, they may create useful equivalences too. 1038 1039 ??? If the code gets re-organized to a worklist to catch more 1040 indirect opportunities and it is made to handle PHIs then this 1041 should only consider use_stmts in basic-blocks we have already visited. */ 1042 FOR_EACH_IMM_USE_FAST (use_p, iter, lhs) 1043 { 1044 gimple *use_stmt = USE_STMT (use_p); 1045 1046 /* Often the use is in DEST, which we trivially know we can't use. 1047 This is cheaper than the dominator set tests below. */ 1048 if (dest == gimple_bb (use_stmt)) 1049 continue; 1050 1051 /* Filter out statements that can never produce a useful 1052 equivalence. */ 1053 tree lhs2 = gimple_get_lhs (use_stmt); 1054 if (!lhs2 || TREE_CODE (lhs2) != SSA_NAME) 1055 continue; 1056 1057 if (domok) 1058 { 1059 if (!dominated_by_p (CDI_DOMINATORS, dest, gimple_bb (use_stmt))) 1060 continue; 1061 } 1062 else 1063 { 1064 /* Profiling has shown the domination tests here can be fairly 1065 expensive when the fast indexes are not computed. 1066 We get significant improvements by building the 1067 set of blocks that dominate BB. We can then just test 1068 for set membership below. 1069 1070 We also initialize the set lazily since often the only uses 1071 are going to be in the same block as DEST. */ 1072 1073 if (!*domby) 1074 { 1075 *domby = BITMAP_ALLOC (NULL); 1076 bitmap_tree_view (*domby); 1077 basic_block bb = get_immediate_dominator (CDI_DOMINATORS, dest); 1078 while (bb) 1079 { 1080 bitmap_set_bit (*domby, bb->index); 1081 bb = get_immediate_dominator (CDI_DOMINATORS, bb); 1082 } 1083 } 1084 1085 /* This tests if USE_STMT does not dominate DEST. */ 1086 if (!bitmap_bit_p (*domby, gimple_bb (use_stmt)->index)) 1087 continue; 1088 } 1089 1090 /* At this point USE_STMT dominates DEST and may result in a 1091 useful equivalence. Try to simplify its RHS to a constant 1092 or SSA_NAME. */ 1093 tree res = gimple_fold_stmt_to_constant_1 (use_stmt, dom_valueize, 1094 no_follow_ssa_edges); 1095 if (res && (TREE_CODE (res) == SSA_NAME || is_gimple_min_invariant (res))) 1096 record_equality (lhs2, res, const_and_copies); 1097 } 1098} 1099 1100/* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied 1101 by traversing edge E (which are cached in E->aux). 1102 1103 Callers are responsible for managing the unwinding markers. */ 1104void 1105record_temporary_equivalences (edge e, 1106 class const_and_copies *const_and_copies, 1107 class avail_exprs_stack *avail_exprs_stack) 1108{ 1109 int i; 1110 class edge_info *edge_info = (class edge_info *) e->aux; 1111 1112 /* If we have info associated with this edge, record it into 1113 our equivalence tables. */ 1114 if (edge_info) 1115 { 1116 cond_equivalence *eq; 1117 /* If we have 0 = COND or 1 = COND equivalences, record them 1118 into our expression hash tables. */ 1119 for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i) 1120 avail_exprs_stack->record_cond (eq); 1121 1122 bitmap domby = NULL; 1123 edge_info::equiv_pair *seq; 1124 for (i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i) 1125 { 1126 tree lhs = seq->first; 1127 if (!lhs || TREE_CODE (lhs) != SSA_NAME) 1128 continue; 1129 1130 /* Record the simple NAME = VALUE equivalence. */ 1131 tree rhs = seq->second; 1132 1133 /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is 1134 cheaper to compute than the other, then set up the equivalence 1135 such that we replace the expensive one with the cheap one. 1136 1137 If they are the same cost to compute, then do not record 1138 anything. */ 1139 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME) 1140 { 1141 gimple *rhs_def = SSA_NAME_DEF_STMT (rhs); 1142 int rhs_cost = estimate_num_insns (rhs_def, &eni_size_weights); 1143 1144 gimple *lhs_def = SSA_NAME_DEF_STMT (lhs); 1145 int lhs_cost = estimate_num_insns (lhs_def, &eni_size_weights); 1146 1147 if (rhs_cost > lhs_cost) 1148 record_equality (rhs, lhs, const_and_copies); 1149 else if (rhs_cost < lhs_cost) 1150 record_equality (lhs, rhs, const_and_copies); 1151 } 1152 else 1153 record_equality (lhs, rhs, const_and_copies); 1154 1155 1156 /* Any equivalence found for LHS may result in additional 1157 equivalences for other uses of LHS that we have already 1158 processed. */ 1159 back_propagate_equivalences (lhs, e, const_and_copies, &domby); 1160 } 1161 if (domby) 1162 BITMAP_FREE (domby); 1163 } 1164} 1165 1166/* PHI nodes can create equivalences too. 1167 1168 Ignoring any alternatives which are the same as the result, if 1169 all the alternatives are equal, then the PHI node creates an 1170 equivalence. */ 1171 1172static void 1173record_equivalences_from_phis (basic_block bb) 1174{ 1175 gphi_iterator gsi; 1176 1177 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); ) 1178 { 1179 gphi *phi = gsi.phi (); 1180 1181 /* We might eliminate the PHI, so advance GSI now. */ 1182 gsi_next (&gsi); 1183 1184 tree lhs = gimple_phi_result (phi); 1185 tree rhs = NULL; 1186 size_t i; 1187 1188 for (i = 0; i < gimple_phi_num_args (phi); i++) 1189 { 1190 tree t = gimple_phi_arg_def (phi, i); 1191 1192 /* Ignore alternatives which are the same as our LHS. Since 1193 LHS is a PHI_RESULT, it is known to be a SSA_NAME, so we 1194 can simply compare pointers. */ 1195 if (lhs == t) 1196 continue; 1197 1198 /* If the associated edge is not marked as executable, then it 1199 can be ignored. */ 1200 if ((gimple_phi_arg_edge (phi, i)->flags & EDGE_EXECUTABLE) == 0) 1201 continue; 1202 1203 t = dom_valueize (t); 1204 1205 /* If T is an SSA_NAME and its associated edge is a backedge, 1206 then quit as we cannot utilize this equivalence. */ 1207 if (TREE_CODE (t) == SSA_NAME 1208 && (gimple_phi_arg_edge (phi, i)->flags & EDGE_DFS_BACK)) 1209 break; 1210 1211 /* If we have not processed an alternative yet, then set 1212 RHS to this alternative. */ 1213 if (rhs == NULL) 1214 rhs = t; 1215 /* If we have processed an alternative (stored in RHS), then 1216 see if it is equal to this one. If it isn't, then stop 1217 the search. */ 1218 else if (! operand_equal_for_phi_arg_p (rhs, t)) 1219 break; 1220 } 1221 1222 /* If we had no interesting alternatives, then all the RHS alternatives 1223 must have been the same as LHS. */ 1224 if (!rhs) 1225 rhs = lhs; 1226 1227 /* If we managed to iterate through each PHI alternative without 1228 breaking out of the loop, then we have a PHI which may create 1229 a useful equivalence. We do not need to record unwind data for 1230 this, since this is a true assignment and not an equivalence 1231 inferred from a comparison. All uses of this ssa name are dominated 1232 by this assignment, so unwinding just costs time and space. */ 1233 if (i == gimple_phi_num_args (phi)) 1234 { 1235 if (may_propagate_copy (lhs, rhs)) 1236 set_ssa_name_value (lhs, rhs); 1237 else if (virtual_operand_p (lhs)) 1238 { 1239 gimple *use_stmt; 1240 imm_use_iterator iter; 1241 use_operand_p use_p; 1242 /* For virtual operands we have to propagate into all uses as 1243 otherwise we will create overlapping life-ranges. */ 1244 FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) 1245 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) 1246 SET_USE (use_p, rhs); 1247 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) 1248 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1; 1249 gimple_stmt_iterator tmp_gsi = gsi_for_stmt (phi); 1250 remove_phi_node (&tmp_gsi, true); 1251 } 1252 } 1253 } 1254} 1255 1256/* Record any equivalences created by the incoming edge to BB into 1257 CONST_AND_COPIES and AVAIL_EXPRS_STACK. If BB has more than one 1258 incoming edge, then no equivalence is created. */ 1259 1260static void 1261record_equivalences_from_incoming_edge (basic_block bb, 1262 class const_and_copies *const_and_copies, 1263 class avail_exprs_stack *avail_exprs_stack) 1264{ 1265 edge e; 1266 basic_block parent; 1267 1268 /* If our parent block ended with a control statement, then we may be 1269 able to record some equivalences based on which outgoing edge from 1270 the parent was followed. */ 1271 parent = get_immediate_dominator (CDI_DOMINATORS, bb); 1272 1273 e = single_pred_edge_ignoring_loop_edges (bb, true); 1274 1275 /* If we had a single incoming edge from our parent block, then enter 1276 any data associated with the edge into our tables. */ 1277 if (e && e->src == parent) 1278 record_temporary_equivalences (e, const_and_copies, avail_exprs_stack); 1279} 1280 1281/* Dump statistics for the hash table HTAB. */ 1282 1283static void 1284htab_statistics (FILE *file, const hash_table<expr_elt_hasher> &htab) 1285{ 1286 fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n", 1287 (long) htab.size (), 1288 (long) htab.elements (), 1289 htab.collisions ()); 1290} 1291 1292/* Dump SSA statistics on FILE. */ 1293 1294static void 1295dump_dominator_optimization_stats (FILE *file, 1296 hash_table<expr_elt_hasher> *avail_exprs) 1297{ 1298 fprintf (file, "Total number of statements: %6ld\n\n", 1299 opt_stats.num_stmts); 1300 fprintf (file, "Exprs considered for dominator optimizations: %6ld\n", 1301 opt_stats.num_exprs_considered); 1302 1303 fprintf (file, "\nHash table statistics:\n"); 1304 1305 fprintf (file, " avail_exprs: "); 1306 htab_statistics (file, *avail_exprs); 1307} 1308 1309 1310/* Similarly, but assume that X and Y are the two operands of an EQ_EXPR. 1311 This constrains the cases in which we may treat this as assignment. */ 1312 1313static void 1314record_equality (tree x, tree y, class const_and_copies *const_and_copies) 1315{ 1316 tree prev_x = NULL, prev_y = NULL; 1317 1318 if (tree_swap_operands_p (x, y)) 1319 std::swap (x, y); 1320 1321 /* Most of the time tree_swap_operands_p does what we want. But there 1322 are cases where we know one operand is better for copy propagation than 1323 the other. Given no other code cares about ordering of equality 1324 comparison operators for that purpose, we just handle the special cases 1325 here. */ 1326 if (TREE_CODE (x) == SSA_NAME && TREE_CODE (y) == SSA_NAME) 1327 { 1328 /* If one operand is a single use operand, then make it 1329 X. This will preserve its single use properly and if this 1330 conditional is eliminated, the computation of X can be 1331 eliminated as well. */ 1332 if (has_single_use (y) && ! has_single_use (x)) 1333 std::swap (x, y); 1334 } 1335 if (TREE_CODE (x) == SSA_NAME) 1336 prev_x = SSA_NAME_VALUE (x); 1337 if (TREE_CODE (y) == SSA_NAME) 1338 prev_y = SSA_NAME_VALUE (y); 1339 1340 /* If one of the previous values is invariant, or invariant in more loops 1341 (by depth), then use that. 1342 Otherwise it doesn't matter which value we choose, just so 1343 long as we canonicalize on one value. */ 1344 if (is_gimple_min_invariant (y)) 1345 ; 1346 else if (is_gimple_min_invariant (x)) 1347 prev_x = x, x = y, y = prev_x, prev_x = prev_y; 1348 else if (prev_x && is_gimple_min_invariant (prev_x)) 1349 x = y, y = prev_x, prev_x = prev_y; 1350 else if (prev_y) 1351 y = prev_y; 1352 1353 /* After the swapping, we must have one SSA_NAME. */ 1354 if (TREE_CODE (x) != SSA_NAME) 1355 return; 1356 1357 /* For IEEE, -0.0 == 0.0, so we don't necessarily know the sign of a 1358 variable compared against zero. If we're honoring signed zeros, 1359 then we cannot record this value unless we know that the value is 1360 nonzero. */ 1361 if (HONOR_SIGNED_ZEROS (x) 1362 && (TREE_CODE (y) != REAL_CST 1363 || real_equal (&dconst0, &TREE_REAL_CST (y)))) 1364 return; 1365 1366 const_and_copies->record_const_or_copy (x, y, prev_x); 1367} 1368 1369/* Returns true when STMT is a simple iv increment. It detects the 1370 following situation: 1371 1372 i_1 = phi (..., i_k) 1373 [...] 1374 i_j = i_{j-1} for each j : 2 <= j <= k-1 1375 [...] 1376 i_k = i_{k-1} +/- ... */ 1377 1378bool 1379simple_iv_increment_p (gimple *stmt) 1380{ 1381 enum tree_code code; 1382 tree lhs, preinc; 1383 gimple *phi; 1384 size_t i; 1385 1386 if (gimple_code (stmt) != GIMPLE_ASSIGN) 1387 return false; 1388 1389 lhs = gimple_assign_lhs (stmt); 1390 if (TREE_CODE (lhs) != SSA_NAME) 1391 return false; 1392 1393 code = gimple_assign_rhs_code (stmt); 1394 if (code != PLUS_EXPR 1395 && code != MINUS_EXPR 1396 && code != POINTER_PLUS_EXPR) 1397 return false; 1398 1399 preinc = gimple_assign_rhs1 (stmt); 1400 if (TREE_CODE (preinc) != SSA_NAME) 1401 return false; 1402 1403 phi = SSA_NAME_DEF_STMT (preinc); 1404 while (gimple_code (phi) != GIMPLE_PHI) 1405 { 1406 /* Follow trivial copies, but not the DEF used in a back edge, 1407 so that we don't prevent coalescing. */ 1408 if (!gimple_assign_ssa_name_copy_p (phi)) 1409 return false; 1410 preinc = gimple_assign_rhs1 (phi); 1411 phi = SSA_NAME_DEF_STMT (preinc); 1412 } 1413 1414 for (i = 0; i < gimple_phi_num_args (phi); i++) 1415 if (gimple_phi_arg_def (phi, i) == lhs) 1416 return true; 1417 1418 return false; 1419} 1420 1421/* Propagate know values from SSA_NAME_VALUE into the PHI nodes of the 1422 successors of BB. */ 1423 1424static void 1425cprop_into_successor_phis (basic_block bb, 1426 class const_and_copies *const_and_copies) 1427{ 1428 edge e; 1429 edge_iterator ei; 1430 1431 FOR_EACH_EDGE (e, ei, bb->succs) 1432 { 1433 int indx; 1434 gphi_iterator gsi; 1435 1436 /* If this is an abnormal edge, then we do not want to copy propagate 1437 into the PHI alternative associated with this edge. */ 1438 if (e->flags & EDGE_ABNORMAL) 1439 continue; 1440 1441 gsi = gsi_start_phis (e->dest); 1442 if (gsi_end_p (gsi)) 1443 continue; 1444 1445 /* We may have an equivalence associated with this edge. While 1446 we cannot propagate it into non-dominated blocks, we can 1447 propagate them into PHIs in non-dominated blocks. */ 1448 1449 /* Push the unwind marker so we can reset the const and copies 1450 table back to its original state after processing this edge. */ 1451 const_and_copies->push_marker (); 1452 1453 /* Extract and record any simple NAME = VALUE equivalences. 1454 1455 Don't bother with [01] = COND equivalences, they're not useful 1456 here. */ 1457 class edge_info *edge_info = (class edge_info *) e->aux; 1458 1459 if (edge_info) 1460 { 1461 edge_info::equiv_pair *seq; 1462 for (int i = 0; edge_info->simple_equivalences.iterate (i, &seq); ++i) 1463 { 1464 tree lhs = seq->first; 1465 tree rhs = seq->second; 1466 1467 if (lhs && TREE_CODE (lhs) == SSA_NAME) 1468 const_and_copies->record_const_or_copy (lhs, rhs); 1469 } 1470 1471 } 1472 1473 indx = e->dest_idx; 1474 for ( ; !gsi_end_p (gsi); gsi_next (&gsi)) 1475 { 1476 tree new_val; 1477 use_operand_p orig_p; 1478 tree orig_val; 1479 gphi *phi = gsi.phi (); 1480 1481 /* The alternative may be associated with a constant, so verify 1482 it is an SSA_NAME before doing anything with it. */ 1483 orig_p = gimple_phi_arg_imm_use_ptr (phi, indx); 1484 orig_val = get_use_from_ptr (orig_p); 1485 if (TREE_CODE (orig_val) != SSA_NAME) 1486 continue; 1487 1488 /* If we have *ORIG_P in our constant/copy table, then replace 1489 ORIG_P with its value in our constant/copy table. */ 1490 new_val = SSA_NAME_VALUE (orig_val); 1491 if (new_val 1492 && new_val != orig_val 1493 && may_propagate_copy (orig_val, new_val)) 1494 propagate_value (orig_p, new_val); 1495 } 1496 1497 const_and_copies->pop_to_marker (); 1498 } 1499} 1500 1501edge 1502dom_opt_dom_walker::before_dom_children (basic_block bb) 1503{ 1504 gimple_stmt_iterator gsi; 1505 1506 if (dump_file && (dump_flags & TDF_DETAILS)) 1507 fprintf (dump_file, "\n\nOptimizing block #%d\n\n", bb->index); 1508 1509 m_evrp_range_analyzer->enter (bb); 1510 1511 /* Push a marker on the stacks of local information so that we know how 1512 far to unwind when we finalize this block. */ 1513 m_avail_exprs_stack->push_marker (); 1514 m_const_and_copies->push_marker (); 1515 1516 record_equivalences_from_incoming_edge (bb, m_const_and_copies, 1517 m_avail_exprs_stack); 1518 1519 /* PHI nodes can create equivalences too. */ 1520 record_equivalences_from_phis (bb); 1521 1522 /* Create equivalences from redundant PHIs. PHIs are only truly 1523 redundant when they exist in the same block, so push another 1524 marker and unwind right afterwards. */ 1525 m_avail_exprs_stack->push_marker (); 1526 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1527 eliminate_redundant_computations (&gsi, m_const_and_copies, 1528 m_avail_exprs_stack); 1529 m_avail_exprs_stack->pop_to_marker (); 1530 1531 edge taken_edge = NULL; 1532 /* Initialize visited flag ahead of us, it has undefined state on 1533 pass entry. */ 1534 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1535 gimple_set_visited (gsi_stmt (gsi), false); 1536 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);) 1537 { 1538 /* Do not optimize a stmt twice, substitution might end up with 1539 _3 = _3 which is not valid. */ 1540 if (gimple_visited_p (gsi_stmt (gsi))) 1541 { 1542 gsi_next (&gsi); 1543 continue; 1544 } 1545 1546 m_state->record_ranges_from_stmt (gsi_stmt (gsi), false); 1547 bool removed_p = false; 1548 taken_edge = this->optimize_stmt (bb, &gsi, &removed_p); 1549 if (!removed_p) 1550 gimple_set_visited (gsi_stmt (gsi), true); 1551 1552 /* Go back and visit stmts inserted by folding after substituting 1553 into the stmt at gsi. */ 1554 if (gsi_end_p (gsi)) 1555 { 1556 gcc_checking_assert (removed_p); 1557 gsi = gsi_last_bb (bb); 1558 while (!gsi_end_p (gsi) && !gimple_visited_p (gsi_stmt (gsi))) 1559 gsi_prev (&gsi); 1560 } 1561 else 1562 { 1563 do 1564 { 1565 gsi_prev (&gsi); 1566 } 1567 while (!gsi_end_p (gsi) && !gimple_visited_p (gsi_stmt (gsi))); 1568 } 1569 if (gsi_end_p (gsi)) 1570 gsi = gsi_start_bb (bb); 1571 else 1572 gsi_next (&gsi); 1573 } 1574 1575 /* Now prepare to process dominated blocks. */ 1576 record_edge_info (bb); 1577 cprop_into_successor_phis (bb, m_const_and_copies); 1578 if (taken_edge && !dbg_cnt (dom_unreachable_edges)) 1579 return NULL; 1580 1581 return taken_edge; 1582} 1583 1584/* We have finished processing the dominator children of BB, perform 1585 any finalization actions in preparation for leaving this node in 1586 the dominator tree. */ 1587 1588void 1589dom_opt_dom_walker::after_dom_children (basic_block bb) 1590{ 1591 m_threader->thread_outgoing_edges (bb); 1592 m_avail_exprs_stack->pop_to_marker (); 1593 m_const_and_copies->pop_to_marker (); 1594 m_evrp_range_analyzer->leave (bb); 1595} 1596 1597/* Search for redundant computations in STMT. If any are found, then 1598 replace them with the variable holding the result of the computation. 1599 1600 If safe, record this expression into AVAIL_EXPRS_STACK and 1601 CONST_AND_COPIES. */ 1602 1603static void 1604eliminate_redundant_computations (gimple_stmt_iterator* gsi, 1605 class const_and_copies *const_and_copies, 1606 class avail_exprs_stack *avail_exprs_stack) 1607{ 1608 tree expr_type; 1609 tree cached_lhs; 1610 tree def; 1611 bool insert = true; 1612 bool assigns_var_p = false; 1613 1614 gimple *stmt = gsi_stmt (*gsi); 1615 1616 if (gimple_code (stmt) == GIMPLE_PHI) 1617 def = gimple_phi_result (stmt); 1618 else 1619 def = gimple_get_lhs (stmt); 1620 1621 /* Certain expressions on the RHS can be optimized away, but cannot 1622 themselves be entered into the hash tables. */ 1623 if (! def 1624 || TREE_CODE (def) != SSA_NAME 1625 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) 1626 || gimple_vdef (stmt) 1627 /* Do not record equivalences for increments of ivs. This would create 1628 overlapping live ranges for a very questionable gain. */ 1629 || simple_iv_increment_p (stmt)) 1630 insert = false; 1631 1632 /* Check if the expression has been computed before. */ 1633 cached_lhs = avail_exprs_stack->lookup_avail_expr (stmt, insert, true); 1634 1635 opt_stats.num_exprs_considered++; 1636 1637 /* Get the type of the expression we are trying to optimize. */ 1638 if (is_gimple_assign (stmt)) 1639 { 1640 expr_type = TREE_TYPE (gimple_assign_lhs (stmt)); 1641 assigns_var_p = true; 1642 } 1643 else if (gimple_code (stmt) == GIMPLE_COND) 1644 expr_type = boolean_type_node; 1645 else if (is_gimple_call (stmt)) 1646 { 1647 gcc_assert (gimple_call_lhs (stmt)); 1648 expr_type = TREE_TYPE (gimple_call_lhs (stmt)); 1649 assigns_var_p = true; 1650 } 1651 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) 1652 expr_type = TREE_TYPE (gimple_switch_index (swtch_stmt)); 1653 else if (gimple_code (stmt) == GIMPLE_PHI) 1654 /* We can't propagate into a phi, so the logic below doesn't apply. 1655 Instead record an equivalence between the cached LHS and the 1656 PHI result of this statement, provided they are in the same block. 1657 This should be sufficient to kill the redundant phi. */ 1658 { 1659 if (def && cached_lhs) 1660 const_and_copies->record_const_or_copy (def, cached_lhs); 1661 return; 1662 } 1663 else 1664 gcc_unreachable (); 1665 1666 if (!cached_lhs) 1667 return; 1668 1669 /* It is safe to ignore types here since we have already done 1670 type checking in the hashing and equality routines. In fact 1671 type checking here merely gets in the way of constant 1672 propagation. Also, make sure that it is safe to propagate 1673 CACHED_LHS into the expression in STMT. */ 1674 if ((TREE_CODE (cached_lhs) != SSA_NAME 1675 && (assigns_var_p 1676 || useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs)))) 1677 || may_propagate_copy_into_stmt (stmt, cached_lhs)) 1678 { 1679 gcc_checking_assert (TREE_CODE (cached_lhs) == SSA_NAME 1680 || is_gimple_min_invariant (cached_lhs)); 1681 1682 if (dump_file && (dump_flags & TDF_DETAILS)) 1683 { 1684 fprintf (dump_file, " Replaced redundant expr '"); 1685 print_gimple_expr (dump_file, stmt, 0, dump_flags); 1686 fprintf (dump_file, "' with '"); 1687 print_generic_expr (dump_file, cached_lhs, dump_flags); 1688 fprintf (dump_file, "'\n"); 1689 } 1690 1691 opt_stats.num_re++; 1692 1693 if (assigns_var_p 1694 && !useless_type_conversion_p (expr_type, TREE_TYPE (cached_lhs))) 1695 cached_lhs = fold_convert (expr_type, cached_lhs); 1696 1697 propagate_tree_value_into_stmt (gsi, cached_lhs); 1698 1699 /* Since it is always necessary to mark the result as modified, 1700 perhaps we should move this into propagate_tree_value_into_stmt 1701 itself. */ 1702 gimple_set_modified (gsi_stmt (*gsi), true); 1703 } 1704} 1705 1706/* STMT, a GIMPLE_ASSIGN, may create certain equivalences, in either 1707 the available expressions table or the const_and_copies table. 1708 Detect and record those equivalences into AVAIL_EXPRS_STACK. 1709 1710 We handle only very simple copy equivalences here. The heavy 1711 lifing is done by eliminate_redundant_computations. */ 1712 1713static void 1714record_equivalences_from_stmt (gimple *stmt, int may_optimize_p, 1715 class avail_exprs_stack *avail_exprs_stack) 1716{ 1717 tree lhs; 1718 enum tree_code lhs_code; 1719 1720 gcc_assert (is_gimple_assign (stmt)); 1721 1722 lhs = gimple_assign_lhs (stmt); 1723 lhs_code = TREE_CODE (lhs); 1724 1725 if (lhs_code == SSA_NAME 1726 && gimple_assign_single_p (stmt)) 1727 { 1728 tree rhs = gimple_assign_rhs1 (stmt); 1729 1730 /* If the RHS of the assignment is a constant or another variable that 1731 may be propagated, register it in the CONST_AND_COPIES table. We 1732 do not need to record unwind data for this, since this is a true 1733 assignment and not an equivalence inferred from a comparison. All 1734 uses of this ssa name are dominated by this assignment, so unwinding 1735 just costs time and space. */ 1736 if (may_optimize_p 1737 && (TREE_CODE (rhs) == SSA_NAME 1738 || is_gimple_min_invariant (rhs))) 1739 { 1740 rhs = dom_valueize (rhs); 1741 1742 if (dump_file && (dump_flags & TDF_DETAILS)) 1743 { 1744 fprintf (dump_file, "==== ASGN "); 1745 print_generic_expr (dump_file, lhs); 1746 fprintf (dump_file, " = "); 1747 print_generic_expr (dump_file, rhs); 1748 fprintf (dump_file, "\n"); 1749 } 1750 1751 set_ssa_name_value (lhs, rhs); 1752 } 1753 } 1754 1755 /* Make sure we can propagate &x + CST. */ 1756 if (lhs_code == SSA_NAME 1757 && gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR 1758 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR 1759 && TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST) 1760 { 1761 tree op0 = gimple_assign_rhs1 (stmt); 1762 tree op1 = gimple_assign_rhs2 (stmt); 1763 tree new_rhs 1764 = build1 (ADDR_EXPR, TREE_TYPE (op0), 1765 fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (op0)), 1766 unshare_expr (op0), fold_convert (ptr_type_node, 1767 op1))); 1768 if (dump_file && (dump_flags & TDF_DETAILS)) 1769 { 1770 fprintf (dump_file, "==== ASGN "); 1771 print_generic_expr (dump_file, lhs); 1772 fprintf (dump_file, " = "); 1773 print_generic_expr (dump_file, new_rhs); 1774 fprintf (dump_file, "\n"); 1775 } 1776 1777 set_ssa_name_value (lhs, new_rhs); 1778 } 1779 1780 /* A memory store, even an aliased store, creates a useful 1781 equivalence. By exchanging the LHS and RHS, creating suitable 1782 vops and recording the result in the available expression table, 1783 we may be able to expose more redundant loads. */ 1784 if (!gimple_has_volatile_ops (stmt) 1785 && gimple_references_memory_p (stmt) 1786 && gimple_assign_single_p (stmt) 1787 && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME 1788 || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))) 1789 && !is_gimple_reg (lhs)) 1790 { 1791 tree rhs = gimple_assign_rhs1 (stmt); 1792 gassign *new_stmt; 1793 1794 /* Build a new statement with the RHS and LHS exchanged. */ 1795 if (TREE_CODE (rhs) == SSA_NAME) 1796 { 1797 /* NOTE tuples. The call to gimple_build_assign below replaced 1798 a call to build_gimple_modify_stmt, which did not set the 1799 SSA_NAME_DEF_STMT on the LHS of the assignment. Doing so 1800 may cause an SSA validation failure, as the LHS may be a 1801 default-initialized name and should have no definition. I'm 1802 a bit dubious of this, as the artificial statement that we 1803 generate here may in fact be ill-formed, but it is simply 1804 used as an internal device in this pass, and never becomes 1805 part of the CFG. */ 1806 gimple *defstmt = SSA_NAME_DEF_STMT (rhs); 1807 new_stmt = gimple_build_assign (rhs, lhs); 1808 SSA_NAME_DEF_STMT (rhs) = defstmt; 1809 } 1810 else 1811 new_stmt = gimple_build_assign (rhs, lhs); 1812 1813 gimple_set_vuse (new_stmt, gimple_vdef (stmt)); 1814 1815 /* Finally enter the statement into the available expression 1816 table. */ 1817 avail_exprs_stack->lookup_avail_expr (new_stmt, true, true); 1818 } 1819} 1820 1821/* Replace *OP_P in STMT with any known equivalent value for *OP_P from 1822 CONST_AND_COPIES. */ 1823 1824static void 1825cprop_operand (gimple *stmt, use_operand_p op_p, range_query *query) 1826{ 1827 tree val; 1828 tree op = USE_FROM_PTR (op_p); 1829 1830 /* If the operand has a known constant value or it is known to be a 1831 copy of some other variable, use the value or copy stored in 1832 CONST_AND_COPIES. */ 1833 val = SSA_NAME_VALUE (op); 1834 if (!val) 1835 { 1836 value_range r; 1837 tree single; 1838 if (query->range_of_expr (r, op, stmt) && r.singleton_p (&single)) 1839 val = single; 1840 } 1841 1842 if (val && val != op) 1843 { 1844 /* Do not replace hard register operands in asm statements. */ 1845 if (gimple_code (stmt) == GIMPLE_ASM 1846 && !may_propagate_copy_into_asm (op)) 1847 return; 1848 1849 /* Certain operands are not allowed to be copy propagated due 1850 to their interaction with exception handling and some GCC 1851 extensions. */ 1852 if (!may_propagate_copy (op, val)) 1853 return; 1854 1855 /* Do not propagate copies into BIVs. 1856 See PR23821 and PR62217 for how this can disturb IV and 1857 number of iteration analysis. */ 1858 if (TREE_CODE (val) != INTEGER_CST) 1859 { 1860 gimple *def = SSA_NAME_DEF_STMT (op); 1861 if (gimple_code (def) == GIMPLE_PHI 1862 && gimple_bb (def)->loop_father->header == gimple_bb (def)) 1863 return; 1864 } 1865 1866 /* Dump details. */ 1867 if (dump_file && (dump_flags & TDF_DETAILS)) 1868 { 1869 fprintf (dump_file, " Replaced '"); 1870 print_generic_expr (dump_file, op, dump_flags); 1871 fprintf (dump_file, "' with %s '", 1872 (TREE_CODE (val) != SSA_NAME ? "constant" : "variable")); 1873 print_generic_expr (dump_file, val, dump_flags); 1874 fprintf (dump_file, "'\n"); 1875 } 1876 1877 if (TREE_CODE (val) != SSA_NAME) 1878 opt_stats.num_const_prop++; 1879 else 1880 opt_stats.num_copy_prop++; 1881 1882 propagate_value (op_p, val); 1883 1884 /* And note that we modified this statement. This is now 1885 safe, even if we changed virtual operands since we will 1886 rescan the statement and rewrite its operands again. */ 1887 gimple_set_modified (stmt, true); 1888 } 1889} 1890 1891/* CONST_AND_COPIES is a table which maps an SSA_NAME to the current 1892 known value for that SSA_NAME (or NULL if no value is known). 1893 1894 Propagate values from CONST_AND_COPIES into the uses, vuses and 1895 vdef_ops of STMT. */ 1896 1897static void 1898cprop_into_stmt (gimple *stmt, range_query *query) 1899{ 1900 use_operand_p op_p; 1901 ssa_op_iter iter; 1902 tree last_copy_propagated_op = NULL; 1903 1904 FOR_EACH_SSA_USE_OPERAND (op_p, stmt, iter, SSA_OP_USE) 1905 { 1906 tree old_op = USE_FROM_PTR (op_p); 1907 1908 /* If we have A = B and B = A in the copy propagation tables 1909 (due to an equality comparison), avoid substituting B for A 1910 then A for B in the trivially discovered cases. This allows 1911 optimization of statements were A and B appear as input 1912 operands. */ 1913 if (old_op != last_copy_propagated_op) 1914 { 1915 cprop_operand (stmt, op_p, query); 1916 1917 tree new_op = USE_FROM_PTR (op_p); 1918 if (new_op != old_op && TREE_CODE (new_op) == SSA_NAME) 1919 last_copy_propagated_op = new_op; 1920 } 1921 } 1922} 1923 1924/* If STMT contains a relational test, try to convert it into an 1925 equality test if there is only a single value which can ever 1926 make the test true. 1927 1928 For example, if the expression hash table contains: 1929 1930 TRUE = (i <= 1) 1931 1932 And we have a test within statement of i >= 1, then we can safely 1933 rewrite the test as i == 1 since there only a single value where 1934 the test is true. 1935 1936 This is similar to code in VRP. */ 1937 1938void 1939dom_opt_dom_walker::test_for_singularity (gimple *stmt, 1940 avail_exprs_stack *avail_exprs_stack) 1941{ 1942 /* We want to support gimple conditionals as well as assignments 1943 where the RHS contains a conditional. */ 1944 if (is_gimple_assign (stmt) || gimple_code (stmt) == GIMPLE_COND) 1945 { 1946 enum tree_code code = ERROR_MARK; 1947 tree lhs, rhs; 1948 1949 /* Extract the condition of interest from both forms we support. */ 1950 if (is_gimple_assign (stmt)) 1951 { 1952 code = gimple_assign_rhs_code (stmt); 1953 lhs = gimple_assign_rhs1 (stmt); 1954 rhs = gimple_assign_rhs2 (stmt); 1955 } 1956 else if (gimple_code (stmt) == GIMPLE_COND) 1957 { 1958 code = gimple_cond_code (as_a <gcond *> (stmt)); 1959 lhs = gimple_cond_lhs (as_a <gcond *> (stmt)); 1960 rhs = gimple_cond_rhs (as_a <gcond *> (stmt)); 1961 } 1962 1963 /* We're looking for a relational test using LE/GE. Also note we can 1964 canonicalize LT/GT tests against constants into LE/GT tests. */ 1965 if (code == LE_EXPR || code == GE_EXPR 1966 || ((code == LT_EXPR || code == GT_EXPR) 1967 && TREE_CODE (rhs) == INTEGER_CST)) 1968 { 1969 /* For LT_EXPR and GT_EXPR, canonicalize to LE_EXPR and GE_EXPR. */ 1970 if (code == LT_EXPR) 1971 rhs = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs), 1972 rhs, build_int_cst (TREE_TYPE (rhs), 1)); 1973 1974 if (code == GT_EXPR) 1975 rhs = fold_build2 (PLUS_EXPR, TREE_TYPE (rhs), 1976 rhs, build_int_cst (TREE_TYPE (rhs), 1)); 1977 1978 /* Determine the code we want to check for in the hash table. */ 1979 enum tree_code test_code; 1980 if (code == GE_EXPR || code == GT_EXPR) 1981 test_code = LE_EXPR; 1982 else 1983 test_code = GE_EXPR; 1984 1985 /* Update the dummy statement so we can query the hash tables. */ 1986 gimple_cond_set_code (m_dummy_cond, test_code); 1987 gimple_cond_set_lhs (m_dummy_cond, lhs); 1988 gimple_cond_set_rhs (m_dummy_cond, rhs); 1989 tree cached_lhs 1990 = avail_exprs_stack->lookup_avail_expr (m_dummy_cond, 1991 false, false); 1992 1993 /* If the lookup returned 1 (true), then the expression we 1994 queried was in the hash table. As a result there is only 1995 one value that makes the original conditional true. Update 1996 STMT accordingly. */ 1997 if (cached_lhs && integer_onep (cached_lhs)) 1998 { 1999 if (is_gimple_assign (stmt)) 2000 { 2001 gimple_assign_set_rhs_code (stmt, EQ_EXPR); 2002 gimple_assign_set_rhs2 (stmt, rhs); 2003 gimple_set_modified (stmt, true); 2004 } 2005 else 2006 { 2007 gimple_set_modified (stmt, true); 2008 gimple_cond_set_code (as_a <gcond *> (stmt), EQ_EXPR); 2009 gimple_cond_set_rhs (as_a <gcond *> (stmt), rhs); 2010 gimple_set_modified (stmt, true); 2011 } 2012 } 2013 } 2014 } 2015} 2016 2017/* If STMT is a comparison of two uniform vectors reduce it to a comparison 2018 of scalar objects, otherwise leave STMT unchanged. */ 2019 2020static void 2021reduce_vector_comparison_to_scalar_comparison (gimple *stmt) 2022{ 2023 if (gimple_code (stmt) == GIMPLE_COND) 2024 { 2025 tree lhs = gimple_cond_lhs (stmt); 2026 tree rhs = gimple_cond_rhs (stmt); 2027 2028 /* We may have a vector comparison where both arms are uniform 2029 vectors. If so, we can simplify the vector comparison down 2030 to a scalar comparison. */ 2031 if (TREE_CODE (TREE_TYPE (lhs)) == VECTOR_TYPE 2032 && TREE_CODE (TREE_TYPE (rhs)) == VECTOR_TYPE) 2033 { 2034 /* If either operand is an SSA_NAME, then look back to its 2035 defining statement to try and get at a suitable source. */ 2036 if (TREE_CODE (rhs) == SSA_NAME) 2037 { 2038 gimple *def_stmt = SSA_NAME_DEF_STMT (rhs); 2039 if (gimple_assign_single_p (def_stmt)) 2040 rhs = gimple_assign_rhs1 (def_stmt); 2041 } 2042 2043 if (TREE_CODE (lhs) == SSA_NAME) 2044 { 2045 gimple *def_stmt = SSA_NAME_DEF_STMT (lhs); 2046 if (gimple_assign_single_p (def_stmt)) 2047 lhs = gimple_assign_rhs1 (def_stmt); 2048 } 2049 2050 /* Now see if they are both uniform vectors and if so replace 2051 the vector comparison with a scalar comparison. */ 2052 tree rhs_elem = rhs ? uniform_vector_p (rhs) : NULL_TREE; 2053 tree lhs_elem = lhs ? uniform_vector_p (lhs) : NULL_TREE; 2054 if (rhs_elem && lhs_elem) 2055 { 2056 if (dump_file && dump_flags & TDF_DETAILS) 2057 { 2058 fprintf (dump_file, "Reducing vector comparison: "); 2059 print_gimple_stmt (dump_file, stmt, 0); 2060 } 2061 2062 gimple_cond_set_rhs (as_a <gcond *>(stmt), rhs_elem); 2063 gimple_cond_set_lhs (as_a <gcond *>(stmt), lhs_elem); 2064 gimple_set_modified (stmt, true); 2065 2066 if (dump_file && dump_flags & TDF_DETAILS) 2067 { 2068 fprintf (dump_file, "To scalar equivalent: "); 2069 print_gimple_stmt (dump_file, stmt, 0); 2070 fprintf (dump_file, "\n"); 2071 } 2072 } 2073 } 2074 } 2075} 2076 2077/* Optimize the statement in block BB pointed to by iterator SI. 2078 2079 We try to perform some simplistic global redundancy elimination and 2080 constant propagation: 2081 2082 1- To detect global redundancy, we keep track of expressions that have 2083 been computed in this block and its dominators. If we find that the 2084 same expression is computed more than once, we eliminate repeated 2085 computations by using the target of the first one. 2086 2087 2- Constant values and copy assignments. This is used to do very 2088 simplistic constant and copy propagation. When a constant or copy 2089 assignment is found, we map the value on the RHS of the assignment to 2090 the variable in the LHS in the CONST_AND_COPIES table. 2091 2092 3- Very simple redundant store elimination is performed. 2093 2094 4- We can simplify a condition to a constant or from a relational 2095 condition to an equality condition. */ 2096 2097edge 2098dom_opt_dom_walker::optimize_stmt (basic_block bb, gimple_stmt_iterator *si, 2099 bool *removed_p) 2100{ 2101 gimple *stmt, *old_stmt; 2102 bool may_optimize_p; 2103 bool modified_p = false; 2104 bool was_noreturn; 2105 edge retval = NULL; 2106 2107 old_stmt = stmt = gsi_stmt (*si); 2108 was_noreturn = is_gimple_call (stmt) && gimple_call_noreturn_p (stmt); 2109 2110 if (dump_file && (dump_flags & TDF_DETAILS)) 2111 { 2112 fprintf (dump_file, "Optimizing statement "); 2113 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2114 } 2115 2116 /* STMT may be a comparison of uniform vectors that we can simplify 2117 down to a comparison of scalars. Do that transformation first 2118 so that all the scalar optimizations from here onward apply. */ 2119 reduce_vector_comparison_to_scalar_comparison (stmt); 2120 2121 update_stmt_if_modified (stmt); 2122 opt_stats.num_stmts++; 2123 2124 /* Const/copy propagate into USES, VUSES and the RHS of VDEFs. */ 2125 cprop_into_stmt (stmt, m_evrp_range_analyzer); 2126 2127 /* If the statement has been modified with constant replacements, 2128 fold its RHS before checking for redundant computations. */ 2129 if (gimple_modified_p (stmt)) 2130 { 2131 tree rhs = NULL; 2132 2133 /* Try to fold the statement making sure that STMT is kept 2134 up to date. */ 2135 if (fold_stmt (si)) 2136 { 2137 stmt = gsi_stmt (*si); 2138 gimple_set_modified (stmt, true); 2139 2140 if (dump_file && (dump_flags & TDF_DETAILS)) 2141 { 2142 fprintf (dump_file, " Folded to: "); 2143 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); 2144 } 2145 } 2146 2147 /* We only need to consider cases that can yield a gimple operand. */ 2148 if (gimple_assign_single_p (stmt)) 2149 rhs = gimple_assign_rhs1 (stmt); 2150 else if (gimple_code (stmt) == GIMPLE_GOTO) 2151 rhs = gimple_goto_dest (stmt); 2152 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) 2153 /* This should never be an ADDR_EXPR. */ 2154 rhs = gimple_switch_index (swtch_stmt); 2155 2156 if (rhs && TREE_CODE (rhs) == ADDR_EXPR) 2157 recompute_tree_invariant_for_addr_expr (rhs); 2158 2159 /* Indicate that maybe_clean_or_replace_eh_stmt needs to be called, 2160 even if fold_stmt updated the stmt already and thus cleared 2161 gimple_modified_p flag on it. */ 2162 modified_p = true; 2163 } 2164 2165 /* Check for redundant computations. Do this optimization only 2166 for assignments that have no volatile ops and conditionals. */ 2167 may_optimize_p = (!gimple_has_side_effects (stmt) 2168 && (is_gimple_assign (stmt) 2169 || (is_gimple_call (stmt) 2170 && gimple_call_lhs (stmt) != NULL_TREE) 2171 || gimple_code (stmt) == GIMPLE_COND 2172 || gimple_code (stmt) == GIMPLE_SWITCH)); 2173 2174 if (may_optimize_p) 2175 { 2176 if (gimple_code (stmt) == GIMPLE_CALL) 2177 { 2178 /* Resolve __builtin_constant_p. If it hasn't been 2179 folded to integer_one_node by now, it's fairly 2180 certain that the value simply isn't constant. */ 2181 tree callee = gimple_call_fndecl (stmt); 2182 if (callee 2183 && fndecl_built_in_p (callee, BUILT_IN_CONSTANT_P)) 2184 { 2185 propagate_tree_value_into_stmt (si, integer_zero_node); 2186 stmt = gsi_stmt (*si); 2187 } 2188 } 2189 2190 if (gimple_code (stmt) == GIMPLE_COND) 2191 { 2192 tree lhs = gimple_cond_lhs (stmt); 2193 tree rhs = gimple_cond_rhs (stmt); 2194 2195 /* If the LHS has a range [0..1] and the RHS has a range ~[0..1], 2196 then this conditional is computable at compile time. We can just 2197 shove either 0 or 1 into the LHS, mark the statement as modified 2198 and all the right things will just happen below. 2199 2200 Note this would apply to any case where LHS has a range 2201 narrower than its type implies and RHS is outside that 2202 narrower range. Future work. */ 2203 if (TREE_CODE (lhs) == SSA_NAME 2204 && ssa_name_has_boolean_range (lhs) 2205 && TREE_CODE (rhs) == INTEGER_CST 2206 && ! (integer_zerop (rhs) || integer_onep (rhs))) 2207 { 2208 gimple_cond_set_lhs (as_a <gcond *> (stmt), 2209 fold_convert (TREE_TYPE (lhs), 2210 integer_zero_node)); 2211 gimple_set_modified (stmt, true); 2212 } 2213 else if (TREE_CODE (lhs) == SSA_NAME) 2214 { 2215 /* Exploiting EVRP data is not yet fully integrated into DOM 2216 but we need to do something for this case to avoid regressing 2217 udr4.f90 and new1.C which have unexecutable blocks with 2218 undefined behavior that get diagnosed if they're left in the 2219 IL because we've attached range information to new 2220 SSA_NAMES. */ 2221 update_stmt_if_modified (stmt); 2222 edge taken_edge = NULL; 2223 simplify_using_ranges simpl (m_evrp_range_analyzer); 2224 simpl.vrp_visit_cond_stmt (as_a <gcond *> (stmt), &taken_edge); 2225 if (taken_edge) 2226 { 2227 if (taken_edge->flags & EDGE_TRUE_VALUE) 2228 gimple_cond_make_true (as_a <gcond *> (stmt)); 2229 else if (taken_edge->flags & EDGE_FALSE_VALUE) 2230 gimple_cond_make_false (as_a <gcond *> (stmt)); 2231 else 2232 gcc_unreachable (); 2233 gimple_set_modified (stmt, true); 2234 update_stmt (stmt); 2235 cfg_altered = true; 2236 return taken_edge; 2237 } 2238 } 2239 } 2240 2241 update_stmt_if_modified (stmt); 2242 eliminate_redundant_computations (si, m_const_and_copies, 2243 m_avail_exprs_stack); 2244 stmt = gsi_stmt (*si); 2245 2246 /* Perform simple redundant store elimination. */ 2247 if (gimple_assign_single_p (stmt) 2248 && TREE_CODE (gimple_assign_lhs (stmt)) != SSA_NAME) 2249 { 2250 tree lhs = gimple_assign_lhs (stmt); 2251 tree rhs = gimple_assign_rhs1 (stmt); 2252 tree cached_lhs; 2253 gassign *new_stmt; 2254 rhs = dom_valueize (rhs); 2255 /* Build a new statement with the RHS and LHS exchanged. */ 2256 if (TREE_CODE (rhs) == SSA_NAME) 2257 { 2258 gimple *defstmt = SSA_NAME_DEF_STMT (rhs); 2259 new_stmt = gimple_build_assign (rhs, lhs); 2260 SSA_NAME_DEF_STMT (rhs) = defstmt; 2261 } 2262 else 2263 new_stmt = gimple_build_assign (rhs, lhs); 2264 gimple_set_vuse (new_stmt, gimple_vuse (stmt)); 2265 expr_hash_elt *elt = NULL; 2266 cached_lhs = m_avail_exprs_stack->lookup_avail_expr (new_stmt, false, 2267 false, &elt); 2268 if (cached_lhs 2269 && operand_equal_p (rhs, cached_lhs, 0) 2270 && refs_same_for_tbaa_p (elt->expr ()->kind == EXPR_SINGLE 2271 ? elt->expr ()->ops.single.rhs 2272 : NULL_TREE, lhs)) 2273 { 2274 basic_block bb = gimple_bb (stmt); 2275 unlink_stmt_vdef (stmt); 2276 if (gsi_remove (si, true)) 2277 { 2278 bitmap_set_bit (need_eh_cleanup, bb->index); 2279 if (dump_file && (dump_flags & TDF_DETAILS)) 2280 fprintf (dump_file, " Flagged to clear EH edges.\n"); 2281 } 2282 release_defs (stmt); 2283 *removed_p = true; 2284 return retval; 2285 } 2286 } 2287 2288 /* If this statement was not redundant, we may still be able to simplify 2289 it, which may in turn allow other part of DOM or other passes to do 2290 a better job. */ 2291 test_for_singularity (stmt, m_avail_exprs_stack); 2292 } 2293 2294 /* Record any additional equivalences created by this statement. */ 2295 if (is_gimple_assign (stmt)) 2296 record_equivalences_from_stmt (stmt, may_optimize_p, m_avail_exprs_stack); 2297 2298 /* If STMT is a COND_EXPR or SWITCH_EXPR and it was modified, then we may 2299 know where it goes. */ 2300 if (gimple_modified_p (stmt) || modified_p) 2301 { 2302 tree val = NULL; 2303 2304 if (gimple_code (stmt) == GIMPLE_COND) 2305 val = fold_binary_loc (gimple_location (stmt), 2306 gimple_cond_code (stmt), boolean_type_node, 2307 gimple_cond_lhs (stmt), 2308 gimple_cond_rhs (stmt)); 2309 else if (gswitch *swtch_stmt = dyn_cast <gswitch *> (stmt)) 2310 val = gimple_switch_index (swtch_stmt); 2311 2312 if (val && TREE_CODE (val) == INTEGER_CST) 2313 { 2314 retval = find_taken_edge (bb, val); 2315 if (retval) 2316 { 2317 /* Fix the condition to be either true or false. */ 2318 if (gimple_code (stmt) == GIMPLE_COND) 2319 { 2320 if (integer_zerop (val)) 2321 gimple_cond_make_false (as_a <gcond *> (stmt)); 2322 else if (integer_onep (val)) 2323 gimple_cond_make_true (as_a <gcond *> (stmt)); 2324 else 2325 gcc_unreachable (); 2326 2327 gimple_set_modified (stmt, true); 2328 } 2329 2330 /* Further simplifications may be possible. */ 2331 cfg_altered = true; 2332 } 2333 } 2334 2335 update_stmt_if_modified (stmt); 2336 2337 /* If we simplified a statement in such a way as to be shown that it 2338 cannot trap, update the eh information and the cfg to match. */ 2339 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)) 2340 { 2341 bitmap_set_bit (need_eh_cleanup, bb->index); 2342 if (dump_file && (dump_flags & TDF_DETAILS)) 2343 fprintf (dump_file, " Flagged to clear EH edges.\n"); 2344 } 2345 2346 if (!was_noreturn 2347 && is_gimple_call (stmt) && gimple_call_noreturn_p (stmt)) 2348 need_noreturn_fixup.safe_push (stmt); 2349 } 2350 return retval; 2351} 2352