Using Aliasing Information for Dynamic Binary Optimization

A compiler compiles code in a target program for later execution with a dynamic binary optimizer by including aliasing information with the compiled code. When the program is subsequently executed, the dynamic binary optimizer accesses the aliasing information to determine whether certain optimizations can be safely performed. Preferably, the aliasing information includes a memory reference index assigning an index to each memory reference instruction and a may-alias bit matrix indicating, for each memory reference instruction, which other memory reference instructions might reference the same memory location. Aliasing information is preferably used by the optimizer during execution to safely re-order operations.