src/vm/jit/lsra.inc

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