code.h

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