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