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 compatible so if we matched
 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   /* For internal calls, lhs types need to be verified, as neither fntype nor
 707      callee comparisons can catch that.  */
 708   if (gimple_call_internal_p (s1)
 709       && t1
 710       && t2
 711       && !compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
 712     return return_false_with_msg ("GIMPLE internal call LHS type mismatch");
 713
 714   return compare_operand (t1, t2, get_operand_access_type (&map, t1));
 715 }
 716
 717
 718 /* Verifies for given GIMPLEs S1 and S2 that
 719    assignment statements are semantically equivalent.  */
 720
 721 bool
 722 func_checker::compare_gimple_assign (gimple *s1, gimple *s2)
 723 {
 724   tree arg1, arg2;
 725   tree_code code1, code2;
 726   unsigned i;
 727
 728   code1 = gimple_assign_rhs_code (s1);
 729   code2 = gimple_assign_rhs_code (s2);
 730
 731   if (code1 != code2)
 732     return false;
 733
 734   operand_access_type_map map (5);
 735   classify_operands (s1, &map);
 736
 737   for (i = 0; i < gimple_num_ops (s1); i++)
 738     {
 739       arg1 = gimple_op (s1, i);
 740       arg2 = gimple_op (s2, i);
 741
 742       /* Compare types for LHS.  */
 743       if (i == 0 && !gimple_store_p (s1))
 744         {
 745           if (!compatible_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
 746             return return_false_with_msg ("GIMPLE LHS type mismatch");
 747         }
 748
 749       if (!compare_operand (arg1, arg2, get_operand_access_type (&map, arg1)))
 750         return return_false_with_msg ("GIMPLE assignment operands "
 751                                       "are different");
 752     }
 753
 754
 755   return true;
 756 }
 757
 758 /* Verifies for given GIMPLEs S1 and S2 that
 759    condition statements are semantically equivalent.  */
 760
 761 bool
 762 func_checker::compare_gimple_cond (gimple *s1, gimple *s2)
 763 {
 764   tree t1, t2;
 765   tree_code code1, code2;
 766
 767   code1 = gimple_cond_code (s1);
 768   code2 = gimple_cond_code (s2);
 769
 770   if (code1 != code2)
 771     return false;
 772
 773   t1 = gimple_cond_lhs (s1);
 774   t2 = gimple_cond_lhs (s2);
 775
 776   if (!compare_operand (t1, t2, OP_NORMAL))
 777     return false;
 778
 779   t1 = gimple_cond_rhs (s1);
 780   t2 = gimple_cond_rhs (s2);
 781
 782   return compare_operand (t1, t2, OP_NORMAL);
 783 }
 784
 785 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 786    label statements are semantically equivalent.  */
 787
 788 bool
 789 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 790 {
 791   if (m_ignore_labels)
 792     return true;
 793
 794   tree t1 = gimple_label_label (g1);
 795   tree t2 = gimple_label_label (g2);
 796
 797   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 798     return return_false_with_msg ("FORCED_LABEL");
 799
 800   /* As the pass build BB to label mapping, no further check is needed.  */
 801   return true;
 802 }
 803
 804 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 805    switch statements are semantically equivalent.  */
 806
 807 bool
 808 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
 809 {
 810   unsigned lsize1, lsize2, i;
 811
 812   lsize1 = gimple_switch_num_labels (g1);
 813   lsize2 = gimple_switch_num_labels (g2);
 814
 815   if (lsize1 != lsize2)
 816     return false;
 817
 818   tree t1 = gimple_switch_index (g1);
 819   tree t2 = gimple_switch_index (g2);
 820
 821   if (!compare_operand (t1, t2, OP_NORMAL))
 822     return false;
 823
 824   for (i = 0; i < lsize1; i++)
 825     {
 826       tree label1 = gimple_switch_label (g1, i);
 827       tree label2 = gimple_switch_label (g2, i);
 828
 829       /* Label LOW and HIGH comparison.  */
 830       tree low1 = CASE_LOW (label1);
 831       tree low2 = CASE_LOW (label2);
 832
 833       if (!tree_int_cst_equal (low1, low2))
 834         return return_false_with_msg ("case low values are different");
 835
 836       tree high1 = CASE_HIGH (label1);
 837       tree high2 = CASE_HIGH (label2);
 838
 839       if (!tree_int_cst_equal (high1, high2))
 840         return return_false_with_msg ("case high values are different");
 841
 842       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 843           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 844         {
 845           label1 = CASE_LABEL (label1);
 846           label2 = CASE_LABEL (label2);
 847
 848           if (!compare_operand (label1, label2, OP_NORMAL))
 849             return return_false_with_msg ("switch label_exprs are different");
 850         }
 851       else if (!tree_int_cst_equal (label1, label2))
 852         return return_false_with_msg ("switch labels are different");
 853     }
 854
 855   return true;
 856 }
 857
 858 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 859    return statements are semantically equivalent.  */
 860
 861 bool
 862 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
 863 {
 864   tree t1, t2;
 865
 866   t1 = gimple_return_retval (g1);
 867   t2 = gimple_return_retval (g2);
 868
 869   /* Void return type.  */
 870   if (t1 == NULL && t2 == NULL)
 871     return true;
 872   else
 873     {
 874       operand_access_type_map map (3);
 875       return compare_operand (t1, t2, get_operand_access_type (&map, t1));
 876     }
 877 }
 878
 879 /* Verifies for given GIMPLEs S1 and S2 that
 880    goto statements are semantically equivalent.  */
 881
 882 bool
 883 func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
 884 {
 885   tree dest1, dest2;
 886
 887   dest1 = gimple_goto_dest (g1);
 888   dest2 = gimple_goto_dest (g2);
 889
 890   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 891     return false;
 892
 893   return compare_operand (dest1, dest2, OP_NORMAL);
 894 }
 895
 896 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 897    resx statements are semantically equivalent.  */
 898
 899 bool
 900 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
 901 {
 902   return gimple_resx_region (g1) == gimple_resx_region (g2);
 903 }
 904
 905 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 906    For the beginning, the pass only supports equality for
 907    '__asm__ __volatile__ ("", "", "", "memory")'.  */
 908
 909 bool
 910 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
 911 {
 912   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
 913     return false;
 914
 915   if (gimple_asm_input_p (g1) != gimple_asm_input_p (g2))
 916     return false;
 917
 918   if (gimple_asm_inline_p (g1) != gimple_asm_inline_p (g2))
 919     return false;
 920
 921   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
 922     return false;
 923
 924   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
 925     return false;
 926
 927   /* We do not suppport goto ASM statement comparison.  */
 928   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
 929     return false;
 930
 931   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
 932     return false;
 933
 934   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
 935     return return_false_with_msg ("ASM strings are different");
 936
 937   operand_access_type_map map (5);
 938   classify_operands (g1, &map);
 939
 940   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
 941     {
 942       tree input1 = gimple_asm_input_op (g1, i);
 943       tree input2 = gimple_asm_input_op (g2, i);
 944
 945       if (!compare_asm_inputs_outputs (input1, input2, &map))
 946         return return_false_with_msg ("ASM input is different");
 947     }
 948
 949   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
 950     {
 951       tree output1 = gimple_asm_output_op (g1, i);
 952       tree output2 = gimple_asm_output_op (g2, i);
 953
 954       if (!compare_asm_inputs_outputs (output1, output2, &map))
 955         return return_false_with_msg ("ASM output is different");
 956     }
 957
 958   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
 959     {
 960       tree clobber1 = gimple_asm_clobber_op (g1, i);
 961       tree clobber2 = gimple_asm_clobber_op (g2, i);
 962
 963       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
 964                             OEP_ONLY_CONST))
 965         return return_false_with_msg ("ASM clobber is different");
 966     }
 967
 968   return true;
 969 }
 970
 971 /* Helper for func_checker::classify_operands.  Record that T is a load.  */
 972
 973 static bool
 974 visit_load_store (gimple *, tree, tree t, void *data)
 975 {
 976   func_checker::operand_access_type_map *map =
 977     (func_checker::operand_access_type_map *) data;
 978   map->add (t);
 979   return false;
 980 }
 981
 982 /* Compute hash map determining access types of operands.  */
 983
 984 void
 985 func_checker::classify_operands (const gimple *stmt,
 986                                  operand_access_type_map *map)
 987 {
 988   walk_stmt_load_store_ops (const_cast <gimple *> (stmt),
 989                             (void *)map, visit_load_store, visit_load_store);
 990 }
 991
 992 /* Return access type of a given operand.  */
 993
 994 func_checker::operand_access_type
 995 func_checker::get_operand_access_type (operand_access_type_map *map, tree t)
 996 {
 997   if (map->contains (t))
 998     return OP_MEMORY;
 999   return OP_NORMAL;
1000 }
1001
1002 } // ipa_icf_gimple namespace