dvander@2320: #include <assert.h>
dvander@2320: #include <string.h>
dvander@2320: #include <stdlib.h>
dvander@2320: #include "decompiler.h"
dvander@2320: #include "code_analyzer.h"
dvander@2320: #include "platform_util.h"
dvander@2320: 
dvander@2320: struct Block;
dvander@2320: 
dvander@2320: #define PCM_BRANCH_TARGET		(1<<0)
dvander@2320: #define PCM_OPCODE				(1<<1)
dvander@2320: #define PCM_HAS_BLOCK			(1<<2)
dvander@2320: #define PCM_NUM_BITS			3
dvander@2320: 
dvander@2320: #define NEXT_OP(cip, op)		cip += (dc->opdef[op].params + 1) * sizeof(cell_t)
dvander@2320: 
dvander@2320: struct Edge
dvander@2320: {
dvander@2320: 	Edge *next;
dvander@2320: 	Block *target;
dvander@2320: 	uint32_t ip;
dvander@2320: };
dvander@2320: 
dvander@2320: struct Block
dvander@2320: {
dvander@2320: 	cell_t ip_start;
dvander@2320: 	cell_t ip_end;
dvander@2320: 	Edge *edge_list;
dvander@2320: 	Edge *final_edge;
dvander@2320: 	Block *next_in_table;
dvander@2320: };
dvander@2320: 
dvander@2320: struct ControlFlowGraph
dvander@2320: {
dvander@2320: 	int err;
dvander@2320: 	unsigned int max_blocks;
dvander@2320: 	unsigned int max_edges;
dvander@2320: 	unsigned int used_blocks;
dvander@2320: 	unsigned int used_edges;
dvander@2320: 	Block *blocks;
dvander@2320: 	Edge *edges;
dvander@2320: 	Block *entry;
dvander@2320: 	FunctionInfo *func;
dvander@2320: };
dvander@2320: 
dvander@2322: DefineNode::DefineNode(BaseNode *o, const char *fmt, ...) : BaseNode(_OP_DEFINE), other(o)
dvander@2322: {
dvander@2322: 	va_list ap;
dvander@2322: 	
dvander@2322: 	va_start(ap, fmt);
dvander@2322: 	Sp_FormatArgs(name, sizeof(name), fmt, ap);
dvander@2322: 	va_end(ap);
dvander@2322: }
dvander@2322: 
dvander@2320: static FunctionInfo *sp_InferFuncPrototype(sp_decomp_t *dc, uint32_t code_addr, bool is_public)
dvander@2320: {
dvander@2320: 	sp_tag_t *pTag;
dvander@2320: 	sp_file_t *plugin;
dvander@2320: 	FunctionInfo *info;
dvander@2320: 	sp_fdbg_symbol_t *sym;
dvander@2320: 
dvander@2320: 	plugin = dc->plugin;
dvander@2320: 	info = new FunctionInfo;
dvander@2320: 	memset(info, 0, sizeof(FunctionInfo));
dvander@2320: 
dvander@2320: 	info->code_addr = code_addr;
dvander@2320: 	
dvander@2320: 	if ((sym = Sp_FindFunctionSym(plugin, code_addr)) != NULL)
dvander@2320: 	{
dvander@2320: 		Sp_Format(info->name, sizeof(info->name), "%s", plugin->debug.stringbase + sym->name);
dvander@2320: 		if (sym->tagid != 0)
dvander@2320: 		{
dvander@2320: 			info->tag = Sp_FindTag(plugin, sym->tagid);
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 	else
dvander@2320: 	{
dvander@2320: 		Sp_Format(info->name, sizeof(info->name), "function_%x", code_addr);
dvander@2320: 		for (uint32_t i = 0; i < plugin->num_publics; i++)
dvander@2320: 		{
dvander@2320: 			if (plugin->publics[i].code_offs == code_addr)
dvander@2320: 			{
dvander@2320: 				Sp_Format(info->name,
dvander@2320: 					sizeof(info->name),
dvander@2320: 					"%s",
dvander@2320: 					plugin->publics[i].name);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 	info->sym = sym;
dvander@2320: 	info->is_public = is_public;
dvander@2320: 	
dvander@2320: 
dvander@2320: 	/* Search for all locals */
dvander@2320: 	{
dvander@2320: 		uint32_t i;
dvander@2320: 		uint8_t *cursor;
dvander@2320: 
dvander@2320: 		cursor = (uint8_t *)plugin->debug.symbols;
dvander@2320: 		for (i = 0; i < plugin->debug.syms_num; i++)
dvander@2320: 		{
dvander@2320: 			sym = (sp_fdbg_symbol_t *)cursor;
dvander@2320: 
dvander@2320: 			if (sym->ident == SP_SYM_VARIABLE
dvander@2320: 				|| sym->ident == SP_SYM_REFARRAY
dvander@2320: 				|| sym->ident == SP_SYM_REFERENCE
dvander@2320: 				|| sym->ident == SP_SYM_ARRAY)
dvander@2320: 			{
dvander@2320: 				if (code_addr >= sym->codestart
dvander@2320: 					&& code_addr < sym->codeend
dvander@2320: 					&& sym->addr >= 0xC
dvander@2320: 					&& (sym->addr & 0x3) == 0
dvander@2320: 					&& ((sym->addr - 0xC) >> 2) < SP_MAX_EXEC_PARAMS
dvander@2320: 					&& sym->vclass == 1)
dvander@2320: 				{
dvander@2320: 					unsigned int num;
dvander@2320: 
dvander@2320: 					num = (sym->addr - 0xC) >> 2;
dvander@2320: 					info->known_args[num].sym = sym;
dvander@2320: 					if (num + 1 > info->num_known_args)
dvander@2320: 					{
dvander@2320: 						info->num_known_args = num + 1;
dvander@2320: 					}
dvander@2320: 				}
dvander@2320: 			}
dvander@2320: 
dvander@2320: 			cursor += sizeof(sp_fdbg_symbol_t);
dvander@2320: 			if (sym->dimcount > 0)
dvander@2320: 			{
dvander@2320: 				cursor += sizeof(sp_fdbg_arraydim_t) * sym->dimcount;
dvander@2320: 			}
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	/* Map all arguments into place. */
dvander@2320: 	for (unsigned int i = 0; i < info->num_known_args; i++)
dvander@2320: 	{
dvander@2320: 		if ((sym = info->known_args[i].sym) == NULL)
dvander@2320: 		{
dvander@2320: 			continue;
dvander@2320: 		}
dvander@2320: 		if (sym->tagid != 0 && (pTag = Sp_FindTag(plugin, sym->tagid)) != NULL)
dvander@2320: 		{
dvander@2320: 			info->known_args[i].tag = pTag;
dvander@2320: 		}
dvander@2320: 		info->known_args[i].name = plugin->debug.stringbase + sym->name;
dvander@2320: 		
dvander@2325: 		info->known_args[i].dimcount = sym->dimcount;
dvander@2320: 		if (sym->dimcount > 0)
dvander@2320: 		{
dvander@2320: 			info->known_args[i].dims = 
dvander@2320: 				(sp_fdbg_arraydim_t *)((char *)sym + sizeof(sp_fdbg_symbol_t));
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	return info;
dvander@2320: }
dvander@2320: 
dvander@2320: static FunctionInfo *sp_GetFuncPrototype(sp_decomp_t *dc,
dvander@2320: 										 uint32_t code_addr,
dvander@2320: 										 bool known,
dvander@2320: 										 bool is_public = false);
dvander@2320: static FunctionInfo *sp_GetFuncPrototype(sp_decomp_t *dc,
dvander@2320: 										 uint32_t code_addr,
dvander@2320: 										 bool known,
dvander@2320: 										 bool is_public)
dvander@2320: {
dvander@2320: 	FunctionInfo *func;
dvander@2320: 
dvander@2320: 	func = dc->funcs;
dvander@2320: 	while (func != NULL)
dvander@2320: 	{
dvander@2320: 		if (func->code_addr == code_addr)
dvander@2320: 		{
dvander@2320: 			return func;
dvander@2320: 		}
dvander@2320: 		func = func->next;
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	/* See if this is public. */
dvander@2320: 	if (!known)
dvander@2320: 	{
dvander@2320: 		is_public = false;
dvander@2320: 		for (unsigned int i = 0; i < dc->plugin->num_publics; i++)
dvander@2320: 		{
dvander@2320: 			if (dc->plugin->publics[i].code_offs == code_addr)
dvander@2320: 			{
dvander@2320: 				is_public = true;
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	func = sp_InferFuncPrototype(dc, code_addr, is_public);
dvander@2320: 	func->next = dc->funcs;
dvander@2320: 	dc->funcs = func;
dvander@2320: 
dvander@2320: 	return func;
dvander@2320: }
dvander@2320: 
dvander@2320: static void sp_CacheLocals(sp_decomp_t *dc, FunctionInfo *info)
dvander@2320: {
dvander@2320: 	sp_file_t *plugin;
dvander@2320: 	sp_fdbg_symbol_t *sym;
dvander@2320: 
dvander@2320: 	plugin = dc->plugin;
dvander@2320: 
dvander@2320: 	/* Search for all locals */
dvander@2320: 	{
dvander@2320: 		uint32_t i;
dvander@2320: 		uint8_t *cursor;
dvander@2320: 
dvander@2320: 		cursor = (uint8_t *)plugin->debug.symbols;
dvander@2320: 		for (i = 0; i < plugin->debug.syms_num; i++)
dvander@2320: 		{
dvander@2320: 			sym = (sp_fdbg_symbol_t *)cursor;
dvander@2320: 
dvander@2320: 			if ((sym->codestart >= info->code_addr && sym->codestart < info->code_end)
dvander@2320: 				&& (sym->codeend <= info->code_end && sym->codeend >= info->code_addr)
dvander@2320: 				&& sym->vclass == 1)
dvander@2320: 			{
dvander@2320: 				info->num_known_vars++;
dvander@2320: 			}
dvander@2320: 
dvander@2320: 			cursor += sizeof(sp_fdbg_symbol_t);
dvander@2320: 			if (sym->dimcount > 0)
dvander@2320: 			{
dvander@2320: 				cursor += sizeof(sp_fdbg_arraydim_t) * sym->dimcount;
dvander@2320: 			}
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	/* Map all locals into place. */
dvander@2320: 	if (info->num_known_vars)
dvander@2320: 	{
dvander@2320: 		uint32_t i, num;
dvander@2320: 		uint8_t *cursor;
dvander@2320: 
dvander@2320: 		num = 0;
dvander@2320: 		info->known_vars = new FuncVar[info->num_known_vars];
dvander@2320: 		memset(info->known_vars, 0, sizeof(FuncVar) * info->num_known_vars);
dvander@2320: 
dvander@2320: 		cursor = (uint8_t *)plugin->debug.symbols;
dvander@2320: 		for (i = 0; i < plugin->debug.syms_num; i++)
dvander@2320: 		{
dvander@2320: 			sym = (sp_fdbg_symbol_t *)cursor;
dvander@2320: 
dvander@2320: 			if (sym->ident == SP_SYM_VARIABLE
dvander@2320: 				|| sym->ident == SP_SYM_REFARRAY
dvander@2320: 				|| sym->ident == SP_SYM_REFERENCE
dvander@2320: 				|| sym->ident == SP_SYM_ARRAY)
dvander@2320: 			{
dvander@2320: 				/* Detect all function variables. */
dvander@2320: 				if ((sym->codestart >= info->code_addr && sym->codestart < info->code_end)
dvander@2320: 					&& (sym->codeend <= info->code_end && sym->codeend >= info->code_addr)
dvander@2320: 					&& sym->vclass == 1)
dvander@2320: 				{
dvander@2320: 					assert(num < info->num_known_vars);
dvander@2320: 					info->known_vars[num].sym = sym;
dvander@2320: 					info->known_vars[num].name = plugin->debug.stringbase + sym->name;
dvander@2320: 					info->known_vars[num].tag = 
dvander@2320: 						(sym->tagid == 0) ? NULL : Sp_FindTag(plugin, sym->tagid);
dvander@2325: 					info->known_vars[num].dimcount = sym->dimcount;
dvander@2320: 					info->known_vars[num].dims = 
dvander@2320: 						(sym->dimcount == 0)
dvander@2320: 						? NULL
dvander@2320: 						: (sp_fdbg_arraydim_t *)(cursor + sizeof(sp_fdbg_symbol_t));
dvander@2320: 					num++;
dvander@2320: 				}
dvander@2320: 			}
dvander@2320: 
dvander@2320: 			cursor += sizeof(sp_fdbg_symbol_t);
dvander@2320: 			if (sym->dimcount > 0)
dvander@2320: 			{
dvander@2320: 				cursor += sizeof(sp_fdbg_arraydim_t) * sym->dimcount;
dvander@2320: 			}
dvander@2320: 		}
dvander@2320: 
dvander@2320: 		assert(num == info->num_known_vars);
dvander@2320: 	}
dvander@2320: }
dvander@2320: 
dvander@2320: static void sp_PrintFunctionPrototype(PrintBuffer *printer, sp_decomp_t *dc, FunctionInfo *func)
dvander@2320: {
dvander@2320: 	FuncVar *var;
dvander@2320: 	
dvander@2320: 	if (func->is_public)
dvander@2320: 	{
dvander@2320: 		printer->Append("public ");
dvander@2320: 	}
dvander@2320: 	if (func->tag != NULL)
dvander@2320: 	{
dvander@2320: 		printer->Append("%s:", func->tag->name);
dvander@2320: 	}
dvander@2320: 	printer->Append("%s(", func->name);
dvander@2320: 
dvander@2320: 	for (unsigned int i = 0; i < func->num_known_args; i++)
dvander@2320: 	{
dvander@2320: 		var = &func->known_args[i];
dvander@2320: 		if (var->sym == NULL)
dvander@2320: 		{
dvander@2320: 			printer->Append("unknown_arg_%d%s, ", i, i == func->num_known_args - 1 ? "" : ",");
dvander@2320: 			continue;
dvander@2320: 		}
dvander@2320: 		if (var->sym->ident == SP_SYM_REFERENCE)
dvander@2320: 		{
dvander@2320: 			printer->Append("&");
dvander@2320: 		}
dvander@2320: 		if (var->tag != NULL)
dvander@2320: 		{
dvander@2320: 			printer->Append("%s:", var->tag->name);
dvander@2320: 		}
dvander@2320: 		printer->Append("%s", var->name);
dvander@2320: 
dvander@2320: 		if (var->sym->dimcount > 0)
dvander@2320: 		{
dvander@2320: 			sp_fdbg_arraydim_t *dims = 
dvander@2320: 				(sp_fdbg_arraydim_t *)((char *)var->sym + sizeof(sp_fdbg_symbol_t));
dvander@2320: 
dvander@2320: 			for (uint16_t j = 0; j < var->sym->dimcount; j++)
dvander@2320: 			{
dvander@2320: 				if (dims[j].size == 0)
dvander@2320: 				{
dvander@2320: 					printer->Append("[]");
dvander@2320: 				}
dvander@2320: 				else
dvander@2320: 				{
dvander@2320: 					printer->Append("[%d]", dims[j].size);
dvander@2320: 				}
dvander@2320: 			}
dvander@2320: 		}
dvander@2320: 
dvander@2320: 		if (i != func->num_known_args - 1)
dvander@2320: 		{
dvander@2320: 			printer->Append(", ");
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	printer->Append(")");
dvander@2320: }
dvander@2320: 
dvander@2320: void sp_DebugExprTree(PrintBuffer *buffer, BaseNode *node, bool is_stmt=false)
dvander@2320: {
dvander@2320: 	switch (node->op)
dvander@2320: 	{
dvander@2322: 	case _OP_DEFINE:
dvander@2322: 		{
dvander@2322: 			DefineNode *def = (DefineNode *)node;
dvander@2322: 
dvander@2322: 			buffer->Append("new %s = ", def->name);
dvander@2322: 			sp_DebugExprTree(buffer, def->other, is_stmt);
dvander@2322: 			break;
dvander@2322: 		}
dvander@2320: 	case OP_CALL:
dvander@2320: 		{
dvander@2320: 			CallNode *call = (CallNode *)node;
dvander@2320: 
dvander@2320: 			buffer->Append("%s(", call->func->name);
dvander@2320: 			for (unsigned int i = 0; i < call->argc; i++)
dvander@2320: 			{
dvander@2320: 				sp_DebugExprTree(buffer, call->args[i], false);
dvander@2320: 			}
dvander@2320: 			buffer->Append(")");
dvander@2320: 			break;
dvander@2320: 		}
dvander@2322: 	case _OP_USE:
dvander@2322: 		{
dvander@2322: 			UseNode *unode = (UseNode *)node;
dvander@2322: 
dvander@2322: 			buffer->Append("%s", unode->def->name);
dvander@2322: 			break;
dvander@2322: 		}
dvander@2320: 	case _OP_VAR:
dvander@2320: 		{
dvander@2320: 			VarNode *var_node = (VarNode *)node;
dvander@2320: 			buffer->Append("%s", var_node->var->name);
dvander@2320: 			break;
dvander@2320: 		}
dvander@2320: 	case _OP_NEW:
dvander@2320: 		{
dvander@2320: 			DeclNode *d_node = (DeclNode *)node;
dvander@2320: 
dvander@2320: 			if (d_node->expr == NULL)
dvander@2320: 			{
dvander@2320: 				buffer->Append("decl ");
dvander@2320: 				sp_DebugExprTree(buffer, d_node->var, true);
dvander@2320: 			}
dvander@2320: 			else
dvander@2320: 			{
dvander@2320: 				buffer->Append("new ");
dvander@2320: 				sp_DebugExprTree(buffer, d_node->var, true);
dvander@2320: 				buffer->Append(" = ");
dvander@2320: 				sp_DebugExprTree(buffer, d_node->expr, true);
dvander@2320: 			}
dvander@2320: 
dvander@2320: 			break;
dvander@2320: 		}
dvander@2320: 	case _OP_STMT:
dvander@2320: 	case OP_RETN:
dvander@2320: 		{
dvander@2320: 			StmtNode *u_node = (StmtNode *)node;
dvander@2320: 
dvander@2320: 			while (u_node != NULL)
dvander@2320: 			{
dvander@2320: 				buffer->Append("\t");
dvander@2320: 				if (u_node->op == OP_RETN)
dvander@2320: 				{
dvander@2320: 					buffer->Append("return ");
dvander@2320: 				}
dvander@2320: 				sp_DebugExprTree(buffer, u_node->node, true);
dvander@2320: 				buffer->Append(";\n");
dvander@2320: 				u_node = u_node->next;
dvander@2320: 			}
dvander@2320: 			break;
dvander@2320: 		}
dvander@2320: 	case _OP_CONST:
dvander@2320: 		{
dvander@2320: 			ConstNode *c_node = (ConstNode *)node;
dvander@2320: 
dvander@2320: 			buffer->Append("%d", c_node->val);
dvander@2320: 
dvander@2320: 			break;
dvander@2320: 		}
dvander@2320: 	case OP_ADD:
dvander@2320: 	case OP_ADD_C:
dvander@2320: 	case OP_SMUL:
dvander@2320: 	case OP_SMUL_C:
dvander@2320: 	case OP_SDIV:
dvander@2320: 	case OP_SUB_ALT:
dvander@2320: 	case _OP_STORE:
dvander@2320: 	case _OP_MODULO:
dvander@2320: 		{
dvander@2320: 			BinOpNode *bin_node = (BinOpNode *)node;
dvander@2320: 
dvander@2320: 			if (!is_stmt)
dvander@2320: 			{
dvander@2320: 				buffer->Append("(");
dvander@2320: 			}
dvander@2320: 			sp_DebugExprTree(buffer, bin_node->left);
dvander@2320: 
dvander@2320: 			switch (node->op)
dvander@2320: 			{
dvander@2320: 			case OP_ADD:
dvander@2320: 			case OP_ADD_C:
dvander@2320: 				{
dvander@2320: 					buffer->Append(" + ");
dvander@2320: 					break;
dvander@2320: 				}
dvander@2320: 			case OP_SMUL:
dvander@2320: 			case OP_SMUL_C:
dvander@2320: 				{
dvander@2320: 					buffer->Append(" * ");
dvander@2320: 					break;
dvander@2320: 				}
dvander@2320: 			case _OP_STORE:
dvander@2320: 				{
dvander@2320: 					buffer->Append(" = ");
dvander@2320: 					break;
dvander@2320: 				}
dvander@2320: 			case OP_SUB_ALT:
dvander@2320: 				{
dvander@2320: 					buffer->Append(" - ");
dvander@2320: 					break;
dvander@2320: 				}
dvander@2320: 			case OP_SDIV:
dvander@2320: 				{
dvander@2320: 					buffer->Append(" / ");
dvander@2320: 					break;
dvander@2320: 				}
dvander@2320: 			case _OP_MODULO:
dvander@2320: 				{
dvander@2320: 					buffer->Append(" % ");
dvander@2320: 					break;
dvander@2320: 				}
dvander@2320: 			}
dvander@2320: 
dvander@2320: 			sp_DebugExprTree(buffer, bin_node->right, node->op == _OP_STORE);
dvander@2320: 			if (!is_stmt)
dvander@2320: 			{
dvander@2320: 				buffer->Append(")");
dvander@2320: 			}
dvander@2320: 
dvander@2320: 			break;
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: }
dvander@2320: 
dvander@2320: void sp_DebugPrint(FunctionInfo *info, sp_decomp_t *dc, BaseNode *node)
dvander@2320: {
dvander@2320: 	PrintBuffer buffer;
dvander@2320: 
dvander@2320: 	sp_PrintFunctionPrototype(&buffer, dc, info);
dvander@2320: 	buffer.Append("\n{\n");
dvander@2320: 	sp_DebugExprTree(&buffer, node, true);
dvander@2320: 	buffer.Append("}\n");
dvander@2320: 	buffer.Dump(stdout);
dvander@2320: }
dvander@2320: 
dvander@2320: #define PCODE_VAL(pcode, offs)			*(cell_t *)((char *)(pcode)+(offs))
dvander@2320: #define PCODE_PARAM(pcode, offs, num)	*(cell_t *)((char *)(pcode)+(offs)+((num)*sizeof(cell_t)))
dvander@2320: 
dvander@2320: FuncVar *sp_FindGraphVar(FunctionInfo *func, ucell_t cip, cell_t sp, cell_t stack)
dvander@2320: {
dvander@2320: 	if (stack >= 0xC)
dvander@2320: 	{
dvander@2320: 		if ((stack & 0x3) != 0)
dvander@2320: 		{
dvander@2320: 			return NULL;
dvander@2320: 		}
dvander@2320: 		stack -= 0xC;
dvander@2320: 		stack >>= 2;
dvander@2320: 		if (stack >= SP_MAX_EXEC_PARAMS)
dvander@2320: 		{
dvander@2320: 			return NULL;
dvander@2320: 		}
dvander@2320: 		if (func->known_args[stack].sym == NULL)
dvander@2320: 		{
dvander@2320: 			return NULL;
dvander@2320: 		}
dvander@2320: 		return &func->known_args[stack];
dvander@2320: 	}
dvander@2320: 	else if (stack < 0)
dvander@2320: 	{
dvander@2320: 		FuncVar *var;
dvander@2320: 
dvander@2320: 		if (stack < sp)
dvander@2320: 		{
dvander@2320: 			return NULL;
dvander@2320: 		}
dvander@2320: 
dvander@2320: 		for (unsigned int i = 0; i < func->num_known_vars; i++)
dvander@2320: 		{
dvander@2320: 			var = &func->known_vars[i];
dvander@2320: 
dvander@2320: 			if (cip >= var->sym->codestart
dvander@2320: 				&& cip <= var->sym->codeend
dvander@2320: 				&& stack == var->sym->addr)
dvander@2320: 			{
dvander@2320: 				return var;
dvander@2320: 			}
dvander@2320: 		}
dvander@2320: 
dvander@2320: 		return NULL;
dvander@2320: 	}
dvander@2320: 	else
dvander@2320: 	{
dvander@2320: 		return NULL;
dvander@2320: 	}
dvander@2320: }
dvander@2320: 
dvander@2320: #define CHECK_VALUE(v)							\
dvander@2320: 	assert(v != NULL);							\
dvander@2320: 	if (v == NULL) {							\
dvander@2320: 		err = SP_ERROR_INVALID_INSTRUCTION;		\
dvander@2320: 		goto return_error;						\
dvander@2320: 	}
dvander@2320: 
dvander@2320: void *operator new(size_t size, ControlFlowGraph *graph)
dvander@2320: {
dvander@2320: 	return malloc(size);
dvander@2320: }
dvander@2320: 
dvander@2320: void *operator new[](size_t size, ControlFlowGraph *graph)
dvander@2320: {
dvander@2320: 	return malloc(size);
dvander@2320: }
dvander@2320: 
dvander@2320: void operator delete(void *mem, ControlFlowGraph *graph)
dvander@2320: {
dvander@2320: 	free(mem);
dvander@2320: }
dvander@2320: 
dvander@2320: void operator delete[](void *mem, ControlFlowGraph *graph)
dvander@2320: {
dvander@2320: 	free(mem);
dvander@2320: }
dvander@2320: 
dvander@2320: #define MAX_STACK_ENTRIES		256
dvander@2320: 
dvander@2320: struct StackEntry
dvander@2320: {
dvander@2320: 	StackEntry()
dvander@2320: 	{
dvander@2320: 	}
dvander@2320: 	StackEntry(cell_t d, BaseNode *e) : depth(d), expr(e)
dvander@2320: 	{
dvander@2320: 	}
dvander@2320: 	cell_t depth;
dvander@2320: 	BaseNode *expr;
dvander@2320: };
dvander@2320: 
dvander@2320: int sp_AnalyzeGraph(sp_decomp_t *dc, ControlFlowGraph *graph)
dvander@2320: {
dvander@2320: 	int err;
dvander@2320: 	cell_t sp;
dvander@2320: 	Block *block;
dvander@2320: 	cell_t *pcode;
dvander@2320: 	cell_t cip, cip_end;
dvander@2320: 	StmtNode *root, *rtemp;
dvander@2320: 	StmtNode *root_tail;
dvander@2320: 	BaseNode *pri, *alt;
dvander@2320: 	FunctionInfo *func, *tfunc;
dvander@2320: 	cell_t p1, p2, op;
dvander@2320: 	FuncVar *v1, *v2;
dvander@2322: 	unsigned int callnumber = 0;
dvander@2320: 	unsigned int stack_entries = 0;
dvander@2320: 	StackEntry eval_stack[MAX_STACK_ENTRIES];
dvander@2320: 
dvander@2320: 	/* Init everything.
dvander@2320: 	 * Stack pointer starts off at 0.
dvander@2320: 	 */
dvander@2320: 	sp = 0;
dvander@2320: 	pri = NULL;
dvander@2320: 	alt = NULL;
dvander@2320: 	root = NULL;
dvander@2320: 	func = graph->func;
dvander@2320: 	block = graph->entry;
dvander@2320: 	pcode = (cell_t *)dc->plugin->pcode;
dvander@2320: 
dvander@2320: 	cip = block->ip_start;
dvander@2320: 	cip_end = block->ip_end;
dvander@2320: 
dvander@2320: 	root_tail = root = new (graph) StmtNode(_OP_STMT, NULL, NULL);
dvander@2320: 
dvander@2320: 	while (cip < cip_end)
dvander@2320: 	{
dvander@2320: 		op = PCODE_VAL(pcode, cip);
dvander@2320: 
dvander@2320: 		switch (op)
dvander@2320: 		{
dvander@2320: 		case OP_PROC:
dvander@2320: 		case OP_BREAK:
dvander@2320: 			{
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_CALL:
dvander@2325: 		case OP_SYSREQ_N:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2325: 				if (op == OP_CALL)
dvander@2325: 				{
dvander@2325: 					tfunc = sp_GetFuncPrototype(dc, p1, false);
dvander@2325: 				}
dvander@2325: 				else if (op == OP_SYSREQ_N)
dvander@2325: 				{
dvander@2325: 					assert(dc->natives);
dvander@2325: 					assert(uint32_t(p1) < dc->plugin->num_natives);
dvander@2325: 					tfunc = &dc->natives[p1];
dvander@2325: 				}
dvander@2320: 				CHECK_VALUE(tfunc);
dvander@2320: 
dvander@2320: 				/* Sanity checks, :TODO: runtime checks later. */
dvander@2320: 				assert(stack_entries >= 1);
dvander@2320: 
dvander@2325: 				if (op == OP_SYSREQ_N)
dvander@2325: 				{
dvander@2325: 					p2 = PCODE_PARAM(pcode, cip, 2);
dvander@2325: 				}
dvander@2325: 				else
dvander@2325: 				{
dvander@2325: 					/* Try to read the value off the stack. */
dvander@2325: 					ConstNode *cnode;
dvander@2325: 					cnode = (ConstNode *)eval_stack[stack_entries-1].expr;
dvander@2325: 					/* Sanity checks, :TODO: runtime checks later. */
dvander@2325: 					assert(cnode->op == _OP_CONST);
dvander@2325: 					assert(cnode->val >= 0);
dvander@2325: 					assert(uint32_t(cnode->val) == tfunc->num_known_args);
dvander@2325: 					p2 = cnode->val;
dvander@2325: 					stack_entries--;
dvander@2325: 				}
dvander@2320: 
dvander@2325: 				assert(uint32_t(p2) <= stack_entries);
dvander@2320: 				
dvander@2325: 				/* Build arg SSA */
dvander@2325: 				BaseNode **nodes = new (graph) BaseNode *[p2];
dvander@2325: 				for (cell_t argno = 0; argno < p2; argno++, stack_entries--)
dvander@2320: 				{
dvander@2320: 					nodes[argno] = eval_stack[stack_entries-1].expr;
dvander@2320: 				}
dvander@2320: 
dvander@2325: 				/* Get rid of any args we pushed. */
dvander@2325: 				sp += p2 * sizeof(cell_t);
dvander@2325: 				if (op == OP_CALL)
dvander@2325: 				{
dvander@2325: 					sp += sizeof(cell_t);
dvander@2325: 				}
dvander@2320: 				assert(sp <= 0);
dvander@2320: 
dvander@2325: 				/* Build function call SSA */
dvander@2325: 				pri = new (graph) CallNode(tfunc, nodes, p2);
dvander@2322: 				pri = new (graph) DefineNode(pri, "call%03x", ++callnumber);
dvander@2322: 				rtemp = new (graph) StmtNode(_OP_STMT, pri, NULL);
dvander@2322: 				root_tail->next = rtemp;
dvander@2322: 				root_tail = rtemp;
dvander@2322: 				pri = new (graph) UseNode((DefineNode *)pri);
dvander@2320: 				
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_CONST_PRI:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2320: 				pri = new (graph) ConstNode(p1);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_PUSH_C:
dvander@2325: 		case OP_PUSH2_C:
dvander@2325: 		case OP_PUSH3_C:
dvander@2325: 		case OP_PUSH5_C:
dvander@2320: 			{
dvander@2325: 				for (int N = 1; N <= dc->opdef[op].params; N++)
dvander@2320: 				{
dvander@2325: 					p1 = PCODE_PARAM(pcode, cip, N);
dvander@2325: 
dvander@2325: 					/* Adjust stack pointer. */
dvander@2325: 					sp -= sizeof(cell_t);
dvander@2325: 
dvander@2325: 					if ((v1 = sp_FindGraphVar(func, cip, sp, sp)) == NULL)
dvander@2325: 					{
dvander@2325: 						/* Add a new stack entry. */
dvander@2325: 						assert(stack_entries < MAX_STACK_ENTRIES);
dvander@2325: 						eval_stack[stack_entries++] = StackEntry(sp, new ConstNode(p1));
dvander@2325: 					}
dvander@2325: 					else
dvander@2320: 					{
dvander@2325: 						assert(v1->new_stmt == NULL);
dvander@2325: 						if (v1->new_stmt == NULL)
dvander@2325: 						{
dvander@2325: 							v1->new_stmt = new (graph) DeclNode(
dvander@2325: 								new (graph) VarNode(v1),
dvander@2325: 								new (graph) ConstNode(p1));
dvander@2325: 							rtemp = new (graph) StmtNode(
dvander@2325: 								_OP_STMT,
dvander@2325: 								v1->new_stmt,
dvander@2325: 								NULL);
dvander@2325: 							root_tail->next = rtemp;
dvander@2325: 							root_tail = rtemp;
dvander@2325: 						}
dvander@2320: 					}
dvander@2320: 				}
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_PUSH_S:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2320: 				v1 = sp_FindGraphVar(func, cip, sp, p1);
dvander@2320: 				CHECK_VALUE(v1);
dvander@2320: 
dvander@2320: 				/* Adjust stack pointer. */
dvander@2320: 				sp -= sizeof(cell_t);
dvander@2320: 
dvander@2320: 				/* Right now, don't allow aliasing or overflows. */
dvander@2320: 				assert(sp_FindGraphVar(func, cip, sp, sp) == NULL);
dvander@2320: 				assert(stack_entries < MAX_STACK_ENTRIES);
dvander@2320: 
dvander@2320: 				/* Add a new stack entry. */
dvander@2320: 				eval_stack[stack_entries++] = StackEntry(sp, new (graph) VarNode(v1));
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_PUSH_PRI:
dvander@2320: 			{
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 
dvander@2320: 				/* Adjust stack pointer. */
dvander@2320: 				sp -= sizeof(cell_t);
dvander@2320: 				
dvander@2320: 				/* Right now, don't allow aliasing or overflows. */
dvander@2320: 				assert(sp_FindGraphVar(func, cip, sp, sp) == NULL);
dvander@2320: 				assert(stack_entries < MAX_STACK_ENTRIES);
dvander@2320: 
dvander@2320: 				/* Add a new stack entry. */
dvander@2320: 				eval_stack[stack_entries++] = StackEntry(sp, pri);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_POP_ALT:
dvander@2320: 			{
dvander@2320: 				assert(stack_entries > 0);
dvander@2320: 				assert(eval_stack[stack_entries - 1].depth == sp);
dvander@2320: 
dvander@2320: 				alt = eval_stack[--stack_entries].expr;
dvander@2320: 				sp += sizeof(cell_t);
dvander@2320: 				assert(sp <= 0);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_STACK:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2320: 				sp += p1;
dvander@2320: 				assert(sp <= 0);
dvander@2320: 				if (p1 < 0)
dvander@2320: 				{
dvander@2320: 					/* Find if we should track a new variable declaration. */
dvander@2320: 					v1 = sp_FindGraphVar(func, cip, sp, sp);
dvander@2320: 					CHECK_VALUE(v1);
dvander@2320: 					assert(v1->new_stmt == NULL);
dvander@2320: 					if (v1->new_stmt == NULL)
dvander@2320: 					{
dvander@2320: 						v1->new_stmt = new (graph) DeclNode(
dvander@2320: 							new (graph) VarNode(v1),
dvander@2320: 							NULL);
dvander@2320: 						rtemp = new (graph) StmtNode(
dvander@2320: 							_OP_STMT,
dvander@2320: 							v1->new_stmt,
dvander@2320: 							NULL);
dvander@2320: 						root_tail->next = rtemp;
dvander@2320: 						root_tail = rtemp;
dvander@2320: 					}
dvander@2320: 					assert(abs(p1) >> 2 == 1);
dvander@2320: 				}
dvander@2320: 				else
dvander@2320: 				{
dvander@2320: 					/* Erase anything left over on the evaluation stack. */
dvander@2320: 					while (stack_entries > 0
dvander@2320: 						   && eval_stack[stack_entries - 1].depth < sp)
dvander@2320: 					{
dvander@2320: 						assert(0);
dvander@2320: 						stack_entries--;
dvander@2320: 					}
dvander@2320: 				}
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_ZERO_PRI:
dvander@2320: 			{
dvander@2320: 				pri = new (graph) ConstNode(0);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_MOVE_ALT:
dvander@2320: 			{
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 				alt = pri;
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_LOAD_S_PRI:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2320: 				v1 = sp_FindGraphVar(func, cip, sp, p1);
dvander@2320: 				CHECK_VALUE(v1);
dvander@2320: 				pri = new (graph) VarNode(v1);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_LOAD_S_ALT:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2320: 				v1 = sp_FindGraphVar(func, cip, sp, p1);
dvander@2320: 				CHECK_VALUE(v1);
dvander@2320: 				alt = new (graph) VarNode(v1);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_STOR_S_PRI:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2320: 				v1 = sp_FindGraphVar(func, cip, sp, p1);
dvander@2320: 				CHECK_VALUE(v1);
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 				rtemp = new (graph) StmtNode(
dvander@2320: 					_OP_STMT,
dvander@2320: 					new (graph) BinOpNode(_OP_STORE, new (graph) VarNode(v1), pri),
dvander@2320: 					NULL);
dvander@2320: 				root_tail->next = rtemp;
dvander@2320: 				root_tail = rtemp;
dvander@2320: 
dvander@2320: 				/** 
dvander@2320: 				 * We create a varnode to simulate a load here.
dvander@2320: 				 * This helps accidental duplication of the expression tree.
dvander@2320: 				 */
dvander@2320: 				pri = new (graph) VarNode(v1);	
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_LOAD_S_BOTH:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2320: 				p2 = PCODE_PARAM(pcode, cip, 2);
dvander@2320: 				v1 = sp_FindGraphVar(func, cip, sp, p1);
dvander@2320: 				v2 = sp_FindGraphVar(func, cip, sp, p2);
dvander@2320: 				CHECK_VALUE(v1);
dvander@2320: 				CHECK_VALUE(v2);
dvander@2320: 				pri = new (graph) VarNode(v1);
dvander@2320: 				alt = new (graph) VarNode(v2);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_ADD:
dvander@2320: 		case OP_SMUL:
dvander@2320: 			{
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 				CHECK_VALUE(alt);
dvander@2320: 				pri = new (graph) BinOpNode(op, pri, alt);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_SUB_ALT:
dvander@2320: 			{
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 				CHECK_VALUE(alt);
dvander@2320: 				pri = new (graph) BinOpNode(op, alt, pri);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_SDIV:
dvander@2320: 			{
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 				CHECK_VALUE(alt);
dvander@2320: 				pri = new (graph) BinOpNode(OP_SDIV, pri, alt);
dvander@2320: 				alt = new (graph) BinOpNode(_OP_MODULO, pri, alt);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_SDIV_ALT:
dvander@2320: 			{
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 				CHECK_VALUE(alt);
dvander@2320: 				pri = new (graph) BinOpNode(OP_SDIV, alt, pri);
dvander@2320: 				alt = new (graph) BinOpNode(_OP_MODULO, alt, pri);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_ADD_C:
dvander@2320: 		case OP_SMUL_C:
dvander@2320: 			{
dvander@2320: 				p1 = PCODE_PARAM(pcode, cip, 1);
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 				pri = new (graph) BinOpNode(op, pri, new (graph) ConstNode(p1));
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		case OP_RETN:
dvander@2320: 			{
dvander@2320: 				CHECK_VALUE(pri);
dvander@2320: 				rtemp = new (graph) StmtNode(op, pri, NULL);
dvander@2320: 				root_tail->next = rtemp;
dvander@2320: 				root_tail = rtemp;
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		default:
dvander@2320: 			{
dvander@2320: 				assert(0);
dvander@2320: 				break;
dvander@2320: 			}
dvander@2320: 		}
dvander@2320: 
dvander@2320: 		NEXT_OP(cip, op);
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	sp_DebugPrint(graph->func, dc, root->next);
dvander@2320: 
dvander@2320: 	return SP_ERROR_NONE;
dvander@2320: 
dvander@2320: return_error:
dvander@2320: 	return err;
dvander@2320: }
dvander@2320: 
dvander@2320: #undef CHECK_FUNCVAR
dvander@2320: 
dvander@2320: inline Block *sp_BlockFromMap(sp_decomp_t *dc, ControlFlowGraph *graph, cell_t cip)
dvander@2320: {
dvander@2320: 	cell_t val;
dvander@2320: 
dvander@2320: 	assert(PCODE_VAL(dc->pcode_map, cip) & PCM_HAS_BLOCK);
dvander@2320: 
dvander@2320: 	val = PCODE_VAL(dc->pcode_map, cip);
dvander@2320: 	val >>= PCM_NUM_BITS;
dvander@2320: 
dvander@2320: 	assert(val >= 0 && val < (cell_t)graph->used_blocks);
dvander@2320: 
dvander@2320: 	return &graph->blocks[val];
dvander@2320: }
dvander@2320: 
dvander@2320: void sp_InsertBlock(sp_decomp_t *dc, unsigned int index, cell_t cip)
dvander@2320: {
dvander@2320: 	cell_t val;
dvander@2320: 
dvander@2320: 	val = PCODE_VAL(dc->pcode_map, cip);
dvander@2320: 
dvander@2320: 	assert(!(val & PCM_HAS_BLOCK));
dvander@2320: 	assert(index < 0x20000000);
dvander@2320: 
dvander@2320: 	val |= PCM_HAS_BLOCK;
dvander@2320: 	val |= index << 3;
dvander@2320: 
dvander@2320: 	PCODE_VAL(dc->pcode_map, cip) = val;
dvander@2320: }
dvander@2320: 
dvander@2320: static Block *sp_BuildBlocks(sp_decomp_t *dc, ControlFlowGraph *graph, cell_t cip)
dvander@2320: {
dvander@2320: 	cell_t op;
dvander@2320: 	bool is_branch;
dvander@2320: 	cell_t target;
dvander@2320: 	Block *block;
dvander@2320: 	Edge *edge_tail;
dvander@2320: 	Block *outgoing;
dvander@2320: 	cell_t cip_end;
dvander@2320: 	cell_t *pcode;
dvander@2320: 
dvander@2320: 	target = 0;
dvander@2320: 	cip_end = graph->func->code_end;
dvander@2320: 	pcode = (cell_t *)dc->plugin->pcode;
dvander@2320: 
dvander@2320: 	if (PCODE_VAL(dc->pcode_map, cip) & PCM_HAS_BLOCK)
dvander@2320: 	{
dvander@2320: 		return sp_BlockFromMap(dc, graph, cip);
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	/* We can't add a new block if we hit our limit. */
dvander@2320: 	assert(graph->used_blocks < graph->max_blocks);
dvander@2320: 	if (graph->used_blocks >= graph->max_blocks)
dvander@2320: 	{
dvander@2320: 		return NULL;
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	edge_tail = NULL;
dvander@2320: 
dvander@2320: 	/* Reserve a new block. */
dvander@2320: 	block = &graph->blocks[graph->used_blocks++];
dvander@2320: 	block->ip_start = cip;
dvander@2320: 	
dvander@2320: 	/* Enter us into the map. */
dvander@2320: 	sp_InsertBlock(dc, graph->used_blocks - 1, cip);
dvander@2320: 
dvander@2320: 	/* Walk the code. */
dvander@2320: 	while (cip < cip_end)
dvander@2320: 	{
dvander@2320: 		/* Check whether this is the start of a new block. */
dvander@2320: 		if (cip != block->ip_start
dvander@2320: 			&& (PCODE_VAL(dc->pcode_map, cip) & PCM_BRANCH_TARGET))
dvander@2320: 		{
dvander@2320: 			block->ip_end = cip;
dvander@2320: 			if ((outgoing = sp_BuildBlocks(dc, graph, cip)) == NULL)
dvander@2320: 			{
dvander@2320: 				return NULL;
dvander@2320: 			}
dvander@2320: 			/* :TODO: add edge */
dvander@2320: 			return block;
dvander@2320: 		}
dvander@2320: 
dvander@2320: 		is_branch = false;
dvander@2320: 		op = PCODE_VAL(pcode, cip);
dvander@2320: 		NEXT_OP(cip, op);
dvander@2320: 
dvander@2320: 		if (is_branch)
dvander@2320: 		{
dvander@2320: 			/* Check that branch offsets go to valid instructions. */
dvander@2320: 			if (!(PCODE_VAL(dc->pcode_map, target) & PCM_OPCODE))
dvander@2320: 			{
dvander@2320: 				graph->err = SP_ERROR_INVALID_INSTRUCTION;
dvander@2320: 				return NULL;
dvander@2320: 			}
dvander@2320: 
dvander@2320: 			/* Get our target block. */
dvander@2320: 			if ((outgoing = sp_BuildBlocks(dc, graph, target)) == NULL)
dvander@2320: 			{
dvander@2320: 				return NULL;
dvander@2320: 			}
dvander@2320: 			/* :TODO: add edge */
dvander@2320: 		}
dvander@2320: 		else if (op == OP_RETN /* :TODO: || op == OP_RET*/)
dvander@2320: 		{
dvander@2320: 			block->ip_end = cip;
dvander@2320: 			return block;
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	graph->err = SP_ERROR_INVALID_INSTRUCTION;
dvander@2320: 
dvander@2320: 	return NULL;
dvander@2320: }
dvander@2320: 
dvander@2320: 
dvander@2320: int Sp_DecompFunction(sp_decomp_t *dc, uint32_t code_addr, bool is_public)
dvander@2320: {
dvander@2320: 	int err;
dvander@2320: 	cell_t op;
dvander@2320: 	ucell_t cip;
dvander@2320: 	cell_t *pcode;
dvander@2320: 	ucell_t cip_end;
dvander@2320: 	sp_file_t *plugin;
dvander@2320: 	FunctionInfo *func;
dvander@2320: 	ControlFlowGraph graph;
dvander@2320: 	
dvander@2320: 	func = NULL;
dvander@2320: 	plugin = dc->plugin;
dvander@2320: 	memset(&graph, 0, sizeof(graph));
dvander@2320: 
dvander@2320: 	if (code_addr >= plugin->pcode_size)
dvander@2320: 	{
dvander@2320: 		err = SP_ERROR_INVALID_INSTRUCTION;
dvander@2320: 		goto return_error;
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	pcode = (cell_t *)plugin->pcode;
dvander@2320: 
dvander@2320: 	if (PCODE_VAL(pcode, code_addr) != OP_PROC)
dvander@2320: 	{
dvander@2320: 		err = SP_ERROR_INVALID_INSTRUCTION;
dvander@2320: 		goto return_error;
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	cip = code_addr + sizeof(cell_t);
dvander@2320: 
dvander@2320: 	/* See if we have an existing function stored. */
dvander@2320: 	func = sp_GetFuncPrototype(dc, code_addr, true, is_public);
dvander@2320: 
dvander@2320: 	while (cip < plugin->pcode_size)
dvander@2320: 	{
dvander@2320: 		op = PCODE_VAL(pcode, cip);
dvander@2320: 		if (op >= OP_TOTAL || op < 0)
dvander@2320: 		{
dvander@2320: 			err = SP_ERROR_INVALID_INSTRUCTION;
dvander@2320: 		}
dvander@2320: 		if (dc->opdef[op].name == NULL)
dvander@2320: 		{
dvander@2320: 			err = SP_ERROR_INVALID_INSTRUCTION;
dvander@2320: 		}
dvander@2320: 		if (op == OP_PROC)
dvander@2320: 		{
dvander@2320: 			break;
dvander@2320: 		}
dvander@2320: 		NEXT_OP(cip, op);
dvander@2320: 	}
dvander@2320: 	cip_end = cip;
dvander@2320: 
dvander@2320: 	func->code_end = cip_end;
dvander@2320: 
dvander@2320: 	/* Now we can cache all local vars. */
dvander@2320: 	sp_CacheLocals(dc, func);
dvander@2320: 
dvander@2320: 	/** 
dvander@2320: 	 * Make the entry point as the first block.
dvander@2320: 	 * It needs to be flagged as well so it doesn't get double counted.
dvander@2320: 	 */
dvander@2320: 	memset(&PCODE_VAL(dc->pcode_map, code_addr), 0, cip_end - code_addr);
dvander@2320: 		   
dvander@2320: 	graph.max_blocks = 1;
dvander@2320: 	graph.func = func;
dvander@2320: 	PCODE_VAL(dc->pcode_map, code_addr) |= PCM_BRANCH_TARGET;
dvander@2320: 
dvander@2320: 	/* Walk the code. */
dvander@2320: 	{
dvander@2320: 		cell_t target;
dvander@2320: 		bool is_branch;
dvander@2320: 
dvander@2320: 		target = 0;
dvander@2320: 		cip = code_addr;
dvander@2320: 		while (cip < cip_end)
dvander@2320: 		{
dvander@2320: 			/* Get opcode */
dvander@2320: 			op = PCODE_VAL(pcode, cip);
dvander@2320: 			/* Mark as not a branch */
dvander@2320: 			is_branch = false;
dvander@2320: 			/* Make sure we know this is a valid target */
dvander@2320: 			PCODE_VAL(dc->pcode_map, cip) |= PCM_OPCODE;
dvander@2320: 
dvander@2320: 			if (is_branch)
dvander@2320: 			{
dvander@2320: 				/**
dvander@2320: 				 * Keep track of where branches are and how many blocks we need.
dvander@2320: 				 */
dvander@2320: 				if (!(PCODE_VAL(dc->pcode_map, target) & PCM_BRANCH_TARGET))
dvander@2320: 				{
dvander@2320: 					PCODE_VAL(dc->pcode_map, target) |= PCM_BRANCH_TARGET;
dvander@2320: 					graph.max_blocks++;
dvander@2320: 
dvander@2320: 					/**
dvander@2320: 					 * If we're creating a new block, estimate that we need to create a new edge 
dvander@2320: 					 * as well.
dvander@2320: 					 */
dvander@2320: 					graph.max_edges++;
dvander@2320: 				}
dvander@2320: 
dvander@2320:                 /**
dvander@2320:                  * In this algorithm, jumps do not terminate a block unless they are unconditional.
dvander@2320:                  * This reduces the number of blocks and edges.
dvander@2320:                  *
dvander@2320:                  * A property of this is that jumps are edges, so the number of edges is identical 
dvander@2320: 				 * to the number of jumps.
dvander@2320:                  */
dvander@2320: 				graph.max_edges++;
dvander@2320: 			}
dvander@2320: 
dvander@2320: 			NEXT_OP(cip, op);
dvander@2320: 		}
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	/* Initialize memory needed for the graph. */
dvander@2320: 	graph.blocks = new Block[graph.max_blocks];
dvander@2320: 	memset(graph.blocks, 0, sizeof(Block) * graph.max_blocks);
dvander@2320: 	
dvander@2320: 	if (graph.max_edges != 0)
dvander@2320: 	{
dvander@2320: 		graph.edges = new Edge[graph.max_edges];
dvander@2320: 		memset(graph.edges, 0, sizeof(Edge) * graph.max_edges);
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	if ((graph.entry = sp_BuildBlocks(dc, &graph, code_addr)) == NULL)
dvander@2320: 	{
dvander@2320: 		if ((err = graph.err) == SP_ERROR_NONE)
dvander@2320: 		{
dvander@2320: 			err = SP_ERROR_ABORTED;
dvander@2320: 		}
dvander@2320: 		goto return_error;
dvander@2320: 	}
dvander@2320: 
dvander@2325: 	if ((err = sp_AnalyzeGraph(dc, &graph)) != SP_ERROR_NONE)
dvander@2320: 	{
dvander@2320: 		goto return_error;
dvander@2320: 	}
dvander@2320: 
dvander@2320: 	return SP_ERROR_NONE;
dvander@2320: 
dvander@2320: return_error:
dvander@2320: 	return err;
dvander@2320: }