2015-05-22 Robert Dewar <dewar@adacore.com>
[official-gcc.git] / gcc / ipa-polymorphic-call.c
blob083648d7e4213969179d77b9293e9473d2a69590
1 /* Analysis of polymorphic call context.
2 Copyright (C) 2013-2015 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
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.
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.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hash-set.h"
26 #include "machmode.h"
27 #include "vec.h"
28 #include "double-int.h"
29 #include "input.h"
30 #include "alias.h"
31 #include "symtab.h"
32 #include "wide-int.h"
33 #include "inchash.h"
34 #include "tree.h"
35 #include "fold-const.h"
36 #include "print-tree.h"
37 #include "calls.h"
38 #include "hashtab.h"
39 #include "hard-reg-set.h"
40 #include "function.h"
41 #include "rtl.h"
42 #include "flags.h"
43 #include "statistics.h"
44 #include "real.h"
45 #include "fixed-value.h"
46 #include "insn-config.h"
47 #include "expmed.h"
48 #include "dojump.h"
49 #include "explow.h"
50 #include "emit-rtl.h"
51 #include "varasm.h"
52 #include "stmt.h"
53 #include "expr.h"
54 #include "tree-pass.h"
55 #include "target.h"
56 #include "tree-pretty-print.h"
57 #include "predict.h"
58 #include "basic-block.h"
59 #include "hash-map.h"
60 #include "is-a.h"
61 #include "plugin-api.h"
62 #include "ipa-ref.h"
63 #include "cgraph.h"
64 #include "ipa-utils.h"
65 #include "tree-ssa-alias.h"
66 #include "internal-fn.h"
67 #include "gimple-fold.h"
68 #include "gimple-expr.h"
69 #include "gimple.h"
70 #include "alloc-pool.h"
71 #include "symbol-summary.h"
72 #include "ipa-prop.h"
73 #include "ipa-inline.h"
74 #include "diagnostic.h"
75 #include "tree-dfa.h"
76 #include "demangle.h"
77 #include "dbgcnt.h"
78 #include "gimple-pretty-print.h"
79 #include "stor-layout.h"
80 #include "intl.h"
81 #include "data-streamer.h"
82 #include "lto-streamer.h"
83 #include "streamer-hooks.h"
84 #include "tree-ssa-operands.h"
85 #include "tree-into-ssa.h"
87 /* Return true when TYPE contains an polymorphic type and thus is interesting
88 for devirtualization machinery. */
90 static bool contains_type_p (tree, HOST_WIDE_INT, tree,
91 bool consider_placement_new = true,
92 bool consider_bases = true);
94 bool
95 contains_polymorphic_type_p (const_tree type)
97 type = TYPE_MAIN_VARIANT (type);
99 if (RECORD_OR_UNION_TYPE_P (type))
101 if (TYPE_BINFO (type)
102 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
103 return true;
104 for (tree fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
105 if (TREE_CODE (fld) == FIELD_DECL
106 && !DECL_ARTIFICIAL (fld)
107 && contains_polymorphic_type_p (TREE_TYPE (fld)))
108 return true;
109 return false;
111 if (TREE_CODE (type) == ARRAY_TYPE)
112 return contains_polymorphic_type_p (TREE_TYPE (type));
113 return false;
116 /* Return true if it seems valid to use placement new to build EXPECTED_TYPE
117 at possition CUR_OFFSET within TYPE.
119 POD can be changed to an instance of a polymorphic type by
120 placement new. Here we play safe and assume that any
121 non-polymorphic type is POD. */
122 bool
123 possible_placement_new (tree type, tree expected_type,
124 HOST_WIDE_INT cur_offset)
126 return ((TREE_CODE (type) != RECORD_TYPE
127 || !TYPE_BINFO (type)
128 || cur_offset >= POINTER_SIZE
129 || !polymorphic_type_binfo_p (TYPE_BINFO (type)))
130 && (!TYPE_SIZE (type)
131 || !tree_fits_shwi_p (TYPE_SIZE (type))
132 || (cur_offset
133 + (expected_type ? tree_to_uhwi (TYPE_SIZE (expected_type))
134 : POINTER_SIZE)
135 <= tree_to_uhwi (TYPE_SIZE (type)))));
138 /* THIS->OUTER_TYPE is a type of memory object where object of OTR_TYPE
139 is contained at THIS->OFFSET. Walk the memory representation of
140 THIS->OUTER_TYPE and find the outermost class type that match
141 OTR_TYPE or contain OTR_TYPE as a base. Update THIS
142 to represent it.
144 If OTR_TYPE is NULL, just find outermost polymorphic type with
145 virtual table present at possition OFFSET.
147 For example when THIS represents type
148 class A
150 int a;
151 class B b;
153 and we look for type at offset sizeof(int), we end up with B and offset 0.
154 If the same is produced by multiple inheritance, we end up with A and offset
155 sizeof(int).
157 If we can not find corresponding class, give up by setting
158 THIS->OUTER_TYPE to OTR_TYPE and THIS->OFFSET to NULL.
159 Return true when lookup was sucesful.
161 When CONSIDER_PLACEMENT_NEW is false, reject contexts that may be made
162 valid only via alocation of new polymorphic type inside by means
163 of placement new.
165 When CONSIDER_BASES is false, only look for actual fields, not base types
166 of TYPE. */
168 bool
169 ipa_polymorphic_call_context::restrict_to_inner_class (tree otr_type,
170 bool consider_placement_new,
171 bool consider_bases)
173 tree type = outer_type;
174 HOST_WIDE_INT cur_offset = offset;
175 bool speculative = false;
176 bool size_unknown = false;
177 unsigned HOST_WIDE_INT otr_type_size = POINTER_SIZE;
179 /* Update OUTER_TYPE to match EXPECTED_TYPE if it is not set. */
180 if (!outer_type)
182 clear_outer_type (otr_type);
183 type = otr_type;
184 cur_offset = 0;
186 /* See if OFFSET points inside OUTER_TYPE. If it does not, we know
187 that the context is either invalid, or the instance type must be
188 derived from OUTER_TYPE.
190 Because the instance type may contain field whose type is of OUTER_TYPE,
191 we can not derive any effective information about it.
193 TODO: In the case we know all derrived types, we can definitely do better
194 here. */
195 else if (TYPE_SIZE (outer_type)
196 && tree_fits_shwi_p (TYPE_SIZE (outer_type))
197 && tree_to_shwi (TYPE_SIZE (outer_type)) >= 0
198 && tree_to_shwi (TYPE_SIZE (outer_type)) <= offset)
200 clear_outer_type (otr_type);
201 type = otr_type;
202 cur_offset = 0;
204 /* If derived type is not allowed, we know that the context is invalid.
205 For dynamic types, we really do not have information about
206 size of the memory location. It is possible that completely
207 different type is stored after outer_type. */
208 if (!maybe_derived_type && !dynamic)
210 clear_speculation ();
211 invalid = true;
212 return false;
216 if (otr_type && TYPE_SIZE (otr_type)
217 && tree_fits_shwi_p (TYPE_SIZE (otr_type)))
218 otr_type_size = tree_to_uhwi (TYPE_SIZE (otr_type));
220 if (!type || offset < 0)
221 goto no_useful_type_info;
223 /* Find the sub-object the constant actually refers to and mark whether it is
224 an artificial one (as opposed to a user-defined one).
226 This loop is performed twice; first time for outer_type and second time
227 for speculative_outer_type. The second run has SPECULATIVE set. */
228 while (true)
230 unsigned HOST_WIDE_INT pos, size;
231 tree fld;
233 /* If we do not know size of TYPE, we need to be more conservative
234 about accepting cases where we can not find EXPECTED_TYPE.
235 Generally the types that do matter here are of constant size.
236 Size_unknown case should be very rare. */
237 if (TYPE_SIZE (type)
238 && tree_fits_shwi_p (TYPE_SIZE (type))
239 && tree_to_shwi (TYPE_SIZE (type)) >= 0)
240 size_unknown = false;
241 else
242 size_unknown = true;
244 /* On a match, just return what we found. */
245 if ((otr_type
246 && types_odr_comparable (type, otr_type)
247 && types_same_for_odr (type, otr_type))
248 || (!otr_type
249 && TREE_CODE (type) == RECORD_TYPE
250 && TYPE_BINFO (type)
251 && polymorphic_type_binfo_p (TYPE_BINFO (type))))
253 if (speculative)
255 /* If we did not match the offset, just give up on speculation. */
256 if (cur_offset != 0
257 /* Also check if speculation did not end up being same as
258 non-speculation. */
259 || (types_must_be_same_for_odr (speculative_outer_type,
260 outer_type)
261 && (maybe_derived_type
262 == speculative_maybe_derived_type)))
263 clear_speculation ();
264 return true;
266 else
268 /* If type is known to be final, do not worry about derived
269 types. Testing it here may help us to avoid speculation. */
270 if (otr_type && TREE_CODE (outer_type) == RECORD_TYPE
271 && (!in_lto_p || odr_type_p (outer_type))
272 && type_with_linkage_p (outer_type)
273 && type_known_to_have_no_derivations_p (outer_type))
274 maybe_derived_type = false;
276 /* Type can not contain itself on an non-zero offset. In that case
277 just give up. Still accept the case where size is now known.
278 Either the second copy may appear past the end of type or within
279 the non-POD buffer located inside the variably sized type
280 itself. */
281 if (cur_offset != 0)
282 goto no_useful_type_info;
283 /* If we determined type precisely or we have no clue on
284 speuclation, we are done. */
285 if (!maybe_derived_type || !speculative_outer_type
286 || !speculation_consistent_p (speculative_outer_type,
287 speculative_offset,
288 speculative_maybe_derived_type,
289 otr_type))
291 clear_speculation ();
292 return true;
294 /* Otherwise look into speculation now. */
295 else
297 speculative = true;
298 type = speculative_outer_type;
299 cur_offset = speculative_offset;
300 continue;
305 /* Walk fields and find corresponding on at OFFSET. */
306 if (TREE_CODE (type) == RECORD_TYPE)
308 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
310 if (TREE_CODE (fld) != FIELD_DECL)
311 continue;
313 pos = int_bit_position (fld);
314 if (pos > (unsigned HOST_WIDE_INT)cur_offset)
315 continue;
317 /* Do not consider vptr itself. Not even for placement new. */
318 if (!pos && DECL_ARTIFICIAL (fld)
319 && POINTER_TYPE_P (TREE_TYPE (fld))
320 && TYPE_BINFO (type)
321 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
322 continue;
324 if (!DECL_SIZE (fld) || !tree_fits_uhwi_p (DECL_SIZE (fld)))
325 goto no_useful_type_info;
326 size = tree_to_uhwi (DECL_SIZE (fld));
328 /* We can always skip types smaller than pointer size:
329 those can not contain a virtual table pointer.
331 Disqualifying fields that are too small to fit OTR_TYPE
332 saves work needed to walk them for no benefit.
333 Because of the way the bases are packed into a class, the
334 field's size may be smaller than type size, so it needs
335 to be done with a care. */
337 if (pos <= (unsigned HOST_WIDE_INT)cur_offset
338 && (pos + size) >= (unsigned HOST_WIDE_INT)cur_offset
339 + POINTER_SIZE
340 && (!otr_type
341 || !TYPE_SIZE (TREE_TYPE (fld))
342 || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (fld)))
343 || (pos + tree_to_uhwi (TYPE_SIZE (TREE_TYPE (fld))))
344 >= cur_offset + otr_type_size))
345 break;
348 if (!fld)
349 goto no_useful_type_info;
351 type = TYPE_MAIN_VARIANT (TREE_TYPE (fld));
352 cur_offset -= pos;
353 /* DECL_ARTIFICIAL represents a basetype. */
354 if (!DECL_ARTIFICIAL (fld))
356 if (!speculative)
358 outer_type = type;
359 offset = cur_offset;
360 /* As soon as we se an field containing the type,
361 we know we are not looking for derivations. */
362 maybe_derived_type = false;
364 else
366 speculative_outer_type = type;
367 speculative_offset = cur_offset;
368 speculative_maybe_derived_type = false;
371 else if (!consider_bases)
372 goto no_useful_type_info;
374 else if (TREE_CODE (type) == ARRAY_TYPE)
376 tree subtype = TYPE_MAIN_VARIANT (TREE_TYPE (type));
378 /* Give up if we don't know array field size.
379 Also give up on non-polymorphic types as they are used
380 as buffers for placement new. */
381 if (!TYPE_SIZE (subtype)
382 || !tree_fits_shwi_p (TYPE_SIZE (subtype))
383 || tree_to_shwi (TYPE_SIZE (subtype)) <= 0
384 || !contains_polymorphic_type_p (subtype))
385 goto no_useful_type_info;
387 HOST_WIDE_INT new_offset = cur_offset % tree_to_shwi (TYPE_SIZE (subtype));
389 /* We may see buffer for placement new. In this case the expected type
390 can be bigger than the subtype. */
391 if (TYPE_SIZE (subtype)
392 && (cur_offset + otr_type_size
393 > tree_to_uhwi (TYPE_SIZE (subtype))))
394 goto no_useful_type_info;
396 cur_offset = new_offset;
397 type = TYPE_MAIN_VARIANT (subtype);
398 if (!speculative)
400 outer_type = type;
401 offset = cur_offset;
402 maybe_derived_type = false;
404 else
406 speculative_outer_type = type;
407 speculative_offset = cur_offset;
408 speculative_maybe_derived_type = false;
411 /* Give up on anything else. */
412 else
414 no_useful_type_info:
415 if (maybe_derived_type && !speculative
416 && TREE_CODE (outer_type) == RECORD_TYPE
417 && TREE_CODE (otr_type) == RECORD_TYPE
418 && TYPE_BINFO (otr_type)
419 && !offset
420 && get_binfo_at_offset (TYPE_BINFO (otr_type), 0, outer_type))
422 clear_outer_type (otr_type);
423 if (!speculative_outer_type
424 || !speculation_consistent_p (speculative_outer_type,
425 speculative_offset,
426 speculative_maybe_derived_type,
427 otr_type))
428 clear_speculation ();
429 if (speculative_outer_type)
431 speculative = true;
432 type = speculative_outer_type;
433 cur_offset = speculative_offset;
435 else
436 return true;
438 /* We found no way to embedd EXPECTED_TYPE in TYPE.
439 We still permit two special cases - placement new and
440 the case of variadic types containing themselves. */
441 if (!speculative
442 && consider_placement_new
443 && (size_unknown || !type || maybe_derived_type
444 || possible_placement_new (type, otr_type, cur_offset)))
446 /* In these weird cases we want to accept the context.
447 In non-speculative run we have no useful outer_type info
448 (TODO: we may eventually want to record upper bound on the
449 type size that can be used to prune the walk),
450 but we still want to consider speculation that may
451 give useful info. */
452 if (!speculative)
454 clear_outer_type (otr_type);
455 if (!speculative_outer_type
456 || !speculation_consistent_p (speculative_outer_type,
457 speculative_offset,
458 speculative_maybe_derived_type,
459 otr_type))
460 clear_speculation ();
461 if (speculative_outer_type)
463 speculative = true;
464 type = speculative_outer_type;
465 cur_offset = speculative_offset;
467 else
468 return true;
470 else
471 clear_speculation ();
472 return true;
474 else
476 clear_speculation ();
477 if (speculative)
478 return true;
479 clear_outer_type (otr_type);
480 invalid = true;
481 return false;
487 /* Return true if OUTER_TYPE contains OTR_TYPE at OFFSET.
488 CONSIDER_PLACEMENT_NEW makes function to accept cases where OTR_TYPE can
489 be built within OUTER_TYPE by means of placement new. CONSIDER_BASES makes
490 function to accept cases where OTR_TYPE appears as base of OUTER_TYPE or as
491 base of one of fields of OUTER_TYPE. */
493 static bool
494 contains_type_p (tree outer_type, HOST_WIDE_INT offset,
495 tree otr_type,
496 bool consider_placement_new,
497 bool consider_bases)
499 ipa_polymorphic_call_context context;
501 /* Check that type is within range. */
502 if (offset < 0)
503 return false;
504 if (TYPE_SIZE (outer_type) && TYPE_SIZE (otr_type)
505 && TREE_CODE (outer_type) == INTEGER_CST
506 && TREE_CODE (otr_type) == INTEGER_CST
507 && wi::ltu_p (wi::to_offset (outer_type), (wi::to_offset (otr_type) + offset)))
508 return false;
510 context.offset = offset;
511 context.outer_type = TYPE_MAIN_VARIANT (outer_type);
512 context.maybe_derived_type = false;
513 return context.restrict_to_inner_class (otr_type, consider_placement_new, consider_bases);
517 /* Return a FUNCTION_DECL if BLOCK represents a constructor or destructor.
518 If CHECK_CLONES is true, also check for clones of ctor/dtors. */
520 tree
521 inlined_polymorphic_ctor_dtor_block_p (tree block, bool check_clones)
523 tree fn = BLOCK_ABSTRACT_ORIGIN (block);
524 if (fn == NULL || TREE_CODE (fn) != FUNCTION_DECL)
525 return NULL_TREE;
527 if (TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
528 || (!DECL_CXX_CONSTRUCTOR_P (fn) && !DECL_CXX_DESTRUCTOR_P (fn)))
530 if (!check_clones)
531 return NULL_TREE;
533 /* Watch for clones where we constant propagated the first
534 argument (pointer to the instance). */
535 fn = DECL_ABSTRACT_ORIGIN (fn);
536 if (!fn
537 || TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
538 || (!DECL_CXX_CONSTRUCTOR_P (fn) && !DECL_CXX_DESTRUCTOR_P (fn)))
539 return NULL_TREE;
542 if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
543 return NULL_TREE;
545 return fn;
549 /* We know that the instance is stored in variable or parameter
550 (not dynamically allocated) and we want to disprove the fact
551 that it may be in construction at invocation of CALL.
553 BASE represents memory location where instance is stored.
554 If BASE is NULL, it is assumed to be global memory.
555 OUTER_TYPE is known type of the instance or NULL if not
556 known.
558 For the variable to be in construction we actually need to
559 be in constructor of corresponding global variable or
560 the inline stack of CALL must contain the constructor.
561 Check this condition. This check works safely only before
562 IPA passes, because inline stacks may become out of date
563 later. */
565 bool
566 decl_maybe_in_construction_p (tree base, tree outer_type,
567 gimple call, tree function)
569 if (outer_type)
570 outer_type = TYPE_MAIN_VARIANT (outer_type);
571 gcc_assert (!base || DECL_P (base));
573 /* After inlining the code unification optimizations may invalidate
574 inline stacks. Also we need to give up on global variables after
575 IPA, because addresses of these may have been propagated to their
576 constructors. */
577 if (DECL_STRUCT_FUNCTION (function)->after_inlining)
578 return true;
580 /* Pure functions can not do any changes on the dynamic type;
581 that require writting to memory. */
582 if ((!base || !auto_var_in_fn_p (base, function))
583 && flags_from_decl_or_type (function) & (ECF_PURE | ECF_CONST))
584 return false;
586 bool check_clones = !base || is_global_var (base);
587 for (tree block = gimple_block (call); block && TREE_CODE (block) == BLOCK;
588 block = BLOCK_SUPERCONTEXT (block))
589 if (tree fn = inlined_polymorphic_ctor_dtor_block_p (block, check_clones))
591 tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (fn)));
593 if (!outer_type || !types_odr_comparable (type, outer_type))
595 if (TREE_CODE (type) == RECORD_TYPE
596 && TYPE_BINFO (type)
597 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
598 return true;
600 else if (types_same_for_odr (type, outer_type))
601 return true;
604 if (!base || (TREE_CODE (base) == VAR_DECL && is_global_var (base)))
606 if (TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
607 || (!DECL_CXX_CONSTRUCTOR_P (function)
608 && !DECL_CXX_DESTRUCTOR_P (function)))
610 if (!DECL_ABSTRACT_ORIGIN (function))
611 return false;
612 /* Watch for clones where we constant propagated the first
613 argument (pointer to the instance). */
614 function = DECL_ABSTRACT_ORIGIN (function);
615 if (!function
616 || TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
617 || (!DECL_CXX_CONSTRUCTOR_P (function)
618 && !DECL_CXX_DESTRUCTOR_P (function)))
619 return false;
621 tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (function)));
622 if (!outer_type || !types_odr_comparable (type, outer_type))
624 if (TREE_CODE (type) == RECORD_TYPE
625 && TYPE_BINFO (type)
626 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
627 return true;
629 else if (types_same_for_odr (type, outer_type))
630 return true;
632 return false;
635 /* Dump human readable context to F. If NEWLINE is true, it will be terminated
636 by a newline. */
638 void
639 ipa_polymorphic_call_context::dump (FILE *f, bool newline) const
641 fprintf (f, " ");
642 if (invalid)
643 fprintf (f, "Call is known to be undefined");
644 else
646 if (useless_p ())
647 fprintf (f, "nothing known");
648 if (outer_type || offset)
650 fprintf (f, "Outer type%s:", dynamic ? " (dynamic)":"");
651 print_generic_expr (f, outer_type, TDF_SLIM);
652 if (maybe_derived_type)
653 fprintf (f, " (or a derived type)");
654 if (maybe_in_construction)
655 fprintf (f, " (maybe in construction)");
656 fprintf (f, " offset " HOST_WIDE_INT_PRINT_DEC,
657 offset);
659 if (speculative_outer_type)
661 if (outer_type || offset)
662 fprintf (f, " ");
663 fprintf (f, "Speculative outer type:");
664 print_generic_expr (f, speculative_outer_type, TDF_SLIM);
665 if (speculative_maybe_derived_type)
666 fprintf (f, " (or a derived type)");
667 fprintf (f, " at offset " HOST_WIDE_INT_PRINT_DEC,
668 speculative_offset);
671 if (newline)
672 fprintf(f, "\n");
675 /* Print context to stderr. */
677 void
678 ipa_polymorphic_call_context::debug () const
680 dump (stderr);
683 /* Stream out the context to OB. */
685 void
686 ipa_polymorphic_call_context::stream_out (struct output_block *ob) const
688 struct bitpack_d bp = bitpack_create (ob->main_stream);
690 bp_pack_value (&bp, invalid, 1);
691 bp_pack_value (&bp, maybe_in_construction, 1);
692 bp_pack_value (&bp, maybe_derived_type, 1);
693 bp_pack_value (&bp, speculative_maybe_derived_type, 1);
694 bp_pack_value (&bp, dynamic, 1);
695 bp_pack_value (&bp, outer_type != NULL, 1);
696 bp_pack_value (&bp, offset != 0, 1);
697 bp_pack_value (&bp, speculative_outer_type != NULL, 1);
698 streamer_write_bitpack (&bp);
700 if (outer_type != NULL)
701 stream_write_tree (ob, outer_type, true);
702 if (offset)
703 streamer_write_hwi (ob, offset);
704 if (speculative_outer_type != NULL)
706 stream_write_tree (ob, speculative_outer_type, true);
707 streamer_write_hwi (ob, speculative_offset);
709 else
710 gcc_assert (!speculative_offset);
713 /* Stream in the context from IB and DATA_IN. */
715 void
716 ipa_polymorphic_call_context::stream_in (struct lto_input_block *ib,
717 struct data_in *data_in)
719 struct bitpack_d bp = streamer_read_bitpack (ib);
721 invalid = bp_unpack_value (&bp, 1);
722 maybe_in_construction = bp_unpack_value (&bp, 1);
723 maybe_derived_type = bp_unpack_value (&bp, 1);
724 speculative_maybe_derived_type = bp_unpack_value (&bp, 1);
725 dynamic = bp_unpack_value (&bp, 1);
726 bool outer_type_p = bp_unpack_value (&bp, 1);
727 bool offset_p = bp_unpack_value (&bp, 1);
728 bool speculative_outer_type_p = bp_unpack_value (&bp, 1);
730 if (outer_type_p)
731 outer_type = stream_read_tree (ib, data_in);
732 else
733 outer_type = NULL;
734 if (offset_p)
735 offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
736 else
737 offset = 0;
738 if (speculative_outer_type_p)
740 speculative_outer_type = stream_read_tree (ib, data_in);
741 speculative_offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
743 else
745 speculative_outer_type = NULL;
746 speculative_offset = 0;
750 /* Proudce polymorphic call context for call method of instance
751 that is located within BASE (that is assumed to be a decl) at offset OFF. */
753 void
754 ipa_polymorphic_call_context::set_by_decl (tree base, HOST_WIDE_INT off)
756 gcc_assert (DECL_P (base));
757 clear_speculation ();
759 if (!contains_polymorphic_type_p (TREE_TYPE (base)))
761 clear_outer_type ();
762 offset = off;
763 return;
765 outer_type = TYPE_MAIN_VARIANT (TREE_TYPE (base));
766 offset = off;
767 /* Make very conservative assumption that all objects
768 may be in construction.
770 It is up to caller to revisit this via
771 get_dynamic_type or decl_maybe_in_construction_p. */
772 maybe_in_construction = true;
773 maybe_derived_type = false;
774 dynamic = false;
777 /* CST is an invariant (address of decl), try to get meaningful
778 polymorphic call context for polymorphic call of method
779 if instance of OTR_TYPE that is located at offset OFF of this invariant.
780 Return FALSE if nothing meaningful can be found. */
782 bool
783 ipa_polymorphic_call_context::set_by_invariant (tree cst,
784 tree otr_type,
785 HOST_WIDE_INT off)
787 HOST_WIDE_INT offset2, size, max_size;
788 tree base;
790 invalid = false;
791 off = 0;
792 clear_outer_type (otr_type);
794 if (TREE_CODE (cst) != ADDR_EXPR)
795 return false;
797 cst = TREE_OPERAND (cst, 0);
798 base = get_ref_base_and_extent (cst, &offset2, &size, &max_size);
799 if (!DECL_P (base) || max_size == -1 || max_size != size)
800 return false;
802 /* Only type inconsistent programs can have otr_type that is
803 not part of outer type. */
804 if (otr_type && !contains_type_p (TREE_TYPE (base), off, otr_type))
805 return false;
807 set_by_decl (base, off);
808 return true;
811 /* See if OP is SSA name initialized as a copy or by single assignment.
812 If so, walk the SSA graph up. Because simple PHI conditional is considered
813 copy, GLOBAL_VISITED may be used to avoid infinite loop walking the SSA
814 graph. */
816 static tree
817 walk_ssa_copies (tree op, hash_set<tree> **global_visited = NULL)
819 hash_set <tree> *visited = NULL;
820 STRIP_NOPS (op);
821 while (TREE_CODE (op) == SSA_NAME
822 && !SSA_NAME_IS_DEFAULT_DEF (op)
823 /* We might be called via fold_stmt during cfgcleanup where
824 SSA form need not be up-to-date. */
825 && !name_registered_for_update_p (op)
826 && (gimple_assign_single_p (SSA_NAME_DEF_STMT (op))
827 || gimple_code (SSA_NAME_DEF_STMT (op)) == GIMPLE_PHI))
829 if (global_visited)
831 if (!*global_visited)
832 *global_visited = new hash_set<tree>;
833 if ((*global_visited)->add (op))
834 goto done;
836 else
838 if (!visited)
839 visited = new hash_set<tree>;
840 if (visited->add (op))
841 goto done;
843 /* Special case
844 if (ptr == 0)
845 ptr = 0;
846 else
847 ptr = ptr.foo;
848 This pattern is implicitly produced for casts to non-primary
849 bases. When doing context analysis, we do not really care
850 about the case pointer is NULL, becuase the call will be
851 undefined anyway. */
852 if (gimple_code (SSA_NAME_DEF_STMT (op)) == GIMPLE_PHI)
854 gimple phi = SSA_NAME_DEF_STMT (op);
856 if (gimple_phi_num_args (phi) > 2)
857 goto done;
858 if (gimple_phi_num_args (phi) == 1)
859 op = gimple_phi_arg_def (phi, 0);
860 else if (integer_zerop (gimple_phi_arg_def (phi, 0)))
861 op = gimple_phi_arg_def (phi, 1);
862 else if (integer_zerop (gimple_phi_arg_def (phi, 1)))
863 op = gimple_phi_arg_def (phi, 0);
864 else
865 goto done;
867 else
869 if (gimple_assign_load_p (SSA_NAME_DEF_STMT (op)))
870 goto done;
871 op = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op));
873 STRIP_NOPS (op);
875 done:
876 if (visited)
877 delete (visited);
878 return op;
881 /* Create polymorphic call context from IP invariant CST.
882 This is typically &global_var.
883 OTR_TYPE specify type of polymorphic call or NULL if unknown, OFF
884 is offset of call. */
886 ipa_polymorphic_call_context::ipa_polymorphic_call_context (tree cst,
887 tree otr_type,
888 HOST_WIDE_INT off)
890 clear_speculation ();
891 set_by_invariant (cst, otr_type, off);
894 /* Build context for pointer REF contained in FNDECL at statement STMT.
895 if INSTANCE is non-NULL, return pointer to the object described by
896 the context or DECL where context is contained in. */
898 ipa_polymorphic_call_context::ipa_polymorphic_call_context (tree fndecl,
899 tree ref,
900 gimple stmt,
901 tree *instance)
903 tree otr_type = NULL;
904 tree base_pointer;
905 hash_set <tree> *visited = NULL;
907 if (TREE_CODE (ref) == OBJ_TYPE_REF)
909 otr_type = obj_type_ref_class (ref);
910 base_pointer = OBJ_TYPE_REF_OBJECT (ref);
912 else
913 base_pointer = ref;
915 /* Set up basic info in case we find nothing interesting in the analysis. */
916 clear_speculation ();
917 clear_outer_type (otr_type);
918 invalid = false;
920 /* Walk SSA for outer object. */
921 while (true)
923 base_pointer = walk_ssa_copies (base_pointer, &visited);
924 if (TREE_CODE (base_pointer) == ADDR_EXPR)
926 HOST_WIDE_INT size, max_size;
927 HOST_WIDE_INT offset2;
928 tree base = get_ref_base_and_extent (TREE_OPERAND (base_pointer, 0),
929 &offset2, &size, &max_size);
931 if (max_size != -1 && max_size == size)
932 combine_speculation_with (TYPE_MAIN_VARIANT (TREE_TYPE (base)),
933 offset + offset2,
934 true,
935 NULL /* Do not change outer type. */);
937 /* If this is a varying address, punt. */
938 if ((TREE_CODE (base) == MEM_REF || DECL_P (base))
939 && max_size != -1
940 && max_size == size)
942 /* We found dereference of a pointer. Type of the pointer
943 and MEM_REF is meaningless, but we can look futher. */
944 if (TREE_CODE (base) == MEM_REF)
946 base_pointer = TREE_OPERAND (base, 0);
947 offset
948 += offset2 + mem_ref_offset (base).to_short_addr () * BITS_PER_UNIT;
949 outer_type = NULL;
951 /* We found base object. In this case the outer_type
952 is known. */
953 else if (DECL_P (base))
955 if (visited)
956 delete (visited);
957 /* Only type inconsistent programs can have otr_type that is
958 not part of outer type. */
959 if (otr_type
960 && !contains_type_p (TREE_TYPE (base),
961 offset + offset2, otr_type))
963 invalid = true;
964 if (instance)
965 *instance = base_pointer;
966 return;
968 set_by_decl (base, offset + offset2);
969 if (outer_type && maybe_in_construction && stmt)
970 maybe_in_construction
971 = decl_maybe_in_construction_p (base,
972 outer_type,
973 stmt,
974 fndecl);
975 if (instance)
976 *instance = base;
977 return;
979 else
980 break;
982 else
983 break;
985 else if (TREE_CODE (base_pointer) == POINTER_PLUS_EXPR
986 && tree_fits_uhwi_p (TREE_OPERAND (base_pointer, 1)))
988 offset += tree_to_shwi (TREE_OPERAND (base_pointer, 1))
989 * BITS_PER_UNIT;
990 base_pointer = TREE_OPERAND (base_pointer, 0);
992 else
993 break;
996 if (visited)
997 delete (visited);
999 /* Try to determine type of the outer object. */
1000 if (TREE_CODE (base_pointer) == SSA_NAME
1001 && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
1002 && TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL)
1004 /* See if parameter is THIS pointer of a method. */
1005 if (TREE_CODE (TREE_TYPE (fndecl)) == METHOD_TYPE
1006 && SSA_NAME_VAR (base_pointer) == DECL_ARGUMENTS (fndecl))
1008 outer_type
1009 = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
1010 gcc_assert (TREE_CODE (outer_type) == RECORD_TYPE
1011 || TREE_CODE (outer_type) == UNION_TYPE);
1013 /* Dynamic casting has possibly upcasted the type
1014 in the hiearchy. In this case outer type is less
1015 informative than inner type and we should forget
1016 about it. */
1017 if ((otr_type
1018 && !contains_type_p (outer_type, offset,
1019 otr_type))
1020 || !contains_polymorphic_type_p (outer_type))
1022 outer_type = NULL;
1023 if (instance)
1024 *instance = base_pointer;
1025 return;
1028 dynamic = true;
1030 /* If the function is constructor or destructor, then
1031 the type is possibly in construction, but we know
1032 it is not derived type. */
1033 if (DECL_CXX_CONSTRUCTOR_P (fndecl)
1034 || DECL_CXX_DESTRUCTOR_P (fndecl))
1036 maybe_in_construction = true;
1037 maybe_derived_type = false;
1039 else
1041 maybe_derived_type = true;
1042 maybe_in_construction = false;
1044 if (instance)
1045 *instance = base_pointer;
1046 return;
1048 /* Non-PODs passed by value are really passed by invisible
1049 reference. In this case we also know the type of the
1050 object. */
1051 if (DECL_BY_REFERENCE (SSA_NAME_VAR (base_pointer)))
1053 outer_type
1054 = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
1055 /* Only type inconsistent programs can have otr_type that is
1056 not part of outer type. */
1057 if (otr_type && !contains_type_p (outer_type, offset,
1058 otr_type))
1060 invalid = true;
1061 if (instance)
1062 *instance = base_pointer;
1063 return;
1065 /* Non-polymorphic types have no interest for us. */
1066 else if (!otr_type && !contains_polymorphic_type_p (outer_type))
1068 outer_type = NULL;
1069 if (instance)
1070 *instance = base_pointer;
1071 return;
1073 maybe_derived_type = false;
1074 maybe_in_construction = false;
1075 if (instance)
1076 *instance = base_pointer;
1077 return;
1081 tree base_type = TREE_TYPE (base_pointer);
1083 if (TREE_CODE (base_pointer) == SSA_NAME
1084 && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
1085 && !(TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL
1086 || TREE_CODE (SSA_NAME_VAR (base_pointer)) == RESULT_DECL))
1088 invalid = true;
1089 if (instance)
1090 *instance = base_pointer;
1091 return;
1093 if (TREE_CODE (base_pointer) == SSA_NAME
1094 && SSA_NAME_DEF_STMT (base_pointer)
1095 && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer)))
1096 base_type = TREE_TYPE (gimple_assign_rhs1
1097 (SSA_NAME_DEF_STMT (base_pointer)));
1099 if (base_type && POINTER_TYPE_P (base_type))
1100 combine_speculation_with (TYPE_MAIN_VARIANT (TREE_TYPE (base_type)),
1101 offset,
1102 true, NULL /* Do not change type here */);
1103 /* TODO: There are multiple ways to derive a type. For instance
1104 if BASE_POINTER is passed to an constructor call prior our refernece.
1105 We do not make this type of flow sensitive analysis yet. */
1106 if (instance)
1107 *instance = base_pointer;
1108 return;
1111 /* Structure to be passed in between detect_type_change and
1112 check_stmt_for_type_change. */
1114 struct type_change_info
1116 /* Offset into the object where there is the virtual method pointer we are
1117 looking for. */
1118 HOST_WIDE_INT offset;
1119 /* The declaration or SSA_NAME pointer of the base that we are checking for
1120 type change. */
1121 tree instance;
1122 /* The reference to virtual table pointer used. */
1123 tree vtbl_ptr_ref;
1124 tree otr_type;
1125 /* If we actually can tell the type that the object has changed to, it is
1126 stored in this field. Otherwise it remains NULL_TREE. */
1127 tree known_current_type;
1128 HOST_WIDE_INT known_current_offset;
1130 /* Set to true if dynamic type change has been detected. */
1131 bool type_maybe_changed;
1132 /* Set to true if multiple types have been encountered. known_current_type
1133 must be disregarded in that case. */
1134 bool multiple_types_encountered;
1135 /* Set to true if we possibly missed some dynamic type changes and we should
1136 consider the set to be speculative. */
1137 bool speculative;
1138 bool seen_unanalyzed_store;
1141 /* Return true if STMT is not call and can modify a virtual method table pointer.
1142 We take advantage of fact that vtable stores must appear within constructor
1143 and destructor functions. */
1145 static bool
1146 noncall_stmt_may_be_vtbl_ptr_store (gimple stmt)
1148 if (is_gimple_assign (stmt))
1150 tree lhs = gimple_assign_lhs (stmt);
1152 if (gimple_clobber_p (stmt))
1153 return false;
1154 if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
1156 if (flag_strict_aliasing
1157 && !POINTER_TYPE_P (TREE_TYPE (lhs)))
1158 return false;
1160 if (TREE_CODE (lhs) == COMPONENT_REF
1161 && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
1162 return false;
1163 /* In the future we might want to use get_base_ref_and_offset to find
1164 if there is a field corresponding to the offset and if so, proceed
1165 almost like if it was a component ref. */
1169 /* Code unification may mess with inline stacks. */
1170 if (cfun->after_inlining)
1171 return true;
1173 /* Walk the inline stack and watch out for ctors/dtors.
1174 TODO: Maybe we can require the store to appear in toplevel
1175 block of CTOR/DTOR. */
1176 for (tree block = gimple_block (stmt); block && TREE_CODE (block) == BLOCK;
1177 block = BLOCK_SUPERCONTEXT (block))
1178 if (BLOCK_ABSTRACT_ORIGIN (block)
1179 && TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block)) == FUNCTION_DECL)
1180 return inlined_polymorphic_ctor_dtor_block_p (block, false);
1181 return (TREE_CODE (TREE_TYPE (current_function_decl)) == METHOD_TYPE
1182 && (DECL_CXX_CONSTRUCTOR_P (current_function_decl)
1183 || DECL_CXX_DESTRUCTOR_P (current_function_decl)));
1186 /* If STMT can be proved to be an assignment to the virtual method table
1187 pointer of ANALYZED_OBJ and the type associated with the new table
1188 identified, return the type. Otherwise return NULL_TREE if type changes
1189 in unknown way or ERROR_MARK_NODE if type is unchanged. */
1191 static tree
1192 extr_type_from_vtbl_ptr_store (gimple stmt, struct type_change_info *tci,
1193 HOST_WIDE_INT *type_offset)
1195 HOST_WIDE_INT offset, size, max_size;
1196 tree lhs, rhs, base;
1198 if (!gimple_assign_single_p (stmt))
1199 return NULL_TREE;
1201 lhs = gimple_assign_lhs (stmt);
1202 rhs = gimple_assign_rhs1 (stmt);
1203 if (TREE_CODE (lhs) != COMPONENT_REF
1204 || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
1206 if (dump_file)
1207 fprintf (dump_file, " LHS is not virtual table.\n");
1208 return NULL_TREE;
1211 if (tci->vtbl_ptr_ref && operand_equal_p (lhs, tci->vtbl_ptr_ref, 0))
1213 else
1215 base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
1216 if (DECL_P (tci->instance))
1218 if (base != tci->instance)
1220 if (dump_file)
1222 fprintf (dump_file, " base:");
1223 print_generic_expr (dump_file, base, TDF_SLIM);
1224 fprintf (dump_file, " does not match instance:");
1225 print_generic_expr (dump_file, tci->instance, TDF_SLIM);
1226 fprintf (dump_file, "\n");
1228 return NULL_TREE;
1231 else if (TREE_CODE (base) == MEM_REF)
1233 if (!operand_equal_p (tci->instance, TREE_OPERAND (base, 0), 0))
1235 if (dump_file)
1237 fprintf (dump_file, " base mem ref:");
1238 print_generic_expr (dump_file, base, TDF_SLIM);
1239 fprintf (dump_file, " does not match instance:");
1240 print_generic_expr (dump_file, tci->instance, TDF_SLIM);
1241 fprintf (dump_file, "\n");
1243 return NULL_TREE;
1245 if (!integer_zerop (TREE_OPERAND (base, 1)))
1247 if (!tree_fits_shwi_p (TREE_OPERAND (base, 1)))
1249 if (dump_file)
1251 fprintf (dump_file, " base mem ref:");
1252 print_generic_expr (dump_file, base, TDF_SLIM);
1253 fprintf (dump_file, " has non-representable offset:");
1254 print_generic_expr (dump_file, tci->instance, TDF_SLIM);
1255 fprintf (dump_file, "\n");
1257 return NULL_TREE;
1259 else
1260 offset += tree_to_shwi (TREE_OPERAND (base, 1)) * BITS_PER_UNIT;
1263 else if (!operand_equal_p (tci->instance, base, 0)
1264 || tci->offset)
1266 if (dump_file)
1268 fprintf (dump_file, " base:");
1269 print_generic_expr (dump_file, base, TDF_SLIM);
1270 fprintf (dump_file, " does not match instance:");
1271 print_generic_expr (dump_file, tci->instance, TDF_SLIM);
1272 fprintf (dump_file, " with offset %i\n", (int)tci->offset);
1274 return tci->offset > POINTER_SIZE ? error_mark_node : NULL_TREE;
1276 if (offset != tci->offset
1277 || size != POINTER_SIZE
1278 || max_size != POINTER_SIZE)
1280 if (dump_file)
1281 fprintf (dump_file, " wrong offset %i!=%i or size %i\n",
1282 (int)offset, (int)tci->offset, (int)size);
1283 return offset + POINTER_SIZE <= tci->offset
1284 || (max_size != -1
1285 && tci->offset + POINTER_SIZE > offset + max_size)
1286 ? error_mark_node : NULL;
1290 tree vtable;
1291 unsigned HOST_WIDE_INT offset2;
1293 if (!vtable_pointer_value_to_vtable (rhs, &vtable, &offset2))
1295 if (dump_file)
1296 fprintf (dump_file, " Failed to lookup binfo\n");
1297 return NULL;
1300 tree binfo = subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
1301 offset2, vtable);
1302 if (!binfo)
1304 if (dump_file)
1305 fprintf (dump_file, " Construction vtable used\n");
1306 /* FIXME: We should suport construction contexts. */
1307 return NULL;
1310 *type_offset = tree_to_shwi (BINFO_OFFSET (binfo)) * BITS_PER_UNIT;
1311 return DECL_CONTEXT (vtable);
1314 /* Record dynamic type change of TCI to TYPE. */
1316 static void
1317 record_known_type (struct type_change_info *tci, tree type, HOST_WIDE_INT offset)
1319 if (dump_file)
1321 if (type)
1323 fprintf (dump_file, " Recording type: ");
1324 print_generic_expr (dump_file, type, TDF_SLIM);
1325 fprintf (dump_file, " at offset %i\n", (int)offset);
1327 else
1328 fprintf (dump_file, " Recording unknown type\n");
1331 /* If we found a constructor of type that is not polymorphic or
1332 that may contain the type in question as a field (not as base),
1333 restrict to the inner class first to make type matching bellow
1334 happier. */
1335 if (type
1336 && (offset
1337 || (TREE_CODE (type) != RECORD_TYPE
1338 || !TYPE_BINFO (type)
1339 || !polymorphic_type_binfo_p (TYPE_BINFO (type)))))
1341 ipa_polymorphic_call_context context;
1343 context.offset = offset;
1344 context.outer_type = type;
1345 context.maybe_in_construction = false;
1346 context.maybe_derived_type = false;
1347 context.dynamic = true;
1348 /* If we failed to find the inner type, we know that the call
1349 would be undefined for type produced here. */
1350 if (!context.restrict_to_inner_class (tci->otr_type))
1352 if (dump_file)
1353 fprintf (dump_file, " Ignoring; does not contain otr_type\n");
1354 return;
1356 /* Watch for case we reached an POD type and anticipate placement
1357 new. */
1358 if (!context.maybe_derived_type)
1360 type = context.outer_type;
1361 offset = context.offset;
1364 if (tci->type_maybe_changed
1365 && (!types_same_for_odr (type, tci->known_current_type)
1366 || offset != tci->known_current_offset))
1367 tci->multiple_types_encountered = true;
1368 tci->known_current_type = TYPE_MAIN_VARIANT (type);
1369 tci->known_current_offset = offset;
1370 tci->type_maybe_changed = true;
1373 /* Callback of walk_aliased_vdefs and a helper function for
1374 detect_type_change to check whether a particular statement may modify
1375 the virtual table pointer, and if possible also determine the new type of
1376 the (sub-)object. It stores its result into DATA, which points to a
1377 type_change_info structure. */
1379 static bool
1380 check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
1382 gimple stmt = SSA_NAME_DEF_STMT (vdef);
1383 struct type_change_info *tci = (struct type_change_info *) data;
1384 tree fn;
1386 /* If we already gave up, just terminate the rest of walk. */
1387 if (tci->multiple_types_encountered)
1388 return true;
1390 if (is_gimple_call (stmt))
1392 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
1393 return false;
1395 /* Check for a constructor call. */
1396 if ((fn = gimple_call_fndecl (stmt)) != NULL_TREE
1397 && DECL_CXX_CONSTRUCTOR_P (fn)
1398 && TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
1399 && gimple_call_num_args (stmt))
1401 tree op = walk_ssa_copies (gimple_call_arg (stmt, 0));
1402 tree type = method_class_type (TREE_TYPE (fn));
1403 HOST_WIDE_INT offset = 0, size, max_size;
1405 if (dump_file)
1407 fprintf (dump_file, " Checking constructor call: ");
1408 print_gimple_stmt (dump_file, stmt, 0, 0);
1411 /* See if THIS parameter seems like instance pointer. */
1412 if (TREE_CODE (op) == ADDR_EXPR)
1414 op = get_ref_base_and_extent (TREE_OPERAND (op, 0),
1415 &offset, &size, &max_size);
1416 if (size != max_size || max_size == -1)
1418 tci->speculative = true;
1419 return false;
1421 if (op && TREE_CODE (op) == MEM_REF)
1423 if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
1425 tci->speculative = true;
1426 return false;
1428 offset += tree_to_shwi (TREE_OPERAND (op, 1))
1429 * BITS_PER_UNIT;
1430 op = TREE_OPERAND (op, 0);
1432 else if (DECL_P (op))
1434 else
1436 tci->speculative = true;
1437 return false;
1439 op = walk_ssa_copies (op);
1441 if (operand_equal_p (op, tci->instance, 0)
1442 && TYPE_SIZE (type)
1443 && TREE_CODE (TYPE_SIZE (type)) == INTEGER_CST
1444 && tree_fits_shwi_p (TYPE_SIZE (type))
1445 && tree_to_shwi (TYPE_SIZE (type)) + offset > tci->offset)
1447 record_known_type (tci, type, tci->offset - offset);
1448 return true;
1451 /* Calls may possibly change dynamic type by placement new. Assume
1452 it will not happen, but make result speculative only. */
1453 if (dump_file)
1455 fprintf (dump_file, " Function call may change dynamic type:");
1456 print_gimple_stmt (dump_file, stmt, 0, 0);
1458 tci->speculative = true;
1459 return false;
1461 /* Check for inlined virtual table store. */
1462 else if (noncall_stmt_may_be_vtbl_ptr_store (stmt))
1464 tree type;
1465 HOST_WIDE_INT offset = 0;
1466 if (dump_file)
1468 fprintf (dump_file, " Checking vtbl store: ");
1469 print_gimple_stmt (dump_file, stmt, 0, 0);
1472 type = extr_type_from_vtbl_ptr_store (stmt, tci, &offset);
1473 if (type == error_mark_node)
1474 return false;
1475 gcc_assert (!type || TYPE_MAIN_VARIANT (type) == type);
1476 if (!type)
1478 if (dump_file)
1479 fprintf (dump_file, " Unanalyzed store may change type.\n");
1480 tci->seen_unanalyzed_store = true;
1481 tci->speculative = true;
1483 else
1484 record_known_type (tci, type, offset);
1485 return true;
1487 else
1488 return false;
1491 /* THIS is polymorphic call context obtained from get_polymorphic_context.
1492 OTR_OBJECT is pointer to the instance returned by OBJ_TYPE_REF_OBJECT.
1493 INSTANCE is pointer to the outer instance as returned by
1494 get_polymorphic_context. To avoid creation of temporary expressions,
1495 INSTANCE may also be an declaration of get_polymorphic_context found the
1496 value to be in static storage.
1498 If the type of instance is not fully determined
1499 (either OUTER_TYPE is unknown or MAYBE_IN_CONSTRUCTION/INCLUDE_DERIVED_TYPES
1500 is set), try to walk memory writes and find the actual construction of the
1501 instance.
1503 Return true if memory is unchanged from function entry.
1505 We do not include this analysis in the context analysis itself, because
1506 it needs memory SSA to be fully built and the walk may be expensive.
1507 So it is not suitable for use withing fold_stmt and similar uses. */
1509 bool
1510 ipa_polymorphic_call_context::get_dynamic_type (tree instance,
1511 tree otr_object,
1512 tree otr_type,
1513 gimple call)
1515 struct type_change_info tci;
1516 ao_ref ao;
1517 bool function_entry_reached = false;
1518 tree instance_ref = NULL;
1519 gimple stmt = call;
1520 /* Remember OFFSET before it is modified by restrict_to_inner_class.
1521 This is because we do not update INSTANCE when walking inwards. */
1522 HOST_WIDE_INT instance_offset = offset;
1524 if (otr_type)
1525 otr_type = TYPE_MAIN_VARIANT (otr_type);
1527 /* Walk into inner type. This may clear maybe_derived_type and save us
1528 from useless work. It also makes later comparsions with static type
1529 easier. */
1530 if (outer_type && otr_type)
1532 if (!restrict_to_inner_class (otr_type))
1533 return false;
1536 if (!maybe_in_construction && !maybe_derived_type)
1537 return false;
1539 /* We need to obtain refernce to virtual table pointer. It is better
1540 to look it up in the code rather than build our own. This require bit
1541 of pattern matching, but we end up verifying that what we found is
1542 correct.
1544 What we pattern match is:
1546 tmp = instance->_vptr.A; // vtbl ptr load
1547 tmp2 = tmp[otr_token]; // vtable lookup
1548 OBJ_TYPE_REF(tmp2;instance->0) (instance);
1550 We want to start alias oracle walk from vtbl pointer load,
1551 but we may not be able to identify it, for example, when PRE moved the
1552 load around. */
1554 if (gimple_code (call) == GIMPLE_CALL)
1556 tree ref = gimple_call_fn (call);
1557 HOST_WIDE_INT offset2, size, max_size;
1559 if (TREE_CODE (ref) == OBJ_TYPE_REF)
1561 ref = OBJ_TYPE_REF_EXPR (ref);
1562 ref = walk_ssa_copies (ref);
1564 /* Check if definition looks like vtable lookup. */
1565 if (TREE_CODE (ref) == SSA_NAME
1566 && !SSA_NAME_IS_DEFAULT_DEF (ref)
1567 && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref))
1568 && TREE_CODE (gimple_assign_rhs1
1569 (SSA_NAME_DEF_STMT (ref))) == MEM_REF)
1571 ref = get_base_address
1572 (TREE_OPERAND (gimple_assign_rhs1
1573 (SSA_NAME_DEF_STMT (ref)), 0));
1574 ref = walk_ssa_copies (ref);
1575 /* Find base address of the lookup and see if it looks like
1576 vptr load. */
1577 if (TREE_CODE (ref) == SSA_NAME
1578 && !SSA_NAME_IS_DEFAULT_DEF (ref)
1579 && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref)))
1581 tree ref_exp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ref));
1582 tree base_ref = get_ref_base_and_extent
1583 (ref_exp, &offset2, &size, &max_size);
1585 /* Finally verify that what we found looks like read from OTR_OBJECT
1586 or from INSTANCE with offset OFFSET. */
1587 if (base_ref
1588 && ((TREE_CODE (base_ref) == MEM_REF
1589 && ((offset2 == instance_offset
1590 && TREE_OPERAND (base_ref, 0) == instance)
1591 || (!offset2 && TREE_OPERAND (base_ref, 0) == otr_object)))
1592 || (DECL_P (instance) && base_ref == instance
1593 && offset2 == instance_offset)))
1595 stmt = SSA_NAME_DEF_STMT (ref);
1596 instance_ref = ref_exp;
1603 /* If we failed to look up the refernece in code, build our own. */
1604 if (!instance_ref)
1606 /* If the statement in question does not use memory, we can't tell
1607 anything. */
1608 if (!gimple_vuse (stmt))
1609 return false;
1610 ao_ref_init_from_ptr_and_size (&ao, otr_object, NULL);
1612 else
1613 /* Otherwise use the real reference. */
1614 ao_ref_init (&ao, instance_ref);
1616 /* We look for vtbl pointer read. */
1617 ao.size = POINTER_SIZE;
1618 ao.max_size = ao.size;
1619 if (otr_type)
1620 ao.ref_alias_set
1621 = get_deref_alias_set (TREE_TYPE (BINFO_VTABLE (TYPE_BINFO (otr_type))));
1623 if (dump_file)
1625 fprintf (dump_file, "Determining dynamic type for call: ");
1626 print_gimple_stmt (dump_file, call, 0, 0);
1627 fprintf (dump_file, " Starting walk at: ");
1628 print_gimple_stmt (dump_file, stmt, 0, 0);
1629 fprintf (dump_file, " instance pointer: ");
1630 print_generic_expr (dump_file, otr_object, TDF_SLIM);
1631 fprintf (dump_file, " Outer instance pointer: ");
1632 print_generic_expr (dump_file, instance, TDF_SLIM);
1633 fprintf (dump_file, " offset: %i (bits)", (int)offset);
1634 fprintf (dump_file, " vtbl reference: ");
1635 print_generic_expr (dump_file, instance_ref, TDF_SLIM);
1636 fprintf (dump_file, "\n");
1639 tci.offset = offset;
1640 tci.instance = instance;
1641 tci.vtbl_ptr_ref = instance_ref;
1642 gcc_assert (TREE_CODE (instance) != MEM_REF);
1643 tci.known_current_type = NULL_TREE;
1644 tci.known_current_offset = 0;
1645 tci.otr_type = otr_type;
1646 tci.type_maybe_changed = false;
1647 tci.multiple_types_encountered = false;
1648 tci.speculative = false;
1649 tci.seen_unanalyzed_store = false;
1651 walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
1652 &tci, NULL, &function_entry_reached);
1654 /* If we did not find any type changing statements, we may still drop
1655 maybe_in_construction flag if the context already have outer type.
1657 Here we make special assumptions about both constructors and
1658 destructors which are all the functions that are allowed to alter the
1659 VMT pointers. It assumes that destructors begin with assignment into
1660 all VMT pointers and that constructors essentially look in the
1661 following way:
1663 1) The very first thing they do is that they call constructors of
1664 ancestor sub-objects that have them.
1666 2) Then VMT pointers of this and all its ancestors is set to new
1667 values corresponding to the type corresponding to the constructor.
1669 3) Only afterwards, other stuff such as constructor of member
1670 sub-objects and the code written by the user is run. Only this may
1671 include calling virtual functions, directly or indirectly.
1673 4) placement new can not be used to change type of non-POD statically
1674 allocated variables.
1676 There is no way to call a constructor of an ancestor sub-object in any
1677 other way.
1679 This means that we do not have to care whether constructors get the
1680 correct type information because they will always change it (in fact,
1681 if we define the type to be given by the VMT pointer, it is undefined).
1683 The most important fact to derive from the above is that if, for some
1684 statement in the section 3, we try to detect whether the dynamic type
1685 has changed, we can safely ignore all calls as we examine the function
1686 body backwards until we reach statements in section 2 because these
1687 calls cannot be ancestor constructors or destructors (if the input is
1688 not bogus) and so do not change the dynamic type (this holds true only
1689 for automatically allocated objects but at the moment we devirtualize
1690 only these). We then must detect that statements in section 2 change
1691 the dynamic type and can try to derive the new type. That is enough
1692 and we can stop, we will never see the calls into constructors of
1693 sub-objects in this code.
1695 Therefore if the static outer type was found (outer_type)
1696 we can safely ignore tci.speculative that is set on calls and give up
1697 only if there was dyanmic type store that may affect given variable
1698 (seen_unanalyzed_store) */
1700 if (!tci.type_maybe_changed
1701 || (outer_type
1702 && !dynamic
1703 && !tci.seen_unanalyzed_store
1704 && !tci.multiple_types_encountered
1705 && offset == tci.offset
1706 && types_same_for_odr (tci.known_current_type,
1707 outer_type)))
1709 if (!outer_type || tci.seen_unanalyzed_store)
1710 return false;
1711 if (maybe_in_construction)
1712 maybe_in_construction = false;
1713 if (dump_file)
1714 fprintf (dump_file, " No dynamic type change found.\n");
1715 return true;
1718 if (tci.known_current_type
1719 && !function_entry_reached
1720 && !tci.multiple_types_encountered)
1722 if (!tci.speculative)
1724 outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
1725 offset = tci.known_current_offset;
1726 dynamic = true;
1727 maybe_in_construction = false;
1728 maybe_derived_type = false;
1729 if (dump_file)
1730 fprintf (dump_file, " Determined dynamic type.\n");
1732 else if (!speculative_outer_type
1733 || speculative_maybe_derived_type)
1735 speculative_outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
1736 speculative_offset = tci.known_current_offset;
1737 speculative_maybe_derived_type = false;
1738 if (dump_file)
1739 fprintf (dump_file, " Determined speculative dynamic type.\n");
1742 else if (dump_file)
1744 fprintf (dump_file, " Found multiple types%s%s\n",
1745 function_entry_reached ? " (function entry reached)" : "",
1746 function_entry_reached ? " (multiple types encountered)" : "");
1749 return false;
1752 /* See if speculation given by SPEC_OUTER_TYPE, SPEC_OFFSET and SPEC_MAYBE_DERIVED_TYPE
1753 seems consistent (and useful) with what we already have in the non-speculative context. */
1755 bool
1756 ipa_polymorphic_call_context::speculation_consistent_p (tree spec_outer_type,
1757 HOST_WIDE_INT spec_offset,
1758 bool spec_maybe_derived_type,
1759 tree otr_type) const
1761 if (!flag_devirtualize_speculatively)
1762 return false;
1764 /* Non-polymorphic types are useless for deriving likely polymorphic
1765 call targets. */
1766 if (!spec_outer_type || !contains_polymorphic_type_p (spec_outer_type))
1767 return false;
1769 /* If we know nothing, speculation is always good. */
1770 if (!outer_type)
1771 return true;
1773 /* Speculation is only useful to avoid derived types.
1774 This is not 100% true for placement new, where the outer context may
1775 turn out to be useless, but ignore these for now. */
1776 if (!maybe_derived_type)
1777 return false;
1779 /* If types agrees, speculation is consistent, but it makes sense only
1780 when it says something new. */
1781 if (types_must_be_same_for_odr (spec_outer_type, outer_type))
1782 return maybe_derived_type && !spec_maybe_derived_type;
1784 /* If speculation does not contain the type in question, ignore it. */
1785 if (otr_type
1786 && !contains_type_p (spec_outer_type, spec_offset, otr_type, false, true))
1787 return false;
1789 /* If outer type already contains speculation as a filed,
1790 it is useless. We already know from OUTER_TYPE
1791 SPEC_TYPE and that it is not in the construction. */
1792 if (contains_type_p (outer_type, offset - spec_offset,
1793 spec_outer_type, false, false))
1794 return false;
1796 /* If speculative outer type is not more specified than outer
1797 type, just give up.
1798 We can only decide this safely if we can compare types with OUTER_TYPE.
1800 if ((!in_lto_p || odr_type_p (outer_type))
1801 && !contains_type_p (spec_outer_type,
1802 spec_offset - offset,
1803 outer_type, false))
1804 return false;
1805 return true;
1808 /* Improve THIS with speculation described by NEW_OUTER_TYPE, NEW_OFFSET,
1809 NEW_MAYBE_DERIVED_TYPE
1810 If OTR_TYPE is set, assume the context is used with OTR_TYPE. */
1812 bool
1813 ipa_polymorphic_call_context::combine_speculation_with
1814 (tree new_outer_type, HOST_WIDE_INT new_offset, bool new_maybe_derived_type,
1815 tree otr_type)
1817 if (!new_outer_type)
1818 return false;
1820 /* restrict_to_inner_class may eliminate wrong speculation making our job
1821 easeier. */
1822 if (otr_type)
1823 restrict_to_inner_class (otr_type);
1825 if (!speculation_consistent_p (new_outer_type, new_offset,
1826 new_maybe_derived_type, otr_type))
1827 return false;
1829 /* New speculation is a win in case we have no speculation or new
1830 speculation does not consider derivations. */
1831 if (!speculative_outer_type
1832 || (speculative_maybe_derived_type
1833 && !new_maybe_derived_type))
1835 speculative_outer_type = new_outer_type;
1836 speculative_offset = new_offset;
1837 speculative_maybe_derived_type = new_maybe_derived_type;
1838 return true;
1840 else if (types_must_be_same_for_odr (speculative_outer_type,
1841 new_outer_type))
1843 if (speculative_offset != new_offset)
1845 /* OK we have two contexts that seems valid but they disagree,
1846 just give up.
1848 This is not a lattice operation, so we may want to drop it later. */
1849 if (dump_file && (dump_flags & TDF_DETAILS))
1850 fprintf (dump_file,
1851 "Speculative outer types match, "
1852 "offset mismatch -> invalid speculation\n");
1853 clear_speculation ();
1854 return true;
1856 else
1858 if (speculative_maybe_derived_type && !new_maybe_derived_type)
1860 speculative_maybe_derived_type = false;
1861 return true;
1863 else
1864 return false;
1867 /* Choose type that contains the other. This one either contains the outer
1868 as a field (thus giving exactly one target) or is deeper in the type
1869 hiearchy. */
1870 else if (speculative_outer_type
1871 && speculative_maybe_derived_type
1872 && (new_offset > speculative_offset
1873 || (new_offset == speculative_offset
1874 && contains_type_p (new_outer_type,
1875 0, speculative_outer_type, false))))
1877 tree old_outer_type = speculative_outer_type;
1878 HOST_WIDE_INT old_offset = speculative_offset;
1879 bool old_maybe_derived_type = speculative_maybe_derived_type;
1881 speculative_outer_type = new_outer_type;
1882 speculative_offset = new_offset;
1883 speculative_maybe_derived_type = new_maybe_derived_type;
1885 if (otr_type)
1886 restrict_to_inner_class (otr_type);
1888 /* If the speculation turned out to make no sense, revert to sensible
1889 one. */
1890 if (!speculative_outer_type)
1892 speculative_outer_type = old_outer_type;
1893 speculative_offset = old_offset;
1894 speculative_maybe_derived_type = old_maybe_derived_type;
1895 return false;
1897 return (old_offset != speculative_offset
1898 || old_maybe_derived_type != speculative_maybe_derived_type
1899 || types_must_be_same_for_odr (speculative_outer_type,
1900 new_outer_type));
1902 return false;
1905 /* Make speculation less specific so
1906 NEW_OUTER_TYPE, NEW_OFFSET, NEW_MAYBE_DERIVED_TYPE is also included.
1907 If OTR_TYPE is set, assume the context is used with OTR_TYPE. */
1909 bool
1910 ipa_polymorphic_call_context::meet_speculation_with
1911 (tree new_outer_type, HOST_WIDE_INT new_offset, bool new_maybe_derived_type,
1912 tree otr_type)
1914 if (!new_outer_type && speculative_outer_type)
1916 clear_speculation ();
1917 return true;
1920 /* restrict_to_inner_class may eliminate wrong speculation making our job
1921 easeier. */
1922 if (otr_type)
1923 restrict_to_inner_class (otr_type);
1925 if (!speculative_outer_type
1926 || !speculation_consistent_p (speculative_outer_type,
1927 speculative_offset,
1928 speculative_maybe_derived_type,
1929 otr_type))
1930 return false;
1932 if (!speculation_consistent_p (new_outer_type, new_offset,
1933 new_maybe_derived_type, otr_type))
1935 clear_speculation ();
1936 return true;
1939 else if (types_must_be_same_for_odr (speculative_outer_type,
1940 new_outer_type))
1942 if (speculative_offset != new_offset)
1944 clear_speculation ();
1945 return true;
1947 else
1949 if (!speculative_maybe_derived_type && new_maybe_derived_type)
1951 speculative_maybe_derived_type = true;
1952 return true;
1954 else
1955 return false;
1958 /* See if one type contains the other as a field (not base). */
1959 else if (contains_type_p (new_outer_type, new_offset - speculative_offset,
1960 speculative_outer_type, false, false))
1961 return false;
1962 else if (contains_type_p (speculative_outer_type,
1963 speculative_offset - new_offset,
1964 new_outer_type, false, false))
1966 speculative_outer_type = new_outer_type;
1967 speculative_offset = new_offset;
1968 speculative_maybe_derived_type = new_maybe_derived_type;
1969 return true;
1971 /* See if OUTER_TYPE is base of CTX.OUTER_TYPE. */
1972 else if (contains_type_p (new_outer_type,
1973 new_offset - speculative_offset,
1974 speculative_outer_type, false, true))
1976 if (!speculative_maybe_derived_type)
1978 speculative_maybe_derived_type = true;
1979 return true;
1981 return false;
1983 /* See if CTX.OUTER_TYPE is base of OUTER_TYPE. */
1984 else if (contains_type_p (speculative_outer_type,
1985 speculative_offset - new_offset, new_outer_type, false, true))
1987 speculative_outer_type = new_outer_type;
1988 speculative_offset = new_offset;
1989 speculative_maybe_derived_type = true;
1990 return true;
1992 else
1994 if (dump_file && (dump_flags & TDF_DETAILS))
1995 fprintf (dump_file, "Giving up on speculative meet\n");
1996 clear_speculation ();
1997 return true;
2001 /* Assume that both THIS and a given context is valid and strenghten THIS
2002 if possible. Return true if any strenghtening was made.
2003 If actual type the context is being used in is known, OTR_TYPE should be
2004 set accordingly. This improves quality of combined result. */
2006 bool
2007 ipa_polymorphic_call_context::combine_with (ipa_polymorphic_call_context ctx,
2008 tree otr_type)
2010 bool updated = false;
2012 if (ctx.useless_p () || invalid)
2013 return false;
2015 /* Restricting context to inner type makes merging easier, however do not
2016 do that unless we know how the context is used (OTR_TYPE is non-NULL) */
2017 if (otr_type && !invalid && !ctx.invalid)
2019 restrict_to_inner_class (otr_type);
2020 ctx.restrict_to_inner_class (otr_type);
2021 if(invalid)
2022 return false;
2025 if (dump_file && (dump_flags & TDF_DETAILS))
2027 fprintf (dump_file, "Polymorphic call context combine:");
2028 dump (dump_file);
2029 fprintf (dump_file, "With context: ");
2030 ctx.dump (dump_file);
2031 if (otr_type)
2033 fprintf (dump_file, "To be used with type: ");
2034 print_generic_expr (dump_file, otr_type, TDF_SLIM);
2035 fprintf (dump_file, "\n");
2039 /* If call is known to be invalid, we are done. */
2040 if (ctx.invalid)
2042 if (dump_file && (dump_flags & TDF_DETAILS))
2043 fprintf (dump_file, "-> Invalid context\n");
2044 goto invalidate;
2047 if (!ctx.outer_type)
2049 else if (!outer_type)
2051 outer_type = ctx.outer_type;
2052 offset = ctx.offset;
2053 dynamic = ctx.dynamic;
2054 maybe_in_construction = ctx.maybe_in_construction;
2055 maybe_derived_type = ctx.maybe_derived_type;
2056 updated = true;
2058 /* If types are known to be same, merging is quite easy. */
2059 else if (types_must_be_same_for_odr (outer_type, ctx.outer_type))
2061 if (offset != ctx.offset
2062 && TYPE_SIZE (outer_type)
2063 && TREE_CODE (TYPE_SIZE (outer_type)) == INTEGER_CST)
2065 if (dump_file && (dump_flags & TDF_DETAILS))
2066 fprintf (dump_file, "Outer types match, offset mismatch -> invalid\n");
2067 clear_speculation ();
2068 clear_outer_type ();
2069 invalid = true;
2070 return true;
2072 if (dump_file && (dump_flags & TDF_DETAILS))
2073 fprintf (dump_file, "Outer types match, merging flags\n");
2074 if (maybe_in_construction && !ctx.maybe_in_construction)
2076 updated = true;
2077 maybe_in_construction = false;
2079 if (maybe_derived_type && !ctx.maybe_derived_type)
2081 updated = true;
2082 maybe_derived_type = false;
2084 if (dynamic && !ctx.dynamic)
2086 updated = true;
2087 dynamic = false;
2090 /* If we know the type precisely, there is not much to improve. */
2091 else if (!maybe_derived_type && !maybe_in_construction
2092 && !ctx.maybe_derived_type && !ctx.maybe_in_construction)
2094 /* It may be easy to check if second context permits the first
2095 and set INVALID otherwise. This is not easy to do in general;
2096 contains_type_p may return false negatives for non-comparable
2097 types.
2099 If OTR_TYPE is known, we however can expect that
2100 restrict_to_inner_class should have discovered the same base
2101 type. */
2102 if (otr_type && !ctx.maybe_in_construction && !ctx.maybe_derived_type)
2104 if (dump_file && (dump_flags & TDF_DETAILS))
2105 fprintf (dump_file, "Contextes disagree -> invalid\n");
2106 goto invalidate;
2109 /* See if one type contains the other as a field (not base).
2110 In this case we want to choose the wider type, because it contains
2111 more information. */
2112 else if (contains_type_p (ctx.outer_type, ctx.offset - offset,
2113 outer_type, false, false))
2115 if (dump_file && (dump_flags & TDF_DETAILS))
2116 fprintf (dump_file, "Second type contain the first as a field\n");
2118 if (maybe_derived_type)
2120 outer_type = ctx.outer_type;
2121 maybe_derived_type = ctx.maybe_derived_type;
2122 offset = ctx.offset;
2123 dynamic = ctx.dynamic;
2124 updated = true;
2127 /* If we do not know how the context is being used, we can
2128 not clear MAYBE_IN_CONSTRUCTION because it may be offseted
2129 to other component of OUTER_TYPE later and we know nothing
2130 about it. */
2131 if (otr_type && maybe_in_construction
2132 && !ctx.maybe_in_construction)
2134 maybe_in_construction = false;
2135 updated = true;
2138 else if (contains_type_p (outer_type, offset - ctx.offset,
2139 ctx.outer_type, false, false))
2141 if (dump_file && (dump_flags & TDF_DETAILS))
2142 fprintf (dump_file, "First type contain the second as a field\n");
2144 if (otr_type && maybe_in_construction
2145 && !ctx.maybe_in_construction)
2147 maybe_in_construction = false;
2148 updated = true;
2151 /* See if OUTER_TYPE is base of CTX.OUTER_TYPE. */
2152 else if (contains_type_p (ctx.outer_type,
2153 ctx.offset - offset, outer_type, false, true))
2155 if (dump_file && (dump_flags & TDF_DETAILS))
2156 fprintf (dump_file, "First type is base of second\n");
2157 if (!maybe_derived_type)
2159 if (!ctx.maybe_in_construction
2160 && types_odr_comparable (outer_type, ctx.outer_type))
2162 if (dump_file && (dump_flags & TDF_DETAILS))
2163 fprintf (dump_file, "Second context does not permit base -> invalid\n");
2164 goto invalidate;
2167 /* Pick variant deeper in the hiearchy. */
2168 else
2170 outer_type = ctx.outer_type;
2171 maybe_in_construction = ctx.maybe_in_construction;
2172 maybe_derived_type = ctx.maybe_derived_type;
2173 offset = ctx.offset;
2174 dynamic = ctx.dynamic;
2175 updated = true;
2178 /* See if CTX.OUTER_TYPE is base of OUTER_TYPE. */
2179 else if (contains_type_p (outer_type,
2180 offset - ctx.offset, ctx.outer_type, false, true))
2182 if (dump_file && (dump_flags & TDF_DETAILS))
2183 fprintf (dump_file, "Second type is base of first\n");
2184 if (!ctx.maybe_derived_type)
2186 if (!maybe_in_construction
2187 && types_odr_comparable (outer_type, ctx.outer_type))
2189 if (dump_file && (dump_flags & TDF_DETAILS))
2190 fprintf (dump_file, "First context does not permit base -> invalid\n");
2191 goto invalidate;
2193 /* Pick the base type. */
2194 else if (maybe_in_construction)
2196 outer_type = ctx.outer_type;
2197 maybe_in_construction = ctx.maybe_in_construction;
2198 maybe_derived_type = ctx.maybe_derived_type;
2199 offset = ctx.offset;
2200 dynamic = ctx.dynamic;
2201 updated = true;
2205 /* TODO handle merging using hiearchy. */
2206 else if (dump_file && (dump_flags & TDF_DETAILS))
2207 fprintf (dump_file, "Giving up on merge\n");
2209 updated |= combine_speculation_with (ctx.speculative_outer_type,
2210 ctx.speculative_offset,
2211 ctx.speculative_maybe_derived_type,
2212 otr_type);
2214 if (updated && dump_file && (dump_flags & TDF_DETAILS))
2216 fprintf (dump_file, "Updated as: ");
2217 dump (dump_file);
2218 fprintf (dump_file, "\n");
2220 return updated;
2222 invalidate:
2223 invalid = true;
2224 clear_speculation ();
2225 clear_outer_type ();
2226 return true;
2229 /* Take non-speculative info, merge it with speculative and clear speculation.
2230 Used when we no longer manage to keep track of actual outer type, but we
2231 think it is still there.
2233 If OTR_TYPE is set, the transformation can be done more effectively assuming
2234 that context is going to be used only that way. */
2236 void
2237 ipa_polymorphic_call_context::make_speculative (tree otr_type)
2239 tree spec_outer_type = outer_type;
2240 HOST_WIDE_INT spec_offset = offset;
2241 bool spec_maybe_derived_type = maybe_derived_type;
2243 if (invalid)
2245 invalid = false;
2246 clear_outer_type ();
2247 clear_speculation ();
2248 return;
2250 if (!outer_type)
2251 return;
2252 clear_outer_type ();
2253 combine_speculation_with (spec_outer_type, spec_offset,
2254 spec_maybe_derived_type,
2255 otr_type);
2258 /* Use when we can not track dynamic type change. This speculatively assume
2259 type change is not happening. */
2261 void
2262 ipa_polymorphic_call_context::possible_dynamic_type_change (bool in_poly_cdtor,
2263 tree otr_type)
2265 if (dynamic)
2266 make_speculative (otr_type);
2267 else if (in_poly_cdtor)
2268 maybe_in_construction = true;
2271 /* Return TRUE if this context conveys the same information as OTHER. */
2273 bool
2274 ipa_polymorphic_call_context::equal_to
2275 (const ipa_polymorphic_call_context &x) const
2277 if (useless_p ())
2278 return x.useless_p ();
2279 if (invalid)
2280 return x.invalid;
2281 if (x.useless_p () || x.invalid)
2282 return false;
2284 if (outer_type)
2286 if (!x.outer_type
2287 || !types_odr_comparable (outer_type, x.outer_type)
2288 || !types_same_for_odr (outer_type, x.outer_type)
2289 || offset != x.offset
2290 || maybe_in_construction != x.maybe_in_construction
2291 || maybe_derived_type != x.maybe_derived_type
2292 || dynamic != x.dynamic)
2293 return false;
2295 else if (x.outer_type)
2296 return false;
2299 if (speculative_outer_type
2300 && speculation_consistent_p (speculative_outer_type, speculative_offset,
2301 speculative_maybe_derived_type, NULL_TREE))
2303 if (!x.speculative_outer_type)
2304 return false;
2306 if (!types_odr_comparable (speculative_outer_type,
2307 x.speculative_outer_type)
2308 || !types_same_for_odr (speculative_outer_type,
2309 x.speculative_outer_type)
2310 || speculative_offset != x.speculative_offset
2311 || speculative_maybe_derived_type != x.speculative_maybe_derived_type)
2312 return false;
2314 else if (x.speculative_outer_type
2315 && x.speculation_consistent_p (x.speculative_outer_type,
2316 x.speculative_offset,
2317 x.speculative_maybe_derived_type,
2318 NULL))
2319 return false;
2321 return true;
2324 /* Modify context to be strictly less restrictive than CTX. */
2326 bool
2327 ipa_polymorphic_call_context::meet_with (ipa_polymorphic_call_context ctx,
2328 tree otr_type)
2330 bool updated = false;
2332 if (useless_p () || ctx.invalid)
2333 return false;
2335 /* Restricting context to inner type makes merging easier, however do not
2336 do that unless we know how the context is used (OTR_TYPE is non-NULL) */
2337 if (otr_type && !useless_p () && !ctx.useless_p ())
2339 restrict_to_inner_class (otr_type);
2340 ctx.restrict_to_inner_class (otr_type);
2341 if(invalid)
2342 return false;
2345 if (equal_to (ctx))
2346 return false;
2348 if (ctx.useless_p () || invalid)
2350 *this = ctx;
2351 return true;
2354 if (dump_file && (dump_flags & TDF_DETAILS))
2356 fprintf (dump_file, "Polymorphic call context meet:");
2357 dump (dump_file);
2358 fprintf (dump_file, "With context: ");
2359 ctx.dump (dump_file);
2360 if (otr_type)
2362 fprintf (dump_file, "To be used with type: ");
2363 print_generic_expr (dump_file, otr_type, TDF_SLIM);
2364 fprintf (dump_file, "\n");
2368 if (!dynamic && ctx.dynamic)
2370 dynamic = true;
2371 updated = true;
2374 /* If call is known to be invalid, we are done. */
2375 if (!outer_type)
2377 else if (!ctx.outer_type)
2379 clear_outer_type ();
2380 updated = true;
2382 /* If types are known to be same, merging is quite easy. */
2383 else if (types_must_be_same_for_odr (outer_type, ctx.outer_type))
2385 if (offset != ctx.offset
2386 && TYPE_SIZE (outer_type)
2387 && TREE_CODE (TYPE_SIZE (outer_type)) == INTEGER_CST)
2389 if (dump_file && (dump_flags & TDF_DETAILS))
2390 fprintf (dump_file, "Outer types match, offset mismatch -> clearing\n");
2391 clear_outer_type ();
2392 return true;
2394 if (dump_file && (dump_flags & TDF_DETAILS))
2395 fprintf (dump_file, "Outer types match, merging flags\n");
2396 if (!maybe_in_construction && ctx.maybe_in_construction)
2398 updated = true;
2399 maybe_in_construction = true;
2401 if (!maybe_derived_type && ctx.maybe_derived_type)
2403 updated = true;
2404 maybe_derived_type = true;
2406 if (!dynamic && ctx.dynamic)
2408 updated = true;
2409 dynamic = true;
2412 /* See if one type contains the other as a field (not base). */
2413 else if (contains_type_p (ctx.outer_type, ctx.offset - offset,
2414 outer_type, false, false))
2416 if (dump_file && (dump_flags & TDF_DETAILS))
2417 fprintf (dump_file, "Second type contain the first as a field\n");
2419 /* The second type is more specified, so we keep the first.
2420 We need to set DYNAMIC flag to avoid declaring context INVALID
2421 of OFFSET ends up being out of range. */
2422 if (!dynamic
2423 && (ctx.dynamic
2424 || (!otr_type
2425 && (!TYPE_SIZE (ctx.outer_type)
2426 || !TYPE_SIZE (outer_type)
2427 || !operand_equal_p (TYPE_SIZE (ctx.outer_type),
2428 TYPE_SIZE (outer_type), 0)))))
2430 dynamic = true;
2431 updated = true;
2434 else if (contains_type_p (outer_type, offset - ctx.offset,
2435 ctx.outer_type, false, false))
2437 if (dump_file && (dump_flags & TDF_DETAILS))
2438 fprintf (dump_file, "First type contain the second as a field\n");
2440 if (!dynamic
2441 && (ctx.dynamic
2442 || (!otr_type
2443 && (!TYPE_SIZE (ctx.outer_type)
2444 || !TYPE_SIZE (outer_type)
2445 || !operand_equal_p (TYPE_SIZE (ctx.outer_type),
2446 TYPE_SIZE (outer_type), 0)))))
2447 dynamic = true;
2448 outer_type = ctx.outer_type;
2449 offset = ctx.offset;
2450 dynamic = ctx.dynamic;
2451 maybe_in_construction = ctx.maybe_in_construction;
2452 maybe_derived_type = ctx.maybe_derived_type;
2453 updated = true;
2455 /* See if OUTER_TYPE is base of CTX.OUTER_TYPE. */
2456 else if (contains_type_p (ctx.outer_type,
2457 ctx.offset - offset, outer_type, false, true))
2459 if (dump_file && (dump_flags & TDF_DETAILS))
2460 fprintf (dump_file, "First type is base of second\n");
2461 if (!maybe_derived_type)
2463 maybe_derived_type = true;
2464 updated = true;
2466 if (!maybe_in_construction && ctx.maybe_in_construction)
2468 maybe_in_construction = true;
2469 updated = true;
2471 if (!dynamic && ctx.dynamic)
2473 dynamic = true;
2474 updated = true;
2477 /* See if CTX.OUTER_TYPE is base of OUTER_TYPE. */
2478 else if (contains_type_p (outer_type,
2479 offset - ctx.offset, ctx.outer_type, false, true))
2481 if (dump_file && (dump_flags & TDF_DETAILS))
2482 fprintf (dump_file, "Second type is base of first\n");
2483 outer_type = ctx.outer_type;
2484 offset = ctx.offset;
2485 updated = true;
2486 if (!maybe_derived_type)
2487 maybe_derived_type = true;
2488 if (!maybe_in_construction && ctx.maybe_in_construction)
2489 maybe_in_construction = true;
2490 if (!dynamic && ctx.dynamic)
2491 dynamic = true;
2493 /* TODO handle merging using hiearchy. */
2494 else
2496 if (dump_file && (dump_flags & TDF_DETAILS))
2497 fprintf (dump_file, "Giving up on meet\n");
2498 clear_outer_type ();
2499 updated = true;
2502 updated |= meet_speculation_with (ctx.speculative_outer_type,
2503 ctx.speculative_offset,
2504 ctx.speculative_maybe_derived_type,
2505 otr_type);
2507 if (updated && dump_file && (dump_flags & TDF_DETAILS))
2509 fprintf (dump_file, "Updated as: ");
2510 dump (dump_file);
2511 fprintf (dump_file, "\n");
2513 return updated;