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