contrib/gcc-5.0/gcc/ipa-icf-gimple.c

   1 /* Interprocedural Identical Code Folding pass
   2    Copyright (C) 2014-2015 Free Software Foundation, Inc.
   3
   4    Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "hash-set.h"
  26 #include "machmode.h"
  27 #include "vec.h"
  28 #include "double-int.h"
  29 #include "input.h"
  30 #include "alias.h"
  31 #include "symtab.h"
  32 #include "options.h"
  33 #include "wide-int.h"
  34 #include "inchash.h"
  35 #include "tree.h"
  36 #include "fold-const.h"
  37 #include "predict.h"
  38 #include "tm.h"
  39 #include "hard-reg-set.h"
  40 #include "function.h"
  41 #include "basic-block.h"
  42 #include "tree-ssa-alias.h"
  43 #include "internal-fn.h"
  44 #include "gimple-expr.h"
  45 #include "is-a.h"
  46 #include "gimple.h"
  47 #include "hashtab.h"
  48 #include "rtl.h"
  49 #include "flags.h"
  50 #include "statistics.h"
  51 #include "real.h"
  52 #include "fixed-value.h"
  53 #include "insn-config.h"
  54 #include "expmed.h"
  55 #include "dojump.h"
  56 #include "explow.h"
  57 #include "calls.h"
  58 #include "emit-rtl.h"
  59 #include "varasm.h"
  60 #include "stmt.h"
  61 #include "expr.h"
  62 #include "gimple-iterator.h"
  63 #include "gimple-ssa.h"
  64 #include "tree-cfg.h"
  65 #include "stringpool.h"
  66 #include "tree-dfa.h"
  67 #include "tree-pass.h"
  68 #include "gimple-pretty-print.h"
  69 #include "cfgloop.h"
  70 #include "except.h"
  71 #include "hash-map.h"
  72 #include "plugin-api.h"
  73 #include "ipa-ref.h"
  74 #include "cgraph.h"
  75 #include "data-streamer.h"
  76 #include "ipa-utils.h"
  77 #include <list>
  78 #include "tree-ssanames.h"
  79 #include "tree-eh.h"
  80 #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_ssa_name (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         case GIMPLE_EH_DISPATCH:
 710           break;
 711         case GIMPLE_RESX:
 712           if (!compare_gimple_resx (as_a <gresx *> (s1),
 713                                     as_a <gresx *> (s2)))
 714             return return_different_stmts (s1, s2, "GIMPLE_RESX");
 715           break;
 716         case GIMPLE_LABEL:
 717           if (!compare_gimple_label (as_a <glabel *> (s1),
 718                                      as_a <glabel *> (s2)))
 719             return return_different_stmts (s1, s2, "GIMPLE_LABEL");
 720           break;
 721         case GIMPLE_RETURN:
 722           if (!compare_gimple_return (as_a <greturn *> (s1),
 723                                       as_a <greturn *> (s2)))
 724             return return_different_stmts (s1, s2, "GIMPLE_RETURN");
 725           break;
 726         case GIMPLE_GOTO:
 727           if (!compare_gimple_goto (s1, s2))
 728             return return_different_stmts (s1, s2, "GIMPLE_GOTO");
 729           break;
 730         case GIMPLE_ASM:
 731           if (!compare_gimple_asm (as_a <gasm *> (s1),
 732                                    as_a <gasm *> (s2)))
 733             return return_different_stmts (s1, s2, "GIMPLE_ASM");
 734           break;
 735         case GIMPLE_PREDICT:
 736         case GIMPLE_NOP:
 737           return true;
 738         default:
 739           return return_false_with_msg ("Unknown GIMPLE code reached");
 740         }
 741
 742       gsi_next_nondebug (&gsi1);
 743       gsi_next_nondebug (&gsi2);
 744     }
 745
 746   if (!gsi_end_p (gsi2))
 747     return return_false ();
 748
 749   return true;
 750 }
 751
 752 /* Verifies for given GIMPLEs S1 and S2 that
 753    call statements are semantically equivalent.  */
 754
 755 bool
 756 func_checker::compare_gimple_call (gcall *s1, gcall *s2)
 757 {
 758   unsigned i;
 759   tree t1, t2;
 760
 761   if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
 762     return false;
 763
 764   t1 = gimple_call_fn (s1);
 765   t2 = gimple_call_fn (s2);
 766   if (!compare_operand (t1, t2))
 767     return return_false ();
 768
 769   /* Compare flags.  */
 770   if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
 771       || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
 772       || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
 773       || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
 774       || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
 775       || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
 776       || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2)
 777       || gimple_call_with_bounds_p (s1) != gimple_call_with_bounds_p (s2))
 778     return false;
 779
 780   if (gimple_call_internal_p (s1)
 781       && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
 782     return false;
 783
 784   tree fntype1 = gimple_call_fntype (s1);
 785   tree fntype2 = gimple_call_fntype (s2);
 786   if ((fntype1 && !fntype2)
 787       || (!fntype1 && fntype2)
 788       || (fntype1 && !types_compatible_p (fntype1, fntype2)))
 789     return return_false_with_msg ("call function types are not compatible");
 790
 791   tree chain1 = gimple_call_chain (s1);
 792   tree chain2 = gimple_call_chain (s2);
 793   if ((chain1 && !chain2)
 794       || (!chain1 && chain2)
 795       || !compare_operand (chain1, chain2))
 796     return return_false_with_msg ("static call chains are different");
 797
 798   /* Checking of argument.  */
 799   for (i = 0; i < gimple_call_num_args (s1); ++i)
 800     {
 801       t1 = gimple_call_arg (s1, i);
 802       t2 = gimple_call_arg (s2, i);
 803
 804       if (!compare_memory_operand (t1, t2))
 805         return return_false_with_msg ("memory operands are different");
 806     }
 807
 808   /* Return value checking.  */
 809   t1 = gimple_get_lhs (s1);
 810   t2 = gimple_get_lhs (s2);
 811
 812   return compare_memory_operand (t1, t2);
 813 }
 814
 815
 816 /* Verifies for given GIMPLEs S1 and S2 that
 817    assignment statements are semantically equivalent.  */
 818
 819 bool
 820 func_checker::compare_gimple_assign (gimple s1, gimple s2)
 821 {
 822   tree arg1, arg2;
 823   tree_code code1, code2;
 824   unsigned i;
 825
 826   code1 = gimple_expr_code (s1);
 827   code2 = gimple_expr_code (s2);
 828
 829   if (code1 != code2)
 830     return false;
 831
 832   code1 = gimple_assign_rhs_code (s1);
 833   code2 = gimple_assign_rhs_code (s2);
 834
 835   if (code1 != code2)
 836     return false;
 837
 838   for (i = 0; i < gimple_num_ops (s1); i++)
 839     {
 840       arg1 = gimple_op (s1, i);
 841       arg2 = gimple_op (s2, i);
 842
 843       if (!compare_memory_operand (arg1, arg2))
 844         return return_false_with_msg ("memory operands are different");
 845     }
 846
 847
 848   return true;
 849 }
 850
 851 /* Verifies for given GIMPLEs S1 and S2 that
 852    condition statements are semantically equivalent.  */
 853
 854 bool
 855 func_checker::compare_gimple_cond (gimple s1, gimple s2)
 856 {
 857   tree t1, t2;
 858   tree_code code1, code2;
 859
 860   code1 = gimple_expr_code (s1);
 861   code2 = gimple_expr_code (s2);
 862
 863   if (code1 != code2)
 864     return false;
 865
 866   t1 = gimple_cond_lhs (s1);
 867   t2 = gimple_cond_lhs (s2);
 868
 869   if (!compare_operand (t1, t2))
 870     return false;
 871
 872   t1 = gimple_cond_rhs (s1);
 873   t2 = gimple_cond_rhs (s2);
 874
 875   return compare_operand (t1, t2);
 876 }
 877
 878 /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2.  */
 879
 880 bool
 881 func_checker::compare_tree_ssa_label (tree t1, tree t2)
 882 {
 883   return compare_operand (t1, t2);
 884 }
 885
 886 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
 887    label statements are semantically equivalent.  */
 888
 889 bool
 890 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
 891 {
 892   if (m_ignore_labels)
 893     return true;
 894
 895   tree t1 = gimple_label_label (g1);
 896   tree t2 = gimple_label_label (g2);
 897
 898   if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
 899     return return_false_with_msg ("FORCED_LABEL");
 900
 901   /* As the pass build BB to label mapping, no further check is needed.  */
 902   return true;
 903 }
 904
 905 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
 906    switch statements are semantically equivalent.  */
 907
 908 bool
 909 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
 910 {
 911   unsigned lsize1, lsize2, i;
 912
 913   lsize1 = gimple_switch_num_labels (g1);
 914   lsize2 = gimple_switch_num_labels (g2);
 915
 916   if (lsize1 != lsize2)
 917     return false;
 918
 919   tree t1 = gimple_switch_index (g1);
 920   tree t2 = gimple_switch_index (g2);
 921
 922   if (!compare_operand (t1, t2))
 923     return false;
 924
 925   for (i = 0; i < lsize1; i++)
 926     {
 927       tree label1 = gimple_switch_label (g1, i);
 928       tree label2 = gimple_switch_label (g2, i);
 929
 930       /* Label LOW and HIGH comparison.  */
 931       tree low1 = CASE_LOW (label1);
 932       tree low2 = CASE_LOW (label2);
 933
 934       if (!tree_int_cst_equal (low1, low2))
 935         return return_false_with_msg ("case low values are different");
 936
 937       tree high1 = CASE_HIGH (label1);
 938       tree high2 = CASE_HIGH (label2);
 939
 940       if (!tree_int_cst_equal (high1, high2))
 941         return return_false_with_msg ("case high values are different");
 942
 943       if (TREE_CODE (label1) == CASE_LABEL_EXPR
 944           && TREE_CODE (label2) == CASE_LABEL_EXPR)
 945         {
 946           label1 = CASE_LABEL (label1);
 947           label2 = CASE_LABEL (label2);
 948
 949           if (!compare_operand (label1, label2))
 950             return return_false_with_msg ("switch label_exprs are different");
 951         }
 952       else if (!tree_int_cst_equal (label1, label2))
 953         return return_false_with_msg ("switch labels are different");
 954     }
 955
 956   return true;
 957 }
 958
 959 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
 960    return statements are semantically equivalent.  */
 961
 962 bool
 963 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
 964 {
 965   tree t1, t2;
 966
 967   t1 = gimple_return_retval (g1);
 968   t2 = gimple_return_retval (g2);
 969
 970   /* Void return type.  */
 971   if (t1 == NULL && t2 == NULL)
 972     return true;
 973   else
 974     return compare_operand (t1, t2);
 975 }
 976
 977 /* Verifies for given GIMPLEs S1 and S2 that
 978    goto statements are semantically equivalent.  */
 979
 980 bool
 981 func_checker::compare_gimple_goto (gimple g1, gimple g2)
 982 {
 983   tree dest1, dest2;
 984
 985   dest1 = gimple_goto_dest (g1);
 986   dest2 = gimple_goto_dest (g2);
 987
 988   if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
 989     return false;
 990
 991   return compare_operand (dest1, dest2);
 992 }
 993
 994 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
 995    resx statements are semantically equivalent.  */
 996
 997 bool
 998 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
 999 {
1000   return gimple_resx_region (g1) == gimple_resx_region (g2);
1001 }
1002
1003 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
1004    For the beginning, the pass only supports equality for
1005    '__asm__ __volatile__ ("", "", "", "memory")'.  */
1006
1007 bool
1008 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
1009 {
1010   if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
1011     return false;
1012
1013   if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
1014     return false;
1015
1016   if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
1017     return false;
1018
1019   /* We do not suppport goto ASM statement comparison.  */
1020   if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
1021     return false;
1022
1023   if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
1024     return false;
1025
1026   if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
1027     return return_false_with_msg ("ASM strings are different");
1028
1029   for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
1030     {
1031       tree input1 = gimple_asm_input_op (g1, i);
1032       tree input2 = gimple_asm_input_op (g2, i);
1033
1034       if (!compare_tree_list_operand (input1, input2))
1035         return return_false_with_msg ("ASM input is different");
1036     }
1037
1038   for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
1039     {
1040       tree output1 = gimple_asm_output_op (g1, i);
1041       tree output2 = gimple_asm_output_op (g2, i);
1042
1043       if (!compare_tree_list_operand (output1, output2))
1044         return return_false_with_msg ("ASM output is different");
1045     }
1046
1047   for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
1048     {
1049       tree clobber1 = gimple_asm_clobber_op (g1, i);
1050       tree clobber2 = gimple_asm_clobber_op (g2, i);
1051
1052       if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
1053                             OEP_ONLY_CONST))
1054         return return_false_with_msg ("ASM clobber is different");
1055     }
1056
1057   return true;
1058 }
1059
1060 } // ipa_icf_gimple namespace