diff options
author | Søren Sandmann Pedersen <ssp@redhat.com> | 2012-06-17 13:07:02 -0400 |
---|---|---|
committer | Søren Sandmann Pedersen <ssp@redhat.com> | 2012-06-17 13:07:02 -0400 |
commit | 32a44ba354322aefe82d7a5c1747eb48194f6177 (patch) | |
tree | 422bafee9c2f80b3c75017218341d55b85b126b5 | |
parent | 47fed2c5d43d7689b745640473a6959042284c55 (diff) |
Make the optimization passes non-recursive.
Very long functions could cause stack overflow due to peephole() and
remove_nops() being recursive.
-rw-r--r-- | ast.h | 1 | ||||
-rw-r--r-- | examples/lamb.nl | 30 | ||||
-rw-r--r-- | node.c | 6 | ||||
-rw-r--r-- | optimize.c | 762 |
4 files changed, 419 insertions, 380 deletions
@@ -683,6 +683,7 @@ node_t *node_new_this (ast_class_definition_t *class, ast_t *ast); node_t *node_insert_after (node_t *node, node_t *pred); +void node_free (node_t *node); typedef void (* node_callback_t) (node_t *node, gpointer data); diff --git a/examples/lamb.nl b/examples/lamb.nl index 2b12204..ea94a0c 100644 --- a/examples/lamb.nl +++ b/examples/lamb.nl @@ -1,4 +1,4 @@ -make_adder (x: int32) -> fn (int32) -> int32 +make_adder (x: int32) -> fn (p: int32) -> int32 { // Which looks prettier? This: @@ -6,26 +6,28 @@ make_adder (x: int32) -> fn (int32) -> int32 // or this: - return - fn () -> fn (int32) -> int32 + return fn () -> fn (p: int32) -> int32 { return fn (y: int32) -> int32 { return x + y; }; } (); } -adder: fn (int32) -> int32; +adder: fn (p: int32) -> int32; adder = make_adder (100); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); -adder = make_adder (adder (100)); +for (i: = 0; i < 81150; ++i) +{ + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); + adder = make_adder (adder (100)); +} print adder (500); @@ -62,6 +62,12 @@ node_new (node_type_t type, return new; } +void +node_free (node_t *node) +{ + g_free (node); +} + node_t * node_new_fun_ref (node_t *prolog, node_t *pred, @@ -19,64 +19,66 @@ #include "ast.h" static node_t * -remove_nops (node_t *node, - gboolean *changed) +remove_nops (node_t *node, gboolean *changed) { - if (!node) - return NULL; + node_t *n; - if (node->common.type == NODE_NOP || - node->common.type == NODE_INIT || - node->common.type == NODE_FUN_REF) + n = node; + while (n != NULL) { - node_t *prev; - node_t *next; + node_t *prev = n->common.prev; + node_t *next = n->common.next; - *changed = TRUE; + if (n->common.type == NODE_NOP || + n->common.type == NODE_INIT || + n->common.type == NODE_FUN_REF) + { + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + + if (next) + next->common.prev = prev; + if (prev) + prev->common.next = next; - next = node->common.next; - prev = node->common.prev; + if (!prev) + node = next; - if (next) - next->common.prev = prev; - if (prev) - prev->common.next = next; + node_free (n); + } - return remove_nops (node->common.next, changed); + n = next; } - else - { - node->common.next = remove_nops (node->common.next, changed); - return node; - } + return node; } static void nop_node (node_t *node, int index) { g_assert (node); - + if (index == 0) { label_node_t *label = NULL; - + if (node->common.type == NODE_GOTO) label = node->goto_.label; else if (node->common.type == NODE_IF) label = node->if_.taken; else if (node->common.type == NODE_DYN_LABEL) label = node->dyn_label.label; - + if (label) { g_assert (g_queue_find (label->sources, node)); - + g_queue_remove (label->sources, node); - + g_assert (!g_queue_find (label->sources, node)); } - + node->common.type = NODE_NOP; } else @@ -116,350 +118,376 @@ change_source_node (node_t *source, source->common.type, source); g_assert_not_reached(); } - + g_queue_push_tail (new_target->sources, source); } -static node_t * +static void peephole (node_t *node, gboolean *changed) { - node_t *node0 = node; - node_t *node1 = node0? node0->common.next : NULL; - node_t *node2 = node1? node1->common.next : NULL; - node_t *node3 = node2? node2->common.next : NULL; - node_t *node4 = node3? node3->common.next : NULL; - - if (!node) - return NULL; - - if (node_is (node0, NODE_DUP) && - node_is (node1, NODE_STORE) && - node_is (node2, NODE_POP)) - { - nop_node (node, 0); - nop_node (node, 2); - - *changed = TRUE; - } - else if (node_is (node0, NODE_DUP) && - node_is (node1, NODE_LOAD) && - node_is (node2, NODE_STORE_IND) && - node_is (node3, NODE_POP)) - { - nop_node (node, 0); - nop_node (node, 3); - - *changed = TRUE; - } - else if (node_is (node0, NODE_DUP) && - node_is (node1, NODE_LITERAL) && - node_is (node2, NODE_BINOP) && - node_is (node3, NODE_STORE) && - node_is (node4, NODE_POP)) + for (; node; node = node->common.next) { - nop_node (node, 0); - nop_node (node, 4); - } - else if (node_is (node0, NODE_DUP) && - node_is (node1, NODE_LOAD) && - node_is (node2, NODE_LOAD) && - node_is (node3, NODE_STORE_ARRAY) && - node_is (node4, NODE_POP)) - { - nop_node (node, 0); - nop_node (node, 4); - - *changed = TRUE; - } - else if (node_is (node0, NODE_IF) && - node_is (node1, NODE_GOTO) && - node_is (node2, NODE_LABEL) && - node0->if_.taken == &node2->label) - { - node_new_if (!node0->if_.sense, node1->goto_.label, node0, NULL); - - nop_node (node0, 0); - nop_node (node1, 0); - } - else if (node_is (node0, NODE_LABEL) && - node0->label.sources->length == 0) - { - nop_node (node, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_LABEL) && - node_is (node1, NODE_LABEL)) - { - node_t *label2 = node->common.next; - GList *list; - - for (list = node->label.sources->head; list; list = list->next) + node_t *node0 = node; + node_t *node1 = node0? node0->common.next : NULL; + node_t *node2 = node1? node1->common.next : NULL; + node_t *node3 = node2? node2->common.next : NULL; + node_t *node4 = node3? node3->common.next : NULL; + + if (node_is (node0, NODE_DUP) && + node_is (node1, NODE_STORE) && + node_is (node2, NODE_POP)) { - node_t *source = list->data; - - change_source_node (source, &label2->label); + nop_node (node, 0); + nop_node (node, 2); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; } - - nop_node (node, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_GOTO) && - !node_is (node1, NODE_LABEL) && - !node_is (node1, NODE_NOP) && - node1) - { - nop_node (node, 1); - - *changed = TRUE; - } - else if (node_is (node0, NODE_GOTO) && - node_is (node1, NODE_LABEL) && - node->goto_.label == &node1->label) - { - nop_node (node, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_UNARY) && - node_is (node1, NODE_UNARY) && - node0->unary.operator == AST_UNARY_NOT && - node1->unary.operator == AST_UNARY_NOT) - { - nop_node (node, 0); - nop_node (node, 1); - - *changed = TRUE; - } - else if (node_is (node0, NODE_LABEL) && - node_is (node1, NODE_GOTO) && - node1->goto_.label != &node0->label) - { - GList *list; - - for (list = node0->label.sources->head; list; list = list->next) + else if (node_is (node0, NODE_DUP) && + node_is (node1, NODE_LOAD) && + node_is (node2, NODE_STORE_IND) && + node_is (node3, NODE_POP)) { - node_t *source = list->data; - - change_source_node (source, node1->goto_.label); + nop_node (node, 0); + nop_node (node, 3); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; } + else if (node_is (node0, NODE_DUP) && + node_is (node1, NODE_LITERAL) && + node_is (node2, NODE_BINOP) && + node_is (node3, NODE_STORE) && + node_is (node4, NODE_POP)) + { + nop_node (node, 0); + nop_node (node, 4); - nop_node (node, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_LITERAL) && - node_is (node1, NODE_IF)) - { - if (node0->literal.value.bool_val == node1->if_.sense) - node_new_goto (node1->if_.taken, node1, NULL); - - nop_node (node0, 0); - nop_node (node1, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_IF) && - node_is (node1, NODE_LABEL) && - node0->if_.taken == &node1->label) - { - node_new_pop (node0, NULL); - - nop_node (node0, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_UNARY) && - node_is (node1, NODE_POP)) - { - nop_node (node, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_LOAD) && - node_is (node1, NODE_POP)) - { - nop_node (node, 0); - nop_node (node, 1); - - *changed = TRUE; - } - else if (node_is (node0, NODE_IF) && - node_is (node1, NODE_GOTO) && - node0->if_.taken == node1->goto_.label) - { - node_new_pop (node0, NULL); - - nop_node (node0, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_BINOP) && - node_is (node1, NODE_POP)) - { - node0->common.type = NODE_POP; - - *changed = TRUE; - } - else if (node_is (node0, NODE_LITERAL) && - node_is (node1, NODE_POP)) - { - nop_node (node, 0); - nop_node (node, 1); - - *changed = TRUE; - } - else if (node_is (node0, NODE_DUP) && - node_is (node1, NODE_IF) && - node_is (node1->if_.taken->common.next, NODE_POP) && - node_is (node2, NODE_POP)) - { - node_t *label; - - label = node_new_label (node1->if_.taken->common.next, NULL); - node_new_if (node1->if_.sense, &label->label, node0, NULL); - - nop_node (node0, 0); - nop_node (node2, 0); - nop_node (node1, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_DYN_LABEL) && - node_is (node1, NODE_DYN_GOTO) && - node0->dyn_label.expression->common.level == - node0->dyn_label.definition->level) - { - node_new_goto ( - node0->dyn_label.label, node0, NULL); - - nop_node (node0, 0); - nop_node (node1, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_DUP) && - node_is (node1, NODE_IF) && - node_is (node2, NODE_POP) && - node_is (node1->if_.taken->common.next, NODE_IF)) - { - if_node_t *if1 = &node1->if_; - if_node_t *if2 = &node1->if_.taken->common.next->if_; - label_node_t *label; - - g_print ("type: %d\n", node1->if_.taken->common.type); - g_print ("type: %d\n", node1->if_.taken->common.next->common.type); - - if (if1->sense == if2->sense) + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_DUP) && + node_is (node1, NODE_LOAD) && + node_is (node2, NODE_LOAD) && + node_is (node3, NODE_STORE_ARRAY) && + node_is (node4, NODE_POP)) { - label = if2->taken; + nop_node (node, 0); + nop_node (node, 4); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; } - else + else if (node_is (node0, NODE_IF) && + node_is (node1, NODE_GOTO) && + node_is (node2, NODE_LABEL) && + node0->if_.taken == &node2->label) { - label = &node_new_label ((node_t *)if2, NULL)->label; + node_new_if (!node0->if_.sense, node1->goto_.label, node0, NULL); + + nop_node (node0, 0); + nop_node (node1, 0); } - - node_new_if (if1->sense, label, node0, NULL); - - nop_node (node0, 0); - nop_node (node1, 0); - nop_node (node2, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_UNARY) && - node0->unary.operator == AST_UNARY_NOT && - node_is (node1, NODE_IF)) - { - node1->if_.sense = !node1->if_.sense; - - nop_node (node0, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_LITERAL) && - node_is (node1, NODE_GOTO) && - node_is (node1->goto_.label->common.next, NODE_IF)) - { - if_node_t *if_node = &node1->goto_.label->common.next->if_; - label_node_t *label; - - if (node0->literal.value.bool_val == if_node->sense) + else if (node_is (node0, NODE_LABEL) && + node0->label.sources->length == 0) { - label = if_node->taken; + nop_node (node, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; } - else + else if (node_is (node0, NODE_LABEL) && + node_is (node1, NODE_LABEL)) { - label = &node_new_label ((node_t *)if_node, NULL)->label; + node_t *label2 = node->common.next; + GList *list; + + for (list = node->label.sources->head; list; list = list->next) + { + node_t *source = list->data; + + change_source_node (source, &label2->label); + } + + nop_node (node, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_GOTO) && + !node_is (node1, NODE_LABEL) && + !node_is (node1, NODE_NOP) && + node1) + { + nop_node (node, 1); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_GOTO) && + node_is (node1, NODE_LABEL) && + node->goto_.label == &node1->label) + { + nop_node (node, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_UNARY) && + node_is (node1, NODE_UNARY) && + node0->unary.operator == AST_UNARY_NOT && + node1->unary.operator == AST_UNARY_NOT) + { + nop_node (node, 0); + nop_node (node, 1); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_LABEL) && + node_is (node1, NODE_GOTO) && + node1->goto_.label != &node0->label) + { + GList *list; + + for (list = node0->label.sources->head; list; list = list->next) + { + node_t *source = list->data; + + change_source_node (source, node1->goto_.label); + } + + nop_node (node, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_LITERAL) && + node_is (node1, NODE_IF)) + { + if (node0->literal.value.bool_val == node1->if_.sense) + node_new_goto (node1->if_.taken, node1, NULL); + + nop_node (node0, 0); + nop_node (node1, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_IF) && + node_is (node1, NODE_LABEL) && + node0->if_.taken == &node1->label) + { + node_new_pop (node0, NULL); + + nop_node (node0, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_UNARY) && + node_is (node1, NODE_POP)) + { + nop_node (node, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_LOAD) && + node_is (node1, NODE_POP)) + { + nop_node (node, 0); + nop_node (node, 1); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_IF) && + node_is (node1, NODE_GOTO) && + node0->if_.taken == node1->goto_.label) + { + node_new_pop (node0, NULL); + + nop_node (node0, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_BINOP) && + node_is (node1, NODE_POP)) + { + node0->common.type = NODE_POP; + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_LITERAL) && + node_is (node1, NODE_POP)) + { + nop_node (node, 0); + nop_node (node, 1); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_DUP) && + node_is (node1, NODE_IF) && + node_is (node1->if_.taken->common.next, NODE_POP) && + node_is (node2, NODE_POP)) + { + node_t *label; + + label = node_new_label (node1->if_.taken->common.next, NULL); + node_new_if (node1->if_.sense, &label->label, node0, NULL); + + nop_node (node0, 0); + nop_node (node2, 0); + nop_node (node1, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_DYN_LABEL) && + node_is (node1, NODE_DYN_GOTO) && + node0->dyn_label.expression->common.level == + node0->dyn_label.definition->level) + { + node_new_goto ( + node0->dyn_label.label, node0, NULL); + + nop_node (node0, 0); + nop_node (node1, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_DUP) && + node_is (node1, NODE_IF) && + node_is (node2, NODE_POP) && + node_is (node1->if_.taken->common.next, NODE_IF)) + { + if_node_t *if1 = &node1->if_; + if_node_t *if2 = &node1->if_.taken->common.next->if_; + label_node_t *label; + + g_print ("type: %d\n", node1->if_.taken->common.type); + g_print ("type: %d\n", node1->if_.taken->common.next->common.type); + + if (if1->sense == if2->sense) + { + label = if2->taken; + } + else + { + label = &node_new_label ((node_t *)if2, NULL)->label; + } + + node_new_if (if1->sense, label, node0, NULL); + + nop_node (node0, 0); + nop_node (node1, 0); + nop_node (node2, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_UNARY) && + node0->unary.operator == AST_UNARY_NOT && + node_is (node1, NODE_IF)) + { + node1->if_.sense = !node1->if_.sense; + + nop_node (node0, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_LITERAL) && + node_is (node1, NODE_GOTO) && + node_is (node1->goto_.label->common.next, NODE_IF)) + { + if_node_t *if_node = &node1->goto_.label->common.next->if_; + label_node_t *label; + + if (node0->literal.value.bool_val == if_node->sense) + { + label = if_node->taken; + } + else + { + label = &node_new_label ((node_t *)if_node, NULL)->label; + } + + node_new_goto (label, node0, NULL); + + nop_node (node0, 0); + nop_node (node1, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_STORE) && + !node0->store.definition->used) + { + node0->common.type = NODE_POP; + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_STORE_IND) && + !node0->store_ind.definition->used) + { + node0->common.type = NODE_POP; + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_STORE) && + node_is (node1, NODE_LOAD) && + node0->store.definition == node1->load.definition) + { + node_t *n; + + n = node_new_dup (node1, NULL); + node_new_store ( + node0->store.definition, node0->store.expression, + n, node0->common.ast); + + nop_node (node0, 0); + nop_node (node1, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_DUP) && + node_is (node1, NODE_POP)) + { + nop_node (node0, 0); + nop_node (node1, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; + } + else if (node_is (node0, NODE_LITERAL) && + node_is (node1, NODE_TO_STRING)) + { + value_t value; + + value.pointer_val = value_to_string ( + &node0->literal.value, node0->literal.type_spec); + + node_new_literal ( + value, ast_type_spec_new (AST_STRING_TYPE), + node1, node0->common.ast); + + nop_node (node0, 0); + nop_node (node1, 0); + + printf ("triggered at line %d\n", __LINE__); + (*changed)++; } - - node_new_goto (label, node0, NULL); - - nop_node (node0, 0); - nop_node (node1, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_STORE) && - !node0->store.definition->used) - { - node0->common.type = NODE_POP; - - *changed = TRUE; - } - else if (node_is (node0, NODE_STORE_IND) && - !node0->store_ind.definition->used) - { - node0->common.type = NODE_POP; - - *changed = TRUE; - } - else if (node_is (node0, NODE_STORE) && - node_is (node1, NODE_LOAD) && - node0->store.definition == node1->load.definition) - { - node_t *n; - - n = node_new_dup (node1, NULL); - node_new_store ( - node0->store.definition, node0->store.expression, - n, node0->common.ast); - - nop_node (node0, 0); - nop_node (node1, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_DUP) && - node_is (node1, NODE_POP)) - { - nop_node (node0, 0); - nop_node (node1, 0); - - *changed = TRUE; - } - else if (node_is (node0, NODE_LITERAL) && - node_is (node1, NODE_TO_STRING)) - { - value_t value; - - value.pointer_val = value_to_string ( - &node0->literal.value, node0->literal.type_spec); - - node_new_literal ( - value, ast_type_spec_new (AST_STRING_TYPE), node1, node0->common.ast); - - nop_node (node0, 0); - nop_node (node1, 0); - - *changed = TRUE; } - - node->common.next = peephole (node->common.next, changed); - - return node; } static void @@ -468,36 +496,38 @@ do_optimize (ast_t *ast, gboolean *changed) GList *list; node_t **node = NULL; node_t **entry = NULL; - + for (list = ast->common.children->head; list != NULL; list = list->next) do_optimize (list->data, changed); - + if (ast_is (ast, AST_PROGRAM, 0)) { ast_program_t *program = &ast->program; - + entry = &(program->enter); } else if (ast_is (ast, AST_DEFINITION, AST_FUNCTION_DEFINITION)) { ast_function_definition_t *function = &ast->definition.function; - + entry = &(function->enter); } if (entry) { gboolean c; - + node = entry; - + do { - c = FALSE; + c = 0; - *node = peephole (*node, &c); + peephole (*node, &c); *node = remove_nops (*node, &c); + printf ("changes: %d\n", c); + if (c) *changed = TRUE; } @@ -509,14 +539,14 @@ static void mark_variables_unused (ast_t *ast) { GList *list; - + for (list = ast->common.children->head; list != NULL; list = list->next) mark_variables_unused (list->data); - + if (ast_is (ast, AST_DEFINITION, AST_VARIABLE_DEFINITION)) { ast_variable_definition_t *variable = &ast->definition.variable; - + variable->used = FALSE; } } @@ -538,18 +568,18 @@ gboolean optimize (ast_t *ast) { gboolean changed; - + do { changed = FALSE; - + mark_variables_unused (ast); - + program_breadth_first (&ast->program, mark_used, NULL); do_optimize (ast, &changed); } while (changed); - + /* The offsets pass also uses the "used" field in * ast_variable_definition_t, and it expects it * to start out as FALSE, so clear it here. |