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