gcc/ipa-icf-gimple.c

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