LCOV - code coverage report
Current view: top level - gcc - ipa-polymorphic-call.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 987 1207 81.8 %
Date: 2020-04-04 11:58:09 Functions: 28 29 96.6 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Analysis of polymorphic call context.
       2                 :            :    Copyright (C) 2013-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Jan Hubicka
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "rtl.h"
      26                 :            : #include "tree.h"
      27                 :            : #include "gimple.h"
      28                 :            : #include "tree-pass.h"
      29                 :            : #include "tree-ssa-operands.h"
      30                 :            : #include "streamer-hooks.h"
      31                 :            : #include "cgraph.h"
      32                 :            : #include "data-streamer.h"
      33                 :            : #include "diagnostic.h"
      34                 :            : #include "alias.h"
      35                 :            : #include "fold-const.h"
      36                 :            : #include "calls.h"
      37                 :            : #include "ipa-utils.h"
      38                 :            : #include "tree-dfa.h"
      39                 :            : #include "gimple-pretty-print.h"
      40                 :            : #include "tree-into-ssa.h"
      41                 :            : 
      42                 :            : /* Return true when TYPE contains an polymorphic type and thus is interesting
      43                 :            :    for devirtualization machinery.  */
      44                 :            : 
      45                 :            : static bool contains_type_p (tree, HOST_WIDE_INT, tree,
      46                 :            :                              bool consider_placement_new = true,
      47                 :            :                              bool consider_bases = true);
      48                 :            : 
      49                 :            : bool
      50                 :   14613000 : contains_polymorphic_type_p (const_tree type)
      51                 :            : {
      52                 :   15510500 :   type = TYPE_MAIN_VARIANT (type);
      53                 :            : 
      54                 :   15510500 :   if (RECORD_OR_UNION_TYPE_P (type))
      55                 :            :     {
      56                 :    5516310 :       if (TYPE_BINFO (type)
      57                 :    5516310 :           && polymorphic_type_binfo_p (TYPE_BINFO (type)))
      58                 :            :         return true;
      59                 :  240952000 :       for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
      60                 :  236390000 :         if (TREE_CODE (fld) == FIELD_DECL
      61                 :   12721600 :             && !DECL_ARTIFICIAL (fld)
      62                 :  248090000 :             && contains_polymorphic_type_p (TREE_TYPE (fld)))
      63                 :            :           return true;
      64                 :            :       return false;
      65                 :            :     }
      66                 :    9994150 :   if (TREE_CODE (type) == ARRAY_TYPE)
      67                 :     897420 :     return contains_polymorphic_type_p (TREE_TYPE (type));
      68                 :            :   return false;
      69                 :            : }
      70                 :            : 
      71                 :            : /* Return true if it seems valid to use placement new to build EXPECTED_TYPE
      72                 :            :    at position CUR_OFFSET within TYPE.  
      73                 :            : 
      74                 :            :    POD can be changed to an instance of a polymorphic type by
      75                 :            :    placement new.  Here we play safe and assume that any
      76                 :            :    non-polymorphic type is POD.  */
      77                 :            : bool
      78                 :      83405 : possible_placement_new (tree type, tree expected_type,
      79                 :            :                         HOST_WIDE_INT cur_offset)
      80                 :            : {
      81                 :      83405 :   if (cur_offset < 0)
      82                 :            :     return true;
      83                 :      79924 :   return ((TREE_CODE (type) != RECORD_TYPE
      84                 :       9812 :            || !TYPE_BINFO (type)
      85                 :       9844 :            || cur_offset >= POINTER_SIZE
      86                 :       7960 :            || !polymorphic_type_binfo_p (TYPE_BINFO (type)))
      87                 :     159643 :           && (!TYPE_SIZE (type)
      88                 :      79719 :               || !tree_fits_shwi_p (TYPE_SIZE (type))
      89                 :      79719 :               || (cur_offset
      90                 :     159438 :                   + (expected_type ? tree_to_uhwi (TYPE_SIZE (expected_type))
      91                 :      73286 :                      : POINTER_SIZE)
      92                 :      79719 :                   <= tree_to_uhwi (TYPE_SIZE (type)))));
      93                 :            : }
      94                 :            : 
      95                 :            : /* THIS->OUTER_TYPE is a type of memory object where object of OTR_TYPE
      96                 :            :    is contained at THIS->OFFSET.  Walk the memory representation of
      97                 :            :    THIS->OUTER_TYPE and find the outermost class type that match
      98                 :            :    OTR_TYPE or contain OTR_TYPE as a base.  Update THIS
      99                 :            :    to represent it.
     100                 :            : 
     101                 :            :    If OTR_TYPE is NULL, just find outermost polymorphic type with
     102                 :            :    virtual table present at position OFFSET.
     103                 :            : 
     104                 :            :    For example when THIS represents type
     105                 :            :    class A
     106                 :            :      {
     107                 :            :        int a;
     108                 :            :        class B b;
     109                 :            :      }
     110                 :            :    and we look for type at offset sizeof(int), we end up with B and offset 0.
     111                 :            :    If the same is produced by multiple inheritance, we end up with A and offset
     112                 :            :    sizeof(int). 
     113                 :            : 
     114                 :            :    If we cannot find corresponding class, give up by setting
     115                 :            :    THIS->OUTER_TYPE to OTR_TYPE and THIS->OFFSET to NULL. 
     116                 :            :    Return true when lookup was successful.
     117                 :            : 
     118                 :            :    When CONSIDER_PLACEMENT_NEW is false, reject contexts that may be made
     119                 :            :    valid only via allocation of new polymorphic type inside by means
     120                 :            :    of placement new.
     121                 :            : 
     122                 :            :    When CONSIDER_BASES is false, only look for actual fields, not base types
     123                 :            :    of TYPE.  */
     124                 :            : 
     125                 :            : bool
     126                 :    1190550 : ipa_polymorphic_call_context::restrict_to_inner_class (tree otr_type,
     127                 :            :                                                        bool consider_placement_new,
     128                 :            :                                                        bool consider_bases)
     129                 :            : {
     130                 :    1190550 :   tree type = outer_type;
     131                 :    1190550 :   HOST_WIDE_INT cur_offset = offset;
     132                 :    1190550 :   bool speculative = false;
     133                 :    1190550 :   bool size_unknown = false;
     134                 :    1190550 :   unsigned HOST_WIDE_INT otr_type_size = POINTER_SIZE;
     135                 :            : 
     136                 :            :   /* Update OUTER_TYPE to match EXPECTED_TYPE if it is not set.  */
     137                 :    1190550 :   if (!outer_type)
     138                 :            :     {
     139                 :      32496 :       clear_outer_type (otr_type);
     140                 :      32496 :       type = otr_type;
     141                 :      32496 :       cur_offset = 0;
     142                 :            :     }
     143                 :            :  /* See if OFFSET points inside OUTER_TYPE.  If it does not, we know
     144                 :            :     that the context is either invalid, or the instance type must be
     145                 :            :     derived from OUTER_TYPE.
     146                 :            : 
     147                 :            :     Because the instance type may contain field whose type is of OUTER_TYPE,
     148                 :            :     we cannot derive any effective information about it.
     149                 :            : 
     150                 :            :     TODO: In the case we know all derived types, we can definitely do better
     151                 :            :     here.  */
     152                 :    1158050 :   else if (TYPE_SIZE (outer_type)
     153                 :    1158030 :            && tree_fits_shwi_p (TYPE_SIZE (outer_type))
     154                 :    1158030 :            && tree_to_shwi (TYPE_SIZE (outer_type)) >= 0
     155                 :    2316080 :            && tree_to_shwi (TYPE_SIZE (outer_type)) <= offset)
     156                 :            :    {
     157                 :         30 :      bool der = maybe_derived_type; /* clear_outer_type will reset it.  */
     158                 :         30 :      bool dyn = dynamic;
     159                 :         30 :      clear_outer_type (otr_type);
     160                 :         30 :      type = otr_type;
     161                 :         30 :      cur_offset = 0;
     162                 :            : 
     163                 :            :      /* If derived type is not allowed, we know that the context is invalid.
     164                 :            :         For dynamic types, we really do not have information about
     165                 :            :         size of the memory location.  It is possible that completely
     166                 :            :         different type is stored after outer_type.  */
     167                 :         30 :      if (!der && !dyn)
     168                 :            :        {
     169                 :         30 :          clear_speculation ();
     170                 :         30 :          invalid = true;
     171                 :         30 :          return false;
     172                 :            :        }
     173                 :            :    }
     174                 :            : 
     175                 :    1111640 :   if (otr_type && TYPE_SIZE (otr_type)
     176                 :    2302150 :       && tree_fits_shwi_p (TYPE_SIZE (otr_type)))
     177                 :    1111630 :     otr_type_size = tree_to_uhwi (TYPE_SIZE (otr_type));
     178                 :            : 
     179                 :    1190520 :   if (!type || offset < 0)
     180                 :       3481 :     goto no_useful_type_info;
     181                 :            : 
     182                 :            :   /* Find the sub-object the constant actually refers to and mark whether it is
     183                 :            :      an artificial one (as opposed to a user-defined one).
     184                 :            : 
     185                 :            :      This loop is performed twice; first time for outer_type and second time
     186                 :            :      for speculative_outer_type.  The second run has SPECULATIVE set.  */
     187                 :    1569390 :   while (true)
     188                 :            :     {
     189                 :    1569390 :       unsigned HOST_WIDE_INT pos, size;
     190                 :    1569390 :       tree fld;
     191                 :            : 
     192                 :            :       /* If we do not know size of TYPE, we need to be more conservative
     193                 :            :          about accepting cases where we cannot find EXPECTED_TYPE.
     194                 :            :          Generally the types that do matter here are of constant size.
     195                 :            :          Size_unknown case should be very rare.  */
     196                 :    1569390 :       if (TYPE_SIZE (type)
     197                 :    1569370 :           && tree_fits_shwi_p (TYPE_SIZE (type))
     198                 :    3138760 :           && tree_to_shwi (TYPE_SIZE (type)) >= 0)
     199                 :            :         size_unknown = false;
     200                 :            :       else
     201                 :            :         size_unknown = true;
     202                 :            : 
     203                 :            :       /* On a match, just return what we found.  */
     204                 :    1569390 :       if ((otr_type
     205                 :    1308930 :            && types_odr_comparable (type, otr_type)
     206                 :    1308870 :            && types_same_for_odr (type, otr_type))
     207                 :    1897280 :           || (!otr_type
     208                 :     260468 :               && TREE_CODE (type) == RECORD_TYPE
     209                 :     196589 :               && TYPE_BINFO (type)
     210                 :     196045 :               && polymorphic_type_binfo_p (TYPE_BINFO (type))))
     211                 :            :         {
     212                 :     984790 :           if (speculative)
     213                 :            :             {
     214                 :            :               /* If we did not match the offset, just give up on speculation.  */
     215                 :       6549 :               if (cur_offset != 0
     216                 :            :                   /* Also check if speculation did not end up being same as
     217                 :            :                      non-speculation.  */
     218                 :       6549 :                   || (types_must_be_same_for_odr (speculative_outer_type,
     219                 :            :                                                   outer_type)
     220                 :         78 :                       && (maybe_derived_type
     221                 :         78 :                           == speculative_maybe_derived_type)))
     222                 :          0 :                 clear_speculation ();
     223                 :       6549 :               return true;
     224                 :            :             }
     225                 :            :           else
     226                 :            :             {
     227                 :            :               /* If type is known to be final, do not worry about derived
     228                 :            :                  types.  Testing it here may help us to avoid speculation.  */
     229                 :     974487 :               if (otr_type && TREE_CODE (outer_type) == RECORD_TYPE
     230                 :     974487 :                   && (!in_lto_p || odr_type_p (outer_type))
     231                 :     974487 :                   && type_with_linkage_p (outer_type)
     232                 :    1952730 :                   && type_known_to_have_no_derivations_p (outer_type))
     233                 :       5654 :                 maybe_derived_type = false;
     234                 :            : 
     235                 :            :               /* Type cannot contain itself on an non-zero offset.  In that case
     236                 :            :                  just give up.  Still accept the case where size is now known.
     237                 :            :                  Either the second copy may appear past the end of type or within
     238                 :            :                  the non-POD buffer located inside the variably sized type
     239                 :            :                  itself.  */
     240                 :     978241 :               if (cur_offset != 0)
     241                 :       1625 :                 goto no_useful_type_info;
     242                 :            :               /* If we determined type precisely or we have no clue on
     243                 :            :                  speculation, we are done.  */
     244                 :     756850 :               if (!maybe_derived_type || !speculative_outer_type
     245                 :    1011350 :                   || !speculation_consistent_p (speculative_outer_type,
     246                 :            :                                                 speculative_offset,
     247                 :            :                                                 speculative_maybe_derived_type,
     248                 :            :                                                 otr_type))
     249                 :            :                 {
     250                 :     970070 :                   clear_speculation ();
     251                 :     970070 :                   return true;
     252                 :            :                 }
     253                 :            :               /* Otherwise look into speculation now.  */
     254                 :            :               else
     255                 :            :                 {
     256                 :       6546 :                   speculative = true;
     257                 :       6546 :                   type = speculative_outer_type;
     258                 :       6546 :                   cur_offset = speculative_offset;
     259                 :       6546 :                   continue;
     260                 :            :                 }
     261                 :            :             }
     262                 :            :         }
     263                 :            : 
     264                 :            :       /* Walk fields and find corresponding on at OFFSET.  */
     265                 :     584604 :       if (TREE_CODE (type) == RECORD_TYPE)
     266                 :            :         {
     267                 :    8154900 :           for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
     268                 :            :             {
     269                 :   15383900 :               if (TREE_CODE (fld) != FIELD_DECL
     270                 :    8768100 :                   || TREE_TYPE (fld) == error_mark_node)
     271                 :    7333210 :                 continue;
     272                 :            : 
     273                 :     717442 :               pos = int_bit_position (fld);
     274                 :     717442 :               if (pos > (unsigned HOST_WIDE_INT)cur_offset)
     275                 :     168208 :                 continue;
     276                 :            : 
     277                 :            :               /* Do not consider vptr itself.  Not even for placement new.  */
     278                 :     529143 :               if (!pos && DECL_ARTIFICIAL (fld)
     279                 :     370294 :                   && POINTER_TYPE_P (TREE_TYPE (fld))
     280                 :      39690 :                   && TYPE_BINFO (type)
     281                 :     588924 :                   && polymorphic_type_binfo_p (TYPE_BINFO (type)))
     282                 :      39690 :                 continue;
     283                 :            : 
     284                 :     509544 :               if (!DECL_SIZE (fld) || !tree_fits_uhwi_p (DECL_SIZE (fld)))
     285                 :          0 :                 goto no_useful_type_info;
     286                 :     509544 :               size = tree_to_uhwi (DECL_SIZE (fld));
     287                 :            : 
     288                 :            :               /* We can always skip types smaller than pointer size:
     289                 :            :                  those cannot contain a virtual table pointer.
     290                 :            : 
     291                 :            :                  Disqualifying fields that are too small to fit OTR_TYPE
     292                 :            :                  saves work needed to walk them for no benefit.
     293                 :            :                  Because of the way the bases are packed into a class, the
     294                 :            :                  field's size may be smaller than type size, so it needs
     295                 :            :                  to be done with a care.  */
     296                 :            :                 
     297                 :     509544 :               if (pos <= (unsigned HOST_WIDE_INT)cur_offset
     298                 :    1019090 :                   && (pos + size) >= (unsigned HOST_WIDE_INT)cur_offset
     299                 :     524365 :                                      + POINTER_SIZE
     300                 :     466859 :                   && (!otr_type
     301                 :     281806 :                       || !TYPE_SIZE (TREE_TYPE (fld))
     302                 :     281806 :                       || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (fld)))
     303                 :     281806 :                       || (pos + tree_to_uhwi (TYPE_SIZE (TREE_TYPE (fld))))
     304                 :     281806 :                           >= cur_offset + otr_type_size))
     305                 :            :                 break;
     306                 :            :             }
     307                 :            : 
     308                 :     514241 :           if (!fld)
     309                 :     104252 :             goto no_useful_type_info;
     310                 :            : 
     311                 :     409989 :           type = TYPE_MAIN_VARIANT (TREE_TYPE (fld));
     312                 :     409989 :           cur_offset -= pos;
     313                 :            :           /* DECL_ARTIFICIAL represents a basetype.  */
     314                 :     409989 :           if (!DECL_ARTIFICIAL (fld))
     315                 :            :             {
     316                 :     161685 :               if (!speculative)
     317                 :            :                 {
     318                 :     161371 :                   outer_type = type;
     319                 :     161371 :                   offset = cur_offset;
     320                 :            :                   /* As soon as we see an field containing the type,
     321                 :            :                      we know we are not looking for derivations.  */
     322                 :     161371 :                   maybe_derived_type = false;
     323                 :            :                 }
     324                 :            :               else
     325                 :            :                 {
     326                 :        314 :                   speculative_outer_type = type;
     327                 :        314 :                   speculative_offset = cur_offset;
     328                 :        314 :                   speculative_maybe_derived_type = false;
     329                 :            :                 }
     330                 :            :             }
     331                 :     248304 :           else if (!consider_bases)
     332                 :      34306 :             goto no_useful_type_info;
     333                 :            :         }
     334                 :      70363 :       else if (TREE_CODE (type) == ARRAY_TYPE)
     335                 :            :         {
     336                 :       2035 :           tree subtype = TYPE_MAIN_VARIANT (TREE_TYPE (type));
     337                 :            : 
     338                 :            :           /* Give up if we don't know array field size.
     339                 :            :              Also give up on non-polymorphic types as they are used
     340                 :            :              as buffers for placement new.  */
     341                 :       2035 :           if (!TYPE_SIZE (subtype)
     342                 :       2035 :               || !tree_fits_shwi_p (TYPE_SIZE (subtype))
     343                 :       2035 :               || tree_to_shwi (TYPE_SIZE (subtype)) <= 0
     344                 :       4070 :               || !contains_polymorphic_type_p (subtype))
     345                 :       1518 :             goto no_useful_type_info;
     346                 :            : 
     347                 :        517 :           HOST_WIDE_INT new_offset = cur_offset % tree_to_shwi (TYPE_SIZE (subtype));
     348                 :            : 
     349                 :            :           /* We may see buffer for placement new.  In this case the expected type
     350                 :            :              can be bigger than the subtype.  */
     351                 :        517 :           if (TYPE_SIZE (subtype)
     352                 :        517 :               && (cur_offset + otr_type_size
     353                 :        517 :                   > tree_to_uhwi (TYPE_SIZE (subtype))))
     354                 :        393 :             goto no_useful_type_info;
     355                 :            : 
     356                 :        124 :           cur_offset = new_offset;
     357                 :        124 :           type = TYPE_MAIN_VARIANT (subtype);
     358                 :        124 :           if (!speculative)
     359                 :            :             {
     360                 :        124 :               outer_type = type;
     361                 :        124 :               offset = cur_offset;
     362                 :        124 :               maybe_derived_type = false;
     363                 :            :             }
     364                 :            :           else
     365                 :            :             {
     366                 :          0 :               speculative_outer_type = type;
     367                 :          0 :               speculative_offset = cur_offset;
     368                 :          0 :               speculative_maybe_derived_type = false;
     369                 :            :             }
     370                 :            :         }
     371                 :            :       /* Give up on anything else.  */
     372                 :            :       else
     373                 :            :         {
     374                 :      68328 : no_useful_type_info:
     375                 :          0 :           if (maybe_derived_type && !speculative
     376                 :          0 :               && TREE_CODE (outer_type) == RECORD_TYPE
     377                 :          0 :               && TREE_CODE (otr_type) == RECORD_TYPE
     378                 :          0 :               && TYPE_BINFO (otr_type)
     379                 :          0 :               && !offset
     380                 :     213903 :               && get_binfo_at_offset (TYPE_BINFO (otr_type), 0, outer_type))
     381                 :            :             {
     382                 :          0 :               clear_outer_type (otr_type);
     383                 :          0 :               if (!speculative_outer_type
     384                 :          0 :                   || !speculation_consistent_p (speculative_outer_type,
     385                 :            :                                                 speculative_offset,
     386                 :            :                                                 speculative_maybe_derived_type,
     387                 :          0 :                                                 otr_type))
     388                 :          0 :                 clear_speculation ();
     389                 :          0 :               if (speculative_outer_type)
     390                 :            :                 {
     391                 :          0 :                   speculative = true;
     392                 :          0 :                   type = speculative_outer_type;
     393                 :          0 :                   cur_offset = speculative_offset;
     394                 :            :                 }
     395                 :            :               else
     396                 :            :                 return true;
     397                 :            :             }
     398                 :            :           /* We found no way to embed EXPECTED_TYPE in TYPE.
     399                 :            :              We still permit two special cases - placement new and
     400                 :            :              the case of variadic types containing themselves.  */
     401                 :     213903 :           if (!speculative
     402                 :     213903 :               && consider_placement_new
     403                 :     213903 :               && (size_unknown || !type || maybe_derived_type
     404                 :      83405 :                   || possible_placement_new (type, otr_type, cur_offset)))
     405                 :            :             {
     406                 :            :               /* In these weird cases we want to accept the context.
     407                 :            :                  In non-speculative run we have no useful outer_type info
     408                 :            :                  (TODO: we may eventually want to record upper bound on the
     409                 :            :                   type size that can be used to prune the walk),
     410                 :            :                  but we still want to consider speculation that may
     411                 :            :                  give useful info.  */
     412                 :      82476 :               if (!speculative)
     413                 :            :                 {
     414                 :      82476 :                   clear_outer_type (otr_type);
     415                 :      82476 :                   if (!speculative_outer_type
     416                 :      82481 :                       || !speculation_consistent_p (speculative_outer_type,
     417                 :            :                                                     speculative_offset,
     418                 :            :                                                     speculative_maybe_derived_type,
     419                 :          5 :                                                     otr_type))
     420                 :      82473 :                     clear_speculation ();
     421                 :      82476 :                   if (speculative_outer_type)
     422                 :            :                     {
     423                 :          3 :                       speculative = true;
     424                 :          3 :                       type = speculative_outer_type;
     425                 :          3 :                       cur_offset = speculative_offset;
     426                 :            :                     }
     427                 :            :                   else
     428                 :            :                     return true;
     429                 :            :                 }
     430                 :            :               else
     431                 :            :                 {
     432                 :            :                   clear_speculation ();
     433                 :            :                   return true;
     434                 :            :                 }
     435                 :            :             }
     436                 :            :           else
     437                 :            :             {
     438                 :     131427 :               clear_speculation ();
     439                 :     131427 :               if (speculative)
     440                 :            :                 return true;
     441                 :     131427 :               clear_outer_type (otr_type);
     442                 :     131427 :               invalid = true; 
     443                 :     131427 :               return false;
     444                 :            :             }
     445                 :            :         }
     446                 :            :     }
     447                 :            : }
     448                 :            : 
     449                 :            : /* Return true if OUTER_TYPE contains OTR_TYPE at OFFSET.
     450                 :            :    CONSIDER_PLACEMENT_NEW makes function to accept cases where OTR_TYPE can
     451                 :            :    be built within OUTER_TYPE by means of placement new.  CONSIDER_BASES makes
     452                 :            :    function to accept cases where OTR_TYPE appears as base of OUTER_TYPE or as
     453                 :            :    base of one of fields of OUTER_TYPE.  */
     454                 :            : 
     455                 :            : static bool
     456                 :     332747 : contains_type_p (tree outer_type, HOST_WIDE_INT offset,
     457                 :            :                  tree otr_type,
     458                 :            :                  bool consider_placement_new,
     459                 :            :                  bool consider_bases)
     460                 :            : {
     461                 :     332747 :   ipa_polymorphic_call_context context;
     462                 :            : 
     463                 :            :   /* Check that type is within range.  */
     464                 :     332747 :   if (offset < 0)
     465                 :            :     return false;
     466                 :            : 
     467                 :            :   /* PR ipa/71207
     468                 :            :      As OUTER_TYPE can be a type which has a diamond virtual inheritance,
     469                 :            :      it's not necessary that INNER_TYPE will fit within OUTER_TYPE with
     470                 :            :      a given offset.  It can happen that INNER_TYPE also contains a base object,
     471                 :            :      however it would point to the same instance in the OUTER_TYPE.  */
     472                 :            : 
     473                 :     328937 :   context.offset = offset;
     474                 :     328937 :   context.outer_type = TYPE_MAIN_VARIANT (outer_type);
     475                 :     328937 :   context.maybe_derived_type = false;
     476                 :     328937 :   context.dynamic = false;
     477                 :     328937 :   return context.restrict_to_inner_class (otr_type, consider_placement_new,
     478                 :     328937 :                                           consider_bases);
     479                 :            : }
     480                 :            : 
     481                 :            : 
     482                 :            : /* Return a FUNCTION_DECL if FN represent a constructor or destructor.
     483                 :            :    If CHECK_CLONES is true, also check for clones of ctor/dtors.  */
     484                 :            : 
     485                 :            : tree
     486                 :   20931400 : polymorphic_ctor_dtor_p (tree fn, bool check_clones)
     487                 :            : {
     488                 :   20931400 :   if (TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
     489                 :   34614000 :       || (!DECL_CXX_CONSTRUCTOR_P (fn) && !DECL_CXX_DESTRUCTOR_P (fn)))
     490                 :            :     {
     491                 :   14141000 :       if (!check_clones)
     492                 :            :         return NULL_TREE;
     493                 :            : 
     494                 :            :       /* Watch for clones where we constant propagated the first
     495                 :            :          argument (pointer to the instance).  */
     496                 :   14118000 :       fn = DECL_ABSTRACT_ORIGIN (fn);
     497                 :   14118000 :       if (!fn
     498                 :    9730660 :           || TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
     499                 :   19842200 :           || (!DECL_CXX_CONSTRUCTOR_P (fn) && !DECL_CXX_DESTRUCTOR_P (fn)))
     500                 :            :         return NULL_TREE;
     501                 :            :     }
     502                 :            : 
     503                 :    6790430 :   if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
     504                 :      56695 :     return NULL_TREE;
     505                 :            : 
     506                 :            :   return fn;
     507                 :            : }
     508                 :            : 
     509                 :            : /* Return a FUNCTION_DECL if BLOCK represents a constructor or destructor.
     510                 :            :    If CHECK_CLONES is true, also check for clones of ctor/dtors.  */
     511                 :            : 
     512                 :            : tree
     513                 :   82910000 : inlined_polymorphic_ctor_dtor_block_p (tree block, bool check_clones)
     514                 :            : {
     515                 :   82910000 :   tree fn = block_ultimate_origin (block);
     516                 :   82910000 :   if (fn == NULL || TREE_CODE (fn) != FUNCTION_DECL)
     517                 :            :     return NULL_TREE;
     518                 :            : 
     519                 :   16271600 :   return polymorphic_ctor_dtor_p (fn, check_clones);
     520                 :            : }
     521                 :            : 
     522                 :            : 
     523                 :            : /* We know that the instance is stored in variable or parameter
     524                 :            :    (not dynamically allocated) and we want to disprove the fact
     525                 :            :    that it may be in construction at invocation of CALL.
     526                 :            : 
     527                 :            :    BASE represents memory location where instance is stored.
     528                 :            :    If BASE is NULL, it is assumed to be global memory.
     529                 :            :    OUTER_TYPE is known type of the instance or NULL if not
     530                 :            :    known.
     531                 :            : 
     532                 :            :    For the variable to be in construction we actually need to
     533                 :            :    be in constructor of corresponding global variable or
     534                 :            :    the inline stack of CALL must contain the constructor.
     535                 :            :    Check this condition.  This check works safely only before
     536                 :            :    IPA passes, because inline stacks may become out of date
     537                 :            :    later.  */
     538                 :            : 
     539                 :            : bool
     540                 :   19186300 : decl_maybe_in_construction_p (tree base, tree outer_type,
     541                 :            :                               gimple *call, tree function)
     542                 :            : {
     543                 :   19186300 :   if (outer_type)
     544                 :      33045 :     outer_type = TYPE_MAIN_VARIANT (outer_type);
     545                 :   19186300 :   gcc_assert (!base || DECL_P (base));
     546                 :            : 
     547                 :            :   /* After inlining the code unification optimizations may invalidate
     548                 :            :      inline stacks.  Also we need to give up on global variables after
     549                 :            :      IPA, because addresses of these may have been propagated to their
     550                 :            :      constructors.  */
     551                 :   19186300 :   if (DECL_STRUCT_FUNCTION (function)->after_inlining)
     552                 :            :     return true;
     553                 :            : 
     554                 :            :   /* Pure functions cannot do any changes on the dynamic type;
     555                 :            :      that require writing to memory.  */
     556                 :      32806 :   if ((!base || !auto_var_in_fn_p (base, function))
     557                 :   19173800 :       && flags_from_decl_or_type (function) & (ECF_PURE | ECF_CONST))
     558                 :            :     return false;
     559                 :            : 
     560                 :   19019900 :   bool check_clones = !base || is_global_var (base);
     561                 :  123685000 :   for (tree block = gimple_block (call); block && TREE_CODE (block) == BLOCK;
     562                 :   42822700 :        block = BLOCK_SUPERCONTEXT (block))
     563                 :   42841000 :     if (tree fn = inlined_polymorphic_ctor_dtor_block_p (block, check_clones))
     564                 :            :       {
     565                 :     203862 :         tree type = TYPE_METHOD_BASETYPE (TREE_TYPE (fn));
     566                 :            : 
     567                 :     203862 :         if (!outer_type || !types_odr_comparable (type, outer_type))
     568                 :            :           {
     569                 :     201009 :             if (TREE_CODE (type) == RECORD_TYPE
     570                 :     199728 :                 && TYPE_BINFO (type)
     571                 :     398838 :                 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
     572                 :            :               return true;
     573                 :            :           }
     574                 :       2853 :         else if (types_same_for_odr (type, outer_type))
     575                 :            :           return true;
     576                 :            :       }
     577                 :            : 
     578                 :   19001600 :   if (!base || (VAR_P (base) && is_global_var (base)))
     579                 :            :     {
     580                 :   18983900 :       if (TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
     581                 :   23949100 :           || (!DECL_CXX_CONSTRUCTOR_P (function)
     582                 :    4006260 :               && !DECL_CXX_DESTRUCTOR_P (function)))
     583                 :            :         {
     584                 :   17659200 :           if (!DECL_ABSTRACT_ORIGIN (function))
     585                 :            :             return false;
     586                 :            :           /* Watch for clones where we constant propagated the first
     587                 :            :              argument (pointer to the instance).  */
     588                 :      39106 :           function = DECL_ABSTRACT_ORIGIN (function);
     589                 :      39106 :           if (!function
     590                 :      39106 :               || TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
     591                 :      23762 :               || (!DECL_CXX_CONSTRUCTOR_P (function)
     592                 :      23730 :                   && !DECL_CXX_DESTRUCTOR_P (function)))
     593                 :            :             return false;
     594                 :            :         }
     595                 :    1324730 :       tree type = TYPE_METHOD_BASETYPE (TREE_TYPE (function));
     596                 :    1324730 :       if (!outer_type || !types_odr_comparable (type, outer_type))
     597                 :            :         {
     598                 :    1324450 :           if (TREE_CODE (type) == RECORD_TYPE
     599                 :    1323050 :               && TYPE_BINFO (type)
     600                 :    2640150 :               && polymorphic_type_binfo_p (TYPE_BINFO (type)))
     601                 :     308698 :             return true;
     602                 :            :         }
     603                 :        277 :       else if (types_same_for_odr (type, outer_type))
     604                 :          0 :         return true;
     605                 :            :     }
     606                 :            :   return false;
     607                 :            : }
     608                 :            : 
     609                 :            : /* Dump human readable context to F.  If NEWLINE is true, it will be terminated
     610                 :            :    by a newline.  */
     611                 :            : 
     612                 :            : void
     613                 :       1561 : ipa_polymorphic_call_context::dump (FILE *f, bool newline) const
     614                 :            : {
     615                 :       1561 :   fprintf (f, "    ");
     616                 :       1561 :   if (invalid)
     617                 :          0 :     fprintf (f, "Call is known to be undefined");
     618                 :            :   else
     619                 :            :     {
     620                 :       1561 :       if (useless_p ())
     621                 :          0 :         fprintf (f, "nothing known");
     622                 :       1561 :       if (outer_type || offset)
     623                 :            :         {
     624                 :       1745 :           fprintf (f, "Outer type%s:", dynamic ? " (dynamic)":"");
     625                 :       1373 :           print_generic_expr (f, outer_type, TDF_SLIM);
     626                 :       1373 :           if (maybe_derived_type)
     627                 :        768 :             fprintf (f, " (or a derived type)");
     628                 :       1373 :           if (maybe_in_construction)
     629                 :        194 :             fprintf (f, " (maybe in construction)");
     630                 :       1373 :           fprintf (f, " offset " HOST_WIDE_INT_PRINT_DEC,
     631                 :       1373 :                    offset);
     632                 :            :         }
     633                 :       1561 :       if (speculative_outer_type)
     634                 :            :         {
     635                 :        422 :           if (outer_type || offset)
     636                 :        234 :             fprintf (f, " ");
     637                 :        422 :           fprintf (f, "Speculative outer type:");
     638                 :        422 :           print_generic_expr (f, speculative_outer_type, TDF_SLIM);
     639                 :        422 :           if (speculative_maybe_derived_type)
     640                 :        380 :             fprintf (f, " (or a derived type)");
     641                 :        422 :           fprintf (f, " at offset " HOST_WIDE_INT_PRINT_DEC,
     642                 :        422 :                    speculative_offset);
     643                 :            :         }
     644                 :            :     }
     645                 :       1561 :   if (newline)
     646                 :       1313 :     fprintf(f, "\n");
     647                 :       1561 : }
     648                 :            : 
     649                 :            : /* Print context to stderr.  */
     650                 :            : 
     651                 :            : void
     652                 :          0 : ipa_polymorphic_call_context::debug () const
     653                 :            : {
     654                 :          0 :   dump (stderr);
     655                 :          0 : }
     656                 :            : 
     657                 :            : /* Stream out the context to OB.  */
     658                 :            : 
     659                 :            : void
     660                 :       3043 : ipa_polymorphic_call_context::stream_out (struct output_block *ob) const
     661                 :            : {
     662                 :       3043 :   struct bitpack_d bp = bitpack_create (ob->main_stream);
     663                 :            : 
     664                 :       3043 :   bp_pack_value (&bp, invalid, 1);
     665                 :       3043 :   bp_pack_value (&bp, maybe_in_construction, 1);
     666                 :       3043 :   bp_pack_value (&bp, maybe_derived_type, 1);
     667                 :       3043 :   bp_pack_value (&bp, speculative_maybe_derived_type, 1);
     668                 :       3043 :   bp_pack_value (&bp, dynamic, 1);
     669                 :       3043 :   bp_pack_value (&bp, outer_type != NULL, 1);
     670                 :       3043 :   bp_pack_value (&bp, offset != 0, 1);
     671                 :       3043 :   bp_pack_value (&bp, speculative_outer_type != NULL, 1);
     672                 :       3043 :   streamer_write_bitpack (&bp);
     673                 :            : 
     674                 :       3043 :   if (outer_type != NULL)
     675                 :       1482 :     stream_write_tree (ob, outer_type, true);
     676                 :       3043 :   if (offset)
     677                 :        561 :     streamer_write_hwi (ob, offset);
     678                 :       3043 :   if (speculative_outer_type != NULL)
     679                 :            :     {
     680                 :       1124 :       stream_write_tree (ob, speculative_outer_type, true);
     681                 :       1124 :       streamer_write_hwi (ob, speculative_offset);
     682                 :            :     }
     683                 :            :   else
     684                 :       1919 :     gcc_assert (!speculative_offset);
     685                 :       3043 : }
     686                 :            : 
     687                 :            : /* Stream in the context from IB and DATA_IN.  */
     688                 :            : 
     689                 :            : void
     690                 :       1360 : ipa_polymorphic_call_context::stream_in (class lto_input_block *ib,
     691                 :            :                                          class data_in *data_in)
     692                 :            : {
     693                 :       1360 :   struct bitpack_d bp = streamer_read_bitpack (ib);
     694                 :            : 
     695                 :       1360 :   invalid = bp_unpack_value (&bp, 1);
     696                 :       1360 :   maybe_in_construction = bp_unpack_value (&bp, 1);
     697                 :       1360 :   maybe_derived_type = bp_unpack_value (&bp, 1);
     698                 :       1360 :   speculative_maybe_derived_type = bp_unpack_value (&bp, 1);
     699                 :       1360 :   dynamic = bp_unpack_value (&bp, 1);
     700                 :       1360 :   bool outer_type_p = bp_unpack_value (&bp, 1);
     701                 :       1360 :   bool offset_p = bp_unpack_value (&bp, 1);
     702                 :       1360 :   bool speculative_outer_type_p = bp_unpack_value (&bp, 1);
     703                 :            : 
     704                 :       1360 :   if (outer_type_p)
     705                 :        687 :     outer_type = stream_read_tree (ib, data_in);
     706                 :            :   else
     707                 :        673 :     outer_type = NULL;
     708                 :       1360 :   if (offset_p)
     709                 :        401 :     offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
     710                 :            :   else
     711                 :        959 :     offset = 0;
     712                 :       1360 :   if (speculative_outer_type_p)
     713                 :            :     {
     714                 :        514 :       speculative_outer_type = stream_read_tree (ib, data_in);
     715                 :        514 :       speculative_offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
     716                 :            :     }
     717                 :            :   else
     718                 :            :     {
     719                 :        846 :       speculative_outer_type = NULL;
     720                 :        846 :       speculative_offset = 0;
     721                 :            :     }
     722                 :       1360 : }
     723                 :            : 
     724                 :            : /* Produce polymorphic call context for call method of instance
     725                 :            :    that is located within BASE (that is assumed to be a decl) at offset OFF. */
     726                 :            : 
     727                 :            : void
     728                 :     495282 : ipa_polymorphic_call_context::set_by_decl (tree base, HOST_WIDE_INT off)
     729                 :            : {
     730                 :     495282 :   gcc_assert (DECL_P (base));
     731                 :     495282 :   clear_speculation ();
     732                 :            : 
     733                 :     495282 :   if (!contains_polymorphic_type_p (TREE_TYPE (base)))
     734                 :            :     {
     735                 :     461177 :       clear_outer_type ();
     736                 :     461177 :       offset = off;
     737                 :     461177 :       return;
     738                 :            :     }
     739                 :      34105 :   outer_type = TYPE_MAIN_VARIANT (TREE_TYPE (base));
     740                 :      34105 :   offset = off;
     741                 :            :   /* Make very conservative assumption that all objects
     742                 :            :      may be in construction. 
     743                 :            :  
     744                 :            :      It is up to caller to revisit this via
     745                 :            :      get_dynamic_type or decl_maybe_in_construction_p.  */
     746                 :      34105 :   maybe_in_construction = true;
     747                 :      34105 :   maybe_derived_type = false;
     748                 :      34105 :   dynamic = false;
     749                 :            : }
     750                 :            : 
     751                 :            : /* CST is an invariant (address of decl), try to get meaningful
     752                 :            :    polymorphic call context for polymorphic call of method 
     753                 :            :    if instance of OTR_TYPE that is located at offset OFF of this invariant.
     754                 :            :    Return FALSE if nothing meaningful can be found.  */
     755                 :            : 
     756                 :            : bool
     757                 :       7061 : ipa_polymorphic_call_context::set_by_invariant (tree cst,
     758                 :            :                                                 tree otr_type,
     759                 :            :                                                 HOST_WIDE_INT off)
     760                 :            : {
     761                 :       7061 :   poly_int64 offset2, size, max_size;
     762                 :       7061 :   bool reverse;
     763                 :       7061 :   tree base;
     764                 :            : 
     765                 :       7061 :   invalid = false;
     766                 :       7061 :   off = 0;
     767                 :       7061 :   clear_outer_type (otr_type);
     768                 :            : 
     769                 :       7061 :   if (TREE_CODE (cst) != ADDR_EXPR)
     770                 :            :     return false;
     771                 :            : 
     772                 :       1976 :   cst = TREE_OPERAND (cst, 0);
     773                 :       1976 :   base = get_ref_base_and_extent (cst, &offset2, &size, &max_size, &reverse);
     774                 :       1976 :   if (!DECL_P (base) || !known_size_p (max_size) || maybe_ne (max_size, size))
     775                 :            :     return false;
     776                 :            : 
     777                 :            :   /* Only type inconsistent programs can have otr_type that is
     778                 :            :      not part of outer type.  */
     779                 :       3952 :   if (otr_type && !contains_type_p (TREE_TYPE (base), off, otr_type))
     780                 :            :     return false;
     781                 :            : 
     782                 :       1975 :   set_by_decl (base, off);
     783                 :       1975 :   return true;
     784                 :            : }
     785                 :            : 
     786                 :            : /* See if OP is SSA name initialized as a copy or by single assignment.
     787                 :            :    If so, walk the SSA graph up.  Because simple PHI conditional is considered
     788                 :            :    copy, GLOBAL_VISITED may be used to avoid infinite loop walking the SSA
     789                 :            :    graph.  */
     790                 :            : 
     791                 :            : static tree
     792                 :    3806950 : walk_ssa_copies (tree op, hash_set<tree> **global_visited = NULL)
     793                 :            : {
     794                 :    3806950 :   hash_set <tree> *visited = NULL;
     795                 :    3806950 :   STRIP_NOPS (op);
     796                 :    4136780 :   while (TREE_CODE (op) == SSA_NAME
     797                 :    1845600 :          && !SSA_NAME_IS_DEFAULT_DEF (op)
     798                 :            :          /* We might be called via fold_stmt during cfgcleanup where
     799                 :            :             SSA form need not be up-to-date.  */
     800                 :    1279920 :          && !name_registered_for_update_p (op) 
     801                 :    5416700 :          && (gimple_assign_single_p (SSA_NAME_DEF_STMT (op))
     802                 :     323258 :              || gimple_code (SSA_NAME_DEF_STMT (op)) == GIMPLE_PHI))
     803                 :            :     {
     804                 :    1008030 :       if (global_visited)
     805                 :            :         {
     806                 :     637143 :           if (!*global_visited)
     807                 :     586792 :             *global_visited = new hash_set<tree>;
     808                 :     637143 :           if ((*global_visited)->add (op))
     809                 :          0 :             goto done;
     810                 :            :         }       
     811                 :            :       else
     812                 :            :         {
     813                 :     370885 :           if (!visited)
     814                 :     370853 :             visited = new hash_set<tree>;
     815                 :     370885 :           if (visited->add (op))
     816                 :          0 :             goto done;
     817                 :            :         }
     818                 :            :       /* Special case
     819                 :            :          if (ptr == 0)
     820                 :            :            ptr = 0;
     821                 :            :          else
     822                 :            :            ptr = ptr.foo;
     823                 :            :          This pattern is implicitly produced for casts to non-primary
     824                 :            :          bases.  When doing context analysis, we do not really care
     825                 :            :          about the case pointer is NULL, because the call will be
     826                 :            :          undefined anyway.  */
     827                 :    1008030 :       if (gimple_code (SSA_NAME_DEF_STMT (op)) == GIMPLE_PHI)
     828                 :            :         {
     829                 :      51371 :           gimple *phi = SSA_NAME_DEF_STMT (op);
     830                 :            : 
     831                 :      51371 :           if (gimple_phi_num_args (phi) > 2)
     832                 :       9034 :             goto done;
     833                 :      42337 :           if (gimple_phi_num_args (phi) == 1)
     834                 :       3227 :             op = gimple_phi_arg_def (phi, 0);
     835                 :      39110 :           else if (integer_zerop (gimple_phi_arg_def (phi, 0)))
     836                 :       4936 :             op = gimple_phi_arg_def (phi, 1);
     837                 :      34174 :           else if (integer_zerop (gimple_phi_arg_def (phi, 1)))
     838                 :       1333 :             op = gimple_phi_arg_def (phi, 0);
     839                 :            :           else
     840                 :      32841 :             goto done;
     841                 :            :         }
     842                 :            :       else
     843                 :            :         {
     844                 :     956657 :           if (gimple_assign_load_p (SSA_NAME_DEF_STMT (op)))
     845                 :     636321 :             goto done;
     846                 :     320336 :           op = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op));
     847                 :            :         }
     848                 :     329832 :       STRIP_NOPS (op);
     849                 :            :     }
     850                 :    3806950 : done:
     851                 :    3806950 :   if (visited)
     852                 :     370853 :     delete (visited);
     853                 :    3806950 :   return op;
     854                 :            : }
     855                 :            : 
     856                 :            : /* Create polymorphic call context from IP invariant CST.
     857                 :            :    This is typically &global_var.
     858                 :            :    OTR_TYPE specify type of polymorphic call or NULL if unknown, OFF
     859                 :            :    is offset of call.  */
     860                 :            : 
     861                 :       7061 : ipa_polymorphic_call_context::ipa_polymorphic_call_context (tree cst,
     862                 :            :                                                             tree otr_type,
     863                 :       7061 :                                                             HOST_WIDE_INT off)
     864                 :            : {
     865                 :       7061 :   clear_speculation ();
     866                 :       7061 :   set_by_invariant (cst, otr_type, off);
     867                 :       7061 : }
     868                 :            : 
     869                 :            : /* Build context for pointer REF contained in FNDECL at statement STMT.
     870                 :            :    if INSTANCE is non-NULL, return pointer to the object described by
     871                 :            :    the context or DECL where context is contained in.  */
     872                 :            : 
     873                 :    1812060 : ipa_polymorphic_call_context::ipa_polymorphic_call_context (tree fndecl,
     874                 :            :                                                             tree ref,
     875                 :            :                                                             gimple *stmt,
     876                 :    1812060 :                                                             tree *instance)
     877                 :            : {
     878                 :    1812060 :   tree otr_type = NULL;
     879                 :    1812060 :   tree base_pointer;
     880                 :    1812060 :   hash_set <tree> *visited = NULL;
     881                 :            : 
     882                 :    1812060 :   if (TREE_CODE (ref) == OBJ_TYPE_REF)
     883                 :            :     {
     884                 :     548814 :       otr_type = obj_type_ref_class (ref);
     885                 :     548814 :       base_pointer = OBJ_TYPE_REF_OBJECT (ref);
     886                 :            :     }
     887                 :            :   else
     888                 :            :     base_pointer = ref;
     889                 :            : 
     890                 :            :   /* Set up basic info in case we find nothing interesting in the analysis.  */
     891                 :    1812060 :   clear_speculation ();
     892                 :    1812060 :   clear_outer_type (otr_type);
     893                 :    1812060 :   invalid = false;
     894                 :            : 
     895                 :            :   /* Walk SSA for outer object.  */
     896                 :    1999940 :   while (true)
     897                 :            :     {
     898                 :    1999940 :       base_pointer = walk_ssa_copies (base_pointer, &visited);
     899                 :    1999940 :       if (TREE_CODE (base_pointer) == ADDR_EXPR)
     900                 :            :         {
     901                 :     762936 :           HOST_WIDE_INT offset2, size;
     902                 :     762936 :           bool reverse;
     903                 :     762936 :           tree base
     904                 :     762936 :             = get_ref_base_and_extent_hwi (TREE_OPERAND (base_pointer, 0),
     905                 :            :                                            &offset2, &size, &reverse);
     906                 :     762936 :           if (!base)
     907                 :            :             break;
     908                 :            : 
     909                 :     758379 :           combine_speculation_with (TYPE_MAIN_VARIANT (TREE_TYPE (base)),
     910                 :     758379 :                                     offset + offset2,
     911                 :            :                                     true,
     912                 :            :                                     NULL /* Do not change outer type.  */);
     913                 :            : 
     914                 :            :           /* If this is a varying address, punt.  */
     915                 :     758379 :           if (TREE_CODE (base) == MEM_REF || DECL_P (base))
     916                 :            :             {
     917                 :            :               /* We found dereference of a pointer.  Type of the pointer
     918                 :            :                  and MEM_REF is meaningless, but we can look further.  */
     919                 :     681188 :               offset_int mem_offset;
     920                 :     681188 :               if (TREE_CODE (base) == MEM_REF
     921                 :     681188 :                   && mem_ref_offset (base).is_constant (&mem_offset))
     922                 :            :                 {
     923                 :     187881 :                   offset_int o = mem_offset * BITS_PER_UNIT;
     924                 :     187881 :                   o += offset;
     925                 :     187881 :                   o += offset2;
     926                 :     187881 :                   if (!wi::fits_shwi_p (o))
     927                 :            :                     break;
     928                 :     187879 :                   base_pointer = TREE_OPERAND (base, 0);
     929                 :     187879 :                   offset = o.to_shwi ();
     930                 :     187879 :                   outer_type = NULL;
     931                 :            :                 }
     932                 :            :               /* We found base object.  In this case the outer_type
     933                 :            :                  is known.  */
     934                 :     493307 :               else if (DECL_P (base))
     935                 :            :                 {
     936                 :     493307 :                   if (visited)
     937                 :        534 :                     delete (visited);
     938                 :            :                   /* Only type inconsistent programs can have otr_type that is
     939                 :            :                      not part of outer type.  */
     940                 :     493307 :                   if (otr_type
     941                 :     496478 :                       && !contains_type_p (TREE_TYPE (base),
     942                 :       3171 :                                            offset + offset2, otr_type))
     943                 :            :                     {
     944                 :          0 :                       invalid = true;
     945                 :          0 :                       if (instance)
     946                 :          0 :                         *instance = base_pointer;
     947                 :     493307 :                       return;
     948                 :            :                     }
     949                 :     493307 :                   set_by_decl (base, offset + offset2);
     950                 :     493307 :                   if (outer_type && maybe_in_construction && stmt)
     951                 :      33045 :                     maybe_in_construction
     952                 :      33045 :                      = decl_maybe_in_construction_p (base,
     953                 :            :                                                      outer_type,
     954                 :            :                                                      stmt,
     955                 :            :                                                      fndecl);
     956                 :     493307 :                   if (instance)
     957                 :     490384 :                     *instance = base;
     958                 :     493307 :                   return;
     959                 :            :                 }
     960                 :            :               else
     961                 :            :                 break;
     962                 :            :             }
     963                 :            :           else
     964                 :            :             break;
     965                 :            :         }
     966                 :    1237010 :       else if (TREE_CODE (base_pointer) == POINTER_PLUS_EXPR
     967                 :    1237010 :                && TREE_CODE (TREE_OPERAND (base_pointer, 1)) == INTEGER_CST)
     968                 :            :         {
     969                 :          0 :           offset_int o
     970                 :          0 :             = offset_int::from (wi::to_wide (TREE_OPERAND (base_pointer, 1)),
     971                 :          0 :                                 SIGNED);
     972                 :          0 :           o *= BITS_PER_UNIT;
     973                 :          0 :           o += offset;
     974                 :          0 :           if (!wi::fits_shwi_p (o))
     975                 :            :             break;
     976                 :          0 :           offset = o.to_shwi ();
     977                 :          0 :           base_pointer = TREE_OPERAND (base_pointer, 0);
     978                 :            :         }
     979                 :            :       else
     980                 :            :         break;
     981                 :            :     }
     982                 :            : 
     983                 :    1318760 :   if (visited)
     984                 :     586258 :     delete (visited);
     985                 :            : 
     986                 :            :   /* Try to determine type of the outer object.  */
     987                 :    1318760 :   if (TREE_CODE (base_pointer) == SSA_NAME
     988                 :    1122570 :       && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
     989                 :    2382250 :       && TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL)
     990                 :            :     {
     991                 :            :       /* See if parameter is THIS pointer of a method.  */
     992                 :     525085 :       if (TREE_CODE (TREE_TYPE (fndecl)) == METHOD_TYPE
     993                 :     844928 :           && SSA_NAME_VAR (base_pointer) == DECL_ARGUMENTS (fndecl))
     994                 :            :         {
     995                 :     252369 :           outer_type
     996                 :     252369 :              = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
     997                 :     252369 :           cgraph_node *node = cgraph_node::get (current_function_decl);
     998                 :     252369 :           gcc_assert (TREE_CODE (outer_type) == RECORD_TYPE
     999                 :            :                       || TREE_CODE (outer_type) == UNION_TYPE);
    1000                 :            : 
    1001                 :            :           /* Handle the case we inlined into a thunk.  In this case
    1002                 :            :              thunk has THIS pointer of type bar, but it really receives
    1003                 :            :              address to its base type foo which sits in bar at 
    1004                 :            :              0-thunk.fixed_offset.  It starts with code that adds
    1005                 :            :              think.fixed_offset to the pointer to compensate for this.
    1006                 :            : 
    1007                 :            :              Because we walked all the way to the beginning of thunk, we now
    1008                 :            :              see pointer &bar-thunk.fixed_offset and need to compensate
    1009                 :            :              for it.  */
    1010                 :     252369 :           if (node->thunk.fixed_offset)
    1011                 :         12 :             offset -= node->thunk.fixed_offset * BITS_PER_UNIT;
    1012                 :            : 
    1013                 :            :           /* Dynamic casting has possibly upcasted the type
    1014                 :            :              in the hierarchy.  In this case outer type is less
    1015                 :            :              informative than inner type and we should forget
    1016                 :            :              about it.  */
    1017                 :     252369 :           if ((otr_type
    1018                 :      91286 :                && !contains_type_p (outer_type, offset,
    1019                 :            :                                     otr_type))
    1020                 :     252214 :               || !contains_polymorphic_type_p (outer_type)
    1021                 :            :               /* If we compile thunk with virtual offset, the THIS pointer
    1022                 :            :                  is adjusted by unknown value.  We can't thus use outer info
    1023                 :            :                  at all.  */
    1024                 :     388351 :               || node->thunk.virtual_offset_p)
    1025                 :            :             {
    1026                 :     116387 :               outer_type = NULL;
    1027                 :     116387 :               if (instance)
    1028                 :     116141 :                 *instance = base_pointer;
    1029                 :     116387 :               return;
    1030                 :            :             }
    1031                 :            : 
    1032                 :     135982 :           dynamic = true;
    1033                 :            : 
    1034                 :            :           /* If the function is constructor or destructor, then
    1035                 :            :              the type is possibly in construction, but we know
    1036                 :            :              it is not derived type.  */
    1037                 :     135982 :           if (DECL_CXX_CONSTRUCTOR_P (fndecl)
    1038                 :     135982 :               || DECL_CXX_DESTRUCTOR_P (fndecl))
    1039                 :            :             {
    1040                 :      19959 :               maybe_in_construction = true;
    1041                 :      19959 :               maybe_derived_type = false;
    1042                 :            :             }
    1043                 :            :           else
    1044                 :            :             {
    1045                 :     116023 :               maybe_derived_type = true;
    1046                 :     116023 :               maybe_in_construction = false;
    1047                 :            :             }
    1048                 :     135982 :           if (instance)
    1049                 :            :             {
    1050                 :            :               /* If method is expanded thunk, we need to apply thunk offset
    1051                 :            :                  to instance pointer.  */
    1052                 :      69027 :               if (node->thunk.virtual_offset_p
    1053                 :      69027 :                   || node->thunk.fixed_offset)
    1054                 :         10 :                 *instance = NULL;
    1055                 :            :               else
    1056                 :      69017 :                 *instance = base_pointer;
    1057                 :            :             }
    1058                 :     135982 :           return;
    1059                 :            :         }
    1060                 :            :       /* Non-PODs passed by value are really passed by invisible
    1061                 :            :          reference.  In this case we also know the type of the
    1062                 :            :          object.  */
    1063                 :     545432 :       if (DECL_BY_REFERENCE (SSA_NAME_VAR (base_pointer)))
    1064                 :            :         {
    1065                 :       9371 :           outer_type
    1066                 :       9371 :              = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
    1067                 :            :           /* Only type inconsistent programs can have otr_type that is
    1068                 :            :              not part of outer type.  */
    1069                 :       9371 :           if (otr_type && !contains_type_p (outer_type, offset,
    1070                 :            :                                             otr_type))
    1071                 :            :             { 
    1072                 :          0 :               invalid = true;
    1073                 :          0 :               if (instance)
    1074                 :          0 :                 *instance = base_pointer;
    1075                 :          0 :               return;
    1076                 :            :             }
    1077                 :            :           /* Non-polymorphic types have no interest for us.  */
    1078                 :       9371 :           else if (!otr_type && !contains_polymorphic_type_p (outer_type))
    1079                 :            :             {
    1080                 :       9268 :               outer_type = NULL;
    1081                 :       9268 :               if (instance)
    1082                 :       9268 :                 *instance = base_pointer;
    1083                 :       9268 :               return;
    1084                 :            :             }
    1085                 :        103 :           maybe_derived_type = false;
    1086                 :        103 :           maybe_in_construction = false;
    1087                 :        103 :           if (instance)
    1088                 :         84 :             *instance = base_pointer;
    1089                 :        103 :           return;
    1090                 :            :         }
    1091                 :            :     }
    1092                 :            : 
    1093                 :    1057020 :   tree base_type = TREE_TYPE (base_pointer);
    1094                 :            : 
    1095                 :    1057020 :   if (TREE_CODE (base_pointer) == SSA_NAME
    1096                 :     860834 :       && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
    1097                 :    1597030 :       && !(TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL
    1098                 :      13320 :            || TREE_CODE (SSA_NAME_VAR (base_pointer)) == RESULT_DECL))
    1099                 :            :     {
    1100                 :        274 :       invalid = true;
    1101                 :        274 :       if (instance)
    1102                 :        156 :         *instance = base_pointer;
    1103                 :        274 :       return;
    1104                 :            :     }
    1105                 :    1056740 :   if (TREE_CODE (base_pointer) == SSA_NAME
    1106                 :     860560 :       && SSA_NAME_DEF_STMT (base_pointer)
    1107                 :    1917300 :       && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer)))
    1108                 :     308607 :     base_type = TREE_TYPE (gimple_assign_rhs1
    1109                 :            :                             (SSA_NAME_DEF_STMT (base_pointer)));
    1110                 :            :  
    1111                 :    1056740 :   if (base_type && POINTER_TYPE_P (base_type))
    1112                 :    1056740 :     combine_speculation_with (TYPE_MAIN_VARIANT (TREE_TYPE (base_type)),
    1113                 :            :                               offset,
    1114                 :            :                               true, NULL /* Do not change type here */);
    1115                 :            :   /* TODO: There are multiple ways to derive a type.  For instance
    1116                 :            :      if BASE_POINTER is passed to an constructor call prior our reference.
    1117                 :            :      We do not make this type of flow sensitive analysis yet.  */
    1118                 :    1056740 :   if (instance)
    1119                 :     714262 :     *instance = base_pointer;
    1120                 :            :   return;
    1121                 :            : }
    1122                 :            : 
    1123                 :            : /* Structure to be passed in between detect_type_change and
    1124                 :            :    check_stmt_for_type_change.  */
    1125                 :            : 
    1126                 :            : struct type_change_info
    1127                 :            : {
    1128                 :            :   /* Offset into the object where there is the virtual method pointer we are
    1129                 :            :      looking for.  */
    1130                 :            :   HOST_WIDE_INT offset;
    1131                 :            :   /* The declaration or SSA_NAME pointer of the base that we are checking for
    1132                 :            :      type change.  */
    1133                 :            :   tree instance;
    1134                 :            :   /* The reference to virtual table pointer used.  */
    1135                 :            :   tree vtbl_ptr_ref;
    1136                 :            :   tree otr_type;
    1137                 :            :   /* If we actually can tell the type that the object has changed to, it is
    1138                 :            :      stored in this field.  Otherwise it remains NULL_TREE.  */
    1139                 :            :   tree known_current_type;
    1140                 :            :   HOST_WIDE_INT known_current_offset;
    1141                 :            : 
    1142                 :            :   /* Set to nonzero if we possibly missed some dynamic type changes and we
    1143                 :            :      should consider the set to be speculative.  */
    1144                 :            :   unsigned speculative;
    1145                 :            : 
    1146                 :            :   /* Set to true if dynamic type change has been detected.  */
    1147                 :            :   bool type_maybe_changed;
    1148                 :            :   /* Set to true if multiple types have been encountered.  known_current_type
    1149                 :            :      must be disregarded in that case.  */
    1150                 :            :   bool multiple_types_encountered;
    1151                 :            :   bool seen_unanalyzed_store;
    1152                 :            : };
    1153                 :            : 
    1154                 :            : /* Return true if STMT is not call and can modify a virtual method table pointer.
    1155                 :            :    We take advantage of fact that vtable stores must appear within constructor
    1156                 :            :    and destructor functions.  */
    1157                 :            : 
    1158                 :            : static bool
    1159                 :    3075190 : noncall_stmt_may_be_vtbl_ptr_store (gimple *stmt)
    1160                 :            : {
    1161                 :    3075190 :   if (is_gimple_assign (stmt))
    1162                 :            :     {
    1163                 :    3030100 :       tree lhs = gimple_assign_lhs (stmt);
    1164                 :            : 
    1165                 :    3030100 :       if (gimple_clobber_p (stmt))
    1166                 :            :         return false;
    1167                 :    2406980 :       if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
    1168                 :            :         {
    1169                 :    2107400 :           if (flag_strict_aliasing
    1170                 :    2107400 :               && !POINTER_TYPE_P (TREE_TYPE (lhs)))
    1171                 :            :             return false;
    1172                 :            : 
    1173                 :    1029760 :           if (TREE_CODE (lhs) == COMPONENT_REF
    1174                 :    1029760 :               && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
    1175                 :            :             return false;
    1176                 :            :           /* In the future we might want to use get_ref_base_and_extent to find
    1177                 :            :              if there is a field corresponding to the offset and if so, proceed
    1178                 :            :              almost like if it was a component ref.  */
    1179                 :            :         }
    1180                 :            :     }
    1181                 :            : 
    1182                 :            :   /* Code unification may mess with inline stacks.  */
    1183                 :     568235 :   if (cfun->after_inlining)
    1184                 :            :     return true;
    1185                 :            : 
    1186                 :            :   /* Walk the inline stack and watch out for ctors/dtors.
    1187                 :            :      TODO: Maybe we can require the store to appear in toplevel
    1188                 :            :      block of CTOR/DTOR.  */
    1189                 :    5122360 :   for (tree block = gimple_block (stmt); block && TREE_CODE (block) == BLOCK;
    1190                 :    2011320 :        block = BLOCK_SUPERCONTEXT (block))
    1191                 :    2037130 :     if (BLOCK_ABSTRACT_ORIGIN (block)
    1192                 :    2037130 :         && TREE_CODE (block_ultimate_origin (block)) == FUNCTION_DECL)
    1193                 :      25813 :       return inlined_polymorphic_ctor_dtor_block_p (block, false);
    1194                 :     524047 :   return (TREE_CODE (TREE_TYPE (current_function_decl)) == METHOD_TYPE
    1195                 :     524047 :           && (DECL_CXX_CONSTRUCTOR_P (current_function_decl)
    1196                 :      20291 :               || DECL_CXX_DESTRUCTOR_P (current_function_decl)));
    1197                 :            : }
    1198                 :            : 
    1199                 :            : /* If STMT can be proved to be an assignment to the virtual method table
    1200                 :            :    pointer of ANALYZED_OBJ and the type associated with the new table
    1201                 :            :    identified, return the type.  Otherwise return NULL_TREE if type changes
    1202                 :            :    in unknown way or ERROR_MARK_NODE if type is unchanged.  */
    1203                 :            : 
    1204                 :            : static tree
    1205                 :      35512 : extr_type_from_vtbl_ptr_store (gimple *stmt, struct type_change_info *tci,
    1206                 :            :                                HOST_WIDE_INT *type_offset)
    1207                 :            : {
    1208                 :      35512 :   poly_int64 offset, size, max_size;
    1209                 :      35512 :   tree lhs, rhs, base;
    1210                 :      35512 :   bool reverse;
    1211                 :            : 
    1212                 :      35512 :   if (!gimple_assign_single_p (stmt))
    1213                 :            :     return NULL_TREE;
    1214                 :            : 
    1215                 :      35280 :   lhs = gimple_assign_lhs (stmt);
    1216                 :      35280 :   rhs = gimple_assign_rhs1 (stmt);
    1217                 :      35280 :   if (TREE_CODE (lhs) != COMPONENT_REF
    1218                 :      35280 :       || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
    1219                 :            :      {
    1220                 :       4087 :         if (dump_file)
    1221                 :          0 :           fprintf (dump_file, "  LHS is not virtual table.\n");
    1222                 :       4087 :         return NULL_TREE;
    1223                 :            :      }
    1224                 :            : 
    1225                 :      31193 :   if (tci->vtbl_ptr_ref && operand_equal_p (lhs, tci->vtbl_ptr_ref, 0))
    1226                 :            :     ;
    1227                 :            :   else
    1228                 :            :     {
    1229                 :      31086 :       base = get_ref_base_and_extent (lhs, &offset, &size, &max_size, &reverse);
    1230                 :      31086 :       if (DECL_P (tci->instance))
    1231                 :            :         {
    1232                 :       1130 :           if (base != tci->instance)
    1233                 :            :             {
    1234                 :        201 :               if (dump_file)
    1235                 :            :                 {
    1236                 :          0 :                   fprintf (dump_file, "    base:");
    1237                 :          0 :                   print_generic_expr (dump_file, base, TDF_SLIM);
    1238                 :          0 :                   fprintf (dump_file, " does not match instance:");
    1239                 :          0 :                   print_generic_expr (dump_file, tci->instance, TDF_SLIM);
    1240                 :          0 :                   fprintf (dump_file, "\n");
    1241                 :            :                 }
    1242                 :        201 :               return NULL_TREE;
    1243                 :            :             }
    1244                 :            :         }
    1245                 :      29956 :       else if (TREE_CODE (base) == MEM_REF)
    1246                 :            :         {
    1247                 :      23391 :           if (!operand_equal_p (tci->instance, TREE_OPERAND (base, 0), 0))
    1248                 :            :             {
    1249                 :      15242 :               if (dump_file)
    1250                 :            :                 {
    1251                 :          0 :                   fprintf (dump_file, "    base mem ref:");
    1252                 :          0 :                   print_generic_expr (dump_file, base, TDF_SLIM);
    1253                 :          0 :                   fprintf (dump_file, " does not match instance:");
    1254                 :          0 :                   print_generic_expr (dump_file, tci->instance, TDF_SLIM);
    1255                 :          0 :                   fprintf (dump_file, "\n");
    1256                 :            :                 }
    1257                 :      15242 :               return NULL_TREE;
    1258                 :            :             }
    1259                 :       8149 :           if (!integer_zerop (TREE_OPERAND (base, 1)))
    1260                 :            :             {
    1261                 :       1695 :               if (!tree_fits_shwi_p (TREE_OPERAND (base, 1)))
    1262                 :            :                 {
    1263                 :          0 :                   if (dump_file)
    1264                 :            :                     {
    1265                 :          0 :                       fprintf (dump_file, "    base mem ref:");
    1266                 :          0 :                       print_generic_expr (dump_file, base, TDF_SLIM);
    1267                 :          0 :                       fprintf (dump_file, " has non-representable offset:");
    1268                 :          0 :                       print_generic_expr (dump_file, tci->instance, TDF_SLIM);
    1269                 :          0 :                       fprintf (dump_file, "\n");
    1270                 :            :                     }
    1271                 :          0 :                   return NULL_TREE;
    1272                 :            :                 }
    1273                 :            :               else
    1274                 :       1695 :                 offset += tree_to_shwi (TREE_OPERAND (base, 1)) * BITS_PER_UNIT;
    1275                 :            :             }
    1276                 :            :         }
    1277                 :       6565 :       else if (!operand_equal_p (tci->instance, base, 0)
    1278                 :       6565 :                || tci->offset)
    1279                 :            :         {
    1280                 :       6565 :           if (dump_file)
    1281                 :            :             {
    1282                 :          2 :               fprintf (dump_file, "    base:");
    1283                 :          2 :               print_generic_expr (dump_file, base, TDF_SLIM);
    1284                 :          2 :               fprintf (dump_file, " does not match instance:");
    1285                 :          2 :               print_generic_expr (dump_file, tci->instance, TDF_SLIM);
    1286                 :          2 :               fprintf (dump_file, " with offset %i\n", (int)tci->offset);
    1287                 :            :             }
    1288                 :       6586 :           return tci->offset > POINTER_SIZE ? error_mark_node : NULL_TREE;
    1289                 :            :         }
    1290                 :       9078 :       if (maybe_ne (offset, tci->offset)
    1291                 :       9366 :           || maybe_ne (size, POINTER_SIZE)
    1292                 :      18444 :           || maybe_ne (max_size, POINTER_SIZE))
    1293                 :            :         {
    1294                 :         36 :           if (dump_file)
    1295                 :            :             {
    1296                 :          0 :               fprintf (dump_file, "    wrong offset ");
    1297                 :          0 :               print_dec (offset, dump_file);
    1298                 :          0 :               fprintf (dump_file, "!=%i or size ", (int) tci->offset);
    1299                 :          0 :               print_dec (size, dump_file);
    1300                 :          0 :               fprintf (dump_file, "\n");
    1301                 :            :             }
    1302                 :         36 :           return (known_le (offset + POINTER_SIZE, tci->offset)
    1303                 :          0 :                   || (known_size_p (max_size)
    1304                 :          0 :                       && known_gt (tci->offset + POINTER_SIZE,
    1305                 :            :                                    offset + max_size))
    1306                 :         36 :                   ? error_mark_node : NULL);
    1307                 :            :         }
    1308                 :            :     }
    1309                 :            : 
    1310                 :       9149 :   tree vtable;
    1311                 :       9149 :   unsigned HOST_WIDE_INT offset2;
    1312                 :            : 
    1313                 :       9149 :   if (!vtable_pointer_value_to_vtable (rhs, &vtable, &offset2))
    1314                 :            :     {
    1315                 :         84 :       if (dump_file)
    1316                 :          5 :         fprintf (dump_file, "    Failed to lookup binfo\n");
    1317                 :         84 :       return NULL;
    1318                 :            :     }
    1319                 :            : 
    1320                 :       9065 :   tree binfo = subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
    1321                 :            :                                                offset2, vtable);
    1322                 :       9065 :   if (!binfo)
    1323                 :            :     {
    1324                 :        834 :       if (dump_file)
    1325                 :         12 :         fprintf (dump_file, "    Construction vtable used\n");
    1326                 :            :       /* FIXME: We should support construction contexts.  */
    1327                 :        834 :       return NULL;
    1328                 :            :     }
    1329                 :            :  
    1330                 :       8231 :   *type_offset = tree_to_shwi (BINFO_OFFSET (binfo)) * BITS_PER_UNIT;
    1331                 :       8231 :   return DECL_CONTEXT (vtable);
    1332                 :            : }
    1333                 :            : 
    1334                 :            : /* Record dynamic type change of TCI to TYPE.  */
    1335                 :            : 
    1336                 :            : static void
    1337                 :      88496 : record_known_type (struct type_change_info *tci, tree type, HOST_WIDE_INT offset)
    1338                 :            : {
    1339                 :      88496 :   if (dump_file)
    1340                 :            :     {
    1341                 :         50 :       if (type)
    1342                 :            :         {
    1343                 :         50 :           fprintf (dump_file, "  Recording type: ");
    1344                 :         50 :           print_generic_expr (dump_file, type, TDF_SLIM);
    1345                 :         50 :           fprintf (dump_file, " at offset %i\n", (int)offset);
    1346                 :            :         }
    1347                 :            :      else
    1348                 :          0 :        fprintf (dump_file, "  Recording unknown type\n");
    1349                 :            :     }
    1350                 :            : 
    1351                 :            :   /* If we found a constructor of type that is not polymorphic or
    1352                 :            :      that may contain the type in question as a field (not as base),
    1353                 :            :      restrict to the inner class first to make type matching bellow
    1354                 :            :      happier.  */
    1355                 :      88496 :   if (type
    1356                 :      88496 :       && (offset
    1357                 :      83375 :           || (TREE_CODE (type) != RECORD_TYPE
    1358                 :      83375 :               || !TYPE_BINFO (type)
    1359                 :      83015 :               || !polymorphic_type_binfo_p (TYPE_BINFO (type)))))
    1360                 :            :     {
    1361                 :      78911 :       ipa_polymorphic_call_context context;
    1362                 :            : 
    1363                 :      78911 :       context.offset = offset;
    1364                 :      78911 :       context.outer_type = type;
    1365                 :      78911 :       context.maybe_in_construction = false;
    1366                 :      78911 :       context.maybe_derived_type = false;
    1367                 :      78911 :       context.dynamic = true;
    1368                 :            :       /* If we failed to find the inner type, we know that the call
    1369                 :            :          would be undefined for type produced here.  */
    1370                 :      78911 :       if (!context.restrict_to_inner_class (tci->otr_type))
    1371                 :            :         {
    1372                 :        681 :           if (dump_file)
    1373                 :          0 :             fprintf (dump_file, "  Ignoring; does not contain otr_type\n");
    1374                 :        681 :           return;
    1375                 :            :         }
    1376                 :            :       /* Watch for case we reached an POD type and anticipate placement
    1377                 :            :          new.  */
    1378                 :      78230 :       if (!context.maybe_derived_type)
    1379                 :            :         {
    1380                 :       2152 :           type = context.outer_type;
    1381                 :       2152 :           offset = context.offset;
    1382                 :            :         }
    1383                 :            :     }
    1384                 :      87815 :   if (tci->type_maybe_changed
    1385                 :      87815 :       && (!types_same_for_odr (type, tci->known_current_type)
    1386                 :          0 :           || offset != tci->known_current_offset))
    1387                 :        670 :     tci->multiple_types_encountered = true;
    1388                 :      87815 :   tci->known_current_type = TYPE_MAIN_VARIANT (type);
    1389                 :      87815 :   tci->known_current_offset = offset;
    1390                 :      87815 :   tci->type_maybe_changed = true;
    1391                 :            : }
    1392                 :            : 
    1393                 :            : 
    1394                 :            : /* The maximum number of may-defs we visit when looking for a must-def
    1395                 :            :    that changes the dynamic type in check_stmt_for_type_change.  Tuned
    1396                 :            :    after the PR12392 testcase which unlimited spends 40% time within
    1397                 :            :    these alias walks and 8% with the following limit.  */
    1398                 :            : 
    1399                 :            : static inline bool
    1400                 :    9798900 : csftc_abort_walking_p (unsigned speculative)
    1401                 :            : {
    1402                 :    9798900 :   unsigned max = param_max_speculative_devirt_maydefs;
    1403                 :    9798900 :   return speculative > max ? true : false;
    1404                 :            : }
    1405                 :            : 
    1406                 :            : /* Callback of walk_aliased_vdefs and a helper function for
    1407                 :            :    detect_type_change to check whether a particular statement may modify
    1408                 :            :    the virtual table pointer, and if possible also determine the new type of
    1409                 :            :    the (sub-)object.  It stores its result into DATA, which points to a
    1410                 :            :    type_change_info structure.  */
    1411                 :            : 
    1412                 :            : static bool
    1413                 :   12962400 : check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
    1414                 :            : {
    1415                 :   12962400 :   gimple *stmt = SSA_NAME_DEF_STMT (vdef);
    1416                 :   12962400 :   struct type_change_info *tci = (struct type_change_info *) data;
    1417                 :   12962400 :   tree fn;
    1418                 :            : 
    1419                 :            :   /* If we already gave up, just terminate the rest of walk.  */
    1420                 :   12962400 :   if (tci->multiple_types_encountered)
    1421                 :            :     return true;
    1422                 :            : 
    1423                 :   12954600 :   if (is_gimple_call (stmt))
    1424                 :            :     {
    1425                 :    9879450 :       if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
    1426                 :            :         return false;
    1427                 :            : 
    1428                 :            :       /* Check for a constructor call.  */
    1429                 :    9879160 :       if ((fn = gimple_call_fndecl (stmt)) != NULL_TREE
    1430                 :    8903430 :           && DECL_CXX_CONSTRUCTOR_P (fn)
    1431                 :     754186 :           && TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
    1432                 :   10633400 :           && gimple_call_num_args (stmt))
    1433                 :            :       {
    1434                 :     754186 :         tree op = walk_ssa_copies (gimple_call_arg (stmt, 0));
    1435                 :     754186 :         tree type = TYPE_METHOD_BASETYPE (TREE_TYPE (fn));
    1436                 :     754186 :         HOST_WIDE_INT offset = 0;
    1437                 :     754186 :         bool reverse;
    1438                 :            : 
    1439                 :     754186 :         if (dump_file)
    1440                 :            :           {
    1441                 :         45 :             fprintf (dump_file, "  Checking constructor call: ");
    1442                 :         45 :             print_gimple_stmt (dump_file, stmt, 0);
    1443                 :            :           }
    1444                 :            : 
    1445                 :            :         /* See if THIS parameter seems like instance pointer.  */
    1446                 :     754186 :         if (TREE_CODE (op) == ADDR_EXPR)
    1447                 :            :           {
    1448                 :     726624 :             HOST_WIDE_INT size;
    1449                 :     726624 :             op = get_ref_base_and_extent_hwi (TREE_OPERAND (op, 0),
    1450                 :            :                                               &offset, &size, &reverse);
    1451                 :     726624 :             if (!op)
    1452                 :            :               {
    1453                 :          0 :                 tci->speculative++;
    1454                 :          0 :                 return csftc_abort_walking_p (tci->speculative);
    1455                 :            :               }
    1456                 :     726624 :             if (TREE_CODE (op) == MEM_REF)
    1457                 :            :               {
    1458                 :      39516 :                 if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
    1459                 :            :                   {
    1460                 :          0 :                     tci->speculative++;
    1461                 :          0 :                     return csftc_abort_walking_p (tci->speculative);
    1462                 :            :                   }
    1463                 :      39516 :                 offset += tree_to_shwi (TREE_OPERAND (op, 1))
    1464                 :      39516 :                           * BITS_PER_UNIT;
    1465                 :      39516 :                 op = TREE_OPERAND (op, 0);
    1466                 :            :               }
    1467                 :     687108 :             else if (DECL_P (op))
    1468                 :            :               ;
    1469                 :            :             else
    1470                 :            :               {
    1471                 :          0 :                 tci->speculative++;
    1472                 :          0 :                 return csftc_abort_walking_p (tci->speculative);
    1473                 :            :               }
    1474                 :     726624 :             op = walk_ssa_copies (op);
    1475                 :            :           }
    1476                 :     754186 :         if (operand_equal_p (op, tci->instance, 0)
    1477                 :     123747 :             && TYPE_SIZE (type)
    1478                 :     123747 :             && TREE_CODE (TYPE_SIZE (type)) == INTEGER_CST
    1479                 :     123747 :             && tree_fits_shwi_p (TYPE_SIZE (type))
    1480                 :     123747 :             && tree_to_shwi (TYPE_SIZE (type)) + offset > tci->offset
    1481                 :            :             /* Some inlined constructors may look as follows:
    1482                 :            :                   _3 = operator new (16);
    1483                 :            :                   MEM[(struct  &)_3] ={v} {CLOBBER};
    1484                 :            :                   MEM[(struct CompositeClass *)_3]._vptr.CompositeClass
    1485                 :            :                     = &MEM[(void *)&_ZTV14CompositeClass + 16B];
    1486                 :            :                   _7 = &MEM[(struct CompositeClass *)_3].object;
    1487                 :            :                   EmptyClass::EmptyClass (_7);
    1488                 :            : 
    1489                 :            :                When determining dynamic type of _3 and because we stop at first
    1490                 :            :                dynamic type found, we would stop on EmptyClass::EmptyClass (_7).
    1491                 :            :                In this case the emptyclass is not even polymorphic and we miss
    1492                 :            :                it is contained in an outer type that is polymorphic.  */
    1493                 :            : 
    1494                 :     849827 :             && (tci->offset == offset || contains_polymorphic_type_p (type)))
    1495                 :            :           {
    1496                 :      80265 :             record_known_type (tci, type, tci->offset - offset);
    1497                 :      80265 :             return true;
    1498                 :            :           }
    1499                 :            :       }
    1500                 :            :      /* Calls may possibly change dynamic type by placement new. Assume
    1501                 :            :         it will not happen, but make result speculative only.  */
    1502                 :    9798900 :      if (dump_file)
    1503                 :            :         {
    1504                 :        876 :           fprintf (dump_file, "  Function call may change dynamic type:");
    1505                 :        876 :           print_gimple_stmt (dump_file, stmt, 0);
    1506                 :            :         }
    1507                 :    9798900 :      tci->speculative++;
    1508                 :    9798900 :      return csftc_abort_walking_p (tci->speculative);
    1509                 :            :    }
    1510                 :            :   /* Check for inlined virtual table store.  */
    1511                 :    3075190 :   else if (noncall_stmt_may_be_vtbl_ptr_store (stmt))
    1512                 :            :     {
    1513                 :      35512 :       tree type;
    1514                 :      35512 :       HOST_WIDE_INT offset = 0;
    1515                 :      35512 :       if (dump_file)
    1516                 :            :         {
    1517                 :         45 :           fprintf (dump_file, "  Checking vtbl store: ");
    1518                 :         45 :           print_gimple_stmt (dump_file, stmt, 0);
    1519                 :            :         }
    1520                 :            : 
    1521                 :      35512 :       type = extr_type_from_vtbl_ptr_store (stmt, tci, &offset);
    1522                 :      35512 :       if (type == error_mark_node)
    1523                 :            :         return false;
    1524                 :      43707 :       gcc_assert (!type || TYPE_MAIN_VARIANT (type) == type);
    1525                 :      35476 :       if (!type)
    1526                 :            :         {
    1527                 :      27245 :           if (dump_file)
    1528                 :         19 :             fprintf (dump_file, "  Unanalyzed store may change type.\n");
    1529                 :      27245 :           tci->seen_unanalyzed_store = true;
    1530                 :      27245 :           tci->speculative++;
    1531                 :            :         }
    1532                 :            :       else
    1533                 :       8231 :         record_known_type (tci, type, offset);
    1534                 :      35476 :       return true;
    1535                 :            :     }
    1536                 :            :   else
    1537                 :            :     return false;
    1538                 :            : }
    1539                 :            : 
    1540                 :            : /* THIS is polymorphic call context obtained from get_polymorphic_context.
    1541                 :            :    OTR_OBJECT is pointer to the instance returned by OBJ_TYPE_REF_OBJECT.
    1542                 :            :    INSTANCE is pointer to the outer instance as returned by
    1543                 :            :    get_polymorphic_context.  To avoid creation of temporary expressions,
    1544                 :            :    INSTANCE may also be an declaration of get_polymorphic_context found the
    1545                 :            :    value to be in static storage.
    1546                 :            : 
    1547                 :            :    If the type of instance is not fully determined
    1548                 :            :    (either OUTER_TYPE is unknown or MAYBE_IN_CONSTRUCTION/INCLUDE_DERIVED_TYPES
    1549                 :            :    is set), try to walk memory writes and find the actual construction of the
    1550                 :            :    instance.
    1551                 :            : 
    1552                 :            :    Return true if memory is unchanged from function entry.
    1553                 :            : 
    1554                 :            :    We do not include this analysis in the context analysis itself, because
    1555                 :            :    it needs memory SSA to be fully built and the walk may be expensive.
    1556                 :            :    So it is not suitable for use withing fold_stmt and similar uses.
    1557                 :            : 
    1558                 :            :    AA_WALK_BUDGET_P, if not NULL, is how statements we should allow
    1559                 :            :    walk_aliased_vdefs to examine.  The value should be decremented by the
    1560                 :            :    number of statements we examined or set to zero if exhausted.  */
    1561                 :            : 
    1562                 :            : bool
    1563                 :    1399320 : ipa_polymorphic_call_context::get_dynamic_type (tree instance,
    1564                 :            :                                                 tree otr_object,
    1565                 :            :                                                 tree otr_type,
    1566                 :            :                                                 gimple *call,
    1567                 :            :                                                 unsigned *aa_walk_budget_p)
    1568                 :            : {
    1569                 :    1399320 :   struct type_change_info tci;
    1570                 :    1399320 :   ao_ref ao;
    1571                 :    1399320 :   bool function_entry_reached = false;
    1572                 :    1399320 :   tree instance_ref = NULL;
    1573                 :    1399320 :   gimple *stmt = call;
    1574                 :            :   /* Remember OFFSET before it is modified by restrict_to_inner_class.
    1575                 :            :      This is because we do not update INSTANCE when walking inwards.  */
    1576                 :    1399320 :   HOST_WIDE_INT instance_offset = offset;
    1577                 :    1399320 :   tree instance_outer_type = outer_type;
    1578                 :            : 
    1579                 :    1399320 :   if (!instance)
    1580                 :            :     return false;
    1581                 :            : 
    1582                 :    1399310 :   if (otr_type)
    1583                 :     136073 :     otr_type = TYPE_MAIN_VARIANT (otr_type);
    1584                 :            : 
    1585                 :            :   /* Walk into inner type. This may clear maybe_derived_type and save us
    1586                 :            :      from useless work.  It also makes later comparisons with static type
    1587                 :            :      easier.  */
    1588                 :    1399310 :   if (outer_type && otr_type)
    1589                 :            :     {
    1590                 :     117381 :       if (!restrict_to_inner_class (otr_type))
    1591                 :            :         return false;
    1592                 :            :     }
    1593                 :            : 
    1594                 :    1399310 :   if (!maybe_in_construction && !maybe_derived_type)
    1595                 :            :     return false;
    1596                 :            : 
    1597                 :            :   /* If we are in fact not looking at any object object or the instance is
    1598                 :            :      some placement new into a random load, give up straight away.  */
    1599                 :    1370520 :   if (TREE_CODE (instance) == MEM_REF)
    1600                 :            :     return false;
    1601                 :            : 
    1602                 :            :   /* We need to obtain reference to virtual table pointer.  It is better
    1603                 :            :      to look it up in the code rather than build our own.  This require bit
    1604                 :            :      of pattern matching, but we end up verifying that what we found is
    1605                 :            :      correct. 
    1606                 :            : 
    1607                 :            :      What we pattern match is:
    1608                 :            : 
    1609                 :            :        tmp = instance->_vptr.A;   // vtbl ptr load
    1610                 :            :        tmp2 = tmp[otr_token];     // vtable lookup
    1611                 :            :        OBJ_TYPE_REF(tmp2;instance->0) (instance);
    1612                 :            :  
    1613                 :            :      We want to start alias oracle walk from vtbl pointer load,
    1614                 :            :      but we may not be able to identify it, for example, when PRE moved the
    1615                 :            :      load around.  */
    1616                 :            : 
    1617                 :    1370520 :   if (gimple_code (call) == GIMPLE_CALL)
    1618                 :            :     {
    1619                 :    1370520 :       tree ref = gimple_call_fn (call);
    1620                 :    1370520 :       bool reverse;
    1621                 :            : 
    1622                 :    1370520 :       if (TREE_CODE (ref) == OBJ_TYPE_REF)
    1623                 :            :         {
    1624                 :     163293 :           ref = OBJ_TYPE_REF_EXPR (ref);
    1625                 :     163293 :           ref = walk_ssa_copies (ref);
    1626                 :            : 
    1627                 :            :           /* If call target is already known, no need to do the expensive
    1628                 :            :              memory walk.  */
    1629                 :     163293 :           if (is_gimple_min_invariant (ref))
    1630                 :          0 :             return false;
    1631                 :            : 
    1632                 :            :           /* Check if definition looks like vtable lookup.  */
    1633                 :     163293 :           if (TREE_CODE (ref) == SSA_NAME
    1634                 :     163293 :               && !SSA_NAME_IS_DEFAULT_DEF (ref)
    1635                 :     163293 :               && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref))
    1636                 :     326199 :               && TREE_CODE (gimple_assign_rhs1
    1637                 :            :                              (SSA_NAME_DEF_STMT (ref))) == MEM_REF)
    1638                 :            :             {
    1639                 :     162906 :               ref = get_base_address
    1640                 :     162906 :                      (TREE_OPERAND (gimple_assign_rhs1
    1641                 :            :                                      (SSA_NAME_DEF_STMT (ref)), 0));
    1642                 :     162906 :               ref = walk_ssa_copies (ref);
    1643                 :            :               /* Find base address of the lookup and see if it looks like
    1644                 :            :                  vptr load.  */
    1645                 :     162906 :               if (TREE_CODE (ref) == SSA_NAME
    1646                 :     162820 :                   && !SSA_NAME_IS_DEFAULT_DEF (ref)
    1647                 :     325726 :                   && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref)))
    1648                 :            :                 {
    1649                 :     162384 :                   HOST_WIDE_INT offset2, size;
    1650                 :     162384 :                   tree ref_exp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ref));
    1651                 :     162384 :                   tree base_ref
    1652                 :     162384 :                     = get_ref_base_and_extent_hwi (ref_exp, &offset2,
    1653                 :            :                                                    &size, &reverse);
    1654                 :            : 
    1655                 :            :                   /* Finally verify that what we found looks like read from
    1656                 :            :                      OTR_OBJECT or from INSTANCE with offset OFFSET.  */
    1657                 :     162384 :                   if (base_ref
    1658                 :     162384 :                       && ((TREE_CODE (base_ref) == MEM_REF
    1659                 :     162124 :                            && ((offset2 == instance_offset
    1660                 :     160338 :                                 && TREE_OPERAND (base_ref, 0) == instance)
    1661                 :      13637 :                                || (!offset2
    1662                 :      13637 :                                    && TREE_OPERAND (base_ref, 0)
    1663                 :            :                                       == otr_object)))
    1664                 :      12094 :                           || (DECL_P (instance) && base_ref == instance
    1665                 :        183 :                               && offset2 == instance_offset)))
    1666                 :            :                     {
    1667                 :     150473 :                       stmt = SSA_NAME_DEF_STMT (ref);
    1668                 :     150473 :                       instance_ref = ref_exp;
    1669                 :            :                     }
    1670                 :            :                 }
    1671                 :            :             }
    1672                 :            :         }
    1673                 :            :     }
    1674                 :            :  
    1675                 :            :   /* If we failed to look up the reference in code, build our own.  */
    1676                 :    1370520 :   if (!instance_ref)
    1677                 :            :     {
    1678                 :            :       /* If the statement in question does not use memory, we can't tell
    1679                 :            :          anything.  */
    1680                 :    2440090 :       if (!gimple_vuse (stmt))
    1681                 :            :         return false;
    1682                 :    1216770 :       ao_ref_init_from_ptr_and_size (&ao, otr_object, NULL);
    1683                 :            :     }
    1684                 :            :   else
    1685                 :            :   /* Otherwise use the real reference.  */
    1686                 :     150473 :     ao_ref_init (&ao, instance_ref);
    1687                 :            : 
    1688                 :            :   /* We look for vtbl pointer read.  */
    1689                 :    1529490 :   ao.size = POINTER_SIZE;
    1690                 :    1367240 :   ao.max_size = ao.size;
    1691                 :            :   /* We are looking for stores to vptr pointer within the instance of
    1692                 :            :      outer type.
    1693                 :            :      TODO: The vptr pointer type is globally known, we probably should
    1694                 :            :      keep it and do that even when otr_type is unknown.  */
    1695                 :    1367240 :   if (otr_type)
    1696                 :            :     {
    1697                 :     136029 :       ao.base_alias_set
    1698                 :     253366 :         = get_alias_set (outer_type ? outer_type : otr_type);
    1699                 :     136029 :       ao.ref_alias_set
    1700                 :     136029 :         = get_alias_set (TREE_TYPE (BINFO_VTABLE (TYPE_BINFO (otr_type))));
    1701                 :            :     }
    1702                 :            : 
    1703                 :    1367240 :   if (dump_file)
    1704                 :            :     {
    1705                 :        698 :       fprintf (dump_file, "Determining dynamic type for call: ");
    1706                 :        698 :       print_gimple_stmt (dump_file, call, 0);
    1707                 :        698 :       fprintf (dump_file, "  Starting walk at: ");
    1708                 :        698 :       print_gimple_stmt (dump_file, stmt, 0);
    1709                 :        698 :       fprintf (dump_file, "  instance pointer: ");
    1710                 :        698 :       print_generic_expr (dump_file, otr_object, TDF_SLIM);
    1711                 :        698 :       fprintf (dump_file, "  Outer instance pointer: ");
    1712                 :        698 :       print_generic_expr (dump_file, instance, TDF_SLIM);
    1713                 :        698 :       fprintf (dump_file, " offset: %i (bits)", (int)instance_offset);
    1714                 :        698 :       fprintf (dump_file, " vtbl reference: ");
    1715                 :        698 :       print_generic_expr (dump_file, instance_ref, TDF_SLIM);
    1716                 :        698 :       fprintf (dump_file, "\n");
    1717                 :            :     }
    1718                 :            : 
    1719                 :    1367240 :   tci.offset = instance_offset;
    1720                 :    1367240 :   tci.instance = instance;
    1721                 :    1367240 :   tci.vtbl_ptr_ref = instance_ref;
    1722                 :    1367240 :   tci.known_current_type = NULL_TREE;
    1723                 :    1367240 :   tci.known_current_offset = 0;
    1724                 :    1367240 :   tci.otr_type = otr_type;
    1725                 :    1367240 :   tci.type_maybe_changed = false;
    1726                 :    1367240 :   tci.multiple_types_encountered = false;
    1727                 :    1367240 :   tci.speculative = 0;
    1728                 :    1367240 :   tci.seen_unanalyzed_store = false;
    1729                 :            : 
    1730                 :    1367240 :   unsigned aa_walk_budget = 0;
    1731                 :    1367240 :   if (aa_walk_budget_p)
    1732                 :    1248550 :     aa_walk_budget = *aa_walk_budget_p + 1;
    1733                 :            : 
    1734                 :    1367240 :   int walked
    1735                 :    1367240 :    = walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
    1736                 :            :                          &tci, NULL, &function_entry_reached, aa_walk_budget);
    1737                 :            : 
    1738                 :            :   /* If we did not find any type changing statements, we may still drop
    1739                 :            :      maybe_in_construction flag if the context already have outer type. 
    1740                 :            : 
    1741                 :            :      Here we make special assumptions about both constructors and
    1742                 :            :      destructors which are all the functions that are allowed to alter the
    1743                 :            :      VMT pointers.  It assumes that destructors begin with assignment into
    1744                 :            :      all VMT pointers and that constructors essentially look in the
    1745                 :            :      following way:
    1746                 :            : 
    1747                 :            :      1) The very first thing they do is that they call constructors of
    1748                 :            :      ancestor sub-objects that have them.
    1749                 :            : 
    1750                 :            :      2) Then VMT pointers of this and all its ancestors is set to new
    1751                 :            :      values corresponding to the type corresponding to the constructor.
    1752                 :            : 
    1753                 :            :      3) Only afterwards, other stuff such as constructor of member
    1754                 :            :      sub-objects and the code written by the user is run.  Only this may
    1755                 :            :      include calling virtual functions, directly or indirectly.
    1756                 :            : 
    1757                 :            :      4) placement new cannot be used to change type of non-POD statically
    1758                 :            :      allocated variables.
    1759                 :            : 
    1760                 :            :      There is no way to call a constructor of an ancestor sub-object in any
    1761                 :            :      other way.
    1762                 :            : 
    1763                 :            :      This means that we do not have to care whether constructors get the
    1764                 :            :      correct type information because they will always change it (in fact,
    1765                 :            :      if we define the type to be given by the VMT pointer, it is undefined).
    1766                 :            : 
    1767                 :            :      The most important fact to derive from the above is that if, for some
    1768                 :            :      statement in the section 3, we try to detect whether the dynamic type
    1769                 :            :      has changed, we can safely ignore all calls as we examine the function
    1770                 :            :      body backwards until we reach statements in section 2 because these
    1771                 :            :      calls cannot be ancestor constructors or destructors (if the input is
    1772                 :            :      not bogus) and so do not change the dynamic type (this holds true only
    1773                 :            :      for automatically allocated objects but at the moment we devirtualize
    1774                 :            :      only these).  We then must detect that statements in section 2 change
    1775                 :            :      the dynamic type and can try to derive the new type.  That is enough
    1776                 :            :      and we can stop, we will never see the calls into constructors of
    1777                 :            :      sub-objects in this code. 
    1778                 :            : 
    1779                 :            :      Therefore if the static outer type was found (outer_type)
    1780                 :            :      we can safely ignore tci.speculative that is set on calls and give up
    1781                 :            :      only if there was dynamic type store that may affect given variable
    1782                 :            :      (seen_unanalyzed_store)  */
    1783                 :            : 
    1784                 :    1367240 :   if (walked < 0)
    1785                 :            :     {
    1786                 :       7538 :       if (dump_file)
    1787                 :          0 :         fprintf (dump_file, "  AA walk budget exhausted.\n");
    1788                 :       7538 :       *aa_walk_budget_p = 0;
    1789                 :       7538 :       return false;
    1790                 :            :     }
    1791                 :    1359710 :   else if (aa_walk_budget_p)
    1792                 :    1241010 :     *aa_walk_budget_p -= walked;
    1793                 :            : 
    1794                 :    1359710 :   if (!tci.type_maybe_changed
    1795                 :    1359710 :       || (outer_type
    1796                 :      12454 :           && !dynamic
    1797                 :        933 :           && !tci.seen_unanalyzed_store
    1798                 :        933 :           && !tci.multiple_types_encountered
    1799                 :        933 :           && ((offset == tci.offset
    1800                 :        923 :                && types_same_for_odr (tci.known_current_type,
    1801                 :            :                                       outer_type))
    1802                 :        490 :                || (instance_offset == offset
    1803                 :        480 :                    && types_same_for_odr (tci.known_current_type,
    1804                 :            :                                           instance_outer_type)))))
    1805                 :            :     {
    1806                 :    1273000 :       if (!outer_type || tci.seen_unanalyzed_store)
    1807                 :            :         return false;
    1808                 :     137037 :       if (maybe_in_construction)
    1809                 :      88404 :         maybe_in_construction = false;
    1810                 :     137037 :       if (dump_file)
    1811                 :        303 :         fprintf (dump_file, "  No dynamic type change found.\n");
    1812                 :     137037 :       return true;
    1813                 :            :     }
    1814                 :            : 
    1815                 :      86702 :   if (tci.known_current_type
    1816                 :      86702 :       && !function_entry_reached
    1817                 :      82768 :       && !tci.multiple_types_encountered)
    1818                 :            :     {
    1819                 :      82765 :       if (!tci.speculative)
    1820                 :            :         {
    1821                 :      22362 :           outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
    1822                 :      22362 :           offset = tci.known_current_offset;
    1823                 :      22362 :           dynamic = true;
    1824                 :      22362 :           maybe_in_construction = false;
    1825                 :      22362 :           maybe_derived_type = false;
    1826                 :      22362 :           if (dump_file)
    1827                 :         37 :             fprintf (dump_file, "  Determined dynamic type.\n");
    1828                 :            :         }
    1829                 :      60403 :       else if (!speculative_outer_type
    1830                 :       3162 :                || speculative_maybe_derived_type)
    1831                 :            :         {
    1832                 :      60403 :           speculative_outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
    1833                 :      60403 :           speculative_offset = tci.known_current_offset;
    1834                 :      60403 :           speculative_maybe_derived_type = false;
    1835                 :      60403 :           if (dump_file)
    1836                 :          9 :             fprintf (dump_file, "  Determined speculative dynamic type.\n");
    1837                 :            :         }
    1838                 :            :     }
    1839                 :       3937 :   else if (dump_file)
    1840                 :            :     {
    1841                 :          0 :       fprintf (dump_file, "  Found multiple types%s%s\n",
    1842                 :            :                function_entry_reached ? " (function entry reached)" : "",
    1843                 :            :                function_entry_reached ? " (multiple types encountered)" : "");
    1844                 :            :     }
    1845                 :            : 
    1846                 :            :   return false;
    1847                 :            : }
    1848                 :            : 
    1849                 :            : /* See if speculation given by SPEC_OUTER_TYPE, SPEC_OFFSET and SPEC_MAYBE_DERIVED_TYPE
    1850                 :            :    seems consistent (and useful) with what we already have in the non-speculative context.  */
    1851                 :            : 
    1852                 :            : bool
    1853                 :    1921870 : ipa_polymorphic_call_context::speculation_consistent_p (tree spec_outer_type,
    1854                 :            :                                                         HOST_WIDE_INT spec_offset,
    1855                 :            :                                                         bool spec_maybe_derived_type,
    1856                 :            :                                                         tree otr_type) const
    1857                 :            : {
    1858                 :    1921870 :   if (!flag_devirtualize_speculatively)
    1859                 :            :     return false;
    1860                 :            : 
    1861                 :            :   /* Non-polymorphic types are useless for deriving likely polymorphic
    1862                 :            :      call targets.  */
    1863                 :    1912300 :   if (!spec_outer_type || !contains_polymorphic_type_p (spec_outer_type))
    1864                 :    1214430 :     return false;
    1865                 :            : 
    1866                 :            :   /* If we know nothing, speculation is always good.  */
    1867                 :     697865 :   if (!outer_type)
    1868                 :            :     return true;
    1869                 :            : 
    1870                 :            :   /* Speculation is only useful to avoid derived types.
    1871                 :            :      This is not 100% true for placement new, where the outer context may
    1872                 :            :      turn out to be useless, but ignore these for now.  */
    1873                 :     497427 :   if (!maybe_derived_type)
    1874                 :            :     return false;
    1875                 :            : 
    1876                 :            :   /* If types agrees, speculation is consistent, but it makes sense only
    1877                 :            :      when it says something new.  */
    1878                 :     486470 :   if (types_must_be_same_for_odr (spec_outer_type, outer_type))
    1879                 :     393217 :     return maybe_derived_type && !spec_maybe_derived_type;
    1880                 :            : 
    1881                 :            :   /* If speculation does not contain the type in question, ignore it.  */
    1882                 :      93253 :   if (otr_type
    1883                 :      93253 :       && !contains_type_p (spec_outer_type, spec_offset, otr_type, false, true))
    1884                 :            :     return false;
    1885                 :            : 
    1886                 :            :   /* If outer type already contains speculation as a filed,
    1887                 :            :      it is useless.  We already know from OUTER_TYPE 
    1888                 :            :      SPEC_TYPE and that it is not in the construction.  */
    1889                 :      92575 :   if (contains_type_p (outer_type, offset - spec_offset,
    1890                 :            :                        spec_outer_type, false, false))
    1891                 :            :     return false;
    1892                 :            : 
    1893                 :            :   /* If speculative outer type is not more specified than outer
    1894                 :            :      type, just give up. 
    1895                 :            :      We can only decide this safely if we can compare types with OUTER_TYPE.
    1896                 :            :    */
    1897                 :        222 :   if ((!in_lto_p || odr_type_p (outer_type))
    1898                 :     184844 :       && !contains_type_p (spec_outer_type,
    1899                 :      92422 :                            spec_offset - offset,
    1900                 :      92422 :                            outer_type, false))
    1901                 :      10620 :     return false;
    1902                 :            :   return true;
    1903                 :            : }
    1904                 :            : 
    1905                 :            : /* Improve THIS with speculation described by NEW_OUTER_TYPE, NEW_OFFSET,
    1906                 :            :    NEW_MAYBE_DERIVED_TYPE 
    1907                 :            :    If OTR_TYPE is set, assume the context is used with OTR_TYPE.  */
    1908                 :            : 
    1909                 :            : bool
    1910                 :    1906740 : ipa_polymorphic_call_context::combine_speculation_with
    1911                 :            :    (tree new_outer_type, HOST_WIDE_INT new_offset, bool new_maybe_derived_type,
    1912                 :            :     tree otr_type)
    1913                 :            : {
    1914                 :    1906740 :   if (!new_outer_type)
    1915                 :            :     return false;
    1916                 :            : 
    1917                 :            :   /* restrict_to_inner_class may eliminate wrong speculation making our job
    1918                 :            :      easier.  */
    1919                 :    1865570 :   if (otr_type)
    1920                 :       1283 :     restrict_to_inner_class (otr_type);
    1921                 :            : 
    1922                 :    1865570 :   if (!speculation_consistent_p (new_outer_type, new_offset,
    1923                 :            :                                  new_maybe_derived_type, otr_type))
    1924                 :            :     return false;
    1925                 :            : 
    1926                 :            :   /* New speculation is a win in case we have no speculation or new
    1927                 :            :      speculation does not consider derivations.  */
    1928                 :     256748 :   if (!speculative_outer_type
    1929                 :      74344 :       || (speculative_maybe_derived_type
    1930                 :      74344 :           && !new_maybe_derived_type))
    1931                 :            :     {
    1932                 :     185234 :       speculative_outer_type = new_outer_type;
    1933                 :     185234 :       speculative_offset = new_offset;
    1934                 :     185234 :       speculative_maybe_derived_type = new_maybe_derived_type;
    1935                 :     185234 :       return true;
    1936                 :            :     }
    1937                 :      71514 :   else if (types_must_be_same_for_odr (speculative_outer_type,
    1938                 :            :                                        new_outer_type))
    1939                 :            :     {
    1940                 :      69904 :       if (speculative_offset != new_offset)
    1941                 :            :         {
    1942                 :            :           /* OK we have two contexts that seems valid but they disagree,
    1943                 :            :              just give up.
    1944                 :            : 
    1945                 :            :              This is not a lattice operation, so we may want to drop it later.  */
    1946                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1947                 :          0 :             fprintf (dump_file,
    1948                 :            :                      "Speculative outer types match, "
    1949                 :            :                      "offset mismatch -> invalid speculation\n");
    1950                 :          0 :           clear_speculation ();
    1951                 :          0 :           return true;
    1952                 :            :         }
    1953                 :            :       else
    1954                 :            :         {
    1955                 :      69904 :           if (speculative_maybe_derived_type && !new_maybe_derived_type)
    1956                 :            :             {
    1957                 :          0 :               speculative_maybe_derived_type = false;
    1958                 :          0 :               return true;
    1959                 :            :             }
    1960                 :            :           else
    1961                 :            :             return false;
    1962                 :            :         }
    1963                 :            :     }
    1964                 :            :   /* Choose type that contains the other.  This one either contains the outer
    1965                 :            :      as a field (thus giving exactly one target) or is deeper in the type
    1966                 :            :      hierarchy.  */
    1967                 :       1610 :   else if (speculative_outer_type
    1968                 :       1610 :            && speculative_maybe_derived_type
    1969                 :       2915 :            && (new_offset > speculative_offset
    1970                 :        967 :                || (new_offset == speculative_offset
    1971                 :        940 :                    && contains_type_p (new_outer_type,
    1972                 :            :                                        0, speculative_outer_type, false))))
    1973                 :            :     {
    1974                 :       1004 :       tree old_outer_type = speculative_outer_type;
    1975                 :       1004 :       HOST_WIDE_INT old_offset = speculative_offset;
    1976                 :       1004 :       bool old_maybe_derived_type = speculative_maybe_derived_type;
    1977                 :            : 
    1978                 :       1004 :       speculative_outer_type = new_outer_type;
    1979                 :       1004 :       speculative_offset = new_offset;
    1980                 :       1004 :       speculative_maybe_derived_type = new_maybe_derived_type;
    1981                 :            : 
    1982                 :       1004 :       if (otr_type)
    1983                 :          0 :         restrict_to_inner_class (otr_type);
    1984                 :            : 
    1985                 :            :       /* If the speculation turned out to make no sense, revert to sensible
    1986                 :            :          one.  */
    1987                 :       1004 :       if (!speculative_outer_type)
    1988                 :            :         {
    1989                 :          0 :           speculative_outer_type = old_outer_type;
    1990                 :          0 :           speculative_offset = old_offset;
    1991                 :          0 :           speculative_maybe_derived_type = old_maybe_derived_type;
    1992                 :          0 :           return false;
    1993                 :            :         }
    1994                 :       1004 :       return (old_offset != speculative_offset
    1995                 :        666 :               || old_maybe_derived_type != speculative_maybe_derived_type
    1996                 :       1670 :               || types_must_be_same_for_odr (speculative_outer_type,
    1997                 :            :                                              new_outer_type));
    1998                 :            :     }
    1999                 :            :   return false;
    2000                 :            : }
    2001                 :            : 
    2002                 :            : /* Make speculation less specific so
    2003                 :            :    NEW_OUTER_TYPE, NEW_OFFSET, NEW_MAYBE_DERIVED_TYPE is also included.
    2004                 :            :    If OTR_TYPE is set, assume the context is used with OTR_TYPE.  */
    2005                 :            : 
    2006                 :            : bool
    2007                 :         58 : ipa_polymorphic_call_context::meet_speculation_with
    2008                 :            :    (tree new_outer_type, HOST_WIDE_INT new_offset, bool new_maybe_derived_type,
    2009                 :            :     tree otr_type)
    2010                 :            : {
    2011                 :         58 :   if (!new_outer_type && speculative_outer_type)
    2012                 :            :     {
    2013                 :         17 :       clear_speculation ();
    2014                 :         17 :       return true;
    2015                 :            :     }
    2016                 :            : 
    2017                 :            :   /* restrict_to_inner_class may eliminate wrong speculation making our job
    2018                 :            :      easier.  */
    2019                 :         41 :   if (otr_type)
    2020                 :          0 :     restrict_to_inner_class (otr_type);
    2021                 :            : 
    2022                 :         41 :   if (!speculative_outer_type
    2023                 :         63 :       || !speculation_consistent_p (speculative_outer_type,
    2024                 :            :                                     speculative_offset,
    2025                 :            :                                     speculative_maybe_derived_type,
    2026                 :         22 :                                     otr_type))
    2027                 :         20 :     return false;
    2028                 :            : 
    2029                 :         21 :   if (!speculation_consistent_p (new_outer_type, new_offset,
    2030                 :            :                                  new_maybe_derived_type, otr_type))
    2031                 :            :     {
    2032                 :          0 :       clear_speculation ();
    2033                 :          0 :       return true;
    2034                 :            :     }
    2035                 :            : 
    2036                 :         21 :   else if (types_must_be_same_for_odr (speculative_outer_type,
    2037                 :            :                                        new_outer_type))
    2038                 :            :     {
    2039                 :         19 :       if (speculative_offset != new_offset)
    2040                 :            :         {
    2041                 :          0 :           clear_speculation ();
    2042                 :          0 :           return true;
    2043                 :            :         }
    2044                 :            :       else
    2045                 :            :         {
    2046                 :         19 :           if (!speculative_maybe_derived_type && new_maybe_derived_type)
    2047                 :            :             {
    2048                 :          0 :               speculative_maybe_derived_type = true;
    2049                 :          0 :               return true;
    2050                 :            :             }
    2051                 :            :           else
    2052                 :            :             return false;
    2053                 :            :         }
    2054                 :            :     }
    2055                 :            :   /* See if one type contains the other as a field (not base).  */
    2056                 :          2 :   else if (contains_type_p (new_outer_type, new_offset - speculative_offset,
    2057                 :            :                             speculative_outer_type, false, false))
    2058                 :            :     return false;
    2059                 :          2 :   else if (contains_type_p (speculative_outer_type,
    2060                 :          2 :                             speculative_offset - new_offset,
    2061                 :            :                             new_outer_type, false, false))
    2062                 :            :     {
    2063                 :          2 :       speculative_outer_type = new_outer_type;
    2064                 :          2 :       speculative_offset = new_offset;
    2065                 :          2 :       speculative_maybe_derived_type = new_maybe_derived_type;
    2066                 :          2 :       return true;
    2067                 :            :     }
    2068                 :            :   /* See if OUTER_TYPE is base of CTX.OUTER_TYPE.  */
    2069                 :          0 :   else if (contains_type_p (new_outer_type,
    2070                 :          0 :                             new_offset - speculative_offset,
    2071                 :            :                             speculative_outer_type, false, true))
    2072                 :            :     {
    2073                 :          0 :       if (!speculative_maybe_derived_type)
    2074                 :            :         {
    2075                 :          0 :           speculative_maybe_derived_type = true;
    2076                 :          0 :           return true;
    2077                 :            :         }
    2078                 :            :       return false;
    2079                 :            :     }
    2080                 :            :   /* See if CTX.OUTER_TYPE is base of OUTER_TYPE.  */
    2081                 :          0 :   else if (contains_type_p (speculative_outer_type,
    2082                 :          0 :                             speculative_offset - new_offset, new_outer_type, false, true))
    2083                 :            :     {
    2084                 :          0 :       speculative_outer_type = new_outer_type;
    2085                 :          0 :       speculative_offset = new_offset;
    2086                 :          0 :       speculative_maybe_derived_type = true;
    2087                 :          0 :       return true;
    2088                 :            :     }
    2089                 :            :   else
    2090                 :            :     {
    2091                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2092                 :          0 :         fprintf (dump_file, "Giving up on speculative meet\n");
    2093                 :          0 :       clear_speculation ();
    2094                 :          0 :       return true;
    2095                 :            :     }
    2096                 :            : }
    2097                 :            : 
    2098                 :            : /* Assume that both THIS and a given context is valid and strengthen THIS
    2099                 :            :    if possible.  Return true if any strengthening was made.
    2100                 :            :    If actual type the context is being used in is known, OTR_TYPE should be
    2101                 :            :    set accordingly. This improves quality of combined result.  */
    2102                 :            : 
    2103                 :            : bool
    2104                 :      75333 : ipa_polymorphic_call_context::combine_with (ipa_polymorphic_call_context ctx,
    2105                 :            :                                             tree otr_type)
    2106                 :            : {
    2107                 :      75333 :   bool updated = false;
    2108                 :            : 
    2109                 :     107113 :   if (ctx.useless_p () || invalid)
    2110                 :            :     return false;
    2111                 :            : 
    2112                 :            :   /* Restricting context to inner type makes merging easier, however do not
    2113                 :            :      do that unless we know how the context is used (OTR_TYPE is non-NULL)  */
    2114                 :      74998 :   if (otr_type && !invalid && !ctx.invalid)
    2115                 :            :     {
    2116                 :      18355 :       restrict_to_inner_class (otr_type);
    2117                 :      18355 :       ctx.restrict_to_inner_class (otr_type);
    2118                 :      18355 :       if(invalid)
    2119                 :            :         return false;
    2120                 :            :     }
    2121                 :            : 
    2122                 :      74930 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2123                 :            :     {
    2124                 :         98 :       fprintf (dump_file, "Polymorphic call context combine:");
    2125                 :         98 :       dump (dump_file);
    2126                 :         98 :       fprintf (dump_file, "With context:                    ");
    2127                 :         98 :       ctx.dump (dump_file);
    2128                 :         98 :       if (otr_type)
    2129                 :            :         {
    2130                 :         42 :           fprintf (dump_file, "To be used with type:            ");
    2131                 :         42 :           print_generic_expr (dump_file, otr_type, TDF_SLIM);
    2132                 :         42 :           fprintf (dump_file, "\n");
    2133                 :            :         }
    2134                 :            :     }
    2135                 :            : 
    2136                 :            :   /* If call is known to be invalid, we are done.  */
    2137                 :      74930 :   if (ctx.invalid)
    2138                 :            :     {
    2139                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2140                 :          0 :         fprintf (dump_file, "-> Invalid context\n");
    2141                 :          0 :       goto invalidate;
    2142                 :            :     }
    2143                 :            : 
    2144                 :      74930 :   if (!ctx.outer_type)
    2145                 :            :     ;
    2146                 :      43305 :   else if (!outer_type)
    2147                 :            :     {
    2148                 :       7077 :       outer_type = ctx.outer_type;
    2149                 :       7077 :       offset = ctx.offset;
    2150                 :       7077 :       dynamic = ctx.dynamic;
    2151                 :       7077 :       maybe_in_construction = ctx.maybe_in_construction;
    2152                 :       7077 :       maybe_derived_type = ctx.maybe_derived_type;
    2153                 :       7077 :       updated = true;
    2154                 :            :     }
    2155                 :            :   /* If types are known to be same, merging is quite easy.  */
    2156                 :      36228 :   else if (types_must_be_same_for_odr (outer_type, ctx.outer_type))
    2157                 :            :     {
    2158                 :      23339 :       if (offset != ctx.offset
    2159                 :          0 :           && TYPE_SIZE (outer_type)
    2160                 :      23339 :           && TREE_CODE (TYPE_SIZE (outer_type)) == INTEGER_CST)
    2161                 :            :         {
    2162                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2163                 :          0 :             fprintf (dump_file, "Outer types match, offset mismatch -> invalid\n");
    2164                 :          0 :           clear_speculation ();
    2165                 :          0 :           clear_outer_type ();
    2166                 :          0 :           invalid = true;
    2167                 :          0 :           return true;
    2168                 :            :         }
    2169                 :      23339 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2170                 :         24 :         fprintf (dump_file, "Outer types match, merging flags\n");
    2171                 :      23339 :       if (maybe_in_construction && !ctx.maybe_in_construction)
    2172                 :            :         {
    2173                 :       7046 :           updated = true;
    2174                 :       7046 :           maybe_in_construction = false;
    2175                 :            :         }
    2176                 :      23339 :       if (maybe_derived_type && !ctx.maybe_derived_type)
    2177                 :            :         {
    2178                 :        873 :           updated = true;
    2179                 :        873 :           maybe_derived_type = false;
    2180                 :            :         }
    2181                 :      23339 :       if (dynamic && !ctx.dynamic)
    2182                 :            :         {
    2183                 :       6780 :           updated = true;
    2184                 :       6780 :           dynamic = false;
    2185                 :            :         }
    2186                 :            :     }
    2187                 :            :   /* If we know the type precisely, there is not much to improve.  */
    2188                 :      12889 :   else if (!maybe_derived_type && !maybe_in_construction
    2189                 :       8848 :            && !ctx.maybe_derived_type && !ctx.maybe_in_construction)
    2190                 :            :     {
    2191                 :            :       /* It may be easy to check if second context permits the first
    2192                 :            :          and set INVALID otherwise.  This is not easy to do in general;
    2193                 :            :          contains_type_p may return false negatives for non-comparable
    2194                 :            :          types.  
    2195                 :            : 
    2196                 :            :          If OTR_TYPE is known, we however can expect that
    2197                 :            :          restrict_to_inner_class should have discovered the same base
    2198                 :            :          type.  */
    2199                 :        275 :       if (otr_type && !ctx.maybe_in_construction && !ctx.maybe_derived_type)
    2200                 :            :         {
    2201                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2202                 :          0 :             fprintf (dump_file, "Contextes disagree -> invalid\n");
    2203                 :          0 :           goto invalidate;
    2204                 :            :         }
    2205                 :            :     }
    2206                 :            :   /* See if one type contains the other as a field (not base).
    2207                 :            :      In this case we want to choose the wider type, because it contains
    2208                 :            :      more information.  */
    2209                 :      12614 :   else if (contains_type_p (ctx.outer_type, ctx.offset - offset,
    2210                 :            :                             outer_type, false, false))
    2211                 :            :     {
    2212                 :        453 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2213                 :          0 :         fprintf (dump_file, "Second type contain the first as a field\n");
    2214                 :            : 
    2215                 :        453 :       if (maybe_derived_type)
    2216                 :            :         {
    2217                 :        305 :           outer_type = ctx.outer_type;
    2218                 :        305 :           maybe_derived_type = ctx.maybe_derived_type;
    2219                 :        305 :           offset = ctx.offset;
    2220                 :        305 :           dynamic = ctx.dynamic;
    2221                 :        305 :           updated = true;
    2222                 :            :         }
    2223                 :            : 
    2224                 :            :       /* If we do not know how the context is being used, we cannot
    2225                 :            :          clear MAYBE_IN_CONSTRUCTION because it may be offseted
    2226                 :            :          to other component of OUTER_TYPE later and we know nothing
    2227                 :            :          about it.  */
    2228                 :        453 :       if (otr_type && maybe_in_construction
    2229                 :          0 :           && !ctx.maybe_in_construction)
    2230                 :            :         {
    2231                 :          0 :           maybe_in_construction = false;
    2232                 :          0 :           updated = true;
    2233                 :            :         }
    2234                 :            :     }
    2235                 :      12161 :   else if (contains_type_p (outer_type, offset - ctx.offset,
    2236                 :            :                             ctx.outer_type, false, false))
    2237                 :            :     {
    2238                 :         50 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2239                 :          0 :         fprintf (dump_file, "First type contain the second as a field\n");
    2240                 :            : 
    2241                 :         50 :       if (otr_type && maybe_in_construction
    2242                 :          0 :           && !ctx.maybe_in_construction)
    2243                 :            :         {
    2244                 :          0 :           maybe_in_construction = false;
    2245                 :          0 :           updated = true;
    2246                 :            :         }
    2247                 :            :     }
    2248                 :            :   /* See if OUTER_TYPE is base of CTX.OUTER_TYPE.  */
    2249                 :      12111 :   else if (contains_type_p (ctx.outer_type,
    2250                 :      12111 :                             ctx.offset - offset, outer_type, false, true))
    2251                 :            :     {
    2252                 :       6194 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2253                 :          8 :         fprintf (dump_file, "First type is base of second\n");
    2254                 :       6194 :       if (!maybe_derived_type)
    2255                 :            :         {
    2256                 :       2938 :           if (!ctx.maybe_in_construction
    2257                 :       2938 :               && types_odr_comparable (outer_type, ctx.outer_type))
    2258                 :            :             {
    2259                 :          0 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2260                 :          0 :                 fprintf (dump_file, "Second context does not permit base -> invalid\n");
    2261                 :          0 :               goto invalidate;
    2262                 :            :             }
    2263                 :            :         }
    2264                 :            :       /* Pick variant deeper in the hierarchy.  */
    2265                 :            :       else
    2266                 :            :         {
    2267                 :       3256 :           outer_type = ctx.outer_type;
    2268                 :       3256 :           maybe_in_construction = ctx.maybe_in_construction;
    2269                 :       3256 :           maybe_derived_type = ctx.maybe_derived_type;
    2270                 :       3256 :           offset = ctx.offset;
    2271                 :       3256 :           dynamic = ctx.dynamic;
    2272                 :       3256 :           updated = true;
    2273                 :            :         }
    2274                 :            :     }
    2275                 :            :   /* See if CTX.OUTER_TYPE is base of OUTER_TYPE.  */
    2276                 :       5917 :   else if (contains_type_p (outer_type,
    2277                 :       5917 :                             offset - ctx.offset, ctx.outer_type, false, true))
    2278                 :            :     {
    2279                 :       5776 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2280                 :         34 :         fprintf (dump_file, "Second type is base of first\n");
    2281                 :       5776 :       if (!ctx.maybe_derived_type)
    2282                 :            :         {
    2283                 :        119 :           if (!maybe_in_construction
    2284                 :        119 :               && types_odr_comparable (outer_type, ctx.outer_type))
    2285                 :            :             {
    2286                 :          0 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2287                 :          0 :                 fprintf (dump_file, "First context does not permit base -> invalid\n");
    2288                 :          0 :               goto invalidate;
    2289                 :            :             }
    2290                 :            :           /* Pick the base type.  */
    2291                 :        119 :           else if (maybe_in_construction)
    2292                 :            :             {
    2293                 :        119 :               outer_type = ctx.outer_type;
    2294                 :        119 :               maybe_in_construction = ctx.maybe_in_construction;
    2295                 :        119 :               maybe_derived_type = ctx.maybe_derived_type;
    2296                 :        119 :               offset = ctx.offset;
    2297                 :        119 :               dynamic = ctx.dynamic;
    2298                 :        119 :               updated = true;
    2299                 :            :             }
    2300                 :            :         }
    2301                 :            :     }
    2302                 :            :   /* TODO handle merging using hierarchy. */
    2303                 :        141 :   else if (dump_file && (dump_flags & TDF_DETAILS))
    2304                 :          4 :     fprintf (dump_file, "Giving up on merge\n");
    2305                 :            : 
    2306                 :     149860 :   updated |= combine_speculation_with (ctx.speculative_outer_type,
    2307                 :            :                                        ctx.speculative_offset,
    2308                 :            :                                        ctx.speculative_maybe_derived_type,
    2309                 :      74930 :                                        otr_type);
    2310                 :            : 
    2311                 :      74930 :   if (updated && dump_file && (dump_flags & TDF_DETAILS))
    2312                 :            :     {
    2313                 :         52 :       fprintf (dump_file, "Updated as:                      ");
    2314                 :         52 :       dump (dump_file);
    2315                 :         52 :       fprintf (dump_file, "\n");
    2316                 :            :     }
    2317                 :            :   return updated;
    2318                 :            : 
    2319                 :          0 : invalidate:
    2320                 :          0 :   invalid = true;
    2321                 :          0 :   clear_speculation ();
    2322                 :          0 :   clear_outer_type ();
    2323                 :          0 :   return true;
    2324                 :            : }
    2325                 :            : 
    2326                 :            : /* Take non-speculative info, merge it with speculative and clear speculation.
    2327                 :            :    Used when we no longer manage to keep track of actual outer type, but we
    2328                 :            :    think it is still there.
    2329                 :            : 
    2330                 :            :    If OTR_TYPE is set, the transformation can be done more effectively assuming
    2331                 :            :    that context is going to be used only that way.  */
    2332                 :            : 
    2333                 :            : void
    2334                 :      39092 : ipa_polymorphic_call_context::make_speculative (tree otr_type)
    2335                 :            : {
    2336                 :      39092 :   tree spec_outer_type = outer_type;
    2337                 :      39092 :   HOST_WIDE_INT spec_offset = offset;
    2338                 :      39092 :   bool spec_maybe_derived_type = maybe_derived_type;
    2339                 :            : 
    2340                 :      39092 :   if (invalid)
    2341                 :            :     {
    2342                 :          0 :       invalid = false;
    2343                 :          0 :       clear_outer_type ();
    2344                 :          0 :       clear_speculation ();
    2345                 :          0 :       return;
    2346                 :            :     }
    2347                 :      39092 :   if (!outer_type)
    2348                 :            :     return;
    2349                 :      16689 :   clear_outer_type ();
    2350                 :      16689 :   combine_speculation_with (spec_outer_type, spec_offset,
    2351                 :            :                             spec_maybe_derived_type,
    2352                 :            :                             otr_type);
    2353                 :            : }
    2354                 :            : 
    2355                 :            : /* Use when we cannot track dynamic type change.  This speculatively assume
    2356                 :            :    type change is not happening.  */
    2357                 :            : 
    2358                 :            : void
    2359                 :      52406 : ipa_polymorphic_call_context::possible_dynamic_type_change (bool in_poly_cdtor,
    2360                 :            :                                                             tree otr_type)
    2361                 :            : {
    2362                 :      52406 :   if (dynamic)
    2363                 :      39092 :     make_speculative (otr_type);
    2364                 :      13314 :   else if (in_poly_cdtor)
    2365                 :       9789 :     maybe_in_construction = true;
    2366                 :      52406 : }
    2367                 :            : 
    2368                 :            : /* Return TRUE if this context conveys the same information as OTHER.  */
    2369                 :            : 
    2370                 :            : bool
    2371                 :      29763 : ipa_polymorphic_call_context::equal_to
    2372                 :            :     (const ipa_polymorphic_call_context &x) const
    2373                 :            : {
    2374                 :      29763 :   if (useless_p ())
    2375                 :         31 :     return x.useless_p ();
    2376                 :      29732 :   if (invalid)
    2377                 :          0 :     return x.invalid;
    2378                 :      49250 :   if (x.useless_p () || x.invalid)
    2379                 :            :     return false;
    2380                 :            : 
    2381                 :      29726 :   if (outer_type)
    2382                 :            :     {
    2383                 :       9941 :       if (!x.outer_type
    2384                 :       9844 :           || !types_odr_comparable (outer_type, x.outer_type)
    2385                 :       9844 :           || !types_same_for_odr (outer_type, x.outer_type)
    2386                 :       9580 :           || offset != x.offset
    2387                 :       9555 :           || maybe_in_construction != x.maybe_in_construction
    2388                 :            :           || maybe_derived_type != x.maybe_derived_type
    2389                 :      19496 :           || dynamic != x.dynamic)
    2390                 :        601 :         return false;
    2391                 :            :     }
    2392                 :      19785 :   else if (x.outer_type)
    2393                 :            :     return false;
    2394                 :            : 
    2395                 :            : 
    2396                 :      28761 :   if (speculative_outer_type
    2397                 :      49077 :       && speculation_consistent_p (speculative_outer_type, speculative_offset,
    2398                 :      20316 :                                    speculative_maybe_derived_type, NULL_TREE))
    2399                 :            :     {
    2400                 :      19050 :       if (!x.speculative_outer_type)
    2401                 :            :         return false;
    2402                 :            : 
    2403                 :      19039 :       if (!types_odr_comparable (speculative_outer_type,
    2404                 :            :                                  x.speculative_outer_type)
    2405                 :      19039 :           || !types_same_for_odr  (speculative_outer_type,
    2406                 :      19039 :                                    x.speculative_outer_type)
    2407                 :      18748 :           || speculative_offset != x.speculative_offset
    2408                 :      37723 :           || speculative_maybe_derived_type != x.speculative_maybe_derived_type)
    2409                 :        358 :         return false;
    2410                 :            :     }
    2411                 :       9711 :   else if (x.speculative_outer_type
    2412                 :      10916 :            && x.speculation_consistent_p (x.speculative_outer_type,
    2413                 :       1205 :                                           x.speculative_offset,
    2414                 :            :                                           x.speculative_maybe_derived_type,
    2415                 :       1205 :                                           NULL))
    2416                 :         51 :     return false;
    2417                 :            : 
    2418                 :            :   return true;
    2419                 :            : }
    2420                 :            : 
    2421                 :            : /* Modify context to be strictly less restrictive than CTX.  */
    2422                 :            : 
    2423                 :            : bool
    2424                 :         87 : ipa_polymorphic_call_context::meet_with (ipa_polymorphic_call_context ctx,
    2425                 :            :                                          tree otr_type)
    2426                 :            : {
    2427                 :         87 :   bool updated = false;
    2428                 :            : 
    2429                 :        129 :   if (useless_p () || ctx.invalid)
    2430                 :            :     return false;
    2431                 :            : 
    2432                 :            :   /* Restricting context to inner type makes merging easier, however do not
    2433                 :            :      do that unless we know how the context is used (OTR_TYPE is non-NULL)  */
    2434                 :         87 :   if (otr_type && !useless_p () && !ctx.useless_p ())
    2435                 :            :     {
    2436                 :          0 :       restrict_to_inner_class (otr_type);
    2437                 :          0 :       ctx.restrict_to_inner_class (otr_type);
    2438                 :          0 :       if(invalid)
    2439                 :            :         return false;
    2440                 :            :     }
    2441                 :            : 
    2442                 :         87 :   if (equal_to (ctx))
    2443                 :            :     return false;
    2444                 :            : 
    2445                 :         64 :   if (ctx.useless_p () || invalid)
    2446                 :            :     {
    2447                 :          6 :       *this = ctx;
    2448                 :          6 :       return true;
    2449                 :            :     }
    2450                 :            : 
    2451                 :         58 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2452                 :            :     {
    2453                 :          0 :       fprintf (dump_file, "Polymorphic call context meet:");
    2454                 :          0 :       dump (dump_file);
    2455                 :          0 :       fprintf (dump_file, "With context:                    ");
    2456                 :          0 :       ctx.dump (dump_file);
    2457                 :          0 :       if (otr_type)
    2458                 :            :         {
    2459                 :          0 :           fprintf (dump_file, "To be used with type:            ");
    2460                 :          0 :           print_generic_expr (dump_file, otr_type, TDF_SLIM);
    2461                 :          0 :           fprintf (dump_file, "\n");
    2462                 :            :         }
    2463                 :            :     }
    2464                 :            : 
    2465                 :         58 :   if (!dynamic && ctx.dynamic)
    2466                 :            :     {
    2467                 :          7 :       dynamic = true;
    2468                 :          7 :       updated = true;
    2469                 :            :     }
    2470                 :            : 
    2471                 :            :   /* If call is known to be invalid, we are done.  */
    2472                 :         58 :   if (!outer_type)
    2473                 :            :     ;
    2474                 :         22 :   else if (!ctx.outer_type)
    2475                 :            :     {
    2476                 :          0 :       clear_outer_type ();
    2477                 :          0 :       updated = true;
    2478                 :            :     }
    2479                 :            :   /* If types are known to be same, merging is quite easy.  */
    2480                 :         22 :   else if (types_must_be_same_for_odr (outer_type, ctx.outer_type))
    2481                 :            :     {
    2482                 :         18 :       if (offset != ctx.offset
    2483                 :          0 :           && TYPE_SIZE (outer_type)
    2484                 :         18 :           && TREE_CODE (TYPE_SIZE (outer_type)) == INTEGER_CST)
    2485                 :            :         {
    2486                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2487                 :          0 :             fprintf (dump_file, "Outer types match, offset mismatch -> clearing\n");
    2488                 :          0 :           clear_outer_type ();
    2489                 :          0 :           return true;
    2490                 :            :         }
    2491                 :         18 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2492                 :          0 :         fprintf (dump_file, "Outer types match, merging flags\n");
    2493                 :         18 :       if (!maybe_in_construction && ctx.maybe_in_construction)
    2494                 :            :         {
    2495                 :          0 :           updated = true;
    2496                 :          0 :           maybe_in_construction = true;
    2497                 :            :         }
    2498                 :         18 :       if (!maybe_derived_type && ctx.maybe_derived_type)
    2499                 :            :         {
    2500                 :          3 :           updated = true;
    2501                 :          3 :           maybe_derived_type = true;
    2502                 :            :         }
    2503                 :         18 :       if (!dynamic && ctx.dynamic)
    2504                 :            :         {
    2505                 :          0 :           updated = true;
    2506                 :          0 :           dynamic = true;
    2507                 :            :         }
    2508                 :            :     }
    2509                 :            :   /* See if one type contains the other as a field (not base).  */
    2510                 :          4 :   else if (contains_type_p (ctx.outer_type, ctx.offset - offset,
    2511                 :            :                             outer_type, false, false))
    2512                 :            :     {
    2513                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2514                 :          0 :         fprintf (dump_file, "Second type contain the first as a field\n");
    2515                 :            : 
    2516                 :            :       /* The second type is more specified, so we keep the first.
    2517                 :            :          We need to set DYNAMIC flag to avoid declaring context INVALID
    2518                 :            :          of OFFSET ends up being out of range.  */
    2519                 :          0 :       if (!dynamic
    2520                 :          0 :           && (ctx.dynamic
    2521                 :          0 :               || (!otr_type
    2522                 :          0 :                   && (!TYPE_SIZE (ctx.outer_type)
    2523                 :          0 :                       || !TYPE_SIZE (outer_type)
    2524                 :          0 :                       || !operand_equal_p (TYPE_SIZE (ctx.outer_type),
    2525                 :          0 :                                            TYPE_SIZE (outer_type), 0)))))
    2526                 :            :         {
    2527                 :          0 :           dynamic = true;
    2528                 :          0 :           updated = true;
    2529                 :            :         }
    2530                 :            :     }
    2531                 :          4 :   else if (contains_type_p (outer_type, offset - ctx.offset,
    2532                 :            :                             ctx.outer_type, false, false))
    2533                 :            :     {
    2534                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2535                 :          0 :         fprintf (dump_file, "First type contain the second as a field\n");
    2536                 :            : 
    2537                 :          0 :       if (!dynamic
    2538                 :          0 :           && (ctx.dynamic
    2539                 :          0 :               || (!otr_type
    2540                 :          0 :                   && (!TYPE_SIZE (ctx.outer_type)
    2541                 :          0 :                       || !TYPE_SIZE (outer_type)
    2542                 :          0 :                       || !operand_equal_p (TYPE_SIZE (ctx.outer_type),
    2543                 :          0 :                                            TYPE_SIZE (outer_type), 0)))))
    2544                 :          0 :         dynamic = true;
    2545                 :          0 :       outer_type = ctx.outer_type;
    2546                 :          0 :       offset = ctx.offset;
    2547                 :          0 :       dynamic = ctx.dynamic;
    2548                 :          0 :       maybe_in_construction = ctx.maybe_in_construction;
    2549                 :          0 :       maybe_derived_type = ctx.maybe_derived_type;
    2550                 :          0 :       updated = true;
    2551                 :            :     }
    2552                 :            :   /* See if OUTER_TYPE is base of CTX.OUTER_TYPE.  */
    2553                 :          4 :   else if (contains_type_p (ctx.outer_type,
    2554                 :          4 :                             ctx.offset - offset, outer_type, false, true))
    2555                 :            :     {
    2556                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2557                 :          0 :         fprintf (dump_file, "First type is base of second\n");
    2558                 :          0 :       if (!maybe_derived_type)
    2559                 :            :         {
    2560                 :          0 :           maybe_derived_type = true;
    2561                 :          0 :           updated = true;
    2562                 :            :         }
    2563                 :          0 :       if (!maybe_in_construction && ctx.maybe_in_construction)
    2564                 :            :         {
    2565                 :          0 :           maybe_in_construction = true;
    2566                 :          0 :           updated = true;
    2567                 :            :         }
    2568                 :          0 :       if (!dynamic && ctx.dynamic)
    2569                 :            :         {
    2570                 :          0 :           dynamic = true;
    2571                 :          0 :           updated = true;
    2572                 :            :         }
    2573                 :            :     }
    2574                 :            :   /* See if CTX.OUTER_TYPE is base of OUTER_TYPE.  */
    2575                 :          4 :   else if (contains_type_p (outer_type,
    2576                 :          4 :                             offset - ctx.offset, ctx.outer_type, false, true))
    2577                 :            :     {
    2578                 :          4 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2579                 :          0 :         fprintf (dump_file, "Second type is base of first\n");
    2580                 :          4 :       outer_type = ctx.outer_type;
    2581                 :          4 :       offset = ctx.offset;
    2582                 :          4 :       updated = true;
    2583                 :          4 :       if (!maybe_derived_type)
    2584                 :          4 :         maybe_derived_type = true;
    2585                 :          4 :       if (!maybe_in_construction && ctx.maybe_in_construction)
    2586                 :          0 :         maybe_in_construction = true;
    2587                 :          4 :       if (!dynamic && ctx.dynamic)
    2588                 :          0 :         dynamic = true;
    2589                 :            :     }
    2590                 :            :   /* TODO handle merging using hierarchy. */
    2591                 :            :   else
    2592                 :            :     {
    2593                 :          0 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2594                 :          0 :         fprintf (dump_file, "Giving up on meet\n");
    2595                 :          0 :       clear_outer_type ();
    2596                 :          0 :       updated = true;
    2597                 :            :     }
    2598                 :            : 
    2599                 :        116 :   updated |= meet_speculation_with (ctx.speculative_outer_type,
    2600                 :            :                                     ctx.speculative_offset,
    2601                 :            :                                     ctx.speculative_maybe_derived_type,
    2602                 :         58 :                                     otr_type);
    2603                 :            : 
    2604                 :         58 :   if (updated && dump_file && (dump_flags & TDF_DETAILS))
    2605                 :            :     {
    2606                 :          0 :       fprintf (dump_file, "Updated as:                      ");
    2607                 :          0 :       dump (dump_file);
    2608                 :          0 :       fprintf (dump_file, "\n");
    2609                 :            :     }
    2610                 :            :   return updated;
    2611                 :            : }

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.