/* Copyright (C) 1986 by David R. Chase, Rice University, Houston, Texas, U.S.A. All rights reserved. This code may be freely used and distributed if this copyright notice is maintained. */ # include # include # include /* # include # include # include */ # include # include "util.h" # include "strings.h" # include "gmap.h" # include "tree.h" # include "bv.h" # include "maps.h" # include "table.h" # include "tpmg.h" /***** READ THIS CODE CAREFULLY BEFORE MODIFYING IT *****/ /* It has been somewhat speed-hacked */ /* N.B. the unrolled loops in "bv.c" give the VMS C compiler distress */ /* Since they are legal C, and I don't use VMS, I left them in */ /* Forward declarations. C sucks. */ extern UINT add(); extern UINT build_r_map(); extern void dump_i_maps(FILE * fd); extern void dump_c_tables(FILE * fd); /* A note on terminology. A "table" is a matrix of arbitrary dimension. These are usually accessed through recursive routines. */ GMAP pf_map; UINT pf_size; /* PF_MAP is a "map" used with t_map that associates trees to consecutive integers. The smallest integer associated with a tree is 1; the largest is PF_SIZE (PF_SIZE = t_map_size(PF_MAP) for most of the program, but is stored here to save time). All bit vectors used in this program (PATTERNS, and AI_INFO[A][I]->PAI, and those stored in the bit vector maps MATCHING_SETS and AI_INFO[A][I]->SAI) are indexed by the integers from THIS map. Not surprisingly, the performance of operations on this map is important to the performance of the whole program. [Less true now] PF_MAP contains (associates to integers) the target pattern trees, plus all of the subtrees of trees contained in PF_MAP. The set of trees associated by PF_MAP is known as PF (though no variable PF appears in this program). */ UINT * heights; UINT current_height = 0; /* HEIGHTS is an array indexed by PF_MAP's integers giving the height of each pattern in PF. CURRENT_HEIGHT is equal to the (maximum) height of the patterns found in the matching sets being built on each major iteration of the loop. Its initial value is zero, and the increment is done BEFORE the loop. */ UINT max_pattern; UINT max_wildcard_index; BV * wc_subsumers; UINT * wc_trees; /* MAX_PATTERN is the highest index in PF_MAP associated with an "interesting" pattern; i.e, one of the target patterns that the matcher should identify. */ TREE matchall_tree; UINT matchall_index; /* WILDCARD is the match-anything pattern (a leaf). By convention, it is a tree with label zero. WILDCARD_INDEX is WILDCARD's index in PF_MAP (0 if it does not appear). */ BV matchall, add_scratch, candidate; /* MATCHALL is the bit vector containing the match-anything pattern. The only 1 in the bit vector corresponds to WILDCARD_INDEX (if that is non-zero). If the wildcard index is zero, then this set is empty. ADD_SCRATCH is a bit vector pre-allocated for used in add(). This avoids many many allocations and save a significant amount of time. CANDIDATE is the candidate matching set created by the action of sprod_iter and (potentially) added in make_set_product. It is also pre- allocated for efficiency. */ VMAP matching_sets; /* MATCHING_SETS is a map associating bit vectors with integers. The first integer so associated is 1. This map grows as more matching sets are discovered. Each bit vector represents a set of trees contained in PF. Performance of bit vector operations is critical to the speed of this algorithm. */ LS ** ai_info; /* An object of type LS contains information about the I'th children of nodes labelled 'a'. AI_INFO[A][I] contains all this information; other instances of such objects exist only as an optimization. A and I are indexed starting at 0. The PAI field is a bit vector, where PAI[J] = 1 if and only if the tree corresponding to J appears as the I'th child of some node labelled 'a' in PF_MAP. PAI_ELTS is a pointer to a vector of integers. These integers are indices into PF_MAP, and are used (along with QM_A) as part of a speed hack by which indices of "constructed trees" are computed via table lookup (without building any trees). This informatino is also contained in PAI, but it is more quickly accessed here. SAI is a map of bitvectors. Each bitvector in SAI corresponds to the representor set of an equivalence class of members of MATCHING_SETS; two matching sets (members of MATCHING_SETS) are equivalent if they are equal when intersected with PAI. The representor of this equivalence class is just the value of the intersection. This information is crucial to the asymptotic performance of the algorithm. If two matching sets are equivalent with respect to PAI, then they are equivalent as sources of children of nodes in any new matching set. (Note that any matching set must be contained in PF; thus any member of a matching set must be a member of PF, and (assuming that the topmost non-wildcard pattern trees are labelled 'a') the I'th child of any pattern tree in the matching set MUST be in AI_INFO[A][I]->PAI.) Given these equivalence classes, much smaller tables can be constructed if they are indexed by the (integers corresponding to) the equivalence classes of matching sets instead of by the matching sets themselves. DONE tells how much of the table for label A has been constructed in the I index. PENDING tells how much work remains to be done. The table has been constructed through DONE, and further construction is needed at least through PENDING. Since the table is indexed by the integers from the SAI association, more work may appear. Note also that the coordinates specified by AI_INFO[A][*]->DONE,PENDING specify the corners of two hypercubes within the table (in practice, these cubes are usually segments, squares, and occassionally cubes, but the algorithm is implemented with full time-wasting generality). The cube specified by ...[*]->DONE contains filled-in table entries; the cube ...[*]->PENDING specifies the currently known extent of the table, though entries contained in the PENDING cube but not in the DONE cube must still be filled in. PENDING and DONE are updated by the function change(); the old PENDING dimensions become DONE, and the current size of SAI becomes the PENDING size. HEIGHT is the height of the tallest pattern in PAI. This is used to regulate table growth. PADDING1 is used to be sure that the array addressing is easy (one shift). */ LS * ai_raw; UINT ai_raw_count; /* These are used in an optimization to improve the speed of things. Many of the entries in ai_info are SHARED (if PAI are equal). This is the actual list of them. */ typedef union qm { union qm * q; UINT i; } QM; QM * qm_a; /* QM_A is an array indexed by LABEL (say L). Each entry (an object of type QM) is another multi-dimensional table (dimension determined by the arity of the corresponding label) indexed by integers returned from t_map (integers in the range of pf_map). Each entry in the table returns an index from tree_map that corresponds to the tree built with label L and children correspnding to the corresponding to the coordinates of the entry. This is a BIG speed hack. It turns out that the coordinates of the entry are the indices in PAI (see above) rather than in PF_MAP. This compresses the tables a bit (and saves time later). */ TABLE * theta_a; /* THETA_A is an automatically expanding table (accessed by tab_put() and tab_get()) that contains the tables built to drive a bottom-up tree pattern matcher. THETA_A is indexed by tree labels; each label has a corresponding table of the same dimension as the label's arity. */ COORD v1, vi, vn; /* V1, VI, and VN are coordinates into the THETA_A[A] tables. The I'th component of a coordinate corresponds to bit vectors (sets of patterns) (equivalence class representors) contain in AI_INFO[A][I]->SAI. V1 and VN give bounds, and VI indexes between the bounds (see DONE and PENDING above). */ LABEL a; /* A is a global variable containing the current label. This changes only at a high level, and placing it in a global cuts down on the number of parameters to frequently called subroutines. */ UINT dimension; /* DIMENSION is a global variable containing the arity of the current label. This changes along with a, and placing it in a global cuts down on the number of parameters to frequently called subroutines. */ GMAP string_map; int option_build = 0; int option_bench = 0; int option_quiet = 0; int option_noisy = 0; int option_labels = 0; int option_pf = 0; int option_pai = 0; int option_ms = 0; int option_mss = 0; int option_rs = 0; int option_index = 0; int option_tables = 0; int option_dump_i_maps = 0; int option_dump_c_tables = 0; int option_stats = 0; int option_rows = 50; int option_columns = 20; int option_wildsets = 0; int input_file; FILE * output_file; char *bogus_argv[] = {"","?"}; VOID options(argc,argv) char ** argv; { int i; if (argc == 1) { /* No options */ argv = bogus_argv; argc = 2; } input_file = 0; /* standard input */ output_file = stdout; /* standard output */ for (i = 1; i < argc; i++) { if (strcmp(argv[i], "labels")==0) { option_labels = 1; } else if (strcmp(argv[i], "build")==0) { option_build = 1; } else if (strcmp(argv[i], "bench")==0) { option_bench = 1; } else if (strcmp(argv[i], "pf")==0) { option_pf = 1; } else if (strcmp(argv[i], "pai")==0) { option_pai = 1; } else if (strcmp(argv[i], "ms")==0) { option_ms = 1; } else if (strcmp(argv[i], "mss")==0) { option_mss = 1; } else if (strcmp(argv[i], "rs")==0) { option_rs = 1; } else if (strcmp(argv[i], "index")==0) { option_index = 1; } else if (strcmp(argv[i], "tables")==0) { option_tables = 1; } else if (strcmp(argv[i], "dim")==0) { option_dump_i_maps = 1; } else if (strcmp(argv[i], "dct")==0) { option_dump_c_tables = 1; } else if (strcmp(argv[i], "stats")==0) { option_stats = 1; } else if (strcmp(argv[i], "wildsets")==0) { option_wildsets = 1; } else if (strcmp(argv[i], "quiet")==0) { option_quiet = 1; } else if (strcmp(argv[i], "noisy")==0) { option_noisy = 1; } else if (strcmp(argv[i], "rows")==0) { sscanf(argv[++i], "%d",&option_rows); } else if (strcmp(argv[i], "columns")==0) { sscanf(argv[++i], "%d",&option_columns); } else if (strcmp(argv[i], "input")==0) { input_file = open(argv[++i],O_RDONLY,0); if (input_file < 0) { perror("Couldn't open input file"); exit(666); } } else if (strcmp(argv[i], "output")==0) { output_file = fopen(argv[++i],"w"); if (output_file == NULL) { perror("Couldn't open output file"); exit(666); } } else if (strcmp(argv[i],"help") == 0 || strcmp(argv[i],"?") == 0) { fprintf(stderr,"tpmg version 2.3 (Mon, 1 Oct 90)\n"); fprintf(stderr,"tpmg (options) < input > output\n"); fprintf(stderr,"options accepted:\n"); fprintf(stderr,"labels print node labels\n"); fprintf(stderr,"pf print pattern forest\n"); fprintf(stderr,"pai print subpattern forests\n"); fprintf(stderr,"ms print matching sets\n"); fprintf(stderr,"rs print representer sets\n"); fprintf(stderr,"index print index maps\n"); fprintf(stderr,"tables print compressed tables\n"); fprintf(stderr,"dim dump index maps\n"); fprintf(stderr,"dct dump compressed tables\n"); fprintf(stderr,"stats print statistics\n"); fprintf(stderr,"rows N set rows per page to N\n"); fprintf(stderr,"columns N set columns per page to N\n"); fprintf(stderr,"input FILE use FILE for input\n"); fprintf(stderr,"output FILE use FILE for output\n"); fprintf(stderr,"quiet say little about the program's progress\n"); fprintf(stderr,"help print this message\n"); fprintf(stderr,"? print this message\n"); fprintf(stderr,"Obscure options:\n"); fprintf(stderr,"mss print matching sets w/o wc's added\n"); fprintf(stderr,"wildsets form singleton matching sets for wc's\n"); fprintf(stderr,"build construct index maps internally (for timing purposes)\n"); fprintf(stderr,"bench very terse. Can be used with \'build\' for timing\n"); fprintf(stderr,"noisy say lots about the program's progress\n"); if (argv == bogus_argv) exit(0); } else fprintf(stderr,"Unrecognized option '%s'\n", argv[i]); } } int main(argc, argv) int argc; char ** argv; { UINT i; /* First verify some assertions about the computer on which we run */ if (sizeof(CELL) != sizeof(STRING) || sizeof(CELL) != sizeof(BV) || sizeof(CELL) != sizeof(TREE)) { fprintf(stderr, "This program has been incompletely ported and cannot run on this machine\n"); exit(666); } options(argc,argv); read_file(input_file); string_map = g_new_map(string_hash, string_free, string_copy, string_equal); read_labels(); /* Construct an empty map and an empty bit vector to hold the */ /* pattern map and the bits corresponding to the original */ /* (the structure of this algorithm says that I don't need a */ /* map; just recording the maximum original pattern index is */ /* sufficient. */ pf_map = g_new_map(tree_hash, tree_free, tree_copy, tree_equal); /* This will make it so that the first trees are the wildcards */ /* with numbers the same as their labels */ for (i = 1; i <= max_wildcard_index; i++) { TREE t = tree_new(i); g_map(pf_map,t); tree_free(t); } /* Read the patterns; the format is an integer (number of */ /* patterns) followed by the patterns in standard tree format. */ read_patterns(); /* Add to PF all subtrees of trees in PF (take subtree closure) */ form_subtree_closure(); /* At this point, pf_size is frozen. Do not compute it again. */ pf_size = g_map_size(pf_map); bv_init(pf_size + 1); matchall = bv_new(); add_scratch = bv_new(); candidate = bv_new(); read_wildcards(); /* See if the wildcard node appears in PF */ matchall_index = g_inmap(pf_map, matchall_tree); /* Initialize HEIGHTS */ get_heights(); /* Allocate all of the ai_info entries. Initialize the pai */ /* fields (these will not change) and sai, done, and pending. */ /* Also initialize height */ form_ai_info(); /* Allocate all of the theta_a tables and allocate trees. */ form_theta_a(); /* Build the tables for looking up tree indices. */ form_qm_a(); /* Create the starter set for all other matching sets. (If the */ /* wildcard node appears, then it will be in all sets and this */ /* set will be the singleton set containing the wildcard; if */ /* not, then this set will be empty). */ if (matchall_index != 0) bv_ins(matchall, matchall_index); /* Now create the set of matching sets. To kick-start the */ /* algorithm we need matching sets for all the leaves, so */ /* compute those. */ matching_sets = v_new_map(); form_0_height_matching_sets(); /* allocate coordinate vectors. */ v1 = tab_vect(tree_MAXARITY); vi = tab_vect(tree_MAXARITY); vn = tab_vect(tree_MAXARITY); /* The Big Loop */ while (change()) { /* Change updates the DONE and PENDING fields for AI_INFO, and */ /* return TRUE if any of the SAI grew. */ current_height++; if (!option_quiet && !option_bench) fprintf(output_file, "Beginning iteration to build height %d, # matching sets = %d\n", current_height, v_map_size(matching_sets)); /* This loop defines the GLOBAL a (= current label) */ for (a = 1; a < max_label; a++) if (label_arities[a] > (ARITY) 0) { UINT n = label_arities[a]; UINT i; /* set the GLOBAL dimension */ dimension = n; /* Get the coordinates describing entries to be filled in */ /* the table for A. */ for (i = 0; i < n ; i++) { /* Initialize the bounds of the iteration */ v1[i] = ai_info[a][i] -> done; vn[i] = ai_info[a][i] -> pending; } if (option_noisy) { fprintf(output_file,"label %d ", a); fprintf(output_file,"iterating from "); print_coord(output_file,0,((int) n)-1,v1); fprintf(output_file," to "); print_coord(output_file,0,((int) n)-1,vn); fprintf(output_file,"\n"); } /* Iterate will generate all the table coordinates needing */ /* an entry, and call make_set_product to get the proper */ /* value. */ iterate(n); } } /* At this point, the computing is all done. Now it remains to print. */ /* The previous line is a bit of a lie; certain information is implicit */ /* in the maps and bit vectors computed, and cannot be "just dumped". */ if (option_build) { /* Build the restriction maps, but do not print */ /* This is only for purposes of timing! */ for (i = 0 ; i < ai_raw_count; i++) { LS ai = ai_raw[i]; build_r_map(ai); } } if (option_bench) { fprintf(output_file,"%d patterns, %d matching sets\n", pf_size, v_map_size(matching_sets)); return 0; /* EXIT RIGHT HERE */ } if (option_labels) { fprintf(output_file,"\nLabels and their arities\n"); for (a = 1 ; a < max_label; a++) { fprintf(output_file, "%30s (%3d) %5d\n",(char *) g_unmap(string_map,a),a,label_arities[a]); } } if (option_pf) { fprintf(output_file,"\nThe pattern forest\n"); print_t_map(output_file,pf_map); } if (option_ms) { fprintf(output_file,"\nThe matching sets\n"); print_vo_map(output_file,matching_sets); } if (option_mss) { fprintf(output_file,"\nThe matching sets\n"); print_v_map(output_file,matching_sets); } if (option_dump_i_maps) { dump_i_maps(output_file); } if (option_dump_c_tables) { dump_c_tables(output_file); } if (option_pai || option_rs || option_index || option_tables) /* then */ for (a = max_wildcard_index + 1; a < max_label; a++) { fprintf(output_file,"\nInformation for label %s(%d)\n", (char *) g_unmap(string_map,a),a); for (i = 0; i < label_arities[a]; i++) { LS ai = ai_info[a][i]; fprintf(output_file,"\nInformation for child %d\n", i); if (option_pai) { fprintf(output_file, "\nThe PAI set\n"); print_tree_set(output_file, ai -> pair); } if (option_rs) { fprintf(output_file, "\nThe restricted matching set\n"); print_v_map(output_file,ai->sai); } if (option_index) { fprintf(output_file, "\nThe index map from matching sets to restricted matching sets\n"); print_r_map(output_file,ai); /* construct and print the restrictor map */ } } if (option_tables) { fprintf(output_file, "\nThe compressed table\n"); print_table(output_file, a); } } if (option_stats) { fprintf(output_file, "Statistics\n"); print_stat_info(output_file); } return 0; } /* Here begin a zillion handy-dandy subroutines */ VOID form_subtree_closure() { /* Add to the pf_map all the subtrees of trees in the pf_map */ UINT i; /* note that this loop runs until pf_map quits growing */ for (i = 1; i <= g_map_size(pf_map); i++) { UINT j; TREE t = (TREE) g_unmap(pf_map,i); UINT l = tree_arity(t); for (j = 0; j < l; j++) { g_map(pf_map,KID(t,j)); } } } VOID get_heights() { /* This calls fill_height_table to get the heights of all the patterns */ /* It is somewhat complicated by the presence of wildcard nodes. For a */ /* wildcard, the height is the minimum of the subsuming patterns. For */ /* an ordinary pattern, height is defined in the usual way (1 + max */ /* height of children, leaf height = 0). */ /* Defers helps to cope with wildcards--it is set to -1 for all trees */ /* initially (whose heights may grow), and is set to zero for each tree */ /* that is found to have a completely defined (not deferred) height. */ /* It is also set to zero for each wildcard that is found to be subsumed */ /* by at least one pattern with defined height. (Note that the height */ /* of a wildcard can only shrink, once defined). */ /* At each iteration of the big loop, all the non-wildcard patterns have */ /* deferred set to -1 because their heights may have changed in the */ /* previous iteration's shrinking of wildcard heights. */ UINT i,j; UINT change; heights = (UINT *) MALLOC ((sizeof (UINT)) * (1 + pf_size)); /* wildcard nodes start at infinite height */ for (i = 1; i <= max_wildcard_index; i++) heights[i] = pf_size; /* but the matchall wildcard starts at height zero */ if (matchall_index != 0) heights[matchall_index] = 0; change = 1; while (change) { change = 0; /* Start the real patterns at height 0; it will grow upward */ for (i = max_wildcard_index + 1; i <= pf_size; i++) heights[i] = 0; for (i = 1; i <= pf_size; i++) fill_height_table(i); for (i = 1; i <= max_wildcard_index; i++) { /* Note: pf_size is a max_height */ for (j = 1; j <= pf_size; j++) { if (bv_in(wc_subsumers[i],j) && heights[j] < heights[i]) { change = 1; heights[i] = heights[j]; } } } } } VOID fill_height_table(i) UINT i; { /* This fills in the height table for index i */ /* It may call itself recursively, but it uses the */ /* table in a dynamic programming sort of way. */ TREE t = (TREE) g_unmap(pf_map, i); LABEL a = LBL(t); ARITY l = label_arities[a]; UINT k = 0; UINT s; if (l == 0) return; if (heights[i] > 0) return; for (s = 0; s < l; s++) { UINT j = g_inmap(pf_map,KID(t,s)); fill_height_table(j); if (heights[j] > k) k = heights[j]; } heights[i] = k+1; } BV fill_pai(a,i) LABEL a; ARITY i; { /* For a given a and i, find all patterns appearing as i'th child of node labelled a. This is called by form_ai_info. */ BV pai = bv_new(); UINT j; for (j = 1; j <= pf_size; j++) { TREE t = (TREE) g_unmap(pf_map,j); if (LBL(t) == a) { bv_ins(pai, g_inmap(pf_map, KID(t,i))); } } return pai; } VOID form_ai_info() { /* Allocate and initialize the ai_info structures */ LABEL a; VMAP pai_map = v_new_map(); UINT temp = 0; for (a = 1; a < max_label; a++) { temp = temp + label_arities[a]; } ai_raw = (LS *) MALLOC (temp * sizeof (LS)); ai_raw_count = 0; ai_info = (LS **) MALLOC (max_label * sizeof (LS *)); for (a = 1; a < max_label; a++) { ARITY i; ai_info[a] = (LS *) MALLOC (label_arities[a]*sizeof (LS)); for (i = 0; i < label_arities[a]; i++) { /* Initialize a new label-child structure */ LS ls; BV abv; UINT index; abv = fill_pai(a,i); index = v_map(pai_map, abv); ls = (LS) v_other(pai_map, index).urp; if (ls == 0) { ls = (LS) MALLOC (sizeof *ls); ai_info[a][i] = ls; v_other(pai_map, index).urp = (UINT) ls; ls -> index = ai_raw_count; ai_raw[ai_raw_count++] = ls; ls -> pair = abv; ls -> pai_size = 0; /* Count the number of trees in pai */ { UINT j; for (j = 1; j <= pf_size; j++) if (bv_in(ls -> pair,j)) ls ->pai_size++; } /* Allocate and fill pai_elts. Initialize heights. */ ls -> pai_elts = (UINT *) MALLOC (sizeof(UINT) * ls ->pai_size); { UINT j; UINT k = 0; for (j = 1; j <= pf_size; j++) if (bv_in(ls -> pair,j)) { ls->pai_elts[k++] = j; } } /* allocate the rest */ ls -> sai = v_new_map(); ls -> done = 0; ls -> pending = 0; } else { ai_info[a][i] = ls; } } } } VOID form_theta_a() { /* Create empty tables for pattern matcher */ LABEL l; theta_a = (TABLE *) MALLOC (max_label * sizeof (TABLE)); for (l = 1; l < max_label; l++) { theta_a[l] = tab_new((UINT)label_arities[l]); } } QM form_qm(i,t,a) ARITY i; TREE t; LABEL a;{ /* Called recursively to fill in successive subtables of a QM */ QM q; if (i == 0) { /* If dimension is 0, return the answer */ q.i = g_inmap(pf_map,t); } else { UINT j,k = 0; i--; /* allocate a subtable as big as the i'th dimension for label a */ q.q = (QM *) MALLOC (ai_info[a][i]->pai_size * sizeof (QM)); for (j = 1; j <= pf_size; j++) { if (bv_in(ai_info[a][i]->pair, j)) { /* If j is in this map, then I must unmap it, use it as child, */ /* and recurse. The map entry gets to be the result. */ KID(t,i) = (TREE) g_unmap(pf_map,j); q.q[k] = form_qm(i,t,a); k++; } } } return q; } VOID form_qm_a() { /* Generate the lookup table for label a. */ LABEL l; qm_a = (QM *) MALLOC (max_label * sizeof (QM)); for (l = 1; l < max_label; l++) { qm_a[l] = form_qm(label_arities[l], tree_new(l),l); } } VOID form_0_height_matching_sets() { /* What the name says. */ LABEL l; UINT wci = add(matchall); for (l = 1; l < max_label; l++) { if (label_arities[l] == 0 && (l > max_wildcard_index || (heights[l/* as a tree index */] < pf_size && option_wildsets))) { TREE t = tree_new(l); UINT i = g_inmap(pf_map,t); if (i == 0) theta_a[l] = tab_put(theta_a[l],(COORD) 0,wci); else { bv_assign(matchall,candidate); bv_ins(candidate,i); theta_a[l] = tab_put(theta_a[l],(COORD) 0,add(candidate)); } tree_free(t); } } } UINT add(ms) BV ms; { /* Given a candidate matching set, add it to matching_sets and update the sai as necessary. */ UINT index = v_map_size(matching_sets); UINT i; BV temp; UINT j; v_map(matching_sets,ms); if (index >= v_map_last) return v_map_last; index = v_map_last; /* Add code here to augment the matching set if it is new */ temp = bv_copy(ms); for (j = 1; j <= max_wildcard_index; j++) if (bv_intersects(temp, wc_subsumers[j])) { bv_ins(temp, wc_trees[j]); } v_other(matching_sets,index).bv = temp; /* end of additional code */ /* generate restricted maps */ for (i = 0; i < ai_raw_count; i++) { LS ai = ai_raw[i]; (void) bv_andto(ai->pair, temp, add_scratch); j = v_map(ai->sai,add_scratch); /* If this is a new entry, then create a special representation of add_scratch for use in sprod_iter. */ if (v_other(ai -> sai, j).is == 0) { /* new entry */ UINT size = number_bits_set(add_scratch); UINT * temp_is = (UINT *) MALLOC ((size + 1) * sizeof(UINT)); UINT k,m; UINT * elements = ai -> pai_elts; m = 1; temp_is[0] = size; size = ai -> pai_size; for (k = 0; k < size; k++) { if (bv_in(add_scratch, elements[k])) temp_is[m++] = k; } v_other(ai -> sai, j).is = temp_is; } } return index; } int change() { /* Return TRUE if any of the SAI have changed. Also update done and pending for each */ UINT growth = 0; UINT i; /* Get new values for sai[a][i]->done,pending, see if loop should stop */ for (i = 0; i < ai_raw_count; i++) { LS ai = ai_raw[i]; UINT size = v_map_size(ai->sai); if (size > ai -> pending) growth = 1; ai -> done = ai->pending; ai -> pending = size; } return growth; } /* Here begins the meat of the program. Something like 60 percent of the execution time is spent here. */ static UINT * isvect[tree_MAXARITY]; VOID sprod_iter(i,q) REGISTER ARITY i; REGISTER QM q; { REGISTER UINT j; REGISTER UINT * index_set; REGISTER UINT tree_index; /* This subroutine accounts for the majority of the time spent */ /* computing matching sets. */ if (i == 1) { index_set = isvect[0]; j = index_set[0]; while(j > 0) { tree_index = q.q[index_set[j--]].i; if (tree_index != 0) bv_ins(candidate, tree_index); } } else { i--; index_set = isvect[i]; j = index_set[0]; while(j > 0) { sprod_iter(i,q.q[index_set[j--]]); } } } VOID make_set_product(){ /* Iterate over the cross product of bitvectors (#'s correspond to */ /* trees via pf_map) specified by vi */ register LS * ai_info_a; register UINT i; (void) bv_assign(matchall, candidate); ai_info_a = ai_info[a]; for (i = 0; i < dimension; i++) isvect[i] = v_other(ai_info_a[i]->sai,vi[i]).is; sprod_iter(label_arities[a], qm_a[a]); i = add(candidate); theta_a[a] = tab_put(theta_a[a], vi, i); } VOID iterate(d) register UINT d;{ register UINT i; register COORD addr_of_vi_sub_d_minus_one; d--; addr_of_vi_sub_d_minus_one = vi + d; if (d > 0) { for (i = v1[d]; i > 0; i--) { *addr_of_vi_sub_d_minus_one = i; iterate(d); } for (i = vn[d]; i > v1[d]; i--) { *addr_of_vi_sub_d_minus_one = i; iterate_slab(d); } } else /* d - 1 == 0 */ { for (i = vn[d]; i > v1[d]; i--) { *addr_of_vi_sub_d_minus_one = i; make_set_product(); } } } VOID iterate_slab(d) register UINT d;{ if (d == 0) { make_set_product(); } else { register UINT i; register COORD addr_of_vi_sub_d_minus_one; d--; addr_of_vi_sub_d_minus_one = vi + d; for (i = vn[d]; i > 0; i--) { *addr_of_vi_sub_d_minus_one = i; iterate_slab(d); } } } /* Subroutines to print and interpret information */ VOID print_stat_info(fd) FILE * fd; { UINT i; UINT num_matching_sets = v_map_size(matching_sets); UINT projected_table_elts = 0; UINT projected, this; UINT bytes_for_matching_set = num_matching_sets > 65535 ? 4 : (num_matching_sets > 255 ? 2 : 1); UINT num_transition_bytes = 0; UINT min_index_bytes = 0; UINT num_table_elts = 0; UINT num_restrictor_elts = 0; UINT num_index_bytes = 0; UINT transition_count = 0; /* Print summary information */ fprintf(fd,"%d patterns, %d matching sets\n", pf_size, v_map_size(matching_sets)); for (a = max_wildcard_index + 1; a < max_label; a++) if (label_arities[a] > 0) { projected = 1; this = 1; fprintf(fd,"Table for label %d with arity %d has dimensions ", a, label_arities[a]); for (i = 0; i < label_arities[a]; i++) { UINT dim_size = v_map_size(ai_info[a][i]->sai); projected *= num_matching_sets; this *= dim_size; fprintf(fd,"%d ", dim_size); } projected_table_elts += projected; num_table_elts += this; fprintf (fd,"(%d)", this); fprintf(fd,"\n"); } for (a = max_wildcard_index + 1; a < max_label; a++) { for (i = 0; i < label_arities[a]; i++) { UINT dim_size = v_map_size(ai_info[a][i]->sai); UINT transition_bytes = bytes_for_matching_set * build_r_map(ai_info[a][i]); UINT index_bytes; num_restrictor_elts += num_matching_sets; transition_bytes += dim_size; if (dim_size > 256) transition_bytes += dim_size; if (dim_size > 65536) transition_bytes += 2*dim_size; num_transition_bytes += transition_bytes; if (dim_size > 256) index_bytes = 2 * num_matching_sets ; else if (dim_size > 16) index_bytes = num_matching_sets ; else if (dim_size > 4) index_bytes = (num_matching_sets + 1)/2 ; else if (dim_size > 2) index_bytes = (num_matching_sets + 3)/4 ; else index_bytes = (num_matching_sets + 7)/8 ; num_index_bytes += index_bytes; min_index_bytes += index_bytes < transition_bytes ? index_bytes : transition_bytes; } } fprintf(fd, "Compressed table size = %d\n", num_table_elts); fprintf(fd, "Restrictor map size = %d\n", num_restrictor_elts); fprintf(fd, "Total table size = %d\n", num_restrictor_elts + num_table_elts); fprintf(fd, "Uncompressed table size = %d\n", projected_table_elts); fprintf(fd, "OLD STYLE (POPL \'87)\n"); fprintf(fd, "Comp. (1) map size (bytes) = %d\n", num_index_bytes); fprintf(fd, "Comp. (2) map size (bytes) = %d\n", num_transition_bytes); fprintf(fd, "Comp. (3) map size (bytes) = %d\n", min_index_bytes); num_transition_bytes = 0; min_index_bytes = 0; num_restrictor_elts = 0; num_index_bytes = 0; for (a = max_wildcard_index + 1; a < max_label; a++) { for (i = 0; i < label_arities[a]; i++) { UINT dim_size = v_map_size(ai_info[a][i]->sai); UINT transition_bytes = build_r_map(ai_info[a][i]); UINT index_bytes; num_restrictor_elts += num_matching_sets; if (dim_size <= 255) transition_bytes = transition_bytes * (1 + bytes_for_matching_set); else if (dim_size <= 65535) transition_bytes = transition_bytes * (2 + bytes_for_matching_set); else transition_bytes = transition_bytes * (4 + bytes_for_matching_set); num_transition_bytes += transition_bytes; if (dim_size > 256) index_bytes = 2 * num_matching_sets ; else if (dim_size > 16) index_bytes = num_matching_sets ; else if (dim_size > 4) index_bytes = (num_matching_sets + 1)/2 ; else if (dim_size > 2) index_bytes = (num_matching_sets + 3)/4 ; else index_bytes = (num_matching_sets + 7)/8 ; num_index_bytes += index_bytes; min_index_bytes += index_bytes < transition_bytes ? index_bytes : transition_bytes; } } fprintf(fd, "NEW STYLE (CORRECTED, \'89)\n"); fprintf(fd, "Comp. (1) map size (bytes) = %d\n", num_index_bytes); fprintf(fd, "Comp. (2) map size (bytes) = %d\n", num_transition_bytes); fprintf(fd, "Comp. (3) map size (bytes) = %d\n", min_index_bytes); num_transition_bytes = 0; min_index_bytes = 0; num_restrictor_elts = 0; num_index_bytes = 0; for (i = 0; i < ai_raw_count; i++) { UINT dim_size = v_map_size(ai_raw[i]->sai); UINT t = build_r_map(ai_raw[i]); UINT transition_bytes = t; UINT index_bytes; transition_count += t; num_restrictor_elts += num_matching_sets; if (dim_size <= 255) transition_bytes = transition_bytes * (1 + bytes_for_matching_set); else if (dim_size <= 65535) transition_bytes = transition_bytes * (2 + bytes_for_matching_set); else transition_bytes = transition_bytes * (4 + bytes_for_matching_set); num_transition_bytes += transition_bytes; if (dim_size > 256) index_bytes = 2 * num_matching_sets ; else if (dim_size > 16) index_bytes = num_matching_sets ; else if (dim_size > 4) index_bytes = (num_matching_sets + 1)/2 ; else if (dim_size > 2) index_bytes = (num_matching_sets + 3)/4 ; else index_bytes = (num_matching_sets + 7)/8 ; num_index_bytes += index_bytes; min_index_bytes += index_bytes < transition_bytes ? index_bytes : transition_bytes; } fprintf(fd, "DUPLICATE INDEX MAPS REMOVED ('89)\n"); fprintf(fd, "Restrictor map size = %d\n", num_restrictor_elts); fprintf(fd, "Total table size = %d\n", num_restrictor_elts + num_table_elts); fprintf(fd, "total transition count = %d\n", transition_count); fprintf(fd, "Comp. (1) map size (bytes) = %d\n", num_index_bytes); fprintf(fd, "Comp. (2) map size (bytes) = %d\n", num_transition_bytes); fprintf(fd, "Comp. (3) map size (bytes) = %d\n", min_index_bytes); } UINT build_r_map(ai) REGISTER LS ai; { REGISTER UINT i; REGISTER UINT ms_size = v_map_size(matching_sets); REGISTER BV temp = bv_new(); UINT transitions = 1; REGISTER UINT last; REGISTER UINT next; bv_andto(ai -> pair, v_other(matching_sets,1).bv, temp); last = v_inmap(ai->sai,temp); for (i = 2; i <= ms_size; i++) { bv_andto(ai -> pair, v_other(matching_sets,i).bv, temp); next = v_inmap(ai->sai,temp); if (last != next) { last = next; transitions++; } } return transitions; } void dump_i_maps(FILE * fd) { int i; UINT ms_size = v_map_size(matching_sets); fprintf(fd, "// %d Index maps, each mapping from [1,%d] to a subrange.\n", ai_raw_count, ms_size); fprintf(fd, "// The format of each set is:\n"); fprintf(fd, "// \n"); fprintf(fd, "// = internal index of this index map\n"); fprintf(fd, "// = maximum element in this index map (min is 1)\n"); fprintf(fd, "// = the entries in this map; there will %d of them\n", ms_size); fprintf(fd, "// The map list begins with a count of the number of maps\n"); fprintf(fd, "// and the length of each map.\n"); fprintf(fd, " %d %d\n", ai_raw_count, ms_size); for (i = 0; i < (int) ai_raw_count; i++) { UINT dim_size = v_map_size(ai_raw[i]->sai); BV temp = bv_new(); int j,k; fprintf(fd, " %d %d\n", i, dim_size); for (j = 1; j <= (int) ms_size; j++) { bv_andto(ai_raw[i]->pair, v_other(matching_sets,j).bv, temp); k = v_inmap(ai_raw[i]->sai,temp); fprintf(fd, " %d",k); } fprintf(fd,"\n"); } fprintf(fd, "// End of index maps\n"); } VOID dump_table_internal(FILE * fd, LABEL a, UINT * vi, int i, int n) { if (i == n) { fprintf(fd," %d", tab_get(theta_a[a],vi)); } else { UINT j; for (j = 1; j <= v_map_size(ai_info[a][i]->sai); j++) { vi[i] = j; dump_table_internal(fd,a,vi,i+1,n); } } } VOID dump_table(fd,a) FILE * fd; LABEL a; { int n = (int) label_arities[a]; COORD vi = tab_vect(tree_MAXARITY); dump_table_internal(fd,a,vi,0,n); } void dump_c_tables(FILE * fd) { int table_count = max_label - max_wildcard_index - 1; int a; int i; fprintf(fd, "// %d compressed tables\n", table_count); fprintf(fd, "// The format of each table is:\n"); fprintf(fd, "//