/* Oort
 * Copyright 2007, Soren Sandmann Pedersen
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

#include "ast.h"

static node_t *
remove_nops (node_t *node, gboolean *changed)
{
    node_t *n;

    n = node;
    while (n != NULL)
    {
	node_t *prev = n->common.prev;
	node_t *next = n->common.next;

	if (n->common.type == NODE_NOP		||
	    n->common.type == NODE_INIT		||
	    n->common.type == NODE_FUN_REF)
	{
	    
	    *changed = TRUE;
	    
	    if (next)
		next->common.prev = prev;
	    if (prev)
		prev->common.next = next;

	    if (!prev)
		node = next;

	    node_free (n);
	}

	n = next;
    }

    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
    {
	nop_node (node->common.next, index - 1);
    }
}

static gboolean
node_is (node_t *node, node_type_t type)
{
    if (node && node->common.type == type)
	return TRUE;
    else
	return FALSE;
}

static void
change_source_node (node_t *source,
		    label_node_t *new_target)
{
    if (source->common.type == NODE_GOTO)
    {
	source->goto_.label = new_target;
    }
    else if (source->common.type == NODE_IF)
    {
	source->if_.taken = new_target;
    }
    else if (source->common.type == NODE_DYN_LABEL)
    {
	source->dyn_label.label = new_target;
    }
    else
    {
	g_print ("unexpected type: %d  (node: %p)\n",
		 source->common.type, source);
	g_assert_not_reached();
    }
    
    g_queue_push_tail (new_target->sources, source);
}

static void
peephole (node_t *node,
	  gboolean *changed)
{
    for (; node; node = node->common.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))
	{
	    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))
	{
	    nop_node (node, 0);
	    nop_node (node, 4);

	    *changed = TRUE;
	}
	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 *source = list->data;
		
		change_source_node (source, &label2->label);
	    }
	    
	    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)
	    {
		node_t *source = list->data;
		
		change_source_node (source, node1->goto_.label);
	    }
	    
	    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)
	    {
		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);
	    
	    *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)
	    {
		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);
	    
	    *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;
	}
    }
}

static void
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;
	    
	    peephole (*node, &c);
	    *node = remove_nops (*node, &c);

	    if (c)
		*changed = TRUE;
	}
	while (c);
    }
}

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;
    }
}

static void
mark_used (node_t *node, gpointer data)
{
    if (node->common.type == NODE_LOAD)
    {
	node->load.definition->used = TRUE;
    }
    else if (node->common.type == NODE_LOAD_IND)
    {
	node->load_ind.definition->used = TRUE;
    }
}

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.
     */
    mark_variables_unused (ast);
    return TRUE;
}