+/* Worker for prune_expression_for_jf. */
+
+static tree
+prune_expression_for_jf_1 (tree *tp, int *walk_subtrees, void *)
+{
+ if (EXPR_P (*tp))
+ SET_EXPR_LOCATION (*tp, UNKNOWN_LOCATION);
+ else
+ *walk_subtrees = 0;
+ return NULL_TREE;
+}
+
+/* Return the expression tree EXPR unshared and with location stripped off. */
+
+static tree
+prune_expression_for_jf (tree exp)
+{
+ if (EXPR_P (exp))
+ {
+ exp = unshare_expr (exp);
+ walk_tree (&exp, prune_expression_for_jf_1, NULL, NULL);
+ }
+ return exp;
+}
+
+/* Set JFUNC to be a known type jump function. */
+
+static void
+ipa_set_jf_known_type (struct ipa_jump_func *jfunc, HOST_WIDE_INT offset,
+ tree base_type, tree component_type)
+{
+ jfunc->type = IPA_JF_KNOWN_TYPE;
+ jfunc->value.known_type.offset = offset,
+ jfunc->value.known_type.base_type = base_type;
+ jfunc->value.known_type.component_type = component_type;
+}
+
+/* Set JFUNC to be a constant jmp function. */
+
+static void
+ipa_set_jf_constant (struct ipa_jump_func *jfunc, tree constant)
+{
+ constant = unshare_expr (constant);
+ if (constant && EXPR_P (constant))
+ SET_EXPR_LOCATION (constant, UNKNOWN_LOCATION);
+ jfunc->type = IPA_JF_CONST;
+ jfunc->value.constant = prune_expression_for_jf (constant);
+}
+
+/* Set JFUNC to be a simple pass-through jump function. */
+static void
+ipa_set_jf_simple_pass_through (struct ipa_jump_func *jfunc, int formal_id,
+ bool agg_preserved)
+{
+ jfunc->type = IPA_JF_PASS_THROUGH;
+ jfunc->value.pass_through.operand = NULL_TREE;
+ jfunc->value.pass_through.formal_id = formal_id;
+ jfunc->value.pass_through.operation = NOP_EXPR;
+ jfunc->value.pass_through.agg_preserved = agg_preserved;
+}
+
+/* Set JFUNC to be an arithmetic pass through jump function. */
+
+static void
+ipa_set_jf_arith_pass_through (struct ipa_jump_func *jfunc, int formal_id,
+ tree operand, enum tree_code operation)
+{
+ jfunc->type = IPA_JF_PASS_THROUGH;
+ jfunc->value.pass_through.operand = prune_expression_for_jf (operand);
+ jfunc->value.pass_through.formal_id = formal_id;
+ jfunc->value.pass_through.operation = operation;
+ jfunc->value.pass_through.agg_preserved = false;
+}
+
+/* Set JFUNC to be an ancestor jump function. */
+
+static void
+ipa_set_ancestor_jf (struct ipa_jump_func *jfunc, HOST_WIDE_INT offset,
+ tree type, int formal_id, bool agg_preserved)
+{
+ jfunc->type = IPA_JF_ANCESTOR;
+ jfunc->value.ancestor.formal_id = formal_id;
+ jfunc->value.ancestor.offset = offset;
+ jfunc->value.ancestor.type = type;
+ jfunc->value.ancestor.agg_preserved = agg_preserved;
+}
+
+/* Structure to be passed in between detect_type_change and
+ check_stmt_for_type_change. */
+
+struct type_change_info
+{
+ /* Offset into the object where there is the virtual method pointer we are
+ looking for. */
+ HOST_WIDE_INT offset;
+ /* The declaration or SSA_NAME pointer of the base that we are checking for
+ type change. */
+ tree object;
+ /* If we actually can tell the type that the object has changed to, it is
+ stored in this field. Otherwise it remains NULL_TREE. */
+ tree known_current_type;
+ /* Set to true if dynamic type change has been detected. */
+ bool type_maybe_changed;
+ /* Set to true if multiple types have been encountered. known_current_type
+ must be disregarded in that case. */
+ bool multiple_types_encountered;
+};
+
+/* Return true if STMT can modify a virtual method table pointer.
+
+ This function makes special assumptions about both constructors and
+ destructors which are all the functions that are allowed to alter the VMT
+ pointers. It assumes that destructors begin with assignment into all VMT
+ pointers and that constructors essentially look in the following way:
+
+ 1) The very first thing they do is that they call constructors of ancestor
+ sub-objects that have them.
+
+ 2) Then VMT pointers of this and all its ancestors is set to new values
+ corresponding to the type corresponding to the constructor.
+
+ 3) Only afterwards, other stuff such as constructor of member sub-objects
+ and the code written by the user is run. Only this may include calling
+ virtual functions, directly or indirectly.
+
+ There is no way to call a constructor of an ancestor sub-object in any
+ other way.
+
+ This means that we do not have to care whether constructors get the correct
+ type information because they will always change it (in fact, if we define
+ the type to be given by the VMT pointer, it is undefined).
+
+ The most important fact to derive from the above is that if, for some
+ statement in the section 3, we try to detect whether the dynamic type has
+ changed, we can safely ignore all calls as we examine the function body
+ backwards until we reach statements in section 2 because these calls cannot
+ be ancestor constructors or destructors (if the input is not bogus) and so
+ do not change the dynamic type (this holds true only for automatically
+ allocated objects but at the moment we devirtualize only these). We then
+ must detect that statements in section 2 change the dynamic type and can try
+ to derive the new type. That is enough and we can stop, we will never see
+ the calls into constructors of sub-objects in this code. Therefore we can
+ safely ignore all call statements that we traverse.
+ */
+
+static bool
+stmt_may_be_vtbl_ptr_store (gimple stmt)
+{
+ if (is_gimple_call (stmt))
+ return false;
+ else if (is_gimple_assign (stmt))
+ {
+ tree lhs = gimple_assign_lhs (stmt);
+
+ if (!AGGREGATE_TYPE_P (TREE_TYPE (lhs)))
+ {
+ if (flag_strict_aliasing
+ && !POINTER_TYPE_P (TREE_TYPE (lhs)))
+ return false;
+
+ if (TREE_CODE (lhs) == COMPONENT_REF
+ && !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1)))
+ return false;
+ /* In the future we might want to use get_base_ref_and_offset to find
+ if there is a field corresponding to the offset and if so, proceed
+ almost like if it was a component ref. */
+ }
+ }
+ return true;
+}
+
+/* If STMT can be proved to be an assignment to the virtual method table
+ pointer of ANALYZED_OBJ and the type associated with the new table
+ identified, return the type. Otherwise return NULL_TREE. */
+
+static tree
+extr_type_from_vtbl_ptr_store (gimple stmt, struct type_change_info *tci)
+{
+ HOST_WIDE_INT offset, size, max_size;
+ tree lhs, rhs, base;
+
+ if (!gimple_assign_single_p (stmt))
+ return NULL_TREE;
+
+ lhs = gimple_assign_lhs (stmt);
+ rhs = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (lhs) != COMPONENT_REF
+ || !DECL_VIRTUAL_P (TREE_OPERAND (lhs, 1))
+ || TREE_CODE (rhs) != ADDR_EXPR)
+ return NULL_TREE;
+ rhs = get_base_address (TREE_OPERAND (rhs, 0));
+ if (!rhs
+ || TREE_CODE (rhs) != VAR_DECL
+ || !DECL_VIRTUAL_P (rhs))
+ return NULL_TREE;
+
+ base = get_ref_base_and_extent (lhs, &offset, &size, &max_size);
+ if (offset != tci->offset
+ || size != POINTER_SIZE
+ || max_size != POINTER_SIZE)
+ return NULL_TREE;
+ if (TREE_CODE (base) == MEM_REF)
+ {
+ if (TREE_CODE (tci->object) != MEM_REF
+ || TREE_OPERAND (tci->object, 0) != TREE_OPERAND (base, 0)
+ || !tree_int_cst_equal (TREE_OPERAND (tci->object, 1),
+ TREE_OPERAND (base, 1)))
+ return NULL_TREE;
+ }
+ else if (tci->object != base)
+ return NULL_TREE;
+
+ return DECL_CONTEXT (rhs);
+}
+
+/* Callback of walk_aliased_vdefs and a helper function for
+ detect_type_change to check whether a particular statement may modify
+ the virtual table pointer, and if possible also determine the new type of
+ the (sub-)object. It stores its result into DATA, which points to a
+ type_change_info structure. */
+
+static bool
+check_stmt_for_type_change (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef, void *data)
+{
+ gimple stmt = SSA_NAME_DEF_STMT (vdef);
+ struct type_change_info *tci = (struct type_change_info *) data;
+
+ if (stmt_may_be_vtbl_ptr_store (stmt))
+ {
+ tree type;
+ type = extr_type_from_vtbl_ptr_store (stmt, tci);
+ if (tci->type_maybe_changed
+ && type != tci->known_current_type)
+ tci->multiple_types_encountered = true;
+ tci->known_current_type = type;
+ tci->type_maybe_changed = true;
+ return true;
+ }
+ else
+ return false;
+}
+
+
+
+/* Like detect_type_change but with extra argument COMP_TYPE which will become
+ the component type part of new JFUNC of dynamic type change is detected and
+ the new base type is identified. */
+
+static bool
+detect_type_change_1 (tree arg, tree base, tree comp_type, gimple call,
+ struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+{
+ struct type_change_info tci;
+ ao_ref ao;
+
+ gcc_checking_assert (DECL_P (arg)
+ || TREE_CODE (arg) == MEM_REF
+ || handled_component_p (arg));
+ /* Const calls cannot call virtual methods through VMT and so type changes do
+ not matter. */
+ if (!flag_devirtualize || !gimple_vuse (call))
+ return false;
+
+ ao_ref_init (&ao, arg);
+ ao.base = base;
+ ao.offset = offset;
+ ao.size = POINTER_SIZE;
+ ao.max_size = ao.size;
+
+ tci.offset = offset;
+ tci.object = get_base_address (arg);
+ tci.known_current_type = NULL_TREE;
+ tci.type_maybe_changed = false;
+ tci.multiple_types_encountered = false;
+
+ walk_aliased_vdefs (&ao, gimple_vuse (call), check_stmt_for_type_change,
+ &tci, NULL);
+ if (!tci.type_maybe_changed)
+ return false;
+
+ if (!tci.known_current_type
+ || tci.multiple_types_encountered
+ || offset != 0)
+ jfunc->type = IPA_JF_UNKNOWN;
+ else
+ ipa_set_jf_known_type (jfunc, 0, tci.known_current_type, comp_type);
+
+ return true;
+}
+
+/* Detect whether the dynamic type of ARG has changed (before callsite CALL) by
+ looking for assignments to its virtual table pointer. If it is, return true
+ and fill in the jump function JFUNC with relevant type information or set it
+ to unknown. ARG is the object itself (not a pointer to it, unless
+ dereferenced). BASE is the base of the memory access as returned by
+ get_ref_base_and_extent, as is the offset. */
+
+static bool
+detect_type_change (tree arg, tree base, gimple call,
+ struct ipa_jump_func *jfunc, HOST_WIDE_INT offset)
+{
+ return detect_type_change_1 (arg, base, TREE_TYPE (arg), call, jfunc, offset);
+}
+
+/* Like detect_type_change but ARG is supposed to be a non-dereferenced pointer
+ SSA name (its dereference will become the base and the offset is assumed to
+ be zero). */
+
+static bool
+detect_type_change_ssa (tree arg, gimple call, struct ipa_jump_func *jfunc)
+{
+ tree comp_type;
+
+ gcc_checking_assert (TREE_CODE (arg) == SSA_NAME);
+ if (!flag_devirtualize
+ || !POINTER_TYPE_P (TREE_TYPE (arg))
+ || TREE_CODE (TREE_TYPE (TREE_TYPE (arg))) != RECORD_TYPE)
+ return false;
+
+ comp_type = TREE_TYPE (TREE_TYPE (arg));
+ arg = build2 (MEM_REF, ptr_type_node, arg,
+ build_int_cst (ptr_type_node, 0));
+
+ return detect_type_change_1 (arg, arg, comp_type, call, jfunc, 0);
+}
+
+/* Callback of walk_aliased_vdefs. Flags that it has been invoked to the
+ boolean variable pointed to by DATA. */
+
+static bool
+mark_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
+ void *data)
+{
+ bool *b = (bool *) data;
+ *b = true;
+ return true;
+}
+
+/* Return true if a load from a formal parameter PARM_LOAD is known to retreive
+ a value known not to be modified in this function before reaching the
+ statement STMT. PARM_AINFO is a pointer to a structure containing temporary
+ information about the parameter. */
+
+static bool
+parm_preserved_before_stmt_p (struct param_analysis_info *parm_ainfo,
+ gimple stmt, tree parm_load)
+{
+ bool modified = false;
+ bitmap *visited_stmts;
+ ao_ref refd;
+
+ if (parm_ainfo && parm_ainfo->parm_modified)
+ return false;
+
+ gcc_checking_assert (gimple_vuse (stmt) != NULL_TREE);
+ ao_ref_init (&refd, parm_load);
+ /* We can cache visited statements only when parm_ainfo is available and when
+ we are looking at a naked load of the whole parameter. */
+ if (!parm_ainfo || TREE_CODE (parm_load) != PARM_DECL)
+ visited_stmts = NULL;
+ else
+ visited_stmts = &parm_ainfo->parm_visited_statements;
+ walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified,
+ visited_stmts);
+ if (parm_ainfo && modified)
+ parm_ainfo->parm_modified = true;
+ return !modified;
+}
+
+/* If STMT is an assignment that loads a value from an parameter declaration,
+ return the index of the parameter in ipa_node_params which has not been
+ modified. Otherwise return -1. */
+
+static int
+load_from_unmodified_param (vec<ipa_param_descriptor_t> descriptors,
+ struct param_analysis_info *parms_ainfo,
+ gimple stmt)
+{
+ int index;
+ tree op1;
+
+ if (!gimple_assign_single_p (stmt))
+ return -1;
+
+ op1 = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (op1) != PARM_DECL)
+ return -1;
+
+ index = ipa_get_param_decl_index_1 (descriptors, op1);
+ if (index < 0
+ || !parm_preserved_before_stmt_p (parms_ainfo ? &parms_ainfo[index]
+ : NULL, stmt, op1))
+ return -1;
+
+ return index;
+}
+
+/* Return true if memory reference REF loads data that are known to be
+ unmodified in this function before reaching statement STMT. PARM_AINFO, if
+ non-NULL, is a pointer to a structure containing temporary information about
+ PARM. */
+
+static bool
+parm_ref_data_preserved_p (struct param_analysis_info *parm_ainfo,
+ gimple stmt, tree ref)
+{
+ bool modified = false;
+ ao_ref refd;
+
+ gcc_checking_assert (gimple_vuse (stmt));
+ if (parm_ainfo && parm_ainfo->ref_modified)
+ return false;
+
+ ao_ref_init (&refd, ref);
+ walk_aliased_vdefs (&refd, gimple_vuse (stmt), mark_modified, &modified,
+ NULL);
+ if (parm_ainfo && modified)
+ parm_ainfo->ref_modified = true;
+ return !modified;
+}
+
+/* Return true if the data pointed to by PARM is known to be unmodified in this
+ function before reaching call statement CALL into which it is passed.
+ PARM_AINFO is a pointer to a structure containing temporary information
+ about PARM. */
+
+static bool
+parm_ref_data_pass_through_p (struct param_analysis_info *parm_ainfo,
+ gimple call, tree parm)
+{
+ bool modified = false;
+ ao_ref refd;
+
+ /* It's unnecessary to calculate anything about memory contnets for a const
+ function because it is not goin to use it. But do not cache the result
+ either. Also, no such calculations for non-pointers. */
+ if (!gimple_vuse (call)
+ || !POINTER_TYPE_P (TREE_TYPE (parm)))
+ return false;
+
+ if (parm_ainfo->pt_modified)
+ return false;
+
+ ao_ref_init_from_ptr_and_size (&refd, parm, NULL_TREE);
+ walk_aliased_vdefs (&refd, gimple_vuse (call), mark_modified, &modified,
+ parm_ainfo ? &parm_ainfo->pt_visited_statements : NULL);
+ if (modified)
+ parm_ainfo->pt_modified = true;
+ return !modified;
+}
+
+/* Return true if we can prove that OP is a memory reference loading unmodified
+ data from an aggregate passed as a parameter and if the aggregate is passed
+ by reference, that the alias type of the load corresponds to the type of the
+ formal parameter (so that we can rely on this type for TBAA in callers).
+ INFO and PARMS_AINFO describe parameters of the current function (but the
+ latter can be NULL), STMT is the load statement. If function returns true,
+ *INDEX_P, *OFFSET_P and *BY_REF is filled with the parameter index, offset
+ within the aggregate and whether it is a load from a value passed by
+ reference respectively. */
+
+static bool
+ipa_load_from_parm_agg_1 (vec<ipa_param_descriptor_t> descriptors,
+ struct param_analysis_info *parms_ainfo, gimple stmt,
+ tree op, int *index_p, HOST_WIDE_INT *offset_p,
+ bool *by_ref_p)
+{
+ int index;
+ HOST_WIDE_INT size, max_size;
+ tree base = get_ref_base_and_extent (op, offset_p, &size, &max_size);
+
+ if (max_size == -1 || max_size != size || *offset_p < 0)
+ return false;
+
+ if (DECL_P (base))
+ {
+ int index = ipa_get_param_decl_index_1 (descriptors, base);
+ if (index >= 0
+ && parm_preserved_before_stmt_p (parms_ainfo ? &parms_ainfo[index]
+ : NULL, stmt, op))
+ {
+ *index_p = index;
+ *by_ref_p = false;
+ return true;
+ }
+ return false;
+ }
+
+ if (TREE_CODE (base) != MEM_REF
+ || TREE_CODE (TREE_OPERAND (base, 0)) != SSA_NAME
+ || !integer_zerop (TREE_OPERAND (base, 1)))
+ return false;
+
+ if (SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (base, 0)))
+ {
+ tree parm = SSA_NAME_VAR (TREE_OPERAND (base, 0));
+ index = ipa_get_param_decl_index_1 (descriptors, parm);
+ }
+ else
+ {
+ /* This branch catches situations where a pointer parameter is not a
+ gimple register, for example:
+
+ void hip7(S*) (struct S * p)
+ {
+ void (*<T2e4>) (struct S *) D.1867;
+ struct S * p.1;
+
+ <bb 2>:
+ p.1_1 = p;
+ D.1867_2 = p.1_1->f;
+ D.1867_2 ();
+ gdp = &p;
+ */
+
+ gimple def = SSA_NAME_DEF_STMT (TREE_OPERAND (base, 0));
+ index = load_from_unmodified_param (descriptors, parms_ainfo, def);
+ }
+
+ if (index >= 0
+ && parm_ref_data_preserved_p (parms_ainfo ? &parms_ainfo[index] : NULL,
+ stmt, op))
+ {
+ *index_p = index;
+ *by_ref_p = true;
+ return true;
+ }
+ return false;
+}
+
+/* Just like the previous function, just without the param_analysis_info
+ pointer, for users outside of this file. */
+
+bool
+ipa_load_from_parm_agg (struct ipa_node_params *info, gimple stmt,
+ tree op, int *index_p, HOST_WIDE_INT *offset_p,
+ bool *by_ref_p)
+{
+ return ipa_load_from_parm_agg_1 (info->descriptors, NULL, stmt, op, index_p,
+ offset_p, by_ref_p);
+}
+