src/vm/jit/allocator/lsra.c

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