Rex Liu

What a disassembler may remember

damsel's register tracking on arm64: a snapshot that kept a wrong value for six weeks, and the week I taught the pass when to forget.

damsel is the Mach-O disassembler I started writing in Rust in April. One of its snapshot tests disassembles a small C program I wrote as a fixture, and for six weeks the snapshot had this line in it:

ldr x19, [x9, x8, lsl #3]   ; … | value x19=0x100004048 kind=Address source=AdrpLoad

That instruction is a switch. The fixture has a function that turns a number into its name, eight cases on value & 7 that each return a string, and the compiler built it as a table of eight string pointers. x9 holds the address of the table, x8 holds value & 7, and the load fetches one of the eight pointers. damsel claimed to know what x19 held afterwards: the address of the table itself, which is the one thing x19 never holds. A snapshot test records whatever the program prints and fails if it ever changes, so since April it had been guarding that answer very reliably.

Why it keeps values#

An arm64 instruction is 32 bits wide, which isn't room for a 64-bit address, so compilers build addresses in two steps. adrp puts the start of a 4 KiB page into a register, relative to the page the instruction sits on, and an add or a load supplies the offset inside it. A disassembler that only prints instructions leaves you to do the addition yourself, every time, in hex.

So damsel walks the instructions in order and keeps a map from each register to the value it believes that register holds. When an address comes together, it labels the result with what's there: a C string, an imported function, a stub, an Objective-C selector, a function pointer. The same map lets it resolve indirect control flow. blr x8 calls whatever x8 points to, and if the map knows x8, the listing can say where the call goes.

Most of the work in a pass like this is knowing when a belief stops being true.

In April the rules were short. When an instruction writes a register, forget that register. At a branch like b or b.eq, or at a return, forget everything, because the next instruction might be reached from somewhere else. The very first version also forgot everything at a call. Later that night I exempted bl and blr from the clear, which let values live through a call. One of them was x0, the register a call returns its result in.

Blocks and joins#

In May I gave the pass a picture of control flow. It now splits the listing into basic blocks, starting a new one at every branch target and after every branch, and it counts the ways into each block. A block with more than one way in is a join, and at a join the pass clears everything. I wrote the rule into the failure message of its test:

join block has two possible x0 values and must not inherit either one

Calls got a rule from the arm64 calling convention. A call may change x0 through x18 and the link register x30, and the function it calls has to hand x19 through x28 back the way it found them. So after a call damsel forgets the first group and keeps the second, and the test for it checks both halves: x0 must not survive bl, and after mov x19, #0x220, a call, and add x20, x19, #4, x20 must still come out as 0x224.

Blocks, joins and a rule for combining what arrives at a join are the basic shape of what compilers call dataflow analysis. Gary Kildall's 1973 paper, A unified approach to global program optimization, is the classic general treatment. The general version keeps whatever all the incoming paths agree on. I'd planned exactly that, keeping a value at a join when every path brings the same one, and what I built clears everything. It's the crude end of the same idea, and at a join it can only be wrong by knowing too little.

Stale values and invented ones#

With the blocks in place I spent a few evenings writing small synthetic listings, each built to make the pass believe something it shouldn't, and fixing whatever believed it. They came in two kinds.

The first kind is stale: a value that was true once and outlived the instruction that changed it. A register loaded from a jump table carried a note saying which table it came from, and at a branch that note took priority over the register's value. So after mov x10, #0x1234 had overwritten it, br x10 still resolved through the old table, to 0x3000. A post-indexed load like ldr x0, [x8], #8 reads through x8 and then adds 8 to it, and the pass kept x8 at 0x3000, so the next load through x8 pointed 8 bytes short. I fixed that one by forgetting x8, which is less precise than advancing it by 8 and can't be wrong.

One stale value came from a fix of mine. My rule for "this instruction writes a register" was that the first register operand gets written, which is wrong for stores. str x8, [sp] reads x8 and writes memory, so the pass was forgetting the value it had just watched being stored, and a later blr x8 lost its target. That was the opposite problem, forgetting too much, and I fixed it by exempting every instruction whose name starts with st. The next evening I found stxr. It's a store, and its name starts with st, and its first operand is written: stxr w8, x9, [sp] stores x9 and puts a status code in w8 saying whether the store went through. So x8 kept the 0x1234 it had before, and blr x8 resolved straight to it.

The second kind is worse, because the value was never true at all. Since the second day, a load had been recording the address it read from as the value it loaded. mov x8, #0x3000; ldr x10, [x8]; br x10 resolved the branch to 0x3000, the address of the pointer, as though it were the pointer. The line at the top of this post is the same mistake with an index in it. The pass didn't know value & 7, so it read through the table's base and recorded the base.

I'd also written a test, back in April, asserting that damsel resolved at least one indirect call in that fixture. It did. As far as I can reconstruct it, the call it resolved goes through a table of function pointers with the same unknown-index load in front of it, so the target it found was the start of the table, which is data. When I fixed the load I turned that test around, and it now asserts that damsel resolves none.

What it still forgets#

Forgetting too much has a cost too, and some of it is still there. After a cbz, the instruction that falls through has only one way in, so everything true before the branch is still true there. damsel clears it anyway, along with every other branch. Loops cost more. A loop header has two ways in, the one from above and the one coming back round, so every loop body starts knowing nothing, including any page address the compiler moved out of the loop so it wouldn't have to compute it on every pass.

Getting the loop values back means building the merge I'd planned in the first place. In the meantime the fixture's switch gets no value at all, and the call through its table of function pointers shows up as a call through x8 that damsel can't resolve. It's less than the listing said in April, and none of it is wrong.