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