Changeset 195981 in webkit

Timestamp:

Feb 1, 2016 3:19:26 PM (8 years ago)

Author:

benjamin@webkit.org

Message:

[JSC] IRC can coalesce the frame pointer with a Tmp that is modified
​https://bugs.webkit.org/show_bug.cgi?id=153694

Reviewed by Filip Pizlo.

Let's say we have:

Move(FP, Tmp1)
Add64(#1, Tmp1)

If we were to coalesce the Move, we would modify the frame pointer.
Well, that's exactly what was happening with IRC.

Since the epilogue is not know to Air before IRC, the liveness analysis
never discovers that FP is live when Tmp1 is UseDef by Add64. Adding
FP would a be a problem anyway for a bunch of reasons.

I tried two ways to prevent IRC to override IRC:
1) Add an interference edge with FP for all non-duplication Defs.
2) Let coalesce() know about FP and constraint any coalescing with a re-Def.

The two are within margin of error for performance. The second one was considerably
more complicated. This patch implements the first one.

Some extra note:
-It is very important to not increment the degree of a Tmp when making it interfere

with FP. FP is not a valid color, it is not counted in the "K" colors considered
for coloring. Increasing the degree with the edge to FP would make every stage
pessimistic since there is an extra degree that can never be removed.

-I put "interferenceEdges" and "adjacencyList" in an inconsistent state.

This is intentional, "interferenceEdges" is used to test the existence of an edge,
"adjacencyList" is used to go over all the edges. In this case, we don't want
the edge with FP to be considered when pruning the graph.

• b3/air/AirIteratedRegisterCoalescing.cpp:

One branch could be transformed into an assertion: TmpLiveness is type specific now.

• b3/testb3.cpp:

(JSC::B3::testOverrideFramePointer):
(JSC::B3::run):

Location:

trunk/Source/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• b3/air/AirIteratedRegisterCoalescing.cpp (modified) (4 diffs)
• b3/testb3.cpp (modified) (2 diffs)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2016-02-01  Benjamin Poulain  <benjamin@webkit.org>
+
+        [JSC] IRC can coalesce the frame pointer with a Tmp that is modified
+        https://bugs.webkit.org/show_bug.cgi?id=153694
+
+        Reviewed by Filip Pizlo.
+
+        Let's say we have:
+            Move(FP, Tmp1)
+            Add64(#1, Tmp1)
+
+        If we were to coalesce the Move, we would modify the frame pointer.
+        Well, that's exactly what was happening with IRC.
+
+        Since the epilogue is not know to Air before IRC, the liveness analysis
+        never discovers that FP is live when Tmp1 is UseDef by Add64. Adding
+        FP would a be a problem anyway for a bunch of reasons.
+
+        I tried two ways to prevent IRC to override IRC:
+        1) Add an interference edge with FP for all non-duplication Defs.
+        2) Let coalesce() know about FP and constraint any coalescing with a re-Def.
+
+        The two are within margin of error for performance. The second one was considerably
+        more complicated. This patch implements the first one.
+
+        Some extra note:
+        -It is very important to not increment the degree of a Tmp when making it interfere
+         with FP. FP is not a valid color, it is not counted in the "K" colors considered
+         for coloring. Increasing the degree with the edge to FP would make every stage
+         pessimistic since there is an extra degree that can never be removed.
+        -I put "interferenceEdges" and "adjacencyList" in an inconsistent state.
+         This is intentional, "interferenceEdges" is used to test the existence of an edge,
+         "adjacencyList" is used to go over all the edges. In this case, we don't want
+         the edge with FP to be considered when pruning the graph.
+
+        * b3/air/AirIteratedRegisterCoalescing.cpp:
+        One branch could be transformed into an assertion: TmpLiveness is type specific now.
+        * b3/testb3.cpp:
+        (JSC::B3::testOverrideFramePointer):
+        (JSC::B3::run):
+
 2016-02-01  Csaba Osztrogonác  <ossy@webkit.org>
 

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

@@ -892 +892 @@
                 
                 for (const Tmp& liveTmp : liveTmps) {
-                    if (liveTmp.isGP() == (type == Arg::GP))
-                        addEdge(arg, liveTmp);
+                    ASSERT(liveTmp.isGP() == (type == Arg::GP));
+                    addEdge(arg, liveTmp);
+                }
+
+                if (type == Arg::GP && !arg.isGPR()) {
+                    m_interferenceEdges.add(InterferenceEdge(
+                        AbsoluteTmpMapper<type>::absoluteIndex(Tmp(MacroAssembler::framePointerRegister)),
+                        AbsoluteTmpMapper<type>::absoluteIndex(arg)));
                 }
             });
@@ -1069 +1075 @@
         }
 
-        for (const auto& tmp : tmpsWithInterferences)
-            out.print("    ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[AbsoluteTmpMapper<type>::absoluteIndex(tmp)], ")\"];\n");
+        for (const auto& tmp : tmpsWithInterferences) {
+            unsigned tmpIndex = AbsoluteTmpMapper<type>::absoluteIndex(tmp);
+            if (tmpIndex < m_degrees.size())
+                out.print("    ", tmp.internalValue(), " [label=\"", tmp, " (", m_degrees[tmpIndex], ")\"];\n");
+            else
+                out.print("    ", tmp.internalValue(), " [label=\"", tmp, "\"];\n");
+        }
 
         for (const auto& edge : m_interferenceEdges)
@@ -1130 +1141 @@
         while (true) {
             ++m_numIterations;
+
+            if (traceDebug)
+                dataLog("Code at iteration ", m_numIterations, ":\n", m_code);
 
             // FIXME: One way to optimize this code is to remove the recomputation inside the fixpoint.
@@ -1149 +1163 @@
             if (!allocator.requiresSpilling()) {
                 assignRegistersToTmp(allocator);
+                if (traceDebug)
+                    dataLog("Successfull allocation at iteration ", m_numIterations, ":\n", m_code);
+
                 return;
             }

trunk/Source/JavaScriptCore/b3/testb3.cpp

@@ -4982 +4982 @@
     CHECK(fp < &proc);
     CHECK(fp >= bitwise_cast<char*>(&proc) - 10000);
+}
+
+void testOverrideFramePointer()
+{
+    {
+        Procedure proc;
+        BasicBlock* root = proc.addBlock();
+
+        // Add a stack slot to make the frame non trivial.
+        root->appendNew<SlotBaseValue>(proc, Origin(), proc.addStackSlot(8, StackSlotKind::Locked));
+
+        // Sub on x86 UseDef the source. If FP is not protected correctly, it will be overridden since it is the last visible use.
+        Value* offset = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+        Value* fp = root->appendNew<Value>(proc, FramePointer, Origin());
+        Value* result = root->appendNew<Value>(proc, Sub, Origin(), fp, offset);
+
+        root->appendNew<ControlValue>(proc, Return, Origin(), result);
+        CHECK(compileAndRun<int64_t>(proc, 1));
+    }
+    {
+        Procedure proc;
+        BasicBlock* root = proc.addBlock();
+
+        root->appendNew<SlotBaseValue>(proc, Origin(), proc.addStackSlot(8, StackSlotKind::Locked));
+
+        Value* offset = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR0);
+        Value* fp = root->appendNew<Value>(proc, FramePointer, Origin());
+        Value* offsetFP = root->appendNew<Value>(proc, BitAnd, Origin(), offset, fp);
+        Value* arg = root->appendNew<ArgumentRegValue>(proc, Origin(), GPRInfo::argumentGPR1);
+        Value* offsetArg = root->appendNew<Value>(proc, Add, Origin(), offset, arg);
+        Value* result = root->appendNew<Value>(proc, Add, Origin(), offsetArg, offsetFP);
+
+        root->appendNew<ControlValue>(proc, Return, Origin(), result);
+        CHECK(compileAndRun<int64_t>(proc, 1, 2));
+    }
 }
 
@@ -10767 +10802 @@
     RUN(testLoadAddrShift(3));
     RUN(testFramePointer());
+    RUN(testOverrideFramePointer());
     RUN(testStackSlot());
     RUN(testLoadFromFramePointer());