gcc/ipa-icf-gimple.c

   1 /* Interprocedural Identical Code Folding pass
   2    Copyright (C) 2014 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 "tree.h"
  26 #include "basic-block.h"
  27 #include "tree-ssa-alias.h"
  28 #include "internal-fn.h"
  29 #include "gimple-expr.h"
  30 #include "is-a.h"
  31 #include "gimple.h"
  32 #include "expr.h"
  33 #include "gimple-iterator.h"
  34 #include "gimple-ssa.h"
  35 #include "tree-cfg.h"
  36 #include "stringpool.h"
  37 #include "tree-dfa.h"
  38 #include "tree-pass.h"
  39 #include "gimple-pretty-print.h"
  40 #include "cfgloop.h"
  41 #include "except.h"
  42 #include "data-streamer.h"
  43 #include "ipa-utils.h"
  44 #include <list>
  45 #include "tree-ssanames.h"
  46 #include "tree-eh.h"
  47
  48 #include "ipa-icf-gimple.h"
  49 #include "ipa-icf.h"
  50
  51 namespace ipa_icf_gimple {
  52
  53 /* Initialize internal structures for a given SOURCE_FUNC_DECL and
  54    TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
  55    an option COMPARE_POLYMORPHIC is true. For special cases, one can
  56    set IGNORE_LABELS to skip label comparison.
  57    Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
  58    of declarations that can be skipped.  */
  59
  60 func_checker::func_checker (tree source_func_decl, tree target_func_decl,
  61                             bool compare_polymorphic,
  62                             bool ignore_labels,
  63                             hash_set<symtab_node *> *ignored_source_nodes,
  64                             hash_set<symtab_node *> *ignored_target_nodes)
  65   : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl),
  66     m_ignored_source_nodes (ignored_source_nodes),
  67     m_ignored_target_nodes (ignored_target_nodes),
  68     m_compare_polymorphic (compare_polymorphic),
  69     m_ignore_labels (ignore_labels)
  70 {
  71   function *source_func = DECL_STRUCT_FUNCTION (source_func_decl);
  72   function *target_func = DECL_STRUCT_FUNCTION (target_func_decl);
  73
  74   unsigned ssa_source = SSANAMES (source_func)->length ();
  75   unsigned ssa_target = SSANAMES (target_func)->length ();
  76
  77   m_source_ssa_names.create (ssa_source);
  78   m_target_ssa_names.create (ssa_target);
  79
  80   for (unsigned i = 0; i < ssa_source; i++)
  81     m_source_ssa_names.safe_push (-1);
  82
  83   for (unsigned i = 0; i < ssa_target; i++)
  84     m_target_ssa_names.safe_push (-1);
  85 }
  86
  87 /* Memory release routine.  */
  88
  89 func_checker::~func_checker ()
  90 {
  91   m_source_ssa_names.release();
  92   m_target_ssa_names.release();
  93 }
  94
  95 /* Verifies that trees T1 and T2 are equivalent from perspective of ICF.  */
  96
  97 bool
  98 func_checker::compare_ssa_name (tree t1, tree t2)
  99 {
 100   unsigned i1 = SSA_NAME_VERSION (t1);
 101   unsigned i2 = SSA_NAME_VERSION (t2);
 102
 103   if (m_source_ssa_names[i1] == -1)
 104     m_source_ssa_names[i1] = i2;
 105   else if (m_source_ssa_names[i1] != (int) i2)
 106     return false;
 107
 108   if(m_target_ssa_names[i2] == -1)
 109     m_target_ssa_names[i2] = i1;
 110   else if (m_target_ssa_names[i2] != (int) i1)
 111     return false;
 112
 113   return true;
 114 }
 115
 116 /* Verification function for edges E1 and E2.  */
 117
 118 bool
 119 func_checker::compare_edge (edge e1, edge e2)
 120 {
 121   if (e1->flags != e2->flags)
 122     return false;
 123
 124   bool existed_p;
 125
 126   edge &slot = m_edge_map.get_or_insert (e1, &existed_p);
 127   if (existed_p)
 128     return return_with_debug (slot == e2);
 129   else
 130     slot = e2;
 131
 132   /* TODO: filter edge probabilities for profile feedback match.  */
 133
 134   return true;
 135 }
 136
 137 /* Verification function for declaration trees T1 and T2 that
 138    come from functions FUNC1 and FUNC2.  */
 139
 140 bool
 141 func_checker::compare_decl (tree t1, tree t2)
 142 {
 143   if (!auto_var_in_fn_p (t1, m_source_func_decl)
 144       || !auto_var_in_fn_p (t2, m_target_func_decl))
 145     return return_with_debug (t1 == t2);
 146
 147   tree_code t = TREE_CODE (t1);
 148   if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
 149       && DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2))
 150     return return_false_with_msg ("DECL_BY_REFERENCE flags are different");
 151
 152   if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
 153                            m_compare_polymorphic))
 154     return return_false ();
 155
 156   bool existed_p;
 157
 158   tree &slot = m_decl_map.get_or_insert (t1, &existed_p);
 159   if (existed_p)
 160     return return_with_debug (slot == t2);
 161   else
 162     slot = t2;
 163
 164   return true;
 165 }
 166
 167 /* Return true if types are compatible from perspective of ICF.  */
 168 bool func_checker::compatible_types_p (tree t1, tree t2,
 169                                        bool compare_polymorphic,
 170                                        bool first_argument)
 171 {
 172   if (TREE_CODE (t1) != TREE_CODE (t2))
 173     return return_false_with_msg ("different tree types");
 174
 175   if (!types_compatible_p (t1, t2))
 176     return return_false_with_msg ("types are not compatible");
 177
 178   if (get_alias_set (t1) != get_alias_set (t2))
 179     return return_false_with_msg ("alias sets are different");
 180
 181   /* We call contains_polymorphic_type_p with this pointer type.  */
 182   if (first_argument && TREE_CODE (t1) == POINTER_TYPE)
 183     {
 184       t1 = TREE_TYPE (t1);
 185       t2 = TREE_TYPE (t2);
 186     }
 187
 188   if (compare_polymorphic)
 189     if (contains_polymorphic_type_p (t1) || contains_polymorphic_type_p (t2))
 190       {
 191         if (!contains_polymorphic_type_p (t1) || !contains_polymorphic_type_p (t2))
 192           return return_false_with_msg ("one type is not polymorphic");
 193
 194         if (!types_must_be_same_for_odr (t1, t2))
 195           return return_false_with_msg ("types are not same for ODR");
 196       }
 197
 198   return true;
 199 }
 200
 201 /* Function responsible for comparison of handled components T1 and T2.
 202    If these components, from functions FUNC1 and FUNC2, are equal, true
 203    is returned.  */
 204
 205 bool
 206 func_checker::compare_operand (tree t1, tree t2)
 207 {
 208   tree base1, base2, x1, x2, y1, y2, z1, z2;
 209   HOST_WIDE_INT offset1 = 0, offset2 = 0;
 210   bool ret;
 211
 212   if (!t1 && !t2)
 213     return true;
 214   else if (!t1 || !t2)
 215     return false;
 216
 217   tree tt1 = TREE_TYPE (t1);
 218   tree tt2 = TREE_TYPE (t2);
 219
 220   if (!func_checker::compatible_types_p (tt1, tt2))
 221     return false;
 222
 223   base1 = get_addr_base_and_unit_offset (t1, &offset1);
 224   base2 = get_addr_base_and_unit_offset (t2, &offset2);
 225
 226   if (base1 && base2)
 227     {
 228       if (offset1 != offset2)
 229         return return_false_with_msg ("base offsets are different");
 230
 231       t1 = base1;
 232       t2 = base2;
 233     }
 234
 235   if (TREE_CODE (t1) != TREE_CODE (t2))
 236     return return_false ();
 237
 238   switch (TREE_CODE (t1))
 239     {
 240     case CONSTRUCTOR:
 241       {
 242         unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (t1));
 243         unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (t2));
 244
 245         if (length1 != length2)
 246           return return_false ();
 247
 248         for (unsigned i = 0; i < length1; i++)
 249           if (!compare_operand (CONSTRUCTOR_ELT (t1, i)->value,
 250                                 CONSTRUCTOR_ELT (t2, i)->value))
 251             return return_false();
 252
 253         return true;
 254       }
 255     case ARRAY_REF:
 256     case ARRAY_RANGE_REF:
 257       x1 = TREE_OPERAND (t1, 0);
 258       x2 = TREE_OPERAND (t2, 0);
 259       y1 = TREE_OPERAND (t1, 1);
 260       y2 = TREE_OPERAND (t2, 1);
 261
 262       if (!compare_operand (array_ref_low_bound (t1),
 263                             array_ref_low_bound (t2)))
 264         return return_false_with_msg ("");
 265       if (!compare_operand (array_ref_element_size (t1),
 266                             array_ref_element_size (t2)))
 267         return return_false_with_msg ("");
 268       if (!compare_operand (x1, x2))
 269         return return_false_with_msg ("");
 270       return compare_operand (y1, y2);
 271     case MEM_REF:
 272       {
 273         x1 = TREE_OPERAND (t1, 0);
 274         x2 = TREE_OPERAND (t2, 0);
 275         y1 = TREE_OPERAND (t1, 1);
 276         y2 = TREE_OPERAND (t2, 1);
 277
 278         /* See if operand is an memory access (the test originate from
 279          gimple_load_p).
 280
 281         In this case the alias set of the function being replaced must
 282         be subset of the alias set of the other function.  At the moment
 283         we seek for equivalency classes, so simply require inclussion in
 284         both directions.  */
 285
 286         if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
 287           return return_false ();
 288
 289         if (!compare_operand (x1, x2))
 290           return return_false_with_msg ("");
 291
 292         if (get_alias_set (TREE_TYPE (y1)) != get_alias_set (TREE_TYPE (y2)))
 293           return return_false_with_msg ("alias set for MEM_REF offsets are different");
 294
 295         ao_ref r1, r2;
 296         ao_ref_init (&r1, t1);
 297         ao_ref_init (&r2, t2);
 298         if (ao_ref_alias_set (&r1) != ao_ref_alias_set (&r2)
 299             || ao_ref_base_alias_set (&r1) != ao_ref_base_alias_set (&r2))
 300           return return_false_with_msg ("ao alias sets are different");
 301
 302         /* Type of the offset on MEM_REF does not matter.  */
 303         return wi::to_offset  (y1) == wi::to_offset  (y2);
 304       }
 305     case COMPONENT_REF:
 306       {
 307         x1 = TREE_OPERAND (t1, 0);
 308         x2 = TREE_OPERAND (t2, 0);
 309         y1 = TREE_OPERAND (t1, 1);
 310         y2 = TREE_OPERAND (t2, 1);
 311
 312         ret = compare_operand (x1, x2)
 313               && compare_operand (y1, y2);
 314
 315         return return_with_debug (ret);
 316       }
 317     /* Virtual table call.  */
 318     case OBJ_TYPE_REF:
 319       {
 320         x1 = TREE_OPERAND (t1, 0);
 321         x2 = TREE_OPERAND (t2, 0);
 322         y1 = TREE_OPERAND (t1, 1);
 323         y2 = TREE_OPERAND (t2, 1);
 324         z1 = TREE_OPERAND (t1, 2);
 325         z2 = TREE_OPERAND (t2, 2);
 326
 327         ret = compare_operand (x1, x2)
 328               && compare_operand (y1, y2)
 329               && compare_operand (z1, z2);
 330
 331         return return_with_debug (ret);
 332       }
 333     case ADDR_EXPR:
 334       {
 335         x1 = TREE_OPERAND (t1, 0);
 336         x2 = TREE_OPERAND (t2, 0);
 337
 338         ret = compare_operand (x1, x2);
 339         return return_with_debug (ret);
 340       }
 341     case SSA_NAME:
 342       {
 343         ret = compare_ssa_name (t1, t2);
 344
 345         if (!ret)
 346           return return_with_debug (ret);
 347
 348         if (SSA_NAME_IS_DEFAULT_DEF (t1))
 349           {
 350             tree b1 = SSA_NAME_VAR (t1);
 351             tree b2 = SSA_NAME_VAR (t2);
 352
 353             if (b1 == NULL && b2 == NULL)
 354               return true;
 355
 356             if (b1 == NULL || b2 == NULL || TREE_CODE (b1) != TREE_CODE (b2))
 357               return return_false ();
 358
 359             switch (TREE_CODE (b1))
 360               {
 361               case VAR_DECL:
 362                 return return_with_debug (compare_variable_decl (t1, t2));
 363               case PARM_DECL:
 364               case RESULT_DECL:
 365                 ret = compare_decl (b1, b2);
 366                 return return_with_debug (ret);
 367               default:
 368                 return return_false_with_msg ("Unknown TREE code reached");
 369               }
 370           }
 371         else
 372           return true;
 373       }
 374     case INTEGER_CST:
 375       {
 376         ret = compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2))
 377               && wi::to_offset  (t1) == wi::to_offset  (t2);
 378
 379         return return_with_debug (ret);
 380       }
 381     case COMPLEX_CST:
 382     case VECTOR_CST:
 383     case STRING_CST:
 384     case REAL_CST:
 385       {
 386         ret = operand_equal_p (t1, t2, OEP_ONLY_CONST);
 387         return return_with_debug (ret);
 388       }
 389     case FUNCTION_DECL:
 390       {
 391         ret = compare_function_decl (t1, t2);
 392         return return_with_debug (ret);
 393       }
 394     case VAR_DECL:
 395       return return_with_debug (compare_variable_decl (t1, t2));
 396     case FIELD_DECL:
 397       {
 398         tree offset1 = DECL_FIELD_OFFSET (t1);
 399         tree offset2 = DECL_FIELD_OFFSET (t2);
 400
 401         tree bit_offset1 = DECL_FIELD_BIT_OFFSET (t1);
 402         tree bit_offset2 = DECL_FIELD_BIT_OFFSET (t2);
 403
 404         ret = compare_operand (offset1, offset2)
 405               && compare_operand (bit_offset1, bit_offset2);
 406
 407         return return_with_debug (ret);
 408       }
 409     case LABEL_DECL:
 410       {
 411         int *bb1 = m_label_bb_map.get (t1);
 412         int *bb2 = m_label_bb_map.get (t2);
 413
 414         return return_with_debug (*bb1 == *bb2);
 415       }
 416     case PARM_DECL:
 417     case RESULT_DECL:
 418     case CONST_DECL:
 419     case BIT_FIELD_REF:
 420       {
 421         ret = compare_decl (t1, t2);
 422         return return_with_debug (ret);
 423       }
 424     default:
 425       return return_false_with_msg ("Unknown TREE code reached");
 426     }
 427 }
 428
 429 /* Compares two tree list operands T1 and T2 and returns true if these
 430    two trees are semantically equivalent.  */
 431
 432 bool
 433 func_checker::compare_tree_list_operand (tree t1, tree t2)
 434 {
 435   gcc_assert (TREE_CODE (t1) == TREE_LIST);
 436   gcc_assert (TREE_CODE (t2) == TREE_LIST);
 437
 438   for (; t1; t1 = TREE_CHAIN (t1))
 439     {
 440       if (!t2)
 441         return false;
 442
 443       if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2)))
 444         return return_false ();
 445
 446       t2 = TREE_CHAIN (t2);
 447     }
 448
 449   if (t2)
 450     return return_false ();
 451
 452   return true;
 453 }
 454
 455 /* Verifies that trees T1 and T2, representing function declarations
 456    are equivalent from perspective of ICF.  */
 457
 458 bool
 459 func_checker::compare_function_decl (tree t1, tree t2)
 460 {
 461   bool ret = false;
 462
 463   if (t1 == t2)
 464     return true;
 465
 466   symtab_node *n1 = symtab_node::get (t1);
 467   symtab_node *n2 = symtab_node::get (t2);
 468
 469   if (m_ignored_source_nodes != NULL && m_ignored_target_nodes != NULL)
 470     {
 471       ret = m_ignored_source_nodes->contains (n1)
 472             && m_ignored_target_nodes->contains (n2);
 473
 474       if (ret)
 475         return true;
 476     }
 477
 478   /* If function decl is WEAKREF, we compare targets.  */
 479   cgraph_node *f1 = cgraph_node::get (t1);
 480   cgraph_node *f2 = cgraph_node::get (t2);
 481
 482   if(f1 && f2 && f1->weakref && f2->weakref)
 483     ret = f1->alias_target == f2->alias_target;
 484
 485   return ret;
 486 }
 487
 488 /* Verifies that trees T1 and T2 do correspond.  */
 489
 490 bool
 491 func_checker::compare_variable_decl (tree t1, tree t2)
 492 {
 493   bool ret = false;
 494
 495   if (t1 == t2)
 496     return true;
 497
 498   if (TREE_CODE (t1) == VAR_DECL && (DECL_EXTERNAL (t1) || TREE_STATIC (t1)))
 499     {
 500       symtab_node *n1 = symtab_node::get (t1);
 501       symtab_node *n2 = symtab_node::get (t2);
 502
 503       if (m_ignored_source_nodes != NULL && m_ignored_target_nodes != NULL)
 504         {
 505           ret = m_ignored_source_nodes->contains (n1)
 506                 && m_ignored_target_nodes->contains (n2);
 507
 508           if (ret)
 509             return true;
 510         }
 511     }
 512   ret = compare_decl (t1, t2);
 513
 514   return return_with_debug (ret);
 515 }
 516
 517 void
 518 func_checker::parse_labels (sem_bb *bb)
 519 {
 520   for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
 521        gsi_next (&gsi))
 522     {
 523       gimple stmt = gsi_stmt (gsi);
 524
 525       if (gimple_code (stmt) == GIMPLE_LABEL)
 526         {
 527           tree t = gimple_label_label (stmt);
 528           gcc_assert (TREE_CODE (t) == LABEL_DECL);
 529
 530           m_label_bb_map.put (t, bb->bb->index);
 531         }
 532     }
 533 }
 534
 535 /* Basic block equivalence comparison function that returns true if
 536    basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
 537
 538    In general, a collection of equivalence dictionaries is built for types
 539    like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
 540    is utilized by every statement-by-stament comparison function.  */
 541
 542 bool
 543 func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
 544 {
 545   unsigned i;
 546   gimple_stmt_iterator gsi1, gsi2;
 547   gimple s1, s2;
 548
 549   if (bb1->nondbg_stmt_count != bb2->nondbg_stmt_count
 550       || bb1->edge_count != bb2->edge_count)
 551     return return_false ();
 552
 553   gsi1 = gsi_start_bb (bb1->bb);
 554   gsi2 = gsi_start_bb (bb2->bb);
 555
 556   for (i = 0; i < bb1->nondbg_stmt_count; i++)
 557     {
 558       if (is_gimple_debug (gsi_stmt (gsi1)))
 559         gsi_next_nondebug (&gsi1);
 560
 561       if (is_gimple_debug (gsi_stmt (gsi2)))
 562         gsi_next_nondebug (&gsi2);
 563
 564       s1 = gsi_stmt (gsi1);
 565       s2 = gsi_stmt (gsi2);
 566
 567       int eh1 = lookup_stmt_eh_lp_fn
 568                 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
 569       int eh2 = lookup_stmt_eh_lp_fn
 570                 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
 571
 572       if (eh1 != eh2)
 573         return return_false_with_msg ("EH regions are different");
 574
 575       if (gimple_code (s1) != gimple_code (s2))
 576         return return_false_with_msg ("gimple codes are different");
 577
 578       switch (gimple_code (s1))
 579         {
 580         case GIMPLE_CALL:
 581           if (!compare_gimple_call (s1, s2))
 582             return return_different_stmts (s1, s2, "GIMPLE_CALL");
 583           break;
 584         case GIMPLE_ASSIGN:
 585           if (!compare_gimple_assign (s1, s2))
 586             return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
 587           break;
 588         case GIMPLE_COND:
 589           if (!compare_gimple_cond (s1, s2))
 590             return return_different_stmts (s1, s2, "GIMPLE_COND");
 591           break;
 592         case GIMPLE_SWITCH:
 593           if (!compare_gimple_switch (s1, s2))
 594             return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
 595           break;
 596         case GIMPLE_DEBUG:
 597         case GIMPLE_EH_DISPATCH:
 598           break;
 599         case GIMPLE_RESX:
 600           if (!compare_gimple_resx (s1, s2))
 601             return return_different_stmts (s1, s2, "GIMPLE_RESX");
 602           break;
 603         case GIMPLE_LABEL:
 604           if (!compare_gimple_label (s1, s2))
 605             return return_different_stmts (s1, s2, "GIMPLE_LABEL");
 606           break;
 607         case GIMPLE_RETURN:
 608           if (!compare_gimple_return (s1, s2))
 609             return return_different_stmts (s1, s2, "GIMPLE_RETURN");
 610           break;
 611         case GIMPLE_GOTO:
 612           if (!compare_gimple_goto (s1, s2))
 613             return return_different_stmts (s1, s2, "GIMPLE_GOTO");
 614           break;
 615         case GIMPLE_ASM:
 616           if (!compare_gimple_asm (s1, s2))
 617             return return_different_stmts (s1, s2, "GIMPLE_ASM");
 618           break;
 619         case GIMPLE_PREDICT:
 620         case GIMPLE_NOP:
 621           return true;
 622         default:
 623           return return_false_with_msg ("Unknown GIMPLE code reached");
 624         }
 625
 626       gsi_next (&gsi1);
 627       gsi_next (&gsi2);
 628     }
 629
 630   return true;
 631 }
 632
 633 /* Verifies for given GIMPLEs S1 and S2 that
 634    call statements are semantically equivalent.  */
 635
 636 bool
 637 func_checker::compare_gimple_call (gimple s1, gimple s2)
 638 {
 639   unsigned i;
 640   tree t1, t2;
 641
 642   if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
 643     return false;
 644
 645   t1 = gimple_call_fndecl (s1);
 646   t2 = gimple_call_fndecl (s2);
 647
 648   /* Function pointer variables are not supported yet.  */
 649   if (!compare_operand (t1, t2))
 650     return return_false();
 651
 652   /* Checking of argument.  */
 653   for (i = 0; i < gimple_call_num_args (s1); ++i)
 654     {
 655       t1 = gimple_call_arg (s1, i);
 656       t2 = gimple_call_arg (s2, i);
 657
 658       if (!compare_operand (t1, t2))
 659         return false;
 660     }
 661
 662   /* Return value checking.  */
 663   t1 = gimple_get_lhs (s1);
 664   t2 = gimple_get_lhs (s2);
 665
 666   return compare_operand (t1, t2);
 667 }
 668
 669
 670 /* Verifies for given GIMPLEs S1 and S2 that
 671    assignment statements are semantically equivalent.  */
 672
 673 bool
 674 func_checker::compare_gimple_assign (gimple s1, gimple s2)
 675 {
 676   tree arg1, arg2;
 677   tree_code code1, code2;
 678   unsigned i;
 679
 680   code1 = gimple_expr_code (s1);
 681   code2 = gimple_expr_code (s2);
 682
 683   if (code1 != code2)
 684     return false;
 685
 686   code1 = gimple_assign_rhs_code (s1);
 687   code2 = gimple_assign_rhs_code (s2);
 688
 689   if (code1 != code2)
 690     return false;
 691
 692   for (i = 0; i < gimple_num_ops (s1); i++)
 693     {
 694       arg1 = gimple_op (s1, i);
 695       arg2 = gimple_op (s2, i);
 696
 697       if (!compare_operand (arg1, arg2))
 698         return false;
 699     }
 700
 701
 702   return true;
 703 }
 704
 705 /* Verifies for given GIMPLEs S1 and S2 that
 706    condition statements are semantically equivalent.  */
 707
 708 bool
 709 func_checker::compare_gimple_cond (gimple s1, gimple s2)
 710 {
 711   tree t1, t2;
 712   tree_code code1, code2;
 713
 714   code1 = gimple_expr_code (s1);
 715   code2 = gimple_expr_code (s2);
 716
 717   if (code1 != code2)
 718     return false;
 719
 720   t1 = gimple_cond_lhs (s1);
 721   t2 = gimple_cond_lhs (s2);
 722
 723   if (!compare_operand (t1, t2))
 724     return false;
 725
 726   t1 = gimple_cond_rhs (s1);
 727   t2 = gimple_cond_rhs (s2);
 728
 729   return compare_operand (t1, t2);
 730 }
 731
 732 /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2.  */
 733
 734 bool
 735 func_checker::compare_tree_ssa_label (tree t1, tree t2)
 736 {
 737   return compare_operand (t1, t2);
 738 }
 739
 740 /* Verifies for given GIMPLEs S1 and S2 that
 741    label statements are semantically equivalent.  */
 742
 743 bool
 744 func_checker::compare_gimple_label (gimple g1, gimple g2)
 745 {
 746   if (m_ignore_labels)
 747     return true;
 748
 749   tree t1 = gimple_label_label (g1);
 750   tree t2 = gimple_label_label (g2);
 751
 752   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 753     return return_false_with_msg ("FORCED_LABEL");
 754
 755   return compare_tree_ssa_label (t1, t2);
 756 }
 757
 758 /* Verifies for given GIMPLEs S1 and S2 that
 759    switch statements are semantically equivalent.  */
 760
 761 bool
 762 func_checker::compare_gimple_switch (gimple g1, gimple g2)
 763 {
 764   unsigned lsize1, lsize2, i;
 765
 766   lsize1 = gimple_switch_num_labels (g1);
 767   lsize2 = gimple_switch_num_labels (g2);
 768
 769   if (lsize1 != lsize2)
 770     return false;
 771
 772   tree t1 = gimple_switch_index (g1);
 773   tree t2 = gimple_switch_index (g2);
 774
 775   if (!compare_operand (t1, t2))
 776     return false;
 777
 778   for (i = 0; i < lsize1; i++)
 779     {
 780       tree label1 = gimple_switch_label (g1, i);
 781       tree label2 = gimple_switch_label (g2, i);
 782
 783       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 784           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 785         {
 786           label1 = CASE_LABEL (label1);
 787           label2 = CASE_LABEL (label2);
 788
 789           if (!compare_operand (label1, label2))
 790             return return_false_with_msg ("switch label_exprs are different");
 791         }
 792       else if (!tree_int_cst_equal (label1, label2))
 793         return return_false_with_msg ("switch labels are different");
 794     }
 795
 796   return true;
 797 }
 798
 799 /* Verifies for given GIMPLEs S1 and S2 that
 800    return statements are semantically equivalent.  */
 801
 802 bool
 803 func_checker::compare_gimple_return (gimple g1, gimple g2)
 804 {
 805   tree t1, t2;
 806
 807   t1 = gimple_return_retval (g1);
 808   t2 = gimple_return_retval (g2);
 809
 810   /* Void return type.  */
 811   if (t1 == NULL && t2 == NULL)
 812     return true;
 813   else
 814     return compare_operand (t1, t2);
 815 }
 816
 817 /* Verifies for given GIMPLEs S1 and S2 that
 818    goto statements are semantically equivalent.  */
 819
 820 bool
 821 func_checker::compare_gimple_goto (gimple g1, gimple g2)
 822 {
 823   tree dest1, dest2;
 824
 825   dest1 = gimple_goto_dest (g1);
 826   dest2 = gimple_goto_dest (g2);
 827
 828   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 829     return false;
 830
 831   return compare_operand (dest1, dest2);
 832 }
 833
 834 /* Verifies for given GIMPLEs S1 and S2 that
 835    resx statements are semantically equivalent.  */
 836
 837 bool
 838 func_checker::compare_gimple_resx (gimple g1, gimple g2)
 839 {
 840   return gimple_resx_region (g1) == gimple_resx_region (g2);
 841 }
 842
 843 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 844    For the beginning, the pass only supports equality for
 845    '__asm__ __volatile__ ("", "", "", "memory")'.  */
 846
 847 bool
 848 func_checker::compare_gimple_asm (gimple g1, gimple g2)
 849 {
 850   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
 851     return false;
 852
 853   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
 854     return false;
 855
 856   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
 857     return false;
 858
 859   /* We do not suppport goto ASM statement comparison.  */
 860   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
 861     return false;
 862
 863   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
 864     return false;
 865
 866   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
 867     return return_false_with_msg ("ASM strings are different");
 868
 869   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
 870     {
 871       tree input1 = gimple_asm_input_op (g1, i);
 872       tree input2 = gimple_asm_input_op (g2, i);
 873
 874       if (!compare_tree_list_operand (input1, input2))
 875         return return_false_with_msg ("ASM input is different");
 876     }
 877
 878   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
 879     {
 880       tree output1 = gimple_asm_output_op (g1, i);
 881       tree output2 = gimple_asm_output_op (g2, i);
 882
 883       if (!compare_tree_list_operand (output1, output2))
 884         return return_false_with_msg ("ASM output is different");
 885     }
 886
 887   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
 888     {
 889       tree clobber1 = gimple_asm_clobber_op (g1, i);
 890       tree clobber2 = gimple_asm_clobber_op (g2, i);
 891
 892       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
 893                             OEP_ONLY_CONST))
 894         return return_false_with_msg ("ASM clobber is different");
 895     }
 896
 897   return true;
 898 }
 899
 900 } // ipa_icf_gimple namespace