Lines Matching +full:child +full:- +full:nodes
29 * This file contains routines that merge one tdata_t tree, called the child,
34 * tdata_t structures contain two main elements - a hash of iidesc_t nodes, and
35 * a directed graph of tdesc_t nodes, pointed to by the iidesc_t nodes. Simply
36 * put, we merge the tdesc_t graphs, followed by the iidesc_t nodes, and then we
41 * 1. Mapping iidesc_t nodes
43 * For each child iidesc_t node, we first try to map its tdesc_t subgraph
44 * against the tdesc_t graph in the parent. For each node in the child subgraph
46 * is established. For the child nodes that cannot be mapped onto existing
47 * parent nodes, a mapping is established between the child node ID and a
48 * newly-allocated ID that the node will use when it is re-created in the
49 * parent. These unmappable nodes are added to the md_tdtba (tdesc_t To Be
50 * Added) hash, which tracks nodes that need to be created in the parent.
52 * If all of the nodes in the subgraph for an iidesc_t in the child can be
53 * mapped to existing nodes in the parent, then we can try to map the child
57 * list tracks iidesc_t nodes that are to be created in the parent.
59 * While visiting the tdesc_t nodes, we may discover a forward declaration (a
60 * FORWARD tdesc_t) in the parent that is resolved in the child. That is, there
61 * may be a structure or union definition in the child with the same name as the
65 * definition will use when re-created in the parent.
67 * 2. Creating new tdesc_t nodes (the md_tdtba hash)
69 * We have now attempted to map all tdesc_t nodes from the child into the
70 * parent, and have, in md_tdtba, a hash of all tdesc_t nodes that need to be
72 * through this hash, creating the indicated tdesc_t nodes. For a given tdesc_t
73 * node, conjuring requires two steps - the copying of the common tdesc_t data
74 * (name, type, etc) from the child node, and the creation of links from the
75 * newly-created node to the parent equivalents of other tdesc_t nodes pointed
78 * yet. As such, we can't establish the links from these new nodes into the
79 * parent graph. We therefore conjure them with links to nodes in the *child*
82 * resolved would have its &tdesc_t->t_tdesc added to md_tdtbr.
84 * 3. Creating new iidesc_t nodes (the md_iitba list)
86 * When we have completed step 2, all tdesc_t nodes have been created (or
89 * create all of the iidesc_t nodes, as we can attach the tdesc_t subgraph
93 * 4. Resolving newly-created tdesc_t node links (the md_tdtbr list)
95 * As in step 3, we rely on the fact that all of the tdesc_t nodes have been
98 * pointers point into the child tdesc_t subgraph. We can thus get the target
99 * type ID from the child, look at the ID mapping to determine the desired link
102 * 5. Parent => child forward declaration resolution
106 * re-created in step 2 from the child. Using the md_fdida list, we can locate
131 * re-creation, that do not fit into the tdtraverse() framework. We have our
142 * The workhorse structure of tdata_t merging. Holds all lists of nodes to be
149 alist_t *md_fdida; /* Forward -> Definition ID Association */
150 list_t **md_iitba; /* iidesc_t nodes To Be Added to the parent */
151 hash_t *md_tdtba; /* tdesc_t nodes To Be Added to the parent */
152 list_t **md_tdtbr; /* tdesc_t nodes To Be Remapped */
157 * When we first create a tdata_t from stabs data, we will have duplicate nodes.
158 * Normal merges, however, assume that the child tdata_t is already self-unique,
159 * and for speed reasons do not attempt to self-uniquify. If this flag is set,
160 * the merge algorithm will self-uniquify by avoiding the insertion of
176 * Mapping of child type IDs to parent type IDs
221 intr_t *si = stdp->t_intr; in equiv_intrinsic()
222 intr_t *ti = ttdp->t_intr; in equiv_intrinsic()
224 if (si->intr_type != ti->intr_type || in equiv_intrinsic()
225 si->intr_signed != ti->intr_signed || in equiv_intrinsic()
226 si->intr_offset != ti->intr_offset || in equiv_intrinsic()
227 si->intr_nbits != ti->intr_nbits) in equiv_intrinsic()
230 if (si->intr_type == INTR_INT && in equiv_intrinsic()
231 si->intr_iformat != ti->intr_iformat) in equiv_intrinsic()
233 else if (si->intr_type == INTR_REAL && in equiv_intrinsic()
234 si->intr_fformat != ti->intr_fformat) in equiv_intrinsic()
243 return (equiv_node(stdp->t_tdesc, ttdp->t_tdesc, ed)); in equiv_plain()
249 fndef_t *fn1 = stdp->t_fndef, *fn2 = ttdp->t_fndef; in equiv_function()
252 if (fn1->fn_nargs != fn2->fn_nargs || in equiv_function()
253 fn1->fn_vargs != fn2->fn_vargs) in equiv_function()
256 if (!equiv_node(fn1->fn_ret, fn2->fn_ret, ed)) in equiv_function()
259 for (i = 0; i < (int) fn1->fn_nargs; i++) { in equiv_function()
260 if (!equiv_node(fn1->fn_args[i], fn2->fn_args[i], ed)) in equiv_function()
270 ardef_t *ar1 = stdp->t_ardef, *ar2 = ttdp->t_ardef; in equiv_array()
272 if (!equiv_node(ar1->ad_contents, ar2->ad_contents, ed) || in equiv_array()
273 !equiv_node(ar1->ad_idxtype, ar2->ad_idxtype, ed)) in equiv_array()
276 if (ar1->ad_nelems != ar2->ad_nelems) in equiv_array()
285 mlist_t *ml1 = stdp->t_members, *ml2 = ttdp->t_members; in equiv_su()
288 if (ml1->ml_offset != ml2->ml_offset || in equiv_su()
289 strcmp(ml1->ml_name, ml2->ml_name) != 0 || in equiv_su()
290 ml1->ml_size != ml2->ml_size || in equiv_su()
291 !equiv_node(ml1->ml_type, ml2->ml_type, ed)) in equiv_su()
294 ml1 = ml1->ml_next; in equiv_su()
295 ml2 = ml2->ml_next; in equiv_su()
308 elist_t *el1 = stdp->t_emem; in equiv_enum()
309 elist_t *el2 = ttdp->t_emem; in equiv_enum()
312 if (el1->el_number != el2->el_number || in equiv_enum()
313 strcmp(el1->el_name, el2->el_name) != 0) in equiv_enum()
316 el1 = el1->el_next; in equiv_enum()
317 el2 = el2->el_next; in equiv_enum()
330 /* foul, evil, and very bad - this is a "shouldn't happen" */ in equiv_assert()
339 tdesc_t *defn = (ctdp->t_type == FORWARD ? mtdp : ctdp); in fwd_equiv()
341 return (defn->t_type == STRUCT || defn->t_type == UNION || in fwd_equiv()
342 defn->t_type == ENUM); in fwd_equiv()
351 if (ctdp->t_emark > ed->ed_clear_mark && in equiv_node()
352 mtdp->t_emark > ed->ed_clear_mark) in equiv_node()
353 return (ctdp->t_emark == mtdp->t_emark); in equiv_node()
356 * In normal (non-self-uniquify) mode, we don't want to do equivalency in equiv_node()
358 * has already been established for a given child node, we can simply in equiv_node()
359 * compare the mapping for the child node with the ID of the parent in equiv_node()
360 * node. If we are in self-uniquify mode, then we're comparing two in equiv_node()
361 * subgraphs within the child graph, and thus need to ignore any in equiv_node()
365 if ((mapping = get_mapping(ed->ed_ta, ctdp->t_id)) > 0 && in equiv_node()
366 mapping == mtdp->t_id && !ed->ed_selfuniquify) in equiv_node()
369 if (!streq(ctdp->t_name, mtdp->t_name)) in equiv_node()
372 if (ctdp->t_type != mtdp->t_type) { in equiv_node()
373 if (ctdp->t_type == FORWARD || mtdp->t_type == FORWARD) in equiv_node()
379 ctdp->t_emark = ed->ed_cur_mark; in equiv_node()
380 mtdp->t_emark = ed->ed_cur_mark; in equiv_node()
381 ed->ed_cur_mark++; in equiv_node()
383 if ((equiv = tdesc_ops[ctdp->t_type].equiv) != NULL) in equiv_node()
391 * in lockstep. If a given node is equivalent in both the parent and the child,
395 * If the previously-visited nodes don't have the same emark, then the edges
396 * that brought us to these nodes are not equivalent, and so the check ends.
399 * have not found any inequivalent nodes, then the subgraphs are equivalent.
406 tdesc_t *ctdp = ed->ed_node; in equiv_cb()
408 ed->ed_clear_mark = ed->ed_cur_mark + 1; in equiv_cb()
409 ed->ed_cur_mark = ed->ed_clear_mark + 1; in equiv_cb()
413 ctdp->t_id, ctdp->t_id, mtdp->t_id, mtdp->t_id); in equiv_cb()
414 ed->ed_tgt = mtdp; in equiv_cb()
416 return (-1); in equiv_cb()
428 if (get_mapping(mcd->md_ta, ctdp->t_id) > 0) in map_td_tree_pre()
441 ed.ed_ta = mcd->md_ta; in map_td_tree_post()
442 ed.ed_clear_mark = mcd->md_parent->td_curemark; in map_td_tree_post()
443 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1; in map_td_tree_post()
447 debug(3, "map_td_tree_post on %d <%x> %s\n", ctdp->t_id, ctdp->t_id,tdesc_name(ctdp)); in map_td_tree_post()
449 if (hash_find_iter(mcd->md_parent->td_layouthash, ctdp, in map_td_tree_post()
452 if (ed.ed_tgt->t_type == FORWARD && ctdp->t_type != FORWARD) { in map_td_tree_post()
453 int id = mcd->md_tgt->td_nextid++; in map_td_tree_post()
456 add_mapping(mcd->md_ta, ctdp->t_id, id); in map_td_tree_post()
457 alist_add(mcd->md_fdida, (void *)(ulong_t)ed.ed_tgt, in map_td_tree_post()
459 hash_add(mcd->md_tdtba, ctdp); in map_td_tree_post()
461 add_mapping(mcd->md_ta, ctdp->t_id, ed.ed_tgt->t_id); in map_td_tree_post()
463 } else if (debug_level > 1 && hash_iter(mcd->md_parent->td_idhash, in map_td_tree_post()
471 aborterr("Second pass for %d (%s) == %d\n", ctdp->t_id, in map_td_tree_post()
472 tdesc_name(ctdp), ed.ed_tgt->t_id); in map_td_tree_post()
474 int id = mcd->md_tgt->td_nextid++; in map_td_tree_post()
477 add_mapping(mcd->md_ta, ctdp->t_id, id); in map_td_tree_post()
478 hash_add(mcd->md_tdtba, ctdp); in map_td_tree_post()
481 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1; in map_td_tree_post()
493 ed.ed_ta = mcd->md_ta; in map_td_tree_self_post()
494 ed.ed_clear_mark = mcd->md_parent->td_curemark; in map_td_tree_self_post()
495 ed.ed_cur_mark = mcd->md_parent->td_curemark + 1; in map_td_tree_self_post()
500 if (hash_find_iter(mcd->md_tdtba, ctdp, equiv_cb, &ed) < 0) { in map_td_tree_self_post()
501 debug(3, "Self check found %d <%x> in %d <%x>\n", ctdp->t_id, in map_td_tree_self_post()
502 ctdp->t_id, ed.ed_tgt->t_id, ed.ed_tgt->t_id); in map_td_tree_self_post()
503 add_mapping(mcd->md_ta, ctdp->t_id, in map_td_tree_self_post()
504 get_mapping(mcd->md_ta, ed.ed_tgt->t_id)); in map_td_tree_self_post()
505 } else if (debug_level > 1 && hash_iter(mcd->md_tdtba, in map_td_tree_self_post()
513 aborterr("Self-unique second pass for %d <%x> (%s) == %d <%x>\n", in map_td_tree_self_post()
514 ctdp->t_id, ctdp->t_id, tdesc_name(ctdp), ed.ed_tgt->t_id, in map_td_tree_self_post()
515 ed.ed_tgt->t_id); in map_td_tree_self_post()
517 int id = mcd->md_tgt->td_nextid++; in map_td_tree_self_post()
520 add_mapping(mcd->md_ta, ctdp->t_id, id); in map_td_tree_self_post()
521 hash_add(mcd->md_tdtba, ctdp); in map_td_tree_self_post()
524 mcd->md_parent->td_curemark = ed.ed_cur_mark + 1; in map_td_tree_self_post()
581 * Determining equivalence of iidesc_t nodes
592 * Check to see if this iidesc_t (node) - the current one on the list we're
593 * iterating through - matches the target one (iif->iif_template). Return -1
603 if (node->ii_type != iif->iif_template->ii_type || in iidesc_match()
604 !streq(node->ii_name, iif->iif_template->ii_name) || in iidesc_match()
605 node->ii_dtype->t_id != iif->iif_newidx) in iidesc_match()
608 if ((node->ii_type == II_SVAR || node->ii_type == II_SFUN) && in iidesc_match()
609 !streq(node->ii_owner, iif->iif_template->ii_owner)) in iidesc_match()
612 if (node->ii_nargs != iif->iif_template->ii_nargs) in iidesc_match()
615 for (i = 0; i < node->ii_nargs; i++) { in iidesc_match()
616 if (get_mapping(iif->iif_ta, in iidesc_match()
617 iif->iif_template->ii_args[i]->t_id) != in iidesc_match()
618 node->ii_args[i]->t_id) in iidesc_match()
622 if (iif->iif_refmerge) { in iidesc_match()
623 switch (iif->iif_template->ii_type) { in iidesc_match()
629 iif->iif_template->ii_type, in iidesc_match()
630 iif->iif_template->ii_name, in iidesc_match()
631 (iif->iif_template->ii_owner ? in iidesc_match()
632 iif->iif_template->ii_owner : "NULL")); in iidesc_match()
642 return (-1); in iidesc_match()
653 post = (mcd->md_flags & MCD_F_SELFUNIQUIFY ? map_self_post : map_post); in merge_type_cb()
655 /* Map the tdesc nodes */ in merge_type_cb()
656 (void) iitraverse(sii, &mcd->md_parent->td_curvgen, NULL, map_pre, post, in merge_type_cb()
659 /* Map the iidesc nodes */ in merge_type_cb()
661 iif.iif_ta = mcd->md_ta; in merge_type_cb()
662 iif.iif_newidx = get_mapping(mcd->md_ta, sii->ii_dtype->t_id); in merge_type_cb()
663 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE); in merge_type_cb()
665 if (hash_match(mcd->md_parent->td_iihash, sii, iidesc_match, in merge_type_cb()
670 debug(3, "tba %s (%d)\n", (sii->ii_name ? sii->ii_name : "(anon)"), in merge_type_cb()
671 sii->ii_type); in merge_type_cb()
673 list_add(mcd->md_iitba, sii); in merge_type_cb()
684 int oldid = oldtgt->t_id; in remap_node()
691 if ((template.t_id = get_mapping(mcd->md_ta, oldid)) == 0) in remap_node()
694 if (!hash_find(mcd->md_parent->td_idhash, (void *)&template, in remap_node()
695 (void *)&tgt) && (!(mcd->md_flags & MCD_F_REFMERGE) || in remap_node()
696 !hash_find(mcd->md_tgt->td_idhash, (void *)&template, in remap_node()
701 list_add(mcd->md_tdtbr, tgtp); in remap_node()
714 new->t_name = old->t_name ? xstrdup(old->t_name) : NULL; in conjure_template()
715 new->t_type = old->t_type; in conjure_template()
716 new->t_size = old->t_size; in conjure_template()
717 new->t_id = newselfid; in conjure_template()
718 new->t_flags = old->t_flags; in conjure_template()
729 new->t_intr = xmalloc(sizeof (intr_t)); in conjure_intrinsic()
730 bcopy(old->t_intr, new->t_intr, sizeof (intr_t)); in conjure_intrinsic()
740 (void) remap_node(&new->t_tdesc, old->t_tdesc, old->t_id, new, mcd); in conjure_plain()
750 fndef_t *ofn = old->t_fndef; in conjure_function()
753 (void) remap_node(&nfn->fn_ret, ofn->fn_ret, old->t_id, new, mcd); in conjure_function()
755 nfn->fn_nargs = ofn->fn_nargs; in conjure_function()
756 nfn->fn_vargs = ofn->fn_vargs; in conjure_function()
758 if (nfn->fn_nargs > 0) in conjure_function()
759 nfn->fn_args = xcalloc(sizeof (tdesc_t *) * ofn->fn_nargs); in conjure_function()
761 for (i = 0; i < (int) ofn->fn_nargs; i++) { in conjure_function()
762 (void) remap_node(&nfn->fn_args[i], ofn->fn_args[i], old->t_id, in conjure_function()
766 new->t_fndef = nfn; in conjure_function()
776 ardef_t *oar = old->t_ardef; in conjure_array()
778 (void) remap_node(&nar->ad_contents, oar->ad_contents, old->t_id, new, in conjure_array()
780 (void) remap_node(&nar->ad_idxtype, oar->ad_idxtype, old->t_id, new, in conjure_array()
783 nar->ad_nelems = oar->ad_nelems; in conjure_array()
785 new->t_ardef = nar; in conjure_array()
796 for (omem = old->t_members, nmemp = &new->t_members; in conjure_su()
797 omem; omem = omem->ml_next, nmemp = &((*nmemp)->ml_next)) { in conjure_su()
799 (*nmemp)->ml_offset = omem->ml_offset; in conjure_su()
800 (*nmemp)->ml_size = omem->ml_size; in conjure_su()
801 (*nmemp)->ml_name = xstrdup(omem->ml_name ? omem->ml_name : "empty omem->ml_name"); in conjure_su()
802 (void) remap_node(&((*nmemp)->ml_type), omem->ml_type, in conjure_su()
803 old->t_id, new, mcd); in conjure_su()
817 for (oel = old->t_emem, nelp = &new->t_emem; in conjure_enum()
818 oel; oel = oel->el_next, nelp = &((*nelp)->el_next)) { in conjure_enum()
820 (*nelp)->el_name = xstrdup(oel->el_name); in conjure_enum()
821 (*nelp)->el_number = oel->el_number; in conjure_enum()
834 list_add(&mcd->md_tgt->td_fwdlist, new); in conjure_forward()
853 (void) remap_node(&new->ii_dtype, old->ii_dtype, -1, NULL, mcd); in conjure_iidesc()
854 for (i = 0; i < new->ii_nargs; i++) { in conjure_iidesc()
855 (void) remap_node(&new->ii_args[i], old->ii_args[i], -1, NULL, in conjure_iidesc()
911 if (!hash_find(rmd->rmd_tgt->td_idhash, (void *)&template, in redir_mstr_fwd_cb()
919 alist_add(rmd->rmd_map, (void *)fwd, (void *)defn); in redir_mstr_fwd_cb()
930 rmd.rmd_tgt = mcd->md_tgt; in redir_mstr_fwds()
933 if (alist_iter(mcd->md_fdida, redir_mstr_fwd_cb, &rmd)) { in redir_mstr_fwds()
934 (void) iitraverse_hash(mcd->md_tgt->td_iihash, in redir_mstr_fwds()
935 &mcd->md_tgt->td_curvgen, fwd_redir_cbs, NULL, NULL, map); in redir_mstr_fwds()
950 newidx = get_mapping(mcd->md_ta, tba->ii_dtype->t_id); in add_iitba_cb()
951 assert(newidx != -1); in add_iitba_cb()
953 (void) list_remove(mcd->md_iitba, data, NULL, NULL); in add_iitba_cb()
956 iif.iif_ta = mcd->md_ta; in add_iitba_cb()
958 iif.iif_refmerge = (mcd->md_flags & MCD_F_REFMERGE); in add_iitba_cb()
960 if (hash_match(mcd->md_parent->td_iihash, tba, iidesc_match, in add_iitba_cb()
963 (tba->ii_name ? tba->ii_name : "(anon)")); in add_iitba_cb()
968 hash_add(mcd->md_tgt->td_iihash, new); in add_iitba_cb()
980 assert(hash_find(mcd->md_parent->td_idhash, in add_tdesc()
984 oldtdp->t_type, tdesc_name(oldtdp), oldtdp->t_id, in add_tdesc()
985 oldtdp->t_id, newid, newid); in add_tdesc()
987 if ((newtdp = tdesc_ops[oldtdp->t_type].conjure(oldtdp, newid, in add_tdesc()
994 hash_add(mcd->md_tgt->td_idhash, newtdp); in add_tdesc()
995 hash_add(mcd->md_tgt->td_layouthash, newtdp); in add_tdesc()
1008 newid = get_mapping(mcd->md_ta, tdp->t_id); in add_tdtba_cb()
1009 assert(newid != -1); in add_tdtba_cb()
1012 hash_remove(mcd->md_tdtba, (void *)tdp); in add_tdtba_cb()
1023 debug(3, "Remapping %s (%d)\n", tdesc_name(*tdpp), (*tdpp)->t_id); in add_tdtbr_cb()
1025 if (!remap_node(tdpp, *tdpp, -1, NULL, mcd)) in add_tdtbr_cb()
1028 (void) list_remove(mcd->md_tdtbr, (void *)tdpp, NULL, NULL); in add_tdtbr_cb()
1039 mcd->md_iitba = &iitba; in merge_types()
1040 mcd->md_tdtba = hash_new(TDATA_LAYOUT_HASH_SIZE, tdesc_layouthash, in merge_types()
1042 mcd->md_tdtbr = &tdtbr; in merge_types()
1046 tdrc = hash_iter(mcd->md_tdtba, add_tdtba_cb, mcd); in merge_types()
1049 iirc = list_iter(*mcd->md_iitba, add_iitba_cb, mcd); in merge_types()
1052 assert(list_count(*mcd->md_iitba) == 0 && in merge_types()
1053 hash_count(mcd->md_tdtba) == 0); in merge_types()
1055 tdrc = list_iter(*mcd->md_tdtbr, add_tdtbr_cb, mcd); in merge_types()
1058 if (list_count(*mcd->md_tdtbr) != 0) in merge_types()
1059 aborterr("Couldn't remap all nodes\n"); in merge_types()
1063 * definitions for those forwards in mcd->md_fdida. By this point, in merge_types()
1069 if (mcd->md_parent == mcd->md_tgt) { in merge_types()
1079 cur->td_ref++; in merge_into_master()
1080 mstr->td_ref++; in merge_into_master()
1082 tgt->td_ref++; in merge_into_master()
1084 assert(cur->td_ref == 1 && mstr->td_ref == 1 && in merge_into_master()
1085 (tgt == NULL || tgt->td_ref == 1)); in merge_into_master()
1098 mstr->td_curvgen = MAX(mstr->td_curvgen, cur->td_curvgen); in merge_into_master()
1099 mstr->td_curemark = MAX(mstr->td_curemark, cur->td_curemark); in merge_into_master()
1101 merge_types(cur->td_iihash, &mcd); in merge_into_master()
1107 hash_stats(mcd.md_tgt->td_layouthash, 1); in merge_into_master()
1113 cur->td_ref--; in merge_into_master()
1114 mstr->td_ref--; in merge_into_master()
1116 tgt->td_ref--; in merge_into_master()