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