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