gcc/ipa-icf-gimple.c

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