#include "gcc-plugin.h"
#include "plugin-version.h"
#include "system.h"
#include "coretypes.h"
#include "tree-pass.h"
#include "tree.h"
#include "tree-iterator.h"
#include "gimple.h"
#include "cgraph.h"
#include <stdio.h>

/* This is required for GCC plugin, or it is can not be loaded */
int plugin_is_GPL_compatible;

/*! \brief Parse a tree of type and return respective string.
 *
 * The struncture of a pointer type
 *  - pointer:pointer_type
 *    - type:*_type
 *      - name:type_decl
 *        - name:identifier
 *
 * For a constant type, it is flaged as a readonly.
 *
 * \return a string for the type.  It must be free through ggc_free().
 */
static char *
parse_type(tree type_node) {
    tree type_v;
    tree *pointers;
    tree type_decl, type_name;
    int ptr_lvl = 0;
    int const_cnt = 0;
    char *type_str;
    const char *base_type_name;
    int type_str_len;
    int str_i, ptr_i;
    
    /* Collect pointers */
    type_v = type_node;
    while(TREE_CODE(type_v) == POINTER_TYPE) {
	if(TREE_READONLY(type_v))
	    const_cnt++;
	type_v = TREE_TYPE(type_v);
	ptr_lvl++;
    }

    pointers = (tree *)ggc_alloc(sizeof(tree) * ptr_lvl);
    type_v = type_node;
    for(ptr_i = 0; ptr_i < ptr_lvl; ptr_i++) {
	pointers[ptr_i] = type_v;
	type_v = TREE_TYPE(type_v);
    }

    /* Get name of base type */
    type_decl = TYPE_NAME(type_v);
    type_name = DECL_NAME(type_decl);
    base_type_name = IDENTIFIER_POINTER(type_name);
    
    /* Compute total length of string of full type */
    type_str_len = ptr_lvl + strlen(base_type_name) +
	const_cnt * 5;		/* "const" */
    if(TREE_READONLY(type_v))
	type_str_len += 6;	/* "const " */
    type_str = (char *)ggc_alloc(type_str_len + 1);
    
    /* base type and constant modification */
    type_str[0] = 0;
    if(TREE_READONLY(type_v))
	strcpy(type_str, "const ");
    strcat(type_str, base_type_name);
    
    /* Add pointers and const modifications after base type */
    str_i = strlen(type_str);
    for(ptr_i = ptr_lvl - 1; ptr_i >= 0; ptr_i--) {
	type_v = pointers[ptr_i];
	type_str[str_i++] = '*';
	if(TREE_READONLY(type_v)) {
	    strcpy(type_str + str_i, "const");
	    str_i += 5;
	}
    }
    type_str[str_i] = 0;
    
    ggc_free(pointers);

    return type_str;
}

/*! \brief Show functions that called by a specified function.
 *
 * \param cgn is cgraph_node of a function.
 */
static void
show_callees(struct cgraph_node *cgn) {
    struct cgraph_edge *edge;
    struct cgraph_node *callee_cgn;
    tree callee, callee_name;

    /* Follow edges to called functions */
    edge = cgn->callees;
    while(edge) {
	callee_cgn = edge->callee;
	callee = callee_cgn->decl;
	callee_name = DECL_NAME(callee);
	
	printf("    call %s\n", IDENTIFIER_POINTER(callee_name));
	
	edge = edge->next_callee;
    }
}

/*! \defgroup tree_travel Tree traveling and manipulation tools.
 * @{
 */
typedef struct _stmt_link {
    tree stmt;
    struct _stmt_link *parent;
} stmt_link;

/*! \brief Trival tree of GIMPLE code with a callback.
 *
 * walk_code_free() would call the function given by cb with
 * expression and data as arguments.  The cb is called only for the
 * node with tree code value given by accept_code.
 *
 * \param accept_code is tree code of nodes that calling cb for or -1
 *		to call cb for every node.
 * \param visit is true for traveling and false for cleaning.
 */
static void
_walk_code_tree(tree expr, int accept_code,
		void (*cb)(tree, void *, stmt_link *), void *data,
		stmt_link *parent, bool visit) {
    stmt_link me = {expr, parent};
    int code;
    tree child;
    int i, sz;
    tree_stmt_iterator stmt_itr;

    if(expr == NULL)
	return;
    
    TREE_VISITED(expr) = visit;
    
    if(TREE_VISITED(expr))
	return;

    code = TREE_CODE(expr);

    if(cb && (accept_code == -1 || code == accept_code))
	cb(expr, data, parent);

    switch(code) {
    case ERROR_MARK:		/* 0 */
    case IDENTIFIER_NODE:
    case TREE_LIST:
    case TREE_VEC:
    case BLOCK:
    case OFFSET_TYPE:
    case ENUMERAL_TYPE:
    case BOOLEAN_TYPE:
    case INTEGER_TYPE:
    case REAL_TYPE:
    case POINTER_TYPE:
    case FIXED_POINT_TYPE:
    case REFERENCE_TYPE:
    case COMPLEX_TYPE:
    case VECTOR_TYPE:
    case ARRAY_TYPE:
    case RECORD_TYPE:
    case UNION_TYPE:
    case QUAL_UNION_TYPE:
    case VOID_TYPE:
    case FUNCTION_TYPE:
    case METHOD_TYPE:
    case LANG_TYPE:
    case INTEGER_CST:
    case REAL_CST:
    case FIXED_CST:		/* 25 */
    case COMPLEX_CST:
    case VECTOR_CST:
    case STRING_CST:
    case FUNCTION_DECL:
    case LABEL_DECL:
    case FIELD_DECL:
    case VAR_DECL:
    case CONST_DECL:
    case PARM_DECL:
    case TYPE_DECL:
    case RESULT_DECL:
    case DEBUG_EXPR_DECL:
    case NAMESPACE_DECL:
    case IMPORTED_DECL:
    case TRANSLATION_UNIT_DECL:
    case COMPONENT_REF:
    case BIT_FIELD_REF:
    case REALPART_EXPR:
    case IMAGPART_EXPR:
    case ARRAY_REF:
    case ARRAY_RANGE_REF:
    case INDIRECT_REF:
    case ALIGN_INDIRECT_REF:
    case MISALIGNED_INDIRECT_REF:
    case OBJ_TYPE_REF:		/* 50 */
    case CONSTRUCTOR:
    case COMPOUND_EXPR:
    case MODIFY_EXPR:
    case INIT_EXPR:
    case TARGET_EXPR:
    case COND_EXPR:
    case VEC_COND_EXPR:
	sz = TREE_OPERAND_LENGTH(expr);
	for(i = 0; i < sz; i++) {
	    child = TREE_OPERAND(expr, i);
	    _walk_code_tree(child, accept_code, cb, data, &me, visit);
	}
	break;
	
    case BIND_EXPR:
	/* See BIND_EXPR in tree.def */
	child = BIND_EXPR_BODY(expr);
	_walk_code_tree(child, accept_code, cb, data, &me, visit);
	break;
	
    case CALL_EXPR:
    case WITH_CLEANUP_EXPR:
    case CLEANUP_POINT_EXPR:
    case PLACEHOLDER_EXPR:
    case PLUS_EXPR:
    case MINUS_EXPR:
    case MULT_EXPR:
    case POINTER_PLUS_EXPR:
    case TRUNC_DIV_EXPR:
    case CEIL_DIV_EXPR:
    case FLOOR_DIV_EXPR:
    case ROUND_DIV_EXPR:
    case TRUNC_MOD_EXPR:
    case CEIL_MOD_EXPR:
    case FLOOR_MOD_EXPR:
    case ROUND_MOD_EXPR:
    case RDIV_EXPR:		/* 75 */
    case EXACT_DIV_EXPR:
    case FIX_TRUNC_EXPR:
    case FLOAT_EXPR:
    case NEGATE_EXPR:
    case MIN_EXPR:
    case MAX_EXPR:
    case ABS_EXPR:
    case LSHIFT_EXPR:
    case RSHIFT_EXPR:
    case LROTATE_EXPR:
    case RROTATE_EXPR:
    case BIT_IOR_EXPR:
    case BIT_XOR_EXPR:
    case BIT_AND_EXPR:
    case BIT_NOT_EXPR:
    case TRUTH_ANDIF_EXPR:
    case TRUTH_ORIF_EXPR:
    case TRUTH_AND_EXPR:
    case TRUTH_OR_EXPR:
    case TRUTH_XOR_EXPR:
    case TRUTH_NOT_EXPR:
    case LT_EXPR:
    case LE_EXPR:
    case GT_EXPR:
    case GE_EXPR:		/* 100 */
    case EQ_EXPR:
    case NE_EXPR:
    case UNORDERED_EXPR:
    case ORDERED_EXPR:
    case UNLT_EXPR:
    case UNLE_EXPR:
    case UNGT_EXPR:
    case UNGE_EXPR:
    case UNEQ_EXPR:
    case LTGT_EXPR:
    case RANGE_EXPR:
    case PAREN_EXPR:
    case CONVERT_EXPR:
    case ADDR_SPACE_CONVERT_EXPR:
    case FIXED_CONVERT_EXPR:
    case NOP_EXPR:
    case NON_LVALUE_EXPR:
    case VIEW_CONVERT_EXPR:
    case COMPOUND_LITERAL_EXPR:
    case SAVE_EXPR:
    case ADDR_EXPR:
    case FDESC_EXPR:
    case COMPLEX_EXPR:
    case CONJ_EXPR:
    case PREDECREMENT_EXPR:	/* 125 */
    case PREINCREMENT_EXPR:
    case POSTDECREMENT_EXPR:
    case POSTINCREMENT_EXPR:
    case VA_ARG_EXPR:
    case TRY_CATCH_EXPR:
    case TRY_FINALLY_EXPR:
    case DECL_EXPR:
    case LABEL_EXPR:
    case GOTO_EXPR:
    case RETURN_EXPR:
    case EXIT_EXPR:
    case LOOP_EXPR:
    case SWITCH_EXPR:
    case CASE_LABEL_EXPR:
    case ASM_EXPR:
    case SSA_NAME:
    case CATCH_EXPR:
    case EH_FILTER_EXPR:
    case SCEV_KNOWN:
    case SCEV_NOT_KNOWN:
    case POLYNOMIAL_CHREC:
	sz = TREE_OPERAND_LENGTH(expr);
	for(i = 0; i < sz; i++) {
	    child = TREE_OPERAND(expr, i);
	    _walk_code_tree(child, accept_code, cb, data, &me, visit);
	}
	break;
	
    case STATEMENT_LIST:
	/* See STATEMENT_LIST in tree.def of GCC */
	for(stmt_itr = tsi_start(expr);
	    !tsi_end_p(stmt_itr);
	    tsi_next(&stmt_itr)) {
	    child = tsi_stmt(stmt_itr);
	    _walk_code_tree(child, accept_code, cb, data, &me, visit);
	}
	break;
	
    case ASSERT_EXPR:
    case TREE_BINFO:
    case WITH_SIZE_EXPR:	/* 150 */
    case REALIGN_LOAD_EXPR:
    case TARGET_MEM_REF:
    case OMP_PARALLEL:
    case OMP_TASK:
    case OMP_FOR:
    case OMP_SECTIONS:
    case OMP_SINGLE:
    case OMP_SECTION:
    case OMP_MASTER:
    case OMP_ORDERED:
    case OMP_CRITICAL:
    case OMP_ATOMIC:
    case OMP_CLAUSE:
    case REDUC_MAX_EXPR:
    case REDUC_MIN_EXPR:
    case REDUC_PLUS_EXPR:
    case DOT_PROD_EXPR:
    case WIDEN_SUM_EXPR:
    case WIDEN_MULT_EXPR:
    case VEC_LSHIFT_EXPR:
    case VEC_RSHIFT_EXPR:
    case VEC_WIDEN_MULT_HI_EXPR:
    case VEC_WIDEN_MULT_LO_EXPR:
    case VEC_UNPACK_HI_EXPR:
    case VEC_UNPACK_LO_EXPR:	/* 175 */
    case VEC_UNPACK_FLOAT_HI_EXPR:
    case VEC_UNPACK_FLOAT_LO_EXPR:
    case VEC_PACK_TRUNC_EXPR:
    case VEC_PACK_SAT_EXPR:
    case VEC_PACK_FIX_TRUNC_EXPR:
    case VEC_EXTRACT_EVEN_EXPR:
    case VEC_EXTRACT_ODD_EXPR:
    case VEC_INTERLEAVE_HIGH_EXPR:
    case VEC_INTERLEAVE_LOW_EXPR:
    case PREDICT_EXPR:
    case OPTIMIZATION_NODE:
    case TARGET_OPTION_NODE:
	sz = TREE_OPERAND_LENGTH(expr);
	for(i = 0; i < sz; i++) {
	    child = TREE_OPERAND(expr, i);
	    _walk_code_tree(child, accept_code, cb, data, &me, visit);
	}
	break;
    }
}

static void
walk_code_tree(tree expr, int accept_code,
	       void (*cb)(tree, void *, stmt_link *), void *data) {
    _walk_code_tree(expr, accept_code, cb, data, NULL, true);
    
    /* cleaning visited flag for every node */
    _walk_code_tree(expr, -1, NULL, NULL, NULL, false);
}

static void
tree_insert_before_stmt(tree new_node, tree old_node, tree parent) {
    tree_stmt_iterator itr;
    tree visit;

    for(itr = tsi_start(parent); !tsi_end_p(itr); tsi_next(&itr)) {
	visit = tsi_stmt(itr);
	if(visit == old_node) {
	    tsi_link_before(&itr, new_node, TSI_SAME_STMT);
	    TREE_VISITED(new_node) = true;
	    break;
	}
    }
}

static void
tree_insert_before_arg(tree new_node, tree old_node, tree parent) {
    tree visit;
    tree compound;
    int len;
    int i;

    len = TREE_OPERAND_LENGTH(parent);
    for(i = 0; i < len; i++) {
	visit = TREE_OPERAND(parent, i);
	if(visit == old_node) {
	    compound = build2(COMPOUND_EXPR, TREE_TYPE(old_node),
			      new_node, old_node);
	    TREE_VISITED(compound) = true;
	    TREE_OPERAND(parent, i) = compound;
	    break;
	}
    }
}

/*! \brief Insert a new node before an old node under a parent.
 *
 * \param new_node is the node to be inserted.
 * \param old_node is the node where the new one being inserted before.
 * \param parent is the parent node of old_node.
 */
static void
tree_insert_before(tree new_node, tree old_node, tree parent) {
    int pcode;

    pcode = TREE_CODE(parent);
    if(pcode == STATEMENT_LIST)
	tree_insert_before_stmt(new_node, old_node, parent);
    else
	tree_insert_before_arg(new_node, old_node, parent);
}

/* @} */

/*! \brief Called for found CALL_EXPR in a tree when trevaling.
 */
static void
found_call(tree expr, void *data, stmt_link *parent_link) {
    tree addr;
    tree fn, fn_name;
    tree parent = parent_link->stmt;

    addr = TREE_OPERAND(expr, 1);
    fn = TREE_OPERAND(addr, 0);
    fn_name = DECL_NAME(fn);
    
    printf("    CALL %s:%s:%d from a %d\n",
	   IDENTIFIER_POINTER(fn_name),
	   EXPR_FILENAME(expr),
	   EXPR_LINENO(expr),
	   TREE_CODE(parent));
}

/*! \brief Find all call expression in a code block.
 *
 * This function find CALL_EXPR in body of a function that represented
 * as a GIMPE tree.  See gcc/tree.def and gcc/c-gimplify.c of GCC for
 * more information of tree code of GIMPLE.
 */
static void
find_call_expr(tree fn) {
    tree bind, body;
    
    bind = DECL_SAVED_TREE(fn);	/* BIND_EXPR */
    body = BIND_EXPR_BODY(bind);
    walk_code_tree(body, CALL_EXPR, found_call, NULL);
}

/*! \brief This function is called before running all_passes.
 *
 * all_passes is a list of optimization passes of GCC.  See
 * init_optimization_passes() in gcc/passes.c of GCC.
 *
 * This function is called for every function.
 */
static void
handle_all_passes(void *gcc_data, void *user_data) {
    tree decl;
    struct cgraph_node *cgn;
    
    /*
     * GCC uses cgraph_node to save information of functions and
     * relationships between functions (a.k.a call graphy).
     */
    decl = cfun->decl;
    cgn = cgraph_node(decl);
    
    printf("%s:%d:%s\n", current_function_name(),
	   DECL_SOURCE_LINE(decl),
	   DECL_SOURCE_FILE(decl));
    
    show_callees(cgn);
}

/*! \brief Called before every optimization pass.
 */
static void
handle_every_pass(void *gcc_data, void *user_data) {
#if 0
    printf("PASS %s (type=%x)\n", current_pass->name, current_pass->type);
#endif
}

/*! \brief Callback before any optimization pass.
 *
 * It supposed to get function body in GIMPLE statements.  If we don't
 * do this, here, it, GIMPLE statements, would be destroyed by
 * optimization passes.

 */
static void
handle_pre_genericize(void *gcc_data, void *user_data) {
    tree fndecl;
    /* for arguments */
    tree arg, arg_name;
    tree arg_type;
    char *arg_type_str;

    fndecl = cfun->decl;
    
    printf("%s:%d:%s\n", current_function_name(),
	   DECL_SOURCE_LINE(fndecl),
	   DECL_SOURCE_FILE(fndecl));
    
    /*
     * Parse and show arguments of the function.
     */
    arg = DECL_ARGUMENTS(fndecl);
    while(arg) {
	/*
	 * The structure of an argument.
	 * - parm
	 *   - name:identifier
	 *   - type:type
	 *     - name:type_decl
	 *       - name:identifier
	 */
	arg_name = DECL_NAME(arg);
	arg_type = TREE_TYPE(arg);
	arg_type_str = parse_type(arg_type);
	printf("    %s:%s\n",
	       IDENTIFIER_POINTER(arg_name),
	       arg_type_str);
	ggc_free(arg_type_str);
	arg = TREE_CHAIN(arg);
    }
    
    find_call_expr(fndecl);
}

/*! \brief Initialize function for the plugin.
 */
int
plugin_init(struct plugin_name_args *plugin_info,
	    struct plugin_gcc_version *version) {
    if (!plugin_default_version_check (version, &gcc_version))
	return 1;
    printf("Initialize plugin %s\n", plugin_info->base_name);

    /*
     * Register a callback called before running passes in all_passes.
     */
    register_callback(plugin_info->base_name, PLUGIN_ALL_PASSES_START,
		      handle_all_passes, NULL);
    
    register_callback(plugin_info->base_name, PLUGIN_PASS_EXECUTION,
		      handle_every_pass, NULL);
    
    /*
     * Call handle_pre_genericize before genericize a function.
     *
     * This callback is run before any optimization pass.  It is just
     * after finishing (parsing) a function.
     */
    register_callback(plugin_info->base_name, PLUGIN_PRE_GENERICIZE,
		      handle_pre_genericize, NULL);
    return 0;
}