#include "select_alternatives.h" /**********************************************************************/ /* Definitions */ /***************/ char *profile_data_filename = NULL; /**********************************************************************/ /* Code */ /********/ // [....] /**********************************************************************/ boolean qif_constraints_met(CStringSet *sets[], int set_count, CStringSet *on_set) { int loop; for (loop = 0; loop < set_count; loop++) { CStringSet *set = sets[loop]; Pix index; int vars_on = 0; if (set->empty()) continue; /* Bizarre, but we'll call it OK */ index = set->first(); while (index != 0) { char *qif_var = (*set)(index); if (on_set->contains(qif_var)) vars_on++; set->next(index); } if ((set->contains("... NO FINAL QELSE")) && (vars_on == 1)) continue; /* OK so far */ if ((set->contains("... FINAL QELSE")) && (vars_on <= 1)) continue; /* OK so far */ return FALSE; /* Won't be reached if constraints are being met. Also note this WILL be reached if the set doesn't contain one of the possible qelse's. */ } return TRUE; p} /****************/ // [....] /**********************************************************************/ void get_current_decision(CStringSet **return_qif_decision, CStringSet **return_qint_decision) { annote *an = global_symbol_table->annotes()->peek_annote(k_qdecision_current); if (an == NULL) { (*return_qif_decision) = NULL; (*return_qint_decision) = NULL; return; } CStringSet *decision = pIL2pCStringSet(an->immeds()); CStringSet *qif_decision = new CStringSet(); CStringSet *qint_decision = new CStringSet(); Pix index = decision->first(); while (index != 0) { char *str = (*decision)(index); char *equal = strchr(str, '='); if (equal == NULL) qif_decision->add(str); else qint_decision->add(str); decision->next(index); } (*return_qif_decision) = qif_decision; (*return_qint_decision) = qint_decision; } /****************/ void set_current_decision(CStringSet *all_qif_vars, CStringSet *all_qint_vars, CStringSet *qif_decision, CStringSet *qint_decision) { annote_list *annotes = global_symbol_table->annotes(); if (annotes->get_annote(k_qdecision_current) != NULL) { if (debug_level >= 1) printf(" set_current_decision: error? called when " "there was existing decision.\n"); } CStringSet *decision = new CStringSet(); (*decision) |= (*qif_decision); (*decision) |= (*qint_decision); global_symbol_table->append_annote (k_qdecision_current, pCStringSet2pIL(decision)); /* Implement qif definitions */ Pix index = all_qif_vars->first(); while (index != 0) { var_sym *vs = global_symbol_table->lookup_var((*all_qif_vars)(index)); assert(vs != NULL); var_def *vd = file_symbol_table->lookup_var_def(vs); assert(vd != NULL); (void) vd->get_annote(k_repeat_init); /* strip off any existing */ if (qif_decision->contains((*all_qif_vars)(index))) { immed_list_e *ile1 = new immed_list_e(*(new immed(1))); immed_list_e *ile2 = new immed_list_e(*(new immed(32))); immed_list_e *ile3 = new immed_list_e(*(new immed(1))); immed_list *il = new immed_list(); il->append(ile1); il->append(ile2); il->append(ile3); vd->append_annote(k_repeat_init, il); } all_qif_vars->next(index); } /* Implement qint definitions */ index = all_qint_vars->first(); while (index != 0) { char *value_str; var_sym *vs = global_symbol_table->lookup_var((*all_qint_vars)(index)); assert(vs != NULL); var_def *vd = file_symbol_table->lookup_var_def(vs); assert(vd != NULL); (void) vd->get_annote(k_repeat_init); /* strip off any existing */ if ((value_str = retrieve_rhs(qint_decision,(*all_qint_vars)(index),'=')) != NULL) { immed_list_e *ile1 = new immed_list_e(*(new immed(1))); immed_list_e *ile2 = new immed_list_e(*(new immed(32))); immed_list_e *ile3 = new immed_list_e(*(new immed(atoi(value_str)))); immed_list *il = new immed_list(); il->append(ile1); il->append(ile2); il->append(ile3); vd->append_annote(k_repeat_init, il); } all_qint_vars->next(index); } } /****************/ boolean decision_already_tried(CStringSet *qif_decision, CStringSet *qint_decision) { /* This function strongly begs to have some caching.... */ CStringSet this_decision; this_decision |= (*qif_decision); this_decision |= (*qint_decision); annote_list_iter anli = annote_list_iter(global_symbol_table->annotes()); while (! anli.is_empty()) { annote *an = anli.step(); if (an->name() == k_qdecision_history) { immed_list *il = an->immeds(); immed_list_e *ile = new immed_list_e(il->pop()); CStringSet *past_decision = pIL2pCStringSet(il); il->push(ile); if ((*past_decision) == this_decision) { delete past_decision; return TRUE; } else delete past_decision; } } return FALSE; } /**********************************************************************/ CStringSet *dumpfile2pCStringSet(char *filename) { CStringSet *set = new CStringSet(); if (debug_level >= 2) printf(" dumpfile2pCStringSet: called on file '%s'.\n", filename); FILE *file = fopen(filename, "r"); if (file == NULL) { if (debug_level >= 1) printf(" dumpfile2pCStringSet: error! Could not open file. " "Returning empty set.\n"); return set; } unsigned int int_buffer; fread(&int_buffer, sizeof(unsigned int), 1, file); if (int_buffer != 0xEFBEADDE) { if (debug_level >= 1) printf(" dumpfile2pCStringSet: error! file doesn't start with magic " "cookie value. Returning empty set.\n"); return set; } fread(&int_buffer, sizeof(unsigned int), 1, file); if (int_buffer != 0x00000001) { if (debug_level >= 1) printf(" dumpfile2pCStringSet: error! file version not understood " "by this program. Returning empty set.\n"); return set; } fread(&int_buffer, sizeof(unsigned int), 1, file); fseek(file, 0, SEEK_END); int file_size = ftell(file); if (file_size % (3*sizeof(unsigned int) + int_buffer*sizeof(unsigned long long int)) != 0) { if (debug_level >= 1) printf(" dumpfile2pCStringSet: error! file wrong size. " "Returning empty set.\n"); return set; } fseek(file, 0, SEEK_SET); unsigned long long int *totals = (unsigned long long int *) calloc(int_buffer, sizeof(unsigned long long int)); assert(totals != NULL); int loop; while (! feof(file)) { fseek(file, sizeof(unsigned int)*3, SEEK_CUR); unsigned long long int *pass = (unsigned long long int *) malloc(int_buffer * sizeof(unsigned long long int)); assert(pass != NULL); if (fread(pass,sizeof(unsigned long long int),int_buffer, file) != int_buffer) { if (debug_level >= 1) printf(" dumpfile2pCStringSet: error! Problem reading file. " "Returning empty set.\n"); return set; } for (loop = 0; loop < int_buffer; loop++) totals[loop] += pass[loop]; free(pass); ungetc(getc(file),file); /* Force EOF condition */ } fclose(file); if (unlink(filename) != 0) fprintf(stderr, "Error! Could not remove profile data file.\n"); else { if (debug_level >= 1) printf(" dumpfile2pCStringSet: unlinked profile data file.\n"); } char sprintf_buffer[1024], lltoa_buffer[1024]; for (loop = 0; loop < int_buffer; loop++) { if (totals[loop] != 0) { lltoa(totals[loop], lltoa_buffer); sprintf(sprintf_buffer, "%u=%s", loop, lltoa_buffer); set->add(strdup(sprintf_buffer)); } } if (debug_level >= 2) printf(" dumpfile2pCStringSet: returning {%s}.\n", pCStringSet2pChar(set)); free(totals); return set; } /****************/ void move_to_history(void) { annote_list *annotes = global_symbol_table->annotes(); annote *an = annotes->get_annote(k_qdecision_current); if (an == NULL) { if (debug_level >= 1) printf(" move_to_history: no current decision to be moved.\n"); return; } immed_list *il = an->immeds(); if (debug_level >= 1) printf(" temp...: moving decision {%s} to history.\n", pCStringSet2pChar(pIL2pCStringSet(il))); var_sym *sym = file_symbol_table->lookup_var("qp_basefilename"); assert(sym != NULL); var_def *def = file_symbol_table->lookup_var_def(sym); assert(def != NULL); an = def->annotes()->peek_annote(k_multi_init); // reuse of variable "an" assert(an != NULL); char *basefilename = (char *) malloc(an->immeds()->count()); // basefilename needs an extra byte of storage space for // the terminating '\0', but an->immeds() has one more immediate // than is going to get converted back to string representation anyway immed_list_e *ile = an->immeds()->head(); assert(ile->contents.is_integer() && (ile->contents.integer() == 8)); ile = ile->next(); int loop = 0; while (ile != NULL) { basefilename[loop++] = (char) ile->contents.integer(); ile = ile->next(); } basefilename[loop] = '\0'; char buffer[1024]; sprintf(buffer, "%s.qprofiling_data", basefilename); il->push(new immed_list_e(*(new immed (pCStringSet2pChar(dumpfile2pCStringSet((profile_data_filename != NULL) ? profile_data_filename: buffer)))))); global_symbol_table->append_annote(k_qdecision_history, il); } /**********************************************************************/ int load_qif_sets(CStringSet ***return_qif_sets) { int sets_count = 0; CStringSet **qif_sets; annote_list_iter anli = annote_list_iter(global_symbol_table->annotes()); while (! anli.is_empty()) { annote *an = anli.step(); if (an->name() == k_qif_set) { sets_count++; if (sets_count == 1) assert((qif_sets = (CStringSet **) malloc(sizeof(CStringSet **))) != NULL); else assert((qif_sets = (CStringSet **) realloc(qif_sets, sets_count * sizeof(CStringSet **))) != NULL); immed_list *il = an->immeds(); immed_list_e *ile = new immed_list_e(il->pop()); qif_sets[sets_count-1] = pIL2pCStringSet(il); il->push(ile); } } (*return_qif_sets) = qif_sets; return sets_count; } /****************/ CStringSet *load_qint_set(void) { CStringSet *qint_set = new CStringSet(); annote_list_iter anli = annote_list_iter(global_symbol_table->annotes()); while (! anli.is_empty()) { annote *an = anli.step(); if (an->name() == k_qinfluence_set) { immed_list *il = an->immeds(); immed_list_e *ile = new immed_list_e(il->pop()); (*qint_set) |= (*pIL2pCStringSet(il)); il->push(ile); } } return (qint_set); } /****************/ char *retrieve_rhs(CStringSet *set, char *key, char divider) { /* I could use libg++'s Map containers for this, but the hassle may not be worthwhile.... */ Pix index = set->first(); while (index != 0) { char *str = (*set)(index); if (strncmp(str,key,strlen(key)) == 0) return (rindex(str,divider)+1); set->next(index); } return NULL; } IntSet *range_string_to_set(char *range_str) { IntSet *set = new IntSet(); char *token = strtok(strdup(range_str), ","); while (token != NULL) { char *colon_position = strchr(token,':'); assert(colon_position == strrchr(token,':')); if (colon_position == NULL) { int singleton; sscanf(token,"%d",&singleton); set->add(singleton); } else { int start,end,loop; sscanf(token,"%d:%d",&start,&end); if (start>end) { int tmp = start; start = end; end = tmp; } for (loop=start; loop<=end; loop++) set->add(loop); } token = strtok(NULL, ","); } return set; } int maximum_of_range(IntSet *set) { /* Not very efficient.... */ assert(set->length() != 0); int maximum; Pix index = set->first(); while (index != 0) { maximum = (*set)(index); set->next(index); } return maximum; } int minimum_of_range(IntSet *set) { assert(set->length() != 0); return ((*set)(set->first())); } int next_range_value(IntSet *set, int value) { /* Not very efficient.... */ assert(set->length() != 0); Pix index = set->first(); while (index != 0) { int current_value = (*set)(index); if (current_value > value) return current_value; set->next(index); } assert(0); /* should never be reached */ return -1; /* Make compiler happy */ } /****************/ QintDecisionsGenerator::QintDecisionsGenerator(CStringSet *set) { /* I'll want QintDecisionsGenerator to deal well with being passed empty sets, since that is perfectly valid. */ this->set = new CStringSet(); (*(this->set)) |= (*set); { ranges_set = new CStringSet(); sym_node_list_iter snli = sym_node_list_iter(global_symbol_table->symbols()); while (! snli.is_empty()) { sym_node *sn = snli.step(); annote *an = sn->annotes()->peek_annote(k_qint_parameter); if (an != NULL) { char *buffer = (char *) malloc(1024); assert(buffer != NULL); strcpy(buffer, sn->name()); strcat(buffer, "="); strcat(buffer, an->immeds()->head()->contents.string()); buffer = (char *) realloc(buffer, strlen(buffer)+1); ranges_set->add(strdup(buffer)); free(buffer); } } } current = NULL; } boolean QintDecisionsGenerator::increment_at_position(Pix index) { char *key = (*set)(index); assert(key != NULL); char *range_str = retrieve_rhs(ranges_set,key,'='); char *value_str = retrieve_rhs(current,key,'='); assert(range_str != NULL); assert(value_str != NULL); int value; sscanf(value_str, "%d", &value); IntSet *range = range_string_to_set(range_str); char *sprintf_buffer = (char *) malloc(1024); assert(sprintf_buffer != NULL); if (maximum_of_range(range) == value) { set->seek(key); set->next(index); if (index == 0) assert(0); /* should never be reached, since increment_at_position should not have been called if we're done */ /* Carry over to the next "column" */ sprintf(sprintf_buffer, "%s=%d", key, value); current->del(sprintf_buffer); sprintf(sprintf_buffer, "%s=%d", key, minimum_of_range(range)); current->add(strdup(sprintf_buffer)); /* Note that this sequence of del() and add() will work even if the range only has a singleton value, even though it does much more work than strictly necessary. */ increment_at_position(index); } else { /* Increment this "column" */ int new_value = next_range_value(range, value); sprintf(sprintf_buffer, "%s=%d", key, value); current->del(sprintf_buffer); sprintf(sprintf_buffer, "%s=%d", key, new_value); current->add(strdup(sprintf_buffer)); } free(sprintf_buffer); } boolean QintDecisionsGenerator::done(void) { if (current == NULL) return FALSE; if (set->length() == 0) return TRUE; Pix index = set->first(); while (index != 0) { char *key = (*set)(index); assert(key != NULL); char *range_str = retrieve_rhs(ranges_set,key,'='); char *value_str = retrieve_rhs(current,key,'='); assert(range_str != NULL); assert(value_str != NULL); int value; sscanf(value_str, "%d", &value); IntSet *range = range_string_to_set(range_str); if (value < maximum_of_range(range)) { delete range; return FALSE; } delete range; set->next(index); } return TRUE; } CStringSet *QintDecisionsGenerator::yield(void) { if (done()) return NULL; if (current == NULL) { current = new CStringSet(); Pix index = set->first(); while (index != 0) { char *key = (*set)(index); char *range_str = retrieve_rhs(ranges_set, key, '='); assert(range_str != NULL); IntSet *range = range_string_to_set(range_str); char *sprintf_buffer = (char *) malloc(1024); assert(sprintf_buffer != NULL); sprintf(sprintf_buffer, "%s=%d", key, minimum_of_range(range)); current->add(strdup(sprintf_buffer)); free(sprintf_buffer); set->next(index); } return shallow_copy_CStringSet(current); } increment_at_position(set->first()); return shallow_copy_CStringSet(current); /* There would be considerable rep exposure if I returned current itself. */ } QintDecisionsGenerator::~QintDecisionsGenerator() { delete set; delete ranges_set; delete current; } // [....] /****************/ void choose_best_from_history(void) { /* annote_list_iter anli = annote_list_iter(global_symbol_table->annotes()); while (! anli.is_empty()) { annote *an = anli.step(); if (an->name() == k_qdecision_history) { immed_list *il = an->immeds(); immed_list_e *ile = new immed_list_e(il->pop()); CStringSet *past_decision = pIL2pCStringSet(il); XXX il->push(ile); } } */ fprintf(stderr, "WARNING!!! choose_best_from_history() not implemented.\n"); fprintf(stderr, "(De facto, most recent decision still implemented.)\n"); } /****************/ void make_decision(void) { annote *an = global_symbol_table->annotes()->peek_annote(k_qdecision_current); assert(an == NULL); CStringSet **qif_sets; int sets_count = load_qif_sets(&qif_sets); if (debug_level >= 1) printf(" make_decision: %d qif sets found.\n", sets_count); CStringSet *all_qif_vars = new CStringSet(); int loop; for (loop = 0; loop<sets_count; loop++) (*all_qif_vars) |= *(qif_sets[loop]); all_qif_vars->del("... NO FINAL QELSE"); all_qif_vars->del("... FINAL QELSE"); CStringSet *all_qint_vars = load_qint_set(); /* The following looping constructs are rather inefficient. Even after adding the "(! decision_was_made)" condition to the while loops' tests, this is extremely inefficient. For efficiency, one would want to be able to initialize the SubsetsGenerator and the QintDecisionsGenerator from the value of k_qdecision_current that was just moved into k_qdecision_history. However, it's probably not worth the effort to make that optimization now. Eventually I'll want to rewrite this whole thing anyway, and the focus should be on smarts and not on speed. */ boolean qif_constraints_meetable = FALSE; boolean decision_was_made = FALSE; SubsetsGenerator sg = SubsetsGenerator(all_qif_vars); while ((! decision_was_made) && (! sg.done())) { CStringSet *qif_decision = sg.yield(); if (qif_constraints_met(qif_sets,sets_count,qif_decision)) { qif_constraints_meetable = TRUE; if (debug_level >= 2) printf(" make_decision: {%s} would be a valid qif_decision.\n", pCStringSet2pChar(qif_decision)); if (debug_level >= 2) { print_QintDecisionsGenerator_results(all_qint_vars); } QintDecisionsGenerator qd = QintDecisionsGenerator(all_qint_vars); while ((! decision_was_made) && (! qd.done())) { CStringSet *qint_decision = qd.yield(); if (debug_level >= 2) printf(" make_decision: {%s} would be a valid " "qint_decision.\n", pCStringSet2pChar(qint_decision)); if (decision_was_made) { if (debug_level >= 2) printf(" make_decision: ...but another decision has " "already been set during this pass.\n"); } else { if (decision_already_tried(qif_decision, qint_decision)) { if (debug_level >= 2) printf(" make_decision: ...but was already tried.\n", pCStringSet2pChar(qint_decision)); } else { set_current_decision(all_qif_vars, all_qint_vars, qif_decision, qint_decision); decision_was_made = TRUE; if (debug_level >= 1) printf(" make_decision: ...decided on qif {%s} " "and qint {%s}.\n", pCStringSet2pChar(qif_decision), pCStringSet2pChar(qint_decision)); } } delete qint_decision; } } delete qif_decision; } if (! qif_constraints_meetable) fprintf(stderr, "Error! Not possible to satisfy qif semantic constraints.\n"); if (! decision_was_made) { if (debug_level >= 1) { printf(" make_decision: All qif decisions have been tried.\n"); } choose_best_from_history(); } } /**********************************************************************/ void before_hook(void) { /* Do nothing */ } /****************/ void after_hook(void) { move_to_history(); make_decision(); } /**********************************************************************/ void do_proc(tree_proc *tp) { /* Wish I could set file_symbol_table and global_symbol_table in before_hook() instead, but there isn't anything to grab on to cleanly.... The below will get run a lot more than it has to, but that shouldn't be a big deal. */ if (file_symbol_table == NULL) { file_symbol_table = tp->scope(); while (file_symbol_table->kind() != SYMTAB_FILE) file_symbol_table = file_symbol_table->parent(); } if (global_symbol_table == NULL) { global_symbol_table = file_symbol_table; while (global_symbol_table->kind() != SYMTAB_GLOBAL) global_symbol_table = global_symbol_table->parent(); } } /**********************************************************************/ int main(int argc, char *argv[]) { start_suif(argc, argv); register_qannotations(); process_command_line(argc, argv); if (argc-optind != 2) { fprintf(stderr, "%s: wrong number of filenames given on command line.\n", argv[0]); exit(1); } if (debug_level >= 3) { test_SubsetsGenerator(); test_qif_constraints_met(); test_QintDecisionsGenerator_aux_routines(); } #define WRITE_BACK_TO_FILE TRUE my_suif_proc_iter(argc, argv, do_proc, before_hook, after_hook, WRITE_BACK_TO_FILE); #define RENAME_SUCCESS_CODE 0 if (rename(argv[optind+1], argv[optind]) == RENAME_SUCCESS_CODE) { if (debug_level >= 1) printf(" Successfully renamed '%s' to '%s'.\n", argv[optind+1], argv[optind]); char buffer[1024]; sprintf(buffer, "create_executable %s", argv[optind]); system(buffer); } else { fprintf(stderr, "%s: error renaming file, output left in '%s'.\n", argv[optind+1]); exit(1); } } /**********************************************************************/