620676 - Refactor edge tracking

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect)

Description

[Edwin Smith]

Currently, VarTracker::trackForwardEdge is called from inside CodegenLIR::callIns(), for any nonpure function.  Also, edge & label tracking of vars is done within the if/then/else sequences of inlined 'diamond' shape code, even though we only care about the state of vars[] and tags[] at the beginning and end of these single-entry/single-exit regions.

The problem with tracking at this level of detail is
1. its expensive -- within these regions, we shouldn't be making interesting mutations to vars[] or tags[]
2. it impedes refactoring instruction emitters since it ties them to VarTracker and FrameState.

This bug is to track a sequence of small patches to remove these dependencies.  Actual refactoring of emitters is out of scope for this bug.

Testing:  The testing strategy is to run avmshell -Dverifyonly on Brightspot, to make sure there are absolutely no differences in generated LIR.

Comment 1

[Edwin Smith]

Attachment: v1 patch1: add LIR-only verbose listing mode.

This patch adds a -Dverbose=lir mode, which just prints the generated LIR (interleaved with Verifier state), and the final LIR that we give to the assembler.

It also modifies printNotNull() to not print anything for 'dead' parts of the stack frame, i.e:

  [locals][scope][dead][stack][dead]
                 ^^^^^^       ^^^^^^

Don't print the dead ones.

Comment 2

[Edwin Smith]

Attachment: v1 patch2: Don't track notnull state along exception edges

This patch treats notnull tracking the same as LIns* tracking  -- that is, do not propagate notnull information along exception edges.  At the starts of catch blocks we can just pick up whatever we had in the verifier.

Comment 3

[Edwin Smith]

Attachment: v1 patch3: Don't track exception edges in callIns()

This removes the exception-edge tracking from callIns(), replacing it with code to track var-state before each opcode is emitted.

Issue: does exception-edge tracking even do anything?  trackForwardEdge appears to nullify any tracking when isExceptionEdge=true, maybe we dont need to track these edges at all.

Comment 4

[Edwin Smith]

Attachment: Listing showing LIR diff if exception-edge-tracking is tweaked.

Here is a testcase that benefits from tracking not_null state along exception edges from calls.  If we don't track null state on exception edges at all (the first patch), or if we move the edge to the start of the opcode instead of the middle (second patch), we get one extra null check in a catch/finally block.

swfcontents/+/5/X/m/A/+5XmA7TjhBU+Tu1gCPVQP7QhOucNZ1oYLBhR7w62rcQ=

verify flash::Lib$/eval()

Comment 5

[Edwin Smith]

Comment on attachment 499021 [details] [diff] [review]
v1 patch3: Don't track exception edges in callIns()

This patch is probably wrong - if a catch block is reachable via normal control flow *and* exception flow, then we must merge with exception edges or else the state at the catch block is optimistic and wrong.

Comment 6

[William Maddox]

(In reply to comment #3)
> Created attachment 499021 [details] [diff] [review]
> v1 patch3: Don't track exception edges in callIns()

> Issue: does exception-edge tracking even do anything?  trackForwardEdge appears
> to nullify any tracking when isExceptionEdge=true, maybe we dont need to track
> these edges at all.

If by "nullifying" any tracking, you mean setting the vartracker state for all variables to null (as it is indeed doing), then yes, it is doing quite a bit.  Null is the bottom element for the dataflow lattice here.

Comment 7

[William Maddox]

Comment on attachment 499019 [details] [diff] [review]
v1 patch2: Don't track notnull state along exception edges

This seems plausible, though I presume the real value of this is as a step toward not tracking exception edges at all.  We still have to track the edges to null out the variable state, or just clear it at the handler entry.  We won't lose anything except in the anomalous case of a handler that is unreachable by any exceptions but is reachable via branch or fallthrough, so this is reasonable.

Comment 8

[William Maddox]

(In reply to comment #7)

There used to be code to detect, as each instruction was emitted, whether it was at the start of an exception handler.  This was used to insert code to coerce the exception object, which turned out to be broken in the case that we reached the handler through normal control flow, e.g., fallthrough or a branch.  With the new dispatch scheme that fixed that bug, it was no longer necessary to do anything special at the handler entry, as the dispatch boilerplate did all the work.  If we remove the exception edges, we'll have to restore this code or something like it.

Comment 9

[Edwin Smith]

> If we remove the exception edges, we'll have to restore this
> code or something like it.

I'm not sure I follow; actual exceptions would still work as before;
the real exception edges (from exception dispatch at the bottom, back
up to catch labels in the code) would still be generated.

The problem is the if block in CodegenLIR::callIns() that conditionally calls trackForwardEdge().

What I'm thinking about at this point, is not to remove exception edges, or even exception edge-tracking, but to move that if block somewhere else, because it is only a VarTracker concern; this would make it easier to reuse case analysis and LIR generation code downstream from VarTracker.

I'm exploring two possible ways to do it: (warning: inside baseball ahead)

1. add the tracking to VarTracker::insCall() (called indirectly by callIns()), so any possibly-throwing call will be seen, no matter how late its generated in case selection code.

2. explicitly track exception edges in each CodeWriter writeXXX() callback, before LIR is generated for the instruction.

In the cases when we model an edge in both #1 and #2, I suspect (and must prove) that the local variable state will be the same as in #1, since we update state with localSet() calls, *after* various LIR_calls are generated.

But, there could be cases when #2 would model an edge (generically based on the abc opcode) but #1 would not model an edge (because no possibly-throwing call got generated).  Changing edge tracking could pessimise the generated code in the catch handler.  We dont care about that, but its subtle enough that we need to prove to ourselves that pessimism will always be safe, ie no more pessimistic than what the verifier computed all on its own in phase 1.

the third combination, #1 modeling an edge that #2 doesn't, would be a bug -- it would mean we're calling a helper that could throw, from within the code for an opcode that must not throw.  (hmm, how to assert on this...)

Comment 10

[Edwin Smith]

Comment on attachment 499018 [details] [diff] [review]
v1 patch1: add LIR-only verbose listing mode.

Promoted to bug 	638136