Significantly revamp allocation of machine code to use free lists, real

allocation policies and much more.  All this complexity, and we have no
functionality change, woo! :)


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@28225 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 340 insertions, 51 deletions

diff --git a/lib/ExecutionEngine/JIT/JITEmitter.cpp b/lib/ExecutionEngine/JIT/JITEmitter.cpp
index 704fa80..d61d258 100644
--- a/lib/ExecutionEngine/JIT/JITEmitter.cpp
+++ b/lib/ExecutionEngine/JIT/JITEmitter.cpp
@@ -44,6 +44,203 @@ namespace {
 // JITMemoryManager code.
 //
 namespace {
+  /// MemoryRangeHeader - For a range of memory, this is the header that we put
+  /// on the block of memory.  It is carefully crafted to be one word of memory.
+  /// Allocated blocks have just this header, free'd blocks have FreeRangeHeader
+  /// which starts with this.
+  struct FreeRangeHeader;
+  struct MemoryRangeHeader {
+    /// ThisAllocated - This is true if this block is currently allocated.  If
+    /// not, this can be converted to a FreeRangeHeader.
+    intptr_t ThisAllocated : 1;
+    
+    /// PrevAllocated - Keep track of whether the block immediately before us is
+    /// allocated.  If not, the word immediately before this header is the size
+    /// of the previous block.
+    intptr_t PrevAllocated : 1;
+    
+    /// BlockSize - This is the size in bytes of this memory block,
+    /// including this header.
+    uintptr_t BlockSize : (sizeof(intptr_t)*8 - 2);
+    
+
+    /// getBlockAfter - Return the memory block immediately after this one.
+    ///
+    MemoryRangeHeader &getBlockAfter() const {
+      return *(MemoryRangeHeader*)((char*)this+BlockSize);
+    }
+    
+    /// getFreeBlockBefore - If the block before this one is free, return it,
+    /// otherwise return null.
+    FreeRangeHeader *getFreeBlockBefore() const {
+      if (PrevAllocated) return 0;
+      intptr_t PrevSize = ((intptr_t *)this)[-1];
+      return (FreeRangeHeader*)((char*)this-PrevSize);
+    }
+    
+    /// MakeFreeBlock - Turn an allocated block into a free block, adjusting
+    /// bits in the object headers, and adding an end of region memory block.
+    FreeRangeHeader &MakeFreeBlock(FreeRangeHeader *FreeList);
+    
+    /// TrimAllocationToSize - If this allocated block is significantly larger
+    /// than NewSize, split it into two pieces (where the former is NewSize
+    /// bytes, including the header), and add the new block to the free list.
+    FreeRangeHeader *TrimAllocationToSize(FreeRangeHeader *FreeList, 
+                                          uint64_t NewSize);
+  };
+
+  /// FreeRangeHeader - For a memory block that isn't already allocated, this
+  /// keeps track of the current block and has a pointer to the next free block.
+  /// Free blocks are kept on a circularly linked list.
+  struct FreeRangeHeader : public MemoryRangeHeader {
+    FreeRangeHeader *Prev;
+    FreeRangeHeader *Next;
+    
+    /// getMinBlockSize - Get the minimum size for a memory block.  Blocks
+    /// smaller than this size cannot be created.
+    static unsigned getMinBlockSize() {
+      return sizeof(FreeRangeHeader)+sizeof(intptr_t);
+    }
+    
+    /// SetEndOfBlockSizeMarker - The word at the end of every free block is
+    /// known to be the size of the free block.  Set it for this block.
+    void SetEndOfBlockSizeMarker() {
+      void *EndOfBlock = (char*)this + BlockSize;
+      ((intptr_t *)EndOfBlock)[-1] = BlockSize;
+    }
+
+    FreeRangeHeader *RemoveFromFreeList() {
+      assert(Next->Prev == this && Prev->Next == this && "Freelist broken!");
+      Next->Prev = Prev;
+      return Prev->Next = Next;
+    }
+    
+    void AddToFreeList(FreeRangeHeader *FreeList) {
+      Next = FreeList;
+      Prev = FreeList->Prev;
+      Prev->Next = this;
+      Next->Prev = this;
+    }
+
+    /// GrowBlock - The block after this block just got deallocated.  Merge it
+    /// into the current block.
+    void GrowBlock(uintptr_t NewSize);
+    
+    /// AllocateBlock - Mark this entire block allocated, updating freelists
+    /// etc.  This returns a pointer to the circular free-list.
+    FreeRangeHeader *AllocateBlock();
+  };
+}
+
+
+/// AllocateBlock - Mark this entire block allocated, updating freelists
+/// etc.  This returns a pointer to the circular free-list.
+FreeRangeHeader *FreeRangeHeader::AllocateBlock() {
+  assert(!ThisAllocated && !getBlockAfter().PrevAllocated &&
+         "Cannot allocate an allocated block!");
+  // Mark this block allocated.
+  ThisAllocated = 1;
+  getBlockAfter().PrevAllocated = 1;
+ 
+  // Remove it from the free list.
+  return RemoveFromFreeList();
+}
+
+/// MakeFreeBlock - Turn an allocated block into a free block, adjusting
+/// bits in the object headers, and adding an end of region memory block.
+/// If possible, coallesce this block with neighboring blocks.  Return the
+/// FreeRangeHeader this block ends up in, which may be != this if it got
+/// coallesced.
+FreeRangeHeader &MemoryRangeHeader::MakeFreeBlock(FreeRangeHeader *FreeList) {
+  MemoryRangeHeader *FollowingBlock = &getBlockAfter();
+  assert(ThisAllocated && "This block is already allocated!");
+  assert(FollowingBlock->PrevAllocated && "Flags out of sync!");
+  
+  // If the block after this one is free, merge it into this block.
+  if (!FollowingBlock->ThisAllocated) {
+    FreeRangeHeader &FollowingFreeBlock = *(FreeRangeHeader *)FollowingBlock;
+    FollowingFreeBlock.RemoveFromFreeList();
+    
+    // Include the following block into this one.
+    BlockSize += FollowingFreeBlock.BlockSize;
+    FollowingBlock = &FollowingFreeBlock.getBlockAfter();
+    
+    // Tell the block after the block we are coallescing that this block is
+    // allocated.
+    FollowingBlock->PrevAllocated = 1;
+  }
+  
+  assert(FollowingBlock->ThisAllocated && "Missed coallescing?");
+  
+  if (FreeRangeHeader *PrevFreeBlock = getFreeBlockBefore()) {
+    PrevFreeBlock->GrowBlock(PrevFreeBlock->BlockSize + BlockSize);
+    return *PrevFreeBlock;
+  }
+
+  // Otherwise, mark this block free.
+  FreeRangeHeader &FreeBlock = *(FreeRangeHeader*)this;
+  FollowingBlock->PrevAllocated = 0;
+  FreeBlock.ThisAllocated = 0;
+
+  // Link this into the linked list of free blocks.
+  FreeBlock.AddToFreeList(FreeList);
+
+  // Add a marker at the end of the block, indicating the size of this free
+  // block.
+  FreeBlock.SetEndOfBlockSizeMarker();
+  return FreeBlock;
+}
+
+/// GrowBlock - The block after this block just got deallocated.  Merge it
+/// into the current block.
+void FreeRangeHeader::GrowBlock(uintptr_t NewSize) {
+  assert(NewSize > BlockSize && "Not growing block?");
+  BlockSize = NewSize;
+  SetEndOfBlockSizeMarker();
+}
+
+/// TrimAllocationToSize - If this allocated block is significantly larger
+/// than NewSize, split it into two pieces (where the former is NewSize
+/// bytes, including the header), and add the new block to the free list.
+FreeRangeHeader *MemoryRangeHeader::
+TrimAllocationToSize(FreeRangeHeader *FreeList, uint64_t NewSize) {
+  assert(ThisAllocated && getBlockAfter().PrevAllocated &&
+         "Cannot deallocate part of an allocated block!");
+
+  // Round up size for alignment of header.
+  unsigned HeaderAlign = __alignof(FreeRangeHeader);
+  NewSize = (NewSize+ (HeaderAlign-1)) & ~(HeaderAlign-1);
+  
+  // Size is now the size of the block we will remove from the start of the
+  // current block.
+  assert(NewSize <= BlockSize &&
+         "Allocating more space from this block than exists!");
+  
+  // If splitting this block will cause the remainder to be too small, do not
+  // split the block.
+  if (BlockSize <= NewSize+FreeRangeHeader::getMinBlockSize())
+    return FreeList;
+  
+  // Otherwise, we splice the required number of bytes out of this block, form
+  // a new block immediately after it, then mark this block allocated.
+  MemoryRangeHeader &FormerNextBlock = getBlockAfter();
+  
+  // Change the size of this block.
+  BlockSize = NewSize;
+  
+  // Get the new block we just sliced out and turn it into a free block.
+  FreeRangeHeader &NewNextBlock = (FreeRangeHeader &)getBlockAfter();
+  NewNextBlock.BlockSize = (char*)&FormerNextBlock - (char*)&NewNextBlock;
+  NewNextBlock.ThisAllocated = 0;
+  NewNextBlock.PrevAllocated = 1;
+  NewNextBlock.SetEndOfBlockSizeMarker();
+  FormerNextBlock.PrevAllocated = 0;
+  NewNextBlock.AddToFreeList(FreeList);
+  return &NewNextBlock;
+}
+
+ 
+namespace {  
   /// JITMemoryManager - Manage memory for the JIT code generation in a logical,
   /// sane way.  This splits a large block of MAP_NORESERVE'd memory into two
   /// sections, one for function stubs, one for the functions themselves.  We
@@ -53,19 +250,49 @@ namespace {
   /// we are ready to destroy the JIT, the program exits.
   class JITMemoryManager {
     std::vector<sys::MemoryBlock> Blocks; // Memory blocks allocated by the JIT
-    unsigned char *FunctionBase; // Start of the function body area
-    unsigned char *CurStubPtr, *CurFunctionPtr;
+    FreeRangeHeader *FreeMemoryList;      // Circular list of free blocks.
+    
+    // When emitting code into a memory block, this is the block.
+    MemoryRangeHeader *CurBlock;
+    
+    unsigned char *CurStubPtr, *StubBase;
     unsigned char *GOTBase;      // Target Specific reserved memory
 
-    // centralize memory block allocation
+    // Centralize memory block allocation.
     sys::MemoryBlock getNewMemoryBlock(unsigned size);
+    
+    std::map<const Function*, MemoryRangeHeader*> FunctionBlocks;
   public:
     JITMemoryManager(bool useGOT);
     ~JITMemoryManager();
 
     inline unsigned char *allocateStub(unsigned StubSize);
-    inline unsigned char *startFunctionBody();
-    inline void endFunctionBody(unsigned char *FunctionEnd);
+    
+    /// startFunctionBody - When a function starts, allocate a block of free
+    /// executable memory, returning a pointer to it and its actual size.
+    unsigned char *startFunctionBody(uintptr_t &ActualSize) {
+      CurBlock = FreeMemoryList;
+      
+      // Allocate the entire memory block.
+      FreeMemoryList = FreeMemoryList->AllocateBlock();
+      ActualSize = CurBlock->BlockSize-sizeof(MemoryRangeHeader);
+      return (unsigned char *)(CurBlock+1);
+    }
+    
+    /// endFunctionBody - The function F is now allocated, and takes the memory
+    /// in the range [FunctionStart,FunctionEnd).
+    void endFunctionBody(const Function *F, unsigned char *FunctionStart,
+                         unsigned char *FunctionEnd) {
+      assert(FunctionEnd > FunctionStart);
+      assert(FunctionStart == (unsigned char *)(CurBlock+1) &&
+             "Mismatched function start/end!");
+      
+      uintptr_t BlockSize = FunctionEnd - (unsigned char *)CurBlock;
+      FunctionBlocks[F] = CurBlock;
+
+      // Release the memory at the end of this block that isn't needed.
+      FreeMemoryList =CurBlock->TrimAllocationToSize(FreeMemoryList, BlockSize);
+    }
     
     unsigned char *getGOTBase() const {
       return GOTBase;
@@ -73,18 +300,71 @@ namespace {
     bool isManagingGOT() const {
       return GOTBase != NULL;
     }
+    
+    /// deallocateMemForFunction - Deallocate all memory for the specified
+    /// function body.
+    void deallocateMemForFunction(const Function *F) {
+      
+    }
   };
 }
 
 JITMemoryManager::JITMemoryManager(bool useGOT) {
-  // Allocate a 16M block of memory for functions
-  sys::MemoryBlock FunBlock = getNewMemoryBlock(16 << 20);
+  // Allocate a 16M block of memory for functions.
+  sys::MemoryBlock MemBlock = getNewMemoryBlock(16 << 20);
 
-  FunctionBase = reinterpret_cast<unsigned char*>(FunBlock.base());
+  unsigned char *MemBase = reinterpret_cast<unsigned char*>(MemBlock.base());
 
   // Allocate stubs backwards from the base, allocate functions forward
   // from the base.
-  CurStubPtr = CurFunctionPtr = FunctionBase + 512*1024;// Use 512k for stubs
+  StubBase   = MemBase;
+  CurStubPtr = MemBase + 512*1024; // Use 512k for stubs, working backwards.
+  
+  // We set up the memory chunk with 4 mem regions, like this:
+  //  [ START
+  //    [ Free      #0 ] -> Large space to allocate functions from.
+  //    [ Allocated #1 ] -> Tiny space to separate regions.
+  //    [ Free      #2 ] -> Tiny space so there is always at least 1 free block.
+  //    [ Allocated #3 ] -> Tiny space to prevent looking past end of block.
+  //  END ]
+  //
+  // The last three blocks are never deallocated or touched.
+  
+  // Add MemoryRangeHeader to the end of the memory region, indicating that
+  // the space after the block of memory is allocated.  This is block #3.
+  MemoryRangeHeader *Mem3 = (MemoryRangeHeader*)(MemBase+MemBlock.size())-1;
+  Mem3->ThisAllocated = 1;
+  Mem3->PrevAllocated = 0;
+  Mem3->BlockSize     = 0;
+  
+  /// Add a tiny free region so that the free list always has one entry.
+  FreeRangeHeader *Mem2 = 
+    (FreeRangeHeader *)(((char*)Mem3)-FreeRangeHeader::getMinBlockSize());
+  Mem2->ThisAllocated = 0;
+  Mem2->PrevAllocated = 1;
+  Mem2->BlockSize     = FreeRangeHeader::getMinBlockSize();
+  Mem2->SetEndOfBlockSizeMarker();
+  Mem2->Prev = Mem2;   // Mem2 *is* the free list for now.
+  Mem2->Next = Mem2;
+
+  /// Add a tiny allocated region so that Mem2 is never coallesced away.
+  MemoryRangeHeader *Mem1 = (MemoryRangeHeader*)Mem2-1;
+  Mem2->ThisAllocated = 1;
+  Mem2->PrevAllocated = 0;
+  Mem2->BlockSize     = (char*)Mem2 - (char*)Mem1;
+  
+  // Add a FreeRangeHeader to the start of the function body region, indicating
+  // that the space is free.  Mark the previous block allocated so we never look
+  // at it.
+  FreeRangeHeader *Mem0 = (FreeRangeHeader*)CurStubPtr;
+  Mem0->ThisAllocated = 0;
+  Mem0->PrevAllocated = 1;
+  Mem0->BlockSize = (unsigned char*)Mem1-(unsigned char*)Mem0;
+  Mem0->SetEndOfBlockSizeMarker();
+  Mem0->AddToFreeList(Mem2);
+  
+  // Start out with the freelist pointing to Mem0.
+  FreeMemoryList = Mem0;
 
   // Allocate the GOT.
   GOTBase = NULL;
@@ -99,7 +379,7 @@ JITMemoryManager::~JITMemoryManager() {
 
 unsigned char *JITMemoryManager::allocateStub(unsigned StubSize) {
   CurStubPtr -= StubSize;
-  if (CurStubPtr < FunctionBase) {
+  if (CurStubPtr < StubBase) {
     // FIXME: allocate a new block
     std::cerr << "JIT ran out of memory for function stubs!\n";
     abort();
@@ -107,17 +387,9 @@ unsigned char *JITMemoryManager::allocateStub(unsigned StubSize) {
   return CurStubPtr;
 }
 
-unsigned char *JITMemoryManager::startFunctionBody() {
-  return CurFunctionPtr;
-}
-
-void JITMemoryManager::endFunctionBody(unsigned char *FunctionEnd) {
-  assert(FunctionEnd > CurFunctionPtr);
-  CurFunctionPtr = FunctionEnd;
-}
-
 sys::MemoryBlock JITMemoryManager::getNewMemoryBlock(unsigned size) {
   try {
+    // Allocate a new block close to the last one.
     const sys::MemoryBlock *BOld = Blocks.empty() ? 0 : &Blocks.front();
     sys::MemoryBlock B = sys::Memory::AllocateRWX(size, BOld);
     Blocks.push_back(B);
@@ -324,28 +596,6 @@ void *JITResolver::JITCompilerFn(void *Stub) {
 }
 
 
-// getPointerToFunctionOrStub - If the specified function has been
-// code-gen'd, return a pointer to the function.  If not, compile it, or use
-// a stub to implement lazy compilation if available.
-//
-void *JIT::getPointerToFunctionOrStub(Function *F) {
-  // If we have already code generated the function, just return the address.
-  if (void *Addr = getPointerToGlobalIfAvailable(F))
-    return Addr;
-
-  // Get a stub if the target supports it
-  return getJITResolver(MCE).getFunctionStub(F);
-}
-
-/// freeMachineCodeForFunction - release machine code memory for given Function.
-///
-void JIT::freeMachineCodeForFunction(Function *F) {
-  // Delete translation for this from the ExecutionEngine, so it will get
-  // retranslated next time it is used.
-  updateGlobalMapping(F, 0);
-  
-}
-
 //===----------------------------------------------------------------------===//
 // JITEmitter code.
 //
@@ -418,16 +668,16 @@ public:
       return MBBLocations[MBB->getNumber()];
     }
 
-
+    /// deallocateMemForFunction - Deallocate all memory for the specified
+    /// function body.
+    void deallocateMemForFunction(Function *F) {
+      MemMgr.deallocateMemForFunction(F);
+    }
   private:
     void *getPointerToGlobal(GlobalValue *GV, void *Reference, bool NoNeedStub);
   };
 }
 
-MachineCodeEmitter *JIT::createEmitter(JIT &jit) {
-  return new JITEmitter(jit);
-}
-
 void *JITEmitter::getPointerToGlobal(GlobalValue *V, void *Reference,
                                      bool DoesntNeedStub) {
   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
@@ -461,10 +711,9 @@ void *JITEmitter::getPointerToGlobal(GlobalValue *V, void *Reference,
 }
 
 void JITEmitter::startFunction(MachineFunction &F) {
-  BufferBegin = CurBufferPtr = MemMgr.startFunctionBody();
-  
-  /// FIXME: implement out of space handling correctly!
-  BufferEnd = (unsigned char*)(intptr_t)~0ULL;
+  uintptr_t ActualSize;
+  BufferBegin = CurBufferPtr = MemMgr.startFunctionBody(ActualSize);
+  BufferEnd = BufferBegin+ActualSize;
   
   emitConstantPool(F.getConstantPool());
   initJumpTableInfo(F.getJumpTableInfo());
@@ -477,9 +726,15 @@ void JITEmitter::startFunction(MachineFunction &F) {
 }
 
 bool JITEmitter::finishFunction(MachineFunction &F) {
+  if (CurBufferPtr == BufferEnd) {
+    // FIXME: Allocate more space, then try again.
+    std::cerr << "JIT: Ran out of space for generated machine code!\n";
+    abort();
+  }
+  
   emitJumpTableInfo(F.getJumpTableInfo());
   
-  MemMgr.endFunctionBody(CurBufferPtr);
+  MemMgr.endFunctionBody(F.getFunction(), BufferBegin, CurBufferPtr);
   NumBytes += getCurrentPCOffset();
 
   if (!Relocations.empty()) {
@@ -642,6 +897,14 @@ intptr_t JITEmitter::getJumpTableEntryAddress(unsigned Index) const {
   return (intptr_t)((char *)JumpTableBase + Offset);
 }
 
+//===----------------------------------------------------------------------===//
+//  Public interface to this file
+//===----------------------------------------------------------------------===//
+
+MachineCodeEmitter *JIT::createEmitter(JIT &jit) {
+  return new JITEmitter(jit);
+}
+
 // getPointerToNamedFunction - This function is used as a global wrapper to
 // JIT::getPointerToNamedFunction for the purpose of resolving symbols when
 // bugpoint is debugging the JIT. In that scenario, we are loading an .so and
@@ -655,3 +918,29 @@ extern "C" {
     return TheJIT->getPointerToNamedFunction(Name);
   }
 }
+
+// getPointerToFunctionOrStub - If the specified function has been
+// code-gen'd, return a pointer to the function.  If not, compile it, or use
+// a stub to implement lazy compilation if available.
+//
+void *JIT::getPointerToFunctionOrStub(Function *F) {
+  // If we have already code generated the function, just return the address.
+  if (void *Addr = getPointerToGlobalIfAvailable(F))
+    return Addr;
+  
+  // Get a stub if the target supports it
+  return getJITResolver(MCE).getFunctionStub(F);
+}
+
+/// freeMachineCodeForFunction - release machine code memory for given Function.
+///
+void JIT::freeMachineCodeForFunction(Function *F) {
+  // Delete translation for this from the ExecutionEngine, so it will get
+  // retranslated next time it is used.
+  updateGlobalMapping(F, 0);
+
+  // Free the actual memory for the function body and related stuff.
+  assert(dynamic_cast<JITEmitter*>(MCE) && "Unexpected MCE?");
+  dynamic_cast<JITEmitter*>(MCE)->deallocateMemForFunction(F);
+}
+