Bug 216214 – DFG ASSERTION FAILED: Value not defined in FTLLowerDFGToB3.cpp

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

Created attachment 408082 [details]
the minimal poc

the following poc cause a DFG ASSERTION FAILED in ../../Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp(17338) : JSC::FTL::LValue JSC::FTL::(anonymous namespace)::LowerDFGToB3::lowJSValue(JSC::DFG::Edge, JSC::DFG::OperandSpeculationMode)


function main() {
        const v1 = {};
        v1.p = {a: 42};

        const v3 = [1];
        v3.toString = [];
        if (!v3) {
            	v4 = {
        		get v4(){
            			[...{v4 = 1.45}] = [];
            			v4.v4;
        		}
    		}
        }

        for (const v5 of "asdf") {
            v1.b = 43;
        }

        const v4 = v1.p;

        let = String.fromCharCode("");
        for (let i = 0; i < 2; i++) {
            r = v4;
        }

}

for (let v0 = 0; v0 < 100000; v0++) {
        main();
}

[Alexey Proskuryakov]

I can reproduce, but get a different assertion:

ASSERTION FAILED: !edge->isPhantomAllocation()
./dfg/DFGValidate.cpp(946) : auto JSC::DFG::(anonymous namespace)::Validate::validateSSA()::(anonymous class)::operator()(const JSC::DFG::Edge &) const
1   0x111e8ef79 WTFCrash
2   0x112f537f1 JSC::DFG::(anonymous namespace)::Validate::validateSSA()::'lambda'(JSC::DFG::Edge const&)::operator()(JSC::DFG::Edge const&) const
3   0x112f53724 void JSC::DFG::Graph::doToChildren<JSC::DFG::(anonymous namespace)::Validate::validateSSA()::'lambda'(JSC::DFG::Edge const&)>(JSC::DFG::Node*, JSC::DFG::(anonymous namespace)::Validate::validateSSA()::'lambda'(JSC::DFG::Edge const&) const&)::ForwardingFunc::operator()(JSC::DFG::Node*, JSC::DFG::Edge&) const
4   0x112f536af void JSC::DFG::Graph::doToChildrenWithNode<void JSC::DFG::Graph::doToChildren<JSC::DFG::(anonymous namespace)::Validate::validateSSA()::'lambda'(JSC::DFG::Edge const&)>(JSC::DFG::Node*, JSC::DFG::(anonymous namespace)::Validate::validateSSA()::'lambda'(JSC::DFG::Edge const&) const&)::ForwardingFunc>(JSC::DFG::Node*, JSC::DFG::(anonymous namespace)::Validate::validateSSA()::'lambda'(JSC::DFG::Edge const&) const&)
5   0x112f53518 void JSC::DFG::Graph::doToChildren<JSC::DFG::(anonymous namespace)::Validate::validateSSA()::'lambda'(JSC::DFG::Edge const&)>(JSC::DFG::Node*, JSC::DFG::(anonymous namespace)::Validate::validateSSA()::'lambda'(JSC::DFG::Edge const&) const&)
6   0x112f50bff JSC::DFG::(anonymous namespace)::Validate::validateSSA()
7   0x112f4a4b7 JSC::DFG::(anonymous namespace)::Validate::validate()
8   0x112f4655f JSC::DFG::validate(JSC::DFG::Graph&, JSC::DFG::GraphDumpMode, WTF::CString)
9   0x112ed0173 JSC::DFG::(anonymous namespace)::dumpAndVerifyGraph(JSC::DFG::Graph&, char const*, bool)
10  0x112ecf6ae JSC::DFG::Plan::compileInThreadImpl()
11  0x112eca818 JSC::DFG::Plan::compileInThread(JSC::DFG::ThreadData*)
12  0x112f86b9e JSC::DFG::Worklist::ThreadBody::work()
13  0x111ea4c93 WTF::AutomaticThread::start(WTF::AbstractLocker const&)::$_0::operator()() const
14  0x111ea487e WTF::Detail::CallableWrapper<WTF::AutomaticThread::start(WTF::AbstractLocker const&)::$_0, void>::call()
15  0x111eb6ac2 WTF::Function<void ()>::operator()() const
16  0x111f64f28 WTF::Thread::entryPoint(WTF::Thread::NewThreadContext*)
17  0x111f70e88 WTF::wtfThreadEntryPoint(void*)
18  0x7fff6a51a109 _pthread_start
19  0x7fff6a515b8b thread_start

[Radar WebKit Bug Importer]

<rdar://problem/68518460>

[Saam Barati]

BTW, these are likely the same crash, but just debug vs release build failures.

I know Tadeu is actively diving into this. It's an allocation sinking bug.

[Tadeu Zagallo]

I think I understand the issue now, but still trying to determine what's the right fix here. Consider the following program:

bb0:
    a: NewObject
    b: CreateActivation()
    _: Branch(bb2, bb1)
bb1:
    _: PutByOffset(a, 'x', 42) 
    _: PutStrucute(a, {x: 0})
bb2:
    _: CheckStructure(a, {x: 0})
    _: PutClosureVar(b, 0, Kill:a)
    _: Branch(bb3, bb2)
bb3:
    c: GetClosureVar(b, 0)
    _: PutByOffset(global, 'y', c)
    _: Return

Due to the order we visit the program, we'll visit bb2 before bb1. The first time we visit bb2, heapAtHead will be:
#@a: ObjectAllocation({})
#@b: ActivationAllocation()
@a => #@a
@b => #@b

Now CheckStructure would always fail, so it will escape @a and heapAtTail will be:
#@a: EscapedAllocation()
#@b: ActivationAllocation()
@a => #@a
@b => #@b

And after pruning:
#@b: ActivationAllocation()
@b => #@b

Now, we'll visit bb3 and then bb1. When we visit bb1 we'll set the structure {x: 0} for the #@a and eventually visit bb2 again. This time around CheckStructure will no longer escape @a, since the allocation has the right structure, and heapAtTail will be:
#@a: ObjectAllocation({x: 0})
#@b: ActivationAllocation(0: #@a)
@b => #@b

However, we now have to merge into bb3, which has heapAtHead:
#@b: ActivationAllocation()
@b => #@b

Since we can't add the extra field to the activation, we'll end up escaping @a at the edge and therefore pruning #@b, which will leave the heap for bb3 unchanged. That's a problem, since PutClosureVar didn't see the escaped object, but GetClosureVar thinks it's escaped. The materialization for @a will be placed after the PutClosureVar, at end of bb2, when the node is already dead. When computing the SSA defs, the PutByOffset at bb3 will then see @a (which at this point will be a PhantomNewObject) instead of its materialization.

[Tadeu Zagallo]

Created attachment 408711 [details]
Patch

[Saam Barati]

Comment on attachment 408711 [details]
Patch

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

> Source/JavaScriptCore/ChangeLog:16
> +                _: PutStrucute(a, {x: 0})

what is the terminal node here?

[Tadeu Zagallo]

Comment on attachment 408711 [details]
Patch

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

>> Source/JavaScriptCore/ChangeLog:16
>> +                _: PutStrucute(a, {x: 0})
> 
> what is the terminal node here?

In the original test this was a loop, so it should probably been Branch(bb2, bb1), I can update.

[Tadeu Zagallo]

Created attachment 408756 [details]
Patch

[Saam Barati]

Comment on attachment 408756 [details]
Patch

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

r=me

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:209
> +    Allocation& mergeStructures(const Allocation& other)

nit: I think this is only called in one places. I kinda think we should just inline it into the call site?

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:211
> +        ASSERT(hasStructures() || other.structuresForMaterialization().isEmpty());

you should assert that both are empty at the same time, right?

Also, shouldn't structuresForMaterialization be a superset of structures? Maybe assert that below

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:213
> +        m_structures.filter(other.structures());
> +        m_structuresForMaterialization.merge(other.structuresForMaterialization());

can you comment on the nature of these, either here or maybe at their declaration point in this class, since it's pretty subtle.

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:330
> +        if (!m_structuresForMaterialization.isEmpty())
> +            out.print(inContext(m_structuresForMaterialization.toStructureSet(), context));

can you also print m_structures? And perhaps add some naming to them so we can distinguish.

> JSTests/stress/allocation-sinking-changing-structures.js:1
> +//@

remove or add something here

[Tadeu Zagallo]

Comment on attachment 408756 [details]
Patch

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

Thanks for the review!

>> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:209
>> +    Allocation& mergeStructures(const Allocation& other)
> 
> nit: I think this is only called in one places. I kinda think we should just inline it into the call site?

will do

>> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:211
>> +        ASSERT(hasStructures() || other.structuresForMaterialization().isEmpty());
> 
> you should assert that both are empty at the same time, right?
> 
> Also, shouldn't structuresForMaterialization be a superset of structures? Maybe assert that below

Yeah, it should be a super set, I'll add the assertions.

>> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:213
>> +        m_structuresForMaterialization.merge(other.structuresForMaterialization());
> 
> can you comment on the nature of these, either here or maybe at their declaration point in this class, since it's pretty subtle.

will do

>> JSTests/stress/allocation-sinking-changing-structures.js:1
>> +//@
> 
> remove or add something here

oops

[Tadeu Zagallo]

Created attachment 408873 [details]
Patch for landing

[EWS]

Committed r267114: <https://trac.webkit.org/changeset/267114>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 408873 [details].