-#if defined(JOIN_PHI_LT)
-/******************************************************************************
-Set up data structures for a interference graphs of variables used in each phi
-function
-******************************************************************************/
-void lt_setup_phi_interference(lsradata *ls, graphdata *gd) {
- int a, b, i, j, t;
- int *stack, stack_top;
- struct igraph_lookup **lookup;
- struct igraph_lookup *tmp;
- int lookup_top, igraph_top;
- struct igraph_vars *new_var;
-
- lookup_top = igraph_top = 0;
- lookup = DMNEW(struct igraph_lookup *, ls->max_vars_with_indices*2);
- stack = DMNEW(int, ls->max_vars_with_indices);
- for(b = 0; b < ls->basicblockcount; b++) {
- for(a = 0; a < ls->max_vars; a++) {
- if (ls->phi[b][a] != NULL) {
-
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("Phi(%3i, %3i): ", a, gd->num_pred[b]);
- }
-#endif
- stack_top = 0;
- /* loop for all vars in this phi function -> setup a interf graph */
- /* structure for it */
- for(j = 0; j < gd->num_pred[b] + 1; j++) {
- if (ls->phi[b][a][j] != ls->max_vars_with_indices) {
- /* used entry */
- stack[stack_top++] = ls->phi[b][a][j];
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("%3i ",ls->phi[b][a][j]);
- }
-#endif
- }
- }
- _LT_ASSERT(stack_top <= ls->max_vars_with_indices);
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("\n ");
- }
-#endif
- /* sort (insertion)*/
- /* TODO: make unique sort proc (see lsra_insertion...) */
- for (i = 1; i <= stack_top - 1; i++) {
- j = i;
- t = stack[j];
- while ((j > 0) && (stack[j-1] > t)) {
- stack[j] = stack[j-1];
- j--;
- }
- stack[j] = t;
- }
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("Sorted: ");
- for(i=0; i < stack_top; i++)
- printf("%3i ",stack[i]);
- printf("\n");
- }
-#endif
- /* now remove duplicates */
- /* t ... new stack_top */
- /* i ... first of duplicate sequence */
- /* j ... next duplicate sequence */
- i = t = 0;
- while (i < stack_top) {
- stack[t] = stack[i];
- t++;
- for(j = i + 1; (j < stack_top)&&(stack[i]==stack[j]); j++);
- if (j == stack_top) {
- /* last duplicate entries */
- stack_top = t;
- break;
- }
- i = j;
- }
- _LT_ASSERT(stack_top <= ls->max_vars_with_indices);
-#if defined(LSRA_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("wo duplicates: ");
- for(i=0; i < stack_top; i++)
- printf("%3i ",stack[i]);
- printf("\n");
- }
-#endif
- /* setup lookuptable for vars stack[0..stack_top[ to */
- /* interference graph number & interference graph structure */
- for(i = 0; i < stack_top; i++) {
- _LT_ASSERT(lookup_top < ls->max_vars_with_indices*2);
- lookup[lookup_top] = DNEW(struct igraph_lookup);
- lookup[lookup_top]->var = stack[i]; /* var index */
- lookup[lookup_top]->igraph = igraph_top; /* igraph index */
- lookup_top++;
- }
- igraph_top++;
- }
- }
- }
- ls->igraph = DMNEW(struct igraph , igraph_top);
- ls->igraph_top = igraph_top;
- for(i = 0; i < igraph_top; i++) {
- ls->igraph[i].inter = NULL;
- ls->igraph[i].vars = NULL;
- }
-
- /* sort lookup */
-
- for (i = 1; i < lookup_top; i++) {
- j = i;
- t = lookup[j]->var;
- tmp = lookup[j];
- while ((j > 0) && (lookup[j-1]->var > t)) {
- lookup[j]=lookup[j-1];
- j--;
- }
- lookup[j] = tmp;
- }
-
- /* join igraphs for multiple vars */
- /* TODO: make this more efficient! */
- for (i = 1; i < lookup_top; i++) {
- if (lookup[i-1]->var == lookup[i]->var) {
- for(j = 0; j < lookup_top; j++)
- if (j != i)
- if (lookup[j]->igraph == lookup[i]->igraph)
- lookup[j]->igraph = lookup[i-1]->igraph;
- lookup[i]->igraph = lookup[i-1]->igraph;
- }
- }
-
- ls->igraph_lookup_top = lookup_top;
- ls->igraph_lookup = DMNEW(struct igraph_lookup *, lookup_top);
- for(i = 0; i < lookup_top; i++) {
- ls->igraph_lookup[i] = lookup[i];
- new_var = DNEW(struct igraph_vars);
- new_var->v = lookup[i]->var;
- new_var->next = ls->igraph[lookup[i]->igraph].vars;
- ls->igraph[lookup[i]->igraph].vars = new_var;
- }
-#if defined(LT_DEBUG_VERBOSE)
- if (compileverbose) {
- printf("IGraph(%3i): ",igraph_top);
- for(i = 0; i < igraph_top; i++) {
- printf("%3i(",i);
- for(new_var = ls->igraph[i].vars; new_var != NULL; new_var = new_var->next)
- printf("%3i,",new_var->v);
- printf(") ");
- }
- printf("\n");
- for(i=0; i < lookup_top; i++)
- printf("(%3i->%3i) ",ls->igraph_lookup[i]->var, ls->igraph_lookup[i]->igraph);
- printf("\n");
- }
-#endif
-}
-
-int get_igraph_index(lsradata *ls, int var) {
- int i, i_max, i_min;
-
- if (ls->igraph_lookup == NULL)
- return -1;
-
- i_min = 0;
- i_max = ls->igraph_lookup_top;
-
- while (true) {
- i = (i_min + i_max)/2;
- if (ls->igraph_lookup[i]->var == var)
- return ls->igraph_lookup[i]->igraph;
- if ((i_max - i_min <= 1))
- return -1;
- if (var < ls->igraph_lookup[i]->var) {
- i_max = i;
- } else {
- i_min = i;
- }
- }
- /* prevent compiler warning */
- return -1;
-}
-
-void build_interference(lsradata *ls, int b_index, int iindex,
- struct lifetime *lt) {
- int igraph_index;
- struct igraph_vars *v;
- struct igraph_interference *i;
- struct lifetime *lt_i;
-
- if ((igraph_index = get_igraph_index(ls, lt->v_index)) == -1)
- return;
-
- _LT_ASSERT(ls->igraph[igraph_index].vars != NULL);
-
- for(v = ls->igraph[igraph_index].vars; v != NULL; v = v->next) {
- /* ignore interference with var itself */
- if (v->v != lt->v_index) {
- /* get lifetime of v->v */
- if (v->v >= 0) {
- lt_i = &(ls->lifetime[ls->maxlifetimes + v->v]);
- } else {
- lt_i = &(ls->lifetime[-v->v - 1]);
- }
- _LT_ASSERT(lt_i->v_index == v->v);
-
- if (v_is_defined_at_s(ls, b_index, iindex, lt_i)) {
- /* search if entry already exists */
- for(i = ls->igraph[igraph_index].inter; i != NULL; i = i->next)
- {
- if ((i->v1 == min(v->v, lt->v_index)) &&
- (i->v2 == max(v->v, lt->v_index)))
- break;
- }
- if (i == NULL) {
- i = DNEW(struct igraph_interference);
- i->v1 = min(v->v, lt->v_index);
- i->v2 = max(v->v, lt->v_index);
- i->next = ls->igraph[igraph_index].inter;
- ls->igraph[igraph_index].inter = i;
- }
- }
- }
- }
-
-}
-#endif
-
-void LifenessAnalysis(methodinfo *m, lsradata *ls, graphdata *gd) {
- int *M; /* bit_vecor of visited blocks */
- int *use; /* bit_vecor of blocks with use sites visited */