gcc/ipa-icf-gimple.c

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