src/vm/jit/inline/inline.c

   1 /* jit/inline.c - code inliner
   2
   3 globals moved to structure and passed as parameter
   4
   5    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   6    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
   7    M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
   8    P. Tomsich, J. Wenninger
   9
  10    This file is part of CACAO.
  11
  12    This program is free software; you can redistribute it and/or
  13    modify it under the terms of the GNU General Public License as
  14    published by the Free Software Foundation; either version 2, or (at
  15    your option) any later version.
  16
  17    This program is distributed in the hope that it will be useful, but
  18    WITHOUT ANY WARRANTY; without even the implied warranty of
  19    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20    General Public License for more details.
  21
  22    You should have received a copy of the GNU General Public License
  23    along with this program; if not, write to the Free Software
  24    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  25    02111-1307, USA.
  26
  27    Contact: cacao@complang.tuwien.ac.at
  28
  29    Authors: Dieter Thuernbeck
  30
  31    $Id: inline.c 1414 2004-10-04 12:55:33Z carolyn $
  32
  33 */
  34
  35
  36 #include <stdio.h>
  37 #include <string.h>
  38 #include "global.h"
  39 #include "loader.h"
  40 #include "tables.h"
  41 #include "options.h"
  42 #include "jit/inline.h"
  43 #include "jit/jit.h"
  44 #include "jit/parse.h"
  45 #include "toolbox/logging.h"
  46 #include "toolbox/memory.h"
  47
  48 #define METHINFO(m) \
  49   utf_display(m->class->name); printf("."); fflush(stdout); \
  50   method_display(m); fflush(stdout); \
  51
  52 #define IMETHINFO(m) \
  53   utf_display(m->class->name); printf("."); fflush(stdout); \
  54   method_display(m); fflush(stdout); \
  55   printf("\tm->jcodelength=%i; ",m->jcodelength); fflush(stdout); \
  56   printf("m->jcode=%p;\n",m->jcode); fflush(stdout); \
  57   printf("\tm->maxlocals=%i; ",m->maxlocals); fflush(stdout); \
  58   printf("m->maxstack=%i;\n",m->maxstack); fflush(stdout);
  59
  60 bool DEBUGi = false;
  61 // checked functions and macros: LOADCONST code_get OP1 BUILTIN block_insert bound_check ALIGN
  62
  63 // replace jcodelength loops with correct number after main for loop in parse()!
  64
  65 /*-----------------------------------------------------------*/
  66 /* just initialize global structure for non-inlining         */
  67 /*-----------------------------------------------------------*/
  68
  69 t_inlining_globals *inlining_init0(methodinfo *m,
  70                                    t_inlining_globals *inline_env)
  71 {
  72  /* initialization for normal use in parse */
  73         inlining_set_compiler_variables_fun(m, inline_env);
  74         inline_env->isinlinedmethod = 0;
  75         inline_env->cumjcodelength = m->jcodelength; /* for not inlining */
  76         inline_env->cummaxstack = 0;
  77         inline_env->cumextablelength = 0;
  78         inline_env->cumlocals = m->maxlocals;
  79         inline_env->cummethods = 0;//co not global or static-used only here?
  80         inline_env->inlining_stack = NULL;
  81         inline_env->inlining_rootinfo = NULL;
  82 return inline_env;
  83 }
  84 /*-----------------------------------------------------------*/
  85
  86 t_inlining_globals *inlining_init(methodinfo *m)
  87 {
  88         t_inlining_globals *inline_env = DNEW(t_inlining_globals);
  89         inlining_init0(m,inline_env);
  90 if (useinlining)
  91         {
  92 if (DEBUGi==true) {
  93                 printf("\n-------- Inlining init for: "); fflush(stdout);
  94                 IMETHINFO(m)
  95                 }
  96         inline_env->cumjcodelength = 0;
  97         inline_env->inlining_stack = NEW(list);
  98         list_init(inline_env->inlining_stack,
  99                   OFFSET(t_inlining_stacknode, linkage));
 100         /*------ analyze ------*/
 101 if (DEBUGi==true) {print_t_inlining_globals(inline_env);}
 102         inline_env->inlining_rootinfo
 103                 = inlining_analyse_method(m, 0, 0, 0, 0, inline_env);
 104 if (DEBUGi==true) {print_t_inlining_globals(inline_env);}
 105         /*---------------------*/
 106         //if (inline_env->cummethods == 0) {
 107         //  inline_env = DNEW(t_inlining_globals);
 108         //  inlining_init0(m,inline_env);
 109         //  return inline_env;
 110         //  }
 111 if (DEBUGi==true) {
 112   printf("(l,s) (%i,%i) was (%i,%i)\n",
 113     m->maxlocals, inline_env->cumlocals,
 114     m->maxstack,  inline_env->cummaxstack); fflush(stdout);
 115   }
 116         m->maxlocals = inline_env->cumlocals;   //orig not used
 117         m->maxstack = inline_env->cummaxstack;  //orig global maxstack var!!
 118
 119 //panic("TEMP so can test just inline init\n");
 120         }
 121 return inline_env;
 122 }
 123
 124
 125 void inlining_cleanup(t_inlining_globals *inline_env)
 126 {
 127         FREE(inline_env->inlining_stack, t_inlining_stacknode);
 128 }
 129
 130
 131 void inlining_push_compiler_variables(int i, int p, int nextp, int opcode, inlining_methodinfo *inlinfo, t_inlining_globals *inline_env)
 132 {
 133         t_inlining_stacknode *new = NEW(t_inlining_stacknode);
 134
 135         new->i = i;
 136         new->p = p;
 137         new->nextp = nextp;
 138         new->opcode = opcode;
 139         new->method = inline_env->method;
 140         new->inlinfo = inlinfo;
 141
 142         list_addfirst(inline_env->inlining_stack, new);
 143         inline_env->isinlinedmethod++;
 144 }
 145
 146
 147 void inlining_pop_compiler_variables(
 148                                     int *i, int *p, int *nextp, int *opcode,
 149                                     inlining_methodinfo **inlinfo,
 150                                     t_inlining_globals *inline_env)
 151 {
 152         t_inlining_stacknode *tmp
 153           = (t_inlining_stacknode *) list_first(inline_env->inlining_stack);
 154
 155         if (!inline_env->isinlinedmethod) panic("Attempting to pop from inlining stack in toplevel method!\n");
 156
 157         *i = tmp->i;
 158         *p = tmp->p;
 159         *nextp = tmp->nextp;
 160         *opcode = tmp->opcode;
 161         *inlinfo = tmp->inlinfo;
 162
 163         inline_env->method = tmp->method; /*co*/
 164         inline_env->class = inline_env->method->class; /*co*/
 165         inline_env->jcodelength = inline_env->method->jcodelength; /*co*/
 166         inline_env->jcode = inline_env->method->jcode; /*co*/
 167
 168         list_remove(inline_env->inlining_stack, tmp);
 169         FREE(tmp, t_inlining_stacknode);
 170         inline_env->isinlinedmethod--;
 171 }
 172
 173
 174 void inlining_set_compiler_variables_fun(methodinfo *m,
 175                                          t_inlining_globals *inline_env)
 176 {
 177         /* XXX TWISTI */
 178         inline_env->method = m; /*co*/
 179         inline_env->class  = m->class; /*co*/
 180         inline_env->jcode  = m->jcode; /*co*/
 181         inline_env->jcodelength = m->jcodelength; /*co*/
 182 }
 183
 184
 185 classinfo *first_occurence(classinfo* class, utf* name, utf* desc)
 186 {
 187         classinfo *first = class;
 188
 189         for (; class->super != NULL ; class = class->super) {
 190                 if (class_findmethod(class->super, name, desc) != NULL) {
 191                         first = class->super;
 192                 }
 193         }
 194
 195         return first;
 196 }
 197
 198
 199 bool is_unique_rec(classinfo *class, methodinfo *m, utf* name, utf* desc)
 200 {
 201         methodinfo *tmp = class_findmethod(class, name, desc);
 202         if ((tmp != NULL) && (tmp != m))
 203                 return false;
 204
 205         for (; class != NULL; class = class->nextsub) {
 206                 if ((class->sub != NULL) && !is_unique_rec(class->sub, m, name, desc)) {
 207                         return false;
 208                 }
 209         }
 210         return true;
 211 }
 212
 213
 214 bool is_unique_method(classinfo *class, methodinfo *m, utf* name, utf* desc)
 215 {
 216         classinfo *firstclass;
 217
 218         /*      sprintf (logtext, "First occurence of: ");
 219         utf_sprint (logtext+strlen(logtext), m->class->name);
 220         strcpy (logtext+strlen(logtext), ".");
 221         utf_sprint (logtext+strlen(logtext), m->name);
 222         utf_sprint (logtext+strlen(logtext), m->descriptor);
 223         dolog (); */
 224
 225         firstclass = first_occurence(class, name, desc);
 226
 227         /*      sprintf (logtext, "\nis in class:");
 228         utf_sprint (logtext+strlen(logtext), firstclass->name);
 229         dolog (); */
 230
 231         if (firstclass != class) return false;
 232
 233         return is_unique_rec(class, m, name, desc);
 234 }
 235
 236 inlining_methodinfo *inlining_analyse_method(methodinfo *m,
 237                                           int level, int gp,
 238                                           int firstlocal, int maxstackdepth,
 239                                           t_inlining_globals *inline_env)
 240 {
 241         inlining_methodinfo *newnode = DNEW(inlining_methodinfo);
 242         /*u1 *jcode = m->jcode;*/
 243         int jcodelength = m->jcodelength;
 244         int p;
 245         int nextp;
 246         int opcode;
 247         int i;
 248         bool iswide = false, oldiswide;
 249         bool *readonly = NULL;
 250         int  *label_index = NULL;
 251         bool isnotrootlevel = (level > 0);
 252         bool isnotleaflevel = (level < INLINING_MAXDEPTH);
 253
 254         //      if (level == 0) gp = 0;
 255         /*
 256         sprintf (logtext, "Performing inlining analysis of: ");
 257         utf_sprint (logtext+strlen(logtext), m->class->name);
 258         strcpy (logtext+strlen(logtext), ".");
 259         utf_sprint (logtext+strlen(logtext), m->name);
 260         utf_sprint (logtext+strlen(logtext), m->descriptor);
 261         dolog (); */
 262
 263         if (isnotrootlevel) {
 264                 newnode->readonly = readonly = DMNEW(bool, m->maxlocals); //FIXME only paramcount entrys necessary
 265                 for (i = 0; i < m->maxlocals; readonly[i++] = true);
 266                 isnotrootlevel = true;
 267
 268         } else {
 269                 readonly = NULL;
 270         }
 271
 272         label_index = DMNEW(int, jcodelength+200);
 273
 274         newnode->inlinedmethods = DNEW(list);
 275         list_init(newnode->inlinedmethods, OFFSET(inlining_methodinfo, linkage));
 276
 277         newnode->method = m;
 278         newnode->startgp = gp;
 279         newnode->readonly = readonly;
 280         newnode->label_index = label_index;
 281         newnode->firstlocal = firstlocal;
 282         inline_env->cumjcodelength += jcodelength + m->paramcount + 1 + 5;
 283
 284         if ((firstlocal + m->maxlocals) > inline_env->cumlocals) {
 285                 inline_env->cumlocals = firstlocal + m->maxlocals;
 286         }
 287
 288         if ((maxstackdepth + m->maxstack) > inline_env->cummaxstack) {
 289                 inline_env->cummaxstack = maxstackdepth + m->maxstack;
 290         }
 291
 292         inline_env->cumextablelength += m->exceptiontablelength;
 293
 294
 295         for (p = 0; p < jcodelength; gp += (nextp - p), p = nextp) {
 296                 opcode = code_get_u1 (p,m);
 297                 nextp = p + jcommandsize[opcode];
 298                 oldiswide = iswide;
 299
 300                 /* figure out nextp */
 301
 302                 switch (opcode) {
 303                 case JAVA_ILOAD:
 304                 case JAVA_LLOAD:
 305                 case JAVA_FLOAD:
 306                 case JAVA_DLOAD:
 307                 case JAVA_ALOAD:
 308
 309                 case JAVA_ISTORE:
 310                 case JAVA_LSTORE:
 311                 case JAVA_FSTORE:
 312                 case JAVA_DSTORE:
 313                 case JAVA_ASTORE:
 314
 315                 case JAVA_RET:
 316                         if (iswide) {
 317                                 nextp = p + 3;
 318                                 iswide = false;
 319                         }
 320                         break;
 321
 322                 case JAVA_IINC:
 323                         if (iswide) {
 324                                 nextp = p + 5;
 325                                 iswide = false;
 326                         }
 327                         break;
 328
 329                 case JAVA_WIDE:
 330                         iswide = true;
 331                         nextp = p + 1;
 332                         break;
 333
 334                 case JAVA_LOOKUPSWITCH:
 335                         nextp = ALIGN((p + 1), 4) + 4;
 336                         nextp += code_get_u4(nextp,m) * 8 + 4;
 337                         break;
 338
 339                 case JAVA_TABLESWITCH:
 340                         nextp = ALIGN((p + 1), 4) + 4;
 341                         nextp += (code_get_u4(nextp+4,m) - code_get_u4(nextp,m) + 1) * 4 + 4;
 342                         break;
 343                 }
 344
 345                 /* detect readonly variables in inlined methods */
 346
 347                 if (isnotrootlevel) {
 348                         bool iswide = oldiswide;
 349
 350                         switch (opcode) {
 351                         case JAVA_ISTORE:
 352                         case JAVA_LSTORE:
 353                         case JAVA_FSTORE:
 354                         case JAVA_DSTORE:
 355                         case JAVA_ASTORE:
 356                                 if (!iswide) {
 357                                         i = code_get_u1(p + 1,m);
 358
 359                                 } else {
 360                                         i = code_get_u2(p + 1,m);
 361                                 }
 362                                 readonly[i] = false;
 363                                 break;
 364
 365                         case JAVA_ISTORE_0:
 366                         case JAVA_LSTORE_0:
 367                         case JAVA_FSTORE_0:
 368                         case JAVA_ASTORE_0:
 369                                 readonly[0] = false;
 370                                 break;
 371
 372                         case JAVA_ISTORE_1:
 373                         case JAVA_LSTORE_1:
 374                         case JAVA_FSTORE_1:
 375                         case JAVA_ASTORE_1:
 376                                 readonly[1] = false;
 377                                 break;
 378
 379                         case JAVA_ISTORE_2:
 380                         case JAVA_LSTORE_2:
 381                         case JAVA_FSTORE_2:
 382                         case JAVA_ASTORE_2:
 383                                 readonly[2] = false;
 384                                 break;
 385
 386                         case JAVA_ISTORE_3:
 387                         case JAVA_LSTORE_3:
 388                         case JAVA_FSTORE_3:
 389                         case JAVA_ASTORE_3:
 390                                 readonly[3] = false;
 391                                 break;
 392
 393                         case JAVA_IINC:
 394                                 if (!iswide) {
 395                                         i = code_get_u1(p + 1,m);
 396
 397                                 } else {
 398                                         i = code_get_u2(p + 1,m);
 399                                 }
 400                                 readonly[i] = false;
 401                                 break;
 402                         }
 403                 }
 404
 405                 /*              for (i=lastlabel; i<=p; i++) label_index[i] = gp;
 406                 //              printf("lastlabel=%d p=%d gp=%d\n",lastlabel, p, gp);
 407                 lastlabel = p+1; */
 408                 for (i = p; i < nextp; i++) label_index[i] = gp;
 409
 410                 if (isnotleaflevel) {
 411
 412                         switch (opcode) {
 413                         case JAVA_INVOKEVIRTUAL:
 414                                 if (!inlinevirtuals)
 415                                         break;
 416                         case JAVA_INVOKESTATIC:
 417                                 i = code_get_u2(p + 1,m);
 418                                 {
 419                                         constant_FMIref *imr;
 420                                         methodinfo *imi;
 421
 422                                         imr = class_getconstant(m->class, i, CONSTANT_Methodref);
 423
 424                                         if (!class_load(imr->class))
 425                                                 return NULL;
 426
 427                                         if (!class_link(imr->class))
 428                                                 return NULL;
 429
 430                                         imi = class_resolveclassmethod(imr->class,
 431                                                                                                    imr->name,
 432                                                                                                    imr->descriptor,
 433                                                                                                    m->class,
 434                                                                                                    true);
 435
 436                                         if (!imi)
 437                                                 panic("Exception thrown while parsing bytecode"); /* XXX should be passed on */
 438
 439                                         if (opcode == JAVA_INVOKEVIRTUAL) {
 440                                                 if (!is_unique_method(imi->class, imi, imr->name, imr->descriptor))
 441                                                         break;
 442                                         }
 443
 444                                         if ((inline_env->cummethods < INLINING_MAXMETHODS) &&
 445                                                 (!(imi->flags & ACC_NATIVE)) &&
 446                                                 (!inlineoutsiders || (m->class == imr->class)) &&
 447                                                 (imi->jcodelength < INLINING_MAXCODESIZE) &&
 448                                                 (imi->jcodelength > 0) &&
 449                                                 (!inlineexceptions || (imi->exceptiontablelength == 0))) { //FIXME: eliminate empty methods?
 450                                                 inlining_methodinfo *tmp;
 451                                                 descriptor2types(imi);
 452
 453                                                 inline_env->cummethods++;
 454
 455                                                 if (verbose) {
 456                                                         char logtext[MAXLOGTEXT];
 457                                                         sprintf(logtext, "Going to inline: ");
 458                                                         utf_sprint(logtext  +strlen(logtext), imi->class->name);
 459                                                         strcpy(logtext + strlen(logtext), ".");
 460                                                         utf_sprint(logtext + strlen(logtext), imi->name);
 461                                                         utf_sprint(logtext + strlen(logtext), imi->descriptor);
 462                                                         log_text(logtext);
 463                                                 }
 464
 465                                                 tmp =inlining_analyse_method(imi, level + 1, gp, firstlocal + m->maxlocals, maxstackdepth + m->maxstack, inline_env);
 466                                                 list_addlast(newnode->inlinedmethods, tmp);
 467                                                 gp = tmp->stopgp;
 468                                                 p = nextp;
 469                                         }
 470                                 }
 471                                 break;
 472                         }
 473                 }
 474         } /* for */
 475
 476         newnode->stopgp = gp;
 477
 478         if (DEBUGi==true) {
 479           printf ("\nResult of inlining analysis of: ");
 480           IMETHINFO(m);
 481           printf("was called by:\n"); fflush(stdout);
 482           IMETHINFO(inline_env->method);
 483           printf ("label_index[0..%d]->", jcodelength);
 484           for (i=0;i<jcodelength; i++) printf ("%d:%d ", i, label_index[i]);
 485           printf("stopgp : %d\n",newnode->stopgp);
 486           }
 487
 488     return newnode;
 489 }
 490
 491 /* --------------------------------------------------------------------*/
 492 /*  print_ functions: check inline structures contain what is expected */
 493 /* --------------------------------------------------------------------*/
 494 void print_t_inlining_globals (t_inlining_globals *g)
 495 {
 496 printf("\n------------\nt_inlining_globals struct for: \n\t");fflush(stdout);
 497 METHINFO(g->method);
 498 printf("\tclass=");fflush(stdout);
 499   utf_display(g->class->name);printf("\n");fflush(stdout);
 500
 501 printf("\tjcodelength=%i; jcode=%p;\n",g->jcodelength, g->jcode);
 502
 503 if (g->isinlinedmethod==true) {
 504   printf("\tisinlinedmethod=true ");fflush(stdout);
 505   }
 506 else {
 507   printf("\tisinlinedmethod=false");fflush(stdout);
 508   }
 509
 510 printf("\tcumjcodelength=%i ,cummaxstack=%i ,cumextablelength=%i ",
 511  g->cumjcodelength,    g->cummaxstack,  g->cumextablelength);fflush(stdout);
 512 printf("\tcumlocals=%i ,cummethods=%i \n",
 513  g->cumlocals,    g->cummethods);fflush(stdout);
 514
 515 printf("s>s>s> ");fflush(stdout);
 516 print_inlining_stack     (g->inlining_stack);
 517 printf("i>i>i> "); fflush(stdout);
 518 print_inlining_methodinfo(g->inlining_rootinfo);
 519 printf("-------------------\n");fflush(stdout);
 520 }
 521
 522 /* --------------------------------------------------------------------*/
 523 void print_inlining_stack     ( list                *s)
 524 {
 525 if (s==NULL) {
 526   printf("\n\tinlining_stack: NULL\n");
 527   return;
 528   }
 529
 530   {/* print first  element to see if get into stack */
 531   t_inlining_stacknode *is;
 532   printf("\n\tinlining_stack: NOT NULL\n");
 533
 534   is=list_first(s);
 535   if (is==NULL) {
 536     printf("\n\tinlining_stack = init'd but EMPTY\n");
 537     fflush(stdout);
 538     return;
 539     }
 540   }
 541
 542   {
 543   t_inlining_stacknode *is;
 544   printf("\n\tinlining_stack: NOT NULL\n");
 545
 546
 547   for (is=list_first(s);
 548        is!=NULL;
 549        is=list_next(s,is)) {
 550          printf("\n\ti>--->inlining_stack entry: \n"); fflush(stdout);
 551          METHINFO(is->method);
 552          printf("i=%i, p=%i, nextp=%i, opcode=%i;\n",
 553                 is->i,is->p,is->nextp,is->opcode);fflush(stdout);
 554          print_inlining_methodinfo(is->inlinfo);
 555     } /*end for */
 556   }
 557
 558 }
 559
 560 /* --------------------------------------------------------------------*/
 561 void print_inlining_methodinfo( inlining_methodinfo *r) {
 562 if (r==NULL) {
 563   printf("\n\tinlining_methodinfo: NULL\n");
 564   return;
 565   }
 566
 567 if (r->method != NULL) {
 568   utf_display(r->method->class->name); printf("."); fflush(stdout); \
 569   method_display(r->method); fflush(stdout); \
 570   }
 571 else {
 572   printf("method is NULL!!!!!\n");fflush(stdout);
 573   }
 574
 575 printf("\n\tinlining_methodinfo for:"); fflush(stdout);
 576 if (r->readonly==NULL) {
 577   printf("\treadonly==NULL ");fflush(stdout);
 578   }
 579 else {
 580   int i;
 581   printf("\treadonly=");fflush(stdout);
 582   for (i = 0; i < r->method->maxlocals; i++)  {
 583     if (r->readonly[i] == true)
 584       printf("[i]=T;");
 585     else
 586       printf("[i]=F;");
 587     fflush(stdout);
 588     }
 589   }
 590
 591
 592 printf("\tstartgp=%i; stopgp=%i; firstlocal=%i; label_index=%p;\n",
 593           r->startgp, r->stopgp, r->firstlocal, r->label_index);
 594 {int i;
 595 printf ("label_index[0..%d]->", r->method->jcodelength);
 596 for (i=0; i<r->method->jcodelength; i++) printf ("%d:%d ", i, r->label_index[i]);
 597 }
 598
 599 {
 600 inlining_methodinfo *im;
 601 for (im=list_first(r->inlinedmethods);
 602      im!=NULL;
 603      im=list_next(r->inlinedmethods,im)) {
 604   }
 605 }
 606 }
 607
 608
 609 /*
 610  * These are local overrides for various environment variables in Emacs.
 611  * Please do not remove this and leave it at the end of the file, where
 612  * Emacs will automagically detect them.
 613  * ---------------------------------------------------------------------
 614  * Local variables:
 615  * mode: c
 616  * indent-tabs-mode: t
 617  * c-basic-offset: 4
 618  * tab-width: 4
 619  * End:
 620  */