src/vm/jit/optimizing/lsra.c

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