gcc/ipa-icf-gimple.c

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