src/vm/jit/allocator/lsra.c

   1 /* src/vm/jit/allocator/lsra.c - linear scan register allocator
   2
   3    Copyright (C) 2005, 2006, 2007, 2008
   4    CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
   5
   6    This file is part of CACAO.
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2, or (at
  11    your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23 */
  24
  25
  26 #include "config.h"
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include <assert.h>
  31 #include <limits.h>
  32
  33 #include "arch.h"
  34 #include "md-abi.h"
  35
  36 #include "vm/types.h"
  37
  38 #include "mm/memory.h"
  39 #include "toolbox/logging.h"
  40 #include "vm/builtin.h"
  41 #include "vm/exceptions.h"
  42 #include "vm/resolve.h"
  43 #include "vm/options.h"
  44 #include "vm/statistics.h"
  45 #include "vm/stringlocal.h"
  46 #include "vm/jit/abi.h"
  47 #include "vm/jit/reg.h"
  48 #include "vm/jit/allocator/liveness.h"
  49 #include "vm/jit/allocator/lsra.h"
  50
  51 #ifdef USAGE_COUNT
  52 extern char **prof_m_names;
  53 extern u4   **prof_bb_freq;
  54 extern int  prof_size;
  55 #endif
  56
  57 /* function prototypes */
  58 void lsra_init(jitdata *);
  59 void lsra_setup(jitdata *);
  60 void lsra_main(jitdata *);
  61
  62 void lsra_reg_setup(jitdata *, struct lsra_register *, struct lsra_register * );
  63 void lsra_calc_lifetime_length(jitdata *);
  64 void _lsra_main( jitdata *, int *, int, struct lsra_register *, int *);
  65 void lsra_expire_old_intervalls(jitdata *, struct lifetime *,
  66                                                                 struct lsra_register *);
  67 void spill_at_intervall(jitdata *, struct lifetime *);
  68 void lsra_add_active(struct lifetime *, struct lifetime **, int *);
  69 void _lsra_expire_old_intervalls(jitdata *, struct lifetime *,
  70                                                                  struct lsra_register *, struct lifetime **,
  71                                                                  int *);
  72 void _spill_at_intervall(struct lifetime *, struct lifetime **, int *);
  73
  74 void lsra_alloc(jitdata *, int *, int, int *);
  75 int lsra_getmem(struct lifetime *, struct freemem *, int *);
  76 struct freemem *lsra_getnewmem(int *);
  77 void lsra_setflags(int *, int);
  78
  79 #ifdef LSRA_DEBUG_VERBOSE
  80 void lsra_dump_stack(stackelement_t* );
  81 void print_lifetimes(jitdata *, int *, int);
  82 #endif
  83
  84 #if !defined(LV)
  85 void lsra_scan_registers_canditates(jitdata *, int);
  86 void lsra_join_lifetimes(jitdata *, int);
  87
  88 void _lsra_new_stack( lsradata *, stackelement_t* , int , int, int);
  89 void _lsra_from_stack(lsradata *, stackelement_t* , int , int, int);
  90 void lsra_add_ss(struct lifetime *, stackelement_t* );
  91 void lsra_usage_local(lsradata *, s4 , int , int , int , int );
  92 #endif
  93
  94
  95
  96 bool lsra(jitdata *jd)
  97 {
  98 #if defined(ENABLE_STATISTICS)
  99         lsradata *ls;
 100         int locals_start;
 101         int i,j;
 102 #endif
 103 #if defined(LSRA_DEBUG_CHECK)
 104         methodinfo   *m;
 105         int      b_index;
 106         stackelement_t* in,out;
 107         int      ind, outd;
 108 #endif
 109
 110 #if defined(LSRA_DEBUG_CHECK)
 111         m  = jd->m;
 112         b_index = 0;
 113         while (b_index < m->basicblockcount ) {
 114
 115                 if (m->basicblocks[b_index].flags >= BBREACHED) {
 116
 117                         in=m->basicblocks[b_index].instack;
 118                         ind=m->basicblocks[b_index].indepth;
 119                         for (;ind != 0;in=in->prev, ind--) {
 120                                                         /* ARGVAR or LOCALVAR in instack is ok*/
 121 #if 0
 122                                 if (in->varkind == ARGVAR) printf("ARGVAR in instack: \n");
 123                                 if (in->varkind == LOCALVAR) printf("LOCALVAR in instack\n");
 124 #endif
 125                         }
 126                         out=m->basicblocks[b_index].outstack;
 127                         outd=m->basicblocks[b_index].outdepth;
 128                         for (;outd != 0;out=out->prev, outd--) {
 129                                 if (out->varkind == ARGVAR)
 130                                         { log_text("ARGVAR in outstack\n"); assert(0); }
 131                                 if (out->varkind == LOCALVAR)
 132                                         { log_text("LOCALVAR in outstack\n"); assert(0); }
 133                         }
 134                 }
 135                         b_index++;
 136         }
 137 #endif
 138
 139         jd->ls = DNEW(lsradata);
 140         lsra_init(jd);
 141         lsra_setup(jd);
 142
 143 #if defined(ENABLE_STATISTICS)
 144         /* find conflicts between locals for statistics */
 145         if (opt_stat) {
 146                 ls = jd->ls;
 147                 /* local Variable Lifetimes are at the end of the lifetime array and  */
 148                 /* have v_index >= 0 */
 149                 for (locals_start = ls->lifetimecount-1; (locals_start >=0) &&
 150                         (ls->lifetime[ls->lt_used[locals_start]].v_index >= 0);
 151                          locals_start--);
 152                 for (i=locals_start + 1; i < ls->lifetimecount; i++)
 153                         for (j=i+1; j < ls->lifetimecount; j++)
 154                                 if ( !((ls->lifetime[ls->lt_used[i]].i_end
 155                                            < ls->lifetime[ls->lt_used[j]].i_start)
 156                                         || (ls->lifetime[ls->lt_used[j]].i_end <
 157                                            ls->lifetime[ls->lt_used[i]].i_start)) )
 158                                         count_locals_conflicts += 2;
 159          }
 160 #endif
 161         /* Run LSRA */
 162         lsra_main(jd);
 163
 164         /* everything's ok */
 165
 166         return true;
 167 }
 168
 169 /* sort Basic Blocks using Depth First Search in reverse post order in */
 170 /* ls->sorted.  */
 171 void lsra_DFS(jitdata *jd) {
 172         int *stack;
 173         int *visited;
 174         int stack_top;
 175         bool not_finished;
 176         int i,p;
 177     struct _list *succ;
 178
 179         methodinfo *m;
 180         lsradata   *ls;
 181
 182         m  = jd->m;
 183         ls = jd->ls;
 184
 185         stack = DMNEW( int, m->basicblockcount + 1);
 186         visited = (int *)DMNEW( int, m->basicblockcount + 1);
 187         for (i = 0; i <= m->basicblockcount; i++) {
 188                 visited[i] = 0;
 189                 ls->sorted[i]=-1;
 190                 ls->sorted_rev[i]=-1;
 191         }
 192
 193     stack[0] = 0; /* start with Block 0 */
 194         stack_top = 1;
 195         visited[0] = ls->num_pred[0]; /* Start Block is handled right and can be */
 196                                       /* put in sorted */
 197         p = 0;
 198         not_finished = true;
 199         while (not_finished) {
 200                 while (stack_top != 0) {
 201                         stack_top--;
 202                         i = stack[stack_top];
 203                         ls->sorted[p]=i;
 204                         p++; /*--;*/
 205                         for (succ = ls->succ[i]; succ != NULL; succ = succ->next) {
 206                                 visited[succ->value]++;
 207                                 if (visited[succ->value] == ls->num_pred[succ->value]) {
 208                                         /* push the node on the stack, only if all ancestors have */
 209                                         /* been visited */
 210                                         stack[stack_top] = succ->value;
 211                                         stack_top++;
 212                                 }
 213                         }
 214                 }
 215                 not_finished = false;
 216                 for (i=1; i <= m->basicblockcount; i++) {
 217                         /* search for visited blocks, which have not reached the num_pred */
 218                         /* and put them on the stack -> happens with backedges */
 219                         if ((visited[i] != 0) && (visited[i] < ls->num_pred[i])) {
 220                                 stack[stack_top] = i;
 221                                 stack_top++;
 222                                 visited[i] = ls->num_pred[i];
 223                                 not_finished=true;
 224                                 break;
 225                         }
 226                 }
 227         }
 228 }
 229
 230 void lsra_get_backedges_(lsradata *ls, int basicblockcount) {
 231         struct _list *s;
 232         struct _backedge *n;
 233         struct _backedge *_backedges;
 234         int    i;
 235
 236
 237         _backedges = NULL;
 238
 239         /* now look for backedges */
 240         ls->backedge_count = 0;
 241         for(i=0; i < basicblockcount; i++) {
 242                 if (ls->sorted[i] != -1)
 243                         for(s=ls->succ[ls->sorted[i]]; s != NULL; s=s->next) {
 244                                 if (i >= ls->sorted_rev[s->value]) {
 245                                         n=DNEW(struct _backedge);
 246                                         n->start = max(i, ls->sorted_rev[s->value]);
 247                                         n->end = min(i, ls->sorted_rev[s->value]);
 248                                         n->next = _backedges;
 249                                         _backedges = n;
 250                                         ls->backedge_count++;
 251                                 }
 252                         }
 253         }
 254         /* put _backedges in ls->backedge array */
 255         ls->backedge = DMNEW(struct _backedge *, ls->backedge_count);
 256         for (n=_backedges, i=0; n != NULL; n=n->next, i++) {
 257                 ls->backedge[i] = n;
 258                 ls->backedge[i]->nesting = 1;
 259         }
 260 }
 261
 262 void lsra_get_nesting(jitdata *jd) {
 263         methodinfo *m;
 264         lsradata   *ls;
 265         int    i,j, end;
 266         struct _backedge *n;
 267
 268         m = jd->m;
 269         ls = jd->ls;
 270
 271         for (i=0; i <= m->basicblockcount; i++)
 272                 if (ls->sorted[i] != -1)
 273                         ls->sorted_rev[ls->sorted[i]]=i;
 274
 275         lsra_get_backedges_(ls, m->basicblockcount + 1);
 276         /* - sort backedge by increasing end: */
 277         for (i=0; i < ls->backedge_count; i++)
 278                 for (j=i+1; j < ls->backedge_count; j++)
 279                         if ((ls->backedge[i]->end > ls->backedge[j]->end) ||     /* -> swap */
 280                                   ((ls->backedge[i]->end == ls->backedge[j]->end) &&
 281                                    (ls->backedge[i]->start > ls->backedge[j]->start) )) {
 282                                 n=ls->backedge[i];
 283                                 ls->backedge[i]=ls->backedge[j];
 284                                 ls->backedge[j]=n;
 285                         }
 286
 287         /* create ls->nesting */
 288         /* look for nesting depth (overlapping backedges*/
 289         for (i=0; i < ls->backedge_count - 1; i++) {
 290                 for (j = i + 1; (j < ls->backedge_count) &&
 291                                  (ls->backedge[i]->start >= ls->backedge[j]->end); j++)
 292                         ls->backedge[j]->nesting += ls->backedge[i]->nesting;
 293         }
 294
 295     i = 0;
 296     j = 0;
 297         while ( (i < m->basicblockcount + 1)  ) {
 298                 if (j < ls->backedge_count) {
 299                         while ( i < ls->backedge[j]->end ) {
 300                                 ls->nesting[i] = 0;
 301                                 i++;
 302                         }
 303                         if ( (j+1) < ls->backedge_count)
 304                                 end = min(ls->backedge[j]->start, ls->backedge[j+1]->end - 1);
 305                         else
 306                                 end = ls->backedge[j]->start;
 307                         while (i <= end) {
 308                                 ls->nesting[i] = ls->backedge[j]->nesting;
 309                                 i++;
 310                         }
 311                         j++;
 312                 } else {
 313                         ls->nesting[i] = 0;
 314                         i++;
 315                 }
 316         }
 317
 318 #ifdef LSRA_DEBUG_VERBOSE
 319         if (compileverbose) {
 320         printf("sorted: \n");
 321         for (i=0; i < ls->backedge_count; i++)
 322                 printf("Backedge: %i - %i, %i - %i\n", ls->sorted[ls->backedge[i]->start], ls->sorted[ls->backedge[i]->end], ls->backedge[i]->start, ls->backedge[i]->end);
 323         printf("Nesting Level \n");
 324         for (i=0; i<m->basicblockcount; i++) printf(" %3li", ls->nesting[i]);
 325         printf("\n");
 326         }
 327 #endif
 328         for (i=0; i <= m->basicblockcount; i++) {
 329                 ls->sorted_rev[i] = -1;
 330                 ls->nesting[i] = 1+ls->nesting[i]*ls->nesting[i]*10;
 331         }
 332 }
 333
 334 void lsra_get_backedges(jitdata *jd) {
 335         methodinfo *m;
 336         lsradata   *ls;
 337         struct _list **next;
 338         struct _backedge *n;
 339         int    i,j;
 340         bool   merged;
 341
 342         m  = jd->m;
 343         ls = jd->ls;
 344
 345         /* first remove artificial end basicblock from ls->sorted, succ and pred */
 346     j=-1;
 347         for (i=0; i < m->basicblockcount; i++) {
 348                 for (next=&(ls->succ[i]); *next != NULL; next=&((*next)->next)) {
 349                         if ( (*next)->value == m->basicblockcount ) {
 350                                 /* artificial end bb found */
 351                                 *next = (*next)->next;
 352                                 if (*next == NULL) break;
 353                         }
 354                 }
 355                 for (next=&(ls->pred[i]); *next != NULL; next=&((*next)->next)) {
 356                         if ( (*next)->value == m->basicblockcount ) {
 357                                 /* artificial end bb found */
 358                                 *next = (*next)->next;
 359                                 if (*next == NULL) break;
 360                         }
 361                 }
 362                 if (j==-1)
 363                         if (ls->sorted[i] == m->basicblockcount) j=i;
 364         }
 365
 366         /* if an artificial end block was removed -> change ls->sorted accordingly*/
 367         if (j!=-1)
 368                 for (i=j+1; i <= m->basicblockcount; i++) {
 369                         ls->sorted[i-1] = ls->sorted[i];
 370                         ls->nesting[i-1] = ls->nesting[i];
 371                 }
 372
 373         for (i=0; i < m->basicblockcount; i++)
 374                 if (ls->sorted[i] != -1)
 375                         ls->sorted_rev[ls->sorted[i]]=i;
 376
 377         lsra_get_backedges_(ls, m->basicblockcount);
 378
 379         /* - sort backedge by increasing start */
 380         for (i=0; i < ls->backedge_count; i++)
 381                 for (j=i+1; j < ls->backedge_count; j++)
 382                         if (ls->backedge[i]->start > ls->backedge[j]->start) {
 383                                 /* -> swap */
 384                                 n = ls->backedge[i];
 385                                 ls->backedge[i] = ls->backedge[j];
 386                                 ls->backedge[j] = n;
 387                         }
 388
 389 #ifdef LSRA_DEBUG_VERBOSE
 390         if (compileverbose) {
 391                 printf("sorted: \n");
 392                 for (i=0; i < ls->backedge_count; i++)
 393                         printf("Backedge: %i - %i, %i - %i\n",
 394                                    ls->sorted[ls->backedge[i]->start],
 395                                    ls->sorted[ls->backedge[i]->end], ls->backedge[i]->start,
 396                                    ls->backedge[i]->end);
 397                 printf("Nesting Level \n");
 398                 for (i=0; i<m->basicblockcount; i++) printf(" %3li", ls->nesting[i]);
 399                 printf("\n");
 400         }
 401 #endif
 402
 403         merged = true;
 404         /* - merge overlapping backedges */
 405         while (merged) {
 406                 merged = false;
 407                 for (i=0; i < ls->backedge_count-1; i++) {
 408                         if (ls->backedge[i] != NULL) {
 409                                 for (j = i + 1; (j < ls->backedge_count) && (ls->backedge[j] == NULL); j++ );
 410                                 if (j != ls->backedge_count) {
 411                                         if (ls->backedge[i]->start >= ls->backedge[j]->end) {
 412                                                 merged = true;
 413                                                 /* overlapping -> merge */
 414                                                 ls->backedge[j]->end = min (ls->backedge[j]->end,
 415                                                                                                     ls->backedge[i]->end);
 416                                                 ls->backedge[i] = NULL;
 417                                         }
 418                                 }
 419                         }
 420                 }
 421         }
 422 #ifdef LSRA_DEBUG_VERBOSE
 423         if (compileverbose) {
 424                 printf("merged: \n");
 425                 for (i = 0; i < ls->backedge_count; i++)
 426                         if (ls->backedge[i] != NULL)
 427                                 printf("Backedge: %i - %i, %i - %i\n",
 428                                            ls->sorted[ls->backedge[i]->start],
 429                                            ls->sorted[ls->backedge[i]->end],
 430                                            ls->backedge[i]->start, ls->backedge[i]->end);
 431         }
 432 #endif
 433         /* - remove backedge[] == NULL from array */
 434
 435         for (j = ls->backedge_count - 1; ((j>=0) && (ls->backedge[j] == NULL));
 436                  j--);
 437         i=j;
 438         while (i >= 0) {
 439                 if (ls->backedge[i] == NULL) { /* swap backedge[i] and backedge[j]*/
 440                         n=ls->backedge[j];
 441                         ls->backedge[j] = ls->backedge[i];
 442                         ls->backedge[i] = n;
 443                         i--;
 444                         j--;
 445                         ls->backedge_count--;
 446                 } else i--;
 447         }
 448 #ifdef LSRA_DEBUG_VERBOSE
 449         if (compileverbose) {
 450                 printf("ready: \n");
 451                 for (i=0; i < ls->backedge_count; i++)
 452                         printf("Backedge: %i - %i, %i - %i\n",
 453                                    ls->sorted[ls->backedge[i]->start],
 454                                    ls->sorted[ls->backedge[i]->end],ls->backedge[i]->start,
 455                                    ls->backedge[i]->end);
 456         }
 457 #endif
 458 }
 459
 460 void lsra_add_cfg(jitdata *jd, int from, int to) {
 461         struct _list *n;
 462         methodinfo *m;
 463         lsradata   *ls;
 464
 465         m  = jd->m;
 466         ls = jd->ls;
 467
 468         /* ignore Empty, Deleted,... Basic Blocks as target */
 469         /* TODO: Setup BasicBlock array before to avoid this */
 470         /*       best together with using the basicblock list, so lsra works */
 471         /*       with opt_loops, too */
 472         for (;(to < m->basicblockcount) && (m->basicblocks[to].flags < BBREACHED); to++);
 473
 474         for (n=ls->succ[from]; (n!= NULL) && (n->value != to); n=n->next);
 475         if (n != NULL) return; /* edge from->to already existing */
 476
 477         n=DNEW(struct _list);
 478
 479         n->value=to;
 480         n->next=ls->succ[from];
 481         ls->succ[from]=n;
 482
 483         n=DNEW(struct _list);
 484         n->value=from;
 485         n->next=ls->pred[to];
 486         ls->pred[to]=n;
 487         ls->num_pred[to]++;
 488 }
 489
 490 /* add Edges from guarded Areas to Exception handlers in the CFG */
 491 void lsra_add_exceptions(jitdata *jd) {
 492         methodinfo  *m;
 493         lsradata    *ls;
 494         int i;
 495         exceptiontable *ex;
 496
 497
 498         m  = jd->m;
 499         ls = jd->ls;
 500
 501         ex = jd->exceptiontable;
 502
 503         /* add cfg edges from all bb of a try block to the start of the according */
 504         /* exception handler to ensure the right order after depthfirst search    */
 505
 506 #ifdef LSRA_DEBUG_VERBOSE
 507         if (compileverbose)
 508                 printf("ExTable(%i): ", jd->exceptiontablelength);
 509 #endif
 510
 511         for (; ex != NULL; ex = ex->down) {
 512
 513 #ifdef LSRA_DEBUG_VERBOSE
 514         if (compileverbose) {
 515                 printf("[%i-%i]->%i ",ex->start->nr, ex->end->nr,
 516                            ex->handler->nr);
 517                 if (ex->handler->nr >= m->basicblockcount) {
 518                         log_text("Exceptionhandler Basicblocknummer invalid\n");
 519                         abort();
 520                 }
 521                 if (m->basicblocks[ex->handler->nr].flags < BBREACHED) {
 522                         log_text("Exceptionhandler Basicblocknummer not reachable\n");
 523                         abort();
 524                 }
 525                 if (ex->start->nr > ex->end->nr) {
 526                         log_text("Guarded Area starts after its end\n");
 527                         abort();
 528                 }
 529         }
 530 #endif
 531                 /* loop all valid Basic Blocks of the guarded area and add CFG edges  */
 532                 /* to the appropriate handler */
 533                 for (i=ex->start->nr; (i <= ex->end->nr) &&
 534                                  (i < m->basicblockcount); i++)
 535                         if (m->basicblocks[i].flags >= BBREACHED)
 536                                 lsra_add_cfg(jd, i, ex->handler->nr);
 537         }
 538 #ifdef LSRA_DEBUG_VERBOSE
 539         if (compileverbose) {
 540                 printf("\n");
 541         }
 542 #endif
 543 }
 544
 545 void lsra_add_jsr(jitdata *jd, int from, int to) {
 546         methodinfo *m;
 547         lsradata   *ls;
 548         struct _sbr *sbr, *n;
 549         struct _list *ret;
 550
 551         ls = jd->ls;
 552         m  = jd->m;
 553
 554         /* ignore Empty, Deleted,... Basic Blocks as target */
 555         /* TODO: Setup BasicBlock array before to avoid this */
 556         /*       best together with using the basicblock list, so lsra works */
 557         /*       with opt_loops, too */
 558         for (; (to < m->basicblockcount) && (m->basicblocks[to].flags < BBREACHED);
 559                  to++);
 560 #ifdef LSRA_DEBUG_CHECK
 561                 if (to == m->basicblockcount)
 562                         { log_text("Invalid subroutine start index\n"); assert(0); }
 563 #endif
 564
 565         lsra_add_cfg(jd, from, to);
 566
 567         /* from + 1 ist the return Basic Block Index */
 568         for (from++; (from < m->basicblockcount) &&
 569                          (m->basicblocks[from].flags < BBREACHED); from++);
 570 #ifdef LSRA_DEBUG_CHECK
 571         if (from == m->basicblockcount)
 572                 { log_text("Invalid return basic block index for jsr\n"); assert(0); }
 573 #endif
 574
 575         /* add subroutine info in ls->sbr.next */
 576
 577         /* search for right place to insert */
 578         for (sbr = &(ls->sbr); (sbr->next != NULL) && (sbr->next->header < to); sbr=sbr->next);
 579
 580         if ((sbr->next!= NULL) && (sbr->next->header == to)) {
 581                 /* Entry for this sub already exist */
 582                 sbr = sbr->next;
 583         } else {
 584                 /* make new Entry and insert it in ls->sbr.next */
 585                 n = DNEW( struct _sbr );
 586                 n->header = to;
 587                 n->ret = NULL;
 588
 589                 n->next = sbr->next;
 590                 sbr->next = n;
 591
 592                 sbr = n;
 593         }
 594
 595         /* now insert return adress in sbr->ret */
 596         ret = DNEW( struct _list);
 597         ret->value = from;
 598         ret->next = sbr->ret;
 599         sbr->ret = ret;
 600 }
 601
 602 void lsra_add_sub( jitdata *jd, int b_index, struct _list *ret,
 603                                    bool *visited )
 604 {
 605         methodinfo *m;
 606         lsradata  *ls;
 607         struct _list *l;
 608         instruction *ip;
 609         bool next_block;
 610
 611         m  = jd->m;
 612         ls = jd->ls;
 613
 614         /* break at virtual End Block */
 615         if (b_index != m->basicblockcount) {
 616                 visited[b_index] = true;
 617                 next_block = false;
 618
 619                 if (m->basicblocks[b_index].flags < BBREACHED)
 620                         next_block = true;
 621                 if (!next_block && !(m->basicblocks[b_index].icount))
 622                         next_block = true;
 623
 624                 if (!next_block) {
 625                         ip = m->basicblocks[b_index].iinstr
 626                                 + m->basicblocks[b_index].icount -1;
 627
 628                         if (ip->opc == ICMD_JSR) /* nested Subroutines */
 629                                 next_block = true;
 630                 }
 631
 632                 if (!next_block) {
 633                         if (ip->opc == ICMD_RET) {
 634                                 /* subroutine return found -> add return adresses to CFG */
 635                                 for (l = ret; l != NULL; l = l->next)
 636                                         lsra_add_cfg(jd, b_index, l->value);
 637                         } else { /* follow CFG */
 638                                 for ( l = ls->succ[b_index]; l != NULL; l = l->next)
 639                                         if (!visited[l->value])
 640                                                 lsra_add_sub(jd, l->value, ret, visited);
 641                         }
 642                 } else { /* fall through to next block */
 643                                 if (!visited[b_index + 1])
 644                                         lsra_add_sub(jd, b_index + 1, ret, visited);
 645                 }
 646         }
 647 }
 648
 649 /* Add subroutines from ls->sbr list to CFG */
 650 void lsra_add_subs(jitdata *jd) {
 651         methodinfo *m;
 652         lsradata   *ls;
 653         struct _sbr *sbr;
 654         bool *visited;
 655         int i;
 656 #ifdef LSRA_DEBUG_VERBOSE
 657         struct _list *ret;
 658 #endif
 659
 660         m  = jd->m;
 661         ls = jd->ls;
 662
 663         visited = (bool *)DMNEW(int, m->basicblockcount + 1);
 664         for (i=0; i <= m->basicblockcount; i++) visited[i] = false;
 665         for (sbr = ls->sbr.next; sbr != NULL; sbr=sbr->next) {
 666
 667 #ifdef LSRA_DEBUG_VERBOSE
 668                 if (compileverbose) {
 669                         printf("Subroutine Header: %3i Return Adresses:",sbr->header);
 670                         for (ret = sbr->ret; ret != NULL; ret = ret->next)
 671                                 printf(" %3i", ret->value);
 672                         printf("\n");
 673                 }
 674 #endif
 675                 lsra_add_sub(jd, sbr->header, sbr->ret, visited );
 676         }
 677 }
 678
 679 /* Generate the Control Flow Graph             */
 680 /* ( pred,succ,num_pred of lsradata structure) */
 681
 682 void lsra_make_cfg(jitdata *jd) {
 683         methodinfo *m;
 684         lsradata *ls;
 685         instruction *ip;
 686         s4 *s4ptr;
 687         int high, low, count;
 688         int b_index, len;
 689
 690         m  = jd->m;
 691         ls = jd->ls;
 692
 693         b_index=0;
 694         while (b_index < m->basicblockcount ) {
 695                 if ((m->basicblocks[b_index].flags >= BBREACHED) &&
 696                         (len = m->basicblocks[b_index].icount)) {
 697                         /* block is valid and contains instructions     */
 698
 699                         /* set ip to last instruction   */
 700                         ip = m->basicblocks[b_index].iinstr +
 701                                 m->basicblocks[b_index].icount -1;
 702                         while ((len>0) && (ip->opc == ICMD_NOP)) {
 703                                 len--;
 704                                 ip--;
 705                         }
 706                         switch (ip->opc) {                      /* check type of last instruction */
 707                             case ICMD_RETURN:
 708                             case ICMD_IRETURN:
 709                             case ICMD_LRETURN:
 710                                 case ICMD_FRETURN:
 711                                 case ICMD_DRETURN:
 712                                 case ICMD_ARETURN:
 713                                 case ICMD_ATHROW:
 714                                         lsra_add_cfg(jd, b_index, m->basicblockcount);
 715                                         break;                            /* function returns -> end of graph */
 716
 717                                 case ICMD_IFNULL:
 718                                 case ICMD_IFNONNULL:
 719                                 case ICMD_IFEQ:
 720                                 case ICMD_IFNE:
 721                                 case ICMD_IFLT:
 722                                 case ICMD_IFGE:
 723                                 case ICMD_IFGT:
 724                                 case ICMD_IFLE:
 725                                 case ICMD_IF_LEQ:
 726                                 case ICMD_IF_LNE:
 727                                 case ICMD_IF_LLT:
 728                                 case ICMD_IF_LGE:
 729                                 case ICMD_IF_LGT:
 730                                 case ICMD_IF_LLE:
 731                                 case ICMD_IF_ICMPEQ:
 732                                 case ICMD_IF_ICMPNE:
 733                                 case ICMD_IF_ICMPLT:
 734                                 case ICMD_IF_ICMPGE:
 735                                 case ICMD_IF_ICMPGT:
 736                                 case ICMD_IF_ICMPLE:
 737                                 case ICMD_IF_LCMPEQ:
 738                                 case ICMD_IF_LCMPNE:
 739                                 case ICMD_IF_LCMPLT:
 740                                 case ICMD_IF_LCMPGE:
 741                                 case ICMD_IF_LCMPGT:
 742                                 case ICMD_IF_LCMPLE:
 743                                 case ICMD_IF_ACMPEQ:
 744                                 case ICMD_IF_ACMPNE:                /* branch -> add next block */
 745                                         lsra_add_cfg(jd, b_index, b_index+1);
 746                                         /* fall throu -> add branch target */
 747
 748                                 case ICMD_GOTO:
 749                                         lsra_add_cfg(jd, b_index,  m->basicblockindex[ip->op1]);
 750                                         break;                                  /* visit branch (goto) target   */
 751
 752                                 case ICMD_TABLESWITCH:          /* switch statement                             */
 753                                         s4ptr = ip->val.a;
 754
 755                                         lsra_add_cfg(jd, b_index,  m->basicblockindex[*s4ptr]);
 756
 757                                         s4ptr++;
 758                                         low = *s4ptr;
 759                                         s4ptr++;
 760                                         high = *s4ptr;
 761
 762                                         count = (high-low+1);
 763
 764                                         while (--count >= 0) {
 765                                                 s4ptr++;
 766                                                 lsra_add_cfg(jd, b_index,
 767                                                                          m->basicblockindex[*s4ptr]);
 768                                     }
 769                                         break;
 770
 771                                 case ICMD_LOOKUPSWITCH:         /* switch statement                             */
 772                                         s4ptr = ip->val.a;
 773
 774                                         lsra_add_cfg(jd, b_index,  m->basicblockindex[*s4ptr]);
 775
 776                                         ++s4ptr;
 777                                         count = *s4ptr++;
 778
 779                                         while (--count >= 0) {
 780                                                 lsra_add_cfg(jd, b_index,
 781                                                                          m->basicblockindex[s4ptr[1]]);
 782                                                 s4ptr += 2;
 783                                     }
 784                                         break;
 785
 786                                 case ICMD_JSR:
 787                                         lsra_add_jsr(jd, b_index, m->basicblockindex[ip->op1]);
 788                                         break;
 789
 790                                 case ICMD_RET:
 791                                         break;
 792
 793                                 default:
 794                                         lsra_add_cfg(jd, b_index, b_index + 1 );
 795                                         break;
 796                         } /* switch (ip->opc)*/
 797                 }     /* if ((m->basicblocks[blockIndex].icount)&& */
 798                       /*     (m->basicblocks[b_index].flags >= BBREACHED)) */
 799                 b_index++;
 800         }             /* while (b_index < m->basicblockcount ) */
 801 }
 802
 803 void lsra_init(jitdata *jd) {
 804         methodinfo   *m;
 805         lsradata     *ls;
 806         int i;
 807
 808         ls = jd->ls;
 809         m  = jd->m;
 810
 811         /* Init LSRA Data Structures */
 812         /* allocate lifetimes for all Basicblocks */
 813         /* + 1 for an artificial exit node */
 814         /* which is needed as "start" point for the reverse postorder sorting */
 815         ls->pred = DMNEW(struct _list *, m->basicblockcount+1);
 816         ls->succ = DMNEW(struct _list *, m->basicblockcount+1);
 817         ls->sorted = DMNEW(int , m->basicblockcount+1);
 818         ls->sorted_rev = DMNEW(int , m->basicblockcount+1);
 819         ls->num_pred = DMNEW(int , m->basicblockcount+1);
 820         ls->nesting = DMNEW(long , m->basicblockcount+1);
 821         for (i=0; i<m->basicblockcount; i++) {
 822                 ls->pred[i]=NULL;
 823                 ls->succ[i]=NULL;
 824                 ls->sorted[i]=-1;
 825                 ls->sorted_rev[i]=-1;
 826                 ls->num_pred[i]=0;
 827                 ls->nesting[i] = 1;
 828         }
 829         ls->pred[m->basicblockcount]=NULL;
 830         ls->succ[m->basicblockcount]=NULL;
 831         ls->sorted[m->basicblockcount]=-1;
 832         ls->sorted_rev[m->basicblockcount]=-1;
 833         ls->num_pred[m->basicblockcount]=0;
 834
 835         ls->sbr.next = NULL;
 836
 837         ls->v_index = -1;
 838 }
 839
 840 void lsra_setup(jitdata *jd) {
 841         methodinfo *m;
 842         codegendata *cd;
 843         lsradata *ls;
 844
 845 #ifdef LSRA_DEBUG_VERBOSE
 846         basicblock  *bptr;
 847         struct _list *nl;
 848 #endif
 849
 850         int i;
 851
 852 #if !defined(LV)
 853         registerdata *rd;
 854
 855         rd = jd->rd;
 856 #endif
 857
 858         ls = jd->ls;
 859         m  = jd->m;
 860         cd = jd->cd;
 861
 862 #if defined(ENABLE_LOOP)
 863         /* Loop optimization "destroys" the basicblock array */
 864         /* TODO: work with the basicblock list               */
 865         if (opt_loops) {
 866                 log_text("lsra not possible with loop optimization\n");
 867                 abort();
 868         }
 869 #endif /* defined(ENABLE_LOOP) */
 870
 871         /* Setup LSRA Data structures */
 872
 873         /* Generate the Control Flow Graph */
 874         lsra_make_cfg(jd);
 875         /* gather nesting before adding of Exceptions and Subroutines!!! */
 876
 877 #ifdef USAGE_COUNT
 878         lsra_DFS(jd);
 879         lsra_get_nesting(jd);
 880 #endif
 881
 882 #ifdef LSRA_DEBUG_VERBOSE
 883         if (compileverbose) {
 884         printf("Successors:\n");
 885         for (i=0; i < m->basicblockcount; i++) {
 886                 printf("%3i->: ",i);
 887                 for (nl=ls->succ[i]; nl!= NULL; nl=nl->next)
 888                         printf("%3i ",nl->value);
 889                 printf("\n");
 890         }
 891         printf("Predecessors:\n");
 892         for (i=0; i < m->basicblockcount; i++) {
 893                 printf("%3i->: ",i);
 894                 for (nl=ls->pred[i]; nl!= NULL; nl=nl->next)
 895                         printf("%3i ",nl->value);
 896                 printf("\n");
 897         }
 898         printf("Sorted: ");
 899         for (i=0; i < m->basicblockcount; i++) printf("%3i ", ls->sorted[i]);
 900         printf("\n");
 901         printf("Sorted_rev: ");
 902         for (i=0; i < m->basicblockcount; i++) printf("%3i ", ls->sorted_rev[i]);
 903         printf("\n");
 904         }
 905 #endif
 906
 907         /* add subroutines before exceptions! They "destroy" the CFG */
 908         lsra_add_subs(jd);
 909         lsra_add_exceptions(jd);
 910
 911         /* generate reverse post order sort */
 912         lsra_DFS(jd);
 913
 914         /* setup backedge and nested data structures*/
 915         lsra_get_backedges(jd);
 916
 917         liveness_init(jd);
 918
 919         ls->lifetimecount = ls->maxlifetimes + jd->maxlocals * (TYPE_ADR+1);
 920         ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
 921         ls->lt_used  = DMNEW(int, ls->lifetimecount);
 922         ls->lt_int   = DMNEW(int, ls->lifetimecount);
 923         ls->lt_int_count = 0;
 924         ls->lt_flt   = DMNEW(int, ls->lifetimecount);
 925         ls->lt_flt_count = 0;
 926         ls->lt_mem   = DMNEW(int, ls->lifetimecount);
 927         ls->lt_mem_count = 0;
 928
 929         for (i=0; i < ls->lifetimecount; i++) ls->lifetime[i].type = -1;
 930
 931 #ifdef LSRA_DEBUG_VERBOSE
 932         if (compileverbose) {
 933         printf("Successors:\n");
 934         for (i=0; i < m->basicblockcount; i++) {
 935                 printf("%3i->: ",i);
 936                 for (nl=ls->succ[i]; nl!= NULL; nl=nl->next)
 937                         printf("%3i ",nl->value);
 938                 printf("\n");
 939         }
 940         printf("Predecessors:\n");
 941         for (i=0; i < m->basicblockcount; i++) {
 942                 printf("%3i->: ",i);
 943                 for (nl=ls->pred[i]; nl!= NULL; nl=nl->next)
 944                         printf("%3i ",nl->value);
 945                 printf("\n");
 946         }
 947         printf("Sorted: ");
 948         for (i=0; i < m->basicblockcount; i++) printf("%3i ", ls->sorted[i]);
 949         printf("\n");
 950         printf("Sorted_rev: ");
 951         for (i=0; i < m->basicblockcount; i++) printf("%3i ", ls->sorted_rev[i]);
 952         printf("\n");
 953         }
 954 #endif
 955
 956
 957 #ifdef LSRA_DEBUG_CHECK
 958         /* compare m->basicblocks[] with the list basicblocks->next */
 959         i=0;
 960         bptr = m->basicblocks;
 961         while (bptr != NULL) {
 962                 if (i > m->basicblockcount){
 963                         { log_text("linked bb list does not correspond with bb array(1)\n");
 964                                 assert(0); }
 965                 }
 966                 if (bptr != &(m->basicblocks[i])){
 967                         { log_text("linked bb list does not correspond with bb array(2)\n");
 968                                 assert(0); }
 969                 }
 970
 971                 i++;
 972                 bptr=bptr->next;
 973         }
 974         if (i<m->basicblockcount){
 975                 { log_text("linked bb list does not correspond with bb array(3)\n");
 976                         assert(0); }
 977         }
 978
 979 #endif
 980
 981         liveness_setup(jd);
 982
 983 #if defined(LV)
 984         liveness(jd);
 985 #else /* LV */
 986         {
 987                 int p, t;
 988                 methoddesc *md = m->parseddesc;
 989
 990                 /* Create Stack Slot lifetimes over all basic blocks */
 991                 for (i=m->basicblockcount-1; i >= 0; i--) {
 992                         if (ls->sorted[i] != -1) {
 993                                 lsra_scan_registers_canditates(jd, ls->sorted[i]);
 994                                 lsra_join_lifetimes(jd, ls->sorted[i]);
 995                         }
 996                 }
 997
 998                 /* Parameter initialisiation for locals [0 .. paramcount[            */
 999                 /* -> add local var write access at (bb=0,iindex=-1)                 */
1000                 /* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!   */
1001                 /* this needs a special treatment, wenn lifetimes get extended       */
1002                 /* over backedges, since this parameter initialisation happens       */
1003                 /* outside of Basic Block 0 !!!!                                     */
1004                 /* this could have been avoided by marking the read access with -1,0 */
1005
1006                 for (p = 0, i = 0; p < md->paramcount; p++) {
1007                         t = md->paramtypes[p].type;
1008
1009                         if (rd->locals[i][t].type >= 0)
1010                                 /* Param to Local init happens before normal Code */
1011                                 lsra_usage_local(ls, i, t, 0, -1, LSRA_STORE);
1012                         i++;
1013                         /* increment local counter a second time  */
1014                         /* for 2 word types */
1015                         if (IS_2_WORD_TYPE(t))
1016                                 i++;
1017                 }  /* end for */
1018         }
1019 #endif /* LV */
1020
1021         lsra_calc_lifetime_length(jd);
1022
1023 #ifdef LSRA_DEBUG_VERBOSE
1024         if (compileverbose)
1025                 printf("Basicblockcount: %4i\n",m->basicblockcount);
1026 #endif
1027 }
1028
1029
1030 void lsra_reg_setup(jitdata *jd, struct lsra_register *int_reg,
1031                                         struct lsra_register *flt_reg ) {
1032         int i, j, iarg, farg;
1033         int int_sav_top;
1034         int flt_sav_top;
1035         bool *fltarg_used, *intarg_used;
1036         methoddesc *md;
1037         methodinfo *m;
1038         registerdata *rd;
1039
1040         m  = jd->m;
1041         rd = jd->rd;
1042         md = m->parseddesc;
1043
1044         int_reg->nregdesc = nregdescint;
1045         flt_reg->nregdesc = nregdescfloat;
1046         if (code_is_leafmethod(code)) {
1047                 /* Temp and Argumentregister can be used as saved registers */
1048
1049                 int_reg->sav_top = INT_ARG_CNT + INT_TMP_CNT + INT_SAV_CNT;
1050                 int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
1051                 int_reg->tmp_reg = NULL;
1052                 int_reg->tmp_top = -1;
1053                 flt_reg->sav_top = FLT_ARG_CNT + FLT_TMP_CNT + FLT_SAV_CNT;
1054                 flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
1055                 flt_reg->tmp_reg = NULL;
1056                 flt_reg->tmp_top = -1;
1057
1058                 /* additionaly precolour registers for Local Variables acting as */
1059                 /* Parameters */
1060
1061                 farg = FLT_ARG_CNT;
1062                 iarg = INT_ARG_CNT;
1063
1064                 intarg_used = DMNEW(bool, INT_ARG_CNT);
1065                 for (i=0; i < INT_ARG_CNT; i++)
1066                         intarg_used[i]=false;
1067
1068                 fltarg_used = DMNEW(bool, FLT_ARG_CNT);
1069                 for (i=0; i < FLT_ARG_CNT; i++)
1070                         fltarg_used[i]=false;
1071
1072                 int_sav_top=int_reg->sav_top;
1073                 flt_sav_top=flt_reg->sav_top;
1074
1075                 for (i=0; (i < md->paramcount); i++) {
1076                         if (!md->params[i].inmemory) {
1077                                 if (IS_INT_LNG_TYPE(md->paramtypes[i].type)) {
1078 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1079                                         if (IS_2_WORD_TYPE(md->paramtypes[i].type)) {
1080                                                 int_reg->sav_reg[--int_sav_top] =
1081                                                         rd->argintregs[GET_HIGH_REG(md->params[i].regoff)];
1082                                                 intarg_used[GET_HIGH_REG(md->params[i].regoff)]=true;
1083                                                 /*used -> don't copy later on */
1084                                                 int_reg->sav_reg[--int_sav_top] =
1085                                                         rd->argintregs[GET_LOW_REG(md->params[i].regoff)];
1086                                                 intarg_used[GET_LOW_REG(md->params[i].regoff)]=true;
1087                                                 /*used -> don't copy later on */
1088                                         } else
1089 #endif
1090                                         { /* !IS_2_WORD_TYPE(md->paramtypes[i].type */
1091                                                 int_reg->sav_reg[--int_sav_top] =
1092                                                         rd->argintregs[md->params[i].regoff];
1093                                                 intarg_used[md->params[i].regoff]=true;
1094                                                 /*used -> don't copy later on */
1095                                         }
1096                                 }
1097 #if !defined(SUPPORT_PASS_FLOATARGS_IN_INTREGS)
1098                                 /* do not precolour float arguments if they are passed in     */
1099                                 /* integer registers. But these integer argument registers    */
1100                                 /* still be used in the method! */
1101                                 else { /* IS_FLT_DBL_TYPE(md->paramtypes[i].type */
1102                                                 flt_reg->sav_reg[--flt_sav_top] =
1103                                                         rd->argfltregs[md->params[i].regoff];
1104                                                 fltarg_used[md->params[i].regoff]=true;
1105                                 }
1106 #endif
1107
1108                         }
1109                 }
1110
1111                 /* copy rest of argument registers to flt_reg->sav_reg and */
1112                 /* int_reg->sav_reg; */
1113                 for (i=0; i < INT_ARG_CNT; i++)
1114                         if (!intarg_used[i])
1115                                 int_reg->sav_reg[--int_sav_top]=rd->argintregs[i];
1116                 for (i=0; i < FLT_ARG_CNT; i++)
1117                         if (!fltarg_used[i])
1118                                 flt_reg->sav_reg[--flt_sav_top]=rd->argfltregs[i];
1119
1120                 /* copy temp registers to flt_reg->sav_reg and int_reg->sav_reg */
1121                 for (i=0; i < INT_TMP_CNT; i++)
1122                         int_reg->sav_reg[--int_sav_top]=rd->tmpintregs[i];
1123                 for (i=0; i < FLT_TMP_CNT; i++)
1124                         flt_reg->sav_reg[--flt_sav_top]=rd->tmpfltregs[i];
1125
1126         } else {
1127                 /* non leaf method -> use Argument Registers [arg[int|flt]reguse */
1128                 /* ... [INT|FLT]_ARG_CNT[ as temp reg */
1129                 /* divide temp and saved registers */
1130                 int argintreguse, argfltreguse;
1131 #ifdef LV
1132                 /* with Locals as non SAVEDVAR, the used arg[int|flt] as in params */
1133                 /* of the method itself have to be regarded, or mismatch before    */
1134                 /* block 0 with parameter copy could happen! */
1135                 argintreguse = max(rd->argintreguse, md->argintreguse);
1136                 argfltreguse = max(rd->argfltreguse, md->argfltreguse);
1137 #else
1138                 argintreguse = rd->argintreguse;
1139                 argfltreguse = rd->argfltreguse;
1140 #endif
1141                 int_sav_top = int_reg->sav_top = INT_SAV_CNT;
1142                 int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
1143                 int_reg->tmp_top = INT_TMP_CNT +
1144                         max(0, (INT_ARG_CNT - argintreguse));
1145                 int_reg->tmp_reg = DMNEW(int, int_reg->tmp_top);
1146
1147                 flt_sav_top =flt_reg->sav_top = FLT_SAV_CNT;
1148                 flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
1149                 flt_reg->tmp_top = FLT_TMP_CNT +
1150                         max(0 , (FLT_ARG_CNT - argfltreguse));
1151                 flt_reg->tmp_reg = DMNEW(int, flt_reg->tmp_top);
1152
1153                 /* copy temp and unused argument registers to flt_reg->tmp_reg and */
1154                 /* int_reg->tmp_reg */
1155                 for (i=0; i < INT_TMP_CNT; i++)
1156                         int_reg->tmp_reg[i]=rd->tmpintregs[i];
1157                 for (j=argintreguse; j < INT_ARG_CNT; j++, i++)
1158                         int_reg->tmp_reg[i]=rd->argintregs[j];
1159                 for (i=0; i < FLT_TMP_CNT; i++)
1160                         flt_reg->tmp_reg[i]=rd->tmpfltregs[i];
1161                 for (j=argfltreguse; j < FLT_ARG_CNT; j++, i++)
1162                         flt_reg->tmp_reg[i]=rd->argfltregs[j];
1163         }
1164
1165         /* now copy saved registers to flt_reg->sav_reg and int_reg->sav_reg */
1166         for (i = INT_SAV_CNT-1; i >= 0; i--)
1167                 int_reg->sav_reg[--int_sav_top]=rd->savintregs[i];
1168         for (i = FLT_SAV_CNT-1; i >= 0; i--)
1169                 flt_reg->sav_reg[--flt_sav_top]=rd->savfltregs[i];
1170         /* done */
1171 }
1172
1173 void lsra_insertion_sort( struct lsradata *ls, int *a, int lo, int hi) {
1174         int i,j,t,tmp;
1175
1176         for (i=lo+1; i<=hi; i++) {
1177                 j=i;
1178                 t=ls->lifetime[a[j]].i_start;
1179                 tmp = a[j];
1180                 while ((j>lo) && (ls->lifetime[a[j-1]].i_start > t)) {
1181                         a[j]=a[j-1];
1182                         j--;
1183                 }
1184                 a[j]=tmp;
1185         }
1186 }
1187
1188 void lsra_qsort( struct lsradata *ls, int *a, int lo, int hi) {
1189         int i,j,x,tmp;
1190         if (lo < hi) {
1191                 if ( (lo+5)<hi) {
1192                         i = lo;
1193                         j = hi;
1194                         x = ls->lifetime[a[(lo+hi)/2]].i_start;
1195
1196                         while (i <= j) {
1197                                 while (ls->lifetime[a[i]].i_start < x) i++;
1198                                 while (ls->lifetime[a[j]].i_start > x) j--;
1199                                 if (i <= j) {
1200                                         /* exchange a[i], a[j] */
1201                                         tmp = a[i];
1202                                         a[i] = a[j];
1203                                         a[j] = tmp;
1204
1205                                         i++;
1206                                         j--;
1207                                 }
1208                         }
1209
1210                         if (lo < j) lsra_qsort( ls, a, lo, j);
1211                         if (i < hi) lsra_qsort( ls, a, i, hi);
1212                 } else
1213                         lsra_insertion_sort(ls, a, lo, hi);
1214         }
1215 }
1216
1217 void lsra_param_sort(struct lsradata *ls, int *lifetime, int lifetime_count) {
1218
1219         int param_count;
1220         int i,j,tmp;
1221
1222         /* count number of parameters ( .i_start == -1) */
1223         for (param_count=0; (param_count < lifetime_count) &&
1224                  (ls->lifetime[lifetime[param_count]].i_start == -1); param_count++);
1225
1226         if (param_count > 0) {
1227                 /* now sort the parameters by v_index */
1228                 for (i=0; i < param_count -1; i++)
1229                         for (j=i+1; j < param_count; j++)
1230                                 if ( ls->lifetime[lifetime[i]].v_index >
1231                                          ls->lifetime[lifetime[j]].v_index) {
1232                                         /* swap */
1233                                         tmp = lifetime[i];
1234                                         lifetime[i]=lifetime[j];
1235                                         lifetime[j]=tmp;
1236                                 }
1237         }
1238 }
1239
1240 void lsra_main(jitdata *jd) {
1241 #ifdef LSRA_DEBUG_VERBOSE
1242         int i;
1243 #endif
1244         int lsra_mem_use;
1245         int lsra_reg_use;
1246         struct lsra_register flt_reg, int_reg;
1247         lsradata *ls;
1248         registerdata *rd;
1249 #if defined(__I386__)
1250         methodinfo *m;
1251
1252         m  = jd->m;
1253 #endif
1254         ls = jd->ls;
1255         rd = jd->rd;
1256
1257 /* sort lifetimes by increasing start */
1258         lsra_qsort( ls, ls->lt_mem, 0, ls->lt_mem_count - 1);
1259         lsra_qsort( ls, ls->lt_int, 0, ls->lt_int_count - 1);
1260         lsra_qsort( ls, ls->lt_flt, 0, ls->lt_flt_count - 1);
1261 /* sort local vars used as parameter */
1262         lsra_param_sort( ls, ls->lt_int, ls->lt_int_count);
1263         lsra_param_sort( ls, ls->lt_flt, ls->lt_flt_count);
1264         lsra_reg_setup(jd, &int_reg, &flt_reg);
1265
1266 #ifdef LSRA_DEBUG_VERBOSE
1267         if (compileverbose) {
1268                 printf("INTSAV REG: ");
1269                 for (i=0; i<int_reg.sav_top; i++)
1270                         printf("%2i ",int_reg.sav_reg[i]);
1271                 printf("\nINTTMP REG: ");
1272                 for (i=0; i<int_reg.tmp_top; i++)
1273                         printf("%2i ",int_reg.tmp_reg[i]);
1274                 printf("\nFLTSAV REG: ");
1275                 for (i=0; i<flt_reg.sav_top; i++)
1276                         printf("%2i ",flt_reg.sav_reg[i]);
1277                 printf("\nFLTTMP REG: ");
1278                 for (i=0; i<flt_reg.tmp_top; i++)
1279                         printf("%2i ",flt_reg.tmp_reg[i]);
1280                 printf("\n");
1281         }
1282 #endif
1283         ls->active_tmp = DMNEW( struct lifetime *, max(INT_REG_CNT, FLT_REG_CNT));
1284         ls->active_sav = DMNEW( struct lifetime *, max(INT_REG_CNT, FLT_REG_CNT));
1285
1286         lsra_reg_use=INT_SAV_CNT; /* init to no saved reg used... */
1287         _lsra_main(jd, ls->lt_int, ls->lt_int_count, &int_reg, &lsra_reg_use);
1288         if (lsra_reg_use > INT_SAV_CNT)
1289                 lsra_reg_use=INT_SAV_CNT;
1290         rd->savintreguse = lsra_reg_use;
1291
1292         lsra_reg_use = FLT_SAV_CNT; /* no saved reg used... */
1293         _lsra_main(jd, ls->lt_flt, ls->lt_flt_count, &flt_reg, &lsra_reg_use);
1294         if (lsra_reg_use > FLT_SAV_CNT)
1295                 lsra_reg_use=FLT_SAV_CNT;
1296         rd->savfltreguse=lsra_reg_use;
1297
1298         /* rd->memuse was already set in stack.c to allocate stack space for */
1299         /* passing arguments to called methods */
1300 #if defined(__I386__)
1301         if (checksync && code_is_synchronized(code)) {
1302                 /* reserve 0(%esp) for Monitorenter/exit Argument on i386 */
1303                 if (rd->memuse < 1)
1304                         rd->memuse = 1;
1305         }
1306 #endif
1307
1308         lsra_mem_use = rd->memuse; /* Init with memuse from stack.c */
1309
1310         lsra_alloc(jd, ls->lt_mem, ls->lt_mem_count, &lsra_mem_use);
1311         lsra_alloc(jd, ls->lt_int, ls->lt_int_count, &lsra_mem_use);
1312         lsra_alloc(jd, ls->lt_flt, ls->lt_flt_count, &lsra_mem_use);
1313
1314         rd->memuse=lsra_mem_use;
1315
1316 #ifdef LSRA_DEBUG_VERBOSE
1317         if (compileverbose) {
1318                 printf("Int RA complete \n");
1319                 printf("Lifetimes after splitting int: \n");
1320                 print_lifetimes(jd, ls->lt_int, ls->lt_int_count);
1321
1322                 printf("Flt RA complete \n");
1323                 printf("Lifetimes after splitting flt:\n");
1324                 print_lifetimes(jd, ls->lt_flt, ls->lt_flt_count);
1325
1326                 printf("Rest RA complete \n");
1327                 printf("Lifetimes after leftt:\n");
1328                 print_lifetimes(jd, ls->lt_mem, ls->lt_mem_count);
1329         }
1330 #endif
1331 }
1332
1333 void lsra_alloc(jitdata *jd, int *lifet, int lifetimecount, int *mem_use)
1334 {
1335         int flags,regoff;
1336         struct lifetime *lt;
1337         struct freemem *fmem;
1338         struct stackslot *n;
1339         int lt_index;
1340 #ifdef HAS_4BYTE_STACKSLOT
1341         struct freemem *fmem_2;
1342 #endif
1343         registerdata *rd;
1344         lsradata     *ls;
1345
1346         rd = jd->rd;
1347         ls = jd->ls;
1348
1349         fmem = DNEW(struct freemem);
1350         fmem->off  = -1;
1351         fmem->next = NULL;
1352 #ifdef HAS_4BYTE_STACKSLOT
1353         fmem_2=DNEW(struct freemem);
1354         fmem_2->off  = -1;
1355         fmem_2->next = NULL;
1356 #endif
1357
1358         for (lt_index = 0; lt_index < lifetimecount; lt_index ++) {
1359                 lt = &(ls->lifetime[lifet[lt_index]]);
1360 #ifdef LSRA_MEMORY
1361                 lt->reg = -1;
1362 #endif
1363                 if (lt->reg == -1) {
1364                         flags = INMEMORY;
1365 #ifdef HAS_4BYTE_STACKSLOT
1366                         if (IS_2_WORD_TYPE(lt->type))
1367                                 regoff = lsra_getmem(lt, fmem_2, mem_use);
1368                         else
1369 #endif
1370                         regoff = lsra_getmem(lt, fmem, mem_use);
1371                 } else {
1372                         flags  = lt->savedvar;
1373                         regoff = lt->reg;
1374                 }
1375
1376                 if (lt->v_index < 0) {
1377                         for (n = lt->local_ss; n != NULL; n = n->next) {
1378                                 lsra_setflags(&(n->s->flags), flags);
1379                                 n->s->regoff = regoff;
1380                         }
1381                 } else { /* local var */
1382                         if (rd->locals[lt->v_index][lt->type].type >= 0) {
1383                                 rd->locals[lt->v_index][lt->type].flags  = flags;
1384                                 rd->locals[lt->v_index][lt->type].regoff = regoff;
1385                         } else {
1386                                 log_text("Type Data mismatch\n");
1387                                 abort();
1388                         }
1389                 }
1390                 lt->reg = regoff;
1391         }
1392 }
1393
1394 void lsra_setflags(int *flags, int newflags)
1395 {
1396         if ( newflags & INMEMORY)
1397                 *flags |= INMEMORY;
1398         else
1399                 *flags &= ~INMEMORY;
1400
1401         if (newflags & SAVEDVAR)
1402                 *flags |= SAVEDVAR;
1403 }
1404
1405 int lsra_getmem(struct lifetime *lt, struct freemem *fmem, int *mem_use)
1406 {
1407         struct freemem *fm, *p;
1408
1409         /* no Memory Slot allocated till now or all are still live */
1410         if ((fmem->next == NULL) || (fmem->next->end > lt->i_start)) {
1411 #ifdef HAS_4BYTE_STACKSLOT
1412                 if (IS_2_WORD_TYPE(lt->type))
1413                         if ( (*mem_use)&1 ) /* align memory location for 2 Word Types */
1414                                 (*mem_use)++;
1415                 fm=lsra_getnewmem(mem_use);
1416                 if (IS_2_WORD_TYPE(lt->type))
1417                         /* allocate a second following Slot for 2 Word Types */
1418                         (*mem_use)++;
1419 #else
1420                 fm=lsra_getnewmem(mem_use);
1421 #endif
1422         } else {
1423                 /* Memoryslot free */
1424                 fm = fmem->next;
1425                 fmem->next = fm->next;
1426                 fm->next = NULL;
1427         }
1428         fm->end = lt->i_end;
1429         for (p = fmem; (p->next != NULL) && (p->next->end < fm->end); p = p->next);
1430         fm->next = p->next;
1431         p->next = fm;
1432         return fm->off;
1433 }
1434
1435 struct freemem *lsra_getnewmem(int *mem_use)
1436 {
1437         struct freemem *fm;
1438
1439         fm = DNEW(struct freemem);
1440         fm->next = NULL;
1441         fm->off = *mem_use;
1442         (*mem_use)++;
1443         return fm;
1444 }
1445
1446 void _lsra_main(jitdata *jd, int *lifet, int lifetimecount,
1447                                 struct lsra_register *reg, int *reg_use)
1448 {
1449         struct lifetime *lt;
1450         int lt_index;
1451         int reg_index;
1452         int regsneeded;
1453         bool temp; /* reg from temp registers (true) or saved registers (false) */
1454         methodinfo *m;
1455         lsradata *ls;
1456
1457         m  = jd->m;
1458         ls = jd->ls;
1459
1460 #if !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1461         regsneeded = 0;
1462 #endif
1463         if ((reg->tmp_top+reg->sav_top) == 0) {
1464
1465                 /* no registers available */
1466                 for (lt_index = 0; lt_index < lifetimecount; lt_index++)
1467                         ls->lifetime[lifet[lt_index]].reg = -1;
1468                 return;
1469         }
1470
1471         ls->active_tmp_top = 0;
1472         ls->active_sav_top = 0;
1473
1474         for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
1475                 lt = &(ls->lifetime[lifet[lt_index]]);
1476
1477 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1478         regsneeded = (lt->type == TYPE_LNG)?1:0;
1479 #endif
1480
1481                 lsra_expire_old_intervalls(jd, lt, reg);
1482                 reg_index = -1;
1483                 temp = false;
1484                 if (lt->savedvar || code_is_leafmethod(code)) {
1485                         /* use Saved Reg (in case of leafmethod all regs are saved regs) */
1486                         if (reg->sav_top > regsneeded) {
1487 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1488                                 if (regsneeded)
1489                                         reg_index = PACK_REGS(reg->sav_reg[--reg->sav_top],
1490                                                                                   reg->sav_reg[--reg->sav_top]);
1491                                 else
1492 #endif
1493
1494                                         reg_index = reg->sav_reg[--reg->sav_top];
1495                         }
1496                 } else { /* use Temp Reg or if none is free a Saved Reg */
1497                         if (reg->tmp_top > regsneeded) {
1498                                 temp = true;
1499 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1500                         if (regsneeded)
1501                                 reg_index = PACK_REGS(reg->tmp_reg[--reg->tmp_top],
1502                                                                           reg->tmp_reg[--reg->tmp_top]);
1503                         else
1504 #endif
1505                                 reg_index = reg->tmp_reg[--reg->tmp_top];
1506                         }
1507                         else
1508                                 if (reg->sav_top > regsneeded) {
1509
1510 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1511                                 if (regsneeded)
1512                                         reg_index = PACK_REGS(reg->sav_reg[--reg->sav_top],
1513                                                                                   reg->sav_reg[--reg->sav_top]);
1514                                 else
1515 #endif
1516                                         reg_index = reg->sav_reg[--reg->sav_top];
1517                                 }
1518                 }
1519                 if (reg_index == -1) /* no reg is available anymore... -> spill */
1520                         spill_at_intervall(jd, lt);
1521                 else {
1522                         lt->reg = reg_index;
1523                         if (temp)
1524                                 lsra_add_active(lt, ls->active_tmp, &(ls->active_tmp_top));
1525                         else {
1526                                 if (reg->sav_top<*reg_use) *reg_use=reg->sav_top;
1527                                 lsra_add_active(lt, ls->active_sav, &(ls->active_sav_top));
1528                         }
1529                 }
1530         }
1531 }
1532
1533 void lsra_add_active(struct lifetime *lt, struct lifetime **active,
1534                                          int *active_top)
1535 {
1536         int i, j;
1537
1538         for(i = 0; (i < *active_top) && (active[i]->i_end < lt->i_end); i++);
1539         for(j = *active_top; j > i; j--) active[j] = active[j-1];
1540         (*active_top)++;
1541         active[i] = lt;
1542 }
1543
1544 void lsra_expire_old_intervalls(jitdata *jd, struct lifetime *lt,
1545                                                                 struct lsra_register *reg)
1546 {
1547         _lsra_expire_old_intervalls(jd, lt, reg, jd->ls->active_tmp,
1548                                                                 &(jd->ls->active_tmp_top));
1549         _lsra_expire_old_intervalls(jd, lt, reg, jd->ls->active_sav,
1550                                                                 &(jd->ls->active_sav_top));
1551 }
1552
1553 void _lsra_expire_old_intervalls(jitdata *jd, struct lifetime *lt,
1554                                                                  struct lsra_register *reg,
1555                                                                  struct lifetime **active, int *active_top)
1556 {
1557         int i, j, k;
1558
1559         for(i = 0; i < *active_top; i++) {
1560                 if (active[i]->i_end > lt->i_start) break;
1561
1562                 /* make active[i]->reg available again */
1563                 if (code_is_leafmethod(code)) {
1564                         /* leafmethod -> don't care about type -> put all again into */
1565                         /* reg->sav_reg */
1566 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1567                         if (active[i]->type == TYPE_LNG) {
1568                                 reg->sav_reg[reg->sav_top++] = GET_LOW_REG(active[i]->reg);
1569                                 reg->sav_reg[reg->sav_top++] = GET_HIGH_REG(active[i]->reg);
1570                         } else
1571 #endif
1572                                 reg->sav_reg[reg->sav_top++] = active[i]->reg;
1573                 } else {
1574                         /* no leafmethod -> distinguish between temp and saved register */
1575 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1576                         if (active[i]->type == TYPE_LNG) {
1577                                 /* no temp and saved regs are packed together, so looking at */
1578                                 /* LOW_REG is sufficient */
1579                                 if ( reg->nregdesc[ GET_LOW_REG(active[i]->reg)] == REG_SAV) {
1580                                         reg->sav_reg[reg->sav_top++] = GET_LOW_REG(active[i]->reg);
1581                                         reg->sav_reg[reg->sav_top++] = GET_HIGH_REG(active[i]->reg);
1582                                 } else {
1583                                         reg->tmp_reg[reg->tmp_top++] = GET_LOW_REG(active[i]->reg);
1584                                         reg->tmp_reg[reg->tmp_top++] = GET_HIGH_REG(active[i]->reg);
1585                                 }
1586                         } else
1587 #endif
1588                         if ( reg->nregdesc[active[i]->reg] == REG_SAV) {
1589                                         reg->sav_reg[reg->sav_top++] = active[i]->reg;
1590                         } else {
1591                                         reg->tmp_reg[reg->tmp_top++] = active[i]->reg;
1592                         }
1593                 }
1594         }
1595
1596         /* active[0..i[ is to be removed */
1597         /* -> move [i..*active_top[ to [0..*active_top-i[ */
1598         for(k = 0, j = i; (j < *active_top); k++,j++)
1599                 active[k] = active[j];
1600
1601         (*active_top) -= i;
1602
1603 }
1604
1605 void spill_at_intervall(jitdata *jd, struct lifetime *lt )
1606 {
1607         if (lt->savedvar || code_is_leafmethod(code)) {
1608                 _spill_at_intervall(lt, jd->ls->active_sav, &(jd->ls->active_sav_top));
1609         } else {
1610                 _spill_at_intervall(lt, jd->ls->active_tmp, &(jd->ls->active_tmp_top));
1611                 if (lt->reg == -1) { /* no tmp free anymore */
1612                         _spill_at_intervall(lt, jd->ls->active_sav,
1613                                                                 &(jd->ls->active_sav_top));
1614                 }
1615         }
1616 }
1617
1618 void _spill_at_intervall(struct lifetime *lt, struct lifetime **active,
1619                                                  int *active_top)
1620 {
1621         int i, j;
1622 #ifdef USAGE_COUNT_EXACT
1623         int u_min, i_min;
1624 #endif
1625
1626         if (*active_top == 0) {
1627                 lt->reg=-1;
1628                 return;
1629         }
1630
1631         i = *active_top - 1;
1632 #if defined(USAGE_COUNT_EXACT)
1633         /* find intervall which ends later or equal than than lt and has the lowest
1634            usagecount lower than lt */
1635         i_min = -1;
1636         u_min = lt->usagecount;
1637         for (; (i >= 0) && (active[i]->i_end >= lt->i_end); i--) {
1638                 if (active[i]->usagecount < u_min) {
1639                         u_min = active[i]->usagecount;
1640                         i_min = i;
1641                 }
1642         }
1643
1644         if (i_min != -1) {
1645                 i = i_min;
1646 #else
1647 # if defined(USAGE_COUNT) && !defined(USAGE_COUNT_EXACT)
1648         if ((active[i]->i_end >= lt->i_end)
1649                  && (active[i]->usagecount < lt->usagecount)) {
1650 # else /* "normal" LSRA heuristic */
1651         /* get last intervall from active */
1652         if (active[i]->i_end > lt->i_end) {
1653 # endif
1654 #endif
1655 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1656                 /* Don't spill between one and two word int types */
1657                 if ((active[i]->type == TYPE_LNG) != (lt->type == TYPE_LNG))
1658                         return;
1659 #endif
1660                 lt->reg = active[i]->reg;
1661                 active[i]->reg=-1;
1662
1663                 (*active_top)--;
1664                 for (j = i; j < *active_top; j++)
1665                         active[j] = active[j + 1];
1666
1667                 lsra_add_active(lt, active, active_top);
1668         } else {
1669                 lt->reg=-1;
1670         }
1671 }
1672
1673 void lsra_calc_lifetime_length(jitdata *jd) {
1674         methodinfo *m;
1675         lsradata *ls;
1676         codegendata *cd;
1677         struct lifetime *lt;
1678 #if defined(LSRA_DEBUG_VERBOSE) || !defined(LV)
1679         int i;
1680 #endif
1681         int lt_index;
1682         int lifetimecount;
1683         int flags; /* 0 INMEMORY -> ls->lt_mem */
1684                    /* 1 INTREG   -> ls->lt_int  */
1685                    /* 2 FLTREG   -> ls->lt_flt  */
1686
1687
1688         m  = jd->m;
1689         ls = jd->ls;
1690         cd = jd->cd;
1691
1692 #ifdef LSRA_DEBUG_VERBOSE
1693         if (compileverbose) {
1694         printf("icount_block: ");
1695         for (i=0; i < m->basicblockcount; i++)
1696             printf("(%3i-%3i) ",i, ls->icount_block[i]);
1697         printf("\n");
1698         }
1699 #endif
1700
1701         /* extend lifetime over backedges (for the lsra version without exact
1702            liveness analysis)
1703            now iterate through lifetimes and expand them */
1704
1705         lifetimecount = 0;
1706         for(lt_index = 0 ;lt_index < ls->lifetimecount; lt_index++) {
1707                 if ( ls->lifetime[lt_index].type != -1) { /* used lifetime */
1708                         /* remember lt_index in lt_sorted */
1709                         ls->lt_used[lifetimecount++] = lt_index;
1710                         lt = &(ls->lifetime[lt_index]);
1711 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1712                         /* prevent conflicts between lifetimes of type long by increasing
1713                            the lifetime by one instruction
1714                            i.e.(ri/rj)  ...
1715                                (rk/rl)  ICMD_LNEG
1716                            with i==l and/or j==k
1717                            to resolve this during codegeneration a temporary register
1718                            would be needed */
1719                         if (lt->type == TYPE_LNG)
1720                                 lt->i_last_use++;
1721 #endif
1722
1723 /* distribute lifetimes to lt_int, lt_flt and lt_mem */
1724
1725                         lt->reg = -1;
1726
1727                         switch (lt->type) {
1728                         case TYPE_LNG:
1729 #if defined(HAS_4BYTE_STACKSLOT) && !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1730                                 flags = 0;
1731 #else
1732                                 flags = 1;
1733 #endif
1734                                 break;
1735
1736                         case TYPE_INT:
1737                         case TYPE_ADR:
1738                                 flags=1;
1739                                 break;
1740                         case TYPE_DBL:
1741                         case TYPE_FLT:
1742 #if defined(__I386__)
1743                                 /*
1744                                  * for i386 put all floats in memory
1745                                  */
1746                                 flags=0;
1747                                 break;
1748 #endif
1749                                 flags=2;
1750                                 break;
1751                         default:
1752                                 { log_text("Unknown Type\n"); assert(0); }
1753                         }
1754
1755                         switch (flags) {
1756                         case 0: /* lt_used[lt_used_index] -> lt_rest */
1757                                 ls->lt_mem[ ls->lt_mem_count++ ] = lt_index;
1758                                 break;
1759                         case 1: /* l->lifetimes -> lt_int */
1760                                 ls->lt_int[ ls->lt_int_count++ ] = lt_index;
1761                                 break;
1762                         case 2: /* l->lifetimes -> lt_flt */
1763                                 ls->lt_flt[ ls->lt_flt_count++ ] = lt_index;
1764                                 break;
1765                         }
1766
1767
1768                         if (lt->i_first_def == INT_MAX) {
1769 #ifdef LSRA_DEBUG_VERBOSE
1770                                 printf("Warning: var not defined! vi: %i start: %i end: %i\n",
1771                                            lt->v_index, lt->i_start, lt->i_end);
1772 #endif
1773                                 lt->bb_first_def = 0;
1774                                 lt->i_first_def = 0;
1775                         }
1776
1777                         lt->i_start = lt->i_first_def;
1778
1779                         if (lt->i_last_use == -2) {
1780 #ifdef LSRA_DEBUG_VERBOSE
1781                                 printf("Warning: Var not used! vi: %i start: %i end: %i\n",
1782                                            lt->v_index, lt->i_start, lt->i_end);
1783 #endif
1784                                 lt->bb_last_use = lt->bb_first_def;
1785                                 lt->i_last_use = lt->i_first_def;
1786                         }
1787
1788                         lt->i_end = lt->i_last_use;
1789
1790 #ifdef LSRA_DEBUG_VERBOSE
1791                         if (lt->i_start > lt->i_end)
1792                                 printf("Warning: last use before first def! vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end);
1793 #endif
1794
1795 #if !defined(LV)
1796                         if ((lt->bb_first_def != lt->bb_last_use) ||
1797                                 (lt->i_first_def == -1)) {
1798                                 /* Lifetime goes over more than one Basic Block ->  */
1799                                 /* check for necessary extension over backedges     */
1800                                 /* see lsra_get_backedges                           */
1801                                 /* Arguments are set "before" Block 0, so they have */
1802                                 /* a lifespan of more then one block, too           */
1803
1804                                 for (i=0; i < ls->backedge_count; i++) {
1805                                         if (!( (lt->bb_first_def > ls->backedge[i]->start) ||
1806                                                    (lt->bb_last_use < ls->backedge[i]->end) )) {
1807                                                 /* Live intervall intersects with a backedge */
1808                                                 /*      if (lt->bb_first_def <= ls->backedge[i]->start) */
1809                                                 if (lt->bb_last_use <= ls->backedge[i]->start)
1810                                                         lt->i_end =
1811                                                                 ls->icount_block[ls->backedge[i]->start] +
1812                                           m->basicblocks[ls->sorted[ls->backedge[i]->start]].icount;
1813                                         }
1814                                 }
1815                         }
1816 #endif /* !defined(LV) */
1817
1818 #ifdef USAGE_PER_INSTR
1819                         lt->usagecount = lt->usagecount / ( lt->i_end - lt->i_start + 1);
1820 #endif
1821                 }
1822         }
1823         ls->lifetimecount = lifetimecount;
1824 }
1825
1826 #ifdef LSRA_DEBUG_VERBOSE
1827 void print_lifetimes(jitdata *jd, int *lt, int lifetimecount)
1828 {
1829         struct lifetime *n;
1830         int lt_index;
1831         int type,flags,regoff,varkind;
1832
1833         lsradata     *ls;
1834         registerdata *rd;
1835
1836         ls = jd->ls;
1837         rd = jd->rd;
1838
1839         for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
1840                 n = &(ls->lifetime[lt[lt_index]]);
1841                 if (n->savedvar == SAVEDVAR)
1842                         printf("S");
1843                 else
1844                         printf(" ");
1845                 if (n->v_index < 0) { /* stackslot */
1846                         type = n->local_ss->s->type;
1847                         flags=n->local_ss->s->flags;
1848                         regoff=n->local_ss->s->regoff;
1849                         varkind=n->local_ss->s->varkind;
1850                 } else { /* local var */
1851                         if (rd->locals[n->v_index][n->type].type>=0) {
1852                                 type = rd->locals[n->v_index][n->type].type;
1853                                 flags=rd->locals[n->v_index][n->type].flags;
1854                                 regoff=rd->locals[n->v_index][n->type].regoff;
1855                                 varkind=-1;
1856                         } else
1857                                 { log_text("Type Data mismatch 3\n"); assert(0); }
1858                 }
1859 #if !defined(LV)
1860                 printf("i_Start: %3i(%3i,%3i) i_stop: %3i(%3i,%3i) reg: %3i VI: %3i type: %3i flags: %3i varkind: %3i usage: %3li ltflags: %xi \n",n->i_start, ls->sorted[n->bb_first_def], n->i_first_def,n->i_end, ls->sorted[n->bb_last_use], n->i_last_use,regoff,n->v_index,type,flags, varkind, n->usagecount, n->flags);
1861 #else
1862                 printf("i_Start: %3i i_stop: %3i reg: %3i VI: %3i type: %3i flags: %3i varkind: %3i usage: %3li ltflags: %xi \n",n->i_start, n->i_end, regoff,n->v_index,type,flags, varkind, n->usagecount, n->flags);
1863 #endif
1864         }
1865         printf( "%3i Lifetimes printed \n",lt_index);
1866 }
1867 #endif
1868
1869
1870
1871 /******************************************************************************
1872 Helpers for first LSRA Version without exact Liveness Analysis
1873  *****************************************************************************/
1874
1875 #if !defined(LV)
1876 bool lsra_join_ss( struct lsradata *ls, struct stackelement *in,
1877                                    struct stackelement *out, int join_flag) {
1878         struct lifetime *lt, *lto;
1879         struct stackslot *ss, *ss_last;
1880
1881
1882         if (in->varnum != out->varnum) {
1883                 lt = &(ls->lifetime[-in->varnum - 1]);
1884
1885 #ifdef LSRA_DEBUG_CHECK
1886                 if (join_flag == JOIN_BB)
1887                         if (lt->type == -1) {
1888                                 log_text("lsra_join_ss: lifetime for instack not found\n");
1889                                 assert(0);
1890                         }
1891 #endif
1892
1893                 if (out->varnum >= 0) { /* no lifetime for this slot till now */
1894                         lsra_add_ss(lt, out);
1895                 } else {
1896                         lto = &(ls->lifetime[-out->varnum - 1]);
1897                         if ((join_flag == JOIN_DUP) || (join_flag == JOIN_OP))
1898                                 if ( (lt->flags & JOIN_BB) || (lto->flags & JOIN_BB)) {
1899                                         return false;
1900                                 }
1901                         if (join_flag == JOIN_DUP)
1902                                 if ( (lt->flags & JOIN_OP) || (lto->flags & JOIN_OP)) {
1903                                         return false;
1904                                 }
1905 #ifdef LSRA_DEBUG_CHECK
1906                         if (lto->type == -1) {
1907                                 log_text("lsra_join_ss: lifetime for outstack not found\n");
1908                                 abort();
1909                         }
1910 #endif
1911 #ifdef LSRA_DEBUG_CHECK
1912                         if (lto->type != lt->type) {
1913                                 log_text("lsra_join_ss: in/out stack type mismatch\n");
1914                                 abort();
1915                         }
1916 #endif
1917
1918                         lt->flags |= JOINING;
1919
1920                         /* take Lifetime lto out of ls->lifetimes */
1921                         lto->type = -1;
1922
1923                         /* merge lto into lt of in */
1924
1925                         ss_last = ss = lto->local_ss;
1926                         while (ss != NULL) {
1927                                 ss_last = ss;
1928                                 ss->s->varnum = lt->v_index;
1929                                 ss = ss->next;
1930                         }
1931                         if (ss_last != NULL) {
1932                                 ss_last->next = lt->local_ss;
1933                                 lt->local_ss = lto->local_ss;
1934                         }
1935
1936                         lt->savedvar |= lto->savedvar;
1937                         lt->flags |= lto->flags | join_flag;
1938                         lt->usagecount += lto->usagecount;
1939
1940                         /*join of i_first_def and i_last_use */
1941                         if (lto->i_first_def < lt->i_first_def) {
1942                                 lt->i_first_def = lto->i_first_def;
1943                         }
1944                         if (lto->i_last_use > lt->i_last_use) {
1945                                 lt->i_last_use = lto->i_last_use;
1946                         }
1947                 }
1948         }
1949         return true;
1950 }
1951
1952 /* join instack of Basic Block b_index with outstack of predecessors */
1953 void lsra_join_lifetimes(jitdata *jd,int b_index) {
1954         methodinfo *m;
1955         lsradata *ls;
1956         struct stackelement *in, *i, *out;
1957     struct _list *pred;
1958
1959         m  = jd->m;
1960         ls = jd->ls;
1961
1962         /* do not join instack of Exception Handler */
1963         if (m->basicblocks[b_index].type == BBTYPE_EXH)
1964                 return;
1965         in=m->basicblocks[b_index].instack;
1966         /* do not join first instack element of a subroutine header */
1967         if (m->basicblocks[b_index].type == BBTYPE_SBR)
1968                 in=in->prev;
1969
1970         if (in != NULL) {
1971                 for (pred = ls->pred[b_index]; pred != NULL; pred = pred->next) {
1972                         out = m->basicblocks[pred->value].outstack;
1973                         for (i=in; (i != NULL); i = i->prev, out=out->prev) {
1974                                 lsra_join_ss(ls, i, out, JOIN_BB);
1975                         }
1976                 }
1977         }
1978 }
1979
1980 struct stackslot *lsra_make_ss(stackelement_t* s, int bb_index)
1981 {
1982         struct stackslot *ss;
1983
1984         ss = DNEW(struct stackslot);
1985         ss->bb = bb_index;
1986         ss->s  = s;
1987         return ss;
1988 }
1989
1990 void lsra_add_ss(struct lifetime *lt, stackelement_t* s) {
1991         struct stackslot *ss;
1992
1993         /* Stackslot not in list? */
1994         if (s->varnum != lt->v_index) {
1995                 ss = DNEW(struct stackslot);
1996                 ss->s = s;
1997                 ss->s->varnum = lt->v_index;
1998                 ss->next = lt->local_ss;
1999                 lt->local_ss = ss;
2000                 if (s != NULL)
2001                         lt->savedvar |= s->flags & SAVEDVAR;
2002                 if (s != NULL)
2003                         lt->type = s->type;
2004         }
2005 }
2006
2007 struct lifetime *get_ss_lifetime(lsradata *ls, stackelement_t* s) {
2008         struct lifetime *n;
2009
2010         if (s->varnum >= 0) { /* new stackslot lifetime */
2011 #ifdef LSRA_DEBUG_CHECK_VERBOSE
2012                 if (-ls->v_index - 1 >= ls->maxlifetimes) {
2013                         printf("%i %i\n", -ls->v_index - 1, ls->maxlifetimes);
2014                 }
2015 #endif
2016                 _LSRA_ASSERT(-ls->v_index - 1 < ls->maxlifetimes);
2017
2018                 n = &(ls->lifetime[-ls->v_index - 1]);
2019                 n->type = s->type;
2020                 n->v_index = ls->v_index--;
2021                 n->usagecount = 0;
2022
2023                 n->bb_last_use  = -1;
2024                 n->bb_first_def = -1;
2025                 n->i_last_use   = -2; /* At -1 param init happens, so -2 is below all
2026                                                                  possible instruction indices */
2027                 n->i_first_def  = INT_MAX;
2028                 n->local_ss = NULL;
2029                 n->savedvar = 0;
2030                 n->flags    = 0;
2031         } else
2032                 n = &(ls->lifetime[-s->varnum - 1]);
2033
2034         lsra_add_ss( n, s);
2035         return n;
2036 }
2037
2038 #define IS_TEMP_VAR(s) (((s)->varkind != ARGVAR) && ((s)->varkind != LOCALVAR))
2039
2040 #define lsra_join_3_stack(ls, dst, src1, src2, join_type) \
2041         if ( IS_TEMP_VAR(dst) ) { \
2042                 join_ret = false; \
2043                 if ( IS_TEMP_VAR(src1) && ((src1)->type == (dst)->type)) { \
2044                         join_ret = lsra_join_ss(ls, dst, src1, join_type);                                                              \
2045                 } \
2046                 if ((!join_ret) && IS_TEMP_VAR(src2) && ((src2)->type == (dst)->type)) { \
2047                         lsra_join_ss(ls, dst, src2, join_type); \
2048                 } \
2049         }
2050
2051 #define lsra_join_2_stack(ls, dst, src, join_type) \
2052         if ( IS_TEMP_VAR(dst) ) { \
2053                 if ( (IS_TEMP_VAR(src)) && ((src)->type == (dst)->type)) {      \
2054                         lsra_join_ss(ls, dst, src, join_type); \
2055                 } \
2056         }
2057
2058 #define lsra_join_dup(ls, s1, s2, s3) {                            \
2059                 if (IS_TEMP_VAR(s1)) {                                             \
2060                         join_ret = false;                                                  \
2061                         if (IS_TEMP_VAR(s2))                                   \
2062                                 join_ret = lsra_join_ss(ls, s1, s2, JOIN); \
2063                                                  /* undangerous join!*/\
2064                         if (IS_TEMP_VAR(s3)) {                                 \
2065                                 if (join_ret)   /* first join succesfull -> second of type */ \
2066                                                     /* JOIN_DUP */                      \
2067                     lsra_join_ss(ls, s1, s3, JOIN_DUP); \
2068                                 else                                                                    \
2069                         lsra_join_ss(ls, s1, s3, JOIN); /* first join did not */ \
2070                                                           /* happen -> second undangerous */ \
2071                     }                                                                           \
2072                 }                                                                                       \
2073         if (IS_TEMP_VAR(s2) && IS_TEMP_VAR(s3))         \
2074                 lsra_join_ss(ls, s2, s3, JOIN_DUP);                 \
2075         }
2076
2077 #define lsra_new_stack(ls, s, block, instr) \
2078         if ((s)->varkind != ARGVAR) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
2079 void _lsra_new_stack(lsradata *ls, stackelement_t* s, int block, int instr, int store)
2080 {
2081         struct lifetime *n;
2082
2083         if (s->varkind == LOCALVAR) {
2084                 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_STORE);
2085         } else /* if (s->varkind != ARGVAR) */ {
2086
2087                 n=get_ss_lifetime(ls, s);
2088
2089                 if (store == LSRA_BB_IN)
2090                         n->flags |= JOIN_BB;
2091                 /* remember first def -> overwrite everytime */
2092                 n->bb_first_def = ls->sorted_rev[block];
2093                 n->i_first_def = ls->icount_block[ls->sorted_rev[block]] + instr;
2094
2095                 n->usagecount+=ls->nesting[ls->sorted_rev[block]];
2096         }
2097 }
2098
2099 #define lsra_from_stack(ls, s, block, instr) \
2100         if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
2101 #define lsra_pop_from_stack(ls, s, block, instr) \
2102         if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
2103 void _lsra_from_stack(lsradata *ls, stackelement_t* s, int block, int instr, int store)
2104 {
2105         struct lifetime *n;
2106
2107         if (s->varkind == LOCALVAR) {
2108                 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
2109         } else /* if (s->varkind != ARGVAR) */ {
2110                 if (s->varkind == STACKVAR )
2111                         /* No STACKVARS possible with lsra! */
2112                         s->varkind = TEMPVAR;
2113
2114                 n=get_ss_lifetime(ls, s);
2115
2116                 if (store == LSRA_BB_OUT)
2117                         n->flags |= JOIN_BB;
2118                 if (n->flags & JOINING)
2119                         n->flags &= ~JOINING;
2120                 n->usagecount+=ls->nesting[ls->sorted_rev[block]];
2121
2122                 /* remember last USE, so only write, if USE Field is undefined (==-1) */
2123                 if (n->bb_last_use == -1) {
2124                         n->bb_last_use = ls->sorted_rev[block];
2125                         n->i_last_use = ls->icount_block[ls->sorted_rev[block]] + instr;
2126                 }
2127         }
2128 }
2129
2130 void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr,
2131                                           int store)
2132 {
2133         struct lifetime *n;
2134
2135         n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);
2136
2137         if (n->type == -1) { /* new local lifetime */
2138                 n->local_ss=NULL;
2139                 n->v_index=v_index;
2140                 n->type=type;
2141                 n->savedvar = SAVEDVAR;
2142                 n->flags = 0;
2143                 n->usagecount = 0;
2144
2145                 n->bb_last_use = -1;
2146                 n->bb_first_def = -1;
2147                 n->i_last_use = -2;
2148                 n->i_first_def = INT_MAX;
2149         }
2150         n->usagecount+=ls->nesting[ls->sorted_rev[block]];
2151         /* add access at (block, instr) to instruction list */
2152         /* remember last USE, so only write, if USE Field is undefined (==-1)   */
2153         /* count store as use, too -> defined and not used vars would overwrite */
2154         /* other vars */
2155         if (n->bb_last_use == -1) {
2156                 n->bb_last_use = ls->sorted_rev[block];
2157                 n->i_last_use = ls->icount_block[ls->sorted_rev[block]] + instr;
2158         }
2159         if (store == LSRA_STORE) {
2160                 /* store == LSRA_STORE, remember first def -> overwrite everytime */
2161                 n->bb_first_def = ls->sorted_rev[block];
2162                 n->i_first_def = ls->icount_block[ls->sorted_rev[block]] + instr;
2163         }
2164 }
2165
2166 #ifdef LSRA_DEBUG_VERBOSE
2167 void lsra_dump_stack(stackelement_t* s)
2168 {
2169         while (s!=NULL) {
2170                 printf("%p(R%3i N%3i K%3i T%3i F%3i) ",(void *)s,s->regoff, s->varnum,
2171                            s->varkind, s->type, s->flags);
2172                 s=s->prev;
2173         }
2174         printf("\n");
2175 }
2176 #endif
2177
2178
2179 void lsra_scan_registers_canditates(jitdata *jd, int b_index)
2180 {
2181 /*      methodinfo         *lm; */
2182         builtintable_entry *bte;
2183         methoddesc         *md;
2184         int i;
2185         int opcode;
2186         int iindex;
2187         stackelement_t*    src;
2188         stackelement_t*    dst;
2189         instruction *iptr;
2190         bool join_ret; /* for lsra_join* Macros */
2191         methodinfo *m;
2192         lsradata *ls;
2193
2194         m  = jd->m;
2195         ls = jd->ls;
2196
2197     /* get instruction count for BB and remember the max instruction count */
2198         /* of all BBs */
2199         iindex = m->basicblocks[b_index].icount - 1;
2200
2201         src = m->basicblocks[b_index].instack;
2202         if (m->basicblocks[b_index].type != BBTYPE_STD) {
2203                 lsra_new_stack(ls, src, b_index, 0);
2204                 src = src->prev;
2205         }
2206         for (;src != NULL; src=src->prev) {
2207 /*******************************************************************************
2208 Check this - ? For every incoming Stack Slot a lifetime has to be created ?
2209 *******************************************************************************/
2210                         _lsra_new_stack(ls, src, b_index, 0, LSRA_BB_IN);
2211         }
2212         src = m->basicblocks[b_index].outstack;
2213         for (;src != NULL; src=src->prev) {
2214                         _lsra_from_stack(ls, src, b_index, iindex, LSRA_BB_OUT);
2215         }
2216
2217         /* set iptr to last instruction of BB */
2218         iptr = m->basicblocks[b_index].iinstr + iindex;
2219
2220         for (;iindex >= 0; iindex--, iptr--)  {
2221
2222                 /* get source and destination Stack for the current instruction     */
2223                 /* destination stack is available as iptr->dst                      */
2224
2225                 dst = iptr->dst;
2226
2227                 /* source stack is either the destination stack of the previos      */
2228                 /* instruction, or the basicblock instack for the first instruction */
2229
2230                 if (iindex) /* != 0 is > 0 here, since iindex ist always >= 0 */
2231                         src=(iptr-1)->dst;
2232                 else
2233                         src=m->basicblocks[b_index].instack;
2234                 opcode = iptr->opc;
2235
2236
2237                 switch (opcode) {
2238
2239                         /* pop 0 push 0 */
2240                 case ICMD_RET:
2241                         /* local read (return adress) */
2242                         lsra_usage_local(ls, iptr->op1, TYPE_ADR, b_index, iindex,
2243                                                          LSRA_LOAD);
2244                         break;
2245                 case ICMD_NOP:
2246 /*              case ICMD_ELSE_ICONST: */
2247                 case ICMD_CHECKNULL:
2248                 case ICMD_JSR:
2249                 case ICMD_RETURN:
2250                 case ICMD_GOTO:
2251                 case ICMD_PUTSTATICCONST:
2252                 case ICMD_INLINE_START:
2253                 case ICMD_INLINE_END:
2254                 case ICMD_INLINE_GOTO:
2255                         break;
2256
2257                 case ICMD_IINC:
2258                         /* local = local+<const> */
2259                         lsra_usage_local(ls, iptr->op1, TYPE_INT, b_index, iindex,
2260                                                          LSRA_LOAD);
2261                         lsra_usage_local(ls, iptr->op1, TYPE_INT, b_index, iindex,
2262                                                          LSRA_STORE);
2263                         break;
2264
2265                         /* pop 0 push 1 const: const->stack */
2266                 case ICMD_ICONST:
2267                 case ICMD_LCONST:
2268                 case ICMD_FCONST:
2269                 case ICMD_DCONST:
2270                 case ICMD_ACONST:
2271                         /* new stack slot */
2272                         lsra_new_stack(ls, dst, b_index, iindex);
2273                         break;
2274
2275                         /* pop 0 push 1 load: local->stack */
2276                 case ICMD_ILOAD:
2277                 case ICMD_LLOAD:
2278                 case ICMD_FLOAD:
2279                 case ICMD_DLOAD:
2280                 case ICMD_ALOAD:
2281                         if (dst->varkind != LOCALVAR) {
2282                                 /* local->value on stack */
2283                                 lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD, b_index,
2284                                                                  iindex, LSRA_LOAD);
2285                                 lsra_new_stack(ls, dst, b_index, iindex); /* value->stack */
2286                         } else /* if (dst->varnum != iptr->op1) */ {
2287                                 /* local -> local */
2288                                 lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD, b_index,
2289                                                                  iindex,LSRA_LOAD); /* local->value */
2290                                 lsra_usage_local(ls, dst->varnum, opcode - ICMD_ILOAD, b_index,
2291                                                                  iindex, LSRA_STORE); /* local->value */
2292                         }
2293
2294                         break;
2295
2296                         /* pop 2 push 1 */
2297                         /* Stack(arrayref,index)->stack */
2298                 case ICMD_IALOAD:
2299                 case ICMD_LALOAD:
2300                 case ICMD_FALOAD:
2301                 case ICMD_DALOAD:
2302                 case ICMD_AALOAD:
2303
2304                 case ICMD_BALOAD:
2305                 case ICMD_CALOAD:
2306                 case ICMD_SALOAD:
2307                         /* stack->index */
2308                         lsra_from_stack(ls, src, b_index, iindex);
2309                         /* stack->arrayref */
2310                         lsra_from_stack(ls, src->prev, b_index, iindex);
2311                         /* arrayref[index]->stack */
2312                         lsra_new_stack(ls, dst, b_index, iindex);
2313                         break;
2314
2315                         /* pop 3 push 0 */
2316                         /* stack(arrayref,index,value)->arrayref[index]=value */
2317                 case ICMD_IASTORE:
2318                 case ICMD_LASTORE:
2319                 case ICMD_FASTORE:
2320                 case ICMD_DASTORE:
2321                 case ICMD_AASTORE:
2322
2323                 case ICMD_BASTORE:
2324                 case ICMD_CASTORE:
2325                 case ICMD_SASTORE:
2326
2327                         lsra_from_stack(ls, src,b_index, iindex); /* stack -> value */
2328                         lsra_from_stack(ls, src->prev, b_index, iindex); /* stack -> index*/
2329                         /* stack -> arrayref */
2330                         lsra_from_stack(ls, src->prev->prev, b_index, iindex);
2331                         break;
2332
2333                         /* pop 1 push 0 store: stack -> local */
2334                 case ICMD_ISTORE:
2335                 case ICMD_LSTORE:
2336                 case ICMD_FSTORE:
2337                 case ICMD_DSTORE:
2338                 case ICMD_ASTORE:
2339                         if (src->varkind != LOCALVAR) {
2340                                 lsra_from_stack(ls, src, b_index, iindex); /* stack -> value */
2341                                 lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE, b_index,
2342                                                                  iindex, LSRA_STORE); /* local->value */
2343                         } else /* if (src->varnum != iptr->op1) */ {
2344                                 lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE, b_index,
2345                                                                  iindex, LSRA_STORE); /* local->value */
2346                                 lsra_usage_local(ls, src->varnum, opcode-ICMD_ISTORE, b_index,
2347                                                                  iindex, LSRA_LOAD); /* local->value */
2348                         }
2349                         break;
2350
2351                         /* pop 1 push 0 */
2352                 case ICMD_POP: /* throw away a stackslot */
2353                         /* TODO: check if used anyway (DUP...) and change codegen to */
2354                         /*       ignore this stackslot */
2355                         lsra_pop_from_stack(ls, src, b_index, iindex);
2356                         break;
2357
2358                         /* pop 1 push 0 */
2359                 case ICMD_IRETURN:
2360                 case ICMD_LRETURN:
2361                 case ICMD_FRETURN:
2362                 case ICMD_DRETURN:
2363                 case ICMD_ARETURN: /* stack(value) -> [empty]    */
2364
2365                 case ICMD_ATHROW:  /* stack(objref) -> undefined */
2366
2367                 case ICMD_PUTSTATIC: /* stack(value) -> static_field */
2368                 case ICMD_PUTFIELDCONST:
2369
2370                         /* pop 1 push 0 branch */
2371                 case ICMD_IFNULL: /* stack(value) -> branch? */
2372                 case ICMD_IFNONNULL:
2373
2374                 case ICMD_IFEQ:
2375                 case ICMD_IFNE:
2376                 case ICMD_IFLT:
2377                 case ICMD_IFGE:
2378                 case ICMD_IFGT:
2379                 case ICMD_IFLE:
2380
2381                 case ICMD_IF_LEQ:
2382                 case ICMD_IF_LNE:
2383                 case ICMD_IF_LLT:
2384                 case ICMD_IF_LGE:
2385                 case ICMD_IF_LGT:
2386                 case ICMD_IF_LLE:
2387
2388                         /* pop 1 push 0 table branch */
2389                 case ICMD_TABLESWITCH:
2390                 case ICMD_LOOKUPSWITCH:
2391
2392                 case ICMD_MONITORENTER:
2393                 case ICMD_MONITOREXIT:
2394                         lsra_from_stack(ls, src, b_index, iindex); /* stack -> value */
2395                         break;
2396
2397                         /* pop 2 push 0 */
2398                 case ICMD_POP2: /* throw away 2 stackslots */
2399                         /* TODO: check if used anyway (DUP...) and change codegen to */
2400                         /*       ignore this stackslot */
2401                         lsra_pop_from_stack(ls, src, b_index, iindex);
2402                         lsra_pop_from_stack(ls, src->prev, b_index, iindex);
2403                         break;
2404
2405                         /* pop 2 push 0 branch */
2406
2407                 case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
2408                 case ICMD_IF_ICMPNE:
2409                 case ICMD_IF_ICMPLT:
2410                 case ICMD_IF_ICMPGE:
2411                 case ICMD_IF_ICMPGT:
2412                 case ICMD_IF_ICMPLE:
2413
2414                 case ICMD_IF_LCMPEQ:
2415                 case ICMD_IF_LCMPNE:
2416                 case ICMD_IF_LCMPLT:
2417                 case ICMD_IF_LCMPGE:
2418                 case ICMD_IF_LCMPGT:
2419                 case ICMD_IF_LCMPLE:
2420
2421                 case ICMD_IF_ACMPEQ:
2422                 case ICMD_IF_ACMPNE:
2423
2424                         /* pop 2 push 0 */
2425                 case ICMD_PUTFIELD: /* stack(objref,value) -> objref = value */
2426
2427                 case ICMD_IASTORECONST:
2428                 case ICMD_LASTORECONST:
2429                 case ICMD_AASTORECONST:
2430                 case ICMD_BASTORECONST:
2431                 case ICMD_CASTORECONST:
2432                 case ICMD_SASTORECONST:
2433                         lsra_from_stack(ls, src, b_index, iindex);         /* stack -> value*/
2434                         lsra_from_stack(ls, src->prev, b_index, iindex);
2435                         break;
2436
2437                         /* pop 0 push 1 dup */
2438                 case ICMD_DUP: /* src == dst->prev, src -> dst */
2439                         /* lsra_from_stack(ls, src,b_index,iindex);*/
2440                         lsra_new_stack(ls, dst, b_index, iindex);
2441
2442 #ifdef JOIN_DUP_STACK
2443                         /* src is identical to dst->prev */
2444                         lsra_join_2_stack(ls, src, dst, JOIN_DUP);
2445 #endif
2446                         break;
2447
2448                         /* pop 0 push 2 dup */
2449                 case ICMD_DUP2:
2450                         /* lsra_from_stack(ls, src,b_index, iindex); */
2451                         /* lsra_from_stack(ls, src->prev, b_index, iindex); */
2452                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2453                         lsra_new_stack(ls, dst, b_index, iindex);
2454
2455 #ifdef JOIN_DUP_STACK
2456                         lsra_join_2_stack(ls, src, dst, JOIN_DUP);
2457                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN_DUP);
2458                         /* src is identical to dst->prev->prev */
2459                         /* src->prev is identical to dst->prev->prev->prev */
2460 #endif
2461                         break;
2462
2463                         /* pop 2 push 3 dup */
2464                 case ICMD_DUP_X1:
2465                         lsra_from_stack(ls, src, b_index, iindex+1);
2466                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2467                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2468                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2469                         lsra_new_stack(ls, dst, b_index, iindex);
2470 #ifdef JOIN_DUP_STACK
2471                         lsra_join_dup(ls, src, dst, dst->prev->prev);
2472                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN);
2473 #endif
2474                         break;
2475
2476                         /* pop 3 push 4 dup */
2477                 case ICMD_DUP_X2:
2478                         lsra_from_stack(ls, src,b_index, iindex+1);
2479                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2480                         lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
2481                         lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
2482                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2483                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2484                         lsra_new_stack(ls, dst, b_index, iindex);
2485
2486 #ifdef JOIN_DUP_STACK
2487                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev);
2488                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN);
2489                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2490 #endif
2491                         break;
2492
2493                         /* pop 3 push 5 dup */
2494                 case ICMD_DUP2_X1:
2495                         lsra_from_stack(ls, src, b_index, iindex+1);
2496                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2497                         lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
2498                         lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index, iindex);
2499                         lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
2500                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2501                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2502                         lsra_new_stack(ls, dst, b_index, iindex);
2503
2504 #ifdef JOIN_DUP_STACK
2505                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev);
2506                         lsra_join_dup(ls, src->prev, dst->prev,
2507                                                   dst->prev->prev->prev->prev);
2508                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2509 #endif
2510                         break;
2511
2512                         /* pop 4 push 6 dup */
2513                 case ICMD_DUP2_X2:
2514                         lsra_from_stack(ls, src, b_index, iindex+1);
2515                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2516                         lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
2517                         lsra_from_stack(ls, src->prev->prev->prev, b_index, iindex+1);
2518                         lsra_new_stack(ls, dst->prev->prev->prev->prev->prev, b_index,
2519                                                    iindex);
2520                         lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index, iindex);
2521                         lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
2522                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2523                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2524                         lsra_new_stack(ls, dst, b_index, iindex);
2525
2526 #ifdef JOIN_DUP_STACK
2527                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev->prev);
2528                         lsra_join_dup(ls, src->prev, dst->prev,
2529                                                   dst->prev->prev->prev->prev->prev);
2530                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2531                         lsra_join_2_stack(ls, src->prev->prev->prev, dst->prev->prev->prev,
2532                                                           JOIN);
2533 #endif
2534                         break;
2535
2536                         /* pop 2 push 2 swap */
2537                 case ICMD_SWAP:
2538                         lsra_from_stack(ls, src, b_index, iindex+1);
2539                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2540                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2541                         lsra_new_stack(ls, dst, b_index, iindex);
2542
2543                         lsra_join_2_stack(ls, src->prev, dst, JOIN);
2544                         lsra_join_2_stack(ls, src, dst->prev, JOIN);
2545
2546                         break;
2547
2548                         /* pop 2 push 1 */
2549
2550                 case ICMD_LADD:
2551                 case ICMD_LSUB:
2552                 case ICMD_LMUL:
2553
2554                 case ICMD_LOR:
2555                 case ICMD_LAND:
2556                 case ICMD_LXOR:
2557
2558                 case ICMD_LSHL:
2559                 case ICMD_LSHR:
2560                 case ICMD_LUSHR:
2561
2562                 case ICMD_IADD:
2563                 case ICMD_IMUL:
2564
2565                 case ICMD_ISHL:
2566                 case ICMD_ISHR:
2567                 case ICMD_IUSHR:
2568                 case ICMD_IAND:
2569                 case ICMD_IOR:
2570                 case ICMD_IXOR:
2571
2572
2573                 case ICMD_FADD:
2574                 case ICMD_FSUB:
2575                 case ICMD_FMUL:
2576
2577                 case ICMD_DADD:
2578                 case ICMD_DSUB:
2579                 case ICMD_DMUL:
2580                 case ICMD_DDIV:
2581                 case ICMD_DREM:
2582                         lsra_from_stack(ls, src, b_index, iindex);
2583                         lsra_from_stack(ls, src->prev, b_index, iindex);
2584                         lsra_new_stack(ls, dst, b_index, iindex);
2585 #ifdef JOIN_DEST_STACK
2586                         lsra_join_3_stack(ls, dst, src->prev, src, JOIN_OP);
2587 #endif
2588                         break;
2589
2590                 case ICMD_ISUB:
2591                         lsra_from_stack(ls, src, b_index, iindex);
2592                         lsra_from_stack(ls, src->prev,b_index,iindex);
2593                         lsra_new_stack(ls, dst, b_index, iindex);
2594 #ifdef JOIN_DEST_STACK
2595                         lsra_join_2_stack(ls, src, dst, JOIN_OP);
2596 #endif
2597                         break;
2598
2599                 case ICMD_LDIV:
2600                 case ICMD_LREM:
2601
2602                 case ICMD_IDIV:
2603                 case ICMD_IREM:
2604
2605                 case ICMD_FDIV:
2606                 case ICMD_FREM:
2607
2608                 case ICMD_LCMP:
2609                 case ICMD_FCMPL:
2610                 case ICMD_FCMPG:
2611                 case ICMD_DCMPL:
2612                 case ICMD_DCMPG:
2613                         lsra_from_stack(ls, src, b_index, iindex);
2614                         lsra_from_stack(ls, src->prev, b_index, iindex);
2615                         lsra_new_stack(ls, dst, b_index, iindex);
2616                         break;
2617
2618                         /* pop 1 push 1 */
2619                 case ICMD_LADDCONST:
2620                 case ICMD_LSUBCONST:
2621                 case ICMD_LMULCONST:
2622                 case ICMD_LMULPOW2:
2623                 case ICMD_LDIVPOW2:
2624                 case ICMD_LREMPOW2:
2625                 case ICMD_LANDCONST:
2626                 case ICMD_LORCONST:
2627                 case ICMD_LXORCONST:
2628                 case ICMD_LSHLCONST:
2629                 case ICMD_LSHRCONST:
2630                 case ICMD_LUSHRCONST:
2631
2632                 case ICMD_IADDCONST:
2633                 case ICMD_ISUBCONST:
2634                 case ICMD_IMULCONST:
2635                 case ICMD_IMULPOW2:
2636                 case ICMD_IDIVPOW2:
2637                 case ICMD_IREMPOW2:
2638                 case ICMD_IANDCONST:
2639                 case ICMD_IORCONST:
2640                 case ICMD_IXORCONST:
2641                 case ICMD_ISHLCONST:
2642                 case ICMD_ISHRCONST:
2643                 case ICMD_IUSHRCONST:
2644
2645 /*              case ICMD_IFEQ_ICONST: */
2646 /*              case ICMD_IFNE_ICONST: */
2647 /*              case ICMD_IFLT_ICONST: */
2648 /*              case ICMD_IFGE_ICONST: */
2649 /*              case ICMD_IFGT_ICONST: */
2650 /*              case ICMD_IFLE_ICONST: */
2651
2652                 case ICMD_INEG:
2653                 case ICMD_INT2BYTE:
2654                 case ICMD_INT2CHAR:
2655                 case ICMD_INT2SHORT:
2656                 case ICMD_LNEG:
2657                 case ICMD_FNEG:
2658                 case ICMD_DNEG:
2659
2660                 case ICMD_I2L:
2661                 case ICMD_I2F:
2662                 case ICMD_I2D:
2663                 case ICMD_L2I:
2664                 case ICMD_L2F:
2665                 case ICMD_L2D:
2666                 case ICMD_F2I:
2667                 case ICMD_F2L:
2668                 case ICMD_F2D:
2669                 case ICMD_D2I:
2670                 case ICMD_D2L:
2671                 case ICMD_D2F:
2672
2673                 case ICMD_CHECKCAST:
2674                         lsra_from_stack(ls, src, b_index, iindex);
2675                         lsra_new_stack(ls, dst, b_index, iindex);
2676 #ifdef JOIN_DEST_STACK
2677                         lsra_join_2_stack(ls, src, dst, JOIN_OP);
2678 #endif
2679                         break;
2680
2681                         /* TODO: check if for these ICMDs JOIN_DEST_STACK works, too! */
2682                 case ICMD_ARRAYLENGTH:
2683                 case ICMD_INSTANCEOF:
2684
2685                 case ICMD_NEWARRAY:
2686                 case ICMD_ANEWARRAY:
2687
2688                 case ICMD_GETFIELD:
2689                         lsra_from_stack(ls, src, b_index, iindex);
2690                         lsra_new_stack(ls, dst, b_index, iindex);
2691                         break;
2692
2693                         /* pop 0 push 1 */
2694                 case ICMD_GETSTATIC:
2695
2696                 case ICMD_NEW:
2697                         lsra_new_stack(ls, dst, b_index, iindex);
2698                         break;
2699
2700                         /* pop many push any */
2701
2702                 case ICMD_INVOKESTATIC:
2703                 case ICMD_INVOKESPECIAL:
2704                 case ICMD_INVOKEVIRTUAL:
2705                 case ICMD_INVOKEINTERFACE:
2706                         INSTRUCTION_GET_METHODDESC(iptr,md);
2707                         i = md->paramcount;
2708                         while (--i >= 0) {
2709                                 lsra_from_stack(ls, src, b_index, iindex);
2710                                 src = src->prev;
2711                         }
2712                         if (md->returntype.type != TYPE_VOID)
2713                                 lsra_new_stack(ls, dst, b_index, iindex);
2714                         break;
2715
2716
2717                 case ICMD_BUILTIN:
2718                         bte = iptr->val.a;
2719                         md = bte->md;
2720                         i = md->paramcount;
2721                         while (--i >= 0) {
2722                                 lsra_from_stack(ls, src, b_index, iindex);
2723                                 src = src->prev;
2724                         }
2725                         if (md->returntype.type != TYPE_VOID)
2726                                 lsra_new_stack(ls, dst, b_index, iindex);
2727                         break;
2728
2729                 case ICMD_MULTIANEWARRAY:
2730                         i = iptr->op1;
2731                         while (--i >= 0) {
2732                                 lsra_from_stack(ls, src, b_index, iindex);
2733                                 src = src->prev;
2734                         }
2735                         lsra_new_stack(ls, dst, b_index, iindex);
2736                         break;
2737
2738                 default:
2739                         exceptions_throw_internalerror("Unknown ICMD %d during register allocation",
2740                                                                                    iptr->opc);
2741                         return;
2742                 } /* switch */
2743         }
2744 }
2745 #endif /* defined(LV) */
2746
2747
2748 /*
2749  * These are local overrides for various environment variables in Emacs.
2750  * Please do not remove this and leave it at the end of the file, where
2751  * Emacs will automagically detect them.
2752  * ---------------------------------------------------------------------
2753  * Local variables:
2754  * mode: c
2755  * indent-tabs-mode: t
2756  * c-basic-offset: 4
2757  * tab-width: 4
2758  * End:
2759  * vim:noexpandtab:sw=4:ts=4:
2760  */