src/vm/jit/verify/typecheck.c

   1 /* jit/typecheck.c - typechecking (part of bytecode verification)
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
   5    M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
   6    P. Tomsich, J. Wenninger
   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: Edwin Steiner
  28
  29    $Id: typecheck.c 701 2003-12-07 16:26:58Z edwin $
  30
  31 */
  32
  33 #include "global.h" /* must be here because of CACAO_TYPECHECK */
  34
  35 #ifdef CACAO_TYPECHECK
  36
  37 #include "jit.h"
  38 #include "builtin.h"
  39 #include "tables.h"
  40 #include "loader.h"
  41 #include "types.h"
  42 #include "toolbox/loging.h"
  43 #include "toolbox/memory.h"
  44
  45 #define TOUCHED_YES    0x01
  46 #define TOUCHED_NO     0x02
  47 #define TOUCHED_MAYBE  (TOUCHED_YES | TOUCHED_NO)
  48
  49 #define REACH_STD      0  /* reached by branch or fallthrough */
  50 #define REACH_JSR      1  /* reached by JSR */
  51 #define REACH_RET      2  /* reached by RET */ /* XXX ? */
  52 #define REACH_THROW    3  /* reached by THROW (exception handler) */
  53
  54 /****************************************************************************/
  55 /* DEBUG HELPERS                                                            */
  56 /****************************************************************************/
  57
  58 #ifdef TYPECHECK_VERBOSE_OPT
  59 bool typecheckverbose = false;
  60 #define DOLOG(action)  do { if (typecheckverbose) {action;} } while(0)
  61 #else
  62 #define DOLOG(action)
  63 #endif
  64
  65 #ifdef TYPECHECK_VERBOSE
  66 #define TYPECHECK_VERBOSE_IMPORTANT
  67 #define LOG(str)           DOLOG(log_text(str))
  68 #define LOG1(str,a)        DOLOG(dolog(str,a))
  69 #define LOG2(str,a,b)      DOLOG(dolog(str,a,b))
  70 #define LOG3(str,a,b,c)    DOLOG(dolog(str,a,b,c))
  71 #define LOGIF(cond,str)    DOLOG(do {if (cond) log_text(str);} while(0))
  72 #define LOGINFO(info)      DOLOG(do {typeinfo_print_short(get_logfile(),info);log_plain("\n");} while(0))
  73 #define LOGFLUSH           DOLOG(fflush(get_logfile()))
  74 #define LOGNL              DOLOG(log_plain("\n"))
  75 #define LOGSTR(str)        DOLOG(dolog_plain(str))
  76 #define LOGSTR1(str,a)     DOLOG(dolog_plain(str,a))
  77 #define LOGSTR2(str,a,b)   DOLOG(dolog_plain(str,a,b))
  78 #define LOGSTR3(str,a,b,c) DOLOG(dolog_plain(str,a,b,c))
  79 #define LOGSTRu(utf)       DOLOG(log_plain_utf(utf))
  80 #else
  81 #define LOG(str)
  82 #define LOG1(str,a)
  83 #define LOG2(str,a,b)
  84 #define LOG3(str,a,b,c)
  85 #define LOGIF(cond,str)
  86 #define LOGINFO(info)
  87 #define LOGFLUSH
  88 #define LOGNL
  89 #define LOGSTR(str)
  90 #define LOGSTR1(str,a)
  91 #define LOGSTR2(str,a,b)
  92 #define LOGSTR3(str,a,b,c)
  93 #define LOGSTRu(utf)
  94 #endif
  95
  96 #ifdef TYPECHECK_VERBOSE_IMPORTANT
  97 #define LOGimp(str)     DOLOG(log_text(str))
  98 #define LOGimpSTR(str)  DOLOG(dolog_plain(str))
  99 #define LOGimpSTRu(utf) DOLOG(log_plain_utf(utf))
 100 #else
 101 #define LOGimp(str)
 102 #define LOGimpSTR(str)
 103 #define LOGimpSTRu(utf)
 104 #endif
 105
 106 #if defined(TYPECHECK_VERBOSE) || defined(TYPECHECK_VERBOSE_IMPORTANT)
 107
 108 static
 109 void
 110 typeinfo_print_locals(FILE *file,u1 *vtype,typeinfo *vinfo,u1 *touched,int num)
 111 {
 112     int i;
 113
 114     for (i=0; i<num; ++i) {
 115         if (touched)
 116             fprintf(file," %d%s=",i,
 117                     (touched[i]==TOUCHED_YES) ? "*"
 118                     : ((touched[i]==TOUCHED_NO) ? "" : "~"));
 119         else
 120             fprintf(file," %d=",i);
 121         typeinfo_print_type(file,vtype[i],vinfo+i);
 122     }
 123 }
 124
 125 static
 126 void
 127 typeinfo_print_stack(FILE *file,stackptr stack)
 128 {
 129     while (stack) {
 130         typeinfo_print_type(file,stack->type,&stack->typeinfo);
 131         stack = stack->prev;
 132         if (stack) fprintf(file," ");
 133     }
 134 }
 135
 136 static
 137 void
 138 typeinfo_print_block(FILE *file,stackptr instack,
 139                      u1 *vtype,typeinfo *vinfo,u1 *touched)
 140 {
 141     fprintf(file,"Stack: ");
 142     typeinfo_print_stack(file,instack);
 143     fprintf(file," Locals:");
 144     typeinfo_print_locals(file,vtype,vinfo,touched,maxlocals);
 145 }
 146
 147
 148 static
 149 void
 150 typeinfo_print_blocks(FILE *file,u1 *vtype,typeinfo *vinfo)
 151 {
 152     int bi;
 153     /*    int j;*/
 154
 155     for (bi=0; bi<block_count; ++bi) {
 156         fprintf(file,"%04d: (%3d) ",bi,block[bi].flags);
 157         typeinfo_print_block(file,block[bi].instack,
 158                              vtype+maxlocals*bi,vinfo+maxlocals*bi,NULL);
 159         fprintf(file,"\n");
 160
 161 /*         for (j=0; j<block[bi].icount; ++j) { */
 162 /*             fprintf(file,"\t%s\n",icmd_names[block[bi].iinstr[j].opc]); */
 163 /*         } */
 164
 165         show_icmd_block(block+bi);
 166     }
 167 }
 168
 169 #endif
 170
 171 /****************************************************************************/
 172 /* INTERNAL DATA STRUCTURES                                                 */
 173 /****************************************************************************/
 174
 175 typedef struct jsr_record jsr_record;
 176
 177 /*
 178  * For each basic block we store the chain of JSR instructions which
 179  * were used to reach the block (usually zero or one). For more
 180  * details on verifying JSR and RET instructions see the Java VM
 181  * Specification.
 182  *
 183  * CAUTION: The fields starting with sbr_ are only valid for the
 184  * jsr_record of the first block of the subroutine.
 185  */
 186 struct jsr_record {
 187     basicblock *target;      /* target of the JSR instruction (first block of subroutine) */
 188     jsr_record *next;        /* for chaining in nested try ... finally */ /* XXX make it sbr_next? */
 189     u1         *sbr_touched; /* specifies which variables the subroutine touches */
 190     u1         *sbr_vtype;   /* Types of local variables after RET */
 191     typeinfo   *sbr_vinfo;   /* Types of local variables after RET */
 192     u1          touched[1];  /* touched flags for local variables */
 193 };
 194
 195 /****************************************************************************/
 196 /* MACROS USED INTERNALLY IN typecheck()                                    */
 197 /****************************************************************************/
 198
 199 #define TOUCH_VARIABLE(num) do {if (jsrchain) touched[num] = TOUCHED_YES;} while (0)
 200 #define TOUCH_TWOWORD(num)  do {TOUCH_VARIABLE(num);TOUCH_VARIABLE((num)+1);} while (0)
 201
 202 /* XXX should check num in range? */
 203 /* XXX invalidate two word variables on store in second half! */
 204 #define STORE_TYPE(num,type)       do {vtype[(num)] = (type); TOUCH_VARIABLE(num);} while(0)
 205 #define STORE_INVALID(num)         STORE_TYPE((num),TYPE_VOID)
 206 #define STORE_PRIMITIVE(num,type)  STORE_TYPE((num),(type))
 207 #define STORE_TWOWORD(num,type)    {STORE_PRIMITIVE((num),(type));STORE_INVALID((num)+1);}
 208
 209 #define CHECKVARTYPE(num,type)  \
 210             {if (vtype[(num)] != (type)) panic("Variable type mismatch"); TOUCH_VARIABLE(num);}
 211
 212 /* XXX maybe it's faster to copy always */
 213 #define COPYTYPE(source,dest)   \
 214             {if ((source)->type == TYPE_ADR) \
 215                  TYPEINFO_COPY((source)->typeinfo,(dest)->typeinfo);}
 216
 217 #define ISBUILTIN(v)   (iptr->val.a == (functionptr)(v))
 218
 219 /* TYPECHECK_COPYVARS: copy the types and typeinfos of the current local
 220  *     variables to the local variables of the target block.
 221  * Input:
 222  *     vtype......current local variable types
 223  *     vinfo......current local variable typeinfos
 224  *     ttype......local variable types of target block
 225  *     tinfo......local variable typeinfos of target block
 226  *     maxlocals..number of local variables
 227  * Used:
 228  *     macro_i
 229  */
 230 #define TYPECHECK_COPYVARS                                      \
 231     do {                                                        \
 232     LOG("TYPECHECK_COPYVARS");                                  \
 233     for (macro_i=0; macro_i<maxlocals; ++macro_i) {             \
 234         if ((ttype[macro_i] = vtype[macro_i]) == TYPE_ADR)      \
 235             TYPEINFO_CLONE(vinfo[macro_i],tinfo[macro_i]);      \
 236     } } while(0)
 237
 238 /* TYPECHECK_MERGEVARS: merge the local variables of the target block
 239  *     with the current local variables.
 240  * Input:
 241  *     vtype......current local variable types
 242  *     vinfo......current local variable typeinfos
 243  *     ttype......local variable types of target block
 244  *     tinfo......local variable typeinfos of target block
 245  *     maxlocals..number of local variables
 246  * Ouput:
 247  *     changed....set to true if any typeinfo has changed
 248  * Used:
 249  *     macro_i
 250  */
 251 #define TYPECHECK_MERGEVARS                                             \
 252     do {                                                                \
 253     LOG("TYPECHECK_MERGEVARS");                                         \
 254     for (macro_i=0; macro_i<maxlocals; ++macro_i) {                     \
 255         if ((ttype[macro_i] != TYPE_VOID) && (vtype[macro_i] != ttype[macro_i])) { \
 256             LOG3("var %d: type %d + type %d = void",macro_i,ttype[macro_i],vtype[macro_i]); \
 257             ttype[macro_i] = TYPE_VOID;                                 \
 258             changed = true;                                             \
 259         } else if (ttype[macro_i] == TYPE_ADR) {                        \
 260             if ( ((TYPEINFO_IS_PRIMITIVE(tinfo[macro_i])) ? 1 : 0)      \
 261                  ^                                                      \
 262                  ((TYPEINFO_IS_PRIMITIVE(vinfo[macro_i])) ? 1 : 0)) {   \
 263                 LOG1("var %d: primitive + reference merge",macro_i);    \
 264                 ttype[macro_i] = TYPE_VOID;                             \
 265                 changed = true;                                         \
 266             }                                                           \
 267             else {                                                      \
 268                 LOG1("var %d:",macro_i);                                \
 269                 LOGINFO(tinfo+macro_i);                                 \
 270                 LOGINFO(vinfo+macro_i);                                 \
 271                 changed |= typeinfo_merge(tinfo+macro_i,vinfo+macro_i); \
 272                 LOGINFO(tinfo+macro_i);                                 \
 273                 LOGIF(changed,"vars have changed");                     \
 274             }                                                           \
 275         };                                                              \
 276     } } while (0)
 277
 278 /* TYPECHECK_MERGEJSR:
 279  *
 280  * Input:
 281  * Ouput:
 282  *     tbptr......target block
 283  *     changed....set to true if any typeinfo has changed
 284  *     maxlocals..number of local variables
 285  *     touched....current touched flags of local variables
 286  * Used:
 287  *     macro_i, jsrtemp, jsrtemp2
 288  */
 289 #define TYPECHECK_MERGEJSR                                              \
 290     do {                                                                \
 291         LOG("TYPECHECK_MERGEJSR");                                      \
 292     jsrtemp = jsrbuffer[tbptr-block];                                   \
 293     jsrtemp2 = jsrchain;                                                \
 294     while (jsrtemp || jsrtemp2) {                                       \
 295         if (!jsrtemp || !jsrtemp2)                                      \
 296             panic("Merging JSR subroutines of different depth");        \
 297         if (jsrtemp->target != jsrtemp2->target)                        \
 298             panic("Merging different JSR subroutines");                 \
 299         jsrtemp = jsrtemp->next;                                        \
 300         jsrtemp2 = jsrtemp2->next;                                      \
 301     }                                                                   \
 302     jsrtemp = jsrbuffer[tbptr-block];                                   \
 303     if (jsrtemp)                                                        \
 304         for (macro_i=0; macro_i<maxlocals; ++macro_i) {                 \
 305             jsrtemp->touched[i] |= touched[i];                          \
 306     } } while (0)
 307
 308 /* TYPECHECK_COPYSTACK: copy the typeinfos of the current stack to
 309  *     the input stack of the target block.
 310  * Input:
 311  *     srcstack...current stack
 312  *     dststack...input stack of target block
 313  */
 314 #define TYPECHECK_COPYSTACK                                             \
 315     do {                                                                \
 316     LOG("TYPECHECK_COPYSTACK");                                         \
 317     while (srcstack) {                                                  \
 318         LOG1("copy %d",srcstack->type);                                 \
 319         if (!dststack) panic("Stack depth mismatch");                   \
 320         if (srcstack->type != dststack->type)                           \
 321             panic("Type mismatch on stack");                            \
 322         if (srcstack->type == TYPE_ADR) {                               \
 323             TYPEINFO_CLONE(srcstack->typeinfo,dststack->typeinfo);      \
 324         }                                                               \
 325         dststack = dststack->prev;                                      \
 326         srcstack = srcstack->prev;                                      \
 327     }                                                                   \
 328     if (dststack) panic("Stack depth mismatch");                        \
 329     } while (0)
 330
 331 /* TYPECHECK_MERGESTACK: merge the input stack of the target block
 332  *     with the current stack.
 333  * Input:
 334  *     srcstack...current stack
 335  *     dststack...input stack of target block
 336  * Ouput:
 337  *     changed....set to true if any typeinfo has changed
 338  */
 339 #define TYPECHECK_MERGESTACK                                            \
 340     do {                                                                \
 341     LOG("TYPECHECK_MERGESTACK");                                        \
 342     while (srcstack) {                                                  \
 343         if (!dststack) panic("Stack depth mismatch");                   \
 344         if (srcstack->type != dststack->type)                           \
 345             panic("Type mismatch on stack");                            \
 346         if (srcstack->type == TYPE_ADR) {                               \
 347             LOGINFO(&dststack->typeinfo);                               \
 348             LOGINFO(&srcstack->typeinfo);  LOGFLUSH;                    \
 349             changed |= typeinfo_merge(&dststack->typeinfo,              \
 350                                       &srcstack->typeinfo);             \
 351             LOGINFO(&dststack->typeinfo);                               \
 352             LOG((changed)?"CHANGED!\n":"not changed.\n");               \
 353         }                                                               \
 354         dststack = dststack->prev;                                      \
 355         srcstack = srcstack->prev;                                      \
 356     }                                                                   \
 357     if (dststack) panic("Stack depth mismatch");                        \
 358     } while(0)
 359
 360
 361 /* TYPECHECK_CHECK_JSR_CHAIN: checks if the target block is reached by
 362  *     the same JSR targets on all control paths.
 363  *
 364  * Input:
 365  *     tbptr......target block
 366  *     jsrchain...current JSR target chain
 367  *     jsrbuffer..JSR target chain for each basic block
 368  * Output:
 369  *     panic if the JSR target chains don't match
 370  * Used:
 371  *     jsrtemp, jsrtemp2
 372  */
 373 #define TYPECHECK_CHECK_JSR_CHAIN                                       \
 374     do {                                                                \
 375     jsrtemp = jsrbuffer[tbptr-block];                                   \
 376     if (!jsrtemp) panic("non-subroutine called by JSR");                \
 377     if (jsrtemp->target != tbptr)                                       \
 378         panic("Merging different JSR subroutines");                     \
 379     jsrtemp = jsrtemp->next;                                            \
 380     jsrtemp2 = jsrchain;                                                \
 381     while (jsrtemp || jsrtemp2) {                                       \
 382         if (!jsrtemp || !jsrtemp2)                                      \
 383             panic("Merging JSR subroutines of different depth");        \
 384         if (jsrtemp->target != jsrtemp2->target)                        \
 385             panic("Merging different JSR subroutines");                 \
 386         jsrtemp = jsrtemp->next;                                        \
 387         jsrtemp2 = jsrtemp2->next;                                      \
 388     } } while (0)
 389
 390 /* TYPECHECK_ADD_JSR: add a JSR target to the current JSR target chain
 391  *     and store the resulting chain in the target block.
 392  *
 393  * Input:
 394  *     jsrchain...current JSR target chain
 395  *     tbptr.....the basic block targeted by the JSR
 396  *     maxlocals..number of local variables
 397  *     jsrbuffer..JSR target chain for each basic block
 398  * Used:
 399  *     jsrtemp
 400  */
 401 #define TYPECHECK_ADD_JSR                                               \
 402     do {                                                                \
 403         LOG1("adding JSR to block %04d",(tbptr)-block);                 \
 404     jsrtemp = (jsr_record *) dump_alloc(sizeof(jsr_record)+(maxlocals-1)*sizeof(u1)); \
 405     jsrtemp->target = (tbptr);                                          \
 406     jsrtemp->next = jsrchain;                                           \
 407     jsrtemp->sbr_touched = NULL;                                        \
 408     memset(&jsrtemp->touched,TOUCHED_NO,sizeof(u1)*maxlocals);          \
 409     jsrbuffer[tbptr-block] = jsrtemp;                                   \
 410     } while (0)
 411
 412 /* TYPECHECK_COPYJSR: copy the current JSR chain to the target block.
 413  *
 414  * Input:
 415  *     chain......current JSR target chain
 416  *     tbptr.....the basic block targeted by the JSR
 417  *     maxlocals..number of local variables
 418  *     jsrbuffer..JSR target chain for each basic block
 419  *     touched....current touched flags of local variables
 420  * Used:
 421  *     jsrtemp
 422  */
 423 #define TYPECHECK_COPYJSR(chain)                                        \
 424     do {                                                                \
 425         LOG("TYPECHECK_COPYJSR");                                       \
 426         if (chain) {                                                    \
 427             jsrtemp = (jsr_record *) dump_alloc(sizeof(jsr_record)+(maxlocals-1)*sizeof(u1)); \
 428             jsrtemp->target = (chain)->target;                          \
 429             jsrtemp->next = (chain)->next;                              \
 430             jsrtemp->sbr_touched = NULL;                                \
 431             memcpy(&jsrtemp->touched,touched,sizeof(u1)*maxlocals);     \
 432             jsrbuffer[tbptr-block] = jsrtemp;                           \
 433         }                                                               \
 434         else                                                            \
 435             jsrbuffer[tbptr-block] = NULL;                              \
 436     } while (0)
 437
 438 /* TYPECHECK_REACH: executed, when the target block (tbptr) can be reached
 439  *     from the current block (bptr). The types of local variables and
 440  *     stack slots are propagated to the target block.
 441  * Input:
 442  *     bptr.......current block
 443  *     tbptr......target block
 444  *     dst........current output stack pointer (not needed for REACH_THROW)
 445  *     vtype......current local variable types
 446  *     vinfo......current local variable typeinfos
 447  *     jsrchain...current JSR target chain
 448  *     jsrbuffer..JSR target chain for each basic block
 449  *     way........in which way the block is reached (REACH_ constant)
 450  *     touched....current touched flags of local variables
 451  * Output:
 452  *     repeat.....changed to true if a block before the current
 453  *                block has changed
 454  * Used:
 455  *     ttype, tinfo, srcstack, dststack, changed, macro_i
 456  */
 457 #define TYPECHECK_REACH(way)                                            \
 458     do {                                                                \
 459     LOG2("reaching block %04d (%d)",tbptr-block,way);                   \
 460     srcstack = dst;                                                     \
 461     dststack = tbptr->instack;                                          \
 462     ttype = vartype + maxlocals*(tbptr-block);                          \
 463     tinfo = vartypeinfo + maxlocals*(tbptr-block);                      \
 464     if (tbptr->flags == BBTYPECHECK_UNDEF) {                            \
 465         /* This block is reached for the first time */                  \
 466         if (way == REACH_JSR) {                                         \
 467             TYPECHECK_ADD_JSR;                                          \
 468             TYPECHECK_COPYVARS;                                         \
 469         }                                                               \
 470         else {                                                          \
 471             TYPECHECK_COPYJSR(jsrchain);                                \
 472             TYPECHECK_COPYVARS;                                         \
 473         }                                                               \
 474         if (way != REACH_THROW) TYPECHECK_COPYSTACK;                    \
 475         changed = true;                                                 \
 476     } else {                                                            \
 477         /* This block has been reached before */                        \
 478         changed = false;                                                \
 479         if (way == REACH_JSR)                                           \
 480             TYPECHECK_CHECK_JSR_CHAIN;                                  \
 481         else                                                            \
 482             TYPECHECK_MERGEJSR;                                         \
 483         TYPECHECK_MERGEVARS;                                            \
 484         if (way != REACH_THROW) TYPECHECK_MERGESTACK;                   \
 485     }                                                                   \
 486     if (changed) {                                                      \
 487         LOG("REACHED!");                                                \
 488         tbptr->flags = BBTYPECHECK_REACHED;                             \
 489         if (tbptr <= bptr) {repeat = true; LOG("MUST REPEAT!");}        \
 490     }                                                                   \
 491     LOG("done.");                                                       \
 492     } while (0)
 493
 494 /****************************************************************************/
 495 /* typecheck()                                                              */
 496 /****************************************************************************/
 497
 498 #define MAXPARAMS 255
 499
 500 /* typecheck is called directly after analyse_stack */
 501 void
 502 typecheck()
 503 {
 504     int b_count, b_index;
 505     stackptr curstack;      /* input stack top for current instruction */
 506     stackptr srcstack;         /* source stack for copying and merging */
 507     stackptr dststack;         /* target stack for copying and merging */
 508     int opcode;                                      /* current opcode */
 509     int macro_i, i;                              /* temporary counters */
 510     int len;                        /* for counting instructions, etc. */
 511     bool superblockend;        /* true if no fallthrough to next block */
 512     bool repeat;            /* if true, blocks are iterated over again */
 513     bool changed;                                    /* used in macros */
 514     instruction *iptr;               /* pointer to current instruction */
 515     basicblock *bptr;                /* pointer to current basic block */
 516     basicblock *tbptr;                   /* temporary for target block */
 517     u1 *vartype;            /* type of each local for each basic block */
 518     typeinfo *vartypeinfo;  /* type of each local for each basic block */
 519     u1 *vtype;           /* type of each local for current instruction */
 520     typeinfo *vinfo;     /* type of each local for current instruction */
 521     u1 *ttype;                                    /* temporary pointer */
 522     typeinfo *tinfo;                              /* temporary pointer */
 523     typeinfo tempinfo;                                    /* temporary */
 524     int returntype;                   /* return type of current method */
 525     typeinfo returntypeinfo;               /* typeinfo for return type */
 526     u1 *ptype;                     /* parameter types of called method */
 527     typeinfo *pinfo;           /* parameter typeinfos of called method */
 528     int rtype;                         /* return type of called method */
 529     typeinfo rinfo;       /* typeinfo for return type of called method */
 530     stackptr dst;               /* output stack of current instruction */
 531     basicblock **tptr;    /* pointer into target list of switch instructions */
 532     jsr_record **jsrbuffer;   /* JSR target chain for each basic block */
 533     jsr_record *jsrchain;               /* JSR chain for current block */
 534     jsr_record *jsrtemp,*jsrtemp2;              /* temporary variables */
 535     jsr_record *subroutine;    /* jsr_record of the current subroutine */
 536     u1 *touched;                  /* touched flags for local variables */
 537     xtable **handlers;                    /* active exception handlers */
 538     classinfo *cls;                                       /* temporary */
 539     bool maythrow;               /* true if this instruction may throw */
 540
 541     LOGSTR("\n==============================================================================\n");
 542     DOLOG(show_icmd_method());
 543     LOGSTR("\n==============================================================================\n");
 544     LOGimpSTR("Entering typecheck: ");
 545     LOGimpSTRu(method->name);
 546     LOGimpSTR("    ");
 547     LOGimpSTRu(method->descriptor);
 548     LOGimpSTR("    (class ");
 549     LOGimpSTRu(method->class->name);
 550     LOGimpSTR(")\n");
 551
 552     /* XXX allocate buffers for method arguments */
 553     ptype = DMNEW(u1,MAXPARAMS);
 554     pinfo = DMNEW(typeinfo,MAXPARAMS);
 555
 556     LOG("Buffer allocated.\n");
 557
 558     /* reset all BBFINISHED blocks to BBTYPECHECK_UNDEF. */
 559     b_count = block_count;
 560     bptr = block;
 561     while (--b_count >= 0) {
 562 #ifdef TYPECHECK_DEBUG
 563         if (bptr->flags != BBFINISHED && bptr->flags != BBDELETED
 564             && bptr->flags != BBUNDEF)
 565         {
 566             show_icmd_method();
 567             LOGSTR1("block flags: %d\n",bptr->flags); LOGFLUSH;
 568             panic("Internal error: Unexpected block flags in typecheck()");
 569         }
 570 #endif
 571         if (bptr->flags >= BBFINISHED) {
 572             bptr->flags = BBTYPECHECK_UNDEF;
 573         }
 574         bptr++;
 575     }
 576
 577     /* The first block is always reached */
 578     if (block_count && block[0].flags == BBTYPECHECK_UNDEF)
 579         block[0].flags = BBTYPECHECK_REACHED;
 580
 581     LOG("Blocks reset.\n");
 582
 583     /* allocate the buffers for local variables */
 584     vartype = DMNEW(u1,maxlocals * (block_count+1));
 585     vartypeinfo = DMNEW(typeinfo,maxlocals * (block_count+1));
 586     touched = DMNEW(u1,maxlocals);
 587     vtype = vartype + maxlocals * block_count;
 588     vinfo = vartypeinfo + maxlocals * block_count;
 589     memset(vartype,TYPE_VOID,maxlocals * (block_count+1) * sizeof(typeinfo));
 590     memset(vartypeinfo,0,maxlocals * (block_count+1) * sizeof(typeinfo));
 591
 592     LOG("Variable buffer initialized.\n");
 593
 594     /* allocate the buffer for storing JSR target chains */
 595     jsrbuffer = DMNEW(jsr_record*,block_count);
 596     memset(jsrbuffer,0,block_count * sizeof(jsr_record*));
 597     jsrchain = NULL;
 598
 599     LOG("jsrbuffer initialized.\n");
 600
 601     /* allocate the buffer of active exception handlers */
 602     handlers = DMNEW(xtable*,method->exceptiontablelength + 1);
 603
 604     /* initialize the variable types of the first block */
 605     /* to the types of the arguments */
 606     ttype = vartype;
 607     tinfo = vartypeinfo;
 608
 609     /* if this is an instance method initialize the "this" ref type */
 610     if (!(method->flags & ACC_STATIC)) {
 611         *ttype++ = TYPE_ADDRESS;
 612         TYPEINFO_INIT_CLASSINFO(*tinfo,class);
 613         tinfo++;
 614     }
 615
 616     LOG("'this' argument set.\n");
 617
 618     /* the rest of the arguments and the return type */
 619     typeinfo_init_from_method_args(method->descriptor,ttype,tinfo,
 620                                    maxlocals - (tinfo-vartypeinfo),
 621                                    true, /* two word types use two slots */
 622                                    &returntype,&returntypeinfo);
 623
 624     LOG("Arguments set.\n");
 625
 626     /* initialize the input stack of exception handlers */
 627     for (i=0; i<method->exceptiontablelength; ++i) {
 628         cls = extable[i].catchtype;
 629         if (!cls) cls = class_java_lang_Throwable;
 630         LOGSTR1("handler %i: ",i); LOGSTRu(cls->name); LOGNL;
 631         TYPEINFO_INIT_CLASSINFO(extable[i].handler->instack->typeinfo,cls);
 632     }
 633
 634     LOG("Exception handler stacks set.\n");
 635
 636     /* loop while there are still blocks to be checked */
 637     do {
 638
 639         repeat = false;
 640
 641         b_count = block_count;
 642         bptr = block;
 643
 644         while (--b_count >= 0) {
 645             LOGSTR1("---- BLOCK %04d, ",bptr-block);
 646             LOGSTR1("blockflags: %d\n",bptr->flags);
 647             LOGFLUSH;
 648
 649             if (bptr->flags == BBTYPECHECK_REACHED) {
 650                 LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",bptr-block);
 651                 LOGFLUSH;
 652
 653                 superblockend = false;
 654                 bptr->flags = BBFINISHED;
 655                 b_index = bptr - block;
 656
 657                 /* init stack at the start of this block */
 658                 curstack = bptr->instack;
 659
 660                 /* init variable types at the start of this block */
 661                 for (i=0; i<maxlocals; ++i) {
 662                     vtype[i] = vartype[maxlocals*b_index + i];
 663                     TYPEINFO_COPY(vartypeinfo[maxlocals*b_index + i],vinfo[i]);
 664                 }
 665
 666                 /* init JSR target chain */
 667                 if ((jsrchain = jsrbuffer[b_index]) != NULL) {
 668 #ifdef TYPECHECK_VERBOSE
 669                     if (typecheckverbose) {
 670                         LOGSTR("jsr chain:");
 671                         jsrtemp = jsrchain;
 672                         while (jsrtemp) {
 673                             LOGSTR1(" L%03d",jsrtemp->target->debug_nr);
 674                             jsrtemp = jsrtemp->next;
 675                         }
 676                         LOGNL;
 677                         LOGFLUSH;
 678                     }
 679 #endif
 680
 681                     subroutine = jsrbuffer[jsrchain->target - block];
 682                     memcpy(touched,jsrchain->touched,sizeof(u1)*maxlocals);
 683                 }
 684                 else
 685                     subroutine = NULL;
 686 #ifdef TYPECHECK_VERBOSE
 687                 if (typecheckverbose) {
 688                     if (subroutine) {LOGSTR1("subroutine L%03d\n",subroutine->target->debug_nr);LOGFLUSH;}
 689                     typeinfo_print_block(get_logfile(),curstack,vtype,vinfo,(jsrchain) ? touched : NULL);
 690                     LOGNL; LOGFLUSH;
 691                 }
 692 #endif
 693
 694                 /* determine the active exception handlers for this block */
 695                 /* XXX could use a faster algorithm with sorted lists or
 696                  * something? */
 697                 len = 0;
 698                 for (i=0; i<method->exceptiontablelength; ++i) {
 699                     if ((extable[i].start <= bptr) && (extable[i].end > bptr)) {
 700                         LOG1("active handler L%03d",extable[i].handler->debug_nr);
 701                         handlers[len++] = extable + i;
 702                     }
 703                 }
 704                 handlers[len] = NULL;
 705
 706                 /* loop over the instructions */
 707                 len = bptr->icount;
 708                 iptr = bptr->iinstr;
 709                 while (--len >= 0)  {
 710                     DOLOG(show_icmd(iptr,false));
 711                     LOGNL;
 712                     LOGFLUSH;
 713
 714                     opcode = iptr->opc;
 715                     dst = iptr->dst;
 716                     maythrow = false;
 717
 718                     switch (opcode) {
 719
 720                         /****************************************/
 721                         /* STACK MANIPULATIONS                  */
 722
 723                         /* We just need to copy the typeinfo */
 724                         /* for slots containing addresses.   */
 725
 726                       case ICMD_DUP:
 727                           COPYTYPE(curstack,dst);
 728                           break;
 729
 730                       case ICMD_DUP_X1:
 731                           COPYTYPE(curstack,dst);
 732                           COPYTYPE(curstack,dst-2);
 733                           COPYTYPE(curstack->prev,dst-1);
 734                           break;
 735
 736                       case ICMD_DUP_X2:
 737                           COPYTYPE(curstack,dst);
 738                           COPYTYPE(curstack,dst-3);
 739                           COPYTYPE(curstack->prev,dst-1);
 740                           COPYTYPE(curstack->prev->prev,dst-2);
 741                           break;
 742
 743                       case ICMD_DUP2:
 744                           COPYTYPE(curstack,dst);
 745                           COPYTYPE(curstack->prev,dst-1);
 746                           break;
 747
 748                       case ICMD_DUP2_X1:
 749                           COPYTYPE(curstack,dst);
 750                           COPYTYPE(curstack->prev,dst-1);
 751                           COPYTYPE(curstack,dst-3);
 752                           COPYTYPE(curstack->prev,dst-4);
 753                           COPYTYPE(curstack->prev->prev,dst-2);
 754                           break;
 755
 756                       case ICMD_DUP2_X2:
 757                           COPYTYPE(curstack,dst);
 758                           COPYTYPE(curstack->prev,dst-1);
 759                           COPYTYPE(curstack,dst-4);
 760                           COPYTYPE(curstack->prev,dst-5);
 761                           COPYTYPE(curstack->prev->prev,dst-2);
 762                           COPYTYPE(curstack->prev->prev->prev,dst-3);
 763                           break;
 764
 765                       case ICMD_SWAP:
 766                           COPYTYPE(curstack,dst-1);
 767                           COPYTYPE(curstack->prev,dst);
 768                           break;
 769
 770                           /* XXX only add these cases in debug mode? */
 771                       case ICMD_POP:
 772                           break;
 773
 774                       case ICMD_POP2:
 775                           break;
 776
 777                           /****************************************/
 778                           /* LOADING ADDRESS FROM VARIABLE        */
 779
 780                       case ICMD_ALOAD:
 781                           CHECKVARTYPE(iptr->op1,TYPE_ADR);
 782
 783                           /* loading a returnAddress is not allowed */
 784                           if (TYPEINFO_IS_PRIMITIVE(vinfo[iptr->op1]))
 785                               panic("illegal instruction: ALOAD loading returnAddress");
 786
 787                           TYPEINFO_COPY(vinfo[iptr->op1],dst->typeinfo);
 788                           break;
 789
 790                           /****************************************/
 791                           /* STORING ADDRESS TO VARIABLE          */
 792
 793                       case ICMD_ASTORE:
 794                           /* TYPE_ADR has already been checked. */
 795                           STORE_TYPE(iptr->op1,TYPE_ADDRESS);
 796                           TYPEINFO_COPY(curstack->typeinfo,vinfo[iptr->op1]);
 797                           break;
 798
 799                           /****************************************/
 800                           /* LOADING ADDRESS FROM ARRAY           */
 801
 802                       case ICMD_AALOAD:
 803                           if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(curstack->prev->typeinfo))
 804                               panic("illegal instruction: AALOAD on non-reference array");
 805
 806                           typeinfo_init_component(&curstack->prev->typeinfo,&dst->typeinfo);
 807                           maythrow = true;
 808                           break;
 809
 810                           /****************************************/
 811                           /* STORING ADDRESS TO ARRAY             */
 812
 813                       case ICMD_AASTORE:
 814                           /* XXX also handled by builtin3 */
 815                           /* XXX move this to unexpected instructions? */
 816                           if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(curstack->prev->prev->typeinfo))
 817                               panic("illegal instruction: AASTORE to non-reference array");
 818
 819                           /* XXX optimize */
 820                           /*
 821                             typeinfo_init_component(&curstack->prev->prev->typeinfo,&tempinfo);
 822                             if (!typeinfo_is_assignable(&curstack->typeinfo,&tempinfo))
 823                             panic("illegal instruction: AASTORE to incompatible type");
 824                           */
 825                           maythrow = true;
 826                           break;
 827
 828                           /****************************************/
 829                           /* FIELD ACCESS                         */
 830
 831                       case ICMD_PUTFIELD:
 832                           if (!TYPEINFO_IS_REFERENCE(curstack->prev->typeinfo))
 833                               panic("illegal instruction: PUTFIELD on non-reference");
 834                           if (TYPEINFO_IS_ARRAY(curstack->prev->typeinfo)) /* XXX arraystub */
 835                               panic("illegal instruction: PUTFIELD on array");
 836
 837
 838                           /* XXX */
 839                           maythrow = true;
 840                           break;
 841
 842                       case ICMD_PUTSTATIC:
 843                           /* XXX */
 844                           maythrow = true; /* XXX ? */
 845                           break;
 846
 847                       case ICMD_GETFIELD:
 848                           if (!TYPEINFO_IS_REFERENCE(curstack->typeinfo))
 849                               panic("illegal instruction: GETFIELD on non-reference");
 850                           if (TYPEINFO_IS_ARRAY(curstack->typeinfo))
 851                               panic("illegal instruction: GETFIELD on array");
 852
 853                           {
 854                               fieldinfo *fi = (fieldinfo *)(iptr->val.a);
 855                               /* XXX check non-static? */
 856                               if (dst->type == TYPE_ADR) {
 857                                   TYPEINFO_INIT_FROM_FIELDINFO(dst->typeinfo,fi);
 858                               }
 859                               else {
 860                                   /* XXX check field type? */
 861                                   TYPEINFO_INIT_PRIMITIVE(dst->typeinfo);
 862                               }
 863                           }
 864                           maythrow = true;
 865                           break;
 866
 867                       case ICMD_GETSTATIC:
 868                           {
 869                               fieldinfo *fi = (fieldinfo *)(iptr->val.a);
 870                               /* XXX check static? */
 871                               if (dst->type == TYPE_ADR) {
 872                                   TYPEINFO_INIT_FROM_FIELDINFO(dst->typeinfo,fi);
 873                               }
 874                               else {
 875                                   /* XXX check field type? */
 876                                   TYPEINFO_INIT_PRIMITIVE(dst->typeinfo);
 877                               }
 878                           }
 879                           /* XXX may throw? */
 880                           break;
 881
 882                           /****************************************/
 883                           /* PRIMITIVE ARRAY ACCESS               */
 884
 885                       case ICMD_ARRAYLENGTH:
 886                           /* XXX should this also work on arraystubs? */
 887                           if (!TYPEINFO_MAYBE_ARRAY(curstack->typeinfo))
 888                               panic("illegal instruction: ARRAYLENGTH on non-array");
 889                           maythrow = true;
 890                           break;
 891
 892                       case ICMD_BALOAD:
 893                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->typeinfo,ARRAYTYPE_BOOLEAN)
 894                               && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->typeinfo,ARRAYTYPE_BYTE))
 895                               panic("Array type mismatch");
 896                           maythrow = true;
 897                           break;
 898                       case ICMD_CALOAD:
 899                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->typeinfo,ARRAYTYPE_CHAR))
 900                               panic("Array type mismatch");
 901                           maythrow = true;
 902                           break;
 903                       case ICMD_DALOAD:
 904                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->typeinfo,ARRAYTYPE_DOUBLE))
 905                               panic("Array type mismatch");
 906                           maythrow = true;
 907                           break;
 908                       case ICMD_FALOAD:
 909                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->typeinfo,ARRAYTYPE_FLOAT))
 910                               panic("Array type mismatch");
 911                           maythrow = true;
 912                           break;
 913                       case ICMD_IALOAD:
 914                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->typeinfo,ARRAYTYPE_INT))
 915                               panic("Array type mismatch");
 916                           maythrow = true;
 917                           break;
 918                       case ICMD_SALOAD:
 919                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->typeinfo,ARRAYTYPE_SHORT))
 920                               panic("Array type mismatch");
 921                           maythrow = true;
 922                           break;
 923                       case ICMD_LALOAD:
 924                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->typeinfo,ARRAYTYPE_LONG))
 925                               panic("Array type mismatch");
 926                           maythrow = true;
 927                           break;
 928
 929                       case ICMD_BASTORE:
 930                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->prev->typeinfo,ARRAYTYPE_BOOLEAN)
 931                               && !TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->prev->typeinfo,ARRAYTYPE_BYTE))
 932                               panic("Array type mismatch");
 933                           maythrow = true;
 934                           break;
 935                       case ICMD_CASTORE:
 936                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->prev->typeinfo,ARRAYTYPE_CHAR))
 937                               panic("Array type mismatch");
 938                           maythrow = true;
 939                           break;
 940                       case ICMD_DASTORE:
 941                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->prev->typeinfo,ARRAYTYPE_DOUBLE))
 942                               panic("Array type mismatch");
 943                           maythrow = true;
 944                           break;
 945                       case ICMD_FASTORE:
 946                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->prev->typeinfo,ARRAYTYPE_FLOAT))
 947                               panic("Array type mismatch");
 948                           maythrow = true;
 949                           break;
 950                       case ICMD_IASTORE:
 951                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->prev->typeinfo,ARRAYTYPE_INT))
 952                               panic("Array type mismatch");
 953                           maythrow = true;
 954                           break;
 955                       case ICMD_SASTORE:
 956                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->prev->typeinfo,ARRAYTYPE_SHORT))
 957                               panic("Array type mismatch");
 958                           maythrow = true;
 959                           break;
 960                       case ICMD_LASTORE:
 961                           if (!TYPEINFO_MAYBE_PRIMITIVE_ARRAY(curstack->prev->prev->typeinfo,ARRAYTYPE_LONG))
 962                               panic("Array type mismatch");
 963                           maythrow = true;
 964                           break;
 965
 966                           /****************************************/
 967                           /* OPERATIONS WITH UNCHECKED INPUT      */
 968
 969                       case ICMD_CHECKCAST:
 970                           /* returnAddress is not allowed */
 971                           if (!TYPEINFO_IS_REFERENCE(curstack->typeinfo))
 972                               panic("Illegal instruction: INSTANCEOF on non-reference");
 973
 974                           /* XXX check if the cast can be done statically */
 975                           TYPEINFO_INIT_CLASSINFO(dst->typeinfo,(classinfo *)iptr[0].val.a);
 976                           /* XXX */
 977                           maythrow = true;
 978                           break;
 979
 980                       case ICMD_INSTANCEOF:
 981                           /* returnAddress is not allowed */
 982                           if (!TYPEINFO_IS_REFERENCE(curstack->typeinfo))
 983                               panic("Illegal instruction: INSTANCEOF on non-reference");
 984
 985                           /* XXX may throw ? */
 986                           break;
 987
 988                       case ICMD_ACONST:
 989                           if (iptr->val.a == NULL)
 990                               TYPEINFO_INIT_NULLTYPE(dst->typeinfo)
 991                           else
 992                               /* XXX constants for builtin functions */
 993                               /* string constants */
 994                               TYPEINFO_INIT_CLASSINFO(dst->typeinfo,class_java_lang_String);
 995                           break;
 996
 997                           /****************************************/
 998                           /* BRANCH INSTRUCTIONS                  */
 999
1000                       case ICMD_GOTO:
1001                           superblockend = true;
1002                           /* FALLTHROUGH! */
1003                       case ICMD_IFNULL:
1004                       case ICMD_IFNONNULL:
1005                       case ICMD_IFEQ:
1006                       case ICMD_IFNE:
1007                       case ICMD_IFLT:
1008                       case ICMD_IFGE:
1009                       case ICMD_IFGT:
1010                       case ICMD_IFLE:
1011                       case ICMD_IF_ICMPEQ:
1012                       case ICMD_IF_ICMPNE:
1013                       case ICMD_IF_ICMPLT:
1014                       case ICMD_IF_ICMPGE:
1015                       case ICMD_IF_ICMPGT:
1016                       case ICMD_IF_ICMPLE:
1017                       case ICMD_IF_ACMPEQ:
1018                       case ICMD_IF_ACMPNE:
1019                       case ICMD_IF_LEQ:
1020                       case ICMD_IF_LNE:
1021                       case ICMD_IF_LLT:
1022                       case ICMD_IF_LGE:
1023                       case ICMD_IF_LGT:
1024                       case ICMD_IF_LLE:
1025                       case ICMD_IF_LCMPEQ:
1026                       case ICMD_IF_LCMPNE:
1027                       case ICMD_IF_LCMPLT:
1028                       case ICMD_IF_LCMPGE:
1029                       case ICMD_IF_LCMPGT:
1030                       case ICMD_IF_LCMPLE:
1031                           tbptr = (basicblock *) iptr->target;
1032
1033                           /* propagate stack and variables to the target block */
1034                           TYPECHECK_REACH(REACH_STD);
1035                           /* XXX */
1036                           break;
1037
1038                           /****************************************/
1039                           /* SWITCHES                             */
1040
1041                       case ICMD_TABLESWITCH:
1042                           {
1043                               s4 *s4ptr = iptr->val.a;
1044                               s4ptr++; /* skip default */
1045                               i = *s4ptr++; /* low */
1046                               i = *s4ptr++ - i + 2; /* +1 for default target */
1047                           }
1048                           goto switch_instruction_tail;
1049
1050                       case ICMD_LOOKUPSWITCH:
1051                           {
1052                               s4 *s4ptr = iptr->val.a;
1053                               s4ptr++; /* skip default */
1054                               i = *s4ptr++ + 1; /* count +1 for default target */
1055                           }
1056                     switch_instruction_tail:
1057                           tptr = (basicblock **)iptr->target;
1058
1059                           while (--i >= 0) {
1060                               tbptr = *tptr++;
1061                               LOG2("target %d is block %04d",(tptr-(basicblock **)iptr->target)-1,tbptr-block);
1062                               TYPECHECK_REACH(REACH_STD);
1063                           }
1064                           LOG("switch done");
1065                           superblockend = true;
1066                           break;
1067
1068                           /****************************************/
1069                           /* RETURNS AND THROW                    */
1070
1071                       case ICMD_ATHROW:
1072                           TYPEINFO_INIT_CLASSINFO(tempinfo,class_java_lang_Throwable);
1073                           if (!typeinfo_is_assignable(&curstack->typeinfo,&tempinfo))
1074                               panic("illegal instruction: ATHROW on non-Throwable");
1075                           superblockend = true;
1076                           maythrow = true;
1077                           break;
1078
1079                       case ICMD_ARETURN:
1080                           if (!TYPEINFO_IS_REFERENCE(curstack->typeinfo))
1081                               panic("illegal instruction: ARETURN on non-reference");
1082
1083                           if (returntype != TYPE_ADDRESS
1084                               || !typeinfo_is_assignable(&curstack->typeinfo,&returntypeinfo))
1085                               panic("Return type mismatch");
1086
1087                           superblockend = true;
1088                           break;
1089
1090                       case ICMD_IRETURN:
1091                           if (returntype != TYPE_INT)
1092                               panic("Return type mismatch");
1093                           superblockend = true;
1094                           break;
1095                       case ICMD_LRETURN:
1096                           if (returntype != TYPE_LONG)
1097                               panic("Return type mismatch");
1098                           superblockend = true;
1099                           break;
1100                       case ICMD_FRETURN:
1101                           if (returntype != TYPE_FLOAT)
1102                               panic("Return type mismatch");
1103                           superblockend = true;
1104                           break;
1105                       case ICMD_DRETURN:
1106                           if (returntype != TYPE_DOUBLE)
1107                               panic("Return type mismatch");
1108                           superblockend = true;
1109                           break;
1110                       case ICMD_RETURN:
1111                           if (returntype != TYPE_VOID)
1112                               panic("Return type mismatch");
1113                           superblockend = true;
1114                           break;
1115
1116                           /****************************************/
1117                           /* SUBROUTINE INSTRUCTIONS              */
1118
1119                       case ICMD_JSR:
1120                           LOG("jsr");
1121
1122                           /* XXX This is a dirty hack. It is needed
1123                            * because of the special handling of ICMD_JSR in stack.c
1124                            */
1125                           dst = (stackptr) iptr->val.a;
1126
1127                           /* push return address */
1128                           TYPEINFO_INIT_PRIMITIVE(dst->typeinfo);
1129
1130                           LOG("reaching block...");
1131
1132                           /* add the target to the JSR target chain and */
1133                           /* propagate stack and variables to the target block */
1134                           tbptr = (basicblock *) iptr->target;
1135                           TYPECHECK_REACH(REACH_JSR);
1136
1137                           /* set dst to the stack after the subroutine execution */
1138                           /* XXX We assume (as in stack.c) that the
1139                            * subroutine returns the stack as it was
1140                            * before the JSR instruction. Is this
1141                            * correct?
1142                            */
1143                           dst = iptr->dst;
1144
1145                           /* Find the jsr_record of the called subroutine */
1146                           jsrtemp = jsrbuffer[tbptr - block];
1147
1148                           /* Check if we already calculated (at least
1149                            * for one RET) which variables the
1150                            * subroutine touches.
1151                            */
1152                           if (jsrtemp->sbr_touched) {
1153                               /* Calculate the local variables after the subroutine call */
1154                               for (i=0; i<maxlocals; ++i)
1155                                   if (jsrtemp->sbr_touched[i] != TOUCHED_NO) {
1156                                       TOUCH_VARIABLE(i);
1157                                       if ((vtype[i] = jsrtemp->sbr_vtype[i]) == TYPE_ADR)
1158                                           TYPEINFO_CLONE(jsrtemp->sbr_vinfo[i],vinfo[i]);
1159                                   }
1160
1161                               /* continue after the JSR call */
1162                               superblockend = false;
1163                           }
1164                           else {
1165                               /* We cannot proceed until the subroutine has been typechecked. */
1166                               /* XXX actually we would not have to check this block again */
1167                               bptr->flags = BBTYPECHECK_REACHED;
1168                               repeat = true;
1169                               superblockend = true;
1170                           }
1171                           /* XXX may throw? */
1172                           break;
1173
1174                       case ICMD_RET:
1175                           /* check returnAddress variable */
1176                           CHECKVARTYPE(iptr->op1,TYPE_ADR);
1177
1178                           if (!TYPEINFO_IS_PRIMITIVE(vinfo[iptr->op1]))
1179                               panic("illegal instruction: RET using non-returnAddress variable");
1180
1181                           /* check if we are inside a subroutine */
1182                           if (!subroutine)
1183                               panic("RET outside of subroutine");
1184
1185                           /* determine which variables are touched by this subroutine */
1186                           /* and their types */
1187                           if (subroutine->sbr_touched) {
1188                               for (i=0; i<maxlocals; ++i)
1189                                   subroutine->sbr_touched[i] |= touched[i];
1190                               ttype = subroutine->sbr_vtype;
1191                               tinfo = subroutine->sbr_vinfo;
1192                               TYPECHECK_MERGEVARS;
1193                           }
1194                           else {
1195                               subroutine->sbr_touched = DMNEW(u1,maxlocals);
1196                               memcpy(subroutine->sbr_touched,touched,sizeof(u1)*maxlocals);
1197                               subroutine->sbr_vtype = DMNEW(u1,maxlocals);
1198                               memcpy(subroutine->sbr_vtype,vtype,sizeof(u1)*maxlocals);
1199                               subroutine->sbr_vinfo = DMNEW(typeinfo,maxlocals);
1200                               for (i=0; i<maxlocals; ++i)
1201                                   if (vtype[i] == TYPE_ADR)
1202                                       TYPEINFO_CLONE(vinfo[i],subroutine->sbr_vinfo[i]);
1203                           }
1204                           /* XXX check if subroutine changed types? */
1205
1206                           LOGSTR("subroutine touches:");
1207                           DOLOG(typeinfo_print_locals(get_logfile(),subroutine->sbr_vtype,subroutine->sbr_vinfo,
1208                                                       subroutine->sbr_touched,maxlocals));
1209                           LOGNL; LOGFLUSH;
1210
1211                           /* reach blocks after JSR statements */
1212                           for (i=0; i<block_count; ++i) {
1213                               tbptr = block + i;
1214                               LOG1("block L%03d",tbptr->debug_nr);
1215                               if (tbptr->iinstr[tbptr->icount - 1].opc != ICMD_JSR)
1216                                   continue;
1217                               LOG("ends with JSR");
1218                               if ((basicblock*) tbptr->iinstr[tbptr->icount - 1].target != subroutine->target)
1219                                   continue;
1220                               tbptr++;
1221
1222                               LOG1("RET reaches block %04d",tbptr-block);
1223
1224                               /*TYPECHECK_REACH(REACH_RET);*/
1225                           }
1226
1227                           superblockend = true;
1228                           break;
1229
1230                           /****************************************/
1231                           /* INVOKATIONS                          */
1232
1233                       case ICMD_INVOKEVIRTUAL:
1234                       case ICMD_INVOKESPECIAL:
1235                       case ICMD_INVOKESTATIC:
1236                       case ICMD_INVOKEINTERFACE:
1237                           {
1238                               /* XXX check access rights */
1239
1240                               methodinfo *mi = (methodinfo*) iptr->val.a;
1241
1242                               /* XXX for INVOKESPECIAL: check if the invokation is done at all */
1243
1244                               /* fetch parameter types and return type */
1245                               /* XXX might use dst->typeinfo directly if non void */
1246                               i = 0;
1247                               if (opcode != ICMD_INVOKESTATIC) {
1248                                   ptype[0] = TYPE_ADR;
1249                                   TYPEINFO_INIT_CLASSINFO(pinfo[0],mi->class);
1250                                   i++;
1251                               }
1252                               typeinfo_init_from_method_args(mi->descriptor,ptype+i,pinfo+i,
1253                                                              MAXPARAMS-i,false,
1254                                                              &rtype,&rinfo);
1255
1256                               /* check parameter types */
1257                               srcstack = curstack;
1258                               i = mi->paramcount; /* number of parameters including 'this'*/
1259                               while (--i >= 0) {
1260                                   LOG1("param %d",i);
1261                                   if (srcstack->type != ptype[i])
1262                                       panic("Parameter type mismatch in method invocation");
1263                                   if (srcstack->type == TYPE_ADR) {
1264                                       LOGINFO(&(srcstack->typeinfo));
1265                                       LOGINFO(pinfo + i);
1266                                       if (!typeinfo_is_assignable(&(srcstack->typeinfo),pinfo+i))
1267                                           panic("Parameter reference type mismatch in method invocation");
1268                                   }
1269                                   LOG("ok");
1270
1271                                   srcstack = srcstack->prev;
1272                               }
1273
1274                               if (rtype != TYPE_VOID) {
1275                                   if (rtype != dst->type)
1276                                       panic("Return type mismatch in method invocation");
1277                                   TYPEINFO_COPY(rinfo,dst->typeinfo);
1278                               }
1279                           }
1280                           maythrow = true;
1281                           break;
1282
1283                       case ICMD_MULTIANEWARRAY:
1284                           /* check the array lengths on the stack */
1285                           i = iptr[0].op1;
1286                           if (i<1) panic("MULTIANEWARRAY with dimensions < 1");
1287                           srcstack = curstack;
1288                           while (i--) {
1289                               if (!srcstack)
1290                                   panic("MULTIANEWARRAY missing array length");
1291                               if (srcstack->type != TYPE_INT)
1292                                   panic("MULTIANEWARRAY using non-int as array length");
1293                               srcstack = srcstack->prev;
1294                           }
1295
1296                           /* set the array type of the result */
1297                           TYPEINFO_INIT_CLASSINFO(dst->typeinfo,((vftbl *)iptr[0].val.a)->class);
1298                           maythrow = true;
1299                           break;
1300
1301                       case ICMD_BUILTIN3:
1302                           if (ISBUILTIN(asm_builtin_aastore)) {
1303                               /* XXX also handled by ICMD_AASTORE */
1304                               if (!TYPEINFO_MAYBE_ARRAY_OF_REFS(curstack->prev->prev->typeinfo))
1305                                   panic("illegal instruction: AASTORE to non-reference array");
1306
1307                               /* XXX optimize */
1308                               /*
1309                                 typeinfo_init_component(&curstack->prev->prev->typeinfo,&tempinfo);
1310                                 if (!typeinfo_is_assignable(&curstack->typeinfo,&tempinfo))
1311                                 panic("illegal instruction: AASTORE to incompatible type");
1312                               */
1313                           }
1314                           /* XXX check for missed builtins in debug mode? */
1315                           maythrow = true; /* XXX better safe than sorry */
1316                           break;
1317
1318                       case ICMD_BUILTIN2:
1319                           if (
1320 #if defined(__I386__)
1321                               ISBUILTIN(asm_builtin_newarray)
1322 #else
1323                               ISBUILTIN(builtin_newarray)
1324 #endif
1325                               )
1326                           {
1327                               if (iptr[-1].opc != ICMD_ACONST)
1328                                   panic("illegal instruction: builtin_newarray without classinfo");
1329                               TYPEINFO_INIT_CLASSINFO(dst->typeinfo,((vftbl *)iptr[-1].val.a)->class);
1330                           }
1331                           else if (ISBUILTIN(asm_builtin_checkarraycast)) {
1332                               if (iptr[-1].opc != ICMD_ACONST)
1333                                   panic("illegal instruction: asm_builtin_checkarraycast without classinfo");
1334                               TYPEINFO_INIT_CLASSINFO(dst->typeinfo,((vftbl *)iptr[-1].val.a)->class);
1335                           }
1336                           /* XXX check for missed builtins in debug mode? */
1337                           maythrow = true; /* XXX better safe than sorry */
1338                           break;
1339
1340                       case ICMD_BUILTIN1:
1341                           if (ISBUILTIN(builtin_new)) {
1342                               if (iptr[-1].opc != ICMD_ACONST)
1343                                   panic("illegal instruction: builtin_new without classinfo");
1344                               TYPEINFO_INIT_CLASSINFO(dst->typeinfo,(classinfo *)iptr[-1].val.a);
1345                           }
1346                           else if (ISBUILTIN(builtin_newarray_boolean)) {
1347                               TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_BOOLEAN);
1348                           }
1349                           else if (ISBUILTIN(builtin_newarray_char)) {
1350                               TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_CHAR);
1351                           }
1352                           else if (ISBUILTIN(builtin_newarray_float)) {
1353                               TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_FLOAT);
1354                           }
1355                           else if (ISBUILTIN(builtin_newarray_double)) {
1356                               TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_DOUBLE);
1357                           }
1358                           else if (ISBUILTIN(builtin_newarray_byte)) {
1359                               TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_BYTE);
1360                           }
1361                           else if (ISBUILTIN(builtin_newarray_short)) {
1362                               TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_SHORT);
1363                           }
1364                           else if (ISBUILTIN(builtin_newarray_int)) {
1365                               TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_INT);
1366                           }
1367                           else if (ISBUILTIN(builtin_newarray_long)) {
1368                               TYPEINFO_INIT_PRIMITIVE_ARRAY(dst->typeinfo,ARRAYTYPE_LONG);
1369                           }
1370                           /* XXX check for missed builtins in debug mode? */
1371                           maythrow = true; /* XXX better safe than sorry */
1372                           break;
1373
1374                           /****************************************/
1375                           /* PRIMITIVE VARIABLE ACCESS            */
1376
1377                       case ICMD_ILOAD: CHECKVARTYPE(iptr->op1,TYPE_INT); break;
1378                       case ICMD_LLOAD: CHECKVARTYPE(iptr->op1,TYPE_LONG); break;
1379                       case ICMD_FLOAD: CHECKVARTYPE(iptr->op1,TYPE_FLOAT); break;
1380                       case ICMD_DLOAD: CHECKVARTYPE(iptr->op1,TYPE_DOUBLE); break;
1381                       case ICMD_IINC:  CHECKVARTYPE(iptr->op1,TYPE_INT); /*TOUCH_VARIABLE(iptr->op1);*/ break;
1382
1383                       case ICMD_FSTORE: STORE_PRIMITIVE(iptr->op1,TYPE_FLOAT); break;
1384                       case ICMD_ISTORE: STORE_PRIMITIVE(iptr->op1,TYPE_INT); break;
1385                       case ICMD_LSTORE: STORE_TWOWORD(iptr->op1,TYPE_LONG); break;
1386                       case ICMD_DSTORE: STORE_TWOWORD(iptr->op1,TYPE_DOUBLE); break;
1387
1388                           /****************************************/
1389                           /* INSTRUCTIONS WHICH SHOULD HAVE BEEN  */
1390                           /* REPLACED BY BUILTIN CALLS            */
1391
1392                       case ICMD_NEW:
1393                       case ICMD_NEWARRAY:
1394                       case ICMD_ANEWARRAY:
1395                       case ICMD_MONITORENTER:
1396                       case ICMD_MONITOREXIT:
1397                           /* XXX only check this in debug mode? */
1398                           LOGSTR2("ICMD %d at %d\n", iptr->opc, (int)(iptr-instr));
1399                           panic("Internal error: unexpected instruction encountered");
1400                           break;
1401
1402                           /****************************************/
1403                           /* UNCHECKED OPERATIONS                 */
1404
1405                           /* These ops have no input or output to be checked */
1406                           /* (apart from the checks done in analyse_stack).  */
1407                                                 /* XXX only add cases for them in debug mode? */
1408
1409                       case ICMD_NOP:
1410                       case ICMD_READONLY_ARG: /* XXX ? */
1411                       case ICMD_CLEAR_ARGREN: /* XXX ? */
1412                           break;
1413
1414                       case ICMD_CHECKASIZE:
1415                       case ICMD_NULLCHECKPOP:
1416                           maythrow = true;
1417                           break;
1418
1419                           /****************************************/
1420                           /* ARITHMETIC AND CONVERSION            */
1421
1422                           /* These instructions are typechecked in analyse_stack. */
1423                                                 /* XXX only add cases for them in debug mode? */
1424
1425                       case ICMD_IADD:
1426                       case ICMD_ISUB:
1427                       case ICMD_IMUL:
1428                       case ICMD_IDIV:
1429                       case ICMD_IREM:
1430                       case ICMD_INEG:
1431                       case ICMD_IAND:
1432                       case ICMD_IOR:
1433                       case ICMD_IXOR:
1434                       case ICMD_ISHL:
1435                       case ICMD_ISHR:
1436                       case ICMD_IUSHR:
1437                       case ICMD_LADD:
1438                       case ICMD_LSUB:
1439                       case ICMD_LMUL:
1440                       case ICMD_LDIV:
1441                       case ICMD_LREM:
1442                       case ICMD_LNEG:
1443                       case ICMD_LAND:
1444                       case ICMD_LOR:
1445                       case ICMD_LXOR:
1446                       case ICMD_LSHL:
1447                       case ICMD_LSHR:
1448                       case ICMD_LUSHR:
1449                       case ICMD_IREM0X10001:
1450                       case ICMD_LREM0X10001:
1451                       case ICMD_IDIVPOW2:
1452                       case ICMD_LDIVPOW2:
1453                       case ICMD_IADDCONST:
1454                       case ICMD_ISUBCONST:
1455                       case ICMD_IMULCONST:
1456                       case ICMD_IANDCONST:
1457                       case ICMD_IORCONST:
1458                       case ICMD_IXORCONST:
1459                       case ICMD_ISHLCONST:
1460                       case ICMD_ISHRCONST:
1461                       case ICMD_IUSHRCONST:
1462                       case ICMD_IREMPOW2:
1463                       case ICMD_LADDCONST:
1464                       case ICMD_LSUBCONST:
1465                       case ICMD_LMULCONST:
1466                       case ICMD_LANDCONST:
1467                       case ICMD_LORCONST:
1468                       case ICMD_LXORCONST:
1469                       case ICMD_LSHLCONST:
1470                       case ICMD_LSHRCONST:
1471                       case ICMD_LUSHRCONST:
1472                       case ICMD_LREMPOW2:
1473
1474                       case ICMD_LCMP:
1475                       case ICMD_LCMPCONST:
1476                       case ICMD_FCMPL:
1477                       case ICMD_FCMPG:
1478                       case ICMD_DCMPL:
1479                       case ICMD_DCMPG:
1480
1481                       case ICMD_FADD:
1482                       case ICMD_DADD:
1483                       case ICMD_FSUB:
1484                       case ICMD_DSUB:
1485                       case ICMD_FMUL:
1486                       case ICMD_DMUL:
1487                       case ICMD_FDIV:
1488                       case ICMD_DDIV:
1489                       case ICMD_FREM:
1490                       case ICMD_DREM:
1491                       case ICMD_FNEG:
1492                       case ICMD_DNEG:
1493
1494                       case ICMD_I2L:
1495                       case ICMD_I2F:
1496                       case ICMD_I2D:
1497                       case ICMD_L2I:
1498                       case ICMD_L2F:
1499                       case ICMD_L2D:
1500                       case ICMD_F2I:
1501                       case ICMD_F2L:
1502                       case ICMD_F2D:
1503                       case ICMD_D2I:
1504                       case ICMD_D2L:
1505                       case ICMD_D2F:
1506                       case ICMD_INT2BYTE:
1507                       case ICMD_INT2CHAR:
1508                       case ICMD_INT2SHORT:
1509
1510                           maythrow = true; /* XXX be more selective here */
1511                           break;
1512
1513                       case ICMD_ICONST:
1514                       case ICMD_LCONST:
1515                       case ICMD_FCONST:
1516                       case ICMD_DCONST:
1517
1518                       case ICMD_IFEQ_ICONST:
1519                       case ICMD_IFNE_ICONST:
1520                       case ICMD_IFLT_ICONST:
1521                       case ICMD_IFGE_ICONST:
1522                       case ICMD_IFGT_ICONST:
1523                       case ICMD_IFLE_ICONST:
1524                       case ICMD_ELSE_ICONST:
1525
1526                           break;
1527
1528                           /****************************************/
1529
1530                       default:
1531                           LOGSTR2("ICMD %d at %d\n", iptr->opc, (int)(iptr-instr));
1532                           panic("Missing ICMD code during typecheck");
1533                     }
1534
1535                     /* the output of this instruction becomes the current stack */
1536                     curstack = dst;
1537
1538                     /* reach exception handlers for this instruction */
1539                     if (maythrow) {
1540                         LOG("reaching exception handlers");
1541                         i = 0;
1542                         while (handlers[i]) {
1543                             tbptr = handlers[i]->handler;
1544                             TYPECHECK_REACH(REACH_THROW); /* XXX jsr chain? */
1545                             i++;
1546                         }
1547                     }
1548
1549                     iptr++;
1550                 } /* while instructions */
1551
1552                 LOG("instructions done");
1553                 LOGSTR("RESULT=> ");
1554                 DOLOG(typeinfo_print_block(get_logfile(),curstack,vtype,vinfo,(jsrchain) ? touched : NULL));
1555                 LOGNL; LOGFLUSH;
1556
1557                 /* propagate stack and variables to the following block */
1558                 if (!superblockend) {
1559                     LOG("reaching following block");
1560                     tbptr = bptr + 1;
1561                     while (tbptr->flags == BBDELETED) {
1562                         tbptr++;
1563 #ifdef TYPECHECK_DEBUG
1564                         if ((tbptr-block) >= block_count)
1565                             panic("Control flow falls off the last block");
1566 #endif
1567                     }
1568                     TYPECHECK_REACH(REACH_STD);
1569                 }
1570
1571             } /* if block has to be checked */
1572             bptr++;
1573         } /* while blocks */
1574
1575         LOGIF(repeat,"repeat=true");
1576     } while (repeat);
1577
1578     /* XXX reset BB... to BBFINISHED */
1579
1580     /* XXX free vartype */
1581     /* XXX free vartypeinfo */
1582             /* XXX free buffers for method arguments. */
1583
1584     /* XXX add debug check if all non-dead blocks have been checked */
1585
1586     LOGimp("exiting typecheck");
1587 }
1588
1589 #undef COPYTYPE
1590
1591 #endif /* CACAO_TYPECHECK */