gcc/ipa-icf-gimple.c

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