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