Add Glulxe and Git. They compile but don't work yet.
[rodin/chimara.git] / 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 }