gcc/ipa-icf-gimple.c

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