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 3028 2005-07-13 11:41:53Z 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_CHECKEXCEPTION:
1952                 case ICMD_CHECKASIZE:
1953                 case ICMD_PUTSTATICCONST:
1954                 case ICMD_INLINE_START:
1955                 case ICMD_INLINE_END:
1956                 case ICMD_RETURN:
1957                         break;
1958
1959                 case ICMD_IINC:
1960                         lsra_usage_local(ls,iptr->op1,TYPE_INT, b_index,iindex,LSRA_LOAD); /* local */
1961                         lsra_usage_local(ls,iptr->op1,TYPE_INT, b_index,iindex,LSRA_STORE); /* local = local+<const> */
1962                         break;
1963
1964                         /* pop 0 push 1 const */
1965                         /* const->stack */
1966
1967                 case ICMD_ICONST:
1968                 case ICMD_LCONST:
1969                 case ICMD_FCONST:
1970                 case ICMD_DCONST:
1971                 case ICMD_ACONST:
1972                         /* new stack slot */
1973                         lsra_new_stack(ls,dst,b_index,iindex); /* const->stack */
1974                         break;
1975
1976                         /* pop 0 push 1 load */
1977                         /* local->stack */
1978
1979                 case ICMD_ILOAD:
1980                 case ICMD_LLOAD:
1981                 case ICMD_FLOAD:
1982                 case ICMD_DLOAD:
1983                 case ICMD_ALOAD:
1984                         if (dst->varkind != LOCALVAR) {
1985                                 lsra_usage_local(ls,iptr->op1,opcode-ICMD_ILOAD, b_index,iindex,LSRA_LOAD); /* local->value */
1986                                 lsra_new_stack(ls,dst,b_index,iindex); /* value->stack */
1987                         } else if (dst->varnum != iptr->op1) {
1988                                 lsra_usage_local(ls,iptr->op1,opcode-ICMD_ILOAD, b_index,iindex,LSRA_LOAD); /* local->value */
1989                                 lsra_usage_local(ls,dst->varnum,opcode-ICMD_ILOAD, b_index,iindex,LSRA_STORE); /* local->value */
1990                         }
1991
1992                         break;
1993
1994                         /* pop 2 push 1 */
1995                         /* Stack(arrayref,index)->stack */
1996
1997                 case ICMD_IALOAD:
1998                 case ICMD_LALOAD:
1999                 case ICMD_FALOAD:
2000                 case ICMD_DALOAD:
2001                 case ICMD_AALOAD:
2002
2003                 case ICMD_BALOAD:
2004                 case ICMD_CALOAD:
2005                 case ICMD_SALOAD:
2006
2007                         lsra_from_stack(ls, src,b_index,iindex); /* stack->index */
2008                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack->arrayref */
2009                         lsra_new_stack(ls,dst,b_index,iindex); /* arrayref[index]->stack */
2010                         break;
2011
2012                         /* pop 3 push 0 */
2013                         /* stack(arrayref,index,value)->arrayref[index]=value */
2014
2015                 case ICMD_IASTORE:
2016                 case ICMD_LASTORE:
2017                 case ICMD_FASTORE:
2018                 case ICMD_DASTORE:
2019                 case ICMD_AASTORE:
2020
2021                 case ICMD_BASTORE:
2022                 case ICMD_CASTORE:
2023                 case ICMD_SASTORE:
2024
2025                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2026                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> index */
2027                         lsra_from_stack(ls, src->prev->prev,b_index,iindex); /* stack -> arrayref */
2028                         break;
2029
2030                 case ICMD_POP: /* throw away a stackslot -> check if used anyway! */
2031                         lsra_pop_from_stack(ls,src,b_index,iindex);
2032                         break;
2033
2034                         /* pop 1 push 0 store */
2035                         /* stack -> local */
2036
2037                 case ICMD_ISTORE:
2038                 case ICMD_LSTORE:
2039                 case ICMD_FSTORE:
2040                 case ICMD_DSTORE:
2041                 case ICMD_ASTORE:
2042                         if (src->varkind != LOCALVAR) {
2043                                 lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2044                                 lsra_usage_local(ls,iptr->op1,opcode-ICMD_ISTORE, b_index,iindex,LSRA_STORE); /* local->value */
2045                         } else if (src->varnum != iptr->op1) {
2046                                 lsra_usage_local(ls,iptr->op1,opcode-ICMD_ISTORE, b_index,iindex,LSRA_STORE); /* local->value */
2047                                 lsra_usage_local(ls,src->varnum,opcode-ICMD_ISTORE, b_index,iindex,LSRA_LOAD); /* local->value */
2048                         }
2049                         break;
2050
2051                         /* pop 1 push 0 */
2052
2053                 case ICMD_IRETURN:
2054                 case ICMD_LRETURN:
2055                 case ICMD_FRETURN:
2056                 case ICMD_DRETURN:
2057                 case ICMD_ARETURN: /* stack(value) -> [empty] */
2058                 case ICMD_ATHROW: /* stack(objref) -> undefined */
2059                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2060                         break;
2061                 case ICMD_PUTSTATIC: /* stack(value) -> static_field */
2062                 case ICMD_PUTFIELDCONST:
2063                         /* pop 1 push 0 branch */
2064                 case ICMD_MONITORENTER:
2065                 case ICMD_MONITOREXIT:
2066                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2067                         break;
2068
2069                 case ICMD_IFNULL: /* stack(value) -> branch? */
2070                 case ICMD_IFNONNULL:
2071                 case ICMD_IFEQ:
2072                 case ICMD_IFNE:
2073                 case ICMD_IFLT:
2074                 case ICMD_IFGE:
2075                 case ICMD_IFGT:
2076                 case ICMD_IFLE:
2077                 case ICMD_IF_LEQ:
2078                 case ICMD_IF_LNE:
2079                 case ICMD_IF_LLT:
2080                 case ICMD_IF_LGE:
2081                 case ICMD_IF_LGT:
2082                 case ICMD_IF_LLE:
2083                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2084                         break;
2085
2086                         /* pop 1 push 0 table branch */
2087
2088                 case ICMD_TABLESWITCH:
2089                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2090                         break;
2091                 case ICMD_LOOKUPSWITCH:
2092                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2093                         break;
2094
2095                         /* pop 2 push 0 */
2096
2097                 case ICMD_POP2: /* throw away 2 stackslots -> check if used anyway! */
2098                         lsra_pop_from_stack(ls,src,b_index,iindex);
2099                         lsra_pop_from_stack(ls,src->prev,b_index,iindex);
2100                         break;
2101
2102                         /* pop 2 push 0 branch */
2103
2104                 case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
2105                 case ICMD_IF_ICMPNE:
2106                 case ICMD_IF_ICMPLT:
2107                 case ICMD_IF_ICMPGE:
2108                 case ICMD_IF_ICMPGT:
2109                 case ICMD_IF_ICMPLE:
2110
2111                 case ICMD_IF_LCMPEQ:
2112                 case ICMD_IF_LCMPNE:
2113                 case ICMD_IF_LCMPLT:
2114                 case ICMD_IF_LCMPGE:
2115                 case ICMD_IF_LCMPGT:
2116                 case ICMD_IF_LCMPLE:
2117
2118                 case ICMD_IF_ACMPEQ:
2119                 case ICMD_IF_ACMPNE:
2120                         lsra_from_stack(ls, src,b_index,iindex);           /* stack -> value*/
2121                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> objref*/
2122                         break;
2123
2124                         /* pop 2 push 0 */
2125
2126                 case ICMD_PUTFIELD: /* stack(objref,value) -> objref->method=value */
2127
2128                 case ICMD_IASTORECONST:
2129                 case ICMD_LASTORECONST:
2130                 case ICMD_AASTORECONST:
2131                 case ICMD_BASTORECONST:
2132                 case ICMD_CASTORECONST:
2133                 case ICMD_SASTORECONST:
2134                         lsra_from_stack(ls, src,b_index,iindex);           /* stack -> value*/
2135                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> objref*/
2136                         break;
2137
2138                         /* pop 0 push 1 dup */
2139                         /* merge dupped vars??? */
2140                 case ICMD_DUP: /* src == dst->prev, src -> dst */
2141                         /* lsra_from_stack(ls, src,b_index,iindex);*/ /* just inc usage count? */
2142                         lsra_new_stack(ls,dst,b_index,iindex);
2143
2144 /* #if (defined(JOIN_DUP_STACK) && !defined(JOIN_DEST_STACK)) */
2145 #ifdef JOIN_DUP_STACK
2146                         /* src is identical to dst->prev */
2147                         lsra_join_2_stack(ls, src, dst, JOIN_DUP);
2148 #endif
2149                         break;
2150
2151                         /* pop 0 push 2 dup */
2152
2153                 case ICMD_DUP2:
2154                         /* lsra_from_stack(ls, src,b_index,iindex); */ /* just inc usage count? */
2155                         /* lsra_from_stack(ls, src->prev,b_index,iindex); */ /* just inc usage count? */
2156                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2157                         lsra_new_stack(ls,dst,b_index,iindex);
2158
2159 /* #if (defined(JOIN_DUP_STACK) && !defined(JOIN_DEST_STACK)) */
2160 #ifdef JOIN_DUP_STACK
2161                         lsra_join_2_stack(ls, src, dst, JOIN_DUP);
2162                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN_DUP);
2163                         /* src is identical to dst->prev->prev */
2164                         /* src->prev is identical to dst->prev->prev->prev */
2165 #endif
2166                         break;
2167
2168                         /* pop 2 push 3 dup */
2169
2170                 case ICMD_DUP_X1:
2171                         lsra_from_stack(ls, src, b_index, iindex);
2172                         lsra_from_stack(ls, src->prev, b_index, iindex);
2173                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2174                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2175                         lsra_new_stack(ls, dst, b_index, iindex);
2176 #ifdef JOIN_DUP_STACK
2177                         lsra_join_dup(ls, src, dst, dst->prev->prev);
2178                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN);
2179 #endif
2180                         break;
2181
2182                         /* pop 3 push 4 dup */
2183
2184                 case ICMD_DUP_X2:
2185                         lsra_from_stack(ls, src,b_index,iindex);
2186                         lsra_from_stack(ls, src->prev,b_index,iindex);
2187                         lsra_from_stack(ls, src->prev->prev,b_index,iindex);
2188                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2189                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2190                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2191                         lsra_new_stack(ls,dst,b_index,iindex);
2192
2193 #ifdef JOIN_DUP_STACK
2194                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev);
2195                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN);
2196                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2197 #endif
2198                         break;
2199
2200                         /* pop 3 push 5 dup */
2201
2202                 case ICMD_DUP2_X1:
2203                         lsra_from_stack(ls, src,b_index,iindex);
2204                         lsra_from_stack(ls, src->prev,b_index,iindex);
2205                         lsra_from_stack(ls, src->prev->prev,b_index,iindex);
2206                         lsra_new_stack(ls,dst->prev->prev->prev->prev,b_index,iindex);
2207                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2208                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2209                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2210                         lsra_new_stack(ls,dst,b_index,iindex);
2211
2212 #ifdef JOIN_DUP_STACK
2213                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev);
2214                         lsra_join_dup(ls, src->prev, dst->prev, dst->prev->prev->prev->prev);
2215                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2216 #endif
2217                         break;
2218
2219                         /* pop 4 push 6 dup */
2220
2221                 case ICMD_DUP2_X2:
2222                         lsra_from_stack(ls, src,b_index,iindex);
2223                         lsra_from_stack(ls, src->prev,b_index,iindex);
2224                         lsra_from_stack(ls, src->prev->prev,b_index,iindex);
2225                         lsra_from_stack(ls, src->prev->prev->prev,b_index,iindex);
2226                         lsra_new_stack(ls,dst->prev->prev->prev->prev->prev,b_index,iindex);
2227                         lsra_new_stack(ls,dst->prev->prev->prev->prev,b_index,iindex);
2228                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2229                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2230                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2231                         lsra_new_stack(ls,dst,b_index,iindex);
2232
2233 #ifdef JOIN_DUP_STACK
2234                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev->prev);
2235                         lsra_join_dup(ls, src->prev, dst->prev, dst->prev->prev->prev->prev->prev);
2236                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2237                         lsra_join_2_stack(ls, src->prev->prev->prev, dst->prev->prev->prev, JOIN);
2238 #endif
2239                         break;
2240
2241                         /* pop 2 push 2 swap */
2242
2243                 case ICMD_SWAP:
2244                         lsra_from_stack(ls, src,b_index,iindex);
2245                         lsra_from_stack(ls, src->prev,b_index,iindex);
2246                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2247                         lsra_new_stack(ls,dst,b_index,iindex);
2248
2249                         lsra_join_2_stack(ls, src->prev, dst, JOIN);
2250                         lsra_join_2_stack(ls, src, dst->prev, JOIN);
2251
2252                         break;
2253
2254                         /* pop 2 push 1 */
2255
2256                 case ICMD_IADD:
2257                 case ICMD_IMUL:
2258
2259                 case ICMD_ISHL:
2260                 case ICMD_ISHR:
2261                 case ICMD_IUSHR:
2262                 case ICMD_IAND:
2263                 case ICMD_IOR:
2264                 case ICMD_IXOR:
2265
2266                 case ICMD_LADD:
2267                 case ICMD_LSUB:
2268                 case ICMD_LMUL:
2269
2270                 case ICMD_LOR:
2271                 case ICMD_LAND:
2272                 case ICMD_LXOR:
2273
2274                 case ICMD_LSHL:
2275                 case ICMD_LSHR:
2276                 case ICMD_LUSHR:
2277
2278                 case ICMD_FADD:
2279                 case ICMD_FSUB:
2280                 case ICMD_FMUL:
2281
2282                 case ICMD_DADD:
2283                 case ICMD_DSUB:
2284                 case ICMD_DMUL:
2285                 case ICMD_DDIV:
2286                 case ICMD_DREM:
2287                         lsra_from_stack(ls, src, b_index, iindex);
2288                         lsra_from_stack(ls, src->prev, b_index, iindex);
2289                         lsra_new_stack(ls, dst, b_index, iindex);
2290 #ifdef JOIN_DEST_STACK
2291                         lsra_join_3_stack(ls, dst, src->prev, src, JOIN_OP);
2292 #endif
2293                         break;
2294
2295                 case ICMD_ISUB:
2296                         lsra_from_stack(ls, src, b_index, iindex);
2297                         lsra_from_stack(ls, src->prev,b_index,iindex);
2298                         lsra_new_stack(ls, dst, b_index, iindex);
2299 #ifdef JOIN_DEST_STACK
2300                         lsra_join_2_stack(ls, src, dst, JOIN_OP);
2301 #endif
2302                         break;
2303                 case ICMD_IDIV:
2304                 case ICMD_IREM:
2305
2306                 case ICMD_LDIV:
2307                 case ICMD_LREM:
2308
2309                 case ICMD_FDIV:
2310                 case ICMD_FREM:
2311
2312                 case ICMD_LCMP:
2313                 case ICMD_FCMPL:
2314                 case ICMD_FCMPG:
2315                 case ICMD_DCMPL:
2316                 case ICMD_DCMPG:
2317                         lsra_from_stack(ls, src,b_index,iindex);
2318                         lsra_from_stack(ls, src->prev,b_index,iindex);
2319                         lsra_new_stack(ls,dst,b_index,iindex);
2320                         break;
2321
2322                         /* pop 1 push 1 */
2323                 case ICMD_IADDCONST:
2324                 case ICMD_ISUBCONST:
2325                 case ICMD_IMULCONST:
2326                 case ICMD_IMULPOW2:
2327                 case ICMD_IDIVPOW2:
2328                 case ICMD_IREMPOW2:
2329                 case ICMD_IANDCONST:
2330                 case ICMD_IORCONST:
2331                 case ICMD_IXORCONST:
2332                 case ICMD_ISHLCONST:
2333                 case ICMD_ISHRCONST:
2334                 case ICMD_IUSHRCONST:
2335
2336                 case ICMD_LADDCONST:
2337                 case ICMD_LSUBCONST:
2338                 case ICMD_LMULCONST:
2339                 case ICMD_LMULPOW2:
2340                 case ICMD_LDIVPOW2:
2341                 case ICMD_LREMPOW2:
2342                 case ICMD_LANDCONST:
2343                 case ICMD_LORCONST:
2344                 case ICMD_LXORCONST:
2345                 case ICMD_LSHLCONST:
2346                 case ICMD_LSHRCONST:
2347                 case ICMD_LUSHRCONST:
2348
2349                 case ICMD_IFEQ_ICONST:
2350                 case ICMD_IFNE_ICONST:
2351                 case ICMD_IFLT_ICONST:
2352                 case ICMD_IFGE_ICONST:
2353                 case ICMD_IFGT_ICONST:
2354                 case ICMD_IFLE_ICONST:
2355
2356                 case ICMD_INEG:
2357                 case ICMD_INT2BYTE:
2358                 case ICMD_INT2CHAR:
2359                 case ICMD_INT2SHORT:
2360                 case ICMD_LNEG:
2361                 case ICMD_FNEG:
2362                 case ICMD_DNEG:
2363
2364                 case ICMD_I2L:
2365                 case ICMD_I2F:
2366                 case ICMD_I2D:
2367                 case ICMD_L2I:
2368                 case ICMD_L2F:
2369                 case ICMD_L2D:
2370                 case ICMD_F2I:
2371                 case ICMD_F2L:
2372                 case ICMD_F2D:
2373                 case ICMD_D2I:
2374                 case ICMD_D2L:
2375                 case ICMD_D2F:
2376
2377                 case ICMD_CHECKCAST:
2378                         lsra_from_stack(ls, src, b_index, iindex);
2379                         lsra_new_stack(ls, dst, b_index, iindex);
2380 #ifdef JOIN_DEST_STACK
2381                         lsra_join_2_stack(ls, src, dst, JOIN_OP);
2382 #endif
2383                         break;
2384
2385                 case ICMD_ARRAYLENGTH:
2386                 case ICMD_INSTANCEOF:
2387
2388                 case ICMD_NEWARRAY:
2389                 case ICMD_ANEWARRAY:
2390
2391                 case ICMD_GETFIELD:
2392                         lsra_from_stack(ls, src,b_index,iindex);
2393                         lsra_new_stack(ls,dst,b_index,iindex);
2394                         break;
2395
2396                         /* pop 0 push 1 */
2397
2398                 case ICMD_GETSTATIC:
2399                 case ICMD_NEW:
2400                         lsra_new_stack(ls,dst,b_index,iindex);
2401                         break;
2402
2403                         /* pop many push any */
2404                 case ICMD_INVOKEVIRTUAL:
2405                 case ICMD_INVOKESPECIAL:
2406                 case ICMD_INVOKESTATIC:
2407                 case ICMD_INVOKEINTERFACE:
2408                         i = iptr->op1;
2409                         while (--i >= 0) {
2410                                 lsra_from_stack(ls, src,b_index,iindex);
2411                                 src = src->prev;
2412                         }
2413 #if defined(__X86_64__) || defined(__I386__) || defined(__ALPHA__)
2414                         if (((unresolved_method *) iptr->target)->methodref->parseddesc.md->returntype.type != TYPE_VOID)
2415 #else
2416                         if (((methodinfo*)iptr->val.a)->returntype != TYPE_VOID)
2417 #endif
2418                                 lsra_new_stack(ls,dst,b_index,iindex);
2419                         break;
2420
2421 #if 0
2422                 case ICMD_BUILTIN3:
2423                         lsra_from_stack(ls, src,b_index,iindex);
2424                         src = src->prev;
2425                 case ICMD_BUILTIN2:
2426                         lsra_from_stack(ls, src,b_index,iindex);
2427                         src = src->prev;
2428                 case ICMD_BUILTIN1:
2429                         lsra_from_stack(ls, src,b_index,iindex);
2430                         src = src->prev; /* ??????????? */
2431                         if (iptr->op1 != TYPE_VOID)
2432                                 lsra_new_stack(ls,dst,b_index,iindex);
2433                         break;
2434 #endif
2435
2436                 case ICMD_MULTIANEWARRAY:
2437                         i = iptr->op1;
2438                         while (--i >= 0) {
2439                                 lsra_from_stack(ls, src,b_index,iindex);
2440                                 src = src->prev;
2441                         }
2442                         lsra_new_stack(ls,dst,b_index,iindex);
2443                         break;
2444
2445                 default:
2446                         printf("ICMD %d at %d\n", iptr->opc, (int)(iptr - m->instructions));
2447                         { log_text("Missing ICMD code during register allocation"); assert(0); }
2448                 } /* switch */
2449
2450 #if defined(LSRA_USES_REG_RES)
2451                 if (opt_lsra)
2452                 {
2453                         int length, maxlength, j;
2454                         int index, reg_res,start_iindex;
2455                         struct stackslot * ss;
2456                         struct lifetime *n;
2457
2458
2459                         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) {
2460                                 if (reg_res == -1) reg_res = EDX; /* patch because icmd_uses_reg_res [][REG_RES_CNT] ist defaulting to -1 */
2461                                 maxlength = -1;
2462                                 index = -1;
2463                                 if ((iindex == 0) || (icmd_uses_reg_res[opcode][reg_res])) {
2464                                         if (ls->reg_res_free[reg_res] != -1) {
2465                                                 /* reg_res is free from ls->reg_res_free[] til here (iindex) */
2466                                                 /* now search for the longest lifetime, which fits in this intervall */
2467                                                 /* and if found assign edx to it */
2468                                                 if (icmd_uses_reg_res[opcode][reg_res] & D) /* ICMD destroys REG_RES as destination operand */
2469                                                         start_iindex = iindex +1;
2470                                                 else
2471                                                         start_iindex = iindex;
2472                                                 for (i = (-v_index_min[reg_res] - 1); i < (-ls->v_index -1); i++) {
2473
2474                                                         n = &(ls->lifetime[i]);
2475                                                         if (!(n->flags & (JOINING || JOIN_BB))) { /* do not assign reserved Regs to lifetimes not fully seen till now */
2476                                                                 if ((n->type == TYPE_INT) || (n->type == TYPE_ADR)) {
2477                                                                         if (n->savedvar == 0) {
2478                                                                                 if ((n->bb_last_use == n->bb_first_def) && (n->bb_last_use == ls->sorted_rev[b_index])) {
2479                                                                                         if ((n->i_last_use <= ls->reg_res_free[reg_res]) && (n->i_first_def >= start_iindex)) {
2480
2481                                                                                                 length = n->i_last_use - n->i_first_def;
2482                                                                                                 if (length > maxlength) {
2483                                                                                                         maxlength = length;
2484                                                                                                         index = i;
2485                                                                                                 }
2486                                                                                         }
2487                                                                                 }
2488                                                                         }
2489                                                                 }
2490                                                         }
2491                                                 }
2492                                         }
2493                                         if (icmd_uses_reg_res[opcode][reg_res] & S) /* ICMD destroys REG_RES as source operand */
2494                                                 ls->reg_res_free[reg_res] = -1;
2495                                         else
2496                                                 ls->reg_res_free[reg_res] = iindex;
2497
2498                                         if (index != -1) { /* there is a lifetime, which a reserved register can be assigned to */
2499 #ifdef LSRA_DEBUG
2500                                                 {
2501                                                         struct lifetime *n;
2502                                                         n=&(ls->lifetime[index]);
2503                                                         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);
2504                                                 }
2505 #endif
2506                                                 ls->lifetime[index].reg = lsra_reg_res[reg_res];
2507                                                 for (ss = ls->lifetime[index].local_ss; ss != NULL; ss=ss->next) {
2508                                                         ss->s->regoff = lsra_reg_res[reg_res];
2509                                                 }
2510                                                 ls->lifetime[index].type = -1; /* drop lifetime, no further processing required */
2511                                         }
2512
2513                                         v_index_min[reg_res] = v_index_min_before_instruction;
2514                                 } else
2515                                         if (ls->reg_res_free[reg_res] == -1)
2516                                                 ls->reg_res_free[reg_res] = iindex;
2517                         }
2518                 }
2519 #endif
2520
2521
2522         }
2523 }
2524
2525
2526 #ifdef LSRA_TESTLT
2527
2528 int lsra_test_lt(registerdata *rd, struct lifetime *n, int store, int *values, bool inmemory) {
2529         int value_index;
2530
2531         if (inmemory) {
2532                 value_index = n->reg;
2533         } else {
2534                 if (IS_FLT_DBL_TYPE(n->type)) {
2535                         value_index = rd->memuse + INT_REG_CNT + n->reg;
2536                 } else {
2537                         value_index = rd->memuse + n->reg;
2538                 }
2539         }
2540
2541         if ((store == LSRA_LOAD) || (store == LSRA_POP)) {
2542                 if (values[value_index] == VS) {
2543                         if (n->i_start != -1) { /* not a parameter */
2544                                 printf("lsra_test: Warning: v_index %3i type %3i reg %3i", n->v_index, n->type, n->reg);
2545                                 if (inmemory)
2546                                         printf (" MEM");
2547                                 printf(" not initialized\n");
2548                         }
2549                 } else if (values[value_index] != n->v_index) {
2550                         printf("lsra_test: Error: v_index %3i  type %3i reg %3i", n->v_index, n->type, n->reg);
2551                         if (inmemory)
2552                                 printf (" MEM  ");
2553                         printf("Conflict: %3i \n", values[value_index]);
2554                         return (n->reg);
2555                 }
2556
2557         } else { /* LSRA_STORE */
2558                 values[value_index] = n->v_index;
2559         }
2560         return -1;
2561 }
2562
2563 int lsra_test_local( lsradata *ls, registerdata *rd, int v_index, int type, int store, int *values) {
2564         struct lifetime *n;
2565
2566         n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);
2567         if (n->type == -1)
2568                 { log_text("lsra_test: Local Var Lifetime not initialized!\n"); assert(0); }
2569
2570         return lsra_test_lt(rd, n, store, values, rd->locals[v_index][type].flags & INMEMORY);
2571 }
2572
2573 #define lsra_test_new_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values, LSRA_STORE)
2574 #define lsra_test_from_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values,LSRA_LOAD)
2575 #define lsra_test_pop_from_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values,  LSRA_LOAD)
2576 int lsra_test_stack( lsradata *ls, registerdata *rd, stackptr s, int *values, int store)
2577 {
2578         struct lifetime *n;
2579         int value_index;
2580
2581         if (s->varkind == LOCALVAR) {
2582                 return lsra_test_local(ls, rd, s->varnum, s->type, store, values);
2583         }
2584         if (s->varkind != ARGVAR) {
2585                 if (s->varnum >=0)
2586                         { log_text("lsra_test: Stackslot not initialized!\n"); assert(0); }
2587                 n = &(ls->lifetime[-s->varnum - 1]);
2588                 if (n->type == -1)
2589                         { log_text("lsra_test: Stackslot Lifetime not initialized!\n"); assert(0); }
2590
2591                 return lsra_test_lt(rd, n, store, values, s->flags & INMEMORY);
2592         }
2593         return -1;
2594 }
2595
2596 int _test_lifetimes(methodinfo *m, lsradata *ls, registerdata *rd, int b_index, int *values)
2597 {
2598         struct stackslot *ss;
2599         int *v, i, j;
2600
2601
2602         int opcode;
2603         int iindex;
2604         stackptr    src;
2605         stackptr    dst;
2606         instruction *iptr;
2607
2608         struct _list *succ;
2609
2610         int ret;
2611
2612         ret = -1;
2613
2614
2615         iptr = m->basicblocks[b_index].iinstr;
2616
2617         dst = m->basicblocks[b_index].instack;
2618
2619         for (iindex =0 ;(iindex < m->basicblocks[b_index].icount) && (ret == -1) ; iindex++, iptr++)  {
2620                 src = dst;
2621                 dst = iptr->dst;
2622                 opcode = iptr->opc;
2623
2624                 switch (opcode) {
2625
2626                         /* pop 0 push 0 */
2627                 case ICMD_RET:
2628                         ret = lsra_test_local(ls, rd, iptr->op1, TYPE_ADR, LSRA_LOAD, values); /* local read (return adress) */
2629                         break;
2630                 case ICMD_JSR:
2631                 case ICMD_GOTO:
2632                 case ICMD_NOP:
2633                 case ICMD_ELSE_ICONST:
2634                 case ICMD_CHECK_NULL:
2635                 case ICMD_CHECKEXCEPTION:
2636                 case ICMD_CHECKASIZE:
2637                 case ICMD_PUTSTATICCONST:
2638                 case ICMD_INLINE_START:
2639                 case ICMD_INLINE_END:
2640                 case ICMD_RETURN:
2641                         break;
2642
2643                 case ICMD_IINC:
2644                         ret = lsra_test_local(ls, rd,iptr->op1,TYPE_INT, LSRA_LOAD, values); /* local */
2645                         ret = lsra_test_local(ls, rd,iptr->op1,TYPE_INT, LSRA_STORE, values); /* local = local+<const> */
2646                         break;
2647
2648                         /* pop 0 push 1 const */
2649                         /* const->stack */
2650
2651                 case ICMD_ICONST:
2652                 case ICMD_LCONST:
2653                 case ICMD_FCONST:
2654                 case ICMD_DCONST:
2655                 case ICMD_ACONST:
2656                         /* new stack slot */
2657                         ret = lsra_test_new_stack(ls, rd,dst, values); /* const->stack */
2658                         break;
2659
2660                         /* pop 0 push 1 load */
2661                         /* local->stack */
2662
2663                 case ICMD_ILOAD:
2664                 case ICMD_LLOAD:
2665                 case ICMD_FLOAD:
2666                 case ICMD_DLOAD:
2667                 case ICMD_ALOAD:
2668                         if (dst->varkind != LOCALVAR) {
2669                                 ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ILOAD, LSRA_LOAD, values); /* local->value */
2670                                 ret = lsra_test_new_stack(ls, rd,dst, values); /* value->stack */
2671                         } else if (dst->varnum != iptr->op1) {
2672                                 ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ILOAD, LSRA_LOAD, values); /* local->value */
2673                                 ret = lsra_test_local(ls, rd,dst->varnum,opcode-ICMD_ILOAD, LSRA_STORE, values); /* local->value */
2674                         }
2675
2676                         break;
2677
2678                         /* pop 2 push 1 */
2679                         /* Stack(arrayref,index)->stack */
2680
2681                 case ICMD_IALOAD:
2682                 case ICMD_LALOAD:
2683                 case ICMD_FALOAD:
2684                 case ICMD_DALOAD:
2685                 case ICMD_AALOAD:
2686
2687                 case ICMD_BALOAD:
2688                 case ICMD_CALOAD:
2689                 case ICMD_SALOAD:
2690                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack->index */
2691                         ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack->arrayref */
2692                         ret = lsra_test_new_stack(ls, rd, dst, values); /* arrayref[index]->stack */
2693                         break;
2694
2695                         /* pop 3 push 0 */
2696                         /* stack(arrayref,index,value)->arrayref[index]=value */
2697
2698                 case ICMD_IASTORE:
2699                 case ICMD_LASTORE:
2700                 case ICMD_FASTORE:
2701                 case ICMD_DASTORE:
2702                 case ICMD_AASTORE:
2703
2704                 case ICMD_BASTORE:
2705                 case ICMD_CASTORE:
2706                 case ICMD_SASTORE:
2707
2708                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2709                         ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> index */
2710                         ret = lsra_test_from_stack(ls, rd, src->prev->prev, values); /* stack -> arrayref */
2711                         break;
2712
2713                 case ICMD_POP: /* throw away a stackslot -> check if used anyway! */
2714                         ret = lsra_test_pop_from_stack(ls, rd,src, values);
2715                         break;
2716
2717                         /* pop 1 push 0 store */
2718                         /* stack -> local */
2719
2720                 case ICMD_ISTORE:
2721                 case ICMD_LSTORE:
2722                 case ICMD_FSTORE:
2723                 case ICMD_DSTORE:
2724                 case ICMD_ASTORE:
2725                         if (src->varkind != LOCALVAR) {
2726                                 ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2727                                 ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ISTORE, LSRA_STORE, values); /* local->value */
2728                         } else if (src->varnum != iptr->op1) {
2729                                 ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ISTORE, LSRA_STORE, values); /* local->value */
2730                                 ret = lsra_test_local(ls, rd,src->varnum,opcode-ICMD_ISTORE, LSRA_LOAD, values); /* local->value */
2731                         }
2732                         break;
2733
2734                         /* pop 1 push 0 */
2735
2736                 case ICMD_IRETURN:
2737                 case ICMD_LRETURN:
2738                 case ICMD_FRETURN:
2739                 case ICMD_DRETURN:
2740                 case ICMD_ARETURN: /* stack(value) -> [empty] */
2741                 case ICMD_ATHROW: /* stack(objref) -> undefined */
2742                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2743                         break;
2744                 case ICMD_PUTSTATIC: /* stack(value) -> static_field */
2745                 case ICMD_PUTFIELDCONST:
2746                         /* pop 1 push 0 branch */
2747                 case ICMD_MONITORENTER:
2748                 case ICMD_MONITOREXIT:
2749                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2750                         break;
2751
2752                 case ICMD_IFNULL: /* stack(value) -> branch? */
2753                 case ICMD_IFNONNULL:
2754                 case ICMD_IFEQ:
2755                 case ICMD_IFNE:
2756                 case ICMD_IFLT:
2757                 case ICMD_IFGE:
2758                 case ICMD_IFGT:
2759                 case ICMD_IFLE:
2760                 case ICMD_IF_LEQ:
2761                 case ICMD_IF_LNE:
2762                 case ICMD_IF_LLT:
2763                 case ICMD_IF_LGE:
2764                 case ICMD_IF_LGT:
2765                 case ICMD_IF_LLE:
2766                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2767                         break;
2768
2769                         /* pop 1 push 0 table branch */
2770
2771                 case ICMD_TABLESWITCH:
2772                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2773                         break;
2774                 case ICMD_LOOKUPSWITCH:
2775                         ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
2776                         break;
2777
2778                         /* pop 2 push 0 */
2779
2780                 case ICMD_POP2: /* throw away 2 stackslots -> check if used anyway! */
2781                         ret = lsra_test_pop_from_stack(ls, rd,src, values);
2782                         ret = lsra_test_pop_from_stack(ls, rd,src->prev, values);
2783                         break;
2784
2785                         /* pop 2 push 0 branch */
2786
2787                 case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
2788                 case ICMD_IF_ICMPNE:
2789                 case ICMD_IF_ICMPLT:
2790                 case ICMD_IF_ICMPGE:
2791                 case ICMD_IF_ICMPGT:
2792                 case ICMD_IF_ICMPLE:
2793
2794                 case ICMD_IF_LCMPEQ:
2795                 case ICMD_IF_LCMPNE:
2796                 case ICMD_IF_LCMPLT:
2797                 case ICMD_IF_LCMPGE:
2798                 case ICMD_IF_LCMPGT:
2799                 case ICMD_IF_LCMPLE:
2800
2801                 case ICMD_IF_ACMPEQ:
2802                 case ICMD_IF_ACMPNE:
2803                         ret = lsra_test_from_stack(ls, rd, src, values);           /* stack -> value*/
2804                         ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> objref*/
2805                         break;
2806
2807                         /* pop 2 push 0 */
2808
2809                 case ICMD_PUTFIELD: /* stack(objref,value) -> objref->method=value */
2810
2811                 case ICMD_IASTORECONST:
2812                 case ICMD_LASTORECONST:
2813                 case ICMD_AASTORECONST:
2814                 case ICMD_BASTORECONST:
2815                 case ICMD_CASTORECONST:
2816                 case ICMD_SASTORECONST:
2817                         ret = lsra_test_from_stack(ls, rd, src, values);           /* stack -> value*/
2818                         ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> objref*/
2819                         break;
2820
2821                         /* pop 0 push 1 dup */
2822                         /* merge dupped vars??? */
2823                 case ICMD_DUP: /* src == dst->prev, src -> dst */
2824                         /* ret = lsra_test_from_stack(ls, rd, src,b_index,iindex);*/ /* just inc usage count? */
2825                         ret = lsra_test_new_stack(ls, rd,dst, values);
2826                         break;
2827
2828                         /* pop 0 push 2 dup */
2829
2830                 case ICMD_DUP2:
2831                         /* ret = lsra_test_from_stack(ls, rd, src,b_index,iindex); */ /* just inc usage count? */
2832                         /* ret = lsra_test_from_stack(ls, rd, src->prev,b_index,iindex); */ /* just inc usage count? */
2833                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2834                         ret = lsra_test_new_stack(ls, rd,dst, values);
2835                         break;
2836
2837                         /* pop 2 push 3 dup */
2838
2839                 case ICMD_DUP_X1:
2840                         ret = lsra_test_from_stack(ls, rd, src, values);
2841                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2842                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
2843                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2844                         ret = lsra_test_new_stack(ls, rd,dst, values);
2845                         break;
2846
2847                         /* pop 3 push 4 dup */
2848
2849                 case ICMD_DUP_X2:
2850                         ret = lsra_test_from_stack(ls, rd, src, values);
2851                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2852                         ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
2853                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
2854                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
2855                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2856                         ret = lsra_test_new_stack(ls, rd,dst, values);
2857                         break;
2858
2859                         /* pop 3 push 5 dup */
2860
2861                 case ICMD_DUP2_X1:
2862                         ret = lsra_test_from_stack(ls, rd, src, values);
2863                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2864                         ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
2865                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev, values);
2866                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
2867                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
2868                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2869                         ret = lsra_test_new_stack(ls, rd,dst, values);
2870                         break;
2871
2872                         /* pop 4 push 6 dup */
2873
2874                 case ICMD_DUP2_X2:
2875                         ret = lsra_test_from_stack(ls, rd, src, values);
2876                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2877                         ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
2878                         ret = lsra_test_from_stack(ls, rd, src->prev->prev->prev, values);
2879                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev->prev, values);
2880                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev, values);
2881                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
2882                         ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
2883                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2884                         ret = lsra_test_new_stack(ls, rd,dst, values);
2885
2886                         break;
2887
2888                         /* pop 2 push 2 swap */
2889
2890                 case ICMD_SWAP:
2891                         ret = lsra_test_from_stack(ls, rd, src, values);
2892                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2893                         ret = lsra_test_new_stack(ls, rd,dst->prev, values);
2894                         ret = lsra_test_new_stack(ls, rd,dst, values);
2895
2896                         break;
2897
2898                         /* pop 2 push 1 */
2899
2900                 case ICMD_IADD:
2901                 case ICMD_ISUB:
2902                 case ICMD_IMUL:
2903                 case ICMD_IDIV:
2904                 case ICMD_IREM:
2905
2906                 case ICMD_ISHL:
2907                 case ICMD_ISHR:
2908                 case ICMD_IUSHR:
2909                 case ICMD_IAND:
2910                 case ICMD_IOR:
2911                 case ICMD_IXOR:
2912
2913                 case ICMD_LADD:
2914                 case ICMD_LSUB:
2915                 case ICMD_LMUL:
2916                 case ICMD_LDIV:
2917                 case ICMD_LREM:
2918
2919                 case ICMD_LOR:
2920                 case ICMD_LAND:
2921                 case ICMD_LXOR:
2922
2923                 case ICMD_LSHL:
2924                 case ICMD_LSHR:
2925                 case ICMD_LUSHR:
2926
2927                 case ICMD_FADD:
2928                 case ICMD_FSUB:
2929                 case ICMD_FMUL:
2930                 case ICMD_FDIV:
2931                 case ICMD_FREM:
2932
2933                 case ICMD_DADD:
2934                 case ICMD_DSUB:
2935                 case ICMD_DMUL:
2936                 case ICMD_DDIV:
2937                 case ICMD_DREM:
2938
2939                 case ICMD_LCMP:
2940                 case ICMD_FCMPL:
2941                 case ICMD_FCMPG:
2942                 case ICMD_DCMPL:
2943                 case ICMD_DCMPG:
2944                         ret = lsra_test_from_stack(ls, rd, src, values);
2945                         ret = lsra_test_from_stack(ls, rd, src->prev, values);
2946                         ret = lsra_test_new_stack(ls, rd,dst, values);
2947                         break;
2948
2949                         /* pop 1 push 1 */
2950                 case ICMD_IADDCONST:
2951                 case ICMD_ISUBCONST:
2952                 case ICMD_IMULCONST:
2953                 case ICMD_IMULPOW2:
2954                 case ICMD_IDIVPOW2:
2955                 case ICMD_IREMPOW2:
2956                 case ICMD_IANDCONST:
2957                 case ICMD_IORCONST:
2958                 case ICMD_IXORCONST:
2959                 case ICMD_ISHLCONST:
2960                 case ICMD_ISHRCONST:
2961                 case ICMD_IUSHRCONST:
2962
2963                 case ICMD_LADDCONST:
2964                 case ICMD_LSUBCONST:
2965                 case ICMD_LMULCONST:
2966                 case ICMD_LMULPOW2:
2967                 case ICMD_LDIVPOW2:
2968                 case ICMD_LREMPOW2:
2969                 case ICMD_LANDCONST:
2970                 case ICMD_LORCONST:
2971                 case ICMD_LXORCONST:
2972                 case ICMD_LSHLCONST:
2973                 case ICMD_LSHRCONST:
2974                 case ICMD_LUSHRCONST:
2975
2976                 case ICMD_IFEQ_ICONST:
2977                 case ICMD_IFNE_ICONST:
2978                 case ICMD_IFLT_ICONST:
2979                 case ICMD_IFGE_ICONST:
2980                 case ICMD_IFGT_ICONST:
2981                 case ICMD_IFLE_ICONST:
2982
2983                 case ICMD_INEG:
2984                 case ICMD_INT2BYTE:
2985                 case ICMD_INT2CHAR:
2986                 case ICMD_INT2SHORT:
2987                 case ICMD_LNEG:
2988                 case ICMD_FNEG:
2989                 case ICMD_DNEG:
2990
2991                 case ICMD_I2L:
2992                 case ICMD_I2F:
2993                 case ICMD_I2D:
2994                 case ICMD_L2I:
2995                 case ICMD_L2F:
2996                 case ICMD_L2D:
2997                 case ICMD_F2I:
2998                 case ICMD_F2L:
2999                 case ICMD_F2D:
3000                 case ICMD_D2I:
3001                 case ICMD_D2L:
3002                 case ICMD_D2F:
3003
3004                 case ICMD_CHECKCAST:
3005
3006                 case ICMD_ARRAYLENGTH:
3007                 case ICMD_INSTANCEOF:
3008
3009                 case ICMD_NEWARRAY:
3010                 case ICMD_ANEWARRAY:
3011
3012                 case ICMD_GETFIELD:
3013                         ret = lsra_test_from_stack(ls, rd, src, values);
3014                         ret = lsra_test_new_stack(ls, rd,dst, values);
3015                         break;
3016
3017                         /* pop 0 push 1 */
3018
3019                 case ICMD_GETSTATIC:
3020                 case ICMD_NEW:
3021                         ret = lsra_test_new_stack(ls, rd,dst, values);
3022                         break;
3023
3024                         /* pop many push any */
3025                 case ICMD_INVOKEVIRTUAL:
3026                 case ICMD_INVOKESPECIAL:
3027                 case ICMD_INVOKESTATIC:
3028                 case ICMD_INVOKEINTERFACE:
3029                         i = iptr->op1;
3030                         while (--i >= 0) {
3031                                 ret = lsra_test_from_stack(ls, rd, src, values);
3032                                 src = src->prev;
3033                         }
3034 #if defined(__X86_64__) || defined(__I386__) || defined(__ALPHA__)
3035                         if (((unresolved_method *) iptr->target)->methodref->parseddesc.md->returntype.type != TYPE_VOID)
3036 #else
3037                         if (((methodinfo*)iptr->val.a)->returntype != TYPE_VOID)
3038 #endif
3039                                 ret = lsra_test_new_stack(ls, rd,dst, values);
3040                         break;
3041
3042                 case ICMD_BUILTIN3:
3043                         ret = lsra_test_from_stack(ls, rd, src, values);
3044                         src = src->prev;
3045                 case ICMD_BUILTIN2:
3046                         ret = lsra_test_from_stack(ls, rd, src, values);
3047                         src = src->prev;
3048                 case ICMD_BUILTIN1:
3049                         ret = lsra_test_from_stack(ls, rd, src, values);
3050                         src = src->prev; /* ??????????? */
3051                         if (iptr->op1 != TYPE_VOID)
3052                                 ret = lsra_test_new_stack(ls, rd, dst, values);
3053                         break;
3054
3055                 case ICMD_MULTIANEWARRAY:
3056                         i = iptr->op1;
3057                         while (--i >= 0) {
3058                                 ret = lsra_test_from_stack(ls, rd, src, values);
3059                                 src = src->prev;
3060                         }
3061                         ret = lsra_test_new_stack(ls, rd, dst, values);
3062                         break;
3063
3064                 default:
3065                         printf("ICMD %d at %d\n", iptr->opc, (int)(iptr - m->instructions));
3066                         { log_text("Missing ICMD code during register allocation"); assert(0); }
3067                 } /* switch */
3068         }
3069         if (ret != -1) {
3070                 printf("BB: %i IIndex %i \n", b_index, iindex);
3071         } else {
3072
3073                 i=0;
3074
3075                 for (succ = ls->succ[b_index]; succ != NULL; succ = succ->next)
3076                         i++;
3077
3078                 if (i != 0) {
3079                         j = rand() % i;
3080
3081                         for (i=0, succ = ls->succ[b_index]; i!=j; i++, succ=succ->next);
3082
3083                         if ( (ret=_test_lifetimes(m, ls, rd, succ->value, values)) != -1) {
3084                                 printf("[BB %3i IIndex %3i]",b_index, iindex);
3085                         }
3086                 }
3087         }
3088         return ret;
3089 }
3090
3091 void test_lifetimes( methodinfo *m, lsradata *ls, registerdata *rd)
3092 {
3093         int *values, i, j, p, t;
3094         int v_max,ret;
3095
3096         v_max = rd->memuse + INT_REG_CNT + FLT_REG_CNT;
3097
3098         if ( (values = calloc( v_max, sizeof(int))) == NULL )
3099                  { log_text("test_lifetimes: out of memory\n"); assert(0); }
3100
3101         ret = -1;
3102         for (j=0; (j < 100) && (ret == -1); j++ ) {
3103                 for (i=0; i < v_max; i++) values[i]=VS;
3104
3105                 for (p = 0, i = 0; p < m->paramcount; p++) {
3106                         t = m->paramtypes[p];
3107
3108                         if (rd->locals[i][t].type >= 0)
3109                                 lsra_test_local( ls, rd, i, t, LSRA_STORE, values);
3110
3111                         i++;
3112                         if (IS_2_WORD_TYPE(t))    /* increment local counter for 2 word types */
3113                                 i++;
3114                 }  /* end for */
3115
3116                 if ((ret=_test_lifetimes(m, ls, rd, 0, values)) != -1) {
3117                         printf("\n");
3118                 }
3119         }
3120
3121
3122         free(values);
3123 }
3124 #endif
3125
3126
3127 /*
3128  * These are local overrides for various environment variables in Emacs.
3129  * Please do not remove this and leave it at the end of the file, where
3130  * Emacs will automagically detect them.
3131  * ---------------------------------------------------------------------
3132  * Local variables:
3133  * mode: c
3134  * indent-tabs-mode: t
3135  * c-basic-offset: 4
3136  * tab-width: 4
3137  * End:
3138  */