src/vm/jit/stack.h

   1 /* vm/jit/stack.h - stack analysis header
   2
   3    Copyright (C) 1996-2005 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 Thalinger
  28
  29    $Id: stack.h 2211 2005-04-04 10:39:36Z christian $
  30
  31 */
  32
  33
  34 #ifndef _STACK_H
  35 #define _STACK_H
  36
  37 #include "vm/global.h"
  38 #include "vm/exceptions.h"
  39 #include "vm/jit/reg.h"
  40
  41
  42 /**********************************************************************/
  43 /* Macros used internally by analyse_stack                            */
  44 /**********************************************************************/
  45
  46 #ifdef STATISTICS
  47 #define COUNT(cnt) cnt++
  48 #else
  49 #define COUNT(cnt)
  50 #endif
  51
  52 /* convenient abbreviations */
  53 #define CURKIND    curstack->varkind
  54 #define CURTYPE    curstack->type
  55
  56 /*--------------------------------------------------*/
  57 /* SIGNALING ERRORS                                 */
  58 /*--------------------------------------------------*/
  59
  60 #define TYPEPANIC  {panic("Stack type mismatch");}
  61
  62
  63 /*--------------------------------------------------*/
  64 /* STACK UNDERFLOW/OVERFLOW CHECKS                  */
  65 /*--------------------------------------------------*/
  66
  67 /* underflow checks */
  68
  69 #define REQUIRE(num) \
  70     do { \
  71         if (stackdepth < (num)) { \
  72             *exceptionptr = \
  73                 new_verifyerror(m, "Unable to pop operand off an empty stack"); \
  74             return NULL; \
  75         } \
  76     } while(0)
  77
  78 #define REQUIRE_1     REQUIRE(1)
  79 #define REQUIRE_2     REQUIRE(2)
  80 #define REQUIRE_3     REQUIRE(3)
  81 #define REQUIRE_4     REQUIRE(4)
  82
  83
  84 /* overflow check */
  85 /* We allow ACONST instructions inserted as arguments to builtin
  86  * functions to exceed the maximum stack depth.  Maybe we should check
  87  * against maximum stack depth only at block boundaries?
  88  */
  89
  90 #define CHECKOVERFLOW \
  91         do { \
  92                 if (stackdepth > m->maxstack) { \
  93                         if (iptr[0].opc != ICMD_ACONST || iptr[0].op1 == 0) { \
  94                 *exceptionptr = new_verifyerror(m, "Stack size too large"); \
  95                 return NULL; \
  96             } \
  97                 } \
  98         } while(0)
  99
 100
 101 /*--------------------------------------------------*/
 102 /* ALLOCATING STACK SLOTS                           */
 103 /*--------------------------------------------------*/
 104
 105 #define NEWSTACK_(s,v,n) {new->prev=curstack;new->type=s;new->flags=0;  \
 106                                 new->varkind=v;new->varnum=n;curstack=new;new++; }
 107 #ifdef LSRA
 108     #define NEWSTACK(s,v,n) {NEWSTACK_(s,v,n); m->maxlifetimes++;}
 109 #else
 110     #define NEWSTACK(s,v,n) NEWSTACK_(s,v,n)
 111 #endif
 112
 113 #define NEWSTACKn(s,n)  NEWSTACK(s,UNDEFVAR,n)
 114 #define NEWSTACK0(s)    NEWSTACK(s,UNDEFVAR,0)
 115
 116 /* allocate the input stack for an exception handler */
 117 #define NEWXSTACK   {NEWSTACK(TYPE_ADR,STACKVAR,0);curstack=0;}
 118
 119
 120 /*--------------------------------------------------*/
 121 /* STACK MANIPULATION                               */
 122 /*--------------------------------------------------*/
 123
 124 /* resetting to an empty operand stack */
 125 #define STACKRESET {curstack=0;stackdepth=0;}
 126
 127 /* set the output stack of the current instruction */
 128 #define SETDST      {iptr->dst=curstack;}
 129
 130 /* The following macros do NOT check stackdepth, set stackdepth or iptr->dst */
 131 #define POP(s)      {if(s!=curstack->type){TYPEPANIC;}                                                                          \
 132                      if(curstack->varkind==UNDEFVAR)curstack->varkind=TEMPVAR;\
 133                      curstack=curstack->prev;}
 134 #define POPANY      {if(curstack->varkind==UNDEFVAR)curstack->varkind=TEMPVAR;  \
 135                      curstack=curstack->prev;}
 136 #define COPY(s,d)   {(d)->flags=0;(d)->type=(s)->type;\
 137                      (d)->varkind=(s)->varkind;(d)->varnum=(s)->varnum;}
 138
 139
 140 /*--------------------------------------------------*/
 141 /* STACK OPERATIONS MODELING                        */
 142 /*--------------------------------------------------*/
 143
 144 /* The following macros are used to model the stack manipulations of
 145  * different kinds of instructions.
 146  *
 147  * These macros check the input stackdepth and they set the output
 148  * stackdepth and the output stack of the instruction (iptr->dst).
 149  *
 150  * These macros do *not* check for stack overflows!
 151  */
 152
 153 #define PUSHCONST(s){NEWSTACKn(s,stackdepth);SETDST;stackdepth++;}
 154 #define LOAD(s,v,n) {NEWSTACK(s,v,n);SETDST;stackdepth++;}
 155 #define STORE(s)    {REQUIRE_1;POP(s);SETDST;stackdepth--;}
 156 #define OP1_0(s)    {REQUIRE_1;POP(s);SETDST;stackdepth--;}
 157 #define OP1_0ANY    {REQUIRE_1;POPANY;SETDST;stackdepth--;}
 158 #define OP0_1(s)    {NEWSTACKn(s,stackdepth);SETDST;stackdepth++;}
 159 #define OP1_1(s,d)  {REQUIRE_1;POP(s);NEWSTACKn(d,stackdepth-1);SETDST;}
 160 #define OP2_0(s)    {REQUIRE_2;POP(s);POP(s);SETDST;stackdepth-=2;}
 161 #define OPTT2_0(t,b){REQUIRE_2;POP(t);POP(b);SETDST;stackdepth-=2;}
 162 #define OP2_1(s)    {REQUIRE_2;POP(s);POP(s);NEWSTACKn(s,stackdepth-2);SETDST;stackdepth--;}
 163 #define OP2IAT_1(s) {REQUIRE_2;POP(TYPE_INT);POP(TYPE_ADR);NEWSTACKn(s,stackdepth-2);\
 164                      SETDST;stackdepth--;}
 165 #define OP2IT_1(s)  {REQUIRE_2;POP(TYPE_INT);POP(s);NEWSTACKn(s,stackdepth-2);\
 166                      SETDST;stackdepth--;}
 167 #define OPTT2_1(s,d){REQUIRE_2;POP(s);POP(s);NEWSTACKn(d,stackdepth-2);SETDST;stackdepth--;}
 168 #define OP2_2(s)    {REQUIRE_2;POP(s);POP(s);NEWSTACKn(s,stackdepth-2);\
 169                      NEWSTACKn(s,stackdepth-1);SETDST;}
 170 #define OP3TIA_0(s) {REQUIRE_3;POP(s);POP(TYPE_INT);POP(TYPE_ADR);SETDST;stackdepth-=3;}
 171 #define OP3_0(s)    {REQUIRE_3;POP(s);POP(s);POP(s);SETDST;stackdepth-=3;}
 172 #define POPMANY(i)  {REQUIRE(i);stackdepth-=i;while(--i>=0){POPANY;}SETDST;}
 173 #define DUP         {REQUIRE_1;NEWSTACK(CURTYPE,CURKIND,curstack->varnum);SETDST; \
 174                     stackdepth++;}
 175 #define SWAP        {REQUIRE_2;COPY(curstack,new);POPANY;COPY(curstack,new+1);POPANY;\
 176                     new[0].prev=curstack;new[1].prev=new;\
 177                     curstack=new+1;new+=2;SETDST;}
 178 #define DUP_X1      {REQUIRE_2;COPY(curstack,new);COPY(curstack,new+2);POPANY;\
 179                     COPY(curstack,new+1);POPANY;new[0].prev=curstack;\
 180                     new[1].prev=new;new[2].prev=new+1;\
 181                     curstack=new+2;new+=3;SETDST;stackdepth++;}
 182 #define DUP2_X1     {REQUIRE_3;COPY(curstack,new+1);COPY(curstack,new+4);POPANY;\
 183                     COPY(curstack,new);COPY(curstack,new+3);POPANY;\
 184                     COPY(curstack,new+2);POPANY;new[0].prev=curstack;\
 185                     new[1].prev=new;new[2].prev=new+1;\
 186                     new[3].prev=new+2;new[4].prev=new+3;\
 187                     curstack=new+4;new+=5;SETDST;stackdepth+=2;}
 188 #define DUP_X2      {REQUIRE_3;COPY(curstack,new);COPY(curstack,new+3);POPANY;\
 189                     COPY(curstack,new+2);POPANY;COPY(curstack,new+1);POPANY;\
 190                     new[0].prev=curstack;new[1].prev=new;\
 191                     new[2].prev=new+1;new[3].prev=new+2;\
 192                     curstack=new+3;new+=4;SETDST;stackdepth++;}
 193 #define DUP2_X2     {REQUIRE_4;COPY(curstack,new+1);COPY(curstack,new+5);POPANY;\
 194                     COPY(curstack,new);COPY(curstack,new+4);POPANY;\
 195                     COPY(curstack,new+3);POPANY;COPY(curstack,new+2);POPANY;\
 196                     new[0].prev=curstack;new[1].prev=new;\
 197                     new[2].prev=new+1;new[3].prev=new+2;\
 198                     new[4].prev=new+3;new[5].prev=new+4;\
 199                     curstack=new+5;new+=6;SETDST;stackdepth+=2;}
 200
 201
 202 /*--------------------------------------------------*/
 203 /* MACROS FOR HANDLING BASIC BLOCKS                 */
 204 /*--------------------------------------------------*/
 205
 206 /* COPYCURSTACK makes a copy of the current operand stack (curstack)
 207  * and returns it in the variable copy.
 208  *
 209  * This macro is used to propagate the operand stack from one basic
 210  * block to another. The destination block receives the copy as its
 211  * input stack.
 212  */
 213 #define COPYCURSTACK(copy) {\
 214         int d;\
 215         stackptr s;\
 216         if(curstack){\
 217                 s=curstack;\
 218                 new+=stackdepth;\
 219                 d=stackdepth;\
 220                 copy=new;\
 221                 while(s){\
 222                         copy--;d--;\
 223                         copy->prev=copy-1;\
 224                         copy->type=s->type;\
 225                         copy->flags=0;\
 226                         copy->varkind=STACKVAR;\
 227                         copy->varnum=d;\
 228                         s=s->prev;\
 229                         }\
 230                 copy->prev=NULL;\
 231                 copy=new-1;\
 232                 }\
 233         else\
 234                 copy=NULL;\
 235 }
 236
 237 /* BBEND is called at the end of each basic block (after the last
 238  * instruction of the block has been processed).
 239  */
 240
 241 #define BBEND(s,i){ \
 242         i = stackdepth - 1; \
 243         copy = s; \
 244         while (copy) { \
 245                 if ((copy->varkind == STACKVAR) && (copy->varnum > i)) \
 246                         copy->varkind = TEMPVAR; \
 247                 else { \
 248                         copy->varkind = STACKVAR; \
 249                         copy->varnum = i;\
 250                 } \
 251                 rd->interfaces[i][copy->type].type = copy->type; \
 252                 rd->interfaces[i][copy->type].flags |= copy->flags; \
 253                 i--; copy = copy->prev; \
 254         } \
 255         i = bptr->indepth - 1; \
 256         copy = bptr->instack; \
 257         while (copy) { \
 258                 rd->interfaces[i][copy->type].type = copy->type; \
 259                 if (copy->varkind == STACKVAR) { \
 260                         if (copy->flags & SAVEDVAR) \
 261                                 rd->interfaces[i][copy->type].flags |= SAVEDVAR; \
 262                 } \
 263                 i--; copy = copy->prev; \
 264         } \
 265 }
 266
 267
 268 /* MARKREACHED marks the destination block <b> as reached. If this
 269  * block has been reached before we check if stack depth and types
 270  * match. Otherwise the destination block receives a copy of the
 271  * current stack as its input stack.
 272  *
 273  * b...destination block
 274  * c...current stack
 275  */
 276
 277 #define MARKREACHED(b,c) \
 278     do { \
 279             if ((b)->flags < 0) { \
 280                     COPYCURSTACK((c)); \
 281             (b)->flags = 0; \
 282             (b)->instack = (c); \
 283             (b)->indepth = stackdepth; \
 284         } else { \
 285             stackptr s = curstack; \
 286             stackptr t = (b)->instack; \
 287                     if ((b)->indepth != stackdepth) { \
 288                             show_icmd_method(m, cd, rd); \
 289                 panic("Stack depth mismatch"); \
 290             } \
 291                     while (s) { \
 292                 if (s->type != t->type) \
 293                                     TYPEPANIC; \
 294                             s = s->prev; \
 295                 t = t->prev; \
 296                         } \
 297                 } \
 298     } while (0)
 299
 300
 301 /* function prototypes */
 302
 303 methodinfo *analyse_stack(methodinfo *m, codegendata *cd, registerdata *rd);
 304
 305 void icmd_print_stack(codegendata *cd, stackptr s);
 306 char *icmd_builtin_name(functionptr bptr);
 307 void show_icmd_method(methodinfo *m, codegendata *cd, registerdata *rd);
 308 void show_icmd_block(methodinfo *m, codegendata *cd, basicblock *bptr);
 309 void show_icmd(instruction *iptr, bool deadcode);
 310
 311 #endif /* _STACK_H */
 312
 313
 314 /*
 315  * These are local overrides for various environment variables in Emacs.
 316  * Please do not remove this and leave it at the end of the file, where
 317  * Emacs will automagically detect them.
 318  * ---------------------------------------------------------------------
 319  * Local variables:
 320  * mode: c
 321  * indent-tabs-mode: t
 322  * c-basic-offset: 4
 323  * tab-width: 4
 324  * End:
 325  */