Changeset 262932 in webkit

Timestamp:

Jun 11, 2020, 5:29:30 PM (5 years ago)

Author:

sbarati@apple.com

Message:

Linear Scan uses the wrong Interval for spills for tmps with roles of early def or late use
​https://bugs.webkit.org/show_bug.cgi?id=213055
<rdar://problem/59874018>

Reviewed by Yusuke Suzuki.

There was a bug in linear scan when computing the live range interval for
spill tmps that had early defs or late uses. When linear scan spills a
tmp, it creates a new tmp that it loads to and stores from, and replaces the old tmp
with the new tmp, and emits stores/loads around pertinent instructions. The live
interval for such tmps is small by nature, it's contained in the interval for the
instruction itself. However, we'd build this interval purely based off the
original tmp's arg timing. So, for example, let's consider a program like this:

RandoInsn: LateUse:Tmp1, Use:Tmp2, [early = N, late = N+1]
Let's say that Tmp1's last use is RandoInsn, and it had a def before
RandoInsn, therefore, its live range will be something like:
[J where J < N, N+1]

and now imagine we spilled Tmp1 for some reason, and rewrote the
program to be:
Move Addr(spill for Tmp1), TmpSpill
RandoInsn: LateUse:TmpSpill, Use:Tmp2, [early = N, late = N+1]

We used to incorrectly mark the live range for TmpSpill to just be [N+1, N+2).
However, the bug here is that we neglected that TmpSpill actually had an earlier
def at [N, N+1). So, the live range for TmpSpill was wrong. This could incorrectly
lead us to allocate Tmp2 and TmpSpill to the same register, since their live
ranges may not intersect if Tmp2 dies at RandoInsn.

We also had the symmetric bug for EarlyDefs: we wouldn't account for the
store-spill that'd happen after something like RandoInsn.

The fix is to account for the loads/stores of spill tmps when assigning
them a live range.

This patch contains a standalone test in testair. It also fixes crashes we had when
running B3O1 tests using typed arrays on arm64e since we had patchpoints that utilized
LateUse for signing and auth.

• b3/B3Procedure.h:
• b3/air/AirAllocateRegistersAndStackByLinearScan.cpp:
• b3/air/testair.cpp:

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• b3/B3Procedure.h (modified) (1 diff)
• b3/air/AirAllocateRegistersAndStackByLinearScan.cpp (modified) (2 diffs)
• b3/air/testair.cpp (modified) (2 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2020-06-11  Saam Barati  <sbarati@apple.com>
+
+        Linear Scan uses the wrong Interval for spills for tmps with roles of early def or late use
+        https://bugs.webkit.org/show_bug.cgi?id=213055
+        <rdar://problem/59874018>
+
+        Reviewed by Yusuke Suzuki.
+
+        There was a bug in linear scan when computing the live range interval for
+        spill tmps that had early defs or late uses.  When linear scan spills a
+        tmp, it creates a new tmp that it loads to and stores from, and replaces the old tmp
+        with the new tmp, and emits stores/loads around pertinent instructions. The live
+        interval for such tmps is small by nature, it's contained in the interval for the
+        instruction itself. However, we'd build this interval purely based off the
+        original tmp's arg timing. So, for example, let's consider a program like this:
+        
+        RandoInsn: LateUse:Tmp1, Use:Tmp2, [early = N, late = N+1]
+        Let's say that Tmp1's last use is RandoInsn, and it had a def before
+        RandoInsn, therefore, its live range will be something like:
+        [J where J < N, N+1]
+        
+        and now imagine we spilled Tmp1 for some reason, and rewrote the
+        program to be:
+        Move Addr(spill for Tmp1), TmpSpill
+        RandoInsn: LateUse:TmpSpill, Use:Tmp2, [early = N, late = N+1]
+        
+        We used to incorrectly mark the live range for TmpSpill to just be [N+1, N+2).
+        However, the bug here is that we neglected that TmpSpill actually had an earlier
+        def at [N, N+1). So, the live range for TmpSpill was wrong. This could incorrectly
+        lead us to allocate Tmp2 and TmpSpill to the same register, since their live
+        ranges may not intersect if Tmp2 dies at RandoInsn.
+        
+        We also had the symmetric bug for EarlyDefs: we wouldn't account for the
+        store-spill that'd happen after something like RandoInsn.
+        
+        The fix is to account for the loads/stores of spill tmps when assigning
+        them a live range.
+        
+        This patch contains a standalone test in testair. It also fixes crashes we had when
+        running B3O1 tests using typed arrays on arm64e since we had patchpoints that utilized
+        LateUse for signing and auth.
+
+        * b3/B3Procedure.h:
+        * b3/air/AirAllocateRegistersAndStackByLinearScan.cpp:
+        * b3/air/testair.cpp:
+
 2020-06-11  Saam Barati  <sbarati@apple.com>
 

trunk/Source/JavaScriptCore/b3/B3Procedure.h

@@ -134 +134 @@
 
     // bits is a bitwise_cast of the constant you want.
-    Value* addConstant(Origin, Type, uint64_t bits);
+    JS_EXPORT_PRIVATE Value* addConstant(Origin, Type, uint64_t bits);
 
     // You're guaranteed that bottom is zero.

trunk/Source/JavaScriptCore/b3/air/AirAllocateRegistersAndStackByLinearScan.cpp

@@ -184 +184 @@
     }
     
-    Interval interval(size_t indexOfEarly, Arg::Timing timing)
+    static Interval earlyInterval(size_t indexOfEarly)
+    {
+        return Interval(indexOfEarly);
+    }
+
+    static Interval lateInterval(size_t indexOfEarly)
+    {
+        return Interval(indexOfEarly + 1);
+    }
+
+    static Interval earlyAndLateInterval(size_t indexOfEarly)
+    {
+        return earlyInterval(indexOfEarly) | lateInterval(indexOfEarly);
+    }
+
+    static Interval interval(size_t indexOfEarly, Arg::Timing timing)
     {
         switch (timing) {
         case Arg::OnlyEarly:
-            return Interval(indexOfEarly);
+            return earlyInterval(indexOfEarly);
         case Arg::OnlyLate:
-            return Interval(indexOfEarly + 1);
+            return lateInterval(indexOfEarly);
         case Arg::EarlyAndLate:
-            return Interval(indexOfEarly, indexOfEarly + 2);
+            return earlyAndLateInterval(indexOfEarly);
+        }
+        ASSERT_NOT_REACHED();
+        return Interval();
+    }
+
+    static Interval intervalForSpill(size_t indexOfEarly, Arg::Role role)
+    {
+        Arg::Timing timing = Arg::timing(role);
+        switch (timing) {
+        case Arg::OnlyEarly:
+            if (Arg::isAnyDef(role))
+                return earlyAndLateInterval(indexOfEarly); // We have a spill store after this insn.
+            return earlyInterval(indexOfEarly);
+        case Arg::OnlyLate:
+            if (Arg::isAnyUse(role))
+                return earlyAndLateInterval(indexOfEarly); // We had a spill load before this insn.
+            return lateInterval(indexOfEarly);
+        case Arg::EarlyAndLate:
+            return earlyAndLateInterval(indexOfEarly);
         }
         ASSERT_NOT_REACHED();
@@ -550 +584 @@
                             return;
                         Opcode move = bank == GP ? Move : MoveDouble;
-                        tmp = addSpillTmpWithInterval(bank, interval(indexOfEarly, Arg::timing(role)));
+                        tmp = addSpillTmpWithInterval(bank, intervalForSpill(indexOfEarly, role));
                         if (role == Arg::Scratch)
                             return;

trunk/Source/JavaScriptCore/b3/air/testair.cpp

@@ -2237 +2237 @@
         CHECK(runResult == static_cast<unsigned>(42 + (42 * (reg == GPRInfo::returnValueGPR))));
     }
+}
+
+void testLinearScanSpillRangesLateUse()
+{
+    B3::Procedure proc;
+    Code& code = proc.code();
+
+    BasicBlock* root = code.addBlock();
+
+    B3::Air::Special* patchpointSpecial = code.addSpecial(makeUnique<B3::PatchpointSpecial>());
+
+    Vector<Tmp> tmps;
+    for (unsigned i = 0; i < 100; ++i) {
+        Tmp tmp = code.newTmp(GP);
+        tmps.append(tmp);
+        root->append(Move, nullptr, Arg::bigImm(i), tmp);
+    }
+
+    for (unsigned i = 0; i + 1 < tmps.size(); ++i) {
+        Tmp tmp1 = tmps[i];
+        Tmp tmp2 = tmps[i + 1];
+
+        B3::Value* dummyValue = proc.addConstant(B3::Origin(), B3::Int64, 0);
+        B3::Value* dummyValue2 = proc.addConstant(B3::Origin(), B3::Int64, 0);
+
+        B3::PatchpointValue* patchpoint = proc.add<B3::PatchpointValue>(B3::Void, B3::Origin());
+        patchpoint->append(dummyValue, B3::ValueRep::SomeRegister);
+        patchpoint->append(dummyValue2, B3::ValueRep::SomeLateRegister);
+        patchpoint->setGenerator([=] (CCallHelpers& jit, const B3::StackmapGenerationParams& params) {
+            RELEASE_ASSERT(params[0].gpr() != params[1].gpr());
+
+            auto good = jit.branch32(CCallHelpers::Equal, params[0].gpr(), CCallHelpers::TrustedImm32(i));
+            jit.breakpoint();
+            good.link(&jit);
+
+            good = jit.branch32(CCallHelpers::Equal, params[1].gpr(), CCallHelpers::TrustedImm32(i + 1));
+            jit.breakpoint();
+            good.link(&jit);
+
+        });
+
+        Inst inst(Patch, patchpoint, Arg::special(patchpointSpecial));
+        inst.args.append(tmp1);
+        inst.args.append(tmp2);
+
+        root->append(inst);
+    }
+
+    root->append(Move32, nullptr, tmps.last(), Tmp(GPRInfo::returnValueGPR));
+    root->append(Ret32, nullptr, Tmp(GPRInfo::returnValueGPR));
+
+    auto runResult = compileAndRun<uint32_t>(proc);
+    CHECK(runResult == 99);
+}
+
+void testLinearScanSpillRangesEarlyDef()
+{
+    B3::Procedure proc;
+    Code& code = proc.code();
+
+    BasicBlock* root = code.addBlock();
+
+    B3::Air::Special* patchpointSpecial = code.addSpecial(makeUnique<B3::PatchpointSpecial>());
+
+    Vector<Tmp> tmps;
+    for (unsigned i = 0; i < 100; ++i) {
+        Tmp tmp = code.newTmp(GP);
+        tmps.append(tmp);
+        if (!i)
+            root->append(Move, nullptr, Arg::bigImm(i), tmp);
+    }
+
+    for (unsigned i = 0; i + 1 < tmps.size(); ++i) {
+        Tmp tmp1 = tmps[i];
+        Tmp tmp2 = tmps[i + 1];
+
+        B3::Value* dummyValue = proc.addConstant(B3::Origin(), B3::Int64, 0);
+
+        B3::PatchpointValue* patchpoint = proc.add<B3::PatchpointValue>(B3::Int32, B3::Origin());
+        patchpoint->resultConstraints = { B3::ValueRep::SomeEarlyRegister };
+        patchpoint->append(dummyValue, B3::ValueRep::SomeLateRegister);
+        patchpoint->setGenerator([=] (CCallHelpers& jit, const B3::StackmapGenerationParams& params) {
+            RELEASE_ASSERT(params[0].gpr() != params[1].gpr());
+
+            auto good = jit.branch32(CCallHelpers::Equal, params[1].gpr(), CCallHelpers::TrustedImm32(i));
+            jit.breakpoint();
+            good.link(&jit);
+
+            jit.move(CCallHelpers::TrustedImm32(i + 1), params[0].gpr());
+        });
+
+        Inst inst(Patch, patchpoint, Arg::special(patchpointSpecial));
+        inst.args.append(tmp2); // def
+        inst.args.append(tmp1); // use
+
+        root->append(inst);
+    }
+
+    // Make all tmps live till the end
+    for (unsigned i = 0; i < tmps.size(); ++i) {
+        Tmp tmp = tmps[i];
+
+        B3::Value* dummyValue = proc.addConstant(B3::Origin(), B3::Int64, 0);
+
+        B3::PatchpointValue* patchpoint = proc.add<B3::PatchpointValue>(B3::Void, B3::Origin());
+        patchpoint->append(dummyValue, B3::ValueRep::SomeRegister);
+        patchpoint->setGenerator([=] (CCallHelpers& jit, const B3::StackmapGenerationParams& params) {
+            auto good = jit.branch32(CCallHelpers::Equal, params[0].gpr(), CCallHelpers::TrustedImm32(i));
+            jit.breakpoint();
+            good.link(&jit);
+        });
+
+        Inst inst(Patch, patchpoint, Arg::special(patchpointSpecial));
+        inst.args.append(tmp);
+        root->append(inst);
+    }
+
+    root->append(Move32, nullptr, tmps.last(), Tmp(GPRInfo::returnValueGPR));
+    root->append(Ret32, nullptr, Tmp(GPRInfo::returnValueGPR));
+
+    auto runResult = compileAndRun<uint32_t>(proc);
+    CHECK(runResult == 99);
 }
 
@@ -2331 +2453 @@
     RUN(testElideMoveThenRealloc());
 
+    RUN(testLinearScanSpillRangesLateUse());
+    RUN(testLinearScanSpillRangesEarlyDef());
+
     if (tasks.isEmpty())
         usage();