src/vm/jit/lsra.inc

   1 /* vm/jit/lsra.inc - linear scan register allocator
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
   4    Institut f. Computersprachen, TU Wien
   5    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
   6    S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
   7    J. Wenninger, C. Ullrich
   8
   9    This file is part of CACAO.
  10
  11    This program is free software; you can redistribute it and/or
  12    modify it under the terms of the GNU General Public License as
  13    published by the Free Software Foundation; either version 2, or (at
  14    your option) any later version.
  15
  16    This program is distributed in the hope that it will be useful, but
  17    WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19    General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; if not, write to the Free Software
  23    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  24    02111-1307, USA.
  25
  26    Contact: cacao@complang.tuwien.ac.at
  27
  28    Authors: Christian Ullrich
  29
  30    $Id: lsra.inc 1621 2004-11-30 13:06:55Z twisti $
  31
  32 */
  33
  34 /* #define LSRA_DEBUG */
  35 /* #define LSRA_SAVEDVAR */
  36 /* #define LSRA_MEMORY */
  37 /* #define LSRA_PRINTLIFETIMES */
  38
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42
  43 #ifdef LSRA_DEBUG
  44 #define LSRA_PRINTLIFETIMES
  45 #endif
  46
  47 #include "mm/memory.h"
  48 #include "vm/options.h"
  49 #include "vm/jit/lsra.h"
  50 #include "vm/jit/reg.h"
  51 #include "vm/jit/loop/graph.h"
  52 #include "vm/jit/loop/loop.h"
  53
  54
  55 void lsra(methodinfo *m, codegendata *cd, registerdata *rd, loopdata *ld, t_inlining_globals *id)
  56 {
  57
  58         lsradata *ls;
  59
  60 #ifdef LSRA_DEBUG
  61         char name[1256], name1[1256];
  62
  63         utf_sprint(name, m->class->name);
  64         utf_sprint(name1, m->name);
  65         strcat(name, name1);
  66         utf_sprint(name1, m->descriptor);
  67         strcat(name, name1);
  68
  69
  70         printf("LSRA Start for %s\n", name);
  71
  72         if (strcmp(name,"java/lang/SysteminitProperties()V")==0) {
  73                 printf("-------------------\n");
  74         }
  75 #endif
  76
  77         ls=DNEW(lsradata);
  78         lsra_init(m, cd, id, ls);
  79         lsra_setup(m, cd, rd, ls, ld);
  80
  81
  82         /* Run LSRA */
  83         lsra_main(m, ls, rd);
  84
  85         return;
  86 }
  87
  88 void lsra_init(methodinfo *m, codegendata *cd, t_inlining_globals *id, lsradata *ls)
  89 {
  90         int i;
  91
  92         /* Init LSRA Data Structures */
  93         ls->back_edge_panic=false;
  94         /* lifetimes für alle Basicblocks allokieren */
  95         ls->ss_lifetimes=DMNEW(struct lifetime *, m->basicblockcount);
  96         for (i=0; i<m->basicblockcount; i++) ls->ss_lifetimes[i]=NULL;
  97 #ifdef LSRA_DEBUG
  98         if (cd->maxlocals != id->cumlocals) panic("lsra: Welche locals nehmen?\n");
  99 #endif
 100         ls->locals_lifetimes=DMNEW(struct lifetime *, cd->maxlocals);
 101         for (i=0; i < cd->maxlocals; i++) ls->locals_lifetimes[i]=NULL;
 102         ls->lifetimes=NULL;
 103         ls->stackslots=NULL;
 104 }
 105
 106 void lsra_setup(methodinfo *m, codegendata *cd, registerdata *rd, lsradata *ls, loopdata *ld)
 107 {
 108 #ifdef LSRA_DEBUG
 109         basicblock  *bptr;
 110 #endif
 111         int i,p;
 112         s4  t;
 113         struct lifetime *lt, *n;
 114         int v_index;
 115         struct stackslot *ss;
 116         bool drop;
 117
 118         /* Setup LSRA Data structures */
 119         if (opt_loops) panic("lsra with -oloop not possible!\n");
 120         if (!opt_loops) {
 121                 depthFirst(m, ld);
 122                 analyseGraph(m, ld);
 123         }
 124
 125         /* BBDELETED Blöcke aus loopdata->c_dTable rausschmeissen! */
 126         /* Exceptionhandler in loopdata->c_dTable hinzufügen       */
 127 #ifdef LSRA_DEBUG
 128         printf("LSRA lsra_clean_Graph\n");
 129 #endif
 130         lsra_clean_Graph(m, cd, ls, ld);
 131
 132 #ifdef LSRA_DEBUG
 133         /* sicherheitshalber Konsistenz von m->basicblocks[..] mit basicblocks->next (Liste) überprüfen */
 134         printf("LSRA bb prüfen\n");
 135         i=0;
 136         bptr = m->basicblocks;
 137         while (bptr != NULL) {
 138                 if (i > m->basicblockcount){
 139                         panic("linked bb list does not correspond with bb array(1)\n");
 140                 }
 141                 if (bptr != &(m->basicblocks[i])){
 142                         panic("linked bb list does not correspond with bb array(2)\n");
 143                 }
 144
 145                 i++;
 146                 bptr=bptr->next;
 147         }
 148         if (i<m->basicblockcount){
 149                 panic("linked bb list does not correspond with bb array(3)\n");
 150         }
 151
 152         printf("LSRA lsra_dump_Graph\n");
 153         lsra_dump_Graph(m, ld->c_dTable);
 154 #endif
 155
 156
 157         /* Parameter initialisieren = local Vars schreibzugriff bei 0,0*/
 158
 159         for (p = 0, i = 0; p < m->paramcount; p++) {
 160                 t = m->paramtypes[p];
 161
 162                 if (rd->locals[i][t].type >= 0)
 163                         lsra_usage_local(ls, i, t, 0, 0, LSRA_STORE);
 164                 i++;
 165                 if (IS_2_WORD_TYPE(t))    /* increment local counter for 2 word types */
 166                         i++;
 167         }  /* end for */
 168
 169 #ifdef LSRA_DEBUG
 170         printf("LSRA lsra_scan_register_canditates\n");
 171 #endif
 172         lsra_scan_registers_canditates(m, ls);
 173         lsra_join_lifetimes(m, cd, ls, ld);
 174
 175         v_index=-1;
 176
 177         /* ls->lifetimes contains only the joined stackslotlifetimes */
 178         for (lt=ls->lifetimes; lt != NULL; lt=lt->next) {
 179                 lt->v_index=v_index;
 180 #ifdef LSRA_SAVEDVAR
 181                 lt->savedvar=SAVEDVAR;
 182 #endif
 183                 for (ss=lt->local_ss; ss != NULL; ss=ss->next) {
 184                         ss->s->varnum=v_index;
 185                         ss->s->varkind=TEMPVAR; /* just another time */
 186                 }
 187         }
 188
 189         /* add ss_lifetimes[i] to ls->lifetimes or local_lifetimes[lt->s->varnum] */
 190         for (i=0; i < m->basicblockcount; i++) {
 191                 if (m->basicblocks[i].flags >= BBREACHED) {
 192                         for (; ls->ss_lifetimes[i] != NULL;) {
 193                                 lt=ls->ss_lifetimes[i];
 194 #ifdef LSRA_SAVEDVAR
 195                                 lt->savedvar=SAVEDVAR;
 196 #endif
 197 #ifdef LSRA_DEBUG
 198                                 if (lt->local_ss == NULL) panic("lsra_setup: normal Stackslot Lifetimes local_ss == NULL\n");
 199 #endif
 200                                 drop=false;
 201                                 for (ss=lt->local_ss; (ss!=NULL) && (!drop); ss=ss->next) {
 202                                         if (lt->local_ss->next == NULL) { /* only one Stackslot in local_ss */
 203                                                 /* Special Treatment for "lonely" LOCAL and ARGVARs */
 204                                                 if (ss->s->varkind == LOCALVAR) {
 205                                                         /* join with LOCALVAR */
 206                                                         /* local Lifetime vom richtigen Type suchen */
 207                                                         for (n=ls->locals_lifetimes[lt->local_ss->s->varnum]; (n!=NULL) && (n->type!=lt->local_ss->s->type);n=n->next);
 208                                                         lsra_merge_i_lists(n, lt);
 209                                                         if (n->local_ss == NULL)  /* "pure" Local without Stackslots */
 210                                                                 n->local_ss = lt->local_ss;
 211                                                         else
 212                                                                 lsra_merge_local_ss(n, lt);
 213
 214                                                         drop = true;
 215                                                 }
 216                                                 if (lt->local_ss->s->varkind == ARGVAR) {
 217                                                         drop = true;
 218                                                 }
 219                                         } else {
 220                                                 /* no special treatment (only one Stackslot Lifetimes)? */
 221                                                 ss->s->varnum=v_index;
 222                                                 ss->s->varkind=TEMPVAR; /* only TEMPVAR possible for now */
 223                                         }
 224                                 }
 225                                 if (drop)
 226                                         ls->ss_lifetimes[i]=lt->next;
 227                                 else {
 228                                         /* link into ls->lifetimes */
 229                                         ls->ss_lifetimes[i]=lt->next;
 230                                         lt->next=ls->lifetimes;
 231                                         ls->lifetimes=lt;
 232                                         lt->v_index=v_index--;
 233                                 }
 234                         } /* for */
 235                 } /* if */
 236         }
 237
 238         /* add local_lifetimes to lifetimes */
 239         for (i=0; i < cd->maxlocals; i++) {
 240                 if (ls->locals_lifetimes[i] != NULL) {
 241                         for (lt=ls->locals_lifetimes[i]; lt->next != NULL; lt=lt->next);
 242                         lt->next=ls->lifetimes;
 243                         ls->lifetimes=ls->locals_lifetimes[i];
 244                 }
 245         }
 246
 247         /* calc lifetime length */
 248 #ifdef LSRA_DEBUG
 249         printf("Lifetimes before calc_lifetime_length: \n");
 250         print_lifetimes(rd, ls->lifetimes);
 251         printf("LSRA lsra_calc_lifetime_lengthe\n");
 252 #endif
 253         lsra_calc_lifetime_length(m, ls, cd, ld);
 254 }
 255
 256 int lsra_get_sbr_end(methodinfo *m, loopdata *ld, int bb, int *bb_visited)
 257 {
 258         int j, bb_end;
 259         struct depthElement *de;
 260         instruction *ip;
 261
 262         bb_visited[bb]=true;
 263         ip = m->basicblocks[bb].iinstr + m->basicblocks[bb].icount -1;/* set ip to last instruction                     */
 264         if (ip->opc == ICMD_RET)
 265                 return bb;
 266         /* This Block is not the end -> search all following Blocks */
 267         j=bb_end=-1;
 268         for (de=ld->c_dTable[bb]; de != NULL; de=de->next) {
 269                 if (!bb_visited[de->value]) {
 270                         j=lsra_get_sbr_end(m, ld, de->value, bb_visited);
 271                         if (j!=-1) { /* No new return path found */
 272                                 if ((bb_end != -1) && (j!=bb_end)) panic("SBR has more than one exit Blocks\n");
 273                                 bb_end=j;
 274                         }
 275                 }
 276         }
 277         return bb_end;
 278 }
 279
 280 void lsra_clean_Graph( methodinfo *m, codegendata *cd, lsradata *ls, loopdata *ld)
 281 {
 282         int i,j;
 283         struct depthElement *de, *n;
 284         int *bb_succ, *bb_visited, *ptr, index;
 285         exceptiontable *ex;
 286         struct depthElement **table;
 287         bool back_edge;
 288         struct LoopContainer *lc;
 289
 290         table=ld->c_dTable;
 291
 292         if (table == NULL) {
 293                 return;
 294         }
 295
 296         /* Exceptionhandler noch in c_dTable aufnehmen */
 297         ex=cd->exceptiontable;
 298 #ifdef LSRA_DEBUG
 299         printf("ExTable(%i): ", cd->exceptiontablelength);
 300 #endif
 301
 302         for (; ex != NULL; ex = ex->down) {
 303
 304 #ifdef LSRA_DEBUG
 305                 printf("%i ",ex->handler->debug_nr);
 306 #endif
 307                 dF(m, ld, -1, ex->handler->debug_nr);
 308         }
 309
 310
 311         /* Setting up successors of deleted Basic Blocks, in case c_dTable has an edge */
 312         /* to a deleted block, so it can be replaced with the next "normal" Block */
 313         bb_succ= DMNEW(int, m->basicblockcount);
 314         for (i=0; i < m->basicblockcount; i++) {
 315                 if (m->basicblocks[i].flags >= BBREACHED)
 316                         bb_succ[i]=i;
 317                 else {
 318                         for(j=i; ((j < m->basicblockcount) && (m->basicblocks[j].flags < BBREACHED)); j++);
 319                         if (j < m->basicblockcount)
 320                                 bb_succ[i]=j;
 321                         else
 322                                 bb_succ[i]=-1;
 323                 }
 324         }
 325
 326         back_edge=false;
 327         for(i=0; i < m->basicblockcount; i++) {
 328                 if (m->basicblocks[i].flags < BBREACHED) {
 329                         table[i]=NULL;
 330                 } else {
 331                         for (de=table[i]; de != NULL; de=de->next) {
 332                                 if (de->value < i) back_edge=true;
 333                                 if (bb_succ[de->value] != de->value)
 334                                         de->value = bb_succ[de->value];
 335                                 if (de->value == -1) panic("lsra_clean_Graph: Sprung ins nichts....");
 336                         }
 337                 }
 338         }
 339
 340         if (back_edge) {
 341                 if ( ld->c_allLoops == NULL ) {
 342                         /* Keine Loops in Datenstruktur aber backedge!                     */
 343                         /* sollte nach BasicBlock umsortieren (revererse Depth First sort) */
 344                         /* und überprüfen von jit/loop/loop.c nicht mehr nötig sein        */
 345                         /* TODO bis dahin eine loop über die backedge eintragen            */
 346                         /*      anstatt back_edge_panic zu setzen und alle Lifetimes über die */
 347                         /*      gesamt Methode auszudehnen                                    */
 348 /*                      ls->back_edge_panic = true; */
 349
 350                         /* create loops from all back edges */
 351
 352                         for(i=0; i < m->basicblockcount; i++) {
 353                                 if (m->basicblocks[i].flags >= BBREACHED) {
 354                                         for (de=table[i]; de != NULL; de=de->next) {
 355                                                 if (de->value < i) {
 356                                                         if (ld->c_allLoops == NULL) {
 357                                                                 ld->c_allLoops = lc = DNEW(struct LoopContainer);
 358                                                         } else {
 359                                                                 lc->next=DNEW(struct LoopContainer);
 360                                                                 lc=lc->next;
 361                                                         }
 362                                                         lc->nodes=DNEW(struct LoopElement);
 363                                                         lc->nodes->next=DNEW(struct LoopElement);
 364                                                         lc->nodes->next->next=NULL;
 365
 366                                                         lc->nodes->block=&(m->basicblocks[i]);
 367                                                         lc->nodes->next->block=&(m->basicblocks[de->value]);
 368                                                         lc->next = NULL;
 369                                                 }
 370                                         }
 371                                 }
 372                         }
 373 #ifdef LSRA_DEBUG
 374                         printf("-------------Warnung Back Edge + no LOOP..\n");
 375 #endif
 376                 }
 377         }
 378
 379         bb_visited=DMNEW(int, m->basicblockcount);
 380         for (i=0; i<m->basicblockcount; i++) {
 381                 bb_visited[i]=false;
 382         }
 383
 384         /* Add all return possibilities to subroutine returns!           */
 385         /* --- subroutines will be inlined ---- -> then cancel this part */
 386 #ifdef LSRA_DEBUG
 387         printf("LSRA Subroutine patching\n");
 388 #endif
 389         for (i=0; i < m->basicblockcount; i++ ) {
 390                 /* Search all Subroutine Headers */
 391                 if (m->basicblocks[i].type == BBTYPE_SBR) {
 392 #ifdef LSRA_DEBUG
 393                         printf("Subroutine at BB %3i num pred: %3i Pred: ",i, ld->c_numPre[i]);
 394                         for (ptr=ld->c_pre[i], index=0; index < ld->c_numPre[i]; ++index, ++ptr)
 395                                 printf("%3i ", *ptr);
 396                         printf("\n");
 397 #endif
 398                         if (ld->c_numPre[i] > 1) { /* only if more than one call */
 399 #ifdef LSRA_DEBUG
 400                                 printf("Searching End of Subroutine: ");
 401 #endif
 402                                 j=lsra_get_sbr_end(m, ld, i, bb_visited); /* get Ending Block of Subroutine */
 403 #ifdef LSRA_DEBUG
 404                                 printf("%3i \n",j);
 405 #endif
 406                                 /* ensure, that all Predecessors+1 of the Subroutine Header are in the list */
 407                                 /* in the List is only one Predecessor */
 408 #ifdef LSRA_DEBUG
 409                                 if (ld->c_dTable[j] == NULL) panic("No SBR Return in c_dTable\n");
 410                                 if (ld->c_dTable[j]->next != NULL) panic("More than one SBR Return in c_dTable\n");
 411 #endif
 412                                 de=ld->c_dTable[j];
 413                                 for (ptr=ld->c_pre[i], index=0; index < ld->c_numPre[i]; ++index, ++ptr) {
 414                                         if (*ptr+1!=de->value) { /* Make new Entry */
 415                                                 n=DNEW(struct depthElement);
 416                                                 n->value=*ptr+1;
 417                                                 n->next=de->next;
 418                                                 de->next=n;
 419                                         }
 420                                 }
 421                         }
 422 #ifdef LSRA_DEBUG
 423                         printf( "(%3i)table[%3i %3i]:  ",m->basicblocks[j].flags,j,m->basicblocks[j].debug_nr);
 424                         for (de=ld->c_dTable[j]; de != NULL; de=de->next) {
 425                                 printf( "%3i ", de->value);
 426                         }
 427                         printf("\n");
 428 #endif
 429                 }
 430         }
 431 }
 432
 433 #ifdef LSRA_DEBUG
 434 void lsra_dump_Graph(methodinfo *m, struct depthElement **table)
 435 {
 436         int i;
 437         struct depthElement *de;
 438
 439         if (table == NULL) {
 440                 printf ("table == NULL\n");
 441                 return;
 442         }
 443
 444         for(i=0; i < m->basicblockcount; i++) {
 445
 446                         switch (m->basicblocks[i].type) {
 447
 448                         case BBTYPE_STD:
 449                                 printf("STD ");
 450                                 break;
 451                         case BBTYPE_EXH:
 452                                 printf("EXH ");
 453                                 break;
 454                         case BBTYPE_SBR:
 455                                 printf("SBR ");
 456                                 break;
 457
 458                         default:
 459                                 printf("%3i ", m->basicblocks[i].flags);
 460                                 break;
 461                         }
 462
 463                         printf( "(F%3i)table[%3i %3i]:  ",m->basicblocks[i].flags,i,m->basicblocks[i].debug_nr);
 464                         for (de=table[i]; de != NULL; de=de->next) {
 465                                 printf( "%3i ", de->value);
 466                 }
 467                 printf("\n");
 468         }
 469         printf( "table dump end\n");
 470 }
 471 #endif
 472
 473 void lsra_main(methodinfo *m, lsradata *ls, registerdata *rd)
 474 {
 475         struct lifetime *lt, *lt_prev, *lt_temp, *int_lt, *int_lt_last, *flt_lt, *flt_lt_last;
 476 #ifdef LSRA_DEBUG
 477         int lt_count,lt_int_count,lt_flt_count,lt_left_count;
 478 #endif
 479         int i;
 480         int lsra_mem_use;
 481         int sav_reg_count, tmp_reg_count;
 482         struct lsra_reg *reg;
 483         int reg_count;
 484 /*      varinfo *v; */
 485         int type;
 486         int flags; /* 0 INMEMORY->lifetimes, 1 INTREG->int_lt, 2 FLTREG->flt_lt */
 487         int lsra_reg_use;
 488
 489         /* first split lifetimes for integer and float registers */
 490         int_lt_last=int_lt=NULL;
 491         flt_lt_last=flt_lt=NULL;
 492
 493 #ifdef LSRA_DEBUG
 494         for (lt_count=0,lt=ls->lifetimes; lt!=NULL;lt=lt->next,lt_count++);
 495 #endif
 496
 497         for (lt_prev=lt=ls->lifetimes;lt!=NULL;) {
 498                 lt->reg = -1;
 499
 500                 if (lt->v_index < 0) { /* stackslot */
 501
 502 #ifdef LSRA_DEBUG
 503                         if (lt->local_ss == NULL) panic("lsra_main Lifetime Stackslot invalid\n");
 504 #endif
 505                         type = lt->local_ss->s->type;
 506                 } else { /* local var */
 507                         if (rd->locals[lt->v_index][lt->type].type>=0) {
 508                                 type = rd->locals[lt->v_index][lt->type].type;
 509                         } else panic("Type Data Mismatch 2\n");
 510                 }
 511
 512                 switch (type) {
 513                 case TYPE_LNG:
 514 #if defined(__I386__)
 515                         /*
 516                          * for i386 put all longs in memory
 517                          */
 518                         flags=0;
 519                         break;
 520 #endif
 521                 case TYPE_INT:
 522                 case TYPE_ADR:
 523                         flags=1;
 524                         break;
 525                 case TYPE_DBL:
 526                 case TYPE_FLT:
 527                         flags=2;
 528                         break;
 529                 default:
 530                         panic("Unknown Type\n");
 531                 }
 532
 533                 if (flags!=0) {
 534                         switch (flags) {
 535                         case 1: /* l->lifetimes -> int_lt */
 536                                 if (int_lt == NULL) {
 537                                         int_lt_last=int_lt=lt;
 538                                 } else {
 539                                         int_lt_last->next=lt;
 540                                         int_lt_last=lt;
 541                                 }
 542                                 break;
 543                         case 2: /* l->lifetimes -> flt_lt */
 544                                 if (flt_lt==NULL) {
 545                                         flt_lt_last=flt_lt=lt;
 546                                 } else {
 547                                         flt_lt_last->next=lt;
 548                                         flt_lt_last=lt;
 549                                 }
 550                                 break;
 551                         }
 552                         lt_temp=lt;
 553                         if (lt == ls->lifetimes) {
 554                                 lt=lt_prev=ls->lifetimes=ls->lifetimes->next;
 555                         } else {
 556                                 lt_prev->next=lt->next;
 557                                 lt=lt->next;
 558                         }
 559                         lt_temp->next=0;
 560                 } else {
 561                         lt_prev=lt;
 562                         lt=lt->next;
 563                 }
 564         }
 565         lsra_sort_lt(&int_lt);
 566         lsra_sort_lt(&(ls->lifetimes));
 567         lsra_sort_lt(&flt_lt);
 568
 569 #ifdef LSRA_DEBUG
 570         for (lt_int_count=0,lt=int_lt; lt!=NULL;lt=lt->next,lt_int_count++);
 571         for (lt_flt_count=0,lt=flt_lt; lt!=NULL;lt=lt->next,lt_flt_count++);
 572         for (lt_left_count=0,lt=ls->lifetimes; lt!=NULL;lt=lt->next,lt_left_count++);
 573
 574         printf("\nLifetimes: %3i left: %3i Intlt: %3i Fltlt: %3i \n",lt_count,lt_left_count,lt_int_count,lt_flt_count);
 575         if (lt_count != lt_int_count + lt_flt_count + lt_left_count) {
 576                 panic ("lifetimes missing\n");
 577         }
 578 #endif
 579         lsra_reg_use=rd->savintregcnt;
 580         if (int_lt!=NULL) {
 581                 for (reg_count = 0; nregdescint[reg_count] != REG_END; reg_count++);
 582
 583                 reg=DMNEW(struct lsra_reg,reg_count);
 584                 sav_reg_count=0;
 585                 for (i=0; i<reg_count ; i++)
 586                         if (nregdescint[i]==REG_SAV) {
 587                                 reg[sav_reg_count].reg_index=i;
 588                                 reg[sav_reg_count].use=0;
 589                                 sav_reg_count++;
 590                         }
 591                 tmp_reg_count=sav_reg_count;
 592                 for (i=0; i<reg_count ; i++) {
 593 #if defined(__I386__)
 594                         if ((method_uses_ecx) && (i==ECX)) continue;
 595                         if ((method_uses_edx) && (i==EDX)) continue;
 596 #endif
 597                         if (nregdescint[i]==REG_TMP) {
 598                                 reg[tmp_reg_count].reg_index=i;
 599                                 reg[tmp_reg_count].use=0;
 600                                 tmp_reg_count++;
 601                         }
 602                 }
 603                 _lsra_main(m, ls, int_lt, reg, tmp_reg_count, sav_reg_count, &lsra_mem_use, &lsra_reg_use);
 604                 if (lsra_reg_use > rd->savintregcnt) lsra_reg_use=rd->savintregcnt;
 605         }
 606         rd->maxsavintreguse= lsra_reg_use;
 607         lsra_reg_use=rd->savfltregcnt;
 608
 609         if (flt_lt!=NULL){
 610                 for (reg_count = 0; nregdescfloat[reg_count] != REG_END; reg_count++);
 611
 612                 reg=DMNEW(struct lsra_reg,reg_count);
 613                 sav_reg_count=0;
 614                 for (i=0; i<reg_count ; i++)
 615                         if ((nregdescfloat[i]==REG_SAV) || (m->isleafmethod && (nregdescfloat[i]==REG_ARG))) {
 616                                 reg[sav_reg_count].reg_index=i;
 617                                 reg[sav_reg_count].use=0;
 618                                 sav_reg_count++;
 619                         }
 620
 621                 tmp_reg_count=sav_reg_count;
 622                 for (i=0; i<reg_count ; i++)
 623                         if (nregdescfloat[i]==REG_TMP) {
 624                                 reg[tmp_reg_count].reg_index=i;
 625                                 reg[tmp_reg_count].use=0;
 626                                 tmp_reg_count++;
 627                         }
 628                 _lsra_main(m,ls, flt_lt, reg, tmp_reg_count, sav_reg_count, &lsra_mem_use, &lsra_reg_use);
 629                 if (lsra_reg_use > rd->savfltregcnt) lsra_reg_use=rd->savfltregcnt;
 630         }
 631
 632         rd->maxsavfltreguse=lsra_reg_use;
 633
 634 #ifndef SPECIALMEMUSE
 635 #if defined(__X86_64__)
 636         /*
 637          * XXX: we have a problem here, but allocating a little more stack space
 638          *      is better than having a bug
 639          */
 640         /*      if (arguments_num > (intreg_argnum + fltreg_argnum)) */
 641         /*              ifmemuse = arguments_num - (intreg_argnum + fltreg_argnum); */
 642         if (rd->arguments_num > rd->fltreg_argnum)
 643                 lsra_mem_use = rd->arguments_num - rd->fltreg_argnum;
 644 #else
 645         if (rd->arguments_num > rd->intreg_argnum)
 646                 lsra_mem_use = rd->arguments_num - rd->intreg_argnum;
 647 #endif
 648         else
 649                 lsra_mem_use = 0;
 650 #endif
 651 #ifdef SPECIALMEMUSE
 652         lsra_mem_use = rd->ifmemuse;
 653 #endif
 654
 655 #ifdef LSRA_DEBUG
 656         printf("Alloc Rest\n");
 657 #endif
 658         lsra_alloc(m, rd, ls->lifetimes,&lsra_mem_use);
 659 #ifdef LSRA_DEBUG
 660         printf("Alloc Int\n");
 661 #endif
 662         lsra_alloc(m, rd, int_lt,&lsra_mem_use);
 663 #ifdef LSRA_DEBUG
 664         printf("Alloc Flt\n");
 665 #endif
 666         lsra_alloc(m, rd, flt_lt,&lsra_mem_use);
 667
 668 #ifdef LSRA_PRINTLIFETIMES
 669         printf("Int RA complete \n");
 670         printf("Lifetimes after splitting int: \n");
 671         print_lifetimes(rd, int_lt);
 672
 673         printf("Flt RA complete \n");
 674         printf("Lifetimes after splitting flt:\n");
 675         print_lifetimes(rd, flt_lt);
 676
 677         printf("Rest RA complete \n");
 678         printf("Lifetimes after leftt:\n");
 679         print_lifetimes(rd, ls->lifetimes);
 680 #endif
 681
 682         rd->maxmemuse=lsra_mem_use;
 683 }
 684
 685 void lsra_alloc(methodinfo *m, registerdata *rd, struct lifetime *lifet, int *mem_use)
 686 {
 687         int flags,regoff;
 688         struct lifetime *lt;
 689         struct freemem *fmem;
 690         struct stackslot *n;
 691
 692         fmem=DNEW(struct freemem);
 693         fmem->off=-1;
 694         fmem->next=NULL;
 695
 696         for (lt=lifet;lt!=NULL;lt=lt->next) {
 697 #ifdef LSRA_MEMORY
 698                 lt->reg=-1;
 699 #endif
 700                 if (lt->reg==-1) {
 701                         flags=INMEMORY;
 702
 703                         regoff=lsra_getmem(lt, fmem, mem_use);
 704                 } else {
 705                         flags=lt->savedvar;
 706                         regoff=lt->reg;
 707                 }
 708
 709                 if (lt->v_index < 0) {
 710                         for (n=lt->local_ss; n!=NULL; n=n->next) {
 711                                 lsra_setflags( &(n->s->flags), flags);
 712                                 n->s->regoff=regoff;
 713                         }
 714                 } else { /* local var */
 715                         if (rd->locals[lt->v_index][lt->type].type>=0) {
 716 /*                              lsra_setflags( &(rd->locals[lt->v_index][lt->type].flags), flags); */
 717                                 rd->locals[lt->v_index][lt->type].flags= flags;
 718                                 rd->locals[lt->v_index][lt->type].regoff=regoff;
 719                         } else panic("Type Data mismatch 1\n");
 720                 }
 721         }
 722 }
 723
 724 void lsra_setflags(int *flags, int newflags)
 725 {
 726         if ( newflags & INMEMORY)
 727                 *flags |= INMEMORY;
 728         else
 729                 *flags &= ~INMEMORY;
 730
 731         if (newflags & SAVEDVAR)
 732                 *flags |= SAVEDVAR;
 733 }
 734
 735 int lsra_getmem(struct lifetime *lt, struct freemem *fmem, int *mem_use)
 736 {
 737         struct freemem *fm, *p;
 738
 739         /* noch kein Speicher vergeben, oder alle Enden später */
 740         if ((fmem->next == NULL) || (fmem->next->end > lt->i_start))
 741                 fm=lsra_getnewmem(mem_use);
 742         else {
 743                 /* Speicherstelle frei */
 744                 fm=fmem->next;
 745                 fmem->next=fm->next;
 746                 fm->next=NULL;
 747         }
 748         fm->end=lt->i_end;
 749         for (p=fmem; (p->next!=NULL) && (p->next->end < fm->end); p=p->next);
 750         fm->next=p->next;
 751         p->next=fm;
 752         return fm->off;
 753 }
 754
 755 struct freemem *lsra_getnewmem(int *mem_use)
 756 {
 757         struct freemem *fm;
 758
 759         fm=DNEW(struct freemem);
 760         fm->next=NULL;
 761         fm->off=*mem_use;
 762         (*mem_use)++;
 763         return fm;
 764 }
 765
 766 void _lsra_main( methodinfo *m, lsradata *ls, struct lifetime *lifet,   struct lsra_reg *reg, int tmp_reg_count, int sav_reg_count, int *mem_use, int *reg_use)
 767 {
 768         struct lifetime *lt;
 769         int i;
 770         int _reg_use;
 771         int reg_count, active_count;
 772
 773         if ((tmp_reg_count+sav_reg_count) == 0) {
 774                 for (lt=lifet; lt != NULL; lt=lt->next)
 775                         lt->reg=-1;
 776                 return;
 777         }
 778
 779         ls->active_tmp = NULL;
 780         ls->active_sav = NULL;
 781         ls->active_tmp_count=0;
 782         ls->active_sav_count=0;
 783         for (lt=lifet; lt != NULL; lt=lt->next) {
 784                 lsra_expire_old_intervalls(ls, lt,reg);
 785                 if (lt->savedvar && (!m->isleafmethod)) {
 786                         reg_count=sav_reg_count;
 787                         active_count=ls->active_sav_count;
 788                 }
 789                 else {
 790                         reg_count=tmp_reg_count;
 791                         active_count=ls->active_sav_count+ls->active_tmp_count;
 792                 }
 793                 if (active_count == reg_count)
 794                         spill_at_intervall(ls, lt);
 795                 else {
 796                         for (i=reg_count-1;i>=0;i--) {
 797                                 if (reg[i].use==0) {
 798                                         reg[i].use=1;
 799                                         lt->reg=reg[i].reg_index;
 800                                         _reg_use=i;
 801                                         if (_reg_use<*reg_use) *reg_use=_reg_use;
 802                                         break;
 803                                 }
 804                         }
 805                         if (i < sav_reg_count)
 806                                 lsra_add_active(lt, &(ls->active_sav), &(ls->active_sav_count));
 807                         else
 808                                 lsra_add_active(lt, &(ls->active_tmp), &(ls->active_tmp_count));
 809                 }
 810         }
 811 }
 812
 813 void lsra_add_active(struct lifetime *lt, struct active_lt **active, int *active_count)
 814 {
 815         struct active_lt *alt,*alt1,*alt2;
 816         alt=DNEW(struct active_lt);
 817         alt->lt=lt;
 818
 819         for(alt1=alt2=*active; alt1 != NULL; alt2=alt1, alt1=alt1->next)
 820                 if (alt1->lt->i_end > lt->i_end) break;
 821
 822         if (alt1 == *active) {
 823                 alt->next = *active;
 824                 *active = alt;
 825         } else {
 826                 alt->next = alt2->next;
 827                 alt2->next = alt;
 828         }
 829         (*active_count)++;
 830 }
 831
 832
 833 void lsra_expire_old_intervalls(lsradata *ls, struct lifetime *lt, struct lsra_reg *reg)
 834 {
 835         _lsra_expire_old_intervalls(lt, reg, &(ls->active_tmp), &(ls->active_tmp_count));
 836         _lsra_expire_old_intervalls(lt, reg, &(ls->active_sav), &(ls->active_sav_count));
 837 }
 838
 839 void _lsra_expire_old_intervalls(struct lifetime *lt, struct lsra_reg *reg, struct active_lt **active, int *active_count)
 840 {
 841         struct active_lt *alt,*alt1;
 842         int i;
 843
 844         for (alt1=alt=*active; alt != NULL; alt1=alt, alt=alt->next) {
 845                 if (alt->lt->i_end >= lt->i_start) return;
 846                 if (alt == *active)
 847                         *active = (*active)->next;
 848                 else
 849                         alt1->next=alt->next;
 850
 851                 for (i=0;reg[i].reg_index != alt->lt->reg;i++);
 852                 reg[i].use=0;
 853                 (*active_count)--;
 854         }
 855 }
 856
 857 void spill_at_intervall(lsradata *ls, struct lifetime *lt )
 858 {
 859         if (lt->savedvar)
 860                 _spill_at_intervall(lt, &(ls->active_sav), &(ls->active_sav_count));
 861         else {
 862                 _spill_at_intervall(lt, &(ls->active_tmp), &(ls->active_tmp_count));
 863                 if (lt->reg == -1) /* kein tmp mehr frei gewesen */
 864                         _spill_at_intervall(lt, &(ls->active_sav), &(ls->active_sav_count));
 865         }
 866         if (lt->reg == -2) panic("spill_at_intervall: Keine Register mehr frei gewesen!\n");
 867 }
 868
 869 void _spill_at_intervall(struct lifetime *lt, struct active_lt **active, int *active_count)
 870 {
 871         struct active_lt *alt,*alt1;
 872         if (*active == NULL) {
 873                 lt->reg=-2;
 874                 return;
 875         }
 876         /* get last intervall from active */
 877         for (alt1=alt=*active; alt->next != NULL; alt1=alt, alt=alt->next);
 878
 879         if ((alt->lt->i_end > lt->i_end) && (alt->lt->usagecount < lt->usagecount)) {
 880                         lt->reg=alt->lt->reg;
 881                         alt->lt->reg=-1;
 882
 883                         if (alt == *active)
 884                                 *active=(*active)->next;
 885                         else
 886                                 alt1->next=alt->next;
 887                         /*              FREE(alt,struct active_lt); */
 888                         (*active_count)--;
 889                         lsra_add_active(lt, active, active_count);
 890         } else {
 891                 lt->reg=-1;
 892         }
 893 }
 894
 895 int lsra_getmaxblock(methodinfo *m, loopdata *ld, int bb_start)
 896 {
 897         int i, *blocks;
 898         int finished;
 899         struct depthElement *hp;
 900         int bb_max;
 901
 902         blocks=DMNEW(int, m->basicblockcount);
 903         /* ExTable Ablauf kann in die STD Code BB wieder "hineinspringen" */
 904         /* -> deshalb */
 905         /* TODO vorher alle "normalen" BB mit 2=bereits besucht initialisieren */
 906         bb_max=0;
 907
 908         for (i=0; i<m->basicblockcount; i++) blocks[i]=-1;
 909
 910         blocks[bb_start]=1;
 911
 912         finished=0;
 913         while (!finished) {
 914                 finished=1;
 915                 for (i=0; i<m->basicblockcount; i++) {
 916
 917                         if (blocks[i] == 1) {
 918                                 if (i > bb_max) bb_max = i;
 919                                 blocks[i]=2; /* visited */
 920                                 for (hp=ld->c_dTable[i]; hp!=NULL; hp=hp->next) {
 921                                         if (blocks[hp->value] != 2) {
 922                                                 blocks[hp->value]=1; /* to visit */
 923                                                 finished=0;
 924                                         }
 925                                 }
 926                         }
 927                 }
 928         }
 929 #ifdef LSRA_DEBUG
 930         printf("ExTable searching: BB_MAX %3i ",bb_max);
 931         for (i=0; i<m->basicblockcount; i++)
 932                 if (blocks[i] != -1) printf("%3i ",i);
 933         printf("\n");
 934 #endif
 935         return bb_max;
 936 }
 937
 938
 939 void lsra_calc_lifetime_length(methodinfo *m, lsradata *ls, codegendata *cd, loopdata *ld)
 940 {
 941         struct lifetime *lt;
 942         struct _i_list *il;
 943         struct l_loop *loops;
 944         struct b_loop *block_loop;
 945         exceptiontable *ex;
 946         int *exh_max; /* Exception Handler End BB */
 947         int *exh_min; /* Exception Handler Start BB */
 948         int *ex_max;  /* Exception guarded Area End BB */
 949         int *ex_min;  /* Exception guarded Area Start BB */
 950
 951         int blast,bfirst,ilast,ifirst,usage;
 952
 953         int i, j, num_loops;
 954         struct LoopContainer *lc;
 955         struct LoopElement *le;
 956
 957         /**********/
 958         /* Todo: */
 959         /* Für Exceptionhandler Blocks wurde keine Loop Analyse durchgeführt! */
 960         /* -> deshalb vorerst die einzelnen Handler als eine Loop eintragen */
 961         /* oder loop analyse extra für jeden Handler aufrufen */
 962         /**/
 963         /* lifetime der Vars des ExHandlers über guarded Bereich ausdehnen! */
 964         /**/
 965         /* Falls die einzelnen Blöcke einer Loop nicht durchgehend nummeriert sind */
 966         /* auch nicht alle in block_loop eintragen! */
 967
 968         exh_max = DMNEW(int, cd->exceptiontablelength);
 969         exh_min = DMNEW(int, cd->exceptiontablelength);
 970         ex_max =  DMNEW(int, cd->exceptiontablelength);
 971         ex_min =  DMNEW(int, cd->exceptiontablelength);
 972
 973         /* BB der Exhandler bestimmen + BB der guarded Area hinzu */
 974         ex = cd->exceptiontable;
 975         for (i=0; ex != NULL; i++,ex = ex->down) {
 976                 if (ex->handler == NULL) {
 977 #ifdef LSRA_DEBUG
 978                         printf("lsra_init_blocks EXCEPTIONTABLE without handler!\n");
 979 #endif
 980                 } else {
 981                         if ((ex->handler->debug_nr < 0) || (ex->handler->debug_nr >= m->basicblockcount)) {
 982 #ifdef LSRA_DEBUG
 983                                 printf("lsra_init_blocks EXCEPTIONTABLE Handler Blocknummer invalid! %i\n", ex->handler->debug_nr);
 984 #endif
 985                         } else {
 986                                 exh_min[i]=ex->handler->debug_nr;
 987                                 exh_max[i]=lsra_getmaxblock(m, ld, ex->handler->debug_nr);
 988
 989                                 ex_min[i]=ex->start->debug_nr;
 990                                 ex_max[i]=ex->end->debug_nr;
 991 #ifdef LSRA_DEBUG
 992                                 printf("EX %3i exmin %3i exmax %3i exhmin %3i exhmax %3i\n",i,ex_min[i],ex_max[i],exh_min[i],exh_max[i]);
 993 #endif
 994                         }
 995                 }
 996         }
 997
 998         /* extend lifetime within loops */
 999
1000         for (num_loops=0,lc =ld->c_allLoops;lc!=NULL;num_loops++,lc=lc->next);
1001
1002         /* set up loops[i].b_first .b_last to hold the first and last node of all loops */
1003         loops=DMNEW(struct l_loop,num_loops);
1004         for (i=0,lc=ld->c_allLoops;i<num_loops;i++,lc=lc->next) {
1005
1006                 le = lc->nodes;
1007                 bfirst=m->basicblockcount;
1008                 blast=0;
1009                 while (le != NULL) {
1010                         if (le->node<bfirst) bfirst=le->node;
1011                         if (le->node>blast) blast=le->node;
1012                         le = le->next;
1013                 }
1014                 loops[i].b_first=bfirst;
1015                 loops[i].b_last=blast;
1016                 loops[i].nesting=0;
1017         }
1018
1019         /* sort loops by b_first desc*/
1020         for (i=0; i<num_loops-1;i++) {
1021                 for (j=i+1; j<num_loops;j++) {
1022                         if (loops[i].b_first < loops[j].b_first) {
1023                                 bfirst=loops[j].b_first;
1024                                 blast=loops[j].b_last;
1025                                 loops[j].b_first=loops[i].b_first;
1026                                 loops[j].b_last=loops[i].b_last;
1027                                 loops[i].b_first=bfirst;
1028                                 loops[i].b_last=blast;
1029                         }
1030                 }
1031         }
1032
1033         /* check for nesting_level, overlapping */
1034         for (i=0; i<num_loops-1;i++) {
1035                 /*! loops[i].b_first >= loops[i+1].b_first !*/
1036                 if (loops[i+1].b_last>=loops[i].b_first) {
1037                         if (loops[i+1].b_last<loops[i].b_last) {
1038                                 /* overlapping -> make one loop of both */
1039                                 loops[i+1].b_last=loops[i].b_last;
1040                                 loops[i].b_first=-1;
1041                                 loops[i].b_last=-1;
1042                         } else {
1043                                 loops[i].nesting++; /* only boolean if nested... */
1044                         }
1045                 }
1046         }
1047
1048         /* cumulate basicblocks[i].icount in block_loop[i].instr*/
1049         block_loop=DMNEW(struct b_loop, m->basicblockcount);
1050         for (i=0;i<m->basicblockcount; i++) {
1051                 block_loop[i].loop=-1;
1052                 if (i!=0)
1053                         block_loop[i].instr=block_loop[i-1].instr+m->basicblocks[i-1].icount;
1054                 else
1055                         block_loop[i].instr=0;
1056         }
1057
1058         /* set block_loop[j].loop to loop index, if Basic Block is in this loop */
1059         for (i=0; i<num_loops;i++) {
1060                 if (loops[i].b_first!=-1) {
1061                         /* valid loop */
1062                         for (j=loops[i].b_first;j<=loops[i].b_last;j++) block_loop[j].loop=i;
1063                 }
1064         }
1065
1066         /* now iterate through lifetimes and expand them */
1067         lt=ls->lifetimes;
1068         while(lt!=NULL) {
1069
1070                 if (ls->back_edge_panic) {
1071                         lt->i_start=0;
1072                         lt->i_end=block_loop[m->basicblockcount-1].instr+m->basicblocks[m->basicblockcount-1].icount;
1073                 } else {
1074                         usage = 1;
1075                         il=lt->i_list;
1076                         blast=il->b_index;
1077                         ilast=il->instr;
1078                         while (il->next!=NULL) {
1079                                 if ((il->b_index != il->next->b_index) || ((il->b_index == il->next->b_index) && (il->instr != il->next->instr))) {
1080                                         if (block_loop[il->b_index].loop == -1)
1081                                                 usage++; /* not in a loop */
1082                                 }
1083                                 il=il->next;
1084                         }
1085                         bfirst=il->b_index;
1086                         ifirst=il->instr;
1087                         /* expand lifetimes in a exceptionhandler to at least the whole handler */
1088                         /* TODO do a loop analyze for the exceptionhandler, too*/
1089                         for (i=0; i < cd->exceptiontablelength; i++) {
1090
1091                                 if ( !((bfirst > exh_max[i]) || ( blast < exh_min[i])) ) {
1092                                         /* Überschneidung mit exh_???[i]-> lt liegt in Exceptionhandler */
1093                                         /* -> Start auf mindestens die erste Instruktion des geschützten Bereiches legen */
1094                                         if (bfirst >= exh_min[i]) {
1095                                                 bfirst=exh_min[i];
1096                                                 ifirst=0;
1097                                         }
1098                                         /* -> Ende auf mindestens die letzte Instruktion des geschützten Bereiches legen */
1099                                         if (blast <= exh_max[i]) {
1100                                                 blast=exh_max[i];
1101                                                 ilast= m->basicblocks[exh_max[i]].icount-1;
1102                                         }
1103                                 }
1104                         }
1105
1106                         ilast+=block_loop[blast].instr;   /* add icount of previous Basic Blocks */
1107                         ifirst+=block_loop[bfirst].instr; /* add icount of previous Basic Blocks */
1108
1109                         if ((j=block_loop[bfirst].loop)==-1)
1110                                 j=block_loop[blast].loop;
1111
1112                         if (j!=-1) {
1113                                 if (loops[j].b_first<=bfirst) {
1114                                         bfirst=loops[j].b_first;
1115                                         ifirst=block_loop[bfirst].instr;
1116                                         usage+=loops[j].nesting*100;
1117                                 }
1118                                 if (blast <= loops[j].b_last) {
1119                                         blast=loops[j].b_last;
1120                                         ilast=block_loop[blast].instr+m->basicblocks[blast].icount;
1121                                         usage+=loops[j].nesting*100;
1122                                 }
1123                         }
1124
1125                         lt->i_start=ifirst;
1126                         lt->i_end=ilast;
1127                         i=ilast-ifirst;
1128                         if (i==0) i=1;
1129                         lt->usagecount=usage;
1130                 }
1131                 lt=lt->next;
1132         }
1133
1134 #ifdef LSRA_DEBUG
1135         for (i=0; i<num_loops;i++) {
1136                 printf("LoopNR: %3i Start: %3i End: %3i Nesting: %3i Block_loop[%3i]:",i,loops[i].b_first,loops[i].b_last,loops[i].nesting,i);
1137                 for (j=0;j<m->basicblockcount;j++)
1138                         if (block_loop[j].loop==i) printf(" %3i",j);
1139                 printf("\n");
1140         }
1141 #endif
1142 }
1143
1144 /* void lsra_sort_lt(struct lifetime **lifet) */
1145 /* { */
1146 /*      struct lifetime *lt, lt_new, *temp, *tmp; */
1147
1148 /*      lt_new.next=NULL; */
1149
1150 /*      for (lt=*lifet; lt!= NULL;) { */
1151 /*              temp=lt->next; */
1152
1153 /*              for(tmp=&lt_new; (tmp->next!= NULL) && (tmp->next->i_start < lt->i_start); tmp=tmp->next); */
1154 /*              lt->next=tmp->next; */
1155 /*              tmp->next=lt; */
1156 /*              lt=temp; */
1157 /*      } */
1158 /*      *lifet=lt_new.next; */
1159 /* } */
1160
1161
1162 #define P_MAX 21
1163 void _lsra_merge_lt(struct lifetime **p, int i1, int i2)
1164 {
1165         struct lifetime *iptr, *iptr1, *iptr2;
1166
1167         if ( (iptr1=p[i2])==NULL) return;
1168     if ( (iptr=p[i1])==NULL) return;
1169
1170         iptr2=p[i1]=NULL;
1171         p[i2]=NULL;
1172
1173         while  ((iptr != NULL) && (iptr1 != NULL)) {
1174                 if (iptr->i_start < iptr1->i_start) {
1175                         if (iptr2==NULL) {
1176                                 p[i1]=iptr;
1177                         } else {
1178                                 iptr2->next=iptr;
1179                         }
1180                         iptr2=iptr;
1181                         iptr=iptr->next;
1182                 } else {
1183                         if (iptr2==NULL) {
1184                                 p[i1]=iptr1;
1185                         } else {
1186                                 iptr2->next=iptr1;
1187                         }
1188                         iptr2=iptr1;
1189                         iptr1=iptr1->next;
1190                 }
1191         }
1192         if (iptr==NULL)
1193                 iptr2->next=iptr1;
1194         if (iptr1==NULL)
1195                 iptr2->next=iptr;
1196 }
1197
1198 void lsra_merge_lt(struct lifetime **p, int top)
1199 {
1200         int i,j;
1201
1202         for (j=1; j<top; j*=2)
1203                 for (i=1; i<top; i+=2*j)
1204                         _lsra_merge_lt(p, i, i+j);
1205         _lsra_merge_lt(p, 0, 1);
1206 }
1207
1208 void lsra_sort_lt(struct lifetime **lifet)
1209 {
1210         /* sort lifetimes by increasing start point */
1211 /*      struct lifetime **plt,**plt1; */
1212         struct lifetime *lt, *temp, *tmp;
1213         int i, top;
1214         struct lifetime **p;
1215
1216         p=DMNEW(struct lifetime *, P_MAX);
1217         for (i=0; i<P_MAX; i++) p[i]=NULL;
1218
1219         top=0;
1220
1221         for (lt=*lifet; lt!= NULL;) {
1222                 temp=lt;
1223                 lt=lt->next;
1224                 if (lt == NULL) {
1225                         p[top]=temp;
1226                         temp->next=NULL;
1227                 } else {
1228                         tmp=lt;
1229                         lt=lt->next;
1230
1231                         if (temp->i_start < tmp->i_start) {
1232                                 p[top]=temp;
1233                                 /* temp->next == tmp */
1234                                 tmp->next=NULL;
1235                         } else {
1236                                 p[top]=tmp;
1237                                 tmp->next=temp;
1238                                 temp->next=NULL;
1239                         }
1240                 }
1241                 top++;
1242                 if (top == P_MAX) {
1243                         lsra_merge_lt(p, P_MAX);
1244                         top=1;
1245                 }
1246         }
1247         lsra_merge_lt(p, top);
1248         *lifet=p[0];
1249 }
1250
1251 #ifdef LSRA_PRINTLIFETIMES
1252 void print_lifetimes(registerdata *rd, struct lifetime *lt)
1253 {
1254         struct lifetime *n;
1255         struct _i_list *ni;
1256         int type,flags,regoff,j,varkind;
1257         /*      int i; */
1258
1259         for (n=lt,j=0; n!=NULL; n=n->next,j++) {
1260                 if (n->v_index < 0) { /* stackslot */
1261                         type = n->local_ss->s->type;
1262                         flags=n->local_ss->s->flags;
1263                         regoff=n->local_ss->s->regoff;
1264                         varkind=n->local_ss->s->varkind;
1265                 } else { /* local var */
1266                         if (rd->locals[n->v_index][n->type].type>=0) {
1267                                 type = rd->locals[n->v_index][n->type].type;
1268                                 flags=rd->locals[n->v_index][n->type].flags;
1269                                 regoff=rd->locals[n->v_index][n->type].regoff;
1270                                 varkind=-1;
1271                         } else
1272                                 panic("Type Data mismatch 3\n");
1273                 }
1274                 printf("i_Start: %3i i_stop: %3i reg: %3i VI: %3i Usage: %3i type: %3i flags: %3i varkind: %3i ILst: ",n->i_start,n->i_end,regoff,n->v_index,n->usagecount,type,flags, varkind);
1275                 for (ni=n->i_list; ni!=NULL; ni=ni->next) {
1276                         if (ni==ni->next) panic("loop in instruction list!\n");
1277                         printf( "(%3i,%3i) ",ni->b_index,ni->instr);
1278                 }
1279                 printf("\n");
1280         }
1281         printf( "%3i Lifetimes printed \n",j);
1282 }
1283 #endif
1284
1285 struct stackslot *lsra_make_ss(stackptr s, int bb_index)
1286 {
1287         struct stackslot *ss;
1288
1289         ss=DNEW(struct stackslot);
1290         ss->bb=bb_index;
1291         ss->s=s;
1292         return ss;
1293 }
1294
1295 /* merge i_list from lt1 to lt in order */
1296 void lsra_merge_i_lists(struct lifetime *lt, struct lifetime *lt1)
1297 {
1298         struct _i_list *iptr, *iptr1, *iptr2;
1299
1300         /* merge i_lists in order */
1301         iptr=lt->i_list;
1302         iptr2=lt->i_list=NULL;
1303         iptr1=lt1->i_list;
1304         while  ((iptr != NULL) && (iptr1 != NULL)) {
1305                 if (iptr1->instr == -1) {
1306                         /* throw away, just for joining */
1307                         iptr1=iptr1->next;
1308                 } else {
1309                         if ((iptr->b_index > iptr1->b_index)|| ((iptr->b_index == iptr1->b_index) && (iptr->instr > iptr1->instr))) {
1310                                 if (lt->i_list==NULL) {
1311                                         lt->i_list=iptr;
1312                                 } else {
1313                                         iptr2->next=iptr;
1314                                 }
1315                                 iptr2=iptr;
1316                                 iptr=iptr->next;
1317                         } else {
1318                                 if (lt->i_list==NULL) {
1319                                         lt->i_list=iptr1;
1320                                 } else {
1321                                         iptr2->next=iptr1;
1322                                 }
1323                                 iptr2=iptr1;
1324                                 iptr1=iptr1->next;
1325                         }
1326                 }
1327         }
1328 #ifdef LSRA_DEBUG
1329         if (iptr2 == NULL)
1330                 panic("lsra_merge_i_lists: Empty Instruction List in Lifetime\n");
1331 #endif
1332         if (iptr==NULL) {
1333                 if (lt->i_list==NULL)
1334                         lt->i_list=iptr1;
1335                 else
1336                         iptr2->next=iptr1;
1337         }
1338         if (iptr1==NULL) {
1339                 if (lt->i_list==NULL)
1340                         lt->i_list=iptr;
1341                 else
1342                         iptr2->next=iptr;
1343         }
1344 }
1345
1346 /* merge local_ss from lt1 to lt in order */
1347 void lsra_merge_local_ss(struct lifetime *lt, struct lifetime *lt1)
1348 {
1349         struct stackslot *ssptr, *ssptr1, *ssptr2;
1350
1351         /* merge stackslots in order */
1352         ssptr=lt->local_ss;
1353         ssptr2=lt->local_ss=NULL;
1354         ssptr1=lt1->local_ss;
1355         while  ((ssptr != NULL) && (ssptr1 != NULL)) {
1356
1357                 if (ssptr->s > ssptr1->s) {
1358                         if (lt->local_ss==NULL) {
1359                                 lt->local_ss=ssptr;
1360                         } else {
1361                                 ssptr2->next=ssptr;
1362                         }
1363                         ssptr2=ssptr;
1364                         ssptr=ssptr->next;
1365                 } else {
1366                         if (lt->local_ss==NULL) {
1367                                 lt->local_ss=ssptr1;
1368                         } else {
1369                                 ssptr2->next=ssptr1;
1370                         }
1371                         ssptr2=ssptr1;
1372                         ssptr1=ssptr1->next;
1373                 }
1374         }
1375 #ifdef LSRA_DEBUG
1376         if (ssptr2 == NULL)
1377                 panic("lsra_merge_local_ss: Empty Stackslot List in Lifetime\n");
1378 #endif
1379         if (ssptr==NULL) {
1380                 if (lt->local_ss==NULL)
1381                         lt->local_ss=ssptr1;
1382                 else
1383                         ssptr2->next=ssptr1;
1384         }
1385         if (ssptr1==NULL) {
1386                 if (lt->local_ss==NULL)
1387                         lt->local_ss=ssptr;
1388                 else
1389                         ssptr2->next=ssptr;
1390         }
1391 }
1392
1393 #ifdef LSRA_DEBUG
1394 void dump_join( struct lifetime *lt_passing)
1395 {
1396         struct lifetime *lt;
1397         struct stackslot *ss;
1398         int i;
1399
1400         for (lt=lt_passing,i=0; lt != NULL; lt=lt->next, ++i) {
1401                 printf("Lifetime(%2i)\n  PT: ",i);
1402                 for ( ss=lt->passthrough; ss!=NULL; ss=ss->next)
1403                         printf("(%2i, %2i, %6p) ",ss->bb, ss->s->varnum, (void *)ss->s);
1404                 printf("\n  SS: ");
1405                 for (ss = lt->local_ss; ss!=NULL; ss=ss->next)
1406                         printf("(%2i, %2i, %6p) ", ss->bb, ss->s->varnum, (void *)ss->s);
1407                 printf("\n");
1408         }
1409 }
1410 #endif
1411
1412 void lsra_join_lifetimes(methodinfo *m, codegendata *cd, lsradata *ls, loopdata *ld)
1413 {
1414         int i, j, index, stacks_top;
1415         int in1, out1, in2, out2, temp;
1416         struct depthElement *de;
1417
1418         int *in_stacks, *out_stacks;
1419         stackptr out, s;
1420         struct stackslot **stacks, *ss, *ss1, *ss_new;
1421         struct lifetime *lt, *lt_prev, *lt_new, *lt_passing;
1422         struct stackslot *p, *q, *r;
1423         bool drop, pt;
1424
1425 #ifdef LSRA_DEBUG
1426         stackptr in;
1427
1428         in=m->basicblocks[0].instack; /* ?falls Instack des Startblocks != leer ?*/
1429         if (in != NULL) printf("------------ Instack von BB0 nicht leer! -------\n");
1430 #endif
1431
1432         /* join copies of dup/swap? or let just codegen copy the contents?  */
1433         /* -> ?TODO? save at ICMD_DUP* and ICMD_SWAP Copy Info              */
1434
1435         /* out_stacks hold an index to stacks, which holds the joined stacks */
1436         /* in_stacks hold an index to out_stacks, with which they are joined */
1437         /* an initial index of -1 mark, that they where not visited yet      */
1438         in_stacks =   DMNEW(int, m->basicblockcount);
1439         out_stacks = DMNEW(int, m->basicblockcount);
1440         stacks = DMNEW(struct stackslot *, m->basicblockcount);
1441 /*      for (i=0; i< m->basicblockcount; i++) stacks[i]=NULL; */
1442         for (i=0; i < m->basicblockcount; i++ ) in_stacks[i]=out_stacks[i]=-1;
1443         stacks_top=0;
1444
1445         for (i=0; i < m->basicblockcount; i++)
1446                 if (m->basicblocks[i].flags >= BBREACHED) {
1447                         if ((out=m->basicblocks[i].outstack) != NULL) {
1448                                 ss=lsra_make_ss(out, i);
1449                                 ss->next=NULL;
1450                                 stacks[stacks_top]=ss;
1451                                 out_stacks[i]=stacks_top++;
1452                                 for (de=ld->c_dTable[i]; de != NULL; de=de->next) {
1453                                         if (in_stacks[de->value] == -1) { /* not visited==joined yet */
1454                                                 in_stacks[de->value] = i;
1455                                                 ss=lsra_make_ss(m->basicblocks[de->value].instack, de->value);
1456                                                 ss->next=stacks[out_stacks[i]];
1457                                                 stacks[out_stacks[i]]=ss;
1458                                         } else { /* in stacks already joined -> join with others */
1459                                                 /* join this outstack to index in_stack[de->value] points to */
1460                                                 for (ss=stacks[out_stacks[i]]; ss->next != NULL; ss=ss->next); /* get last element */
1461                                                 ss->next=stacks[out_stacks[in_stacks[de->value]]];
1462                                                 stacks[out_stacks[in_stacks[de->value]]]=stacks[out_stacks[i]];
1463                                                 stacks[out_stacks[i]]=NULL;
1464                                                 /* update all prior out_stacks indexes to this new join */
1465                                                 for (j=0; j <= i; j++) {
1466                                                         if (out_stacks[j] == out_stacks[i]) {
1467                                                                 out_stacks[j]=out_stacks[in_stacks[de->value]];
1468                                                         }
1469                                                 }
1470                                         }
1471                                 }
1472                         }
1473                 }
1474
1475         /* leere einträge aus stacks entfernen */
1476         for (i=index=0; i< stacks_top;) {
1477                 if (stacks[index]!=NULL) { /* nächsten freien Platz suchen */
1478                         ++index;
1479                         ++i;
1480                 } else {
1481                         if (stacks[i]==NULL) { /* nächsten bestetzten Platz zum verschieben suchen*/
1482                                 ++i;
1483                         } else { /* von i nach index umhängen */
1484                                 stacks[index]=stacks[i];
1485                                 stacks[i]=NULL;
1486                                 ++index;
1487                         }
1488                 }
1489         }
1490
1491         lt_passing=NULL;
1492         /* 0 <= i < index | join all corresponding stackslots of in- and outstacks of stacks[i] to lt_new */
1493         /* and put lt_new in lt_passing (if passthrough ss exist in them) or ls->lifetimes                */
1494         for (i=0; i < index; i++) {
1495                 while (stacks[i]->s != NULL) {
1496                         lt_new=NULL;
1497                         for (ss=stacks[i]; ss!=NULL; ss=ss->next) {
1498                                 /* search stackslot ss->s lifetimelist of basicblock(ss->bb) (ss_lifetimes) */
1499                                 /* remember the link before found lifetime, to remove it afterwards         */
1500                                 for (lt_prev=lt=ls->ss_lifetimes[ss->bb]; lt!=NULL; lt_prev=lt, lt=lt->next) {
1501                                         for (ss1=lt->local_ss; (ss1!=NULL) && (ss1->s != ss->s); ss1 = ss1->next);
1502                                         if (ss1 != NULL) break; /* found */
1503                                 }
1504 #ifdef LSRA_DEBUG
1505                                 if (lt==NULL) panic("lsra_join_lifetimes error in lifetimelist\n");
1506 #endif
1507                                 /* Remove found lifetime from Block Stackslot Lifetimelist */
1508                                 if (lt==ls->ss_lifetimes[ss->bb]) {
1509                                         ls->ss_lifetimes[ss->bb]=lt->next;
1510                                 } else {
1511                                         lt_prev->next=lt->next;
1512                                 }
1513                                 lt->next=NULL;
1514
1515                                 drop = false;
1516                                 if (lt->i_list->instr==-1) {
1517                                         if (out_stacks[in_stacks[ss->bb]] == out_stacks[ss->bb]) {
1518                                                 /* Throughpassing Basicblock is already in one "join Group" */
1519                                                 /* If this stackslot ((lt->local_ss)ss1->s == ss->s) is already in lt_new->local_ss */
1520                                                 /* do not add it a second time! */
1521                                                 if (lt_new != NULL) {
1522                                                         for (ss_new=lt_new->local_ss; (ss_new != NULL) && (ss_new->s != ss1->s); ss_new = ss_new->next);
1523                                                         if (ss_new != NULL) drop = true;
1524                                                 }
1525                                         }
1526                                 }
1527                                 if (!drop) {
1528                                         /* lt->s->varkind=TEMPVAR */; /* no LOCALVAR, ARGVAR or STACKVAR with joined lifetimes */
1529                                         lt->v_index=-1; /* not a local var */
1530
1531                                         /* join Lifetime lt to lt_new */
1532                                         if (lt_new == NULL) {
1533                                                 lt_new = lt;
1534                                                 lt_new->passthrough = NULL;
1535                                         } else {
1536                                                 lsra_merge_i_lists( lt_new, lt);
1537                                                 lsra_merge_local_ss( lt_new, lt);
1538                                         }
1539
1540
1541                                         pt=(lt->i_list->instr==-1); /* remember this now, because merge_i_list could once destroy this link*/
1542
1543                                         /* add stackslot to local_ss of lt_new */
1544                                         ss_new = DNEW(struct stackslot);
1545
1546                                         lt_new->savedvar |= (lt->savedvar & SAVEDVAR);
1547
1548                                         if (pt) { /*lt->i_list->instr==-1) {*/
1549                                         /* BB passes this stackslot through -> join later with other side!*/
1550                                                 if (out_stacks[in_stacks[ss->bb]] != out_stacks[ss->bb]) {
1551                                                         /* Stackslot ist not passed through to same (this) "join group" */
1552
1553                                                         p = DNEW(struct stackslot);
1554                                                         p->bb = ss->bb; /* Basic Block index of joined Lifetime */
1555                                                         p->s = ss->s;
1556                                                         /* sort p in lt_new->passthrough list by increasing stackslot adress               */
1557                                                         /* there are no two stackslots allowed, which "join" the same "join groups"    */
1558                                                         /* in case one has to be dropped, keep the one with the "greater" address      */
1559                                                         r = NULL;
1560                                                         drop = false;
1561                                                         in2=out_stacks[in_stacks[p->bb]];
1562                                                         out2=out_stacks[p->bb];
1563                                                         if (in2 > out2) { temp=in2; in2=out2; out2=temp; }
1564                                                         for (q=lt_new->passthrough; (q != NULL);) {
1565                                                                 in1=out_stacks[in_stacks[q->bb]];
1566                                                                 out1=out_stacks[q->bb];
1567                                                                 if (in1 > out1) { temp=in1; in1=out1; out1=temp; }
1568
1569                                                                 if ((in1 == in2) && (out1 == out2)) { /* p->s would join to same group -> drop the one with the lower address */
1570                                                                         if (p->s < q->s)  /* drop p->s, it has the lower address */
1571                                                                                 drop = true;
1572                                                                         else { /* drop q from the list, since it has the lower address */
1573                                                                                 if (q == lt_new->passthrough ) {
1574                                                                                         lt_new->passthrough=q->next;
1575                                                                                         q=q->next;
1576                                                                                 } else { /* r points to the previous element */
1577                                                                                         r->next=q->next;
1578                                                                                 }
1579                                                                         }
1580                                                                 }
1581                                                                 if (q != NULL) {
1582                                                                         if (q->s < p->s)
1583                                                                                 r=q; /* remember position for sorting p in */
1584                                                                         q=q->next;
1585                                                                 }
1586                                                         }
1587                                                         if (!drop) {
1588                                                                 if (r == NULL) {
1589                                                                         /* List Empty or all elements greater than p->s */
1590                                                                         p->next=lt_new->passthrough;
1591                                                                         lt_new->passthrough=p;
1592                                                                 } else {
1593                                                                         p->next=r->next;
1594                                                                         r->next=p;
1595                                                                 }
1596                                                         }
1597                                                 }
1598                                         }
1599                                 }
1600                                 ss->s=ss->s->prev; /* Next Stackslot for next Iteration */
1601                         } /*for */
1602                         if (lt_new->passthrough != NULL) {
1603                                 lt_new->next=lt_passing;
1604                                 lt_passing=lt_new;
1605                         } else {
1606                                 lt_new->next=ls->lifetimes;
1607                                 ls->lifetimes=lt_new;
1608                         }
1609                 }/* while */
1610         } /* for */
1611
1612         /* join lifetimes with same stackslots in ->passthrough in lt_passing */
1613         for (lt=lt_passing; lt != NULL; lt=lt->next) {
1614                 while (lt->passthrough != NULL) {
1615 #ifdef LSRA_DEBUG
1616                         printf("before \n");
1617                         dump_join(lt_passing);
1618 #endif
1619                         s=lt->passthrough->s;
1620                         lt->passthrough=lt->passthrough->next; /* drop this stackslot from lt_passthrough list */
1621                         /* search for next lifetime, which has the same stackslot in passthrough  */
1622                         /* lt_new->next will point to it                                          */
1623                         /* there has to be another lifetime after lt with same s in passthrough   */
1624                         for (lt_new=lt; (lt_new->next != NULL); lt_new=lt_new->next) {
1625                                 /* passthrough is sorted by increasing address of s */
1626                                 /* remember in q the list element before p with p->s == s */
1627                                 for (p=lt_new->next->passthrough; (p!=NULL) && (p->s < s); q=p,p=p->next);
1628                                 if ((p != NULL) && (p->s == s)) {
1629                                         /* found -> now drop this stackslot from lt_new's passtrough list */
1630                                         if (p == lt_new->next->passthrough) { /* first element in list */
1631                                                 lt_new->next->passthrough = lt_new->next->passthrough->next;
1632                                         } else
1633                                                 q->next=p->next;
1634                                         break;
1635                                 }
1636                         }
1637 #ifdef LSRA_DEBUG
1638                         if (lt_new->next==NULL)
1639                                 panic("lsra_join_lifetimes error in lt_passing lifetimelist\n");
1640 #endif
1641                         /* join lt and lt_new->next to lt */
1642                         lt->savedvar |= (lt_new->next->savedvar & SAVEDVAR);
1643
1644                         /* join local_ss lists */
1645 #ifdef LSRA_DEBUG
1646                         if (lt_new->next->local_ss == NULL)
1647                                 panic("lsra_join_lifetimes Lifetime without stackslot\n");
1648 #endif
1649 /*                      for (ss=lt_new->next->local_ss; (ss->next != NULL); ss=ss->next); */
1650 /*                      ss->next=lt->local_ss; */
1651 /*                      lt->local_ss=lt_new->next->local_ss; */
1652                         lsra_merge_local_ss(lt, lt_new->next);
1653
1654                         /* merge i_lists in order */
1655                         lsra_merge_i_lists(lt, lt_new->next);
1656
1657                         /* join passthrough lists in ascending order  */
1658                         /* if there are duplicates, it happened that a join was done through the   */
1659                         /* other joins till now, so just drop both of them                         */
1660                         p=lt->passthrough;
1661                         q=lt_new->next->passthrough;
1662                         lt->passthrough=NULL;
1663                         ss=NULL; /* pointer to the end of lt->passthrough */
1664                         while ( (p!=NULL) && (q!=NULL) ) {
1665                                 if (p->s > q->s) {
1666                                         if (ss==NULL) {
1667                                                 lt->passthrough=q;
1668                                         } else {
1669                                                 ss->next=q;
1670                                         }
1671                                         ss=q;
1672                                         q=q->next;
1673                                 } else {
1674                                         if (q->s == p->s) {
1675                                                 /* Drop both stackslots -> they where just joined through some other joins */
1676                                                 q=q->next;
1677                                                 p=p->next;
1678                                         } else {
1679                                                 /* p->s < q->s */
1680                                                 if (ss==NULL) {
1681                                                         lt->passthrough=p;
1682                                                 } else {
1683                                                         ss->next=p;
1684                                                 }
1685                                                 ss=p;
1686                                                 p=p->next;
1687                                         }
1688                                 }
1689                         }
1690                         if (q == NULL) {
1691                                 if (lt->passthrough == NULL)
1692                                         lt->passthrough=p;
1693                                 else
1694                                         ss->next = p;
1695                         }
1696                         if (p == NULL) {
1697                                 if (lt->passthrough == NULL)
1698                                         lt->passthrough=q;
1699                                 else
1700                                         ss->next = q;
1701                         }
1702                         lt_new->next=lt_new->next->next; /* throw away joined lifetime lt_new->next */
1703 #ifdef LSRA_DEBUG
1704                         printf("after\n");
1705                         dump_join(lt_passing);
1706 #endif
1707                 } /* while */
1708         } /* for */
1709
1710         if (lt_passing!=NULL) {
1711                 for (lt=lt_passing; (lt->next!=NULL); lt=lt->next);
1712                 lt->next=ls->lifetimes;
1713                 ls->lifetimes=lt_passing;
1714         }
1715 }
1716
1717
1718 struct _i_list *lsra_add_i_list(struct _i_list *i_list, int instr, int b_index, int store)
1719 {
1720         struct _i_list *n;
1721
1722         n=DNEW(struct _i_list);
1723         n->instr=instr;
1724         n->b_index=b_index;
1725         n->store=store;
1726         n->next=i_list;
1727         return n;
1728 }
1729
1730 void lsra_add_ss(struct lifetime *lt, stackptr s) {
1731         struct stackslot *ss;
1732         /* Stackslot noch nicht eingetragen? */
1733         if ((lt->local_ss==NULL) || (lt->local_ss->s != s)) {
1734                 ss = DNEW(struct stackslot);
1735                 ss->s = s;
1736                 ss->next = lt->local_ss;
1737                 lt->local_ss = ss;
1738                 if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
1739         }
1740 }
1741
1742 #define lsra_new_stack(ls, s, block, instr) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
1743 void _lsra_new_stack(lsradata *ls, stackptr s, int block, int instr, int store)
1744 {
1745         struct lifetime *n;
1746
1747         n=DNEW(struct lifetime);
1748
1749         n->savedvar = (s->flags & SAVEDVAR);
1750         n->local_ss=NULL;
1751         lsra_add_ss( n, s);
1752         n->usagecount=1;
1753         if (s->varkind == LOCALVAR)
1754                 n->v_index=s->varnum;
1755         else
1756                 n->v_index=-1;
1757         n->i_list=NULL;
1758
1759         n->next=ls->ss_lifetimes[block];
1760         ls->ss_lifetimes[block]=n;
1761
1762         n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
1763 }
1764
1765 #define lsra_from_stack(ls, s, block, instr) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
1766 #define lsra_pop_from_stack(ls, s, block, instr) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
1767 void _lsra_from_stack(lsradata *ls, stackptr s, int block, int instr, int store)
1768 {
1769         struct lifetime *n;
1770         /* ss_lifetimes[block]->local_ss have exactly one entry! */
1771         for (n=ls->ss_lifetimes[block]; (n!=NULL) && (n->local_ss->s!=s);n=n->next);
1772         if (n==NULL) {
1773                 _lsra_new_stack(ls, s, block, instr, store);
1774                 /* ist mit dem neuen joinen hinterher immer so, wenn ein Stackslot in einen BB "reinkommt" */
1775 /*              printf("type %i flags %i  varkind %i varnum %i regoff %i \n",s->type,s->flags ,s->varkind ,s->varnum ,s->regoff); */
1776 /*              panic("lsra_from_stack: Var on Stack not found"); */
1777         } else {
1778                 n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
1779         }
1780 }
1781
1782 void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr, int store)
1783 {
1784         struct lifetime *n;
1785
1786         /* Lifetime vom richtigen Type suchen */
1787         for (n=ls->locals_lifetimes[v_index]; (n!=NULL) && (n->type!=type);n=n->next);
1788
1789         if (n==NULL) {
1790 #ifdef LSRA_DEBUG
1791                 if (store != LSRA_STORE) printf("lsra_local_store: Read before write Local var: %i paramcount: ?\n", v_index);
1792 #endif
1793                 lsra_new_local(ls, v_index, type);
1794                 /* neue Lifetimes werden immer am Anfang der Liste eingehängt */
1795                 n=ls->locals_lifetimes[v_index];
1796         }
1797         /* add access at (block, instr) to intruction list */
1798         n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
1799 }
1800
1801 void lsra_new_local(lsradata *ls, s4 v_index, int type)
1802 {
1803         struct lifetime *n;
1804
1805         n=DNEW(struct lifetime);
1806         n->local_ss=NULL;
1807         n->i_list=NULL;
1808         n->v_index=v_index;
1809         n->type=type;
1810         n->savedvar = SAVEDVAR;
1811
1812         n->next=ls->locals_lifetimes[v_index];
1813         ls->locals_lifetimes[v_index]=n;
1814 }
1815
1816 #ifdef LSRA_DEBUG
1817 void lsra_dump_stack(stackptr s)
1818 {
1819         while (s!=NULL) {
1820                 printf("%p(R%3i N%3i K%3i T%3i F%3i) ",(void *)s,s->regoff, s->varnum, s->varkind, s->type, s->flags);
1821                 s=s->prev;
1822         }
1823         printf("\n");
1824 }
1825 #endif
1826
1827 void dup_mark( struct dup *dup,stackptr s)
1828 {
1829         struct stackslot *n;
1830         n = DNEW(struct stackslot);
1831         if (dup->ss == NULL) {
1832                 dup->ss = n;
1833                 n->next = NULL;
1834         } else {
1835                 n->next=dup->ss;
1836                 dup->ss=n;
1837         }
1838         n->s=s;
1839 }
1840
1841 void dup_next( struct dup *dup)
1842 {
1843         struct dup *n;
1844
1845         n = DNEW(struct dup);
1846         n->next = dup->next;
1847         dup->next=n;
1848         n->ss = dup->ss;
1849         dup->ss = NULL;
1850 }
1851
1852 void dup_join( struct lsradata *ls, struct dup *dup, int block)
1853 {
1854         struct dup *d;
1855         struct stackslot *ss, *ss1;
1856         bool pt; /* joins with passthrough lifetimes not yet possible! */
1857         struct lifetime *join_lt[3]; /* max three lifetimes to join */
1858         struct lifetime *join_lt_prev[3]; /* previous elements for unlinking */
1859         struct lifetime *lt, *lt_prev;
1860         int i, join_lt_top, join_to;
1861
1862         for (i=0; i<3; i++) join_lt[i]=join_lt_prev[i]=NULL;
1863         /* walk through dup structure and clean it up for next block */
1864         /* the first dup entry is alway empty for the next group to come*/
1865         for (d=dup->next; d!= NULL; d = dup->next=dup->next->next) {
1866                 pt=false;
1867                 join_lt_top=0;
1868                 for (ss=d->ss; (ss != NULL) && (!pt); ss = ss->next) {
1869                         for (lt = lt_prev = ls->ss_lifetimes[block]; lt != NULL ; lt_prev=lt, lt=lt->next) {
1870                                 for (ss1=lt->local_ss; (ss1!=NULL) && (ss1->s != ss->s); ss1 = ss1->next);
1871                                 if (ss1 != NULL) break; /* found */
1872                         }
1873                         if (lt == NULL) panic("dup_join Lifetimes not found\n");
1874                         pt=(lt->i_list->instr == -1); /* joins with passthrough lifetimes not yet possible! */
1875                         pt|=(lt->i_list->next == NULL); /* joins with "interface" Stackslots not yet possible! */
1876                         if (!pt) {
1877                                 join_lt_prev[join_lt_top]=lt_prev;
1878                                 join_lt[join_lt_top++]=lt;
1879                         }
1880                 }
1881                 if (!pt) { /* now join */
1882                         /* look if one element is the root of the list (joint_lt == join_lt_prev == ls->ss_lifetimes[block]) */
1883                         for (join_to=0; (join_to < join_lt_top) && (join_lt[join_to] != join_lt_prev[join_to]); join_to++);
1884                         if (join_to == join_lt_top) /* no root element in join array */
1885                                 join_to=0;
1886                         join_lt[join_to]->v_index = -1;
1887                         for (i=0; i<join_lt_top; i++) {
1888                                 if (i != join_to) {
1889                                         /* now join finally */
1890                                         lsra_merge_i_lists(join_lt[join_to], join_lt[i]);
1891                                         lsra_merge_local_ss(join_lt[join_to], join_lt[i]);
1892                                         join_lt[join_to]->savedvar|=(join_lt[i]->savedvar & SAVEDVAR);
1893                                         /* drop join_lt[i] from list */
1894                                         join_lt_prev[i]->next = join_lt[i]->next;
1895                                 }
1896                         }
1897                 }
1898         }
1899         dup->next = NULL;
1900 }
1901
1902 void lsra_scan_registers_canditates(methodinfo *m, lsradata *ls)
1903 {
1904         int i;
1905         int opcode;
1906         int iindex;
1907         int len;
1908         stackptr    src;
1909         stackptr    dst;
1910         instruction *iptr;
1911         stackptr in,out;
1912         int      id, od;
1913         int b_index;
1914         struct dup dup;
1915
1916         dup.ss=NULL;
1917         dup.next=NULL;
1918
1919         b_index=0;
1920         while (b_index < m->basicblockcount ) {
1921
1922                 if (m->basicblocks[b_index].flags >= BBREACHED) {
1923                         dst = m->basicblocks[b_index].instack;
1924                         if (dst != NULL) { /* create Lifetimes for pass-through Stackslots */
1925                                 in=m->basicblocks[b_index].instack;
1926                                 id=m->basicblocks[b_index].indepth;
1927                                 if (m->basicblocks[b_index].type != BBTYPE_STD) {
1928                                         /* Pay attention to the top Stackslot in BBTYPE_EXH and BBTYPE_SBR Basicblocks  */
1929                                         /* this is not a passthrough, but set from the "system" to the exception object or */
1930                                         /* the return adress -> just create a lifetime with a write at instr==0            */
1931                                         lsra_new_stack(ls, in, b_index, 0);
1932                                         in=in->prev;
1933                                         --id;
1934                                 }
1935
1936                                 out=m->basicblocks[b_index].outstack;
1937                                 od=m->basicblocks[b_index].outdepth;
1938
1939                                 /* ignore all in-stackslots not in outstack */
1940                                 for (;id>od; in=in->prev, --id);
1941                                 /* ignore all out-stackslots not in instack */
1942                                 for (;od>id; out=out->prev, --od);
1943                                 /* ignore all non equal stackslots from in and outstack */
1944                                 for (;in != out; in=in->prev, out=out->prev, --id);
1945                                 /* set up a lifetime for the rest: */
1946                                 /* stackslot adress equal, stackslot"number" equal */
1947                                 for (;in!=NULL; in=in->prev) {
1948                                         /* Make 2 entries -> one for the instack, one for the out stack */
1949                                         lsra_new_stack(ls, in, b_index, -1);
1950                                         lsra_new_stack(ls, in, b_index, -1);
1951                                 }
1952                         }
1953                         iptr = m->basicblocks[b_index].iinstr;
1954                         len = m->basicblocks[b_index].icount;
1955                         iindex=0;
1956
1957                         while (iindex<len)  {
1958                                 src = dst;
1959                                 dst = iptr->dst;
1960                                 opcode = iptr->opc;
1961 #ifdef LSRA_DEBUG
1962                                 printf("bb: %3i bcount: %3i iindex: %3i ilen: %3i opcode: %3i %s\n",b_index,m->basicblockcount,iindex,len,opcode,icmd_names[opcode]);
1963                                 lsra_dump_stack(src);
1964                                 lsra_dump_stack(dst);
1965 #endif
1966                                 switch (opcode) {
1967
1968                                 case ICMD_RET:
1969                                         lsra_usage_local(ls,iptr->op1,TYPE_ADR, b_index,iindex,LSRA_LOAD); /* local read (return adress) */
1970
1971                                         /* pop 0 push 0 */
1972
1973                                 case ICMD_NOP:
1974                                 case ICMD_ELSE_ICONST:
1975                                 case ICMD_CHECKEXCEPTION:
1976                                 case ICMD_CHECKASIZE:
1977                                 case ICMD_IINC:
1978                                 case ICMD_JSR:
1979                                 case ICMD_RETURN:
1980                                 case ICMD_GOTO:
1981                                 case ICMD_INLINE_START:
1982                                 case ICMD_INLINE_END:
1983                                         break;
1984
1985                                         /* pop 0 push 1 const */
1986                                         /* const->stack */
1987
1988                                 case ICMD_ICONST:
1989                                 case ICMD_LCONST:
1990                                 case ICMD_FCONST:
1991                                 case ICMD_DCONST:
1992                                 case ICMD_ACONST:
1993                                         /* new stack slot */
1994                                         lsra_new_stack(ls,dst,b_index,iindex); /* const->stack */
1995                                         break;
1996
1997                                         /* pop 0 push 1 load */
1998                                         /* local->stack */
1999
2000                                 case ICMD_ILOAD:
2001                                 case ICMD_LLOAD:
2002                                 case ICMD_FLOAD:
2003                                 case ICMD_DLOAD:
2004                                 case ICMD_ALOAD:
2005                                         lsra_usage_local(ls,iptr->op1,opcode-ICMD_ILOAD, b_index,iindex,LSRA_LOAD); /* local->value */
2006                                         lsra_new_stack(ls,dst,b_index,iindex); /* value->stack */
2007                                         /* ?Reference to local var?-> attention if local var is changed */
2008                                 break;
2009
2010                                         /* pop 2 push 1 */
2011                                     /* Stack(arrayref,index)->stack */
2012
2013                                 case ICMD_IALOAD:
2014                                 case ICMD_LALOAD:
2015                                 case ICMD_FALOAD:
2016                                 case ICMD_DALOAD:
2017                                 case ICMD_AALOAD:
2018
2019                                 case ICMD_BALOAD:
2020                                 case ICMD_CALOAD:
2021                                 case ICMD_SALOAD:
2022
2023                                         lsra_new_stack(ls,dst,b_index,iindex); /* arrayref[index]->stack */
2024                                         lsra_from_stack(ls, src,b_index,iindex); /* stack->index */
2025                                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack->arrayref */
2026                                         break;
2027
2028                                         /* pop 3 push 0 */
2029                                         /* stack(arrayref,index,value)->arrayref[index]=value */
2030
2031                                 case ICMD_IASTORE:
2032                                 case ICMD_LASTORE:
2033                                 case ICMD_FASTORE:
2034                                 case ICMD_DASTORE:
2035                                 case ICMD_AASTORE:
2036
2037                                 case ICMD_BASTORE:
2038                                 case ICMD_CASTORE:
2039                                 case ICMD_SASTORE:
2040
2041                                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2042                                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> index */
2043                                         lsra_from_stack(ls, src->prev->prev,b_index,iindex); /* stack -> arrayref */
2044                                         break;
2045
2046                                 case ICMD_POP: /* throw away a stackslot -> check if used anyway! */
2047                                         lsra_pop_from_stack(ls,src,b_index,iindex);
2048                                         break;
2049
2050                                         /* pop 1 push 0 store */
2051                                         /* stack -> local */
2052
2053                                 case ICMD_ISTORE:
2054                                 case ICMD_LSTORE:
2055                                 case ICMD_FSTORE:
2056                                 case ICMD_DSTORE:
2057                                 case ICMD_ASTORE:
2058                                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2059                                         lsra_usage_local(ls,iptr->op1,opcode-ICMD_ISTORE, b_index,iindex,LSRA_STORE); /* local->value */
2060                                         break;
2061
2062                                         /* pop 1 push 0 */
2063
2064                                 case ICMD_IRETURN:
2065                                 case ICMD_LRETURN:
2066                                 case ICMD_FRETURN:
2067                                 case ICMD_DRETURN:
2068                                 case ICMD_ARETURN: /*stack(value) -> [empty] */
2069
2070                                 case ICMD_ATHROW: /* stack(objref) -> undefined */
2071
2072                                 case ICMD_PUTSTATIC: /* stack(value) -> static_field */
2073                                         /* pop 1 push 0 branch */
2074
2075                                 case ICMD_IFNULL: /* stack(value) -> branch? */
2076                                 case ICMD_IFNONNULL:
2077
2078                                 case ICMD_IFEQ:
2079                                 case ICMD_IFNE:
2080                                 case ICMD_IFLT:
2081                                 case ICMD_IFGE:
2082                                 case ICMD_IFGT:
2083                                 case ICMD_IFLE:
2084
2085                                 case ICMD_IF_LEQ:
2086                                 case ICMD_IF_LNE:
2087                                 case ICMD_IF_LLT:
2088                                 case ICMD_IF_LGE:
2089                                 case ICMD_IF_LGT:
2090                                 case ICMD_IF_LLE:
2091
2092                                         /* pop 1 push 0 table branch */
2093
2094                                 case ICMD_TABLESWITCH:
2095                                 case ICMD_LOOKUPSWITCH:
2096
2097                                 case ICMD_NULLCHECKPOP: /****** ????? -1 -> stack *********/
2098                                 case ICMD_MONITORENTER:
2099                                 case ICMD_MONITOREXIT:
2100                                         lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
2101                                         break;
2102
2103                                         /* pop 2 push 0 */
2104
2105                                 case ICMD_POP2: /* throw away 2 stackslots -> check if used anyway! */
2106                                         lsra_pop_from_stack(ls,src,b_index,iindex);
2107                                         lsra_pop_from_stack(ls,src->prev,b_index,iindex);
2108                                         break;
2109
2110                                         /* pop 2 push 0 branch */
2111
2112                                 case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
2113                                 case ICMD_IF_ICMPNE:
2114                                 case ICMD_IF_ICMPLT:
2115                                 case ICMD_IF_ICMPGE:
2116                                 case ICMD_IF_ICMPGT:
2117                                 case ICMD_IF_ICMPLE:
2118
2119                                 case ICMD_IF_LCMPEQ:
2120                                 case ICMD_IF_LCMPNE:
2121                                 case ICMD_IF_LCMPLT:
2122                                 case ICMD_IF_LCMPGE:
2123                                 case ICMD_IF_LCMPGT:
2124                                 case ICMD_IF_LCMPLE:
2125
2126                                 case ICMD_IF_ACMPEQ:
2127                                 case ICMD_IF_ACMPNE:
2128
2129                                         /* pop 2 push 0 */
2130
2131                                 case ICMD_PUTFIELD: /* stack(objref,value) -> objref->method=value */
2132
2133                                 case ICMD_IASTORECONST:
2134                                 case ICMD_LASTORECONST:
2135                                 case ICMD_AASTORECONST:
2136                                 case ICMD_BASTORECONST:
2137                                 case ICMD_CASTORECONST:
2138                                 case ICMD_SASTORECONST:
2139                                         lsra_from_stack(ls, src,b_index,iindex);           /* stack -> value*/
2140                                         lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> objref*/
2141                                         break;
2142
2143                                         /* pop 0 push 1 dup */
2144                                         /* merge dupped vars??? */
2145                                 case ICMD_DUP:
2146                                         /* lsra_from_stack(ls, src,b_index,iindex);*/ /* inc usage_count! */
2147                                         lsra_new_stack(ls,dst,b_index,iindex);
2148                                         dup_mark(&dup, src);
2149                                         dup_mark(&dup, dst);
2150                                         dup_next(&dup);
2151                                         break;
2152
2153                                         /* pop 0 push 2 dup */
2154
2155                                 case ICMD_DUP2:
2156                                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2157                                         lsra_new_stack(ls,dst,b_index,iindex);
2158                                         lsra_from_stack(ls, src,b_index,iindex); /* or inc usage_count! */
2159                                         lsra_from_stack(ls, src->prev,b_index,iindex); /* inc usage_count! */
2160
2161                                         dup_mark(&dup, src);
2162                                         dup_mark(&dup, dst);
2163                                         dup_mark(&dup, dst->prev->prev);
2164                                         dup_next(&dup);
2165                                         dup_mark(&dup, src->prev);
2166                                         dup_mark(&dup, dst->prev);
2167                                         dup_mark(&dup, dst->prev->prev->prev);
2168                                         dup_next(&dup);
2169                                         break;
2170
2171                                         /* pop 2 push 3 dup */
2172
2173                                 case ICMD_DUP_X1:
2174                                         lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
2175                                         lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2176                                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2177                                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2178                                         lsra_new_stack(ls,dst,b_index,iindex);
2179                                         dup_mark(&dup, src);
2180                                         dup_mark(&dup, dst);
2181                                         dup_mark(&dup, dst->prev->prev);
2182                                         dup_next(&dup);
2183                                         dup_mark(&dup, src->prev);
2184                                         dup_mark(&dup, dst->prev);
2185                                         dup_next(&dup);
2186                                         break;
2187
2188                                         /* pop 3 push 4 dup */
2189
2190                                 case ICMD_DUP_X2:
2191                                         lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
2192                                         lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2193                                         lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2194                                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2195                                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2196                                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2197                                         lsra_new_stack(ls,dst,b_index,iindex);
2198                                         dup_mark(&dup, src);
2199                                         dup_mark(&dup, dst);
2200                                         dup_mark(&dup, dst->prev->prev->prev);
2201                                         dup_next(&dup);
2202                                         dup_mark(&dup, src->prev);
2203                                         dup_mark(&dup, dst->prev);
2204                                         dup_next(&dup);
2205                                         dup_mark(&dup, src->prev->prev);
2206                                         dup_mark(&dup, dst->prev->prev);
2207                                         dup_next(&dup);
2208                                         break;
2209
2210                                         /* pop 3 push 5 dup */
2211
2212                                 case ICMD_DUP2_X1:
2213                                         lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
2214                                         lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2215                                         lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2216                                         lsra_new_stack(ls,dst->prev->prev->prev->prev,b_index,iindex);
2217                                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2218                                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2219                                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2220                                         lsra_new_stack(ls,dst,b_index,iindex);
2221                                         dup_mark(&dup, src);
2222                                         dup_mark(&dup, dst);
2223                                         dup_mark(&dup, dst->prev->prev->prev);
2224                                         dup_next(&dup);
2225                                         dup_mark(&dup, src->prev);
2226                                         dup_mark(&dup, dst->prev);
2227                                         dup_mark(&dup, dst->prev->prev->prev->prev);
2228                                         dup_next(&dup);
2229                                         dup_mark(&dup, src->prev->prev);
2230                                         dup_mark(&dup, dst->prev->prev);
2231                                         dup_next(&dup);
2232                                         break;
2233
2234                                         /* pop 4 push 6 dup */
2235
2236                                 case ICMD_DUP2_X2:
2237                                         lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
2238                                         lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2239                                         lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2240                                         lsra_from_stack(ls, src->prev->prev->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2241                                         lsra_new_stack(ls,dst->prev->prev->prev->prev->prev,b_index,iindex);
2242                                         lsra_new_stack(ls,dst->prev->prev->prev->prev,b_index,iindex);
2243                                         lsra_new_stack(ls,dst->prev->prev->prev,b_index,iindex);
2244                                         lsra_new_stack(ls,dst->prev->prev,b_index,iindex);
2245                                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2246                                         lsra_new_stack(ls,dst,b_index,iindex);
2247                                         dup_mark(&dup, src);
2248                                         dup_mark(&dup, dst);
2249                                         dup_mark(&dup, dst->prev->prev->prev->prev);
2250                                         dup_next(&dup);
2251                                         dup_mark(&dup, src->prev);
2252                                         dup_mark(&dup, dst->prev);
2253                                         dup_mark(&dup, dst->prev->prev->prev->prev->prev);
2254                                         dup_next(&dup);
2255                                         dup_mark(&dup, src->prev->prev);
2256                                         dup_mark(&dup, dst->prev->prev);
2257                                         dup_next(&dup);
2258                                         dup_mark(&dup, src->prev->prev->prev);
2259                                         dup_mark(&dup, dst->prev->prev->prev);
2260                                         dup_next(&dup);
2261                                         break;
2262
2263                                         /* pop 2 push 2 swap */
2264
2265                                 case ICMD_SWAP:
2266                                         lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
2267                                         lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work!  inc usage_count! */
2268                                         lsra_new_stack(ls,dst->prev,b_index,iindex);
2269                                         lsra_new_stack(ls,dst,b_index,iindex);
2270                                         dup_mark(&dup, src);
2271                                         dup_mark(&dup, dst->prev);
2272                                         dup_next(&dup);
2273                                         dup_mark(&dup, src->prev);
2274                                         dup_mark(&dup, dst);
2275                                         dup_next(&dup);
2276                                         break;
2277
2278                                         /* pop 2 push 1 */
2279
2280                                 case ICMD_IADD:
2281                                 case ICMD_ISUB:
2282                                 case ICMD_IMUL:
2283                                 case ICMD_IDIV:
2284                                 case ICMD_IREM:
2285
2286                                 case ICMD_ISHL:
2287                                 case ICMD_ISHR:
2288                                 case ICMD_IUSHR:
2289                                 case ICMD_IAND:
2290                                 case ICMD_IOR:
2291                                 case ICMD_IXOR:
2292
2293                                 case ICMD_LADD:
2294                                 case ICMD_LSUB:
2295                                 case ICMD_LMUL:
2296                                 case ICMD_LDIV:
2297                                 case ICMD_LREM:
2298
2299                                 case ICMD_LOR:
2300                                 case ICMD_LAND:
2301                                 case ICMD_LXOR:
2302
2303                                 case ICMD_LSHL:
2304                                 case ICMD_LSHR:
2305                                 case ICMD_LUSHR:
2306
2307                                 case ICMD_FADD:
2308                                 case ICMD_FSUB:
2309                                 case ICMD_FMUL:
2310                                 case ICMD_FDIV:
2311                                 case ICMD_FREM:
2312
2313                                 case ICMD_DADD:
2314                                 case ICMD_DSUB:
2315                                 case ICMD_DMUL:
2316                                 case ICMD_DDIV:
2317                                 case ICMD_DREM:
2318
2319                                 case ICMD_LCMP:
2320                                 case ICMD_FCMPL:
2321                                 case ICMD_FCMPG:
2322                                 case ICMD_DCMPL:
2323                                 case ICMD_DCMPG:
2324                                         lsra_from_stack(ls, src,b_index,iindex);
2325                                         lsra_from_stack(ls, src->prev,b_index,iindex);
2326                                         lsra_new_stack(ls,dst,b_index,iindex);
2327                                         break;
2328
2329                                         /* pop 1 push 1 */
2330
2331                                 case ICMD_IADDCONST:
2332                                 case ICMD_ISUBCONST:
2333                                 case ICMD_IMULCONST:
2334                                 case ICMD_IDIVPOW2:
2335                                 case ICMD_IREMPOW2:
2336                                 case ICMD_IANDCONST:
2337                                 case ICMD_IORCONST:
2338                                 case ICMD_IXORCONST:
2339                                 case ICMD_ISHLCONST:
2340                                 case ICMD_ISHRCONST:
2341                                 case ICMD_IUSHRCONST:
2342
2343                                 case ICMD_LADDCONST:
2344                                 case ICMD_LSUBCONST:
2345                                 case ICMD_LMULCONST:
2346                                 case ICMD_LDIVPOW2:
2347                                 case ICMD_LREMPOW2:
2348                                 case ICMD_LANDCONST:
2349                                 case ICMD_LORCONST:
2350                                 case ICMD_LXORCONST:
2351                                 case ICMD_LSHLCONST:
2352                                 case ICMD_LSHRCONST:
2353                                 case ICMD_LUSHRCONST:
2354
2355                                 case ICMD_IFEQ_ICONST:
2356                                 case ICMD_IFNE_ICONST:
2357                                 case ICMD_IFLT_ICONST:
2358                                 case ICMD_IFGE_ICONST:
2359                                 case ICMD_IFGT_ICONST:
2360                                 case ICMD_IFLE_ICONST:
2361
2362                                 case ICMD_INEG:
2363                                 case ICMD_INT2BYTE:
2364                                 case ICMD_INT2CHAR:
2365                                 case ICMD_INT2SHORT:
2366                                 case ICMD_LNEG:
2367                                 case ICMD_FNEG:
2368                                 case ICMD_DNEG:
2369
2370                                 case ICMD_I2L:
2371                                 case ICMD_I2F:
2372                                 case ICMD_I2D:
2373                                 case ICMD_L2I:
2374                                 case ICMD_L2F:
2375                                 case ICMD_L2D:
2376                                 case ICMD_F2I:
2377                                 case ICMD_F2L:
2378                                 case ICMD_F2D:
2379                                 case ICMD_D2I:
2380                                 case ICMD_D2L:
2381                                 case ICMD_D2F:
2382
2383                                 case ICMD_CHECKCAST:
2384
2385                                 case ICMD_ARRAYLENGTH:
2386                                 case ICMD_INSTANCEOF:
2387
2388                                 case ICMD_NEWARRAY:
2389                                 case ICMD_ANEWARRAY:
2390
2391                                 case ICMD_GETFIELD:
2392                                         lsra_from_stack(ls, src,b_index,iindex);
2393                                         lsra_new_stack(ls,dst,b_index,iindex);
2394                                         break;
2395
2396                                         /* pop 0 push 1 */
2397
2398                                 case ICMD_GETSTATIC:
2399
2400                                 case ICMD_NEW:
2401
2402                                         lsra_new_stack(ls,dst,b_index,iindex);
2403                                         break;
2404
2405                                         /* pop many push any */
2406                                 case ICMD_INVOKEVIRTUAL:
2407                                 case ICMD_INVOKESPECIAL:
2408                                 case ICMD_INVOKESTATIC:
2409                                 case ICMD_INVOKEINTERFACE:
2410                                         {
2411                                                 i = iptr->op1;
2412                                                 while (--i >= 0) {
2413                                                         lsra_from_stack(ls, src,b_index,iindex);
2414                                                         src = src->prev;
2415                                                 }
2416                                                 if (((methodinfo*)iptr->val.a)->returntype != TYPE_VOID) {
2417                                                         lsra_new_stack(ls,dst,b_index,iindex);
2418                                                 }
2419                                                 break;
2420                                         }
2421
2422                                 case ICMD_BUILTIN3:
2423                                         lsra_from_stack(ls, src,b_index,iindex);
2424                                         src = src->prev;
2425                                 case ICMD_BUILTIN2:
2426                                         lsra_from_stack(ls, src,b_index,iindex);
2427                                         src = src->prev;
2428                                 case ICMD_BUILTIN1:
2429                                         lsra_from_stack(ls, src,b_index,iindex);
2430                                         src = src->prev; /* ??????????? */
2431                                         if (iptr->op1 != TYPE_VOID)
2432                                                 lsra_new_stack(ls,dst,b_index,iindex);
2433                                         break;
2434
2435                                 case ICMD_MULTIANEWARRAY:
2436                                         i = iptr->op1;
2437                                         while (--i >= 0) {
2438                                                 lsra_from_stack(ls, src,b_index,iindex);
2439                                                 src = src->prev;
2440                                         }
2441                                         lsra_new_stack(ls,dst,b_index,iindex);
2442                                         break;
2443
2444                                 default:
2445                                         printf("ICMD %d at %d\n", iptr->opc, (int)(iptr - m->instructions));
2446                                         panic("Missing ICMD code during register allocation");
2447                                 } /* switch */
2448                                 iptr++;
2449                                 iindex++;
2450                         } /* while instructions */
2451                 } /* if */
2452
2453                 dup_join(ls, &dup, b_index);
2454
2455                 b_index++;
2456         } /* while blocks */
2457 }
2458
2459 /*
2460  * These are local overrides for various environment variables in Emacs.
2461  * Please do not remove this and leave it at the end of the file, where
2462  * Emacs will automagically detect them.
2463  * ---------------------------------------------------------------------
2464  * Local variables:
2465  * mode: c
2466  * indent-tabs-mode: t
2467  * c-basic-offset: 4
2468  * tab-width: 4
2469  * End:
2470  */