src/vm/jit/optimizing/lsra.c

   1 /* src/vm/jit/optimizing/lsra.inc - linear scan register allocator
   2
   3    Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    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., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Ullrich
  28
  29    $Id: lsra.c $
  30
  31 */
  32 #include "config.h"
  33
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36
  37 #include "arch.h"
  38 #include "md-abi.h"
  39
  40 #include "mm/memory.h"
  41
  42 #include "toolbox/bitvector.h"
  43
  44 #include "vm/statistics.h"
  45 #include "vm/options.h"
  46
  47 #include "vm/jit/abi.h"
  48 #include "vm/jit/reg.h"
  49 #include "vm/jit/jit.h"
  50
  51
  52 #include "vm/jit/optimizing/graph.h"
  53 #include "vm/jit/optimizing/lifetimes.h"
  54 #include "vm/jit/optimizing/ssa.h"
  55
  56 #include "vm/jit/optimizing/lsra.h"
  57
  58 #ifdef LSRA_TESTLT
  59 # include "vm/resolve.h"
  60 #include "vm/builtin.h"
  61 #endif
  62
  63
  64 #include "toolbox/logging.h"
  65
  66 extern const char *string_java_lang_InternalError;
  67 /* function prototypes */
  68 void lsra_init(jitdata *);
  69 graphdata *lsra_setup(jitdata *);
  70 void lsra_main(jitdata *);
  71 #ifdef LSRA_DEBUG_VERBOSE
  72 void lsra_dump_stack(stackptr );
  73 void print_lifetimes(jitdata *, int *, int);
  74 void print_all_lifetimes(jitdata *);
  75 #endif
  76 void lsra_reg_setup(jitdata *,struct lsra_register *,
  77                                         struct lsra_register *);
  78
  79 void lsra_calc_lifetime_length(jitdata *);
  80
  81 void _lsra_main( jitdata *, int *, int, struct lsra_register *,
  82                                  int *);
  83 void lsra_expire_old_intervalls(jitdata *, struct lifetime *,
  84                                                                 struct lsra_register *);
  85 void spill_at_intervall(jitdata *, struct lifetime *);
  86 void lsra_add_active(struct lifetime *, struct lifetime **, int *);
  87 void _lsra_expire_old_intervalls(jitdata *, struct lifetime *,
  88                                                                  struct lsra_register *,
  89                                                                  struct lifetime **, int *);
  90 void _spill_at_intervall(struct lifetime *, struct lifetime **, int *);
  91 void lsra_alloc(jitdata *, int *, int,
  92                                 int *);
  93 int lsra_getmem(struct lifetime *, struct freemem *, int *);
  94 struct freemem *lsra_getnewmem(int *);
  95 void lsra_setflags(int *, int);
  96
  97 void lsra(jitdata *jd) {
  98         methodinfo *m;
  99         codegendata *cd;
 100         registerdata *rd;
 101         lsradata *ls;
 102         graphdata *gd;
 103 #if defined(STATISTICS)
 104         int locals_start;
 105         int i,j;
 106 #endif
 107 #if defined(LSRA_DEBUG_CHECK)
 108         int b_index;
 109         stackptr in,out;
 110         int      ind, outd;
 111 #endif
 112
 113         m = jd->m;
 114         cd = jd->cd;
 115         rd = jd->rd;
 116         ls = jd->ls;
 117
 118 #if defined(LSRA_DEBUG_CHECK)
 119         b_index = 0;
 120         while (b_index < m->basicblockcount ) {
 121
 122                 if (m->basicblocks[b_index].flags >= BBREACHED) {
 123
 124                         in=m->basicblocks[b_index].instack;
 125                         ind=m->basicblocks[b_index].indepth;
 126                         for (;ind != 0;in=in->prev, ind--) {
 127                                 /* ARGVAR or LOCALVAR in instack is ok*/
 128 #if defined(LSRA_DEBUG_VERBOSE)
 129                                 if (compileverbose) {
 130                                         if (in->varkind == ARGVAR) printf("ARGVAR in instack: \n");
 131                                         if (in->varkind == LOCALVAR)
 132                                                 printf("LOCALVAR in instack\n");
 133                                 }
 134 #endif
 135                         }
 136                         out=m->basicblocks[b_index].outstack;
 137                         outd=m->basicblocks[b_index].outdepth;
 138                         for (;outd != 0;out=out->prev, outd--) {
 139                                 if (out->varkind == ARGVAR)
 140                                         { log_text("ARGVAR in outstack\n"); assert(0); }
 141                                 if (out->varkind == LOCALVAR)
 142                                         { log_text("LOCALVAR in outstack\n"); assert(0); }
 143                         }
 144                 }
 145                         b_index++;
 146         }
 147 #endif
 148
 149 #if defined(LSRA_DEBUG_CHECK) || defined(LSRA_DEBUG_VERBOSE)
 150 #if defined(LSRA_DEBUG_VERBOSE)
 151         if (compileverbose) {
 152                 printf("%s %s ",m->class->name->text, m->name->text);
 153                 if (jd->isleafmethod)
 154                         printf("**Leafmethod**");
 155                 printf("\n");
 156         }
 157 #endif
 158         if (strcmp(m->class->name->text,"java/lang/String")==0)
 159                 if (strcmp(m->name->text,"toLowerCase")==0)
 160 #if defined(LSRA_DEBUG_VERBOSE)
 161                         if (compileverbose)
 162                                 printf("12-------------------12\n");
 163 #else
 164                 { int dummy=1; dummy++; }
 165 #endif
 166 #endif
 167
 168     lsra_init(jd);
 169
 170
 171         gd = lsra_setup(jd);
 172
 173 #if defined(ENABLE_STATISTICS)
 174         /* find conflicts between locals for statistics */
 175         if (opt_stat) {
 176                 /* local Variable Lifetimes are at the end of the lifetime array and */
 177                 /* have v_index >= 0 */
 178                 for (locals_start = ls->lifetimecount-1; (locals_start >=0) &&
 179                         (ls->lifetime[ls->lt_used[locals_start]].v_index >= 0);
 180                          locals_start--);
 181                 for (i=locals_start + 1; i < ls->lifetimecount; i++)
 182                         for (j=i+1; j < ls->lifetimecount; j++)
 183                                 if ( !((ls->lifetime[ls->lt_used[i]].i_end
 184                                            < ls->lifetime[ls->lt_used[j]].i_start)
 185                                         || (ls->lifetime[ls->lt_used[j]].i_end <
 186                                            ls->lifetime[ls->lt_used[i]].i_start)) )
 187                                         count_locals_conflicts += 2;
 188          }
 189 #endif
 190         /* Run LSRA */
 191         lsra_main(jd);
 192 #ifdef LSRA_TESTLT
 193         test_lifetimes( jd, gd );
 194 #endif
 195         fflush(stdout);
 196 }
 197
 198
 199 void lsra_init(jitdata *jd)
 200 {
 201         lsradata *ls = jd->ls;
 202
 203         /* Init LSRA Data Structures */
 204         /* allocate lifetimes for all Basicblocks */
 205
 206         ls->v_index = -1;
 207
 208
 209 }
 210
 211 graphdata *lsra_setup(jitdata *jd)
 212 {
 213         methodinfo *m;
 214         codegendata *cd;
 215         registerdata *rd;
 216         lsradata *ls;
 217         graphdata *gd;
 218
 219 #if defined(ENABLE_LOOPS)
 220         /* Loop optimization "destroys" the basicblock array */
 221         /* TODO: work with the basicblock list               */
 222         if (opt_loops) {
 223                 log_text("lsra not possible with loop optimization\n");
 224                 exit(1);
 225         }
 226 #endif
 227
 228         m = jd->m;
 229         cd = jd->cd;
 230         rd = jd->rd;
 231         ls = jd->ls;
 232
 233         ssa_init(jd);
 234
 235         /* Setup LSRA Data structures */
 236
 237         /* Generate the Control Flow Graph */
 238         /* Add one for a Basic Block 0 to be inserted, so lateron */
 239         /* with SSA Parameter initialization is handled right */
 240         gd = graph_init(m->basicblockcount + 1);
 241         graph_make_cfg(jd, gd);
 242
 243         ssa(jd, gd);
 244
 245         LifenessAnalysis(m, ls, gd);
 246
 247 #ifdef LSRA_DEBUG_VERBOSE
 248         if (compileverbose) {
 249                 printf("Lifetimes after LifenessAnalyse: \n");
 250                 print_all_lifetimes(jd);
 251         }
 252 #endif
 253
 254         lsra_calc_lifetime_length(jd);
 255
 256 #ifdef LSRA_DEBUG_VERBOSE
 257         if (compileverbose) {
 258                 printf("Basicblockcount: %4i\n",ls->basicblockcount);
 259         }
 260 #endif
 261         return gd;
 262 }
 263
 264 void lsra_reg_setup(jitdata *jd,
 265                                         struct lsra_register *int_reg,
 266                                         struct lsra_register *flt_reg ) {
 267         int i, j, iarg, farg;
 268         int int_sav_top;
 269         int flt_sav_top;
 270         bool *fltarg_used, *intarg_used;
 271         methoddesc *md;
 272         methodinfo *m;
 273         registerdata *rd;
 274
 275         m = jd->m;
 276         rd = jd->rd;
 277         md = m->parseddesc;
 278
 279         int_reg->nregdesc = nregdescint;
 280         flt_reg->nregdesc = nregdescfloat;
 281         if (jd->isleafmethod) {
 282                 /* Temp and Argumentregister can be used as saved registers */
 283
 284                 int_reg->sav_top = INT_ARG_CNT + INT_TMP_CNT + INT_SAV_CNT;
 285                 int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
 286                 int_reg->tmp_reg = NULL;
 287                 int_reg->tmp_top = -1;
 288                 flt_reg->sav_top = FLT_ARG_CNT + FLT_TMP_CNT + FLT_SAV_CNT;
 289                 flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
 290                 flt_reg->tmp_reg = NULL;
 291                 flt_reg->tmp_top = -1;
 292
 293                 /* additionaly precolour registers for Local Variables acting as */
 294                 /* Parameters */
 295
 296                 farg = FLT_ARG_CNT;
 297                 iarg = INT_ARG_CNT;
 298
 299                 intarg_used = DMNEW(bool, INT_ARG_CNT);
 300                 for (i=0; i < INT_ARG_CNT; i++)
 301                         intarg_used[i]=false;
 302
 303                 fltarg_used = DMNEW(bool, FLT_ARG_CNT);
 304                 for (i=0; i < FLT_ARG_CNT; i++)
 305                         fltarg_used[i]=false;
 306
 307                 int_sav_top=int_reg->sav_top;
 308                 flt_sav_top=flt_reg->sav_top;
 309
 310                 for (i=0; (i < md->paramcount); i++) {
 311                         if (!md->params[i].inmemory) {
 312                                 if (IS_INT_LNG_TYPE(md->paramtypes[i].type)) {
 313 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 314                                         if (IS_2_WORD_TYPE(md->paramtypes[i].type)) {
 315                                                 int_reg->sav_reg[--int_sav_top] =
 316                                                         rd->argintregs[GET_HIGH_REG(md->params[i].regoff)];
 317                                                 intarg_used[GET_HIGH_REG(md->params[i].regoff)]=true;
 318                                                 /*used -> don't copy later on */
 319                                                 int_reg->sav_reg[--int_sav_top] =
 320                                                         rd->argintregs[GET_LOW_REG(md->params[i].regoff)];
 321                                                 intarg_used[GET_LOW_REG(md->params[i].regoff)]=true;
 322                                                 /*used -> don't copy later on */
 323                                         } else
 324 #endif
 325                                         { /* !IS_2_WORD_TYPE(md->paramtypes[i].type */
 326                                                 int_reg->sav_reg[--int_sav_top] =
 327                                                         rd->argintregs[md->params[i].regoff];
 328                                                 intarg_used[md->params[i].regoff]=true;
 329                                                 /*used -> don't copy later on */
 330                                         }
 331                                 }
 332 #if !defined(SUPPORT_PASS_FLOATARGS_IN_INTREGS)
 333                                 /* do not precolour float arguments if they are passed in     */
 334                                 /* integer registers. But these integer argument registers    */
 335                                 /* still be used in the method! */
 336                                 else { /* IS_FLT_DBL_TYPE(md->paramtypes[i].type */
 337                                                 flt_reg->sav_reg[--flt_sav_top] =
 338                                                         rd->argfltregs[md->params[i].regoff];
 339                                                 fltarg_used[md->params[i].regoff]=true;
 340                                 }
 341 #endif
 342
 343                         }
 344                 }
 345
 346                 /* copy rest of argument registers to flt_reg->sav_reg and */
 347                 /* int_reg->sav_reg; */
 348                 for (i=0; i < INT_ARG_CNT; i++)
 349                         if (!intarg_used[i])
 350                                 int_reg->sav_reg[--int_sav_top]=rd->argintregs[i];
 351                 for (i=0; i < FLT_ARG_CNT; i++)
 352                         if (!fltarg_used[i])
 353                                 flt_reg->sav_reg[--flt_sav_top]=rd->argfltregs[i];
 354
 355                 /* copy temp registers to flt_reg->sav_reg and int_reg->sav_reg */
 356                 for (i=0; i < INT_TMP_CNT; i++)
 357                         int_reg->sav_reg[--int_sav_top]=rd->tmpintregs[i];
 358                 for (i=0; i < FLT_TMP_CNT; i++)
 359                         flt_reg->sav_reg[--flt_sav_top]=rd->tmpfltregs[i];
 360
 361         } else {
 362                 /* non leaf method -> use Argument Registers [arg[int|flt]reguse */
 363                 /* ... [INT|FLT]_ARG_CNT[ as temp reg */
 364                 /* divide temp and saved registers */
 365
 366                 int argintreguse, argfltreguse;
 367
 368                 /* with Locals as non SAVEDVAR, the used arg[int|flt] as in params */
 369                 /* of the method itself have to be regarded, or mismatch before    */
 370                 /* block 0 with parameter copy could happen! */
 371                 argintreguse = max(rd->argintreguse, md->argintreguse);
 372                 argfltreguse = max(rd->argfltreguse, md->argfltreguse);
 373
 374                 int_sav_top = int_reg->sav_top = INT_SAV_CNT;
 375                 int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
 376                 int_reg->tmp_top = INT_TMP_CNT +
 377                         max(0, (INT_ARG_CNT - argintreguse));
 378                 int_reg->tmp_reg = DMNEW(int, int_reg->tmp_top);
 379
 380                 flt_sav_top =flt_reg->sav_top = FLT_SAV_CNT;
 381                 flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
 382                 flt_reg->tmp_top = FLT_TMP_CNT +
 383                         max(0 , (FLT_ARG_CNT - argfltreguse));
 384                 flt_reg->tmp_reg = DMNEW(int, flt_reg->tmp_top);
 385
 386                 /* copy temp and unused argument registers to flt_reg->tmp_reg and */
 387                 /* int_reg->tmp_reg */
 388                 for (i=0; i < INT_TMP_CNT; i++)
 389                         int_reg->tmp_reg[i]=rd->tmpintregs[i];
 390                 for (j = argintreguse; j < INT_ARG_CNT; j++, i++)
 391                         int_reg->tmp_reg[i]=rd->argintregs[j];
 392                 for (i=0; i < FLT_TMP_CNT; i++)
 393                         flt_reg->tmp_reg[i]=rd->tmpfltregs[i];
 394                 for (j = argfltreguse; j < FLT_ARG_CNT; j++, i++)
 395                         flt_reg->tmp_reg[i]=rd->argfltregs[j];
 396         }
 397
 398         /* now copy saved registers to flt_reg->sav_reg and int_reg->sav_reg */
 399         for (i = INT_SAV_CNT-1; i >= 0; i--)
 400                 int_reg->sav_reg[--int_sav_top]=rd->savintregs[i];
 401         for (i = FLT_SAV_CNT-1; i >= 0; i--)
 402                 flt_reg->sav_reg[--flt_sav_top]=rd->savfltregs[i];
 403         /* done */
 404 }
 405
 406 void lsra_insertion( struct lsradata *ls, int *a, int lo, int hi) {
 407         int i,j,t,tmp;
 408
 409         for (i=lo+1; i<=hi; i++) {
 410                 j=i;
 411                 t=ls->lifetime[a[j]].i_start;
 412                 tmp = a[j];
 413                 while ((j>lo) && (ls->lifetime[a[j-1]].i_start > t)) {
 414                         a[j]=a[j-1];
 415                         j--;
 416                 }
 417                 a[j]=tmp;
 418         }
 419 }
 420
 421 void lsra_qsort( struct lsradata *ls, int *a, int lo, int hi) {
 422         int i,j,x,tmp;
 423         if (lo < hi) {
 424                 if ( (lo+5)<hi) {
 425                         i = lo;
 426                         j = hi;
 427                         x = ls->lifetime[a[(lo+hi)/2]].i_start;
 428
 429                         while (i <= j) {
 430                                 while (ls->lifetime[a[i]].i_start < x) i++;
 431                                 while (ls->lifetime[a[j]].i_start > x) j--;
 432                                 if (i <= j) {
 433                                         /* exchange a[i], a[j] */
 434                                         tmp = a[i];
 435                                         a[i] = a[j];
 436                                         a[j] = tmp;
 437
 438                                         i++;
 439                                         j--;
 440                                 }
 441                         }
 442
 443                         if (lo < j) lsra_qsort( ls, a, lo, j);
 444                         if (i < hi) lsra_qsort( ls, a, i, hi);
 445                 } else
 446                         lsra_insertion(ls, a, lo, hi);
 447         }
 448 }
 449
 450 void lsra_param_sort(struct lsradata *ls, int *lifetime, int lifetime_count) {
 451
 452         int param_count;
 453         int i,j,tmp;
 454
 455         /* count number of parameters ( .i_start == -1) */
 456         for (param_count=0; (param_count < lifetime_count) &&
 457 /*               (ls->lifetime[lifetime[param_count]].i_start == -1); param_count++); */
 458                  (ls->lifetime[lifetime[param_count]].i_start == 0); param_count++);
 459
 460         if (param_count > 0) {
 461                 /* now sort the parameters by v_index */
 462                 for (i=0; i < param_count -1; i++)
 463                         for (j=i+1; j < param_count; j++)
 464                                 if ( ls->lifetime[lifetime[i]].v_index >
 465                                          ls->lifetime[lifetime[j]].v_index) {
 466                                         /* swap */
 467                                         tmp = lifetime[i];
 468                                         lifetime[i]=lifetime[j];
 469                                         lifetime[j]=tmp;
 470                                 }
 471         }
 472 }
 473
 474 void lsra_main(jitdata *jd)
 475 {
 476 #ifdef LSRA_DEBUG_VERBOSE
 477         int i;
 478 #endif
 479         int lsra_mem_use;
 480         int lsra_reg_use;
 481         struct lsra_register flt_reg, int_reg;
 482         methodinfo *m;
 483         registerdata *rd;
 484         lsradata *ls;
 485
 486         ls = jd->ls;
 487         m = jd->m;
 488         rd = jd->rd;
 489
 490 /* sort lifetimes by increasing start */
 491         lsra_qsort( ls, ls->lt_mem, 0, ls->lt_mem_count - 1);
 492         lsra_qsort( ls, ls->lt_int, 0, ls->lt_int_count - 1);
 493         lsra_qsort( ls, ls->lt_flt, 0, ls->lt_flt_count - 1);
 494 /* sort local vars used as parameter */
 495         lsra_param_sort( ls, ls->lt_int, ls->lt_int_count);
 496         lsra_param_sort( ls, ls->lt_flt, ls->lt_flt_count);
 497         lsra_reg_setup(jd, &int_reg, &flt_reg);
 498
 499 #ifdef LSRA_DEBUG_VERBOSE
 500         if (compileverbose) {
 501                 printf("INTSAV REG: ");
 502                 for (i=0; i<int_reg.sav_top; i++)
 503                         printf("%2i ",int_reg.sav_reg[i]);
 504                 printf("\nINTTMP REG: ");
 505                 for (i=0; i<int_reg.tmp_top; i++)
 506                         printf("%2i ",int_reg.tmp_reg[i]);
 507                 printf("\nFLTSAV REG: ");
 508                 for (i=0; i<flt_reg.sav_top; i++)
 509                         printf("%2i ",flt_reg.sav_reg[i]);
 510                 printf("\nFLTTMP REG: ");
 511                 for (i=0; i<flt_reg.tmp_top; i++)
 512                         printf("%2i ",flt_reg.tmp_reg[i]);
 513                 printf("\n");
 514         }
 515 #endif
 516
 517         ls->active_tmp = DMNEW( struct lifetime *, max(INT_REG_CNT, FLT_REG_CNT));
 518         ls->active_sav = DMNEW( struct lifetime *, max(INT_REG_CNT, FLT_REG_CNT));
 519
 520         lsra_reg_use=INT_SAV_CNT; /* init to no saved reg used... */
 521         _lsra_main(jd, ls->lt_int, ls->lt_int_count, &int_reg,
 522                                    &lsra_reg_use);
 523         if (lsra_reg_use > INT_SAV_CNT) lsra_reg_use=INT_SAV_CNT;
 524         rd->savintreguse = lsra_reg_use;
 525
 526         lsra_reg_use = FLT_SAV_CNT; /* no saved reg used... */
 527
 528         _lsra_main(jd, ls->lt_flt, ls->lt_flt_count, &flt_reg, &lsra_reg_use);
 529         if (lsra_reg_use > FLT_SAV_CNT) lsra_reg_use=FLT_SAV_CNT;
 530
 531         rd->savfltreguse=lsra_reg_use;
 532
 533         /* rd->memuse was already set in stack.c to allocate stack space for */
 534         /* passing arguments to called methods */
 535 #if defined(__I386__)
 536         if (checksync && (m->flags & ACC_SYNCHRONIZED)) {
 537                 /* reserve 0(%esp) for Monitorenter/exit Argument on i386 */
 538                 if (rd->memuse < 1)
 539                         rd->memuse = 1;
 540         }
 541 #endif
 542
 543         lsra_mem_use = rd->memuse; /* Init with memuse from stack.c */
 544
 545         lsra_alloc(jd, ls->lt_mem, ls->lt_mem_count, &lsra_mem_use);
 546         lsra_alloc(jd, ls->lt_int, ls->lt_int_count, &lsra_mem_use);
 547         lsra_alloc(jd, ls->lt_flt, ls->lt_flt_count, &lsra_mem_use);
 548
 549         rd->memuse=lsra_mem_use;
 550
 551 #ifdef LSRA_DEBUG_VERBOSE
 552         if (compileverbose) {
 553                 printf("Int RA complete \n");
 554                 printf("Lifetimes after splitting int: \n");
 555                 print_lifetimes(jd, ls->lt_int, ls->lt_int_count);
 556
 557                 printf("Flt RA complete \n");
 558                 printf("Lifetimes after splitting flt:\n");
 559                 print_lifetimes(jd, ls->lt_flt, ls->lt_flt_count);
 560
 561                 printf("Rest RA complete \n");
 562                 printf("Lifetimes after leftt:\n");
 563                 print_lifetimes(jd, ls->lt_mem, ls->lt_mem_count);
 564         }
 565 #endif
 566 }
 567
 568 void lsra_alloc(jitdata *jd, int *lifet, int lifetimecount, int *mem_use)
 569 {
 570         int flags,regoff;
 571         struct lifetime *lt;
 572         struct freemem *fmem;
 573         struct stackslot *n;
 574         int lt_index;
 575 #ifdef HAS_4BYTE_STACKSLOT
 576         struct freemem *fmem_2;
 577 #endif
 578         methodinfo *m;
 579         registerdata *rd;
 580         lsradata *ls;
 581
 582         m = jd->m;
 583         rd = jd->rd;
 584         ls = jd->ls;
 585
 586         fmem=DNEW(struct freemem);
 587         fmem->off=-1;
 588         fmem->next=NULL;
 589 #ifdef HAS_4BYTE_STACKSLOT
 590         fmem_2=DNEW(struct freemem);
 591         fmem_2->off=-1;
 592         fmem_2->next=NULL;
 593 #endif
 594
 595         for (lt_index = 0; lt_index < lifetimecount; lt_index ++) {
 596                 lt = &(ls->lifetime[lifet[lt_index]]);
 597 #ifdef LSRA_MEMORY
 598                 lt->reg=-1;
 599 #endif
 600                 if (lt->reg==-1) {
 601                         flags=INMEMORY;
 602 #ifdef HAS_4BYTE_STACKSLOT
 603                         if (IS_2_WORD_TYPE(lt->type))
 604                                 regoff=lsra_getmem(lt, fmem_2, mem_use);
 605                         else
 606 #endif
 607                         regoff=lsra_getmem(lt, fmem, mem_use);
 608                 } else {
 609                         flags=lt->savedvar;
 610                         regoff=lt->reg;
 611                 }
 612
 613                 for (n=lt->local_ss; n!=NULL; n=n->next) {
 614                         lsra_setflags( &(n->s->flags), flags);
 615                         n->s->regoff=regoff;
 616                 }
 617                 if (lt->v_index >= 0) {
 618                         if (rd->locals[lt->v_index][lt->type].type>=0) {
 619                                 rd->locals[lt->v_index][lt->type].flags= flags;
 620                                 rd->locals[lt->v_index][lt->type].regoff=regoff;
 621                         } else { log_text("Type Data mismatch 1\n"); exit(1); }
 622                 }
 623
 624                 lt->reg = regoff;
 625         }
 626 }
 627
 628 void lsra_setflags(int *flags, int newflags)
 629 {
 630         if ( newflags & INMEMORY)
 631                 *flags |= INMEMORY;
 632         else
 633                 *flags &= ~INMEMORY;
 634
 635         if (newflags & SAVEDVAR)
 636                 *flags |= SAVEDVAR;
 637         else
 638                 *flags &= ~SAVEDVAR;
 639 }
 640
 641 int lsra_getmem(struct lifetime *lt, struct freemem *fmem, int *mem_use)
 642 {
 643         struct freemem *fm, *p;
 644
 645         /* no memmory allocated till now, or all other are still live */
 646         if ((fmem->next == NULL) || (fmem->next->end > lt->i_start)) {
 647 /*      if (1) { */
 648 #ifdef HAS_4BYTE_STACKSLOT
 649                 if (IS_2_WORD_TYPE(lt->type))
 650                         if ( (*mem_use)&1 ) /* align memory location for 2 Word Types */
 651                                 (*mem_use)++;
 652                 fm=lsra_getnewmem(mem_use);
 653                 if (IS_2_WORD_TYPE(lt->type))
 654                         /* allocate a second following Slot for 2 Word Types */
 655                         (*mem_use)++;
 656 #else
 657                 fm=lsra_getnewmem(mem_use);
 658 #endif
 659         } else {
 660                 /* Speicherstelle frei */
 661                 fm=fmem->next;
 662                 fmem->next=fm->next;
 663                 fm->next=NULL;
 664         }
 665         fm->end=lt->i_end;
 666         for (p=fmem; (p->next!=NULL) && (p->next->end < fm->end); p=p->next);
 667         fm->next=p->next;
 668         p->next=fm;
 669         return fm->off;
 670 }
 671
 672 struct freemem *lsra_getnewmem(int *mem_use)
 673 {
 674         struct freemem *fm;
 675
 676         fm=DNEW(struct freemem);
 677         fm->next=NULL;
 678         fm->off=*mem_use;
 679         (*mem_use)++;
 680         return fm;
 681 }
 682
 683 void _lsra_main( jitdata *jd, int *lifet, int lifetimecount,
 684                                  struct lsra_register *reg, int *reg_use)
 685 {
 686         struct lifetime *lt;
 687         int lt_index;
 688         int reg_index;
 689         int regsneeded;
 690         bool temp; /* reg from temp registers (true) or saved registers (false) */
 691         methodinfo *m;
 692         lsradata *ls;
 693
 694         m = jd->m;
 695         ls = jd->ls;
 696
 697 #if !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 698         regsneeded = 0;
 699 #endif
 700         if ((reg->tmp_top+reg->sav_top) == 0) {
 701
 702                 /* no registers available */
 703                 for (lt_index = 0; lt_index < lifetimecount; lt_index++)
 704                         ls->lifetime[lifet[lt_index]].reg = -1;
 705                 return;
 706         }
 707
 708         ls->active_tmp_top = 0;
 709         ls->active_sav_top = 0;
 710
 711         for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
 712                 lt = &(ls->lifetime[lifet[lt_index]]);
 713
 714 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 715         regsneeded = (lt->type == TYPE_LNG)?1:0;
 716 #endif
 717
 718                 lsra_expire_old_intervalls(jd, lt, reg);
 719                 reg_index = -1;
 720                 temp = false;
 721 #ifdef LSRA_SAVEDVAR
 722                 lt->savedvar = SAVEDVAR;
 723 #endif
 724                 if (lt->savedvar || jd->isleafmethod) {
 725                         /* use Saved Reg (in case of leafmethod all regs are saved regs) */
 726                         if (reg->sav_top > regsneeded) {
 727 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 728                                 if (regsneeded)
 729                                         reg_index = PACK_REGS(reg->sav_reg[--reg->sav_top],
 730                                                                                   reg->sav_reg[--reg->sav_top]);
 731                                 else
 732 #endif
 733
 734                                         reg_index = reg->sav_reg[--reg->sav_top];
 735                         }
 736                 } else { /* use Temp Reg or if none is free a Saved Reg */
 737                         if (reg->tmp_top > regsneeded) {
 738                                 temp = true;
 739 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 740                         if (regsneeded)
 741                                 reg_index = PACK_REGS(reg->tmp_reg[--reg->tmp_top],
 742                                                                           reg->tmp_reg[--reg->tmp_top]);
 743                         else
 744 #endif
 745                                 reg_index = reg->tmp_reg[--reg->tmp_top];
 746                         }
 747                         else
 748                                 if (reg->sav_top > regsneeded) {
 749
 750 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 751                                 if (regsneeded)
 752                                         reg_index = PACK_REGS(reg->sav_reg[--reg->sav_top],
 753                                                                                   reg->sav_reg[--reg->sav_top]);
 754                                 else
 755 #endif
 756                                         reg_index = reg->sav_reg[--reg->sav_top];
 757                                 }
 758                 }
 759                 if (reg_index == -1) /* no reg is available anymore... -> spill */
 760                         spill_at_intervall(jd, lt);
 761                 else {
 762                         lt->reg = reg_index;
 763                         if (temp)
 764                                 lsra_add_active(lt, ls->active_tmp, &(ls->active_tmp_top));
 765                         else {
 766                                 if (reg->sav_top<*reg_use) *reg_use=reg->sav_top;
 767                                 lsra_add_active(lt, ls->active_sav, &(ls->active_sav_top));
 768                         }
 769                 }
 770         }
 771 }
 772
 773 void lsra_add_active(struct lifetime *lt, struct lifetime **active,
 774                                          int *active_top)
 775 {
 776         int i, j;
 777
 778         for(i = 0; (i < *active_top) && (active[i]->i_end < lt->i_end); i++);
 779
 780         for(j = *active_top; j > i; j--) active[j] = active[j-1];
 781
 782         (*active_top)++;
 783
 784         active[i] = lt;
 785
 786 }
 787
 788 void lsra_expire_old_intervalls(jitdata *jd,
 789                                                                 struct lifetime *lt, struct lsra_register *reg)
 790 {
 791         _lsra_expire_old_intervalls(jd, lt, reg, jd->ls->active_tmp,
 792                                                                 &(jd->ls->active_tmp_top));
 793         _lsra_expire_old_intervalls(jd, lt, reg, jd->ls->active_sav,
 794                                                                 &(jd->ls->active_sav_top));
 795 }
 796
 797 void _lsra_expire_old_intervalls(jitdata *jd, struct lifetime *lt,
 798                                                                  struct lsra_register *reg,
 799                                                                  struct lifetime **active, int *active_top)
 800 {
 801         int i, j, k;
 802
 803         for(i = 0; i < *active_top; i++) {
 804                 if (active[i]->i_end > lt->i_start) break;
 805
 806                 /* make active[i]->reg available again */
 807                 if (jd->isleafmethod) {
 808                         /* leafmethod -> don't care about type -> put all again into */
 809                         /* reg->sav_reg */
 810 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 811                         if (active[i]->type == TYPE_LNG) {
 812                                 reg->sav_reg[reg->sav_top++] = GET_LOW_REG(active[i]->reg);
 813                                 reg->sav_reg[reg->sav_top++] = GET_HIGH_REG(active[i]->reg);
 814                         } else
 815 #endif
 816                                 reg->sav_reg[reg->sav_top++] = active[i]->reg;
 817                 } else {
 818                         /* no leafmethod -> distinguish between temp and saved register */
 819 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 820                         if (active[i]->type == TYPE_LNG) {
 821                                 /* no temp and saved regs are packed together, so looking at */
 822                                 /* LOW_REG is sufficient */
 823                                 if ( reg->nregdesc[ GET_LOW_REG(active[i]->reg)] == REG_SAV) {
 824                                         reg->sav_reg[reg->sav_top++] = GET_LOW_REG(active[i]->reg);
 825                                         reg->sav_reg[reg->sav_top++] = GET_HIGH_REG(active[i]->reg);
 826                                 } else {
 827                                         reg->tmp_reg[reg->tmp_top++] = GET_LOW_REG(active[i]->reg);
 828                                         reg->tmp_reg[reg->tmp_top++] = GET_HIGH_REG(active[i]->reg);
 829                                 }
 830                         } else
 831 #endif
 832                         if ( reg->nregdesc[active[i]->reg] == REG_SAV) {
 833                                         reg->sav_reg[reg->sav_top++] = active[i]->reg;
 834                         } else {
 835                                         reg->tmp_reg[reg->tmp_top++] = active[i]->reg;
 836                         }
 837                 }
 838         }
 839
 840         /* active[0..i[ is to be removed */
 841         /* -> move [i..*active_top[ to [0..*active_top-i[ */
 842         for(k = 0, j = i; (j < *active_top); k++,j++)
 843                 active[k] = active[j];
 844
 845         (*active_top) -= i;
 846
 847 }
 848
 849 void spill_at_intervall(jitdata *jd, struct lifetime *lt )
 850 {
 851         lsradata *ls;
 852
 853         ls = jd->ls;
 854
 855         if (lt->savedvar || jd->isleafmethod) {
 856                 _spill_at_intervall(lt, ls->active_sav, &(ls->active_sav_top));
 857         } else {
 858                 _spill_at_intervall(lt, ls->active_tmp, &(ls->active_tmp_top));
 859                 if (lt->reg == -1) { /* kein tmp mehr frei gewesen */
 860                         _spill_at_intervall(lt, ls->active_sav, &(ls->active_sav_top));
 861                 }
 862         }
 863 }
 864
 865 void _spill_at_intervall(struct lifetime *lt, struct lifetime **active,
 866                                                  int *active_top)
 867 {
 868         int i, j;
 869 #if 0
 870 #ifdef USAGE_COUNT
 871         int u_min, i_min;
 872 #endif /* USAGE_COUNT */
 873 #endif /* 0 */
 874
 875         if (*active_top == 0) {
 876                 lt->reg=-1;
 877                 return;
 878         }
 879
 880         i = *active_top - 1;
 881 #ifdef USAGE_COUNT
 882 #if 0
 883     /* find intervall which ends later or equal than than lt and has the */
 884         /* lowest usagecount lower than lt */
 885         i_min = -1;
 886         u_min = lt->usagecount;
 887         for (; (i >= 0) && (active[i]->i_end >= lt->i_end); i--) {
 888                 if (active[i]->usagecount < u_min) {
 889                         u_min = active[i]->usagecount;
 890                         i_min = i;
 891                 }
 892         }
 893
 894         if (i_min != -1) {
 895                 i = i_min;
 896 #endif /* 0 */
 897         if ((active[i]->i_end >= lt->i_end) &&
 898                 (active[i]->usagecount < lt->usagecount)) {
 899 #else /* USAGE_COUNT */
 900         /* get last intervall from active */
 901         if (active[i]->i_end > lt->i_end) {
 902 #endif /* USAGE_COUNT */
 903
 904 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 905                 /* Don't spill between one and two word int types */
 906                 if ((active[i]->type == TYPE_LNG) != (lt->type == TYPE_LNG))
 907                         return;
 908 #endif
 909
 910                 lt->reg=active[i]->reg;
 911                 active[i]->reg=-1;
 912
 913                 (*active_top)--;
 914                 for (j = i; j < *active_top; j++)
 915                         active[j] = active[j + 1];
 916
 917                 lsra_add_active(lt, active, active_top);
 918         } else {
 919                 lt->reg=-1;
 920         }
 921 }
 922
 923 void lsra_calc_lifetime_length(jitdata *jd)
 924 {
 925         struct lifetime *lt;
 926         int i, lt_index;
 927         int lifetimecount;
 928
 929         int *icount_block, icount;
 930         int flags; /* 0 INMEMORY -> ls->lt_mem */
 931                    /* 1 INTREG   -> ls->lt_int  */
 932                    /* 2 FLTREG   -> ls->lt_flt  */
 933
 934         instruction *iptr;
 935         lsradata *ls;
 936
 937         ls = jd->ls;
 938
 939         icount_block = DMNEW(int, ls->basicblockcount);
 940         icount_block[0] = icount = 0 /* + ls->max_vars_with_indices + 1 */;
 941         for (i=1; i < ls->basicblockcount; i++) {
 942                 if (ls->sorted[i-1] != -1)
 943                         icount += ls->basicblocks[ls->sorted[i-1]]->icount + 1 +
 944                                 ls->max_vars_with_indices;
 945                 if (ls->sorted[i] != -1)
 946                         icount_block[i] = icount;
 947         }
 948
 949 #ifdef LSRA_DEBUG_VERBOSE
 950         if (compileverbose) {
 951                 printf("icount_block: ");
 952                 for (i=0; i < ls->basicblockcount; i++)
 953                         printf("(%3i-%3i) ",i, icount_block[i]);
 954                 printf("\n");
 955         }
 956 #endif
 957
 958         lifetimecount = 0;
 959         for(lt_index = 0 ;lt_index < ls->lifetimecount; lt_index++) {
 960                 if ( ls->lifetime[lt_index].type != -1) { /* used lifetime */
 961                         /* remember lt_index in lt_sorted */
 962                         ls->lt_used[lifetimecount ++] = lt_index;
 963                         lt = &(ls->lifetime[lt_index]);
 964
 965                         /* compute lt->bb_first_def, i_first_def, bb_last_use and */
 966                         /* i_last_use */
 967
 968                         _LSRA_ASSERT(lt->def != NULL);
 969                         _LSRA_ASSERT(lt->use != NULL);
 970
 971                         /* there are conflicts possible between in and outstacks of */
 972                         /* DUP* ICMDs. So extend lifetime of outstacks by one */
 973                         if (lt->i_first_def >= 0 && (lt->bb_first_def != 0)) {
 974                                 iptr = ls->basicblocks[ls->sorted[lt->bb_first_def]]->iinstr +
 975                                         lt->i_first_def;
 976                                 switch (iptr->opc) {
 977 /*                              case ICMD_DUP:  */
 978                                 case ICMD_DUP2:
 979                                 case ICMD_DUP_X1:
 980                                 case ICMD_DUP_X2:
 981                                 case ICMD_DUP2_X1:
 982                                 case ICMD_DUP2_X2:
 983                                 case ICMD_SWAP:
 984 /*                                      _LSRA_ASSERT(lt->i_first_def != 0); */
 985                                         lt->i_first_def--;
 986                                 }
 987                         }
 988
 989 #if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
 990                         /* prevent conflicts between lifetimes of type long by increasing */
 991                         /* the lifetime by one instruction */
 992                         /* i.e.(ri/rj)  ...       */
 993                         /*     (rk/rl)  ICMD_LNEG */
 994                         /* with i==l and/or j==k  */
 995                         /* to resolve this during codegeneration a temporary register     */
 996                         /* would be needed */
 997                         if (lt->type == TYPE_LNG)
 998                                 lt->i_last_use++;
 999 #endif
1000
1001 /* distribute lifetimes to lt_int, lt_flt and lt_mem */
1002
1003                         lt->reg = -1;
1004
1005                         switch (lt->type) {
1006                         case TYPE_LNG:
1007 #if defined(HAS_4BYTE_STACKSLOT) && !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
1008                                 flags = 0;
1009 #else
1010                                 flags = 1;
1011 #endif
1012                                 break;
1013
1014                         case TYPE_INT:
1015                         case TYPE_ADR:
1016                                 flags=1;
1017                                 break;
1018                         case TYPE_DBL:
1019                         case TYPE_FLT:
1020 #if defined(__I386__)
1021                                 /*
1022                                  * for i386 put all floats in memory
1023                                  */
1024                                 flags=0;
1025                                 break;
1026 #endif
1027                                 flags=2;
1028                                 break;
1029                         default:
1030                                 { log_text("Unknown Type\n"); exit(1); }
1031                         }
1032
1033                         switch (flags) {
1034                         case 0: /* lt_used[lt_used_index] -> lt_rest */
1035                                 ls->lt_mem[ ls->lt_mem_count++ ] = lt_index;
1036                                 break;
1037                         case 1: /* l->lifetimes -> lt_int */
1038                                 ls->lt_int[ ls->lt_int_count++ ] = lt_index;
1039                                 break;
1040                         case 2: /* l->lifetimes -> lt_flt */
1041                                 ls->lt_flt[ ls->lt_flt_count++ ] = lt_index;
1042                                 break;
1043                         }
1044
1045
1046                         if (lt->bb_first_def < -1) {
1047                                 printf("--------- Warning: variable not defined!------------------vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end);
1048                                 lt->bb_first_def = 0;
1049                                 lt->i_first_def = 0;
1050                         }
1051
1052                         lt->i_start = icount_block[lt->bb_first_def] + lt->i_first_def;
1053
1054                         if (lt->bb_last_use == -1) {
1055                                 printf("--------- Warning: variable not used! --------------------vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end);
1056                                 lt->bb_last_use = lt->bb_first_def;
1057                                 lt->i_last_use = lt->i_first_def;
1058                         }
1059
1060                         lt->i_end = icount_block[lt->bb_last_use] + lt->i_last_use;
1061
1062                         if (lt->i_start < 0)
1063                                 printf("------- Error: Lt %3i Vi %4i invalid!\n",lt_index, lt->v_index);
1064
1065                         if (lt->i_start > lt->i_end)
1066                                 printf("--------- Warning: last use before first def! vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end);
1067
1068 #ifdef USAGE_PER_INSTR
1069                         lt->usagecount = lt->usagecount / ( lt->i_end - lt->i_start + 1);
1070 #endif
1071                 }
1072         }
1073         ls->lifetimecount = lifetimecount;
1074 }
1075
1076 #ifdef LSRA_DEBUG_VERBOSE
1077 void print_lifetimes(jitdata *jd, int *lt, int lifetimecount)
1078 {
1079         struct lifetime *n;
1080         int lt_index;
1081         int type,flags,regoff,varkind;
1082         lsradata *ls;
1083         registerdata *rd;
1084
1085         rd = jd->rd;
1086         ls = jd->ls;
1087
1088         for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
1089                 n = &(ls->lifetime[lt[lt_index]]);
1090                 if (n->v_index < 0) { /* stackslot */
1091                         type = n->local_ss->s->type;
1092                         flags=n->local_ss->s->flags;
1093                         regoff=n->local_ss->s->regoff;
1094                         varkind=n->local_ss->s->varkind;
1095                 } else { /* local var */
1096                         if (rd->locals[n->v_index][n->type].type>=0) {
1097                                 type = rd->locals[n->v_index][n->type].type;
1098                                 flags=rd->locals[n->v_index][n->type].flags;
1099                                 regoff=rd->locals[n->v_index][n->type].regoff;
1100                                 varkind=-1;
1101                         } else
1102                                 { log_text("Type Data mismatch 3\n"); assert(0); }
1103                 }
1104                 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);
1105         }
1106         printf( "%3i Lifetimes printed \n",lt_index);
1107 }
1108
1109 void print_all_lifetimes(jitdata *jd)
1110 {
1111         struct lifetime *n;
1112         int lt_index;
1113         int type,flags,regoff,varkind;
1114         lsradata *ls;
1115         registerdata *rd;
1116
1117         rd = jd->rd;
1118         ls = jd->ls;
1119
1120         for (lt_index = 0; lt_index < ls->lifetimecount; lt_index++) {
1121                 n = &(ls->lifetime[lt_index]);
1122                 if (n->type != -1) {
1123                         if (n->v_index < 0) { /* stackslot */
1124                                 type = n->local_ss->s->type;
1125                                 flags=n->local_ss->s->flags;
1126                                 regoff=n->local_ss->s->regoff;
1127                                 varkind=n->local_ss->s->varkind;
1128                         } else { /* local var */
1129                                 if (rd->locals[n->v_index][n->type].type>=0) {
1130                                         type = rd->locals[n->v_index][n->type].type;
1131                                         flags=rd->locals[n->v_index][n->type].flags;
1132                                         regoff=rd->locals[n->v_index][n->type].regoff;
1133                                         varkind=-1;
1134                                 } else
1135                                         { log_text("Type Data mismatch 3\n"); assert(0); }
1136                         }
1137                         printf("i_Start: %3i(%3i,%3i) i_stop: %3i(%3i,%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,n->v_index,type,flags, varkind, n->usagecount, n->flags);
1138                 }
1139         }
1140         printf( "%3i Lifetimes printed \n",lt_index);
1141 }
1142 #endif
1143
1144 /*
1145  * These are local overrides for various environment variables in Emacs.
1146  * Please do not remove this and leave it at the end of the file, where
1147  * Emacs will automagically detect them.
1148  * ---------------------------------------------------------------------
1149  * Local variables:
1150  * mode: c
1151  * indent-tabs-mode: t
1152  * c-basic-offset: 4
1153  * tab-width: 4
1154  * End:
1155  */