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_ALIGN (t1) != DECL_ALIGN (t2))
 579     return return_false_with_msg ("alignments are different");
 580
 581   if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
 582     return return_false_with_msg ("DECL_HARD_REGISTER are different");
 583
 584   if (DECL_HARD_REGISTER (t1)
 585       && DECL_ASSEMBLER_NAME (t1) != DECL_ASSEMBLER_NAME (t2))
 586     return return_false_with_msg ("HARD REGISTERS are different");
 587
 588   if (TREE_CODE (t1) == VAR_DECL && (DECL_EXTERNAL (t1) || TREE_STATIC (t1)))
 589     {
 590       symtab_node *n1 = symtab_node::get (t1);
 591       symtab_node *n2 = symtab_node::get (t2);
 592
 593       if (m_ignored_source_nodes != NULL && m_ignored_target_nodes != NULL)
 594         {
 595           ret = m_ignored_source_nodes->contains (n1)
 596                 && m_ignored_target_nodes->contains (n2);
 597
 598           if (ret)
 599             return true;
 600         }
 601     }
 602   ret = compare_decl (t1, t2);
 603
 604   return return_with_debug (ret);
 605 }
 606
 607
 608 /* Function visits all gimple labels and creates corresponding
 609    mapping between basic blocks and labels.  */
 610
 611 void
 612 func_checker::parse_labels (sem_bb *bb)
 613 {
 614   for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
 615        gsi_next (&gsi))
 616     {
 617       gimple stmt = gsi_stmt (gsi);
 618
 619       if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
 620         {
 621           tree t = gimple_label_label (label_stmt);
 622           gcc_assert (TREE_CODE (t) == LABEL_DECL);
 623
 624           m_label_bb_map.put (t, bb->bb->index);
 625         }
 626     }
 627 }
 628
 629 /* Basic block equivalence comparison function that returns true if
 630    basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
 631
 632    In general, a collection of equivalence dictionaries is built for types
 633    like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
 634    is utilized by every statement-by-statement comparison function.  */
 635
 636 bool
 637 func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
 638 {
 639   gimple_stmt_iterator gsi1, gsi2;
 640   gimple s1, s2;
 641
 642   gsi1 = gsi_start_bb_nondebug (bb1->bb);
 643   gsi2 = gsi_start_bb_nondebug (bb2->bb);
 644
 645   while (!gsi_end_p (gsi1))
 646     {
 647       if (gsi_end_p (gsi2))
 648         return return_false ();
 649
 650       s1 = gsi_stmt (gsi1);
 651       s2 = gsi_stmt (gsi2);
 652
 653       int eh1 = lookup_stmt_eh_lp_fn
 654                 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
 655       int eh2 = lookup_stmt_eh_lp_fn
 656                 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
 657
 658       if (eh1 != eh2)
 659         return return_false_with_msg ("EH regions are different");
 660
 661       if (gimple_code (s1) != gimple_code (s2))
 662         return return_false_with_msg ("gimple codes are different");
 663
 664       switch (gimple_code (s1))
 665         {
 666         case GIMPLE_CALL:
 667           if (!compare_gimple_call (as_a <gcall *> (s1),
 668                                     as_a <gcall *> (s2)))
 669             return return_different_stmts (s1, s2, "GIMPLE_CALL");
 670           break;
 671         case GIMPLE_ASSIGN:
 672           if (!compare_gimple_assign (s1, s2))
 673             return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
 674           break;
 675         case GIMPLE_COND:
 676           if (!compare_gimple_cond (s1, s2))
 677             return return_different_stmts (s1, s2, "GIMPLE_COND");
 678           break;
 679         case GIMPLE_SWITCH:
 680           if (!compare_gimple_switch (as_a <gswitch *> (s1),
 681                                       as_a <gswitch *> (s2)))
 682             return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
 683           break;
 684         case GIMPLE_DEBUG:
 685         case GIMPLE_EH_DISPATCH:
 686           break;
 687         case GIMPLE_RESX:
 688           if (!compare_gimple_resx (as_a <gresx *> (s1),
 689                                     as_a <gresx *> (s2)))
 690             return return_different_stmts (s1, s2, "GIMPLE_RESX");
 691           break;
 692         case GIMPLE_LABEL:
 693           if (!compare_gimple_label (as_a <glabel *> (s1),
 694                                      as_a <glabel *> (s2)))
 695             return return_different_stmts (s1, s2, "GIMPLE_LABEL");
 696           break;
 697         case GIMPLE_RETURN:
 698           if (!compare_gimple_return (as_a <greturn *> (s1),
 699                                       as_a <greturn *> (s2)))
 700             return return_different_stmts (s1, s2, "GIMPLE_RETURN");
 701           break;
 702         case GIMPLE_GOTO:
 703           if (!compare_gimple_goto (s1, s2))
 704             return return_different_stmts (s1, s2, "GIMPLE_GOTO");
 705           break;
 706         case GIMPLE_ASM:
 707           if (!compare_gimple_asm (as_a <gasm *> (s1),
 708                                    as_a <gasm *> (s2)))
 709             return return_different_stmts (s1, s2, "GIMPLE_ASM");
 710           break;
 711         case GIMPLE_PREDICT:
 712         case GIMPLE_NOP:
 713           return true;
 714         default:
 715           return return_false_with_msg ("Unknown GIMPLE code reached");
 716         }
 717
 718       gsi_next_nondebug (&gsi1);
 719       gsi_next_nondebug (&gsi2);
 720     }
 721
 722   if (!gsi_end_p (gsi2))
 723     return return_false ();
 724
 725   return true;
 726 }
 727
 728 /* Verifies for given GIMPLEs S1 and S2 that
 729    call statements are semantically equivalent.  */
 730
 731 bool
 732 func_checker::compare_gimple_call (gcall *s1, gcall *s2)
 733 {
 734   unsigned i;
 735   tree t1, t2;
 736
 737   if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
 738     return false;
 739
 740   t1 = gimple_call_fn (s1);
 741   t2 = gimple_call_fn (s2);
 742   if (!compare_operand (t1, t2))
 743     return return_false ();
 744
 745   /* Compare flags.  */
 746   if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
 747       || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
 748       || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
 749       || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
 750       || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
 751       || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
 752       || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2)
 753       || gimple_call_with_bounds_p (s1) != gimple_call_with_bounds_p (s2))
 754     return false;
 755
 756   if (gimple_call_internal_p (s1)
 757       && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
 758     return false;
 759
 760   tree fntype1 = gimple_call_fntype (s1);
 761   tree fntype2 = gimple_call_fntype (s2);
 762   if ((fntype1 && !fntype2)
 763       || (!fntype1 && fntype2)
 764       || (fntype1 && !types_compatible_p (fntype1, fntype2)))
 765     return return_false_with_msg ("call function types are not compatible");
 766
 767   tree chain1 = gimple_call_chain (s1);
 768   tree chain2 = gimple_call_chain (s2);
 769   if ((chain1 && !chain2)
 770       || (!chain1 && chain2)
 771       || !compare_operand (chain1, chain2))
 772     return return_false_with_msg ("static call chains are different");
 773
 774   /* Checking of argument.  */
 775   for (i = 0; i < gimple_call_num_args (s1); ++i)
 776     {
 777       t1 = gimple_call_arg (s1, i);
 778       t2 = gimple_call_arg (s2, i);
 779
 780       if (!compare_memory_operand (t1, t2))
 781         return return_false_with_msg ("memory operands are different");
 782     }
 783
 784   /* Return value checking.  */
 785   t1 = gimple_get_lhs (s1);
 786   t2 = gimple_get_lhs (s2);
 787
 788   return compare_memory_operand (t1, t2);
 789 }
 790
 791
 792 /* Verifies for given GIMPLEs S1 and S2 that
 793    assignment statements are semantically equivalent.  */
 794
 795 bool
 796 func_checker::compare_gimple_assign (gimple s1, gimple s2)
 797 {
 798   tree arg1, arg2;
 799   tree_code code1, code2;
 800   unsigned i;
 801
 802   code1 = gimple_expr_code (s1);
 803   code2 = gimple_expr_code (s2);
 804
 805   if (code1 != code2)
 806     return false;
 807
 808   code1 = gimple_assign_rhs_code (s1);
 809   code2 = gimple_assign_rhs_code (s2);
 810
 811   if (code1 != code2)
 812     return false;
 813
 814   for (i = 0; i < gimple_num_ops (s1); i++)
 815     {
 816       arg1 = gimple_op (s1, i);
 817       arg2 = gimple_op (s2, i);
 818
 819       if (!compare_memory_operand (arg1, arg2))
 820         return return_false_with_msg ("memory operands are different");
 821     }
 822
 823
 824   return true;
 825 }
 826
 827 /* Verifies for given GIMPLEs S1 and S2 that
 828    condition statements are semantically equivalent.  */
 829
 830 bool
 831 func_checker::compare_gimple_cond (gimple s1, gimple s2)
 832 {
 833   tree t1, t2;
 834   tree_code code1, code2;
 835
 836   code1 = gimple_expr_code (s1);
 837   code2 = gimple_expr_code (s2);
 838
 839   if (code1 != code2)
 840     return false;
 841
 842   t1 = gimple_cond_lhs (s1);
 843   t2 = gimple_cond_lhs (s2);
 844
 845   if (!compare_operand (t1, t2))
 846     return false;
 847
 848   t1 = gimple_cond_rhs (s1);
 849   t2 = gimple_cond_rhs (s2);
 850
 851   return compare_operand (t1, t2);
 852 }
 853
 854 /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2.  */
 855
 856 bool
 857 func_checker::compare_tree_ssa_label (tree t1, tree t2)
 858 {
 859   return compare_operand (t1, t2);
 860 }
 861
 862 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 863    label statements are semantically equivalent.  */
 864
 865 bool
 866 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 867 {
 868   if (m_ignore_labels)
 869     return true;
 870
 871   tree t1 = gimple_label_label (g1);
 872   tree t2 = gimple_label_label (g2);
 873
 874   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 875     return return_false_with_msg ("FORCED_LABEL");
 876
 877   /* As the pass build BB to label mapping, no further check is needed.  */
 878   return true;
 879 }
 880
 881 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 882    switch statements are semantically equivalent.  */
 883
 884 bool
 885 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
 886 {
 887   unsigned lsize1, lsize2, i;
 888
 889   lsize1 = gimple_switch_num_labels (g1);
 890   lsize2 = gimple_switch_num_labels (g2);
 891
 892   if (lsize1 != lsize2)
 893     return false;
 894
 895   tree t1 = gimple_switch_index (g1);
 896   tree t2 = gimple_switch_index (g2);
 897
 898   if (!compare_operand (t1, t2))
 899     return false;
 900
 901   for (i = 0; i < lsize1; i++)
 902     {
 903       tree label1 = gimple_switch_label (g1, i);
 904       tree label2 = gimple_switch_label (g2, i);
 905
 906       /* Label LOW and HIGH comparison.  */
 907       tree low1 = CASE_LOW (label1);
 908       tree low2 = CASE_LOW (label2);
 909
 910       if (!tree_int_cst_equal (low1, low2))
 911         return return_false_with_msg ("case low values are different");
 912
 913       tree high1 = CASE_HIGH (label1);
 914       tree high2 = CASE_HIGH (label2);
 915
 916       if (!tree_int_cst_equal (high1, high2))
 917         return return_false_with_msg ("case high values are different");
 918
 919       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 920           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 921         {
 922           label1 = CASE_LABEL (label1);
 923           label2 = CASE_LABEL (label2);
 924
 925           if (!compare_operand (label1, label2))
 926             return return_false_with_msg ("switch label_exprs are different");
 927         }
 928       else if (!tree_int_cst_equal (label1, label2))
 929         return return_false_with_msg ("switch labels are different");
 930     }
 931
 932   return true;
 933 }
 934
 935 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 936    return statements are semantically equivalent.  */
 937
 938 bool
 939 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
 940 {
 941   tree t1, t2;
 942
 943   t1 = gimple_return_retval (g1);
 944   t2 = gimple_return_retval (g2);
 945
 946   /* Void return type.  */
 947   if (t1 == NULL && t2 == NULL)
 948     return true;
 949   else
 950     return compare_operand (t1, t2);
 951 }
 952
 953 /* Verifies for given GIMPLEs S1 and S2 that
 954    goto statements are semantically equivalent.  */
 955
 956 bool
 957 func_checker::compare_gimple_goto (gimple g1, gimple g2)
 958 {
 959   tree dest1, dest2;
 960
 961   dest1 = gimple_goto_dest (g1);
 962   dest2 = gimple_goto_dest (g2);
 963
 964   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 965     return false;
 966
 967   return compare_operand (dest1, dest2);
 968 }
 969
 970 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 971    resx statements are semantically equivalent.  */
 972
 973 bool
 974 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
 975 {
 976   return gimple_resx_region (g1) == gimple_resx_region (g2);
 977 }
 978
 979 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 980    For the beginning, the pass only supports equality for
 981    '__asm__ __volatile__ ("", "", "", "memory")'.  */
 982
 983 bool
 984 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
 985 {
 986   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
 987     return false;
 988
 989   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
 990     return false;
 991
 992   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
 993     return false;
 994
 995   /* We do not suppport goto ASM statement comparison.  */
 996   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
 997     return false;
 998
 999   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
1000     return false;
1001
1002   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
1003     return return_false_with_msg ("ASM strings are different");
1004
1005   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
1006     {
1007       tree input1 = gimple_asm_input_op (g1, i);
1008       tree input2 = gimple_asm_input_op (g2, i);
1009
1010       if (!compare_tree_list_operand (input1, input2))
1011         return return_false_with_msg ("ASM input is different");
1012     }
1013
1014   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
1015     {
1016       tree output1 = gimple_asm_output_op (g1, i);
1017       tree output2 = gimple_asm_output_op (g2, i);
1018
1019       if (!compare_tree_list_operand (output1, output2))
1020         return return_false_with_msg ("ASM output is different");
1021     }
1022
1023   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
1024     {
1025       tree clobber1 = gimple_asm_clobber_op (g1, i);
1026       tree clobber2 = gimple_asm_clobber_op (g2, i);
1027
1028       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
1029                             OEP_ONLY_CONST))
1030         return return_false_with_msg ("ASM clobber is different");
1031     }
1032
1033   return true;
1034 }
1035
1036 } // ipa_icf_gimple namespace