[llvm-dev] Reordering of load/stores using MemorySSA

[Juneyoung Lee via llvm-dev]

Hello all,

It seems that it is insufficient to
rely on MemorySSA to correctly reorder load/stores.

For example, we have this following code:

v = load q
store 10, p

=>

store 10, p
v = load q // This is incorrect if p and q may alias

In the MemorySSA representation however,
there's no syntactic dependency between load/store,
because MemorySSA before transformation would look like this:

USE(M0) // corresponding to `v = load q`
M1 = DEF(M0) // corresponding to `store 10, p`

Reordering these two nodes does not break syntactic dependency,
hence additional flow-sensitive analysis is needed to check whether
reordering is valid.
To my understanding, GVNHoist seems to do that:
Memory operations in basic blocks are checked by
GVNHoist::hasMemoryUse().


If USE nodes of MemorySSA also have left-hand side, we can correctly
represent this kind of reorderability IMHO.

For the example above:

U1 = USE(M0) // corresponding to `v = load q`
M1 = DEF(M0, U1) // corresponding to `store 10, p`

Now there is a syntactic dependency between M1 and U1, hence
we can syntactically check whether reordering is allowed without any
flow-sensitive analysis.
If the store and load don't alias, we can remove U1 from DEF:

U1 = USE(M0) // corresponding to `v = load q`
M1 = DEF(M0) // corresponding to `store 10, p`

Then, the reordering is valid.

One issue is regarding PHI node: possible solution is to make
two kinds of PHIS - PHIs for DEFs & PHIS for USEs, so there are
at most 2 PHIs.


Does this idea seem to make sense? Any thoughts?

Best Regards,
Juneyoung Lee

-- 

Juneyoung Lee
Software Foundation Lab, Seoul National University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20181002/e330a088/attachment.html>