From f34af567130fe00b14e46ee9deb5c4420ad6b966 Mon Sep 17 00:00:00 2001 From: Humberto Date: Tue, 5 May 2009 13:37:11 -0300 Subject: [PATCH] Melhorando documentacao --- code.h | 131 ++++++++++++++++++++++++++++++++-------------------------- controlflow.c | 45 +++++++++----------- graph.c | 26 ++++++------ outgraph.c | 8 ++-- ssa.c | 4 +- subroutines.c | 16 ++++--- 6 files changed, 123 insertions(+), 107 deletions(-) diff --git a/code.h b/code.h index 40f25ce..465325b 100644 --- a/code.h +++ b/code.h @@ -7,115 +7,129 @@ #include "lists.h" #include "types.h" +/* Possible reachable status */ enum locationreachable { - LOCATION_UNREACHABLE = 0, - LOCATION_REACHABLE, - LOCATION_DELAY_SLOT + LOCATION_UNREACHABLE = 0, /* Location is not reachable by any means */ + LOCATION_REACHABLE, /* Location is reachable by some path */ + LOCATION_DELAY_SLOT /* Location is a delay slot of a reachable branch/jump */ }; +/* If an error was detected one a location */ enum locationerror { - ERROR_NONE = 0, - ERROR_INVALID_OPCODE, - ERROR_DELAY_SLOT, - ERROR_TARGET_OUTSIDE_FILE, - ERROR_ILLEGAL_BRANCH + ERROR_NONE = 0, /* No error */ + ERROR_INVALID_OPCODE, /* Opcode is not recognized */ + ERROR_DELAY_SLOT, /* Branch/jump inside a delay slot */ + ERROR_TARGET_OUTSIDE_FILE, /* Branch/jump target outside the code */ + ERROR_ILLEGAL_BRANCH /* Branch with a condition that can never occur, such as `bne $0, $0, target' */ }; +/* Represents a location in the code */ struct location { - uint32 opc; - uint32 address; + uint32 opc; /* The opcode (little-endian) */ + uint32 address; /* The virtual address of the location */ - const struct allegrex_instruction *insn; - struct location *target; + const struct allegrex_instruction *insn; /* The decoded instruction or null (illegal opcode) */ + struct location *target; /* A possible target of a branch/jump */ - list references; - int branchalways; - enum locationreachable reachable; - enum locationerror error; + list references; /* Number of references to this target inside the same subroutine */ + int branchalways; /* True if this location is a branch that always occurs */ + enum locationreachable reachable; /* Reachable status */ + enum locationerror error; /* Error status */ - struct subroutine *sub; - struct basicblock *block; - struct codeswitch *cswitch; + struct subroutine *sub; /* Owner subroutine */ + struct basicblock *block; /* Basic block mark (used when extracting basic blocks) */ + struct codeswitch *cswitch; /* Code switch mark */ }; +/* Represents a switch in the code */ struct codeswitch { struct prx_reloc *jumpreloc; struct prx_reloc *switchreloc; - struct location *location; - struct location *jumplocation; - list references; - int count; - int checked; + struct location *location; /* The location that loads the base address of the switch */ + struct location *jumplocation; /* The location of the jump instruction */ + list references; /* A list of possible target locations (without repeating) */ + int count; /* How many possible targets this switch have */ + int checked; /* Is this switch valid? */ }; +/* Subroutine decompilation status */ +#define SUBROUTINE_EXTRACTED 1 +#define SUBROUTINE_CFG_EXTRACTED 2 + +/* A subroutine */ struct subroutine { - struct code *code; - struct prx_function *export; - struct prx_function *import; + struct code *code; /* The owner code of this subroutine */ + struct prx_function *export; /* Is this a function export? */ + struct prx_function *import; /* Is this a function import? */ - struct location *begin; - struct location *end; + struct location *begin; /* Where the subroutine begins */ + struct location *end; /* Where the subroutine ends */ - struct basicblock *startblock; - struct basicblock *endblock; - list blocks, dfsblocks, revdfsblocks; + struct basicblock *startblock; /* Points to the first basic block of this subroutine */ + struct basicblock *endblock; /* Points to the last basic block of this subroutine */ + list blocks; /* A list of the basic blocks of this subroutine */ + list dfsblocks, revdfsblocks; /* Blocks ordered in DFS and Reverse-DFS order */ - list wherecalled; + list whereused; /* A list of basic blocks calling this subroutine */ list variables; uint32 stacksize; int numregargs; - int haserror; + int haserror, status; /* Subroutine decompilation status */ int temp; }; - +/* Represents a pair of integers */ struct intpair { - int first; - int last; + int first, last; }; + +/* Abstract node in DFS and DOM trees (or reverse DFS and DOM trees) */ struct basicblocknode { - int dfsnum; - struct intpair domdfs; - struct basicblocknode *dominator; - struct basicblocknode *parent; - element block; - list children; - list domchildren; - list frontier; + int dfsnum; /* The Depth-First search number */ + struct intpair domdfsnum; /* To determine ancestry information in the dominator tree */ + struct basicblocknode *dominator; /* The dominator node */ + struct basicblocknode *parent; /* The parent node (in the depth-first search) */ + element blockel; /* An element inside the list (dfsblocks or revdfsblocks) */ + list children; /* Children in the DFS tree */ + list domchildren; /* Children in the dominator tree */ + list frontier; /* The dominator frontier */ }; +/* The type of the basic block */ enum basicblocktype { - BLOCK_START = 0, - BLOCK_END, - BLOCK_SIMPLE, - BLOCK_CALL + BLOCK_START = 0, /* The first basic block in a subroutine */ + BLOCK_SIMPLE, /* A simple block */ + BLOCK_CALL, /* A block that represents a call */ + BLOCK_END /* The last basic block */ }; +/* The basic block */ struct basicblock { - enum basicblocktype type; + enum basicblocktype type; /* The type of the basic block *? + element blockel; /* An element inside the list sub->blocks */ union { struct { - struct location *begin; - struct location *end; - struct location *jumploc; + struct location *begin; /* The start of the simple block */ + struct location *end; /* The end of the simple block */ + struct location *jumploc; /* The jump/branch location inside the block */ } simple; struct { - struct subroutine *calltarget; + struct subroutine *calltarget; /* The target of the call */ } call; } info; uint32 reg_gen[2], reg_kill[2]; uint32 reg_live_in[2], reg_live_out[2]; list operations; - struct subroutine *sub; + struct subroutine *sub; /* The owner subroutine */ - struct basicblocknode node; - struct basicblocknode revnode; + struct basicblocknode node; /* Node info for DFS and DOM trees */ + struct basicblocknode revnode; /* Node info for the reverse DFS and DOM trees */ - list inrefs, outrefs; + list inrefs, outrefs; /* A list of in- and out-edges of this block */ struct loopstructure *loopst; struct ifstructure *ifst; @@ -137,6 +151,7 @@ enum edgetype { struct basicedge { enum edgetype type; struct basicblock *from, *to; + element fromel, toel; int fromnum, tonum; }; diff --git a/controlflow.c b/controlflow.c index 71aa8f0..9b4d9a6 100644 --- a/controlflow.c +++ b/controlflow.c @@ -17,6 +17,7 @@ struct basicblock *alloc_block (struct subroutine *sub) block->node.frontier = list_alloc (sub->code->lstpool); block->revnode.frontier = list_alloc (sub->code->lstpool); block->sub = sub; + return block; } @@ -32,7 +33,7 @@ void extract_blocks (struct subroutine *sub) sub->dfsblocks = list_alloc (sub->code->lstpool); block = alloc_block (sub); - list_inserttail (sub->blocks, block); + block->blockel = list_inserttail (sub->blocks, block); block->type = BLOCK_START; sub->startblock = block; @@ -40,7 +41,7 @@ void extract_blocks (struct subroutine *sub) while (1) { block = alloc_block (sub); - list_inserttail (sub->blocks, block); + block->blockel = list_inserttail (sub->blocks, block); if (!begin) break; next = begin; @@ -106,20 +107,19 @@ void make_link (struct basicblock *from, struct basicblock *to) edge->to = to; edge->tonum = list_size (to->inrefs); - list_inserttail (from->outrefs, edge); - list_inserttail (to->inrefs, edge); + edge->fromel = list_inserttail (from->outrefs, edge); + edge->toel = list_inserttail (to->inrefs, edge); } static -element make_link_and_insert (struct basicblock *from, struct basicblock *to, element el) +struct basicblock *make_link_and_insert (struct basicblock *from, struct basicblock *to, element el) { struct basicblock *block = alloc_block (from->sub); - element inserted = element_alloc (from->sub->code->lstpool, block); - - element_insertbefore (el, inserted); + block->blockel = element_alloc (from->sub->code->lstpool, block); + element_insertbefore (el, block->blockel); make_link (from, block); make_link (block, to); - return inserted; + return block; } static @@ -128,7 +128,7 @@ void make_call (struct basicblock *block, struct location *loc) block->type = BLOCK_CALL; if (loc->target) { block->info.call.calltarget = loc->target->sub; - list_inserttail (loc->target->sub->wherecalled, block); + list_inserttail (loc->target->sub->whereused, block); } } @@ -139,7 +139,7 @@ void link_blocks (struct subroutine *sub) struct basicblock *block, *next; struct basicblock *target; struct location *loc; - element el, inserted; + element el; el = list_head (sub->blocks); @@ -169,8 +169,8 @@ void link_blocks (struct subroutine *sub) if (loc == block->info.simple.end) { struct basicblock *slot = alloc_block (sub); - inserted = element_alloc (sub->code->lstpool, slot); - element_insertbefore (el, inserted); + slot->blockel = element_alloc (sub->code->lstpool, slot); + element_insertbefore (el, slot->blockel); slot->type = BLOCK_SIMPLE; slot->info.simple.begin = &block->info.simple.end[1]; @@ -180,12 +180,10 @@ void link_blocks (struct subroutine *sub) } if (loc->insn->flags & INSN_LINK) { - inserted = make_link_and_insert (block, loc[2].block, el); - target = element_getvalue (inserted); + target = make_link_and_insert (block, loc[2].block, el); make_call (target, loc); } else if (loc->target->sub->begin == loc->target) { - inserted = make_link_and_insert (block, sub->endblock, el); - target = element_getvalue (inserted); + target = make_link_and_insert (block, sub->endblock, el); make_call (target, loc); } else { make_link (block, loc->target->block); @@ -193,14 +191,12 @@ void link_blocks (struct subroutine *sub) } else { if (loc->insn->flags & (INSN_LINK | INSN_WRITE_GPR_D)) { - inserted = make_link_and_insert (block, next, el); - target = element_getvalue (inserted); + target = make_link_and_insert (block, next, el); make_call (target, loc); } else { if (loc->target) { if (loc->target->sub->begin == loc->target) { - inserted = make_link_and_insert (block, sub->endblock, el); - target = element_getvalue (inserted); + target = make_link_and_insert (block, sub->endblock, el); make_call (target, loc); } else { make_link (block, loc->target->block); @@ -222,7 +218,6 @@ void link_blocks (struct subroutine *sub) } else { make_link (block, next); } - } } @@ -255,7 +250,7 @@ void mark_backward (struct subroutine *sub, struct basicblock *block, int num, i element el, ref; int count = 1; - el = block->node.block; + el = block->node.blockel; while (el && count) { struct basicblock *block = element_getvalue (el); if (block->node.dfsnum < end) break; @@ -284,7 +279,7 @@ void mark_forward (struct subroutine *sub, struct basicblock *block, { element el, ref; - el = block->node.block; + el = block->node.blockel; while (el) { struct basicblock *block = element_getvalue (el); if (block->node.dfsnum > end) break; @@ -428,7 +423,7 @@ void extract_ifs (struct subroutine *sub) while (domel) { int incount = 0; struct basicblocknode *dom = element_getvalue (domel); - struct basicblock *domblock = element_getvalue (dom->block); + struct basicblock *domblock = element_getvalue (dom->blockel); element ref; ref = list_head (domblock->inrefs); diff --git a/graph.c b/graph.c index 8759783..a5a29ff 100644 --- a/graph.c +++ b/graph.c @@ -42,7 +42,7 @@ void dfs_step (struct basicblock *block, int reverse) } node->dfsnum = block->sub->temp--; - node->block = list_inserthead (out, block); + node->blockel = list_inserthead (out, block); } int cfg_dfs (struct subroutine *sub, int reverse) @@ -57,8 +57,8 @@ int cfg_dfs (struct subroutine *sub, int reverse) int dom_isancestor (struct basicblocknode *ancestor, struct basicblocknode *node) { - return (ancestor->domdfs.first <= node->domdfs.first && - ancestor->domdfs.last <= node->domdfs.last); + return (ancestor->domdfsnum.first <= node->domdfsnum.first && + ancestor->domdfsnum.last <= node->domdfsnum.last); } struct basicblocknode *dom_common (struct basicblocknode *n1, struct basicblocknode *n2) @@ -75,29 +75,29 @@ struct basicblocknode *dom_common (struct basicblocknode *n1, struct basicblockn } static -void dom_dfs_step (struct basicblocknode *node, struct intpair *domdfs) +void dom_dfs_step (struct basicblocknode *node, struct intpair *domdfsnum) { struct basicblocknode *next; element el; - node->domdfs.first = (domdfs->first)++; + node->domdfsnum.first = (domdfsnum->first)++; el = list_head (node->domchildren); while (el) { next = element_getvalue (el); - if (!next->domdfs.first) - dom_dfs_step (next, domdfs); + if (!next->domdfsnum.first) + dom_dfs_step (next, domdfsnum); el = element_next (el); } - node->domdfs.last = (domdfs->last)--; + node->domdfsnum.last = (domdfsnum->last)--; } void cfg_dominance (struct subroutine *sub, int reverse) { struct basicblock *start; struct basicblocknode *startnode; - list blocks, refs; + struct intpair domdfsnum; int changed = TRUE; - struct intpair domdfs; + list blocks, refs; element el; if (reverse) { @@ -169,9 +169,9 @@ void cfg_dominance (struct subroutine *sub, int reverse) el = element_next (el); } - domdfs.first = 0; - domdfs.last = list_size (blocks); - dom_dfs_step (startnode, &domdfs); + domdfsnum.first = 0; + domdfsnum.last = list_size (blocks); + dom_dfs_step (startnode, &domdfsnum); } void cfg_frontier (struct subroutine *sub, int reverse) diff --git a/outgraph.c b/outgraph.c index 45ae55e..0fc3c66 100644 --- a/outgraph.c +++ b/outgraph.c @@ -83,10 +83,10 @@ void print_dominator (FILE *out, struct basicblock *block, int reverse, const ch if (reverse) { if (list_size (block->outrefs) <= 1) return; - dominator = element_getvalue (block->revnode.dominator->block); + dominator = element_getvalue (block->revnode.dominator->blockel); } else { if (list_size (block->inrefs) <= 1) return; - dominator = element_getvalue (block->node.dominator->block); + dominator = element_getvalue (block->node.dominator->blockel); } fprintf (out, " %3d -> %3d [color=%s];\n", block->node.dfsnum, dominator->node.dfsnum, color); @@ -105,7 +105,7 @@ void print_frontier (FILE *out, struct basicblock *block, list frontier, const c struct basicblock *refblock; refnode = element_getvalue (ref); - refblock = element_getvalue (refnode->block); + refblock = element_getvalue (refnode->blockel); fprintf (out, "%3d ", refblock->node.dfsnum); ref = element_next (ref); @@ -183,7 +183,7 @@ void print_subroutine_graph (FILE *out, struct code *c, struct subroutine *sub, if (ref != list_head (block->outrefs)) fprintf (out, "[arrowtail=dot]"); - if (element_getvalue (refblock->node.parent->block) == block) { + if (element_getvalue (refblock->node.parent->blockel) == block) { fprintf (out, "[style=bold]"); } else if (block->node.dfsnum >= refblock->node.dfsnum) { fprintf (out, "[color=red]"); diff --git a/ssa.c b/ssa.c index 0611f5e..f532788 100644 --- a/ssa.c +++ b/ssa.c @@ -562,7 +562,7 @@ void ssa_place_phis (struct subroutine *sub, list *defblocks) ref = list_head (block->node.frontier); while (ref) { brefnode = element_getvalue (ref); - bref = element_getvalue (brefnode->block); + bref = element_getvalue (brefnode->blockel); if (bref->mark2 != i && IS_BIT_SET (bref->reg_live_out, i)) { struct operation *op; @@ -677,7 +677,7 @@ void ssa_search (struct basicblock *block, list *vars) struct basicblock *child; childnode = element_getvalue (el); - child = element_getvalue (childnode->block); + child = element_getvalue (childnode->blockel); ssa_search (child, vars); el = element_next (el); } diff --git a/subroutines.c b/subroutines.c index 83cded3..7b8a769 100644 --- a/subroutines.c +++ b/subroutines.c @@ -71,7 +71,7 @@ void new_subroutine (struct code *c, struct location *loc, struct prx_function * sub = fixedpool_alloc (c->subspool); sub->begin = loc; sub->code = c; - sub->wherecalled = list_alloc (c->lstpool); + sub->whereused = list_alloc (c->lstpool); loc->sub = sub; } if (imp) sub->import = imp; @@ -128,7 +128,7 @@ void extract_from_relocs (struct code *c) if (!loc->cswitch) new_subroutine (c, loc, NULL, NULL); } else if (rel->type == R_MIPS_HI16 || rel->type == R_MIPSX_HI16) { - /* TODO */ + /* TODO: is this OK to do? */ if (!loc->cswitch) new_subroutine (c, loc, NULL, NULL); } @@ -201,7 +201,7 @@ void extract_hidden_subroutines (struct code *c) uint32 i; int changed = TRUE; - /* TODO */ + /* TODO: improve the hidden subroutine detection algorithm */ while (changed) { changed = FALSE; for (i = 0; i < c->numopc; i++) { @@ -372,8 +372,14 @@ void extract_subroutines (struct code *c) if (!sub->import) { check_switches (sub); check_subroutine (sub); - if (!sub->haserror) extract_cfg (sub); - if (!sub->haserror) extract_structures (sub); + if (!sub->haserror) { + sub->status |= SUBROUTINE_EXTRACTED; + extract_cfg (sub); + } + if (!sub->haserror) { + sub->status |= SUBROUTINE_CFG_EXTRACTED; + extract_structures (sub); + } if (!sub->haserror) build_ssa (sub); if (!sub->haserror) extract_variables (sub); } -- 2.11.4.GIT