1: /**********************************************************************
    2: 
    3:   compile.c - ruby node tree -> VM instruction sequence
    4: 
    5:   $Author: ko1 $
    6:   $Date: 2007-12-25 21:37:16 +0900 (Tue, 25 Dec 2007) $
    7:   created at: 04/01/01 03:42:15 JST
    8: 
    9:   Copyright (C) 2004-2007 Koichi Sasada
   10: 
   11: **********************************************************************/
   12: 
   13: #include "ruby/ruby.h"
   14: #include "ruby/node.h"
   15: 
   16: #define USE_INSN_STACK_INCREASE 1
   17: #include "vm_core.h"
   18: #include "compile.h"
   19: #include "insns.inc"
   20: #include "insns_info.inc"
   21: 
   22: #ifdef HAVE_STDARG_PROTOTYPES
   23: #include <stdarg.h>
   24: #define va_init_list(a,b) va_start(a,b)
   25: #else
   26: #include <varargs.h>
   27: #define va_init_list(a,b) va_start(a)
   28: #endif
   29: 
   30: /* iseq.c */
   31: VALUE iseq_load(VALUE self, VALUE data, VALUE parent, VALUE opt);
   32: 
   33: /* vm.c */
   34: VALUE vm_eval(void *);
   35: 
   36: /* types */
   37: 
   38: #define ISEQ_ELEMENT_NONE  INT2FIX(0x00)
   39: #define ISEQ_ELEMENT_LABEL INT2FIX(0x01)
   40: #define ISEQ_ELEMENT_INSN  INT2FIX(0x02)
   41: #define ISEQ_ELEMENT_SEQ   INT2FIX(0x03)
   42: 
   43: typedef struct iseq_link_element {
   44:     int type;
   45:     struct iseq_link_element *next;
   46:     struct iseq_link_element *prev;
   47: } LINK_ELEMENT;
   48: 
   49: typedef struct iseq_link_anchor {
   50:     LINK_ELEMENT anchor;
   51:     LINK_ELEMENT *last;
   52: } LINK_ANCHOR;
   53: 
   54: typedef struct iseq_label_data {
   55:     LINK_ELEMENT link;
   56:     int label_no;
   57:     int position;
   58:     int sc_state;
   59:     int set;
   60:     int sp;
   61: } LABEL;
   62: 
   63: typedef struct iseq_insn_data {
   64:     LINK_ELEMENT link;
   65:     int insn_id;
   66:     int line_no;
   67:     int operand_size;
   68:     int sc_state;
   69:     VALUE *operands;
   70: } INSN;
   71: 
   72: struct ensure_range {
   73:     LABEL *begin;
   74:     LABEL *end;
   75:     struct ensure_range *next;
   76: };
   77: 
   78: struct iseq_compile_data_ensure_node_stack {
   79:     NODE *ensure_node;
   80:     struct iseq_compile_data_ensure_node_stack *prev;
   81:     struct ensure_range *erange;
   82: };
   83: 
   84: #include "optinsn.inc"
   85: #if OPT_INSTRUCTIONS_UNIFICATION
   86: #include "optunifs.inc"
   87: #endif
   88: 
   89: /* for debug */
   90: #if CPDEBUG > 0
   91: static long gl_node_level = 0;
   92: static void debug_list(LINK_ANCHOR *anchor);
   93: #endif
   94: 
   95: static void dump_disasm_list(LINK_ELEMENT *elem);
   96: 
   97: static int insn_data_length(INSN *iobj);
   98: static int insn_data_line_no(INSN *iobj);
   99: static int calc_sp_depth(int depth, INSN *iobj);
  100: 
  101: static void ADD_ELEM(LINK_ANCHOR *anchor, LINK_ELEMENT *elem);
  102: 
  103: static INSN *new_insn_body(rb_iseq_t *iseq, int line_no, int insn_id, int argc, ...);
  104: static LABEL *new_label_body(rb_iseq_t *iseq, int line);
  105: 
  106: static int iseq_compile_each(rb_iseq_t *iseq, LINK_ANCHOR *anchor, NODE * n, int);
  107: static int iseq_setup(rb_iseq_t *iseq, LINK_ANCHOR *anchor);
  108: static int iseq_optimize(rb_iseq_t *iseq, LINK_ANCHOR *anchor);
  109: static int iseq_insns_unification(rb_iseq_t *iseq, LINK_ANCHOR *anchor);
  110: 
  111: static int iseq_set_local_table(rb_iseq_t *iseq, ID *tbl);
  112: static int iseq_set_exception_local_table(rb_iseq_t *iseq);
  113: static int iseq_set_arguments(rb_iseq_t *iseq, LINK_ANCHOR *anchor, NODE * node);
  114: 
  115: static int iseq_set_sequence_stackcaching(rb_iseq_t *iseq, LINK_ANCHOR *anchor);
  116: static int iseq_set_sequence(rb_iseq_t *iseq, LINK_ANCHOR *anchor);
  117: static int iseq_set_exception_table(rb_iseq_t *iseq);
  118: static int iseq_set_optargs_table(rb_iseq_t *iseq);
  119: 
  120: static int
  121: iseq_add_mark_object(rb_iseq_t *iseq, VALUE v)
  122: {
  123:     if (!SPECIAL_CONST_P(v)) {
  124:         rb_ary_push(iseq->mark_ary, v);
  125:     }
  126:     return COMPILE_OK;
  127: }
  128: 
  129: static int
  130: iseq_add_mark_object_compile_time(rb_iseq_t *iseq, VALUE v)
  131: {
  132:     if (!SPECIAL_CONST_P(v)) {
  133:         rb_ary_push(iseq->compile_data->mark_ary, v);
  134:     }
  135:     return COMPILE_OK;
  136: }
  137: 
  138: VALUE
  139: iseq_compile(VALUE self, NODE *node)
  140: {
  141:     DECL_ANCHOR(ret);
  142:     rb_iseq_t *iseq;
  143:     INIT_ANCHOR(ret);
  144:     GetISeqPtr(self, iseq);
  145: 
  146:     if (node == 0) {
  147:         COMPILE(ret, "nil", node);
  148:         iseq_set_local_table(iseq, 0);
  149:     }
  150:     else if (nd_type(node) == NODE_SCOPE) {
  151:         /* iseq type of top, method, class, block */
  152:         iseq_set_local_table(iseq, node->nd_tbl);
  153:         iseq_set_arguments(iseq, ret, node->nd_args);
  154: 
  155:         switch (iseq->type) {
  156:           case ISEQ_TYPE_BLOCK: {
  157:             LABEL *start = iseq->compile_data->start_label = NEW_LABEL(0);
  158:             LABEL *end = iseq->compile_data->end_label = NEW_LABEL(0);
  159: 
  160:             ADD_LABEL(ret, iseq->compile_data->start_label);
  161:             COMPILE(ret, "block body", node->nd_body);
  162:             ADD_LABEL(ret, iseq->compile_data->end_label);
  163: 
  164:             /* wide range catch handler must put at last */
  165:             ADD_CATCH_ENTRY(CATCH_TYPE_REDO, start, end, 0, start);
  166:             ADD_CATCH_ENTRY(CATCH_TYPE_NEXT, start, end, 0, end);
  167:             break;
  168:           }
  169:           case ISEQ_TYPE_CLASS: {
  170:             ADD_TRACE(ret, nd_line(node), RUBY_EVENT_CLASS);
  171:             COMPILE(ret, "scoped node", node->nd_body);
  172:             ADD_TRACE(ret, nd_line(node), RUBY_EVENT_END);
  173:             break;
  174:           }
  175:           case ISEQ_TYPE_METHOD: {
  176:             ADD_TRACE(ret, nd_line(node), RUBY_EVENT_CALL);
  177:             COMPILE(ret, "scoped node", node->nd_body);
  178:             ADD_TRACE(ret, nd_line(node), RUBY_EVENT_RETURN);
  179:             break;
  180:           }
  181:           default: {
  182:             COMPILE(ret, "scoped node", node->nd_body);
  183:             break;
  184:           }
  185:         }
  186:     }
  187:     else {
  188:         switch (iseq->type) {
  189:           case ISEQ_TYPE_METHOD:
  190:           case ISEQ_TYPE_CLASS:
  191:           case ISEQ_TYPE_BLOCK:
  192:           case ISEQ_TYPE_EVAL:
  193:           case ISEQ_TYPE_TOP:
  194:             rb_compile_error(ERROR_ARGS "compile/should not be reached: %s:%d",
  195:                              __FILE__, __LINE__);
  196:             break;
  197:           case ISEQ_TYPE_RESCUE:
  198:             iseq_set_exception_local_table(iseq);
  199:             COMPILE(ret, "rescue", node);
  200:             break;
  201:           case ISEQ_TYPE_ENSURE:
  202:             iseq_set_exception_local_table(iseq);
  203:             COMPILE_POPED(ret, "ensure", node);
  204:             break;
  205:           case ISEQ_TYPE_DEFINED_GUARD:
  206:             COMPILE(ret, "defined guard", node);
  207:             break;
  208:           default:
  209:             rb_bug("unknown scope");
  210:         }
  211:     }
  212: 
  213:     if (iseq->type == ISEQ_TYPE_RESCUE || iseq->type == ISEQ_TYPE_ENSURE) {
  214:         ADD_INSN2(ret, 0, getdynamic, INT2FIX(1), INT2FIX(0));
  215:         ADD_INSN1(ret, 0, throw, INT2FIX(0) /* continue throw */ );
  216:     }
  217:     else {
  218:         ADD_INSN(ret, iseq->compile_data->last_line, leave);
  219:     }
  220: 
  221:     return iseq_setup(iseq, ret);
  222: }
  223: 
  224: int
  225: iseq_translate_threaded_code(rb_iseq_t *iseq)
  226: {
  227: #if OPT_DIRECT_THREADED_CODE || OPT_CALL_THREADED_CODE
  228: 
  229: #if OPT_DIRECT_THREADED_CODE
  230:     const void *const *table = (const void **)vm_eval(0);
  231: #else
  232:     extern const void *const *get_insns_address_table();
  233:     const void *const *table = get_insns_address_table();
  234: #endif
  235:     int i;
  236: 
  237:     iseq->iseq_encoded = ALLOC_N(VALUE, iseq->iseq_size);
  238:     MEMCPY(iseq->iseq_encoded, iseq->iseq, VALUE, iseq->iseq_size);
  239: 
  240:     for (i = 0; i < iseq->iseq_size; /* */ ) {
  241:         int insn = iseq->iseq_encoded[i];
  242:         int len = insn_len(insn);
  243:         iseq->iseq_encoded[i] = (VALUE)table[insn];
  244:         i += len;
  245:     }
  246: #else
  247:     iseq->iseq_encoded = iseq->iseq;
  248: #endif
  249:     return COMPILE_OK;
  250: }
  251: 
  252: /*********************************************/
  253: /* definition of data structure for compiler */
  254: /*********************************************/
  255: 
  256: static void *
  257: compile_data_alloc(rb_iseq_t *iseq, size_t size)
  258: {
  259:     void *ptr = 0;
  260:     struct iseq_compile_data_storage *storage =
  261:         iseq->compile_data->storage_current;
  262: 
  263:     if (storage->pos + size > storage->size) {
  264:         unsigned long alloc_size = storage->size * 2;
  265: 
  266:       retry:
  267:         if (alloc_size < size) {
  268:             alloc_size *= 2;
  269:             goto retry;
  270:         }
  271:         storage->next = (void *)ALLOC_N(char, alloc_size +
  272:                                         sizeof(struct
  273:                                                iseq_compile_data_storage));
  274:         storage = iseq->compile_data->storage_current = storage->next;
  275:         storage->next = 0;
  276:         storage->pos = 0;
  277:         storage->size = alloc_size;
  278:         storage->buff = (char *)(&storage->buff + 1);
  279:     }
  280: 
  281:     ptr = (void *)&storage->buff[storage->pos];
  282:     storage->pos += size;
  283:     return ptr;
  284: }
  285: 
  286: static INSN *
  287: compile_data_alloc_insn(rb_iseq_t *iseq)
  288: {
  289:     return (INSN *)compile_data_alloc(iseq, sizeof(INSN));
  290: }
  291: 
  292: static LABEL *
  293: compile_data_alloc_label(rb_iseq_t *iseq)
  294: {
  295:     return (LABEL *)compile_data_alloc(iseq, sizeof(LABEL));
  296: }
  297: 
  298: /*
  299:  * To make Array to LinkedList, use link_anchor
  300:  */
  301: 
  302: static void
  303: verify_list(char *info, LINK_ANCHOR *anchor)
  304: {
  305: #if CPDEBUG > 0
  306:     int flag = 0;
  307:     LINK_ELEMENT *list = anchor->anchor.next, *plist = &anchor->anchor;
  308: 
  309:     while (list) {
  310:         if (plist != list->prev) {
  311:             flag += 1;
  312:         }
  313:         plist = list;
  314:         list = list->next;
  315:     }
  316: 
  317:     if (anchor->last != plist && anchor->last != 0) {
  318:         flag |= 0x70000;
  319:     }
  320: 
  321:     if (flag != 0) {
  322:         rb_bug("list verify error: %08x (%s)", flag, info);
  323:     }
  324: #endif
  325: }
  326: 
  327: /*
  328:  * elem1, elem2 => elem1, elem2, elem
  329:  */
  330: static void
  331: ADD_ELEM(LINK_ANCHOR *anchor, LINK_ELEMENT *elem)
  332: {
  333:     elem->prev = anchor->last;
  334:     anchor->last->next = elem;
  335:     anchor->last = elem;
  336:     verify_list("add", anchor);
  337: }
  338: 
  339: #if 0 /* unused */
  340: /*
  341:  * elem1, elemX => elem1, elem2, elemX
  342:  */
  343: static void
  344: INSERT_ELEM_NEXT(LINK_ELEMENT *elem1, LINK_ELEMENT *elem2)
  345: {
  346:     elem2->next = elem1->next;
  347:     elem2->prev = elem1;
  348:     elem1->next = elem2;
  349:     if (elem2->next) {
  350:         elem2->next->prev = elem2;
  351:     }
  352: }
  353: #endif
  354: 
  355: #if 0 /* unused */
  356: /*
  357:  * elemX, elem1 => elemX, elem2, elem1
  358:  */
  359: static void
  360: INSERT_ELEM_PREV(LINK_ELEMENT *elem1, LINK_ELEMENT *elem2)
  361: {
  362:     elem2->prev = elem1->prev;
  363:     elem2->next = elem1;
  364:     elem1->prev = elem2;
  365:     if (elem2->prev) {
  366:         elem2->prev->next = elem2;
  367:     }
  368: }
  369: #endif
  370: 
  371: /*
  372:  * elemX, elem1, elemY => elemX, elem2, elemY
  373:  */
  374: static void
  375: REPLACE_ELEM(LINK_ELEMENT *elem1, LINK_ELEMENT *elem2)
  376: {
  377:     elem2->prev = elem1->prev;
  378:     elem2->next = elem1->next;
  379:     if (elem1->prev) {
  380:         elem1->prev->next = elem2;
  381:     }
  382:     if (elem1->next) {
  383:         elem1->next->prev = elem2;
  384:     }
  385: }
  386: 
  387: static void
  388: REMOVE_ELEM(LINK_ELEMENT *elem)
  389: {
  390:     elem->prev->next = elem->next;
  391:     if (elem->next) {
  392:         elem->next->prev = elem->prev;
  393:     }
  394: }
  395: 
  396: static LINK_ELEMENT *
  397: FIRST_ELEMENT(LINK_ANCHOR *anchor)
  398: {
  399:     return anchor->anchor.next;
  400: }
  401: 
  402: #if 0 /* unused */
  403: static LINK_ELEMENT *
  404: LAST_ELEMENT(LINK_ANCHOR *anchor)
  405: {
  406:   return anchor->last;
  407: }
  408: #endif
  409: 
  410: static LINK_ELEMENT *
  411: POP_ELEMENT(LINK_ANCHOR *anchor)
  412: {
  413:     LINK_ELEMENT *elem = anchor->last;
  414:     anchor->last = anchor->last->prev;
  415:     anchor->last->next = 0;
  416:     verify_list("pop", anchor);
  417:     return elem;
  418: }
  419: 
  420: #if 0 /* unused */
  421: static LINK_ELEMENT *
  422: SHIFT_ELEMENT(LINK_ANCHOR *anchor)
  423: {
  424:     LINK_ELEMENT *elem = anchor->anchor.next;
  425:     if (elem) {
  426:         anchor->anchor.next = elem->next;
  427:     }
  428:     return elem;
  429: }
  430: #endif
  431: 
  432: #if 0 /* unused */
  433: static int
  434: LIST_SIZE(LINK_ANCHOR *anchor)
  435: {
  436:     LINK_ELEMENT *elem = anchor->anchor.next;
  437:     int size = 0;
  438:     while (elem) {
  439:         size += 1;
  440:         elem = elem->next;
  441:     }
  442:     return size;
  443: }
  444: #endif
  445: 
  446: static int
  447: LIST_SIZE_ZERO(LINK_ANCHOR *anchor)
  448: {
  449:     if (anchor->anchor.next == 0) {
  450:         return 1;
  451:     }
  452:     else {
  453:         return 0;
  454:     }
  455: }
  456: 
  457: /*
  458:  * anc1: e1, e2, e3
  459:  * anc2: e4, e5
  460:  *#=>
  461:  * anc1: e1, e2, e3, e4, e5
  462:  * anc2: e4, e5 (broken)
  463:  */
  464: static void
  465: APPEND_LIST(LINK_ANCHOR *anc1, LINK_ANCHOR *anc2)
  466: {
  467:     if (anc2->anchor.next) {
  468:         anc1->last->next = anc2->anchor.next;
  469:         anc2->anchor.next->prev = anc1->last;
  470:         anc1->last = anc2->last;
  471:     }
  472:     verify_list("append", anc1);
  473: }
  474: 
  475: /*
  476:  * anc1: e1, e2, e3
  477:  * anc2: e4, e5
  478:  *#=>
  479:  * anc1: e4, e5, e1, e2, e3
  480:  * anc2: e4, e5 (broken)
  481:  */
  482: static void
  483: INSERT_LIST(LINK_ANCHOR *anc1, LINK_ANCHOR *anc2)
  484: {
  485:     if (anc2->anchor.next) {
  486:         LINK_ELEMENT *first = anc1->anchor.next;
  487:         anc1->anchor.next = anc2->anchor.next;
  488:         anc1->anchor.next->prev = &anc1->anchor;
  489:         anc2->last->next = first;
  490:         if (first) {
  491:             first->prev = anc2->last;
  492:         }
  493:         else {
  494:             anc1->last = anc2->last;
  495:         }
  496:     }
  497: 
  498:     verify_list("append", anc1);
  499: }
  500: 
  501: #if 0 /* unused */
  502: /*
  503:  * anc1: e1, e2, e3
  504:  * anc2: e4, e5
  505:  *#=>
  506:  * anc1: e4, e5
  507:  * anc2: e1, e2, e3
  508:  */
  509: static void
  510: SWAP_LIST(LINK_ANCHOR *anc1, LINK_ANCHOR *anc2)
  511: {
  512:     LINK_ANCHOR tmp = *anc2;
  513: 
  514:     /* it has bug */
  515:     *anc2 = *anc1;
  516:     *anc1 = tmp;
  517: 
  518:     verify_list("swap1", anc1);
  519:     verify_list("swap2", anc2);
  520: }
  521: 
  522: static LINK_ANCHOR *
  523: REVERSE_LIST(LINK_ANCHOR *anc)
  524: {
  525:     LINK_ELEMENT *first, *last, *elem, *e;
  526:     first = &anc->anchor;
  527:     elem = first->next;
  528:     last = anc->last;
  529: 
  530:     if (elem != 0) {
  531:         anc->anchor.next = last;
  532:         anc->last = elem;
  533:     }
  534:     else {
  535:         /* null list */
  536:         return anc;
  537:     }
  538:     while (elem) {
  539:         e = elem->next;
  540:         elem->next = elem->prev;
  541:         elem->prev = e;
  542:         elem = e;
  543:     }
  544: 
  545:     first->next = last;
  546:     last->prev = first;
  547:     anc->last->next = 0;
  548: 
  549:     verify_list("reverse", anc);
  550:     return anc;
  551: }
  552: #endif
  553: 
  554: #if CPDEBUG > 0
  555: static void
  556: debug_list(LINK_ANCHOR *anchor)
  557: {
  558:     LINK_ELEMENT *list = FIRST_ELEMENT(anchor);
  559:     printf("----\n");
  560:     printf("anch: %p, frst: %p, last: %p\n", &anchor->anchor,
  561:            anchor->anchor.next, anchor->last);
  562:     while (list) {
  563:         printf("curr: %p, next: %p, prev: %p, type: %d\n", list, list->next,
  564:                list->prev, FIX2INT(list->type));
  565:         list = list->next;
  566:     }
  567:     printf("----\n");
  568: 
  569:     dump_disasm_list(anchor->anchor.next);
  570:     verify_list("debug list", anchor);
  571: }
  572: #endif
  573: 
  574: static LABEL *
  575: new_label_body(rb_iseq_t *iseq, int line)
  576: {
  577:     LABEL *labelobj = compile_data_alloc_label(iseq);
  578:     static int label_no = 0;
  579: 
  580:     labelobj->link.type = ISEQ_ELEMENT_LABEL;
  581:     labelobj->link.next = 0;
  582: 
  583:     labelobj->label_no = label_no++;
  584:     labelobj->sc_state = 0;
  585:     labelobj->sp = -1;
  586:     return labelobj;
  587: }
  588: 
  589: static INSN *
  590: new_insn_core(rb_iseq_t *iseq, int line_no,
  591:               int insn_id, int argc, VALUE *argv)
  592: {
  593:     INSN *iobj = compile_data_alloc_insn(iseq);
  594: 
  595:     iobj->link.type = ISEQ_ELEMENT_INSN;
  596:     iobj->link.next = 0;
  597:     iobj->insn_id = insn_id;
  598:     iobj->line_no = line_no;
  599:     iobj->operands = argv;
  600:     iobj->operand_size = argc;
  601:     iobj->sc_state = 0;