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