interpreters/git/compiler.c

   1 // $Id: compiler.c,v 1.27 2004/12/10 00:37:00 iain Exp $
   2
   3 #include "git.h"
   4 #include <assert.h>
   5 #include <stdlib.h>
   6 #include <setjmp.h>
   7 #include <string.h>
   8
   9 // -------------------------------------------------------------
  10 // Constants
  11
  12 enum
  13 {
  14     LONGJMP_NO_ERROR = 0,
  15     LONGJMP_CACHE_FULL = 1,
  16     LONGJMP_BAD_OPCODE = 2
  17 };
  18
  19 // -------------------------------------------------------------
  20 // Globals
  21
  22 int gPeephole = 1;
  23 int gDebug = 0;
  24 int gCacheRAM = 0;
  25
  26 BlockHeader * gBlockHeader;
  27
  28 const char * gLabelNames [] = {
  29 #define LABEL(label) #label,
  30 #include "labels.inc"
  31     NULL
  32 };
  33
  34 HashNode ** gHashTable; // Hash table of glulx address -> code.
  35 git_uint32 gHashSize;   // Number of slots in the hash table.
  36
  37 // -------------------------------------------------------------
  38 // Types.
  39
  40 typedef struct PatchNode
  41 {
  42     git_uint32 address;       // The glulx address of this instruction.
  43     git_sint16 codeOffset;    // Offset from the block header to the compiled code for this instruction.
  44     git_sint16 branchOffset;  // If non-zero, offset to a branch opcode followed by a glulx address.
  45     union {
  46         int isReferenced;     // Set to TRUE if this can be the destination of a jump.
  47         HashNode* pad;        // This pad assures that PatchNode and HashNode are the same size.
  48     } u;
  49 }
  50 PatchNode;
  51
  52 // -------------------------------------------------------------
  53 // Static variables.
  54
  55 static git_uint32 * sBuffer;   // The buffer where everything is stored.
  56 static git_uint32 sBufferSize; // Size of the buffer, in 4-byte words.
  57
  58 static Block       sCodeStart; // Start of code cache.
  59 static Block       sCodeTop;   // Next free space in code cache.
  60 static PatchNode*  sTempStart; // Start of temporary storage.
  61 static PatchNode*  sTempEnd;   // End of temporary storage.
  62
  63 static jmp_buf sJumpBuf; // setjmp buffer, used to abort compilation when the buffer is full.
  64
  65 // This is the patch node for the opcode currently being compiled.
  66 // The 'address' and 'code' fields will be filled in. The other
  67 // fields can be updated during compilation as necessary.
  68 static PatchNode * sPatch;
  69
  70 static int sNextInstructionIsReferenced;
  71 static git_uint32 sLastAddr;
  72
  73 // -------------------------------------------------------------
  74 // Functions
  75
  76 void initCompiler (size_t size)
  77 {
  78     static BlockHeader dummyHeader;
  79     gBlockHeader = &dummyHeader;
  80
  81     // Make sure various assumptions we're making are correct.
  82
  83     assert (sizeof(HashNode) <= sizeof(PatchNode));
  84
  85     // Allocate the buffer. As far as possible, we're going to
  86     // use this buffer for everything compiler-related, and
  87     // avoid further dynamic allocation.
  88
  89     sBuffer = malloc (size);
  90     if (sBuffer == NULL)
  91         fatalError ("Couldn't allocate code cache");
  92
  93     memset (sBuffer, 0, size);
  94     sBufferSize = size / 4;
  95
  96     // Pick a reasonable size for the hash table. This should be
  97     // a power of two, and take up about a tenth of the buffer.
  98     // (If the buffer is itself a power of two in size, the hash
  99     // table will take up a sixteenth of it, which is fine.)
 100
 101     gHashSize = 1;
 102     while (gHashSize < (sBufferSize / 20))
 103         gHashSize *= 2;
 104
 105     // The hash table is stored at the beginning of the buffer,
 106     // and the rest is used for code and temporary storage.
 107
 108     gHashTable = (HashNode**) sBuffer;
 109
 110     sCodeStart = sCodeTop = (Block) (gHashTable + gHashSize);
 111     sTempStart = sTempEnd = (PatchNode*) (sBuffer + sBufferSize);
 112 }
 113
 114 void shutdownCompiler ()
 115 {
 116     free (sBuffer);
 117
 118     sBuffer = NULL;
 119     sCodeStart = sCodeTop = NULL;
 120     sTempStart = sTempEnd = NULL;
 121
 122     gHashTable = NULL;
 123     gBlockHeader = NULL;
 124 }
 125
 126 static void abortIfBufferFull ()
 127 {
 128     // Make sure we have at least two words free,
 129     // because we'll need them to store a jumpabs
 130     // instruction at the very end of the buffer.
 131
 132     if ((void*) (sCodeTop + 2) >= (void*) sTempStart)
 133         longjmp (sJumpBuf, LONGJMP_CACHE_FULL);
 134 }
 135
 136 void abortCompilation ()
 137 {
 138     longjmp (sJumpBuf, LONGJMP_BAD_OPCODE);
 139 }
 140
 141 void nextInstructionIsReferenced ()
 142 {
 143     sNextInstructionIsReferenced = 1;
 144 }
 145
 146 Block compile (git_uint32 pc)
 147 {
 148     git_uint32 endOfBlock;
 149     int i, numNodes;
 150
 151     // Make sure we have enough room for, at a minimum:
 152     // - the block header
 153     // - one patch node
 154     // - one jumpabs instruction (two words).
 155
 156     int spaceNeeded = (sizeof(BlockHeader) + sizeof(PatchNode) + 8) / 4;
 157     if ((void*) (sCodeTop + spaceNeeded) >= (void*) sTempStart)
 158     {
 159         compressCodeCache();
 160     }
 161
 162     // Emit the header for this block.
 163
 164     gBlockHeader = (BlockHeader*) sCodeTop;
 165     sCodeTop = (git_uint32*) (gBlockHeader + 1);
 166
 167     sLastAddr = 0;
 168     sNextInstructionIsReferenced = 1;
 169     resetPeepholeOptimiser();
 170
 171     sPatch = NULL;
 172
 173     i = setjmp (sJumpBuf);
 174     if (i == LONGJMP_NO_ERROR)
 175     {
 176         git_uint32 patchSize = 0;
 177         git_uint32 codeSize = 0;
 178
 179         int done = 0;
 180
 181         while (!done)
 182         {
 183                 // If we don't have room for more code, abort.
 184                         if ((void*) (sCodeTop + 2) >= (void*) (sTempStart - 1))
 185                         {
 186                                 longjmp (sJumpBuf, LONGJMP_CACHE_FULL);
 187                         }
 188
 189             // Create a temporary patch node for this instruction.
 190             --sTempStart;
 191             sPatch = sTempStart;
 192             sPatch->address = pc;
 193             sPatch->codeOffset = sCodeTop - (git_uint32*)gBlockHeader;
 194             sPatch->branchOffset = 0;
 195             sPatch->u.isReferenced = sNextInstructionIsReferenced;
 196
 197             sNextInstructionIsReferenced = 0;
 198
 199             // Make sure we haven't generated over 32K of code.
 200
 201             patchSize += sizeof(PatchNode) / 4;
 202             codeSize = sCodeTop - (git_uint32*)gBlockHeader;
 203
 204             if (codeSize + patchSize > 32000)
 205             {
 206                 // We've generated almost 32K words of code, which will
 207                 // start to cause problems for the 16-bit offsets we use
 208                 // in the hash nodes, so let's just stop here.
 209                 longjmp (sJumpBuf, LONGJMP_CACHE_FULL);
 210             }
 211
 212             // Parse the next instruction.
 213
 214             parseInstruction (&pc, &done);
 215
 216             if (pc < sLastAddr)
 217                 done = 0;
 218         }
 219     }
 220     else
 221     {
 222         // Compilation was aborted, but we should have a
 223         // patch node and at least two words of space free.
 224
 225         assert (sPatch != NULL);
 226         sPatch->branchOffset = 0; // Make sure the patch isn't treated as a branch.
 227
 228         sCodeTop = ((git_uint32*)gBlockHeader) + sPatch->codeOffset;
 229
 230         if (i == LONGJMP_CACHE_FULL)
 231         {
 232             // The buffer is full. We'll replace the partially-compiled
 233             // instruction with a jumpabs, forcing another cache lookup
 234             // when the terp hits this point in the code.
 235
 236             *sCodeTop++ = (git_uint32) labelToOpcode (label_recompile);
 237             *sCodeTop++ = sPatch->address;
 238
 239             // Make sure this node doesn't get put into the hash table.
 240             sPatch->u.isReferenced = 0;
 241         }
 242         else if (i == LONGJMP_BAD_OPCODE)
 243         {
 244             // We found a badly-formed instruction. We'll replace the
 245             // partially-compiled instruction with a label that raises
 246             // an error if the terp hits this code location.
 247
 248             *sCodeTop++ = (git_uint32) labelToOpcode (label_error_bad_opcode);
 249             *sCodeTop++ = sPatch->address;
 250         }
 251         else
 252         {
 253             fatalError ("unknown error in compile (BUG)");
 254         }
 255     }
 256
 257     assert ((void*) sCodeTop <= (void*) sTempStart);
 258
 259     // We now know where the block ends.
 260
 261     endOfBlock = pc;
 262
 263     // Fix up the constant branches.
 264
 265     numNodes = sTempEnd - sTempStart;
 266     for (i = 0 ; i < numNodes ; ++i)
 267     {
 268         git_uint32* constBranch;
 269
 270         git_uint32 dest;
 271         git_uint32 lower = 0;
 272         git_uint32 upper = numNodes;
 273
 274         PatchNode * p = sTempStart + i;
 275         if (p->branchOffset == 0)
 276             continue;
 277
 278         constBranch = ((git_uint32*)gBlockHeader) + p->branchOffset;
 279         dest = constBranch [1];
 280         while (upper > lower)
 281         {
 282             git_uint32 guess = (lower + upper) / 2;
 283             PatchNode * p2 = sTempStart + guess;
 284             if (p2->address == dest)
 285             {
 286                 git_uint32 * op = constBranch;
 287                 git_uint32 * by = constBranch + 1;
 288
 289                 // Change the 'const' branch to a 'by' branch.
 290                 *op = *op - label_jump_const + label_jump_by;
 291
 292                 // Turn the address into a relative offset.
 293                 *by = ((git_uint32*)gBlockHeader + p2->codeOffset) - (constBranch + 2);
 294
 295                 // And we're done.
 296                 break;
 297             }
 298             else if (p2->address > dest)
 299                 lower = guess + 1;
 300             else
 301                 upper = guess;
 302         }
 303
 304         // Whether we found the branch destination or not,
 305         // turn the label into a real opcode.
 306         *constBranch = (git_uint32) labelToOpcode (*constBranch);
 307     }
 308
 309     // Convert all the referenced addresses into hash table nodes,
 310     // as long as they're not in RAM.
 311
 312     numNodes = 0;
 313     for ( ; sTempStart < sTempEnd ; ++sTempStart)
 314     {
 315         // 'pc' holds the address of *end* of the instruction,
 316         // so we'll use that to determine whether it overlaps
 317         // the start of RAM.
 318
 319         int isInRAM = (pc > gRamStart);
 320
 321         // Set the PC to the start of the instruction, since
 322         // that's equal to the end of the previous instruction.
 323
 324         pc = sTempStart->address;
 325
 326         if (isInRAM && !gCacheRAM)
 327             continue;
 328
 329         // If we're not skipping this instruction, and it's
 330         // referenced somewhere, attach it to the hash table.
 331
 332         if (sTempStart->u.isReferenced)
 333         {
 334             HashNode * node = (HashNode*) sCodeTop;
 335             sCodeTop = (git_uint32*) (node + 1);
 336
 337             node->address = sTempStart->address;
 338             node->headerOffset = (git_uint32*)gBlockHeader - (git_uint32*)node;
 339             node->codeOffset = node->headerOffset + sTempStart->codeOffset;
 340
 341             node->u.next = gHashTable [node->address & (gHashSize-1)];
 342             gHashTable [node->address & (gHashSize-1)] = node;
 343
 344             ++numNodes;
 345         }
 346     }
 347
 348     // Write the block header.
 349
 350     assert (sCodeTop - (git_uint32*) gBlockHeader < 32767);
 351
 352     gBlockHeader->numHashNodes = numNodes;
 353     gBlockHeader->compiledSize = sCodeTop - (git_uint32*) gBlockHeader;
 354     gBlockHeader->glulxSize = endOfBlock - pc;
 355     gBlockHeader->runCounter = 0;
 356
 357     assert(gBlockHeader->compiledSize > 0);
 358
 359     // And we're done.
 360     return (git_uint32*) (gBlockHeader + 1);
 361 }
 362
 363 #define END_OF_BLOCK(header) ((void*) (((git_uint32*)header) + header->compiledSize))
 364
 365 static git_uint32 findCutoffPoint ()
 366 {
 367     BlockHeader * start = (BlockHeader*) sCodeStart;
 368     BlockHeader * top = (BlockHeader*) sCodeTop;
 369     BlockHeader * h;
 370
 371     git_uint32 blockCount = 0;
 372     git_uint32 runCount = 0;
 373
 374     for (h = start ; h < top ; h = END_OF_BLOCK(h))
 375     {
 376         if (h->glulxSize > 0)
 377         {
 378             ++blockCount;
 379         }
 380     }
 381
 382     for (h = start ; h < top ; h = END_OF_BLOCK(h))
 383     {
 384         if (h->glulxSize > 0)
 385         {
 386             runCount += (h->runCounter + blockCount + 1) / blockCount;
 387         }
 388     }
 389
 390     return runCount / 2;
 391 }
 392
 393 static void compressWithCutoff (git_uint32 cutoff)
 394 {
 395     BlockHeader * start = (BlockHeader*) sCodeStart;
 396     BlockHeader * top = (BlockHeader*) sCodeTop;
 397     BlockHeader * h = start;
 398
 399     git_uint32 saveCount = 0;
 400     git_uint32 deleteCount = 0;
 401
 402     sCodeTop = sCodeStart;
 403
 404     while (h < top)
 405     {
 406         BlockHeader * next = END_OF_BLOCK(h);
 407         if (h->runCounter >= cutoff && h->glulxSize > 0)
 408         {
 409                 git_uint32 size = h->compiledSize;
 410
 411             // Lower the run count of the saved blocks so that they'll
 412             // stick around in the short term, but eventually fall out
 413             // of the cache if they're not used much in the future.
 414             h->runCounter /= 2;
 415
 416             memmove (sCodeTop, h, size * sizeof(git_uint32));
 417             sCodeTop += size;
 418             ++saveCount;
 419         }
 420         else
 421         {
 422             ++deleteCount;
 423         }
 424         h = next;
 425     }
 426 }
 427
 428 static void rebuildHashTable ()
 429 {
 430     BlockHeader * start = (BlockHeader*) sCodeStart;
 431     BlockHeader * top = (BlockHeader*) sCodeTop;
 432     BlockHeader * h;
 433
 434     memset (gHashTable, 0, gHashSize * sizeof(HashNode*));
 435
 436     for (h = start ; h < top ; h = END_OF_BLOCK(h))
 437     {
 438         if (h->glulxSize > 0)
 439         {
 440             HashNode * node = END_OF_BLOCK(h);
 441             git_uint32 i;
 442             for (i = 0 ; i < h->numHashNodes ; ++i)
 443             {
 444                 --node;
 445                 node->u.next = gHashTable [node->address & (gHashSize-1)];
 446                 gHashTable [node->address & (gHashSize-1)] = node;
 447             }
 448         }
 449     }
 450 }
 451
 452 static void removeHashNode (HashNode* deadNode)
 453 {
 454     HashNode* n = gHashTable [deadNode->address & (gHashSize-1)];
 455     assert (deadNode != NULL);
 456
 457     if (n == NULL)
 458     {
 459         // This hash bucket is empty! We have nothing to do.
 460     }
 461     else if (n == deadNode)
 462     {
 463         // The node to be removed is the first one in its bucket.
 464         gHashTable [deadNode->address & (gHashSize-1)] = NULL;
 465     }
 466     else
 467     {
 468         // The node to be removed is somewhere in the middle
 469         // of the bucket. Step along the linked list until
 470         // we find it.
 471
 472         while (n->u.next != deadNode)
 473             n = n->u.next;
 474
 475         // Unlink it from the linked list.
 476         n->u.next = deadNode->u.next;
 477     }
 478 }
 479
 480 void pruneCodeCache (git_uint32 address, git_uint32 size)
 481 {
 482     BlockHeader * start = (BlockHeader*) sCodeStart;
 483     BlockHeader * top = (BlockHeader*) sCodeTop;
 484     BlockHeader * h;
 485
 486     // Step through the cache, looking for blocks that overlap the
 487     // specified range. If we find any, remove their nodes from the
 488     // hash table, and set glulxSize to 0 so that they're dropped
 489     // the next time we clean up the cache.
 490
 491     for (h = start ; h < top ; h = END_OF_BLOCK(h))
 492     {
 493         // The start address of the block is in its final hash node.
 494
 495         HashNode * node = END_OF_BLOCK(h);
 496         git_uint32 glulxAddr = node[-1].address;
 497
 498         if (glulxAddr < (address + size) && (glulxAddr + h->glulxSize) > address)
 499         {
 500             // This block overlaps the range of code that has to be pruned.
 501
 502             git_uint32 i;
 503             for (i = 0 ; i < h->numHashNodes ; ++i)
 504             {
 505                 --node;
 506                 removeHashNode (node);
 507             }
 508
 509             h->glulxSize = 0;
 510         }
 511     }
 512 }
 513
 514 void compressCodeCache ()
 515 {
 516     git_uint32 n;
 517     git_uint32 spaceUsed, spaceFree;
 518
 519     n = findCutoffPoint();
 520     compressWithCutoff (n);
 521     rebuildHashTable ();
 522
 523     spaceUsed = sCodeTop - sCodeStart;
 524     spaceFree = sBufferSize - spaceUsed - gHashSize;
 525
 526 //    {
 527 //        char buffer [100];
 528 //        sprintf (buffer, "[Cache cleanup: %d bytes used, %d free]\n",
 529 //            spaceUsed * 4, spaceFree * 4);
 530 //        glk_put_string (buffer);
 531 //    }
 532
 533     // If that didn't free up at least a quarter of the cache,
 534     // clear it out entirely.
 535
 536     if (spaceFree * 3 < spaceUsed)
 537         resetCodeCache();
 538 }
 539
 540 void resetCodeCache ()
 541 {
 542 //    glk_put_string ("[resetting cache]\n");
 543
 544     memset (sBuffer, 0, sBufferSize * 4);
 545     sCodeStart = sCodeTop = (Block) (gHashTable + gHashSize);
 546     sTempStart = sTempEnd = (PatchNode*) (sBuffer + sBufferSize);
 547 }
 548
 549 Block peekAtEmittedStuff (int numOpcodes)
 550 {
 551     return sCodeTop - numOpcodes;
 552 }
 553
 554 void emitConstBranch (Label op, git_uint32 address)
 555 {
 556     sPatch->branchOffset = sCodeTop - (git_uint32*)gBlockHeader;
 557     emitData (op);
 558     emitData (address);
 559
 560     if (sLastAddr < address)
 561         sLastAddr = address;
 562 }
 563
 564 void emitData (git_uint32 val)
 565 {
 566     abortIfBufferFull ();
 567     *sCodeTop++ = val;
 568 }
 569
 570 extern void emitFinalCode (Label op)
 571 {
 572     abortIfBufferFull ();
 573     *sCodeTop++ = (git_uint32) labelToOpcode (op);
 574 }
 575
 576 extern git_uint32 undoEmit ()
 577 {
 578     return *--sCodeTop;
 579 }