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.hpp"
  39
  40 #include "toolbox/logging.hpp"
  41
  42 #include "vm/jit/builtin.hpp"
  43 #include "vm/exceptions.hpp"
  44 #include "vm/resolve.hpp"
  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         registerdata *rd;
1344         lsradata     *ls;
1345
1346         rd = jd->rd;
1347         ls = jd->ls;
1348
1349         fmem = DNEW(struct freemem);
1350         fmem->off  = -1;
1351         fmem->next = NULL;
1352
1353         for (lt_index = 0; lt_index < lifetimecount; lt_index ++) {
1354                 lt = &(ls->lifetime[lifet[lt_index]]);
1355 #ifdef LSRA_MEMORY
1356                 lt->reg = -1;
1357 #endif
1358                 if (lt->reg == -1) {
1359                         flags = INMEMORY;
1360                         regoff = lsra_getmem(lt, fmem, mem_use);
1361                 } else {
1362                         flags  = lt->savedvar;
1363                         regoff = lt->reg;
1364                 }
1365
1366                 if (lt->v_index < 0) {
1367                         for (n = lt->local_ss; n != NULL; n = n->next) {
1368                                 lsra_setflags(&(n->s->flags), flags);
1369                                 n->s->regoff = regoff;
1370                         }
1371                 } else { /* local var */
1372                         if (rd->locals[lt->v_index][lt->type].type >= 0) {
1373                                 rd->locals[lt->v_index][lt->type].flags  = flags;
1374                                 rd->locals[lt->v_index][lt->type].regoff = regoff;
1375                         } else {
1376                                 log_text("Type Data mismatch\n");
1377                                 abort();
1378                         }
1379                 }
1380                 lt->reg = regoff;
1381         }
1382 }
1383
1384 void lsra_setflags(int *flags, int newflags)
1385 {
1386         if ( newflags & INMEMORY)
1387                 *flags |= INMEMORY;
1388         else
1389                 *flags &= ~INMEMORY;
1390
1391         if (newflags & SAVEDVAR)
1392                 *flags |= SAVEDVAR;
1393 }
1394
1395 int lsra_getmem(struct lifetime *lt, struct freemem *fmem, int *mem_use)
1396 {
1397         struct freemem *fm, *p;
1398
1399         /* no Memory Slot allocated till now or all are still live */
1400         if ((fmem->next == NULL) || (fmem->next->end > lt->i_start)) {
1401                 fm=lsra_getnewmem(mem_use);
1402         } else {
1403                 /* Memoryslot free */
1404                 fm = fmem->next;
1405                 fmem->next = fm->next;
1406                 fm->next = NULL;
1407         }
1408         fm->end = lt->i_end;
1409         for (p = fmem; (p->next != NULL) && (p->next->end < fm->end); p = p->next);
1410         fm->next = p->next;
1411         p->next = fm;
1412         return fm->off;
1413 }
1414
1415 struct freemem *lsra_getnewmem(int *mem_use)
1416 {
1417         struct freemem *fm;
1418
1419         fm = DNEW(struct freemem);
1420         fm->next = NULL;
1421         fm->off = *mem_use;
1422         (*mem_use)++;
1423         return fm;
1424 }
1425
1426 void _lsra_main(jitdata *jd, int *lifet, int lifetimecount,
1427                                 struct lsra_register *reg, int *reg_use)
1428 {
1429         struct lifetime *lt;
1430         int lt_index;
1431         int reg_index;
1432         int regsneeded;
1433         bool temp; /* reg from temp registers (true) or saved registers (false) */
1434         methodinfo *m;
1435         lsradata *ls;
1436
1437         m  = jd->m;
1438         ls = jd->ls;
1439
1440 #if !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1441         regsneeded = 0;
1442 #endif
1443         if ((reg->tmp_top+reg->sav_top) == 0) {
1444
1445                 /* no registers available */
1446                 for (lt_index = 0; lt_index < lifetimecount; lt_index++)
1447                         ls->lifetime[lifet[lt_index]].reg = -1;
1448                 return;
1449         }
1450
1451         ls->active_tmp_top = 0;
1452         ls->active_sav_top = 0;
1453
1454         for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
1455                 lt = &(ls->lifetime[lifet[lt_index]]);
1456
1457 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1458         regsneeded = (lt->type == TYPE_LNG)?1:0;
1459 #endif
1460
1461                 lsra_expire_old_intervalls(jd, lt, reg);
1462                 reg_index = -1;
1463                 temp = false;
1464                 if (lt->savedvar || code_is_leafmethod(code)) {
1465                         /* use Saved Reg (in case of leafmethod all regs are saved regs) */
1466                         if (reg->sav_top > regsneeded) {
1467 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1468                                 if (regsneeded)
1469                                         reg_index = PACK_REGS(reg->sav_reg[--reg->sav_top],
1470                                                                                   reg->sav_reg[--reg->sav_top]);
1471                                 else
1472 #endif
1473
1474                                         reg_index = reg->sav_reg[--reg->sav_top];
1475                         }
1476                 } else { /* use Temp Reg or if none is free a Saved Reg */
1477                         if (reg->tmp_top > regsneeded) {
1478                                 temp = true;
1479 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1480                         if (regsneeded)
1481                                 reg_index = PACK_REGS(reg->tmp_reg[--reg->tmp_top],
1482                                                                           reg->tmp_reg[--reg->tmp_top]);
1483                         else
1484 #endif
1485                                 reg_index = reg->tmp_reg[--reg->tmp_top];
1486                         }
1487                         else
1488                                 if (reg->sav_top > regsneeded) {
1489
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                                         reg_index = reg->sav_reg[--reg->sav_top];
1497                                 }
1498                 }
1499                 if (reg_index == -1) /* no reg is available anymore... -> spill */
1500                         spill_at_intervall(jd, lt);
1501                 else {
1502                         lt->reg = reg_index;
1503                         if (temp)
1504                                 lsra_add_active(lt, ls->active_tmp, &(ls->active_tmp_top));
1505                         else {
1506                                 if (reg->sav_top<*reg_use) *reg_use=reg->sav_top;
1507                                 lsra_add_active(lt, ls->active_sav, &(ls->active_sav_top));
1508                         }
1509                 }
1510         }
1511 }
1512
1513 void lsra_add_active(struct lifetime *lt, struct lifetime **active,
1514                                          int *active_top)
1515 {
1516         int i, j;
1517
1518         for(i = 0; (i < *active_top) && (active[i]->i_end < lt->i_end); i++);
1519         for(j = *active_top; j > i; j--) active[j] = active[j-1];
1520         (*active_top)++;
1521         active[i] = lt;
1522 }
1523
1524 void lsra_expire_old_intervalls(jitdata *jd, struct lifetime *lt,
1525                                                                 struct lsra_register *reg)
1526 {
1527         _lsra_expire_old_intervalls(jd, lt, reg, jd->ls->active_tmp,
1528                                                                 &(jd->ls->active_tmp_top));
1529         _lsra_expire_old_intervalls(jd, lt, reg, jd->ls->active_sav,
1530                                                                 &(jd->ls->active_sav_top));
1531 }
1532
1533 void _lsra_expire_old_intervalls(jitdata *jd, struct lifetime *lt,
1534                                                                  struct lsra_register *reg,
1535                                                                  struct lifetime **active, int *active_top)
1536 {
1537         int i, j, k;
1538
1539         for(i = 0; i < *active_top; i++) {
1540                 if (active[i]->i_end > lt->i_start) break;
1541
1542                 /* make active[i]->reg available again */
1543                 if (code_is_leafmethod(code)) {
1544                         /* leafmethod -> don't care about type -> put all again into */
1545                         /* reg->sav_reg */
1546 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1547                         if (active[i]->type == TYPE_LNG) {
1548                                 reg->sav_reg[reg->sav_top++] = GET_LOW_REG(active[i]->reg);
1549                                 reg->sav_reg[reg->sav_top++] = GET_HIGH_REG(active[i]->reg);
1550                         } else
1551 #endif
1552                                 reg->sav_reg[reg->sav_top++] = active[i]->reg;
1553                 } else {
1554                         /* no leafmethod -> distinguish between temp and saved register */
1555 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1556                         if (active[i]->type == TYPE_LNG) {
1557                                 /* no temp and saved regs are packed together, so looking at */
1558                                 /* LOW_REG is sufficient */
1559                                 if ( reg->nregdesc[ GET_LOW_REG(active[i]->reg)] == REG_SAV) {
1560                                         reg->sav_reg[reg->sav_top++] = GET_LOW_REG(active[i]->reg);
1561                                         reg->sav_reg[reg->sav_top++] = GET_HIGH_REG(active[i]->reg);
1562                                 } else {
1563                                         reg->tmp_reg[reg->tmp_top++] = GET_LOW_REG(active[i]->reg);
1564                                         reg->tmp_reg[reg->tmp_top++] = GET_HIGH_REG(active[i]->reg);
1565                                 }
1566                         } else
1567 #endif
1568                         if ( reg->nregdesc[active[i]->reg] == REG_SAV) {
1569                                         reg->sav_reg[reg->sav_top++] = active[i]->reg;
1570                         } else {
1571                                         reg->tmp_reg[reg->tmp_top++] = active[i]->reg;
1572                         }
1573                 }
1574         }
1575
1576         /* active[0..i[ is to be removed */
1577         /* -> move [i..*active_top[ to [0..*active_top-i[ */
1578         for(k = 0, j = i; (j < *active_top); k++,j++)
1579                 active[k] = active[j];
1580
1581         (*active_top) -= i;
1582
1583 }
1584
1585 void spill_at_intervall(jitdata *jd, struct lifetime *lt )
1586 {
1587         if (lt->savedvar || code_is_leafmethod(code)) {
1588                 _spill_at_intervall(lt, jd->ls->active_sav, &(jd->ls->active_sav_top));
1589         } else {
1590                 _spill_at_intervall(lt, jd->ls->active_tmp, &(jd->ls->active_tmp_top));
1591                 if (lt->reg == -1) { /* no tmp free anymore */
1592                         _spill_at_intervall(lt, jd->ls->active_sav,
1593                                                                 &(jd->ls->active_sav_top));
1594                 }
1595         }
1596 }
1597
1598 void _spill_at_intervall(struct lifetime *lt, struct lifetime **active,
1599                                                  int *active_top)
1600 {
1601         int i, j;
1602 #ifdef USAGE_COUNT_EXACT
1603         int u_min, i_min;
1604 #endif
1605
1606         if (*active_top == 0) {
1607                 lt->reg=-1;
1608                 return;
1609         }
1610
1611         i = *active_top - 1;
1612 #if defined(USAGE_COUNT_EXACT)
1613         /* find intervall which ends later or equal than than lt and has the lowest
1614            usagecount lower than lt */
1615         i_min = -1;
1616         u_min = lt->usagecount;
1617         for (; (i >= 0) && (active[i]->i_end >= lt->i_end); i--) {
1618                 if (active[i]->usagecount < u_min) {
1619                         u_min = active[i]->usagecount;
1620                         i_min = i;
1621                 }
1622         }
1623
1624         if (i_min != -1) {
1625                 i = i_min;
1626 #else
1627 # if defined(USAGE_COUNT) && !defined(USAGE_COUNT_EXACT)
1628         if ((active[i]->i_end >= lt->i_end)
1629                  && (active[i]->usagecount < lt->usagecount)) {
1630 # else /* "normal" LSRA heuristic */
1631         /* get last intervall from active */
1632         if (active[i]->i_end > lt->i_end) {
1633 # endif
1634 #endif
1635 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1636                 /* Don't spill between one and two word int types */
1637                 if ((active[i]->type == TYPE_LNG) != (lt->type == TYPE_LNG))
1638                         return;
1639 #endif
1640                 lt->reg = active[i]->reg;
1641                 active[i]->reg=-1;
1642
1643                 (*active_top)--;
1644                 for (j = i; j < *active_top; j++)
1645                         active[j] = active[j + 1];
1646
1647                 lsra_add_active(lt, active, active_top);
1648         } else {
1649                 lt->reg=-1;
1650         }
1651 }
1652
1653 void lsra_calc_lifetime_length(jitdata *jd) {
1654         methodinfo *m;
1655         lsradata *ls;
1656         codegendata *cd;
1657         struct lifetime *lt;
1658 #if defined(LSRA_DEBUG_VERBOSE) || !defined(LV)
1659         int i;
1660 #endif
1661         int lt_index;
1662         int lifetimecount;
1663         int flags; /* 0 INMEMORY -> ls->lt_mem */
1664                    /* 1 INTREG   -> ls->lt_int  */
1665                    /* 2 FLTREG   -> ls->lt_flt  */
1666
1667
1668         m  = jd->m;
1669         ls = jd->ls;
1670         cd = jd->cd;
1671
1672 #ifdef LSRA_DEBUG_VERBOSE
1673         if (compileverbose) {
1674         printf("icount_block: ");
1675         for (i=0; i < m->basicblockcount; i++)
1676             printf("(%3i-%3i) ",i, ls->icount_block[i]);
1677         printf("\n");
1678         }
1679 #endif
1680
1681         /* extend lifetime over backedges (for the lsra version without exact
1682            liveness analysis)
1683            now iterate through lifetimes and expand them */
1684
1685         lifetimecount = 0;
1686         for(lt_index = 0 ;lt_index < ls->lifetimecount; lt_index++) {
1687                 if ( ls->lifetime[lt_index].type != -1) { /* used lifetime */
1688                         /* remember lt_index in lt_sorted */
1689                         ls->lt_used[lifetimecount++] = lt_index;
1690                         lt = &(ls->lifetime[lt_index]);
1691 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1692                         /* prevent conflicts between lifetimes of type long by increasing
1693                            the lifetime by one instruction
1694                            i.e.(ri/rj)  ...
1695                                (rk/rl)  ICMD_LNEG
1696                            with i==l and/or j==k
1697                            to resolve this during codegeneration a temporary register
1698                            would be needed */
1699                         if (lt->type == TYPE_LNG)
1700                                 lt->i_last_use++;
1701 #endif
1702
1703 /* distribute lifetimes to lt_int, lt_flt and lt_mem */
1704
1705                         lt->reg = -1;
1706
1707                         switch (lt->type) {
1708                         case TYPE_LNG:
1709                                 flags = 1;
1710                                 break;
1711                         case TYPE_INT:
1712                         case TYPE_ADR:
1713                                 flags=1;
1714                                 break;
1715                         case TYPE_DBL:
1716                         case TYPE_FLT:
1717 #if defined(__I386__)
1718                                 /*
1719                                  * for i386 put all floats in memory
1720                                  */
1721                                 flags=0;
1722                                 break;
1723 #endif
1724                                 flags=2;
1725                                 break;
1726                         default:
1727                                 { log_text("Unknown Type\n"); assert(0); }
1728                         }
1729
1730                         switch (flags) {
1731                         case 0: /* lt_used[lt_used_index] -> lt_rest */
1732                                 ls->lt_mem[ ls->lt_mem_count++ ] = lt_index;
1733                                 break;
1734                         case 1: /* l->lifetimes -> lt_int */
1735                                 ls->lt_int[ ls->lt_int_count++ ] = lt_index;
1736                                 break;
1737                         case 2: /* l->lifetimes -> lt_flt */
1738                                 ls->lt_flt[ ls->lt_flt_count++ ] = lt_index;
1739                                 break;
1740                         }
1741
1742
1743                         if (lt->i_first_def == INT_MAX) {
1744 #ifdef LSRA_DEBUG_VERBOSE
1745                                 printf("Warning: var not defined! vi: %i start: %i end: %i\n",
1746                                            lt->v_index, lt->i_start, lt->i_end);
1747 #endif
1748                                 lt->bb_first_def = 0;
1749                                 lt->i_first_def = 0;
1750                         }
1751
1752                         lt->i_start = lt->i_first_def;
1753
1754                         if (lt->i_last_use == -2) {
1755 #ifdef LSRA_DEBUG_VERBOSE
1756                                 printf("Warning: Var not used! vi: %i start: %i end: %i\n",
1757                                            lt->v_index, lt->i_start, lt->i_end);
1758 #endif
1759                                 lt->bb_last_use = lt->bb_first_def;
1760                                 lt->i_last_use = lt->i_first_def;
1761                         }
1762
1763                         lt->i_end = lt->i_last_use;
1764
1765 #ifdef LSRA_DEBUG_VERBOSE
1766                         if (lt->i_start > lt->i_end)
1767                                 printf("Warning: last use before first def! vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end);
1768 #endif
1769
1770 #if !defined(LV)
1771                         if ((lt->bb_first_def != lt->bb_last_use) ||
1772                                 (lt->i_first_def == -1)) {
1773                                 /* Lifetime goes over more than one Basic Block ->  */
1774                                 /* check for necessary extension over backedges     */
1775                                 /* see lsra_get_backedges                           */
1776                                 /* Arguments are set "before" Block 0, so they have */
1777                                 /* a lifespan of more then one block, too           */
1778
1779                                 for (i=0; i < ls->backedge_count; i++) {
1780                                         if (!( (lt->bb_first_def > ls->backedge[i]->start) ||
1781                                                    (lt->bb_last_use < ls->backedge[i]->end) )) {
1782                                                 /* Live intervall intersects with a backedge */
1783                                                 /*      if (lt->bb_first_def <= ls->backedge[i]->start) */
1784                                                 if (lt->bb_last_use <= ls->backedge[i]->start)
1785                                                         lt->i_end =
1786                                                                 ls->icount_block[ls->backedge[i]->start] +
1787                                           m->basicblocks[ls->sorted[ls->backedge[i]->start]].icount;
1788                                         }
1789                                 }
1790                         }
1791 #endif /* !defined(LV) */
1792
1793 #ifdef USAGE_PER_INSTR
1794                         lt->usagecount = lt->usagecount / ( lt->i_end - lt->i_start + 1);
1795 #endif
1796                 }
1797         }
1798         ls->lifetimecount = lifetimecount;
1799 }
1800
1801 #ifdef LSRA_DEBUG_VERBOSE
1802 void print_lifetimes(jitdata *jd, int *lt, int lifetimecount)
1803 {
1804         struct lifetime *n;
1805         int lt_index;
1806         int type,flags,regoff,varkind;
1807
1808         lsradata     *ls;
1809         registerdata *rd;
1810
1811         ls = jd->ls;
1812         rd = jd->rd;
1813
1814         for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
1815                 n = &(ls->lifetime[lt[lt_index]]);
1816                 if (n->savedvar == SAVEDVAR)
1817                         printf("S");
1818                 else
1819                         printf(" ");
1820                 if (n->v_index < 0) { /* stackslot */
1821                         type = n->local_ss->s->type;
1822                         flags=n->local_ss->s->flags;
1823                         regoff=n->local_ss->s->regoff;
1824                         varkind=n->local_ss->s->varkind;
1825                 } else { /* local var */
1826                         if (rd->locals[n->v_index][n->type].type>=0) {
1827                                 type = rd->locals[n->v_index][n->type].type;
1828                                 flags=rd->locals[n->v_index][n->type].flags;
1829                                 regoff=rd->locals[n->v_index][n->type].regoff;
1830                                 varkind=-1;
1831                         } else
1832                                 { log_text("Type Data mismatch 3\n"); assert(0); }
1833                 }
1834 #if !defined(LV)
1835                 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);
1836 #else
1837                 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);
1838 #endif
1839         }
1840         printf( "%3i Lifetimes printed \n",lt_index);
1841 }
1842 #endif
1843
1844
1845
1846 /******************************************************************************
1847 Helpers for first LSRA Version without exact Liveness Analysis
1848  *****************************************************************************/
1849
1850 #if !defined(LV)
1851 bool lsra_join_ss( struct lsradata *ls, struct stackelement *in,
1852                                    struct stackelement *out, int join_flag) {
1853         struct lifetime *lt, *lto;
1854         struct stackslot *ss, *ss_last;
1855
1856
1857         if (in->varnum != out->varnum) {
1858                 lt = &(ls->lifetime[-in->varnum - 1]);
1859
1860 #ifdef LSRA_DEBUG_CHECK
1861                 if (join_flag == JOIN_BB)
1862                         if (lt->type == -1) {
1863                                 log_text("lsra_join_ss: lifetime for instack not found\n");
1864                                 assert(0);
1865                         }
1866 #endif
1867
1868                 if (out->varnum >= 0) { /* no lifetime for this slot till now */
1869                         lsra_add_ss(lt, out);
1870                 } else {
1871                         lto = &(ls->lifetime[-out->varnum - 1]);
1872                         if ((join_flag == JOIN_DUP) || (join_flag == JOIN_OP))
1873                                 if ( (lt->flags & JOIN_BB) || (lto->flags & JOIN_BB)) {
1874                                         return false;
1875                                 }
1876                         if (join_flag == JOIN_DUP)
1877                                 if ( (lt->flags & JOIN_OP) || (lto->flags & JOIN_OP)) {
1878                                         return false;
1879                                 }
1880 #ifdef LSRA_DEBUG_CHECK
1881                         if (lto->type == -1) {
1882                                 log_text("lsra_join_ss: lifetime for outstack not found\n");
1883                                 abort();
1884                         }
1885 #endif
1886 #ifdef LSRA_DEBUG_CHECK
1887                         if (lto->type != lt->type) {
1888                                 log_text("lsra_join_ss: in/out stack type mismatch\n");
1889                                 abort();
1890                         }
1891 #endif
1892
1893                         lt->flags |= JOINING;
1894
1895                         /* take Lifetime lto out of ls->lifetimes */
1896                         lto->type = -1;
1897
1898                         /* merge lto into lt of in */
1899
1900                         ss_last = ss = lto->local_ss;
1901                         while (ss != NULL) {
1902                                 ss_last = ss;
1903                                 ss->s->varnum = lt->v_index;
1904                                 ss = ss->next;
1905                         }
1906                         if (ss_last != NULL) {
1907                                 ss_last->next = lt->local_ss;
1908                                 lt->local_ss = lto->local_ss;
1909                         }
1910
1911                         lt->savedvar |= lto->savedvar;
1912                         lt->flags |= lto->flags | join_flag;
1913                         lt->usagecount += lto->usagecount;
1914
1915                         /*join of i_first_def and i_last_use */
1916                         if (lto->i_first_def < lt->i_first_def) {
1917                                 lt->i_first_def = lto->i_first_def;
1918                         }
1919                         if (lto->i_last_use > lt->i_last_use) {
1920                                 lt->i_last_use = lto->i_last_use;
1921                         }
1922                 }
1923         }
1924         return true;
1925 }
1926
1927 /* join instack of Basic Block b_index with outstack of predecessors */
1928 void lsra_join_lifetimes(jitdata *jd,int b_index) {
1929         methodinfo *m;
1930         lsradata *ls;
1931         struct stackelement *in, *i, *out;
1932     struct _list *pred;
1933
1934         m  = jd->m;
1935         ls = jd->ls;
1936
1937         /* do not join instack of Exception Handler */
1938         if (m->basicblocks[b_index].type == BBTYPE_EXH)
1939                 return;
1940         in=m->basicblocks[b_index].instack;
1941         /* do not join first instack element of a subroutine header */
1942         if (m->basicblocks[b_index].type == BBTYPE_SBR)
1943                 in=in->prev;
1944
1945         if (in != NULL) {
1946                 for (pred = ls->pred[b_index]; pred != NULL; pred = pred->next) {
1947                         out = m->basicblocks[pred->value].outstack;
1948                         for (i=in; (i != NULL); i = i->prev, out=out->prev) {
1949                                 lsra_join_ss(ls, i, out, JOIN_BB);
1950                         }
1951                 }
1952         }
1953 }
1954
1955 struct stackslot *lsra_make_ss(stackelement_t* s, int bb_index)
1956 {
1957         struct stackslot *ss;
1958
1959         ss = DNEW(struct stackslot);
1960         ss->bb = bb_index;
1961         ss->s  = s;
1962         return ss;
1963 }
1964
1965 void lsra_add_ss(struct lifetime *lt, stackelement_t* s) {
1966         struct stackslot *ss;
1967
1968         /* Stackslot not in list? */
1969         if (s->varnum != lt->v_index) {
1970                 ss = DNEW(struct stackslot);
1971                 ss->s = s;
1972                 ss->s->varnum = lt->v_index;
1973                 ss->next = lt->local_ss;
1974                 lt->local_ss = ss;
1975                 if (s != NULL)
1976                         lt->savedvar |= s->flags & SAVEDVAR;
1977                 if (s != NULL)
1978                         lt->type = s->type;
1979         }
1980 }
1981
1982 struct lifetime *get_ss_lifetime(lsradata *ls, stackelement_t* s) {
1983         struct lifetime *n;
1984
1985         if (s->varnum >= 0) { /* new stackslot lifetime */
1986 #ifdef LSRA_DEBUG_CHECK_VERBOSE
1987                 if (-ls->v_index - 1 >= ls->maxlifetimes) {
1988                         printf("%i %i\n", -ls->v_index - 1, ls->maxlifetimes);
1989                 }
1990 #endif
1991                 _LSRA_ASSERT(-ls->v_index - 1 < ls->maxlifetimes);
1992
1993                 n = &(ls->lifetime[-ls->v_index - 1]);
1994                 n->type = s->type;
1995                 n->v_index = ls->v_index--;
1996                 n->usagecount = 0;
1997
1998                 n->bb_last_use  = -1;
1999                 n->bb_first_def = -1;
2000                 n->i_last_use   = -2; /* At -1 param init happens, so -2 is below all
2001                                                                  possible instruction indices */
2002                 n->i_first_def  = INT_MAX;
2003                 n->local_ss = NULL;
2004                 n->savedvar = 0;
2005                 n->flags    = 0;
2006         } else
2007                 n = &(ls->lifetime[-s->varnum - 1]);
2008
2009         lsra_add_ss( n, s);
2010         return n;
2011 }
2012
2013 #define IS_TEMP_VAR(s) (((s)->varkind != ARGVAR) && ((s)->varkind != LOCALVAR))
2014
2015 #define lsra_join_3_stack(ls, dst, src1, src2, join_type) \
2016         if ( IS_TEMP_VAR(dst) ) { \
2017                 join_ret = false; \
2018                 if ( IS_TEMP_VAR(src1) && ((src1)->type == (dst)->type)) { \
2019                         join_ret = lsra_join_ss(ls, dst, src1, join_type);                                                              \
2020                 } \
2021                 if ((!join_ret) && IS_TEMP_VAR(src2) && ((src2)->type == (dst)->type)) { \
2022                         lsra_join_ss(ls, dst, src2, join_type); \
2023                 } \
2024         }
2025
2026 #define lsra_join_2_stack(ls, dst, src, join_type) \
2027         if ( IS_TEMP_VAR(dst) ) { \
2028                 if ( (IS_TEMP_VAR(src)) && ((src)->type == (dst)->type)) {      \
2029                         lsra_join_ss(ls, dst, src, join_type); \
2030                 } \
2031         }
2032
2033 #define lsra_join_dup(ls, s1, s2, s3) {                            \
2034                 if (IS_TEMP_VAR(s1)) {                                             \
2035                         join_ret = false;                                                  \
2036                         if (IS_TEMP_VAR(s2))                                   \
2037                                 join_ret = lsra_join_ss(ls, s1, s2, JOIN); \
2038                                                  /* undangerous join!*/\
2039                         if (IS_TEMP_VAR(s3)) {                                 \
2040                                 if (join_ret)   /* first join succesfull -> second of type */ \
2041                                                     /* JOIN_DUP */                      \
2042                     lsra_join_ss(ls, s1, s3, JOIN_DUP); \
2043                                 else                                                                    \
2044                         lsra_join_ss(ls, s1, s3, JOIN); /* first join did not */ \
2045                                                           /* happen -> second undangerous */ \
2046                     }                                                                           \
2047                 }                                                                                       \
2048         if (IS_TEMP_VAR(s2) && IS_TEMP_VAR(s3))         \
2049                 lsra_join_ss(ls, s2, s3, JOIN_DUP);                 \
2050         }
2051
2052 #define lsra_new_stack(ls, s, block, instr) \
2053         if ((s)->varkind != ARGVAR) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
2054 void _lsra_new_stack(lsradata *ls, stackelement_t* s, int block, int instr, int store)
2055 {
2056         struct lifetime *n;
2057
2058         if (s->varkind == LOCALVAR) {
2059                 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_STORE);
2060         } else /* if (s->varkind != ARGVAR) */ {
2061
2062                 n=get_ss_lifetime(ls, s);
2063
2064                 if (store == LSRA_BB_IN)
2065                         n->flags |= JOIN_BB;
2066                 /* remember first def -> overwrite everytime */
2067                 n->bb_first_def = ls->sorted_rev[block];
2068                 n->i_first_def = ls->icount_block[ls->sorted_rev[block]] + instr;
2069
2070                 n->usagecount+=ls->nesting[ls->sorted_rev[block]];
2071         }
2072 }
2073
2074 #define lsra_from_stack(ls, s, block, instr) \
2075         if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
2076 #define lsra_pop_from_stack(ls, s, block, instr) \
2077         if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
2078 void _lsra_from_stack(lsradata *ls, stackelement_t* s, int block, int instr, int store)
2079 {
2080         struct lifetime *n;
2081
2082         if (s->varkind == LOCALVAR) {
2083                 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
2084         } else /* if (s->varkind != ARGVAR) */ {
2085                 if (s->varkind == STACKVAR )
2086                         /* No STACKVARS possible with lsra! */
2087                         s->varkind = TEMPVAR;
2088
2089                 n=get_ss_lifetime(ls, s);
2090
2091                 if (store == LSRA_BB_OUT)
2092                         n->flags |= JOIN_BB;
2093                 if (n->flags & JOINING)
2094                         n->flags &= ~JOINING;
2095                 n->usagecount+=ls->nesting[ls->sorted_rev[block]];
2096
2097                 /* remember last USE, so only write, if USE Field is undefined (==-1) */
2098                 if (n->bb_last_use == -1) {
2099                         n->bb_last_use = ls->sorted_rev[block];
2100                         n->i_last_use = ls->icount_block[ls->sorted_rev[block]] + instr;
2101                 }
2102         }
2103 }
2104
2105 void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr,
2106                                           int store)
2107 {
2108         struct lifetime *n;
2109
2110         n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);
2111
2112         if (n->type == -1) { /* new local lifetime */
2113                 n->local_ss=NULL;
2114                 n->v_index=v_index;
2115                 n->type=type;
2116                 n->savedvar = SAVEDVAR;
2117                 n->flags = 0;
2118                 n->usagecount = 0;
2119
2120                 n->bb_last_use = -1;
2121                 n->bb_first_def = -1;
2122                 n->i_last_use = -2;
2123                 n->i_first_def = INT_MAX;
2124         }
2125         n->usagecount+=ls->nesting[ls->sorted_rev[block]];
2126         /* add access at (block, instr) to instruction list */
2127         /* remember last USE, so only write, if USE Field is undefined (==-1)   */
2128         /* count store as use, too -> defined and not used vars would overwrite */
2129         /* other vars */
2130         if (n->bb_last_use == -1) {
2131                 n->bb_last_use = ls->sorted_rev[block];
2132                 n->i_last_use = ls->icount_block[ls->sorted_rev[block]] + instr;
2133         }
2134         if (store == LSRA_STORE) {
2135                 /* store == LSRA_STORE, remember first def -> overwrite everytime */
2136                 n->bb_first_def = ls->sorted_rev[block];
2137                 n->i_first_def = ls->icount_block[ls->sorted_rev[block]] + instr;
2138         }
2139 }
2140
2141 #ifdef LSRA_DEBUG_VERBOSE
2142 void lsra_dump_stack(stackelement_t* s)
2143 {
2144         while (s!=NULL) {
2145                 printf("%p(R%3i N%3i K%3i T%3i F%3i) ",(void *)s,s->regoff, s->varnum,
2146                            s->varkind, s->type, s->flags);
2147                 s=s->prev;
2148         }
2149         printf("\n");
2150 }
2151 #endif
2152
2153
2154 void lsra_scan_registers_canditates(jitdata *jd, int b_index)
2155 {
2156 /*      methodinfo         *lm; */
2157         builtintable_entry *bte;
2158         methoddesc         *md;
2159         int i;
2160         int opcode;
2161         int iindex;
2162         stackelement_t*    src;
2163         stackelement_t*    dst;
2164         instruction *iptr;
2165         bool join_ret; /* for lsra_join* Macros */
2166         methodinfo *m;
2167         lsradata *ls;
2168
2169         m  = jd->m;
2170         ls = jd->ls;
2171
2172     /* get instruction count for BB and remember the max instruction count */
2173         /* of all BBs */
2174         iindex = m->basicblocks[b_index].icount - 1;
2175
2176         src = m->basicblocks[b_index].instack;
2177         if (m->basicblocks[b_index].type != BBTYPE_STD) {
2178                 lsra_new_stack(ls, src, b_index, 0);
2179                 src = src->prev;
2180         }
2181         for (;src != NULL; src=src->prev) {
2182 /*******************************************************************************
2183 Check this - ? For every incoming Stack Slot a lifetime has to be created ?
2184 *******************************************************************************/
2185                         _lsra_new_stack(ls, src, b_index, 0, LSRA_BB_IN);
2186         }
2187         src = m->basicblocks[b_index].outstack;
2188         for (;src != NULL; src=src->prev) {
2189                         _lsra_from_stack(ls, src, b_index, iindex, LSRA_BB_OUT);
2190         }
2191
2192         /* set iptr to last instruction of BB */
2193         iptr = m->basicblocks[b_index].iinstr + iindex;
2194
2195         for (;iindex >= 0; iindex--, iptr--)  {
2196
2197                 /* get source and destination Stack for the current instruction     */
2198                 /* destination stack is available as iptr->dst                      */
2199
2200                 dst = iptr->dst;
2201
2202                 /* source stack is either the destination stack of the previos      */
2203                 /* instruction, or the basicblock instack for the first instruction */
2204
2205                 if (iindex) /* != 0 is > 0 here, since iindex ist always >= 0 */
2206                         src=(iptr-1)->dst;
2207                 else
2208                         src=m->basicblocks[b_index].instack;
2209                 opcode = iptr->opc;
2210
2211
2212                 switch (opcode) {
2213
2214                         /* pop 0 push 0 */
2215                 case ICMD_RET:
2216                         /* local read (return adress) */
2217                         lsra_usage_local(ls, iptr->op1, TYPE_ADR, b_index, iindex,
2218                                                          LSRA_LOAD);
2219                         break;
2220                 case ICMD_NOP:
2221 /*              case ICMD_ELSE_ICONST: */
2222                 case ICMD_CHECKNULL:
2223                 case ICMD_JSR:
2224                 case ICMD_RETURN:
2225                 case ICMD_GOTO:
2226                 case ICMD_PUTSTATICCONST:
2227                 case ICMD_INLINE_START:
2228                 case ICMD_INLINE_END:
2229                 case ICMD_INLINE_GOTO:
2230                         break;
2231
2232                 case ICMD_IINC:
2233                         /* local = local+<const> */
2234                         lsra_usage_local(ls, iptr->op1, TYPE_INT, b_index, iindex,
2235                                                          LSRA_LOAD);
2236                         lsra_usage_local(ls, iptr->op1, TYPE_INT, b_index, iindex,
2237                                                          LSRA_STORE);
2238                         break;
2239
2240                         /* pop 0 push 1 const: const->stack */
2241                 case ICMD_ICONST:
2242                 case ICMD_LCONST:
2243                 case ICMD_FCONST:
2244                 case ICMD_DCONST:
2245                 case ICMD_ACONST:
2246                         /* new stack slot */
2247                         lsra_new_stack(ls, dst, b_index, iindex);
2248                         break;
2249
2250                         /* pop 0 push 1 load: local->stack */
2251                 case ICMD_ILOAD:
2252                 case ICMD_LLOAD:
2253                 case ICMD_FLOAD:
2254                 case ICMD_DLOAD:
2255                 case ICMD_ALOAD:
2256                         if (dst->varkind != LOCALVAR) {
2257                                 /* local->value on stack */
2258                                 lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD, b_index,
2259                                                                  iindex, LSRA_LOAD);
2260                                 lsra_new_stack(ls, dst, b_index, iindex); /* value->stack */
2261                         } else /* if (dst->varnum != iptr->op1) */ {
2262                                 /* local -> local */
2263                                 lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD, b_index,
2264                                                                  iindex,LSRA_LOAD); /* local->value */
2265                                 lsra_usage_local(ls, dst->varnum, opcode - ICMD_ILOAD, b_index,
2266                                                                  iindex, LSRA_STORE); /* local->value */
2267                         }
2268
2269                         break;
2270
2271                         /* pop 2 push 1 */
2272                         /* Stack(arrayref,index)->stack */
2273                 case ICMD_IALOAD:
2274                 case ICMD_LALOAD:
2275                 case ICMD_FALOAD:
2276                 case ICMD_DALOAD:
2277                 case ICMD_AALOAD:
2278
2279                 case ICMD_BALOAD:
2280                 case ICMD_CALOAD:
2281                 case ICMD_SALOAD:
2282                         /* stack->index */
2283                         lsra_from_stack(ls, src, b_index, iindex);
2284                         /* stack->arrayref */
2285                         lsra_from_stack(ls, src->prev, b_index, iindex);
2286                         /* arrayref[index]->stack */
2287                         lsra_new_stack(ls, dst, b_index, iindex);
2288                         break;
2289
2290                         /* pop 3 push 0 */
2291                         /* stack(arrayref,index,value)->arrayref[index]=value */
2292                 case ICMD_IASTORE:
2293                 case ICMD_LASTORE:
2294                 case ICMD_FASTORE:
2295                 case ICMD_DASTORE:
2296                 case ICMD_AASTORE:
2297
2298                 case ICMD_BASTORE:
2299                 case ICMD_CASTORE:
2300                 case ICMD_SASTORE:
2301
2302                         lsra_from_stack(ls, src,b_index, iindex); /* stack -> value */
2303                         lsra_from_stack(ls, src->prev, b_index, iindex); /* stack -> index*/
2304                         /* stack -> arrayref */
2305                         lsra_from_stack(ls, src->prev->prev, b_index, iindex);
2306                         break;
2307
2308                         /* pop 1 push 0 store: stack -> local */
2309                 case ICMD_ISTORE:
2310                 case ICMD_LSTORE:
2311                 case ICMD_FSTORE:
2312                 case ICMD_DSTORE:
2313                 case ICMD_ASTORE:
2314                         if (src->varkind != LOCALVAR) {
2315                                 lsra_from_stack(ls, src, b_index, iindex); /* stack -> value */
2316                                 lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE, b_index,
2317                                                                  iindex, LSRA_STORE); /* local->value */
2318                         } else /* if (src->varnum != iptr->op1) */ {
2319                                 lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE, b_index,
2320                                                                  iindex, LSRA_STORE); /* local->value */
2321                                 lsra_usage_local(ls, src->varnum, opcode-ICMD_ISTORE, b_index,
2322                                                                  iindex, LSRA_LOAD); /* local->value */
2323                         }
2324                         break;
2325
2326                         /* pop 1 push 0 */
2327                 case ICMD_POP: /* throw away a stackslot */
2328                         /* TODO: check if used anyway (DUP...) and change codegen to */
2329                         /*       ignore this stackslot */
2330                         lsra_pop_from_stack(ls, src, b_index, iindex);
2331                         break;
2332
2333                         /* pop 1 push 0 */
2334                 case ICMD_IRETURN:
2335                 case ICMD_LRETURN:
2336                 case ICMD_FRETURN:
2337                 case ICMD_DRETURN:
2338                 case ICMD_ARETURN: /* stack(value) -> [empty]    */
2339
2340                 case ICMD_ATHROW:  /* stack(objref) -> undefined */
2341
2342                 case ICMD_PUTSTATIC: /* stack(value) -> static_field */
2343                 case ICMD_PUTFIELDCONST:
2344
2345                         /* pop 1 push 0 branch */
2346                 case ICMD_IFNULL: /* stack(value) -> branch? */
2347                 case ICMD_IFNONNULL:
2348
2349                 case ICMD_IFEQ:
2350                 case ICMD_IFNE:
2351                 case ICMD_IFLT:
2352                 case ICMD_IFGE:
2353                 case ICMD_IFGT:
2354                 case ICMD_IFLE:
2355
2356                 case ICMD_IF_LEQ:
2357                 case ICMD_IF_LNE:
2358                 case ICMD_IF_LLT:
2359                 case ICMD_IF_LGE:
2360                 case ICMD_IF_LGT:
2361                 case ICMD_IF_LLE:
2362
2363                         /* pop 1 push 0 table branch */
2364                 case ICMD_TABLESWITCH:
2365                 case ICMD_LOOKUPSWITCH:
2366
2367                 case ICMD_MONITORENTER:
2368                 case ICMD_MONITOREXIT:
2369                         lsra_from_stack(ls, src, b_index, iindex); /* stack -> value */
2370                         break;
2371
2372                         /* pop 2 push 0 */
2373                 case ICMD_POP2: /* throw away 2 stackslots */
2374                         /* TODO: check if used anyway (DUP...) and change codegen to */
2375                         /*       ignore this stackslot */
2376                         lsra_pop_from_stack(ls, src, b_index, iindex);
2377                         lsra_pop_from_stack(ls, src->prev, b_index, iindex);
2378                         break;
2379
2380                         /* pop 2 push 0 branch */
2381
2382                 case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
2383                 case ICMD_IF_ICMPNE:
2384                 case ICMD_IF_ICMPLT:
2385                 case ICMD_IF_ICMPGE:
2386                 case ICMD_IF_ICMPGT:
2387                 case ICMD_IF_ICMPLE:
2388
2389                 case ICMD_IF_LCMPEQ:
2390                 case ICMD_IF_LCMPNE:
2391                 case ICMD_IF_LCMPLT:
2392                 case ICMD_IF_LCMPGE:
2393                 case ICMD_IF_LCMPGT:
2394                 case ICMD_IF_LCMPLE:
2395
2396                 case ICMD_IF_ACMPEQ:
2397                 case ICMD_IF_ACMPNE:
2398
2399                         /* pop 2 push 0 */
2400                 case ICMD_PUTFIELD: /* stack(objref,value) -> objref = value */
2401
2402                 case ICMD_IASTORECONST:
2403                 case ICMD_LASTORECONST:
2404                 case ICMD_AASTORECONST:
2405                 case ICMD_BASTORECONST:
2406                 case ICMD_CASTORECONST:
2407                 case ICMD_SASTORECONST:
2408                         lsra_from_stack(ls, src, b_index, iindex);         /* stack -> value*/
2409                         lsra_from_stack(ls, src->prev, b_index, iindex);
2410                         break;
2411
2412                         /* pop 0 push 1 dup */
2413                 case ICMD_DUP: /* src == dst->prev, src -> dst */
2414                         /* lsra_from_stack(ls, src,b_index,iindex);*/
2415                         lsra_new_stack(ls, dst, b_index, iindex);
2416
2417 #ifdef JOIN_DUP_STACK
2418                         /* src is identical to dst->prev */
2419                         lsra_join_2_stack(ls, src, dst, JOIN_DUP);
2420 #endif
2421                         break;
2422
2423                         /* pop 0 push 2 dup */
2424                 case ICMD_DUP2:
2425                         /* lsra_from_stack(ls, src,b_index, iindex); */
2426                         /* lsra_from_stack(ls, src->prev, b_index, iindex); */
2427                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2428                         lsra_new_stack(ls, dst, b_index, iindex);
2429
2430 #ifdef JOIN_DUP_STACK
2431                         lsra_join_2_stack(ls, src, dst, JOIN_DUP);
2432                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN_DUP);
2433                         /* src is identical to dst->prev->prev */
2434                         /* src->prev is identical to dst->prev->prev->prev */
2435 #endif
2436                         break;
2437
2438                         /* pop 2 push 3 dup */
2439                 case ICMD_DUP_X1:
2440                         lsra_from_stack(ls, src, b_index, iindex+1);
2441                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2442                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2443                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2444                         lsra_new_stack(ls, dst, b_index, iindex);
2445 #ifdef JOIN_DUP_STACK
2446                         lsra_join_dup(ls, src, dst, dst->prev->prev);
2447                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN);
2448 #endif
2449                         break;
2450
2451                         /* pop 3 push 4 dup */
2452                 case ICMD_DUP_X2:
2453                         lsra_from_stack(ls, src,b_index, iindex+1);
2454                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2455                         lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
2456                         lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
2457                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2458                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2459                         lsra_new_stack(ls, dst, b_index, iindex);
2460
2461 #ifdef JOIN_DUP_STACK
2462                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev);
2463                         lsra_join_2_stack(ls, src->prev, dst->prev, JOIN);
2464                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2465 #endif
2466                         break;
2467
2468                         /* pop 3 push 5 dup */
2469                 case ICMD_DUP2_X1:
2470                         lsra_from_stack(ls, src, b_index, iindex+1);
2471                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2472                         lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
2473                         lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index, iindex);
2474                         lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
2475                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2476                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2477                         lsra_new_stack(ls, dst, b_index, iindex);
2478
2479 #ifdef JOIN_DUP_STACK
2480                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev);
2481                         lsra_join_dup(ls, src->prev, dst->prev,
2482                                                   dst->prev->prev->prev->prev);
2483                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2484 #endif
2485                         break;
2486
2487                         /* pop 4 push 6 dup */
2488                 case ICMD_DUP2_X2:
2489                         lsra_from_stack(ls, src, b_index, iindex+1);
2490                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2491                         lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
2492                         lsra_from_stack(ls, src->prev->prev->prev, b_index, iindex+1);
2493                         lsra_new_stack(ls, dst->prev->prev->prev->prev->prev, b_index,
2494                                                    iindex);
2495                         lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index, iindex);
2496                         lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
2497                         lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
2498                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2499                         lsra_new_stack(ls, dst, b_index, iindex);
2500
2501 #ifdef JOIN_DUP_STACK
2502                         lsra_join_dup(ls, src, dst, dst->prev->prev->prev->prev);
2503                         lsra_join_dup(ls, src->prev, dst->prev,
2504                                                   dst->prev->prev->prev->prev->prev);
2505                         lsra_join_2_stack(ls, src->prev->prev, dst->prev->prev, JOIN);
2506                         lsra_join_2_stack(ls, src->prev->prev->prev, dst->prev->prev->prev,
2507                                                           JOIN);
2508 #endif
2509                         break;
2510
2511                         /* pop 2 push 2 swap */
2512                 case ICMD_SWAP:
2513                         lsra_from_stack(ls, src, b_index, iindex+1);
2514                         lsra_from_stack(ls, src->prev, b_index, iindex+1);
2515                         lsra_new_stack(ls, dst->prev, b_index, iindex);
2516                         lsra_new_stack(ls, dst, b_index, iindex);
2517
2518                         lsra_join_2_stack(ls, src->prev, dst, JOIN);
2519                         lsra_join_2_stack(ls, src, dst->prev, JOIN);
2520
2521                         break;
2522
2523                         /* pop 2 push 1 */
2524
2525                 case ICMD_LADD:
2526                 case ICMD_LSUB:
2527                 case ICMD_LMUL:
2528
2529                 case ICMD_LOR:
2530                 case ICMD_LAND:
2531                 case ICMD_LXOR:
2532
2533                 case ICMD_LSHL:
2534                 case ICMD_LSHR:
2535                 case ICMD_LUSHR:
2536
2537                 case ICMD_IADD:
2538                 case ICMD_IMUL:
2539
2540                 case ICMD_ISHL:
2541                 case ICMD_ISHR:
2542                 case ICMD_IUSHR:
2543                 case ICMD_IAND:
2544                 case ICMD_IOR:
2545                 case ICMD_IXOR:
2546
2547
2548                 case ICMD_FADD:
2549                 case ICMD_FSUB:
2550                 case ICMD_FMUL:
2551
2552                 case ICMD_DADD:
2553                 case ICMD_DSUB:
2554                 case ICMD_DMUL:
2555                 case ICMD_DDIV:
2556                 case ICMD_DREM:
2557                         lsra_from_stack(ls, src, b_index, iindex);
2558                         lsra_from_stack(ls, src->prev, b_index, iindex);
2559                         lsra_new_stack(ls, dst, b_index, iindex);
2560 #ifdef JOIN_DEST_STACK
2561                         lsra_join_3_stack(ls, dst, src->prev, src, JOIN_OP);
2562 #endif
2563                         break;
2564
2565                 case ICMD_ISUB:
2566                         lsra_from_stack(ls, src, b_index, iindex);
2567                         lsra_from_stack(ls, src->prev,b_index,iindex);
2568                         lsra_new_stack(ls, dst, b_index, iindex);
2569 #ifdef JOIN_DEST_STACK
2570                         lsra_join_2_stack(ls, src, dst, JOIN_OP);
2571 #endif
2572                         break;
2573
2574                 case ICMD_LDIV:
2575                 case ICMD_LREM:
2576
2577                 case ICMD_IDIV:
2578                 case ICMD_IREM:
2579
2580                 case ICMD_FDIV:
2581                 case ICMD_FREM:
2582
2583                 case ICMD_LCMP:
2584                 case ICMD_FCMPL:
2585                 case ICMD_FCMPG:
2586                 case ICMD_DCMPL:
2587                 case ICMD_DCMPG:
2588                         lsra_from_stack(ls, src, b_index, iindex);
2589                         lsra_from_stack(ls, src->prev, b_index, iindex);
2590                         lsra_new_stack(ls, dst, b_index, iindex);
2591                         break;
2592
2593                         /* pop 1 push 1 */
2594                 case ICMD_LADDCONST:
2595                 case ICMD_LSUBCONST:
2596                 case ICMD_LMULCONST:
2597                 case ICMD_LMULPOW2:
2598                 case ICMD_LDIVPOW2:
2599                 case ICMD_LREMPOW2:
2600                 case ICMD_LANDCONST:
2601                 case ICMD_LORCONST:
2602                 case ICMD_LXORCONST:
2603                 case ICMD_LSHLCONST:
2604                 case ICMD_LSHRCONST:
2605                 case ICMD_LUSHRCONST:
2606
2607                 case ICMD_IADDCONST:
2608                 case ICMD_ISUBCONST:
2609                 case ICMD_IMULCONST:
2610                 case ICMD_IMULPOW2:
2611                 case ICMD_IDIVPOW2:
2612                 case ICMD_IREMPOW2:
2613                 case ICMD_IANDCONST:
2614                 case ICMD_IORCONST:
2615                 case ICMD_IXORCONST:
2616                 case ICMD_ISHLCONST:
2617                 case ICMD_ISHRCONST:
2618                 case ICMD_IUSHRCONST:
2619
2620 /*              case ICMD_IFEQ_ICONST: */
2621 /*              case ICMD_IFNE_ICONST: */
2622 /*              case ICMD_IFLT_ICONST: */
2623 /*              case ICMD_IFGE_ICONST: */
2624 /*              case ICMD_IFGT_ICONST: */
2625 /*              case ICMD_IFLE_ICONST: */
2626
2627                 case ICMD_INEG:
2628                 case ICMD_INT2BYTE:
2629                 case ICMD_INT2CHAR:
2630                 case ICMD_INT2SHORT:
2631                 case ICMD_LNEG:
2632                 case ICMD_FNEG:
2633                 case ICMD_DNEG:
2634
2635                 case ICMD_I2L:
2636                 case ICMD_I2F:
2637                 case ICMD_I2D:
2638                 case ICMD_L2I:
2639                 case ICMD_L2F:
2640                 case ICMD_L2D:
2641                 case ICMD_F2I:
2642                 case ICMD_F2L:
2643                 case ICMD_F2D:
2644                 case ICMD_D2I:
2645                 case ICMD_D2L:
2646                 case ICMD_D2F:
2647
2648                 case ICMD_CHECKCAST:
2649                         lsra_from_stack(ls, src, b_index, iindex);
2650                         lsra_new_stack(ls, dst, b_index, iindex);
2651 #ifdef JOIN_DEST_STACK
2652                         lsra_join_2_stack(ls, src, dst, JOIN_OP);
2653 #endif
2654                         break;
2655
2656                         /* TODO: check if for these ICMDs JOIN_DEST_STACK works, too! */
2657                 case ICMD_ARRAYLENGTH:
2658                 case ICMD_INSTANCEOF:
2659
2660                 case ICMD_NEWARRAY:
2661                 case ICMD_ANEWARRAY:
2662
2663                 case ICMD_GETFIELD:
2664                         lsra_from_stack(ls, src, b_index, iindex);
2665                         lsra_new_stack(ls, dst, b_index, iindex);
2666                         break;
2667
2668                         /* pop 0 push 1 */
2669                 case ICMD_GETSTATIC:
2670
2671                 case ICMD_NEW:
2672                         lsra_new_stack(ls, dst, b_index, iindex);
2673                         break;
2674
2675                         /* pop many push any */
2676
2677                 case ICMD_INVOKESTATIC:
2678                 case ICMD_INVOKESPECIAL:
2679                 case ICMD_INVOKEVIRTUAL:
2680                 case ICMD_INVOKEINTERFACE:
2681                         INSTRUCTION_GET_METHODDESC(iptr,md);
2682                         i = md->paramcount;
2683                         while (--i >= 0) {
2684                                 lsra_from_stack(ls, src, b_index, iindex);
2685                                 src = src->prev;
2686                         }
2687                         if (md->returntype.type != TYPE_VOID)
2688                                 lsra_new_stack(ls, dst, b_index, iindex);
2689                         break;
2690
2691
2692                 case ICMD_BUILTIN:
2693                         bte = iptr->val.a;
2694                         md = bte->md;
2695                         i = md->paramcount;
2696                         while (--i >= 0) {
2697                                 lsra_from_stack(ls, src, b_index, iindex);
2698                                 src = src->prev;
2699                         }
2700                         if (md->returntype.type != TYPE_VOID)
2701                                 lsra_new_stack(ls, dst, b_index, iindex);
2702                         break;
2703
2704                 case ICMD_MULTIANEWARRAY:
2705                         i = iptr->op1;
2706                         while (--i >= 0) {
2707                                 lsra_from_stack(ls, src, b_index, iindex);
2708                                 src = src->prev;
2709                         }
2710                         lsra_new_stack(ls, dst, b_index, iindex);
2711                         break;
2712
2713                 default:
2714                         exceptions_throw_internalerror("Unknown ICMD %d during register allocation",
2715                                                                                    iptr->opc);
2716                         return;
2717                 } /* switch */
2718         }
2719 }
2720 #endif /* defined(LV) */
2721
2722
2723 /*
2724  * These are local overrides for various environment variables in Emacs.
2725  * Please do not remove this and leave it at the end of the file, where
2726  * Emacs will automagically detect them.
2727  * ---------------------------------------------------------------------
2728  * Local variables:
2729  * mode: c
2730  * indent-tabs-mode: t
2731  * c-basic-offset: 4
2732  * tab-width: 4
2733  * End:
2734  * vim:noexpandtab:sw=4:ts=4:
2735  */