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