src/vm/jit/allocator/lsra.c

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