Liveness analysis for environment slots in Hydrogen

Liveness analysis for environment slots in Hydrogen

R=titzer@chromium.org

Committed: http://code.google.com/p/v8/source/detail?r=14938

[Jakob Kummerow, 2013-05-23 08:11:00]

Ben: please take a look.

Danno: just FYI if you're interested.

[titzer, 2013-05-23 12:34:54]

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode823
src/hydrogen.cc:823: // branch. However, we must pretend that the "then" branch
is reachable.
Why must we pretend that it's reachable?

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode2539
src/hydrogen.cc:2539: while (pass != kDone) {
I realize there are some tricky cases inside this loop, but this enum / pass
flag that completely changes the loop behavior is way too complication. Please
extract this to two or three loops and loop-unswitch this code.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode2541
src/hydrogen.cc:2541: if (pass == kIterateUntilFixedPoint &&
!worklist->Contains(block_id)) {
Your loop goes through the block order backwards. No problem. Any order would
work. Luckily the block order has been computed carefully in the previous phases
to match reverse-post order, thus making this loop efficient. Nevertheless your
main loop loops over all the blocks each time. The first time it will visit each
block, but then subsequent iterations (because of loops) will be sparse. 

I am not sure if now is the right time for a helper iterator, but we do seem to
be iterating manually in various order all over the place in the code. If we
have other backwards dataflow problems, we might consider either repurposing or
generalizing the PostorderProcessor to help here.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode2568
src/hydrogen.cc:2568: // a simulate before an EnterInlined.
Scary and brittle, and no ASSERT.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode2613
src/hydrogen.cc:2613: } else if (instr->IsEnterInlined()) {
There is considerably more going on here than meets the eye; you are doing
liveness analysis on different environments for different inlined methods. This
currently works because you are only using the environment bind and environment
lookup as essentially reads and writes and thankfully before any other
optimizations happen, code from different inlined methods is not mixed up into
the same basic blocks. I am not sure if this would hold if the order of this
phase were changed. Also, below you are making assumptions about what order
instructions will appear in inlined methods. This makes this phase brittle and
restricts changes in other phases. Please consider ways to relax these
restrictions, or do something conservative when they do not hold.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode5051
src/hydrogen.cc:5051: EnvironmentLivenessAnalysis();
This phase should be guarded by a flag, and should be named verbly (as other
phases) to reflect that it makes modifications to the graph.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.h#newcode158
src/hydrogen.h:158: void MarkAsInlineReturnTarget(HBasicBlock*
enter_inlined_block) {
This name is somewhat difficult to parse. Is this the first block of the inlined
method? If so, inlined_entry_block might be a better name.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.h#newcode372
src/hydrogen.h:372: void update_biggest_environment_ever(int environment_size) {
Cute name, but "maximum_environment_size" would also work.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.h#newcode426
src/hydrogen.h:426: void ZapEnvironmentSlot(int index, HSimulate* simulate);
Maybe "Kill" or "Null" or "Remove"?

[Jakob Kummerow, 2013-05-24 09:49:34]

Addressed those comments that only required minor changes; more refactorings
will come.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode823
src/hydrogen.cc:823: // branch. However, we must pretend that the "then" branch
is reachable.
On 2013/05/23 12:34:55, titzer wrote:
> Why must we pretend that it's reachable?

So that the graph builder visits it and any environment lookups inside it. I've
updated the comment.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode2541
src/hydrogen.cc:2541: if (pass == kIterateUntilFixedPoint &&
!worklist->Contains(block_id)) {
On 2013/05/23 12:34:55, titzer wrote:
> Your loop goes through the block order backwards. No problem. Any order would
> work. Luckily the block order has been computed carefully in the previous
phases
> to match reverse-post order, thus making this loop efficient. Nevertheless
your
> main loop loops over all the blocks each time. The first time it will visit
each
> block, but then subsequent iterations (because of loops) will be sparse. 
> 
> I am not sure if now is the right time for a helper iterator, but we do seem
to
> be iterating manually in various order all over the place in the code. If we
> have other backwards dataflow problems, we might consider either repurposing
or
> generalizing the PostorderProcessor to help here.

I'm explicitly going backwards in order to reduce the number of needed
iterations.
I'd prefer not to add any unrelated refactorings to this CL (and, frankly, I'm
not convinced we need a generic helper iterator. Ordering blocks once should be
quite sufficient.)

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode2568
src/hydrogen.cc:2568: // a simulate before an EnterInlined.
On 2013/05/23 12:34:55, titzer wrote:
> Scary and brittle, and no ASSERT.

ASSERT added.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.cc#newcode5051
src/hydrogen.cc:5051: EnvironmentLivenessAnalysis();
On 2013/05/23 12:34:55, titzer wrote:
> This phase should be guarded by a flag, and should be named verbly (as other
> phases) to reflect that it makes modifications to the graph.

Done.
Side note: "DeadCodeElimination" isn't a verb either ;-)

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.h
File src/hydrogen.h (right):

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.h#newcode158
src/hydrogen.h:158: void MarkAsInlineReturnTarget(HBasicBlock*
enter_inlined_block) {
On 2013/05/23 12:34:55, titzer wrote:
> This name is somewhat difficult to parse. Is this the first block of the
inlined
> method? If so, inlined_entry_block might be a better name.

Done. (It's the block containing the HEnterInlined. We don't start a new block
when inlining.)

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.h#newcode372
src/hydrogen.h:372: void update_biggest_environment_ever(int environment_size) {
On 2013/05/23 12:34:55, titzer wrote:
> Cute name, but "maximum_environment_size" would also work.

Done.

https://codereview.chromium.org/15533004/diff/1008/src/hydrogen.h#newcode426
src/hydrogen.h:426: void ZapEnvironmentSlot(int index, HSimulate* simulate);
On 2013/05/23 12:34:55, titzer wrote:
> Maybe "Kill" or "Null" or "Remove"?

We use "zap" in other places, so I'd like to keep the name.

[Jakob Kummerow, 2013-05-24 15:31:09]

Made more changes (see patch set descriptions). I believe I have addressed all
of your comments now. Please take another look.

[titzer, 2013-05-27 11:35:27]

https://codereview.chromium.org/15533004/diff/17012/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/15533004/diff/17012/src/hydrogen.cc#newcode2509
src/hydrogen.cc:2509: HSimulate* HGraph::ZapEnvironmentSlotInNextSimulate(int
index,
In this function, we have to walk forward in the graph to find the next simulate
in order to zap a dead environment slot. This could go quadratic for N dead
instructions with a simulate at the end of the block. But recall, we've done a
backwards walk in the iterative phase. You could, for example, keep track of the
last simulate seen in the backward walk and store a pointer to it explicitly in
the HEnvironment{Bind,Lookup}. Then you can kill it in O(1).

https://codereview.chromium.org/15533004/diff/17012/src/hydrogen.cc#newcode2712
src/hydrogen.cc:2712: // Analysis finished. Zap dead environment slots.
I don't think we need the last pass over the blocks. We have the correct live_in
information for every block in the graph.

I think it would be more clear (and also more efficient) to have a liveness
field for each HEnvironment{Bind,Lookup} instruction in the graph. Set the
liveness during the iterative phase (since when an HEnvironment{Bind,Lookup}
becomes live, it never becomes dead again).

Collect all HEnvironment{Bind,Lookup} instructions into a list which you can
inspect at the end. In the last pass, do the ZapEnvironmentSlot() for the dead
ones, then remove all of them from the graph. You can use the live_in vectors
for the blocks directly in UpdateLivenessAtBlockEnd, which kills values
selectively in successors. This saves two whole passes over the hydrogen graph.

[Jakob Kummerow, 2013-05-29 15:41:49]

PTAL.

[titzer, 2013-05-29 16:58:05]

Almost there, just mostly documentation.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
File src/hydrogen-environment-liveness.cc (right):

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:84: HBasicBlock* block) {
E.g. here, it would be more clear to pass in the temporary live_ bitvector, so
that it's clear the caller expects the method to modify it.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:114: if (collect_markers_) {
This is a little tricky; maybe a comment that we only collect markers the first
time through the graph.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:149: case HValue::kDeoptimize: {
What about kSoftDeoptimize?

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:168: // Values in the environment are kept
alive by every subsequent LInstruction
Some reordering of the sentences might make this paragraph clearer. E.g. first
sentence should probably be something to the effect of "Trim live ranges of
environment slots by doing explicit liveness analysis". And then why this is
necessary (stuff is live too long because of environments, and then maybe any
relevant details.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:205: // Reached the start of the block, do
necessary bookkeeping.
Explain bookkeeping steps. E.g. "propagate liveness to predecessors" would do.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
File src/hydrogen-environment-liveness.h (right):

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.h:37: 
Documentation. At least a sentence. Perhaps EnvironmentSlotLivenessAnalyzer
instead of *Analysis?

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.h:40: explicit
EnvironmentSlotLivenessAnalysis(HGraph* graph)
Please put this constructor in the .cc file, if C++ will allow you.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.h:83: ZoneScope zone_scope_;
Would like to see some comments on these fields, e.g. that the various lists are
indexed by blockid.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.h:92: BitVector* live_;
I think it's best to turn this field into a local and pass it between the
various methods; following the effects in the Update* methods will be easier.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen.cc#newcode829
src/hydrogen.cc:829: // constructs within it.
I'm still perplexed why we need to insert a dead branch.

https://codereview.chromium.org/15533004/diff/29001/test/mjsunit/debug-evalua...
File test/mjsunit/debug-evaluate-locals-optimized-double.js (right):

https://codereview.chromium.org/15533004/diff/29001/test/mjsunit/debug-evalua...
test/mjsunit/debug-evaluate-locals-optimized-double.js:187: debugger;  //
Breakpoint.
Not sure why we are changing these tests. Does something break with debugging?

[Jakob Kummerow, 2013-06-03 17:50:38]

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
File src/hydrogen-environment-liveness.cc (right):

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:84: HBasicBlock* block) {
On 2013/05/29 16:58:05, titzer wrote:
> E.g. here, it would be more clear to pass in the temporary live_ bitvector, so
> that it's clear the caller expects the method to modify it.

Done.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:114: if (collect_markers_) {
On 2013/05/29 16:58:05, titzer wrote:
> This is a little tricky; maybe a comment that we only collect markers the
first
> time through the graph.

Done.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:149: case HValue::kDeoptimize: {
On 2013/05/29 16:58:05, titzer wrote:
> What about kSoftDeoptimize?

Usage is different.
HSoftDeoptimize instructions do not affect live ranges in any way, so they don't
need any special handling here.
There are uses of HDeoptimize however that assume that the entire environment is
available. I'm hoping that this will change eventually, but that's a different
issue.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:168: // Values in the environment are kept
alive by every subsequent LInstruction
On 2013/05/29 16:58:05, titzer wrote:
> Some reordering of the sentences might make this paragraph clearer. E.g. first
> sentence should probably be something to the effect of "Trim live ranges of
> environment slots by doing explicit liveness analysis". And then why this is
> necessary (stuff is live too long because of environments, and then maybe any
> relevant details.

Done, and moved to the class, where this comment really makes more sense now.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.cc:205: // Reached the start of the block, do
necessary bookkeeping.
On 2013/05/29 16:58:05, titzer wrote:
> Explain bookkeeping steps. E.g. "propagate liveness to predecessors" would do.

Done.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
File src/hydrogen-environment-liveness.h (right):

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.h:37: 
On 2013/05/29 16:58:05, titzer wrote:
> Documentation. At least a sentence. Perhaps EnvironmentSlotLivenessAnalyzer
> instead of *Analysis?

Done.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.h:40: explicit
EnvironmentSlotLivenessAnalysis(HGraph* graph)
On 2013/05/29 16:58:05, titzer wrote:
> Please put this constructor in the .cc file, if C++ will allow you.

Done. Good point, dunno why it didn't occur to me before.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.h:83: ZoneScope zone_scope_;
On 2013/05/29 16:58:05, titzer wrote:
> Would like to see some comments on these fields, e.g. that the various lists
are
> indexed by blockid.

Done.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
src/hydrogen-environment-liveness.h:92: BitVector* live_;
On 2013/05/29 16:58:05, titzer wrote:
> I think it's best to turn this field into a local and pass it between the
> various methods; following the effects in the Update* methods will be easier.

Done.

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen.cc
File src/hydrogen.cc (right):

https://codereview.chromium.org/15533004/diff/29001/src/hydrogen.cc#newcode829
src/hydrogen.cc:829: // constructs within it.
On 2013/05/29 16:58:05, titzer wrote:
> I'm still perplexed why we need to insert a dead branch.

I'm not sure what information is missing from the comment. Previously, the graph
builder would skip over unreachable branches, where unreachability may be based
solely on type feedback and guarded by corresponding checks. If there's an
environment lookup happening in that branch that keeps a value alive, not
visiting it means not noticing the lookup, not keeping the value alive, and
materializing "undefined" instead of the proper value when we deopt due to the
branch becoming reachable after all. So we must make sure that all live ranges
can be determined accurately from the graph. (We have test coverage for this.)

https://codereview.chromium.org/15533004/diff/29001/test/mjsunit/debug-evalua...
File test/mjsunit/debug-evaluate-locals-optimized-double.js (right):

https://codereview.chromium.org/15533004/diff/29001/test/mjsunit/debug-evalua...
test/mjsunit/debug-evaluate-locals-optimized-double.js:187: debugger;  //
Breakpoint.
On 2013/05/29 16:58:05, titzer wrote:
> Not sure why we are changing these tests. Does something break with debugging?

We need to extend the live ranges of the values that are being inspected beyond
the point where they are inspected. The "debugger;" statement triggers the big
"listener()" function above (lines 65ff.), which has expectations for the local
variables in every stack frame.

This does mean that users inspecting stack frames where local values have been
zapped at the end of their live range will see "undefined" unexpectedly.
Unfortunately, there's nothing we can do to prevent that, because there's no way
to predict if/when a stack frame will be inspected.

[titzer, 2013-06-04 16:20:17]

On 2013/06/03 17:50:38, Jakob wrote:
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> File src/hydrogen-environment-liveness.cc (right):
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.cc:84: HBasicBlock* block) {
> On 2013/05/29 16:58:05, titzer wrote:
> > E.g. here, it would be more clear to pass in the temporary live_ bitvector,
so
> > that it's clear the caller expects the method to modify it.
> 
> Done.
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.cc:114: if (collect_markers_) {
> On 2013/05/29 16:58:05, titzer wrote:
> > This is a little tricky; maybe a comment that we only collect markers the
> first
> > time through the graph.
> 
> Done.
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.cc:149: case HValue::kDeoptimize: {
> On 2013/05/29 16:58:05, titzer wrote:
> > What about kSoftDeoptimize?
> 
> Usage is different.
> HSoftDeoptimize instructions do not affect live ranges in any way, so they
don't
> need any special handling here.
> There are uses of HDeoptimize however that assume that the entire environment
is
> available. I'm hoping that this will change eventually, but that's a different
> issue.
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.cc:168: // Values in the environment are
kept
> alive by every subsequent LInstruction
> On 2013/05/29 16:58:05, titzer wrote:
> > Some reordering of the sentences might make this paragraph clearer. E.g.
first
> > sentence should probably be something to the effect of "Trim live ranges of
> > environment slots by doing explicit liveness analysis". And then why this is
> > necessary (stuff is live too long because of environments, and then maybe
any
> > relevant details.
> 
> Done, and moved to the class, where this comment really makes more sense now.
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.cc:205: // Reached the start of the block,
do
> necessary bookkeeping.
> On 2013/05/29 16:58:05, titzer wrote:
> > Explain bookkeeping steps. E.g. "propagate liveness to predecessors" would
do.
> 
> Done.
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> File src/hydrogen-environment-liveness.h (right):
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.h:37: 
> On 2013/05/29 16:58:05, titzer wrote:
> > Documentation. At least a sentence. Perhaps EnvironmentSlotLivenessAnalyzer
> > instead of *Analysis?
> 
> Done.
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.h:40: explicit
> EnvironmentSlotLivenessAnalysis(HGraph* graph)
> On 2013/05/29 16:58:05, titzer wrote:
> > Please put this constructor in the .cc file, if C++ will allow you.
> 
> Done. Good point, dunno why it didn't occur to me before.
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.h:83: ZoneScope zone_scope_;
> On 2013/05/29 16:58:05, titzer wrote:
> > Would like to see some comments on these fields, e.g. that the various lists
> are
> > indexed by blockid.
> 
> Done.
> 
>
https://codereview.chromium.org/15533004/diff/29001/src/hydrogen-environment-...
> src/hydrogen-environment-liveness.h:92: BitVector* live_;
> On 2013/05/29 16:58:05, titzer wrote:
> > I think it's best to turn this field into a local and pass it between the
> > various methods; following the effects in the Update* methods will be
easier.
> 
> Done.
> 
> https://codereview.chromium.org/15533004/diff/29001/src/hydrogen.cc
> File src/hydrogen.cc (right):
> 
> https://codereview.chromium.org/15533004/diff/29001/src/hydrogen.cc#newcode829
> src/hydrogen.cc:829: // constructs within it.
> On 2013/05/29 16:58:05, titzer wrote:
> > I'm still perplexed why we need to insert a dead branch.
> 
> I'm not sure what information is missing from the comment. Previously, the
graph
> builder would skip over unreachable branches, where unreachability may be
based
> solely on type feedback and guarded by corresponding checks. If there's an
> environment lookup happening in that branch that keeps a value alive, not
> visiting it means not noticing the lookup, not keeping the value alive, and
> materializing "undefined" instead of the proper value when we deopt due to the
> branch becoming reachable after all. So we must make sure that all live ranges
> can be determined accurately from the graph. (We have test coverage for this.)
> 
>
https://codereview.chromium.org/15533004/diff/29001/test/mjsunit/debug-evalua...
> File test/mjsunit/debug-evaluate-locals-optimized-double.js (right):
> 
>
https://codereview.chromium.org/15533004/diff/29001/test/mjsunit/debug-evalua...
> test/mjsunit/debug-evaluate-locals-optimized-double.js:187: debugger;  //
> Breakpoint.
> On 2013/05/29 16:58:05, titzer wrote:
> > Not sure why we are changing these tests. Does something break with
debugging?
> 
> We need to extend the live ranges of the values that are being inspected
beyond
> the point where they are inspected. The "debugger;" statement triggers the big
> "listener()" function above (lines 65ff.), which has expectations for the
local
> variables in every stack frame.
> 
> This does mean that users inspecting stack frames where local values have been
> zapped at the end of their live range will see "undefined" unexpectedly.
> Unfortunately, there's nothing we can do to prevent that, because there's no
way
> to predict if/when a stack frame will be inspected.

LGTM. I am certain people are going to ask why their local variables aren't
available in the debugger after they die. Prepare to point them to your flag :)

[Jakob Kummerow, 2013-06-04 16:41:36]

Committed patchset #11 manually as r14938 (presubmit successful).