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