gcc/ipa-icf-gimple.c

   1 /* Interprocedural Identical Code Folding pass
   2    Copyright (C) 2014-2021 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 "fold-const.h"
  35 #include "gimple-iterator.h"
  36 #include "ipa-utils.h"
  37 #include "tree-eh.h"
  38 #include "builtins.h"
  39 #include "cfgloop.h"
  40 #include "attribs.h"
  41 #include "gimple-walk.h"
  42
  43 #include "tree-ssa-alias-compare.h"
  44 #include "ipa-icf-gimple.h"
  45
  46 namespace ipa_icf_gimple {
  47
  48 /* Initialize internal structures for a given SOURCE_FUNC_DECL and
  49    TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
  50    an option COMPARE_POLYMORPHIC is true. For special cases, one can
  51    set IGNORE_LABELS to skip label comparison.
  52    Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
  53    of declarations that can be skipped.  */
  54
  55 func_checker::func_checker (tree source_func_decl, tree target_func_decl,
  56                             bool ignore_labels, bool tbaa,
  57                             hash_set<symtab_node *> *ignored_source_nodes,
  58                             hash_set<symtab_node *> *ignored_target_nodes)
  59   : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl),
  60     m_ignored_source_nodes (ignored_source_nodes),
  61     m_ignored_target_nodes (ignored_target_nodes),
  62     m_ignore_labels (ignore_labels), m_tbaa (tbaa)
  63 {
  64   function *source_func = DECL_STRUCT_FUNCTION (source_func_decl);
  65   function *target_func = DECL_STRUCT_FUNCTION (target_func_decl);
  66
  67   unsigned ssa_source = SSANAMES (source_func)->length ();
  68   unsigned ssa_target = SSANAMES (target_func)->length ();
  69
  70   m_source_ssa_names.create (ssa_source);
  71   m_target_ssa_names.create (ssa_target);
  72
  73   for (unsigned i = 0; i < ssa_source; i++)
  74     m_source_ssa_names.safe_push (-1);
  75
  76   for (unsigned i = 0; i < ssa_target; i++)
  77     m_target_ssa_names.safe_push (-1);
  78 }
  79
  80 /* Memory release routine.  */
  81
  82 func_checker::~func_checker ()
  83 {
  84   m_source_ssa_names.release();
  85   m_target_ssa_names.release();
  86 }
  87
  88 /* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
  89
  90 bool
  91 func_checker::compare_ssa_name (const_tree t1, const_tree t2)
  92 {
  93   gcc_assert (TREE_CODE (t1) == SSA_NAME);
  94   gcc_assert (TREE_CODE (t2) == SSA_NAME);
  95
  96   unsigned i1 = SSA_NAME_VERSION (t1);
  97   unsigned i2 = SSA_NAME_VERSION (t2);
  98
  99   if (SSA_NAME_IS_DEFAULT_DEF (t1) != SSA_NAME_IS_DEFAULT_DEF (t2))
 100     return false;
 101
 102   if (m_source_ssa_names[i1] == -1)
 103     m_source_ssa_names[i1] = i2;
 104   else if (m_source_ssa_names[i1] != (int) i2)
 105     return false;
 106
 107   if(m_target_ssa_names[i2] == -1)
 108     m_target_ssa_names[i2] = i1;
 109   else if (m_target_ssa_names[i2] != (int) i1)
 110     return false;
 111
 112   if (SSA_NAME_IS_DEFAULT_DEF (t1))
 113     {
 114       tree b1 = SSA_NAME_VAR (t1);
 115       tree b2 = SSA_NAME_VAR (t2);
 116
 117       return compare_operand (b1, b2, OP_NORMAL);
 118     }
 119
 120   return true;
 121 }
 122
 123 /* Verification function for edges E1 and E2.  */
 124
 125 bool
 126 func_checker::compare_edge (edge e1, edge e2)
 127 {
 128   if (e1->flags != e2->flags)
 129     return false;
 130
 131   bool existed_p;
 132
 133   edge &slot = m_edge_map.get_or_insert (e1, &existed_p);
 134   if (existed_p)
 135     return return_with_debug (slot == e2);
 136   else
 137     slot = e2;
 138
 139   /* TODO: filter edge probabilities for profile feedback match.  */
 140
 141   return true;
 142 }
 143
 144 /* Verification function for declaration trees T1 and T2 that
 145    come from functions FUNC1 and FUNC2.  */
 146
 147 bool
 148 func_checker::compare_decl (const_tree t1, const_tree t2)
 149 {
 150   if (!auto_var_in_fn_p (t1, m_source_func_decl)
 151       || !auto_var_in_fn_p (t2, m_target_func_decl))
 152     return return_with_debug (t1 == t2);
 153
 154   tree_code t = TREE_CODE (t1);
 155   if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
 156       && DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2))
 157     return return_false_with_msg ("DECL_BY_REFERENCE flags are different");
 158
 159   /* We do not really need to check types of variables, since they are just
 160      blocks of memory and we verify types of the accesses to them.
 161      However do compare types of other kinds of decls
 162      (parm decls and result decl types may affect ABI convetions).  */
 163   if (t != VAR_DECL)
 164     {
 165       if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
 166         return return_false ();
 167     }
 168   else
 169     {
 170       if (!operand_equal_p (DECL_SIZE (t1), DECL_SIZE (t2),
 171                             OEP_MATCH_SIDE_EFFECTS))
 172         return return_false_with_msg ("DECL_SIZEs are different");
 173     }
 174
 175   bool existed_p;
 176   const_tree &slot = m_decl_map.get_or_insert (t1, &existed_p);
 177   if (existed_p)
 178     return return_with_debug (slot == t2);
 179   else
 180     slot = t2;
 181
 182   return true;
 183 }
 184
 185 /* Return true if T1 and T2 are same for purposes of ipa-polymorphic-call
 186    analysis.  COMPARE_PTR indicates if types of pointers needs to be
 187    considered.  */
 188
 189 bool
 190 func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
 191                                               bool compare_ptr)
 192 {
 193   gcc_assert (TREE_CODE (t1) != FUNCTION_TYPE && TREE_CODE (t1) != METHOD_TYPE);
 194
 195   /* Pointer types generally give no information.  */
 196   if (POINTER_TYPE_P (t1))
 197     {
 198       if (!compare_ptr)
 199         return true;
 200       return func_checker::compatible_polymorphic_types_p (TREE_TYPE (t1),
 201                                                            TREE_TYPE (t2),
 202                                                            false);
 203     }
 204
 205   /* If types contain a polymorphic types, match them.  */
 206   bool c1 = contains_polymorphic_type_p (t1);
 207   bool c2 = contains_polymorphic_type_p (t2);
 208   if (!c1 && !c2)
 209     return true;
 210   if (!c1 || !c2)
 211     return return_false_with_msg ("one type is not polymorphic");
 212   if (!types_must_be_same_for_odr (t1, t2))
 213     return return_false_with_msg ("types are not same for ODR");
 214   return true;
 215 }
 216
 217 /* Return true if types are compatible from perspective of ICF.  */
 218 bool
 219 func_checker::compatible_types_p (tree t1, tree t2)
 220 {
 221   if (TREE_CODE (t1) != TREE_CODE (t2))
 222     return return_false_with_msg ("different tree types");
 223
 224   if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
 225     return return_false_with_msg ("restrict flags are different");
 226
 227   if (!types_compatible_p (t1, t2))
 228     return return_false_with_msg ("types are not compatible");
 229
 230   return true;
 231 }
 232
 233 /* Add hash of ARG to HSTATE. FLAGS have same meaning
 234    as for operand_equal_p.  Works only if operand acces type is OP_NORMAL.  */
 235
 236 void
 237 func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
 238                             unsigned int flags)
 239 {
 240   if (arg == NULL_TREE)
 241     {
 242       hstate.merge_hash (0);
 243       return;
 244     }
 245
 246   switch (TREE_CODE (arg))
 247     {
 248     case PARM_DECL:
 249       {
 250         unsigned int index = 0;
 251         if (DECL_CONTEXT (arg))
 252           for (tree p = DECL_ARGUMENTS (DECL_CONTEXT (arg));
 253                p && index < 32; p = DECL_CHAIN (p), index++)
 254             if (p == arg)
 255               break;
 256         hstate.add_int (PARM_DECL);
 257         hstate.add_int (index);
 258       }
 259       return;
 260     case FUNCTION_DECL:
 261     case VAR_DECL:
 262     case LABEL_DECL:
 263     case RESULT_DECL:
 264     case CONST_DECL:
 265       hstate.add_int (TREE_CODE (arg));
 266       return;
 267     case SSA_NAME:
 268       hstate.add_int (SSA_NAME);
 269       if (SSA_NAME_IS_DEFAULT_DEF (arg))
 270         hash_operand (SSA_NAME_VAR (arg), hstate, flags);
 271       return;
 272     case FIELD_DECL:
 273       inchash::add_expr (DECL_FIELD_OFFSET (arg), hstate, flags);
 274       inchash::add_expr (DECL_FIELD_BIT_OFFSET (arg), hstate, flags);
 275       return;
 276     default:
 277       break;
 278     }
 279
 280   /* In gimple all clobbers can be considered equal: while comparaing two
 281      gimple clobbers we match the left hand memory accesses.  */
 282   if (TREE_CLOBBER_P (arg))
 283     {
 284       hstate.add_int (0xc10bbe5);
 285       return;
 286     }
 287   gcc_assert (!DECL_P (arg));
 288   gcc_assert (!TYPE_P (arg));
 289
 290   return operand_compare::hash_operand (arg, hstate, flags);
 291 }
 292
 293 /* Add hash of ARG accesses according to ACCESS to HSTATE.
 294    FLAGS have same meaning as for operand_equal_p.  */
 295
 296 void
 297 func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
 298                             unsigned int flags, operand_access_type access)
 299 {
 300   if (access == OP_MEMORY)
 301     {
 302       ao_ref ref;
 303       ao_ref_init (&ref, const_cast <tree> (arg));
 304       return hash_ao_ref (&ref, lto_streaming_expected_p (), m_tbaa, hstate);
 305     }
 306   else
 307     return hash_operand (arg, hstate, flags);
 308 }
 309
 310 bool
 311 func_checker::operand_equal_p (const_tree t1, const_tree t2,
 312                                unsigned int flags)
 313 {
 314   bool r;
 315   if (verify_hash_value (t1, t2, flags, &r))
 316     return r;
 317
 318   if (t1 == t2)
 319     return true;
 320   else if (!t1 || !t2)
 321     return false;
 322
 323   if (TREE_CODE (t1) != TREE_CODE (t2))
 324     return return_false ();
 325
 326   switch (TREE_CODE (t1))
 327     {
 328     case FUNCTION_DECL:
 329       /* All function decls are in the symbol table and known to match
 330          before we start comparing bodies.  */
 331       return true;
 332     case VAR_DECL:
 333       return return_with_debug (compare_variable_decl (t1, t2));
 334     case LABEL_DECL:
 335       {
 336         int *bb1 = m_label_bb_map.get (t1);
 337         int *bb2 = m_label_bb_map.get (t2);
 338         /* Labels can point to another function (non-local GOTOs).  */
 339         return return_with_debug (bb1 != NULL && bb2 != NULL && *bb1 == *bb2);
 340       }
 341
 342     case PARM_DECL:
 343     case RESULT_DECL:
 344     case CONST_DECL:
 345       return compare_decl (t1, t2);
 346     case SSA_NAME:
 347       return compare_ssa_name (t1, t2);
 348     default:
 349       break;
 350     }
 351   /* In gimple all clobbers can be considered equal.  We match the left hand
 352      memory accesses.  */
 353   if (TREE_CLOBBER_P (t1) || TREE_CLOBBER_P (t2))
 354     return TREE_CLOBBER_P (t1) == TREE_CLOBBER_P (t2);
 355
 356   return operand_compare::operand_equal_p (t1, t2, flags);
 357 }
 358
 359 /* Function responsible for comparison of various operands T1 and T2
 360    which are accessed as ACCESS.
 361    If these components, from functions FUNC1 and FUNC2, are equal, true
 362    is returned.  */
 363
 364 bool
 365 func_checker::compare_operand (tree t1, tree t2, operand_access_type access)
 366 {
 367   if (!t1 && !t2)
 368     return true;
 369   else if (!t1 || !t2)
 370     return false;
 371   if (access == OP_MEMORY)
 372     {
 373       ao_ref ref1, ref2;
 374       ao_ref_init (&ref1, const_cast <tree> (t1));
 375       ao_ref_init (&ref2, const_cast <tree> (t2));
 376       int flags = compare_ao_refs (&ref1, &ref2,
 377                                    lto_streaming_expected_p (), m_tbaa);
 378
 379       if (!flags)
 380         return true;
 381       if (flags & SEMANTICS)
 382         return return_false_with_msg
 383                 ("compare_ao_refs failed (semantic difference)");
 384       if (flags & BASE_ALIAS_SET)
 385         return return_false_with_msg
 386                 ("compare_ao_refs failed (base alias set difference)");
 387       if (flags & REF_ALIAS_SET)
 388         return return_false_with_msg
 389                  ("compare_ao_refs failed (ref alias set difference)");
 390       if (flags & ACCESS_PATH)
 391         return return_false_with_msg
 392                  ("compare_ao_refs failed (access path difference)");
 393       if (flags & DEPENDENCE_CLIQUE)
 394         return return_false_with_msg
 395                  ("compare_ao_refs failed (dependence clique difference)");
 396       gcc_unreachable ();
 397     }
 398   else
 399     {
 400       if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
 401         return true;
 402       return return_false_with_msg
 403                  ("operand_equal_p failed");
 404     }
 405 }
 406
 407 bool
 408 func_checker::compare_asm_inputs_outputs (tree t1, tree t2,
 409                                           operand_access_type_map *map)
 410 {
 411   gcc_assert (TREE_CODE (t1) == TREE_LIST);
 412   gcc_assert (TREE_CODE (t2) == TREE_LIST);
 413
 414   for (; t1; t1 = TREE_CHAIN (t1))
 415     {
 416       if (!t2)
 417         return false;
 418
 419       if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2),
 420                             get_operand_access_type (map, t1)))
 421         return return_false ();
 422
 423       tree p1 = TREE_PURPOSE (t1);
 424       tree p2 = TREE_PURPOSE (t2);
 425
 426       gcc_assert (TREE_CODE (p1) == TREE_LIST);
 427       gcc_assert (TREE_CODE (p2) == TREE_LIST);
 428
 429       if (strcmp (TREE_STRING_POINTER (TREE_VALUE (p1)),
 430                   TREE_STRING_POINTER (TREE_VALUE (p2))) != 0)
 431         return return_false ();
 432
 433       t2 = TREE_CHAIN (t2);
 434     }
 435
 436   if (t2)
 437     return return_false ();
 438
 439   return true;
 440 }
 441
 442 /* Verifies that trees T1 and T2 do correspond.  */
 443
 444 bool
 445 func_checker::compare_variable_decl (const_tree t1, const_tree t2)
 446 {
 447   bool ret = false;
 448
 449   if (t1 == t2)
 450     return true;
 451
 452   if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
 453     return return_false_with_msg ("alignments are different");
 454
 455   if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
 456     return return_false_with_msg ("DECL_HARD_REGISTER are different");
 457
 458   if (DECL_HARD_REGISTER (t1)
 459       && DECL_ASSEMBLER_NAME_RAW (t1) != DECL_ASSEMBLER_NAME_RAW (t2))
 460     return return_false_with_msg ("HARD REGISTERS are different");
 461
 462   /* Symbol table variables are known to match before we start comparing
 463      bodies.  */
 464   if (decl_in_symtab_p (t1))
 465     return decl_in_symtab_p (t2);
 466   ret = compare_decl (t1, t2);
 467
 468   return return_with_debug (ret);
 469 }
 470
 471 /* Compare loop information for basic blocks BB1 and BB2.  */
 472
 473 bool
 474 func_checker::compare_loops (basic_block bb1, basic_block bb2)
 475 {
 476   if ((bb1->loop_father == NULL) != (bb2->loop_father == NULL))
 477     return return_false ();
 478
 479   class loop *l1 = bb1->loop_father;
 480   class loop *l2 = bb2->loop_father;
 481   if (l1 == NULL)
 482     return true;
 483
 484   if ((bb1 == l1->header) != (bb2 == l2->header))
 485     return return_false_with_msg ("header");
 486   if ((bb1 == l1->latch) != (bb2 == l2->latch))
 487     return return_false_with_msg ("latch");
 488   if (l1->simdlen != l2->simdlen)
 489     return return_false_with_msg ("simdlen");
 490   if (l1->safelen != l2->safelen)
 491     return return_false_with_msg ("safelen");
 492   if (l1->can_be_parallel != l2->can_be_parallel)
 493     return return_false_with_msg ("can_be_parallel");
 494   if (l1->dont_vectorize != l2->dont_vectorize)
 495     return return_false_with_msg ("dont_vectorize");
 496   if (l1->force_vectorize != l2->force_vectorize)
 497     return return_false_with_msg ("force_vectorize");
 498   if (l1->finite_p != l2->finite_p)
 499     return return_false_with_msg ("finite_p");
 500   if (l1->unroll != l2->unroll)
 501     return return_false_with_msg ("unroll");
 502   if (!compare_variable_decl (l1->simduid, l2->simduid))
 503     return return_false_with_msg ("simduid");
 504
 505   return true;
 506 }
 507
 508 /* Function visits all gimple labels and creates corresponding
 509    mapping between basic blocks and labels.  */
 510
 511 void
 512 func_checker::parse_labels (sem_bb *bb)
 513 {
 514   for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
 515        gsi_next (&gsi))
 516     {
 517       gimple *stmt = gsi_stmt (gsi);
 518
 519       if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
 520         {
 521           const_tree t = gimple_label_label (label_stmt);
 522           gcc_assert (TREE_CODE (t) == LABEL_DECL);
 523
 524           m_label_bb_map.put (t, bb->bb->index);
 525         }
 526     }
 527 }
 528
 529 /* Basic block equivalence comparison function that returns true if
 530    basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
 531
 532    In general, a collection of equivalence dictionaries is built for types
 533    like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
 534    is utilized by every statement-by-statement comparison function.  */
 535
 536 bool
 537 func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
 538 {
 539   gimple_stmt_iterator gsi1, gsi2;
 540   gimple *s1, *s2;
 541
 542   gsi1 = gsi_start_nondebug_bb (bb1->bb);
 543   gsi2 = gsi_start_nondebug_bb (bb2->bb);
 544
 545   while (!gsi_end_p (gsi1))
 546     {
 547       if (gsi_end_p (gsi2))
 548         return return_false ();
 549
 550       s1 = gsi_stmt (gsi1);
 551       s2 = gsi_stmt (gsi2);
 552
 553       int eh1 = lookup_stmt_eh_lp_fn
 554                 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
 555       int eh2 = lookup_stmt_eh_lp_fn
 556                 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
 557
 558       if (eh1 != eh2)
 559         return return_false_with_msg ("EH regions are different");
 560
 561       if (gimple_code (s1) != gimple_code (s2))
 562         return return_false_with_msg ("gimple codes are different");
 563
 564       switch (gimple_code (s1))
 565         {
 566         case GIMPLE_CALL:
 567           if (!compare_gimple_call (as_a <gcall *> (s1),
 568                                     as_a <gcall *> (s2)))
 569             return return_different_stmts (s1, s2, "GIMPLE_CALL");
 570           break;
 571         case GIMPLE_ASSIGN:
 572           if (!compare_gimple_assign (s1, s2))
 573             return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
 574           break;
 575         case GIMPLE_COND:
 576           if (!compare_gimple_cond (s1, s2))
 577             return return_different_stmts (s1, s2, "GIMPLE_COND");
 578           break;
 579         case GIMPLE_SWITCH:
 580           if (!compare_gimple_switch (as_a <gswitch *> (s1),
 581                                       as_a <gswitch *> (s2)))
 582             return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
 583           break;
 584         case GIMPLE_DEBUG:
 585           break;
 586         case GIMPLE_EH_DISPATCH:
 587           if (gimple_eh_dispatch_region (as_a <geh_dispatch *> (s1))
 588               != gimple_eh_dispatch_region (as_a <geh_dispatch *> (s2)))
 589             return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH");
 590           break;
 591         case GIMPLE_RESX:
 592           if (!compare_gimple_resx (as_a <gresx *> (s1),
 593                                     as_a <gresx *> (s2)))
 594             return return_different_stmts (s1, s2, "GIMPLE_RESX");
 595           break;
 596         case GIMPLE_LABEL:
 597           if (!compare_gimple_label (as_a <glabel *> (s1),
 598                                      as_a <glabel *> (s2)))
 599             return return_different_stmts (s1, s2, "GIMPLE_LABEL");
 600           break;
 601         case GIMPLE_RETURN:
 602           if (!compare_gimple_return (as_a <greturn *> (s1),
 603                                       as_a <greturn *> (s2)))
 604             return return_different_stmts (s1, s2, "GIMPLE_RETURN");
 605           break;
 606         case GIMPLE_GOTO:
 607           if (!compare_gimple_goto (s1, s2))
 608             return return_different_stmts (s1, s2, "GIMPLE_GOTO");
 609           break;
 610         case GIMPLE_ASM:
 611           if (!compare_gimple_asm (as_a <gasm *> (s1),
 612                                    as_a <gasm *> (s2)))
 613             return return_different_stmts (s1, s2, "GIMPLE_ASM");
 614           break;
 615         case GIMPLE_PREDICT:
 616         case GIMPLE_NOP:
 617           break;
 618         default:
 619           return return_false_with_msg ("Unknown GIMPLE code reached");
 620         }
 621
 622       gsi_next_nondebug (&gsi1);
 623       gsi_next_nondebug (&gsi2);
 624     }
 625
 626   if (!gsi_end_p (gsi2))
 627     return return_false ();
 628
 629   if (!compare_loops (bb1->bb, bb2->bb))
 630     return return_false ();
 631
 632   return true;
 633 }
 634
 635 /* Verifies for given GIMPLEs S1 and S2 that
 636    call statements are semantically equivalent.  */
 637
 638 bool
 639 func_checker::compare_gimple_call (gcall *s1, gcall *s2)
 640 {
 641   unsigned i;
 642   tree t1, t2;
 643
 644   if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
 645     return false;
 646
 647   operand_access_type_map map (5);
 648   classify_operands (s1, &map);
 649
 650   t1 = gimple_call_fn (s1);
 651   t2 = gimple_call_fn (s2);
 652   if (!compare_operand (t1, t2, get_operand_access_type (&map, t1)))
 653     return return_false ();
 654
 655   /* Compare flags.  */
 656   if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
 657       || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
 658       || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
 659       || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
 660       || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
 661       || gimple_call_from_new_or_delete (s1) != gimple_call_from_new_or_delete (s2)
 662       || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
 663       || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2))
 664     return false;
 665
 666   if (gimple_call_internal_p (s1)
 667       && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
 668     return false;
 669
 670   tree fntype1 = gimple_call_fntype (s1);
 671   tree fntype2 = gimple_call_fntype (s2);
 672
 673   /* For direct calls we verify that types are compatible so if we matched
 674      callees, callers must match, too.  For indirect calls however verify
 675      function type.  */
 676   if (!gimple_call_fndecl (s1))
 677     {
 678       if ((fntype1 && !fntype2)
 679           || (!fntype1 && fntype2)
 680           || (fntype1 && !types_compatible_p (fntype1, fntype2)))
 681         return return_false_with_msg ("call function types are not compatible");
 682     }
 683
 684   if (fntype1 && fntype2 && comp_type_attributes (fntype1, fntype2) != 1)
 685     return return_false_with_msg ("different fntype attributes");
 686
 687   tree chain1 = gimple_call_chain (s1);
 688   tree chain2 = gimple_call_chain (s2);
 689   if ((chain1 && !chain2)
 690       || (!chain1 && chain2)
 691       || !compare_operand (chain1, chain2,
 692                            get_operand_access_type (&map, chain1)))
 693     return return_false_with_msg ("static call chains are different");
 694
 695   /* Checking of argument.  */
 696   for (i = 0; i < gimple_call_num_args (s1); ++i)
 697     {
 698       t1 = gimple_call_arg (s1, i);
 699       t2 = gimple_call_arg (s2, i);
 700
 701       if (!compare_operand (t1, t2, get_operand_access_type (&map, t1)))
 702         return return_false_with_msg ("GIMPLE call operands are different");
 703     }
 704
 705   /* Return value checking.  */
 706   t1 = gimple_get_lhs (s1);
 707   t2 = gimple_get_lhs (s2);
 708
 709   /* For internal calls, lhs types need to be verified, as neither fntype nor
 710      callee comparisons can catch that.  */
 711   if (gimple_call_internal_p (s1)
 712       && t1
 713       && t2
 714       && !compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
 715     return return_false_with_msg ("GIMPLE internal call LHS type mismatch");
 716
 717   return compare_operand (t1, t2, get_operand_access_type (&map, t1));
 718 }
 719
 720
 721 /* Verifies for given GIMPLEs S1 and S2 that
 722    assignment statements are semantically equivalent.  */
 723
 724 bool
 725 func_checker::compare_gimple_assign (gimple *s1, gimple *s2)
 726 {
 727   tree arg1, arg2;
 728   tree_code code1, code2;
 729   unsigned i;
 730
 731   code1 = gimple_assign_rhs_code (s1);
 732   code2 = gimple_assign_rhs_code (s2);
 733
 734   if (code1 != code2)
 735     return false;
 736
 737   operand_access_type_map map (5);
 738   classify_operands (s1, &map);
 739
 740   for (i = 0; i < gimple_num_ops (s1); i++)
 741     {
 742       arg1 = gimple_op (s1, i);
 743       arg2 = gimple_op (s2, i);
 744
 745       /* Compare types for LHS.  */
 746       if (i == 0 && !gimple_store_p (s1))
 747         {
 748           if (!compatible_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
 749             return return_false_with_msg ("GIMPLE LHS type mismatch");
 750         }
 751
 752       if (!compare_operand (arg1, arg2, get_operand_access_type (&map, arg1)))
 753         return return_false_with_msg ("GIMPLE assignment operands "
 754                                       "are different");
 755     }
 756
 757
 758   return true;
 759 }
 760
 761 /* Verifies for given GIMPLEs S1 and S2 that
 762    condition statements are semantically equivalent.  */
 763
 764 bool
 765 func_checker::compare_gimple_cond (gimple *s1, gimple *s2)
 766 {
 767   tree t1, t2;
 768   tree_code code1, code2;
 769
 770   code1 = gimple_cond_code (s1);
 771   code2 = gimple_cond_code (s2);
 772
 773   if (code1 != code2)
 774     return false;
 775
 776   t1 = gimple_cond_lhs (s1);
 777   t2 = gimple_cond_lhs (s2);
 778
 779   if (!compare_operand (t1, t2, OP_NORMAL))
 780     return false;
 781
 782   t1 = gimple_cond_rhs (s1);
 783   t2 = gimple_cond_rhs (s2);
 784
 785   return compare_operand (t1, t2, OP_NORMAL);
 786 }
 787
 788 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 789    label statements are semantically equivalent.  */
 790
 791 bool
 792 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 793 {
 794   if (m_ignore_labels)
 795     return true;
 796
 797   tree t1 = gimple_label_label (g1);
 798   tree t2 = gimple_label_label (g2);
 799
 800   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 801     return return_false_with_msg ("FORCED_LABEL");
 802
 803   /* As the pass build BB to label mapping, no further check is needed.  */
 804   return true;
 805 }
 806
 807 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 808    switch statements are semantically equivalent.  */
 809
 810 bool
 811 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
 812 {
 813   unsigned lsize1, lsize2, i;
 814
 815   lsize1 = gimple_switch_num_labels (g1);
 816   lsize2 = gimple_switch_num_labels (g2);
 817
 818   if (lsize1 != lsize2)
 819     return false;
 820
 821   tree t1 = gimple_switch_index (g1);
 822   tree t2 = gimple_switch_index (g2);
 823
 824   if (!compare_operand (t1, t2, OP_NORMAL))
 825     return false;
 826
 827   for (i = 0; i < lsize1; i++)
 828     {
 829       tree label1 = gimple_switch_label (g1, i);
 830       tree label2 = gimple_switch_label (g2, i);
 831
 832       /* Label LOW and HIGH comparison.  */
 833       tree low1 = CASE_LOW (label1);
 834       tree low2 = CASE_LOW (label2);
 835
 836       if (!tree_int_cst_equal (low1, low2))
 837         return return_false_with_msg ("case low values are different");
 838
 839       tree high1 = CASE_HIGH (label1);
 840       tree high2 = CASE_HIGH (label2);
 841
 842       if (!tree_int_cst_equal (high1, high2))
 843         return return_false_with_msg ("case high values are different");
 844
 845       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 846           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 847         {
 848           label1 = CASE_LABEL (label1);
 849           label2 = CASE_LABEL (label2);
 850
 851           if (!compare_operand (label1, label2, OP_NORMAL))
 852             return return_false_with_msg ("switch label_exprs are different");
 853         }
 854       else if (!tree_int_cst_equal (label1, label2))
 855         return return_false_with_msg ("switch labels are different");
 856     }
 857
 858   return true;
 859 }
 860
 861 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 862    return statements are semantically equivalent.  */
 863
 864 bool
 865 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
 866 {
 867   tree t1, t2;
 868
 869   t1 = gimple_return_retval (g1);
 870   t2 = gimple_return_retval (g2);
 871
 872   /* Void return type.  */
 873   if (t1 == NULL && t2 == NULL)
 874     return true;
 875   else
 876     {
 877       operand_access_type_map map (3);
 878       return compare_operand (t1, t2, get_operand_access_type (&map, t1));
 879     }
 880 }
 881
 882 /* Verifies for given GIMPLEs S1 and S2 that
 883    goto statements are semantically equivalent.  */
 884
 885 bool
 886 func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
 887 {
 888   tree dest1, dest2;
 889
 890   dest1 = gimple_goto_dest (g1);
 891   dest2 = gimple_goto_dest (g2);
 892
 893   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 894     return false;
 895
 896   return compare_operand (dest1, dest2, OP_NORMAL);
 897 }
 898
 899 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 900    resx statements are semantically equivalent.  */
 901
 902 bool
 903 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
 904 {
 905   return gimple_resx_region (g1) == gimple_resx_region (g2);
 906 }
 907
 908 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 909    For the beginning, the pass only supports equality for
 910    '__asm__ __volatile__ ("", "", "", "memory")'.  */
 911
 912 bool
 913 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
 914 {
 915   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
 916     return false;
 917
 918   if (gimple_asm_input_p (g1) != gimple_asm_input_p (g2))
 919     return false;
 920
 921   if (gimple_asm_inline_p (g1) != gimple_asm_inline_p (g2))
 922     return false;
 923
 924   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
 925     return false;
 926
 927   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
 928     return false;
 929
 930   /* We do not suppport goto ASM statement comparison.  */
 931   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
 932     return false;
 933
 934   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
 935     return false;
 936
 937   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
 938     return return_false_with_msg ("ASM strings are different");
 939
 940   operand_access_type_map map (5);
 941   classify_operands (g1, &map);
 942
 943   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
 944     {
 945       tree input1 = gimple_asm_input_op (g1, i);
 946       tree input2 = gimple_asm_input_op (g2, i);
 947
 948       if (!compare_asm_inputs_outputs (input1, input2, &map))
 949         return return_false_with_msg ("ASM input is different");
 950     }
 951
 952   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
 953     {
 954       tree output1 = gimple_asm_output_op (g1, i);
 955       tree output2 = gimple_asm_output_op (g2, i);
 956
 957       if (!compare_asm_inputs_outputs (output1, output2, &map))
 958         return return_false_with_msg ("ASM output is different");
 959     }
 960
 961   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
 962     {
 963       tree clobber1 = gimple_asm_clobber_op (g1, i);
 964       tree clobber2 = gimple_asm_clobber_op (g2, i);
 965
 966       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
 967                             OEP_ONLY_CONST))
 968         return return_false_with_msg ("ASM clobber is different");
 969     }
 970
 971   return true;
 972 }
 973
 974 /* Helper for func_checker::classify_operands.  Record that T is a load.  */
 975
 976 static bool
 977 visit_load_store (gimple *, tree, tree t, void *data)
 978 {
 979   func_checker::operand_access_type_map *map =
 980     (func_checker::operand_access_type_map *) data;
 981   map->add (t);
 982   return false;
 983 }
 984
 985 /* Compute hash map determining access types of operands.  */
 986
 987 void
 988 func_checker::classify_operands (const gimple *stmt,
 989                                  operand_access_type_map *map)
 990 {
 991   walk_stmt_load_store_ops (const_cast <gimple *> (stmt),
 992                             (void *)map, visit_load_store, visit_load_store);
 993 }
 994
 995 /* Return access type of a given operand.  */
 996
 997 func_checker::operand_access_type
 998 func_checker::get_operand_access_type (operand_access_type_map *map, tree t)
 999 {
1000   if (map->contains (t))
1001     return OP_MEMORY;
1002   return OP_NORMAL;
1003 }
1004
1005 } // ipa_icf_gimple namespace