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
  11 #define RT(op) ((op >> 16) & 0x1F)
  12 #define RS(op) ((op >> 21) & 0x1F)
  13 #define RD(op) ((op >> 11) & 0x1F)
  14 #define SA(op) ((op >> 6)  & 0x1F)
  15 #define IMM(op) ((signed short) (op & 0xFFFF))
  16 #define IMMU(op) ((unsigned short) (op & 0xFFFF))
  17
  18 /* Subroutine decompilation status */
  19 #define SUBROUTINE_EXTRACTED                 1
  20 #define SUBROUTINE_CFG_EXTRACTED             2
  21 #define SUBROUTINE_OPERATIONS_EXTRACTED      4
  22 #define SUBROUTINE_LIVE_REGISTERS            8
  23 #define SUBROUTINE_CFG_TRAVERSE             16
  24 #define SUBROUTINE_CFG_TRAVERSE_REV         32
  25 #define SUBROUTINE_FIXUP_CALL_ARGS          64
  26 #define SUBROUTINE_SSA                     128
  27 #define SUBROUTINE_CONSTANTS_EXTRACTED     256
  28 #define SUBROUTINE_VARIABLES_EXTRACTED     512
  29 #define SUBROUTINE_STRUCTURES_EXTRACTED   1024
  30
  31 /* Register values */
  32 #define REGISTER_GPR_ZERO  0
  33 #define REGISTER_GPR_AT    1
  34 #define REGISTER_GPR_V0    2
  35 #define REGISTER_GPR_V1    3
  36 #define REGISTER_GPR_A0    4
  37 #define REGISTER_GPR_A1    5
  38 #define REGISTER_GPR_A2    6
  39 #define REGISTER_GPR_A3    7
  40 #define REGISTER_GPR_T0    8
  41 #define REGISTER_GPR_T1    9
  42 #define REGISTER_GPR_T2   10
  43 #define REGISTER_GPR_T3   11
  44 #define REGISTER_GPR_T4   12
  45 #define REGISTER_GPR_T5   13
  46 #define REGISTER_GPR_T6   14
  47 #define REGISTER_GPR_T7   15
  48 #define REGISTER_GPR_S0   16
  49 #define REGISTER_GPR_S1   17
  50 #define REGISTER_GPR_S2   18
  51 #define REGISTER_GPR_S3   19
  52 #define REGISTER_GPR_S4   20
  53 #define REGISTER_GPR_S5   21
  54 #define REGISTER_GPR_S6   22
  55 #define REGISTER_GPR_S7   23
  56 #define REGISTER_GPR_T8   24
  57 #define REGISTER_GPR_T9   25
  58 #define REGISTER_GPR_K0   26
  59 #define REGISTER_GPR_K1   27
  60 #define REGISTER_GPR_GP   28
  61 #define REGISTER_GPR_SP   29
  62 #define REGISTER_GPR_FP   30
  63 #define REGISTER_GPR_RA   31
  64 #define REGISTER_LO       32
  65 #define REGISTER_HI       33
  66 #define NUM_REGISTERS     34
  67 #define NUM_REGMASK   ((NUM_REGISTERS + 31) >> 4)
  68
  69
  70 #define IS_BIT_SET(flags, bit) ((1 << ((bit) & 31)) & ((flags)[(bit) >> 5]))
  71 #define BIT_SET(flags, bit) ((flags)[(bit) >> 5]) |= 1 << ((bit) & 31)
  72
  73 extern const uint32 regmask_call_gen[NUM_REGMASK];
  74 extern const uint32 regmask_call_kill[NUM_REGMASK];
  75 extern const uint32 regmask_subend_gen[NUM_REGMASK];
  76 extern const uint32 regmask_localvars[NUM_REGMASK];
  77
  78
  79 /* Possible reachable status */
  80 enum locationreachable {
  81   LOCATION_UNREACHABLE = 0,  /* Location is not reachable by any means */
  82   LOCATION_REACHABLE,        /* Location is reachable by some path */
  83   LOCATION_DELAY_SLOT        /* Location is a delay slot of a reachable branch/jump */
  84 };
  85
  86 /* If an error was detected one a location */
  87 enum locationerror {
  88   ERROR_NONE = 0,              /* No error */
  89   ERROR_INVALID_OPCODE,        /* Opcode is not recognized */
  90   ERROR_DELAY_SLOT,            /* Branch/jump inside a delay slot */
  91   ERROR_TARGET_OUTSIDE_FILE,   /* Branch/jump target outside the code */
  92   ERROR_ILLEGAL_BRANCH         /* Branch with a condition that can never occur, such as `bne  $0, $0, target' */
  93 };
  94
  95 /* Represents a location in the code */
  96 struct location {
  97   uint32 opc;                                /* The opcode (little-endian) */
  98   uint32 address;                            /* The virtual address of the location */
  99
 100   const struct allegrex_instruction *insn;   /* The decoded instruction or null (illegal opcode) */
 101   struct location *target;                   /* A possible target of a branch/jump */
 102
 103   list references;                           /* Number of references to this target inside the same subroutine */
 104   int  branchalways;                         /* True if this location is a branch that always occurs */
 105   enum locationreachable reachable;          /* Reachable status */
 106   enum locationerror  error;                 /* Error status */
 107
 108   struct subroutine *sub;                    /* Owner subroutine */
 109   struct basicblock *block;                  /* Basic block mark (used when extracting basic blocks) */
 110   struct codeswitch *cswitch;                /* Code switch mark */
 111 };
 112
 113 /* Represents a switch in the code */
 114 struct codeswitch {
 115   struct prx_reloc *jumpreloc;
 116   struct prx_reloc *switchreloc;
 117   struct location  *location;       /* The location that loads the base address of the switch */
 118   struct location  *jumplocation;   /* The location of the jump instruction */
 119   list   references;                /* A list of possible target locations (without repeating) */
 120   int    count;                     /* How many possible targets this switch have */
 121   int    checked;                   /* Is this switch valid? */
 122 };
 123
 124 /* A subroutine */
 125 struct subroutine {
 126   struct code *code;                /* The owner code of this subroutine */
 127   struct prx_function *export;      /* Is this a function export? */
 128   struct prx_function *import;      /* Is this a function import? */
 129
 130   struct location *begin;           /* Where the subroutine begins */
 131   struct location *end;             /* Where the subroutine ends */
 132
 133   struct basicblock *startblock;    /* Points to the START basic block of this subroutine */
 134   struct basicblock *firstblock;    /* Points to the first SIMPLE basic block of this subroutine */
 135   struct basicblock *endblock;      /* Points to the END basic block of this subroutine */
 136   list   blocks;                    /* A list of the basic blocks of this subroutine */
 137   list   dfsblocks, revdfsblocks;   /* Blocks ordered in DFS and Reverse-DFS order */
 138
 139   list   whereused;                 /* A list of basic blocks calling this subroutine */
 140   list   callblocks;                /* Inner blocks of type CALL */
 141   list   variables;
 142
 143   uint32 stacksize;
 144   int    numregargs, numregout;
 145
 146   int    haserror, status;          /* Subroutine decompilation status */
 147   int    temp;
 148 };
 149
 150 /* Represents a pair of integers */
 151 struct intpair {
 152   int first, last;
 153 };
 154
 155
 156 /* Abstract node in DFS and DOM trees (or reverse DFS and DOM trees) */
 157 struct basicblocknode {
 158   int dfsnum;                        /* The Depth-First search number */
 159   struct intpair domdfsnum;          /* To determine ancestry information in the dominator tree */
 160   struct basicblocknode *dominator;  /* The dominator node */
 161   struct basicblocknode *parent;     /* The parent node (in the depth-first search) */
 162   element blockel;                   /* An element inside the list (dfsblocks or revdfsblocks) */
 163   list children;                     /* Children in the DFS tree */
 164   list domchildren;                  /* Children in the dominator tree */
 165   list frontier;                     /* The dominator frontier */
 166 };
 167
 168 /* The type of the basic block */
 169 enum basicblocktype {
 170   BLOCK_START = 0,      /* The first basic block in a subroutine */
 171   BLOCK_SIMPLE,         /* A simple block */
 172   BLOCK_CALL,           /* A block that represents a call */
 173   BLOCK_END             /* The last basic block */
 174 };
 175
 176 /* The basic block */
 177 struct basicblock {
 178   enum basicblocktype type;                /* The type of the basic block */
 179   element blockel;                         /* An element inside the list sub->blocks */
 180   union {
 181     struct {
 182       struct location *begin;              /* The start of the simple block */
 183       struct location *end;                /* The end of the simple block */
 184       struct location *jumploc;            /* The jump/branch location inside the block */
 185     } simple;
 186     struct {
 187       struct subroutine *calltarget;       /* The target of the call */
 188     } call;
 189   } info;
 190
 191   uint32 reg_gen[NUM_REGMASK], reg_kill[NUM_REGMASK];
 192   uint32 reg_live_in[NUM_REGMASK], reg_live_out[NUM_REGMASK];
 193   list   operations;
 194   struct subroutine *sub;                  /* The owner subroutine */
 195
 196   struct basicblocknode node;              /* Node info for DFS and DOM trees */
 197   struct basicblocknode revnode;           /* Node info for the reverse DFS and DOM trees */
 198
 199   list   inrefs, outrefs;                  /* A list of in- and out-edges of this block */
 200
 201   struct loopstructure *loopst;
 202   struct ifstructure *ifst;
 203
 204   int    haslabel, identsize;
 205
 206   int    mark1, mark2;
 207 };
 208
 209 enum edgetype {
 210   EDGE_UNKNOWN = 0,
 211   EDGE_GOTO,
 212   EDGE_CONTINUE,
 213   EDGE_BREAK,
 214   EDGE_FOLLOW,
 215   EDGE_IFEXIT
 216 };
 217
 218 struct basicedge {
 219   enum edgetype type;
 220   struct basicblock *from, *to;
 221   element fromel, toel;
 222   int fromnum, tonum;
 223 };
 224
 225 enum valuetype {
 226   VAL_CONSTANT = 0,
 227   VAL_REGISTER,
 228   VAL_VARIABLE
 229 };
 230
 231 struct value {
 232   enum valuetype type;
 233   union {
 234     uint32 intval;
 235     struct variable *variable;
 236   } val;
 237 };
 238
 239
 240 enum variabletype {
 241   VARIABLE_UNK = 0,
 242   VARIABLE_LOCAL,
 243   VARIABLE_ARGUMENT,
 244   VARIABLE_TEMP,
 245   VARIABLE_CONSTANT,
 246   VARIABLE_CONSTANTUNK,
 247   VARIABLE_INVALID
 248 };
 249
 250 struct variable {
 251   enum variabletype type;
 252
 253   struct value name;
 254   uint32 info;
 255
 256   struct operation *def;
 257   list   uses;
 258 };
 259
 260 enum operationtype {
 261   OP_START,
 262   OP_END,
 263   OP_CALL,
 264   OP_INSTRUCTION,
 265   OP_MOVE,
 266   OP_ASM,
 267   OP_NOP,
 268   OP_PHI
 269 };
 270
 271 struct operation {
 272   enum operationtype type;
 273   struct basicblock *block;
 274
 275   union {
 276     struct {
 277       enum allegrex_insn insn;
 278       struct location *loc;
 279     } iop;
 280     struct {
 281       struct location *begin, *end;
 282     } asmop;
 283     struct {
 284       list arguments;
 285       list retvalues;
 286     } callop;
 287   } info;
 288
 289   int  deferred;
 290
 291   list results;
 292   list operands;
 293 };
 294
 295 enum looptype {
 296   LOOP_WHILE,
 297   LOOP_REPEAT,
 298   LOOP_FOR
 299 };
 300
 301 struct loopstructure {
 302   enum looptype type;
 303   struct basicblock *start;
 304   struct basicblock *end;
 305   int    hasendgoto;
 306   list  edges;
 307 };
 308
 309 struct ifstructure {
 310   struct basicblock *end;
 311   int    outermost;
 312   int    hasendgoto;
 313 };
 314
 315
 316 /* Represents the entire PRX code */
 317 struct code {
 318   struct prx *file;        /* The PRX file */
 319
 320   uint32 baddr, numopc;    /* The code segment base address and number of opcodes */
 321   struct location *base;   /* The code segment start */
 322   struct location *end;    /* The code segment end */
 323
 324   list subroutines;        /* The list of subroutines */
 325
 326   listpool  lstpool;
 327   fixedpool switchpool;
 328   fixedpool subspool;
 329   fixedpool blockspool;
 330   fixedpool edgespool;
 331   fixedpool varspool;
 332   fixedpool opspool;
 333   fixedpool valspool;
 334   fixedpool loopspool;
 335   fixedpool ifspool;
 336 };
 337
 338
 339 struct code* code_analyse (struct prx *p);
 340 void code_free (struct code *c);
 341
 342 int decode_instructions (struct code *c);
 343 uint32 location_gpr_used (struct location *loc);
 344 uint32 location_gpr_defined (struct location *loc);
 345 int location_branch_may_swap (struct location *branch);
 346
 347 void extract_switches (struct code *c);
 348 void extract_subroutines (struct code *c);
 349
 350 void extract_cfg (struct subroutine *sub);
 351 void cfg_traverse (struct subroutine *sub, int reverse);
 352 int dom_isancestor (struct basicblocknode *ancestor, struct basicblocknode *node);
 353 struct basicblocknode *dom_common (struct basicblocknode *n1, struct basicblocknode *n2);
 354
 355
 356 struct operation *operation_alloc (struct basicblock *block);
 357 struct value *value_append (struct subroutine *sub, list l, enum valuetype type, uint32 value);
 358 void extract_operations (struct subroutine *sub);
 359 void merge_block_operations (struct subroutine *sub);
 360 void fixup_call_arguments (struct subroutine *sub);
 361 void remove_call_arguments (struct subroutine *sub);
 362
 363 void live_registers (struct code *c);
 364 void live_registers_imports (struct code *c);
 365
 366 void build_ssa (struct subroutine *sub);
 367 void unbuild_ssa (struct subroutine *sub);
 368
 369 void abi_check (struct subroutine *sub);
 370
 371 void propagate_constants (struct subroutine *sub);
 372 void extract_variables (struct subroutine *sub);
 373
 374
 375 void reset_marks (struct subroutine *sub);
 376 void extract_structures (struct subroutine *sub);
 377
 378 #endif /* __CODE_H */