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