1 /* src/vm/jit/lsra.inc - lifetime anaylsis
3 Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
4 R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
5 C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
6 Institut f. Computersprachen - TU Wien
8 This file is part of CACAO.
10 This program is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License as
12 published by the Free Software Foundation; either version 2, or (at
13 your option) any later version.
15 This program is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
25 Contact: cacao@complang.tuwien.ac.at
27 Authors: Christian Ullrich
36 #include "mm/memory.h"
38 #include "toolbox/bitvector.h"
39 #include "toolbox/worklist.h"
41 #include "vm/builtin.h"
42 #include "vm/resolve.h"
43 #include "vm/exceptions.h"
44 #include "vm/stringlocal.h"
46 #include "vm/jit/jit.h"
48 #include "vm/jit/optimizing/graph.h"
49 #include "vm/jit/optimizing/lsra.h"
50 #include "vm/jit/optimizing/ssa.h"
51 #include "vm/jit/optimizing/lifetimes.h"
53 #ifdef LT_DEBUG_VERBOSE
54 #include "vm/options.h"
60 /* function prototypes */
61 void _scan_lifetimes(registerdata *rd, lsradata *ls, graphdata *gd,
63 void _lsra_new_stack( lsradata *, stackptr , int , int, int);
64 void _lsra_from_stack(lsradata *, stackptr , int , int, int);
65 void lsra_usage_local(lsradata *, s4 , int , int , int , int );
68 void LifeOutAtBlock(lsradata *ls, graphdata *gd, int *M, int n,
70 void LifeInAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
71 int iindex, struct lifetime *lt);
72 void LifeOutAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
73 int iindex, struct lifetime *lt);
75 void lt_get_nesting(lsradata *ls, graphdata *gd, dominatordata *dd);
78 void set_use_site(struct lifetime *lt, struct site *use_site) {
81 struct site *get_first_use_site(struct lifetime *lt, lt_iterator *iter) {
82 return ((*iter) = lt->use);
85 struct site *get_next_site(lt_iterator *iter) {
89 return ((*iter) = (*iter)->next);
92 struct site *get_first_def_site(struct lifetime *lt, lt_iterator *iter) {
93 return ((*iter) = lt->def);
96 bool v_is_defined_at_s(lsradata *ls, int b_index, int iindex,
97 struct lifetime * lt) {
98 struct site *def_site;
102 is_defined_at_s = ((def_site->b_index == b_index)
103 && (def_site->iindex == iindex));
104 return is_defined_at_s;
107 /****************************************************************************
109 ****************************************************************************/
110 void scan_lifetimes(methodinfo *m, codegendata *cd, registerdata *rd,
111 lsradata *ls, graphdata *gd, dominatordata *dd) {
114 methoddesc *md = m->parseddesc;
119 lt_get_nesting(ls, gd, dd);
122 #if defined(LT_DEBUG_VERBOSE)
123 if (compileverbose) {
125 for (i=0; i < ls->basicblockcount; i++) printf("%3i ", ls->sorted[i]);
127 printf("Sorted_rev: ");
128 for (i=0; i < ls->basicblockcount; i++)
129 printf("%3i ", ls->sorted_rev[i]);
133 if (ls->max_interfaces != -1) {
134 /* init Interface Stackslot lifetimes -1.. */
135 for (i = -1; i > -ls->interface_0[-ls->max_interfaces-1]-1; i--) {
136 ls->lifetime[-i-1].v_index = i;
137 ls->lifetime[-i-1].usagecount = 0;
138 ls->lifetime[-i-1].bb_last_use = -1;
139 ls->lifetime[-i-1].bb_first_def = -1;
140 ls->lifetime[-i-1].local_ss = NULL;
141 ls->lifetime[-i-1].savedvar = 0;
142 ls->lifetime[-i-1].flags = 0;
143 /* .type already set while ssa_Rename_, so we could save a */
144 /* lookup table for the type information */
146 ls->v_index = -ls->interface_0[-ls->max_interfaces-1]-1;
149 for(i = ls->basicblockcount - 1; i>= 0; i--)
150 if (ls->sorted[i] != -1)
151 _scan_lifetimes(rd, ls, gd, ls->basicblocks[ls->sorted[i]]);
153 /* Parameter initialisiation for locals [0 .. paramcount[ */
154 /* -> add local var write access at (bb=0,iindex=0) */
156 for (p = 0; p < md->paramcount; p++) {
157 t = md->paramtypes[p].type;
159 _LT_ASSERT( i < jd->maxlocals);
160 #ifdef LT_DEBUG_VERBOSE
162 printf("param %3i -> L %3i/%3i",p,i,t);
164 if (rd->locals[i][t].type >= 0) {
165 /* Param to Local init happens before normal Code */
166 #ifdef LT_DEBUG_VERBOSE
170 lsra_usage_local(ls, i, t, 0, 0, LSRA_STORE);
172 #ifdef LT_DEBUG_VERBOSE
181 bool is_simple_lt(struct lifetime *lt) {
182 lt_iterator i_def, i_use;
183 struct site *def, *use;
184 bool all_in_same_block;
187 def = get_first_def_site(lt, &i_def);
188 use = get_first_use_site(lt, &i_use);
189 all_in_same_block = true;
190 for (; (all_in_same_block && (use != NULL)); use = get_next_site(&i_use)) {
192 (use->iindex >= 0) && (use->b_index == def->b_index);
194 return all_in_same_block;
197 void lt_is_live(lsradata *ls, struct lifetime *lt, int b_index, int iindex) {
200 bb_sorted = ls->sorted_rev[b_index];
202 if ((lt->bb_last_use < bb_sorted) ||
203 ((lt->bb_last_use == bb_sorted) && (lt->i_last_use < iindex))) {
204 lt->bb_last_use = bb_sorted;
205 lt->i_last_use = iindex;
207 if ((lt->bb_first_def > bb_sorted) ||
208 ((lt->bb_first_def == bb_sorted) && (lt->i_first_def > iindex))) {
209 lt->bb_first_def = bb_sorted;
210 lt->i_first_def = iindex;
214 void lt_set_simple_use(lsradata *ls, struct lifetime *lt) {
218 /* SAVEDVAR is nowhere set!!!! */
220 /* Def is first use */
221 /* lt->bb_first_def = ls->sorted_rev[lt->def->b_index]; */
222 /* lt->i_first_def = lt->def->iindex; */
224 lt_is_live(ls, lt, lt->def->b_index, lt->def->iindex);
227 use = get_first_use_site(lt, &i_use);
228 /* lt->bb_last_use = ls->sorted_rev[use->b_index]; */
229 /* lt->i_last_use = use->iindex; */
230 for (; (use != NULL); use = get_next_site(&i_use))
231 lt_is_live(ls, lt, use->b_index, use->iindex);
232 /* if (use->iindex > lt->i_last_use) */
233 /* lt->i_last_use = use->iindex; */
236 #if defined(JOIN_PHI_LT)
237 /******************************************************************************
238 Set up data structures for a interference graphs of variables used in each phi
240 ******************************************************************************/
241 void lt_setup_phi_interference(lsradata *ls, graphdata *gd) {
243 int *stack, stack_top;
244 struct igraph_lookup **lookup;
245 struct igraph_lookup *tmp;
246 int lookup_top, igraph_top;
247 struct igraph_vars *new_var;
249 lookup_top = igraph_top = 0;
250 lookup = DMNEW(struct igraph_lookup *, ls->max_vars_with_indices*2);
251 stack = DMNEW(int, ls->max_vars_with_indices);
252 for(b = 0; b < ls->basicblockcount; b++) {
253 for(a = 0; a < ls->max_vars; a++) {
254 if (ls->phi[b][a] != NULL) {
256 #if defined(LT_DEBUG_VERBOSE)
257 if (compileverbose) {
258 printf("Phi(%3i, %3i): ", a, gd->num_pred[b]);
262 /* loop for all vars in this phi function -> setup a interf graph */
263 /* structure for it */
264 for(j = 0; j < gd->num_pred[b] + 1; j++) {
265 if (ls->phi[b][a][j] != ls->max_vars_with_indices) {
267 stack[stack_top++] = ls->phi[b][a][j];
268 #if defined(LT_DEBUG_VERBOSE)
269 if (compileverbose) {
270 printf("%3i ",ls->phi[b][a][j]);
275 _LT_ASSERT(stack_top <= ls->max_vars_with_indices);
276 #if defined(LT_DEBUG_VERBOSE)
277 if (compileverbose) {
281 /* sort (insertion)*/
282 /* TODO: make unique sort proc (see lsra_insertion...) */
283 for (i = 1; i <= stack_top - 1; i++) {
286 while ((j > 0) && (stack[j-1] > t)) {
287 stack[j] = stack[j-1];
292 #if defined(LT_DEBUG_VERBOSE)
293 if (compileverbose) {
295 for(i=0; i < stack_top; i++)
296 printf("%3i ",stack[i]);
300 /* now remove duplicates */
301 /* t ... new stack_top */
302 /* i ... first of duplicate sequence */
303 /* j ... next duplicate sequence */
305 while (i < stack_top) {
308 for(j = i + 1; (j < stack_top)&&(stack[i]==stack[j]); j++);
309 if (j == stack_top) {
310 /* last duplicate entries */
316 _LT_ASSERT(stack_top <= ls->max_vars_with_indices);
317 #if defined(LSRA_DEBUG_VERBOSE)
318 if (compileverbose) {
319 printf("wo duplicates: ");
320 for(i=0; i < stack_top; i++)
321 printf("%3i ",stack[i]);
325 /* setup lookuptable for vars stack[0..stack_top[ to */
326 /* interference graph number & interference graph structure */
327 for(i = 0; i < stack_top; i++) {
328 _LT_ASSERT(lookup_top < ls->max_vars_with_indices*2);
329 lookup[lookup_top] = DNEW(struct igraph_lookup);
330 lookup[lookup_top]->var = stack[i]; /* var index */
331 lookup[lookup_top]->igraph = igraph_top; /* igraph index */
338 ls->igraph = DMNEW(struct igraph , igraph_top);
339 ls->igraph_top = igraph_top;
340 for(i = 0; i < igraph_top; i++) {
341 ls->igraph[i].inter = NULL;
342 ls->igraph[i].vars = NULL;
347 for (i = 1; i < lookup_top; i++) {
351 while ((j > 0) && (lookup[j-1]->var > t)) {
352 lookup[j]=lookup[j-1];
358 /* join igraphs for multiple vars */
359 /* TODO: make this more efficient! */
360 for (i = 1; i < lookup_top; i++) {
361 if (lookup[i-1]->var == lookup[i]->var) {
362 for(j = 0; j < lookup_top; j++)
364 if (lookup[j]->igraph == lookup[i]->igraph)
365 lookup[j]->igraph = lookup[i-1]->igraph;
366 lookup[i]->igraph = lookup[i-1]->igraph;
370 ls->igraph_lookup_top = lookup_top;
371 ls->igraph_lookup = DMNEW(struct igraph_lookup *, lookup_top);
372 for(i = 0; i < lookup_top; i++) {
373 ls->igraph_lookup[i] = lookup[i];
374 new_var = DNEW(struct igraph_vars);
375 new_var->v = lookup[i]->var;
376 new_var->next = ls->igraph[lookup[i]->igraph].vars;
377 ls->igraph[lookup[i]->igraph].vars = new_var;
379 #if defined(LT_DEBUG_VERBOSE)
380 if (compileverbose) {
381 printf("IGraph(%3i): ",igraph_top);
382 for(i = 0; i < igraph_top; i++) {
384 for(new_var = ls->igraph[i].vars; new_var != NULL; new_var = new_var->next)
385 printf("%3i,",new_var->v);
389 for(i=0; i < lookup_top; i++)
390 printf("(%3i->%3i) ",ls->igraph_lookup[i]->var, ls->igraph_lookup[i]->igraph);
396 int get_igraph_index(lsradata *ls, int var) {
399 if (ls->igraph_lookup == NULL)
403 i_max = ls->igraph_lookup_top;
406 i = (i_min + i_max)/2;
407 if (ls->igraph_lookup[i]->var == var)
408 return ls->igraph_lookup[i]->igraph;
409 if ((i_max - i_min <= 1))
411 if (var < ls->igraph_lookup[i]->var) {
417 /* prevent compiler warning */
421 void build_interference(lsradata *ls, int b_index, int iindex,
422 struct lifetime *lt) {
424 struct igraph_vars *v;
425 struct igraph_interference *i;
426 struct lifetime *lt_i;
428 if ((igraph_index = get_igraph_index(ls, lt->v_index)) == -1)
431 _LT_ASSERT(ls->igraph[igraph_index].vars != NULL);
433 for(v = ls->igraph[igraph_index].vars; v != NULL; v = v->next) {
434 /* ignore interference with var itself */
435 if (v->v != lt->v_index) {
436 /* get lifetime of v->v */
438 lt_i = &(ls->lifetime[ls->maxlifetimes + v->v]);
440 lt_i = &(ls->lifetime[-v->v - 1]);
442 _LT_ASSERT(lt_i->v_index == v->v);
444 if (v_is_defined_at_s(ls, b_index, iindex, lt_i)) {
445 /* search if entry already exists */
446 for(i = ls->igraph[igraph_index].inter; i != NULL; i = i->next)
448 if ((i->v1 == min(v->v, lt->v_index)) &&
449 (i->v2 == max(v->v, lt->v_index)))
453 i = DNEW(struct igraph_interference);
454 i->v1 = min(v->v, lt->v_index);
455 i->v2 = max(v->v, lt->v_index);
456 i->next = ls->igraph[igraph_index].inter;
457 ls->igraph[igraph_index].inter = i;
466 void LifenessAnalysis(methodinfo *m, lsradata *ls, graphdata *gd) {
467 int *M; /* bit_vecor of visited blocks */
468 int *use; /* bit_vecor of blocks with use sites visited */
470 struct site *use_site, *u_site;
471 lt_iterator iter, iter1;
472 graphiterator pred_iter;
474 int lt_index, i, pred, iindex, iindex1;
477 struct timespec time_start,time_end;
479 bool measure = false;
482 /* #define MEASURE_RT */
485 if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_start)) != 0) {
486 fprintf(stderr,"could not get time: %s\n",strerror(errno));
491 if ((strcmp(m->class->name->text, "java/lang/Object")==0) &&
492 (strcmp(m->name->text,"equals")==0)) {
493 printf("----------------\n");
494 /* measure = false; */
497 #if defined(JOIN_PHI_LT)
498 lt_setup_phi_interference(ls, gd);
501 M = bv_new(ls->basicblockcount);
502 use = bv_new(ls->basicblockcount);
504 #ifdef LT_DEBUG_VERBOSE
506 printf("LT_ANALYSE: \n");
508 for(lt_index = 0; lt_index < ls->lifetimecount; lt_index++) {
509 lt = &(ls->lifetime[lt_index]);
512 #ifdef LT_DEBUG_VERBOSE
514 printf("LT: %3i:", lt_index);
519 if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_start)) != 0) {
520 fprintf(stderr,"could not get time: %s\n",strerror(errno));
527 _LT_ASSERT(lt->def != NULL);
528 _LT_ASSERT(lt->def->next == NULL); /* SSA! */
529 _LT_ASSERT(lt->use != NULL);
531 lt->bb_last_use = -1;
532 lt->bb_first_def = ls->basicblockcount;
534 bv_reset(M, ls->basicblockcount);
535 bv_reset(use, ls->basicblockcount);
537 use_site = get_first_use_site(lt, &iter);
538 for (;use_site != NULL; use_site = get_next_site(&iter)) {
539 iindex = use_site->iindex;
540 if ((lt->def->b_index == use_site->b_index) &&
542 (iindex <= lt->def->iindex)) {
543 if (iindex == lt->def->iindex) /* check this */
545 /* do normal analysis */
546 /* there is a use in a phi function before def site */
547 } else if (bv_get_bit(use, use_site->b_index)) {
550 bv_set_bit(use, use_site->b_index);
551 /* use sites of this basic block not visited till now */
552 /* get use site of this bb with highest iindex (lower than def site)*/
555 for(iter1= iter; u_site != NULL; u_site = get_next_site(&iter1)) {
556 if ((u_site->b_index == use_site->b_index) &&
557 (lt->def->b_index == use_site->b_index) &&
558 (u_site->iindex >= 0) &&
559 (u_site->iindex < lt->def->iindex) &&
560 (u_site->iindex > iindex1)) {
561 iindex1 = u_site->iindex;
563 if ((u_site->b_index == use_site->b_index) &&
564 (u_site->iindex > iindex))
565 iindex = u_site->iindex;
571 #ifdef LT_DEBUG_VERBOSE
573 printf("(%3i,%3i)", use_site->b_index, iindex);
577 /* use in phi function */
578 /* ls->phi[use_site->b_index][-use_site->iindex-1]*/
580 lt_is_live(ls, lt, use_site->b_index, iindex);
582 phi = ls->phi[use_site->b_index][-iindex-1];
583 _LT_ASSERT(phi != NULL);
585 if (lt->v_index != phi[0]) { /* check this */
586 /* ignore "Self use/def" in phi function */
589 pred = graph_get_first_predecessor(gd, use_site->b_index,
591 for(i = 1; (pred != -1); i++,pred =
592 graph_get_next(&pred_iter))
593 if (lt->v_index == phi[i])
594 LifeOutAtBlock(ls, gd, M, pred, lt);
597 LifeInAtStatement(ls, gd, M, use_site->b_index,
600 #ifdef LT_DEBUG_VERBOSE
607 if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_end)) != 0) {
608 fprintf(stderr,"could not get time: %s\n",strerror(errno));
616 diff = (time_end.tv_nsec - time_start.tv_nsec) / 1000;
617 atime = time_start.tv_sec;
618 while (atime < time_end.tv_sec) {
622 printf("%8li %3i %s.%s.%s\n",diff, lt_index, m->class->name->text, m->name->text,
623 m->descriptor->text);
629 if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_end)) != 0) {
630 fprintf(stderr,"could not get time: %s\n",strerror(errno));
638 diff = (time_end.tv_nsec - time_start.tv_nsec) / 1000;
639 atime = time_start.tv_sec;
640 while (atime < time_end.tv_sec) {
644 printf("%8li %s.%s.%s\n",diff, m->class->name->text, m->name->text,
645 m->descriptor->text);
649 #if defined(JOIN_PHI_LT)
650 #if defined(LT_DEBUG_VERBOSE)
651 if (compileverbose) {
652 struct igraph_interference *inter;
653 printf("Interferences: ");
654 for(i = 0; i < ls->igraph_top; i++) {
655 if (ls->igraph[i].inter != NULL) {
656 for(inter = ls->igraph[i].inter; inter != NULL; inter = inter->next)
657 printf("%3i(%3i,%3i) ",i,inter->v1,inter->v2);
665 struct igraph_vars *var, *var1;
666 struct igraph_interference *inter;
667 struct lifetime *lt1, *lt2;
668 struct stackslot *ss;
675 /* join phi arguments that do not interfere */
676 printf("this should not be seen \n");
677 for(i = 0; i < ls->igraph_top; i++) {
678 if (ls->igraph[i].inter == NULL) {
680 for(var = ls->igraph[i].vars; var != NULL; var = var->next) {
683 lt1 = &(ls->lifetime[ls->maxlifetimes + var->v]);
685 lt1 = &(ls->lifetime[-var->v - 1]);
687 _LT_ASSERT(lt1->v_index == var->v);
691 lt2 = &(ls->lifetime[ls->maxlifetimes + var->v]);
693 lt2 = &(ls->lifetime[-var->v - 1]);
695 _LT_ASSERT(lt2->v_index == var->v);
698 if ((lt1->v_index < 0) && (lt2->v_index >=0)) {
699 /* swap lt1 and lt2 - cannot join Stackslotlifetime */
700 /* into Localvar lifetimes */
707 if ((lt1->v_index >=0) && (lt2->v_index >=0)) {
708 for(s = lt2->def; s != NULL; s = s->next) {
709 if ((s->b_index == 0) && (s->iindex ==0)) {
710 /* swap lt1 and lt2 - lt2 is initialized by a param*/
712 _LT_ASSERT((lt1->def->b_index != 0)
713 || (lt1->def->iindex !=0));
723 if ((lt2->type == -1) || (lt1 == lt2))
725 #if defined(LT_DEBUG_VERBOSE)
726 if (compileverbose) {
727 printf("Joining %3i into %3i\n",lt2->v_index, lt1->v_index);
731 /* copy local_ss from lt2 to lt1 & rename local_ss->s->varnum */
732 while (lt2->local_ss != NULL) {
733 if (lt1->v_index >= 0) {
734 lt2->local_ss->s->varkind = LOCALVAR;
736 /* other direction not possible! (LOCALVAR->TEMPVAR) */
738 lt2->local_ss->s->varnum = lt1->v_index;
741 lt1->local_ss = lt2->local_ss;
742 lt2->local_ss = lt2->local_ss->next;
743 lt1->local_ss->next = ss;
746 /* look at the use sites */
747 for(s = lt2->use; s != NULL; s = s->next) {
749 /* use in phi function -> change */
750 pred=graph_get_first_predecessor(gd, s->b_index, &iter);
751 for (j = 1; pred != -1; j++,
752 pred = graph_get_next(&iter)) {
753 if (ls->phi[s->b_index][-s->iindex-1][j] ==
755 ls->phi[s->b_index][-s->iindex-1][j]
757 /* change in appropriate phi_move, too */
758 for(k=0; k<ls->num_phi_moves[pred]; k++) {
759 if (ls->phi_moves[pred][k][1] ==
761 ls->phi_moves[pred][k][1]=lt1->v_index;
763 /* if (ls->phi_moves[pred][k][0] == */
764 /* lt2->v_index) { */
765 /* ls->phi_moves[pred][k][0]=lt1->v_index; */
770 /* change in appropriate phi_move, too */
772 if (lt2->v_index >= 0) {
773 /* lt1&<2 are LOCALVAR, XSTORE,IINC and XLOAD */
774 /* have to be changed */
775 iptr = ls->basicblocks[s->b_index]->iinstr +
778 /* no edge splitting block from SSA */
784 case ICMD_ALOAD:/* iptr->op1 == USE */
790 case ICMD_IINC: /* iptr->op1 == USE */
791 if (iptr->op1 == lt2->v_index)
792 iptr->op1 = lt1->v_index;
795 /* could be in another than the top stackslot */
797 /* _LT_ASSERT((iptr-1)->dst->varnum == */
802 /* uses in stackslots are already changed above by */
803 /* renameing and copying of local_ss */
805 } /* for(s = lt2->use; s != NULL; s = s->next) */
806 if (lt2->v_index >= 0) {
807 /* change def site */
808 _LT_ASSERT(lt2->def != NULL);
809 /* no SSA Anymore -> cyle through all def sites */
810 /* _LT_ASSERT(lt2->def->next == NULL); */
812 for(s = lt2->def; s != NULL; s = s->next) {
815 if (ls->phi[s->b_index][-s->iindex-1][0] == lt2->v_index)
816 ls->phi[s->b_index][-s->iindex-1][0] = lt1->v_index;
817 pred=graph_get_first_predecessor(gd, s->b_index, &iter);
818 for (; pred != -1; pred = graph_get_next(&iter)) {
819 /* change in appropriate phi_move, too */
820 for(k=0; k<ls->num_phi_moves[pred]; k++) {
821 if (ls->phi_moves[pred][k][0] ==
823 ls->phi_moves[pred][k][0]=lt1->v_index;
830 iptr = ls->basicblocks[s->b_index]->iinstr
842 case ICMD_ASTORE: /* iptr->op1 == DEF */
843 if(iptr->op1 == lt2->v_index)
844 iptr->op1 = lt1->v_index;
846 case ICMD_IINC: /* iptr->val._i.op1_t == DEF */
847 if (iptr->val._i.op1_t == lt2->v_index)
848 iptr->val._i.op1_t = lt1->v_index;
851 /* could be in another than the top stackslot */
853 /* _LT_ASSERT((iptr->dst->varnum == lt1->v_index)); */
859 /* combine def sites (SSA is dead now)*/
860 _LT_ASSERT(lt2->def != NULL);
861 for(s = lt2->def; s->next != NULL; s = s->next);
865 /* combine use sites */
866 _LT_ASSERT(lt2->use != NULL);
867 for(s = lt2->use; s->next != NULL; s = s->next);
871 /* combine first_def and last_use */
872 if (lt1->bb_first_def == lt2->bb_first_def) {
873 lt1->i_first_def = min(lt1->i_first_def, lt2->i_first_def);
874 } else if (lt1->bb_first_def > lt2->bb_first_def) {
875 lt1->bb_first_def = lt2->bb_first_def;
876 lt1->i_first_def = lt2->i_first_def;
878 if (lt1->bb_last_use == lt2->bb_last_use) {
879 lt1->i_last_use = max(lt1->i_last_use, lt2->i_last_use);
880 } else if (lt1->bb_last_use < lt2->bb_last_use) {
881 lt1->bb_last_use = lt2->bb_last_use;
882 lt1->i_last_use = lt2->i_last_use;
885 /* combine savedvar flags */
886 lt1->savedvar |= lt2->savedvar;
887 _LT_ASSERT(lt1->type == lt2->type);
889 /* change the var in all future references of ls->igraph */
890 /* TODO: do something against this!! */
891 /* for(j = i + 1; j < ls->igraph_top; j++) { */
892 /* if (ls->igraph[j].inter == NULL) { */
893 /* for(var1 = ls->igraph[j].vars; var1 != NULL; */
894 /* var1 = var1->next) { */
895 /* if (var1->v == lt2->v_index) */
896 /* var1->v = lt1->v_index; */
900 /* not needed by now, since only for phi functions */
901 /* with absolutely no interference is checked */
903 inter = ls->igraph[j].inter;
904 for(;inter != NULL; inter = inter->next) {
905 if (inter->v1 == lt2->v_index)
906 inter->v1 = lt1->v_index;
907 if (inter->v2 == lt2->v_index)
908 inter->v2 = lt1->v_index;
914 /* look through all phi functions */
915 for(j = 0; j < ls->basicblockcount; j++) {
916 for(k = 0; k < ls->max_vars; k++) {
917 if (ls->phi[j][k] != NULL) {
918 if (ls->phi[j][k][0] == lt2->v_index)
919 ls->phi[j][k][0] = lt1->v_index;
920 for (l = 1; l < graph_get_num_predecessor(gd, j); l++) {
921 if (ls->phi[j][k][l] == lt2->v_index)
922 ls->phi[j][k][l] = lt1->v_index;
926 /* change in phi move, too */
927 for(k = 0; k < ls->num_phi_moves[j]; k++) {
928 if (ls->phi_moves[j][k][1] == lt2->v_index)
929 ls->phi_moves[j][k][1] = lt1->v_index;
930 if (ls->phi_moves[j][k][0] == lt2->v_index)
931 ls->phi_moves[j][k][0] = lt1->v_index;
934 } /* for(var = ls->igraph[i].vars; var != NULL; var = var->next) */
935 } /* if (ls->igraph[i].inter == NULL) */
936 } /* for(i = 0; i < ls->igraph_top; i++) */
941 void LifeOutAtBlock(lsradata *ls, graphdata *gd, int *M, int n,
942 struct lifetime *lt) {
943 /* lt->v_index is life at Block n */
944 if (!bv_get_bit(M,n)) { /* n no Element of M */
947 /* lt->v_index is life at last Statement of n */
950 i = ls->basicblocks[n]->icount - 1;
951 for (;((i>0) && (ls->basicblocks[n]->iinstr+i == ICMD_NOP)); i--);
952 LifeOutAtStatement(ls, gd, M, n, i,lt);
955 LifeOutAtStatement(ls, gd, M, n, 0, lt);
959 void LifeInAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
960 int iindex, struct lifetime *lt) {
961 /* lt->v_index is live-in at s */
962 int prev_iindex; /* Statement before iindex */
964 graphiterator pred_iter;
966 lt_is_live(ls, lt, b_index, iindex);
968 prev_iindex = iindex - 1;
970 /* look through phi functions */
971 for(; prev_iindex > -ls->max_vars-1;
973 if (ls->phi[b_index][-prev_iindex-1] != NULL)
976 if (iindex == -ls->max_vars-1) {
977 /* iindex is the first statement of b_index */
978 /* Statements -ls->max_vars-1 .. -1 are possible phi functions */
979 /* lt->v_index is live-in at b_index */
981 pred = graph_get_first_predecessor(gd, b_index, &pred_iter);
982 for(; pred != -1; pred = graph_get_next(&pred_iter))
983 LifeOutAtBlock(ls, gd, M, pred, lt);
985 LifeOutAtStatement(ls, gd, M, b_index, prev_iindex, lt);
988 void LifeOutAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
989 int iindex, struct lifetime *lt) {
993 /* lt->v_index is life-out at s */
995 /* for each variable w defined at s except v=lt->v_index, add a edge */
996 /* (v,w) to the interference graph, once one is needed */
998 #if defined(JOIN_PHI_LT)
999 /* Build interference Graph for variables involved in phi functions */
1000 /* it is essential, that these variables get merged, if possible! */
1001 build_interference(ls, b_index, iindex, lt);
1003 if (!v_is_defined_at_s(ls, b_index, iindex, lt)) {
1004 /* v is life in at out of statement -> check if the SAVEDVAR */
1005 /* flag is needed to be set */
1006 if ((iindex >= 0) && (b_index != 0)) {
1008 _LT_ASSERT(ls->basicblocks[b_index]->iinstr != NULL);
1009 iptr = ls->basicblocks[b_index]->iinstr + iindex;
1010 if (icmd_table[iptr->opc].flags & ICMDTABLE_CALLS)
1011 lt->savedvar = SAVEDVAR;
1013 LifeInAtStatement(ls, gd, M, b_index, iindex, lt);
1015 lt_is_live(ls, lt, b_index, iindex);
1018 struct stackslot *lsra_make_ss(stackptr s, int bb_index)
1020 struct stackslot *ss;
1022 ss=DNEW(struct stackslot);
1028 void lsra_add_ss(struct lifetime *lt, stackptr s) {
1029 struct stackslot *ss;
1031 /* Stackslot noch nicht eingetragen? */
1035 for (ss = lt->local_ss; (!insert_s) && (ss != NULL); ss = ss->next)
1036 insert_s = (ss->s == s);
1039 /* local_ss == NULL -> stack lt was set in ssa -> create Stack entry */
1040 if ((lt->local_ss == NULL) || (insert_s)) {
1041 ss = DNEW(struct stackslot);
1043 ss->s->varnum = lt->v_index;
1044 ss->next = lt->local_ss;
1046 if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
1047 if (s != NULL) lt->type = s->type;
1051 void move_stackslots(struct lifetime *from, struct lifetime *to) {
1052 struct stackslot *ss;
1054 if (from->local_ss == NULL)
1055 /* nothing to move */
1058 for(ss = from->local_ss; ss->next != NULL; ss = ss->next);
1060 ss->next = to->local_ss;
1061 to->local_ss = from->local_ss;
1062 from->local_ss = NULL;
1064 void move_use_sites(struct lifetime *from, struct lifetime *to) {
1067 _LT_ASSERT(from->use != NULL);
1068 if (from->use == NULL)
1070 for(s = from->use; s->next != NULL; s = s->next);
1073 to->use = from->use;
1077 void add_use_site(struct lifetime *lt, int block, int iindex) {
1080 n = DNEW(struct site);
1086 /* CFG is analysed from the end to the start -> so first found use site */
1087 /* is the last use of the Local Var */
1088 if (lt->last_use == NULL)
1092 void remove_use_site(struct lifetime *lt, int block, int iindex) {
1095 /* check lt->use itself */
1096 if ((lt->use->b_index == block) && (lt->use->iindex == iindex)) {
1098 lt->use = lt->use->next;
1100 /* look through list */
1101 for (n = lt->use; (n->next != NULL) && ((n->next->b_index != block) ||
1102 (n->next->iindex != iindex)); n = n->next);
1103 /* assert, that lt was found */
1104 _LT_ASSERT(n->next != NULL);
1105 _LT_ASSERT(n->next->b_index == block);
1106 _LT_ASSERT(n->next->iindex == iindex);
1108 n->next = n->next->next;
1112 void add_def_site(struct lifetime *lt, int block, int iindex) {
1115 /* SSA <-> only one definition per lifetime! */
1116 _LT_ASSERT(lt->def == NULL);
1117 n = DNEW(struct site);
1124 struct lifetime *get_ss_lifetime(lsradata *ls, stackptr s) {
1127 if (s->varnum >= 0) { /* new stackslot lifetime */
1128 if (-ls->v_index - 1 >= ls->maxlifetimes) {
1129 printf("%i %i\n", -ls->v_index - 1, ls->maxlifetimes);
1131 _LT_ASSERT(-ls->v_index - 1 < ls->maxlifetimes);
1133 n = &(ls->lifetime[-ls->v_index - 1]);
1135 n->v_index = ls->v_index--;
1138 n->bb_last_use = -1;
1139 n->bb_first_def = -1;
1148 _LT_ASSERT(-s->varnum - 1 < ls->maxlifetimes);
1149 n = &(ls->lifetime[-s->varnum - 1]);
1156 #define lsra_new_stack(ls, s, block, instr) \
1157 if ((s)->varkind != ARGVAR) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
1158 void _lsra_new_stack(lsradata *ls, stackptr s, int block, int instr, int store)
1162 if (s->varkind == LOCALVAR) {
1163 /* _LT_ASSERT(0); */
1164 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
1168 n=get_ss_lifetime( ls, s );
1169 if (store == LSRA_STORE) {
1170 /* for LSRA_BB_[IN|OUT] do not add a def site, just add s to */
1172 add_def_site(n, block, instr);
1177 #define lsra_from_stack(ls, s, block, instr) \
1178 if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
1179 #define lsra_pop_from_stack(ls, s, block, instr) \
1180 if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
1181 void _lsra_from_stack(lsradata *ls, stackptr s, int block, int instr, int store)
1185 if (s->varkind == LOCALVAR) {
1186 /* _LT_ASSERT(0); */
1187 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
1188 } else /* if (s->varkind != ARGVAR) */ {
1189 if (s->varkind == STACKVAR ) {
1190 /* _LT_ASSERT(0); */
1191 printf("---------STACKVAR left over! \n");
1192 /* No STACKVARS possible with lsra! */
1193 s->varkind = TEMPVAR;
1197 n=get_ss_lifetime( ls, s );
1199 /* LSRA_POP -> invalidate Stackslot ?! */
1201 n->usagecount += ls->nesting[block];
1204 add_use_site(n, block, instr);
1208 void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr,
1213 n = &(ls->lifetime[ls->maxlifetimes + v_index]);
1215 if (n->type == -1) { /* new local lifetime */
1219 n->savedvar = SAVEDVAR;
1223 n->bb_last_use = -1;
1224 n->bb_first_def = -1;
1230 _LT_ASSERT(type == n->type);
1232 /* add access at (block, instr) to instruction list */
1233 /* remember last USE, so only write, if USE Field is undefined (==-1) */
1234 /* count store as use, too -> defined and not used vars would overwrite */
1236 if (store == LSRA_LOAD) {
1238 n->usagecount += ls->nesting[block];
1240 add_use_site(n, block, instr);
1242 if (store == LSRA_STORE) {
1243 add_def_site(n, block, instr);
1247 /***************************************************************************
1248 use sites: dead code elemination, LifenessAnalysis
1249 def sites: dead code elemination
1250 ***************************************************************************/
1251 void _scan_lifetimes(registerdata *rd, lsradata *ls, graphdata *gd,
1254 /* methodinfo *lm; */
1255 builtintable_entry *bte;
1259 int iindex, b_index;
1264 struct lifetime *lt;
1267 if (bptr->flags >= BBREACHED) {
1271 /* get instruction count for BB */
1272 iindex = bptr->icount - 1;
1273 /* regard not setup new BB with maybee just in and outstack */
1274 if (iindex < 0) iindex = 0;
1276 /* Regard phi_functions (Definition of target, Use of source) */
1277 for(i = 0; i < ls->max_vars; i++) {
1278 if (ls->phi[b_index][i] != NULL) {
1279 /* Phi Function for var i at b_index exists */
1280 v = ls->phi[b_index][i][0];
1281 _LT_ASSERT( v != ls->max_vars_with_indices);
1284 for(t = 0;(t < 5) && (rd->locals[v][t].type==-1); t++);
1286 /* Add definition of target add - phi index -1*/
1287 lsra_usage_local(ls, v, t, b_index, -i-1,
1289 /* Add Use of sources */
1290 for (j = 1; j <= graph_get_num_predecessor(gd, b_index);
1292 if (ls->phi[b_index][i][j] != ls->max_vars_with_indices)
1293 lsra_usage_local(ls, ls->phi[b_index][i][j], t,
1294 b_index, -i-1, LSRA_LOAD);
1297 /* Interface Stackslot */
1298 /* Add definition of target */
1299 lt = &(ls->lifetime[-v-1]);
1300 add_def_site(lt, b_index, -i-1);
1301 /* add use of sources */
1302 for (j = 1; j <= graph_get_num_predecessor(gd, b_index);
1304 if (ls->phi[b_index][i][j] != ls->max_vars_with_indices)
1306 lt = &(ls->lifetime[-ls->phi[b_index][i][j]-1]);
1307 add_use_site(lt, b_index, -i-1);
1314 src = bptr->instack;
1315 if (bptr->type != BBTYPE_STD) {
1316 #ifdef LT_DEBUG_CHECK
1318 log_text("No Incoming Stackslot for Exception/Subroutine BB\n");
1322 _LT_ASSERT(src != NULL);
1323 lsra_new_stack(ls, src, b_index, 0);
1324 if (src->varkind == STACKVAR)
1325 src->varkind = TEMPVAR;
1328 for (;src != NULL; src=src->prev) {
1329 /* no ARGVAR possible at BB Boundaries with LSRA! */
1330 /* -> change to TEMPVAR */
1332 if (src->varkind == ARGVAR ) {
1333 src->varkind = TEMPVAR;
1334 /* On Architectures with own return registers a return */
1335 /* stackslot is marked as varkind=ARGVAR with varnum=-1 */
1336 /* but for lsra a varkind==TEMPVAR, varnum=-1 would mean, */
1337 /* that already a lifetime was allocated! */
1338 if (src->varnum < 0) src->varnum = 0;
1340 else if (src->varkind == LOCALVAR )
1341 /* only allowed for topmost ss at sbr or exh entries! */
1342 { log_text("LOCALVAR at basicblock instack\n"); exit(1); }
1344 /* no Interfaces (STACKVAR) at BB Boundaries with LSRA! */
1345 /* -> change to TEMPVAR */
1346 if (src->varkind == STACKVAR )
1347 src->varkind = TEMPVAR;
1348 /* _lsra_new_stack(ls, src, b_index, 0, LSRA_BB_IN); */
1349 _lsra_from_stack(ls, src, b_index, 0, LSRA_BB_OUT);
1352 /* Should not be necessary to check out stackslots, too */
1353 /* either they are identical to the instacks or handled */
1354 /* by their phi functions */
1355 src = bptr->outstack;
1356 for (;src != NULL; src=src->prev) {
1357 if (src->varkind == ARGVAR )
1358 { log_text("ARGVAR at basicblock outstack\n"); exit(1); }
1359 else if (src->varkind == LOCALVAR )
1360 { log_text("LOCALVAR at basicblock outstack\n"); exit(1); }
1362 /* no Interfaces at BB Boundaries with LSRA! */
1363 /* -> change to TEMPVAR */
1364 if (src->varkind == STACKVAR )
1365 src->varkind = TEMPVAR;
1366 /* _lsra_from_stack(ls, src, b_index, iindex, LSRA_BB_OUT); */
1370 if (bptr->iinstr != NULL) {
1371 /* set iptr to last instruction of BB */
1372 iptr = bptr->iinstr + iindex;
1376 for (;iindex >= 0; iindex--, iptr--) {
1377 /* Get source and destination Stack for the current */
1378 /* instruction. Destination stack is available as iptr->dst */
1380 /* source stack is either the destination stack of the previos*/
1381 /* instruction, or the basicblock instack for the */
1382 /* first instruction */
1383 if (iindex) /* != 0 is > 0 here, since iindex ist always >= 0 */
1393 /* local read (return adress) */
1394 lsra_usage_local(ls, iptr->op1, TYPE_ADR, b_index, iindex,
1398 /* case ICMD_ELSE_ICONST: */
1399 case ICMD_CHECKNULL:
1403 case ICMD_PUTSTATICCONST:
1404 case ICMD_INLINE_START:
1405 case ICMD_INLINE_END:
1406 case ICMD_INLINE_GOTO:
1410 /* local = local+<const> */
1411 lsra_usage_local(ls, iptr->op1, TYPE_INT, b_index, iindex,
1413 lsra_usage_local(ls, iptr->val._i.op1_t, TYPE_INT, b_index,
1414 iindex, LSRA_STORE);
1417 /* pop 0 push 1 const: const->stack */
1423 /* new stack slot */
1424 lsra_new_stack(ls, dst, b_index, iindex);
1427 /* pop 0 push 1 load: local->stack */
1433 if (dst->varkind != LOCALVAR) {
1434 /* local->value on stack */
1435 lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD,
1436 b_index, iindex, LSRA_LOAD);
1437 lsra_new_stack(ls, dst, b_index, iindex);
1438 } else /* if (dst->varnum != iptr->op1) */ {
1439 /* local -> local */
1440 lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD,
1441 b_index, iindex,LSRA_LOAD);
1442 lsra_usage_local(ls, dst->varnum, opcode - ICMD_ILOAD,
1443 b_index, iindex, LSRA_STORE);
1449 /* Stack(arrayref,index)->stack */
1460 lsra_from_stack(ls, src, b_index, iindex);
1461 /* stack->arrayref */
1462 lsra_from_stack(ls, src->prev, b_index, iindex);
1463 /* arrayref[index]->stack */
1464 lsra_new_stack(ls, dst, b_index, iindex);
1468 /* stack(arrayref,index,value)->arrayref[index]=value */
1479 lsra_from_stack(ls, src,b_index, iindex);
1480 lsra_from_stack(ls, src->prev, b_index, iindex);
1481 lsra_from_stack(ls, src->prev->prev, b_index, iindex);
1484 /* pop 1 push 0 store: stack -> local */
1490 if (src->varkind != LOCALVAR) {
1491 lsra_from_stack(ls, src, b_index, iindex);
1492 lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE,
1493 b_index, iindex, LSRA_STORE);
1494 } else /* if (src->varnum != iptr->op1) */ {
1495 lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE,
1496 b_index, iindex, LSRA_STORE);
1497 lsra_usage_local(ls, src->varnum, opcode-ICMD_ISTORE,
1498 b_index, iindex, LSRA_LOAD);
1503 case ICMD_POP: /* throw away a stackslot */
1504 /* TODO: check if used anyway (DUP...) and change codegen */
1505 /* to ignore this stackslot */
1507 lsra_pop_from_stack(ls, src, b_index, iindex);
1516 case ICMD_ARETURN: /* stack(value) -> [empty] */
1518 case ICMD_ATHROW: /* stack(objref) -> undefined */
1520 case ICMD_PUTSTATIC: /* stack(value) -> static_field */
1521 case ICMD_PUTFIELDCONST:
1523 /* pop 1 push 0 branch */
1524 case ICMD_IFNULL: /* stack(value) -> branch? */
1525 case ICMD_IFNONNULL:
1541 /* pop 1 push 0 table branch */
1542 case ICMD_TABLESWITCH:
1543 case ICMD_LOOKUPSWITCH:
1545 case ICMD_MONITORENTER:
1546 case ICMD_MONITOREXIT:
1547 lsra_from_stack(ls, src, b_index, iindex);
1551 case ICMD_POP2: /* throw away 2 stackslots */
1553 /* TODO: check if used anyway (DUP...) and change codegen */
1554 /* to ignore this stackslot */
1555 lsra_pop_from_stack(ls, src, b_index, iindex);
1556 lsra_pop_from_stack(ls, src->prev, b_index, iindex);
1560 /* pop 2 push 0 branch */
1562 case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
1563 case ICMD_IF_ICMPNE:
1564 case ICMD_IF_ICMPLT:
1565 case ICMD_IF_ICMPGE:
1566 case ICMD_IF_ICMPGT:
1567 case ICMD_IF_ICMPLE:
1569 case ICMD_IF_LCMPEQ:
1570 case ICMD_IF_LCMPNE:
1571 case ICMD_IF_LCMPLT:
1572 case ICMD_IF_LCMPGE:
1573 case ICMD_IF_LCMPGT:
1574 case ICMD_IF_LCMPLE:
1576 case ICMD_IF_ACMPEQ:
1577 case ICMD_IF_ACMPNE:
1580 case ICMD_PUTFIELD: /* stack(objref,value) -> objref = value */
1582 case ICMD_IASTORECONST:
1583 case ICMD_LASTORECONST:
1584 case ICMD_AASTORECONST:
1585 case ICMD_BASTORECONST:
1586 case ICMD_CASTORECONST:
1587 case ICMD_SASTORECONST:
1588 lsra_from_stack(ls, src, b_index, iindex);
1589 lsra_from_stack(ls, src->prev, b_index, iindex);
1592 /* pop 0 push 1 dup */
1594 /* src == dst->prev */
1595 /* ---------------- */
1598 /* Add the use site for src==dst */
1599 lsra_from_stack(ls, src, b_index, iindex);
1601 lsra_new_stack(ls, dst, b_index, iindex);
1605 /* pop 0 push 2 dup */
1607 /* src == dst->prev->prev */
1608 /* src->prev == dst->prev->prev->prev */
1609 /* ---------------- */
1611 /* src->prev -> dst->prev */
1612 /* src & src->prev "continue" living -> so no conflicts */
1613 /* with dst and dst->prec possible */
1615 /* add the use site for src == dst->prev->prev */
1616 lsra_from_stack(ls, src, b_index, iindex);
1617 /* add the use site for src->prev == dst->prev->prev->prev */
1618 lsra_from_stack(ls, src->prev, b_index, iindex);
1621 lsra_new_stack(ls, dst->prev, b_index, iindex);
1622 lsra_new_stack(ls, dst, b_index, iindex);
1626 /* pop 2 push 3 dup */
1629 /* src->prev -> dst->prev */
1630 /* src -> dst->prev->prev */
1631 /* !!!!!!!!!!!!!!!!!!!!!!!!!!!! */
1632 /* Copy Conflicts possible! */
1633 /* -> instack [ t1 t0 ] */
1634 /* -> outstack[ t0 t1 t3 ] */
1635 /* -> t1->t0, t0->t1, t1->t3 !! */
1636 /* -> Remove src->prev on iindex+1 instead of iindex! */
1637 lsra_from_stack(ls, src, b_index, iindex);
1638 lsra_from_stack(ls, src->prev, b_index, iindex);
1639 lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
1640 lsra_new_stack(ls, dst->prev, b_index, iindex);
1641 lsra_new_stack(ls, dst, b_index, iindex);
1645 /* pop 3 push 4 dup */
1648 /* src -> dst->prev->prev->prev */
1649 /* src->prev -> dst->prev */
1650 /* src->prev->prev -> dst->prev->prev */
1651 /* Conflicts possible! -> remove srces at iindex + 1 */
1652 lsra_from_stack(ls, src,b_index, iindex);
1653 lsra_from_stack(ls, src->prev, b_index, iindex);
1654 lsra_from_stack(ls, src->prev->prev, b_index, iindex);
1655 lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
1656 lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
1657 lsra_new_stack(ls, dst->prev, b_index, iindex);
1658 lsra_new_stack(ls, dst, b_index, iindex);
1662 /* pop 3 push 5 dup */
1665 /* src -> dst->prev->prev->prev */
1666 /* src->prev -> dst->prev->prev->prev->prev */
1667 /* src->prev -> dst->prev */
1668 /* src->prev->prev -> dst->prev->prev */
1669 /* Conflicts possible! -> remove srces at iindex + 1 */
1670 lsra_from_stack(ls, src, b_index, iindex);
1671 lsra_from_stack(ls, src->prev, b_index, iindex);
1672 lsra_from_stack(ls, src->prev->prev, b_index, iindex);
1673 lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index,
1675 lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
1676 lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
1677 lsra_new_stack(ls, dst->prev, b_index, iindex);
1678 lsra_new_stack(ls, dst, b_index, iindex);
1683 /* pop 4 push 6 dup */
1686 /* src -> dst->prev->prev->prev->prev */
1687 /* src->prev -> dst->prev->prev->prev->prev->prev */
1688 /* src->prev -> dst->prev */
1689 /* src->prev->prev -> dst->prev->prev */
1690 /* src->prev->prev->prev -> dst->prev->prev->prev */
1691 /* Conflicts possible! -> remove srcs at iindex + 1 */
1692 lsra_from_stack(ls, src, b_index, iindex);
1693 lsra_from_stack(ls, src->prev, b_index, iindex);
1694 lsra_from_stack(ls, src->prev->prev, b_index, iindex);
1695 lsra_from_stack(ls, src->prev->prev->prev, b_index, iindex);
1696 lsra_new_stack(ls, dst->prev->prev->prev->prev->prev,
1698 lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index,
1700 lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
1701 lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
1702 lsra_new_stack(ls, dst->prev, b_index, iindex);
1703 lsra_new_stack(ls, dst, b_index, iindex);
1707 /* pop 2 push 2 swap */
1709 /* src -> dst->prev */
1710 /* src->prev -> dst */
1711 /* Conflicts possible -> remove src at iindex + 1 */
1712 lsra_from_stack(ls, src, b_index, iindex);
1713 lsra_from_stack(ls, src->prev, b_index, iindex);
1714 lsra_new_stack(ls, dst->prev, b_index, iindex);
1715 lsra_new_stack(ls, dst, b_index, iindex);
1752 lsra_from_stack(ls, src, b_index, iindex);
1753 lsra_from_stack(ls, src->prev, b_index, iindex);
1754 lsra_new_stack(ls, dst, b_index, iindex);
1758 lsra_from_stack(ls, src, b_index, iindex);
1759 lsra_from_stack(ls, src->prev,b_index,iindex);
1760 lsra_new_stack(ls, dst, b_index, iindex);
1777 lsra_from_stack(ls, src, b_index, iindex);
1778 lsra_from_stack(ls, src->prev, b_index, iindex);
1779 lsra_new_stack(ls, dst, b_index, iindex);
1783 case ICMD_LADDCONST:
1784 case ICMD_LSUBCONST:
1785 case ICMD_LMULCONST:
1789 case ICMD_LANDCONST:
1791 case ICMD_LXORCONST:
1792 case ICMD_LSHLCONST:
1793 case ICMD_LSHRCONST:
1794 case ICMD_LUSHRCONST:
1796 case ICMD_IADDCONST:
1797 case ICMD_ISUBCONST:
1798 case ICMD_IMULCONST:
1802 case ICMD_IANDCONST:
1804 case ICMD_IXORCONST:
1805 case ICMD_ISHLCONST:
1806 case ICMD_ISHRCONST:
1807 case ICMD_IUSHRCONST:
1809 /* case ICMD_IFEQ_ICONST: */
1810 /* case ICMD_IFNE_ICONST: */
1811 /* case ICMD_IFLT_ICONST: */
1812 /* case ICMD_IFGE_ICONST: */
1813 /* case ICMD_IFGT_ICONST: */
1814 /* case ICMD_IFLE_ICONST: */
1819 case ICMD_INT2SHORT:
1837 case ICMD_CHECKCAST:
1838 lsra_from_stack(ls, src, b_index, iindex);
1839 lsra_new_stack(ls, dst, b_index, iindex);
1842 case ICMD_ARRAYLENGTH:
1843 case ICMD_INSTANCEOF:
1846 case ICMD_ANEWARRAY:
1849 lsra_from_stack(ls, src, b_index, iindex);
1850 lsra_new_stack(ls, dst, b_index, iindex);
1854 case ICMD_GETSTATIC:
1857 lsra_new_stack(ls, dst, b_index, iindex);
1860 /* pop many push any */
1862 case ICMD_INVOKESTATIC:
1863 case ICMD_INVOKESPECIAL:
1864 case ICMD_INVOKEVIRTUAL:
1865 case ICMD_INVOKEINTERFACE:
1866 INSTRUCTION_GET_METHODDESC(iptr,md);
1869 lsra_from_stack(ls, src, b_index, iindex);
1872 if (md->returntype.type != TYPE_VOID)
1873 lsra_new_stack(ls, dst, b_index, iindex);
1881 lsra_from_stack(ls, src, b_index, iindex);
1884 if (md->returntype.type != TYPE_VOID)
1885 lsra_new_stack(ls, dst, b_index, iindex);
1888 case ICMD_MULTIANEWARRAY:
1891 lsra_from_stack(ls, src, b_index, iindex);
1894 lsra_new_stack(ls, dst, b_index, iindex);
1899 throw_cacao_exception_exit(string_java_lang_InternalError,
1900 "Unknown ICMD %d during register allocation", iptr->opc);
1902 } /* for (;iindex >= 0; iindex--, iptr--) */
1903 } /* if (bptr->flags >= BBREACHED) */
1904 } /* scan_lifetimes */
1908 /*******************************************************************************
1909 true, if i dominates j
1910 *******************************************************************************/
1911 bool dominates(dominatordata *dd, int i, int j) {
1912 bool dominates = false;
1914 while(!dominates && (dd->idom[j] != -1)) {
1915 dominates = (i == dd->idom[j]);
1921 /*******************************************************************************
1924 Look for loops in the CFG and set the nesting depth of all Basicblocks in
1927 The Loop Header BB h is an element of DF[n] for all Basicblocks n of this loop
1928 So Look through all x element of DF[n] for a backedge n->x. If this
1929 exists, increment nesting for all n with x in DF[n]
1930 *******************************************************************************/
1931 void lt_get_nesting(lsradata *ls, graphdata *gd, dominatordata *dd) {
1933 bitvector loop_header;
1934 worklist *loop, *loop1;
1944 /* init nesting to 1 and get loop_headers */
1945 ls->nesting = DMNEW(long, ls->basicblockcount);
1946 loop_header = bv_new(ls->basicblockcount);
1947 loop = wl_new(ls->basicblockcount);
1949 for(i = 0; i < ls->basicblockcount; i++) {
1952 for(succ = graph_get_first_successor(gd, i, &iter); succ != -1;
1953 succ = graph_get_next(&iter)) {
1954 for (j = 0; j < dd->num_DF[i]; j++) {
1955 if (succ == dd->DF[i][j]) {
1956 /* There is an edge from i to DF[i][j] */
1958 /* look if DF[i][j] dominates i -> backedge */
1959 if (dominates(dd, dd->DF[i][j], i)) {
1960 /* this edge is a backedge */
1961 /* -> DF[i][j] is a loop header */
1962 _LT_CHECK_BOUNDS(dd->DF[i][j], 0, ls->basicblockcount);
1963 if (!bv_get_bit(loop_header, dd->DF[i][j])) {
1964 /* new loop_header found */
1966 bv_set_bit(loop_header, dd->DF[i][j]);
1967 ls->nesting[dd->DF[i][j]] = 10;
1969 wl_add(loop, dd->DF[i][j]);
1976 loop_parent = DMNEW(int , ls->basicblockcount);
1977 loop1 = wl_new(ls->basicblockcount);
1979 /* look for direct parents of nested loopheaders */
1980 /* (DF[loop_header[i]] has the element loop_header[j] with i != j */
1981 /* TODO: BULLSHIT:unfortunately not such an easy condition ;( */
1982 while(!wl_is_empty(loop)) {
1986 loop_parent[lh] = -1;
1988 for (j = 0; j < dd->num_DF[lh]; j++) {
1989 _LT_CHECK_BOUNDS(dd->DF[lh][j], 0, ls->basicblockcount);
1990 if (lh != dd->DF[lh][j]) {
1991 if (bv_get_bit(loop_header, dd->DF[lh][j])) {
1992 #ifdef LT_DEBUG_VERBOSE
1994 if (loop_parent[lh] != -1)
1995 printf("Warning: LoopHeader has more than one parent\n");
1997 /* _LT_ASSERT( loop_parent[lh] == -1); */
1998 loop_parent[lh] = dd->DF[lh][j];
2004 /* create nesting for loopheaders */
2005 while(!wl_is_empty(loop1)) {
2007 for (lh_p = lh; lh_p != -1; lh_p = loop_parent[lh_p]) {
2008 ls->nesting[lh] *= 10;
2013 /* copy loopheader nesting to loop body */
2014 for(i = 0; i < ls->basicblockcount; i++) {
2015 if (!bv_get_bit(loop_header, i)) {
2016 /* Do not touch the nesting of a loopheader itself */
2017 for(j = 0; j < dd->num_DF[i]; j++) {
2018 _LT_CHECK_BOUNDS(dd->DF[i][j], 0, ls->basicblockcount);
2019 if (bv_get_bit(loop_header, dd->DF[i][j])) {
2020 /* DF[i][j] is a loop header -> copy nesting for i */
2021 #ifdef LT_DEBUG_VERBOSE
2023 if (ls->nesting[i] != 1)
2024 printf("Warning: More than one loopheader for one BB\n");
2025 /* _LT_ASSERT(ls->nesting[i] == 1); */
2027 ls->nesting[i] = ls->nesting[dd->DF[i][j]];
2033 #ifdef LT_DEBUG_VERBOSE
2034 if (compileverbose) {
2035 printf("Num Loops: %3i\n",num_loops);
2036 for(i = 0; i < ls->basicblockcount; i++)
2037 printf("(BB%3i->N%3li) ",i, ls->nesting[i]);
2046 * These are local overrides for various environment variables in Emacs.
2047 * Please do not remove this and leave it at the end of the file, where
2048 * Emacs will automagically detect them.
2049 * ---------------------------------------------------------------------
2052 * indent-tabs-mode: t