src/vm/jit/lsra.inc

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