contrib/gcc-8.0/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 wi::to_offset  (y1) == wi::to_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       || gimple_call_with_bounds_p (s1) != gimple_call_with_bounds_p (s2))
 759     return false;
 760
 761   if (gimple_call_internal_p (s1)
 762       && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
 763     return false;
 764
 765   tree fntype1 = gimple_call_fntype (s1);
 766   tree fntype2 = gimple_call_fntype (s2);
 767   if ((fntype1 && !fntype2)
 768       || (!fntype1 && fntype2)
 769       || (fntype1 && !types_compatible_p (fntype1, fntype2)))
 770     return return_false_with_msg ("call function types are not compatible");
 771
 772   tree chain1 = gimple_call_chain (s1);
 773   tree chain2 = gimple_call_chain (s2);
 774   if ((chain1 && !chain2)
 775       || (!chain1 && chain2)
 776       || !compare_operand (chain1, chain2))
 777     return return_false_with_msg ("static call chains are different");
 778
 779   /* Checking of argument.  */
 780   for (i = 0; i < gimple_call_num_args (s1); ++i)
 781     {
 782       t1 = gimple_call_arg (s1, i);
 783       t2 = gimple_call_arg (s2, i);
 784
 785       if (!compare_memory_operand (t1, t2))
 786         return return_false_with_msg ("memory operands are different");
 787     }
 788
 789   /* Return value checking.  */
 790   t1 = gimple_get_lhs (s1);
 791   t2 = gimple_get_lhs (s2);
 792
 793   return compare_memory_operand (t1, t2);
 794 }
 795
 796
 797 /* Verifies for given GIMPLEs S1 and S2 that
 798    assignment statements are semantically equivalent.  */
 799
 800 bool
 801 func_checker::compare_gimple_assign (gimple *s1, gimple *s2)
 802 {
 803   tree arg1, arg2;
 804   tree_code code1, code2;
 805   unsigned i;
 806
 807   code1 = gimple_expr_code (s1);
 808   code2 = gimple_expr_code (s2);
 809
 810   if (code1 != code2)
 811     return false;
 812
 813   code1 = gimple_assign_rhs_code (s1);
 814   code2 = gimple_assign_rhs_code (s2);
 815
 816   if (code1 != code2)
 817     return false;
 818
 819   for (i = 0; i < gimple_num_ops (s1); i++)
 820     {
 821       arg1 = gimple_op (s1, i);
 822       arg2 = gimple_op (s2, i);
 823
 824       if (!compare_memory_operand (arg1, arg2))
 825         return return_false_with_msg ("memory operands are different");
 826     }
 827
 828
 829   return true;
 830 }
 831
 832 /* Verifies for given GIMPLEs S1 and S2 that
 833    condition statements are semantically equivalent.  */
 834
 835 bool
 836 func_checker::compare_gimple_cond (gimple *s1, gimple *s2)
 837 {
 838   tree t1, t2;
 839   tree_code code1, code2;
 840
 841   code1 = gimple_expr_code (s1);
 842   code2 = gimple_expr_code (s2);
 843
 844   if (code1 != code2)
 845     return false;
 846
 847   t1 = gimple_cond_lhs (s1);
 848   t2 = gimple_cond_lhs (s2);
 849
 850   if (!compare_operand (t1, t2))
 851     return false;
 852
 853   t1 = gimple_cond_rhs (s1);
 854   t2 = gimple_cond_rhs (s2);
 855
 856   return compare_operand (t1, t2);
 857 }
 858
 859 /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2.  */
 860
 861 bool
 862 func_checker::compare_tree_ssa_label (tree t1, tree t2)
 863 {
 864   return compare_operand (t1, t2);
 865 }
 866
 867 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 868    label statements are semantically equivalent.  */
 869
 870 bool
 871 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 872 {
 873   if (m_ignore_labels)
 874     return true;
 875
 876   tree t1 = gimple_label_label (g1);
 877   tree t2 = gimple_label_label (g2);
 878
 879   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 880     return return_false_with_msg ("FORCED_LABEL");
 881
 882   /* As the pass build BB to label mapping, no further check is needed.  */
 883   return true;
 884 }
 885
 886 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 887    switch statements are semantically equivalent.  */
 888
 889 bool
 890 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
 891 {
 892   unsigned lsize1, lsize2, i;
 893
 894   lsize1 = gimple_switch_num_labels (g1);
 895   lsize2 = gimple_switch_num_labels (g2);
 896
 897   if (lsize1 != lsize2)
 898     return false;
 899
 900   tree t1 = gimple_switch_index (g1);
 901   tree t2 = gimple_switch_index (g2);
 902
 903   if (!compare_operand (t1, t2))
 904     return false;
 905
 906   for (i = 0; i < lsize1; i++)
 907     {
 908       tree label1 = gimple_switch_label (g1, i);
 909       tree label2 = gimple_switch_label (g2, i);
 910
 911       /* Label LOW and HIGH comparison.  */
 912       tree low1 = CASE_LOW (label1);
 913       tree low2 = CASE_LOW (label2);
 914
 915       if (!tree_int_cst_equal (low1, low2))
 916         return return_false_with_msg ("case low values are different");
 917
 918       tree high1 = CASE_HIGH (label1);
 919       tree high2 = CASE_HIGH (label2);
 920
 921       if (!tree_int_cst_equal (high1, high2))
 922         return return_false_with_msg ("case high values are different");
 923
 924       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 925           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 926         {
 927           label1 = CASE_LABEL (label1);
 928           label2 = CASE_LABEL (label2);
 929
 930           if (!compare_operand (label1, label2))
 931             return return_false_with_msg ("switch label_exprs are different");
 932         }
 933       else if (!tree_int_cst_equal (label1, label2))
 934         return return_false_with_msg ("switch labels are different");
 935     }
 936
 937   return true;
 938 }
 939
 940 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 941    return statements are semantically equivalent.  */
 942
 943 bool
 944 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
 945 {
 946   tree t1, t2;
 947
 948   t1 = gimple_return_retval (g1);
 949   t2 = gimple_return_retval (g2);
 950
 951   /* Void return type.  */
 952   if (t1 == NULL && t2 == NULL)
 953     return true;
 954   else
 955     return compare_operand (t1, t2);
 956 }
 957
 958 /* Verifies for given GIMPLEs S1 and S2 that
 959    goto statements are semantically equivalent.  */
 960
 961 bool
 962 func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
 963 {
 964   tree dest1, dest2;
 965
 966   dest1 = gimple_goto_dest (g1);
 967   dest2 = gimple_goto_dest (g2);
 968
 969   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 970     return false;
 971
 972   return compare_operand (dest1, dest2);
 973 }
 974
 975 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 976    resx statements are semantically equivalent.  */
 977
 978 bool
 979 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
 980 {
 981   return gimple_resx_region (g1) == gimple_resx_region (g2);
 982 }
 983
 984 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 985    For the beginning, the pass only supports equality for
 986    '__asm__ __volatile__ ("", "", "", "memory")'.  */
 987
 988 bool
 989 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
 990 {
 991   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
 992     return false;
 993
 994   if (gimple_asm_input_p (g1) != gimple_asm_input_p (g2))
 995     return false;
 996
 997   if (gimple_asm_inline_p (g1) != gimple_asm_inline_p (g2))
 998     return false;
 999
1000   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
1001     return false;
1002
1003   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
1004     return false;
1005
1006   /* We do not suppport goto ASM statement comparison.  */
1007   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
1008     return false;
1009
1010   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
1011     return false;
1012
1013   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
1014     return return_false_with_msg ("ASM strings are different");
1015
1016   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
1017     {
1018       tree input1 = gimple_asm_input_op (g1, i);
1019       tree input2 = gimple_asm_input_op (g2, i);
1020
1021       if (!compare_asm_inputs_outputs (input1, input2))
1022         return return_false_with_msg ("ASM input is different");
1023     }
1024
1025   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
1026     {
1027       tree output1 = gimple_asm_output_op (g1, i);
1028       tree output2 = gimple_asm_output_op (g2, i);
1029
1030       if (!compare_asm_inputs_outputs (output1, output2))
1031         return return_false_with_msg ("ASM output is different");
1032     }
1033
1034   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
1035     {
1036       tree clobber1 = gimple_asm_clobber_op (g1, i);
1037       tree clobber2 = gimple_asm_clobber_op (g2, i);
1038
1039       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
1040                             OEP_ONLY_CONST))
1041         return return_false_with_msg ("ASM clobber is different");
1042     }
1043
1044   return true;
1045 }
1046
1047 } // ipa_icf_gimple namespace