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 IMAGPART_EXPR:
 452     case REALPART_EXPR:
 453     case ADDR_EXPR:
 454       {
 455         x1 = TREE_OPERAND (t1, 0);
 456         x2 = TREE_OPERAND (t2, 0);
 457
 458         ret = compare_operand (x1, x2);
 459         return return_with_debug (ret);
 460       }
 461     case BIT_FIELD_REF:
 462       {
 463         x1 = TREE_OPERAND (t1, 0);
 464         x2 = TREE_OPERAND (t2, 0);
 465         y1 = TREE_OPERAND (t1, 1);
 466         y2 = TREE_OPERAND (t2, 1);
 467         z1 = TREE_OPERAND (t1, 2);
 468         z2 = TREE_OPERAND (t2, 2);
 469
 470         ret = compare_operand (x1, x2)
 471               && compare_cst_or_decl (y1, y2)
 472               && compare_cst_or_decl (z1, z2);
 473
 474         return return_with_debug (ret);
 475       }
 476     case SSA_NAME:
 477         return compare_ssa_name (t1, t2);
 478     case INTEGER_CST:
 479     case COMPLEX_CST:
 480     case VECTOR_CST:
 481     case STRING_CST:
 482     case REAL_CST:
 483     case FUNCTION_DECL:
 484     case VAR_DECL:
 485     case FIELD_DECL:
 486     case LABEL_DECL:
 487     case PARM_DECL:
 488     case RESULT_DECL:
 489     case CONST_DECL:
 490       return compare_cst_or_decl (t1, t2);
 491     default:
 492       return return_false_with_msg ("Unknown TREE code reached");
 493     }
 494 }
 495
 496 /* Compares two tree list operands T1 and T2 and returns true if these
 497    two trees are semantically equivalent.  */
 498
 499 bool
 500 func_checker::compare_tree_list_operand (tree t1, tree t2)
 501 {
 502   gcc_assert (TREE_CODE (t1) == TREE_LIST);
 503   gcc_assert (TREE_CODE (t2) == TREE_LIST);
 504
 505   for (; t1; t1 = TREE_CHAIN (t1))
 506     {
 507       if (!t2)
 508         return false;
 509
 510       if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2)))
 511         return return_false ();
 512
 513       t2 = TREE_CHAIN (t2);
 514     }
 515
 516   if (t2)
 517     return return_false ();
 518
 519   return true;
 520 }
 521
 522 /* Verifies that trees T1 and T2, representing function declarations
 523    are equivalent from perspective of ICF.  */
 524
 525 bool
 526 func_checker::compare_function_decl (tree t1, tree t2)
 527 {
 528   bool ret = false;
 529
 530   if (t1 == t2)
 531     return true;
 532
 533   symtab_node *n1 = symtab_node::get (t1);
 534   symtab_node *n2 = symtab_node::get (t2);
 535
 536   if (m_ignored_source_nodes != NULL && m_ignored_target_nodes != NULL)
 537     {
 538       ret = m_ignored_source_nodes->contains (n1)
 539             && m_ignored_target_nodes->contains (n2);
 540
 541       if (ret)
 542         return true;
 543     }
 544
 545   /* If function decl is WEAKREF, we compare targets.  */
 546   cgraph_node *f1 = cgraph_node::get (t1);
 547   cgraph_node *f2 = cgraph_node::get (t2);
 548
 549   if(f1 && f2 && f1->weakref && f2->weakref)
 550     ret = f1->alias_target == f2->alias_target;
 551
 552   return ret;
 553 }
 554
 555 /* Verifies that trees T1 and T2 do correspond.  */
 556
 557 bool
 558 func_checker::compare_variable_decl (tree t1, tree t2)
 559 {
 560   bool ret = false;
 561
 562   if (t1 == t2)
 563     return true;
 564
 565   if (TREE_CODE (t1) == VAR_DECL && (DECL_EXTERNAL (t1) || TREE_STATIC (t1)))
 566     {
 567       symtab_node *n1 = symtab_node::get (t1);
 568       symtab_node *n2 = symtab_node::get (t2);
 569
 570       if (m_ignored_source_nodes != NULL && m_ignored_target_nodes != NULL)
 571         {
 572           ret = m_ignored_source_nodes->contains (n1)
 573                 && m_ignored_target_nodes->contains (n2);
 574
 575           if (ret)
 576             return true;
 577         }
 578     }
 579   ret = compare_decl (t1, t2);
 580
 581   return return_with_debug (ret);
 582 }
 583
 584
 585 /* Function visits all gimple labels and creates corresponding
 586    mapping between basic blocks and labels.  */
 587
 588 void
 589 func_checker::parse_labels (sem_bb *bb)
 590 {
 591   for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
 592        gsi_next (&gsi))
 593     {
 594       gimple stmt = gsi_stmt (gsi);
 595
 596       if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
 597         {
 598           tree t = gimple_label_label (label_stmt);
 599           gcc_assert (TREE_CODE (t) == LABEL_DECL);
 600
 601           m_label_bb_map.put (t, bb->bb->index);
 602         }
 603     }
 604 }
 605
 606 /* Basic block equivalence comparison function that returns true if
 607    basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
 608
 609    In general, a collection of equivalence dictionaries is built for types
 610    like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
 611    is utilized by every statement-by-statement comparison function.  */
 612
 613 bool
 614 func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
 615 {
 616   gimple_stmt_iterator gsi1, gsi2;
 617   gimple s1, s2;
 618
 619   gsi1 = gsi_start_bb_nondebug (bb1->bb);
 620   gsi2 = gsi_start_bb_nondebug (bb2->bb);
 621
 622   while (!gsi_end_p (gsi1))
 623     {
 624       if (gsi_end_p (gsi2))
 625         return return_false ();
 626
 627       s1 = gsi_stmt (gsi1);
 628       s2 = gsi_stmt (gsi2);
 629
 630       int eh1 = lookup_stmt_eh_lp_fn
 631                 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
 632       int eh2 = lookup_stmt_eh_lp_fn
 633                 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
 634
 635       if (eh1 != eh2)
 636         return return_false_with_msg ("EH regions are different");
 637
 638       if (gimple_code (s1) != gimple_code (s2))
 639         return return_false_with_msg ("gimple codes are different");
 640
 641       switch (gimple_code (s1))
 642         {
 643         case GIMPLE_CALL:
 644           if (!compare_gimple_call (as_a <gcall *> (s1),
 645                                     as_a <gcall *> (s2)))
 646             return return_different_stmts (s1, s2, "GIMPLE_CALL");
 647           break;
 648         case GIMPLE_ASSIGN:
 649           if (!compare_gimple_assign (s1, s2))
 650             return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
 651           break;
 652         case GIMPLE_COND:
 653           if (!compare_gimple_cond (s1, s2))
 654             return return_different_stmts (s1, s2, "GIMPLE_COND");
 655           break;
 656         case GIMPLE_SWITCH:
 657           if (!compare_gimple_switch (as_a <gswitch *> (s1),
 658                                       as_a <gswitch *> (s2)))
 659             return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
 660           break;
 661         case GIMPLE_DEBUG:
 662         case GIMPLE_EH_DISPATCH:
 663           break;
 664         case GIMPLE_RESX:
 665           if (!compare_gimple_resx (as_a <gresx *> (s1),
 666                                     as_a <gresx *> (s2)))
 667             return return_different_stmts (s1, s2, "GIMPLE_RESX");
 668           break;
 669         case GIMPLE_LABEL:
 670           if (!compare_gimple_label (as_a <glabel *> (s1),
 671                                      as_a <glabel *> (s2)))
 672             return return_different_stmts (s1, s2, "GIMPLE_LABEL");
 673           break;
 674         case GIMPLE_RETURN:
 675           if (!compare_gimple_return (as_a <greturn *> (s1),
 676                                       as_a <greturn *> (s2)))
 677             return return_different_stmts (s1, s2, "GIMPLE_RETURN");
 678           break;
 679         case GIMPLE_GOTO:
 680           if (!compare_gimple_goto (s1, s2))
 681             return return_different_stmts (s1, s2, "GIMPLE_GOTO");
 682           break;
 683         case GIMPLE_ASM:
 684           if (!compare_gimple_asm (as_a <gasm *> (s1),
 685                                    as_a <gasm *> (s2)))
 686             return return_different_stmts (s1, s2, "GIMPLE_ASM");
 687           break;
 688         case GIMPLE_PREDICT:
 689         case GIMPLE_NOP:
 690           return true;
 691         default:
 692           return return_false_with_msg ("Unknown GIMPLE code reached");
 693         }
 694
 695       gsi_next_nondebug (&gsi1);
 696       gsi_next_nondebug (&gsi2);
 697     }
 698
 699   if (!gsi_end_p (gsi2))
 700     return return_false ();
 701
 702   return true;
 703 }
 704
 705 /* Verifies for given GIMPLEs S1 and S2 that
 706    call statements are semantically equivalent.  */
 707
 708 bool
 709 func_checker::compare_gimple_call (gcall *s1, gcall *s2)
 710 {
 711   unsigned i;
 712   tree t1, t2;
 713
 714   if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
 715     return false;
 716
 717   t1 = gimple_call_fn (s1);
 718   t2 = gimple_call_fn (s2);
 719   if (!compare_operand (t1, t2))
 720     return return_false ();
 721
 722   /* Compare flags.  */
 723   if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
 724       || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
 725       || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
 726       || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
 727       || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
 728       || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
 729       || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2)
 730       || gimple_call_with_bounds_p (s1) != gimple_call_with_bounds_p (s2))
 731     return false;
 732
 733   if (gimple_call_internal_p (s1)
 734       && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
 735     return false;
 736
 737   tree fntype1 = gimple_call_fntype (s1);
 738   tree fntype2 = gimple_call_fntype (s2);
 739   if ((fntype1 && !fntype2)
 740       || (!fntype1 && fntype2)
 741       || (fntype1 && !types_compatible_p (fntype1, fntype2)))
 742     return return_false_with_msg ("call function types are not compatible");
 743
 744   tree chain1 = gimple_call_chain (s1);
 745   tree chain2 = gimple_call_chain (s2);
 746   if ((chain1 && !chain2)
 747       || (!chain1 && chain2)
 748       || !compare_operand (chain1, chain2))
 749     return return_false_with_msg ("static call chains are different");
 750
 751   /* Checking of argument.  */
 752   for (i = 0; i < gimple_call_num_args (s1); ++i)
 753     {
 754       t1 = gimple_call_arg (s1, i);
 755       t2 = gimple_call_arg (s2, i);
 756
 757       if (!compare_memory_operand (t1, t2))
 758         return return_false_with_msg ("memory operands are different");
 759     }
 760
 761   /* Return value checking.  */
 762   t1 = gimple_get_lhs (s1);
 763   t2 = gimple_get_lhs (s2);
 764
 765   return compare_memory_operand (t1, t2);
 766 }
 767
 768
 769 /* Verifies for given GIMPLEs S1 and S2 that
 770    assignment statements are semantically equivalent.  */
 771
 772 bool
 773 func_checker::compare_gimple_assign (gimple s1, gimple s2)
 774 {
 775   tree arg1, arg2;
 776   tree_code code1, code2;
 777   unsigned i;
 778
 779   code1 = gimple_expr_code (s1);
 780   code2 = gimple_expr_code (s2);
 781
 782   if (code1 != code2)
 783     return false;
 784
 785   code1 = gimple_assign_rhs_code (s1);
 786   code2 = gimple_assign_rhs_code (s2);
 787
 788   if (code1 != code2)
 789     return false;
 790
 791   for (i = 0; i < gimple_num_ops (s1); i++)
 792     {
 793       arg1 = gimple_op (s1, i);
 794       arg2 = gimple_op (s2, i);
 795
 796       if (!compare_memory_operand (arg1, arg2))
 797         return return_false_with_msg ("memory operands are different");
 798     }
 799
 800
 801   return true;
 802 }
 803
 804 /* Verifies for given GIMPLEs S1 and S2 that
 805    condition statements are semantically equivalent.  */
 806
 807 bool
 808 func_checker::compare_gimple_cond (gimple s1, gimple s2)
 809 {
 810   tree t1, t2;
 811   tree_code code1, code2;
 812
 813   code1 = gimple_expr_code (s1);
 814   code2 = gimple_expr_code (s2);
 815
 816   if (code1 != code2)
 817     return false;
 818
 819   t1 = gimple_cond_lhs (s1);
 820   t2 = gimple_cond_lhs (s2);
 821
 822   if (!compare_operand (t1, t2))
 823     return false;
 824
 825   t1 = gimple_cond_rhs (s1);
 826   t2 = gimple_cond_rhs (s2);
 827
 828   return compare_operand (t1, t2);
 829 }
 830
 831 /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2.  */
 832
 833 bool
 834 func_checker::compare_tree_ssa_label (tree t1, tree t2)
 835 {
 836   return compare_operand (t1, t2);
 837 }
 838
 839 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 840    label statements are semantically equivalent.  */
 841
 842 bool
 843 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 844 {
 845   if (m_ignore_labels)
 846     return true;
 847
 848   tree t1 = gimple_label_label (g1);
 849   tree t2 = gimple_label_label (g2);
 850
 851   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 852     return return_false_with_msg ("FORCED_LABEL");
 853
 854   /* As the pass build BB to label mapping, no further check is needed.  */
 855   return true;
 856 }
 857
 858 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 859    switch statements are semantically equivalent.  */
 860
 861 bool
 862 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
 863 {
 864   unsigned lsize1, lsize2, i;
 865
 866   lsize1 = gimple_switch_num_labels (g1);
 867   lsize2 = gimple_switch_num_labels (g2);
 868
 869   if (lsize1 != lsize2)
 870     return false;
 871
 872   tree t1 = gimple_switch_index (g1);
 873   tree t2 = gimple_switch_index (g2);
 874
 875   if (!compare_operand (t1, t2))
 876     return false;
 877
 878   for (i = 0; i < lsize1; i++)
 879     {
 880       tree label1 = gimple_switch_label (g1, i);
 881       tree label2 = gimple_switch_label (g2, i);
 882
 883       /* Label LOW and HIGH comparison.  */
 884       tree low1 = CASE_LOW (label1);
 885       tree low2 = CASE_LOW (label2);
 886
 887       if (!tree_int_cst_equal (low1, low2))
 888         return return_false_with_msg ("case low values are different");
 889
 890       tree high1 = CASE_HIGH (label1);
 891       tree high2 = CASE_HIGH (label2);
 892
 893       if (!tree_int_cst_equal (high1, high2))
 894         return return_false_with_msg ("case high values are different");
 895
 896       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 897           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 898         {
 899           label1 = CASE_LABEL (label1);
 900           label2 = CASE_LABEL (label2);
 901
 902           if (!compare_operand (label1, label2))
 903             return return_false_with_msg ("switch label_exprs are different");
 904         }
 905       else if (!tree_int_cst_equal (label1, label2))
 906         return return_false_with_msg ("switch labels are different");
 907     }
 908
 909   return true;
 910 }
 911
 912 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 913    return statements are semantically equivalent.  */
 914
 915 bool
 916 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
 917 {
 918   tree t1, t2;
 919
 920   t1 = gimple_return_retval (g1);
 921   t2 = gimple_return_retval (g2);
 922
 923   /* Void return type.  */
 924   if (t1 == NULL && t2 == NULL)
 925     return true;
 926   else
 927     return compare_operand (t1, t2);
 928 }
 929
 930 /* Verifies for given GIMPLEs S1 and S2 that
 931    goto statements are semantically equivalent.  */
 932
 933 bool
 934 func_checker::compare_gimple_goto (gimple g1, gimple g2)
 935 {
 936   tree dest1, dest2;
 937
 938   dest1 = gimple_goto_dest (g1);
 939   dest2 = gimple_goto_dest (g2);
 940
 941   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 942     return false;
 943
 944   return compare_operand (dest1, dest2);
 945 }
 946
 947 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 948    resx statements are semantically equivalent.  */
 949
 950 bool
 951 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
 952 {
 953   return gimple_resx_region (g1) == gimple_resx_region (g2);
 954 }
 955
 956 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 957    For the beginning, the pass only supports equality for
 958    '__asm__ __volatile__ ("", "", "", "memory")'.  */
 959
 960 bool
 961 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
 962 {
 963   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
 964     return false;
 965
 966   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
 967     return false;
 968
 969   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
 970     return false;
 971
 972   /* We do not suppport goto ASM statement comparison.  */
 973   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
 974     return false;
 975
 976   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
 977     return false;
 978
 979   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
 980     return return_false_with_msg ("ASM strings are different");
 981
 982   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
 983     {
 984       tree input1 = gimple_asm_input_op (g1, i);
 985       tree input2 = gimple_asm_input_op (g2, i);
 986
 987       if (!compare_tree_list_operand (input1, input2))
 988         return return_false_with_msg ("ASM input is different");
 989     }
 990
 991   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
 992     {
 993       tree output1 = gimple_asm_output_op (g1, i);
 994       tree output2 = gimple_asm_output_op (g2, i);
 995
 996       if (!compare_tree_list_operand (output1, output2))
 997         return return_false_with_msg ("ASM output is different");
 998     }
 999
1000   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
1001     {
1002       tree clobber1 = gimple_asm_clobber_op (g1, i);
1003       tree clobber2 = gimple_asm_clobber_op (g2, i);
1004
1005       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
1006                             OEP_ONLY_CONST))
1007         return return_false_with_msg ("ASM clobber is different");
1008     }
1009
1010   return true;
1011 }
1012
1013 } // ipa_icf_gimple namespace