411183 - TASK: simple load elimination

Status: VERIFIED WONTFIX

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), enhancement, P4)

Description

[Edwin Smith]

if a value is loaded twice from the same pointer with no intermediate stores, it can be reused.  ordinarily this is complicated, however since a trace inlines all the intermediate code it should be much easier.

e.g. (from boids): 
dist = sqrt(vec.x * vec.x + vec.y * vec.y)

note: TC will do this for trivial situations, TT can be more aggressive.

Comment 1

[Edwin Smith]

This can piggyback on the single forward scan we use for CSE.  maintain a set of available loads.  when we get to a call with side effects, clear the set.  when we see a store, clear any loads that could be modified by the store.  even a simple rule that clears the set aggressively can potentially uncover many redundant loads.

Comment 2

[Edwin Smith]

similar situation, by maintaining info about available stores:

store a, [p+off]
b = load [p+off]  => b = a

Comment 3

[Andreas Gal :gal]

Seeing through store-load chains and connecting the load directly with the definition is quite helpful. It essentially eliminates most of the cost associated with temporary objects. 

function f() {
    Point p = new()
    p.x = 1
    p.y = 2
}

Point q = f();
s = q.x * q.y

If you connect the load to the definition, even if you don't eliminate the new it will execute mostly in parallel and not cost all that much since s will be constant 3 and the rest of the dependent code is not waiting for q.x and q.y to be loaded.

We do this in the CSE filter in hotpath. We have a bit more information available about allocations though since Java is concurrent and q.x and q.y could get modified asynchronously. For tracemonkey I this won't be an issue I think since it uses some funky object ownership locking model so nobody can have a handle to p.

Last but not least, we need to improve our call code wrt to register saving (separate bug) and memory side effects (relevant this bug). The latter we might do via annotation. Just add a field to builtins.tbl.

Comment 4

[Edwin Smith]

I have a very simple (forward) LoadFilter that assumes all pointers are aliased except for sp and rp, worth posting pushing or should we work on a smarter impl?

this loadfilter doesn't see thru store-load chains, it just finds redundant loads when there are no intervening aliasing stores.  maybe, 30 lines of code.

Comment 5

[Andreas Gal :gal]

Push first, improve later :)

Comment 6

[Andreas Gal :gal]

Speculating on aliasing is pretty cheap.

if recording and p and q do not alias
    guard p != q
    do optimization
fi

If you bail out there, let the interpreter handle the 1-off case where they do alias and re-enter at the loop header.

Comment 7

[Edwin Smith]

Attachment: simple load elimination (remove 2nd load if nothing could have modified the first one)

This patch eliminates a second load from the same base pointer and offset if the first result could not have changed (no intervening stores or calls with side effects).

at the moment it only assumes rp and sp are not aliased.

Comment 8

[Nicholas Nethercote [inactive]]

Is this bug relevant any more?  Seems like the (already implemented) CSEing of loads by using alias info is better than what this bug was proposing.

Comment 9

[Edwin Smith]

that was a TT patch, agree that alias annotations are more general.

Comment 10

[Trevor Baker]

bulk verifying resolved !fixed issues