src/vm/jit/stack.h

   1 /* vm/jit/stack.h - stack analysis header
   2
   3    Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, 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., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Christian Thalinger
  28
  29    Changes: Christian Ullrich
  30
  31    $Id: stack.h 4678 2006-03-22 23:17:27Z edwin $
  32
  33 */
  34
  35
  36 #ifndef _STACK_H
  37 #define _STACK_H
  38
  39 #include "config.h"
  40
  41 #include "vm/types.h"
  42
  43 #include "vm/exceptions.h"
  44 #include "vm/global.h"
  45 #include "vm/jit/jit.h"
  46 #include "vm/jit/reg.h"
  47
  48
  49 /* macros used internally by analyse_stack ************************************/
  50
  51 #if defined(ENABLE_LSRA)
  52 # define INC_LIFETIMES(a) { m->maxlifetimes += (a); }
  53 #else
  54 # define INC_LIFETIMES(a)
  55 #endif
  56
  57 /* convenient abbreviations */
  58 #define CURKIND    curstack->varkind
  59 #define CURTYPE    curstack->type
  60
  61
  62 /*--------------------------------------------------*/
  63 /* BASIC TYPE CHECKING                              */
  64 /*--------------------------------------------------*/
  65
  66 /* XXX would be nice if we did not have to pass the expected type */
  67
  68 #if defined(ENABLE_VERIFIER)
  69 #define CHECK_BASIC_TYPE(expected,actual) \
  70         do { \
  71                 if ((actual) != (expected)) { \
  72                         expectedtype = (expected); \
  73                         goto throw_stack_type_error; \
  74                 } \
  75         } while (0)
  76 #else /* !ENABLE_VERIFIER */
  77 #define CHECK_BASIC_TYPE(expected,actual)
  78 #endif /* ENABLE_VERIFIER */
  79
  80 /*--------------------------------------------------*/
  81 /* STACK UNDERFLOW/OVERFLOW CHECKS                  */
  82 /*--------------------------------------------------*/
  83
  84 /* underflow checks */
  85
  86 #if defined(ENABLE_VERIFIER)
  87 #define REQUIRE(num) \
  88     do { \
  89         if (stackdepth < (num)) \
  90                         goto throw_stack_underflow; \
  91         } while (0)
  92 #else /* !ENABLE_VERIFIER */
  93 #define REQUIRE(num)
  94 #endif /* ENABLE_VERIFIER */
  95
  96 #define REQUIRE_1     REQUIRE(1)
  97 #define REQUIRE_2     REQUIRE(2)
  98 #define REQUIRE_3     REQUIRE(3)
  99 #define REQUIRE_4     REQUIRE(4)
 100
 101
 102 /* overflow check */
 103 /* We allow ACONST instructions inserted as arguments to builtin
 104  * functions to exceed the maximum stack depth.  Maybe we should check
 105  * against maximum stack depth only at block boundaries?
 106  */
 107
 108 /* XXX we should find a way to remove the opc/op1 check */
 109 #if defined(ENABLE_VERIFIER)
 110 #define CHECKOVERFLOW \
 111         do { \
 112                 if (stackdepth > m->maxstack) \
 113                         if (iptr[0].opc != ICMD_ACONST || iptr[0].op1 == 0) \
 114                                 goto throw_stack_overflow; \
 115         } while(0)
 116 #else /* !ENABLE_VERIFIER */
 117 #define CHECKOVERFLOW
 118 #endif /* ENABLE_VERIFIER */
 119
 120 /*--------------------------------------------------*/
 121 /* ALLOCATING STACK SLOTS                           */
 122 /*--------------------------------------------------*/
 123
 124 #define NEWSTACK_(s,v,n) \
 125     do { \
 126         new->prev = curstack; \
 127         new->type = (s); \
 128         new->flags = 0; \
 129         new->varkind = (v); \
 130         new->varnum = (n); \
 131         curstack = new; \
 132         new++; \
 133     } while (0)
 134
 135
 136 /* Initialize regoff, so -sia can show regnames even before reg.inc */
 137 /* regs[rd->intregargnum has to be set for this */
 138 /* new->regoff = (IS_FLT_DBL_TYPE(s))?-1:rd->intreg_argnum; }*/
 139
 140 #define NEWSTACK(s,v,n) { NEWSTACK_(s,v,n); INC_LIFETIMES(1); }
 141
 142 #define NEWSTACKn(s,n)  NEWSTACK(s,UNDEFVAR,n)
 143 #define NEWSTACK0(s)    NEWSTACK(s,UNDEFVAR,0)
 144
 145 /* allocate the input stack for an exception handler */
 146 #define NEWXSTACK   {NEWSTACK(TYPE_ADR,STACKVAR,0);curstack=0;}
 147
 148
 149 /*--------------------------------------------------*/
 150 /* STACK MANIPULATION                               */
 151 /*--------------------------------------------------*/
 152
 153 /* resetting to an empty operand stack */
 154
 155 #define STACKRESET \
 156     do { \
 157         curstack = 0; \
 158         stackdepth = 0; \
 159     } while (0)
 160
 161
 162 /* set the output stack of the current instruction */
 163
 164 #define SETDST    iptr->dst = curstack;
 165
 166
 167 /* The following macros do NOT check stackdepth, set stackdepth or iptr->dst */
 168
 169 #define POP(s) \
 170     do { \
 171                 CHECK_BASIC_TYPE((s),curstack->type); \
 172         if (curstack->varkind == UNDEFVAR) \
 173             curstack->varkind = TEMPVAR; \
 174         curstack = curstack->prev; \
 175     } while (0)
 176
 177 #define POPANY \
 178     do { \
 179         if (curstack->varkind == UNDEFVAR) \
 180             curstack->varkind = TEMPVAR; \
 181         curstack = curstack->prev; \
 182     } while (0)
 183
 184 /* Do not copy Interface Stackslots over DUPx, Swaps! */
 185 #define COPY(s,d) \
 186     do { \
 187         (d)->flags = 0; \
 188         (d)->type = (s)->type; \
 189                 if ( (s)->varkind != STACKVAR) {                \
 190                         (d)->varkind = (s)->varkind; \
 191                         (d)->varnum = (s)->varnum;       \
 192                 } else { \
 193                         (d)->varkind = TEMPVAR; \
 194                         (d)->varnum = 0; \
 195                 } \
 196     } while (0)
 197
 198
 199 /*--------------------------------------------------*/
 200 /* STACK OPERATIONS MODELING                        */
 201 /*--------------------------------------------------*/
 202
 203 /* The following macros are used to model the stack manipulations of
 204  * different kinds of instructions.
 205  *
 206  * These macros check the input stackdepth and they set the output
 207  * stackdepth and the output stack of the instruction (iptr->dst).
 208  *
 209  * These macros do *not* check for stack overflows!
 210  */
 211
 212 #define PUSHCONST(s){NEWSTACKn(s,stackdepth);SETDST;stackdepth++;}
 213 #define LOAD(s,v,n) {NEWSTACK(s,v,n);SETDST;stackdepth++;}
 214 #define STORE(s)    {REQUIRE_1;POP(s);SETDST;stackdepth--;}
 215
 216 #define OP1_0(s) \
 217     do { \
 218         REQUIRE_1; \
 219         POP(s); \
 220         SETDST; \
 221         stackdepth--; \
 222     } while (0)
 223
 224 #define OP1_0ANY \
 225     do { \
 226         REQUIRE_1; \
 227         POPANY; \
 228         SETDST; \
 229         stackdepth--; \
 230     } while (0)
 231
 232 #define OP0_1(s) \
 233     do { \
 234         NEWSTACKn(s, stackdepth); \
 235         SETDST; \
 236         stackdepth++; \
 237     } while (0)
 238
 239 #define OP1_1(s,d) \
 240     do { \
 241         REQUIRE_1; \
 242         POP(s); \
 243         NEWSTACKn(d, stackdepth - 1);\
 244         SETDST; \
 245     } while (0)
 246
 247 #define OP2_0(s) \
 248     do { \
 249         REQUIRE_2; \
 250         POP(s); \
 251         POP(s); \
 252         SETDST; \
 253         stackdepth -= 2; \
 254     } while (0)
 255
 256 #define OPTT2_0(t,b) \
 257     do { \
 258         REQUIRE_2; \
 259         POP(t); \
 260         POP(b); \
 261         SETDST; \
 262         stackdepth -= 2; \
 263     } while (0)
 264
 265 #define OP2_1(s) \
 266     do { \
 267         REQUIRE_2; \
 268         POP(s); \
 269         POP(s); \
 270         NEWSTACKn(s, stackdepth - 2); \
 271         SETDST; \
 272         stackdepth--; \
 273     } while (0)
 274
 275 #define OP2IAT_1(s) \
 276     do { \
 277         REQUIRE_2; \
 278         POP(TYPE_INT); \
 279         POP(TYPE_ADR); \
 280         NEWSTACKn(s, stackdepth - 2); \
 281         SETDST; \
 282         stackdepth--; \
 283     } while (0)
 284
 285 #define OP2IT_1(s) \
 286     do { \
 287         REQUIRE_2; \
 288         POP(TYPE_INT); \
 289         POP(s); \
 290         NEWSTACKn(s, stackdepth - 2); \
 291         SETDST; \
 292         stackdepth--; \
 293     } while (0)
 294
 295 #define OPTT2_1(s,d) \
 296     do { \
 297         REQUIRE_2; \
 298         POP(s); \
 299         POP(s); \
 300         NEWSTACKn(d, stackdepth - 2); \
 301         SETDST; \
 302         stackdepth--; \
 303     } while (0)
 304
 305 #define OP2_2(s) \
 306     do { \
 307         REQUIRE_2; \
 308         POP(s); \
 309         POP(s); \
 310         NEWSTACKn(s, stackdepth - 2); \
 311         NEWSTACKn(s, stackdepth - 1); \
 312         SETDST; \
 313     } while (0)
 314
 315 #define OP3TIA_0(s) \
 316     do { \
 317         REQUIRE_3; \
 318         POP(s); \
 319         POP(TYPE_INT); \
 320         POP(TYPE_ADR); \
 321         SETDST; \
 322         stackdepth -= 3; \
 323     } while (0)
 324
 325 #define OP3_0(s) \
 326     do { \
 327         REQUIRE_3; \
 328         POP(s); \
 329         POP(s); \
 330         POP(s); \
 331         SETDST; \
 332         stackdepth -= 3; \
 333     } while (0)
 334
 335 #define POPMANY(i) \
 336     do { \
 337         REQUIRE((i)); \
 338         stackdepth -= (i); \
 339         while(--(i) >= 0) { \
 340             POPANY; \
 341         } \
 342         SETDST; \
 343     } while (0)
 344
 345 /* Do not copy Interface Stackslots over DUP! */
 346 #define DUP         {REQUIRE_1; \
 347                              if (CURKIND != STACKVAR) { \
 348                                                  NEWSTACK(CURTYPE,CURKIND,curstack->varnum); \
 349                                          } else { \
 350                                                  NEWSTACK(CURTYPE, TEMPVAR, stackdepth); \
 351                                          } \
 352                                          SETDST; stackdepth++; INC_LIFETIMES(1);}
 353 #define SWAP        {REQUIRE_2;COPY(curstack,new);POPANY;COPY(curstack,new+1);POPANY;\
 354                     new[0].prev=curstack;new[1].prev=new;\
 355                     curstack=new+1;new+=2;SETDST;}
 356 #define DUP_X1      {REQUIRE_2;COPY(curstack,new);COPY(curstack,new+2);POPANY;\
 357                     COPY(curstack,new+1);POPANY;new[0].prev=curstack;\
 358                     new[1].prev=new;new[2].prev=new+1;\
 359                     curstack=new+2;new+=3;SETDST;stackdepth++; INC_LIFETIMES(3);}
 360 #define DUP2_X1     {REQUIRE_3;COPY(curstack,new+1);COPY(curstack,new+4);POPANY;\
 361                     COPY(curstack,new);COPY(curstack,new+3);POPANY;\
 362                     COPY(curstack,new+2);POPANY;new[0].prev=curstack;\
 363                     new[1].prev=new;new[2].prev=new+1;\
 364                     new[3].prev=new+2;new[4].prev=new+3;\
 365                     curstack=new+4;new+=5;SETDST;stackdepth+=2; INC_LIFETIMES(5);}
 366 #define DUP_X2      {REQUIRE_3;COPY(curstack,new);COPY(curstack,new+3);POPANY;\
 367                     COPY(curstack,new+2);POPANY;COPY(curstack,new+1);POPANY;\
 368                     new[0].prev=curstack;new[1].prev=new;\
 369                     new[2].prev=new+1;new[3].prev=new+2;\
 370                     curstack=new+3;new+=4;SETDST;stackdepth++; INC_LIFETIMES(4);}
 371 #define DUP2_X2     {REQUIRE_4;COPY(curstack,new+1);COPY(curstack,new+5);POPANY;\
 372                     COPY(curstack,new);COPY(curstack,new+4);POPANY;\
 373                     COPY(curstack,new+3);POPANY;COPY(curstack,new+2);POPANY;\
 374                     new[0].prev=curstack;new[1].prev=new;\
 375                     new[2].prev=new+1;new[3].prev=new+2;\
 376                     new[4].prev=new+3;new[5].prev=new+4;\
 377                     curstack=new+5;new+=6;SETDST;stackdepth+=2; INC_LIFETIMES(6);}
 378
 379
 380 /*--------------------------------------------------*/
 381 /* MACROS FOR HANDLING BASIC BLOCKS                 */
 382 /*--------------------------------------------------*/
 383
 384 /* COPYCURSTACK makes a copy of the current operand stack (curstack)
 385  * and returns it in the variable copy.
 386  *
 387  * This macro is used to propagate the operand stack from one basic
 388  * block to another. The destination block receives the copy as its
 389  * input stack.
 390  */
 391 #define COPYCURSTACK(copy) {\
 392         int d;\
 393         stackptr s;\
 394         if(curstack){\
 395                 s=curstack;\
 396                 new+=stackdepth;\
 397                 d=stackdepth;\
 398                 copy=new;\
 399                 while(s){\
 400                         copy--;d--;\
 401                         copy->prev=copy-1;\
 402                         copy->type=s->type;\
 403                         copy->flags=0;\
 404                         copy->varkind=STACKVAR;\
 405                         copy->varnum=d;\
 406                         s=s->prev;\
 407                         }\
 408                 copy->prev=NULL;\
 409                 copy=new-1;\
 410                 }\
 411         else\
 412                 copy=NULL;\
 413 }
 414
 415 /* BBEND is called at the end of each basic block (after the last
 416  * instruction of the block has been processed).
 417  */
 418
 419
 420 #if defined(ENABLE_INTRP)
 421 #define IF_NO_INTRP(x) if (!opt_intrp) { x }
 422 #else
 423 #define IF_NO_INTRP(x) { x }
 424 #endif
 425
 426 #define BBEND(s,i) { \
 427         (i) = stackdepth - 1; \
 428         copy = (s); \
 429         while (copy) { \
 430                 if ((copy->varkind == STACKVAR) && (copy->varnum > (i))) \
 431                         copy->varkind = TEMPVAR; \
 432                 else { \
 433                         copy->varkind = STACKVAR; \
 434                         copy->varnum = (i);\
 435                 } \
 436         IF_NO_INTRP(rd->interfaces[(i)][copy->type].type = copy->type; \
 437                     rd->interfaces[(i)][copy->type].flags |= copy->flags;) \
 438                 (i)--; copy = copy->prev; \
 439         } \
 440         (i) = bptr->indepth - 1; \
 441         copy = bptr->instack; \
 442         while (copy) { \
 443         IF_NO_INTRP( \
 444             rd->interfaces[(i)][copy->type].type = copy->type; \
 445             if (copy->varkind == STACKVAR) { \
 446                 if (copy->flags & SAVEDVAR) \
 447                     rd->interfaces[(i)][copy->type].flags |= SAVEDVAR; \
 448             } \
 449         ) \
 450                 (i)--; copy = copy->prev; \
 451         } \
 452 }
 453
 454
 455 /* MARKREACHED marks the destination block <b> as reached. If this
 456  * block has been reached before we check if stack depth and types
 457  * match. Otherwise the destination block receives a copy of the
 458  * current stack as its input stack.
 459  *
 460  * b...destination block
 461  * c...current stack
 462  */
 463
 464 #define MARKREACHED(b,c) \
 465     do { \
 466                 if ((b) <= (bptr)) \
 467                         (b)->bitflags |= BBFLAG_REPLACEMENT; \
 468             if ((b)->flags < BBREACHED) { \
 469                     COPYCURSTACK((c)); \
 470             (b)->flags = BBREACHED; \
 471             (b)->instack = (c); \
 472             (b)->indepth = stackdepth; \
 473         } else { \
 474             stackptr s = curstack; \
 475             stackptr t = (b)->instack; \
 476                     if ((b)->indepth != stackdepth) { \
 477                 *exceptionptr = new_verifyerror(m,"Stack depth mismatch"); \
 478                 return NULL; \
 479             } \
 480                     while (s) { \
 481                                 CHECK_BASIC_TYPE(s->type,t->type); \
 482                             s = s->prev; \
 483                 t = t->prev; \
 484                         } \
 485                 } \
 486     } while (0)
 487
 488
 489 /* function prototypes ********************************************************/
 490
 491 bool stack_init(void);
 492
 493 methodinfo *analyse_stack(methodinfo *m, codegendata *cd, registerdata *rd);
 494
 495 void stack_print(codegendata *cd, stackptr s);
 496 void show_icmd_method(methodinfo *m, codegendata *cd, registerdata *rd);
 497 void show_icmd_block(methodinfo *m, codegendata *cd, basicblock *bptr);
 498 void show_icmd(instruction *iptr, bool deadcode);
 499
 500 /* machine dependent return value handling function */
 501 void md_return_alloc(methodinfo *m, registerdata *rd, s4 return_type,
 502                                          stackptr stackslot);
 503
 504 #endif /* _STACK_H */
 505
 506
 507 /*
 508  * These are local overrides for various environment variables in Emacs.
 509  * Please do not remove this and leave it at the end of the file, where
 510  * Emacs will automagically detect them.
 511  * ---------------------------------------------------------------------
 512  * Local variables:
 513  * mode: c
 514  * indent-tabs-mode: t
 515  * c-basic-offset: 4
 516  * tab-width: 4
 517  * End:
 518  * vim:noexpandtab:sw=4:ts=4:
 519  */