src/vm/jit/optimizing/lsra.c

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