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