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