Hi,
As many of you know I am currently digging towards implementing escape
analysis into IonMonkey. During our last meetup, I clearly highlighted that
recover instructions are prerequisite for any form of optimizations based on
escape analysis.
After the meetup, as requested by Jan, I made a simple prototype of Scalar
Replacement. This implementation of Scalar Replacement does not benefit
from any other optimizations as it is ran first, to avoid messing up with
the depend instructions added by our Alias Analysis.
The current implementation is separated in 2 things. The first part is
dealing with a "dummy" and conservative implementation of escape analysis.
The second part is dealing with the replacement of all properties of the
object by scalars. This implementation is available under
--ion-scalar-replacement=on command line interface.
I want to ask other JIT developers about taking another approach for
implementing Scalar Replacement. This other approach is is the easiest.
Also, it is different form the Sink-Store approach I experimented back in
December. What I want to propose is a DCE for effectful instructions.
In both the Sink-Store and the Effectful-DCE approaches, we need to
precisely keep tracks of memory operands and uses. This means that a Load
instruction which currently have operands to identify the object and the
property/index which are manipulated, would also have memory operands which
would correspond to the last store instruction which might alias the same
memory.
Currently our alias analysis only keep track of one unique operand, which is
fine for aliasing loads in GVN, but to make such information useful for the
Sink-Store and Effectful-DCE we also need to keep tracks of the Uses. The
idea being that a Store should be able to iterate over all its uses.
The Sink-Store approach was a hairy implementation of a graph walker which
was iterating the MIR Instructions within the graph and substitute every
memory uses of them while including the stores in the resume points. This
proved to be quite complex to handle and to understand.
The Effectful-DCE implies that the alias sets are registered in the resume
points by the alias analysis. If we do so, then deciding if we can remove a
store or not is done *exactly the same way* as our DCE algorithm handle
instructions which are only hold by resume points, by marking them as
recovered on bailout.
Both the Sink-Store and the Effectful-DCE are capable of removing double stores:
o.a = 1;
… some code which does not alias o.a …
o.a = 2;
The current Scalar Replacement implementation is only allowed to do that on
non-escaped objects. We could modify the current algorithm to also do the
same thing on any object, but this would imply that the algorithm would have
to be transformed in a 2-phase algorithm (to properly handle loops), the
first one emulating the object, and the second one removing actual object
manipulation. Doing so would increase the complexity of the Scalar
Replacement algorithm.
Note that most of the work needed for implementing Effectful-DCE would be
done as part of making a precise Alias Analysis, the only remaining piece
would be to register its state while visiting the resume points.
Sink-Store and Effectful-DCE are also both (indirectly) capable of removing
non-escaped objects allocations, by instrumenting our Alias Analysis to
prevent aliasing of non-escaped objects with Store(Any) alias sets. A
non-escaped object consist of unused stores, once all the load are folded
with the stores. Then, this is just a matter of using DCE to recover the
allocation on bailouts.
To make it simple, this is a trade off between memory vs. clarity &
efficiency. If we do not want to instrument resume points with the alias
sets, then this means that we would have to follow any location a store
content can flow into, which is exactly what the Memory Uses would prevent
us from doing. The idea would be to add an extra list of operands and uses
for instructions which have a non-empty alias set.
So the question that I want to ask is, do you think this is an acceptable
trade-off? Should we go for the Effectful-DCE implementation, or should we
keep incrementing our Scalar Replacement code to handle more code paths?
--
Nicolas B. Pierron
_______________________________________________
dev-tech-js-engine-internals mailing list
[email protected]
https://lists.mozilla.org/listinfo/dev-tech-js-engine-internals
