Merge from trunk @222673.
[official-gcc.git] / gcc / ipa-polymorphic-call.c
blob0676abeeb4e426939c9557ca497f237c10d25b39
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_known_to_have_no_deriavations_p (outer_type))
273 maybe_derived_type = false;
275 /* Type can not contain itself on an non-zero offset. In that case
276 just give up. Still accept the case where size is now known.
277 Either the second copy may appear past the end of type or within
278 the non-POD buffer located inside the variably sized type
279 itself. */
280 if (cur_offset != 0)
281 goto no_useful_type_info;
282 /* If we determined type precisely or we have no clue on
283 speuclation, we are done. */
284 if (!maybe_derived_type || !speculative_outer_type
285 || !speculation_consistent_p (speculative_outer_type,
286 speculative_offset,
287 speculative_maybe_derived_type,
288 otr_type))
290 clear_speculation ();
291 return true;
293 /* Otherwise look into speculation now. */
294 else
296 speculative = true;
297 type = speculative_outer_type;
298 cur_offset = speculative_offset;
299 continue;
304 /* Walk fields and find corresponding on at OFFSET. */
305 if (TREE_CODE (type) == RECORD_TYPE)
307 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld))
309 if (TREE_CODE (fld) != FIELD_DECL)
310 continue;
312 pos = int_bit_position (fld);
313 if (pos > (unsigned HOST_WIDE_INT)cur_offset)
314 continue;
316 /* Do not consider vptr itself. Not even for placement new. */
317 if (!pos && DECL_ARTIFICIAL (fld)
318 && POINTER_TYPE_P (TREE_TYPE (fld))
319 && TYPE_BINFO (type)
320 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
321 continue;
323 if (!DECL_SIZE (fld) || !tree_fits_uhwi_p (DECL_SIZE (fld)))
324 goto no_useful_type_info;
325 size = tree_to_uhwi (DECL_SIZE (fld));
327 /* We can always skip types smaller than pointer size:
328 those can not contain a virtual table pointer.
330 Disqualifying fields that are too small to fit OTR_TYPE
331 saves work needed to walk them for no benefit.
332 Because of the way the bases are packed into a class, the
333 field's size may be smaller than type size, so it needs
334 to be done with a care. */
336 if (pos <= (unsigned HOST_WIDE_INT)cur_offset
337 && (pos + size) >= (unsigned HOST_WIDE_INT)cur_offset
338 + POINTER_SIZE
339 && (!otr_type
340 || !TYPE_SIZE (TREE_TYPE (fld))
341 || !tree_fits_shwi_p (TYPE_SIZE (TREE_TYPE (fld)))
342 || (pos + tree_to_uhwi (TYPE_SIZE (TREE_TYPE (fld))))
343 >= cur_offset + otr_type_size))
344 break;
347 if (!fld)
348 goto no_useful_type_info;
350 type = TYPE_MAIN_VARIANT (TREE_TYPE (fld));
351 cur_offset -= pos;
352 /* DECL_ARTIFICIAL represents a basetype. */
353 if (!DECL_ARTIFICIAL (fld))
355 if (!speculative)
357 outer_type = type;
358 offset = cur_offset;
359 /* As soon as we se an field containing the type,
360 we know we are not looking for derivations. */
361 maybe_derived_type = false;
363 else
365 speculative_outer_type = type;
366 speculative_offset = cur_offset;
367 speculative_maybe_derived_type = false;
370 else if (!consider_bases)
371 goto no_useful_type_info;
373 else if (TREE_CODE (type) == ARRAY_TYPE)
375 tree subtype = TYPE_MAIN_VARIANT (TREE_TYPE (type));
377 /* Give up if we don't know array field size.
378 Also give up on non-polymorphic types as they are used
379 as buffers for placement new. */
380 if (!TYPE_SIZE (subtype)
381 || !tree_fits_shwi_p (TYPE_SIZE (subtype))
382 || tree_to_shwi (TYPE_SIZE (subtype)) <= 0
383 || !contains_polymorphic_type_p (subtype))
384 goto no_useful_type_info;
386 HOST_WIDE_INT new_offset = cur_offset % tree_to_shwi (TYPE_SIZE (subtype));
388 /* We may see buffer for placement new. In this case the expected type
389 can be bigger than the subtype. */
390 if (TYPE_SIZE (subtype)
391 && (cur_offset + otr_type_size
392 > tree_to_uhwi (TYPE_SIZE (subtype))))
393 goto no_useful_type_info;
395 cur_offset = new_offset;
396 type = subtype;
397 if (!speculative)
399 outer_type = type;
400 offset = cur_offset;
401 maybe_derived_type = false;
403 else
405 speculative_outer_type = type;
406 speculative_offset = cur_offset;
407 speculative_maybe_derived_type = false;
410 /* Give up on anything else. */
411 else
413 no_useful_type_info:
414 if (maybe_derived_type && !speculative
415 && TREE_CODE (outer_type) == RECORD_TYPE
416 && TREE_CODE (otr_type) == RECORD_TYPE
417 && TYPE_BINFO (otr_type)
418 && !offset
419 && get_binfo_at_offset (TYPE_BINFO (otr_type), 0, outer_type))
421 clear_outer_type (otr_type);
422 if (!speculative_outer_type
423 || !speculation_consistent_p (speculative_outer_type,
424 speculative_offset,
425 speculative_maybe_derived_type,
426 otr_type))
427 clear_speculation ();
428 if (speculative_outer_type)
430 speculative = true;
431 type = speculative_outer_type;
432 cur_offset = speculative_offset;
434 else
435 return true;
437 /* We found no way to embedd EXPECTED_TYPE in TYPE.
438 We still permit two special cases - placement new and
439 the case of variadic types containing themselves. */
440 if (!speculative
441 && consider_placement_new
442 && (size_unknown || !type || maybe_derived_type
443 || possible_placement_new (type, otr_type, cur_offset)))
445 /* In these weird cases we want to accept the context.
446 In non-speculative run we have no useful outer_type info
447 (TODO: we may eventually want to record upper bound on the
448 type size that can be used to prune the walk),
449 but we still want to consider speculation that may
450 give useful info. */
451 if (!speculative)
453 clear_outer_type (otr_type);
454 if (!speculative_outer_type
455 || !speculation_consistent_p (speculative_outer_type,
456 speculative_offset,
457 speculative_maybe_derived_type,
458 otr_type))
459 clear_speculation ();
460 if (speculative_outer_type)
462 speculative = true;
463 type = speculative_outer_type;
464 cur_offset = speculative_offset;
466 else
467 return true;
469 else
470 clear_speculation ();
471 return true;
473 else
475 clear_speculation ();
476 if (speculative)
477 return true;
478 clear_outer_type (otr_type);
479 invalid = true;
480 return false;
486 /* Return true if OUTER_TYPE contains OTR_TYPE at OFFSET.
487 CONSIDER_PLACEMENT_NEW makes function to accept cases where OTR_TYPE can
488 be built within OUTER_TYPE by means of placement new. CONSIDER_BASES makes
489 function to accept cases where OTR_TYPE appears as base of OUTER_TYPE or as
490 base of one of fields of OUTER_TYPE. */
492 static bool
493 contains_type_p (tree outer_type, HOST_WIDE_INT offset,
494 tree otr_type,
495 bool consider_placement_new,
496 bool consider_bases)
498 ipa_polymorphic_call_context context;
500 /* Check that type is within range. */
501 if (offset < 0)
502 return false;
503 if (TYPE_SIZE (outer_type) && TYPE_SIZE (otr_type)
504 && TREE_CODE (outer_type) == INTEGER_CST
505 && TREE_CODE (otr_type) == INTEGER_CST
506 && wi::ltu_p (wi::to_offset (outer_type), (wi::to_offset (otr_type) + offset)))
507 return false;
509 context.offset = offset;
510 context.outer_type = TYPE_MAIN_VARIANT (outer_type);
511 context.maybe_derived_type = false;
512 return context.restrict_to_inner_class (otr_type, consider_placement_new, consider_bases);
516 /* Return a FUNCTION_DECL if BLOCK represents a constructor or destructor.
517 If CHECK_CLONES is true, also check for clones of ctor/dtors. */
519 tree
520 inlined_polymorphic_ctor_dtor_block_p (tree block, bool check_clones)
522 tree fn = BLOCK_ABSTRACT_ORIGIN (block);
523 if (fn == NULL || TREE_CODE (fn) != FUNCTION_DECL)
524 return NULL_TREE;
526 if (TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
527 || (!DECL_CXX_CONSTRUCTOR_P (fn) && !DECL_CXX_DESTRUCTOR_P (fn)))
529 if (!check_clones)
530 return NULL_TREE;
532 /* Watch for clones where we constant propagated the first
533 argument (pointer to the instance). */
534 fn = DECL_ABSTRACT_ORIGIN (fn);
535 if (!fn
536 || TREE_CODE (TREE_TYPE (fn)) != METHOD_TYPE
537 || (!DECL_CXX_CONSTRUCTOR_P (fn) && !DECL_CXX_DESTRUCTOR_P (fn)))
538 return NULL_TREE;
541 if (flags_from_decl_or_type (fn) & (ECF_PURE | ECF_CONST))
542 return NULL_TREE;
544 return fn;
548 /* We know that the instance is stored in variable or parameter
549 (not dynamically allocated) and we want to disprove the fact
550 that it may be in construction at invocation of CALL.
552 BASE represents memory location where instance is stored.
553 If BASE is NULL, it is assumed to be global memory.
554 OUTER_TYPE is known type of the instance or NULL if not
555 known.
557 For the variable to be in construction we actually need to
558 be in constructor of corresponding global variable or
559 the inline stack of CALL must contain the constructor.
560 Check this condition. This check works safely only before
561 IPA passes, because inline stacks may become out of date
562 later. */
564 bool
565 decl_maybe_in_construction_p (tree base, tree outer_type,
566 gimple call, tree function)
568 if (outer_type)
569 outer_type = TYPE_MAIN_VARIANT (outer_type);
570 gcc_assert (!base || DECL_P (base));
572 /* After inlining the code unification optimizations may invalidate
573 inline stacks. Also we need to give up on global variables after
574 IPA, because addresses of these may have been propagated to their
575 constructors. */
576 if (DECL_STRUCT_FUNCTION (function)->after_inlining)
577 return true;
579 /* Pure functions can not do any changes on the dynamic type;
580 that require writting to memory. */
581 if ((!base || !auto_var_in_fn_p (base, function))
582 && flags_from_decl_or_type (function) & (ECF_PURE | ECF_CONST))
583 return false;
585 bool check_clones = !base || is_global_var (base);
586 for (tree block = gimple_block (call); block && TREE_CODE (block) == BLOCK;
587 block = BLOCK_SUPERCONTEXT (block))
588 if (tree fn = inlined_polymorphic_ctor_dtor_block_p (block, check_clones))
590 tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (fn)));
592 if (!outer_type || !types_odr_comparable (type, outer_type))
594 if (TREE_CODE (type) == RECORD_TYPE
595 && TYPE_BINFO (type)
596 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
597 return true;
599 else if (types_same_for_odr (type, outer_type))
600 return true;
603 if (!base || (TREE_CODE (base) == VAR_DECL && is_global_var (base)))
605 if (TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
606 || (!DECL_CXX_CONSTRUCTOR_P (function)
607 && !DECL_CXX_DESTRUCTOR_P (function)))
609 if (!DECL_ABSTRACT_ORIGIN (function))
610 return false;
611 /* Watch for clones where we constant propagated the first
612 argument (pointer to the instance). */
613 function = DECL_ABSTRACT_ORIGIN (function);
614 if (!function
615 || TREE_CODE (TREE_TYPE (function)) != METHOD_TYPE
616 || (!DECL_CXX_CONSTRUCTOR_P (function)
617 && !DECL_CXX_DESTRUCTOR_P (function)))
618 return false;
620 tree type = TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (function)));
621 if (!outer_type || !types_odr_comparable (type, outer_type))
623 if (TREE_CODE (type) == RECORD_TYPE
624 && TYPE_BINFO (type)
625 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
626 return true;
628 else if (types_same_for_odr (type, outer_type))
629 return true;
631 return false;
634 /* Dump human readable context to F. If NEWLINE is true, it will be terminated
635 by a newline. */
637 void
638 ipa_polymorphic_call_context::dump (FILE *f, bool newline) const
640 fprintf (f, " ");
641 if (invalid)
642 fprintf (f, "Call is known to be undefined");
643 else
645 if (useless_p ())
646 fprintf (f, "nothing known");
647 if (outer_type || offset)
649 fprintf (f, "Outer type%s:", dynamic ? " (dynamic)":"");
650 print_generic_expr (f, outer_type, TDF_SLIM);
651 if (maybe_derived_type)
652 fprintf (f, " (or a derived type)");
653 if (maybe_in_construction)
654 fprintf (f, " (maybe in construction)");
655 fprintf (f, " offset "HOST_WIDE_INT_PRINT_DEC,
656 offset);
658 if (speculative_outer_type)
660 if (outer_type || offset)
661 fprintf (f, " ");
662 fprintf (f, "Speculative outer type:");
663 print_generic_expr (f, speculative_outer_type, TDF_SLIM);
664 if (speculative_maybe_derived_type)
665 fprintf (f, " (or a derived type)");
666 fprintf (f, " at offset "HOST_WIDE_INT_PRINT_DEC,
667 speculative_offset);
670 if (newline)
671 fprintf(f, "\n");
674 /* Print context to stderr. */
676 void
677 ipa_polymorphic_call_context::debug () const
679 dump (stderr);
682 /* Stream out the context to OB. */
684 void
685 ipa_polymorphic_call_context::stream_out (struct output_block *ob) const
687 struct bitpack_d bp = bitpack_create (ob->main_stream);
689 bp_pack_value (&bp, invalid, 1);
690 bp_pack_value (&bp, maybe_in_construction, 1);
691 bp_pack_value (&bp, maybe_derived_type, 1);
692 bp_pack_value (&bp, speculative_maybe_derived_type, 1);
693 bp_pack_value (&bp, dynamic, 1);
694 bp_pack_value (&bp, outer_type != NULL, 1);
695 bp_pack_value (&bp, offset != 0, 1);
696 bp_pack_value (&bp, speculative_outer_type != NULL, 1);
697 streamer_write_bitpack (&bp);
699 if (outer_type != NULL)
700 stream_write_tree (ob, outer_type, true);
701 if (offset)
702 streamer_write_hwi (ob, offset);
703 if (speculative_outer_type != NULL)
705 stream_write_tree (ob, speculative_outer_type, true);
706 streamer_write_hwi (ob, speculative_offset);
708 else
709 gcc_assert (!speculative_offset);
712 /* Stream in the context from IB and DATA_IN. */
714 void
715 ipa_polymorphic_call_context::stream_in (struct lto_input_block *ib,
716 struct data_in *data_in)
718 struct bitpack_d bp = streamer_read_bitpack (ib);
720 invalid = bp_unpack_value (&bp, 1);
721 maybe_in_construction = bp_unpack_value (&bp, 1);
722 maybe_derived_type = bp_unpack_value (&bp, 1);
723 speculative_maybe_derived_type = bp_unpack_value (&bp, 1);
724 dynamic = bp_unpack_value (&bp, 1);
725 bool outer_type_p = bp_unpack_value (&bp, 1);
726 bool offset_p = bp_unpack_value (&bp, 1);
727 bool speculative_outer_type_p = bp_unpack_value (&bp, 1);
729 if (outer_type_p)
730 outer_type = stream_read_tree (ib, data_in);
731 else
732 outer_type = NULL;
733 if (offset_p)
734 offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
735 else
736 offset = 0;
737 if (speculative_outer_type_p)
739 speculative_outer_type = stream_read_tree (ib, data_in);
740 speculative_offset = (HOST_WIDE_INT) streamer_read_hwi (ib);
742 else
744 speculative_outer_type = NULL;
745 speculative_offset = 0;
749 /* Proudce polymorphic call context for call method of instance
750 that is located within BASE (that is assumed to be a decl) at offset OFF. */
752 void
753 ipa_polymorphic_call_context::set_by_decl (tree base, HOST_WIDE_INT off)
755 gcc_assert (DECL_P (base));
756 clear_speculation ();
758 if (!contains_polymorphic_type_p (TREE_TYPE (base)))
760 clear_outer_type ();
761 offset = off;
762 return;
764 outer_type = TYPE_MAIN_VARIANT (TREE_TYPE (base));
765 offset = off;
766 /* Make very conservative assumption that all objects
767 may be in construction.
769 It is up to caller to revisit this via
770 get_dynamic_type or decl_maybe_in_construction_p. */
771 maybe_in_construction = true;
772 maybe_derived_type = false;
773 dynamic = false;
776 /* CST is an invariant (address of decl), try to get meaningful
777 polymorphic call context for polymorphic call of method
778 if instance of OTR_TYPE that is located at offset OFF of this invariant.
779 Return FALSE if nothing meaningful can be found. */
781 bool
782 ipa_polymorphic_call_context::set_by_invariant (tree cst,
783 tree otr_type,
784 HOST_WIDE_INT off)
786 HOST_WIDE_INT offset2, size, max_size;
787 bool reverse;
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, &reverse);
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 bool reverse;
929 tree base
930 = get_ref_base_and_extent (TREE_OPERAND (base_pointer, 0),
931 &offset2, &size, &max_size, &reverse);
933 if (max_size != -1 && max_size == size)
934 combine_speculation_with (TYPE_MAIN_VARIANT (TREE_TYPE (base)),
935 offset + offset2,
936 true,
937 NULL /* Do not change outer type. */);
939 /* If this is a varying address, punt. */
940 if ((TREE_CODE (base) == MEM_REF || DECL_P (base))
941 && max_size != -1
942 && max_size == size)
944 /* We found dereference of a pointer. Type of the pointer
945 and MEM_REF is meaningless, but we can look futher. */
946 if (TREE_CODE (base) == MEM_REF)
948 base_pointer = TREE_OPERAND (base, 0);
949 offset
950 += offset2 + mem_ref_offset (base).to_short_addr () * BITS_PER_UNIT;
951 outer_type = NULL;
953 /* We found base object. In this case the outer_type
954 is known. */
955 else if (DECL_P (base))
957 if (visited)
958 delete (visited);
959 /* Only type inconsistent programs can have otr_type that is
960 not part of outer type. */
961 if (otr_type
962 && !contains_type_p (TREE_TYPE (base),
963 offset + offset2, otr_type))
965 invalid = true;
966 if (instance)
967 *instance = base_pointer;
968 return;
970 set_by_decl (base, offset + offset2);
971 if (outer_type && maybe_in_construction && stmt)
972 maybe_in_construction
973 = decl_maybe_in_construction_p (base,
974 outer_type,
975 stmt,
976 fndecl);
977 if (instance)
978 *instance = base;
979 return;
981 else
982 break;
984 else
985 break;
987 else if (TREE_CODE (base_pointer) == POINTER_PLUS_EXPR
988 && tree_fits_uhwi_p (TREE_OPERAND (base_pointer, 1)))
990 offset += tree_to_shwi (TREE_OPERAND (base_pointer, 1))
991 * BITS_PER_UNIT;
992 base_pointer = TREE_OPERAND (base_pointer, 0);
994 else
995 break;
998 if (visited)
999 delete (visited);
1001 /* Try to determine type of the outer object. */
1002 if (TREE_CODE (base_pointer) == SSA_NAME
1003 && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
1004 && TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL)
1006 /* See if parameter is THIS pointer of a method. */
1007 if (TREE_CODE (TREE_TYPE (fndecl)) == METHOD_TYPE
1008 && SSA_NAME_VAR (base_pointer) == DECL_ARGUMENTS (fndecl))
1010 outer_type
1011 = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
1012 gcc_assert (TREE_CODE (outer_type) == RECORD_TYPE
1013 || TREE_CODE (outer_type) == UNION_TYPE);
1015 /* Dynamic casting has possibly upcasted the type
1016 in the hiearchy. In this case outer type is less
1017 informative than inner type and we should forget
1018 about it. */
1019 if ((otr_type
1020 && !contains_type_p (outer_type, offset,
1021 otr_type))
1022 || !contains_polymorphic_type_p (outer_type))
1024 outer_type = NULL;
1025 if (instance)
1026 *instance = base_pointer;
1027 return;
1030 dynamic = true;
1032 /* If the function is constructor or destructor, then
1033 the type is possibly in construction, but we know
1034 it is not derived type. */
1035 if (DECL_CXX_CONSTRUCTOR_P (fndecl)
1036 || DECL_CXX_DESTRUCTOR_P (fndecl))
1038 maybe_in_construction = true;
1039 maybe_derived_type = false;
1041 else
1043 maybe_derived_type = true;
1044 maybe_in_construction = false;
1046 if (instance)
1047 *instance = base_pointer;
1048 return;
1050 /* Non-PODs passed by value are really passed by invisible
1051 reference. In this case we also know the type of the
1052 object. */
1053 if (DECL_BY_REFERENCE (SSA_NAME_VAR (base_pointer)))
1055 outer_type
1056 = TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (base_pointer)));
1057 /* Only type inconsistent programs can have otr_type that is
1058 not part of outer type. */
1059 if (otr_type && !contains_type_p (outer_type, offset,
1060 otr_type))
1062 invalid = true;
1063 if (instance)
1064 *instance = base_pointer;
1065 return;
1067 /* Non-polymorphic types have no interest for us. */
1068 else if (!otr_type && !contains_polymorphic_type_p (outer_type))
1070 outer_type = NULL;
1071 if (instance)
1072 *instance = base_pointer;
1073 return;
1075 maybe_derived_type = false;
1076 maybe_in_construction = false;
1077 if (instance)
1078 *instance = base_pointer;
1079 return;
1083 tree base_type = TREE_TYPE (base_pointer);
1085 if (TREE_CODE (base_pointer) == SSA_NAME
1086 && SSA_NAME_IS_DEFAULT_DEF (base_pointer)
1087 && !(TREE_CODE (SSA_NAME_VAR (base_pointer)) == PARM_DECL
1088 || TREE_CODE (SSA_NAME_VAR (base_pointer)) == RESULT_DECL))
1090 invalid = true;
1091 if (instance)
1092 *instance = base_pointer;
1093 return;
1095 if (TREE_CODE (base_pointer) == SSA_NAME
1096 && SSA_NAME_DEF_STMT (base_pointer)
1097 && gimple_assign_single_p (SSA_NAME_DEF_STMT (base_pointer)))
1098 base_type = TREE_TYPE (gimple_assign_rhs1
1099 (SSA_NAME_DEF_STMT (base_pointer)));
1101 if (base_type && POINTER_TYPE_P (base_type))
1102 combine_speculation_with (TYPE_MAIN_VARIANT (TREE_TYPE (base_type)),
1103 offset,
1104 true, NULL /* Do not change type here */);
1105 /* TODO: There are multiple ways to derive a type. For instance
1106 if BASE_POINTER is passed to an constructor call prior our refernece.
1107 We do not make this type of flow sensitive analysis yet. */
1108 if (instance)
1109 *instance = base_pointer;
1110 return;
1113 /* Structure to be passed in between detect_type_change and
1114 check_stmt_for_type_change. */
1116 struct type_change_info
1118 /* Offset into the object where there is the virtual method pointer we are
1119 looking for. */
1120 HOST_WIDE_INT offset;
1121 /* The declaration or SSA_NAME pointer of the base that we are checking for
1122 type change. */
1123 tree instance;
1124 /* The reference to virtual table pointer used. */
1125 tree vtbl_ptr_ref;
1126 tree otr_type;
1127 /* If we actually can tell the type that the object has changed to, it is
1128 stored in this field. Otherwise it remains NULL_TREE. */
1129 tree known_current_type;
1130 HOST_WIDE_INT known_current_offset;
1132 /* Set to true if dynamic type change has been detected. */
1133 bool type_maybe_changed;
1134 /* Set to true if multiple types have been encountered. known_current_type
1135 must be disregarded in that case. */
1136 bool multiple_types_encountered;
1137 /* Set to true if we possibly missed some dynamic type changes and we should
1138 consider the set to be speculative. */
1139 bool speculative;
1140 bool seen_unanalyzed_store;
1143 /* Return true if STMT is not call and can modify a virtual method table pointer.
1144 We take advantage of fact that vtable stores must appear within constructor
1145 and destructor functions. */
1147 static bool
1148 noncall_stmt_may_be_vtbl_ptr_store (gimple stmt)
1150 if (is_gimple_assign (stmt))
1152 tree lhs = gimple_assign_lhs (stmt);
1154 if (gimple_clobber_p (stmt))
1155 return false;
1156 if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
1158 if (flag_strict_aliasing
1159 && !POINTER_TYPE_P (TREE_TYPE (lhs)))
1160 return false;
1162 if (TREE_CODE (lhs) == COMPONENT_REF
1163 && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
1164 return false;
1165 /* In the future we might want to use get_base_ref_and_offset to find
1166 if there is a field corresponding to the offset and if so, proceed
1167 almost like if it was a component ref. */
1171 /* Code unification may mess with inline stacks. */
1172 if (cfun->after_inlining)
1173 return true;
1175 /* Walk the inline stack and watch out for ctors/dtors.
1176 TODO: Maybe we can require the store to appear in toplevel
1177 block of CTOR/DTOR. */
1178 for (tree block = gimple_block (stmt); block && TREE_CODE (block) == BLOCK;
1179 block = BLOCK_SUPERCONTEXT (block))
1180 if (BLOCK_ABSTRACT_ORIGIN (block)
1181 && TREE_CODE (BLOCK_ABSTRACT_ORIGIN (block)) == FUNCTION_DECL)
1182 return inlined_polymorphic_ctor_dtor_block_p (block, false);
1183 return (TREE_CODE (TREE_TYPE (current_function_decl)) == METHOD_TYPE
1184 && (DECL_CXX_CONSTRUCTOR_P (current_function_decl)
1185 || DECL_CXX_DESTRUCTOR_P (current_function_decl)));
1188 /* If STMT can be proved to be an assignment to the virtual method table
1189 pointer of ANALYZED_OBJ and the type associated with the new table
1190 identified, return the type. Otherwise return NULL_TREE if type changes
1191 in unknown way or ERROR_MARK_NODE if type is unchanged. */
1193 static tree
1194 extr_type_from_vtbl_ptr_store (gimple stmt, struct type_change_info *tci,
1195 HOST_WIDE_INT *type_offset)
1197 HOST_WIDE_INT offset, size, max_size;
1198 tree lhs, rhs, base;
1199 bool reverse;
1201 if (!gimple_assign_single_p (stmt))
1202 return NULL_TREE;
1204 lhs = gimple_assign_lhs (stmt);
1205 rhs = gimple_assign_rhs1 (stmt);
1206 if (TREE_CODE (lhs) != COMPONENT_REF
1207 || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
1209 if (dump_file)
1210 fprintf (dump_file, " LHS is not virtual table.\n");
1211 return NULL_TREE;
1214 if (tci->vtbl_ptr_ref && operand_equal_p (lhs, tci->vtbl_ptr_ref, 0))
1216 else
1218 base = get_ref_base_and_extent (lhs, &offset, &size, &max_size, &reverse);
1219 if (DECL_P (tci->instance))
1221 if (base != tci->instance)
1223 if (dump_file)
1225 fprintf (dump_file, " base:");
1226 print_generic_expr (dump_file, base, TDF_SLIM);
1227 fprintf (dump_file, " does not match instance:");
1228 print_generic_expr (dump_file, tci->instance, TDF_SLIM);
1229 fprintf (dump_file, "\n");
1231 return NULL_TREE;
1234 else if (TREE_CODE (base) == MEM_REF)
1236 if (!operand_equal_p (tci->instance, TREE_OPERAND (base, 0), 0))
1238 if (dump_file)
1240 fprintf (dump_file, " base mem ref:");
1241 print_generic_expr (dump_file, base, TDF_SLIM);
1242 fprintf (dump_file, " does not match instance:");
1243 print_generic_expr (dump_file, tci->instance, TDF_SLIM);
1244 fprintf (dump_file, "\n");
1246 return NULL_TREE;
1248 if (!integer_zerop (TREE_OPERAND (base, 1)))
1250 if (!tree_fits_shwi_p (TREE_OPERAND (base, 1)))
1252 if (dump_file)
1254 fprintf (dump_file, " base mem ref:");
1255 print_generic_expr (dump_file, base, TDF_SLIM);
1256 fprintf (dump_file, " has non-representable offset:");
1257 print_generic_expr (dump_file, tci->instance, TDF_SLIM);
1258 fprintf (dump_file, "\n");
1260 return NULL_TREE;
1262 else
1263 offset += tree_to_shwi (TREE_OPERAND (base, 1)) * BITS_PER_UNIT;
1266 else if (!operand_equal_p (tci->instance, base, 0)
1267 || tci->offset)
1269 if (dump_file)
1271 fprintf (dump_file, " base:");
1272 print_generic_expr (dump_file, base, TDF_SLIM);
1273 fprintf (dump_file, " does not match instance:");
1274 print_generic_expr (dump_file, tci->instance, TDF_SLIM);
1275 fprintf (dump_file, " with offset %i\n", (int)tci->offset);
1277 return tci->offset > POINTER_SIZE ? error_mark_node : NULL_TREE;
1279 if (offset != tci->offset
1280 || size != POINTER_SIZE
1281 || max_size != POINTER_SIZE)
1283 if (dump_file)
1284 fprintf (dump_file, " wrong offset %i!=%i or size %i\n",
1285 (int)offset, (int)tci->offset, (int)size);
1286 return offset + POINTER_SIZE <= tci->offset
1287 || (max_size != -1
1288 && tci->offset + POINTER_SIZE > offset + max_size)
1289 ? error_mark_node : NULL;
1293 tree vtable;
1294 unsigned HOST_WIDE_INT offset2;
1296 if (!vtable_pointer_value_to_vtable (rhs, &vtable, &offset2))
1298 if (dump_file)
1299 fprintf (dump_file, " Failed to lookup binfo\n");
1300 return NULL;
1303 tree binfo = subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
1304 offset2, vtable);
1305 if (!binfo)
1307 if (dump_file)
1308 fprintf (dump_file, " Construction vtable used\n");
1309 /* FIXME: We should suport construction contexts. */
1310 return NULL;
1313 *type_offset = tree_to_shwi (BINFO_OFFSET (binfo)) * BITS_PER_UNIT;
1314 return DECL_CONTEXT (vtable);
1317 /* Record dynamic type change of TCI to TYPE. */
1319 static void
1320 record_known_type (struct type_change_info *tci, tree type, HOST_WIDE_INT offset)
1322 if (dump_file)
1324 if (type)
1326 fprintf (dump_file, " Recording type: ");
1327 print_generic_expr (dump_file, type, TDF_SLIM);
1328 fprintf (dump_file, " at offset %i\n", (int)offset);
1330 else
1331 fprintf (dump_file, " Recording unknown type\n");
1334 /* If we found a constructor of type that is not polymorphic or
1335 that may contain the type in question as a field (not as base),
1336 restrict to the inner class first to make type matching bellow
1337 happier. */
1338 if (type
1339 && (offset
1340 || (TREE_CODE (type) != RECORD_TYPE
1341 || !TYPE_BINFO (type)
1342 || !polymorphic_type_binfo_p (TYPE_BINFO (type)))))
1344 ipa_polymorphic_call_context context;
1346 context.offset = offset;
1347 context.outer_type = type;
1348 context.maybe_in_construction = false;
1349 context.maybe_derived_type = false;
1350 context.dynamic = true;
1351 /* If we failed to find the inner type, we know that the call
1352 would be undefined for type produced here. */
1353 if (!context.restrict_to_inner_class (tci->otr_type))
1355 if (dump_file)
1356 fprintf (dump_file, " Ignoring; does not contain otr_type\n");
1357 return;
1359 /* Watch for case we reached an POD type and anticipate placement
1360 new. */
1361 if (!context.maybe_derived_type)
1363 type = context.outer_type;
1364 offset = context.offset;
1367 if (tci->type_maybe_changed
1368 && (!types_same_for_odr (type, tci->known_current_type)
1369 || offset != tci->known_current_offset))
1370 tci->multiple_types_encountered = true;
1371 tci->known_current_type = TYPE_MAIN_VARIANT (type);
1372 tci->known_current_offset = offset;
1373 tci->type_maybe_changed = true;
1376 /* Callback of walk_aliased_vdefs and a helper function for
1377 detect_type_change to check whether a particular statement may modify
1378 the virtual table pointer, and if possible also determine the new type of
1379 the (sub-)object. It stores its result into DATA, which points to a
1380 type_change_info structure. */
1382 static bool
1383 check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
1385 gimple stmt = SSA_NAME_DEF_STMT (vdef);
1386 struct type_change_info *tci = (struct type_change_info *) data;
1387 tree fn;
1389 /* If we already gave up, just terminate the rest of walk. */
1390 if (tci->multiple_types_encountered)
1391 return true;
1393 if (is_gimple_call (stmt))
1395 if (gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE))
1396 return false;
1398 /* Check for a constructor call. */
1399 if ((fn = gimple_call_fndecl (stmt)) != NULL_TREE
1400 && DECL_CXX_CONSTRUCTOR_P (fn)
1401 && TREE_CODE (TREE_TYPE (fn)) == METHOD_TYPE
1402 && gimple_call_num_args (stmt))
1404 tree op = walk_ssa_copies (gimple_call_arg (stmt, 0));
1405 tree type = method_class_type (TREE_TYPE (fn));
1406 HOST_WIDE_INT offset = 0, size, max_size;
1407 bool reverse;
1409 if (dump_file)
1411 fprintf (dump_file, " Checking constructor call: ");
1412 print_gimple_stmt (dump_file, stmt, 0, 0);
1415 /* See if THIS parameter seems like instance pointer. */
1416 if (TREE_CODE (op) == ADDR_EXPR)
1418 op = get_ref_base_and_extent (TREE_OPERAND (op, 0), &offset,
1419 &size, &max_size, &reverse);
1420 if (size != max_size || max_size == -1)
1422 tci->speculative = true;
1423 return false;
1425 if (op && TREE_CODE (op) == MEM_REF)
1427 if (!tree_fits_shwi_p (TREE_OPERAND (op, 1)))
1429 tci->speculative = true;
1430 return false;
1432 offset += tree_to_shwi (TREE_OPERAND (op, 1))
1433 * BITS_PER_UNIT;
1434 op = TREE_OPERAND (op, 0);
1436 else if (DECL_P (op))
1438 else
1440 tci->speculative = true;
1441 return false;
1443 op = walk_ssa_copies (op);
1445 if (operand_equal_p (op, tci->instance, 0)
1446 && TYPE_SIZE (type)
1447 && TREE_CODE (TYPE_SIZE (type)) == INTEGER_CST
1448 && tree_fits_shwi_p (TYPE_SIZE (type))
1449 && tree_to_shwi (TYPE_SIZE (type)) + offset > tci->offset)
1451 record_known_type (tci, type, tci->offset - offset);
1452 return true;
1455 /* Calls may possibly change dynamic type by placement new. Assume
1456 it will not happen, but make result speculative only. */
1457 if (dump_file)
1459 fprintf (dump_file, " Function call may change dynamic type:");
1460 print_gimple_stmt (dump_file, stmt, 0, 0);
1462 tci->speculative = true;
1463 return false;
1465 /* Check for inlined virtual table store. */
1466 else if (noncall_stmt_may_be_vtbl_ptr_store (stmt))
1468 tree type;
1469 HOST_WIDE_INT offset = 0;
1470 if (dump_file)
1472 fprintf (dump_file, " Checking vtbl store: ");
1473 print_gimple_stmt (dump_file, stmt, 0, 0);
1476 type = extr_type_from_vtbl_ptr_store (stmt, tci, &offset);
1477 if (type == error_mark_node)
1478 return false;
1479 gcc_assert (!type || TYPE_MAIN_VARIANT (type) == type);
1480 if (!type)
1482 if (dump_file)
1483 fprintf (dump_file, " Unanalyzed store may change type.\n");
1484 tci->seen_unanalyzed_store = true;
1485 tci->speculative = true;
1487 else
1488 record_known_type (tci, type, offset);
1489 return true;
1491 else
1492 return false;
1495 /* THIS is polymorphic call context obtained from get_polymorphic_context.
1496 OTR_OBJECT is pointer to the instance returned by OBJ_TYPE_REF_OBJECT.
1497 INSTANCE is pointer to the outer instance as returned by
1498 get_polymorphic_context. To avoid creation of temporary expressions,
1499 INSTANCE may also be an declaration of get_polymorphic_context found the
1500 value to be in static storage.
1502 If the type of instance is not fully determined
1503 (either OUTER_TYPE is unknown or MAYBE_IN_CONSTRUCTION/INCLUDE_DERIVED_TYPES
1504 is set), try to walk memory writes and find the actual construction of the
1505 instance.
1507 Return true if memory is unchanged from function entry.
1509 We do not include this analysis in the context analysis itself, because
1510 it needs memory SSA to be fully built and the walk may be expensive.
1511 So it is not suitable for use withing fold_stmt and similar uses. */
1513 bool
1514 ipa_polymorphic_call_context::get_dynamic_type (tree instance,
1515 tree otr_object,
1516 tree otr_type,
1517 gimple call)
1519 struct type_change_info tci;
1520 ao_ref ao;
1521 bool function_entry_reached = false;
1522 tree instance_ref = NULL;
1523 gimple stmt = call;
1524 /* Remember OFFSET before it is modified by restrict_to_inner_class.
1525 This is because we do not update INSTANCE when walking inwards. */
1526 HOST_WIDE_INT instance_offset = offset;
1528 if (otr_type)
1529 otr_type = TYPE_MAIN_VARIANT (otr_type);
1531 /* Walk into inner type. This may clear maybe_derived_type and save us
1532 from useless work. It also makes later comparsions with static type
1533 easier. */
1534 if (outer_type && otr_type)
1536 if (!restrict_to_inner_class (otr_type))
1537 return false;
1540 if (!maybe_in_construction && !maybe_derived_type)
1541 return false;
1543 /* We need to obtain refernce to virtual table pointer. It is better
1544 to look it up in the code rather than build our own. This require bit
1545 of pattern matching, but we end up verifying that what we found is
1546 correct.
1548 What we pattern match is:
1550 tmp = instance->_vptr.A; // vtbl ptr load
1551 tmp2 = tmp[otr_token]; // vtable lookup
1552 OBJ_TYPE_REF(tmp2;instance->0) (instance);
1554 We want to start alias oracle walk from vtbl pointer load,
1555 but we may not be able to identify it, for example, when PRE moved the
1556 load around. */
1558 if (gimple_code (call) == GIMPLE_CALL)
1560 tree ref = gimple_call_fn (call);
1561 HOST_WIDE_INT offset2, size, max_size;
1562 bool reverse;
1564 if (TREE_CODE (ref) == OBJ_TYPE_REF)
1566 ref = OBJ_TYPE_REF_EXPR (ref);
1567 ref = walk_ssa_copies (ref);
1569 /* Check if definition looks like vtable lookup. */
1570 if (TREE_CODE (ref) == SSA_NAME
1571 && !SSA_NAME_IS_DEFAULT_DEF (ref)
1572 && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref))
1573 && TREE_CODE (gimple_assign_rhs1
1574 (SSA_NAME_DEF_STMT (ref))) == MEM_REF)
1576 ref = get_base_address
1577 (TREE_OPERAND (gimple_assign_rhs1
1578 (SSA_NAME_DEF_STMT (ref)), 0));
1579 ref = walk_ssa_copies (ref);
1580 /* Find base address of the lookup and see if it looks like
1581 vptr load. */
1582 if (TREE_CODE (ref) == SSA_NAME
1583 && !SSA_NAME_IS_DEFAULT_DEF (ref)
1584 && gimple_assign_load_p (SSA_NAME_DEF_STMT (ref)))
1586 tree ref_exp = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (ref));
1587 tree base_ref
1588 = get_ref_base_and_extent (ref_exp, &offset2, &size,
1589 &max_size, &reverse);
1591 /* Finally verify that what we found looks like read from OTR_OBJECT
1592 or from INSTANCE with offset OFFSET. */
1593 if (base_ref
1594 && ((TREE_CODE (base_ref) == MEM_REF
1595 && ((offset2 == instance_offset
1596 && TREE_OPERAND (base_ref, 0) == instance)
1597 || (!offset2 && TREE_OPERAND (base_ref, 0) == otr_object)))
1598 || (DECL_P (instance) && base_ref == instance
1599 && offset2 == instance_offset)))
1601 stmt = SSA_NAME_DEF_STMT (ref);
1602 instance_ref = ref_exp;
1609 /* If we failed to look up the refernece in code, build our own. */
1610 if (!instance_ref)
1612 /* If the statement in question does not use memory, we can't tell
1613 anything. */
1614 if (!gimple_vuse (stmt))
1615 return false;
1616 ao_ref_init_from_ptr_and_size (&ao, otr_object, NULL);
1618 else
1619 /* Otherwise use the real reference. */
1620 ao_ref_init (&ao, instance_ref);
1622 /* We look for vtbl pointer read. */
1623 ao.size = POINTER_SIZE;
1624 ao.max_size = ao.size;
1625 if (otr_type)
1626 ao.ref_alias_set
1627 = get_deref_alias_set (TREE_TYPE (BINFO_VTABLE (TYPE_BINFO (otr_type))));
1629 if (dump_file)
1631 fprintf (dump_file, "Determining dynamic type for call: ");
1632 print_gimple_stmt (dump_file, call, 0, 0);
1633 fprintf (dump_file, " Starting walk at: ");
1634 print_gimple_stmt (dump_file, stmt, 0, 0);
1635 fprintf (dump_file, " instance pointer: ");
1636 print_generic_expr (dump_file, otr_object, TDF_SLIM);
1637 fprintf (dump_file, " Outer instance pointer: ");
1638 print_generic_expr (dump_file, instance, TDF_SLIM);
1639 fprintf (dump_file, " offset: %i (bits)", (int)offset);
1640 fprintf (dump_file, " vtbl reference: ");
1641 print_generic_expr (dump_file, instance_ref, TDF_SLIM);
1642 fprintf (dump_file, "\n");
1645 tci.offset = offset;
1646 tci.instance = instance;
1647 tci.vtbl_ptr_ref = instance_ref;
1648 gcc_assert (TREE_CODE (instance) != MEM_REF);
1649 tci.known_current_type = NULL_TREE;
1650 tci.known_current_offset = 0;
1651 tci.otr_type = otr_type;
1652 tci.type_maybe_changed = false;
1653 tci.multiple_types_encountered = false;
1654 tci.speculative = false;
1655 tci.seen_unanalyzed_store = false;
1657 walk_aliased_vdefs (&ao, gimple_vuse (stmt), check_stmt_for_type_change,
1658 &tci, NULL, &function_entry_reached);
1660 /* If we did not find any type changing statements, we may still drop
1661 maybe_in_construction flag if the context already have outer type.
1663 Here we make special assumptions about both constructors and
1664 destructors which are all the functions that are allowed to alter the
1665 VMT pointers. It assumes that destructors begin with assignment into
1666 all VMT pointers and that constructors essentially look in the
1667 following way:
1669 1) The very first thing they do is that they call constructors of
1670 ancestor sub-objects that have them.
1672 2) Then VMT pointers of this and all its ancestors is set to new
1673 values corresponding to the type corresponding to the constructor.
1675 3) Only afterwards, other stuff such as constructor of member
1676 sub-objects and the code written by the user is run. Only this may
1677 include calling virtual functions, directly or indirectly.
1679 4) placement new can not be used to change type of non-POD statically
1680 allocated variables.
1682 There is no way to call a constructor of an ancestor sub-object in any
1683 other way.
1685 This means that we do not have to care whether constructors get the
1686 correct type information because they will always change it (in fact,
1687 if we define the type to be given by the VMT pointer, it is undefined).
1689 The most important fact to derive from the above is that if, for some
1690 statement in the section 3, we try to detect whether the dynamic type
1691 has changed, we can safely ignore all calls as we examine the function
1692 body backwards until we reach statements in section 2 because these
1693 calls cannot be ancestor constructors or destructors (if the input is
1694 not bogus) and so do not change the dynamic type (this holds true only
1695 for automatically allocated objects but at the moment we devirtualize
1696 only these). We then must detect that statements in section 2 change
1697 the dynamic type and can try to derive the new type. That is enough
1698 and we can stop, we will never see the calls into constructors of
1699 sub-objects in this code.
1701 Therefore if the static outer type was found (outer_type)
1702 we can safely ignore tci.speculative that is set on calls and give up
1703 only if there was dyanmic type store that may affect given variable
1704 (seen_unanalyzed_store) */
1706 if (!tci.type_maybe_changed
1707 || (outer_type
1708 && !dynamic
1709 && !tci.seen_unanalyzed_store
1710 && !tci.multiple_types_encountered
1711 && offset == tci.offset
1712 && types_same_for_odr (tci.known_current_type,
1713 outer_type)))
1715 if (!outer_type || tci.seen_unanalyzed_store)
1716 return false;
1717 if (maybe_in_construction)
1718 maybe_in_construction = false;
1719 if (dump_file)
1720 fprintf (dump_file, " No dynamic type change found.\n");
1721 return true;
1724 if (tci.known_current_type
1725 && !function_entry_reached
1726 && !tci.multiple_types_encountered)
1728 if (!tci.speculative)
1730 outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
1731 offset = tci.known_current_offset;
1732 dynamic = true;
1733 maybe_in_construction = false;
1734 maybe_derived_type = false;
1735 if (dump_file)
1736 fprintf (dump_file, " Determined dynamic type.\n");
1738 else if (!speculative_outer_type
1739 || speculative_maybe_derived_type)
1741 speculative_outer_type = TYPE_MAIN_VARIANT (tci.known_current_type);
1742 speculative_offset = tci.known_current_offset;
1743 speculative_maybe_derived_type = false;
1744 if (dump_file)
1745 fprintf (dump_file, " Determined speculative dynamic type.\n");
1748 else if (dump_file)
1750 fprintf (dump_file, " Found multiple types%s%s\n",
1751 function_entry_reached ? " (function entry reached)" : "",
1752 function_entry_reached ? " (multiple types encountered)" : "");
1755 return false;
1758 /* See if speculation given by SPEC_OUTER_TYPE, SPEC_OFFSET and SPEC_MAYBE_DERIVED_TYPE
1759 seems consistent (and useful) with what we already have in the non-speculative context. */
1761 bool
1762 ipa_polymorphic_call_context::speculation_consistent_p (tree spec_outer_type,
1763 HOST_WIDE_INT spec_offset,
1764 bool spec_maybe_derived_type,
1765 tree otr_type) const
1767 if (!flag_devirtualize_speculatively)
1768 return false;
1770 /* Non-polymorphic types are useless for deriving likely polymorphic
1771 call targets. */
1772 if (!spec_outer_type || !contains_polymorphic_type_p (spec_outer_type))
1773 return false;
1775 /* If we know nothing, speculation is always good. */
1776 if (!outer_type)
1777 return true;
1779 /* Speculation is only useful to avoid derived types.
1780 This is not 100% true for placement new, where the outer context may
1781 turn out to be useless, but ignore these for now. */
1782 if (!maybe_derived_type)
1783 return false;
1785 /* If types agrees, speculation is consistent, but it makes sense only
1786 when it says something new. */
1787 if (types_must_be_same_for_odr (spec_outer_type, outer_type))
1788 return maybe_derived_type && !spec_maybe_derived_type;
1790 /* If speculation does not contain the type in question, ignore it. */
1791 if (otr_type
1792 && !contains_type_p (spec_outer_type, spec_offset, otr_type, false, true))
1793 return false;
1795 /* If outer type already contains speculation as a filed,
1796 it is useless. We already know from OUTER_TYPE
1797 SPEC_TYPE and that it is not in the construction. */
1798 if (contains_type_p (outer_type, offset - spec_offset,
1799 spec_outer_type, false, false))
1800 return false;
1802 /* If speculative outer type is not more specified than outer
1803 type, just give up.
1804 We can only decide this safely if we can compare types with OUTER_TYPE.
1806 if ((!in_lto_p || odr_type_p (outer_type))
1807 && !contains_type_p (spec_outer_type,
1808 spec_offset - offset,
1809 outer_type, false))
1810 return false;
1811 return true;
1814 /* Improve THIS with speculation described by NEW_OUTER_TYPE, NEW_OFFSET,
1815 NEW_MAYBE_DERIVED_TYPE
1816 If OTR_TYPE is set, assume the context is used with OTR_TYPE. */
1818 bool
1819 ipa_polymorphic_call_context::combine_speculation_with
1820 (tree new_outer_type, HOST_WIDE_INT new_offset, bool new_maybe_derived_type,
1821 tree otr_type)
1823 if (!new_outer_type)
1824 return false;
1826 /* restrict_to_inner_class may eliminate wrong speculation making our job
1827 easeier. */
1828 if (otr_type)
1829 restrict_to_inner_class (otr_type);
1831 if (!speculation_consistent_p (new_outer_type, new_offset,
1832 new_maybe_derived_type, otr_type))
1833 return false;
1835 /* New speculation is a win in case we have no speculation or new
1836 speculation does not consider derivations. */
1837 if (!speculative_outer_type
1838 || (speculative_maybe_derived_type
1839 && !new_maybe_derived_type))
1841 speculative_outer_type = new_outer_type;
1842 speculative_offset = new_offset;
1843 speculative_maybe_derived_type = new_maybe_derived_type;
1844 return true;
1846 else if (types_must_be_same_for_odr (speculative_outer_type,
1847 new_outer_type))
1849 if (speculative_offset != new_offset)
1851 /* OK we have two contexts that seems valid but they disagree,
1852 just give up.
1854 This is not a lattice operation, so we may want to drop it later. */
1855 if (dump_file && (dump_flags & TDF_DETAILS))
1856 fprintf (dump_file,
1857 "Speculative outer types match, "
1858 "offset mismatch -> invalid speculation\n");
1859 clear_speculation ();
1860 return true;
1862 else
1864 if (speculative_maybe_derived_type && !new_maybe_derived_type)
1866 speculative_maybe_derived_type = false;
1867 return true;
1869 else
1870 return false;
1873 /* Choose type that contains the other. This one either contains the outer
1874 as a field (thus giving exactly one target) or is deeper in the type
1875 hiearchy. */
1876 else if (speculative_outer_type
1877 && speculative_maybe_derived_type
1878 && (new_offset > speculative_offset
1879 || (new_offset == speculative_offset
1880 && contains_type_p (new_outer_type,
1881 0, speculative_outer_type, false))))
1883 tree old_outer_type = speculative_outer_type;
1884 HOST_WIDE_INT old_offset = speculative_offset;
1885 bool old_maybe_derived_type = speculative_maybe_derived_type;
1887 speculative_outer_type = new_outer_type;
1888 speculative_offset = new_offset;
1889 speculative_maybe_derived_type = new_maybe_derived_type;
1891 if (otr_type)
1892 restrict_to_inner_class (otr_type);
1894 /* If the speculation turned out to make no sense, revert to sensible
1895 one. */
1896 if (!speculative_outer_type)
1898 speculative_outer_type = old_outer_type;
1899 speculative_offset = old_offset;
1900 speculative_maybe_derived_type = old_maybe_derived_type;
1901 return false;
1903 return (old_offset != speculative_offset
1904 || old_maybe_derived_type != speculative_maybe_derived_type
1905 || types_must_be_same_for_odr (speculative_outer_type,
1906 new_outer_type));
1908 return false;
1911 /* Make speculation less specific so
1912 NEW_OUTER_TYPE, NEW_OFFSET, NEW_MAYBE_DERIVED_TYPE is also included.
1913 If OTR_TYPE is set, assume the context is used with OTR_TYPE. */
1915 bool
1916 ipa_polymorphic_call_context::meet_speculation_with
1917 (tree new_outer_type, HOST_WIDE_INT new_offset, bool new_maybe_derived_type,
1918 tree otr_type)
1920 if (!new_outer_type && speculative_outer_type)
1922 clear_speculation ();
1923 return true;
1926 /* restrict_to_inner_class may eliminate wrong speculation making our job
1927 easeier. */
1928 if (otr_type)
1929 restrict_to_inner_class (otr_type);
1931 if (!speculative_outer_type
1932 || !speculation_consistent_p (speculative_outer_type,
1933 speculative_offset,
1934 speculative_maybe_derived_type,
1935 otr_type))
1936 return false;
1938 if (!speculation_consistent_p (new_outer_type, new_offset,
1939 new_maybe_derived_type, otr_type))
1941 clear_speculation ();
1942 return true;
1945 else if (types_must_be_same_for_odr (speculative_outer_type,
1946 new_outer_type))
1948 if (speculative_offset != new_offset)
1950 clear_speculation ();
1951 return true;
1953 else
1955 if (!speculative_maybe_derived_type && new_maybe_derived_type)
1957 speculative_maybe_derived_type = true;
1958 return true;
1960 else
1961 return false;
1964 /* See if one type contains the other as a field (not base). */
1965 else if (contains_type_p (new_outer_type, new_offset - speculative_offset,
1966 speculative_outer_type, false, false))
1967 return false;
1968 else if (contains_type_p (speculative_outer_type,
1969 speculative_offset - new_offset,
1970 new_outer_type, false, false))
1972 speculative_outer_type = new_outer_type;
1973 speculative_offset = new_offset;
1974 speculative_maybe_derived_type = new_maybe_derived_type;
1975 return true;
1977 /* See if OUTER_TYPE is base of CTX.OUTER_TYPE. */
1978 else if (contains_type_p (new_outer_type,
1979 new_offset - speculative_offset,
1980 speculative_outer_type, false, true))
1982 if (!speculative_maybe_derived_type)
1984 speculative_maybe_derived_type = true;
1985 return true;
1987 return false;
1989 /* See if CTX.OUTER_TYPE is base of OUTER_TYPE. */
1990 else if (contains_type_p (speculative_outer_type,
1991 speculative_offset - new_offset, new_outer_type, false, true))
1993 speculative_outer_type = new_outer_type;
1994 speculative_offset = new_offset;
1995 speculative_maybe_derived_type = true;
1996 return true;
1998 else
2000 if (dump_file && (dump_flags & TDF_DETAILS))
2001 fprintf (dump_file, "Giving up on speculative meet\n");
2002 clear_speculation ();
2003 return true;
2007 /* Assume that both THIS and a given context is valid and strenghten THIS
2008 if possible. Return true if any strenghtening was made.
2009 If actual type the context is being used in is known, OTR_TYPE should be
2010 set accordingly. This improves quality of combined result. */
2012 bool
2013 ipa_polymorphic_call_context::combine_with (ipa_polymorphic_call_context ctx,
2014 tree otr_type)
2016 bool updated = false;
2018 if (ctx.useless_p () || invalid)
2019 return false;
2021 /* Restricting context to inner type makes merging easier, however do not
2022 do that unless we know how the context is used (OTR_TYPE is non-NULL) */
2023 if (otr_type && !invalid && !ctx.invalid)
2025 restrict_to_inner_class (otr_type);
2026 ctx.restrict_to_inner_class (otr_type);
2027 if(invalid)
2028 return false;
2031 if (dump_file && (dump_flags & TDF_DETAILS))
2033 fprintf (dump_file, "Polymorphic call context combine:");
2034 dump (dump_file);
2035 fprintf (dump_file, "With context: ");
2036 ctx.dump (dump_file);
2037 if (otr_type)
2039 fprintf (dump_file, "To be used with type: ");
2040 print_generic_expr (dump_file, otr_type, TDF_SLIM);
2041 fprintf (dump_file, "\n");
2045 /* If call is known to be invalid, we are done. */
2046 if (ctx.invalid)
2048 if (dump_file && (dump_flags & TDF_DETAILS))
2049 fprintf (dump_file, "-> Invalid context\n");
2050 goto invalidate;
2053 if (!ctx.outer_type)
2055 else if (!outer_type)
2057 outer_type = ctx.outer_type;
2058 offset = ctx.offset;
2059 dynamic = ctx.dynamic;
2060 maybe_in_construction = ctx.maybe_in_construction;
2061 maybe_derived_type = ctx.maybe_derived_type;
2062 updated = true;
2064 /* If types are known to be same, merging is quite easy. */
2065 else if (types_must_be_same_for_odr (outer_type, ctx.outer_type))
2067 if (offset != ctx.offset
2068 && TYPE_SIZE (outer_type)
2069 && TREE_CODE (TYPE_SIZE (outer_type)) == INTEGER_CST)
2071 if (dump_file && (dump_flags & TDF_DETAILS))
2072 fprintf (dump_file, "Outer types match, offset mismatch -> invalid\n");
2073 clear_speculation ();
2074 clear_outer_type ();
2075 invalid = true;
2076 return true;
2078 if (dump_file && (dump_flags & TDF_DETAILS))
2079 fprintf (dump_file, "Outer types match, merging flags\n");
2080 if (maybe_in_construction && !ctx.maybe_in_construction)
2082 updated = true;
2083 maybe_in_construction = false;
2085 if (maybe_derived_type && !ctx.maybe_derived_type)
2087 updated = true;
2088 maybe_derived_type = false;
2090 if (dynamic && !ctx.dynamic)
2092 updated = true;
2093 dynamic = false;
2096 /* If we know the type precisely, there is not much to improve. */
2097 else if (!maybe_derived_type && !maybe_in_construction
2098 && !ctx.maybe_derived_type && !ctx.maybe_in_construction)
2100 /* It may be easy to check if second context permits the first
2101 and set INVALID otherwise. This is not easy to do in general;
2102 contains_type_p may return false negatives for non-comparable
2103 types.
2105 If OTR_TYPE is known, we however can expect that
2106 restrict_to_inner_class should have discovered the same base
2107 type. */
2108 if (otr_type && !ctx.maybe_in_construction && !ctx.maybe_derived_type)
2110 if (dump_file && (dump_flags & TDF_DETAILS))
2111 fprintf (dump_file, "Contextes disagree -> invalid\n");
2112 goto invalidate;
2115 /* See if one type contains the other as a field (not base).
2116 In this case we want to choose the wider type, because it contains
2117 more information. */
2118 else if (contains_type_p (ctx.outer_type, ctx.offset - offset,
2119 outer_type, false, false))
2121 if (dump_file && (dump_flags & TDF_DETAILS))
2122 fprintf (dump_file, "Second type contain the first as a field\n");
2124 if (maybe_derived_type)
2126 outer_type = ctx.outer_type;
2127 maybe_derived_type = ctx.maybe_derived_type;
2128 offset = ctx.offset;
2129 dynamic = ctx.dynamic;
2130 updated = true;
2133 /* If we do not know how the context is being used, we can
2134 not clear MAYBE_IN_CONSTRUCTION because it may be offseted
2135 to other component of OUTER_TYPE later and we know nothing
2136 about it. */
2137 if (otr_type && maybe_in_construction
2138 && !ctx.maybe_in_construction)
2140 maybe_in_construction = false;
2141 updated = true;
2144 else if (contains_type_p (outer_type, offset - ctx.offset,
2145 ctx.outer_type, false, false))
2147 if (dump_file && (dump_flags & TDF_DETAILS))
2148 fprintf (dump_file, "First type contain the second as a field\n");
2150 if (otr_type && maybe_in_construction
2151 && !ctx.maybe_in_construction)
2153 maybe_in_construction = false;
2154 updated = true;
2157 /* See if OUTER_TYPE is base of CTX.OUTER_TYPE. */
2158 else if (contains_type_p (ctx.outer_type,
2159 ctx.offset - offset, outer_type, false, true))
2161 if (dump_file && (dump_flags & TDF_DETAILS))
2162 fprintf (dump_file, "First type is base of second\n");
2163 if (!maybe_derived_type)
2165 if (!ctx.maybe_in_construction
2166 && types_odr_comparable (outer_type, ctx.outer_type))
2168 if (dump_file && (dump_flags & TDF_DETAILS))
2169 fprintf (dump_file, "Second context does not permit base -> invalid\n");
2170 goto invalidate;
2173 /* Pick variant deeper in the hiearchy. */
2174 else
2176 outer_type = ctx.outer_type;
2177 maybe_in_construction = ctx.maybe_in_construction;
2178 maybe_derived_type = ctx.maybe_derived_type;
2179 offset = ctx.offset;
2180 dynamic = ctx.dynamic;
2181 updated = true;
2184 /* See if CTX.OUTER_TYPE is base of OUTER_TYPE. */
2185 else if (contains_type_p (outer_type,
2186 offset - ctx.offset, ctx.outer_type, false, true))
2188 if (dump_file && (dump_flags & TDF_DETAILS))
2189 fprintf (dump_file, "Second type is base of first\n");
2190 if (!ctx.maybe_derived_type)
2192 if (!maybe_in_construction
2193 && types_odr_comparable (outer_type, ctx.outer_type))
2195 if (dump_file && (dump_flags & TDF_DETAILS))
2196 fprintf (dump_file, "First context does not permit base -> invalid\n");
2197 goto invalidate;
2199 /* Pick the base type. */
2200 else if (maybe_in_construction)
2202 outer_type = ctx.outer_type;
2203 maybe_in_construction = ctx.maybe_in_construction;
2204 maybe_derived_type = ctx.maybe_derived_type;
2205 offset = ctx.offset;
2206 dynamic = ctx.dynamic;
2207 updated = true;
2211 /* TODO handle merging using hiearchy. */
2212 else if (dump_file && (dump_flags & TDF_DETAILS))
2213 fprintf (dump_file, "Giving up on merge\n");
2215 updated |= combine_speculation_with (ctx.speculative_outer_type,
2216 ctx.speculative_offset,
2217 ctx.speculative_maybe_derived_type,
2218 otr_type);
2220 if (updated && dump_file && (dump_flags & TDF_DETAILS))
2222 fprintf (dump_file, "Updated as: ");
2223 dump (dump_file);
2224 fprintf (dump_file, "\n");
2226 return updated;
2228 invalidate:
2229 invalid = true;
2230 clear_speculation ();
2231 clear_outer_type ();
2232 return true;
2235 /* Take non-speculative info, merge it with speculative and clear speculation.
2236 Used when we no longer manage to keep track of actual outer type, but we
2237 think it is still there.
2239 If OTR_TYPE is set, the transformation can be done more effectively assuming
2240 that context is going to be used only that way. */
2242 void
2243 ipa_polymorphic_call_context::make_speculative (tree otr_type)
2245 tree spec_outer_type = outer_type;
2246 HOST_WIDE_INT spec_offset = offset;
2247 bool spec_maybe_derived_type = maybe_derived_type;
2249 if (invalid)
2251 invalid = false;
2252 clear_outer_type ();
2253 clear_speculation ();
2254 return;
2256 if (!outer_type)
2257 return;
2258 clear_outer_type ();
2259 combine_speculation_with (spec_outer_type, spec_offset,
2260 spec_maybe_derived_type,
2261 otr_type);
2264 /* Use when we can not track dynamic type change. This speculatively assume
2265 type change is not happening. */
2267 void
2268 ipa_polymorphic_call_context::possible_dynamic_type_change (bool in_poly_cdtor,
2269 tree otr_type)
2271 if (dynamic)
2272 make_speculative (otr_type);
2273 else if (in_poly_cdtor)
2274 maybe_in_construction = true;
2277 /* Return TRUE if this context conveys the same information as OTHER. */
2279 bool
2280 ipa_polymorphic_call_context::equal_to
2281 (const ipa_polymorphic_call_context &x) const
2283 if (useless_p ())
2284 return x.useless_p ();
2285 if (invalid)
2286 return x.invalid;
2287 if (x.useless_p () || x.invalid)
2288 return false;
2290 if (outer_type)
2292 if (!x.outer_type
2293 || !types_odr_comparable (outer_type, x.outer_type)
2294 || !types_same_for_odr (outer_type, x.outer_type)
2295 || offset != x.offset
2296 || maybe_in_construction != x.maybe_in_construction
2297 || maybe_derived_type != x.maybe_derived_type
2298 || dynamic != x.dynamic)
2299 return false;
2301 else if (x.outer_type)
2302 return false;
2305 if (speculative_outer_type
2306 && speculation_consistent_p (speculative_outer_type, speculative_offset,
2307 speculative_maybe_derived_type, NULL_TREE))
2309 if (!x.speculative_outer_type)
2310 return false;
2312 if (!types_odr_comparable (speculative_outer_type,
2313 x.speculative_outer_type)
2314 || !types_same_for_odr (speculative_outer_type,
2315 x.speculative_outer_type)
2316 || speculative_offset != x.speculative_offset
2317 || speculative_maybe_derived_type != x.speculative_maybe_derived_type)
2318 return false;
2320 else if (x.speculative_outer_type
2321 && x.speculation_consistent_p (x.speculative_outer_type,
2322 x.speculative_offset,
2323 x.speculative_maybe_derived_type,
2324 NULL))
2325 return false;
2327 return true;
2330 /* Modify context to be strictly less restrictive than CTX. */
2332 bool
2333 ipa_polymorphic_call_context::meet_with (ipa_polymorphic_call_context ctx,
2334 tree otr_type)
2336 bool updated = false;
2338 if (useless_p () || ctx.invalid)
2339 return false;
2341 /* Restricting context to inner type makes merging easier, however do not
2342 do that unless we know how the context is used (OTR_TYPE is non-NULL) */
2343 if (otr_type && !useless_p () && !ctx.useless_p ())
2345 restrict_to_inner_class (otr_type);
2346 ctx.restrict_to_inner_class (otr_type);
2347 if(invalid)
2348 return false;
2351 if (equal_to (ctx))
2352 return false;
2354 if (ctx.useless_p () || invalid)
2356 *this = ctx;
2357 return true;
2360 if (dump_file && (dump_flags & TDF_DETAILS))
2362 fprintf (dump_file, "Polymorphic call context meet:");
2363 dump (dump_file);
2364 fprintf (dump_file, "With context: ");
2365 ctx.dump (dump_file);
2366 if (otr_type)
2368 fprintf (dump_file, "To be used with type: ");
2369 print_generic_expr (dump_file, otr_type, TDF_SLIM);
2370 fprintf (dump_file, "\n");
2374 if (!dynamic && ctx.dynamic)
2376 dynamic = true;
2377 updated = true;
2380 /* If call is known to be invalid, we are done. */
2381 if (!outer_type)
2383 else if (!ctx.outer_type)
2385 clear_outer_type ();
2386 updated = true;
2388 /* If types are known to be same, merging is quite easy. */
2389 else if (types_must_be_same_for_odr (outer_type, ctx.outer_type))
2391 if (offset != ctx.offset
2392 && TYPE_SIZE (outer_type)
2393 && TREE_CODE (TYPE_SIZE (outer_type)) == INTEGER_CST)
2395 if (dump_file && (dump_flags & TDF_DETAILS))
2396 fprintf (dump_file, "Outer types match, offset mismatch -> clearing\n");
2397 clear_outer_type ();
2398 return true;
2400 if (dump_file && (dump_flags & TDF_DETAILS))
2401 fprintf (dump_file, "Outer types match, merging flags\n");
2402 if (!maybe_in_construction && ctx.maybe_in_construction)
2404 updated = true;
2405 maybe_in_construction = true;
2407 if (!maybe_derived_type && ctx.maybe_derived_type)
2409 updated = true;
2410 maybe_derived_type = true;
2412 if (!dynamic && ctx.dynamic)
2414 updated = true;
2415 dynamic = true;
2418 /* See if one type contains the other as a field (not base). */
2419 else if (contains_type_p (ctx.outer_type, ctx.offset - offset,
2420 outer_type, false, false))
2422 if (dump_file && (dump_flags & TDF_DETAILS))
2423 fprintf (dump_file, "Second type contain the first as a field\n");
2425 /* The second type is more specified, so we keep the first.
2426 We need to set DYNAMIC flag to avoid declaring context INVALID
2427 of OFFSET ends up being out of range. */
2428 if (!dynamic
2429 && (ctx.dynamic
2430 || (!otr_type
2431 && (!TYPE_SIZE (ctx.outer_type)
2432 || !TYPE_SIZE (outer_type)
2433 || !operand_equal_p (TYPE_SIZE (ctx.outer_type),
2434 TYPE_SIZE (outer_type), 0)))))
2436 dynamic = true;
2437 updated = true;
2440 else if (contains_type_p (outer_type, offset - ctx.offset,
2441 ctx.outer_type, false, false))
2443 if (dump_file && (dump_flags & TDF_DETAILS))
2444 fprintf (dump_file, "First type contain the second as a field\n");
2446 if (!dynamic
2447 && (ctx.dynamic
2448 || (!otr_type
2449 && (!TYPE_SIZE (ctx.outer_type)
2450 || !TYPE_SIZE (outer_type)
2451 || !operand_equal_p (TYPE_SIZE (ctx.outer_type),
2452 TYPE_SIZE (outer_type), 0)))))
2453 dynamic = true;
2454 outer_type = ctx.outer_type;
2455 offset = ctx.offset;
2456 dynamic = ctx.dynamic;
2457 maybe_in_construction = ctx.maybe_in_construction;
2458 maybe_derived_type = ctx.maybe_derived_type;
2459 updated = true;
2461 /* See if OUTER_TYPE is base of CTX.OUTER_TYPE. */
2462 else if (contains_type_p (ctx.outer_type,
2463 ctx.offset - offset, outer_type, false, true))
2465 if (dump_file && (dump_flags & TDF_DETAILS))
2466 fprintf (dump_file, "First type is base of second\n");
2467 if (!maybe_derived_type)
2469 maybe_derived_type = true;
2470 updated = true;
2472 if (!maybe_in_construction && ctx.maybe_in_construction)
2474 maybe_in_construction = true;
2475 updated = true;
2477 if (!dynamic && ctx.dynamic)
2479 dynamic = true;
2480 updated = true;
2483 /* See if CTX.OUTER_TYPE is base of OUTER_TYPE. */
2484 else if (contains_type_p (outer_type,
2485 offset - ctx.offset, ctx.outer_type, false, true))
2487 if (dump_file && (dump_flags & TDF_DETAILS))
2488 fprintf (dump_file, "Second type is base of first\n");
2489 outer_type = ctx.outer_type;
2490 offset = ctx.offset;
2491 updated = true;
2492 if (!maybe_derived_type)
2493 maybe_derived_type = true;
2494 if (!maybe_in_construction && ctx.maybe_in_construction)
2495 maybe_in_construction = true;
2496 if (!dynamic && ctx.dynamic)
2497 dynamic = true;
2499 /* TODO handle merging using hiearchy. */
2500 else
2502 if (dump_file && (dump_flags & TDF_DETAILS))
2503 fprintf (dump_file, "Giving up on meet\n");
2504 clear_outer_type ();
2505 updated = true;
2508 updated |= meet_speculation_with (ctx.speculative_outer_type,
2509 ctx.speculative_offset,
2510 ctx.speculative_maybe_derived_type,
2511 otr_type);
2513 if (updated && dump_file && (dump_flags & TDF_DETAILS))
2515 fprintf (dump_file, "Updated as: ");
2516 dump (dump_file);
2517 fprintf (dump_file, "\n");
2519 return updated;