gcc/ipa-icf-gimple.c

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