1 // $Id: compiler.c,v 1.27 2004/12/10 00:37:00 iain Exp $
9 // -------------------------------------------------------------
15 LONGJMP_CACHE_FULL = 1,
16 LONGJMP_BAD_OPCODE = 2
19 // -------------------------------------------------------------
26 BlockHeader * gBlockHeader;
28 const char * gLabelNames [] = {
29 #define LABEL(label) #label,
34 HashNode ** gHashTable; // Hash table of glulx address -> code.
35 git_uint32 gHashSize; // Number of slots in the hash table.
37 // -------------------------------------------------------------
40 typedef struct PatchNode
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.
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.
52 // -------------------------------------------------------------
55 static git_uint32 * sBuffer; // The buffer where everything is stored.
56 static git_uint32 sBufferSize; // Size of the buffer, in 4-byte words.
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.
63 static jmp_buf sJumpBuf; // setjmp buffer, used to abort compilation when the buffer is full.
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;
70 static int sNextInstructionIsReferenced;
71 static git_uint32 sLastAddr;
73 // -------------------------------------------------------------
76 void initCompiler (size_t size)
78 static BlockHeader dummyHeader;
79 gBlockHeader = &dummyHeader;
81 // Make sure various assumptions we're making are correct.
83 assert (sizeof(HashNode) <= sizeof(PatchNode));
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.
89 sBuffer = malloc (size);
91 fatalError ("Couldn't allocate code cache");
93 memset (sBuffer, 0, size);
94 sBufferSize = size / 4;
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.)
102 while (gHashSize < (sBufferSize / 20))
105 // The hash table is stored at the beginning of the buffer,
106 // and the rest is used for code and temporary storage.
108 gHashTable = (HashNode**) sBuffer;
110 sCodeStart = sCodeTop = (Block) (gHashTable + gHashSize);
111 sTempStart = sTempEnd = (PatchNode*) (sBuffer + sBufferSize);
114 void shutdownCompiler ()
119 sCodeStart = sCodeTop = NULL;
120 sTempStart = sTempEnd = NULL;
126 static void abortIfBufferFull ()
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.
132 if ((void*) (sCodeTop + 2) >= (void*) sTempStart)
133 longjmp (sJumpBuf, LONGJMP_CACHE_FULL);
136 void abortCompilation ()
138 longjmp (sJumpBuf, LONGJMP_BAD_OPCODE);
141 void nextInstructionIsReferenced ()
143 sNextInstructionIsReferenced = 1;
146 Block compile (git_uint32 pc)
148 git_uint32 endOfBlock;
151 // Make sure we have enough room for, at a minimum:
152 // - the block header
154 // - one jumpabs instruction (two words).
156 int spaceNeeded = (sizeof(BlockHeader) + sizeof(PatchNode) + 8) / 4;
157 if ((void*) (sCodeTop + spaceNeeded) >= (void*) sTempStart)
162 // Emit the header for this block.
164 gBlockHeader = (BlockHeader*) sCodeTop;
165 sCodeTop = (git_uint32*) (gBlockHeader + 1);
168 sNextInstructionIsReferenced = 1;
169 resetPeepholeOptimiser();
173 i = setjmp (sJumpBuf);
174 if (i == LONGJMP_NO_ERROR)
176 git_uint32 patchSize = 0;
177 git_uint32 codeSize = 0;
183 // If we don't have room for more code, abort.
184 if ((void*) (sCodeTop + 2) >= (void*) (sTempStart - 1))
186 longjmp (sJumpBuf, LONGJMP_CACHE_FULL);
189 // Create a temporary patch node for this instruction.
192 sPatch->address = pc;
193 sPatch->codeOffset = sCodeTop - (git_uint32*)gBlockHeader;
194 sPatch->branchOffset = 0;
195 sPatch->u.isReferenced = sNextInstructionIsReferenced;
197 sNextInstructionIsReferenced = 0;
199 // Make sure we haven't generated over 32K of code.
201 patchSize += sizeof(PatchNode) / 4;
202 codeSize = sCodeTop - (git_uint32*)gBlockHeader;
204 if (codeSize + patchSize > 32000)
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);
212 // Parse the next instruction.
214 parseInstruction (&pc, &done);
222 // Compilation was aborted, but we should have a
223 // patch node and at least two words of space free.
225 assert (sPatch != NULL);
226 sPatch->branchOffset = 0; // Make sure the patch isn't treated as a branch.
228 sCodeTop = ((git_uint32*)gBlockHeader) + sPatch->codeOffset;
230 if (i == LONGJMP_CACHE_FULL)
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.
236 *sCodeTop++ = (git_uint32) labelToOpcode (label_recompile);
237 *sCodeTop++ = sPatch->address;
239 // Make sure this node doesn't get put into the hash table.
240 sPatch->u.isReferenced = 0;
242 else if (i == LONGJMP_BAD_OPCODE)
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.
248 *sCodeTop++ = (git_uint32) labelToOpcode (label_error_bad_opcode);
249 *sCodeTop++ = sPatch->address;
253 fatalError ("unknown error in compile (BUG)");
257 assert ((void*) sCodeTop <= (void*) sTempStart);
259 // We now know where the block ends.
263 // Fix up the constant branches.
265 numNodes = sTempEnd - sTempStart;
266 for (i = 0 ; i < numNodes ; ++i)
268 git_uint32* constBranch;
271 git_uint32 lower = 0;
272 git_uint32 upper = numNodes;
274 PatchNode * p = sTempStart + i;
275 if (p->branchOffset == 0)
278 constBranch = ((git_uint32*)gBlockHeader) + p->branchOffset;
279 dest = constBranch [1];
280 while (upper > lower)
282 git_uint32 guess = (lower + upper) / 2;
283 PatchNode * p2 = sTempStart + guess;
284 if (p2->address == dest)
286 git_uint32 * op = constBranch;
287 git_uint32 * by = constBranch + 1;
289 // Change the 'const' branch to a 'by' branch.
290 *op = *op - label_jump_const + label_jump_by;
292 // Turn the address into a relative offset.
293 *by = ((git_uint32*)gBlockHeader + p2->codeOffset) - (constBranch + 2);
298 else if (p2->address > dest)
304 // Whether we found the branch destination or not,
305 // turn the label into a real opcode.
306 *constBranch = (git_uint32) labelToOpcode (*constBranch);
309 // Convert all the referenced addresses into hash table nodes,
310 // as long as they're not in RAM.
313 for ( ; sTempStart < sTempEnd ; ++sTempStart)
315 // 'pc' holds the address of *end* of the instruction,
316 // so we'll use that to determine whether it overlaps
319 int isInRAM = (pc > gRamStart);
321 // Set the PC to the start of the instruction, since
322 // that's equal to the end of the previous instruction.
324 pc = sTempStart->address;
326 if (isInRAM && !gCacheRAM)
329 // If we're not skipping this instruction, and it's
330 // referenced somewhere, attach it to the hash table.
332 if (sTempStart->u.isReferenced)
334 HashNode * node = (HashNode*) sCodeTop;
335 sCodeTop = (git_uint32*) (node + 1);
337 node->address = sTempStart->address;
338 node->headerOffset = (git_uint32*)gBlockHeader - (git_uint32*)node;
339 node->codeOffset = node->headerOffset + sTempStart->codeOffset;
341 node->u.next = gHashTable [node->address & (gHashSize-1)];
342 gHashTable [node->address & (gHashSize-1)] = node;
348 // Write the block header.
350 assert (sCodeTop - (git_uint32*) gBlockHeader < 32767);
352 gBlockHeader->numHashNodes = numNodes;
353 gBlockHeader->compiledSize = sCodeTop - (git_uint32*) gBlockHeader;
354 gBlockHeader->glulxSize = endOfBlock - pc;
355 gBlockHeader->runCounter = 0;
357 assert(gBlockHeader->compiledSize > 0);
360 return (git_uint32*) (gBlockHeader + 1);
363 #define END_OF_BLOCK(header) ((void*) (((git_uint32*)header) + header->compiledSize))
365 static git_uint32 findCutoffPoint ()
367 BlockHeader * start = (BlockHeader*) sCodeStart;
368 BlockHeader * top = (BlockHeader*) sCodeTop;
371 git_uint32 blockCount = 0;
372 git_uint32 runCount = 0;
374 for (h = start ; h < top ; h = END_OF_BLOCK(h))
376 if (h->glulxSize > 0)
382 for (h = start ; h < top ; h = END_OF_BLOCK(h))
384 if (h->glulxSize > 0)
386 runCount += (h->runCounter + blockCount + 1) / blockCount;
393 static void compressWithCutoff (git_uint32 cutoff)
395 BlockHeader * start = (BlockHeader*) sCodeStart;
396 BlockHeader * top = (BlockHeader*) sCodeTop;
397 BlockHeader * h = start;
399 git_uint32 saveCount = 0;
400 git_uint32 deleteCount = 0;
402 sCodeTop = sCodeStart;
406 BlockHeader * next = END_OF_BLOCK(h);
407 if (h->runCounter >= cutoff && h->glulxSize > 0)
409 git_uint32 size = h->compiledSize;
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.
416 memmove (sCodeTop, h, size * sizeof(git_uint32));
428 static void rebuildHashTable ()
430 BlockHeader * start = (BlockHeader*) sCodeStart;
431 BlockHeader * top = (BlockHeader*) sCodeTop;
434 memset (gHashTable, 0, gHashSize * sizeof(HashNode*));
436 for (h = start ; h < top ; h = END_OF_BLOCK(h))
438 if (h->glulxSize > 0)
440 HashNode * node = END_OF_BLOCK(h);
442 for (i = 0 ; i < h->numHashNodes ; ++i)
445 node->u.next = gHashTable [node->address & (gHashSize-1)];
446 gHashTable [node->address & (gHashSize-1)] = node;
452 static void removeHashNode (HashNode* deadNode)
454 HashNode* n = gHashTable [deadNode->address & (gHashSize-1)];
455 assert (deadNode != NULL);
459 // This hash bucket is empty! We have nothing to do.
461 else if (n == deadNode)
463 // The node to be removed is the first one in its bucket.
464 gHashTable [deadNode->address & (gHashSize-1)] = NULL;
468 // The node to be removed is somewhere in the middle
469 // of the bucket. Step along the linked list until
472 while (n->u.next != deadNode)
475 // Unlink it from the linked list.
476 n->u.next = deadNode->u.next;
480 void pruneCodeCache (git_uint32 address, git_uint32 size)
482 BlockHeader * start = (BlockHeader*) sCodeStart;
483 BlockHeader * top = (BlockHeader*) sCodeTop;
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.
491 for (h = start ; h < top ; h = END_OF_BLOCK(h))
493 // The start address of the block is in its final hash node.
495 HashNode * node = END_OF_BLOCK(h);
496 git_uint32 glulxAddr = node[-1].address;
498 if (glulxAddr < (address + size) && (glulxAddr + h->glulxSize) > address)
500 // This block overlaps the range of code that has to be pruned.
503 for (i = 0 ; i < h->numHashNodes ; ++i)
506 removeHashNode (node);
514 void compressCodeCache ()
517 git_uint32 spaceUsed, spaceFree;
519 n = findCutoffPoint();
520 compressWithCutoff (n);
523 spaceUsed = sCodeTop - sCodeStart;
524 spaceFree = sBufferSize - spaceUsed - gHashSize;
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);
533 // If that didn't free up at least a quarter of the cache,
534 // clear it out entirely.
536 if (spaceFree * 3 < spaceUsed)
540 void resetCodeCache ()
542 // glk_put_string ("[resetting cache]\n");
544 memset (sBuffer, 0, sBufferSize * 4);
545 sCodeStart = sCodeTop = (Block) (gHashTable + gHashSize);
546 sTempStart = sTempEnd = (PatchNode*) (sBuffer + sBufferSize);
549 Block peekAtEmittedStuff (int numOpcodes)
551 return sCodeTop - numOpcodes;
554 void emitConstBranch (Label op, git_uint32 address)
556 sPatch->branchOffset = sCodeTop - (git_uint32*)gBlockHeader;
560 if (sLastAddr < address)
564 void emitData (git_uint32 val)
566 abortIfBufferFull ();
570 extern void emitFinalCode (Label op)
572 abortIfBufferFull ();
573 *sCodeTop++ = (git_uint32) labelToOpcode (op);
576 extern git_uint32 undoEmit ()