src/compiler/dex/compiler_utility.cc

/*
 * 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 "compiler_internals.h"
#include "dex_file-inl.h"

namespace art {

const char* extended_mir_op_names[kMirOpLast - kMirOpFirst] = {
  "Phi",
  "Copy",
  "FusedCmplFloat",
  "FusedCmpgFloat",
  "FusedCmplDouble",
  "FusedCmpgDouble",
  "FusedCmpLong",
  "Nop",
  "OpNullCheck",
  "OpRangeCheck",
  "OpDivZeroCheck",
  "Check1",
  "Check2",
  "Select",
};

#ifdef WITH_MEMSTATS
struct Memstats {
  uint32_t alloc_stats[kNumAllocKinds];
  int list_sizes[kNumListKinds];
  int list_wasted[kNumListKinds];
  int list_grows[kNumListKinds];
  int list_max_elems[kNumListKinds];
  int bit_map_sizes[kNumBitMapKinds];
  int bit_map_wasted[kNumBitMapKinds];
  int bit_map_grows[kNumBitMapKinds];
};

const char* alloc_names[kNumAllocKinds] = {
  "Misc       ",
  "BasicBlock ",
  "LIR        ",
  "MIR        ",
  "DataFlow   ",
  "GrowList   ",
  "GrowBitMap ",
  "Dalvik2SSA ",
  "DebugInfo  ",
  "Successor  ",
  "RegAlloc   ",
  "Data       ",
  "Preds      ",
};

const char* list_names[kNumListKinds] = {
  "Misc                  ",
  "block_list             ",
  "SSAtoDalvik           ",
  "dfs_order              ",
  "dfs_post_order          ",
  "dom_post_order_traversal ",
  "throw_launch_pads       ",
  "suspend_launch_pads     ",
  "switch_tables          ",
  "fill_array_data         ",
  "SuccessorBlocks       ",
  "Predecessors          ",
};

const char* bit_map_names[kNumBitMapKinds] = {
  "Misc                  ",
  "Use                   ",
  "Def                   ",
  "LiveIn                ",
  "BlockMatrix           ",
  "Dominators            ",
  "IDominated            ",
  "DomFrontier           ",
  "Phi                   ",
  "TmpBlocks             ",
  "InputBlocks           ",
  "RegisterV             ",
  "TempSSARegisterV      ",
  "Null Check            ",
  "TmpBlockV             ",
  "Predecessors          ",
};
#endif

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

/* Allocate the initial memory block for arena-based allocation */
bool HeapInit(CompilationUnit* cu)
{
  DCHECK(cu->arena_head == NULL);
  cu->arena_head =
      static_cast<ArenaMemBlock*>(malloc(sizeof(ArenaMemBlock) + ARENA_DEFAULT_SIZE));
  if (cu->arena_head == NULL) {
    LOG(FATAL) << "No memory left to create compiler heap memory";
  }
  cu->arena_head->block_size = ARENA_DEFAULT_SIZE;
  cu->current_arena = cu->arena_head;
  cu->current_arena->bytes_allocated = 0;
  cu->current_arena->next = NULL;
  cu->num_arena_blocks = 1;
#ifdef WITH_MEMSTATS
  cu->mstats = (Memstats*) NewMem(cu, sizeof(Memstats), true,
                   kAllocDebugInfo);
#endif
  return true;
}

/* Arena-based malloc for compilation tasks */
void* NewMem(CompilationUnit* cu, size_t size, bool zero, oat_alloc_kind kind)
{
  size = (size + 3) & ~3;
#ifdef WITH_MEMSTATS
  if (cu->mstats != NULL) {
    cu->mstats->alloc_stats[kind] += size;
  }
#endif
retry:
  /* Normal case - space is available in the current page */
  if (size + cu->current_arena->bytes_allocated <=
    cu->current_arena->block_size) {
    void *ptr;
    ptr = &cu->current_arena->ptr[cu->current_arena->bytes_allocated];
    cu->current_arena->bytes_allocated += size;
    if (zero) {
      memset(ptr, 0, size);
    }
    return ptr;
  } else {
    /*
     * See if there are previously allocated arena blocks before the last
     * reset
     */
    if (cu->current_arena->next) {
        cu->current_arena = cu->current_arena->next;
        cu->current_arena->bytes_allocated = 0;
        goto retry;
    }

    size_t block_size = (size < ARENA_DEFAULT_SIZE) ?  ARENA_DEFAULT_SIZE : size;
    /* Time to allocate a new arena */
    ArenaMemBlock *new_arena =
        static_cast<ArenaMemBlock*>(malloc(sizeof(ArenaMemBlock) + block_size));
    if (new_arena == NULL) {
      LOG(FATAL) << "Arena allocation failure";
    }
    new_arena->block_size = block_size;
    new_arena->bytes_allocated = 0;
    new_arena->next = NULL;
    cu->current_arena->next = new_arena;
    cu->current_arena = new_arena;
    cu->num_arena_blocks++;
    if (cu->num_arena_blocks > 20000) {
      LOG(INFO) << "Total arena pages: " << cu->num_arena_blocks;
    }
    goto retry;
  }
}

/* Reclaim all the arena blocks allocated so far */
void ArenaReset(CompilationUnit* cu)
{
  ArenaMemBlock* head = cu->arena_head;
  while (head != NULL) {
    ArenaMemBlock* p = head;
    head = head->next;
    free(p);
  }
  cu->arena_head = NULL;
  cu->current_arena = NULL;
}

/* Growable List initialization */
void CompilerInitGrowableList(CompilationUnit* cu, GrowableList* g_list,
                       size_t init_length, oat_list_kind kind)
{
  g_list->num_allocated = init_length;
  g_list->num_used = 0;
  g_list->elem_list = static_cast<uintptr_t *>(NewMem(cu, sizeof(intptr_t) * init_length,
                                             true, kAllocGrowableList));
#ifdef WITH_MEMSTATS
  cu->mstats->list_sizes[kind] += sizeof(uintptr_t) * init_length;
  g_list->kind = kind;
  if (static_cast<int>(init_length) > cu->mstats->list_max_elems[kind]) {
    cu->mstats->list_max_elems[kind] = init_length;
  }
#endif
}

void ReallocGrowableList(CompilationUnit* cu, GrowableList* g_list, size_t new_length)
{
  if (new_length > g_list->num_allocated) {
    uintptr_t *new_array =
        static_cast<uintptr_t*>(NewMem(cu, sizeof(uintptr_t) * new_length, true,
                                       kAllocGrowableList));
    memcpy(new_array, g_list->elem_list, sizeof(uintptr_t) * g_list->num_allocated);
    g_list->num_allocated = new_length;
    g_list->elem_list = new_array;
  }
}

/* Expand the capacity of a growable list */
static void ExpandGrowableList(CompilationUnit* cu, GrowableList* g_list)
{
  int new_length = g_list->num_allocated;
  if (new_length < 128) {
    new_length <<= 1;
  } else {
    new_length += 128;
  }
  uintptr_t *new_array =
      static_cast<uintptr_t*>(NewMem(cu, sizeof(uintptr_t) * new_length, true,
                                     kAllocGrowableList));
  memcpy(new_array, g_list->elem_list, sizeof(uintptr_t) * g_list->num_allocated);
#ifdef WITH_MEMSTATS
  cu->mstats->list_sizes[g_list->kind] += sizeof(uintptr_t) * new_length;
  cu->mstats->list_wasted[g_list->kind] +=
      sizeof(uintptr_t) * g_list->num_allocated;
  cu->mstats->list_grows[g_list->kind]++;
  if (new_length > cu->mstats->list_max_elems[g_list->kind]) {
    cu->mstats->list_max_elems[g_list->kind] = new_length;
  }
#endif
  g_list->num_allocated = new_length;
  g_list->elem_list = new_array;
}

/* Insert a new element into the growable list */
void InsertGrowableList(CompilationUnit* cu, GrowableList* g_list,
                           uintptr_t elem)
{
  DCHECK_NE(g_list->num_allocated, 0U);
  if (g_list->num_used == g_list->num_allocated) {
    ExpandGrowableList(cu, g_list);
  }
  g_list->elem_list[g_list->num_used++] = elem;
}

/* Delete an element from a growable list. Element must be present */
void DeleteGrowableList(GrowableList* g_list, uintptr_t elem)
{
  bool found = false;
  for (unsigned int i = 0; i < g_list->num_used; i++) {
    if (!found && g_list->elem_list[i] == elem) {
      found = true;
    }
    if (found) {
      g_list->elem_list[i] = g_list->elem_list[i+1];
    }
  }
  DCHECK_EQ(found, true);
  g_list->num_used--;
}

void GrowableListIteratorInit(GrowableList* g_list,
                               GrowableListIterator* iterator)
{
  iterator->list = g_list;
  iterator->idx = 0;
  iterator->size = g_list->num_used;
}

uintptr_t GrowableListIteratorNext(GrowableListIterator* iterator)
{
  DCHECK_EQ(iterator->size, iterator->list->num_used);
  if (iterator->idx == iterator->size) return 0;
  return iterator->list->elem_list[iterator->idx++];
}

uintptr_t GrowableListGetElement(const GrowableList* g_list, size_t idx)
{
  DCHECK_LT(idx, g_list->num_used);
  return g_list->elem_list[idx];
}

#ifdef WITH_MEMSTATS
/* Dump memory usage stats */
void DumpMemStats(CompilationUnit* cu)
{
  uint32_t total = 0;
  for (int i = 0; i < kNumAllocKinds; i++) {
    total += cu->mstats->alloc_stats[i];
  }
  if (total > (10 * 1024 * 1024)) {
    LOG(INFO) << "MEMUSAGE: " << total << " : "
        << PrettyMethod(cu->method_idx, *cu->dex_file);
    LOG(INFO) << "insns_size: " << cu->code_item->insns_size_in_code_units_;
    if (cu->disable_dataflow) {
        LOG(INFO) << " ** Dataflow disabled ** ";
    }
    LOG(INFO) << "===== Overall allocations";
    for (int i = 0; i < kNumAllocKinds; i++) {
        LOG(INFO) << alloc_names[i] << std::setw(10) <<
        cu->mstats->alloc_stats[i];
    }
    LOG(INFO) << "===== GrowableList allocations";
    for (int i = 0; i < kNumListKinds; i++) {
      LOG(INFO) << list_names[i]
                << " S:" << cu->mstats->list_sizes[i]
                << ", W:" << cu->mstats->list_wasted[i]
                << ", G:" << cu->mstats->list_grows[i]
                << ", E:" << cu->mstats->list_max_elems[i];
    }
    LOG(INFO) << "===== GrowableBitMap allocations";
    for (int i = 0; i < kNumBitMapKinds; i++) {
      LOG(INFO) << bit_map_names[i]
                << " S:" << cu->mstats->bit_map_sizes[i]
                << ", W:" << cu->mstats->bit_map_wasted[i]
                << ", G:" << cu->mstats->bit_map_grows[i];
    }
  }
}
#endif

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

  LOG(INFO) << "Compiling " << PrettyMethod(cu->method_idx, *cu->dex_file);
  LOG(INFO) << cu->insns << " insns";
  LOG(INFO) << cu->mir_graph->GetNumBlocks() << " blocks in total";
  GrowableListIterator iterator = cu->mir_graph->GetBasicBlockIterator();

  while (true) {
    bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iterator));
    if (bb == NULL) break;
    LOG(INFO) << StringPrintf("Block %d (%s) (insn %04x - %04x%s)",
        bb->id,
        block_type_names[bb->block_type],
        bb->start_offset,
        bb->last_mir_insn ? bb->last_mir_insn->offset : bb->start_offset,
        bb->last_mir_insn ? "" : " empty");
    if (bb->taken) {
      LOG(INFO) << "  Taken branch: block " << bb->taken->id
                << "(0x" << std::hex << bb->taken->start_offset << ")";
    }
    if (bb->fall_through) {
      LOG(INFO) << "  Fallthrough : block " << bb->fall_through->id
                << " (0x" << std::hex << bb->fall_through->start_offset << ")";
    }
  }
}

static uint32_t check_masks[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* AllocBitVector(CompilationUnit* cu,
                                unsigned int start_bits, bool expandable,
                                oat_bit_map_kind kind)
{
  ArenaBitVector* bv;
  unsigned int count;

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

  bv = static_cast<ArenaBitVector*>(NewMem(cu, sizeof(ArenaBitVector), false,
                                                kAllocGrowableBitMap));

  count = (start_bits + 31) >> 5;

  bv->storage_size = count;
  bv->expandable = expandable;
  bv->storage = static_cast<uint32_t*>(NewMem(cu, count * sizeof(uint32_t), true,
                                              kAllocGrowableBitMap));
#ifdef WITH_MEMSTATS
  bv->kind = kind;
  cu->mstats->bit_map_sizes[kind] += count * sizeof(uint32_t);
#endif
  return bv;
}

/*
 * Determine whether or not the specified bit is set.
 */
bool IsBitSet(const ArenaBitVector* p_bits, unsigned int num)
{
  DCHECK_LT(num, p_bits->storage_size * sizeof(uint32_t) * 8);

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

/*
 * Mark all bits bit as "clear".
 */
void ClearAllBits(ArenaBitVector* p_bits)
{
  unsigned int count = p_bits->storage_size;
  memset(p_bits->storage, 0, count * sizeof(uint32_t));
}

/*
 * 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 SetBit(CompilationUnit* cu, ArenaBitVector* p_bits, unsigned int num)
{
  if (num >= p_bits->storage_size * sizeof(uint32_t) * 8) {
    if (!p_bits->expandable) {
      LOG(FATAL) << "Can't expand";
    }

    /* Round up to word boundaries for "num+1" bits */
    unsigned int new_size = (num + 1 + 31) >> 5;
    DCHECK_GT(new_size, p_bits->storage_size);
    uint32_t *new_storage = static_cast<uint32_t*>(NewMem(cu, new_size * sizeof(uint32_t), false,
                                                         kAllocGrowableBitMap));
    memcpy(new_storage, p_bits->storage, p_bits->storage_size * sizeof(uint32_t));
    memset(&new_storage[p_bits->storage_size], 0,
           (new_size - p_bits->storage_size) * sizeof(uint32_t));
#ifdef WITH_MEMSTATS
    cu->mstats->bit_map_wasted[p_bits->kind] +=
        p_bits->storage_size * sizeof(uint32_t);
    cu->mstats->bit_map_sizes[p_bits->kind] += new_size * sizeof(uint32_t);
    cu->mstats->bit_map_grows[p_bits->kind]++;
#endif
    p_bits->storage = new_storage;
    p_bits->storage_size = new_size;
  }

  p_bits->storage[num >> 5] |= check_masks[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 ClearBit(ArenaBitVector* p_bits, unsigned int num)
{
  if (num >= p_bits->storage_size * sizeof(uint32_t) * 8) {
    LOG(FATAL) << "Attempt to clear a bit not set in the vector yet";;
  }

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

/* Initialize the iterator structure */
void BitVectorIteratorInit(ArenaBitVector* p_bits,
                            ArenaBitVectorIterator* iterator)
{
  iterator->p_bits = p_bits;
  iterator->bit_size = p_bits->storage_size * sizeof(uint32_t) * 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->storage_size != bv2->storage_size) {
    LOG(FATAL) << "Mismatched vector sizes (" << bv1->storage_size
               << ", " << bv2->storage_size << ")";
  }
}

/*
 * Copy a whole vector to the other. Only do that when the both vectors have
 * the same size.
 */
void CopyBitVector(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(uint32_t) * dest->storage_size);
}

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

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

  unsigned int idx;
  for (idx = 0; idx < dest->storage_size; 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 UnifyBitVetors(ArenaBitVector* dest, const ArenaBitVector* src1,
                      const ArenaBitVector* src2)
{
  DCHECK(src1 != NULL);
  DCHECK(src2 != NULL);
  if (dest->storage_size != src1->storage_size ||
      dest->storage_size != src2->storage_size ||
      dest->expandable != src1->expandable ||
      dest->expandable != src2->expandable)
    return false;

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

/*
 * Return true if any bits collide.  Vectors must be same size.
 */
bool TestBitVectors(const ArenaBitVector* src1,
                     const ArenaBitVector* src2)
{
  DCHECK_EQ(src1->storage_size, src2->storage_size);
  for (uint32_t idx = 0; idx < src1->storage_size; idx++) {
    if (src1->storage[idx] & src2->storage[idx]) return true;
  }
  return false;
}

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

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

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

  for (word = 0; word < p_bits->storage_size; word++) {
    uint32_t val = p_bits->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 BitVectorIteratorNext(ArenaBitVectorIterator* iterator)
{
  ArenaBitVector* p_bits = iterator->p_bits;
  uint32_t bit_index = iterator->idx;
  uint32_t bit_size = iterator->bit_size;

  DCHECK_EQ(bit_size, p_bits->storage_size * sizeof(uint32_t) * 8);

  if (bit_index >= bit_size) return -1;

  uint32_t word_index = bit_index >> 5;
  uint32_t end_word_index = bit_size >> 5;
  uint32_t* storage = p_bits->storage;
  uint32_t word = storage[word_index++];

  // Mask out any bits in the first word we've already considered
  word &= ~((1 << (bit_index & 0x1f))-1);

  for (; word_index <= end_word_index;) {
    uint32_t bit_pos = bit_index & 0x1f;
    if (word == 0) {
      bit_index += (32 - bit_pos);
      word = storage[word_index++];
      continue;
    }
    for (; bit_pos < 32; bit_pos++) {
      if (word & (1 << bit_pos)) {
        iterator->idx = bit_index + 1;
        return bit_index;
      }
      bit_index++;
    }
    word = storage[word_index++];
  }
  iterator->idx = iterator->bit_size;
  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 SetInitialBits(ArenaBitVector* p_bits, unsigned int num_bits)
{
  unsigned int idx;
  DCHECK_LE(((num_bits + 31) >> 5), p_bits->storage_size);
  for (idx = 0; idx < (num_bits >> 5); idx++) {
    p_bits->storage[idx] = -1;
  }
  unsigned int rem_num_bits = num_bits & 0x1f;
  if (rem_num_bits) {
    p_bits->storage[idx] = (1 << rem_num_bits) - 1;
  }
}

void GetBlockName(BasicBlock* bb, char* name)
{
  switch (bb->block_type) {
    case kEntryBlock:
      snprintf(name, BLOCK_NAME_LEN, "entry_%d", bb->id);
      break;
    case kExitBlock:
      snprintf(name, BLOCK_NAME_LEN, "exit_%d", bb->id);
      break;
    case kDalvikByteCode:
      snprintf(name, BLOCK_NAME_LEN, "block%04x_%d", bb->start_offset, bb->id);
      break;
    case kExceptionHandling:
      snprintf(name, BLOCK_NAME_LEN, "exception%04x_%d", bb->start_offset,
               bb->id);
      break;
    default:
      snprintf(name, BLOCK_NAME_LEN, "_%d", bb->id);
      break;
  }
}

const char* GetShortyFromTargetIdx(CompilationUnit *cu, int target_idx)
{
  const DexFile::MethodId& method_id = cu->dex_file->GetMethodId(target_idx);
  return cu->dex_file->GetShorty(method_id.proto_idx_);
}

/* Allocate a new basic block */
BasicBlock* NewMemBB(CompilationUnit* cu, BBType block_type, int block_id)
{
  BasicBlock* bb = static_cast<BasicBlock*>(NewMem(cu, sizeof(BasicBlock), true, kAllocBB));
  bb->block_type = block_type;
  bb->id = block_id;
  bb->predecessors = static_cast<GrowableList*>
      (NewMem(cu, sizeof(GrowableList), false, kAllocPredecessors));
  CompilerInitGrowableList(cu, bb->predecessors,
                      (block_type == kExitBlock) ? 2048 : 2,
                      kListPredecessors);
  cu->block_id_map.Put(block_id, block_id);
  return bb;
}

/* Insert an MIR instruction to the end of a basic block */
void AppendMIR(BasicBlock* bb, MIR* mir)
{
  if (bb->first_mir_insn == NULL) {
    DCHECK(bb->last_mir_insn == NULL);
    bb->last_mir_insn = bb->first_mir_insn = mir;
    mir->prev = mir->next = NULL;
  } else {
    bb->last_mir_insn->next = mir;
    mir->prev = bb->last_mir_insn;
    mir->next = NULL;
    bb->last_mir_insn = mir;
  }
}

/* Insert an MIR instruction to the head of a basic block */
void PrependMIR(BasicBlock* bb, MIR* mir)
{
  if (bb->first_mir_insn == NULL) {
    DCHECK(bb->last_mir_insn == NULL);
    bb->last_mir_insn = bb->first_mir_insn = mir;
    mir->prev = mir->next = NULL;
  } else {
    bb->first_mir_insn->prev = mir;
    mir->next = bb->first_mir_insn;
    mir->prev = NULL;
    bb->first_mir_insn = mir;
  }
}

/* Insert a MIR instruction after the specified MIR */
void InsertMIRAfter(BasicBlock* bb, MIR* current_mir, MIR* new_mir)
{
  new_mir->prev = current_mir;
  new_mir->next = current_mir->next;
  current_mir->next = new_mir;

  if (new_mir->next) {
    /* Is not the last MIR in the block */
    new_mir->next->prev = new_mir;
  } else {
    /* Is the last MIR in the block */
    bb->last_mir_insn = new_mir;
  }
}

/*
 * Append an LIR instruction to the LIR list maintained by a compilation
 * unit
 */
void AppendLIR(CompilationUnit *cu, LIR* lir)
{
  if (cu->first_lir_insn == NULL) {
    DCHECK(cu->last_lir_insn == NULL);
     cu->last_lir_insn = cu->first_lir_insn = lir;
    lir->prev = lir->next = NULL;
  } else {
    cu->last_lir_insn->next = lir;
    lir->prev = cu->last_lir_insn;
    lir->next = NULL;
    cu->last_lir_insn = lir;
  }
}

/*
 * Insert an LIR instruction before the current instruction, which cannot be the
 * first instruction.
 *
 * prev_lir <-> new_lir <-> current_lir
 */
void InsertLIRBefore(LIR* current_lir, LIR* new_lir)
{
  DCHECK(current_lir->prev != NULL);
  LIR *prev_lir = current_lir->prev;

  prev_lir->next = new_lir;
  new_lir->prev = prev_lir;
  new_lir->next = current_lir;
  current_lir->prev = new_lir;
}

/*
 * Insert an LIR instruction after the current instruction, which cannot be the
 * first instruction.
 *
 * current_lir -> new_lir -> old_next
 */
void InsertLIRAfter(LIR* current_lir, LIR* new_lir)
{
  new_lir->prev = current_lir;
  new_lir->next = current_lir->next;
  current_lir->next = new_lir;
  new_lir->next->prev = new_lir;
}

/* Turn method name into a legal Linux file name */
void ReplaceSpecialChars(std::string& str)
{
  static const struct { const char before; const char after; } match[] =
      {{'/','-'}, {';','#'}, {' ','#'}, {'$','+'},
       {'(','@'}, {')','@'}, {'<','='}, {'>','='}};
  for (unsigned int i = 0; i < sizeof(match)/sizeof(match[0]); i++) {
    std::replace(str.begin(), str.end(), match[i].before, match[i].after);
  }
}

std::string GetSSAName(const CompilationUnit* cu, int ssa_reg)
{
  return StringPrintf("v%d_%d", cu->mir_graph->SRegToVReg(ssa_reg), cu->mir_graph->GetSSASubscript(ssa_reg));
}

// Similar to GetSSAName, but if ssa name represents an immediate show that as well.
std::string GetSSANameWithConst(const CompilationUnit* cu, int ssa_reg, bool singles_only)
{
  if (cu->reg_location == NULL) {
    // Pre-SSA - just use the standard name
    return GetSSAName(cu, ssa_reg);
  }
  if (cu->mir_graph->IsConst(cu->reg_location[ssa_reg])) {
    if (!singles_only && cu->reg_location[ssa_reg].wide) {
      return StringPrintf("v%d_%d#0x%llx", cu->mir_graph->SRegToVReg(ssa_reg),
                          cu->mir_graph->GetSSASubscript(ssa_reg),
                          cu->mir_graph->ConstantValueWide(cu->reg_location[ssa_reg]));
    } else {
      return StringPrintf("v%d_%d#0x%x", cu->mir_graph->SRegToVReg(ssa_reg),
                          cu->mir_graph->GetSSASubscript(ssa_reg),
                          cu->mir_graph->ConstantValue(cu->reg_location[ssa_reg]));
    }
  } else {
    return StringPrintf("v%d_%d", cu->mir_graph->SRegToVReg(ssa_reg),
                        cu->mir_graph->GetSSASubscript(ssa_reg));
  }
}

char* GetDalvikDisassembly(CompilationUnit* cu, const MIR* mir)
{
  DecodedInstruction insn = mir->dalvikInsn;
  std::string str;
  int flags = 0;
  int opcode = insn.opcode;
  char* ret;
  bool nop = false;
  SSARepresentation* ssa_rep = mir->ssa_rep;
  Instruction::Format dalvik_format = Instruction::k10x;  // Default to no-operand format
  int defs = (ssa_rep != NULL) ? ssa_rep->num_defs : 0;
  int uses = (ssa_rep != NULL) ? ssa_rep->num_uses : 0;

  // Handle special cases.
  if ((opcode == kMirOpCheck) || (opcode == kMirOpCheckPart2)) {
    str.append(extended_mir_op_names[opcode - kMirOpFirst]);
    str.append(": ");
    // Recover the original Dex instruction
    insn = mir->meta.throw_insn->dalvikInsn;
    ssa_rep = mir->meta.throw_insn->ssa_rep;
    defs = ssa_rep->num_defs;
    uses = ssa_rep->num_uses;
    opcode = insn.opcode;
  } else if (opcode == kMirOpNop) {
    str.append("[");
    insn.opcode = mir->meta.original_opcode;
    opcode = mir->meta.original_opcode;
    nop = true;
  }

  if (opcode >= kMirOpFirst) {
    str.append(extended_mir_op_names[opcode - kMirOpFirst]);
  } else {
    dalvik_format = Instruction::FormatOf(insn.opcode);
    flags = Instruction::FlagsOf(insn.opcode);
    str.append(Instruction::Name(insn.opcode));
  }

  if (opcode == kMirOpPhi) {
    int* incoming = reinterpret_cast<int*>(insn.vB);
    str.append(StringPrintf(" %s = (%s",
               GetSSANameWithConst(cu, ssa_rep->defs[0], true).c_str(),
               GetSSANameWithConst(cu, ssa_rep->uses[0], true).c_str()));
    str.append(StringPrintf(":%d",incoming[0]));
    int i;
    for (i = 1; i < uses; i++) {
      str.append(StringPrintf(", %s:%d",
                              GetSSANameWithConst(cu, ssa_rep->uses[i], true).c_str(),
                              incoming[i]));
    }
    str.append(")");
  } else if ((flags & Instruction::kBranch) != 0) {
    // For branches, decode the instructions to print out the branch targets.
    int offset = 0;
    switch (dalvik_format) {
      case Instruction::k21t:
        str.append(StringPrintf(" %s,", GetSSANameWithConst(cu, ssa_rep->uses[0], false).c_str()));
        offset = insn.vB;
        break;
      case Instruction::k22t:
        str.append(StringPrintf(" %s, %s,", GetSSANameWithConst(cu, ssa_rep->uses[0], false).c_str(),
                   GetSSANameWithConst(cu, ssa_rep->uses[1], false).c_str()));
        offset = insn.vC;
        break;
      case Instruction::k10t:
      case Instruction::k20t:
      case Instruction::k30t:
        offset = insn.vA;
        break;
      default:
        LOG(FATAL) << "Unexpected branch format " << dalvik_format << " from " << insn.opcode;
    }
    str.append(StringPrintf(" 0x%x (%c%x)", mir->offset + offset,
                            offset > 0 ? '+' : '-', offset > 0 ? offset : -offset));
  } else {
    // For invokes-style formats, treat wide regs as a pair of singles
    bool show_singles = ((dalvik_format == Instruction::k35c) ||
                         (dalvik_format == Instruction::k3rc));
    if (defs != 0) {
      str.append(StringPrintf(" %s", GetSSANameWithConst(cu, ssa_rep->defs[0], false).c_str()));
      if (uses != 0) {
        str.append(", ");
      }
    }
    for (int i = 0; i < uses; i++) {
      str.append(
          StringPrintf(" %s", GetSSANameWithConst(cu, ssa_rep->uses[i], show_singles).c_str()));
      if (!show_singles && (cu->reg_location != NULL) && cu->reg_location[i].wide) {
        // For the listing, skip the high sreg.
        i++;
      }
      if (i != (uses -1)) {
        str.append(",");
      }
    }
    switch (dalvik_format) {
      case Instruction::k11n: // Add one immediate from vB
      case Instruction::k21s:
      case Instruction::k31i:
      case Instruction::k21h:
        str.append(StringPrintf(", #%d", insn.vB));
        break;
      case Instruction::k51l: // Add one wide immediate
        str.append(StringPrintf(", #%lld", insn.vB_wide));
        break;
      case Instruction::k21c: // One register, one string/type/method index
      case Instruction::k31c:
        str.append(StringPrintf(", index #%d", insn.vB));
        break;
      case Instruction::k22c: // Two registers, one string/type/method index
        str.append(StringPrintf(", index #%d", insn.vC));
        break;
      case Instruction::k22s: // Add one immediate from vC
      case Instruction::k22b:
        str.append(StringPrintf(", #%d", insn.vC));
        break;
      default:
        ; // Nothing left to print
      }
  }
  if (nop) {
    str.append("]--optimized away");
  }
  int length = str.length() + 1;
  ret = static_cast<char*>(NewMem(cu, length, false, kAllocDFInfo));
  strncpy(ret, str.c_str(), length);
  return ret;
}
}  // namespace art