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