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       /* All function decls are in the symbol table and known to match
 316          before we start comparing bodies.  */
 317       return true;
 318     case VAR_DECL:
 319       return return_with_debug (compare_variable_decl (t1, t2));
 320     case FIELD_DECL:
 321       {
 322         tree offset1 = DECL_FIELD_OFFSET (t1);
 323         tree offset2 = DECL_FIELD_OFFSET (t2);
 324
 325         tree bit_offset1 = DECL_FIELD_BIT_OFFSET (t1);
 326         tree bit_offset2 = DECL_FIELD_BIT_OFFSET (t2);
 327
 328         ret = compare_operand (offset1, offset2)
 329               && compare_operand (bit_offset1, bit_offset2);
 330
 331         return return_with_debug (ret);
 332       }
 333     case LABEL_DECL:
 334       {
 335         int *bb1 = m_label_bb_map.get (t1);
 336         int *bb2 = m_label_bb_map.get (t2);
 337
 338         return return_with_debug (*bb1 == *bb2);
 339       }
 340     case PARM_DECL:
 341     case RESULT_DECL:
 342     case CONST_DECL:
 343       {
 344         ret = compare_decl (t1, t2);
 345         return return_with_debug (ret);
 346       }
 347     default:
 348       gcc_unreachable ();
 349     }
 350 }
 351
 352 /* Function responsible for comparison of various operands T1 and T2.
 353    If these components, from functions FUNC1 and FUNC2, are equal, true
 354    is returned.  */
 355
 356 bool
 357 func_checker::compare_operand (tree t1, tree t2)
 358 {
 359   tree x1, x2, y1, y2, z1, z2;
 360   bool ret;
 361
 362   if (!t1 && !t2)
 363     return true;
 364   else if (!t1 || !t2)
 365     return false;
 366
 367   tree tt1 = TREE_TYPE (t1);
 368   tree tt2 = TREE_TYPE (t2);
 369
 370   if (!func_checker::compatible_types_p (tt1, tt2))
 371     return false;
 372
 373   if (TREE_CODE (t1) != TREE_CODE (t2))
 374     return return_false ();
 375
 376   switch (TREE_CODE (t1))
 377     {
 378     case CONSTRUCTOR:
 379       {
 380         unsigned length1 = vec_safe_length (CONSTRUCTOR_ELTS (t1));
 381         unsigned length2 = vec_safe_length (CONSTRUCTOR_ELTS (t2));
 382
 383         if (length1 != length2)
 384           return return_false ();
 385
 386         for (unsigned i = 0; i < length1; i++)
 387           if (!compare_operand (CONSTRUCTOR_ELT (t1, i)->value,
 388                                 CONSTRUCTOR_ELT (t2, i)->value))
 389             return return_false();
 390
 391         return true;
 392       }
 393     case ARRAY_REF:
 394     case ARRAY_RANGE_REF:
 395       /* First argument is the array, second is the index.  */
 396       x1 = TREE_OPERAND (t1, 0);
 397       x2 = TREE_OPERAND (t2, 0);
 398       y1 = TREE_OPERAND (t1, 1);
 399       y2 = TREE_OPERAND (t2, 1);
 400
 401       if (!compare_operand (array_ref_low_bound (t1),
 402                             array_ref_low_bound (t2)))
 403         return return_false_with_msg ("");
 404       if (!compare_operand (array_ref_element_size (t1),
 405                             array_ref_element_size (t2)))
 406         return return_false_with_msg ("");
 407
 408       if (!compare_operand (x1, x2))
 409         return return_false_with_msg ("");
 410       return compare_operand (y1, y2);
 411     case MEM_REF:
 412       {
 413         x1 = TREE_OPERAND (t1, 0);
 414         x2 = TREE_OPERAND (t2, 0);
 415         y1 = TREE_OPERAND (t1, 1);
 416         y2 = TREE_OPERAND (t2, 1);
 417
 418         /* See if operand is an memory access (the test originate from
 419          gimple_load_p).
 420
 421         In this case the alias set of the function being replaced must
 422         be subset of the alias set of the other function.  At the moment
 423         we seek for equivalency classes, so simply require inclussion in
 424         both directions.  */
 425
 426         if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
 427           return return_false ();
 428
 429         if (!compare_operand (x1, x2))
 430           return return_false_with_msg ("");
 431
 432         /* Type of the offset on MEM_REF does not matter.  */
 433         return wi::to_offset  (y1) == wi::to_offset  (y2);
 434       }
 435     case COMPONENT_REF:
 436       {
 437         x1 = TREE_OPERAND (t1, 0);
 438         x2 = TREE_OPERAND (t2, 0);
 439         y1 = TREE_OPERAND (t1, 1);
 440         y2 = TREE_OPERAND (t2, 1);
 441
 442         ret = compare_operand (x1, x2)
 443               && compare_cst_or_decl (y1, y2);
 444
 445         return return_with_debug (ret);
 446       }
 447     /* Virtual table call.  */
 448     case OBJ_TYPE_REF:
 449       {
 450         if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2)))
 451           return return_false ();
 452         if (opt_for_fn (m_source_func_decl, flag_devirtualize)
 453             && virtual_method_call_p (t1))
 454           {
 455             if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t1))
 456                 != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t2)))
 457               return return_false_with_msg ("OBJ_TYPE_REF token mismatch");
 458             if (!types_same_for_odr (obj_type_ref_class (t1),
 459                                      obj_type_ref_class (t2)))
 460               return return_false_with_msg ("OBJ_TYPE_REF OTR type mismatch");
 461             if (!compare_ssa_name (OBJ_TYPE_REF_OBJECT (t1),
 462                                    OBJ_TYPE_REF_OBJECT (t2)))
 463               return return_false_with_msg ("OBJ_TYPE_REF object mismatch");
 464           }
 465
 466         return return_with_debug (true);
 467       }
 468     case IMAGPART_EXPR:
 469     case REALPART_EXPR:
 470     case ADDR_EXPR:
 471       {
 472         x1 = TREE_OPERAND (t1, 0);
 473         x2 = TREE_OPERAND (t2, 0);
 474
 475         ret = compare_operand (x1, x2);
 476         return return_with_debug (ret);
 477       }
 478     case BIT_FIELD_REF:
 479       {
 480         x1 = TREE_OPERAND (t1, 0);
 481         x2 = TREE_OPERAND (t2, 0);
 482         y1 = TREE_OPERAND (t1, 1);
 483         y2 = TREE_OPERAND (t2, 1);
 484         z1 = TREE_OPERAND (t1, 2);
 485         z2 = TREE_OPERAND (t2, 2);
 486
 487         ret = compare_operand (x1, x2)
 488               && compare_cst_or_decl (y1, y2)
 489               && compare_cst_or_decl (z1, z2);
 490
 491         return return_with_debug (ret);
 492       }
 493     case SSA_NAME:
 494         return compare_ssa_name (t1, t2);
 495     case INTEGER_CST:
 496     case COMPLEX_CST:
 497     case VECTOR_CST:
 498     case STRING_CST:
 499     case REAL_CST:
 500     case FUNCTION_DECL:
 501     case VAR_DECL:
 502     case FIELD_DECL:
 503     case LABEL_DECL:
 504     case PARM_DECL:
 505     case RESULT_DECL:
 506     case CONST_DECL:
 507       return compare_cst_or_decl (t1, t2);
 508     default:
 509       return return_false_with_msg ("Unknown TREE code reached");
 510     }
 511 }
 512
 513 /* Compares two tree list operands T1 and T2 and returns true if these
 514    two trees are semantically equivalent.  */
 515
 516 bool
 517 func_checker::compare_tree_list_operand (tree t1, tree t2)
 518 {
 519   gcc_assert (TREE_CODE (t1) == TREE_LIST);
 520   gcc_assert (TREE_CODE (t2) == TREE_LIST);
 521
 522   for (; t1; t1 = TREE_CHAIN (t1))
 523     {
 524       if (!t2)
 525         return false;
 526
 527       if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2)))
 528         return return_false ();
 529
 530       t2 = TREE_CHAIN (t2);
 531     }
 532
 533   if (t2)
 534     return return_false ();
 535
 536   return true;
 537 }
 538
 539 /* Verifies that trees T1 and T2 do correspond.  */
 540
 541 bool
 542 func_checker::compare_variable_decl (tree t1, tree t2)
 543 {
 544   bool ret = false;
 545
 546   if (t1 == t2)
 547     return true;
 548
 549   if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
 550     return return_false_with_msg ("alignments are different");
 551
 552   if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
 553     return return_false_with_msg ("DECL_HARD_REGISTER are different");
 554
 555   if (DECL_HARD_REGISTER (t1)
 556       && DECL_ASSEMBLER_NAME (t1) != DECL_ASSEMBLER_NAME (t2))
 557     return return_false_with_msg ("HARD REGISTERS are different");
 558
 559   /* Symbol table variables are known to match before we start comparing
 560      bodies.  */
 561   if (decl_in_symtab_p (t1))
 562     return decl_in_symtab_p (t2);
 563   ret = compare_decl (t1, t2);
 564
 565   return return_with_debug (ret);
 566 }
 567
 568
 569 /* Function visits all gimple labels and creates corresponding
 570    mapping between basic blocks and labels.  */
 571
 572 void
 573 func_checker::parse_labels (sem_bb *bb)
 574 {
 575   for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
 576        gsi_next (&gsi))
 577     {
 578       gimple stmt = gsi_stmt (gsi);
 579
 580       if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
 581         {
 582           tree t = gimple_label_label (label_stmt);
 583           gcc_assert (TREE_CODE (t) == LABEL_DECL);
 584
 585           m_label_bb_map.put (t, bb->bb->index);
 586         }
 587     }
 588 }
 589
 590 /* Basic block equivalence comparison function that returns true if
 591    basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
 592
 593    In general, a collection of equivalence dictionaries is built for types
 594    like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
 595    is utilized by every statement-by-statement comparison function.  */
 596
 597 bool
 598 func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
 599 {
 600   gimple_stmt_iterator gsi1, gsi2;
 601   gimple s1, s2;
 602
 603   gsi1 = gsi_start_bb_nondebug (bb1->bb);
 604   gsi2 = gsi_start_bb_nondebug (bb2->bb);
 605
 606   while (!gsi_end_p (gsi1))
 607     {
 608       if (gsi_end_p (gsi2))
 609         return return_false ();
 610
 611       s1 = gsi_stmt (gsi1);
 612       s2 = gsi_stmt (gsi2);
 613
 614       int eh1 = lookup_stmt_eh_lp_fn
 615                 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
 616       int eh2 = lookup_stmt_eh_lp_fn
 617                 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
 618
 619       if (eh1 != eh2)
 620         return return_false_with_msg ("EH regions are different");
 621
 622       if (gimple_code (s1) != gimple_code (s2))
 623         return return_false_with_msg ("gimple codes are different");
 624
 625       switch (gimple_code (s1))
 626         {
 627         case GIMPLE_CALL:
 628           if (!compare_gimple_call (as_a <gcall *> (s1),
 629                                     as_a <gcall *> (s2)))
 630             return return_different_stmts (s1, s2, "GIMPLE_CALL");
 631           break;
 632         case GIMPLE_ASSIGN:
 633           if (!compare_gimple_assign (s1, s2))
 634             return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
 635           break;
 636         case GIMPLE_COND:
 637           if (!compare_gimple_cond (s1, s2))
 638             return return_different_stmts (s1, s2, "GIMPLE_COND");
 639           break;
 640         case GIMPLE_SWITCH:
 641           if (!compare_gimple_switch (as_a <gswitch *> (s1),
 642                                       as_a <gswitch *> (s2)))
 643             return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
 644           break;
 645         case GIMPLE_DEBUG:
 646         case GIMPLE_EH_DISPATCH:
 647           break;
 648         case GIMPLE_RESX:
 649           if (!compare_gimple_resx (as_a <gresx *> (s1),
 650                                     as_a <gresx *> (s2)))
 651             return return_different_stmts (s1, s2, "GIMPLE_RESX");
 652           break;
 653         case GIMPLE_LABEL:
 654           if (!compare_gimple_label (as_a <glabel *> (s1),
 655                                      as_a <glabel *> (s2)))
 656             return return_different_stmts (s1, s2, "GIMPLE_LABEL");
 657           break;
 658         case GIMPLE_RETURN:
 659           if (!compare_gimple_return (as_a <greturn *> (s1),
 660                                       as_a <greturn *> (s2)))
 661             return return_different_stmts (s1, s2, "GIMPLE_RETURN");
 662           break;
 663         case GIMPLE_GOTO:
 664           if (!compare_gimple_goto (s1, s2))
 665             return return_different_stmts (s1, s2, "GIMPLE_GOTO");
 666           break;
 667         case GIMPLE_ASM:
 668           if (!compare_gimple_asm (as_a <gasm *> (s1),
 669                                    as_a <gasm *> (s2)))
 670             return return_different_stmts (s1, s2, "GIMPLE_ASM");
 671           break;
 672         case GIMPLE_PREDICT:
 673         case GIMPLE_NOP:
 674           return true;
 675         default:
 676           return return_false_with_msg ("Unknown GIMPLE code reached");
 677         }
 678
 679       gsi_next_nondebug (&gsi1);
 680       gsi_next_nondebug (&gsi2);
 681     }
 682
 683   if (!gsi_end_p (gsi2))
 684     return return_false ();
 685
 686   return true;
 687 }
 688
 689 /* Verifies for given GIMPLEs S1 and S2 that
 690    call statements are semantically equivalent.  */
 691
 692 bool
 693 func_checker::compare_gimple_call (gcall *s1, gcall *s2)
 694 {
 695   unsigned i;
 696   tree t1, t2;
 697
 698   if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
 699     return false;
 700
 701   t1 = gimple_call_fn (s1);
 702   t2 = gimple_call_fn (s2);
 703   if (!compare_operand (t1, t2))
 704     return return_false ();
 705
 706   /* Compare flags.  */
 707   if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
 708       || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
 709       || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
 710       || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
 711       || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
 712       || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
 713       || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2)
 714       || gimple_call_with_bounds_p (s1) != gimple_call_with_bounds_p (s2))
 715     return false;
 716
 717   if (gimple_call_internal_p (s1)
 718       && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
 719     return false;
 720
 721   tree fntype1 = gimple_call_fntype (s1);
 722   tree fntype2 = gimple_call_fntype (s2);
 723   if ((fntype1 && !fntype2)
 724       || (!fntype1 && fntype2)
 725       || (fntype1 && !types_compatible_p (fntype1, fntype2)))
 726     return return_false_with_msg ("call function types are not compatible");
 727
 728   tree chain1 = gimple_call_chain (s1);
 729   tree chain2 = gimple_call_chain (s2);
 730   if ((chain1 && !chain2)
 731       || (!chain1 && chain2)
 732       || !compare_operand (chain1, chain2))
 733     return return_false_with_msg ("static call chains are different");
 734
 735   /* Checking of argument.  */
 736   for (i = 0; i < gimple_call_num_args (s1); ++i)
 737     {
 738       t1 = gimple_call_arg (s1, i);
 739       t2 = gimple_call_arg (s2, i);
 740
 741       if (!compare_memory_operand (t1, t2))
 742         return return_false_with_msg ("memory operands are different");
 743     }
 744
 745   /* Return value checking.  */
 746   t1 = gimple_get_lhs (s1);
 747   t2 = gimple_get_lhs (s2);
 748
 749   return compare_memory_operand (t1, t2);
 750 }
 751
 752
 753 /* Verifies for given GIMPLEs S1 and S2 that
 754    assignment statements are semantically equivalent.  */
 755
 756 bool
 757 func_checker::compare_gimple_assign (gimple s1, gimple s2)
 758 {
 759   tree arg1, arg2;
 760   tree_code code1, code2;
 761   unsigned i;
 762
 763   code1 = gimple_expr_code (s1);
 764   code2 = gimple_expr_code (s2);
 765
 766   if (code1 != code2)
 767     return false;
 768
 769   code1 = gimple_assign_rhs_code (s1);
 770   code2 = gimple_assign_rhs_code (s2);
 771
 772   if (code1 != code2)
 773     return false;
 774
 775   for (i = 0; i < gimple_num_ops (s1); i++)
 776     {
 777       arg1 = gimple_op (s1, i);
 778       arg2 = gimple_op (s2, i);
 779
 780       if (!compare_memory_operand (arg1, arg2))
 781         return return_false_with_msg ("memory operands are different");
 782     }
 783
 784
 785   return true;
 786 }
 787
 788 /* Verifies for given GIMPLEs S1 and S2 that
 789    condition statements are semantically equivalent.  */
 790
 791 bool
 792 func_checker::compare_gimple_cond (gimple s1, gimple s2)
 793 {
 794   tree t1, t2;
 795   tree_code code1, code2;
 796
 797   code1 = gimple_expr_code (s1);
 798   code2 = gimple_expr_code (s2);
 799
 800   if (code1 != code2)
 801     return false;
 802
 803   t1 = gimple_cond_lhs (s1);
 804   t2 = gimple_cond_lhs (s2);
 805
 806   if (!compare_operand (t1, t2))
 807     return false;
 808
 809   t1 = gimple_cond_rhs (s1);
 810   t2 = gimple_cond_rhs (s2);
 811
 812   return compare_operand (t1, t2);
 813 }
 814
 815 /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2.  */
 816
 817 bool
 818 func_checker::compare_tree_ssa_label (tree t1, tree t2)
 819 {
 820   return compare_operand (t1, t2);
 821 }
 822
 823 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 824    label statements are semantically equivalent.  */
 825
 826 bool
 827 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 828 {
 829   if (m_ignore_labels)
 830     return true;
 831
 832   tree t1 = gimple_label_label (g1);
 833   tree t2 = gimple_label_label (g2);
 834
 835   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 836     return return_false_with_msg ("FORCED_LABEL");
 837
 838   /* As the pass build BB to label mapping, no further check is needed.  */
 839   return true;
 840 }
 841
 842 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 843    switch statements are semantically equivalent.  */
 844
 845 bool
 846 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
 847 {
 848   unsigned lsize1, lsize2, i;
 849
 850   lsize1 = gimple_switch_num_labels (g1);
 851   lsize2 = gimple_switch_num_labels (g2);
 852
 853   if (lsize1 != lsize2)
 854     return false;
 855
 856   tree t1 = gimple_switch_index (g1);
 857   tree t2 = gimple_switch_index (g2);
 858
 859   if (!compare_operand (t1, t2))
 860     return false;
 861
 862   for (i = 0; i < lsize1; i++)
 863     {
 864       tree label1 = gimple_switch_label (g1, i);
 865       tree label2 = gimple_switch_label (g2, i);
 866
 867       /* Label LOW and HIGH comparison.  */
 868       tree low1 = CASE_LOW (label1);
 869       tree low2 = CASE_LOW (label2);
 870
 871       if (!tree_int_cst_equal (low1, low2))
 872         return return_false_with_msg ("case low values are different");
 873
 874       tree high1 = CASE_HIGH (label1);
 875       tree high2 = CASE_HIGH (label2);
 876
 877       if (!tree_int_cst_equal (high1, high2))
 878         return return_false_with_msg ("case high values are different");
 879
 880       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 881           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 882         {
 883           label1 = CASE_LABEL (label1);
 884           label2 = CASE_LABEL (label2);
 885
 886           if (!compare_operand (label1, label2))
 887             return return_false_with_msg ("switch label_exprs are different");
 888         }
 889       else if (!tree_int_cst_equal (label1, label2))
 890         return return_false_with_msg ("switch labels are different");
 891     }
 892
 893   return true;
 894 }
 895
 896 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 897    return statements are semantically equivalent.  */
 898
 899 bool
 900 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
 901 {
 902   tree t1, t2;
 903
 904   t1 = gimple_return_retval (g1);
 905   t2 = gimple_return_retval (g2);
 906
 907   /* Void return type.  */
 908   if (t1 == NULL && t2 == NULL)
 909     return true;
 910   else
 911     return compare_operand (t1, t2);
 912 }
 913
 914 /* Verifies for given GIMPLEs S1 and S2 that
 915    goto statements are semantically equivalent.  */
 916
 917 bool
 918 func_checker::compare_gimple_goto (gimple g1, gimple g2)
 919 {
 920   tree dest1, dest2;
 921
 922   dest1 = gimple_goto_dest (g1);
 923   dest2 = gimple_goto_dest (g2);
 924
 925   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 926     return false;
 927
 928   return compare_operand (dest1, dest2);
 929 }
 930
 931 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 932    resx statements are semantically equivalent.  */
 933
 934 bool
 935 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
 936 {
 937   return gimple_resx_region (g1) == gimple_resx_region (g2);
 938 }
 939
 940 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
 941    For the beginning, the pass only supports equality for
 942    '__asm__ __volatile__ ("", "", "", "memory")'.  */
 943
 944 bool
 945 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
 946 {
 947   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
 948     return false;
 949
 950   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
 951     return false;
 952
 953   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
 954     return false;
 955
 956   /* We do not suppport goto ASM statement comparison.  */
 957   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
 958     return false;
 959
 960   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
 961     return false;
 962
 963   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
 964     return return_false_with_msg ("ASM strings are different");
 965
 966   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
 967     {
 968       tree input1 = gimple_asm_input_op (g1, i);
 969       tree input2 = gimple_asm_input_op (g2, i);
 970
 971       if (!compare_tree_list_operand (input1, input2))
 972         return return_false_with_msg ("ASM input is different");
 973     }
 974
 975   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
 976     {
 977       tree output1 = gimple_asm_output_op (g1, i);
 978       tree output2 = gimple_asm_output_op (g2, i);
 979
 980       if (!compare_tree_list_operand (output1, output2))
 981         return return_false_with_msg ("ASM output is different");
 982     }
 983
 984   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
 985     {
 986       tree clobber1 = gimple_asm_clobber_op (g1, i);
 987       tree clobber2 = gimple_asm_clobber_op (g2, i);
 988
 989       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
 990                             OEP_ONLY_CONST))
 991         return return_false_with_msg ("ASM clobber is different");
 992     }
 993
 994   return true;
 995 }
 996
 997 } // ipa_icf_gimple namespace