code.h

   1 #ifndef __CODE_H
   2 #define __CODE_H
   3
   4 #include "prx.h"
   5 #include "allegrex.h"
   6 #include "alloc.h"
   7 #include "lists.h"
   8 #include "types.h"
   9
  10 /* Possible reachable status */
  11 enum locationreachable {
  12   LOCATION_UNREACHABLE = 0,  /* Location is not reachable by any means */
  13   LOCATION_REACHABLE,        /* Location is reachable by some path */
  14   LOCATION_DELAY_SLOT        /* Location is a delay slot of a reachable branch/jump */
  15 };
  16
  17 /* If an error was detected one a location */
  18 enum locationerror {
  19   ERROR_NONE = 0,              /* No error */
  20   ERROR_INVALID_OPCODE,        /* Opcode is not recognized */
  21   ERROR_DELAY_SLOT,            /* Branch/jump inside a delay slot */
  22   ERROR_TARGET_OUTSIDE_FILE,   /* Branch/jump target outside the code */
  23   ERROR_ILLEGAL_BRANCH         /* Branch with a condition that can never occur, such as `bne  $0, $0, target' */
  24 };
  25
  26 /* Represents a location in the code */
  27 struct location {
  28   uint32 opc;                                /* The opcode (little-endian) */
  29   uint32 address;                            /* The virtual address of the location */
  30
  31   const struct allegrex_instruction *insn;   /* The decoded instruction or null (illegal opcode) */
  32   struct location *target;                   /* A possible target of a branch/jump */
  33
  34   list references;                           /* Number of references to this target inside the same subroutine */
  35   int  branchalways;                         /* True if this location is a branch that always occurs */
  36   enum locationreachable reachable;          /* Reachable status */
  37   enum locationerror  error;                 /* Error status */
  38
  39   struct subroutine *sub;                    /* Owner subroutine */
  40   struct basicblock *block;                  /* Basic block mark (used when extracting basic blocks) */
  41   struct codeswitch *cswitch;                /* Code switch mark */
  42 };
  43
  44 /* Represents a switch in the code */
  45 struct codeswitch {
  46   struct prx_reloc *jumpreloc;
  47   struct prx_reloc *switchreloc;
  48   struct location  *location;       /* The location that loads the base address of the switch */
  49   struct location  *jumplocation;   /* The location of the jump instruction */
  50   list   references;                /* A list of possible target locations (without repeating) */
  51   int    count;                     /* How many possible targets this switch have */
  52   int    checked;                   /* Is this switch valid? */
  53 };
  54
  55 /* Subroutine decompilation status */
  56 #define SUBROUTINE_EXTRACTED          1
  57 #define SUBROUTINE_CFG_EXTRACTED      2
  58
  59 /* A subroutine */
  60 struct subroutine {
  61   struct code *code;                /* The owner code of this subroutine */
  62   struct prx_function *export;      /* Is this a function export? */
  63   struct prx_function *import;      /* Is this a function import? */
  64
  65   struct location *begin;           /* Where the subroutine begins */
  66   struct location *end;             /* Where the subroutine ends */
  67
  68   struct basicblock *startblock;    /* Points to the first basic block of this subroutine */
  69   struct basicblock *endblock;      /* Points to the last basic block of this subroutine */
  70   list   blocks;                    /* A list of the basic blocks of this subroutine */
  71   list   dfsblocks, revdfsblocks;   /* Blocks ordered in DFS and Reverse-DFS order */
  72
  73   list   whereused;                 /* A list of basic blocks calling this subroutine */
  74   list   variables;
  75
  76   uint32 stacksize;
  77   int    numregargs;
  78
  79   int    haserror, status;          /* Subroutine decompilation status */
  80   int    temp;
  81 };
  82
  83 /* Represents a pair of integers */
  84 struct intpair {
  85   int first, last;
  86 };
  87
  88
  89 /* Abstract node in DFS and DOM trees (or reverse DFS and DOM trees) */
  90 struct basicblocknode {
  91   int dfsnum;                        /* The Depth-First search number */
  92   struct intpair domdfsnum;          /* To determine ancestry information in the dominator tree */
  93   struct basicblocknode *dominator;  /* The dominator node */
  94   struct basicblocknode *parent;     /* The parent node (in the depth-first search) */
  95   element blockel;                   /* An element inside the list (dfsblocks or revdfsblocks) */
  96   list children;                     /* Children in the DFS tree */
  97   list domchildren;                  /* Children in the dominator tree */
  98   list frontier;                     /* The dominator frontier */
  99 };
 100
 101 /* The type of the basic block */
 102 enum basicblocktype {
 103   BLOCK_START = 0,      /* The first basic block in a subroutine */
 104   BLOCK_SIMPLE,         /* A simple block */
 105   BLOCK_CALL,           /* A block that represents a call */
 106   BLOCK_END             /* The last basic block */
 107 };
 108
 109 /* The basic block */
 110 struct basicblock {
 111   enum basicblocktype type;                /* The type of the basic block *?
 112   element blockel;                         /* An element inside the list sub->blocks */
 113   union {
 114     struct {
 115       struct location *begin;              /* The start of the simple block */
 116       struct location *end;                /* The end of the simple block */
 117       struct location *jumploc;            /* The jump/branch location inside the block */
 118     } simple;
 119     struct {
 120       struct subroutine *calltarget;       /* The target of the call */
 121     } call;
 122   } info;
 123
 124   uint32 reg_gen[2], reg_kill[2];
 125   uint32 reg_live_in[2], reg_live_out[2];
 126   list   operations;
 127   struct subroutine *sub;                  /* The owner subroutine */
 128
 129   struct basicblocknode node;              /* Node info for DFS and DOM trees */
 130   struct basicblocknode revnode;           /* Node info for the reverse DFS and DOM trees */
 131
 132   list   inrefs, outrefs;                  /* A list of in- and out-edges of this block */
 133
 134   struct loopstructure *loopst;
 135   struct ifstructure *ifst;
 136
 137   int    haslabel, identsize;
 138
 139   int    mark1, mark2;
 140 };
 141
 142 enum edgetype {
 143   EDGE_UNKNOWN = 0,
 144   EDGE_GOTO,
 145   EDGE_CONTINUE,
 146   EDGE_BREAK,
 147   EDGE_FOLLOW,
 148   EDGE_IFEXIT
 149 };
 150
 151 struct basicedge {
 152   enum edgetype type;
 153   struct basicblock *from, *to;
 154   element fromel, toel;
 155   int fromnum, tonum;
 156 };
 157
 158 #define REGISTER_LINK 31
 159 #define REGISTER_LO   32
 160 #define REGISTER_HI   33
 161 #define NUM_REGISTERS 34
 162
 163 enum valuetype {
 164   VAL_CONSTANT = 0,
 165   VAL_REGISTER,
 166   VAL_VARIABLE
 167 };
 168
 169 struct value {
 170   enum valuetype type;
 171   union {
 172     uint32 intval;
 173     struct variable *variable;
 174   } val;
 175 };
 176
 177
 178 enum variabletype {
 179   VARIABLE_UNK = 0,
 180   VARIABLE_LOCAL,
 181   VARIABLE_ARGUMENT,
 182   VARIABLE_TEMP,
 183   VARIABLE_CONSTANT,
 184   VARIABLE_CONSTANTUNK,
 185   VARIABLE_INVALID
 186 };
 187
 188 struct variable {
 189   struct value name;
 190   enum variabletype type;
 191   uint32 info;
 192
 193   struct operation *def;
 194   list   uses;
 195 };
 196
 197 enum operationtype {
 198   OP_START,
 199   OP_END,
 200   OP_CALL,
 201   OP_INSTRUCTION,
 202   OP_MOVE,
 203   OP_ASM,
 204   OP_NOP,
 205   OP_PHI
 206 };
 207
 208 struct operation {
 209   enum operationtype type;
 210   enum allegrex_insn insn;
 211   struct location *begin;
 212   struct location *end;
 213   struct basicblock *block;
 214
 215   int  deferred;
 216
 217   list results;
 218   list operands;
 219 };
 220
 221 enum looptype {
 222   LOOP_WHILE,
 223   LOOP_REPEAT,
 224   LOOP_FOR
 225 };
 226
 227 struct loopstructure {
 228   enum looptype type;
 229   struct basicblock *start;
 230   struct basicblock *end;
 231   int    hasendgoto;
 232   list  edges;
 233 };
 234
 235 struct ifstructure {
 236   struct basicblock *end;
 237   int    outermost;
 238   int    hasendgoto;
 239 };
 240
 241
 242 struct code {
 243   struct prx *file;
 244
 245   uint32 baddr, numopc;
 246   struct location *base;
 247   struct location *end;
 248
 249   list subroutines;
 250
 251   listpool  lstpool;
 252   fixedpool switchpool;
 253   fixedpool subspool;
 254   fixedpool blockspool;
 255   fixedpool edgespool;
 256   fixedpool varspool;
 257   fixedpool opspool;
 258   fixedpool valspool;
 259   fixedpool loopspool;
 260   fixedpool ifspool;
 261 };
 262
 263
 264 struct code* code_analyse (struct prx *p);
 265 void code_free (struct code *c);
 266
 267 int decode_instructions (struct code *c);
 268 uint32 location_gpr_used (struct location *loc);
 269 uint32 location_gpr_defined (struct location *loc);
 270 int location_branch_may_swap (struct location *branch);
 271
 272 void extract_switches (struct code *c);
 273 void extract_subroutines (struct code *c);
 274
 275 void extract_cfg (struct subroutine *sub);
 276
 277 int cfg_dfs (struct subroutine *sub, int reverse);
 278
 279 int dom_isancestor (struct basicblocknode *ancestor, struct basicblocknode *node);
 280 struct basicblocknode *dom_common (struct basicblocknode *n1, struct basicblocknode *n2);
 281 void cfg_dominance (struct subroutine *sub, int reverse);
 282 void cfg_frontier (struct subroutine *sub, int reverse);
 283
 284 void reset_marks (struct subroutine *sub);
 285 void extract_structures (struct subroutine *sub);
 286
 287 void build_ssa (struct subroutine *sub);
 288 void extract_variables (struct subroutine *sub);
 289
 290
 291 #endif /* __CODE_H */