Changeset 65042 in webkit for trunk/JavaScriptCore/assembler/ARMv7Assembler.h

Timestamp:

Aug 9, 2010, 8:19:19 PM (15 years ago)

Author:

[email protected]

Message:

2010-08-09 Oliver Hunt <​[email protected]>

Reviewed by Gavin Barraclough.

Allow an assembler/macroassembler to compact branches to more concise forms when linking
​https://bugs.webkit.org/show_bug.cgi?id=43745

This patch makes it possible for an assembler to convert jumps into a different
(presumably more efficient) form at link time. Currently implemented in the
ARMv7 JIT as that already had logic to delay linking of jumps until the end of
compilation already. The ARMv7 JIT chooses between either a 4 byte short jump
or a full 32-bit offset (and rewrites ITTT instructions as appropriate), so does
not yet produce the most compact form possible. The general design of the linker
should make it relatively simple to introduce new branch types with little effort,
as the linker has no knowledge of the exact form of any of the branches.

• JavaScriptCore.xcodeproj/project.pbxproj:
• assembler/ARMv7Assembler.cpp: Added. (JSC::): Record jump sizes

• assembler/ARMv7Assembler.h: (JSC::ARMv7Assembler::LinkRecord::LinkRecord): (JSC::ARMv7Assembler::LinkRecord::from): (JSC::ARMv7Assembler::LinkRecord::setFrom): (JSC::ARMv7Assembler::LinkRecord::to): (JSC::ARMv7Assembler::LinkRecord::type): (JSC::ARMv7Assembler::LinkRecord::linkType): (JSC::ARMv7Assembler::LinkRecord::setLinkType): Encapsulate LinkRecord fields so we can compress the values somewhat

(JSC::ARMv7Assembler::JmpSrc::JmpSrc):

Need to record the jump type now

(JSC::ARMv7Assembler::b):
(JSC::ARMv7Assembler::blx):
(JSC::ARMv7Assembler::bx):

Need to pass the jump types

(JSC::ARMv7Assembler::executableOffsetFor):
(JSC::ARMv7Assembler::jumpSizeDelta):
(JSC::ARMv7Assembler::linkRecordSourceComparator):
(JSC::ARMv7Assembler::computeJumpType):
(JSC::ARMv7Assembler::convertJumpTo):
(JSC::ARMv7Assembler::recordLinkOffsets):
(JSC::ARMv7Assembler::jumpsToLink):
(JSC::ARMv7Assembler::link):
(JSC::ARMv7Assembler::unlinkedCode):

Helper functions for the linker

(JSC::ARMv7Assembler::linkJump):
(JSC::ARMv7Assembler::canBeShortJump):
(JSC::ARMv7Assembler::linkLongJump):
(JSC::ARMv7Assembler::linkShortJump):
(JSC::ARMv7Assembler::linkJumpAbsolute):

Moving code around for the various jump linking functions

• assembler/AbstractMacroAssembler.h: (JSC::AbstractMacroAssembler::beginUninterruptedSequence): (JSC::AbstractMacroAssembler::endUninterruptedSequence): We have to track uninterrupted sequences in any assembler that compacts branches as that's not something we're allowed to do in such sequences. AbstractMacroAssembler has a nop version of these functions as it makes the code elsewhere nicer.

• assembler/LinkBuffer.h: (JSC::LinkBuffer::LinkBuffer): (JSC::LinkBuffer::link): (JSC::LinkBuffer::patch): (JSC::LinkBuffer::locationOf): (JSC::LinkBuffer::locationOfNearCall): (JSC::LinkBuffer::returnAddressOffset): (JSC::LinkBuffer::trampolineAt): Updated these functions to adjust for any changed offsets in the linked code

(JSC::LinkBuffer::applyOffset):

A helper function to deal with the now potentially moved labels

(JSC::LinkBuffer::linkCode):

The new and mighty linker function

• assembler/MacroAssemblerARMv7.h: (JSC::MacroAssemblerARMv7::MacroAssemblerARMv7): (JSC::MacroAssemblerARMv7::beginUninterruptedSequence): (JSC::MacroAssemblerARMv7::endUninterruptedSequence): (JSC::MacroAssemblerARMv7::jumpsToLink): (JSC::MacroAssemblerARMv7::unlinkedCode): (JSC::MacroAssemblerARMv7::computeJumpType): (JSC::MacroAssemblerARMv7::convertJumpTo): (JSC::MacroAssemblerARMv7::recordLinkOffsets): (JSC::MacroAssemblerARMv7::jumpSizeDelta): (JSC::MacroAssemblerARMv7::link): (JSC::MacroAssemblerARMv7::jump): (JSC::MacroAssemblerARMv7::branchMul32): (JSC::MacroAssemblerARMv7::breakpoint): (JSC::MacroAssemblerARMv7::nearCall): (JSC::MacroAssemblerARMv7::call): (JSC::MacroAssemblerARMv7::ret): (JSC::MacroAssemblerARMv7::tailRecursiveCall): (JSC::MacroAssemblerARMv7::executableOffsetFor): (JSC::MacroAssemblerARMv7::inUninterruptedSequence): (JSC::MacroAssemblerARMv7::makeJump): (JSC::MacroAssemblerARMv7::makeBranch):

All branches need to pass on their type now

• jit/ExecutableAllocator.h: (JSC::ExecutablePool::returnLastBytes):

We can't know ahead of time how much space will be necessary to
hold the linked code if we're compacting branches, this new
function allows us to return the unused bytes at the end of linking

• jit/JIT.cpp: (JSC::JIT::JIT): (JSC::JIT::privateCompile):
• jit/JIT.h: (JSC::JIT::compile):

The JIT class now needs to take a linker offset so that recompilation
can generate the same jumps when using branch compaction.

• jit/JITArithmetic32_64.cpp: (JSC::JIT::emitSlow_op_mod):
• jit/JITOpcodes.cpp: (JSC::JIT::privateCompileCTIMachineTrampolines):
• jit/JITOpcodes32_64.cpp: (JSC::JIT::privateCompileCTIMachineTrampolines): (JSC::JIT::privateCompileCTINativeCall): Update for new trampolineAt changes

• wtf/FastMalloc.cpp: (WTF::TCMallocStats::):
• wtf/Platform.h:

File:

• trunk/JavaScriptCore/assembler/ARMv7Assembler.h (modified) (16 diffs)

trunk/JavaScriptCore/assembler/ARMv7Assembler.h

@@ -382 +382 @@
         u.d = d;
 
-        int sign = (u.i >> 63);
-        int exponent = (u.i >> 52) & 0x7ff;
+        int sign = static_cast<int>(u.i >> 63);
+        int exponent = static_cast<int>(u.i >> 52) & 0x7ff;
         uint64_t mantissa = u.i & 0x000fffffffffffffull;
 
@@ -445 +445 @@
     } m_u;
 };
-
 
 class ARMv7Assembler {
@@ -477 +476 @@
         ConditionLE,
         ConditionAL,
-
+        
         ConditionCS = ConditionHS,
         ConditionCC = ConditionLO,
     } Condition;
 
+    enum JumpType { JumpNoCondition, JumpCondition, JumpFullSize };
+    enum JumpLinkType { LinkInvalid, LinkShortJump, LinkConditionalShortJump, LinkLongJump, JumpTypeCount };
+    static const int JumpSizes[JumpTypeCount];
+    enum { JumpPaddingSize = 5 * sizeof(uint16_t) };
+    class LinkRecord {
+    public:
+        LinkRecord(intptr_t from, intptr_t to, JumpType type, Condition condition)
+            : m_from(from)
+            , m_to(to)
+            , m_type(type)
+            , m_linkType(LinkInvalid)
+            , m_condition(condition)
+        {
+        }
+        intptr_t from() const { return m_from; }
+        void setFrom(intptr_t from) { m_from = from; }
+        intptr_t to() const { return m_to; }
+        JumpType type() const { return m_type; }
+        JumpLinkType linkType() const { return m_linkType; }
+        void setLinkType(JumpLinkType linkType) { ASSERT(m_linkType == LinkInvalid); m_linkType = linkType; }
+        Condition condition() const { return m_condition; }
+    private:
+        intptr_t m_from : 31;
+        intptr_t m_to : 31;
+        JumpType m_type : 2;
+        JumpLinkType m_linkType : 3;
+        Condition m_condition : 16;
+    };
+    
     class JmpSrc {
         friend class ARMv7Assembler;
         friend class ARMInstructionFormatter;
+        friend class LinkBuffer;
     public:
         JmpSrc()
@@ -492 +521 @@
 
     private:
-        JmpSrc(int offset)
+        JmpSrc(int offset, JumpType type)
             : m_offset(offset)
-        {
+            , m_condition(0xffff)
+            , m_type(type)
+        {
+            ASSERT(m_type != JumpCondition);
+        }
+
+        JmpSrc(int offset, JumpType type, Condition condition)
+            : m_offset(offset)
+            , m_condition(condition)
+            , m_type(type)
+        {
+            ASSERT(m_type == JumpCondition || m_type == JumpFullSize);
         }
 
         int m_offset;
+        Condition m_condition : 16;
+        JumpType m_type : 16;
+        
     };
     
@@ -503 +546 @@
         friend class ARMv7Assembler;
         friend class ARMInstructionFormatter;
+        friend class LinkBuffer;
     public:
         JmpDst()
@@ -525 +569 @@
 
 private:
-
-    struct LinkRecord {
-        LinkRecord(intptr_t from, intptr_t to)
-            : from(from)
-            , to(to)
-        {
-        }
-
-        intptr_t from;
-        intptr_t to;
-    };
 
     // ARMv7, Appx-A.6.3
@@ -740 +773 @@
 
 public:
-
+    
     void add(RegisterID rd, RegisterID rn, ARMThumbImmediate imm)
     {
@@ -879 +912 @@
         m_formatter.twoWordOp12Reg4FourFours(OP_ASR_reg_T2, rn, FourFours(0xf, rd, 0, rm));
     }
-
+    
     // Only allowed in IT (if then) block if last instruction.
-    JmpSrc b()
+    JmpSrc b(JumpType type)
     {
         m_formatter.twoWordOp16Op16(OP_B_T4a, OP_B_T4b);
-        return JmpSrc(m_formatter.size());
+        return JmpSrc(m_formatter.size(), type);
     }
     
     // Only allowed in IT (if then) block if last instruction.
-    JmpSrc blx(RegisterID rm)
+    JmpSrc blx(RegisterID rm, JumpType type)
     {
         ASSERT(rm != ARMRegisters::pc);
         m_formatter.oneWordOp8RegReg143(OP_BLX, rm, (RegisterID)8);
-        return JmpSrc(m_formatter.size());
+        return JmpSrc(m_formatter.size(), type);
     }
 
     // Only allowed in IT (if then) block if last instruction.
-    JmpSrc bx(RegisterID rm)
+    JmpSrc bx(RegisterID rm, JumpType type, Condition condition)
     {
         m_formatter.oneWordOp8RegReg143(OP_BX, rm, (RegisterID)0);
-        return JmpSrc(m_formatter.size());
+        return JmpSrc(m_formatter.size(), type, condition);
+    }
+
+    JmpSrc bx(RegisterID rm, JumpType type)
+    {
+        m_formatter.oneWordOp8RegReg143(OP_BX, rm, (RegisterID)0);
+        return JmpSrc(m_formatter.size(), type);
     }
 
@@ -1618 +1657 @@
         return dst.m_offset - src.m_offset;
     }
+
+    int executableOffsetFor(int location)
+    {
+        if (!location)
+            return 0;
+        return static_cast<int32_t*>(m_formatter.data())[location / sizeof(int32_t) - 1];
+    }
+    
+    int jumpSizeDelta(JumpLinkType jumpLinkType) { return JumpPaddingSize - JumpSizes[jumpLinkType]; }
     
     // Assembler admin methods:
@@ -1626 +1674 @@
     }
 
-    void* executableCopy(ExecutablePool* allocator)
-    {
-        void* copy = m_formatter.executableCopy(allocator);
-        if (!copy)
-            return 0;
-
-        unsigned jumpCount = m_jumpsToLink.size();
-        for (unsigned i = 0; i < jumpCount; ++i) {
-            uint16_t* location = reinterpret_cast<uint16_t*>(reinterpret_cast<intptr_t>(copy) + m_jumpsToLink[i].from);
-            uint16_t* target = reinterpret_cast<uint16_t*>(reinterpret_cast<intptr_t>(copy) + m_jumpsToLink[i].to);
-            linkJumpAbsolute(location, target);
-        }
-        m_jumpsToLink.clear();
-
-        return copy;
-    }
-
+    static bool linkRecordSourceComparator(const LinkRecord& a, const LinkRecord& b)
+    {
+        return a.from() < b.from();
+    }
+
+    JumpLinkType computeJumpType(LinkRecord& record, const uint8_t* from, const uint8_t* to)
+    {
+        if (record.type() >= JumpFullSize) {
+            record.setLinkType(LinkLongJump);
+            return LinkLongJump;
+        }
+        bool mayTriggerErrata = false;
+        const uint16_t* shortJumpLocation = reinterpret_cast<const uint16_t*>(from  - (JumpPaddingSize - JumpSizes[LinkShortJump]));
+        if (!canBeShortJump(shortJumpLocation, to, mayTriggerErrata)) {
+            record.setLinkType(LinkLongJump);
+            return LinkLongJump;
+        }
+        if (mayTriggerErrata) {
+            record.setLinkType(LinkLongJump);
+            return LinkLongJump;
+        }
+        if (record.type() == JumpCondition) {
+            record.setLinkType(LinkConditionalShortJump);
+            return LinkConditionalShortJump;
+        }
+        record.setLinkType(LinkShortJump);
+        return LinkShortJump;
+    }
+
+    void recordLinkOffsets(int32_t regionStart, int32_t regionEnd, int32_t offset)
+    {
+        int32_t ptr = regionStart / sizeof(int32_t);
+        const int32_t end = regionEnd / sizeof(int32_t);
+        int32_t* offsets = static_cast<int32_t*>(m_formatter.data());
+        while (ptr < end)
+            offsets[ptr++] = offset;
+    }
+    
+    Vector<LinkRecord>& jumpsToLink()
+    {
+        std::sort(m_jumpsToLink.begin(), m_jumpsToLink.end(), linkRecordSourceComparator);
+        return m_jumpsToLink;
+    }
+
+    void link(LinkRecord& record, uint8_t* from, uint8_t* to)
+    {
+        uint16_t* itttLocation;
+        if (record.linkType() == LinkConditionalShortJump) {
+            itttLocation = reinterpret_cast<uint16_t*>(from - JumpSizes[LinkConditionalShortJump] - 2);
+            itttLocation[0] = ifThenElse(record.condition()) | OP_IT;
+        }
+        ASSERT(record.linkType() != LinkInvalid);
+        if (record.linkType() != LinkLongJump)
+            linkShortJump(reinterpret_cast<uint16_t*>(from), to);
+        else
+            linkLongJump(reinterpret_cast<uint16_t*>(from), to);
+    }
+
+    void* unlinkedCode() { return m_formatter.data(); }
+    
     static unsigned getCallReturnOffset(JmpSrc call)
     {
@@ -1661 +1752 @@
         ASSERT(to.m_offset != -1);
         ASSERT(from.m_offset != -1);
-        m_jumpsToLink.append(LinkRecord(from.m_offset, to.m_offset));
+        m_jumpsToLink.append(LinkRecord(from.m_offset, to.m_offset, from.m_type, from.m_condition));
     }
 
@@ -1864 +1955 @@
     }
 
-    static void linkJumpAbsolute(uint16_t* instruction, void* target)
-    {
-        // FIMXE: this should be up in the MacroAssembler layer. :-(
-        const uint16_t JUMP_TEMPORARY_REGISTER = ARMRegisters::ip;
-
+    static bool canBeShortJump(const uint16_t* instruction, const void* target, bool& mayTriggerErrata)
+    {
         ASSERT(!(reinterpret_cast<intptr_t>(instruction) & 1));
         ASSERT(!(reinterpret_cast<intptr_t>(target) & 1));
-
-        ASSERT( (isMOV_imm_T3(instruction - 5) && isMOVT(instruction - 3) && isBX(instruction - 1))
-            || (isNOP_T1(instruction - 5) && isNOP_T2(instruction - 4) && isB(instruction - 2)) );
-
+        
         intptr_t relative = reinterpret_cast<intptr_t>(target) - (reinterpret_cast<intptr_t>(instruction));
-
         // From Cortex-A8 errata:
         // If the 32-bit Thumb-2 branch instruction spans two 4KiB regions and
@@ -1885 +1969 @@
         // The instruction is spanning two pages if it ends at an address ending 0x002
         bool spansTwo4K = ((reinterpret_cast<intptr_t>(instruction) & 0xfff) == 0x002);
+        mayTriggerErrata = spansTwo4K;
         // The target is in the first page if the jump branch back by [3..0x1002] bytes
         bool targetInFirstPage = (relative >= -0x1002) && (relative < -2);
         bool wouldTriggerA8Errata = spansTwo4K && targetInFirstPage;
-
-        if (((relative << 7) >> 7) == relative && !wouldTriggerA8Errata) {
+        return ((relative << 7) >> 7) == relative && !wouldTriggerA8Errata;
+    }
+
+    static void linkLongJump(uint16_t* instruction, void* target)
+    {
+        linkJumpAbsolute(instruction, target);
+    }
+    
+    static void linkShortJump(uint16_t* instruction, void* target)
+    {
+        // FIMXE: this should be up in the MacroAssembler layer. :-(        
+        ASSERT(!(reinterpret_cast<intptr_t>(instruction) & 1));
+        ASSERT(!(reinterpret_cast<intptr_t>(target) & 1));
+        
+        intptr_t relative = reinterpret_cast<intptr_t>(target) - (reinterpret_cast<intptr_t>(instruction));
+        bool scratch;
+        UNUSED_PARAM(scratch);
+        ASSERT(canBeShortJump(instruction, target, scratch));
+        // ARM encoding for the top two bits below the sign bit is 'peculiar'.
+        if (relative >= 0)
+            relative ^= 0xC00000;
+
+        // All branch offsets should be an even distance.
+        ASSERT(!(relative & 1));
+        instruction[-2] = OP_B_T4a | ((relative & 0x1000000) >> 14) | ((relative & 0x3ff000) >> 12);
+        instruction[-1] = OP_B_T4b | ((relative & 0x800000) >> 10) | ((relative & 0x400000) >> 11) | ((relative & 0xffe) >> 1);
+    }
+
+    static void linkJumpAbsolute(uint16_t* instruction, void* target)
+    {
+        // FIMXE: this should be up in the MacroAssembler layer. :-(
+        ASSERT(!(reinterpret_cast<intptr_t>(instruction) & 1));
+        ASSERT(!(reinterpret_cast<intptr_t>(target) & 1));
+
+        ASSERT((isMOV_imm_T3(instruction - 5) && isMOVT(instruction - 3) && isBX(instruction - 1))
+            || (isNOP_T1(instruction - 5) && isNOP_T2(instruction - 4) && isB(instruction - 2)));
+
+        intptr_t relative = reinterpret_cast<intptr_t>(target) - (reinterpret_cast<intptr_t>(instruction));
+        bool scratch;
+        if (canBeShortJump(instruction, target, scratch)) {
             // ARM encoding for the top two bits below the sign bit is 'peculiar'.
             if (relative >= 0)
@@ -1907 +2030 @@
             instruction[-1] = OP_B_T4b | ((relative & 0x800000) >> 10) | ((relative & 0x400000) >> 11) | ((relative & 0xffe) >> 1);
         } else {
+            const uint16_t JUMP_TEMPORARY_REGISTER = ARMRegisters::ip;
             ARMThumbImmediate lo16 = ARMThumbImmediate::makeUInt16(static_cast<uint16_t>(reinterpret_cast<uint32_t>(target) + 1));
             ARMThumbImmediate hi16 = ARMThumbImmediate::makeUInt16(static_cast<uint16_t>(reinterpret_cast<uint32_t>(target) >> 16));
@@ -1921 +2045 @@
         return op | (imm.m_value.i << 10) | imm.m_value.imm4;
     }
+
     static uint16_t twoWordOp5i6Imm4Reg4EncodedImmSecond(uint16_t rd, ARMThumbImmediate imm)
     {
@@ -2037 +2162 @@
 
     Vector<LinkRecord> m_jumpsToLink;
+    Vector<int32_t> m_offsets;
 };