1/* Interprocedural Identical Code Folding pass 2 Copyright (C) 2014-2015 Free Software Foundation, Inc. 3 4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz> 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 3, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "hash-set.h" 26#include "machmode.h" 27#include "vec.h" 28#include "double-int.h" 29#include "input.h" 30#include "alias.h" 31#include "symtab.h" 32#include "options.h" 33#include "wide-int.h" 34#include "inchash.h" 35#include "tree.h" 36#include "fold-const.h" 37#include "predict.h" 38#include "tm.h" 39#include "hard-reg-set.h" 40#include "function.h" 41#include "basic-block.h" 42#include "tree-ssa-alias.h" 43#include "internal-fn.h" 44#include "gimple-expr.h" 45#include "is-a.h" 46#include "gimple.h" 47#include "hashtab.h" 48#include "rtl.h" 49#include "flags.h" 50#include "statistics.h" 51#include "real.h" 52#include "fixed-value.h" 53#include "insn-config.h" 54#include "expmed.h" 55#include "dojump.h" 56#include "explow.h" 57#include "calls.h" 58#include "emit-rtl.h" 59#include "varasm.h" 60#include "stmt.h" 61#include "expr.h" 62#include "gimple-iterator.h" 63#include "gimple-ssa.h" 64#include "tree-cfg.h" 65#include "stringpool.h" 66#include "tree-dfa.h" 67#include "tree-pass.h" 68#include "gimple-pretty-print.h" 69#include "cfgloop.h" 70#include "except.h" 71#include "hash-map.h" 72#include "plugin-api.h" 73#include "ipa-ref.h" 74#include "cgraph.h" 75#include "data-streamer.h" 76#include "ipa-utils.h" 77#include <list> 78#include "tree-ssanames.h" 79#include "tree-eh.h" 80#include "builtins.h" 81 82#include "ipa-icf-gimple.h" 83#include "ipa-icf.h" 84 85namespace ipa_icf_gimple { 86 87/* Initialize internal structures for a given SOURCE_FUNC_DECL and 88 TARGET_FUNC_DECL. Strict polymorphic comparison is processed if 89 an option COMPARE_POLYMORPHIC is true. For special cases, one can 90 set IGNORE_LABELS to skip label comparison. 91 Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets 92 of declarations that can be skipped. */ 93 94func_checker::func_checker (tree source_func_decl, tree target_func_decl, 95 bool compare_polymorphic, 96 bool ignore_labels, 97 hash_set<symtab_node *> *ignored_source_nodes, 98 hash_set<symtab_node *> *ignored_target_nodes) 99 : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl), 100 m_ignored_source_nodes (ignored_source_nodes), 101 m_ignored_target_nodes (ignored_target_nodes), 102 m_compare_polymorphic (compare_polymorphic), 103 m_ignore_labels (ignore_labels) 104{ 105 function *source_func = DECL_STRUCT_FUNCTION (source_func_decl); 106 function *target_func = DECL_STRUCT_FUNCTION (target_func_decl); 107 108 unsigned ssa_source = SSANAMES (source_func)->length (); 109 unsigned ssa_target = SSANAMES (target_func)->length (); 110 111 m_source_ssa_names.create (ssa_source); 112 m_target_ssa_names.create (ssa_target); 113 114 for (unsigned i = 0; i < ssa_source; i++) 115 m_source_ssa_names.safe_push (-1); 116 117 for (unsigned i = 0; i < ssa_target; i++) 118 m_target_ssa_names.safe_push (-1); 119} 120 121/* Memory release routine. */ 122 123func_checker::~func_checker () 124{ 125 m_source_ssa_names.release(); 126 m_target_ssa_names.release(); 127} 128 129/* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */ 130 131bool 132func_checker::compare_ssa_name (tree t1, tree t2) 133{ 134 gcc_assert (TREE_CODE (t1) == SSA_NAME); 135 gcc_assert (TREE_CODE (t2) == SSA_NAME); 136 137 unsigned i1 = SSA_NAME_VERSION (t1); 138 unsigned i2 = SSA_NAME_VERSION (t2); 139 140 if (m_source_ssa_names[i1] == -1) 141 m_source_ssa_names[i1] = i2; 142 else if (m_source_ssa_names[i1] != (int) i2) 143 return false; 144 145 if(m_target_ssa_names[i2] == -1) 146 m_target_ssa_names[i2] = i1; 147 else if (m_target_ssa_names[i2] != (int) i1) 148 return false; 149 150 if (SSA_NAME_IS_DEFAULT_DEF (t1)) 151 { 152 tree b1 = SSA_NAME_VAR (t1); 153 tree b2 = SSA_NAME_VAR (t2); 154 155 if (b1 == NULL && b2 == NULL) 156 return true; 157 158 if (b1 == NULL || b2 == NULL || TREE_CODE (b1) != TREE_CODE (b2)) 159 return return_false (); 160 161 return compare_cst_or_decl (b1, b2); 162 } 163 164 return true; 165} 166 167/* Verification function for edges E1 and E2. */ 168 169bool 170func_checker::compare_edge (edge e1, edge e2) 171{ 172 if (e1->flags != e2->flags) 173 return false; 174 175 bool existed_p; 176 177 edge &slot = m_edge_map.get_or_insert (e1, &existed_p); 178 if (existed_p) 179 return return_with_debug (slot == e2); 180 else 181 slot = e2; 182 183 /* TODO: filter edge probabilities for profile feedback match. */ 184 185 return true; 186} 187 188/* Verification function for declaration trees T1 and T2 that 189 come from functions FUNC1 and FUNC2. */ 190 191bool 192func_checker::compare_decl (tree t1, tree t2) 193{ 194 if (!auto_var_in_fn_p (t1, m_source_func_decl) 195 || !auto_var_in_fn_p (t2, m_target_func_decl)) 196 return return_with_debug (t1 == t2); 197 198 tree_code t = TREE_CODE (t1); 199 if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL) 200 && DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2)) 201 return return_false_with_msg ("DECL_BY_REFERENCE flags are different"); 202 203 if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2))) 204 return return_false (); 205 206 /* TODO: we are actually too strict here. We only need to compare if 207 T1 can be used in polymorphic call. */ 208 if (TREE_ADDRESSABLE (t1) 209 && m_compare_polymorphic 210 && !compatible_polymorphic_types_p (TREE_TYPE (t1), TREE_TYPE (t2), 211 false)) 212 return return_false (); 213 214 if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL) 215 && DECL_BY_REFERENCE (t1) 216 && m_compare_polymorphic 217 && !compatible_polymorphic_types_p (TREE_TYPE (t1), TREE_TYPE (t2), 218 true)) 219 return return_false (); 220 221 bool existed_p; 222 223 tree &slot = m_decl_map.get_or_insert (t1, &existed_p); 224 if (existed_p) 225 return return_with_debug (slot == t2); 226 else 227 slot = t2; 228 229 return true; 230} 231 232/* Return true if T1 and T2 are same for purposes of ipa-polymorphic-call 233 analysis. COMPARE_PTR indicates if types of pointers needs to be 234 considered. */ 235 236bool 237func_checker::compatible_polymorphic_types_p (tree t1, tree t2, 238 bool compare_ptr) 239{ 240 gcc_assert (TREE_CODE (t1) != FUNCTION_TYPE && TREE_CODE (t1) != METHOD_TYPE); 241 242 /* Pointer types generally give no information. */ 243 if (POINTER_TYPE_P (t1)) 244 { 245 if (!compare_ptr) 246 return true; 247 return func_checker::compatible_polymorphic_types_p (TREE_TYPE (t1), 248 TREE_TYPE (t2), 249 false); 250 } 251 252 /* If types contain a polymorphic types, match them. */ 253 bool c1 = contains_polymorphic_type_p (t1); 254 bool c2 = contains_polymorphic_type_p (t2); 255 if (!c1 && !c2) 256 return true; 257 if (!c1 || !c2) 258 return return_false_with_msg ("one type is not polymorphic"); 259 if (!types_must_be_same_for_odr (t1, t2)) 260 return return_false_with_msg ("types are not same for ODR"); 261 return true; 262} 263 264/* Return true if types are compatible from perspective of ICF. */ 265bool 266func_checker::compatible_types_p (tree t1, tree t2) 267{ 268 if (TREE_CODE (t1) != TREE_CODE (t2)) 269 return return_false_with_msg ("different tree types"); 270 271 if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2)) 272 return return_false_with_msg ("restrict flags are different"); 273 274 if (!types_compatible_p (t1, t2)) 275 return return_false_with_msg ("types are not compatible"); 276 277 if (get_alias_set (t1) != get_alias_set (t2)) 278 return return_false_with_msg ("alias sets are different"); 279 280 return true; 281} 282 283/* Function compare for equality given memory operands T1 and T2. */ 284 285bool 286func_checker::compare_memory_operand (tree t1, tree t2) 287{ 288 if (!t1 && !t2) 289 return true; 290 else if (!t1 || !t2) 291 return false; 292 293 ao_ref r1, r2; 294 ao_ref_init (&r1, t1); 295 ao_ref_init (&r2, t2); 296 297 tree b1 = ao_ref_base (&r1); 298 tree b2 = ao_ref_base (&r2); 299 300 bool source_is_memop = DECL_P (b1) || INDIRECT_REF_P (b1) 301 || TREE_CODE (b1) == MEM_REF 302 || TREE_CODE (b1) == TARGET_MEM_REF; 303 304 bool target_is_memop = DECL_P (b2) || INDIRECT_REF_P (b2) 305 || TREE_CODE (b2) == MEM_REF 306 || TREE_CODE (b2) == TARGET_MEM_REF; 307 308 /* Compare alias sets for memory operands. */ 309 if (source_is_memop && target_is_memop) 310 { 311 if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2)) 312 return return_false_with_msg ("different operand volatility"); 313 314 if (ao_ref_alias_set (&r1) != ao_ref_alias_set (&r2) 315 || ao_ref_base_alias_set (&r1) != ao_ref_base_alias_set (&r2)) 316 return return_false_with_msg ("ao alias sets are different"); 317 318 /* We can't simply use get_object_alignment_1 on the full 319 reference as for accesses with variable indexes this reports 320 too conservative alignment. We also can't use the ao_ref_base 321 base objects as ao_ref_base happily strips MEM_REFs around 322 decls even though that may carry alignment info. */ 323 b1 = t1; 324 while (handled_component_p (b1)) 325 b1 = TREE_OPERAND (b1, 0); 326 b2 = t2; 327 while (handled_component_p (b2)) 328 b2 = TREE_OPERAND (b2, 0); 329 unsigned int align1, align2; 330 unsigned HOST_WIDE_INT tem; 331 get_object_alignment_1 (b1, &align1, &tem); 332 get_object_alignment_1 (b2, &align2, &tem); 333 if (align1 != align2) 334 return return_false_with_msg ("different access alignment"); 335 336 /* Similarly we have to compare dependence info where equality 337 tells us we are safe (even some unequal values would be safe 338 but then we have to maintain a map of bases and cliques). */ 339 unsigned short clique1 = 0, base1 = 0, clique2 = 0, base2 = 0; 340 if (TREE_CODE (b1) == MEM_REF) 341 { 342 clique1 = MR_DEPENDENCE_CLIQUE (b1); 343 base1 = MR_DEPENDENCE_BASE (b1); 344 } 345 if (TREE_CODE (b2) == MEM_REF) 346 { 347 clique2 = MR_DEPENDENCE_CLIQUE (b2); 348 base2 = MR_DEPENDENCE_BASE (b2); 349 } 350 if (clique1 != clique2 || base1 != base2) 351 return return_false_with_msg ("different dependence info"); 352 } 353 354 return compare_operand (t1, t2); 355} 356 357/* Function compare for equality given trees T1 and T2 which 358 can be either a constant or a declaration type. */ 359 360bool 361func_checker::compare_cst_or_decl (tree t1, tree t2) 362{ 363 bool ret; 364 365 switch (TREE_CODE (t1)) 366 { 367 case INTEGER_CST: 368 case COMPLEX_CST: 369 case VECTOR_CST: 370 case STRING_CST: 371 case REAL_CST: 372 { 373 ret = compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)) 374 && operand_equal_p (t1, t2, OEP_ONLY_CONST); 375 return return_with_debug (ret); 376 } 377 case FUNCTION_DECL: 378 /* All function decls are in the symbol table and known to match 379 before we start comparing bodies. */ 380 return true; 381 case VAR_DECL: 382 return return_with_debug (compare_variable_decl (t1, t2)); 383 case FIELD_DECL: 384 { 385 tree offset1 = DECL_FIELD_OFFSET (t1); 386 tree offset2 = DECL_FIELD_OFFSET (t2); 387 388 tree bit_offset1 = DECL_FIELD_BIT_OFFSET (t1); 389 tree bit_offset2 = DECL_FIELD_BIT_OFFSET (t2); 390 391 ret = compare_operand (offset1, offset2) 392 && compare_operand (bit_offset1, bit_offset2); 393 394 return return_with_debug (ret); 395 } 396 case LABEL_DECL: 397 { 398 int *bb1 = m_label_bb_map.get (t1); 399 int *bb2 = m_label_bb_map.get (t2); 400 401 return return_with_debug (*bb1 == *bb2); 402 } 403 case PARM_DECL: 404 case RESULT_DECL: 405 case CONST_DECL: 406 { 407 ret = compare_decl (t1, t2); 408 return return_with_debug (ret); 409 } 410 default: 411 gcc_unreachable (); 412 } 413} 414 415/* Function responsible for comparison of various operands T1 and T2. 416 If these components, from functions FUNC1 and FUNC2, are equal, true 417 is returned. */ 418 419bool 420func_checker::compare_operand (tree t1, tree t2) 421{ 422 tree x1, x2, y1, y2, z1, z2; 423 bool ret; 424 425 if (!t1 && !t2) 426 return true; 427 else if (!t1 || !t2) 428 return false; 429 430 tree tt1 = TREE_TYPE (t1); 431 tree tt2 = TREE_TYPE (t2); 432 433 if (!func_checker::compatible_types_p (tt1, tt2)) 434 return false; 435 436 if (TREE_CODE (t1) != TREE_CODE (t2)) 437 return return_false (); 438 439 switch (TREE_CODE (t1)) 440 { 441 case CONSTRUCTOR: 442 { 443 unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (t1)); 444 unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (t2)); 445 446 if (length1 != length2) 447 return return_false (); 448 449 for (unsigned i = 0; i < length1; i++) 450 if (!compare_operand (CONSTRUCTOR_ELT (t1, i)->value, 451 CONSTRUCTOR_ELT (t2, i)->value)) 452 return return_false(); 453 454 return true; 455 } 456 case ARRAY_REF: 457 case ARRAY_RANGE_REF: 458 /* First argument is the array, second is the index. */ 459 x1 = TREE_OPERAND (t1, 0); 460 x2 = TREE_OPERAND (t2, 0); 461 y1 = TREE_OPERAND (t1, 1); 462 y2 = TREE_OPERAND (t2, 1); 463 464 if (!compare_operand (array_ref_low_bound (t1), 465 array_ref_low_bound (t2))) 466 return return_false_with_msg (""); 467 if (!compare_operand (array_ref_element_size (t1), 468 array_ref_element_size (t2))) 469 return return_false_with_msg (""); 470 471 if (!compare_operand (x1, x2)) 472 return return_false_with_msg (""); 473 return compare_operand (y1, y2); 474 case MEM_REF: 475 { 476 x1 = TREE_OPERAND (t1, 0); 477 x2 = TREE_OPERAND (t2, 0); 478 y1 = TREE_OPERAND (t1, 1); 479 y2 = TREE_OPERAND (t2, 1); 480 481 /* See if operand is an memory access (the test originate from 482 gimple_load_p). 483 484 In this case the alias set of the function being replaced must 485 be subset of the alias set of the other function. At the moment 486 we seek for equivalency classes, so simply require inclussion in 487 both directions. */ 488 489 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2))) 490 return return_false (); 491 492 if (!compare_operand (x1, x2)) 493 return return_false_with_msg (""); 494 495 /* Type of the offset on MEM_REF does not matter. */ 496 return wi::to_offset (y1) == wi::to_offset (y2); 497 } 498 case COMPONENT_REF: 499 { 500 x1 = TREE_OPERAND (t1, 0); 501 x2 = TREE_OPERAND (t2, 0); 502 y1 = TREE_OPERAND (t1, 1); 503 y2 = TREE_OPERAND (t2, 1); 504 505 ret = compare_operand (x1, x2) 506 && compare_cst_or_decl (y1, y2); 507 508 return return_with_debug (ret); 509 } 510 /* Virtual table call. */ 511 case OBJ_TYPE_REF: 512 { 513 if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2))) 514 return return_false (); 515 if (opt_for_fn (m_source_func_decl, flag_devirtualize) 516 && virtual_method_call_p (t1)) 517 { 518 if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t1)) 519 != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t2))) 520 return return_false_with_msg ("OBJ_TYPE_REF token mismatch"); 521 if (!types_same_for_odr (obj_type_ref_class (t1), 522 obj_type_ref_class (t2))) 523 return return_false_with_msg ("OBJ_TYPE_REF OTR type mismatch"); 524 if (!compare_operand (OBJ_TYPE_REF_OBJECT (t1), 525 OBJ_TYPE_REF_OBJECT (t2))) 526 return return_false_with_msg ("OBJ_TYPE_REF object mismatch"); 527 } 528 529 return return_with_debug (true); 530 } 531 case IMAGPART_EXPR: 532 case REALPART_EXPR: 533 case ADDR_EXPR: 534 { 535 x1 = TREE_OPERAND (t1, 0); 536 x2 = TREE_OPERAND (t2, 0); 537 538 ret = compare_operand (x1, x2); 539 return return_with_debug (ret); 540 } 541 case BIT_FIELD_REF: 542 { 543 x1 = TREE_OPERAND (t1, 0); 544 x2 = TREE_OPERAND (t2, 0); 545 y1 = TREE_OPERAND (t1, 1); 546 y2 = TREE_OPERAND (t2, 1); 547 z1 = TREE_OPERAND (t1, 2); 548 z2 = TREE_OPERAND (t2, 2); 549 550 ret = compare_operand (x1, x2) 551 && compare_cst_or_decl (y1, y2) 552 && compare_cst_or_decl (z1, z2); 553 554 return return_with_debug (ret); 555 } 556 case SSA_NAME: 557 return compare_ssa_name (t1, t2); 558 case INTEGER_CST: 559 case COMPLEX_CST: 560 case VECTOR_CST: 561 case STRING_CST: 562 case REAL_CST: 563 case FUNCTION_DECL: 564 case VAR_DECL: 565 case FIELD_DECL: 566 case LABEL_DECL: 567 case PARM_DECL: 568 case RESULT_DECL: 569 case CONST_DECL: 570 return compare_cst_or_decl (t1, t2); 571 default: 572 return return_false_with_msg ("Unknown TREE code reached"); 573 } 574} 575 576/* Compares two tree list operands T1 and T2 and returns true if these 577 two trees are semantically equivalent. */ 578 579bool 580func_checker::compare_tree_list_operand (tree t1, tree t2) 581{ 582 gcc_assert (TREE_CODE (t1) == TREE_LIST); 583 gcc_assert (TREE_CODE (t2) == TREE_LIST); 584 585 for (; t1; t1 = TREE_CHAIN (t1)) 586 { 587 if (!t2) 588 return false; 589 590 if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2))) 591 return return_false (); 592 593 t2 = TREE_CHAIN (t2); 594 } 595 596 if (t2) 597 return return_false (); 598 599 return true; 600} 601 602/* Verifies that trees T1 and T2 do correspond. */ 603 604bool 605func_checker::compare_variable_decl (tree t1, tree t2) 606{ 607 bool ret = false; 608 609 if (t1 == t2) 610 return true; 611 612 if (DECL_ALIGN (t1) != DECL_ALIGN (t2)) 613 return return_false_with_msg ("alignments are different"); 614 615 if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2)) 616 return return_false_with_msg ("DECL_HARD_REGISTER are different"); 617 618 if (DECL_HARD_REGISTER (t1) 619 && DECL_ASSEMBLER_NAME (t1) != DECL_ASSEMBLER_NAME (t2)) 620 return return_false_with_msg ("HARD REGISTERS are different"); 621 622 /* Symbol table variables are known to match before we start comparing 623 bodies. */ 624 if (decl_in_symtab_p (t1)) 625 return decl_in_symtab_p (t2); 626 ret = compare_decl (t1, t2); 627 628 return return_with_debug (ret); 629} 630 631 632/* Function visits all gimple labels and creates corresponding 633 mapping between basic blocks and labels. */ 634 635void 636func_checker::parse_labels (sem_bb *bb) 637{ 638 for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi); 639 gsi_next (&gsi)) 640 { 641 gimple stmt = gsi_stmt (gsi); 642 643 if (glabel *label_stmt = dyn_cast <glabel *> (stmt)) 644 { 645 tree t = gimple_label_label (label_stmt); 646 gcc_assert (TREE_CODE (t) == LABEL_DECL); 647 648 m_label_bb_map.put (t, bb->bb->index); 649 } 650 } 651} 652 653/* Basic block equivalence comparison function that returns true if 654 basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond. 655 656 In general, a collection of equivalence dictionaries is built for types 657 like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure 658 is utilized by every statement-by-statement comparison function. */ 659 660bool 661func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2) 662{ 663 gimple_stmt_iterator gsi1, gsi2; 664 gimple s1, s2; 665 666 gsi1 = gsi_start_bb_nondebug (bb1->bb); 667 gsi2 = gsi_start_bb_nondebug (bb2->bb); 668 669 while (!gsi_end_p (gsi1)) 670 { 671 if (gsi_end_p (gsi2)) 672 return return_false (); 673 674 s1 = gsi_stmt (gsi1); 675 s2 = gsi_stmt (gsi2); 676 677 int eh1 = lookup_stmt_eh_lp_fn 678 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1); 679 int eh2 = lookup_stmt_eh_lp_fn 680 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2); 681 682 if (eh1 != eh2) 683 return return_false_with_msg ("EH regions are different"); 684 685 if (gimple_code (s1) != gimple_code (s2)) 686 return return_false_with_msg ("gimple codes are different"); 687 688 switch (gimple_code (s1)) 689 { 690 case GIMPLE_CALL: 691 if (!compare_gimple_call (as_a <gcall *> (s1), 692 as_a <gcall *> (s2))) 693 return return_different_stmts (s1, s2, "GIMPLE_CALL"); 694 break; 695 case GIMPLE_ASSIGN: 696 if (!compare_gimple_assign (s1, s2)) 697 return return_different_stmts (s1, s2, "GIMPLE_ASSIGN"); 698 break; 699 case GIMPLE_COND: 700 if (!compare_gimple_cond (s1, s2)) 701 return return_different_stmts (s1, s2, "GIMPLE_COND"); 702 break; 703 case GIMPLE_SWITCH: 704 if (!compare_gimple_switch (as_a <gswitch *> (s1), 705 as_a <gswitch *> (s2))) 706 return return_different_stmts (s1, s2, "GIMPLE_SWITCH"); 707 break; 708 case GIMPLE_DEBUG: 709 break; 710 case GIMPLE_EH_DISPATCH: 711 if (gimple_eh_dispatch_region (as_a <geh_dispatch *> (s1)) 712 != gimple_eh_dispatch_region (as_a <geh_dispatch *> (s2))) 713 return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH"); 714 break; 715 case GIMPLE_RESX: 716 if (!compare_gimple_resx (as_a <gresx *> (s1), 717 as_a <gresx *> (s2))) 718 return return_different_stmts (s1, s2, "GIMPLE_RESX"); 719 break; 720 case GIMPLE_LABEL: 721 if (!compare_gimple_label (as_a <glabel *> (s1), 722 as_a <glabel *> (s2))) 723 return return_different_stmts (s1, s2, "GIMPLE_LABEL"); 724 break; 725 case GIMPLE_RETURN: 726 if (!compare_gimple_return (as_a <greturn *> (s1), 727 as_a <greturn *> (s2))) 728 return return_different_stmts (s1, s2, "GIMPLE_RETURN"); 729 break; 730 case GIMPLE_GOTO: 731 if (!compare_gimple_goto (s1, s2)) 732 return return_different_stmts (s1, s2, "GIMPLE_GOTO"); 733 break; 734 case GIMPLE_ASM: 735 if (!compare_gimple_asm (as_a <gasm *> (s1), 736 as_a <gasm *> (s2))) 737 return return_different_stmts (s1, s2, "GIMPLE_ASM"); 738 break; 739 case GIMPLE_PREDICT: 740 case GIMPLE_NOP: 741 break; 742 default: 743 return return_false_with_msg ("Unknown GIMPLE code reached"); 744 } 745 746 gsi_next_nondebug (&gsi1); 747 gsi_next_nondebug (&gsi2); 748 } 749 750 if (!gsi_end_p (gsi2)) 751 return return_false (); 752 753 return true; 754} 755 756/* Verifies for given GIMPLEs S1 and S2 that 757 call statements are semantically equivalent. */ 758 759bool 760func_checker::compare_gimple_call (gcall *s1, gcall *s2) 761{ 762 unsigned i; 763 tree t1, t2; 764 765 if (gimple_call_num_args (s1) != gimple_call_num_args (s2)) 766 return false; 767 768 t1 = gimple_call_fn (s1); 769 t2 = gimple_call_fn (s2); 770 if (!compare_operand (t1, t2)) 771 return return_false (); 772 773 /* Compare flags. */ 774 if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2) 775 || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2) 776 || gimple_call_tail_p (s1) != gimple_call_tail_p (s2) 777 || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2) 778 || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2) 779 || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2) 780 || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2) 781 || gimple_call_with_bounds_p (s1) != gimple_call_with_bounds_p (s2)) 782 return false; 783 784 if (gimple_call_internal_p (s1) 785 && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2)) 786 return false; 787 788 tree fntype1 = gimple_call_fntype (s1); 789 tree fntype2 = gimple_call_fntype (s2); 790 if ((fntype1 && !fntype2) 791 || (!fntype1 && fntype2) 792 || (fntype1 && !types_compatible_p (fntype1, fntype2))) 793 return return_false_with_msg ("call function types are not compatible"); 794 795 tree chain1 = gimple_call_chain (s1); 796 tree chain2 = gimple_call_chain (s2); 797 if ((chain1 && !chain2) 798 || (!chain1 && chain2) 799 || !compare_operand (chain1, chain2)) 800 return return_false_with_msg ("static call chains are different"); 801 802 /* Checking of argument. */ 803 for (i = 0; i < gimple_call_num_args (s1); ++i) 804 { 805 t1 = gimple_call_arg (s1, i); 806 t2 = gimple_call_arg (s2, i); 807 808 if (!compare_memory_operand (t1, t2)) 809 return return_false_with_msg ("memory operands are different"); 810 } 811 812 /* Return value checking. */ 813 t1 = gimple_get_lhs (s1); 814 t2 = gimple_get_lhs (s2); 815 816 return compare_memory_operand (t1, t2); 817} 818 819 820/* Verifies for given GIMPLEs S1 and S2 that 821 assignment statements are semantically equivalent. */ 822 823bool 824func_checker::compare_gimple_assign (gimple s1, gimple s2) 825{ 826 tree arg1, arg2; 827 tree_code code1, code2; 828 unsigned i; 829 830 code1 = gimple_expr_code (s1); 831 code2 = gimple_expr_code (s2); 832 833 if (code1 != code2) 834 return false; 835 836 code1 = gimple_assign_rhs_code (s1); 837 code2 = gimple_assign_rhs_code (s2); 838 839 if (code1 != code2) 840 return false; 841 842 for (i = 0; i < gimple_num_ops (s1); i++) 843 { 844 arg1 = gimple_op (s1, i); 845 arg2 = gimple_op (s2, i); 846 847 if (!compare_memory_operand (arg1, arg2)) 848 return return_false_with_msg ("memory operands are different"); 849 } 850 851 852 return true; 853} 854 855/* Verifies for given GIMPLEs S1 and S2 that 856 condition statements are semantically equivalent. */ 857 858bool 859func_checker::compare_gimple_cond (gimple s1, gimple s2) 860{ 861 tree t1, t2; 862 tree_code code1, code2; 863 864 code1 = gimple_expr_code (s1); 865 code2 = gimple_expr_code (s2); 866 867 if (code1 != code2) 868 return false; 869 870 t1 = gimple_cond_lhs (s1); 871 t2 = gimple_cond_lhs (s2); 872 873 if (!compare_operand (t1, t2)) 874 return false; 875 876 t1 = gimple_cond_rhs (s1); 877 t2 = gimple_cond_rhs (s2); 878 879 return compare_operand (t1, t2); 880} 881 882/* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2. */ 883 884bool 885func_checker::compare_tree_ssa_label (tree t1, tree t2) 886{ 887 return compare_operand (t1, t2); 888} 889 890/* Verifies for given GIMPLE_LABEL stmts S1 and S2 that 891 label statements are semantically equivalent. */ 892 893bool 894func_checker::compare_gimple_label (const glabel *g1, const glabel *g2) 895{ 896 if (m_ignore_labels) 897 return true; 898 899 tree t1 = gimple_label_label (g1); 900 tree t2 = gimple_label_label (g2); 901 902 if (FORCED_LABEL (t1) || FORCED_LABEL (t2)) 903 return return_false_with_msg ("FORCED_LABEL"); 904 905 /* As the pass build BB to label mapping, no further check is needed. */ 906 return true; 907} 908 909/* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that 910 switch statements are semantically equivalent. */ 911 912bool 913func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2) 914{ 915 unsigned lsize1, lsize2, i; 916 917 lsize1 = gimple_switch_num_labels (g1); 918 lsize2 = gimple_switch_num_labels (g2); 919 920 if (lsize1 != lsize2) 921 return false; 922 923 tree t1 = gimple_switch_index (g1); 924 tree t2 = gimple_switch_index (g2); 925 926 if (!compare_operand (t1, t2)) 927 return false; 928 929 for (i = 0; i < lsize1; i++) 930 { 931 tree label1 = gimple_switch_label (g1, i); 932 tree label2 = gimple_switch_label (g2, i); 933 934 /* Label LOW and HIGH comparison. */ 935 tree low1 = CASE_LOW (label1); 936 tree low2 = CASE_LOW (label2); 937 938 if (!tree_int_cst_equal (low1, low2)) 939 return return_false_with_msg ("case low values are different"); 940 941 tree high1 = CASE_HIGH (label1); 942 tree high2 = CASE_HIGH (label2); 943 944 if (!tree_int_cst_equal (high1, high2)) 945 return return_false_with_msg ("case high values are different"); 946 947 if (TREE_CODE (label1) == CASE_LABEL_EXPR 948 && TREE_CODE (label2) == CASE_LABEL_EXPR) 949 { 950 label1 = CASE_LABEL (label1); 951 label2 = CASE_LABEL (label2); 952 953 if (!compare_operand (label1, label2)) 954 return return_false_with_msg ("switch label_exprs are different"); 955 } 956 else if (!tree_int_cst_equal (label1, label2)) 957 return return_false_with_msg ("switch labels are different"); 958 } 959 960 return true; 961} 962 963/* Verifies for given GIMPLE_RETURN stmts S1 and S2 that 964 return statements are semantically equivalent. */ 965 966bool 967func_checker::compare_gimple_return (const greturn *g1, const greturn *g2) 968{ 969 tree t1, t2; 970 971 t1 = gimple_return_retval (g1); 972 t2 = gimple_return_retval (g2); 973 974 /* Void return type. */ 975 if (t1 == NULL && t2 == NULL) 976 return true; 977 else 978 return compare_operand (t1, t2); 979} 980 981/* Verifies for given GIMPLEs S1 and S2 that 982 goto statements are semantically equivalent. */ 983 984bool 985func_checker::compare_gimple_goto (gimple g1, gimple g2) 986{ 987 tree dest1, dest2; 988 989 dest1 = gimple_goto_dest (g1); 990 dest2 = gimple_goto_dest (g2); 991 992 if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME) 993 return false; 994 995 return compare_operand (dest1, dest2); 996} 997 998/* Verifies for given GIMPLE_RESX stmts S1 and S2 that 999 resx statements are semantically equivalent. */ 1000 1001bool 1002func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2) 1003{ 1004 return gimple_resx_region (g1) == gimple_resx_region (g2); 1005} 1006 1007/* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent. 1008 For the beginning, the pass only supports equality for 1009 '__asm__ __volatile__ ("", "", "", "memory")'. */ 1010 1011bool 1012func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2) 1013{ 1014 if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2)) 1015 return false; 1016 1017 if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2)) 1018 return false; 1019 1020 if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2)) 1021 return false; 1022 1023 /* We do not suppport goto ASM statement comparison. */ 1024 if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2)) 1025 return false; 1026 1027 if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2)) 1028 return false; 1029 1030 if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0) 1031 return return_false_with_msg ("ASM strings are different"); 1032 1033 for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++) 1034 { 1035 tree input1 = gimple_asm_input_op (g1, i); 1036 tree input2 = gimple_asm_input_op (g2, i); 1037 1038 if (!compare_tree_list_operand (input1, input2)) 1039 return return_false_with_msg ("ASM input is different"); 1040 } 1041 1042 for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++) 1043 { 1044 tree output1 = gimple_asm_output_op (g1, i); 1045 tree output2 = gimple_asm_output_op (g2, i); 1046 1047 if (!compare_tree_list_operand (output1, output2)) 1048 return return_false_with_msg ("ASM output is different"); 1049 } 1050 1051 for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++) 1052 { 1053 tree clobber1 = gimple_asm_clobber_op (g1, i); 1054 tree clobber2 = gimple_asm_clobber_op (g2, i); 1055 1056 if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2), 1057 OEP_ONLY_CONST)) 1058 return return_false_with_msg ("ASM clobber is different"); 1059 } 1060 1061 return true; 1062} 1063 1064} // ipa_icf_gimple namespace 1065