Bug 180852 – The CleanUp after LICM is erroneously removing a Check

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Mark Lam]

Created attachment 329425 [details]
Repro test case.

This results in a subsequent node expecting a checked String object, but instead, got a non-String cell, which leads to a crash.

I ran the test as follows:
$ JSC_useConcurrentJIT=0 jsc repro1.js

[Radar WebKit Bug Importer]

<rdar://problem/36063494>

[Saam Barati]

The bug is we're running part of AI inside LICM. This part of AI will change the proof status of a node. The bug here is:

We have two loops, L1 and L2, and two preheaders, P1 and P2. L2 is nested inside of L1. We have a Check inside a node inside L1, say in block BB, and that Check dominates all of L2. This is also a hoisting candidate, so we hoist it outside of L1 and put it inside P1. Then, when we run AI, we look at the preheader for each loop inside L1, so P1 and P2. When considering P2, we execute the Check. Inside P2, before any hoisting is done, this Check is dead code, because BB dominates P2. When we use AI to "execute" the Check, it'll set its proof status to proved. This is because inside P2, in the program before LICM runs, the Check is indeed proven at P2. But it is not proven inside P1. This "execute" call will set our proof status for the node inside *P1*, hence, we crash.

I see two easy solutions:
1. Remove the CleanUp phase after LICM
2. Run CFA before the CleanUP phase after LICM

I vote for (1) since CFA is expensive to run.

[Saam Barati]

Yet another alternative solution:
Clear isProved() for the children of all nodes we hoist.

[Filip Pizlo]

(In reply to Saam Barati from comment #2)
> The bug is we're running part of AI inside LICM. 

How is that a bug?  It should generate a valid proof. 

> This part of AI will change
> the proof status of a node. The bug here is:
> 
> We have two loops, L1 and L2, and two preheaders, P1 and P2. L2 is nested
> inside of L1. We have a Check inside a node inside L1, say in block BB, and
> that Check dominates all of L2. This is also a hoisting candidate, so we
> hoist it outside of L1 and put it inside P1. Then, when we run AI, we look
> at the preheader for each loop inside L1, so P1 and P2. When considering P2,
> we execute the Check. Inside P2, before any hoisting is done, this Check is
> dead code, because BB dominates P2. When we use AI to "execute" the Check,
> it'll set its proof status to proved. This is because inside P2, in the
> program before LICM runs, the Check is indeed proven at P2. But it is not
> proven inside P1. This "execute" call will set our proof status for the node
> inside *P1*, hence, we crash.
> 
> I see two easy solutions:
> 1. Remove the CleanUp phase after LICM
> 2. Run CFA before the CleanUP phase after LICM
> 
> I vote for (1) since CFA is expensive to run.

Clean up is pretty useful. How about 3: make licm’s use of AI leave behind valid AI state.

[Filip Pizlo]

Seems like we need a way of executing a node without changing its proved bits. That execution in LICM is to update another block’s state summary so it shouldn’t be changing proved bots. 

Maybe you can hook that into the existing AtTail versus InPlace template magic.

[Saam Barati]

(In reply to Saam Barati from comment #3)
> Yet another alternative solution:
> Clear isProved() for the children of all nodes we hoist.

I like this option the most. It also seems like Fil predicted it a few years ago:
https://bugs.webkit.org/show_bug.cgi?id=148544

I think it's ok to be conservative and just say anything we hoist no longer has valid proofs for its children. Also, it's important to note that the act of hoisting a node will never change the proof status from IsProved to NeedsCheck for anything inside the loop. It could make it go from NeedsCheck to IsProved though, but that's purely profit that we don't gain until we run AI again.

[Saam Barati]

(In reply to Filip Pizlo from comment #5)
> Seems like we need a way of executing a node without changing its proved
> bits. That execution in LICM is to update another block’s state summary so
> it shouldn’t be changing proved bots. 
> 
> Maybe you can hook that into the existing AtTail versus InPlace template
> magic.

Right. Let's say I make this change to not update proved bits for AtTail. What worries me is this:
What if hoisting the node changes its proved bits?

I'm not sure if this is possible, but it seems like it'd be better to be conservative and say things aren't proved once hoisted.

[Saam Barati]

(In reply to Saam Barati from comment #7)
> (In reply to Filip Pizlo from comment #5)
> > Seems like we need a way of executing a node without changing its proved
> > bits. That execution in LICM is to update another block’s state summary so
> > it shouldn’t be changing proved bots. 
> > 
> > Maybe you can hook that into the existing AtTail versus InPlace template
> > magic.
> 
> Right. Let's say I make this change to not update proved bits for AtTail.
> What worries me is this:
> What if hoisting the node changes its proved bits?
> 
> I'm not sure if this is possible, but it seems like it'd be better to be
> conservative and say things aren't proved once hoisted.

I actually think this is necessary. The fact that we update the Proved bits probably helps us in a bunch of scenarios where we have something like this:

```
bb#1:
a: Foo: produces Heap TOP
jump #2
bb#2
b: CantBeHoisted(Check:Cell:@a)
c: CanBeHoisted(Cell:@a)
some stuff to make a loop
```

if we hoist without updating the proved bits, we're going to be sad

[Saam Barati]

I still like the idea of making this method as part of AbstractState though so it's a nop for LICM

[Filip Pizlo]

(In reply to Saam Barati from comment #9)
> I still like the idea of making this method as part of AbstractState though
> so it's a nop for LICM

I’m fine with your solution, but it seems like there are two different execution modes in LICM at-tail:

- execute to update state of nested headers

- execute to establish the right state at the tail of the header we hoisted to. 

So, you could be precise if you wanted to be.

[Saam Barati]

Created attachment 329435 [details]
patch

[Filip Pizlo]

Comment on attachment 329435 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=329435&action=review

I think this could be simpler.

> Source/JavaScriptCore/dfg/DFGAtTailAbstractState.h:67
> +    void setProofStatus(Edge&, ProofStatus) { }

What if this set it to NeedsCheck?  Then you don’t need more data structures.

> Source/JavaScriptCore/dfg/DFGLICMPhase.cpp:313
> +        m_hoistedNodes.add(node);

I don’t think you need this.

> Source/JavaScriptCore/dfg/DFGLICMPhase.cpp:354
> +    HashSet<Node*> m_hoistedNodes;

And if you did need it, it should probably be a vector. Optimizing away duplicates isn’t going to help you.

[Saam Barati]

(In reply to Filip Pizlo from comment #10)
> (In reply to Saam Barati from comment #9)
> > I still like the idea of making this method as part of AbstractState though
> > so it's a nop for LICM
> 
> I’m fine with your solution, but it seems like there are two different
> execution modes in LICM at-tail:
> 
> - execute to update state of nested headers
> 
> - execute to establish the right state at the tail of the header we hoisted
> to. 
> 
> So, you could be precise if you wanted to be.

I see. Yeah this makes sense. We could do it with a bit inside AtTail. The patch I uploaded is conservative and never does it, and says anything we hoist can't have proven children. I like the idea of being precise. I'll make a new patch

[Saam Barati]

*** Bug 148544 has been marked as a duplicate of this bug. ***

[Saam Barati]

Created attachment 329442 [details]
patch

[Filip Pizlo]

Comment on attachment 329442 [details]
patch

Nice!

[Saam Barati]

Comment on attachment 329442 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=329442&action=review

> Source/JavaScriptCore/ChangeLog:25
> +        The fix I'm going with is to conservatively say the proof status for the
> +        children of all nodes we hoist is NeedsCheck.

This no longer reflects what I'm actually doing. I'll update it to be accurate.

[Saam Barati]

Created attachment 329445 [details]
patch for landing

[Saam Barati]

Created attachment 329446 [details]
patch for landing

Fix typo

[WebKit Commit Bot]

Comment on attachment 329446 [details]
patch for landing

Clearing flags on attachment: 329446

Committed r225966: <https://trac.webkit.org/changeset/225966>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.