draperlaboratory / VIBES

Verified, Incremental, Binary Editing with Synthesis
MIT License
51 stars 1 forks source link

Perform naiive branch relaxing (and other fixes to the BIR passes) #210

Closed bmourad01 closed 2 years ago

bmourad01 commented 2 years ago

There's a number of changes here:

  1. Branch relaxing (see #195)
  2. Hacky workaround for #179 (only affects Thumb, see the huge comment in Bir_passes.Shape.split_on_conditional)
  3. Only "finalize" higher variables at the "implicit exit" node. If we have a block that does goto L_0x1234, then this is not an implicit exit and we can assume that the higher vars aren't needed "at exit" in any particular register.
  4. Adds the lsl rt, [rn, rm, lsl #n] pattern to the current selector (results in much smaller code!)
philzook58 commented 2 years ago

Seems like good stuff. Great work! I am worried that it feels like the patch_spaces being in bir_passes is ensnarling the codebase in itself, but I don't see an easy way around it. Everything is dependent on everything if you want it to be really good unfortunately.

Is point 3 above correct? I think this is maybe because of a weakness of the schema of the config file. Each possible exit point should have it's own notion in general of where hvars need to be put. In other words we need a write-to relation: (addr, hvar, lowloc)

bmourad01 commented 2 years ago

Yes, it seems that this would be an avenue for future work. In general when we have a patch like:

x = y + z;
if (x > w) {
  goto L_0x1234;
}
--y;

We could just assume that once we go to 0x1234 there is an entirely different set of data dependencies (but for our purposes we just assume there are none at all), since we're kind of "aborting" the normal control flow of the function being patched.

Meanwhile, the fallthrough to --y means that we're continuing back to the end of the patch point, which means the dependencies should be preserved.

It would be nice to have some granularity per-exit about what kind of data dependency is needed.

philzook58 commented 2 years ago

Anyway seems good to me. Rebase and merge when you want. You've got conflicts right now