src/compiler/Utility.cc - platform/art - Git at Google

 /*
  * Copyright (C) 2011 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 #include "Dalvik.h"
 #include "CompilerInternals.h"

 static ArenaMemBlock *arenaHead, *currentArena;
 static int numArenaBlocks;

 #define kArenaBitVectorGrowth    4   /* increase by 4 u4s when limit hit */

 /* Allocate the initial memory block for arena-based allocation */
 bool oatHeapInit(void)
 {
     DCHECK(arenaHead == NULL);
     arenaHead =
         (ArenaMemBlock *) malloc(sizeof(ArenaMemBlock) + ARENA_DEFAULT_SIZE);
     if (arenaHead == NULL) {
         LOG(FATAL) << "No memory left to create compiler heap memory";
     }
     arenaHead->blockSize = ARENA_DEFAULT_SIZE;
     currentArena = arenaHead;
     currentArena->bytesAllocated = 0;
     currentArena->next = NULL;
     numArenaBlocks = 1;

     return true;
 }

 /* Arena-based malloc for compilation tasks */
 void* oatNew(size_t size, bool zero)
 {
     size = (size + 3) & ~3;
 retry:
     /* Normal case - space is available in the current page */
     if (size + currentArena->bytesAllocated <= currentArena->blockSize) {
         void *ptr;
         ptr = &currentArena->ptr[currentArena->bytesAllocated];
         currentArena->bytesAllocated += size;
         if (zero) {
             memset(ptr, 0, size);
         }
         return ptr;
     } else {
         /*
          * See if there are previously allocated arena blocks before the last
          * reset
          */
         if (currentArena->next) {
             currentArena = currentArena->next;
             currentArena->bytesAllocated = 0;
             goto retry;
         }

         size_t blockSize = (size < ARENA_DEFAULT_SIZE) ?
                           ARENA_DEFAULT_SIZE : size;
         /* Time to allocate a new arena */
         ArenaMemBlock *newArena = (ArenaMemBlock *)
             malloc(sizeof(ArenaMemBlock) + blockSize);
         if (newArena == NULL) {
             LOG(FATAL) << "Arena allocation failure";
         }
         newArena->blockSize = blockSize;
         newArena->bytesAllocated = 0;
         newArena->next = NULL;
         currentArena->next = newArena;
         currentArena = newArena;
         numArenaBlocks++;
         if (numArenaBlocks > 20000) {
             LOG(INFO) << "Total arena pages: " << numArenaBlocks;
         }
         goto retry;
     }
 }

 /* Reclaim all the arena blocks allocated so far */
 void oatArenaReset(void)
 {
     currentArena = arenaHead;
     if (currentArena) {
         currentArena->bytesAllocated = 0;
     }
 }

 /* Growable List initialization */
 void oatInitGrowableList(GrowableList* gList, size_t initLength)
 {
     gList->numAllocated = initLength;
     gList->numUsed = 0;
     gList->elemList = (intptr_t *) oatNew(sizeof(intptr_t) * initLength,
                                                   true);
 }

 /* Expand the capacity of a growable list */
 STATIC void expandGrowableList(GrowableList* gList)
 {
     int newLength = gList->numAllocated;
     if (newLength < 128) {
         newLength <<= 1;
     } else {
         newLength += 128;
     }
     intptr_t *newArray =
         (intptr_t *) oatNew(sizeof(intptr_t) * newLength, true);
     memcpy(newArray, gList->elemList, sizeof(intptr_t) * gList->numAllocated);
     gList->numAllocated = newLength;
     gList->elemList = newArray;
 }

 /* Insert a new element into the growable list */
 void oatInsertGrowableList(GrowableList* gList, intptr_t elem)
 {
     DCHECK_NE(gList->numAllocated, 0U);
     if (gList->numUsed == gList->numAllocated) {
         expandGrowableList(gList);
     }
     gList->elemList[gList->numUsed++] = elem;
 }

 void oatGrowableListIteratorInit(GrowableList* gList,
                                  GrowableListIterator* iterator)
 {
     iterator->list = gList;
     iterator->idx = 0;
     iterator->size = gList->numUsed;
 }

 intptr_t oatGrowableListIteratorNext(GrowableListIterator* iterator)
 {
     DCHECK_EQ(iterator->size, iterator->list->numUsed);
     if (iterator->idx == iterator->size) return 0;
     return iterator->list->elemList[iterator->idx++];
 }

 intptr_t oatGrowableListGetElement(const GrowableList* gList, size_t idx)
 {
     DCHECK_LT(idx, gList->numUsed);
     return gList->elemList[idx];
 }

 /* Debug Utility - dump a compilation unit */
 void oatDumpCompilationUnit(CompilationUnit* cUnit)
 {
     BasicBlock* bb;
     const char* blockTypeNames[] = {
         "Entry Block",
         "Code Block",
         "Exit Block",
         "Exception Handling",
         "Catch Block"
     };

     LOG(INFO) << "Compiling " << art::PrettyMethod(cUnit->method);
     LOG(INFO) << cUnit->insns << " insns";
     LOG(INFO) << cUnit->numBlocks << " blocks in total";
     GrowableListIterator iterator;

     oatGrowableListIteratorInit(&cUnit->blockList, &iterator);

     while (true) {
         bb = (BasicBlock *) oatGrowableListIteratorNext(&iterator);
         if (bb == NULL) break;
         char buf[100];
         snprintf(buf, 100, "Block %d (%s) (insn %04x - %04x%s)",
              bb->id,
              blockTypeNames[bb->blockType],
              bb->startOffset,
              bb->lastMIRInsn ? bb->lastMIRInsn->offset : bb->startOffset,
              bb->lastMIRInsn ? "" : " empty");
         LOG(INFO) << buf;
         if (bb->taken) {
             LOG(INFO) << "  Taken branch: block " << bb->taken->id <<
                  "(0x" << std::hex << bb->taken->startOffset << ")";
         }
         if (bb->fallThrough) {
             LOG(INFO) << "  Fallthrough : block " << bb->fallThrough->id <<
                  " (0x" << std::hex << bb->fallThrough->startOffset << ")";
         }
     }
 }

 /*
  * Dump the current stats of the compiler.
  */
 void oatDumpStats(void)
 {
     oatArchDump();
 }

 static uint32_t checkMasks[32] = {
     0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010,
     0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200,
     0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
     0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000,
     0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000,
     0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
     0x40000000, 0x80000000 };

 /*
  * Allocate a bit vector with enough space to hold at least the specified
  * number of bits.
  *
  * NOTE: memory is allocated from the compiler arena.
  */
 ArenaBitVector* oatAllocBitVector(unsigned int startBits, bool expandable)
 {
     ArenaBitVector* bv;
     unsigned int count;

     DCHECK_EQ(sizeof(bv->storage[0]), 4U);        /* assuming 32-bit units */

     bv = (ArenaBitVector*) oatNew(sizeof(ArenaBitVector), false);

     count = (startBits + 31) >> 5;

     bv->storageSize = count;
     bv->expandable = expandable;
     bv->storage = (u4*) oatNew(count * sizeof(u4), true);
     return bv;
 }

 /*
  * Determine whether or not the specified bit is set.
  */
 bool oatIsBitSet(const ArenaBitVector* pBits, unsigned int num)
 {
     DCHECK_LT(num, pBits->storageSize * sizeof(u4) * 8);

     unsigned int val = pBits->storage[num >> 5] & checkMasks[num & 0x1f];
     return (val != 0);
 }

 /*
  * Mark all bits bit as "clear".
  */
 void oatClearAllBits(ArenaBitVector* pBits)
 {
     unsigned int count = pBits->storageSize;
     memset(pBits->storage, 0, count * sizeof(u4));
 }

 /*
  * Mark the specified bit as "set".
  *
  * Returns "false" if the bit is outside the range of the vector and we're
  * not allowed to expand.
  *
  * NOTE: memory is allocated from the compiler arena.
  */
 bool oatSetBit(ArenaBitVector* pBits, unsigned int num)
 {
     if (num >= pBits->storageSize * sizeof(u4) * 8) {
         if (!pBits->expandable) {
             LOG(FATAL) << "Can't expand";
         }

         /* Round up to word boundaries for "num+1" bits */
         unsigned int newSize = (num + 1 + 31) >> 5;
         DCHECK_GT(newSize, pBits->storageSize);
         u4 *newStorage = (u4*)oatNew(newSize * sizeof(u4), false);
         memcpy(newStorage, pBits->storage, pBits->storageSize * sizeof(u4));
         memset(&newStorage[pBits->storageSize], 0,
                (newSize - pBits->storageSize) * sizeof(u4));
         pBits->storage = newStorage;
         pBits->storageSize = newSize;
     }

     pBits->storage[num >> 5] |= checkMasks[num & 0x1f];
     return true;
 }

 /*
  * Mark the specified bit as "unset".
  *
  * Returns "false" if the bit is outside the range of the vector and we're
  * not allowed to expand.
  *
  * NOTE: memory is allocated from the compiler arena.
  */
 bool oatClearBit(ArenaBitVector* pBits, unsigned int num)
 {
     if (num >= pBits->storageSize * sizeof(u4) * 8) {
         LOG(FATAL) << "Attempt to clear a bit not set in the vector yet";;
     }

     pBits->storage[num >> 5] &= ~checkMasks[num & 0x1f];
     return true;
 }

 /*
  * If set is true, mark all bits as 1. Otherwise mark all bits as 0.
  */
 void oatMarkAllBits(ArenaBitVector* pBits, bool set)
 {
     int value = set ? -1 : 0;
     memset(pBits->storage, value, pBits->storageSize * (int)sizeof(u4));
 }

 void oatDebugBitVector(char* msg, const ArenaBitVector* bv, int length)
 {
     int i;

     LOG(INFO) <<  msg;
     for (i = 0; i < length; i++) {
         if (oatIsBitSet(bv, i)) {
             LOG(INFO) << "    Bit " << i << " is set";
         }
     }
 }

 void oatAbort(CompilationUnit* cUnit)
 {
     LOG(FATAL) << "Compiler aborting";
 }

 void oatDumpBlockBitVector(const GrowableList* blocks, char* msg,
                            const ArenaBitVector* bv, int length)
 {
     int i;

     LOG(INFO) <<  msg;
     for (i = 0; i < length; i++) {
         if (oatIsBitSet(bv, i)) {
             BasicBlock *bb =
                 (BasicBlock *) oatGrowableListGetElement(blocks, i);
             char blockName[BLOCK_NAME_LEN];
             oatGetBlockName(bb, blockName);
             LOG(INFO) << "Bit " << i << " / " << blockName << " is set";
         }
     }
 }
 /* Initialize the iterator structure */
 void oatBitVectorIteratorInit(ArenaBitVector* pBits,
                               ArenaBitVectorIterator* iterator)
 {
     iterator->pBits = pBits;
     iterator->bitSize = pBits->storageSize * sizeof(u4) * 8;
     iterator->idx = 0;
 }

 /*
  * If the vector sizes don't match, log an error and abort.
  */
 STATIC void checkSizes(const ArenaBitVector* bv1, const ArenaBitVector* bv2)
 {
     if (bv1->storageSize != bv2->storageSize) {
         LOG(FATAL) << "Mismatched vector sizes (" << bv1->storageSize <<
             ", " << bv2->storageSize << ")";
     }
 }

 /*
  * Copy a whole vector to the other. Only do that when the both vectors have
  * the same size.
  */
 void oatCopyBitVector(ArenaBitVector* dest, const ArenaBitVector* src)
 {
     /* if dest is expandable and < src, we could expand dest to match */
     checkSizes(dest, src);

     memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
 }

 /*
  * Intersect two bit vectors and store the result to the dest vector.
  */

 bool oatIntersectBitVectors(ArenaBitVector* dest, const ArenaBitVector* src1,
                             const ArenaBitVector* src2)
 {
     DCHECK(src1 != NULL);
     DCHECK(src2 != NULL);
     if (dest->storageSize != src1->storageSize ||
         dest->storageSize != src2->storageSize ||
         dest->expandable != src1->expandable ||
         dest->expandable != src2->expandable)
         return false;

     unsigned int idx;
     for (idx = 0; idx < dest->storageSize; idx++) {
         dest->storage[idx] = src1->storage[idx] & src2->storage[idx];
     }
     return true;
 }

 /*
  * Unify two bit vectors and store the result to the dest vector.
  */
 bool oatUnifyBitVectors(ArenaBitVector* dest, const ArenaBitVector* src1,
                         const ArenaBitVector* src2)
 {
     DCHECK(src1 != NULL);
     DCHECK(src2 != NULL);
     if (dest->storageSize != src1->storageSize ||
         dest->storageSize != src2->storageSize ||
         dest->expandable != src1->expandable ||
         dest->expandable != src2->expandable)
         return false;

     unsigned int idx;
     for (idx = 0; idx < dest->storageSize; idx++) {
         dest->storage[idx] = src1->storage[idx] | src2->storage[idx];
     }
     return true;
 }

 /*
  * Compare two bit vectors and return true if difference is seen.
  */
 bool oatCompareBitVectors(const ArenaBitVector* src1,
                           const ArenaBitVector* src2)
 {
     if (src1->storageSize != src2->storageSize ||
         src1->expandable != src2->expandable)
         return true;

     unsigned int idx;
     for (idx = 0; idx < src1->storageSize; idx++) {
         if (src1->storage[idx] != src2->storage[idx]) return true;
     }
     return false;
 }

 /*
  * Count the number of bits that are set.
  */
 int oatCountSetBits(const ArenaBitVector* pBits)
 {
     unsigned int word;
     unsigned int count = 0;

     for (word = 0; word < pBits->storageSize; word++) {
         u4 val = pBits->storage[word];

         if (val != 0) {
             if (val == 0xffffffff) {
                 count += 32;
             } else {
                 /* count the number of '1' bits */
                 while (val != 0) {
                     val &= val - 1;
                     count++;
                 }
             }
         }
     }

     return count;
 }

 /* Return the next position set to 1. -1 means end-of-element reached */
 int oatBitVectorIteratorNext(ArenaBitVectorIterator* iterator)
 {
     const ArenaBitVector* pBits = iterator->pBits;
     u4 bitIndex = iterator->idx;

     DCHECK_EQ(iterator->bitSize, pBits->storageSize * sizeof(u4) * 8);
     if (bitIndex >= iterator->bitSize) return -1;

     for (; bitIndex < iterator->bitSize;) {
         unsigned int wordIndex = bitIndex >> 5;
         unsigned int bitPos = bitIndex & 0x1f;
         unsigned int word = pBits->storage[wordIndex];
         if (word & checkMasks[bitPos]) {
             iterator->idx = bitIndex+1;
             return bitIndex;
         }
         if (word == 0) {
             // Helps if this is a sparse vector
             bitIndex += (32 - bitPos);
         } else {
             bitIndex++;
         }
     }
     /* No more set bits */
     return -1;
 }

 /*
  * Mark specified number of bits as "set". Cannot set all bits like ClearAll
  * since there might be unused bits - setting those to one will confuse the
  * iterator.
  */
 void oatSetInitialBits(ArenaBitVector* pBits, unsigned int numBits)
 {
     unsigned int idx;
     DCHECK_LE(((numBits + 31) >> 5), pBits->storageSize);
     for (idx = 0; idx < (numBits >> 5); idx++) {
         pBits->storage[idx] = -1;
     }
     unsigned int remNumBits = numBits & 0x1f;
     if (remNumBits) {
         pBits->storage[idx] = (1 << remNumBits) - 1;
     }
 }

 void oatGetBlockName(BasicBlock* bb, char* name)
 {
     switch (bb->blockType) {
         case kEntryBlock:
             snprintf(name, BLOCK_NAME_LEN, "entry");
             break;
         case kExitBlock:
             snprintf(name, BLOCK_NAME_LEN, "exit");
             break;
         case kDalvikByteCode:
             snprintf(name, BLOCK_NAME_LEN, "block%04x", bb->startOffset);
             break;
         case kExceptionHandling:
             snprintf(name, BLOCK_NAME_LEN, "exception%04x", bb->startOffset);
             break;
         default:
             snprintf(name, BLOCK_NAME_LEN, "??");
             break;
     }
 }

 const char* oatGetShortyFromTargetIdx(CompilationUnit *cUnit, int targetIdx)
 {
     art::DexCache* dex_cache =
         cUnit->method->GetDeclaringClass()->GetDexCache();
     art::ClassLinker* class_linker = art::Runtime::Current()->GetClassLinker();
     const art::DexFile& dex_file = class_linker->FindDexFile(dex_cache);
     const art::DexFile::MethodId& methodId = dex_file.GetMethodId(targetIdx);
     return dex_file.GetShorty(methodId.proto_idx_);
 }
	/*
	* Copyright (C) 2011 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	#include "Dalvik.h"
	#include "CompilerInternals.h"

	static ArenaMemBlock arenaHead, currentArena;
	static int numArenaBlocks;

	#define kArenaBitVectorGrowth 4 /* increase by 4 u4s when limit hit */

	/* Allocate the initial memory block for arena-based allocation */
	bool oatHeapInit(void)
	{
	DCHECK(arenaHead == NULL);
	arenaHead =
	(ArenaMemBlock *) malloc(sizeof(ArenaMemBlock) + ARENA_DEFAULT_SIZE);
	if (arenaHead == NULL) {
	LOG(FATAL) << "No memory left to create compiler heap memory";
	}
	arenaHead->blockSize = ARENA_DEFAULT_SIZE;
	currentArena = arenaHead;
	currentArena->bytesAllocated = 0;
	currentArena->next = NULL;
	numArenaBlocks = 1;

	return true;
	}

	/* Arena-based malloc for compilation tasks */
	void* oatNew(size_t size, bool zero)
	{
	size = (size + 3) & ~3;
	retry:
	/* Normal case - space is available in the current page */
	if (size + currentArena->bytesAllocated <= currentArena->blockSize) {
	void *ptr;
	ptr = &currentArena->ptr[currentArena->bytesAllocated];
	currentArena->bytesAllocated += size;
	if (zero) {
	memset(ptr, 0, size);
	}
	return ptr;
	} else {
	/*
	* See if there are previously allocated arena blocks before the last
	* reset
	*/
	if (currentArena->next) {
	currentArena = currentArena->next;
	currentArena->bytesAllocated = 0;
	goto retry;
	}

	size_t blockSize = (size < ARENA_DEFAULT_SIZE) ?
	ARENA_DEFAULT_SIZE : size;
	/* Time to allocate a new arena */
	ArenaMemBlock newArena = (ArenaMemBlock )
	malloc(sizeof(ArenaMemBlock) + blockSize);
	if (newArena == NULL) {
	LOG(FATAL) << "Arena allocation failure";
	}
	newArena->blockSize = blockSize;
	newArena->bytesAllocated = 0;
	newArena->next = NULL;
	currentArena->next = newArena;
	currentArena = newArena;
	numArenaBlocks++;
	if (numArenaBlocks > 20000) {
	LOG(INFO) << "Total arena pages: " << numArenaBlocks;
	}
	goto retry;
	}
	}

	/* Reclaim all the arena blocks allocated so far */
	void oatArenaReset(void)
	{
	currentArena = arenaHead;
	if (currentArena) {
	currentArena->bytesAllocated = 0;
	}
	}

	/* Growable List initialization */
	void oatInitGrowableList(GrowableList* gList, size_t initLength)
	{
	gList->numAllocated = initLength;
	gList->numUsed = 0;
	gList->elemList = (intptr_t ) oatNew(sizeof(intptr_t) initLength,
	true);
	}

	/* Expand the capacity of a growable list */
	STATIC void expandGrowableList(GrowableList* gList)
	{
	int newLength = gList->numAllocated;
	if (newLength < 128) {
	newLength <<= 1;
	} else {
	newLength += 128;
	}
	intptr_t *newArray =
	(intptr_t ) oatNew(sizeof(intptr_t) newLength, true);
	memcpy(newArray, gList->elemList, sizeof(intptr_t) * gList->numAllocated);
	gList->numAllocated = newLength;
	gList->elemList = newArray;
	}

	/* Insert a new element into the growable list */
	void oatInsertGrowableList(GrowableList* gList, intptr_t elem)
	{
	DCHECK_NE(gList->numAllocated, 0U);
	if (gList->numUsed == gList->numAllocated) {
	expandGrowableList(gList);
	}
	gList->elemList[gList->numUsed++] = elem;
	}

	void oatGrowableListIteratorInit(GrowableList* gList,
	GrowableListIterator* iterator)
	{
	iterator->list = gList;
	iterator->idx = 0;
	iterator->size = gList->numUsed;
	}

	intptr_t oatGrowableListIteratorNext(GrowableListIterator* iterator)
	{
	DCHECK_EQ(iterator->size, iterator->list->numUsed);
	if (iterator->idx == iterator->size) return 0;
	return iterator->list->elemList[iterator->idx++];
	}

	intptr_t oatGrowableListGetElement(const GrowableList* gList, size_t idx)
	{
	DCHECK_LT(idx, gList->numUsed);
	return gList->elemList[idx];
	}

	/* Debug Utility - dump a compilation unit */
	void oatDumpCompilationUnit(CompilationUnit* cUnit)
	{
	BasicBlock* bb;
	const char* blockTypeNames[] = {
	"Entry Block",
	"Code Block",
	"Exit Block",
	"Exception Handling",
	"Catch Block"
	};

	LOG(INFO) << "Compiling " << art::PrettyMethod(cUnit->method);
	LOG(INFO) << cUnit->insns << " insns";
	LOG(INFO) << cUnit->numBlocks << " blocks in total";
	GrowableListIterator iterator;

	oatGrowableListIteratorInit(&cUnit->blockList, &iterator);

	while (true) {
	bb = (BasicBlock *) oatGrowableListIteratorNext(&iterator);
	if (bb == NULL) break;
	char buf[100];
	snprintf(buf, 100, "Block %d (%s) (insn %04x - %04x%s)",
	bb->id,
	blockTypeNames[bb->blockType],
	bb->startOffset,
	bb->lastMIRInsn ? bb->lastMIRInsn->offset : bb->startOffset,
	bb->lastMIRInsn ? "" : " empty");
	LOG(INFO) << buf;
	if (bb->taken) {
	LOG(INFO) << " Taken branch: block " << bb->taken->id <<
	"(0x" << std::hex << bb->taken->startOffset << ")";
	}
	if (bb->fallThrough) {
	LOG(INFO) << " Fallthrough : block " << bb->fallThrough->id <<
	" (0x" << std::hex << bb->fallThrough->startOffset << ")";
	}
	}
	}

	/*
	* Dump the current stats of the compiler.
	*/
	void oatDumpStats(void)
	{
	oatArchDump();
	}

	static uint32_t checkMasks[32] = {
	0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010,
	0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200,
	0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
	0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000,
	0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000,
	0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000,
	0x40000000, 0x80000000 };

	/*
	* Allocate a bit vector with enough space to hold at least the specified
	* number of bits.
	*
	* NOTE: memory is allocated from the compiler arena.
	*/
	ArenaBitVector* oatAllocBitVector(unsigned int startBits, bool expandable)
	{
	ArenaBitVector* bv;
	unsigned int count;

	DCHECK_EQ(sizeof(bv->storage[0]), 4U); /* assuming 32-bit units */

	bv = (ArenaBitVector*) oatNew(sizeof(ArenaBitVector), false);

	count = (startBits + 31) >> 5;

	bv->storageSize = count;
	bv->expandable = expandable;
	bv->storage = (u4) oatNew(count sizeof(u4), true);
	return bv;
	}

	/*
	* Determine whether or not the specified bit is set.
	*/
	bool oatIsBitSet(const ArenaBitVector* pBits, unsigned int num)
	{
	DCHECK_LT(num, pBits->storageSize * sizeof(u4) * 8);

	unsigned int val = pBits->storage[num >> 5] & checkMasks[num & 0x1f];
	return (val != 0);
	}

	/*
	* Mark all bits bit as "clear".
	*/
	void oatClearAllBits(ArenaBitVector* pBits)
	{
	unsigned int count = pBits->storageSize;
	memset(pBits->storage, 0, count * sizeof(u4));
	}

	/*
	* Mark the specified bit as "set".
	*
	* Returns "false" if the bit is outside the range of the vector and we're
	* not allowed to expand.
	*
	* NOTE: memory is allocated from the compiler arena.
	*/
	bool oatSetBit(ArenaBitVector* pBits, unsigned int num)
	{
	if (num >= pBits->storageSize * sizeof(u4) * 8) {
	if (!pBits->expandable) {
	LOG(FATAL) << "Can't expand";
	}

	/* Round up to word boundaries for "num+1" bits */
	unsigned int newSize = (num + 1 + 31) >> 5;
	DCHECK_GT(newSize, pBits->storageSize);
	u4 newStorage = (u4)oatNew(newSize * sizeof(u4), false);
	memcpy(newStorage, pBits->storage, pBits->storageSize * sizeof(u4));
	memset(&newStorage[pBits->storageSize], 0,
	(newSize - pBits->storageSize) * sizeof(u4));
	pBits->storage = newStorage;
	pBits->storageSize = newSize;
	}

	pBits->storage[num >> 5] \|= checkMasks[num & 0x1f];
	return true;
	}

	/*
	* Mark the specified bit as "unset".
	*
	* Returns "false" if the bit is outside the range of the vector and we're
	* not allowed to expand.
	*
	* NOTE: memory is allocated from the compiler arena.
	*/
	bool oatClearBit(ArenaBitVector* pBits, unsigned int num)
	{
	if (num >= pBits->storageSize * sizeof(u4) * 8) {
	LOG(FATAL) << "Attempt to clear a bit not set in the vector yet";;
	}

	pBits->storage[num >> 5] &= ~checkMasks[num & 0x1f];
	return true;
	}

	/*
	* If set is true, mark all bits as 1. Otherwise mark all bits as 0.
	*/
	void oatMarkAllBits(ArenaBitVector* pBits, bool set)
	{
	int value = set ? -1 : 0;
	memset(pBits->storage, value, pBits->storageSize * (int)sizeof(u4));
	}

	void oatDebugBitVector(char* msg, const ArenaBitVector* bv, int length)
	{
	int i;

	LOG(INFO) << msg;
	for (i = 0; i < length; i++) {
	if (oatIsBitSet(bv, i)) {
	LOG(INFO) << " Bit " << i << " is set";
	}
	}
	}

	void oatAbort(CompilationUnit* cUnit)
	{
	LOG(FATAL) << "Compiler aborting";
	}

	void oatDumpBlockBitVector(const GrowableList* blocks, char* msg,
	const ArenaBitVector* bv, int length)
	{
	int i;

	LOG(INFO) << msg;
	for (i = 0; i < length; i++) {
	if (oatIsBitSet(bv, i)) {
	BasicBlock *bb =
	(BasicBlock *) oatGrowableListGetElement(blocks, i);
	char blockName[BLOCK_NAME_LEN];
	oatGetBlockName(bb, blockName);
	LOG(INFO) << "Bit " << i << " / " << blockName << " is set";
	}
	}
	}
	/* Initialize the iterator structure */
	void oatBitVectorIteratorInit(ArenaBitVector* pBits,
	ArenaBitVectorIterator* iterator)
	{
	iterator->pBits = pBits;
	iterator->bitSize = pBits->storageSize * sizeof(u4) * 8;
	iterator->idx = 0;
	}

	/*
	* If the vector sizes don't match, log an error and abort.
	*/
	STATIC void checkSizes(const ArenaBitVector* bv1, const ArenaBitVector* bv2)
	{
	if (bv1->storageSize != bv2->storageSize) {
	LOG(FATAL) << "Mismatched vector sizes (" << bv1->storageSize <<
	", " << bv2->storageSize << ")";
	}
	}

	/*
	* Copy a whole vector to the other. Only do that when the both vectors have
	* the same size.
	*/
	void oatCopyBitVector(ArenaBitVector* dest, const ArenaBitVector* src)
	{
	/* if dest is expandable and < src, we could expand dest to match */
	checkSizes(dest, src);

	memcpy(dest->storage, src->storage, sizeof(u4) * dest->storageSize);
	}

	/*
	* Intersect two bit vectors and store the result to the dest vector.
	*/

	bool oatIntersectBitVectors(ArenaBitVector* dest, const ArenaBitVector* src1,
	const ArenaBitVector* src2)
	{
	DCHECK(src1 != NULL);
	DCHECK(src2 != NULL);
	if (dest->storageSize != src1->storageSize \|\|
	dest->storageSize != src2->storageSize \|\|
	dest->expandable != src1->expandable \|\|
	dest->expandable != src2->expandable)
	return false;

	unsigned int idx;
	for (idx = 0; idx < dest->storageSize; idx++) {
	dest->storage[idx] = src1->storage[idx] & src2->storage[idx];
	}
	return true;
	}

	/*
	* Unify two bit vectors and store the result to the dest vector.
	*/
	bool oatUnifyBitVectors(ArenaBitVector* dest, const ArenaBitVector* src1,
	const ArenaBitVector* src2)
	{
	DCHECK(src1 != NULL);
	DCHECK(src2 != NULL);
	if (dest->storageSize != src1->storageSize \|\|
	dest->storageSize != src2->storageSize \|\|
	dest->expandable != src1->expandable \|\|
	dest->expandable != src2->expandable)
	return false;

	unsigned int idx;
	for (idx = 0; idx < dest->storageSize; idx++) {
	dest->storage[idx] = src1->storage[idx] \| src2->storage[idx];
	}
	return true;
	}

	/*
	* Compare two bit vectors and return true if difference is seen.
	*/
	bool oatCompareBitVectors(const ArenaBitVector* src1,
	const ArenaBitVector* src2)
	{
	if (src1->storageSize != src2->storageSize \|\|
	src1->expandable != src2->expandable)
	return true;

	unsigned int idx;
	for (idx = 0; idx < src1->storageSize; idx++) {
	if (src1->storage[idx] != src2->storage[idx]) return true;
	}
	return false;
	}

	/*
	* Count the number of bits that are set.
	*/
	int oatCountSetBits(const ArenaBitVector* pBits)
	{
	unsigned int word;
	unsigned int count = 0;

	for (word = 0; word < pBits->storageSize; word++) {
	u4 val = pBits->storage[word];

	if (val != 0) {
	if (val == 0xffffffff) {
	count += 32;
	} else {
	/* count the number of '1' bits */
	while (val != 0) {
	val &= val - 1;
	count++;
	}
	}
	}
	}

	return count;
	}

	/* Return the next position set to 1. -1 means end-of-element reached */
	int oatBitVectorIteratorNext(ArenaBitVectorIterator* iterator)
	{
	const ArenaBitVector* pBits = iterator->pBits;
	u4 bitIndex = iterator->idx;

	DCHECK_EQ(iterator->bitSize, pBits->storageSize * sizeof(u4) * 8);
	if (bitIndex >= iterator->bitSize) return -1;

	for (; bitIndex < iterator->bitSize;) {
	unsigned int wordIndex = bitIndex >> 5;
	unsigned int bitPos = bitIndex & 0x1f;
	unsigned int word = pBits->storage[wordIndex];
	if (word & checkMasks[bitPos]) {
	iterator->idx = bitIndex+1;
	return bitIndex;
	}
	if (word == 0) {
	// Helps if this is a sparse vector
	bitIndex += (32 - bitPos);
	} else {
	bitIndex++;
	}
	}
	/* No more set bits */
	return -1;
	}

	/*
	* Mark specified number of bits as "set". Cannot set all bits like ClearAll
	* since there might be unused bits - setting those to one will confuse the
	* iterator.
	*/
	void oatSetInitialBits(ArenaBitVector* pBits, unsigned int numBits)
	{
	unsigned int idx;
	DCHECK_LE(((numBits + 31) >> 5), pBits->storageSize);
	for (idx = 0; idx < (numBits >> 5); idx++) {
	pBits->storage[idx] = -1;
	}
	unsigned int remNumBits = numBits & 0x1f;
	if (remNumBits) {
	pBits->storage[idx] = (1 << remNumBits) - 1;
	}
	}

	void oatGetBlockName(BasicBlock* bb, char* name)
	{
	switch (bb->blockType) {
	case kEntryBlock:
	snprintf(name, BLOCK_NAME_LEN, "entry");
	break;
	case kExitBlock:
	snprintf(name, BLOCK_NAME_LEN, "exit");
	break;
	case kDalvikByteCode:
	snprintf(name, BLOCK_NAME_LEN, "block%04x", bb->startOffset);
	break;
	case kExceptionHandling:
	snprintf(name, BLOCK_NAME_LEN, "exception%04x", bb->startOffset);
	break;
	default:
	snprintf(name, BLOCK_NAME_LEN, "??");
	break;
	}
	}

	const char* oatGetShortyFromTargetIdx(CompilationUnit *cUnit, int targetIdx)
	{
	art::DexCache* dex_cache =
	cUnit->method->GetDeclaringClass()->GetDexCache();
	art::ClassLinker* class_linker = art::Runtime::Current()->GetClassLinker();
	const art::DexFile& dex_file = class_linker->FindDexFile(dex_cache);
	const art::DexFile::MethodId& methodId = dex_file.GetMethodId(targetIdx);
	return dex_file.GetShorty(methodId.proto_idx_);
	}