gcc/ipa-icf-gimple.c

   1 /* Interprocedural Identical Code Folding pass
   2    Copyright (C) 2014-2018 Free Software Foundation, Inc.
   3
   4    Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "backend.h"
  26 #include "rtl.h"
  27 #include "tree.h"
  28 #include "gimple.h"
  29 #include "tree-pass.h"
  30 #include "ssa.h"
  31 #include "cgraph.h"
  32 #include "data-streamer.h"
  33 #include "gimple-pretty-print.h"
  34 #include "alias.h"
  35 #include "fold-const.h"
  36 #include "gimple-iterator.h"
  37 #include "ipa-utils.h"
  38 #include "tree-eh.h"
  39 #include "builtins.h"
  40
  41 #include "ipa-icf-gimple.h"
  42
  43 namespace ipa_icf_gimple {
  44
  45 /* Initialize internal structures for a given SOURCE_FUNC_DECL and
  46    TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
  47    an option COMPARE_POLYMORPHIC is true. For special cases, one can
  48    set IGNORE_LABELS to skip label comparison.
  49    Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
  50    of declarations that can be skipped.  */
  51
  52 func_checker::func_checker (tree source_func_decl, tree target_func_decl,
  53                             bool compare_polymorphic,
  54                             bool ignore_labels,
  55                             hash_set<symtab_node *> *ignored_source_nodes,
  56                             hash_set<symtab_node *> *ignored_target_nodes)
  57   : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl),
  58     m_ignored_source_nodes (ignored_source_nodes),
  59     m_ignored_target_nodes (ignored_target_nodes),
  60     m_compare_polymorphic (compare_polymorphic),
  61     m_ignore_labels (ignore_labels)
  62 {
  63   function *source_func = DECL_STRUCT_FUNCTION (source_func_decl);
  64   function *target_func = DECL_STRUCT_FUNCTION (target_func_decl);
  65
  66   unsigned ssa_source = SSANAMES (source_func)->length ();
  67   unsigned ssa_target = SSANAMES (target_func)->length ();
  68
  69   m_source_ssa_names.create (ssa_source);
  70   m_target_ssa_names.create (ssa_target);
  71
  72   for (unsigned i = 0; i < ssa_source; i++)
  73     m_source_ssa_names.safe_push (-1);
  74
  75   for (unsigned i = 0; i < ssa_target; i++)
  76     m_target_ssa_names.safe_push (-1);
  77 }
  78
  79 /* Memory release routine.  */
  80
  81 func_checker::~func_checker ()
  82 {
  83   m_source_ssa_names.release();
  84   m_target_ssa_names.release();
  85 }
  86
  87 /* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
  88
  89 bool
  90 func_checker::compare_ssa_name (tree t1, tree t2)
  91 {
  92   gcc_assert (TREE_CODE (t1) == SSA_NAME);
  93   gcc_assert (TREE_CODE (t2) == SSA_NAME);
  94
  95   unsigned i1 = SSA_NAME_VERSION (t1);
  96   unsigned i2 = SSA_NAME_VERSION (t2);
  97
  98   if (m_source_ssa_names[i1] == -1)
  99     m_source_ssa_names[i1] = i2;
 100   else if (m_source_ssa_names[i1] != (int) i2)
 101     return false;
 102
 103   if(m_target_ssa_names[i2] == -1)
 104     m_target_ssa_names[i2] = i1;
 105   else if (m_target_ssa_names[i2] != (int) i1)
 106     return false;
 107
 108   if (SSA_NAME_IS_DEFAULT_DEF (t1))
 109     {
 110       tree b1 = SSA_NAME_VAR (t1);
 111       tree b2 = SSA_NAME_VAR (t2);
 112
 113       if (b1 == NULL && b2 == NULL)
 114         return true;
 115
 116       if (b1 == NULL || b2 == NULL || TREE_CODE (b1) != TREE_CODE (b2))
 117         return return_false ();
 118
 119       return compare_cst_or_decl (b1, b2);
 120     }
 121
 122   return true;
 123 }
 124
 125 /* Verification function for edges E1 and E2.  */
 126
 127 bool
 128 func_checker::compare_edge (edge e1, edge e2)
 129 {
 130   if (e1->flags != e2->flags)
 131     return false;
 132
 133   bool existed_p;
 134
 135   edge &slot = m_edge_map.get_or_insert (e1, &existed_p);
 136   if (existed_p)
 137     return return_with_debug (slot == e2);
 138   else
 139     slot = e2;
 140
 141   /* TODO: filter edge probabilities for profile feedback match.  */
 142
 143   return true;
 144 }
 145
 146 /* Verification function for declaration trees T1 and T2 that
 147    come from functions FUNC1 and FUNC2.  */
 148
 149 bool
 150 func_checker::compare_decl (tree t1, tree t2)
 151 {
 152   if (!auto_var_in_fn_p (t1, m_source_func_decl)
 153       || !auto_var_in_fn_p (t2, m_target_func_decl))
 154     return return_with_debug (t1 == t2);
 155
 156   tree_code t = TREE_CODE (t1);
 157   if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
 158       && DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2))
 159     return return_false_with_msg ("DECL_BY_REFERENCE flags are different");
 160
 161   if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
 162     return return_false ();
 163
 164   /* TODO: we are actually too strict here.  We only need to compare if
 165      T1 can be used in polymorphic call.  */
 166   if (TREE_ADDRESSABLE (t1)
 167       && m_compare_polymorphic
 168       && !compatible_polymorphic_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
 169                                           false))
 170     return return_false ();
 171
 172   if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
 173       && DECL_BY_REFERENCE (t1)
 174       && m_compare_polymorphic
 175       && !compatible_polymorphic_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
 176                                           true))
 177     return return_false ();
 178
 179   bool existed_p;
 180
 181   tree &slot = m_decl_map.get_or_insert (t1, &existed_p);
 182   if (existed_p)
 183     return return_with_debug (slot == t2);
 184   else
 185     slot = t2;
 186
 187   return true;
 188 }
 189
 190 /* Return true if T1 and T2 are same for purposes of ipa-polymorphic-call
 191    analysis.  COMPARE_PTR indicates if types of pointers needs to be
 192    considered.  */
 193
 194 bool
 195 func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
 196                                               bool compare_ptr)
 197 {
 198   gcc_assert (TREE_CODE (t1) != FUNCTION_TYPE && TREE_CODE (t1) != METHOD_TYPE);
 199
 200   /* Pointer types generally give no information.  */
 201   if (POINTER_TYPE_P (t1))
 202     {
 203       if (!compare_ptr)
 204         return true;
 205       return func_checker::compatible_polymorphic_types_p (TREE_TYPE (t1),
 206                                                            TREE_TYPE (t2),
 207                                                            false);
 208     }
 209
 210   /* If types contain a polymorphic types, match them.  */
 211   bool c1 = contains_polymorphic_type_p (t1);
 212   bool c2 = contains_polymorphic_type_p (t2);
 213   if (!c1 && !c2)
 214     return true;
 215   if (!c1 || !c2)
 216     return return_false_with_msg ("one type is not polymorphic");
 217   if (!types_must_be_same_for_odr (t1, t2))
 218     return return_false_with_msg ("types are not same for ODR");
 219   return true;
 220 }
 221
 222 /* Return true if types are compatible from perspective of ICF.  */
 223 bool
 224 func_checker::compatible_types_p (tree t1, tree t2)
 225 {
 226   if (TREE_CODE (t1) != TREE_CODE (t2))
 227     return return_false_with_msg ("different tree types");
 228
 229   if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
 230     return return_false_with_msg ("restrict flags are different");
 231
 232   if (!types_compatible_p (t1, t2))
 233     return return_false_with_msg ("types are not compatible");
 234
 235   /* We do a lot of unnecesary matching of types that are not being
 236      accessed and thus do not need to be compatible.  In longer term we should
 237      remove these checks on all types which are not accessed as memory
 238      locations.
 239
 240      For time being just avoid calling get_alias_set on types that are not
 241      having alias sets defined at all.  */
 242   if (type_with_alias_set_p (t1) && type_with_alias_set_p (t2)
 243       && get_alias_set (t1) != get_alias_set (t2))
 244     return return_false_with_msg ("alias sets are different");
 245
 246   return true;
 247 }
 248
 249 /* Function compare for equality given memory operands T1 and T2.  */
 250
 251 bool
 252 func_checker::compare_memory_operand (tree t1, tree t2)
 253 {
 254   if (!t1 && !t2)
 255     return true;
 256   else if (!t1 || !t2)
 257     return false;
 258
 259   ao_ref r1, r2;
 260   ao_ref_init (&r1, t1);
 261   ao_ref_init (&r2, t2);
 262
 263   tree b1 = ao_ref_base (&r1);
 264   tree b2 = ao_ref_base (&r2);
 265
 266   bool source_is_memop = DECL_P (b1) || INDIRECT_REF_P (b1)
 267                          || TREE_CODE (b1) == MEM_REF
 268                          || TREE_CODE (b1) == TARGET_MEM_REF;
 269
 270   bool target_is_memop = DECL_P (b2) || INDIRECT_REF_P (b2)
 271                          || TREE_CODE (b2) == MEM_REF
 272                          || TREE_CODE (b2) == TARGET_MEM_REF;
 273
 274   /* Compare alias sets for memory operands.  */
 275   if (source_is_memop && target_is_memop)
 276     {
 277       if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2))
 278         return return_false_with_msg ("different operand volatility");
 279
 280       if (ao_ref_alias_set (&r1) != ao_ref_alias_set (&r2)
 281           || ao_ref_base_alias_set (&r1) != ao_ref_base_alias_set (&r2))
 282         return return_false_with_msg ("ao alias sets are different");
 283
 284       /* We can't simply use get_object_alignment_1 on the full
 285          reference as for accesses with variable indexes this reports
 286          too conservative alignment.  We also can't use the ao_ref_base
 287          base objects as ao_ref_base happily strips MEM_REFs around
 288          decls even though that may carry alignment info.  */
 289       b1 = t1;
 290       while (handled_component_p (b1))
 291         b1 = TREE_OPERAND (b1, 0);
 292       b2 = t2;
 293       while (handled_component_p (b2))
 294         b2 = TREE_OPERAND (b2, 0);
 295       unsigned int align1, align2;
 296       unsigned HOST_WIDE_INT tem;
 297       get_object_alignment_1 (b1, &align1, &tem);
 298       get_object_alignment_1 (b2, &align2, &tem);
 299       if (align1 != align2)
 300         return return_false_with_msg ("different access alignment");
 301
 302       /* Similarly we have to compare dependence info where equality
 303          tells us we are safe (even some unequal values would be safe
 304          but then we have to maintain a map of bases and cliques).  */
 305       unsigned short clique1 = 0, base1 = 0, clique2 = 0, base2 = 0;
 306       if (TREE_CODE (b1) == MEM_REF)
 307         {
 308           clique1 = MR_DEPENDENCE_CLIQUE (b1);
 309           base1 = MR_DEPENDENCE_BASE (b1);
 310         }
 311       if (TREE_CODE (b2) == MEM_REF)
 312         {
 313           clique2 = MR_DEPENDENCE_CLIQUE (b2);
 314           base2 = MR_DEPENDENCE_BASE (b2);
 315         }
 316       if (clique1 != clique2 || base1 != base2)
 317         return return_false_with_msg ("different dependence info");
 318     }
 319
 320   return compare_operand (t1, t2);
 321 }
 322
 323 /* Function compare for equality given trees T1 and T2 which
 324    can be either a constant or a declaration type.  */
 325
 326 bool
 327 func_checker::compare_cst_or_decl (tree t1, tree t2)
 328 {
 329   bool ret;
 330
 331   switch (TREE_CODE (t1))
 332     {
 333     case INTEGER_CST:
 334     case COMPLEX_CST:
 335     case VECTOR_CST:
 336     case STRING_CST:
 337     case REAL_CST:
 338       {
 339         ret = compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2))
 340               && operand_equal_p (t1, t2, OEP_ONLY_CONST);
 341         return return_with_debug (ret);
 342       }
 343     case FUNCTION_DECL:
 344       /* All function decls are in the symbol table and known to match
 345          before we start comparing bodies.  */
 346       return true;
 347     case VAR_DECL:
 348       return return_with_debug (compare_variable_decl (t1, t2));
 349     case FIELD_DECL:
 350       {
 351         tree offset1 = DECL_FIELD_OFFSET (t1);
 352         tree offset2 = DECL_FIELD_OFFSET (t2);
 353
 354         tree bit_offset1 = DECL_FIELD_BIT_OFFSET (t1);
 355         tree bit_offset2 = DECL_FIELD_BIT_OFFSET (t2);
 356
 357         ret = compare_operand (offset1, offset2)
 358               && compare_operand (bit_offset1, bit_offset2);
 359
 360         return return_with_debug (ret);
 361       }
 362     case LABEL_DECL:
 363       {
 364         if (t1 == t2)
 365           return true;
 366
 367         int *bb1 = m_label_bb_map.get (t1);
 368         int *bb2 = m_label_bb_map.get (t2);
 369
 370         /* Labels can point to another function (non-local GOTOs).  */
 371         return return_with_debug (bb1 != NULL && bb2 != NULL && *bb1 == *bb2);
 372       }
 373     case PARM_DECL:
 374     case RESULT_DECL:
 375     case CONST_DECL:
 376       {
 377         ret = compare_decl (t1, t2);
 378         return return_with_debug (ret);
 379       }
 380     default:
 381       gcc_unreachable ();
 382     }
 383 }
 384
 385 /* Function responsible for comparison of various operands T1 and T2.
 386    If these components, from functions FUNC1 and FUNC2, are equal, true
 387    is returned.  */
 388
 389 bool
 390 func_checker::compare_operand (tree t1, tree t2)
 391 {
 392   tree x1, x2, y1, y2, z1, z2;
 393   bool ret;
 394
 395   if (!t1 && !t2)
 396     return true;
 397   else if (!t1 || !t2)
 398     return false;
 399
 400   tree tt1 = TREE_TYPE (t1);
 401   tree tt2 = TREE_TYPE (t2);
 402
 403   if (!func_checker::compatible_types_p (tt1, tt2))
 404     return false;
 405
 406   if (TREE_CODE (t1) != TREE_CODE (t2))
 407     return return_false ();
 408
 409   switch (TREE_CODE (t1))
 410     {
 411     case CONSTRUCTOR:
 412       {
 413         unsigned length1 = CONSTRUCTOR_NELTS (t1);
 414         unsigned length2 = CONSTRUCTOR_NELTS (t2);
 415
 416         if (length1 != length2)
 417           return return_false ();
 418
 419         for (unsigned i = 0; i < length1; i++)
 420           if (!compare_operand (CONSTRUCTOR_ELT (t1, i)->value,
 421                                 CONSTRUCTOR_ELT (t2, i)->value))
 422             return return_false();
 423
 424         return true;
 425       }
 426     case ARRAY_REF:
 427     case ARRAY_RANGE_REF:
 428       /* First argument is the array, second is the index.  */
 429       x1 = TREE_OPERAND (t1, 0);
 430       x2 = TREE_OPERAND (t2, 0);
 431       y1 = TREE_OPERAND (t1, 1);
 432       y2 = TREE_OPERAND (t2, 1);
 433
 434       if (!compare_operand (array_ref_low_bound (t1),
 435                             array_ref_low_bound (t2)))
 436         return return_false_with_msg ("");
 437       if (!compare_operand (array_ref_element_size (t1),
 438                             array_ref_element_size (t2)))
 439         return return_false_with_msg ("");
 440
 441       if (!compare_operand (x1, x2))
 442         return return_false_with_msg ("");
 443       return compare_operand (y1, y2);
 444     case MEM_REF:
 445       {
 446         x1 = TREE_OPERAND (t1, 0);
 447         x2 = TREE_OPERAND (t2, 0);
 448         y1 = TREE_OPERAND (t1, 1);
 449         y2 = TREE_OPERAND (t2, 1);
 450
 451         /* See if operand is an memory access (the test originate from
 452          gimple_load_p).
 453
 454         In this case the alias set of the function being replaced must
 455         be subset of the alias set of the other function.  At the moment
 456         we seek for equivalency classes, so simply require inclussion in
 457         both directions.  */
 458
 459         if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
 460           return return_false ();
 461
 462         if (!compare_operand (x1, x2))
 463           return return_false_with_msg ("");
 464
 465         /* Type of the offset on MEM_REF does not matter.  */
 466         return known_eq (wi::to_poly_offset (y1), wi::to_poly_offset (y2));
 467       }
 468     case COMPONENT_REF:
 469       {
 470         x1 = TREE_OPERAND (t1, 0);
 471         x2 = TREE_OPERAND (t2, 0);
 472         y1 = TREE_OPERAND (t1, 1);
 473         y2 = TREE_OPERAND (t2, 1);
 474
 475         ret = compare_operand (x1, x2)
 476               && compare_cst_or_decl (y1, y2);
 477
 478         return return_with_debug (ret);
 479       }
 480     /* Virtual table call.  */
 481     case OBJ_TYPE_REF:
 482       {
 483         if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2)))
 484           return return_false ();
 485         if (opt_for_fn (m_source_func_decl, flag_devirtualize)
 486             && virtual_method_call_p (t1))
 487           {
 488             if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t1))
 489                 != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t2)))
 490               return return_false_with_msg ("OBJ_TYPE_REF token mismatch");
 491             if (!types_same_for_odr (obj_type_ref_class (t1),
 492                                      obj_type_ref_class (t2)))
 493               return return_false_with_msg ("OBJ_TYPE_REF OTR type mismatch");
 494             if (!compare_operand (OBJ_TYPE_REF_OBJECT (t1),
 495                                   OBJ_TYPE_REF_OBJECT (t2)))
 496               return return_false_with_msg ("OBJ_TYPE_REF object mismatch");
 497           }
 498
 499         return return_with_debug (true);
 500       }
 501     case IMAGPART_EXPR:
 502     case REALPART_EXPR:
 503     case ADDR_EXPR:
 504       {
 505         x1 = TREE_OPERAND (t1, 0);
 506         x2 = TREE_OPERAND (t2, 0);
 507
 508         ret = compare_operand (x1, x2);
 509         return return_with_debug (ret);
 510       }
 511     case BIT_FIELD_REF:
 512       {
 513         x1 = TREE_OPERAND (t1, 0);
 514         x2 = TREE_OPERAND (t2, 0);
 515         y1 = TREE_OPERAND (t1, 1);
 516         y2 = TREE_OPERAND (t2, 1);
 517         z1 = TREE_OPERAND (t1, 2);
 518         z2 = TREE_OPERAND (t2, 2);
 519
 520         ret = compare_operand (x1, x2)
 521               && compare_cst_or_decl (y1, y2)
 522               && compare_cst_or_decl (z1, z2);
 523
 524         return return_with_debug (ret);
 525       }
 526     case SSA_NAME:
 527         return compare_ssa_name (t1, t2);
 528     case INTEGER_CST:
 529     case COMPLEX_CST:
 530     case VECTOR_CST:
 531     case STRING_CST:
 532     case REAL_CST:
 533     case FUNCTION_DECL:
 534     case VAR_DECL:
 535     case FIELD_DECL:
 536     case LABEL_DECL:
 537     case PARM_DECL:
 538     case RESULT_DECL:
 539     case CONST_DECL:
 540       return compare_cst_or_decl (t1, t2);
 541     default:
 542       return return_false_with_msg ("Unknown TREE code reached");
 543     }
 544 }
 545
 546 bool
 547 func_checker::compare_asm_inputs_outputs (tree t1, tree t2)
 548 {
 549   gcc_assert (TREE_CODE (t1) == TREE_LIST);
 550   gcc_assert (TREE_CODE (t2) == TREE_LIST);
 551
 552   for (; t1; t1 = TREE_CHAIN (t1))
 553     {
 554       if (!t2)
 555         return false;
 556
 557       if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2)))
 558         return return_false ();
 559
 560       tree p1 = TREE_PURPOSE (t1);
 561       tree p2 = TREE_PURPOSE (t2);
 562
 563       gcc_assert (TREE_CODE (p1) == TREE_LIST);
 564       gcc_assert (TREE_CODE (p2) == TREE_LIST);
 565
 566       if (strcmp (TREE_STRING_POINTER (TREE_VALUE (p1)),
 567                   TREE_STRING_POINTER (TREE_VALUE (p2))) != 0)
 568         return return_false ();
 569
 570       t2 = TREE_CHAIN (t2);
 571     }
 572
 573   if (t2)
 574     return return_false ();
 575
 576   return true;
 577 }
 578
 579 /* Verifies that trees T1 and T2 do correspond.  */
 580
 581 bool
 582 func_checker::compare_variable_decl (tree t1, tree t2)
 583 {
 584   bool ret = false;
 585
 586   if (t1 == t2)
 587     return true;
 588
 589   if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
 590     return return_false_with_msg ("alignments are different");
 591
 592   if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
 593     return return_false_with_msg ("DECL_HARD_REGISTER are different");
 594
 595   if (DECL_HARD_REGISTER (t1)
 596       && DECL_ASSEMBLER_NAME (t1) != DECL_ASSEMBLER_NAME (t2))
 597     return return_false_with_msg ("HARD REGISTERS are different");
 598
 599   /* Symbol table variables are known to match before we start comparing
 600      bodies.  */
 601   if (decl_in_symtab_p (t1))
 602     return decl_in_symtab_p (t2);
 603   ret = compare_decl (t1, t2);
 604
 605   return return_with_debug (ret);
 606 }
 607
 608
 609 /* Function visits all gimple labels and creates corresponding
 610    mapping between basic blocks and labels.  */
 611
 612 void
 613 func_checker::parse_labels (sem_bb *bb)
 614 {
 615   for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
 616        gsi_next (&gsi))
 617     {
 618       gimple *stmt = gsi_stmt (gsi);
 619
 620       if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
 621         {
 622           tree t = gimple_label_label (label_stmt);
 623           gcc_assert (TREE_CODE (t) == LABEL_DECL);
 624
 625           m_label_bb_map.put (t, bb->bb->index);
 626         }
 627     }
 628 }
 629
 630 /* Basic block equivalence comparison function that returns true if
 631    basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
 632
 633    In general, a collection of equivalence dictionaries is built for types
 634    like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
 635    is utilized by every statement-by-statement comparison function.  */
 636
 637 bool
 638 func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
 639 {
 640   gimple_stmt_iterator gsi1, gsi2;
 641   gimple *s1, *s2;
 642
 643   gsi1 = gsi_start_nondebug_bb (bb1->bb);
 644   gsi2 = gsi_start_nondebug_bb (bb2->bb);
 645
 646   while (!gsi_end_p (gsi1))
 647     {
 648       if (gsi_end_p (gsi2))
 649         return return_false ();
 650
 651       s1 = gsi_stmt (gsi1);
 652       s2 = gsi_stmt (gsi2);
 653
 654       int eh1 = lookup_stmt_eh_lp_fn
 655                 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
 656       int eh2 = lookup_stmt_eh_lp_fn
 657                 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
 658
 659       if (eh1 != eh2)
 660         return return_false_with_msg ("EH regions are different");
 661
 662       if (gimple_code (s1) != gimple_code (s2))
 663         return return_false_with_msg ("gimple codes are different");
 664
 665       switch (gimple_code (s1))
 666         {
 667         case GIMPLE_CALL:
 668           if (!compare_gimple_call (as_a <gcall *> (s1),
 669                                     as_a <gcall *> (s2)))
 670             return return_different_stmts (s1, s2, "GIMPLE_CALL");
 671           break;
 672         case GIMPLE_ASSIGN:
 673           if (!compare_gimple_assign (s1, s2))
 674             return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
 675           break;
 676         case GIMPLE_COND:
 677           if (!compare_gimple_cond (s1, s2))
 678             return return_different_stmts (s1, s2, "GIMPLE_COND");
 679           break;
 680         case GIMPLE_SWITCH:
 681           if (!compare_gimple_switch (as_a <gswitch *> (s1),
 682                                       as_a <gswitch *> (s2)))
 683             return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
 684           break;
 685         case GIMPLE_DEBUG:
 686           break;
 687         case GIMPLE_EH_DISPATCH:
 688           if (gimple_eh_dispatch_region (as_a <geh_dispatch *> (s1))
 689               != gimple_eh_dispatch_region (as_a <geh_dispatch *> (s2)))
 690             return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH");
 691           break;
 692         case GIMPLE_RESX:
 693           if (!compare_gimple_resx (as_a <gresx *> (s1),
 694                                     as_a <gresx *> (s2)))
 695             return return_different_stmts (s1, s2, "GIMPLE_RESX");
 696           break;
 697         case GIMPLE_LABEL:
 698           if (!compare_gimple_label (as_a <glabel *> (s1),
 699                                      as_a <glabel *> (s2)))
 700             return return_different_stmts (s1, s2, "GIMPLE_LABEL");
 701           break;
 702         case GIMPLE_RETURN:
 703           if (!compare_gimple_return (as_a <greturn *> (s1),
 704                                       as_a <greturn *> (s2)))
 705             return return_different_stmts (s1, s2, "GIMPLE_RETURN");
 706           break;
 707         case GIMPLE_GOTO:
 708           if (!compare_gimple_goto (s1, s2))
 709             return return_different_stmts (s1, s2, "GIMPLE_GOTO");
 710           break;
 711         case GIMPLE_ASM:
 712           if (!compare_gimple_asm (as_a <gasm *> (s1),
 713                                    as_a <gasm *> (s2)))
 714             return return_different_stmts (s1, s2, "GIMPLE_ASM");
 715           break;
 716         case GIMPLE_PREDICT:
 717         case GIMPLE_NOP:
 718           break;
 719         default:
 720           return return_false_with_msg ("Unknown GIMPLE code reached");
 721         }
 722
 723       gsi_next_nondebug (&gsi1);
 724       gsi_next_nondebug (&gsi2);
 725     }
 726
 727   if (!gsi_end_p (gsi2))
 728     return return_false ();
 729
 730   return true;
 731 }
 732
 733 /* Verifies for given GIMPLEs S1 and S2 that
 734    call statements are semantically equivalent.  */
 735
 736 bool
 737 func_checker::compare_gimple_call (gcall *s1, gcall *s2)
 738 {
 739   unsigned i;
 740   tree t1, t2;
 741
 742   if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
 743     return false;
 744
 745   t1 = gimple_call_fn (s1);
 746   t2 = gimple_call_fn (s2);
 747   if (!compare_operand (t1, t2))
 748     return return_false ();
 749
 750   /* Compare flags.  */
 751   if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
 752       || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
 753       || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
 754       || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
 755       || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
 756       || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
 757       || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_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_input_p (g1) != gimple_asm_input_p (g2))
 994     return false;
 995
 996   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
 997     return false;
 998
 999   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
1000     return false;
1001
1002   /* We do not suppport goto ASM statement comparison.  */
1003   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
1004     return false;
1005
1006   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
1007     return false;
1008
1009   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
1010     return return_false_with_msg ("ASM strings are different");
1011
1012   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
1013     {
1014       tree input1 = gimple_asm_input_op (g1, i);
1015       tree input2 = gimple_asm_input_op (g2, i);
1016
1017       if (!compare_asm_inputs_outputs (input1, input2))
1018         return return_false_with_msg ("ASM input is different");
1019     }
1020
1021   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
1022     {
1023       tree output1 = gimple_asm_output_op (g1, i);
1024       tree output2 = gimple_asm_output_op (g2, i);
1025
1026       if (!compare_asm_inputs_outputs (output1, output2))
1027         return return_false_with_msg ("ASM output is different");
1028     }
1029
1030   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
1031     {
1032       tree clobber1 = gimple_asm_clobber_op (g1, i);
1033       tree clobber2 = gimple_asm_clobber_op (g2, i);
1034
1035       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
1036                             OEP_ONLY_CONST))
1037         return return_false_with_msg ("ASM clobber is different");
1038     }
1039
1040   return true;
1041 }
1042
1043 } // ipa_icf_gimple namespace