src/vm/jit/optimizing/lsra.c

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