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