src/vm/jit/allocator/lsra.c

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