gcc/ipa-icf-gimple.c

   1 /* Interprocedural Identical Code Folding pass
   2    Copyright (C) 2014-2016 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         int *bb1 = m_label_bb_map.get (t1);
 365         int *bb2 = m_label_bb_map.get (t2);
 366
 367         return return_with_debug (*bb1 == *bb2);
 368       }
 369     case PARM_DECL:
 370     case RESULT_DECL:
 371     case CONST_DECL:
 372       {
 373         ret = compare_decl (t1, t2);
 374         return return_with_debug (ret);
 375       }
 376     default:
 377       gcc_unreachable ();
 378     }
 379 }
 380
 381 /* Function responsible for comparison of various operands T1 and T2.
 382    If these components, from functions FUNC1 and FUNC2, are equal, true
 383    is returned.  */
 384
 385 bool
 386 func_checker::compare_operand (tree t1, tree t2)
 387 {
 388   tree x1, x2, y1, y2, z1, z2;
 389   bool ret;
 390
 391   if (!t1 && !t2)
 392     return true;
 393   else if (!t1 || !t2)
 394     return false;
 395
 396   tree tt1 = TREE_TYPE (t1);
 397   tree tt2 = TREE_TYPE (t2);
 398
 399   if (!func_checker::compatible_types_p (tt1, tt2))
 400     return false;
 401
 402   if (TREE_CODE (t1) != TREE_CODE (t2))
 403     return return_false ();
 404
 405   switch (TREE_CODE (t1))
 406     {
 407     case CONSTRUCTOR:
 408       {
 409         unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (t1));
 410         unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (t2));
 411
 412         if (length1 != length2)
 413           return return_false ();
 414
 415         for (unsigned i = 0; i < length1; i++)
 416           if (!compare_operand (CONSTRUCTOR_ELT (t1, i)->value,
 417                                 CONSTRUCTOR_ELT (t2, i)->value))
 418             return return_false();
 419
 420         return true;
 421       }
 422     case ARRAY_REF:
 423     case ARRAY_RANGE_REF:
 424       /* First argument is the array, second is the index.  */
 425       x1 = TREE_OPERAND (t1, 0);
 426       x2 = TREE_OPERAND (t2, 0);
 427       y1 = TREE_OPERAND (t1, 1);
 428       y2 = TREE_OPERAND (t2, 1);
 429
 430       if (!compare_operand (array_ref_low_bound (t1),
 431                             array_ref_low_bound (t2)))
 432         return return_false_with_msg ("");
 433       if (!compare_operand (array_ref_element_size (t1),
 434                             array_ref_element_size (t2)))
 435         return return_false_with_msg ("");
 436
 437       if (!compare_operand (x1, x2))
 438         return return_false_with_msg ("");
 439       return compare_operand (y1, y2);
 440     case MEM_REF:
 441       {
 442         x1 = TREE_OPERAND (t1, 0);
 443         x2 = TREE_OPERAND (t2, 0);
 444         y1 = TREE_OPERAND (t1, 1);
 445         y2 = TREE_OPERAND (t2, 1);
 446
 447         /* See if operand is an memory access (the test originate from
 448          gimple_load_p).
 449
 450         In this case the alias set of the function being replaced must
 451         be subset of the alias set of the other function.  At the moment
 452         we seek for equivalency classes, so simply require inclussion in
 453         both directions.  */
 454
 455         if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
 456           return return_false ();
 457
 458         if (!compare_operand (x1, x2))
 459           return return_false_with_msg ("");
 460
 461         /* Type of the offset on MEM_REF does not matter.  */
 462         return wi::to_offset  (y1) == wi::to_offset  (y2);
 463       }
 464     case COMPONENT_REF:
 465       {
 466         x1 = TREE_OPERAND (t1, 0);
 467         x2 = TREE_OPERAND (t2, 0);
 468         y1 = TREE_OPERAND (t1, 1);
 469         y2 = TREE_OPERAND (t2, 1);
 470
 471         ret = compare_operand (x1, x2)
 472               && compare_cst_or_decl (y1, y2);
 473
 474         return return_with_debug (ret);
 475       }
 476     /* Virtual table call.  */
 477     case OBJ_TYPE_REF:
 478       {
 479         if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2)))
 480           return return_false ();
 481         if (opt_for_fn (m_source_func_decl, flag_devirtualize)
 482             && virtual_method_call_p (t1))
 483           {
 484             if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t1))
 485                 != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t2)))
 486               return return_false_with_msg ("OBJ_TYPE_REF token mismatch");
 487             if (!types_same_for_odr (obj_type_ref_class (t1),
 488                                      obj_type_ref_class (t2)))
 489               return return_false_with_msg ("OBJ_TYPE_REF OTR type mismatch");
 490             if (!compare_operand (OBJ_TYPE_REF_OBJECT (t1),
 491                                   OBJ_TYPE_REF_OBJECT (t2)))
 492               return return_false_with_msg ("OBJ_TYPE_REF object mismatch");
 493           }
 494
 495         return return_with_debug (true);
 496       }
 497     case IMAGPART_EXPR:
 498     case REALPART_EXPR:
 499     case ADDR_EXPR:
 500       {
 501         x1 = TREE_OPERAND (t1, 0);
 502         x2 = TREE_OPERAND (t2, 0);
 503
 504         ret = compare_operand (x1, x2);
 505         return return_with_debug (ret);
 506       }
 507     case BIT_FIELD_REF:
 508       {
 509         x1 = TREE_OPERAND (t1, 0);
 510         x2 = TREE_OPERAND (t2, 0);
 511         y1 = TREE_OPERAND (t1, 1);
 512         y2 = TREE_OPERAND (t2, 1);
 513         z1 = TREE_OPERAND (t1, 2);
 514         z2 = TREE_OPERAND (t2, 2);
 515
 516         ret = compare_operand (x1, x2)
 517               && compare_cst_or_decl (y1, y2)
 518               && compare_cst_or_decl (z1, z2);
 519
 520         return return_with_debug (ret);
 521       }
 522     case SSA_NAME:
 523         return compare_ssa_name (t1, t2);
 524     case INTEGER_CST:
 525     case COMPLEX_CST:
 526     case VECTOR_CST:
 527     case STRING_CST:
 528     case REAL_CST:
 529     case FUNCTION_DECL:
 530     case VAR_DECL:
 531     case FIELD_DECL:
 532     case LABEL_DECL:
 533     case PARM_DECL:
 534     case RESULT_DECL:
 535     case CONST_DECL:
 536       return compare_cst_or_decl (t1, t2);
 537     default:
 538       return return_false_with_msg ("Unknown TREE code reached");
 539     }
 540 }
 541
 542 /* Compares two tree list operands T1 and T2 and returns true if these
 543    two trees are semantically equivalent.  */
 544
 545 bool
 546 func_checker::compare_tree_list_operand (tree t1, tree t2)
 547 {
 548   gcc_assert (TREE_CODE (t1) == TREE_LIST);
 549   gcc_assert (TREE_CODE (t2) == TREE_LIST);
 550
 551   for (; t1; t1 = TREE_CHAIN (t1))
 552     {
 553       if (!t2)
 554         return false;
 555
 556       if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2)))
 557         return return_false ();
 558
 559       t2 = TREE_CHAIN (t2);
 560     }
 561
 562   if (t2)
 563     return return_false ();
 564
 565   return true;
 566 }
 567
 568 /* Verifies that trees T1 and T2 do correspond.  */
 569
 570 bool
 571 func_checker::compare_variable_decl (tree t1, tree t2)
 572 {
 573   bool ret = false;
 574
 575   if (t1 == t2)
 576     return true;
 577
 578   if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
 579     return return_false_with_msg ("alignments are different");
 580
 581   if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
 582     return return_false_with_msg ("DECL_HARD_REGISTER are different");
 583
 584   if (DECL_HARD_REGISTER (t1)
 585       && DECL_ASSEMBLER_NAME (t1) != DECL_ASSEMBLER_NAME (t2))
 586     return return_false_with_msg ("HARD REGISTERS are different");
 587
 588   /* Symbol table variables are known to match before we start comparing
 589      bodies.  */
 590   if (decl_in_symtab_p (t1))
 591     return decl_in_symtab_p (t2);
 592   ret = compare_decl (t1, t2);
 593
 594   return return_with_debug (ret);
 595 }
 596
 597
 598 /* Function visits all gimple labels and creates corresponding
 599    mapping between basic blocks and labels.  */
 600
 601 void
 602 func_checker::parse_labels (sem_bb *bb)
 603 {
 604   for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
 605        gsi_next (&gsi))
 606     {
 607       gimple *stmt = gsi_stmt (gsi);
 608
 609       if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
 610         {
 611           tree t = gimple_label_label (label_stmt);
 612           gcc_assert (TREE_CODE (t) == LABEL_DECL);
 613
 614           m_label_bb_map.put (t, bb->bb->index);
 615         }
 616     }
 617 }
 618
 619 /* Basic block equivalence comparison function that returns true if
 620    basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
 621
 622    In general, a collection of equivalence dictionaries is built for types
 623    like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
 624    is utilized by every statement-by-statement comparison function.  */
 625
 626 bool
 627 func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
 628 {
 629   gimple_stmt_iterator gsi1, gsi2;
 630   gimple *s1, *s2;
 631
 632   gsi1 = gsi_start_bb_nondebug (bb1->bb);
 633   gsi2 = gsi_start_bb_nondebug (bb2->bb);
 634
 635   while (!gsi_end_p (gsi1))
 636     {
 637       if (gsi_end_p (gsi2))
 638         return return_false ();
 639
 640       s1 = gsi_stmt (gsi1);
 641       s2 = gsi_stmt (gsi2);
 642
 643       int eh1 = lookup_stmt_eh_lp_fn
 644                 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
 645       int eh2 = lookup_stmt_eh_lp_fn
 646                 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
 647
 648       if (eh1 != eh2)
 649         return return_false_with_msg ("EH regions are different");
 650
 651       if (gimple_code (s1) != gimple_code (s2))
 652         return return_false_with_msg ("gimple codes are different");
 653
 654       switch (gimple_code (s1))
 655         {
 656         case GIMPLE_CALL:
 657           if (!compare_gimple_call (as_a <gcall *> (s1),
 658                                     as_a <gcall *> (s2)))
 659             return return_different_stmts (s1, s2, "GIMPLE_CALL");
 660           break;
 661         case GIMPLE_ASSIGN:
 662           if (!compare_gimple_assign (s1, s2))
 663             return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
 664           break;
 665         case GIMPLE_COND:
 666           if (!compare_gimple_cond (s1, s2))
 667             return return_different_stmts (s1, s2, "GIMPLE_COND");
 668           break;
 669         case GIMPLE_SWITCH:
 670           if (!compare_gimple_switch (as_a <gswitch *> (s1),
 671                                       as_a <gswitch *> (s2)))
 672             return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
 673           break;
 674         case GIMPLE_DEBUG:
 675           break;
 676         case GIMPLE_EH_DISPATCH:
 677           if (gimple_eh_dispatch_region (as_a <geh_dispatch *> (s1))
 678               != gimple_eh_dispatch_region (as_a <geh_dispatch *> (s2)))
 679             return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH");
 680           break;
 681         case GIMPLE_RESX:
 682           if (!compare_gimple_resx (as_a <gresx *> (s1),
 683                                     as_a <gresx *> (s2)))
 684             return return_different_stmts (s1, s2, "GIMPLE_RESX");
 685           break;
 686         case GIMPLE_LABEL:
 687           if (!compare_gimple_label (as_a <glabel *> (s1),
 688                                      as_a <glabel *> (s2)))
 689             return return_different_stmts (s1, s2, "GIMPLE_LABEL");
 690           break;
 691         case GIMPLE_RETURN:
 692           if (!compare_gimple_return (as_a <greturn *> (s1),
 693                                       as_a <greturn *> (s2)))
 694             return return_different_stmts (s1, s2, "GIMPLE_RETURN");
 695           break;
 696         case GIMPLE_GOTO:
 697           if (!compare_gimple_goto (s1, s2))
 698             return return_different_stmts (s1, s2, "GIMPLE_GOTO");
 699           break;
 700         case GIMPLE_ASM:
 701           if (!compare_gimple_asm (as_a <gasm *> (s1),
 702                                    as_a <gasm *> (s2)))
 703             return return_different_stmts (s1, s2, "GIMPLE_ASM");
 704           break;
 705         case GIMPLE_PREDICT:
 706         case GIMPLE_NOP:
 707           break;
 708         default:
 709           return return_false_with_msg ("Unknown GIMPLE code reached");
 710         }
 711
 712       gsi_next_nondebug (&gsi1);
 713       gsi_next_nondebug (&gsi2);
 714     }
 715
 716   if (!gsi_end_p (gsi2))
 717     return return_false ();
 718
 719   return true;
 720 }
 721
 722 /* Verifies for given GIMPLEs S1 and S2 that
 723    call statements are semantically equivalent.  */
 724
 725 bool
 726 func_checker::compare_gimple_call (gcall *s1, gcall *s2)
 727 {
 728   unsigned i;
 729   tree t1, t2;
 730
 731   if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
 732     return false;
 733
 734   t1 = gimple_call_fn (s1);
 735   t2 = gimple_call_fn (s2);
 736   if (!compare_operand (t1, t2))
 737     return return_false ();
 738
 739   /* Compare flags.  */
 740   if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
 741       || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
 742       || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
 743       || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
 744       || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
 745       || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
 746       || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2)
 747       || gimple_call_with_bounds_p (s1) != gimple_call_with_bounds_p (s2))
 748     return false;
 749
 750   if (gimple_call_internal_p (s1)
 751       && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
 752     return false;
 753
 754   tree fntype1 = gimple_call_fntype (s1);
 755   tree fntype2 = gimple_call_fntype (s2);
 756   if ((fntype1 && !fntype2)
 757       || (!fntype1 && fntype2)
 758       || (fntype1 && !types_compatible_p (fntype1, fntype2)))
 759     return return_false_with_msg ("call function types are not compatible");
 760
 761   tree chain1 = gimple_call_chain (s1);
 762   tree chain2 = gimple_call_chain (s2);
 763   if ((chain1 && !chain2)
 764       || (!chain1 && chain2)
 765       || !compare_operand (chain1, chain2))
 766     return return_false_with_msg ("static call chains are different");
 767
 768   /* Checking of argument.  */
 769   for (i = 0; i < gimple_call_num_args (s1); ++i)
 770     {
 771       t1 = gimple_call_arg (s1, i);
 772       t2 = gimple_call_arg (s2, i);
 773
 774       if (!compare_memory_operand (t1, t2))
 775         return return_false_with_msg ("memory operands are different");
 776     }
 777
 778   /* Return value checking.  */
 779   t1 = gimple_get_lhs (s1);
 780   t2 = gimple_get_lhs (s2);
 781
 782   return compare_memory_operand (t1, t2);
 783 }
 784
 785
 786 /* Verifies for given GIMPLEs S1 and S2 that
 787    assignment statements are semantically equivalent.  */
 788
 789 bool
 790 func_checker::compare_gimple_assign (gimple *s1, gimple *s2)
 791 {
 792   tree arg1, arg2;
 793   tree_code code1, code2;
 794   unsigned i;
 795
 796   code1 = gimple_expr_code (s1);
 797   code2 = gimple_expr_code (s2);
 798
 799   if (code1 != code2)
 800     return false;
 801
 802   code1 = gimple_assign_rhs_code (s1);
 803   code2 = gimple_assign_rhs_code (s2);
 804
 805   if (code1 != code2)
 806     return false;
 807
 808   for (i = 0; i < gimple_num_ops (s1); i++)
 809     {
 810       arg1 = gimple_op (s1, i);
 811       arg2 = gimple_op (s2, i);
 812
 813       if (!compare_memory_operand (arg1, arg2))
 814         return return_false_with_msg ("memory operands are different");
 815     }
 816
 817
 818   return true;
 819 }
 820
 821 /* Verifies for given GIMPLEs S1 and S2 that
 822    condition statements are semantically equivalent.  */
 823
 824 bool
 825 func_checker::compare_gimple_cond (gimple *s1, gimple *s2)
 826 {
 827   tree t1, t2;
 828   tree_code code1, code2;
 829
 830   code1 = gimple_expr_code (s1);
 831   code2 = gimple_expr_code (s2);
 832
 833   if (code1 != code2)
 834     return false;
 835
 836   t1 = gimple_cond_lhs (s1);
 837   t2 = gimple_cond_lhs (s2);
 838
 839   if (!compare_operand (t1, t2))
 840     return false;
 841
 842   t1 = gimple_cond_rhs (s1);
 843   t2 = gimple_cond_rhs (s2);
 844
 845   return compare_operand (t1, t2);
 846 }
 847
 848 /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2.  */
 849
 850 bool
 851 func_checker::compare_tree_ssa_label (tree t1, tree t2)
 852 {
 853   return compare_operand (t1, t2);
 854 }
 855
 856 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 857    label statements are semantically equivalent.  */
 858
 859 bool
 860 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 861 {
 862   if (m_ignore_labels)
 863     return true;
 864
 865   tree t1 = gimple_label_label (g1);
 866   tree t2 = gimple_label_label (g2);
 867
 868   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 869     return return_false_with_msg ("FORCED_LABEL");
 870
 871   /* As the pass build BB to label mapping, no further check is needed.  */
 872   return true;
 873 }
 874
 875 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 876    switch statements are semantically equivalent.  */
 877
 878 bool
 879 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
 880 {
 881   unsigned lsize1, lsize2, i;
 882
 883   lsize1 = gimple_switch_num_labels (g1);
 884   lsize2 = gimple_switch_num_labels (g2);
 885
 886   if (lsize1 != lsize2)
 887     return false;
 888
 889   tree t1 = gimple_switch_index (g1);
 890   tree t2 = gimple_switch_index (g2);
 891
 892   if (!compare_operand (t1, t2))
 893     return false;
 894
 895   for (i = 0; i < lsize1; i++)
 896     {
 897       tree label1 = gimple_switch_label (g1, i);
 898       tree label2 = gimple_switch_label (g2, i);
 899
 900       /* Label LOW and HIGH comparison.  */
 901       tree low1 = CASE_LOW (label1);
 902       tree low2 = CASE_LOW (label2);
 903
 904       if (!tree_int_cst_equal (low1, low2))
 905         return return_false_with_msg ("case low values are different");
 906
 907       tree high1 = CASE_HIGH (label1);
 908       tree high2 = CASE_HIGH (label2);
 909
 910       if (!tree_int_cst_equal (high1, high2))
 911         return return_false_with_msg ("case high values are different");
 912
 913       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 914           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 915         {
 916           label1 = CASE_LABEL (label1);
 917           label2 = CASE_LABEL (label2);
 918
 919           if (!compare_operand (label1, label2))
 920             return return_false_with_msg ("switch label_exprs are different");
 921         }
 922       else if (!tree_int_cst_equal (label1, label2))
 923         return return_false_with_msg ("switch labels are different");
 924     }
 925
 926   return true;
 927 }
 928
 929 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 930    return statements are semantically equivalent.  */
 931
 932 bool
 933 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
 934 {
 935   tree t1, t2;
 936
 937   t1 = gimple_return_retval (g1);
 938   t2 = gimple_return_retval (g2);
 939
 940   /* Void return type.  */
 941   if (t1 == NULL && t2 == NULL)
 942     return true;
 943   else
 944     return compare_operand (t1, t2);
 945 }
 946
 947 /* Verifies for given GIMPLEs S1 and S2 that
 948    goto statements are semantically equivalent.  */
 949
 950 bool
 951 func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
 952 {
 953   tree dest1, dest2;
 954
 955   dest1 = gimple_goto_dest (g1);
 956   dest2 = gimple_goto_dest (g2);
 957
 958   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 959     return false;
 960
 961   return compare_operand (dest1, dest2);
 962 }
 963
 964 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 965    resx statements are semantically equivalent.  */
 966
 967 bool
 968 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
 969 {
 970   return gimple_resx_region (g1) == gimple_resx_region (g2);
 971 }
 972
 973 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 974    For the beginning, the pass only supports equality for
 975    '__asm__ __volatile__ ("", "", "", "memory")'.  */
 976
 977 bool
 978 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
 979 {
 980   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
 981     return false;
 982
 983   if (gimple_asm_input_p (g1) != gimple_asm_input_p (g2))
 984     return false;
 985
 986   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
 987     return false;
 988
 989   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
 990     return false;
 991
 992   /* We do not suppport goto ASM statement comparison.  */
 993   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
 994     return false;
 995
 996   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
 997     return false;
 998
 999   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
1000     return return_false_with_msg ("ASM strings are different");
1001
1002   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
1003     {
1004       tree input1 = gimple_asm_input_op (g1, i);
1005       tree input2 = gimple_asm_input_op (g2, i);
1006
1007       if (!compare_tree_list_operand (input1, input2))
1008         return return_false_with_msg ("ASM input is different");
1009     }
1010
1011   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
1012     {
1013       tree output1 = gimple_asm_output_op (g1, i);
1014       tree output2 = gimple_asm_output_op (g2, i);
1015
1016       if (!compare_tree_list_operand (output1, output2))
1017         return return_false_with_msg ("ASM output is different");
1018     }
1019
1020   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
1021     {
1022       tree clobber1 = gimple_asm_clobber_op (g1, i);
1023       tree clobber2 = gimple_asm_clobber_op (g2, i);
1024
1025       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
1026                             OEP_ONLY_CONST))
1027         return return_false_with_msg ("ASM clobber is different");
1028     }
1029
1030   return true;
1031 }
1032
1033 } // ipa_icf_gimple namespace