X-Git-Url: https://git.stderr.nl/gitweb?a=blobdiff_plain;f=interpreters%2Fgit%2Fcompiler.c;fp=interpreters%2Fgit%2Fcompiler.c;h=6faa94c5ea4acb3bb0c2f98c51d24680814c44c6;hb=147a8cbf17f2b3379277bf7d37cda9866510f16c;hp=0000000000000000000000000000000000000000;hpb=7de488aa6a1709a4d5c59b5ff59862105c1748c5;p=rodin%2Fchimara.git

diff --git a/interpreters/git/compiler.c b/interpreters/git/compiler.c
new file mode 100644
index 0000000..6faa94c
--- /dev/null
+++ b/interpreters/git/compiler.c
@@ -0,0 +1,579 @@
+// $Id: compiler.c,v 1.27 2004/12/10 00:37:00 iain Exp $
+
+#include "git.h"
+#include <assert.h>
+#include <stdlib.h>
+#include <setjmp.h>
+#include <string.h>
+
+// -------------------------------------------------------------
+// Constants
+
+enum
+{
+    LONGJMP_NO_ERROR = 0,
+    LONGJMP_CACHE_FULL = 1,
+    LONGJMP_BAD_OPCODE = 2
+};
+
+// -------------------------------------------------------------
+// Globals
+
+int gPeephole = 1;
+int gDebug = 0;
+int gCacheRAM = 0;
+
+BlockHeader * gBlockHeader;
+
+const char * gLabelNames [] = {
+#define LABEL(label) #label,
+#include "labels.inc"
+    NULL
+};
+
+HashNode ** gHashTable; // Hash table of glulx address -> code.
+git_uint32 gHashSize;   // Number of slots in the hash table.
+
+// -------------------------------------------------------------
+// Types.
+
+typedef struct PatchNode
+{
+    git_uint32 address;       // The glulx address of this instruction.
+    git_sint16 codeOffset;    // Offset from the block header to the compiled code for this instruction.
+    git_sint16 branchOffset;  // If non-zero, offset to a branch opcode followed by a glulx address.
+    union {
+        int isReferenced;     // Set to TRUE if this can be the destination of a jump.
+        HashNode* pad;        // This pad assures that PatchNode and HashNode are the same size.
+    } u;
+}
+PatchNode;
+
+// -------------------------------------------------------------
+// Static variables.
+
+static git_uint32 * sBuffer;   // The buffer where everything is stored.
+static git_uint32 sBufferSize; // Size of the buffer, in 4-byte words.
+
+static Block       sCodeStart; // Start of code cache.
+static Block       sCodeTop;   // Next free space in code cache.
+static PatchNode*  sTempStart; // Start of temporary storage.
+static PatchNode*  sTempEnd;   // End of temporary storage.
+
+static jmp_buf sJumpBuf; // setjmp buffer, used to abort compilation when the buffer is full.
+
+// This is the patch node for the opcode currently being compiled.
+// The 'address' and 'code' fields will be filled in. The other
+// fields can be updated during compilation as necessary.
+static PatchNode * sPatch;
+
+static int sNextInstructionIsReferenced;
+static git_uint32 sLastAddr;
+
+// -------------------------------------------------------------
+// Functions
+
+void initCompiler (size_t size)
+{
+    static BlockHeader dummyHeader;
+    gBlockHeader = &dummyHeader;
+
+    // Make sure various assumptions we're making are correct.
+
+    assert (sizeof(HashNode) <= sizeof(PatchNode));
+
+    // Allocate the buffer. As far as possible, we're going to 
+    // use this buffer for everything compiler-related, and
+    // avoid further dynamic allocation.
+
+    sBuffer = malloc (size);
+    if (sBuffer == NULL)
+        fatalError ("Couldn't allocate code cache");
+    
+    memset (sBuffer, 0, size);
+    sBufferSize = size / 4;
+
+    // Pick a reasonable size for the hash table. This should be
+    // a power of two, and take up about a tenth of the buffer.
+    // (If the buffer is itself a power of two in size, the hash
+    // table will take up a sixteenth of it, which is fine.)
+
+    gHashSize = 1;
+    while (gHashSize < (sBufferSize / 20))
+        gHashSize *= 2;
+
+    // The hash table is stored at the beginning of the buffer,
+    // and the rest is used for code and temporary storage.
+
+    gHashTable = (HashNode**) sBuffer;
+
+    sCodeStart = sCodeTop = (Block) (gHashTable + gHashSize);
+    sTempStart = sTempEnd = (PatchNode*) (sBuffer + sBufferSize);
+}
+
+void shutdownCompiler ()
+{
+    free (sBuffer);
+
+    sBuffer = NULL;
+    sCodeStart = sCodeTop = NULL;
+    sTempStart = sTempEnd = NULL;
+    
+    gHashTable = NULL;
+    gBlockHeader = NULL;
+}
+
+static void abortIfBufferFull ()
+{
+    // Make sure we have at least two words free,
+    // because we'll need them to store a jumpabs
+    // instruction at the very end of the buffer.
+
+    if ((void*) (sCodeTop + 2) >= (void*) sTempStart)
+        longjmp (sJumpBuf, LONGJMP_CACHE_FULL);
+}
+
+void abortCompilation ()
+{
+    longjmp (sJumpBuf, LONGJMP_BAD_OPCODE);
+}
+
+void nextInstructionIsReferenced ()
+{
+    sNextInstructionIsReferenced = 1;
+}
+
+Block compile (git_uint32 pc)
+{
+    git_uint32 endOfBlock;
+    int i, numNodes;
+
+    // Make sure we have enough room for, at a minimum:
+    // - the block header
+    // - one patch node
+    // - one jumpabs instruction (two words).
+
+    int spaceNeeded = (sizeof(BlockHeader) + sizeof(PatchNode) + 8) / 4;
+    if ((void*) (sCodeTop + spaceNeeded) >= (void*) sTempStart)
+    {
+        compressCodeCache();
+    }
+
+    // Emit the header for this block.
+
+    gBlockHeader = (BlockHeader*) sCodeTop;
+    sCodeTop = (git_uint32*) (gBlockHeader + 1);
+
+    sLastAddr = 0;
+    sNextInstructionIsReferenced = 1;
+    resetPeepholeOptimiser();
+
+    sPatch = NULL;
+
+    i = setjmp (sJumpBuf);    
+    if (i == LONGJMP_NO_ERROR)
+    {
+        git_uint32 patchSize = 0;
+        git_uint32 codeSize = 0;
+
+        int done = 0;
+
+        while (!done)
+        {
+        	// If we don't have room for more code, abort.
+			if ((void*) (sCodeTop + 2) >= (void*) (sTempStart - 1))
+			{
+				longjmp (sJumpBuf, LONGJMP_CACHE_FULL);
+			}
+		
+            // Create a temporary patch node for this instruction.
+            --sTempStart;
+            sPatch = sTempStart;
+            sPatch->address = pc;
+            sPatch->codeOffset = sCodeTop - (git_uint32*)gBlockHeader;
+            sPatch->branchOffset = 0;
+            sPatch->u.isReferenced = sNextInstructionIsReferenced;
+
+            sNextInstructionIsReferenced = 0;
+
+            // Make sure we haven't generated over 32K of code.
+
+            patchSize += sizeof(PatchNode) / 4;
+            codeSize = sCodeTop - (git_uint32*)gBlockHeader;
+
+            if (codeSize + patchSize > 32000)
+            {
+                // We've generated almost 32K words of code, which will
+                // start to cause problems for the 16-bit offsets we use
+                // in the hash nodes, so let's just stop here.
+                longjmp (sJumpBuf, LONGJMP_CACHE_FULL);
+            }
+
+            // Parse the next instruction.
+
+            parseInstruction (&pc, &done);
+
+            if (pc < sLastAddr)
+                done = 0;
+        }
+    }
+    else    
+    {
+        // Compilation was aborted, but we should have a
+        // patch node and at least two words of space free.
+        
+        assert (sPatch != NULL);
+        sPatch->branchOffset = 0; // Make sure the patch isn't treated as a branch.
+        
+        sCodeTop = ((git_uint32*)gBlockHeader) + sPatch->codeOffset;
+
+        if (i == LONGJMP_CACHE_FULL)
+        {
+            // The buffer is full. We'll replace the partially-compiled
+            // instruction with a jumpabs, forcing another cache lookup
+            // when the terp hits this point in the code.
+    
+            *sCodeTop++ = (git_uint32) labelToOpcode (label_recompile);
+            *sCodeTop++ = sPatch->address;
+			
+            // Make sure this node doesn't get put into the hash table.
+            sPatch->u.isReferenced = 0;
+        }
+        else if (i == LONGJMP_BAD_OPCODE)
+        {
+            // We found a badly-formed instruction. We'll replace the
+            // partially-compiled instruction with a label that raises
+            // an error if the terp hits this code location.
+            
+            *sCodeTop++ = (git_uint32) labelToOpcode (label_error_bad_opcode);
+            *sCodeTop++ = sPatch->address;
+        }
+        else
+        {
+            fatalError ("unknown error in compile (BUG)");
+        }
+    }
+    
+    assert ((void*) sCodeTop <= (void*) sTempStart);
+
+    // We now know where the block ends.
+    
+    endOfBlock = pc;
+
+    // Fix up the constant branches.
+
+    numNodes = sTempEnd - sTempStart;
+    for (i = 0 ; i < numNodes ; ++i)
+    {
+        git_uint32* constBranch;
+            
+        git_uint32 dest;
+        git_uint32 lower = 0;
+        git_uint32 upper = numNodes;
+        
+        PatchNode * p = sTempStart + i;
+        if (p->branchOffset == 0)
+            continue;
+       
+        constBranch = ((git_uint32*)gBlockHeader) + p->branchOffset;
+        dest = constBranch [1];
+        while (upper > lower)
+        {
+            git_uint32 guess = (lower + upper) / 2;
+            PatchNode * p2 = sTempStart + guess;
+            if (p2->address == dest)
+            {
+                git_uint32 * op = constBranch;
+                git_uint32 * by = constBranch + 1;
+
+                // Change the 'const' branch to a 'by' branch.
+                *op = *op - label_jump_const + label_jump_by;
+
+                // Turn the address into a relative offset.
+                *by = ((git_uint32*)gBlockHeader + p2->codeOffset) - (constBranch + 2);
+
+                // And we're done.
+                break;
+            }
+            else if (p2->address > dest)
+                lower = guess + 1;
+            else
+                upper = guess;
+        }
+
+        // Whether we found the branch destination or not,
+        // turn the label into a real opcode.
+        *constBranch = (git_uint32) labelToOpcode (*constBranch);
+    }
+
+    // Convert all the referenced addresses into hash table nodes,
+    // as long as they're not in RAM.
+
+    numNodes = 0;
+    for ( ; sTempStart < sTempEnd ; ++sTempStart)
+    {
+        // 'pc' holds the address of *end* of the instruction,
+        // so we'll use that to determine whether it overlaps
+        // the start of RAM.
+        
+        int isInRAM = (pc > gRamStart);
+        
+        // Set the PC to the start of the instruction, since
+        // that's equal to the end of the previous instruction.
+        
+        pc = sTempStart->address;
+        
+        if (isInRAM && !gCacheRAM)
+            continue;
+
+        // If we're not skipping this instruction, and it's
+        // referenced somewhere, attach it to the hash table.
+                
+        if (sTempStart->u.isReferenced)
+        {
+            HashNode * node = (HashNode*) sCodeTop;
+            sCodeTop = (git_uint32*) (node + 1);
+
+            node->address = sTempStart->address;
+            node->headerOffset = (git_uint32*)gBlockHeader - (git_uint32*)node;
+            node->codeOffset = node->headerOffset + sTempStart->codeOffset;
+
+            node->u.next = gHashTable [node->address & (gHashSize-1)];
+            gHashTable [node->address & (gHashSize-1)] = node;
+
+            ++numNodes;
+        }
+    }
+
+    // Write the block header.
+
+    assert (sCodeTop - (git_uint32*) gBlockHeader < 32767);
+
+    gBlockHeader->numHashNodes = numNodes;
+    gBlockHeader->compiledSize = sCodeTop - (git_uint32*) gBlockHeader;
+    gBlockHeader->glulxSize = endOfBlock - pc;
+    gBlockHeader->runCounter = 0;
+    
+    assert(gBlockHeader->compiledSize > 0);
+
+    // And we're done.
+    return (git_uint32*) (gBlockHeader + 1);
+}
+
+#define END_OF_BLOCK(header) ((void*) (((git_uint32*)header) + header->compiledSize))
+
+static git_uint32 findCutoffPoint ()
+{
+    BlockHeader * start = (BlockHeader*) sCodeStart;
+    BlockHeader * top = (BlockHeader*) sCodeTop;
+    BlockHeader * h;
+
+    git_uint32 blockCount = 0;
+    git_uint32 runCount = 0;
+
+    for (h = start ; h < top ; h = END_OF_BLOCK(h))
+    {
+        if (h->glulxSize > 0)
+        {
+            ++blockCount;
+        }
+    }
+
+    for (h = start ; h < top ; h = END_OF_BLOCK(h))
+    {
+        if (h->glulxSize > 0)
+        {
+            runCount += (h->runCounter + blockCount + 1) / blockCount;
+        }
+    }
+
+    return runCount / 2;
+}
+
+static void compressWithCutoff (git_uint32 cutoff)
+{
+    BlockHeader * start = (BlockHeader*) sCodeStart;
+    BlockHeader * top = (BlockHeader*) sCodeTop;
+    BlockHeader * h = start;
+
+    git_uint32 saveCount = 0;
+    git_uint32 deleteCount = 0;
+
+    sCodeTop = sCodeStart;
+
+    while (h < top)
+    {
+        BlockHeader * next = END_OF_BLOCK(h);
+        if (h->runCounter >= cutoff && h->glulxSize > 0)
+        {
+        	git_uint32 size = h->compiledSize;
+        	
+            // Lower the run count of the saved blocks so that they'll
+            // stick around in the short term, but eventually fall out
+            // of the cache if they're not used much in the future.
+            h->runCounter /= 2;
+ 
+            memmove (sCodeTop, h, size * sizeof(git_uint32));
+            sCodeTop += size;
+            ++saveCount;
+        }
+        else
+        {
+            ++deleteCount;
+        }
+        h = next;
+    }
+}
+
+static void rebuildHashTable ()
+{
+    BlockHeader * start = (BlockHeader*) sCodeStart;
+    BlockHeader * top = (BlockHeader*) sCodeTop;
+    BlockHeader * h;
+
+    memset (gHashTable, 0, gHashSize * sizeof(HashNode*));
+
+    for (h = start ; h < top ; h = END_OF_BLOCK(h))
+    {
+        if (h->glulxSize > 0)
+        {
+            HashNode * node = END_OF_BLOCK(h);
+            git_uint32 i;
+            for (i = 0 ; i < h->numHashNodes ; ++i) 
+            {
+                --node;
+                node->u.next = gHashTable [node->address & (gHashSize-1)];
+                gHashTable [node->address & (gHashSize-1)] = node;
+            }    
+        }
+    }
+}
+
+static void removeHashNode (HashNode* deadNode)
+{
+    HashNode* n = gHashTable [deadNode->address & (gHashSize-1)];
+    assert (deadNode != NULL);
+    
+    if (n == NULL)
+    {
+        // This hash bucket is empty! We have nothing to do.
+    }
+    else if (n == deadNode)
+    {
+        // The node to be removed is the first one in its bucket.        
+        gHashTable [deadNode->address & (gHashSize-1)] = NULL;
+    }
+    else
+    {
+        // The node to be removed is somewhere in the middle
+        // of the bucket. Step along the linked list until
+        // we find it.
+                
+        while (n->u.next != deadNode)
+            n = n->u.next;
+        
+        // Unlink it from the linked list.        
+        n->u.next = deadNode->u.next;
+    }
+}
+
+void pruneCodeCache (git_uint32 address, git_uint32 size)
+{
+    BlockHeader * start = (BlockHeader*) sCodeStart;
+    BlockHeader * top = (BlockHeader*) sCodeTop;
+    BlockHeader * h;
+
+    // Step through the cache, looking for blocks that overlap the
+    // specified range. If we find any, remove their nodes from the
+    // hash table, and set glulxSize to 0 so that they're dropped
+    // the next time we clean up the cache.
+    
+    for (h = start ; h < top ; h = END_OF_BLOCK(h))
+    {
+        // The start address of the block is in its final hash node.
+        
+        HashNode * node = END_OF_BLOCK(h);
+        git_uint32 glulxAddr = node[-1].address;
+        
+        if (glulxAddr < (address + size) && (glulxAddr + h->glulxSize) > address)
+        {
+            // This block overlaps the range of code that has to be pruned.
+            
+            git_uint32 i;
+            for (i = 0 ; i < h->numHashNodes ; ++i) 
+            {
+                --node;
+                removeHashNode (node);
+            }
+    
+            h->glulxSize = 0;
+        }
+    }
+}
+
+void compressCodeCache ()
+{
+    git_uint32 n;
+    git_uint32 spaceUsed, spaceFree;
+    
+    n = findCutoffPoint();
+    compressWithCutoff (n);
+    rebuildHashTable ();
+
+    spaceUsed = sCodeTop - sCodeStart;
+    spaceFree = sBufferSize - spaceUsed - gHashSize;
+
+//    {
+//        char buffer [100];
+//        sprintf (buffer, "[Cache cleanup: %d bytes used, %d free]\n",
+//            spaceUsed * 4, spaceFree * 4);
+//        glk_put_string (buffer);
+//    }
+
+    // If that didn't free up at least a quarter of the cache,
+    // clear it out entirely.
+
+    if (spaceFree * 3 < spaceUsed)
+        resetCodeCache();
+}
+
+void resetCodeCache ()
+{
+//    glk_put_string ("[resetting cache]\n");
+
+    memset (sBuffer, 0, sBufferSize * 4);
+    sCodeStart = sCodeTop = (Block) (gHashTable + gHashSize);
+    sTempStart = sTempEnd = (PatchNode*) (sBuffer + sBufferSize);
+}
+
+Block peekAtEmittedStuff (int numOpcodes)
+{
+    return sCodeTop - numOpcodes;
+}
+
+void emitConstBranch (Label op, git_uint32 address)
+{
+    sPatch->branchOffset = sCodeTop - (git_uint32*)gBlockHeader;
+    emitData (op);
+    emitData (address);
+
+    if (sLastAddr < address)
+        sLastAddr = address;
+}
+
+void emitData (git_uint32 val)
+{
+    abortIfBufferFull ();
+    *sCodeTop++ = val;
+}
+
+extern void emitFinalCode (Label op)
+{
+    abortIfBufferFull ();
+    *sCodeTop++ = (git_uint32) labelToOpcode (op);
+}
+
+extern git_uint32 undoEmit ()
+{
+    return *--sCodeTop;
+}