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