src/vm/jit/allocator/lsra.c

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