subroutines.c

   1
   2 #include "code.h"
   3 #include "utils.h"
   4
   5
   6 static
   7 void mark_reachable (struct code *c, struct location *loc)
   8 {
   9   uint32 remaining = 1 + ((c->end->address - loc->address) >> 2);
  10   for (; remaining--; loc++) {
  11     if (loc->reachable == LOCATION_REACHABLE) break;
  12     loc->reachable = LOCATION_REACHABLE;
  13
  14     if (!loc->insn) return;
  15
  16     if (loc->insn->flags & INSN_JUMP) {
  17       if (remaining > 0) {
  18         if (loc[1].reachable != LOCATION_REACHABLE)
  19           loc[1].reachable = LOCATION_DELAY_SLOT;
  20       }
  21
  22       if (loc->target)
  23         mark_reachable (c, loc->target);
  24
  25       if (loc->cswitch) {
  26         if (loc->cswitch->checked) {
  27           element el = list_head (loc->cswitch->references);
  28           while (el) {
  29             struct location *target = element_getvalue (el);
  30             mark_reachable (c, target);
  31             if (!target->references)
  32               target->references = list_alloc (c->lstpool);
  33             if (target->cswitch != loc->cswitch)
  34               list_inserttail (target->references, loc);
  35             target->cswitch = loc->cswitch;
  36             el = element_next (el);
  37           }
  38         }
  39       }
  40
  41       if ((remaining == 0) || !(loc->insn->flags & (INSN_LINK | INSN_WRITE_GPR_D)))
  42         return;
  43
  44       loc++;
  45       remaining--;
  46     } else if (loc->insn->flags & INSN_BRANCH) {
  47       if (remaining > 0) {
  48         if (loc[1].reachable != LOCATION_REACHABLE)
  49           loc[1].reachable = LOCATION_DELAY_SLOT;
  50       }
  51
  52       if (loc->target) {
  53         mark_reachable (c, loc->target);
  54       }
  55
  56       if ((remaining == 0) || (loc->branchalways && !(loc->insn->flags & INSN_LINK)))
  57         return;
  58
  59       loc++;
  60       remaining--;
  61     }
  62   };
  63 }
  64
  65 static
  66 void new_subroutine (struct code *c, struct location *loc, struct prx_function *imp, struct prx_function *exp)
  67 {
  68   struct subroutine *sub = loc->sub;
  69
  70   if (!sub) {
  71     sub = fixedpool_alloc (c->subspool);
  72     sub->begin = loc;
  73     sub->code = c;
  74     sub->wherecalled = list_alloc (c->lstpool);
  75     loc->sub = sub;
  76   }
  77   if (imp) sub->import = imp;
  78   if (exp) sub->export = exp;
  79
  80   if (sub->import && sub->export) {
  81     sub->haserror = TRUE;
  82     error (__FILE__ ": location 0x%08X is both import and export", loc->address);
  83   }
  84
  85   mark_reachable (c, loc);
  86 }
  87
  88 static
  89 void extract_from_relocs (struct code *c)
  90 {
  91   uint32 i, tgt;
  92
  93   i = prx_findreloc (c->file, c->baddr);
  94   for (; i < c->file->relocnum; i++) {
  95     struct location *loc;
  96     struct prx_reloc *rel = &c->file->relocs[i];
  97
  98     tgt = (rel->target - c->baddr) >> 2;
  99     if (tgt >= c->numopc) continue;
 100
 101     if (rel->target & 0x03) {
 102       error (__FILE__ ": relocation not word aligned 0x%08X", rel->target);
 103       continue;
 104     }
 105
 106     loc = &c->base[tgt];
 107
 108     if (rel->type == R_MIPSX_JAL26) {
 109       new_subroutine (c, loc, NULL, NULL);
 110     } else if (rel->type == R_MIPS_26) {
 111       struct location *calledfrom;
 112       uint32 ctgt;
 113
 114       if (rel->vaddr < c->baddr) continue;
 115       if (rel->vaddr & 0x03) {
 116         error (__FILE__ ": relocation address not word aligned 0x%08X", rel->vaddr);
 117         continue;
 118       }
 119
 120       ctgt = (rel->vaddr - c->baddr) >> 2;
 121       if (ctgt >= c->numopc) continue;
 122
 123       calledfrom = &c->base[ctgt];
 124       if (calledfrom->insn->insn == I_JAL) {
 125         new_subroutine (c, loc, NULL, NULL);
 126       }
 127     } else if (rel->type == R_MIPS_32) {
 128       if (!loc->cswitch)
 129         new_subroutine (c, loc, NULL, NULL);
 130     } else if (rel->type == R_MIPS_HI16 || rel->type == R_MIPSX_HI16) {
 131       /* TODO */
 132       if (!loc->cswitch)
 133         new_subroutine (c, loc, NULL, NULL);
 134     }
 135   }
 136 }
 137
 138 static
 139 void extract_from_exports (struct code *c)
 140 {
 141   uint32 i, j, tgt;
 142
 143   for (i = 0; i < c->file->modinfo->numexports; i++) {
 144     struct prx_export *exp;
 145
 146     exp = &c->file->modinfo->exports[i];
 147     for (j = 0; j < exp->nfuncs; j++) {
 148       struct location *loc;
 149
 150       tgt = (exp->funcs[j].vaddr - c->baddr) >> 2;
 151       if (exp->funcs[j].vaddr < c->baddr ||
 152           tgt >= c->numopc) {
 153         error (__FILE__ ": invalid exported function");
 154         continue;
 155       }
 156
 157       loc = &c->base[tgt];
 158       new_subroutine (c, loc, NULL, &exp->funcs[j]);
 159     }
 160   }
 161 }
 162
 163 static
 164 void extract_from_imports (struct code *c)
 165 {
 166   uint32 i, j, tgt;
 167
 168   for (i = 0; i < c->file->modinfo->numimports; i++) {
 169     struct prx_import *imp;
 170
 171     imp = &c->file->modinfo->imports[i];
 172     for (j = 0; j < imp->nfuncs; j++) {
 173       struct location *loc;
 174
 175       tgt = (imp->funcs[j].vaddr - c->baddr) >> 2;
 176       if (imp->funcs[j].vaddr < c->baddr ||
 177           tgt >= c->numopc) {
 178         error (__FILE__ ": invalid imported function");
 179         continue;
 180       }
 181
 182       loc = &c->base[tgt];
 183       new_subroutine (c, loc, &imp->funcs[j], NULL);
 184     }
 185   }
 186 }
 187
 188 static
 189 struct subroutine *find_sub (struct code *c, struct location *loc)
 190 {
 191   do {
 192     if (loc->sub) return loc->sub;
 193   } while (loc-- != c->base);
 194   return NULL;
 195 }
 196
 197 static
 198 void extract_hidden_subroutines (struct code *c)
 199 {
 200   struct subroutine *cursub = NULL;
 201   uint32 i;
 202   int changed = TRUE;
 203
 204   /* TODO */
 205   while (changed) {
 206     changed = FALSE;
 207     for (i = 0; i < c->numopc; i++) {
 208       struct location *loc = &c->base[i];
 209       if (loc->sub) cursub = loc->sub;
 210       if (loc->reachable == LOCATION_UNREACHABLE) continue;
 211
 212       if (loc->target) {
 213         struct location *target;
 214         struct subroutine *targetsub;
 215
 216         target = loc->target;
 217         targetsub = find_sub (c, target);
 218
 219         if (!target->sub && (targetsub != cursub)) {
 220           report (__FILE__ ": hidden subroutine at 0x%08X (called by 0x%08X)\n", target->address, loc->address);
 221           new_subroutine (c, target, NULL, NULL);
 222           changed = TRUE;
 223         }
 224       }
 225     }
 226   }
 227 }
 228
 229
 230
 231 static
 232 void delimit_borders (struct code *c)
 233 {
 234   struct subroutine *prevsub = NULL;
 235   uint32 i;
 236
 237   for (i = 0; i < c->numopc; i++) {
 238     if (c->base[i].sub) {
 239       list_inserttail (c->subroutines, c->base[i].sub);
 240       if (prevsub) {
 241         prevsub->end = &c->base[i - 1];
 242       }
 243       prevsub = c->base[i].sub;
 244     } else {
 245       c->base[i].sub = prevsub;
 246     }
 247   }
 248   if (prevsub) {
 249     prevsub->end = &c->base[i - 1];
 250   }
 251 }
 252
 253
 254 static
 255 void check_switches (struct subroutine *sub)
 256 {
 257   struct location *loc;
 258   loc = sub->begin;
 259   do {
 260     if (!loc->cswitch) continue;
 261     if (loc->cswitch->jumplocation == loc) {
 262       element el;
 263       int haserror = FALSE;
 264
 265       el = list_head (loc->cswitch->references);
 266       while (el) {
 267         struct location *target = element_getvalue (el);
 268         if (target->sub != loc->sub) haserror = TRUE;
 269         target->cswitch = NULL;
 270         el = element_next (el);
 271       }
 272
 273       if (haserror) {
 274         report (__FILE__ ": invalid switch at 0x%08X\n", loc->address);
 275         fixedpool_free (sub->code->switchpool, loc->cswitch);
 276         loc->cswitch = NULL;
 277       } else {
 278         loc->cswitch->checked = TRUE;
 279         if (loc->reachable == LOCATION_REACHABLE) {
 280           loc->reachable = LOCATION_UNREACHABLE;
 281           mark_reachable (sub->code, loc);
 282         }
 283       }
 284     }
 285   } while (loc++ != sub->end);
 286 }
 287
 288 static
 289 void check_subroutine (struct subroutine *sub)
 290 {
 291   struct location *loc;
 292   loc = sub->begin;
 293
 294   if ((sub->end->address - sub->begin->address) < 4) {
 295     error (__FILE__ ": subroutine is too short: 0x%08X", sub->begin->address);
 296     sub->haserror = TRUE;
 297     return;
 298   }
 299
 300   do {
 301     if (loc->reachable == LOCATION_UNREACHABLE) continue;
 302
 303     if (loc->error != ERROR_NONE) {
 304       switch (loc->error) {
 305       case ERROR_INVALID_OPCODE:
 306         error (__FILE__ ": invalid opcode 0x%08X at 0x%08X (sub: 0x%08X)", loc->opc, loc->address, sub->begin->address);
 307         sub->haserror = TRUE;
 308         break;
 309       case ERROR_TARGET_OUTSIDE_FILE:
 310         error (__FILE__ ": branch/jump outside file at 0x%08X (sub: 0x%08X)", loc->address, sub->begin->address);
 311         sub->haserror = TRUE;
 312         break;
 313       case ERROR_DELAY_SLOT:
 314         error (__FILE__ ": delay slot error at 0x%08X (sub: 0x%08X)", loc->address, sub->begin->address);
 315         sub->haserror = TRUE;
 316         break;
 317       case ERROR_ILLEGAL_BRANCH:
 318         error (__FILE__ ": illegal branch at 0x%08X (sub: 0x%08X)", loc->address, sub->begin->address);
 319         sub->haserror = TRUE;
 320         break;
 321       case ERROR_NONE:
 322         break;
 323       }
 324     }
 325
 326     if (sub->haserror) continue;
 327
 328
 329     if (loc->target) {
 330       if (!loc->target->references)
 331         loc->target->references = list_alloc (sub->code->lstpool);
 332       list_inserttail (loc->target->references, loc);
 333     }
 334   } while (loc++ != sub->end);
 335   loc--;
 336
 337   if (loc->reachable == LOCATION_UNREACHABLE) return;
 338   loc--;
 339
 340   if ((loc->insn->flags & (INSN_JUMP | INSN_LINK | INSN_WRITE_GPR_D)) == INSN_JUMP)
 341     return;
 342
 343   if ((loc->insn->flags & (INSN_BRANCH | INSN_LINK)) == INSN_BRANCH && loc->branchalways)
 344     return;
 345
 346   error (__FILE__ ": subroutine at 0x%08X (end 0x%08X) has no finish", sub->begin->address, sub->end->address);
 347   sub->haserror = TRUE;
 348 }
 349
 350 void extract_subroutines (struct code *c)
 351 {
 352   element el;
 353
 354   c->subroutines = list_alloc (c->lstpool);
 355
 356   extract_from_exports (c);
 357   extract_from_imports (c);
 358   extract_from_relocs (c);
 359
 360   if (!c->base->sub) {
 361     error (__FILE__ ": creating artificial subroutine at address 0x%08X", c->baddr);
 362     new_subroutine (c, c->base, NULL, NULL);
 363   }
 364
 365   extract_hidden_subroutines (c);
 366   delimit_borders (c);
 367
 368
 369   el = list_head (c->subroutines);
 370   while (el) {
 371     struct subroutine *sub = element_getvalue (el);
 372     if (!sub->import) {
 373       check_switches (sub);
 374       check_subroutine (sub);
 375       if (!sub->haserror) extract_cfg (sub);
 376       if (!sub->haserror) extract_structures (sub);
 377       if (!sub->haserror) build_ssa (sub);
 378       if (!sub->haserror) extract_variables (sub);
 379     }
 380     el = element_next (el);
 381   }
 382 }
 383