src/vm/jit/allocator/lsra.c

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