Re: Type inheritance graph analysis & speculative devirtualization, part 2/6 (type inheritance graph builder)

[Dodji Seketeli <dodji at seketeli dot org>]

Hello Jan,

Just some casual notes.

Jan Hubicka <hubicka@ucw.cz> a Ãcrit:

[...]

> Index: ipa-devirt.c
> ===================================================================

[...]

> +/* Brief vocalburary:

[...]

> +     OTR = OBJ_TYPE_REF
> +       This is Gimple representation of type information of a polymorphic call.
                 ^
Maybe insert a "the" here?

> +       It contains two parameters:
> +	 otr_type is a type of class whose method is called.
> +	 otr_token is index into virtual table where address is taken.

Likewise.

> +
> +     BINFO
> +       This is the type inheritance information attached to each tree
> +       RECORD_TYPE by the C++ frotend.  It provides information about base
> +       types and virtual tables.
> +
> +       BINFO is linked to the RECORD_TYPE by TYPE_BINFO.
> +       BINFO also links to its type by BINFO_TYPE and to the virtual table by
> +       BINFO_VTABLE.
> +
> +       Base types of a given type are enumerated by BINFO_BASE_BINFO
> +       vector.  Members of this vectors are not BINFOs associated
> +       with a base type.  Rather they are new copies of BINFOs
> +       (base BINFOs). Their virtual tables may differ from
> +       virtual table of the base type.  Also BINFO_OFFSET specify
                                                             ^^^^^^^
specifies.

> +       offset of the base within the type.
         ^
Maybe insert a "the" here?

> +
> +       In the case of single inheritance, the virtual table is shared
> +       and BINFO_VTABLE of base BINFO is NULL.  In the case of multiple
> +       inheritance the individual virtual tables are pointer to by
> +       BINFO_VTABLE of base binfos (that differs of BINFO_VTABLE of 
> +       binfo associated to the base type).
> +
> +       BINFO lookup for a given base type and offset can be done by
> +       get_binfo_at_offset.  It returns proper BINFO whose virtual table
> +       can be used for lookup of virtual methods associated with the
> +       base type.
> +
> +     token
> +       This is an index of virtual method in virtual table associated
> +       to the type defining it. Token can be looked up from OBJ_TYPE_REF
> +       or from DECL_VINDEX of given virtual table.
                                ^
Maybe insert a 'a' here?

> +
> +     polymorphic (indirect) call
> +       This is callgraph represention of virtual method call.  Every
> +       polymorphic call contains otr_type and otr_token taken from
> +       original OBJ_TYPE_REF at callgraph construction time.
> +
> +   What we do here:
> +
> +   build_type_inheritance_graph triggers a construction of the type inheritance
> +   graph.
> +
> +     We reconstruct it based on types of methods we see in the unit.
> +     This means that the graph is not complete. Types with no methods are not
> +     inserted to the graph.  Also types without virtual methods are not
                 ^^
into

> +     represented at all, though it may be easy to add this.
> +  
> +     The inheritance graph is represented as follows:
> +
> +       Vertices are structures odr_type.  Every odr_type may correspond
> +       to one or more tree type nodes that are equivalent by ODR rule.
> +       (the multiple type nodes appear only with linktime optimization)
> +
> +       Edges are repsented by odr_type->base and odr_type->derived_types.
                    ^^^^^^^^^
Typo: represented

> +static inline bool
> +polymorphic_type_binfo_p (tree binfo)
> +{
> +  /* See if BINFO's type has an virtual table associtated with it.  */
> +  return BINFO_VTABLE (TYPE_BINFO (BINFO_TYPE (binfo)));

Just for my education, why not just:

    return BINFO_VTABLE (binfo);
?

At the very least, I'd say there ought to be a comment here explaining
why this "gotcha'.

[...]

Incidentally ...

> +/* See if BINFO's type match OTR_TYPE.  If so, lookup method
> +   in vtable of TYPE_BINFO and insert method to NODES array.
> +   Otherwise recurse to base BINFOs.
> +   This match what get_binfo_at_offset does, but with offset
> +   being unknown.
> +
> +   TYPE_BINFO is binfo holding an virtual table matching
> +   BINFO's type.  In the case of single inheritance, this
> +   is binfo of BINFO's type ancestor (vtable is shared),
> +   otherwise it is binfo of BINFO's type.
> +
> +   MATCHED_VTABLES tracks virtual tables we already did lookup
> +   for virtual function in.
> +  */
> +
> +static void
> +record_binfo (vec <cgraph_node *> &nodes,
> +	      tree binfo,
> +	      tree otr_type,
> +	      tree type_binfo,
> +	      HOST_WIDE_INT otr_token,
> +	      pointer_set_t *inserted,
> +	      pointer_set_t *matched_vtables)
> +{
> +  tree type = BINFO_TYPE (binfo);
> +  int i;
> +  tree base_binfo;
> +
> +  gcc_checking_assert (BINFO_VTABLE (type_binfo));
> +
> +  if (types_same_for_odr (type, otr_type)
> +      && !pointer_set_insert (matched_vtables, BINFO_VTABLE (type_binfo)))
> +    {
> +      tree target = gimple_get_virt_method_for_binfo (otr_token, type_binfo);
> +      if (target)
> +	maybe_record_node (nodes, target, inserted);
> +      return;
> +    }
> +
> +  /* Walk bases.  */
> +  for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
> +    /* Walking bases that have no virtual method is pointless excercise.  */
> +    if (polymorphic_type_binfo_p (base_binfo))
> +      record_binfo (nodes, base_binfo, otr_type,
> +		    BINFO_VTABLE (base_binfo) ? base_binfo : type_binfo,

... here, as polymorphic_type_binfo_p (base_binfo) is true,
shouldn't BINFO_VTABLE(base_info) be unconditionally true as well?


> +		    otr_token, inserted,
> +		    matched_vtables);
> +}

Thanks.

-- 
		Dodji