X86: handle memory address load chains

[MattWindsor91]

Some compilers like to emit chains of movs like this:

mov [stack], heap    ; put memory address on stack
mov EAX,     [stack] ; move memory address into register
mov EAX,     [EAX]   ; dereference memory address

Herd doesn't like the idea of manipulating memory addresses in this way, and complains about the syntax of the first instruction.

It's not clear what the best way to fix these issues is. If we were sanitising this at the act level, we'd need to detect this particular flow and convert it to mov EAX, [heap]. But this might change the semantics of the program!

This might be something we can extend Herd to understand, but it sounds a bit sketchy.

[MattWindsor91]

Sometimes the chain is even weirder, which'd require a degree of flow analysis. Here's an actual example:

P0                  | P1                  ;
movl [t0sZM4], ZUy  | movl [t1sZM4], ZUx  ;
movl EAX, [t0sZM4]  | movl EAX, [t1sZM4]  ;
movl EAX, [EAX]     | movl EAX, [EAX]     ;
movl [t0sZM12], EAX | movl [t1sZM12], EAX ;
movl EAX, [t0sZM12] | movl EAX, [t1sZM12] ;
movl [ZUt0r0], EAX  | movl [ZUt1r0], EAX  ;
movl [t0sZM8], ZUx  | movl [t1sZM8], ZUy  ;
movl [t0sZM16], 1   | movl [t1sZM16], 1   ;
movl EAX, [t0sZM16] | movl EAX, [t1sZM16] ;
movl EDX, EAX       | movl EDX, EAX       ;
movl EAX, [t0sZM8]  | movl EAX, [t1sZM8]  ;
movl [EAX], EDX     | movl [EAX], EDX     ;

[MattWindsor91]

A few days ago, I added a heuristic uses_immediate_heap_symbol (it's in Abstract_operands, but seems to have ended up unexpected) that checks to see if any of the operands are a heap symbol used as an immediate value (like ZUy above). This was supposed to be the start of implementing a fix for this, but I got sidetracked.

Things that need doing:

• the heuristic should be able to, specifically, look for heap symbols in source position
• we should warn if we see these sorts of symbols—this'll make it obvious where our heuristics are failing
• to begin with, make a zipper pass that does the following:
  • marks any movement of an immediate heap symbol into a register
  • keeps moving forwards so long as each statement is a symbol that is part of a move chain
  • once we get to a dereferencing, delete all of the statements in between and replaces them with a direct memory reference
• eventually extend the pass so that, if the chain is broken, it rewinds back and starts doing more sophisticated analysis

[MattWindsor91]

Most of today has been spent finding out, the hard way, that:

• the abstract model should distinguish between %EAX (read from register) and (%EAX) (register indirect);
• it presently doesn't (in fact, it refers to %EAX as 'unknown', and doesn't have a leg for it.

[MattWindsor91]

This has landed in act now, though in a fairly rigid form that might need further pruning.