src/vm/jit/lsra.inc

   1 /* src/vm/jit/lsra.inc - linear scan register allocator
   2
   3    Copyright (C) 1996-2005 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
   7
   8    This file is part of CACAO.
   9
  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.
  14
  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.
  19
  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
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Ullrich
  28
  29    $Id: lsra.inc 2297 2005-04-13 12:50:07Z christian $
  30
  31 */
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34
  35 #include "mm/memory.h"
  36 #include "vm/options.h"
  37 #include "vm/jit/lsra.h"
  38 #include "vm/jit/reg.h"
  39 #include "vm/statistics.h"
  40
  41 bool lsra(methodinfo *m, codegendata *cd, registerdata *rd, t_inlining_globals *id)
  42 {
  43
  44         lsradata *ls;
  45 #if defined(STATISTICS)
  46         int locals_start;
  47         int i,j;
  48 #endif
  49 #if defined(LSRA_DEBUG) || defined(LSRA_LEAF)
  50         char name[1256], name1[1256];
  51 #endif
  52
  53 #if defined(LSRA_DEBUG)
  54         int b_index;
  55         stackptr in,out;
  56         int      ind, outd;
  57
  58         b_index = 0;
  59         while (b_index < m->basicblockcount ) {
  60
  61                 if (m->basicblocks[b_index].flags >= BBREACHED) {
  62
  63                         in=m->basicblocks[b_index].instack;
  64                         ind=m->basicblocks[b_index].indepth;
  65                         for (;ind != 0;in=in->prev, ind--) {
  66                                 if (in->varkind == ARGVAR) printf("ARGVAR in instack: \n"); /*ARGVAR in instack ok*/
  67                                 if (in->varkind == LOCALVAR) printf("LOCALVAR in instack\n");
  68                         }
  69                         out=m->basicblocks[b_index].outstack;
  70                         outd=m->basicblocks[b_index].outdepth;
  71                         for (;outd != 0;out=out->prev, outd--) {
  72                                 if (out->varkind == ARGVAR) panic("ARGVAR in outstack\n");
  73                                 if (out->varkind == LOCALVAR) panic("LOCALVAR in outstack\n");
  74                         }
  75                 }
  76                         b_index++;
  77         }
  78 #endif
  79
  80 #if defined(LSRA_DEBUG) || defined(LSRA_LEAF)
  81         utf_sprint(name, m->class->name);
  82         utf_sprint(name1, m->name);
  83         strcat(name, ".");
  84         strcat(name, name1);
  85         utf_sprint(name1, m->descriptor);
  86         strcat(name, name1);
  87
  88 #ifndef LSRA_LEAF
  89         printf("/******************************************************/\n");
  90 #endif
  91 #ifdef LSRA_LEAF
  92         if (m->isleafmethod)
  93 #endif
  94                 printf("LSRA Start for %s opt_from: %i opt_to: %i\n", name, opt_from, opt_to);
  95 #ifndef LSRA_LEAF
  96         if (strcmp(name,"java/lang/ClassLoader.defaultGetSystemClassLoader()Ljava/lang/ClassLoader;")==0) {
  97                 printf("-------------------\n");
  98         }
  99         if (m->isleafmethod)
 100                 printf("**Leafmethod**\n");
 101 #endif
 102 #endif
 103
 104         ls=DNEW(lsradata);
 105         lsra_init(m, cd, id, ls);
 106
 107 #if 0
 108 #if defined(LSRA_USES_REG_RES)
 109         for (i=opt_from; i<=opt_to; i++) {
 110                 icmd_uses_reg_res[i][0]=S|D|YES;
 111                 icmd_uses_reg_res[i][1]=S|D|YES;
 112                 icmd_uses_reg_res[i][2]=S|D|YES;
 113                 icmd_uses_reg_res[i][3]=REG_NULL;
 114         }
 115 #endif
 116 #endif
 117
 118
 119         if (!lsra_setup(m, cd, rd, ls))
 120                 return false;
 121
 122
 123 #if defined(STATISTICS)
 124         /* find conflicts between locals for statistics */
 125         if (opt_stat) {
 126                 /* local Variable Lifetimes are at the end of the lifetime array and have v_index >= 0 */
 127                 for (locals_start = ls->lifetimecount-1; (locals_start >=0) && (ls->lifetime[ls->lt_used[locals_start]].v_index >= 0); locals_start--);
 128                 for (i=locals_start + 1; i < ls->lifetimecount; i++)
 129                         for (j=i+1; j < ls->lifetimecount; j++)
 130                                 if ( !((ls->lifetime[ls->lt_used[i]].i_end < ls->lifetime[ls->lt_used[j]].i_start) || (ls->lifetime[ls->lt_used[j]].i_end<ls->lifetime[ls->lt_used[i]].i_start)) )
 131                                         count_locals_conflicts += 2;
 132          }
 133 #endif
 134         /* Run LSRA */
 135         lsra_main(m, ls, rd, cd);
 136
 137         return true;
 138 }
 139
 140 void lsra_DFS_(lsradata *ls, bool *mark, int bblock, int *n) {
 141         struct _list *p;
 142
 143         if (!mark[bblock])
 144         {
 145                 mark[bblock] = true;
 146                 for (p=ls->pred[bblock]; p != NULL; p=p->next)
 147                         lsra_DFS_(ls, mark, p->value, n);
 148                 ls->sorted[*n]=bblock;
 149                 *n=*n-1;
 150         }
 151 }
 152
 153 void lsra_DFS(methodinfo *m, lsradata *ls) {
 154         bool *mark;
 155         int i,n;
 156
 157         mark=DMNEW(bool, m->basicblockcount);
 158         n=m->basicblockcount;
 159
 160         for (i=0; i <= m->basicblockcount; i++) mark[i]=false;
 161
 162         lsra_DFS_(ls, mark, m->basicblockcount, &n);
 163
 164 }
 165
 166 void lsra_DFS_2(methodinfo *m, lsradata *ls) {
 167         int *stack;
 168         int *visited;
 169         int stack_top;
 170         bool not_finished;
 171         int i,p;
 172     struct _list *succ;
 173
 174         stack = DMNEW( int, m->basicblockcount + 1);
 175         visited = DMNEW( bool, m->basicblockcount + 1);
 176         for (i = 0; i <= m->basicblockcount; i++) {
 177                 visited[i] = 0;
 178                 ls->sorted[i]=-1;
 179                 ls->sorted_rev[i]=-1;
 180         }
 181
 182     stack[0] = 0; /* start with Block 0 */
 183         stack_top = 1;
 184         visited[0] = ls->num_pred[0]; /* Start Block is handled right and can be put in sorted */
 185         p = 0; /*m->basicblockcount;*/
 186         not_finished = true;
 187         while (not_finished) {
 188                 while (stack_top != 0) {
 189                         stack_top--;
 190                         i = stack[stack_top];
 191                         ls->sorted[p]=i;
 192                         p++; /*--;*/
 193                         for (succ = ls->succ[i]; succ != NULL; succ = succ->next) {
 194                                 visited[succ->value]++;
 195                                 if (visited[succ->value] == ls->num_pred[succ->value]) {
 196                                         /* push the node on the stack, only if all ancestors have been visited */
 197                                         stack[stack_top] = succ->value;
 198                                         stack_top++;
 199                                 }
 200                         }
 201                 }
 202                 not_finished = false;
 203                 for (i=1; i <= m->basicblockcount; i++) {
 204                         /* search for visited blocks, which have not reached the num_pred */
 205                         /* and put them on the stack -> happens with backedges */
 206                         if ((visited[i] != 0) && (visited[i] < ls->num_pred[i])) {
 207                                 stack[stack_top] = i;
 208                                 stack_top++;
 209                                 visited[i] = ls->num_pred[i];
 210                                 not_finished=true;
 211                                 break;
 212                         }
 213                 }
 214         }
 215 }
 216
 217 void lsra_get_backedges( methodinfo *m, lsradata *ls) {
 218         struct _list **next, *s;
 219         struct _backedge *n;
 220         struct _backedge *_backedges;
 221         int i,j;
 222
 223         _backedges = NULL;
 224
 225         /* todofirst remove artificial end basicblock from ls->sorted, succ and pred */
 226     j=-1;
 227         for (i=0; i < m->basicblockcount; i++) {
 228                 for (next=&(ls->succ[i]); *next != NULL; next=&((*next)->next)) {
 229                         if ( (*next)->value == m->basicblockcount ) { /* artificial end bb found */
 230                                 *next = (*next)->next;
 231                                 if (*next == NULL) break;
 232                         }
 233                 }
 234                 for (next=&(ls->pred[i]); *next != NULL; next=&((*next)->next)) {
 235                         if ( (*next)->value == m->basicblockcount ) { /* artificial end bb found */
 236                                 *next = (*next)->next;
 237                                 if (*next == NULL) break;
 238                         }
 239                 }
 240                 if (j==-1)
 241                         if (ls->sorted[i] == m->basicblockcount) j=i;
 242         }
 243         if (j!=-1)
 244                 for (i=j+1; i <= m->basicblockcount; i++)
 245                         ls->sorted[i-1]=ls->sorted[i];
 246         for (i=0; i < m->basicblockcount; i++)
 247                 if (ls->sorted[i] != -1)
 248                         ls->sorted_rev[ls->sorted[i]]=i;
 249         /* now look for backedges */
 250         ls->backedge_count = 0;
 251         for(i=0; i < m->basicblockcount; i++) {
 252                 if (ls->sorted[i] != -1)
 253                         for(s=ls->succ[ls->sorted[i]]; s != NULL; s=s->next) {
 254                                 if (i >= ls->sorted_rev[s->value]) {
 255                                         n=DNEW(struct _backedge);
 256                                         n->start = max(i, ls->sorted_rev[s->value]);
 257                                         n->end = min(i, ls->sorted_rev[s->value]);
 258                                         n->next = _backedges;
 259                                         _backedges = n;
 260                                         ls->backedge_count++;
 261 /*                                      printf("Backedge: %i %i\n", ls->sorted[i], s->value); */
 262                                 }
 263                         }
 264         }
 265         /* put _backedges in ls->backedge array */
 266         ls->backedge = DMNEW(struct _backedge *, ls->backedge_count);
 267         for (n=_backedges, i=0; n != NULL; n=n->next, i++)
 268                 ls->backedge[i] = n;
 269         /* union backedges? */
 270         /* - sort backedge by increasing start: */
 271 /*      printf("unsorted: \n"); */
 272 /*      for (i=0; i < ls->backedge_count; i++) */
 273 /*              printf("Backedge: %i - %i, %i - %i\n",ls->sorted[ls->backedge[i]->start],ls->sorted[ls->backedge[i]->end],ls->backedge[i]->start, ls->backedge[i]->end); */
 274         for (i=0; i < ls->backedge_count; i++)
 275                 for (j=i+1; j < ls->backedge_count; j++)
 276                         if (ls->backedge[i]->start > ls->backedge[j]->start) { /* -> swap */
 277                                 n=ls->backedge[i];
 278                                 ls->backedge[i]=ls->backedge[j];
 279                                 ls->backedge[j]=n;
 280                         }
 281         /* create ls->nesting */
 282         for (i=0; i < ls->backedge_count; i++)
 283                 for (j=ls->backedge[i]->end; j<=ls->backedge[i]->start; j++)
 284                         ls->nesting[j]*=10;
 285 #ifdef LSRA_DEBUG
 286         printf("sorted: \n");
 287         for (i=0; i < ls->backedge_count; i++)
 288                 printf("Backedge: %i - %i, %i - %i\n",ls->sorted[ls->backedge[i]->start],ls->sorted[ls->backedge[i]->end],ls->backedge[i]->start, ls->backedge[i]->end);
 289         printf("Nesting Level \n");
 290         for (i=0; i<m->basicblockcount; i++) printf(" %3li", ls->nesting[i]);
 291         printf("\n");
 292 #endif
 293         /* - merge overlapping backedges */
 294         for (i=0; i < ls->backedge_count-1; i++)
 295                 if (ls->backedge[i]->start >= ls->backedge[i+1]->end) {/* overlapping -> merge */
 296 /*                      ls->backedge[i+1]->start = ls->backedge[i]->start; */
 297                         ls->backedge[i+1]->end = min (ls->backedge[i+1]->end, ls->backedge[i]->end);
 298                         ls->backedge[i] = NULL;
 299                 }
 300 #ifdef LSRA_DEBUG
 301         printf("merged: \n");
 302         for (i=0; i < ls->backedge_count; i++)
 303                 if (ls->backedge[i] != NULL)
 304                         printf("Backedge: %i - %i, %i - %i\n",ls->sorted[ls->backedge[i]->start],ls->sorted[ls->backedge[i]->end],ls->backedge[i]->start, ls->backedge[i]->end);
 305 #endif
 306         /* - remove backedge[] == NULL from array */
 307
 308         for ( j = ls->backedge_count -1; ((j>=0) && ( ls->backedge[j] == NULL)); j--);
 309         i=j;
 310         while (i >= 0) {
 311                 if (ls->backedge[i] == NULL) { /* swap be[i] mit be[j] */
 312                         n=ls->backedge[j];
 313                         ls->backedge[j] = ls->backedge[i];
 314                         ls->backedge[i] = n;
 315                         i--;
 316                         j--;
 317                         ls->backedge_count--;
 318                 } else i--;
 319         }
 320 #ifdef LSRA_DEBUG
 321         printf("ready: \n");
 322         for (i=0; i < ls->backedge_count; i++)
 323                 printf("Backedge: %i - %i, %i - %i\n",ls->sorted[ls->backedge[i]->start],ls->sorted[ls->backedge[i]->end],ls->backedge[i]->start, ls->backedge[i]->end);
 324 #endif
 325 }
 326
 327 void lsra_add_cfg( methodinfo *m, lsradata *ls, int from, int to) {
 328         struct _list *n;
 329
 330         for (;(to < m->basicblockcount) && (m->basicblocks[to].flags < BBREACHED); to++);
 331
 332         for (n=ls->succ[from]; (n!= NULL) && (n->value != to); n=n->next);
 333         if (n != NULL) return; /* edge from->to already existing */
 334
 335         n=DNEW(struct _list);
 336
 337         n->value=to;
 338         n->next=ls->succ[from];
 339         ls->succ[from]=n;
 340
 341         n=DNEW(struct _list);
 342         n->value=from;
 343         n->next=ls->pred[to];
 344         ls->pred[to]=n;
 345         ls->num_pred[to]++;
 346 }
 347
 348 void lsra_add_exceptions(methodinfo *m, codegendata *cd, lsradata *ls) {
 349         int i;
 350
 351         /* add cfg edges from all bb of a try block to the start of the according exception handler */
 352         /* to ensure the right order after depthfirst search */
 353         exceptiontable *ex;
 354         ex=cd->exceptiontable;
 355 #ifdef LSRA_DEBUG
 356         printf("ExTable(%i): ", cd->exceptiontablelength);
 357 #endif
 358
 359         for (; ex != NULL; ex = ex->down) {
 360
 361 #ifdef LSRA_DEBUG
 362                 printf("[%i-%i]->%i ",ex->start->debug_nr, ex->end->debug_nr,ex->handler->debug_nr);
 363                 if (ex->handler->debug_nr >= m->basicblockcount)
 364                         panic("Exceptionhandler Basicblocknummer invalid\n");
 365                 if (m->basicblocks[ex->handler->debug_nr].flags < BBREACHED)
 366                         panic("Exceptionhandler Basicblocknummer not reachable\n");
 367                 if (ex->start->debug_nr > ex->end->debug_nr)
 368                         panic("Guarded Area starts after its end\n");
 369 #endif
 370                 /* loop all valid Basic Blocks of the guarded area and add CFG edges to the appropriate handler */
 371                 for (i=ex->start->debug_nr; (i <= ex->end->debug_nr) && (i < m->basicblockcount); i++)
 372                         if (m->basicblocks[i].flags >= BBREACHED)
 373                                 lsra_add_cfg(m, ls, i, ex->handler->debug_nr);
 374         }
 375 #ifdef LSRA_DEBUG
 376         printf("\n");
 377 #endif
 378 }
 379
 380 void lsra_add_jsr( methodinfo *m, lsradata *ls, int from, int to) {
 381         struct _sbr *sbr, *n;
 382         struct _list *ret;
 383
 384         for (; (to < m->basicblockcount) && (m->basicblocks[to].flags < BBREACHED); to++);
 385 #ifdef LSRA_DEBUG
 386         if (to == m->basicblockcount)
 387                 panic("Invalid subroutine start index\n");
 388 #endif
 389
 390         lsra_add_cfg(m, ls, from, to);
 391
 392         for (from++; (from < m->basicblockcount) && (m->basicblocks[from].flags < BBREACHED); from++);
 393 #ifdef LSRA_DEBUG
 394         if (from == m->basicblockcount)
 395                 panic("Invalid return basic block index for jsr\n");
 396 #endif
 397
 398         /* add subroutine info in ls->sbr.next */
 399
 400         /* search for right place to insert */
 401         for (sbr = &(ls->sbr); (sbr->next != NULL) && (sbr->next->header < to); sbr=sbr->next);
 402
 403         if ((sbr->next!= NULL) && (sbr->next->header == to)) {
 404                 /* Entry for this sub already exist */
 405                 sbr = sbr->next;
 406         } else {
 407                 /* make new Entry and insert it in ls->sbr.next */
 408                 n = DNEW( struct _sbr );
 409                 n->header = to;
 410                 n->ret = NULL;
 411
 412                 n->next = sbr->next;
 413                 sbr->next = n;
 414
 415                 sbr = n;
 416         }
 417
 418         /* now insert return adress in sbr->ret */
 419         ret = DNEW( struct _list);
 420         ret->value = from;
 421         ret->next = sbr->ret;
 422         sbr->ret = ret;
 423 }
 424
 425 void lsra_add_sub( methodinfo *m, lsradata *ls, int b_index, struct _list *ret ) {
 426         struct _list *l;
 427         instruction *ip;
 428         bool next_block;
 429
 430         next_block=false;
 431
 432         if (m->basicblocks[b_index].flags < BBREACHED)
 433                 next_block = true;
 434         if (!next_block && !(m->basicblocks[b_index].icount))
 435                 next_block = true;
 436
 437         if (!next_block) {
 438                 ip = m->basicblocks[b_index].iinstr + m->basicblocks[b_index].icount -1;
 439
 440                 if (ip->opc == ICMD_JSR) /* nested Subroutines */
 441                         next_block = true;
 442         }
 443
 444         if (!next_block) {
 445                 if (ip->opc == ICMD_RET) { /* subroutine return found -> add return adresses to CFG */
 446                         for (l = ret; l != NULL; l = l->next)
 447                                 lsra_add_cfg( m, ls, b_index, l->value);
 448                 } else { /* follow CFG */
 449                         for ( l = ls->succ[b_index]; l != NULL; l = l->next)
 450                                 lsra_add_sub( m, ls, l->value, ret);
 451                 }
 452         } else { /* fall through to next block */
 453                 lsra_add_sub(m, ls, b_index+1, ret);
 454         }
 455 }
 456
 457 void lsra_add_subs(methodinfo *m, lsradata *ls) {
 458         struct _sbr *sbr;
 459 #ifdef LSRA_DEBUG
 460         struct _list *ret;
 461 #endif
 462
 463         for (sbr = ls->sbr.next; sbr != NULL; sbr=sbr->next) {
 464 #ifdef LSRA_DEBUG
 465                 printf("Subroutine Header: %3i Return Adresses:",sbr->header);
 466                 for (ret = sbr->ret; ret != NULL; ret = ret->next)
 467                         printf(" %3i", ret->value);
 468                 printf("\n");
 469 #endif
 470                 lsra_add_sub( m, ls, sbr->header, sbr->ret );
 471
 472         }
 473 }
 474
 475 void lsra_make_cfg(methodinfo *m, lsradata *ls)
 476 {
 477         instruction *ip;
 478         s4 *s4ptr;
 479         int high, low, count;
 480         int b_index;
 481
 482         b_index=0;
 483         while (b_index < m->basicblockcount ) {
 484                 if (m->basicblocks[b_index].flags >= BBREACHED) {
 485                         ip = m->basicblocks[b_index].iinstr + m->basicblocks[b_index].icount -1;
 486                         /* set ip to last instruction                   */
 487
 488                         if (m->basicblocks[b_index].icount) {
 489                                 /* block contains instructions  */
 490                                 switch (ip->opc) {                      /* check type of last instruction               */
 491                                 case ICMD_RETURN:
 492                                 case ICMD_IRETURN:
 493                                 case ICMD_LRETURN:
 494                                 case ICMD_FRETURN:
 495                                 case ICMD_DRETURN:
 496                                 case ICMD_ARETURN:
 497
 498                                 case ICMD_ATHROW:
 499                                         lsra_add_cfg(m, ls, b_index, m->basicblockcount);
 500                                         ls->end_bb=b_index;
 501                                         break;                                  /* function returns -> end of graph             */
 502
 503                                 case ICMD_IFNULL:
 504                                 case ICMD_IFNONNULL:
 505                                 case ICMD_IFEQ:
 506                                 case ICMD_IFNE:
 507                                 case ICMD_IFLT:
 508                                 case ICMD_IFGE:
 509                                 case ICMD_IFGT:
 510                                 case ICMD_IFLE:
 511                                 case ICMD_IF_LEQ:
 512                                 case ICMD_IF_LNE:
 513                                 case ICMD_IF_LLT:
 514                                 case ICMD_IF_LGE:
 515                                 case ICMD_IF_LGT:
 516                                 case ICMD_IF_LLE:
 517                                 case ICMD_IF_ICMPEQ:
 518                                 case ICMD_IF_ICMPNE:
 519                                 case ICMD_IF_ICMPLT:
 520                                 case ICMD_IF_ICMPGE:
 521                                 case ICMD_IF_ICMPGT:
 522                                 case ICMD_IF_ICMPLE:
 523                                 case ICMD_IF_LCMPEQ:
 524                                 case ICMD_IF_LCMPNE:
 525                                 case ICMD_IF_LCMPLT:
 526                                 case ICMD_IF_LCMPGE:
 527                                 case ICMD_IF_LCMPGT:
 528                                 case ICMD_IF_LCMPLE:
 529                                 case ICMD_IF_ACMPEQ:
 530                                 case ICMD_IF_ACMPNE:                            /* branch -> check next block   */
 531                                         lsra_add_cfg(m, ls, b_index, b_index+1);
 532                                         /* fall throu */
 533
 534                                 case ICMD_GOTO:
 535                                         lsra_add_cfg(m, ls, b_index,  m->basicblockindex[ip->op1]);
 536                                         break;                                                  /* visit branch (goto) target   */
 537
 538                                 case ICMD_TABLESWITCH:                          /* switch statement                             */
 539                                         s4ptr = ip->val.a;
 540
 541                                         lsra_add_cfg(m, ls, b_index,  m->basicblockindex[*s4ptr]);
 542
 543                                         s4ptr++;
 544                                         low = *s4ptr;
 545                                         s4ptr++;
 546                                         high = *s4ptr;
 547
 548                                         count = (high-low+1);
 549
 550                                         while (--count >= 0) {
 551                                                 s4ptr++;
 552                                                 lsra_add_cfg(m, ls, b_index,  m->basicblockindex[*s4ptr]);
 553                                     }
 554                                         break;
 555
 556                                 case ICMD_LOOKUPSWITCH:                         /* switch statement                             */
 557                                         s4ptr = ip->val.a;
 558
 559                                         lsra_add_cfg(m, ls, b_index,  m->basicblockindex[*s4ptr]);
 560
 561                                         ++s4ptr;
 562                                         count = *s4ptr++;
 563
 564                                         while (--count >= 0) {
 565                                                 lsra_add_cfg(m, ls, b_index,  m->basicblockindex[s4ptr[1]]);
 566                                                 s4ptr += 2;
 567                                     }
 568                                         break;
 569
 570                                 case ICMD_JSR:
 571                                         lsra_add_jsr(m, ls, b_index, m->basicblockindex[ip->op1]);
 572                                         break;
 573
 574                                 case ICMD_RET:
 575                                         break;
 576
 577                                 default:
 578                                         lsra_add_cfg(m, ls, b_index, b_index + 1 );
 579                                         break;
 580                             } /* switch (ip->opc)*/
 581                     }     /* if (m->basicblocks[blockIndex].icount) */
 582             }         /* if (m->basicblocks[b_index].flags >= BBREACHED) */
 583                 b_index++;
 584         }             /* while (b_index < m->basicblockcount ) */
 585 }
 586
 587
 588
 589
 590 void lsra_init(methodinfo *m, codegendata *cd, t_inlining_globals *id, lsradata *ls)
 591 {
 592         int i;
 593
 594         /* Init LSRA Data Structures */
 595         /* lifetimes für alle Basicblocks allokieren */
 596         ls->pred = DMNEW(struct _list *, m->basicblockcount+1); /* + 1 for a artificial exit node */
 597         ls->succ = DMNEW(struct _list *, m->basicblockcount+1); /* + 1 for a artificial exit node */
 598         ls->sorted = DMNEW(int , m->basicblockcount+1); /* + 1 for a artificial exit node */
 599         ls->sorted_rev = DMNEW(int , m->basicblockcount+1); /* + 1 for a artificial exit node */
 600         ls->num_pred = DMNEW(int , m->basicblockcount+1); /* + 1 for a artificial exit node */
 601         ls->nesting = DMNEW(long , m->basicblockcount);
 602         for (i=0; i<m->basicblockcount; i++) {
 603                 ls->pred[i]=NULL;
 604                 ls->succ[i]=NULL;
 605                 ls->sorted[i]=-1;
 606                 ls->sorted_rev[i]=-1;
 607                 ls->num_pred[i]=0;
 608                 ls->nesting[i] = 1;
 609         }
 610         ls->pred[m->basicblockcount]=NULL;
 611         ls->succ[m->basicblockcount]=NULL;
 612         ls->sorted[m->basicblockcount]=-1;
 613         ls->sorted_rev[m->basicblockcount]=-1;
 614         ls->num_pred[m->basicblockcount]=0;
 615
 616 /*      ls->ss_lifetimes=NULL; */
 617 #ifdef LSRA_DEBUG
 618         if (cd->maxlocals != id->cumlocals) panic("lsra: Welche locals nehmen?\n");
 619 #endif
 620
 621         ls->maxlifetimes = m->maxlifetimes;
 622         ls->lifetimecount = ls->maxlifetimes + cd->maxlocals * (TYPE_ADR+1);
 623         ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
 624         ls->lt_used = DMNEW(int, ls->lifetimecount);
 625         ls->lt_int = NULL;
 626         ls->lt_int_count = 0;
 627         ls->lt_flt = NULL;
 628         ls->lt_flt_count = 0;
 629         ls->lt_rest = NULL;
 630         ls->lt_rest_count = 0;
 631         for (i=0; i < ls->lifetimecount; i++) ls->lifetime[i].type = -1;
 632
 633         ls->end_bb= -1;
 634         ls->icount_max = 0;
 635
 636         ls->sbr.next = NULL;
 637 }
 638
 639 bool lsra_test(methodinfo *m, codegendata *cd)
 640 {
 641         bool jsr;
 642 #ifndef LSRA_DO_SR
 643         instruction *ip;
 644         int i;
 645 #endif
 646
 647 #ifndef LSRA_DO_EX
 648         /* in case of exceptionhandlers or subroutines return to regalloc */
 649         if (cd->exceptiontablelength > 0)
 650                 return false;
 651 #endif
 652
 653         jsr=false;
 654 #ifndef LSRA_DO_SR
 655         for (i=0; i< m->basicblockcount; i++) {
 656                 ip = m->basicblocks[i].iinstr + m->basicblocks[i].icount -1;/* set ip to last instruction       */
 657                 if (ip->opc == ICMD_JSR) {
 658                         /* check Instack of sub */
 659                         /*                      printf("SBR Instackdepth: %3i\n",m->basicblocks[m->basicblockindex[ip->op1]].indepth);*/
 660                         jsr=true;
 661                 }
 662         }
 663 #endif
 664         return (!jsr);
 665 }
 666
 667 bool lsra_setup(methodinfo *m, codegendata *cd, registerdata *rd, lsradata *ls)
 668 {
 669 #ifdef LSRA_DEBUG
 670         basicblock  *bptr;
 671         struct _list *nl;
 672 #endif
 673         int i,p;
 674         s4  t;
 675
 676 #ifdef LSRA_DUMP_LOOPDATA
 677         struct LoopContainer *lc;
 678         struct LoopElement *le;
 679 #endif
 680
 681         /* in case of exceptionhandlers or subroutines return to regalloc */
 682 #if (! (defined(LSRA_DO_SR) && defined(LSRA_DO_EX)) )
 683         if (!lsra_test(m,cd))
 684                 return false;
 685 #endif
 686
 687         /* Setup LSRA Data structures */
 688         if (opt_loops)
 689                 return false;
 690
 691         lsra_make_cfg(m, ls);
 692
 693         lsra_add_subs(m, ls); /* add subroutines before exceptions! They "destroy" the CFG */
 694         lsra_add_exceptions(m, cd, ls);
 695
 696         lsra_DFS_2(m, ls);
 697
 698         lsra_get_backedges( m, ls);
 699 #ifdef LSRA_DEBUG
 700         printf("Successors:\n");
 701         for (i=0; i < m->basicblockcount; i++) {
 702                 printf("%3i->: ",i);
 703                 for (nl=ls->succ[i]; nl!= NULL; nl=nl->next)
 704                         printf("%3i ",nl->value);
 705                 printf("\n");
 706         }
 707         printf("Predecessors:\n");
 708         for (i=0; i < m->basicblockcount; i++) {
 709                 printf("%3i->: ",i);
 710                 for (nl=ls->pred[i]; nl!= NULL; nl=nl->next)
 711                         printf("%3i ",nl->value);
 712                 printf("\n");
 713         }
 714         printf("Sorted: ");
 715         for (i=0; i < m->basicblockcount; i++) printf("%3i ", ls->sorted[i]);
 716         printf("\n");
 717         printf("Sorted_rev: ");
 718         for (i=0; i < m->basicblockcount; i++) printf("%3i ", ls->sorted_rev[i]);
 719         printf("\n");
 720 #endif
 721
 722
 723 #ifdef LSRA_DEBUG
 724         /* sicherheitshalber Konsistenz von m->basicblocks[..] mit basicblocks->next (Liste) überprüfen */
 725         printf("LSRA bb prüfen\n");
 726         i=0;
 727         bptr = m->basicblocks;
 728         while (bptr != NULL) {
 729                 if (i > m->basicblockcount){
 730                         panic("linked bb list does not correspond with bb array(1)\n");
 731                 }
 732                 if (bptr != &(m->basicblocks[i])){
 733                         panic("linked bb list does not correspond with bb array(2)\n");
 734                 }
 735
 736                 i++;
 737                 bptr=bptr->next;
 738         }
 739         if (i<m->basicblockcount){
 740                 panic("linked bb list does not correspond with bb array(3)\n");
 741         }
 742
 743 #endif
 744
 745
 746         ls->v_index = -1;
 747         for (i=m->basicblockcount-1; i >= 0; i--) {
 748                 if (ls->sorted[i] != -1) {
 749                         lsra_scan_registers_canditates(m, ls, ls->sorted[i]);
 750                         lsra_join_lifetimes(m, ls, ls->sorted[i]);
 751                 }
 752         }
 753
 754         /* Parameter initialisiation for locals 0 .. paramcount */
 755         /* Parameter initialisieren == local Vars readaccess at 0,-1*/
 756
 757         for (p = 0, i = 0; p < m->paramcount; p++) {
 758                 t = m->paramtypes[p];
 759
 760                 if (rd->locals[i][t].type >= 0)
 761                         lsra_usage_local(ls, i, t, 0, -1, LSRA_STORE); /* Param to Local init happens before normal Code */
 762                 i++;
 763                 if (IS_2_WORD_TYPE(t))    /* increment local counter for 2 word types */
 764                         i++;
 765         }  /* end for */
 766
 767         lsra_calc_lifetime_length(m, ls, cd);
 768
 769 #ifdef LSRA_PRINTLIFETIMES
 770         printf("Basicblockcount: %4i Max Instr/BB: %4i\n",m->basicblockcount, ls->icount_max);
 771 /*      print_lifetimes(rd, ls, ls->lt_used, ls->lifetimecount); */
 772 #endif
 773         return true;
 774 }
 775
 776 bool lsra_join_ss( struct lsradata *ls, struct stackelement *in, struct stackelement *out, int join_flag) {
 777         struct lifetime *lt, *lto;
 778         struct stackslot *ss, *ss_last;
 779
 780
 781         if (in->varnum != out->varnum) {
 782                 lt = &(ls->lifetime[-in->varnum - 1]);
 783
 784 #ifdef LSRA_DEBUG
 785                 if (join_flag == JOIN_BB)
 786                         if (lt->type == -1) panic("lsra_join_ss: lifetime for instack not found\n");
 787 #endif
 788 #if 0 /* was once upon a time */
 789                 if (lt->type == -1) /* lifetime was assigned a REG_RES and has been thrown away */
 790                         return false;
 791 #endif
 792
 793                 if (out->varnum >= 0) { /* no lifetime for this slot till now */
 794                         lsra_add_ss(lt, out);
 795                 } else {
 796
 797                         lto = &(ls->lifetime[-out->varnum - 1]);
 798
 799                         if ((join_flag == JOIN_DUP) || (join_flag == JOIN_OP))
 800                                 if ( (lt->flags & JOIN_BB) || (lto->flags & JOIN_BB)) {
 801 #ifdef LSRA_DEBUG
 802                                         printf("DUP or OP join rejected for JOIN_BB Lifetime: v_index1 %3i v_index2 %3i\n",in->varnum, out->varnum);
 803 #endif
 804                                         return false;
 805                                 }
 806                         if (join_flag == JOIN_DUP)
 807                                 if ( (lt->flags & JOIN_OP) || (lto->flags & JOIN_OP)) {
 808 #ifdef LSRA_DEBUG
 809                                         printf("DUP join rejected for JOIN_OP Lifetime: v_index1 %3i v_index2 %3i\n",in->varnum, out->varnum);
 810 #endif
 811                                         return false;
 812                                 }
 813 /*                      if (join_flag == JOIN_OP) */
 814 /*                              if ( (lt->flags & JOIN_DUP) || (lto->flags & JOIN_DUP)) { */
 815 /* #ifdef LSRA_DEBUG */
 816 /*                                      printf("OP join rejected for JOIN_DUP Lifetime: v_index1 %3i v_index2 %3i\n",in->varnum, out->varnum); */
 817 /* #endif */
 818 /*                                      return false; */
 819 /*                              } */
 820 #ifdef LSRA_DEBUG
 821 #if 0 /* was once upon a time */
 822                         if (join_flag == JOIN_BB)
 823 #endif
 824                                 if (lto->type == -1) panic("lsra_join_ss: lifetime for outstack not found\n");
 825 #endif
 826 #if 0 /* was once upon a time */
 827                         if (lto->type == -1) /* lifetime was assigned a REG_RES and has been thrown away */
 828                                 return false;
 829 #endif
 830 #ifdef LSRA_DEBUG
 831                         if (lto->type != lt->type) panic ("lsra_join_ss: in/out stack type mismatch\n");
 832 #endif
 833
 834
 835                         lt->flags |= JOINING;
 836
 837                         /* take Lifetime lto out of ls->lifetimes */
 838                         lto->type = -1;
 839
 840                         /* merge lto into lt of in */
 841
 842                         ss_last = ss = lto->local_ss;
 843                         while (ss != NULL) {
 844                                 ss_last = ss;
 845                                 ss->s->varnum = lt->v_index;
 846                                 ss = ss->next;
 847                         }
 848                         if (ss_last != NULL) {
 849                                 ss_last->next = lt->local_ss;
 850                                 lt->local_ss = lto->local_ss;
 851                         }
 852                         lt->savedvar |= lto->savedvar;
 853                         lt->flags |= lto->flags | join_flag;
 854                         lt->usagecount += lto->usagecount;
 855
 856                         /*join of bb_first_def, i_first_def und *_last_use */
 857                         if (lto->bb_first_def < lt->bb_first_def) {
 858                                 lt->bb_first_def = lto->bb_first_def;
 859                                 lt->i_first_def = lto->i_first_def;
 860                         } else if ((lto->bb_first_def == lt->bb_first_def) && ( lto->i_first_def < lt->i_first_def)) {
 861                                 lt->i_first_def = lto->i_first_def;
 862                         }
 863                         if (lto->bb_last_use > lt->bb_last_use) {
 864                                 lt->bb_last_use = lto->bb_last_use;
 865                                 lt->i_last_use = lto->i_last_use;
 866                         } else if ((lto->bb_last_use == lt->bb_last_use) && ( lto->i_last_use > lt->i_last_use)) {
 867                                 lt->i_last_use = lto->i_last_use;
 868                         }
 869                 }
 870         }
 871         return true;
 872 }
 873
 874 /* join instack of Basic Block b_index with outstack of predecessors */
 875 void lsra_join_lifetimes(methodinfo *m, lsradata *ls, int b_index) {
 876         struct stackelement *in, *i, *out;
 877     struct _list *pred;
 878
 879         /* do not join instack of Exception Handler */
 880         if (m->basicblocks[b_index].type == BBTYPE_EXH)
 881                 return;
 882         in=m->basicblocks[b_index].instack;
 883         if (m->basicblocks[b_index].type == BBTYPE_SBR)
 884                 in=in->prev; /* do not join first instack element of a subroutine header */
 885
 886         if (in != NULL) {
 887                 for (pred = ls->pred[b_index]; pred != NULL; pred = pred->next) {
 888                         out = m->basicblocks[pred->value].outstack;
 889                         for (i=in; (i != NULL); i = i->prev, out=out->prev) {
 890                                 lsra_join_ss(ls, i, out, JOIN_BB);
 891                         }
 892                 }
 893         }
 894 }
 895
 896 void lsra_reg_setup(methodinfo *m ,registerdata *rd, struct lsra_register *int_reg,struct lsra_register *flt_reg ) {
 897         int i, iarg, farg;
 898         int int_sav_top;
 899         int flt_sav_top;
 900
 901         int localindex;
 902
 903         bool *fltarg_used, *intarg_used;
 904
 905         int_reg->nregdesc = nregdescint;
 906         flt_reg->nregdesc = nregdescfloat;
 907         if (m->isleafmethod) {
 908 /* Temp and Argumentregister can be used as "saved" registers                           */
 909
 910                 int_reg->sav_top = rd->intreg_argnum + rd->tmpintregcnt + rd->savintregcnt;
 911                 int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
 912                 int_reg->tmp_reg = NULL;
 913                 int_reg->tmp_top = -1;
 914                 flt_reg->sav_top = rd->fltreg_argnum + rd->tmpfltregcnt + rd->savfltregcnt;
 915                 flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
 916                 flt_reg->tmp_reg = NULL;
 917                 flt_reg->tmp_top = -1;
 918
 919
 920 /* additionaly precolour registers for Local Variables acting as Parameters */
 921
 922                 farg = rd->fltreg_argnum;
 923                 iarg = rd->intreg_argnum;
 924
 925                 intarg_used = DMNEW(bool, rd->intreg_argnum);
 926                 for (i=0; i < rd->intreg_argnum; i++)
 927                         intarg_used[i]=false;
 928
 929                 fltarg_used = DMNEW(bool, rd->fltreg_argnum);
 930                 for (i=0; i < rd->fltreg_argnum; i++)
 931                         fltarg_used[i]=false;
 932
 933                 int_sav_top=int_reg->sav_top;
 934                 flt_sav_top=flt_reg->sav_top;
 935
 936                 iarg = -1;
 937                 farg = -1;
 938                 localindex = 0;
 939 #ifdef LSRA_DEBUG
 940                 printf("Paramcount: %i ", m->paramcount);
 941 #endif
 942                 for (i=0; (i < m->paramcount) && ((farg < rd->fltreg_argnum) ||(iarg < rd->intreg_argnum) ); i++) {
 943 #ifdef LSRA_DEBUG
 944                         printf("Type %3i %3i", i, m->paramtypes[i]);
 945 #endif
 946                         switch (m->paramtypes[i]) {
 947                         case TYPE_INT:
 948                         case TYPE_ADR:
 949 #if !defined(__I386__)
 950                         case TYPE_LNG: /* i386->longs stay in Memory */
 951 #endif
 952                                 iarg++;
 953 #ifndef CONSECUTIVE_FLOATARGS
 954                                 farg++;
 955 #endif
 956                                 if (rd->locals[localindex][m->paramtypes[i]].type >= 0)
 957                                         if (iarg < rd->intreg_argnum) {
 958                                                 int_reg->sav_reg[--int_sav_top]=rd->argintregs[iarg];
 959                                                 intarg_used[iarg]=true; /* used -> don't copy later on */
 960                                         }
 961                                 break;
 962                         case TYPE_FLT:
 963 #if !defined(__I386__)
 964                         case TYPE_DBL: /* i386->longs stay in Memory */
 965 #endif
 966                                 farg++;
 967 #ifndef CONSECUTIVE_INTARGS
 968                                 iarg++;
 969 #endif
 970                                 if (rd->locals[localindex][m->paramtypes[i]].type >= 0)
 971                                         if (farg < rd->fltreg_argnum) {
 972                                                 flt_reg->sav_reg[--flt_sav_top]=rd->argfltregs[farg];
 973                                                 fltarg_used[farg]=true; /* used -> don't copy later on */
 974                                         }
 975                                 break;
 976                         }
 977                         if ( IS_2_WORD_TYPE(m->paramtypes[i]))
 978                                 localindex+=2;
 979                         else
 980                                 localindex++;
 981                 }
 982 #ifdef LSRA_DEBUG
 983                 printf("\n");
 984 #endif
 985                 /* copy rest of argument registers to flt_reg->sav_reg and int_reg->sav_reg; */
 986                 for (i=0; i < rd->intreg_argnum; i++)
 987                         if (!intarg_used[i])
 988                                 int_reg->sav_reg[--int_sav_top]=rd->argintregs[i];
 989                 for (i=0; i < rd->fltreg_argnum; i++)
 990                         if (!fltarg_used[i])
 991                                 flt_reg->sav_reg[--flt_sav_top]=rd->argfltregs[i];
 992
 993                 /* copy temp registers to flt_reg->sav_reg and int_reg->sav_reg */
 994                 for (i=0; i < rd->tmpintregcnt; i++)
 995                         int_reg->sav_reg[--int_sav_top]=rd->tmpintregs[i];
 996                 for (i=0; i < rd->tmpfltregcnt; i++)
 997                         flt_reg->sav_reg[--flt_sav_top]=rd->tmpfltregs[i];
 998
 999         } else {
1000                 /* non leaf method -> don't use Argument Registers, divide temp and saved registers */
1001                 int_sav_top = int_reg->sav_top = rd->savintregcnt;
1002                 int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
1003                 int_reg->tmp_top = rd->tmpintregcnt;
1004                 int_reg->tmp_reg = DMNEW(int, int_reg->tmp_top);
1005                 flt_sav_top =flt_reg->sav_top = rd->savfltregcnt;
1006                 flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
1007                 flt_reg->tmp_top = rd->tmpfltregcnt;
1008                 flt_reg->tmp_reg = DMNEW(int, flt_reg->tmp_top);
1009
1010                 /* copy temp registers to flt_reg->tmp_reg and int_reg->tmp_reg */
1011                 for (i=0; i < rd->tmpintregcnt; i++)
1012                         int_reg->tmp_reg[i]=rd->tmpintregs[i];
1013                 for (i=0; i < rd->tmpfltregcnt; i++)
1014                         flt_reg->tmp_reg[i]=rd->tmpfltregs[i];
1015         }
1016
1017         /* now copy saved registers to flt_reg->sav_reg and int_reg->sav_reg */
1018         for (i = rd->savintregcnt-1; i >= 0; i--)
1019                 int_reg->sav_reg[--int_sav_top]=rd->savintregs[i];
1020         for (i = rd->savfltregcnt-1; i >= 0; i--)
1021                 flt_reg->sav_reg[--flt_sav_top]=rd->savfltregs[i];
1022         /* done */
1023 }
1024
1025 void lsra_insertion( struct lsradata *ls, int *a, int lo, int hi) {
1026         int i,j,t,tmp;
1027
1028         for (i=lo+1; i<=hi; i++) {
1029                 j=i;
1030                 t=ls->lifetime[a[j]].i_start;
1031                 tmp = a[j];
1032                 while ((j>lo) && (ls->lifetime[a[j-1]].i_start > t)) {
1033 /*                      ls->lifetime[a[j]].i_start = ls->lifetime[a[j-1]].i_start; */
1034                         a[j]=a[j-1];
1035                         j--;
1036                 }
1037                 a[j]=tmp;
1038 /*              ls->lifetime[a[j]].i_start=t; */
1039         }
1040 }
1041
1042 void lsra_qsort( struct lsradata *ls, int *a, int lo, int hi) {
1043         int i,j,x,tmp;
1044         if (lo < hi) {
1045                 if ( (lo+5)<hi) {
1046                         i = lo;
1047                         j = hi;
1048                         x = ls->lifetime[a[(lo+hi)/2]].i_start;
1049
1050
1051                         while (i <= j) {
1052                                 while (ls->lifetime[a[i]].i_start < x) i++;
1053                                 while (ls->lifetime[a[j]].i_start > x) j--;
1054                                 if (i <= j) {
1055                                         /* exchange a[i], a[j] */
1056                                         tmp = a[i];
1057                                         a[i] = a[j];
1058                                         a[j] = tmp;
1059
1060                                         i++;
1061                                         j--;
1062                                 }
1063                         }
1064
1065                         if (lo < j) lsra_qsort( ls, a, lo, j);
1066                         if (i < hi) lsra_qsort( ls, a, i, hi);
1067                 } else
1068                         lsra_insertion(ls, a, lo, hi);
1069         }
1070 }
1071
1072 void lsra_param_sort(struct lsradata *ls, int *lifetime, int lifetime_count) {
1073
1074         int param_count;
1075         int i,j,tmp;
1076
1077         /* count number of parameters ( .i_start == -1) */
1078         for (param_count=0; (param_count < lifetime_count) && (ls->lifetime[lifetime[param_count]].i_start == -1); param_count++);
1079
1080         if (param_count > 0) {
1081                 /* now sort the parameters by v_index */
1082                 for (i=0; i < param_count -1; i++)
1083                         for (j=i+1; j < param_count; j++)
1084                                 if ( ls->lifetime[lifetime[i]].v_index > ls->lifetime[lifetime[j]].v_index) {
1085                                         /* swap */
1086                                         tmp = lifetime[i];
1087                                         lifetime[i]=lifetime[j];
1088                                         lifetime[j]=tmp;
1089                                 }
1090         }
1091 }
1092
1093 void lsra_main(methodinfo *m, lsradata *ls, registerdata *rd, codegendata *cd)
1094 {
1095         struct lifetime *lt;
1096 #ifdef LSRA_DEBUG
1097         int i;
1098 #endif
1099         int lsra_mem_use;
1100         int flags; /* 0 INMEMORY-> ls->lt_rest, 1 INTREG-> ls->lt_int, 2 FLTREG-> ls->lt_flt */
1101         int lsra_reg_use;
1102         struct lsra_register flt_reg, int_reg;
1103
1104         int lt_used_index;
1105
1106
1107         /* first split lifetimes for integer and float registers */
1108
1109         ls->lt_int = DMNEW(int, ls->lifetimecount); /* todo: do count and split of int/float lifetimes already in lsra_calc_lifetimelength! */
1110         ls->lt_flt = DMNEW(int, ls->lifetimecount);
1111         ls->lt_rest = DMNEW(int, ls->lifetimecount);
1112         ls->lt_int_count = 0;
1113         ls->lt_flt_count = 0;
1114         ls->lt_rest_count = 0;
1115
1116
1117         for (lt_used_index = 0; lt_used_index < ls->lifetimecount; lt_used_index ++) {
1118                 lt = &(ls->lifetime[ls->lt_used[lt_used_index]]);
1119                 lt->reg = -1;
1120
1121                 switch (lt->type) {
1122                 case TYPE_LNG:
1123 #if defined(__I386__) || defined(USETWOREGS)
1124                         /*
1125                          * for i386 put all longs in memory
1126                          */
1127                         /* for PowerPC (USETWOREGS) for now into memory, too */
1128                         flags=0;
1129                         break;
1130 #endif
1131                 case TYPE_INT:
1132                 case TYPE_ADR:
1133                         flags=1;
1134                         break;
1135                 case TYPE_DBL:
1136 #if defined(__I386__)
1137                         /*
1138                          * for i386 put all longs in memory
1139                          */
1140                         flags=0;
1141                         break;
1142 #endif
1143                 case TYPE_FLT:
1144                         flags=2;
1145                         break;
1146                 default:
1147                         panic("Unknown Type\n");
1148                 }
1149
1150                 switch (flags) {
1151                 case 0: /* lt_used[lt_used_index] -> lt_rest */
1152                         ls->lt_rest[ ls->lt_rest_count++ ] = ls->lt_used[lt_used_index];
1153                         break;
1154                 case 1: /* l->lifetimes -> lt_int */
1155                         ls->lt_int[ ls->lt_int_count++ ] = ls->lt_used[lt_used_index];
1156                         break;
1157                 case 2: /* l->lifetimes -> lt_flt */
1158                         ls->lt_flt[ ls->lt_flt_count++ ] = ls->lt_used[lt_used_index];
1159                         break;
1160                 }
1161
1162         }
1163         lsra_qsort( ls, ls->lt_rest, 0, ls->lt_rest_count - 1);
1164         lsra_qsort( ls, ls->lt_int, 0, ls->lt_int_count - 1);
1165         lsra_qsort( ls, ls->lt_flt, 0, ls->lt_flt_count - 1);
1166
1167         lsra_param_sort( ls, ls->lt_int, ls->lt_int_count);
1168         lsra_param_sort( ls, ls->lt_flt, ls->lt_flt_count);
1169
1170         lsra_reg_setup(m, rd, &int_reg, &flt_reg);
1171
1172 #ifdef LSRA_DEBUG
1173         printf("INTSAV REG: ");
1174         for (i=0; i<int_reg.sav_top; i++)
1175                 printf("%2i ",int_reg.sav_reg[i]);
1176         printf("\nINTTMP REG: ");
1177         for (i=0; i<int_reg.tmp_top; i++)
1178                 printf("%2i ",int_reg.tmp_reg[i]);
1179         printf("\nFLTSAV REG: ");
1180         for (i=0; i<flt_reg.sav_top; i++)
1181                 printf("%2i ",flt_reg.sav_reg[i]);
1182         printf("\nFLTTMP REG: ");
1183         for (i=0; i<flt_reg.tmp_top; i++)
1184                 printf("%2i ",flt_reg.tmp_reg[i]);
1185         printf("\n");
1186 #endif
1187         lsra_reg_use=rd->savintregcnt;
1188                 _lsra_main(m, ls, ls->lt_int, ls->lt_int_count, &int_reg, &lsra_reg_use);
1189                 if (lsra_reg_use > rd->savintregcnt) lsra_reg_use=rd->savintregcnt;
1190         rd->maxsavintreguse= lsra_reg_use;
1191         lsra_reg_use=rd->savfltregcnt;
1192
1193                 _lsra_main(m,ls, ls->lt_flt, ls->lt_flt_count, &flt_reg, &lsra_reg_use);
1194                 if (lsra_reg_use > rd->savfltregcnt) lsra_reg_use=rd->savfltregcnt;
1195
1196         rd->maxsavfltreguse=lsra_reg_use;
1197
1198         /* allocate stack space for passing arguments to called methods */
1199
1200 #if !defined(SPECIALMEMUSE)
1201         /* For this to work properly the integer argument register count must be  */
1202         /* less or equal the float argument register count (e.g. x86_64).         */
1203         /* (arch.h: INT_ARG_CNT <= FLT_ARG_CNT)                                   */
1204         if (rd->arguments_num > INT_ARG_CNT) {
1205                 lsra_mem_use = rd->arguments_num - INT_ARG_CNT;
1206
1207         } else {
1208                 lsra_mem_use = 0;
1209         }
1210 #else
1211         lsra_mem_use = rd->ifmemuse; /* Init with if_memuse from pregregpass */
1212 #endif
1213
1214 #ifdef LSRA_DEBUG
1215         printf("Alloc Rest\n");
1216 #endif
1217         lsra_alloc(m, rd, ls, ls->lt_rest, ls->lt_rest_count,&lsra_mem_use);
1218 #ifdef LSRA_DEBUG
1219         printf("Alloc Int\n");
1220 #endif
1221         lsra_alloc(m, rd, ls, ls->lt_int, ls->lt_int_count, &lsra_mem_use);
1222 #ifdef LSRA_DEBUG
1223         printf("Alloc Flt\n");
1224 #endif
1225         lsra_alloc(m, rd, ls, ls->lt_flt, ls->lt_flt_count, &lsra_mem_use);
1226
1227 #ifdef LSRA_PRINTLIFETIMES
1228         printf("Int RA complete \n");
1229         printf("Lifetimes after splitting int: \n");
1230         print_lifetimes(rd, ls, ls->lt_int, ls->lt_int_count);
1231
1232         printf("Flt RA complete \n");
1233         printf("Lifetimes after splitting flt:\n");
1234         print_lifetimes(rd, ls, ls->lt_flt, ls->lt_flt_count);
1235
1236         printf("Rest RA complete \n");
1237         printf("Lifetimes after leftt:\n");
1238         print_lifetimes(rd, ls, ls->lt_rest, ls->lt_rest_count);
1239 #endif
1240         rd->maxmemuse=lsra_mem_use;
1241 #ifdef LSRA_TESTLT
1242         test_lifetimes(m, ls, rd );
1243 #endif
1244
1245 }
1246
1247 void lsra_alloc(methodinfo *m, registerdata *rd, struct lsradata *ls, int *lifet, int lifetimecount, int *mem_use)
1248 {
1249         int flags,regoff;
1250         struct lifetime *lt;
1251         struct freemem *fmem;
1252         struct stackslot *n;
1253         int lt_index;
1254 #ifdef USETWOREGS
1255         struct freemem *fmem_2;
1256 #endif
1257
1258         fmem=DNEW(struct freemem);
1259         fmem->off=-1;
1260         fmem->next=NULL;
1261 #ifdef USETWOREGS
1262         fmem_2=DNEW(struct freemem);
1263         fmem_2->off=-1;
1264         fmem_2->next=NULL;
1265 #endif
1266
1267 /*      for (lt=lifet;lt!=NULL;lt=lt->next) { */
1268         for (lt_index = 0; lt_index < lifetimecount; lt_index ++) {
1269                 lt = &(ls->lifetime[lifet[lt_index]]);
1270 #ifdef LSRA_MEMORY
1271                 lt->reg=-1;
1272 #endif
1273                 if (lt->reg==-1) {
1274                         flags=INMEMORY;
1275 #ifdef USETWOREGS
1276                         if (IS_2_WORD_TYPE(lt->type))
1277                                 regoff=lsra_getmem(lt, fmem_2, mem_use);
1278                         else
1279 #endif
1280                         regoff=lsra_getmem(lt, fmem, mem_use);
1281                 } else {
1282                         flags=lt->savedvar;
1283                         regoff=lt->reg;
1284                 }
1285
1286                 if (lt->v_index < 0) {
1287                         for (n=lt->local_ss; n!=NULL; n=n->next) {
1288                                 lsra_setflags( &(n->s->flags), flags);
1289                                 n->s->regoff=regoff;
1290                         }
1291                 } else { /* local var */
1292                         if (rd->locals[lt->v_index][lt->type].type>=0) {
1293 /*                              lsra_setflags( &(rd->locals[lt->v_index][lt->type].flags), flags); */
1294                                 rd->locals[lt->v_index][lt->type].flags= flags;
1295                                 rd->locals[lt->v_index][lt->type].regoff=regoff;
1296                         } else panic("Type Data mismatch 1\n");
1297                 }
1298                 lt->reg = regoff;
1299         }
1300 }
1301
1302 void lsra_setflags(int *flags, int newflags)
1303 {
1304         if ( newflags & INMEMORY)
1305                 *flags |= INMEMORY;
1306         else
1307                 *flags &= ~INMEMORY;
1308
1309         if (newflags & SAVEDVAR)
1310                 *flags |= SAVEDVAR;
1311 }
1312
1313 int lsra_getmem(struct lifetime *lt, struct freemem *fmem, int *mem_use)
1314 {
1315         struct freemem *fm, *p;
1316
1317         /* noch kein Speicher vergeben, oder alle Enden später */
1318         if ((fmem->next == NULL) || (fmem->next->end > lt->i_start)) {
1319                 fm=lsra_getnewmem(mem_use);
1320 #ifdef USETWOREGS
1321                 if (IS_2_WORD_TYPE(lt->type)) (*mem_use)++;
1322 #endif
1323         } else {
1324                 /* Speicherstelle frei */
1325                 fm=fmem->next;
1326                 fmem->next=fm->next;
1327                 fm->next=NULL;
1328         }
1329         fm->end=lt->i_end;
1330         for (p=fmem; (p->next!=NULL) && (p->next->end < fm->end); p=p->next);
1331         fm->next=p->next;
1332         p->next=fm;
1333         return fm->off;
1334 }
1335
1336 struct freemem *lsra_getnewmem(int *mem_use)
1337 {
1338         struct freemem *fm;
1339
1340         fm=DNEW(struct freemem);
1341         fm->next=NULL;
1342         fm->off=*mem_use;
1343         (*mem_use)++;
1344         return fm;
1345 }
1346
1347 void _lsra_main( methodinfo *m, lsradata *ls, int *lifet, int lifetimecount, struct lsra_register *reg, int *reg_use)
1348 {
1349         struct lifetime *lt;
1350         int lt_index;
1351         int reg_index;
1352         bool temp; /* reg from temp registers (true) or saved registers (false) */
1353
1354         if ((reg->tmp_top+reg->sav_top) == 0) {
1355 /*              for (lt=lifet; lt != NULL; lt=lt->next) */
1356 /*                      lt->reg=-1; */
1357                 for (lt_index = 0; lt_index < lifetimecount; lt_index++)
1358                         ls->lifetime[lifet[lt_index]].reg = -1;
1359                 return;
1360         }
1361
1362         ls->active_tmp = NULL;
1363         ls->active_sav = NULL;
1364
1365 /*      for (lt=lifet; lt != NULL; lt=lt->next) { */
1366         for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
1367                 lt = &(ls->lifetime[lifet[lt_index]]);
1368
1369                 lsra_expire_old_intervalls(m, ls, lt, reg);
1370                 reg_index = -1;
1371                 temp = false;
1372                 if (lt->savedvar || m->isleafmethod) { /* -> use Saved Reg (in case of leafmethod all regs are "saved" regs) */
1373                         if (reg->sav_top > 0) {
1374                                 reg_index = reg->sav_reg[--reg->sav_top];
1375                         }
1376                 } else { /* use Temp Reg or if non free a Saved Reg */
1377                         if (reg->tmp_top > 0) {
1378                                 temp = true;
1379                                 reg_index = reg->tmp_reg[--reg->tmp_top];
1380                         }
1381                         else
1382                                 if (reg->sav_top > 0)
1383                                         reg_index = reg->sav_reg[--reg->sav_top];
1384                 }
1385                 if (reg_index == -1) /* no reg is available anymore... -> spill */
1386                         spill_at_intervall(m, ls, lt);
1387                 else {
1388                         lt->reg = reg_index;
1389                         if (temp)
1390                                 lsra_add_active(lt, &(ls->active_tmp));
1391                         else {
1392                                 if (reg->sav_top<*reg_use) *reg_use=reg->sav_top;
1393                                 lsra_add_active(lt, &(ls->active_sav));
1394                         }
1395                 }
1396         }
1397 }
1398
1399 void lsra_add_active(struct lifetime *lt, struct active_lt **active)
1400 {
1401         struct active_lt *alt,*alt1,*alt2;
1402         alt=DNEW(struct active_lt);
1403         alt->lt=lt;
1404
1405         for(alt1=alt2=*active; alt1 != NULL; alt2=alt1, alt1=alt1->next)
1406                 if (alt1->lt->i_end > lt->i_end) break;
1407
1408         if (alt1 == *active) {
1409                 alt->next = *active;
1410                 *active = alt;
1411         } else {
1412                 alt->next = alt2->next;
1413                 alt2->next = alt;
1414         }
1415 }
1416
1417
1418 void lsra_expire_old_intervalls(methodinfo *m, lsradata *ls, struct lifetime *lt, struct lsra_register *reg)
1419 {
1420         _lsra_expire_old_intervalls(m, lt, reg, &(ls->active_tmp));
1421         _lsra_expire_old_intervalls(m, lt, reg, &(ls->active_sav));
1422 }
1423
1424 void _lsra_expire_old_intervalls(methodinfo *m, struct lifetime *lt, struct lsra_register *reg, struct active_lt **active)
1425 {
1426         struct active_lt *alt,*alt1;
1427 /*      int i; */
1428
1429         for (alt1=alt=*active; alt != NULL; alt1=alt, alt=alt->next) {
1430                 if (alt->lt->i_end > lt->i_start) return;
1431                 if (alt == *active)
1432                         *active = (*active)->next;
1433                 else
1434                         alt1->next=alt->next;
1435
1436                 /* make alt->lt->reg available again */
1437                 if (m->isleafmethod) {
1438                         /* leafmethod -> don't care about type -> put all again into reg->sav_reg */
1439                         reg->sav_reg[reg->sav_top++] = alt->lt->reg;
1440                 } else {
1441                         /* no leafmethod -> distinguish between temp and saved register */
1442                         if ( reg->nregdesc[alt->lt->reg] == REG_SAV)
1443                                 reg->sav_reg[reg->sav_top++] = alt->lt->reg;
1444                         else
1445                                 reg->tmp_reg[reg->tmp_top++] = alt->lt->reg;
1446                 }
1447         }
1448 }
1449
1450 void spill_at_intervall(methodinfo *m, lsradata *ls, struct lifetime *lt )
1451 {
1452         if (lt->savedvar || m->isleafmethod)
1453                 _spill_at_intervall(lt, &(ls->active_sav));
1454         else {
1455                 _spill_at_intervall(lt, &(ls->active_tmp));
1456                 if (lt->reg == -1) /* kein tmp mehr frei gewesen */
1457                         _spill_at_intervall(lt, &(ls->active_sav));
1458         }
1459 /*      if (lt->reg == -2) panic("spill_at_intervall: Keine Register mehr frei gewesen!\n"); */
1460 }
1461
1462 void _spill_at_intervall(struct lifetime *lt, struct active_lt **active)
1463 {
1464         struct active_lt *alt,*alt1;
1465         if (*active == NULL) {
1466                 lt->reg=-1;
1467                 return;
1468         }
1469         /* get last intervall from active */
1470         for (alt1=alt=*active; alt->next != NULL; alt1=alt, alt=alt->next);
1471
1472 #ifdef USAGE_COUNT
1473         if ((alt->lt->i_end > lt->i_end) || (alt->lt->usagecount < lt->usagecount)) {
1474 #else
1475         if (alt->lt->i_end > lt->i_end) {
1476 #endif
1477                         lt->reg=alt->lt->reg;
1478                         alt->lt->reg=-1;
1479
1480                         if (alt == *active)
1481                                 *active=(*active)->next;
1482                         else
1483                                 alt1->next=alt->next;
1484                         lsra_add_active(lt, active);
1485         } else {
1486                 lt->reg=-1;
1487         }
1488 }
1489
1490
1491 void lsra_calc_lifetime_length(methodinfo *m, lsradata *ls, codegendata *cd)
1492 {
1493         struct lifetime *lt;
1494         int i, lt_index;
1495         int lifetimecount;
1496 /*      struct stackslot *ss; */
1497         int *icount_block, icount;
1498
1499 #if 0
1500         int max_local_ss;
1501         int cum_local_ss,local_ss_count;
1502         int i_count;
1503 #endif
1504
1505         icount_block = DMNEW(int, m->basicblockcount);
1506         icount_block[0] = icount = 0;
1507         for (i=1; i < m->basicblockcount; i++) {
1508                 if (ls->sorted[i-1] != -1)
1509                         icount += m->basicblocks[ ls->sorted[i-1] ].icount;
1510                 if (ls->sorted[i] != -1)
1511                         icount_block[i] = icount;
1512         }
1513
1514 #ifdef LSRA_DEBUG
1515         printf("icount_block: ");
1516         for (i=0; i < m->basicblockcount; i++)
1517             printf("(%3i-%3i) ",i, icount_block[i]);
1518         printf("\n");
1519 #endif
1520
1521         /* extend lifetime over backedges */
1522         /* now iterate through lifetimes and expand them */
1523
1524 #if 0
1525         max_local_ss = cum_local_ss = 0;
1526 #endif
1527         lifetimecount = 0;
1528         for(lt_index = 0 ;lt_index < ls->lifetimecount; lt_index++) {
1529                 if ( ls->lifetime[lt_index].type != -1) { /* used lifetime */
1530                         ls->lt_used[lifetimecount ++] = lt_index; /* remember lt_index in lt_sorted */
1531                         lt = &(ls->lifetime[lt_index]);
1532 #if 0
1533                         local_ss_count = 0;
1534                         for (ss=lt->local_ss; ss != 0; ss = ss->next, local_ss_count++);
1535                         if (local_ss_count > max_local_ss) max_local_ss = local_ss_count;
1536                         cum_local_ss+=local_ss_count;
1537 #endif
1538
1539                         if (lt->bb_first_def == -1) {
1540 /*                              printf("--------- Warning: variable not defined!------------------vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end); */
1541                                 lt->bb_first_def = 0;
1542                                 lt->i_first_def = 0;
1543                         }
1544
1545 /*                      lt->i_start =lt->bb_first_def * ls->icount_max + lt->i_first_def; */
1546                         lt->i_start = icount_block[lt->bb_first_def] + lt->i_first_def;
1547
1548                         if (lt->bb_last_use == -1) {
1549 /*                              printf("--------- Warning: variable not used! --------------------vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end); */
1550                                 lt->bb_last_use = lt->bb_first_def;
1551                                 lt->i_last_use = lt->i_first_def;
1552                         }
1553
1554 /*                      lt->i_end = lt->bb_last_use * ls->icount_max + lt->i_last_use; */
1555                         lt->i_end = icount_block[lt->bb_last_use] + lt->i_last_use;
1556
1557                         if (lt->i_start > lt->i_end)
1558                                 printf("--------- Warning: last use before first def! ------------vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end);
1559
1560 #if 0
1561                         /* expand lifetimes in a exceptionhandler to at least the whole handler */
1562                         /* TODO do a loop analyze for the exceptionhandler*/
1563
1564                         /* every lifetime of a guarded area, which is used in the exc. handler, */
1565                         /* has to be expanded to at least the whole guarded area */
1566                         for (i=0; i < cd->exceptiontablelength; i++) {
1567                                 if ( !((bfirst > ls->ex[i].handler_max) || ( blast < ls->ex[i].handler_min)) ) {
1568                                         /* lifetime lt lies within the exceptionhandler */
1569                                         /* expand to at least the extends of this exceptionhandler */
1570
1571                                         /* -> Lifetime start has to be at minimum the start of the exceptionhandler */
1572                                         if (bfirst >= ls->ex[i].handler_min) {
1573                                                 bfirst=ls->ex[i].handler_min;
1574                                                 ifirst=0;
1575                                         }
1576                                         /* -> Lifetime end has to be at minimum the end of the exceptionhandler */
1577                                         if (blast <= ls->ex[i].handler_max) {
1578                                                 blast=ls->ex[i].handler_max;
1579                                                 ilast= m->basicblocks[ls->ex[i].handler_max].icount-1;
1580                                         }
1581                                 }
1582                         }
1583 #endif
1584
1585                         if (lt->bb_first_def != lt->bb_last_use) {
1586                                 /* Lifetime goes over more than one Basic Block ->  */
1587                                 /* check for necessary extension over backedges     */
1588                                 /* see lsra_get_backedges                           */
1589
1590                                 for (i=0; i < ls->backedge_count; i++) {
1591                                         if (!( (lt->bb_first_def > ls->backedge[i]->start) ||
1592                                                    (lt->bb_last_use < ls->backedge[i]->end) )) {
1593                                                 /* Live intervall intersects with a backedge */
1594                                                 /*                                      if (lt->bb_first_def <= ls->backedge[i]->start) */
1595                                                 /*                                              lt->i_start = (m->basicblockcount - ls->backedge[i]->start) * ls->icount_max; */
1596                                                 if (lt->bb_last_use <= ls->backedge[i]->start)
1597 /*                                                      lt->i_end = ls->backedge[i]->start * ls->icount_max +  m->basicblocks[ls->sorted[ls->backedge[i]->start]].icount-1; */
1598                                                         lt->i_end = icount_block[ls->backedge[i]->start] +  m->basicblocks[ls->sorted[ls->backedge[i]->start]].icount;
1599                                 }
1600                                 }
1601                         }
1602 #ifdef USAGE_PER_INSTR
1603                         lt->usagecount = lt->usagecount / ( lt->i_end - lt->i_start + 1);
1604 #endif
1605                 }
1606         }
1607 /*      printf("%5i %5i ====== \n", ls->lifetimecount, lifetimecount); */
1608         ls->lifetimecount = lifetimecount;
1609 #if 0
1610         i_count=0;
1611         for (i=0; i<m->basicblockcount; i++)
1612                 if (m->basicblocks[i].flags >= BBREACHED)
1613                         i_count+=m->basicblocks[i].icount;
1614         printf("Instr: %5i Lifetimes: %5i Local SS Max: %4i Cum: %4i m->maxlifetimes %4i\n",i_count, lifetimecount, max_local_ss, cum_local_ss, m->maxlifetimes);
1615 #endif
1616 }
1617
1618 #ifdef LSRA_PRINTLIFETIMES
1619 void print_lifetimes(registerdata *rd, lsradata *ls, int *lt, int lifetimecount)
1620 {
1621         struct lifetime *n;
1622         int lt_index;
1623         int type,flags,regoff,varkind;
1624
1625         for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
1626                 n = &(ls->lifetime[lt[lt_index]]);
1627                 if (n->v_index < 0) { /* stackslot */
1628                         type = n->local_ss->s->type;
1629                         flags=n->local_ss->s->flags;
1630                         regoff=n->local_ss->s->regoff;
1631                         varkind=n->local_ss->s->varkind;
1632                 } else { /* local var */
1633                         if (rd->locals[n->v_index][n->type].type>=0) {
1634                                 type = rd->locals[n->v_index][n->type].type;
1635                                 flags=rd->locals[n->v_index][n->type].flags;
1636                                 regoff=rd->locals[n->v_index][n->type].regoff;
1637                                 varkind=-1;
1638                         } else
1639                                 panic("Type Data mismatch 3\n");
1640                 }
1641                 printf("i_Start: %3i(%3i,%3i) i_stop: %3i(%3i,%3i) reg: %3i VI: %3i type: %3i flags: %3i varkind: %3i usage: %3li ltflags: %xi \n",n->i_start, ls->sorted[n->bb_first_def], n->i_first_def,n->i_end, ls->sorted[n->bb_last_use], n->i_last_use,regoff,n->v_index,type,flags, varkind, n->usagecount, n->flags);
1642         }
1643         printf( "%3i Lifetimes printed \n",lt_index);
1644 }
1645 #endif
1646
1647 struct stackslot *lsra_make_ss(stackptr s, int bb_index)
1648 {
1649         struct stackslot *ss;
1650
1651         ss=DNEW(struct stackslot);
1652         ss->bb=bb_index;
1653         ss->s=s;
1654         return ss;
1655 }
1656
1657 void lsra_add_ss(struct lifetime *lt, stackptr s) {
1658         struct stackslot *ss;
1659         /* Stackslot noch nicht eingetragen? */
1660
1661         if (s->varnum != lt->v_index) {
1662                 ss = DNEW(struct stackslot);
1663                 ss->s = s;
1664                 ss->s->varnum = lt->v_index;
1665                 ss->next = lt->local_ss;
1666                 lt->local_ss = ss;
1667                 if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
1668                 if (s != NULL) lt->type = s->type;
1669         }
1670 }
1671
1672 struct lifetime *get_ss_lifetime(lsradata *ls, stackptr s) {
1673         struct lifetime *n;
1674
1675         if (s->varnum >= 0) { /* new Lifetime *//* existiert noch nicht -> neue anlegen */
1676                 n = &(ls->lifetime[-ls->v_index - 1]);
1677                 n->type = s->type;
1678                 n->v_index = ls->v_index--;
1679                 n->usagecount = 0;
1680
1681                 n->bb_last_use = -1;
1682                 n->bb_first_def = -1;
1683                 n->local_ss = NULL;
1684                 n->savedvar = 0;
1685                 n->flags = 0;
1686         } else
1687                 n = &(ls->lifetime[-s->varnum - 1]);
1688
1689         lsra_add_ss( n, s);
1690         return n;
1691 }
1692
1693 #define lsra_new_stack(ls, s, block, instr) if ((s)->varkind != ARGVAR) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
1694 void _lsra_new_stack(lsradata *ls, stackptr s, int block, int instr, int store)
1695 {
1696         struct lifetime *n;
1697
1698         if (s->varkind == LOCALVAR) {
1699                 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_STORE);
1700         } else /* if (s->varkind != ARGVAR) */ {
1701
1702                 n=get_ss_lifetime( ls, s );
1703
1704                 if (store == LSRA_BB_IN)
1705                         n->flags |= JOIN_BB;
1706                 /* remember first def -> overwrite everytime */
1707                 n->bb_first_def = ls->sorted_rev[block];
1708                 n->i_first_def = instr;
1709
1710                 n->usagecount+=ls->nesting[ls->sorted_rev[block]];
1711         }
1712 }
1713
1714 #define IS_TEMP_VAR(s) ( ((s)->varkind != ARGVAR) && ((s)->varkind != LOCALVAR) )
1715
1716 #define lsra_join_3_stack(ls, dst, src1, src2, join_type) \
1717         if ( IS_TEMP_VAR(dst) ) { \
1718                 join_ret = false; \
1719                 if ( IS_TEMP_VAR(src1) && ((src1)->type == (dst)->type)) { \
1720                         join_ret = lsra_join_ss(ls, dst, src1, join_type);                                                              \
1721                 } \
1722                 if ( (!join_ret) && IS_TEMP_VAR(src2) && ((src2)->type == (dst)->type)) { \
1723                         lsra_join_ss(ls, dst, src2, join_type); \
1724                 } \
1725         }
1726
1727 #define lsra_join_2_stack(ls, dst, src, join_type) \
1728         if ( IS_TEMP_VAR(dst) ) { \
1729                 if ( (IS_TEMP_VAR(src)) && ((src)->type == (dst)->type)) {      \
1730                         lsra_join_ss(ls, dst, src, join_type); \
1731                 } \
1732         }
1733
1734 #define lsra_join_dup(ls, s1, s2, s3) {                            \
1735                 if (IS_TEMP_VAR(s1)) {                                             \
1736                         join_ret = false;                                                  \
1737                         if (IS_TEMP_VAR(s2))                                   \
1738                                 join_ret = lsra_join_ss(ls, s1, s2, JOIN);      /* undangerous join! */        \
1739                         if (IS_TEMP_VAR(s3)) {                                 \
1740                                 if (join_ret)   /* first join succesfull -> second of type JOIN_DUP */     \
1741                     lsra_join_ss(ls, s1, s3, JOIN_DUP); \
1742                                 else                                                                    \
1743                         lsra_join_ss(ls, s1, s3, JOIN); /* first join did not happen -> second undangerous */ \
1744                     }                                                                           \
1745                 }                                                                                       \
1746         if (IS_TEMP_VAR(s2) && IS_TEMP_VAR(s3))         \
1747                 lsra_join_ss(ls, s2, s3, JOIN_DUP);                 \
1748         }
1749
1750 #if 0
1751 #ifdef JOIN_DEST_STACK
1752 #define lsra_join_dup(ls, s1, s2, s3) { \
1753                 if (IS_TEMP_VAR(s1)) {                          \
1754                         if (IS_TEMP_VAR(s2))                    \
1755                                 lsra_join_ss(ls, s1, s2, JOIN_DUP);     \
1756                         else                                                    \
1757                                 if (IS_TEMP_VAR(s3))            \
1758                                         lsra_join_ss(ls, s1, s3, JOIN_DUP);     \
1759                 }                                                                       \
1760 }
1761 #else
1762 #define lsra_join_dup(ls, s1, s2, s3) {             \
1763                 if (IS_TEMP_VAR(s1)) {                                  \
1764                         if (IS_TEMP_VAR(s2))                            \
1765                                 lsra_join_ss(ls, s1, s2, JOIN_DUP);             \
1766                         if (IS_TEMP_VAR(s3))                            \
1767                                 lsra_join_ss(ls, s1, s3, JOIN_DUP);             \
1768                 }                                                                               \
1769                 if (IS_TEMP_VAR(s2) && IS_TEMP_VAR(s3)) \
1770                         lsra_join_ss(ls, s2, s3, JOIN_DUP);                     \
1771 }
1772 #endif
1773 #endif
1774
1775 #define lsra_from_stack(ls, s, block, instr) if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
1776 #define lsra_pop_from_stack(ls, s, block, instr) if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
1777 void _lsra_from_stack(lsradata *ls, stackptr s, int block, int instr, int store)
1778 {
1779         struct lifetime *n;
1780
1781         if (s->varkind == LOCALVAR) {
1782                 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
1783         } else /* if (s->varkind != ARGVAR) */ {
1784
1785                 n=get_ss_lifetime( ls, s );
1786
1787                 if (store == LSRA_BB_OUT)
1788                         n->flags |= JOIN_BB;
1789                 if (n->flags & JOINING)
1790                         n->flags &= ~JOINING;
1791                 n->usagecount+=ls->nesting[ls->sorted_rev[block]];
1792
1793                 /* remember last USE, so only write, if USE Field is undefined (==-1) */
1794                 if (n->bb_last_use == -1) {
1795                         n->bb_last_use = ls->sorted_rev[block];
1796                         n->i_last_use = instr;
1797                 }
1798         }
1799 }
1800
1801 void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr, int store)
1802 {
1803         struct lifetime *n;
1804
1805         n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);
1806
1807         if (n->type == -1) { /* new local lifetime */
1808 #ifdef LSRA_DEBUG
1809 /*              if (store != LSRA_STORE) printf("lsra_local_store: Read before write Local var: %i paramcount: ?\n", v_index); */
1810 #endif
1811                 n->local_ss=NULL;
1812                 n->v_index=v_index;
1813                 n->type=type;
1814                 n->savedvar = SAVEDVAR;
1815                 n->flags = 0;
1816                 n->usagecount = 0;
1817
1818                 n->bb_last_use = -1;
1819                 n->bb_first_def = -1;
1820         }
1821         n->usagecount+=ls->nesting[ls->sorted_rev[block]];
1822         /* add access at (block, instr) to intruction list */
1823         if (store == LSRA_LOAD) {
1824                 /* remember last USE, so only write, if USE Field is undefined (==-1) */
1825                 if (n->bb_last_use == -1) {
1826                         n->bb_last_use = ls->sorted_rev[block];
1827                         n->i_last_use = instr;
1828                 }
1829         } else {
1830                 /* store == LSRA_STORE, remember first def -> overwrite everytime */
1831                 n->bb_first_def = ls->sorted_rev[block];
1832                 n->i_first_def = instr;
1833         }
1834 }
1835
1836 #ifdef LSRA_DEBUG
1837 void lsra_dump_stack(stackptr s)
1838 {
1839         while (s!=NULL) {
1840                 printf("%p(R%3i N%3i K%3i T%3i F%3i) ",(void *)s,s->regoff, s->varnum, s->varkind, s->type, s->flags);
1841                 s=s->prev;
1842         }
1843         printf("\n");
1844 }
1845 #endif
1846
1847
1848 void lsra_scan_registers_canditates(methodinfo *m, lsradata *ls, int b_index)
1849 {
1850         int i;
1851         int opcode;
1852         int iindex;
1853         stackptr    src;
1854         stackptr    dst;
1855         instruction *iptr;
1856         bool join_ret; /* for lsra_join* Macros */
1857 #if defined(LSRA_USES_REG_RES)
1858         int  v_index_min_before_instruction;
1859         int v_index_min[REG_RES_CNT];
1860
1861         for (i=0; i < REG_RES_CNT; i++) {
1862                 ls->reg_res_free[i] = -1;
1863                 v_index_min[i] = ls->v_index;
1864         }
1865 #endif
1866
1867         src = m->basicblocks[b_index].instack;
1868         if (m->basicblocks[b_index].type != BBTYPE_STD) {
1869 #ifdef LSRA_DEBUG
1870                 if (src == NULL)
1871                         panic("No Incoming Stackslot for Exception or Subroutine Basic Block\n");
1872 #endif
1873                 lsra_new_stack(ls, src, b_index, 0);
1874                 if (src->varkind == STACKVAR)
1875                         src->varkind = TEMPVAR;
1876                 src = src->prev;
1877         }
1878         for (;src != NULL; src=src->prev) {
1879                 if (src->varkind == ARGVAR )  /* no ARGVAR possible at BB Boundaries with LSRA! -> change to TEMPVAR */
1880                         src->varkind = TEMPVAR;
1881                 else if (src->varkind == LOCALVAR )
1882                         panic("LOCALVAR at basicblock instack\n"); /* only allowed for top most ss at sbr or exh entries! */
1883                 else {
1884                         if (src->varkind == STACKVAR )  /* no Interfaces at BB Boundaries with LSRA! -> change to TEMPVAR */
1885                                 src->varkind = TEMPVAR;
1886                         _lsra_new_stack(ls, src, b_index, iindex, LSRA_BB_IN);
1887                 }
1888         }
1889         src = m->basicblocks[b_index].outstack;
1890         for (;src != NULL; src=src->prev) {
1891                 if (src->varkind == ARGVAR )
1892                         panic("ARGVAR at basicblock outstack\n");
1893                 else if (src->varkind == LOCALVAR )
1894                         panic("LOCALVAR at basicblock outstack\n");
1895                 else {
1896                         if (src->varkind == STACKVAR )  /* no Interfaces at BB Boundaries with LSRA! -> change to TEMPVAR */
1897                                 src->varkind = TEMPVAR;
1898                         _lsra_from_stack(ls, src, b_index, iindex, LSRA_BB_OUT);
1899                 }
1900         }
1901
1902         iptr = m->basicblocks[b_index].iinstr;
1903         iindex = m->basicblocks[b_index].icount - 1;
1904         iptr+=iindex;
1905
1906         if ((iindex+1) > ls->icount_max)
1907                 ls->icount_max = iindex+1;
1908
1909
1910         for (;iindex >= 0; iindex--, iptr--)  {
1911                 dst = iptr->dst;
1912                 opcode = iptr->opc;
1913                 if (iindex) /* > 0 */
1914                         src=(iptr-1)->dst;
1915                 else
1916                         src=m->basicblocks[b_index].instack;
1917 #if defined(LSRA_USES_REG_RES)
1918                 v_index_min_before_instruction = ls->v_index;
1919 #endif
1920 #ifdef LSRA_DEBUG
1921                 /*                              printf("bb: %3i bcount: %3i iindex: %3i ilen: %3i opcode: %3i %s\n",b_index,m->basicblockcount,iindex,len,opcode,icmd_names[opcode]); */
1922                 /*                              lsra_dump_stack(src); */
1923                 /*                              lsra_dump_stack(dst); */
1924 #endif
1925                 switch (opcode) {
1926
1927                         /* pop 0 push 0 */
1928                 case ICMD_RET:
1929                         lsra_usage_local(ls,iptr->op1,TYPE_ADR, b_index,iindex,LSRA_LOAD); /* local read (return adress) */
1930                         break;
1931                 case ICMD_JSR:
1932                 case ICMD_GOTO:
1933                 case ICMD_NOP:
1934                 case ICMD_ELSE_ICONST:
1935                 case ICMD_CHECKEXCEPTION:
1936                 case ICMD_CHECKASIZE:
1937                 case ICMD_PUTSTATICCONST:
1938                 case ICMD_INLINE_START:
1939                 case ICMD_INLINE_END:
1940                 case ICMD_RETURN:
1941                         break;
1942
1943                 case ICMD_IINC:
1944                         lsra_usage_local(ls,iptr->op1,TYPE_INT, b_index,iindex,LSRA_LOAD); /* local */
1945                         lsra_usage_local(ls,iptr->op1,TYPE_INT, b_index,iindex,LSRA_STORE); /* local = local+<const> */
1946                         break;
1947
1948                         /* pop 0 push 1 const */
1949                         /* const->stack */
1950
1951                 case ICMD_ICONST:
1952                 case ICMD_LCONST:
1953                 case ICMD_FCONST:
1954                 case ICMD_DCONST:
1955                 case ICMD_ACONST:
1956                         /* new stack slot */
1957                         lsra_new_stack(ls,dst,b_index,iindex); /* const->stack */
1958                         break;
1959
1960                         /* pop 0 push 1 load */
1961                         /* local->stack */
1962
1963                 case ICMD_ILOAD:
1964                 case ICMD_LLOAD:
1965                 case ICMD_FLOAD:
1966                 case ICMD_DLOAD:
1967                 case ICMD_ALOAD:
1968                         if (dst->varkind != LOCALVAR) {
1969                                 lsra_usage_local(ls,iptr->op1,opcode-ICMD_ILOAD, b_index,iindex,LSRA_LOAD); /* local->value */
1970                                 lsra_new_stack(ls,dst,b_index,iindex); /* value->stack */
1971                         } else if (dst->varnum != iptr->op1) {
1972                                 lsra_usage_local(ls,iptr->op1,opcode-ICMD_ILOAD, b_index,iindex,LSRA_LOAD); /* local->value */
1973                                 lsra_usage_local(ls,dst->varnum,opcode-ICMD_ILOAD, b_index,iindex,LSRA_STORE); /* local->value */
1974                         }
1975
1976                         break;
1977
1978                         /* pop 2 push 1 */
1979                         /* Stack(arrayref,index)->stack */
1980
1981                 case ICMD_IALOAD:
1982                 case ICMD_LALOAD:
1983                 case ICMD_FALOAD:
1984                 case ICMD_DALOAD:
1985                 case ICMD_AALOAD:
1986
1987                 case ICMD_BALOAD:
1988                 case ICMD_CALOAD:
1989                 case ICMD_SALOAD:
1990
1991                         lsra_from_stack(ls, src,b_index,iindex); /* stack->index */
1992                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack->arrayref */
1993                         lsra_new_stack(ls,dst,b_index,iindex); /* arrayref[index]->stack */
1994                         break;
1995
1996                         /* pop 3 push 0 */
1997                         /* stack(arrayref,index,value)->arrayref[index]=value */
1998
1999                 case ICMD_IASTORE:
2000                 case ICMD_LASTORE:
2001                 case ICMD_FASTORE:
2002                 case ICMD_DASTORE:
2003                 case ICMD_AASTORE:
2004
2005                 case ICMD_BASTORE:
2006                 case ICMD_CASTORE:
2007                 case ICMD_SASTORE:
2008
2009                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2010                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> index */
2011                         lsra_from_stack(ls, src->prev->prev,b_index,iindex); /* stack -> arrayref */
2012                         break;
2013
2014                 case ICMD_POP: /* throw away a stackslot -> check if used anyway! */
2015                         lsra_pop_from_stack(ls,src,b_index,iindex);
2016                         break;
2017
2018                         /* pop 1 push 0 store */
2019                         /* stack -> local */
2020
2021                 case ICMD_ISTORE:
2022                 case ICMD_LSTORE:
2023                 case ICMD_FSTORE:
2024                 case ICMD_DSTORE:
2025                 case ICMD_ASTORE:
2026                         if (src->varkind != LOCALVAR) {
2027                                 lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2028                                 lsra_usage_local(ls,iptr->op1,opcode-ICMD_ISTORE, b_index,iindex,LSRA_STORE); /* local->value */
2029                         } else if (src->varnum != iptr->op1) {
2030                                 lsra_usage_local(ls,iptr->op1,opcode-ICMD_ISTORE, b_index,iindex,LSRA_STORE); /* local->value */
2031                                 lsra_usage_local(ls,src->varnum,opcode-ICMD_ISTORE, b_index,iindex,LSRA_LOAD); /* local->value */
2032                         }
2033                         break;
2034
2035                         /* pop 1 push 0 */
2036
2037                 case ICMD_IRETURN:
2038                 case ICMD_LRETURN:
2039                 case ICMD_FRETURN:
2040                 case ICMD_DRETURN:
2041                 case ICMD_ARETURN: /* stack(value) -> [empty] */
2042                 case ICMD_ATHROW: /* stack(objref) -> undefined */
2043                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2044                         break;
2045                 case ICMD_PUTSTATIC: /* stack(value) -> static_field */
2046                 case ICMD_PUTFIELDCONST:
2047                         /* pop 1 push 0 branch */
2048                 case ICMD_NULLCHECKPOP: /****** ????? -1 -> stack *********/
2049                 case ICMD_MONITORENTER:
2050                 case ICMD_MONITOREXIT:
2051                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2052                         break;
2053
2054                 case ICMD_IFNULL: /* stack(value) -> branch? */
2055                 case ICMD_IFNONNULL:
2056                 case ICMD_IFEQ:
2057                 case ICMD_IFNE:
2058                 case ICMD_IFLT:
2059                 case ICMD_IFGE:
2060                 case ICMD_IFGT:
2061                 case ICMD_IFLE:
2062                 case ICMD_IF_LEQ:
2063                 case ICMD_IF_LNE:
2064                 case ICMD_IF_LLT:
2065                 case ICMD_IF_LGE:
2066                 case ICMD_IF_LGT:
2067                 case ICMD_IF_LLE:
2068                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2069                         break;
2070
2071                         /* pop 1 push 0 table branch */
2072
2073                 case ICMD_TABLESWITCH:
2074                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2075                         break;
2076                 case ICMD_LOOKUPSWITCH:
2077                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2078                         break;
2079
2080                         /* pop 2 push 0 */
2081
2082                 case ICMD_POP2: /* throw away 2 stackslots -> check if used anyway! */
2083                         lsra_pop_from_stack(ls,src,b_index,iindex);
2084                         lsra_pop_from_stack(ls,src->prev,b_index,iindex);
2085                         break;
2086
2087                         /* pop 2 push 0 branch */
2088
2089                 case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
2090                 case ICMD_IF_ICMPNE:
2091                 case ICMD_IF_ICMPLT:
2092                 case ICMD_IF_ICMPGE:
2093                 case ICMD_IF_ICMPGT:
2094                 case ICMD_IF_ICMPLE:
2095
2096                 case ICMD_IF_LCMPEQ:
2097                 case ICMD_IF_LCMPNE:
2098                 case ICMD_IF_LCMPLT:
2099                 case ICMD_IF_LCMPGE:
2100                 case ICMD_IF_LCMPGT:
2101                 case ICMD_IF_LCMPLE:
2102
2103                 case ICMD_IF_ACMPEQ:
2104                 case ICMD_IF_ACMPNE:
2105                         lsra_from_stack(ls, src,b_index,iindex);           /* stack -> value*/
2106                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> objref*/
2107                         break;
2108
2109                         /* pop 2 push 0 */
2110
2111                 case ICMD_PUTFIELD: /* stack(objref,value) -> objref->method=value */
2112
2113                 case ICMD_IASTORECONST:
2114                 case ICMD_LASTORECONST:
2115                 case ICMD_AASTORECONST:
2116                 case ICMD_BASTORECONST:
2117                 case ICMD_CASTORECONST:
2118                 case ICMD_SASTORECONST:
2119                         lsra_from_stack(ls, src,b_index,iindex);           /* stack -> value*/
2120                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> objref*/
2121                         break;
2122
2123                         /* pop 0 push 1 dup */
2124                         /* merge dupped vars??? */
2125                 case ICMD_DUP: /* src == dst->prev, src -> dst */
2126                         /* lsra_from_stack(ls, src,b_index,iindex);*/ /* just inc usage count? */
2127                         lsra_new_stack(ls,dst,b_index,iindex);
2128
2129 /* #if (defined(JOIN_DUP_STACK) && !defined(JOIN_DEST_STACK)) */
2130 #ifdef JOIN_DUP_STACK
2131                         /* src is identical to dst->prev */
2132                         lsra_join_2_stack(ls, src, dst, JOIN_DUP);
2133 #endif
2134                         break;
2135
2136                         /* pop 0 push 2 dup */
2137
2138                 case ICMD_DUP2:
2139                         /* lsra_from_stack(ls, src,b_index,iindex); */ /* just inc usage count? */
2140                         /* lsra_from_stack(ls, src->prev,b_index,iindex); */ /* just inc usage count? */
2141                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2142                         lsra_new_stack(ls,dst,b_index,iindex);
2143
2144 /* #if (defined(JOIN_DUP_STACK) && !defined(JOIN_DEST_STACK)) */
2145 #ifdef JOIN_DUP_STACK
2146                         lsra_join_2_stack(ls, src, dst, JOIN_DUP);
2147                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN_DUP);
2148                         /* src is identical to dst->prev->prev */
2149                         /* src->prev is identical to dst->prev->prev->prev */
2150 #endif
2151                         break;
2152
2153                         /* pop 2 push 3 dup */
2154
2155                 case ICMD_DUP_X1:
2156                         lsra_from_stack(ls, src, b_index, iindex);
2157                         lsra_from_stack(ls, src->prev, b_index, iindex);
2158                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2159                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2160                         lsra_new_stack(ls, dst, b_index, iindex);
2161 #ifdef JOIN_DUP_STACK
2162                         lsra_join_dup(ls, src, dst, dst->prev->prev);
2163                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN);
2164 #endif
2165                         break;
2166
2167                         /* pop 3 push 4 dup */
2168
2169                 case ICMD_DUP_X2:
2170                         lsra_from_stack(ls, src,b_index,iindex);
2171                         lsra_from_stack(ls, src->prev,b_index,iindex);
2172                         lsra_from_stack(ls, src->prev->prev,b_index,iindex);
2173                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2174                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2175                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2176                         lsra_new_stack(ls,dst,b_index,iindex);
2177
2178 #ifdef JOIN_DUP_STACK
2179                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev);
2180                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN);
2181                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2182 #endif
2183                         break;
2184
2185                         /* pop 3 push 5 dup */
2186
2187                 case ICMD_DUP2_X1:
2188                         lsra_from_stack(ls, src,b_index,iindex);
2189                         lsra_from_stack(ls, src->prev,b_index,iindex);
2190                         lsra_from_stack(ls, src->prev->prev,b_index,iindex);
2191                         lsra_new_stack(ls,dst->prev->prev->prev->prev,b_index,iindex);
2192                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2193                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2194                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2195                         lsra_new_stack(ls,dst,b_index,iindex);
2196
2197 #ifdef JOIN_DUP_STACK
2198                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev);
2199                         lsra_join_dup(ls, src->prev, dst->prev, dst->prev->prev->prev->prev);
2200                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2201 #endif
2202                         break;
2203
2204                         /* pop 4 push 6 dup */
2205
2206                 case ICMD_DUP2_X2:
2207                         lsra_from_stack(ls, src,b_index,iindex);
2208                         lsra_from_stack(ls, src->prev,b_index,iindex);
2209                         lsra_from_stack(ls, src->prev->prev,b_index,iindex);
2210                         lsra_from_stack(ls, src->prev->prev->prev,b_index,iindex);
2211                         lsra_new_stack(ls,dst->prev->prev->prev->prev->prev,b_index,iindex);
2212                         lsra_new_stack(ls,dst->prev->prev->prev->prev,b_index,iindex);
2213                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2214                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2215                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2216                         lsra_new_stack(ls,dst,b_index,iindex);
2217
2218 #ifdef JOIN_DUP_STACK
2219                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev->prev);
2220                         lsra_join_dup(ls, src->prev, dst->prev, dst->prev->prev->prev->prev->prev);
2221                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2222                         lsra_join_2_stack(ls, src->prev->prev->prev, dst->prev->prev->prev, JOIN);
2223 #endif
2224                         break;
2225
2226                         /* pop 2 push 2 swap */
2227
2228                 case ICMD_SWAP:
2229                         lsra_from_stack(ls, src,b_index,iindex);
2230                         lsra_from_stack(ls, src->prev,b_index,iindex);
2231                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2232                         lsra_new_stack(ls,dst,b_index,iindex);
2233
2234                         lsra_join_2_stack(ls, src->prev, dst, JOIN);
2235                         lsra_join_2_stack(ls, src, dst->prev, JOIN);
2236
2237                         break;
2238
2239                         /* pop 2 push 1 */
2240
2241                 case ICMD_IADD:
2242                 case ICMD_IMUL:
2243
2244                 case ICMD_ISHL:
2245                 case ICMD_ISHR:
2246                 case ICMD_IUSHR:
2247                 case ICMD_IAND:
2248                 case ICMD_IOR:
2249                 case ICMD_IXOR:
2250
2251                 case ICMD_LADD:
2252                 case ICMD_LSUB:
2253                 case ICMD_LMUL:
2254
2255                 case ICMD_LOR:
2256                 case ICMD_LAND:
2257                 case ICMD_LXOR:
2258
2259                 case ICMD_LSHL:
2260                 case ICMD_LSHR:
2261                 case ICMD_LUSHR:
2262
2263                 case ICMD_FADD:
2264                 case ICMD_FSUB:
2265                 case ICMD_FMUL:
2266
2267                 case ICMD_DADD:
2268                 case ICMD_DSUB:
2269                 case ICMD_DMUL:
2270                 case ICMD_DDIV:
2271                 case ICMD_DREM:
2272                         lsra_from_stack(ls, src,b_index,iindex);
2273                         lsra_from_stack(ls, src->prev,b_index,iindex);
2274                         lsra_new_stack(ls,dst,b_index,iindex);
2275 #ifdef JOIN_DEST_STACK
2276                         lsra_join_3_stack(ls, dst, src->prev, src, JOIN_OP);
2277 #endif
2278                         break;
2279
2280                 case ICMD_ISUB:
2281                         lsra_from_stack(ls, src, b_index, iindex);
2282                         lsra_from_stack(ls, src->prev,b_index,iindex);
2283                         lsra_new_stack(ls, dst, b_index, iindex);
2284 #ifdef JOIN_DEST_STACK
2285                         lsra_join_2_stack(ls, src, dst, JOIN_OP);
2286 #endif
2287                         break;
2288                 case ICMD_IDIV:
2289                 case ICMD_IREM:
2290
2291                 case ICMD_LDIV:
2292                 case ICMD_LREM:
2293
2294                 case ICMD_FDIV:
2295                 case ICMD_FREM:
2296
2297                 case ICMD_LCMP:
2298                 case ICMD_FCMPL:
2299                 case ICMD_FCMPG:
2300                 case ICMD_DCMPL:
2301                 case ICMD_DCMPG:
2302                         lsra_from_stack(ls, src,b_index,iindex);
2303                         lsra_from_stack(ls, src->prev,b_index,iindex);
2304                         lsra_new_stack(ls,dst,b_index,iindex);
2305                         break;
2306
2307                         /* pop 1 push 1 */
2308                 case ICMD_IADDCONST:
2309                 case ICMD_ISUBCONST:
2310                 case ICMD_IMULCONST:
2311                 case ICMD_IMULPOW2:
2312                 case ICMD_IDIVPOW2:
2313                 case ICMD_IREMPOW2:
2314                 case ICMD_IANDCONST:
2315                 case ICMD_IORCONST:
2316                 case ICMD_IXORCONST:
2317                 case ICMD_ISHLCONST:
2318                 case ICMD_ISHRCONST:
2319                 case ICMD_IUSHRCONST:
2320
2321                 case ICMD_LADDCONST:
2322                 case ICMD_LSUBCONST:
2323                 case ICMD_LMULCONST:
2324                 case ICMD_LMULPOW2:
2325                 case ICMD_LDIVPOW2:
2326                 case ICMD_LREMPOW2:
2327                 case ICMD_LANDCONST:
2328                 case ICMD_LORCONST:
2329                 case ICMD_LXORCONST:
2330                 case ICMD_LSHLCONST:
2331                 case ICMD_LSHRCONST:
2332                 case ICMD_LUSHRCONST:
2333
2334                 case ICMD_IFEQ_ICONST:
2335                 case ICMD_IFNE_ICONST:
2336                 case ICMD_IFLT_ICONST:
2337                 case ICMD_IFGE_ICONST:
2338                 case ICMD_IFGT_ICONST:
2339                 case ICMD_IFLE_ICONST:
2340
2341                 case ICMD_INEG:
2342                 case ICMD_INT2BYTE:
2343                 case ICMD_INT2CHAR:
2344                 case ICMD_INT2SHORT:
2345                 case ICMD_LNEG:
2346                 case ICMD_FNEG:
2347                 case ICMD_DNEG:
2348
2349                 case ICMD_I2L:
2350                 case ICMD_I2F:
2351                 case ICMD_I2D:
2352                 case ICMD_L2I:
2353                 case ICMD_L2F:
2354                 case ICMD_L2D:
2355                 case ICMD_F2I:
2356                 case ICMD_F2L:
2357                 case ICMD_F2D:
2358                 case ICMD_D2I:
2359                 case ICMD_D2L:
2360                 case ICMD_D2F:
2361
2362                 case ICMD_CHECKCAST:
2363                         lsra_from_stack(ls, src, b_index, iindex);
2364                         lsra_new_stack(ls, dst, b_index, iindex);
2365 #ifdef JOIN_DEST_STACK
2366                         lsra_join_2_stack(ls, src, dst, JOIN_OP);
2367 #endif
2368                         break;
2369
2370                 case ICMD_ARRAYLENGTH:
2371                 case ICMD_INSTANCEOF:
2372
2373                 case ICMD_NEWARRAY:
2374                 case ICMD_ANEWARRAY:
2375
2376                 case ICMD_GETFIELD:
2377                         lsra_from_stack(ls, src,b_index,iindex);
2378                         lsra_new_stack(ls,dst,b_index,iindex);
2379                         break;
2380
2381                         /* pop 0 push 1 */
2382
2383                 case ICMD_GETSTATIC:
2384                 case ICMD_NEW:
2385                         lsra_new_stack(ls,dst,b_index,iindex);
2386                         break;
2387
2388                         /* pop many push any */
2389                 case ICMD_INVOKEVIRTUAL:
2390                 case ICMD_INVOKESPECIAL:
2391                 case ICMD_INVOKESTATIC:
2392                 case ICMD_INVOKEINTERFACE:
2393                         i = iptr->op1;
2394                         while (--i >= 0) {
2395                                 lsra_from_stack(ls, src,b_index,iindex);
2396                                 src = src->prev;
2397                         }
2398                         if (((methodinfo*)iptr->val.a)->returntype != TYPE_VOID) {
2399                                 lsra_new_stack(ls,dst,b_index,iindex);
2400                         }
2401                         break;
2402
2403                 case ICMD_BUILTIN3:
2404                         lsra_from_stack(ls, src,b_index,iindex);
2405                         src = src->prev;
2406                 case ICMD_BUILTIN2:
2407                         lsra_from_stack(ls, src,b_index,iindex);
2408                         src = src->prev;
2409                 case ICMD_BUILTIN1:
2410                         lsra_from_stack(ls, src,b_index,iindex);
2411                         src = src->prev; /* ??????????? */
2412                         if (iptr->op1 != TYPE_VOID)
2413                                 lsra_new_stack(ls,dst,b_index,iindex);
2414                         break;
2415
2416                 case ICMD_MULTIANEWARRAY:
2417                         i = iptr->op1;
2418                         while (--i >= 0) {
2419                                 lsra_from_stack(ls, src,b_index,iindex);
2420                                 src = src->prev;
2421                         }
2422                         lsra_new_stack(ls,dst,b_index,iindex);
2423                         break;
2424
2425                 default:
2426                         printf("ICMD %d at %d\n", iptr->opc, (int)(iptr - m->instructions));
2427                         panic("Missing ICMD code during register allocation");
2428                 } /* switch */
2429
2430 #if defined(LSRA_USES_REG_RES)
2431                 if (opt_lsra)
2432                 {
2433                         int length, maxlength, j;
2434                         int index, reg_res,start_iindex;
2435                         struct stackslot * ss;
2436                         struct lifetime *n;
2437
2438
2439                         for (j=0, reg_res = icmd_uses_reg_res[opcode][REG_RES_CNT]; j < REG_RES_CNT; j++, reg_res=(reg_res+1)%REG_RES_CNT) {
2440                                 if (reg_res == -1) reg_res = EDX; /* patch because icmd_uses_reg_res [][REG_RES_CNT] ist defaulting to -1 */
2441                                 maxlength = -1;
2442                                 index = -1;
2443                                 if ((iindex == 0) || (icmd_uses_reg_res[opcode][reg_res])) {
2444                                         if (ls->reg_res_free[reg_res] != -1) {
2445                                                 /* reg_res is free from ls->reg_res_free[] til here (iindex) */
2446                                                 /* now search for the longest lifetime, which fits in this intervall */
2447                                                 /* and if found assign edx to it */
2448                                                 if (icmd_uses_reg_res[opcode][reg_res] & D) /* ICMD destroys REG_RES as destination operand */
2449                                                         start_iindex = iindex +1;
2450                                                 else
2451                                                         start_iindex = iindex;
2452                                                 for (i = (-v_index_min[reg_res] - 1); i < (-ls->v_index -1); i++) {
2453
2454                                                         n = &(ls->lifetime[i]);
2455                                                         if (!(n->flags & (JOINING || JOIN_BB))) { /* do not assign reserved Regs to lifetimes not fully seen till now */
2456                                                                 if ((n->type == TYPE_INT) || (n->type == TYPE_ADR)) {
2457                                                                         if (n->savedvar == 0) {
2458                                                                                 if ((n->bb_last_use == n->bb_first_def) && (n->bb_last_use == ls->sorted_rev[b_index])) {
2459                                                                                         if ((n->i_last_use <= ls->reg_res_free[reg_res]) && (n->i_first_def >= start_iindex)) {
2460
2461                                                                                                 length = n->i_last_use - n->i_first_def;
2462                                                                                                 if (length > maxlength) {
2463                                                                                                         maxlength = length;
2464                                                                                                         index = i;
2465                                                                                                 }
2466                                                                                         }
2467                                                                                 }
2468                                                                         }
2469                                                                 }
2470                                                         }
2471                                                 }
2472                                         }
2473                                         if (icmd_uses_reg_res[opcode][reg_res] & S) /* ICMD destroys REG_RES as source operand */
2474                                                 ls->reg_res_free[reg_res] = -1;
2475                                         else
2476                                                 ls->reg_res_free[reg_res] = iindex;
2477
2478                                         if (index != -1) { /* there is a lifetime, which a reserved register can be assigned to */
2479 #ifdef LSRA_DEBUG
2480                                                 {
2481                                                         struct lifetime *n;
2482                                                         n=&(ls->lifetime[index]);
2483                                                         printf("------ SS Index %i in REG_RES %i bb %3i instr %3i - bb %3i instr %3i\n",  lsra_reg_res[reg_res], n->v_index, ls->sorted[n->bb_first_def], n->i_first_def, ls->sorted[n->bb_last_use], n->i_last_use);
2484                                                 }
2485 #endif
2486                                                 ls->lifetime[index].reg = lsra_reg_res[reg_res];
2487                                                 for (ss = ls->lifetime[index].local_ss; ss != NULL; ss=ss->next) {
2488                                                         ss->s->regoff = lsra_reg_res[reg_res];
2489                                                 }
2490                                                 ls->lifetime[index].type = -1; /* drop lifetime, no further processing required */
2491                                         }
2492
2493                                         v_index_min[reg_res] = v_index_min_before_instruction;
2494                                 } else
2495                                         if (ls->reg_res_free[reg_res] == -1)
2496                                                 ls->reg_res_free[reg_res] = iindex;
2497                         }
2498                 }
2499 #endif
2500
2501
2502         }
2503 }
2504
2505
2506 #ifdef LSRA_TESTLT
2507
2508 int lsra_test_lt(registerdata *rd, struct lifetime *n, int store, int *values, bool inmemory) {
2509         int value_index;
2510
2511         if (inmemory) {
2512                 value_index = n->reg;
2513         } else {
2514                 if (IS_FLT_DBL_TYPE(n->type)) {
2515                         value_index = rd->maxmemuse + rd->intregsnum + n->reg;
2516                 } else {
2517                         value_index = rd->maxmemuse + n->reg;
2518                 }
2519         }
2520
2521         if ((store == LSRA_LOAD) || (store == LSRA_POP)) {
2522                 if (values[value_index] == VS) {
2523                         if (n->i_start != -1) { /* not a parameter */
2524                                 printf("lsra_test: Warning: v_index %3i type %3i reg %3i", n->v_index, n->type, n->reg);
2525                                 if (inmemory)
2526                                         printf (" MEM");
2527                                 printf(" not initialized\n");
2528                         }
2529                 } else if (values[value_index] != n->v_index) {
2530                         printf("lsra_test: Error: v_index %3i  type %3i reg %3i", n->v_index, n->type, n->reg);
2531                         if (inmemory)
2532                                 printf (" MEM  ");
2533                         printf("Conflict: %3i \n", values[value_index]);
2534                         return (n->reg);
2535                 }
2536
2537         } else { /* LSRA_STORE */
2538                 values[value_index] = n->v_index;
2539         }
2540         return -1;
2541 }
2542
2543 int lsra_test_local( lsradata *ls, registerdata *rd, int v_index, int type, int store, int *values) {
2544         struct lifetime *n;
2545
2546         n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);
2547         if (n->type == -1)
2548                 panic("lsra_test: Local Var Lifetime not initialized!\n");
2549
2550         return lsra_test_lt(rd, n, store, values, rd->locals[v_index][type].flags & INMEMORY);
2551 }
2552
2553 #define lsra_test_new_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values, LSRA_STORE)
2554 #define lsra_test_from_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values,LSRA_LOAD)
2555 #define lsra_test_pop_from_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values,  LSRA_LOAD)
2556 int lsra_test_stack( lsradata *ls, registerdata *rd, stackptr s, int *values, int store)
2557 {
2558         struct lifetime *n;
2559         int value_index;
2560
2561         if (s->varkind == LOCALVAR) {
2562                 return lsra_test_local(ls, rd, s->varnum, s->type, store, values);
2563         }
2564         if (s->varkind != ARGVAR) {
2565                 if (s->varnum >=0)
2566                         panic("lsra_test: Stackslot not initialized!\n");
2567                 n = &(ls->lifetime[-s->varnum - 1]);
2568                 if (n->type == -1)
2569                         panic("lsra_test: Stackslot Lifetime not initialized!\n");
2570
2571                 return lsra_test_lt(rd, n, store, values, s->flags & INMEMORY);
2572         }
2573         return -1;
2574 }
2575
2576 int _test_lifetimes(methodinfo *m, lsradata *ls, registerdata *rd, int b_index, int *values)
2577 {
2578         struct stackslot *ss;
2579         int *v, i, j;
2580
2581
2582         int opcode;
2583         int iindex;
2584         stackptr    src;
2585         stackptr    dst;
2586         instruction *iptr;
2587
2588         struct _list *succ;
2589
2590         int ret;
2591
2592         ret = -1;
2593
2594
2595         iptr = m->basicblocks[b_index].iinstr;
2596
2597         dst = m->basicblocks[b_index].instack;
2598
2599         for (iindex =0 ;(iindex < m->basicblocks[b_index].icount) && (ret == -1) ; iindex++, iptr++)  {
2600                 src = dst;
2601                 dst = iptr->dst;
2602                 opcode = iptr->opc;
2603
2604                 switch (opcode) {
2605
2606                         /* pop 0 push 0 */
2607                 case ICMD_RET:
2608                         ret = lsra_test_local(ls, rd, iptr->op1, TYPE_ADR, LSRA_LOAD, values); /* local read (return adress) */
2609                         break;
2610                 case ICMD_JSR:
2611                 case ICMD_GOTO:
2612                 case ICMD_NOP:
2613                 case ICMD_ELSE_ICONST:
2614                 case ICMD_CHECKEXCEPTION:
2615                 case ICMD_CHECKASIZE:
2616                 case ICMD_PUTSTATICCONST:
2617                 case ICMD_INLINE_START:
2618                 case ICMD_INLINE_END:
2619                 case ICMD_RETURN:
2620                         break;
2621
2622                 case ICMD_IINC:
2623                         ret = lsra_test_local(ls, rd,iptr->op1,TYPE_INT, LSRA_LOAD, values); /* local */
2624                         ret = lsra_test_local(ls, rd,iptr->op1,TYPE_INT, LSRA_STORE, values); /* local = local+<const> */
2625                         break;
2626
2627                         /* pop 0 push 1 const */
2628                         /* const->stack */
2629
2630                 case ICMD_ICONST:
2631                 case ICMD_LCONST:
2632                 case ICMD_FCONST:
2633                 case ICMD_DCONST:
2634                 case ICMD_ACONST:
2635                         /* new stack slot */
2636                         ret = lsra_test_new_stack(ls, rd,dst, values); /* const->stack */
2637                         break;
2638
2639                         /* pop 0 push 1 load */
2640                         /* local->stack */
2641
2642                 case ICMD_ILOAD:
2643                 case ICMD_LLOAD:
2644                 case ICMD_FLOAD:
2645                 case ICMD_DLOAD:
2646                 case ICMD_ALOAD:
2647                         if (dst->varkind != LOCALVAR) {
2648                                 ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ILOAD, LSRA_LOAD, values); /* local->value */
2649                                 ret = lsra_test_new_stack(ls, rd,dst, values); /* value->stack */
2650                         } else if (dst->varnum != iptr->op1) {
2651                                 ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ILOAD, LSRA_LOAD, values); /* local->value */
2652                                 ret = lsra_test_local(ls, rd,dst->varnum,opcode-ICMD_ILOAD, LSRA_STORE, values); /* local->value */
2653                         }
2654
2655                         break;
2656
2657                         /* pop 2 push 1 */
2658                         /* Stack(arrayref,index)->stack */
2659
2660                 case ICMD_IALOAD:
2661                 case ICMD_LALOAD:
2662                 case ICMD_FALOAD:
2663                 case ICMD_DALOAD:
2664                 case ICMD_AALOAD:
2665
2666                 case ICMD_BALOAD:
2667                 case ICMD_CALOAD:
2668                 case ICMD_SALOAD:
2669                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack->index */
2670                         ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack->arrayref */
2671                         ret = lsra_test_new_stack(ls, rd, dst, values); /* arrayref[index]->stack */
2672                         break;
2673
2674                         /* pop 3 push 0 */
2675                         /* stack(arrayref,index,value)->arrayref[index]=value */
2676
2677                 case ICMD_IASTORE:
2678                 case ICMD_LASTORE:
2679                 case ICMD_FASTORE:
2680                 case ICMD_DASTORE:
2681                 case ICMD_AASTORE:
2682
2683                 case ICMD_BASTORE:
2684                 case ICMD_CASTORE:
2685                 case ICMD_SASTORE:
2686
2687                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2688                         ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> index */
2689                         ret = lsra_test_from_stack(ls, rd, src->prev->prev, values); /* stack -> arrayref */
2690                         break;
2691
2692                 case ICMD_POP: /* throw away a stackslot -> check if used anyway! */
2693                         ret = lsra_test_pop_from_stack(ls, rd,src, values);
2694                         break;
2695
2696                         /* pop 1 push 0 store */
2697                         /* stack -> local */
2698
2699                 case ICMD_ISTORE:
2700                 case ICMD_LSTORE:
2701                 case ICMD_FSTORE:
2702                 case ICMD_DSTORE:
2703                 case ICMD_ASTORE:
2704                         if (src->varkind != LOCALVAR) {
2705                                 ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2706                                 ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ISTORE, LSRA_STORE, values); /* local->value */
2707                         } else if (src->varnum != iptr->op1) {
2708                                 ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ISTORE, LSRA_STORE, values); /* local->value */
2709                                 ret = lsra_test_local(ls, rd,src->varnum,opcode-ICMD_ISTORE, LSRA_LOAD, values); /* local->value */
2710                         }
2711                         break;
2712
2713                         /* pop 1 push 0 */
2714
2715                 case ICMD_IRETURN:
2716                 case ICMD_LRETURN:
2717                 case ICMD_FRETURN:
2718                 case ICMD_DRETURN:
2719                 case ICMD_ARETURN: /* stack(value) -> [empty] */
2720                 case ICMD_ATHROW: /* stack(objref) -> undefined */
2721                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2722                         break;
2723                 case ICMD_PUTSTATIC: /* stack(value) -> static_field */
2724                 case ICMD_PUTFIELDCONST:
2725                         /* pop 1 push 0 branch */
2726                 case ICMD_NULLCHECKPOP: /****** ????? -1 -> stack *********/
2727                 case ICMD_MONITORENTER:
2728                 case ICMD_MONITOREXIT:
2729                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2730                         break;
2731
2732                 case ICMD_IFNULL: /* stack(value) -> branch? */
2733                 case ICMD_IFNONNULL:
2734                 case ICMD_IFEQ:
2735                 case ICMD_IFNE:
2736                 case ICMD_IFLT:
2737                 case ICMD_IFGE:
2738                 case ICMD_IFGT:
2739                 case ICMD_IFLE:
2740                 case ICMD_IF_LEQ:
2741                 case ICMD_IF_LNE:
2742                 case ICMD_IF_LLT:
2743                 case ICMD_IF_LGE:
2744                 case ICMD_IF_LGT:
2745                 case ICMD_IF_LLE:
2746                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2747                         break;
2748
2749                         /* pop 1 push 0 table branch */
2750
2751                 case ICMD_TABLESWITCH:
2752                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2753                         break;
2754                 case ICMD_LOOKUPSWITCH:
2755                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2756                         break;
2757
2758                         /* pop 2 push 0 */
2759
2760                 case ICMD_POP2: /* throw away 2 stackslots -> check if used anyway! */
2761                         ret = lsra_test_pop_from_stack(ls, rd,src, values);
2762                         ret = lsra_test_pop_from_stack(ls, rd,src->prev, values);
2763                         break;
2764
2765                         /* pop 2 push 0 branch */
2766
2767                 case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
2768                 case ICMD_IF_ICMPNE:
2769                 case ICMD_IF_ICMPLT:
2770                 case ICMD_IF_ICMPGE:
2771                 case ICMD_IF_ICMPGT:
2772                 case ICMD_IF_ICMPLE:
2773
2774                 case ICMD_IF_LCMPEQ:
2775                 case ICMD_IF_LCMPNE:
2776                 case ICMD_IF_LCMPLT:
2777                 case ICMD_IF_LCMPGE:
2778                 case ICMD_IF_LCMPGT:
2779                 case ICMD_IF_LCMPLE:
2780
2781                 case ICMD_IF_ACMPEQ:
2782                 case ICMD_IF_ACMPNE:
2783                         ret = lsra_test_from_stack(ls, rd, src, values);           /* stack -> value*/
2784                         ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> objref*/
2785                         break;
2786
2787                         /* pop 2 push 0 */
2788
2789                 case ICMD_PUTFIELD: /* stack(objref,value) -> objref->method=value */
2790
2791                 case ICMD_IASTORECONST:
2792                 case ICMD_LASTORECONST:
2793                 case ICMD_AASTORECONST:
2794                 case ICMD_BASTORECONST:
2795                 case ICMD_CASTORECONST:
2796                 case ICMD_SASTORECONST:
2797                         ret = lsra_test_from_stack(ls, rd, src, values);           /* stack -> value*/
2798                         ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> objref*/
2799                         break;
2800
2801                         /* pop 0 push 1 dup */
2802                         /* merge dupped vars??? */
2803                 case ICMD_DUP: /* src == dst->prev, src -> dst */
2804                         /* ret = lsra_test_from_stack(ls, rd, src,b_index,iindex);*/ /* just inc usage count? */
2805                         ret = lsra_test_new_stack(ls, rd,dst, values);
2806                         break;
2807
2808                         /* pop 0 push 2 dup */
2809
2810                 case ICMD_DUP2:
2811                         /* ret = lsra_test_from_stack(ls, rd, src,b_index,iindex); */ /* just inc usage count? */
2812                         /* ret = lsra_test_from_stack(ls, rd, src->prev,b_index,iindex); */ /* just inc usage count? */
2813                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2814                         ret = lsra_test_new_stack(ls, rd,dst, values);
2815                         break;
2816
2817                         /* pop 2 push 3 dup */
2818
2819                 case ICMD_DUP_X1:
2820                         ret = lsra_test_from_stack(ls, rd, src, values);
2821                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2822                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
2823                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2824                         ret = lsra_test_new_stack(ls, rd,dst, values);
2825                         break;
2826
2827                         /* pop 3 push 4 dup */
2828
2829                 case ICMD_DUP_X2:
2830                         ret = lsra_test_from_stack(ls, rd, src, values);
2831                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2832                         ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
2833                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
2834                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
2835                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2836                         ret = lsra_test_new_stack(ls, rd,dst, values);
2837                         break;
2838
2839                         /* pop 3 push 5 dup */
2840
2841                 case ICMD_DUP2_X1:
2842                         ret = lsra_test_from_stack(ls, rd, src, values);
2843                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2844                         ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
2845                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev, values);
2846                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
2847                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
2848                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2849                         ret = lsra_test_new_stack(ls, rd,dst, values);
2850                         break;
2851
2852                         /* pop 4 push 6 dup */
2853
2854                 case ICMD_DUP2_X2:
2855                         ret = lsra_test_from_stack(ls, rd, src, values);
2856                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2857                         ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
2858                         ret = lsra_test_from_stack(ls, rd, src->prev->prev->prev, values);
2859                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev->prev, values);
2860                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev, values);
2861                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
2862                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
2863                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2864                         ret = lsra_test_new_stack(ls, rd,dst, values);
2865
2866                         break;
2867
2868                         /* pop 2 push 2 swap */
2869
2870                 case ICMD_SWAP:
2871                         ret = lsra_test_from_stack(ls, rd, src, values);
2872                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2873                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2874                         ret = lsra_test_new_stack(ls, rd,dst, values);
2875
2876                         break;
2877
2878                         /* pop 2 push 1 */
2879
2880                 case ICMD_IADD:
2881                 case ICMD_ISUB:
2882                 case ICMD_IMUL:
2883                 case ICMD_IDIV:
2884                 case ICMD_IREM:
2885
2886                 case ICMD_ISHL:
2887                 case ICMD_ISHR:
2888                 case ICMD_IUSHR:
2889                 case ICMD_IAND:
2890                 case ICMD_IOR:
2891                 case ICMD_IXOR:
2892
2893                 case ICMD_LADD:
2894                 case ICMD_LSUB:
2895                 case ICMD_LMUL:
2896                 case ICMD_LDIV:
2897                 case ICMD_LREM:
2898
2899                 case ICMD_LOR:
2900                 case ICMD_LAND:
2901                 case ICMD_LXOR:
2902
2903                 case ICMD_LSHL:
2904                 case ICMD_LSHR:
2905                 case ICMD_LUSHR:
2906
2907                 case ICMD_FADD:
2908                 case ICMD_FSUB:
2909                 case ICMD_FMUL:
2910                 case ICMD_FDIV:
2911                 case ICMD_FREM:
2912
2913                 case ICMD_DADD:
2914                 case ICMD_DSUB:
2915                 case ICMD_DMUL:
2916                 case ICMD_DDIV:
2917                 case ICMD_DREM:
2918
2919                 case ICMD_LCMP:
2920                 case ICMD_FCMPL:
2921                 case ICMD_FCMPG:
2922                 case ICMD_DCMPL:
2923                 case ICMD_DCMPG:
2924                         ret = lsra_test_from_stack(ls, rd, src, values);
2925                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2926                         ret = lsra_test_new_stack(ls, rd,dst, values);
2927                         break;
2928
2929                         /* pop 1 push 1 */
2930                 case ICMD_IADDCONST:
2931                 case ICMD_ISUBCONST:
2932                 case ICMD_IMULCONST:
2933                 case ICMD_IMULPOW2:
2934                 case ICMD_IDIVPOW2:
2935                 case ICMD_IREMPOW2:
2936                 case ICMD_IANDCONST:
2937                 case ICMD_IORCONST:
2938                 case ICMD_IXORCONST:
2939                 case ICMD_ISHLCONST:
2940                 case ICMD_ISHRCONST:
2941                 case ICMD_IUSHRCONST:
2942
2943                 case ICMD_LADDCONST:
2944                 case ICMD_LSUBCONST:
2945                 case ICMD_LMULCONST:
2946                 case ICMD_LMULPOW2:
2947                 case ICMD_LDIVPOW2:
2948                 case ICMD_LREMPOW2:
2949                 case ICMD_LANDCONST:
2950                 case ICMD_LORCONST:
2951                 case ICMD_LXORCONST:
2952                 case ICMD_LSHLCONST:
2953                 case ICMD_LSHRCONST:
2954                 case ICMD_LUSHRCONST:
2955
2956                 case ICMD_IFEQ_ICONST:
2957                 case ICMD_IFNE_ICONST:
2958                 case ICMD_IFLT_ICONST:
2959                 case ICMD_IFGE_ICONST:
2960                 case ICMD_IFGT_ICONST:
2961                 case ICMD_IFLE_ICONST:
2962
2963                 case ICMD_INEG:
2964                 case ICMD_INT2BYTE:
2965                 case ICMD_INT2CHAR:
2966                 case ICMD_INT2SHORT:
2967                 case ICMD_LNEG:
2968                 case ICMD_FNEG:
2969                 case ICMD_DNEG:
2970
2971                 case ICMD_I2L:
2972                 case ICMD_I2F:
2973                 case ICMD_I2D:
2974                 case ICMD_L2I:
2975                 case ICMD_L2F:
2976                 case ICMD_L2D:
2977                 case ICMD_F2I:
2978                 case ICMD_F2L:
2979                 case ICMD_F2D:
2980                 case ICMD_D2I:
2981                 case ICMD_D2L:
2982                 case ICMD_D2F:
2983
2984                 case ICMD_CHECKCAST:
2985
2986                 case ICMD_ARRAYLENGTH:
2987                 case ICMD_INSTANCEOF:
2988
2989                 case ICMD_NEWARRAY:
2990                 case ICMD_ANEWARRAY:
2991
2992                 case ICMD_GETFIELD:
2993                         ret = lsra_test_from_stack(ls, rd, src, values);
2994                         ret = lsra_test_new_stack(ls, rd,dst, values);
2995                         break;
2996
2997                         /* pop 0 push 1 */
2998
2999                 case ICMD_GETSTATIC:
3000                 case ICMD_NEW:
3001                         ret = lsra_test_new_stack(ls, rd,dst, values);
3002                         break;
3003
3004                         /* pop many push any */
3005                 case ICMD_INVOKEVIRTUAL:
3006                 case ICMD_INVOKESPECIAL:
3007                 case ICMD_INVOKESTATIC:
3008                 case ICMD_INVOKEINTERFACE:
3009                         i = iptr->op1;
3010                         while (--i >= 0) {
3011                                 ret = lsra_test_from_stack(ls, rd, src, values);
3012                                 src = src->prev;
3013                         }
3014                         if (((methodinfo*)iptr->val.a)->returntype != TYPE_VOID) {
3015                                 ret = lsra_test_new_stack(ls, rd,dst, values);
3016                         }
3017                         break;
3018
3019                 case ICMD_BUILTIN3:
3020                         ret = lsra_test_from_stack(ls, rd, src, values);
3021                         src = src->prev;
3022                 case ICMD_BUILTIN2:
3023                         ret = lsra_test_from_stack(ls, rd, src, values);
3024                         src = src->prev;
3025                 case ICMD_BUILTIN1:
3026                         ret = lsra_test_from_stack(ls, rd, src, values);
3027                         src = src->prev; /* ??????????? */
3028                         if (iptr->op1 != TYPE_VOID)
3029                                 ret = lsra_test_new_stack(ls, rd, dst, values);
3030                         break;
3031
3032                 case ICMD_MULTIANEWARRAY:
3033                         i = iptr->op1;
3034                         while (--i >= 0) {
3035                                 ret = lsra_test_from_stack(ls, rd, src, values);
3036                                 src = src->prev;
3037                         }
3038                         ret = lsra_test_new_stack(ls, rd, dst, values);
3039                         break;
3040
3041                 default:
3042                         printf("ICMD %d at %d\n", iptr->opc, (int)(iptr - m->instructions));
3043                         panic("Missing ICMD code during register allocation");
3044                 } /* switch */
3045         }
3046         if (ret != -1) {
3047                 printf("BB: %i IIndex %i \n", b_index, iindex);
3048         } else {
3049
3050                 i=0;
3051
3052                 for (succ = ls->succ[b_index]; succ != NULL; succ = succ->next)
3053                         i++;
3054
3055                 if (i != 0) {
3056                         j = rand() % i;
3057
3058                         for (i=0, succ = ls->succ[b_index]; i!=j; i++, succ=succ->next);
3059
3060                         if ( (ret=_test_lifetimes(m, ls, rd, succ->value, values)) != -1) {
3061                                 printf("[BB %3i IIndex %3i]",b_index, iindex);
3062                         }
3063                 }
3064         }
3065         return ret;
3066 }
3067
3068 void test_lifetimes( methodinfo *m, lsradata *ls, registerdata *rd)
3069 {
3070         int *values, i, j, p, t;
3071         int v_max,ret;
3072
3073         v_max = rd->maxmemuse + rd->intregsnum + rd->fltregsnum;
3074
3075         if ( (values = calloc( v_max, sizeof(int))) == NULL )
3076                  panic("test_lifetimes: out of memory\n");
3077
3078         ret = -1;
3079         for (j=0; (j < 100) && (ret == -1); j++ ) {
3080                 for (i=0; i < v_max; i++) values[i]=VS;
3081
3082                 for (p = 0, i = 0; p < m->paramcount; p++) {
3083                         t = m->paramtypes[p];
3084
3085                         if (rd->locals[i][t].type >= 0)
3086                                 lsra_test_local( ls, rd, i, t, LSRA_STORE, values);
3087
3088                         i++;
3089                         if (IS_2_WORD_TYPE(t))    /* increment local counter for 2 word types */
3090                                 i++;
3091                 }  /* end for */
3092
3093                 if ((ret=_test_lifetimes(m, ls, rd, 0, values)) != -1) {
3094                         printf("\n");
3095                 }
3096         }
3097
3098
3099         free(values);
3100 }
3101 #endif
3102
3103
3104 /*
3105  * These are local overrides for various environment variables in Emacs.
3106  * Please do not remove this and leave it at the end of the file, where
3107  * Emacs will automagically detect them.
3108  * ---------------------------------------------------------------------
3109  * Local variables:
3110  * mode: c
3111  * indent-tabs-mode: t
3112  * c-basic-offset: 4
3113  * tab-width: 4
3114  * End:
3115  */