xref: /dalvik/vm/compiler/codegen/x86/AnalysisO1.cpp

/*
 * Copyright (C) 2012 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.
 */


/*! \file AnalysisO1.cpp
  \brief This file implements register allocator, constant folding
*/
#include "libdex/DexOpcodes.h"
#include "libdex/DexFile.h"
#include "Lower.h"
#include "interp/InterpState.h"
#include "interp/InterpDefs.h"
#include "libdex/Leb128.h"

/* compilation flags to turn on debug printout */
//#define DEBUG_COMPILE_TABLE
//#define DEBUG_ALLOC_CONSTRAINT
//#define DEBUG_REGALLOC
//#define DEBUG_REG_USED
//#define DEBUG_REFCOUNT
//#define DEBUG_REACHING_DEF2
//#define DEBUG_REACHING_DEF
//#define DEBUG_LIVE_RANGE
//#define DEBUG_MOVE_OPT
//#define DEBUG_SPILL
//#define DEBUG_ENDOFBB
//#define DEBUG_CONST
/*
  #define DEBUG_XFER_POINTS
  #define DEBUG_DSE
  #define DEBUG_CFG
  #define DEBUG_GLOBALTYPE
  #define DEBUG_STATE
  #define DEBUG_COMPILE_TABLE
  #define DEBUG_VIRTUAL_INFO
  #define DEBUG_MOVE_OPT
  #define DEBUG_MERGE_ENTRY
  #define DEBUG_INVALIDATE
*/
#include "AnalysisO1.h"

void dumpCompileTable();

/* There are 3 kinds of variables that are handled in this file:
   1> virtual register (isVirtualReg())
   2> temporary (!isVirtualReg() && regNum < PhysicalReg_GLUE_DVMDEX)
   3> glue variables: regNum >= PhysicalReg_GLUE_DVMDEX
*/
/** check whether a variable is a virtual register
 */
bool isVirtualReg(int type) {
    if((type & LowOpndRegType_virtual) != 0) return true;
    return false;
}
bool isTemporary(int type, int regNum) {
    if(!isVirtualReg(type) && regNum < PhysicalReg_GLUE_DVMDEX) return true;
    return false;
}

/** convert type defined in lowering module to type defined in register allocator
    in lowering module <type, isPhysical>
    in register allocator: LowOpndRegType_hard LowOpndRegType_virtual LowOpndRegType_scratch
*/
int convertType(int type, int reg, bool isPhysical) {
    int newType = type;
    if(isPhysical) newType |= LowOpndRegType_hard;
    if(isVirtualReg(type)) newType |= LowOpndRegType_virtual;
    else {
        /* reg number for a VR can exceed PhysicalReg_SCRATCH_1 */
        if(reg >= PhysicalReg_SCRATCH_1 && reg < PhysicalReg_GLUE_DVMDEX)
            newType |= LowOpndRegType_scratch;
    }
    return newType;
}

/** return the size of a variable
 */
OpndSize getRegSize(int type) {
    if((type & MASK_FOR_TYPE) == LowOpndRegType_xmm) return OpndSize_64;
    if((type & MASK_FOR_TYPE) == LowOpndRegType_fs) return OpndSize_64;
    /* for type _gp, _fs_s, _ss */
    return OpndSize_32;
}

/*
   Overlapping cases between two variables A and B
   layout for A,B   isAPartiallyOverlapB  isBPartiallyOverlapA
   1> |__|  |____|         OVERLAP_ALIGN        OVERLAP_B_COVER_A
      |__|  |____|
   2> |____|           OVERLAP_B_IS_LOW_OF_A    OVERLAP_B_COVER_LOW_OF_A
        |__|
   3> |____|           OVERLAP_B_IS_HIGH_OF_A   OVERLAP_B_COVER_HIGH_OF_A
      |__|
   4> |____|      OVERLAP_LOW_OF_A_IS_HIGH_OF_B OVERLAP_B_COVER_LOW_OF_A
         |____|
   5>    |____|   OVERLAP_HIGH_OF_A_IS_LOW_OF_B OVERLAP_B_COVER_HIGH_OF_A
      |____|
   6>   |__|           OVERLAP_A_IS_LOW_OF_B    OVERLAP_B_COVER_A
      |____|
   7> |__|             OVERLAP_A_IS_HIGH_OF_B   OVERLAP_B_COVER_A
      |____|
*/
/** determine the overlapping between variable B and A
*/
OverlapCase getBPartiallyOverlapA(int regB, LowOpndRegType tB, int regA, LowOpndRegType tA) {
    if(getRegSize(tA) == getRegSize(tB) && regA == regB) return OVERLAP_B_COVER_A;
    if(getRegSize(tA) == OpndSize_64 && getRegSize(tB) == OpndSize_32 && regA == regB) return OVERLAP_B_COVER_LOW_OF_A;
    if(getRegSize(tA) == OpndSize_64 && getRegSize(tB) == OpndSize_32 && regB == regA + 1) return OVERLAP_B_COVER_HIGH_OF_A;
    if(getRegSize(tA) == OpndSize_32 && getRegSize(tB) == OpndSize_64 && (regA == regB || regA == regB+1)) return OVERLAP_B_COVER_A;
    if(getRegSize(tB) == OpndSize_64 && getRegSize(tA) == OpndSize_64 && regA == regB+1) return OVERLAP_B_COVER_LOW_OF_A;
    if(getRegSize(tB) == OpndSize_64 && getRegSize(tA) == OpndSize_64 && regB == regA+1) return OVERLAP_B_COVER_HIGH_OF_A;
    return OVERLAP_NO;
}

/** determine overlapping between variable A and B
*/
OverlapCase getAPartiallyOverlapB(int regA, LowOpndRegType tA, int regB, LowOpndRegType tB) {
    if(getRegSize(tA) == getRegSize(tB) && regA == regB) return OVERLAP_ALIGN;
    if(getRegSize(tA) == OpndSize_64 && getRegSize(tB) == OpndSize_32 && regA == regB)
        return OVERLAP_B_IS_LOW_OF_A;
    if(getRegSize(tA) == OpndSize_64 && getRegSize(tB) == OpndSize_32 && regB == regA+1)
        return OVERLAP_B_IS_HIGH_OF_A;
    if(getRegSize(tB) == OpndSize_64 && getRegSize(tA) == OpndSize_64 && regA == regB+1)
        return OVERLAP_LOW_OF_A_IS_HIGH_OF_B;
    if(getRegSize(tB) == OpndSize_64 && getRegSize(tA) == OpndSize_64 && regB == regA+1)
        return OVERLAP_HIGH_OF_A_IS_LOW_OF_B;
    if(getRegSize(tA) == OpndSize_32 && getRegSize(tB) == OpndSize_64 && regA == regB)
        return OVERLAP_A_IS_LOW_OF_B;
    if(getRegSize(tA) == OpndSize_32 && getRegSize(tB) == OpndSize_64 && regA == regB+1)
        return OVERLAP_A_IS_HIGH_OF_B;
    return OVERLAP_NO;
}

/** determine whether variable A fully covers B
 */
bool isAFullyCoverB(int regA, LowOpndRegType tA, int regB, LowOpndRegType tB) {
    if(getRegSize(tB) == OpndSize_32) return true;
    if(getRegSize(tA) == getRegSize(tB) && regA == regB) return true;
    return false;
}

/*
   RegAccessType accessType
   1> DefOrUse.accessType
      can only be D(VR), L(low part of VR), H(high part of VR), N(none)
      for def, it means which part of the VR is live
      for use, it means which part of the VR comes from the def
   2> VirtualRegInfo.accessType
      for currentInfo, it can only be a combination of U & D
      for entries in infoBasicBlock, it can be a combination of U & D|L|H
*/

/*
   Key data structures used:
   1> BasicBlock_O1
      VirtualRegInfo infoBasicBlock[]
      DefUsePair* defUseTable
      XferPoint xferPoints[]
   2> MemoryVRInfo memVRTable[]
      LiveRange* ranges
   3> compileTableEntry compileTable[]
   4> VirtualRegInfo
      DefOrUse reachingDefs[3]
   5> DefUsePair, LiveRange
*/

//! one entry for each variable used

//! a variable can be virtual register, or a temporary (can be hard-coded)
compileTableEntry compileTable[COMPILE_TABLE_SIZE];
int num_compile_entries;
//! tables to save the states of register allocation
regAllocStateEntry1 stateTable1_1[COMPILE_TABLE_SIZE];
regAllocStateEntry1 stateTable1_2[COMPILE_TABLE_SIZE];
regAllocStateEntry1 stateTable1_3[COMPILE_TABLE_SIZE];
regAllocStateEntry1 stateTable1_4[COMPILE_TABLE_SIZE];
regAllocStateEntry2 stateTable2_1[COMPILE_TABLE_SIZE];
regAllocStateEntry2 stateTable2_2[COMPILE_TABLE_SIZE];
regAllocStateEntry2 stateTable2_3[COMPILE_TABLE_SIZE];
regAllocStateEntry2 stateTable2_4[COMPILE_TABLE_SIZE];

//! array of VirtualRegInfo to store VRs accessed by a single bytecode
VirtualRegInfo infoByteCode[MAX_REG_PER_BYTECODE];
int num_regs_per_bytecode;
//! array of TempRegInfo to store temporaries accessed by a single bytecode
TempRegInfo infoByteCodeTemp[MAX_TEMP_REG_PER_BYTECODE];
int num_temp_regs_per_bytecode;
//! array of MemoryVRInfo to store whether a VR is in memory
#define NUM_MEM_VR_ENTRY 140
MemoryVRInfo memVRTable[NUM_MEM_VR_ENTRY];
int num_memory_vr;

CompilationUnit* currentUnit = NULL;

//! the current basic block
BasicBlock_O1* currentBB = NULL;
//! array of RegisterInfo for all the physical registers
RegisterInfo allRegs[PhysicalReg_GLUE+1]; //initialized in codeGen

VirtualRegInfo currentInfo;
VirtualRegInfo tmpInfo;

//! this array says whether a spill location is used (0 means not used, 1 means used)
int spillIndexUsed[MAX_SPILL_JIT_IA];
int indexForGlue = -1;

int num_bbs_for_method;
//! array of basic blocks in a method in program order
BasicBlock_O1* method_bbs_sorted[MAX_NUM_BBS_PER_METHOD];
//! the entry basic block
BasicBlock_O1* bb_entry;
int pc_start = -1;
int pc_end = -1;

//!array of PCs for exception handlers
int exceptionHandlers[10];
int num_exception_handlers;

bool canSpillReg[PhysicalReg_Null]; //physical registers that should not be spilled
int inGetVR_num = -1;
int inGetVR_type;

///////////////////////////////////////////////////////////////////////////////
// FORWARD FUNCTION DECLARATION
void addExceptionHandler(s4 tmp);

int createCFG(Method* method);
int collectInfoOfBasicBlock(Method* method, BasicBlock_O1* bb);
void dumpVirtualInfoOfBasicBlock(BasicBlock_O1* bb);
void setTypeOfVR();
void insertGlueReg();
void dumpVirtualInfoOfMethod();
int codeGenBasicBlock(const Method* method, BasicBlock_O1* bb);

//used in collectInfoOfBasicBlock: getVirtualRegInfo
int mergeEntry2(BasicBlock_O1* bb);
int sortAllocConstraint(RegAllocConstraint* allocConstraints,
                        RegAllocConstraint* allocConstraintsSorted, bool fromHighToLow);

//used in codeGenBasicBlock
void insertFromVirtualInfo(BasicBlock_O1* bb, int k); //update compileTable
void insertFromTempInfo(int k); //update compileTable
int updateXferPoints();
void updateLiveTable();
void printDefUseTable();
bool isFirstOfHandler(BasicBlock_O1* bb);

//used in mergeEntry2
//following functions will not update global data structure
RegAccessType mergeAccess2(RegAccessType A, RegAccessType B, OverlapCase isBPartiallyOverlapA);
RegAccessType updateAccess1(RegAccessType A, OverlapCase isAPartiallyOverlapB); //will not update global data structure
RegAccessType updateAccess2(RegAccessType C1, RegAccessType C2);
RegAccessType updateAccess3(RegAccessType C, RegAccessType B);

void updateDefUseTable();
void updateReachingDefA(int indexToA, OverlapCase isBPartiallyOverlapA);
void updateReachingDefB1(int indexToA);
void updateReachingDefB2();
void updateReachingDefB3();

RegAccessType insertAUse(DefUsePair* ptr, int offsetPC, int regNum, LowOpndRegType physicalType);
DefUsePair* insertADef(int offsetPC, int regNum, LowOpndRegType pType, RegAccessType rType);
RegAccessType insertDefUsePair(int reachingDefIndex);

//used in updateXferPoints
int fakeUsageAtEndOfBB(BasicBlock_O1* bb);
void insertLoadXfer(int offset, int regNum, LowOpndRegType pType);
int searchMemTable(int regNum);
void mergeLiveRange(int tableIndex, int rangeStart, int rangeEnd);
//used in updateLiveTable
RegAccessType setAccessTypeOfUse(OverlapCase isDefPartiallyOverlapUse, RegAccessType reachingDefLive);
DefUsePair* searchDefUseTable(int offsetPC, int regNum, LowOpndRegType pType);
void insertAccess(int tableIndex, LiveRange* startP, int rangeStart);

//register allocation
int spillLogicalReg(int spill_index, bool updateTable);

/** check whether the current bytecode is IF or GOTO or SWITCH
 */
bool isCurrentByteCodeJump() {
    u2 inst_op = INST_INST(inst);
    if(inst_op == OP_IF_EQ || inst_op == OP_IF_NE || inst_op == OP_IF_LT ||
       inst_op == OP_IF_GE || inst_op == OP_IF_GT || inst_op == OP_IF_LE) return true;
    if(inst_op == OP_IF_EQZ || inst_op == OP_IF_NEZ || inst_op == OP_IF_LTZ ||
       inst_op == OP_IF_GEZ || inst_op == OP_IF_GTZ || inst_op == OP_IF_LEZ) return true;
    if(inst_op == OP_GOTO || inst_op == OP_GOTO_16 || inst_op == OP_GOTO_32) return true;
    if(inst_op == OP_PACKED_SWITCH || inst_op == OP_SPARSE_SWITCH) return true;
    return false;
}

/* this function is called before code generation of basic blocks
   initialize data structure allRegs, which stores information for each physical register,
   whether it is used, when it was last freed, whether it is callee-saved */
void initializeAllRegs() {
    int k;
    for(k = PhysicalReg_EAX; k <= PhysicalReg_EBP; k++) {
        allRegs[k].physicalReg = (PhysicalReg) k;
        if(k == PhysicalReg_EDI || k == PhysicalReg_ESP || k == PhysicalReg_EBP)
            allRegs[k].isUsed = true;
        else {
            allRegs[k].isUsed = false;
            allRegs[k].freeTimeStamp = -1;
        }
        if(k == PhysicalReg_EBX || k == PhysicalReg_EBP || k == PhysicalReg_ESI || k == PhysicalReg_EDI)
            allRegs[k].isCalleeSaved = true;
        else
            allRegs[k].isCalleeSaved = false;
    }
    for(k = PhysicalReg_XMM0; k <= PhysicalReg_XMM7; k++) {
        allRegs[k].physicalReg = (PhysicalReg) k;
        allRegs[k].isUsed = false;
        allRegs[k].freeTimeStamp = -1;
        allRegs[k].isCalleeSaved = false;
    }
}

/** sync up allRegs (isUsed & freeTimeStamp) with compileTable
    global data: RegisterInfo allRegs[PhysicalReg_Null]
    update allRegs[EAX to XMM7] except EDI,ESP,EBP
    update RegisterInfo.isUsed & RegisterInfo.freeTimeStamp
        if the physical register was used and is not used now
*/
void syncAllRegs() {
    int k, k2;
    for(k = PhysicalReg_EAX; k <= PhysicalReg_XMM7; k++) {
        if(k == PhysicalReg_EDI || k == PhysicalReg_ESP || k == PhysicalReg_EBP)
            continue;
        //check whether the physical register is used by any logical register
        bool stillUsed = false;
        for(k2 = 0; k2 < num_compile_entries; k2++) {
            if(compileTable[k2].physicalReg == k) {
                stillUsed = true;
                break;
            }
        }
        if(stillUsed && !allRegs[k].isUsed) {
            allRegs[k].isUsed = true;
        }
        if(!stillUsed && allRegs[k].isUsed) {
            allRegs[k].isUsed = false;
            allRegs[k].freeTimeStamp = lowOpTimeStamp;
        }
    }
    return;
}

//!sync up spillIndexUsed with compileTable

//!
void updateSpillIndexUsed() {
    int k;
    for(k = 0; k <= MAX_SPILL_JIT_IA-1; k++) spillIndexUsed[k] = 0;
    for(k = 0; k < num_compile_entries; k++) {
        if(isVirtualReg(compileTable[k].physicalType)) continue;
        if(compileTable[k].spill_loc_index >= 0) {
            if(compileTable[k].spill_loc_index > 4*(MAX_SPILL_JIT_IA-1))
                ALOGE("spill_loc_index is wrong for entry %d: %d",
                      k, compileTable[k].spill_loc_index);
            spillIndexUsed[compileTable[k].spill_loc_index >> 2] = 1;
        }
    }
}

/* free memory used in all basic blocks */
void freeCFG() {
    int k;
    for(k = 0; k < num_bbs_for_method; k++) {
        /* free defUseTable for method_bbs_sorted[k] */
        DefUsePair* ptr = method_bbs_sorted[k]->defUseTable;
        while(ptr != NULL) {
            DefUsePair* tmp = ptr->next;
            /* free ptr->uses */
            DefOrUseLink* ptrUse = ptr->uses;
            while(ptrUse != NULL) {
                DefOrUseLink* tmp2 = ptrUse->next;
                free(ptrUse);
                ptrUse = tmp2;
            }
            free(ptr);
            ptr = tmp;
        }
        free(method_bbs_sorted[k]);
    }
}

/* update compileTable.physicalReg, compileTable.spill_loc_index & allRegs.isUsed
   for glue-related variables, they do not exist
       not in a physical register (physicalReg is Null)
       not in a spilled memory location (spill_loc_index is -1)
*/
void initializeRegStateOfBB(BasicBlock_O1* bb) {
    //for GLUE variables, do not exist
    int k;
    for(k = 0; k < num_compile_entries; k++) {
        /* trace-based JIT: there is no VR with GG type */
        if(isVirtualReg(compileTable[k].physicalType) && compileTable[k].gType == GLOBALTYPE_GG) {
            if(bb->bb_index > 0) { //non-entry block
                if(isFirstOfHandler(bb)) {
                    /* at the beginning of an exception handler, GG VR is in the interpreted stack */
                    compileTable[k].physicalReg = PhysicalReg_Null;
#ifdef DEBUG_COMPILE_TABLE
                    ALOGI("at the first basic block of an exception handler, GG VR %d type %d is in memory",
                          compileTable[k].regNum, compileTable[k].physicalType);
#endif
                } else {
                    if(compileTable[k].physicalReg == PhysicalReg_Null) {
                        /* GG VR is in a specific physical register */
                        compileTable[k].physicalReg = compileTable[k].physicalReg_prev;
                    }
                    int tReg = compileTable[k].physicalReg;
                    allRegs[tReg].isUsed = true;
#ifdef DEBUG_REG_USED
                    ALOGI("REGALLOC: physical reg %d is used by a GG VR %d %d at beginning of BB", tReg, compileTable[k].regNum, compileTable[k].physicalType);
#endif
                }
            } //non-entry block
        } //if GG VR
        if(compileTable[k].regNum != PhysicalReg_GLUE &&
           compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX) {
            /* glue related registers */
            compileTable[k].physicalReg = PhysicalReg_Null;
            compileTable[k].spill_loc_index = -1;
        }
    }
}

/* update memVRTable[].nullCheckDone */
void initializeNullCheck(int indexToMemVR) {
    bool found = false;
#ifdef GLOBAL_NULLCHECK_OPT
    /* search nullCheck_inB of the current Basic Block */
    for(k = 0; k < nullCheck_inSize[currentBB->bb_index2]; k++) {
        if(nullCheck_inB[currentBB->bb_index2][k] == memVRTable[indexToMemVR].regNum) {
            found = true;
            break;
        }
    }
#endif
    memVRTable[indexToMemVR].nullCheckDone = found;
}

/* initialize memVRTable */
void initializeMemVRTable() {
    num_memory_vr = 0;
    int k;
    for(k = 0; k < num_compile_entries; k++) {
        if(!isVirtualReg(compileTable[k].physicalType)) continue;
        /* VRs in compileTable */
        bool setToInMemory = (compileTable[k].physicalReg == PhysicalReg_Null);
        int regNum = compileTable[k].regNum;
        OpndSize sizeVR = getRegSize(compileTable[k].physicalType);
        /* search memVRTable for the VR in compileTable */
        int kk;
        int indexL = -1;
        int indexH = -1;
        for(kk = 0; kk < num_memory_vr; kk++) {
            if(memVRTable[kk].regNum == regNum) {
                indexL = kk;
                continue;
            }
            if(memVRTable[kk].regNum == regNum+1 && sizeVR == OpndSize_64) {
                indexH = kk;
                continue;
            }
        }
        if(indexL < 0) {
            /* the low half of VR is not in memVRTable
               add an entry for the low half in memVRTable */
            if(num_memory_vr >= NUM_MEM_VR_ENTRY) {
                ALOGE("exceeds size of memVRTable");
                dvmAbort();
            }
            memVRTable[num_memory_vr].regNum = regNum;
            memVRTable[num_memory_vr].inMemory = setToInMemory;
            initializeNullCheck(num_memory_vr); //set nullCheckDone
            memVRTable[num_memory_vr].boundCheck.checkDone = false;
            memVRTable[num_memory_vr].num_ranges = 0;
            memVRTable[num_memory_vr].ranges = NULL;
            memVRTable[num_memory_vr].delayFreeFlags = VRDELAY_NONE;
            num_memory_vr++;
        }
        if(sizeVR == OpndSize_64 && indexH < 0) {
            /* the high half of VR is not in memVRTable
               add an entry for the high half in memVRTable */
            if(num_memory_vr >= NUM_MEM_VR_ENTRY) {
                ALOGE("exceeds size of memVRTable");
                dvmAbort();
            }
            memVRTable[num_memory_vr].regNum = regNum+1;
            memVRTable[num_memory_vr].inMemory = setToInMemory;
            initializeNullCheck(num_memory_vr);
            memVRTable[num_memory_vr].boundCheck.checkDone = false;
            memVRTable[num_memory_vr].num_ranges = 0;
            memVRTable[num_memory_vr].ranges = NULL;
            memVRTable[num_memory_vr].delayFreeFlags = VRDELAY_NONE;
            num_memory_vr++;
        }
    }
}

/* create a O1 basic block from basic block constructed in JIT MIR */
BasicBlock_O1* createBasicBlockO1(BasicBlock* bb) {
    BasicBlock_O1* bb1 = createBasicBlock(0, -1);
    bb1->jitBasicBlock = bb;
    return bb1;
}

/* a basic block in JIT MIR can contain bytecodes that are not in program order
   for example, a "goto" bytecode will be followed by the goto target */
void preprocessingBB(BasicBlock* bb) {
    currentBB = createBasicBlockO1(bb);
    /* initialize currentBB->allocConstraints */
    int ii;
    for(ii = 0; ii < 8; ii++) {
        currentBB->allocConstraints[ii].physicalReg = (PhysicalReg)ii;
        currentBB->allocConstraints[ii].count = 0;
    }
    collectInfoOfBasicBlock(currentMethod, currentBB);
#ifdef DEBUG_COMPILE_TABLE
    dumpVirtualInfoOfBasicBlock(currentBB);
#endif
    currentBB = NULL;
}

void preprocessingTrace() {
    int k, k2, k3, jj;
    /* this is a simplified verson of setTypeOfVR()
        all VRs are assumed to be GL, no VR will be GG
    */
    for(k = 0; k < num_bbs_for_method; k++)
        for(jj = 0; jj < method_bbs_sorted[k]->num_regs; jj++)
            method_bbs_sorted[k]->infoBasicBlock[jj].gType = GLOBALTYPE_GL;

    /* insert a glue-related register GLUE_DVMDEX to compileTable */
    insertGlueReg();

    int compile_entries_old = num_compile_entries;
    for(k2 = 0; k2 < num_bbs_for_method; k2++) {
        currentBB = method_bbs_sorted[k2];
        /* update compileTable with virtual register from currentBB */
        for(k3 = 0; k3 < currentBB->num_regs; k3++) {
            insertFromVirtualInfo(currentBB, k3);
        }

        /* for each GL|GG type VR, insert fake usage at end of basic block to keep it live */
        int offsetPC_back = offsetPC;
        offsetPC = PC_FOR_END_OF_BB;
        for(k = 0; k < num_compile_entries; k++) {
            currentInfo.regNum = compileTable[k].regNum;
            currentInfo.physicalType = (LowOpndRegType)compileTable[k].physicalType;
            if(isVirtualReg(compileTable[k].physicalType) &&
               compileTable[k].gType == GLOBALTYPE_GL) {
                /* update defUseTable by assuming a fake usage at END of a basic block for variable @ currentInfo */
                fakeUsageAtEndOfBB(currentBB);
            }
            if(isVirtualReg(compileTable[k].physicalType) &&
               compileTable[k].gType == GLOBALTYPE_GG) {
                fakeUsageAtEndOfBB(currentBB);
            }
        }
        offsetPC = offsetPC_back;
        num_compile_entries = compile_entries_old;
    }
    /* initialize data structure allRegs */
    initializeAllRegs();
#ifdef DEBUG_COMPILE_TABLE
    dumpCompileTable();
#endif
    currentBB = NULL;
}

void printJitTraceInfoAtRunTime(const Method* method, int offset) {
    ALOGI("execute trace for %s%s at offset %x", method->clazz->descriptor, method->name, offset);
}

void startOfTraceO1(const Method* method, LowOpBlockLabel* labelList, int exceptionBlockId, CompilationUnit *cUnit) {
    num_exception_handlers = 0;
    num_compile_entries = 0;
    currentBB = NULL;
    pc_start = -1;
    bb_entry = NULL;
    num_bbs_for_method = 0;
    currentUnit = cUnit;
    lowOpTimeStamp = 0;

// dumpDebuggingInfo is gone in CompilationUnit struct
#if 0
    /* add code to dump debugging information */
    if(cUnit->dumpDebuggingInfo) {
        move_imm_to_mem(OpndSize_32, cUnit->startOffset, -4, PhysicalReg_ESP, true); //2nd argument: offset
        move_imm_to_mem(OpndSize_32, (int)currentMethod, -8, PhysicalReg_ESP, true); //1st argument: method
        load_effective_addr(-8, PhysicalReg_ESP, true, PhysicalReg_ESP, true);

        typedef void (*vmHelper)(const Method*, int);
        vmHelper funcPtr = printJitTraceInfoAtRunTime;
        move_imm_to_reg(OpndSize_32, (int)funcPtr, PhysicalReg_ECX, true);
        call_reg(PhysicalReg_ECX, true);

        load_effective_addr(8, PhysicalReg_ESP, true, PhysicalReg_ESP, true);
    }
#endif
}


/* Code generation for a basic block defined for JIT
   We have two data structures for a basic block:
       BasicBlock defined in vm/compiler by JIT
       BasicBlock_O1 defined in o1 */
int codeGenBasicBlockJit(const Method* method, BasicBlock* bb) {
    /* search method_bbs_sorted to find the O1 basic block corresponding to bb */
    int k;
    for(k = 0; k < num_bbs_for_method; k++) {
        if(method_bbs_sorted[k]->jitBasicBlock == bb) {
            lowOpTimeStamp = 0; //reset time stamp at start of a basic block
            currentBB = method_bbs_sorted[k];
            int cg_ret = codeGenBasicBlock(method, currentBB);
            currentBB = NULL;
            return cg_ret;
        }
    }
    ALOGE("can't find the corresponding O1 basic block for id %d type %d",
         bb->id, bb->blockType);
    return -1;
}
void endOfBasicBlock(BasicBlock* bb) {
    isScratchPhysical = true;
    currentBB = NULL;
}
void endOfTraceO1() {
     freeCFG();
}

/** entry point to collect information about virtual registers used in a basic block
    Initialize data structure BasicBlock_O1
    The usage information of virtual registers is stoerd in bb->infoBasicBlock

    Global variables accessed: offsetPC, rPC
*/
int collectInfoOfBasicBlock(Method* method, BasicBlock_O1* bb) {
    bb->num_regs = 0;
    bb->num_defs = 0;
    bb->defUseTable = NULL;
    bb->defUseTail = NULL;
    u2* rPC_start = (u2*)method->insns;
    int kk;
    bb->endsWithReturn = false;
    bb->hasAccessToGlue = false;

    MIR* mir;
    int seqNum = 0;
    /* traverse the MIR in basic block
       sequence number is used to make sure next bytecode will have a larger sequence number */
    for(mir = bb->jitBasicBlock->firstMIRInsn; mir; mir = mir->next) {
        offsetPC = seqNum;
        mir->seqNum = seqNum++;
        rPC = rPC_start + mir->offset;
#ifdef WITH_JIT_INLINING
        if(mir->dalvikInsn.opcode >= kMirOpFirst &&
           mir->dalvikInsn.opcode != kMirOpCheckInlinePrediction) continue;
        if(ir->dalvikInsn.opcode == kMirOpCheckInlinePrediction) { //TODO
        }
#else
        if(mir->dalvikInsn.opcode >= kNumPackedOpcodes) continue;
#endif
        inst = FETCH(0);
        u2 inst_op = INST_INST(inst);
        /* update bb->hasAccessToGlue */
        if((inst_op >= OP_MOVE_RESULT && inst_op <= OP_RETURN_OBJECT) ||
           (inst_op >= OP_MONITOR_ENTER && inst_op <= OP_INSTANCE_OF) ||
           (inst_op == OP_FILLED_NEW_ARRAY) ||
           (inst_op == OP_FILLED_NEW_ARRAY_RANGE) ||
           (inst_op == OP_THROW) ||
           (inst_op >= OP_INVOKE_VIRTUAL && inst_op <= OP_INVOKE_INTERFACE_RANGE) ||
           (inst_op >= OP_THROW_VERIFICATION_ERROR &&
            inst_op <= OP_EXECUTE_INLINE_RANGE) ||
           (inst_op >= OP_INVOKE_VIRTUAL_QUICK && inst_op <= OP_INVOKE_SUPER_QUICK_RANGE))
            bb->hasAccessToGlue = true;
        /* update bb->endsWithReturn */
        if(inst_op == OP_RETURN_VOID || inst_op == OP_RETURN || inst_op == OP_RETURN_VOID_BARRIER ||
           inst_op == OP_RETURN_OBJECT || inst_op == OP_RETURN_WIDE)
            bb->endsWithReturn = true;

        /* get virtual register usage in current bytecode */
        getVirtualRegInfo(infoByteCode);
        int num_regs = num_regs_per_bytecode;
        for(kk = 0; kk < num_regs; kk++) {
            currentInfo = infoByteCode[kk];
#ifdef DEBUG_MERGE_ENTRY
            ALOGI("call mergeEntry2 at offsetPC %x kk %d VR %d %d", offsetPC, kk,
                  currentInfo.regNum, currentInfo.physicalType);
#endif
            mergeEntry2(bb); //update defUseTable of the basic block
        }

        //dumpVirtualInfoOfBasicBlock(bb);
    }//for each bytecode

    bb->pc_end = seqNum;

    //sort allocConstraints of each basic block
    for(kk = 0; kk < bb->num_regs; kk++) {
#ifdef DEBUG_ALLOC_CONSTRAINT
        ALOGI("sort virtual reg %d type %d -------", bb->infoBasicBlock[kk].regNum,
              bb->infoBasicBlock[kk].physicalType);
#endif
        sortAllocConstraint(bb->infoBasicBlock[kk].allocConstraints,
                            bb->infoBasicBlock[kk].allocConstraintsSorted, true);
    }
#ifdef DEBUG_ALLOC_CONSTRAINT
    ALOGI("sort constraints for BB %d --------", bb->bb_index);
#endif
    sortAllocConstraint(bb->allocConstraints, bb->allocConstraintsSorted, false);
    return 0;
}

/** entry point to generate native code for a O1 basic block
    There are 3 kinds of virtual registers in a O1 basic block:
    1> L VR: local within the basic block
    2> GG VR: is live in other basic blocks,
              its content is in a pre-defined GPR at the beginning of a basic block
    3> GL VR: is live in other basic blocks,
              its content is in the interpreted stack at the beginning of a basic block
    compileTable is updated with infoBasicBlock at the start of the basic block;
    Before lowering each bytecode, compileTable is updated with infoByteCodeTemp;
    At end of the basic block, right before the jump instruction, handles constant VRs and GG VRs
*/
int codeGenBasicBlock(const Method* method, BasicBlock_O1* bb) {
    /* we assume at the beginning of each basic block,
       all GL VRs reside in memory and all GG VRs reside in predefined physical registers,
       so at the end of a basic block, recover a spilled GG VR, store a GL VR to memory */
    /* update compileTable with entries in bb->infoBasicBlock */
    int k;
    for(k = 0; k < bb->num_regs; k++) {
        insertFromVirtualInfo(bb, k);
    }
    updateXferPoints(); //call fakeUsageAtEndOfBB
#ifdef DEBUG_REACHING_DEF
    printDefUseTable();
#endif
#ifdef DSE_OPT
    removeDeadDefs();
    printDefUseTable();
#endif
    //clear const section of compileTable
    for(k = 0; k < num_compile_entries; k++) compileTable[k].isConst = false;
    num_const_vr = 0;
#ifdef DEBUG_COMPILE_TABLE
    ALOGI("At start of basic block %d (num of VRs %d) -------", bb->bb_index, bb->num_regs);
    dumpCompileTable();
#endif
    initializeRegStateOfBB(bb);
    initializeMemVRTable();
    updateLiveTable();
    freeReg(true);  //before code gen of a basic block, also called at end of a basic block?
#ifdef DEBUG_COMPILE_TABLE
    ALOGI("At start of basic block %d (num of VRs %d) -------", bb->bb_index, bb->num_regs);
#endif

    u2* rPC_start = (u2*)method->insns;
    bool lastByteCodeIsJump = false;
    MIR* mir;
    for(mir = bb->jitBasicBlock->firstMIRInsn; mir; mir = mir->next) {
        offsetPC = mir->seqNum;
        rPC = rPC_start + mir->offset;
#ifdef WITH_JIT_INLINING
        if(mir->dalvikInsn.opcode >= kMirOpFirst &&
           mir->dalvikInsn.opcode != kMirOpCheckInlinePrediction) {
#else
        if(mir->dalvikInsn.opcode >= kNumPackedOpcodes) {
#endif
            handleExtendedMIR(currentUnit, mir);
            continue;
        }

        inst = FETCH(0);
        //before handling a bytecode, import info of temporary registers to compileTable including refCount
        num_temp_regs_per_bytecode = getTempRegInfo(infoByteCodeTemp);
        for(k = 0; k < num_temp_regs_per_bytecode; k++) {
            if(infoByteCodeTemp[k].versionNum > 0) continue;
            insertFromTempInfo(k);
        }
        startNativeCode(-1, -1);
        for(k = 0; k <= MAX_SPILL_JIT_IA-1; k++) spillIndexUsed[k] = 0;
        //update spillIndexUsed if a glue variable was spilled
        for(k = 0; k < num_compile_entries; k++) {
            if(compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX) {
                if(compileTable[k].spill_loc_index >= 0)
                    spillIndexUsed[compileTable[k].spill_loc_index >> 2] = 1;
            }
        }
#ifdef DEBUG_COMPILE_TABLE
        ALOGI("compile table size after importing temporary info %d", num_compile_entries);
        ALOGI("before one bytecode %d (num of VRs %d) -------", bb->bb_index, bb->num_regs);
#endif
        //set isConst to true for CONST & MOVE MOVE_OBJ?
        //clear isConst to true for MOVE, MOVE_OBJ, MOVE_RESULT, MOVE_EXCEPTION ...
        bool isConst = getConstInfo(bb); //will reset isConst if a VR is updated by the bytecode
        bool isDeadStmt = false;
#ifdef DSE_OPT
        for(k = 0; k < num_dead_pc; k++) {
            if(deadPCs[k] == offsetPC) {
                isDeadStmt = true;
                break;
            }
        }
#endif
        getVirtualRegInfo(infoByteCode);
        //call something similar to mergeEntry2, but only update refCount
        //clear refCount
        for(k = 0; k < num_regs_per_bytecode; k++) {
            int indexT = searchCompileTable(LowOpndRegType_virtual | infoByteCode[k].physicalType,
                                            infoByteCode[k].regNum);
            if(indexT >= 0)
                compileTable[indexT].refCount = 0;
        }
        for(k = 0; k < num_regs_per_bytecode; k++) {
            int indexT = searchCompileTable(LowOpndRegType_virtual | infoByteCode[k].physicalType,
                                            infoByteCode[k].regNum);
            if(indexT >= 0)
                compileTable[indexT].refCount += infoByteCode[k].refCount;
        } //for k
#ifdef DSE_OPT
        if(isDeadStmt) { //search compileTable
            getVirtualRegInfo(infoByteCode);
#ifdef DEBUG_DSE
            ALOGI("DSE: stmt at offsetPC %d is dead", offsetPC);
#endif
            for(k = 0; k < num_regs_per_bytecode; k++) {
                int indexT = searchCompileTable(LowOpndRegType_virtual | infoByteCode[k].physicalType,
                                                infoByteCode[k].regNum);
                if(indexT >= 0)
                    compileTable[indexT].refCount -= infoByteCode[k].refCount;
            }
        }
#endif
        lastByteCodeIsJump = false;
        if(!isConst && !isDeadStmt)  //isDeadStmt is false when DSE_OPT is not enabled
        {
#ifdef DEBUG_COMPILE_TABLE
            dumpCompileTable();
#endif
            globalShortMap = NULL;
            if(isCurrentByteCodeJump()) lastByteCodeIsJump = true;
            //lowerByteCode will call globalVREndOfBB if it is jump
            int retCode = lowerByteCodeJit(method, rPC, mir);
            if(gDvmJit.codeCacheByteUsed + (stream - streamStart) +
                 CODE_CACHE_PADDING > gDvmJit.codeCacheSize) {
                 ALOGE("JIT code cache full");
                 gDvmJit.codeCacheFull = true;
                 return -1;
            }

            if (retCode == 1) {
                // We always fall back to the interpreter for OP_INVOKE_OBJECT_INIT_RANGE,
                // but any other failure is unexpected and should be logged.
                if (mir->dalvikInsn.opcode != OP_INVOKE_OBJECT_INIT_RANGE) {
                    ALOGE("JIT couldn't compile %s%s dex_pc=%d opcode=%d",
                          method->clazz->descriptor,
                          method->name,
                          offsetPC,
                          mir->dalvikInsn.opcode);
                }
                return -1;
            }
            updateConstInfo(bb);
            freeShortMap();
            if(retCode < 0) {
                ALOGE("error in lowering the bytecode");
                return retCode;
            }
            freeReg(true); //may dump GL VR to memory (this is necessary)
            //after each bytecode, make sure non-VRs have refCount of zero
            for(k = 0; k < num_compile_entries; k++) {
                if(isTemporary(compileTable[k].physicalType, compileTable[k].regNum)) {
#ifdef PRINT_WARNING
                    if(compileTable[k].refCount > 0) {
                        ALOGW("refCount for a temporary reg %d %d is %d after a bytecode", compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].refCount);
                    }
#endif
                    compileTable[k].refCount = 0;
                }
            }
        } else { //isConst || isDeadStmt
            //if this bytecode is the target of a jump, the mapFromBCtoNCG should be updated
            offsetNCG = stream - streamMethodStart;
            mapFromBCtoNCG[offsetPC] = offsetNCG;
#ifdef DEBUG_COMPILE_TABLE
            ALOGI("this bytecode generates a constant and has no side effect");
#endif
            freeReg(true); //may dump GL VR to memory (this is necessary)
        }
#ifdef DEBUG_COMPILE_TABLE
        ALOGI("after one bytecode BB %d (num of VRs %d)", bb->bb_index, bb->num_regs);
#endif
    }//for each bytecode
#ifdef DEBUG_COMPILE_TABLE
    dumpCompileTable();
#endif
    if(!lastByteCodeIsJump) constVREndOfBB();
    //at end of a basic block, get spilled GG VR & dump GL VR
    if(!lastByteCodeIsJump) globalVREndOfBB(method);
    //remove entries for temporary registers, L VR and GL VR
    int jj;
    for(k = 0; k < num_compile_entries; ) {
        bool removeEntry = false;
        if(isVirtualReg(compileTable[k].physicalType) && compileTable[k].gType != GLOBALTYPE_GG) {
            removeEntry = true;
        }
        if(isTemporary(compileTable[k].physicalType, compileTable[k].regNum))
            removeEntry = true;
        if(removeEntry) {
#ifdef PRINT_WARNING
            if(compileTable[k].refCount > 0)
                ALOGW("refCount for REG %d %d is %d at end of a basic block", compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].refCount);
#endif
            compileTable[k].refCount = 0;
            for(jj = k+1; jj < num_compile_entries; jj++) {
                compileTable[jj-1] = compileTable[jj];
            }
            num_compile_entries--;
        } else {
            k++;
        }
    }
    freeReg(true);
    //free LIVE TABLE
    for(k = 0; k < num_memory_vr; k++) {
        LiveRange* ptr2 = memVRTable[k].ranges;
        while(ptr2 != NULL) {
            LiveRange* tmpP = ptr2->next;
            free(ptr2->accessPC);
            free(ptr2);
            ptr2 = tmpP;
        }
    }
#ifdef DEBUG_COMPILE_TABLE
    ALOGI("At end of basic block -------");
    dumpCompileTable();
#endif
    return 0;
}

/** update infoBasicBlock & defUseTable
    input: currentInfo
    side effect: update currentInfo.reachingDefs

    update entries in infoBasicBlock by calling updateReachingDefA
    if there is no entry in infoBasicBlock for B, an entry will be created and inserted to infoBasicBlock

    defUseTable is updated to account for the access at currentInfo
    if accessType of B is U or UD, we call updateReachingDefB to update currentInfo.reachingDefs
        in order to correctly insert the usage to defUseTable
*/
int mergeEntry2(BasicBlock_O1* bb) {
    LowOpndRegType typeB = currentInfo.physicalType;
    int regB = currentInfo.regNum;
    int jj, k;
    int jjend = bb->num_regs;
    bool isMerged = false;
    bool hasAlias = false;
    OverlapCase isBPartiallyOverlapA, isAPartiallyOverlapB;
    RegAccessType tmpType = REGACCESS_N;
    currentInfo.num_reaching_defs = 0;

    /* traverse variable A in infoBasicBlock */
    for(jj = 0; jj < jjend; jj++) {
        int regA = bb->infoBasicBlock[jj].regNum;
        LowOpndRegType typeA = bb->infoBasicBlock[jj].physicalType;
        isBPartiallyOverlapA = getBPartiallyOverlapA(regB, typeB, regA, typeA);
        isAPartiallyOverlapB = getAPartiallyOverlapB(regA, typeA, regB, typeB);
        if(regA == regB && typeA == typeB) {
            /* variable A and B are aligned */
            bb->infoBasicBlock[jj].accessType = mergeAccess2(bb->infoBasicBlock[jj].accessType, currentInfo.accessType,
                                                             OVERLAP_B_COVER_A);
            bb->infoBasicBlock[jj].refCount += currentInfo.refCount;
            /* copy reaching defs of variable B from variable A */
            currentInfo.num_reaching_defs = bb->infoBasicBlock[jj].num_reaching_defs;
            for(k = 0; k < currentInfo.num_reaching_defs; k++)
                currentInfo.reachingDefs[k] = bb->infoBasicBlock[jj].reachingDefs[k];
            updateDefUseTable(); //use currentInfo to update defUseTable
            updateReachingDefA(jj, OVERLAP_B_COVER_A); //update reachingDefs of A
            isMerged = true;
            hasAlias = true;
            if(typeB == LowOpndRegType_gp) {
                //merge allocConstraints
                for(k = 0; k < 8; k++) {
                    bb->infoBasicBlock[jj].allocConstraints[k].count += currentInfo.allocConstraints[k].count;
                }
            }
        }
        else if(isBPartiallyOverlapA != OVERLAP_NO) {
            tmpType = updateAccess2(tmpType, updateAccess1(bb->infoBasicBlock[jj].accessType, isAPartiallyOverlapB));
            bb->infoBasicBlock[jj].accessType = mergeAccess2(bb->infoBasicBlock[jj].accessType, currentInfo.accessType,
                                                             isBPartiallyOverlapA);
#ifdef DEBUG_MERGE_ENTRY
            ALOGI("update accessType in case 2: VR %d %d accessType %d", regA, typeA, bb->infoBasicBlock[jj].accessType);
#endif
            hasAlias = true;
            if(currentInfo.accessType == REGACCESS_U || currentInfo.accessType == REGACCESS_UD) {
                /* update currentInfo.reachingDefs */
                updateReachingDefB1(jj);
                updateReachingDefB2();
            }
            updateReachingDefA(jj, isBPartiallyOverlapA);
        }
        else {
            //even if B does not overlap with A, B can affect the reaching defs of A
            //for example, B is a def of "v0", A is "v1"
            //  B can kill some reaching defs of A or affect the accessType of a reaching def
            updateReachingDefA(jj, OVERLAP_NO); //update reachingDefs of A
        }
    }//for each variable A in infoBasicBlock
    if(!isMerged) {
        /* create a new entry in infoBasicBlock */
        bb->infoBasicBlock[bb->num_regs].refCount = currentInfo.refCount;
        bb->infoBasicBlock[bb->num_regs].physicalType = typeB;
        if(hasAlias)
            bb->infoBasicBlock[bb->num_regs].accessType = updateAccess3(tmpType, currentInfo.accessType);
        else
            bb->infoBasicBlock[bb->num_regs].accessType = currentInfo.accessType;
#ifdef DEBUG_MERGE_ENTRY
        ALOGI("update accessType in case 3: VR %d %d accessType %d", regB, typeB, bb->infoBasicBlock[bb->num_regs].accessType);
#endif
        bb->infoBasicBlock[bb->num_regs].regNum = regB;
        for(k = 0; k < 8; k++)
            bb->infoBasicBlock[bb->num_regs].allocConstraints[k] = currentInfo.allocConstraints[k];
#ifdef DEBUG_MERGE_ENTRY
        ALOGI("isMerged is false, call updateDefUseTable");
#endif
        updateDefUseTable(); //use currentInfo to update defUseTable
        updateReachingDefB3(); //update currentInfo.reachingDefs if currentInfo defines variable B

        //copy from currentInfo.reachingDefs to bb->infoBasicBlock[bb->num_regs]
        bb->infoBasicBlock[bb->num_regs].num_reaching_defs = currentInfo.num_reaching_defs;
        for(k = 0; k < currentInfo.num_reaching_defs; k++)
            bb->infoBasicBlock[bb->num_regs].reachingDefs[k] = currentInfo.reachingDefs[k];
#ifdef DEBUG_MERGE_ENTRY
        ALOGI("try to update reaching defs for VR %d %d", regB, typeB);
        for(k = 0; k < bb->infoBasicBlock[bb->num_regs].num_reaching_defs; k++)
            ALOGI("reaching def %d @ %d for VR %d %d access %d", k, currentInfo.reachingDefs[k].offsetPC,
                  currentInfo.reachingDefs[k].regNum, currentInfo.reachingDefs[k].physicalType,
                  currentInfo.reachingDefs[k].accessType);
#endif
        bb->num_regs++;
        if(bb->num_regs >= MAX_REG_PER_BASICBLOCK) {
            ALOGE("too many VRs in a basic block");
            dvmAbort();
        }
        return -1;
    }
    return 0;
}

//!update reaching defs for infoBasicBlock[indexToA]

//!use currentInfo.reachingDefs to update reaching defs for variable A
void updateReachingDefA(int indexToA, OverlapCase isBPartiallyOverlapA) {
    if(indexToA < 0) return;
    int k, k2;
    OverlapCase isBPartiallyOverlapDef;
    if(currentInfo.accessType == REGACCESS_U) {
        return; //no update to reachingDefs of the VR
    }
    /* access in currentInfo is DU, D, or UD */
    if(isBPartiallyOverlapA == OVERLAP_B_COVER_A) {
        /* from this point on, the reachingDefs for variable A is a single def to currentInfo at offsetPC */
        currentBB->infoBasicBlock[indexToA].num_reaching_defs = 1;
        currentBB->infoBasicBlock[indexToA].reachingDefs[0].offsetPC = offsetPC;
        currentBB->infoBasicBlock[indexToA].reachingDefs[0].regNum = currentInfo.regNum;
        currentBB->infoBasicBlock[indexToA].reachingDefs[0].physicalType = currentInfo.physicalType;
        currentBB->infoBasicBlock[indexToA].reachingDefs[0].accessType = REGACCESS_D;
#ifdef DEBUG_REACHING_DEF
        ALOGI("single reaching def @ %d for VR %d %d", offsetPC, currentInfo.regNum, currentInfo.physicalType);
#endif
        return;
    }
    /* update reachingDefs for variable A to get rid of dead defs */
    /* Bug fix: it is possible that more than one reaching defs need to be removed
                after one reaching def is removed, num_reaching_defs--, but k should not change
    */
    for(k = 0; k < currentBB->infoBasicBlock[indexToA].num_reaching_defs; ) {
        /* remove one reaching def in one interation of the loop */
        //check overlapping between def & B
        isBPartiallyOverlapDef = getBPartiallyOverlapA(currentInfo.regNum, currentInfo.physicalType,
                                                       currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum,
                                                       currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType);
#ifdef DEBUG_REACHING_DEF
        ALOGI("DEBUG B %d %d def %d %d %d", currentInfo.regNum, currentInfo.physicalType,
              currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum,
              currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType,
              currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType);
#endif
        /* cases where one def nees to be removed:
           if B fully covers def, def is removed
           if B overlaps high half of def & def's accessType is H, def is removed
           if B overlaps low half of def & def's accessType is L, def is removed
        */
        if((isBPartiallyOverlapDef == OVERLAP_B_COVER_HIGH_OF_A &&
            currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType == REGACCESS_H) ||
           (isBPartiallyOverlapDef == OVERLAP_B_COVER_LOW_OF_A &&
            currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType == REGACCESS_L) ||
           isBPartiallyOverlapDef == OVERLAP_B_COVER_A
           ) { //remove def
            //shift from k+1 to end
            for(k2 = k+1; k2 < currentBB->infoBasicBlock[indexToA].num_reaching_defs; k2++)
                currentBB->infoBasicBlock[indexToA].reachingDefs[k2-1] = currentBB->infoBasicBlock[indexToA].reachingDefs[k2];
            currentBB->infoBasicBlock[indexToA].num_reaching_defs--;
        }
        /*
           if B overlaps high half of def & def's accessType is not H --> update accessType of def
        */
        else if(isBPartiallyOverlapDef == OVERLAP_B_COVER_HIGH_OF_A &&
                currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType != REGACCESS_H) {
            //low half is still valid
            if(getRegSize(currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType) == OpndSize_32)
                currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType = REGACCESS_D;
            else
                currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType = REGACCESS_L;
#ifdef DEBUG_REACHING_DEF
            ALOGI("DEBUG: set accessType of def to L");
#endif
            k++;
        }
        /*
           if B overlaps low half of def & def's accessType is not L --> update accessType of def
        */
        else if(isBPartiallyOverlapDef == OVERLAP_B_COVER_LOW_OF_A &&
                currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType != REGACCESS_L) {
            //high half of def is still valid
            currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType = REGACCESS_H;
#ifdef DEBUG_REACHING_DEF
            ALOGI("DEBUG: set accessType of def to H");
#endif
            k++;
        }
        else {
            k++;
        }
    }//for k
    if(isBPartiallyOverlapA != OVERLAP_NO) {
        //insert the def to variable @ currentInfo
        k = currentBB->infoBasicBlock[indexToA].num_reaching_defs;
        if(k >= 3) {
          ALOGE("more than 3 reaching defs");
        }
        currentBB->infoBasicBlock[indexToA].reachingDefs[k].offsetPC = offsetPC;
        currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum = currentInfo.regNum;
        currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType = currentInfo.physicalType;
        currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType = REGACCESS_D;
        currentBB->infoBasicBlock[indexToA].num_reaching_defs++;
    }
#ifdef DEBUG_REACHING_DEF2
    ALOGI("IN updateReachingDefA for VR %d %d", currentBB->infoBasicBlock[indexToA].regNum,
          currentBB->infoBasicBlock[indexToA].physicalType);
    for(k = 0; k < currentBB->infoBasicBlock[indexToA].num_reaching_defs; k++)
        ALOGI("reaching def %d @ %d for VR %d %d access %d", k,
              currentBB->infoBasicBlock[indexToA].reachingDefs[k].offsetPC,
              currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum,
              currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType,
              currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType);
#endif
}

/** Given a variable B @currentInfo,
    updates its reaching defs by checking reaching defs of variable A @currentBB->infoBasicBlock[indexToA]
    The result is stored in tmpInfo.reachingDefs
*/
void updateReachingDefB1(int indexToA) {
    if(indexToA < 0) return;
    int k;
    tmpInfo.num_reaching_defs = 0;
    for(k = 0; k < currentBB->infoBasicBlock[indexToA].num_reaching_defs; k++) {
        /* go through reachingDefs of variable A @currentBB->infoBasicBlock[indexToA]
           for each def, check whether it overlaps with variable B @currentInfo
               if the def overlaps with variable B, insert it to tmpInfo.reachingDefs
        */
        OverlapCase isDefPartiallyOverlapB = getAPartiallyOverlapB(
                                                 currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum,
                                                 currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType,
                                                 currentInfo.regNum, currentInfo.physicalType
                                                 );
        bool insert1 = false; //whether to insert the def to tmpInfo.reachingDefs
        if(isDefPartiallyOverlapB == OVERLAP_ALIGN ||
           isDefPartiallyOverlapB == OVERLAP_A_IS_LOW_OF_B ||
           isDefPartiallyOverlapB == OVERLAP_A_IS_HIGH_OF_B) {
            /* B aligns with def */
            /* def is low half of B, def is high half of B
               in these two cases, def is 32 bits */
            insert1 = true;
        }
        RegAccessType deftype = currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType;
        if(isDefPartiallyOverlapB == OVERLAP_B_IS_LOW_OF_A ||
           isDefPartiallyOverlapB == OVERLAP_LOW_OF_A_IS_HIGH_OF_B) {
            /* B is the low half of def */
            /* the low half of def is the high half of B */
            if(deftype != REGACCESS_H) insert1 = true;
        }
        if(isDefPartiallyOverlapB == OVERLAP_B_IS_HIGH_OF_A ||
           isDefPartiallyOverlapB == OVERLAP_HIGH_OF_A_IS_LOW_OF_B) {
            /* B is the high half of def */
            /* the high half of def is the low half of B */
            if(deftype != REGACCESS_L) insert1 = true;
        }
        if(insert1) {
            if(tmpInfo.num_reaching_defs >= 3) {
                ALOGE("more than 3 reaching defs for tmpInfo");
            }
            tmpInfo.reachingDefs[tmpInfo.num_reaching_defs] = currentBB->infoBasicBlock[indexToA].reachingDefs[k];
            tmpInfo.num_reaching_defs++;
#ifdef DEBUG_REACHING_DEF2
            ALOGI("insert from entry %d %d: index %d", currentBB->infoBasicBlock[indexToA].regNum,
                  currentBB->infoBasicBlock[indexToA].physicalType, k);
#endif
        }
    }
}

/** update currentInfo.reachingDefs by merging currentInfo.reachingDefs with tmpInfo.reachingDefs
*/
void updateReachingDefB2() {
    int k, k2;
    for(k2 = 0; k2 < tmpInfo.num_reaching_defs; k2++ ) {
        bool merged = false;
        for(k = 0; k < currentInfo.num_reaching_defs; k++) {
            /* check whether it is the same def, if yes, do nothing */
            if(currentInfo.reachingDefs[k].regNum == tmpInfo.reachingDefs[k2].regNum &&
               currentInfo.reachingDefs[k].physicalType == tmpInfo.reachingDefs[k2].physicalType) {
                merged = true;
                if(currentInfo.reachingDefs[k].offsetPC != tmpInfo.reachingDefs[k2].offsetPC) {
                    ALOGE("defs on the same VR %d %d with different offsetPC %d vs %d",
                          currentInfo.reachingDefs[k].regNum, currentInfo.reachingDefs[k].physicalType,
                          currentInfo.reachingDefs[k].offsetPC, tmpInfo.reachingDefs[k2].offsetPC);
                }
                if(currentInfo.reachingDefs[k].accessType != tmpInfo.reachingDefs[k2].accessType)
                    ALOGE("defs on the same VR %d %d with different accessType",
                          currentInfo.reachingDefs[k].regNum, currentInfo.reachingDefs[k].physicalType);
                break;
            }
        }
        if(!merged) {
            if(currentInfo.num_reaching_defs >= 3) {
               ALOGE("more than 3 reaching defs for currentInfo");
            }
            currentInfo.reachingDefs[currentInfo.num_reaching_defs] = tmpInfo.reachingDefs[k2];
            currentInfo.num_reaching_defs++;
        }
    }
}

//!update currentInfo.reachingDefs with currentInfo if variable is defined in currentInfo

//!
void updateReachingDefB3() {
    if(currentInfo.accessType == REGACCESS_U) {
        return; //no need to update currentInfo.reachingDefs
    }
    currentInfo.num_reaching_defs = 1;
    currentInfo.reachingDefs[0].regNum = currentInfo.regNum;
    currentInfo.reachingDefs[0].physicalType = currentInfo.physicalType;
    currentInfo.reachingDefs[0].offsetPC = offsetPC;
    currentInfo.reachingDefs[0].accessType = REGACCESS_D;
}

/** update defUseTable by checking currentInfo
*/
void updateDefUseTable() {
    /* no access */
    if(currentInfo.accessType == REGACCESS_N) return;
    /* define then use, or define only */
    if(currentInfo.accessType == REGACCESS_DU || currentInfo.accessType == REGACCESS_D) {
        /* insert a definition at offsetPC to variable @ currentInfo */
        DefUsePair* ptr = insertADef(offsetPC, currentInfo.regNum, currentInfo.physicalType, REGACCESS_D);
        if(currentInfo.accessType != REGACCESS_D) {
             /* if access is define then use, insert a use at offsetPC */
            insertAUse(ptr, offsetPC, currentInfo.regNum, currentInfo.physicalType);
        }
        return;
    }
    /* use only or use then define
       check the reaching defs for the usage */
    int k;
    bool isLCovered = false, isHCovered = false, isDCovered = false;
    for(k = 0; k < currentInfo.num_reaching_defs; k++) {
        /* insert a def currentInfo.reachingDefs[k] and a use of variable at offsetPC */
        RegAccessType useType = insertDefUsePair(k);
        if(useType == REGACCESS_D) isDCovered = true;
        if(useType == REGACCESS_L) isLCovered = true;
        if(useType == REGACCESS_H) isHCovered = true;
    }
    OpndSize useSize = getRegSize(currentInfo.physicalType);
    if((!isDCovered) && (!isLCovered)) {
        /* the low half of variable is not defined in the basic block
           so insert a def to the low half at START of the basic block */
        insertDefUsePair(-1);
    }
    if(useSize == OpndSize_64 && (!isDCovered) && (!isHCovered)) {
        /* the high half of variable is not defined in the basic block
           so insert a def to the high half at START of the basic block */
        insertDefUsePair(-2);
    }
    if(currentInfo.accessType == REGACCESS_UD) {
        /* insert a def at offsetPC to variable @ currentInfo */
        insertADef(offsetPC, currentInfo.regNum, currentInfo.physicalType, REGACCESS_D);
        return;
    }
}

//! insert a use at offsetPC of given variable at end of DefUsePair

//!
RegAccessType insertAUse(DefUsePair* ptr, int offsetPC, int regNum, LowOpndRegType physicalType) {
    DefOrUseLink* tLink = (DefOrUseLink*)malloc(sizeof(DefOrUseLink));
    if(tLink == NULL) {
        ALOGE("Memory allocation failed");
        return REGACCESS_UNKNOWN;
    }
    tLink->offsetPC = offsetPC;
    tLink->regNum = regNum;
    tLink->physicalType = physicalType;
    tLink->next = NULL;
    if(ptr->useTail != NULL)
        ptr->useTail->next = tLink;
    ptr->useTail = tLink;
    if(ptr->uses == NULL)
        ptr->uses = tLink;
    ptr->num_uses++;

    //check whether the def is partially overlapping with the variable
    OverlapCase isDefPartiallyOverlapB = getBPartiallyOverlapA(ptr->def.regNum,
                                                       ptr->def.physicalType,
                                                       regNum, physicalType);
    RegAccessType useType = setAccessTypeOfUse(isDefPartiallyOverlapB, ptr->def.accessType);
    tLink->accessType = useType;
    return useType;
}

//! insert a def to currentBB->defUseTable

//! update currentBB->defUseTail if necessary
DefUsePair* insertADef(int offsetPC, int regNum, LowOpndRegType pType, RegAccessType rType) {
    DefUsePair* ptr = (DefUsePair*)malloc(sizeof(DefUsePair));
    if(ptr == NULL) {
        ALOGE("Memory allocation failed");
        return NULL;
    }
    ptr->next = NULL;
    ptr->def.offsetPC = offsetPC;
    ptr->def.regNum = regNum;
    ptr->def.physicalType = pType;
    ptr->def.accessType = rType;
    ptr->num_uses = 0;
    ptr->useTail = NULL;
    ptr->uses = NULL;
    if(currentBB->defUseTail != NULL) {
        currentBB->defUseTail->next = ptr;
    }
    currentBB->defUseTail = ptr;
    if(currentBB->defUseTable == NULL)
        currentBB->defUseTable = ptr;
    currentBB->num_defs++;
#ifdef DEBUG_REACHING_DEF
    ALOGI("insert a def at %d to defUseTable for VR %d %d", offsetPC,
          regNum, pType);
#endif
    return ptr;
}

/** insert a def to defUseTable, then insert a use of variable @ currentInfo
    if reachingDefIndex >= 0, the def is currentInfo.reachingDefs[index]
    if reachingDefIndex is -1, the low half is defined at START of the basic block
    if reachingDefIndex is -2, the high half is defined at START of the basic block
*/
RegAccessType insertDefUsePair(int reachingDefIndex) {
    int k = reachingDefIndex;
    DefUsePair* tableIndex = NULL;
    DefOrUse theDef;
    theDef.regNum = 0;
    if(k < 0) {
        /* def at start of the basic blcok */
        theDef.offsetPC = PC_FOR_START_OF_BB;
        theDef.accessType = REGACCESS_D;
        if(k == -1) //low half of variable
            theDef.regNum = currentInfo.regNum;
        if(k == -2) //high half of variable
            theDef.regNum = currentInfo.regNum+1;
        theDef.physicalType = LowOpndRegType_gp;
    }
    else {
        theDef = currentInfo.reachingDefs[k];
    }
    tableIndex = searchDefUseTable(theDef.offsetPC, theDef.regNum, theDef.physicalType);
    if(tableIndex == NULL) //insert an entry
        tableIndex = insertADef(theDef.offsetPC, theDef.regNum, theDef.physicalType, theDef.accessType);
    else
        tableIndex->def.accessType = theDef.accessType;
    RegAccessType useType = insertAUse(tableIndex, offsetPC, currentInfo.regNum, currentInfo.physicalType);
    return useType;
}

//! insert a XFER_MEM_TO_XMM to currentBB->xferPoints

//!
void insertLoadXfer(int offset, int regNum, LowOpndRegType pType) {
    //check whether it is already in currentBB->xferPoints
    int k;
    for(k = 0; k < currentBB->num_xfer_points; k++) {
        if(currentBB->xferPoints[k].xtype == XFER_MEM_TO_XMM &&
           currentBB->xferPoints[k].offsetPC == offset &&
           currentBB->xferPoints[k].regNum == regNum &&
           currentBB->xferPoints[k].physicalType == pType)
            return;
    }
    currentBB->xferPoints[currentBB->num_xfer_points].xtype = XFER_MEM_TO_XMM;
    currentBB->xferPoints[currentBB->num_xfer_points].regNum = regNum;
    currentBB->xferPoints[currentBB->num_xfer_points].offsetPC = offset;
    currentBB->xferPoints[currentBB->num_xfer_points].physicalType = pType;
#ifdef DEBUG_XFER_POINTS
    ALOGI("insert to xferPoints %d: XFER_MEM_TO_XMM of VR %d %d at %d", currentBB->num_xfer_points, regNum, pType, offset);
#endif
    currentBB->num_xfer_points++;
    if(currentBB->num_xfer_points >= MAX_XFER_PER_BB) {
        ALOGE("too many xfer points");
        dvmAbort();
    }
}

/** update defUseTable by assuming a fake usage at END of a basic block for variable @ currentInfo
    create a fake usage at end of a basic block for variable B (currentInfo.physicalType, currentInfo.regNum)
    get reaching def info for variable B and store the info in currentInfo.reachingDefs
        for each virtual register (variable A) accessed in the basic block
            update reaching defs of B by checking reaching defs of variable A
    update defUseTable
*/
int fakeUsageAtEndOfBB(BasicBlock_O1* bb) {
    currentInfo.accessType = REGACCESS_U;
    LowOpndRegType typeB = currentInfo.physicalType;
    int regB = currentInfo.regNum;
    int jj, k;
    currentInfo.num_reaching_defs = 0;
    for(jj = 0; jj < bb->num_regs; jj++) {
        int regA = bb->infoBasicBlock[jj].regNum;
        LowOpndRegType typeA = bb->infoBasicBlock[jj].physicalType;
        OverlapCase isBPartiallyOverlapA = getBPartiallyOverlapA(regB, typeB, regA, typeA);
        if(regA == regB && typeA == typeB) {
            /* copy reachingDefs from variable A */
            currentInfo.num_reaching_defs = bb->infoBasicBlock[jj].num_reaching_defs;
            for(k = 0; k < currentInfo.num_reaching_defs; k++)
                currentInfo.reachingDefs[k] = bb->infoBasicBlock[jj].reachingDefs[k];
            break;
        }
        else if(isBPartiallyOverlapA != OVERLAP_NO) {
            /* B overlaps with A */
            /* update reaching defs of variable B by checking reaching defs of bb->infoBasicBlock[jj] */
            updateReachingDefB1(jj);
            updateReachingDefB2(); //merge currentInfo with tmpInfo
        }
    }
    /* update defUseTable by checking currentInfo */
    updateDefUseTable();
    return 0;
}

/** update xferPoints of currentBB
    Traverse currentBB->defUseTable
*/
int updateXferPoints() {
    int k = 0;
    currentBB->num_xfer_points = 0;
    DefUsePair* ptr = currentBB->defUseTable;
    DefOrUseLink* ptrUse = NULL;
    /* traverse the def use chain of the basic block */
    while(ptr != NULL) {
        LowOpndRegType defType = ptr->def.physicalType;
        //if definition is for a variable of 32 bits
        if(getRegSize(defType) == OpndSize_32) {
            /* check usages of the definition, whether it reaches a GPR, a XMM, a FS, or a SS */
            bool hasGpUsage = false;
            bool hasGpUsage2 = false; //not a fake usage
            bool hasXmmUsage = false;
            bool hasFSUsage = false;
            bool hasSSUsage = false;
            ptrUse = ptr->uses;
            while(ptrUse != NULL) {
                if(ptrUse->physicalType == LowOpndRegType_gp) {
                    hasGpUsage = true;
                    if(ptrUse->offsetPC != PC_FOR_END_OF_BB)
                        hasGpUsage2 = true;
                }
                if(ptrUse->physicalType == LowOpndRegType_ss) hasSSUsage = true;
                if(ptrUse->physicalType == LowOpndRegType_fs ||
                   ptrUse->physicalType == LowOpndRegType_fs_s)
                    hasFSUsage = true;
                if(ptrUse->physicalType == LowOpndRegType_xmm) {
                    hasXmmUsage = true;
                }
                if(ptrUse->physicalType == LowOpndRegType_xmm ||
                   ptrUse->physicalType == LowOpndRegType_ss) {
                    /* if a 32-bit definition reaches a xmm usage or a SS usage,
                       insert a XFER_MEM_TO_XMM */
                    insertLoadXfer(ptrUse->offsetPC,
                                   ptrUse->regNum, LowOpndRegType_xmm);
                }
                ptrUse = ptrUse->next;
            }
            if(((hasXmmUsage || hasFSUsage || hasSSUsage) && defType == LowOpndRegType_gp) ||
               (hasGpUsage && defType == LowOpndRegType_fs) ||
               (defType == LowOpndRegType_ss && (hasGpUsage || hasXmmUsage || hasFSUsage))) {
                /* insert a transfer if def is on a GPR, usage is on a XMM, FS or SS
                                     if def is on a FS, usage is on a GPR
                                     if def is on a SS, usage is on a GPR, XMM or FS
                   transfer type is XFER_DEF_TO_GP_MEM if a real GPR usage exisits
                   transfer type is XFER_DEF_TO_GP otherwise*/
                currentBB->xferPoints[currentBB->num_xfer_points].offsetPC = ptr->def.offsetPC;
                currentBB->xferPoints[currentBB->num_xfer_points].regNum = ptr->def.regNum;
                currentBB->xferPoints[currentBB->num_xfer_points].physicalType = ptr->def.physicalType;
                if(hasGpUsage2) { //create an entry XFER_DEF_TO_GP_MEM
                    currentBB->xferPoints[currentBB->num_xfer_points].xtype = XFER_DEF_TO_GP_MEM;
                }
                else { //create an entry XFER_DEF_TO_MEM
                    currentBB->xferPoints[currentBB->num_xfer_points].xtype = XFER_DEF_TO_MEM;
                }
                currentBB->xferPoints[currentBB->num_xfer_points].tableIndex = k;
#ifdef DEBUG_XFER_POINTS
                ALOGI("insert XFER %d at def %d: V%d %d", currentBB->num_xfer_points, ptr->def.offsetPC, ptr->def.regNum, defType);
#endif
                currentBB->num_xfer_points++;
                if(currentBB->num_xfer_points >= MAX_XFER_PER_BB) {
                    ALOGE("too many xfer points");
                    dvmAbort();
                }
            }
        }
        else { /* def is on 64 bits */
            bool hasGpUsageOfL = false; //exist a GPR usage of the low half
            bool hasGpUsageOfH = false; //exist a GPR usage of the high half
            bool hasGpUsageOfL2 = false;
            bool hasGpUsageOfH2 = false;
            bool hasMisaligned = false;
            bool hasAligned = false;
            bool hasFSUsage = false;
            bool hasSSUsage = false;
            ptrUse = ptr->uses;
            while(ptrUse != NULL) {
                if(ptrUse->physicalType == LowOpndRegType_gp &&
                   ptrUse->regNum == ptr->def.regNum) {
                    hasGpUsageOfL = true;
                    if(ptrUse->offsetPC != PC_FOR_END_OF_BB)
                        hasGpUsageOfL2 = true;
                }
                if(ptrUse->physicalType == LowOpndRegType_gp &&
                   ptrUse->regNum == ptr->def.regNum + 1) {
                    hasGpUsageOfH = true;
                    if(ptrUse->offsetPC != PC_FOR_END_OF_BB)
                        hasGpUsageOfH2 = true;
                }
                if(ptrUse->physicalType == LowOpndRegType_xmm &&
                   ptrUse->regNum == ptr->def.regNum) {
                    hasAligned = true;
                    /* if def is on FS and use is on XMM, insert a XFER_MEM_TO_XMM */
                    if(defType == LowOpndRegType_fs)
                        insertLoadXfer(ptrUse->offsetPC,
                                       ptrUse->regNum, LowOpndRegType_xmm);
                }
                if(ptrUse->physicalType == LowOpndRegType_fs ||
                   ptrUse->physicalType == LowOpndRegType_fs_s)
                    hasFSUsage = true;
                if(ptrUse->physicalType == LowOpndRegType_xmm &&
                   ptrUse->regNum != ptr->def.regNum) {
                    hasMisaligned = true;
                    /* if use is on XMM and use and def are misaligned, insert a XFER_MEM_TO_XMM */
                    insertLoadXfer(ptrUse->offsetPC,
                                   ptrUse->regNum, LowOpndRegType_xmm);
                }
                if(ptrUse->physicalType == LowOpndRegType_ss) {
                    hasSSUsage = true;
                    /* if use is on SS, insert a XFER_MEM_TO_XMM */
                    insertLoadXfer(ptrUse->offsetPC,
                                   ptrUse->regNum, LowOpndRegType_ss);
                }
                ptrUse = ptrUse->next;
            }
            if(defType == LowOpndRegType_fs && !hasGpUsageOfL && !hasGpUsageOfH) {
                ptr = ptr->next;
                continue;
            }
            if(defType == LowOpndRegType_xmm && !hasFSUsage &&
               !hasGpUsageOfL && !hasGpUsageOfH && !hasMisaligned && !hasSSUsage) {
                ptr = ptr->next;
                continue;
            }
            /* insert a XFER_DEF_IS_XMM */
            currentBB->xferPoints[currentBB->num_xfer_points].regNum = ptr->def.regNum;
            currentBB->xferPoints[currentBB->num_xfer_points].offsetPC = ptr->def.offsetPC;
            currentBB->xferPoints[currentBB->num_xfer_points].physicalType = ptr->def.physicalType;
            currentBB->xferPoints[currentBB->num_xfer_points].xtype = XFER_DEF_IS_XMM;
            currentBB->xferPoints[currentBB->num_xfer_points].vr_gpl = -1;
            currentBB->xferPoints[currentBB->num_xfer_points].vr_gph = -1;
            if(hasGpUsageOfL2) currentBB->xferPoints[currentBB->num_xfer_points].vr_gpl = ptr->def.regNum;
            if(hasGpUsageOfH2) currentBB->xferPoints[currentBB->num_xfer_points].vr_gph = ptr->def.regNum+1;
            currentBB->xferPoints[currentBB->num_xfer_points].dumpToMem = true;
            currentBB->xferPoints[currentBB->num_xfer_points].dumpToXmm = false; //not used in updateVirtualReg
            if(hasAligned) currentBB->xferPoints[currentBB->num_xfer_points].dumpToXmm = true;
            currentBB->xferPoints[currentBB->num_xfer_points].tableIndex = k;
#ifdef DEBUG_XFER_POINTS
            ALOGI("insert XFER %d at def %d: V%d %d", currentBB->num_xfer_points, ptr->def.offsetPC, ptr->def.regNum, defType);
#endif
            currentBB->num_xfer_points++;
            if(currentBB->num_xfer_points >= MAX_XFER_PER_BB) {
                ALOGE("too many xfer points");
                dvmAbort();
            }
        }
        ptr = ptr->next;
    } //while ptr
#ifdef DEBUG_XFER_POINTS
    ALOGI("XFER points for current basic block ------");
    for(k = 0; k < currentBB->num_xfer_points; k++) {
        ALOGI("  at offset %x, VR %d %d: type %d, vr_gpl %d, vr_gph %d, dumpToMem %d, dumpToXmm %d",
              currentBB->xferPoints[k].offsetPC, currentBB->xferPoints[k].regNum,
              currentBB->xferPoints[k].physicalType, currentBB->xferPoints[k].xtype,
              currentBB->xferPoints[k].vr_gpl, currentBB->xferPoints[k].vr_gph,
              currentBB->xferPoints[k].dumpToMem, currentBB->xferPoints[k].dumpToXmm);
    }
#endif
    return -1;
}

//! update memVRTable[].ranges by browsing the defUseTable

//! each virtual register has a list of live ranges, and each live range has a list of PCs that access the VR
void updateLiveTable() {
    DefUsePair* ptr = currentBB->defUseTable;
    while(ptr != NULL) {
        bool updateUse = false;
        if(ptr->num_uses == 0) {
            ptr->num_uses = 1;
            ptr->uses = (DefOrUseLink*)malloc(sizeof(DefOrUseLink));
            if(ptr->uses == NULL) {
                ALOGE("Memory allocation failed");
                return;
            }
            ptr->uses->accessType = REGACCESS_D;
            ptr->uses->regNum = ptr->def.regNum;
            ptr->uses->offsetPC = ptr->def.offsetPC;
            ptr->uses->physicalType = ptr->def.physicalType;
            ptr->uses->next = NULL;
            ptr->useTail = ptr->uses;
            updateUse = true;
        }
        DefOrUseLink* ptrUse = ptr->uses;
        while(ptrUse != NULL) {
            RegAccessType useType = ptrUse->accessType;
            if(useType == REGACCESS_L || useType == REGACCESS_D) {
                int indexL = searchMemTable(ptrUse->regNum);
                if(indexL >= 0)
                    mergeLiveRange(indexL, ptr->def.offsetPC,
                                   ptrUse->offsetPC); //tableIndex, start PC, end PC
            }
            if(getRegSize(ptrUse->physicalType) == OpndSize_64 &&
               (useType == REGACCESS_H || useType == REGACCESS_D)) {
                int indexH = searchMemTable(ptrUse->regNum+1);
                if(indexH >= 0)
                    mergeLiveRange(indexH, ptr->def.offsetPC,
                                   ptrUse->offsetPC);
            }
            ptrUse = ptrUse->next;
        }//while ptrUse
        if(updateUse) {
            ptr->num_uses = 0;
            free(ptr->uses);
            ptr->uses = NULL;
            ptr->useTail = NULL;
        }
        ptr = ptr->next;
    }//while ptr
#ifdef DEBUG_LIVE_RANGE
    ALOGI("LIVE TABLE");
    for(int k = 0; k < num_memory_vr; k++) {
        ALOGI("VR %d live ", memVRTable[k].regNum);
        LiveRange* ptr = memVRTable[k].ranges;
        while(ptr != NULL) {
            ALOGI("[%x %x] (", ptr->start, ptr->end);
            for(int k3 = 0; k3 < ptr->num_access; k3++)
                ALOGI("%x ", ptr->accessPC[k3]);
            ALOGI(") ");
            ptr = ptr->next;
        }
        ALOGI("");
    }
#endif
}

//!add a live range [rangeStart, rangeEnd] to ranges of memVRTable, merge to existing live ranges if necessary

//!ranges are in increasing order of startPC
void mergeLiveRange(int tableIndex, int rangeStart, int rangeEnd) {
    if(rangeStart == PC_FOR_START_OF_BB) rangeStart = currentBB->pc_start;
    if(rangeEnd == PC_FOR_END_OF_BB) rangeEnd = currentBB->pc_end;
#ifdef DEBUG_LIVE_RANGE
    ALOGI("LIVERANGE call mergeLiveRange on tableIndex %d with [%x %x]", tableIndex, rangeStart, rangeEnd);
#endif
    int startIndex = -1, endIndex = -1;
    bool startBeforeRange = false, endBeforeRange = false; //before the index or in the range
    bool startDone = false, endDone = false;
    LiveRange* ptr = memVRTable[tableIndex].ranges;
    LiveRange* ptrStart = NULL;
    LiveRange* ptrStart_prev = NULL;
    LiveRange* ptrEnd = NULL;
    LiveRange* ptrEnd_prev = NULL;
    int k = 0;
    while(ptr != NULL) {
        if(!startDone) {
            if(ptr->start <= rangeStart &&
               ptr->end >= rangeStart) {
                startIndex = k;
                ptrStart = ptr;
                startBeforeRange = false;
                startDone = true;
            }
            else if(ptr->start > rangeStart) {
                startIndex = k;
                ptrStart = ptr;
                startBeforeRange = true;
                startDone = true;
            }
        }
        if(!startDone) ptrStart_prev = ptr;
        if(!endDone) {
            if(ptr->start <= rangeEnd &&
               ptr->end >= rangeEnd) {
                endIndex = k;
                ptrEnd = ptr;
                endBeforeRange = false;
                endDone = true;
            }
            else if(ptr->start > rangeEnd) {
                endIndex = k;
                ptrEnd = ptr;
                endBeforeRange = true;
                endDone = true;
            }
        }
        if(!endDone) ptrEnd_prev = ptr;
        ptr = ptr->next;
        k++;
    } //while
    if(!startDone) { //both can be NULL
        startIndex = memVRTable[tableIndex].num_ranges;
        ptrStart = NULL; //ptrStart_prev should be the last live range
        startBeforeRange = true;
    }
    //if endDone, ptrEnd is not NULL, ptrEnd_prev can be NULL
    if(!endDone) { //both can be NULL
        endIndex = memVRTable[tableIndex].num_ranges;
        ptrEnd = NULL;
        endBeforeRange = true;
    }
    if(startIndex == endIndex && startBeforeRange && endBeforeRange) { //insert at startIndex
        //3 cases depending on BeforeRange when startIndex == endIndex
        //insert only if both true
        //merge otherwise
        /////////// insert before ptrStart
        LiveRange* currRange = (LiveRange *)malloc(sizeof(LiveRange));
        if(ptrStart_prev == NULL) {
            currRange->next = memVRTable[tableIndex].ranges;
            memVRTable[tableIndex].ranges = currRange;
        } else {
            currRange->next = ptrStart_prev->next;
            ptrStart_prev->next = currRange;
        }
        currRange->start = rangeStart;
        currRange->end = rangeEnd;
        currRange->accessPC = (int *)malloc(sizeof(int) * NUM_ACCESS_IN_LIVERANGE);
        currRange->num_alloc = NUM_ACCESS_IN_LIVERANGE;
        if(rangeStart != rangeEnd) {
            currRange->num_access = 2;
            currRange->accessPC[0] = rangeStart;
            currRange->accessPC[1] = rangeEnd;
        } else {
            currRange->num_access = 1;
            currRange->accessPC[0] = rangeStart;
        }
        memVRTable[tableIndex].num_ranges++;
#ifdef DEBUG_LIVE_RANGE
        ALOGI("LIVERANGE insert one live range [%x %x] to tableIndex %d", rangeStart, rangeEnd, tableIndex);
#endif
        return;
    }
    if(!endBeforeRange) { //here ptrEnd is not NULL
        endIndex++; //next
        ptrEnd_prev = ptrEnd; //ptrEnd_prev is not NULL
        ptrEnd = ptrEnd->next; //ptrEnd can be NULL
    }
    if(endIndex < startIndex+1) ALOGE("mergeLiveRange endIndex %d startIndex %d", endIndex, startIndex);
    ///////// use ptrStart & ptrEnd_prev
    if(ptrStart == NULL || ptrEnd_prev == NULL) {
        ALOGE("mergeLiveRange ptr is NULL");
        return;
    }
    //endIndex > startIndex (merge the ranges between startIndex and endIndex-1)
    //update ptrStart
    if(ptrStart->start > rangeStart)
        ptrStart->start = rangeStart; //min of old start & rangeStart
    ptrStart->end = ptrEnd_prev->end; //max of old end & rangeEnd
    if(rangeEnd > ptrStart->end)
        ptrStart->end = rangeEnd;
#ifdef DEBUG_LIVE_RANGE
    ALOGI("LIVERANGE merge entries for tableIndex %d from %d to %d", tableIndex, startIndex+1, endIndex-1);
#endif
    if(ptrStart->num_access <= 0) ALOGE("mergeLiveRange number of access");
#ifdef DEBUG_LIVE_RANGE
    ALOGI("LIVERANGE tableIndex %d startIndex %d num_access %d (", tableIndex, startIndex, ptrStart->num_access);
    for(k = 0; k < ptrStart->num_access; k++)
        ALOGI("%x ", ptrStart->accessPC[k]);
    ALOGI(")");
#endif
    ///// go through pointers from ptrStart->next to ptrEnd
    //from startIndex+1 to endIndex-1
    ptr = ptrStart->next;
    while(ptr != NULL && ptr != ptrEnd) {
        int k2;
        for(k2 = 0; k2 < ptr->num_access; k2++) { //merge to startIndex
            insertAccess(tableIndex, ptrStart, ptr->accessPC[k2]);
        }//k2
        ptr = ptr->next;
    }
    insertAccess(tableIndex, ptrStart, rangeStart);
    insertAccess(tableIndex, ptrStart, rangeEnd);
    //remove startIndex+1 to endIndex-1
    if(startIndex+1 < endIndex) {
        ptr = ptrStart->next;
        while(ptr != NULL && ptr != ptrEnd) {
            LiveRange* tmpP = ptr->next;
            free(ptr->accessPC);
            free(ptr);
            ptr = tmpP;
        }
        ptrStart->next = ptrEnd;
    }
    memVRTable[tableIndex].num_ranges -= (endIndex - startIndex - 1);
#ifdef DEBUG_LIVE_RANGE
    ALOGI("num_ranges for VR %d: %d", memVRTable[tableIndex].regNum, memVRTable[tableIndex].num_ranges);
#endif
}
//! insert an access to a given live range, in order

//!
void insertAccess(int tableIndex, LiveRange* startP, int rangeStart) {
    int k3, k4;
#ifdef DEBUG_LIVE_RANGE
    ALOGI("LIVERANGE insertAccess %d %x", tableIndex, rangeStart);
#endif
    int insertIndex = -1;
    for(k3 = 0; k3 < startP->num_access; k3++) {
        if(startP->accessPC[k3] == rangeStart) {
            return;
        }
        if(startP->accessPC[k3] > rangeStart) {
            insertIndex = k3;
            break;
        }
    }

    //insert here
    k3 = insertIndex;
    if(insertIndex == -1) {
        k3 = startP->num_access;
    }
    if(startP->num_access == startP->num_alloc) {
        int currentAlloc = startP->num_alloc;
        startP->num_alloc += NUM_ACCESS_IN_LIVERANGE;
        int* tmpPtr = (int *)malloc(sizeof(int) * startP->num_alloc);
        for(k4 = 0; k4 < currentAlloc; k4++)
            tmpPtr[k4] = startP->accessPC[k4];
        free(startP->accessPC);
        startP->accessPC = tmpPtr;
    }
    //insert accessPC
    for(k4 = startP->num_access-1; k4 >= k3; k4--)
        startP->accessPC[k4+1] = startP->accessPC[k4];
    startP->accessPC[k3] = rangeStart;
#ifdef DEBUG_LIVE_RANGE
    ALOGI("LIVERANGE insert %x to tableIndex %d", rangeStart, tableIndex);
#endif
    startP->num_access++;
    return;
}

/////////////////////////////////////////////////////////////////////
bool isInMemory(int regNum, OpndSize size);
void setVRToMemory(int regNum, OpndSize size);
bool isVRLive(int vA);
int getSpillIndex(bool isGLUE, OpndSize size);
void clearVRToMemory(int regNum, OpndSize size);
void clearVRNullCheck(int regNum, OpndSize size);

inline int getSpillLocDisp(int offset) {
#ifdef SPILL_IN_THREAD
    return offset+offsetof(Thread, spillRegion);;
#else
    return offset+offEBP_spill;
#endif
}
#if 0
/* used if we keep self pointer in a physical register */
inline int getSpillLocReg(int offset) {
    return PhysicalReg_Glue;
}
#endif
#ifdef SPILL_IN_THREAD
inline void loadFromSpillRegion_with_self(OpndSize size, int reg_self, bool selfPhysical, int reg, int offset) {
    /* only 1 instruction is generated by move_mem_to_reg_noalloc */
    move_mem_to_reg_noalloc(size,
                            getSpillLocDisp(offset), reg_self, selfPhysical,
                            MemoryAccess_SPILL, offset,
                            reg, true);
}
inline void loadFromSpillRegion(OpndSize size, int reg, int offset) {
    get_self_pointer(C_SCRATCH_1, isScratchPhysical);
    int reg_self = registerAlloc(LowOpndRegType_scratch, C_SCRATCH_1, isScratchPhysical, false);
    /* only 1 instruction is generated by move_mem_to_reg_noalloc */
    move_mem_to_reg_noalloc(size,
                            getSpillLocDisp(offset), reg_self, true,
                            MemoryAccess_SPILL, offset,
                            reg, true);
}
inline void saveToSpillRegion_with_self(OpndSize size, int selfReg, bool selfPhysical, int reg, int offset) {
    move_reg_to_mem_noalloc(size,
                            reg, true,
                            getSpillLocDisp(offset), selfReg, selfPhysical,
                            MemoryAccess_SPILL, offset);
}
inline void saveToSpillRegion(OpndSize size, int reg, int offset) {
    get_self_pointer(C_SCRATCH_1, isScratchPhysical);
    int reg_self = registerAlloc(LowOpndRegType_scratch, C_SCRATCH_1, isScratchPhysical, false);
    move_reg_to_mem_noalloc(size,
                            reg, true,
                            getSpillLocDisp(offset), reg_self, true,
                            MemoryAccess_SPILL, offset);
}
#else
inline void loadFromSpillRegion(OpndSize size, int reg, int offset) {
    /* only 1 instruction is generated by move_mem_to_reg_noalloc */
    move_mem_to_reg_noalloc(size,
                            getSpillLocDisp(offset), PhysicalReg_EBP, true,
                            MemoryAccess_SPILL, offset,
                            reg, true);
}
inline void saveToSpillRegion(OpndSize size, int reg, int offset) {
    move_reg_to_mem_noalloc(size,
                            reg, true,
                            getSpillLocDisp(offset), PhysicalReg_EBP, true,
                            MemoryAccess_SPILL, offset);
}
#endif

//! dump an immediate to memory, set inMemory to true

//!
void dumpImmToMem(int vrNum, OpndSize size, int value) {
    if(isInMemory(vrNum, size)) {
#ifdef DEBUG_SPILL
        ALOGI("Skip dumpImmToMem vA %d size %d", vrNum, size);
#endif
        return;
    }
    set_VR_to_imm_noalloc(vrNum, size, value);
    setVRToMemory(vrNum, size);
}
//! dump content of a VR to memory, set inMemory to true

//!
void dumpToMem(int vrNum, LowOpndRegType type, int regAll) { //ss,gp,xmm
    if(isInMemory(vrNum, getRegSize(type))) {
#ifdef DEBUG_SPILL
        ALOGI("Skip dumpToMem vA %d type %d", vrNum, type);
#endif
        return;
    }
    if(type == LowOpndRegType_gp || type == LowOpndRegType_xmm)
        set_virtual_reg_noalloc(vrNum, getRegSize(type), regAll, true);
    if(type == LowOpndRegType_ss)
        move_ss_reg_to_mem_noalloc(regAll, true,
                                   4*vrNum, PhysicalReg_FP, true,
                                   MemoryAccess_VR, vrNum);
    setVRToMemory(vrNum, getRegSize(type));
}
//! dump part of a 64-bit VR to memory and update inMemory

//! isLow tells whether low half or high half is dumped
void dumpPartToMem(int reg /*xmm physical reg*/, int vA, bool isLow) {
    if(isLow) {
        if(isInMemory(vA, OpndSize_32)) {
#ifdef DEBUG_SPILL
            ALOGI("Skip dumpPartToMem isLow %d vA %d", isLow, vA);
#endif
            return;
        }
    }
    else {
        if(isInMemory(vA+1, OpndSize_32)) {
#ifdef DEBUG_SPILL
            ALOGI("Skip dumpPartToMem isLow %d vA %d", isLow, vA);
#endif
            return;
        }
    }
    if(isLow) {
        if(!isVRLive(vA)) return;
    }
    else {
        if(!isVRLive(vA+1)) return;
    }
    //move part to vA or vA+1
    if(isLow) {
        move_ss_reg_to_mem_noalloc(reg, true,
                                   4*vA, PhysicalReg_FP, true, MemoryAccess_VR, vA);
    } else {
        int k = getSpillIndex(false, OpndSize_64);
        //H, L in 4*k+4 & 4*k
#ifdef SPILL_IN_THREAD
        get_self_pointer(PhysicalReg_SCRATCH_1, isScratchPhysical);
        saveToSpillRegion_with_self(OpndSize_64, PhysicalReg_SCRATCH_1, isScratchPhysical, reg, 4*k);
        //update low 32 bits of xmm reg from 4*k+4
        move_ss_mem_to_reg(NULL,
                                   getSpillLocDisp(4*k+4), PhysicalReg_SCRATCH_1, isScratchPhysical,
                                   reg, true);
#else
        saveToSpillRegion(OpndSize_64, reg, 4*k);
        //update low 32 bits of xmm reg from 4*k+4
        move_ss_mem_to_reg_noalloc(
                                   getSpillLocDisp(4*k+4), PhysicalReg_EBP, true,
                                   MemoryAccess_SPILL, 4*k+4,
                                   reg, true);
#endif
        //move low 32 bits of xmm reg to vA+1
        move_ss_reg_to_mem_noalloc(reg, true, 4*(vA+1), PhysicalReg_FP, true, MemoryAccess_VR, vA+1);
    }
    if(isLow)
        setVRToMemory(vA, OpndSize_32);
    else
        setVRToMemory(vA+1, OpndSize_32);
}
void clearVRBoundCheck(int regNum, OpndSize size);
//! the content of a VR is no longer in memory or in physical register if the latest content of a VR is constant

//! clear nullCheckDone; if another VR is overlapped with the given VR, the content of that VR is no longer in physical register
void invalidateVRDueToConst(int reg, OpndSize size) {
    clearVRToMemory(reg, size); //memory content is out-dated
    clearVRNullCheck(reg, size);
    clearVRBoundCheck(reg, size);
    //check reg,gp reg,ss reg,xmm reg-1,xmm
    //if size is 64: check reg+1,gp|ss reg+1,xmm
    int index;
    //if VR is xmm, check whether we need to dump part of VR to memory
    index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg);
    if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
        ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_xmm);
#endif
        if(size == OpndSize_32)
            dumpPartToMem(compileTable[index].physicalReg, reg, false); //dump high of xmm to memory
        compileTable[index].physicalReg = PhysicalReg_Null;
    }
    index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg-1);
    if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
        ALOGI("INVALIDATE virtual reg %d type %d", reg-1, LowOpndRegType_xmm);
#endif
        dumpPartToMem(compileTable[index].physicalReg, reg-1, true); //dump low of xmm to memory
        compileTable[index].physicalReg = PhysicalReg_Null;
    }
    index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, reg);
    if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
        ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_gp);
#endif
        compileTable[index].physicalReg = PhysicalReg_Null;
    }
    index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_ss, reg);
    if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
        ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_ss);
#endif
        compileTable[index].physicalReg = PhysicalReg_Null;
    }
    if(size == OpndSize_64) {
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg+1);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_xmm);
#endif
            dumpPartToMem(compileTable[index].physicalReg, reg+1, false); //dump high of xmm to memory
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, reg+1);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_gp);
#endif
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_ss, reg+1);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_ss);
#endif
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
    }
}
//! check which physical registers hold out-dated content if there is a def

//! if another VR is overlapped with the given VR, the content of that VR is no longer in physical register
//! should we update inMemory?
void invalidateVR(int reg, LowOpndRegType pType) {
    //def at fs: content of xmm & gp & ss are out-dated (reg-1,xmm reg,xmm reg+1,xmm) (reg,gp|ss reg+1,gp|ss)
    //def at xmm: content of misaligned xmm & gp are out-dated (reg-1,xmm reg+1,xmm) (reg,gp|ss reg+1,gp|ss)
    //def at fs_s: content of xmm & gp are out-dated (reg-1,xmm reg,xmm) (reg,gp|ss)
    //def at gp:   content of xmm is out-dated (reg-1,xmm reg,xmm) (reg,ss)
    //def at ss:   content of xmm & gp are out-dated (reg-1,xmm reg,xmm) (reg,gp)
    int index;
    if(pType != LowOpndRegType_xmm) { //check xmm @reg
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_xmm);
#endif
            if(getRegSize(pType) == OpndSize_32)
                dumpPartToMem(compileTable[index].physicalReg, reg, false); //dump high of xmm to memory
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
    }
    //check misaligned xmm @ reg-1
    index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg-1);
    if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
        ALOGI("INVALIDATE virtual reg %d type %d", reg-1, LowOpndRegType_xmm);
#endif
        dumpPartToMem(compileTable[index].physicalReg, reg-1, true); //dump low of xmm to memory
        compileTable[index].physicalReg = PhysicalReg_Null;
    }
    //check misaligned xmm @ reg+1
    if(pType == LowOpndRegType_xmm || pType == LowOpndRegType_fs) {
        //check reg+1,xmm
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg+1);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_xmm);
#endif
            dumpPartToMem(compileTable[index].physicalReg, reg+1, false); //dump high of xmm to memory
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
    }
    if(pType != LowOpndRegType_gp) {
        //check reg,gp
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, reg);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_gp);
#endif
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
    }
    if(pType == LowOpndRegType_xmm || pType == LowOpndRegType_fs) {
        //check reg+1,gp
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, reg+1);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_gp);
#endif
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
    }
    if(pType != LowOpndRegType_ss) {
        //check reg,ss
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_ss, reg);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_ss);
#endif
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
    }
    if(pType == LowOpndRegType_xmm || pType == LowOpndRegType_fs) {
        //check reg+1,ss
        index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_ss, reg+1);
        if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_INVALIDATE
            ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_ss);
#endif
            compileTable[index].physicalReg = PhysicalReg_Null;
        }
    }
}
//! bookkeeping when a VR is updated

//! invalidate contents of some physical registers, clear nullCheckDone, and update inMemory;
//! check whether there exist tranfer points for this bytecode, if yes, perform the transfer
int updateVirtualReg(int reg, LowOpndRegType pType) {
    int k;
    OpndSize size = getRegSize(pType);
    //WAS only invalidate xmm VRs for the following cases:
    //if def reaches a use of vA,xmm and (the def is not xmm or is misaligned xmm)
    //  invalidate "vA,xmm"
    invalidateVR(reg, pType);
    clearVRNullCheck(reg, size);
    clearVRBoundCheck(reg, size);
    if(pType == LowOpndRegType_fs || pType == LowOpndRegType_fs_s)
        setVRToMemory(reg, size);
    else {
        clearVRToMemory(reg, size);
    }
    for(k = 0; k < currentBB->num_xfer_points; k++) {
        if(currentBB->xferPoints[k].offsetPC == offsetPC &&
           currentBB->xferPoints[k].regNum == reg &&
           currentBB->xferPoints[k].physicalType == pType &&
           currentBB->xferPoints[k].xtype != XFER_MEM_TO_XMM) {
            //perform the corresponding action for the def
            PhysicalReg regAll;
            if(currentBB->xferPoints[k].xtype == XFER_DEF_IS_XMM) {
                //def at fs: content of xmm is out-dated
                //def at xmm: content of misaligned xmm is out-dated
                //invalidateXmmVR(currentBB->xferPoints[k].tableIndex);
#ifdef DEBUG_XFER_POINTS
                if(currentBB->xferPoints[k].dumpToXmm) ALOGI("XFER set_virtual_reg to xmm: xmm VR %d", reg);
#endif
                if(pType == LowOpndRegType_xmm)  {
#ifdef DEBUG_XFER_POINTS
                    ALOGI("XFER set_virtual_reg to memory: xmm VR %d", reg);
#endif
                    PhysicalReg regAll = (PhysicalReg)checkVirtualReg(reg, LowOpndRegType_xmm, 0 /* do not update*/);
                    dumpToMem(reg, LowOpndRegType_xmm, regAll);
                }
                if(currentBB->xferPoints[k].vr_gpl >= 0) { //
                }
                if(currentBB->xferPoints[k].vr_gph >= 0) {
                }
            }
            if((pType == LowOpndRegType_gp || pType == LowOpndRegType_ss) &&
               (currentBB->xferPoints[k].xtype == XFER_DEF_TO_MEM ||
                currentBB->xferPoints[k].xtype == XFER_DEF_TO_GP_MEM)) {
                //the defined gp VR already in register
                //invalidateXmmVR(currentBB->xferPoints[k].tableIndex);
                regAll = (PhysicalReg)checkVirtualReg(reg, pType, 0 /* do not update*/);
                dumpToMem(reg, pType, regAll);
#ifdef DEBUG_XFER_POINTS
                ALOGI("XFER set_virtual_reg to memory: gp VR %d", reg);
#endif
            }
            if((pType == LowOpndRegType_fs_s || pType == LowOpndRegType_ss) &&
               currentBB->xferPoints[k].xtype == XFER_DEF_TO_GP_MEM) {
            }
        }
    }
    return -1;
}
////////////////////////////////////////////////////////////////
//REGISTER ALLOCATION
int spillForHardReg(int regNum, int type);
void decreaseRefCount(int index);
int getFreeReg(int type, int reg, int indexToCompileTable);
PhysicalReg spillForLogicalReg(int type, int reg, int indexToCompileTable);
int unspillLogicalReg(int spill_index, int physicalReg);
int searchVirtualInfoOfBB(LowOpndRegType type, int regNum, BasicBlock_O1* bb);
bool isTemp8Bit(int type, int reg);
bool matchType(int typeA, int typeB);
int getNextAccess(int compileIndex);
void dumpCompileTable();

//! allocate a register for a variable

//!if no physical register is free, call spillForLogicalReg to free up a physical register;
//!if the variable is a temporary and it was spilled, call unspillLogicalReg to load from spill location to the allocated physical register;
//!if updateRefCount is true, reduce reference count of the variable by 1
int registerAlloc(int type, int reg, bool isPhysical, bool updateRefCount) {
#ifdef DEBUG_REGALLOC
    ALOGI("%p: try to allocate register %d type %d isPhysical %d", currentBB, reg, type, isPhysical);
#endif
    if(currentBB == NULL) {
        if(type & LowOpndRegType_virtual) return PhysicalReg_Null;
        if(isPhysical) return reg; //for helper functions
        return PhysicalReg_Null;
    }
    //ignore EDI, ESP, EBP (glue)
    if(isPhysical && (reg == PhysicalReg_EDI || reg == PhysicalReg_ESP ||
                      reg == PhysicalReg_EBP || reg == PhysicalReg_Null))
        return reg;

    int newType = convertType(type, reg, isPhysical);
    if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
    int tIndex = searchCompileTable(newType, reg);
    if(tIndex < 0) {
      ALOGE("reg %d type %d not found in registerAlloc", reg, newType);
      return PhysicalReg_Null;
    }

    //physical register
    if(isPhysical) {
        if(allRegs[reg].isUsed) { //if used by a non hard-coded register
            spillForHardReg(reg, newType);
        }
        allRegs[reg].isUsed = true;
#ifdef DEBUG_REG_USED
        ALOGI("REGALLOC: allocate a reg %d", reg);
#endif
        compileTable[tIndex].physicalReg = reg;
        if(updateRefCount)
            decreaseRefCount(tIndex);
#ifdef DEBUG_REGALLOC
        ALOGI("REGALLOC: allocate register %d for logical register %d %d",
               compileTable[tIndex].physicalReg, reg, newType);
#endif
        return reg;
    }
    //already allocated
    if(compileTable[tIndex].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_REGALLOC
        ALOGI("already allocated to physical register %d", compileTable[tIndex].physicalReg);
#endif
        if(updateRefCount)
            decreaseRefCount(tIndex);
        return compileTable[tIndex].physicalReg;
    }

    //at this point, the logical register is not hard-coded and is mapped to Reg_Null
    //first check whether there is a free reg
    //if not, call spillForLogicalReg
    int index = getFreeReg(newType, reg, tIndex);
    if(index >= 0 && index < PhysicalReg_Null) {
        //update compileTable & allRegs
        compileTable[tIndex].physicalReg = allRegs[index].physicalReg;
        allRegs[index].isUsed = true;
#ifdef DEBUG_REG_USED
        ALOGI("REGALLOC: register %d is free", allRegs[index].physicalReg);
#endif
    } else {
        PhysicalReg allocR = spillForLogicalReg(newType, reg, tIndex);
        compileTable[tIndex].physicalReg = allocR;
    }
    if(compileTable[tIndex].spill_loc_index >= 0) {
        unspillLogicalReg(tIndex, compileTable[tIndex].physicalReg);
    }
    if(updateRefCount)
        decreaseRefCount(tIndex);
#ifdef DEBUG_REGALLOC
    ALOGI("REGALLOC: allocate register %d for logical register %d %d",
           compileTable[tIndex].physicalReg, reg, newType);
#endif
    return compileTable[tIndex].physicalReg;
}
//!a variable will use a physical register allocated for another variable

//!This is used when MOVE_OPT is on, it tries to alias a virtual register with a temporary to remove a move
int registerAllocMove(int reg, int type, bool isPhysical, int srcReg) {
    if(srcReg == PhysicalReg_EDI || srcReg == PhysicalReg_ESP || srcReg == PhysicalReg_EBP)
        ALOGE("can't move from srcReg EDI or ESP or EBP");
#ifdef DEBUG_REGALLOC
    ALOGI("in registerAllocMove: reg %d type %d srcReg %d", reg, type, srcReg);
#endif
    int newType = convertType(type, reg, isPhysical);
    if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
    int index = searchCompileTable(newType, reg);
    if(index < 0) {
        ALOGE("reg %d type %d not found in registerAllocMove", reg, newType);
        return -1;
    }

    decreaseRefCount(index);
    compileTable[index].physicalReg = srcReg;
#ifdef DEBUG_REGALLOC
    ALOGI("REGALLOC: registerAllocMove %d for logical register %d %d",
           compileTable[index].physicalReg, reg, newType);
#endif
    return srcReg;
}

//! check whether a physical register is available to be used by a variable

//! data structures accessed:
//! 1> currentBB->infoBasicBlock[index].allocConstraintsSorted
//!    sorted from high count to low count
//! 2> currentBB->allocConstraintsSorted
//!    sorted from low count to high count
//! 3> allRegs: whether a physical register is available, indexed by PhysicalReg
//! NOTE: if a temporary variable is 8-bit, only %eax, %ebx, %ecx, %edx can be used
int getFreeReg(int type, int reg, int indexToCompileTable) {
    syncAllRegs();
    /* handles requests for xmm or ss registers */
    int k;
    if(((type & MASK_FOR_TYPE) == LowOpndRegType_xmm) ||
       ((type & MASK_FOR_TYPE) == LowOpndRegType_ss)) {
        for(k = PhysicalReg_XMM0; k <= PhysicalReg_XMM7; k++) {
            if(!allRegs[k].isUsed) return k;
        }
        return -1;
    }
#ifdef DEBUG_REGALLOC
    ALOGI("USED registers: ");
    for(k = 0; k < 8; k++)
        ALOGI("%d used: %d time freed: %d callee-saveld: %d", k, allRegs[k].isUsed,
             allRegs[k].freeTimeStamp, allRegs[k].isCalleeSaved);
    ALOGI("");
#endif

    /* a VR is requesting a physical register */
    if(isVirtualReg(type)) { //find a callee-saved register
        /* if VR is type GG, check the pre-allocated physical register first */
        bool isGGVR = compileTable[indexToCompileTable].gType == GLOBALTYPE_GG;
        if(isGGVR) {
            int regCandidateT = compileTable[indexToCompileTable].physicalReg_prev;
            if(!allRegs[regCandidateT].isUsed) return regCandidateT;
        }

        int index = searchVirtualInfoOfBB((LowOpndRegType)(type&MASK_FOR_TYPE), reg, currentBB);
        if(index < 0) {
            ALOGE("VR %d %d not found in infoBasicBlock of currentBB %d (num of VRs %d)",
                  reg, type, currentBB->bb_index, currentBB->num_regs);
            dvmAbort();
        }

        /* check allocConstraints for this VR,
           return an available physical register with the highest constraint > 0 */
        for(k = 0; k < 8; k++) {
            if(currentBB->infoBasicBlock[index].allocConstraintsSorted[k].count == 0) break;
            int regCandidateT = currentBB->infoBasicBlock[index].allocConstraintsSorted[k].physicalReg;
            assert(regCandidateT < PhysicalReg_Null);
            if(!allRegs[regCandidateT].isUsed) return regCandidateT;
        }

        /* WAS: return an available physical register with the lowest constraint
           NOW: consider a new factor (freeTime) when there is a tie
                if 2 available physical registers have the same number of constraints
                choose the one with smaller free time stamp */
        int currentCount = -1;
        int index1 = -1;
        int smallestTime = -1;
        for(k = 0; k < 8; k++) {
            int regCandidateT = currentBB->allocConstraintsSorted[k].physicalReg;
            assert(regCandidateT < PhysicalReg_Null);
            if(index1 >= 0 && currentBB->allocConstraintsSorted[k].count > currentCount)
                break; //candidate has higher count than index1
            if(!allRegs[regCandidateT].isUsed) {
                if(index1 < 0) {
                    index1 = k;
                    currentCount = currentBB->allocConstraintsSorted[k].count;
                    smallestTime = allRegs[regCandidateT].freeTimeStamp;
                } else if(allRegs[regCandidateT].freeTimeStamp < smallestTime) {
                    index1 = k;
                    smallestTime = allRegs[regCandidateT].freeTimeStamp;
                }
            }
        }
        if(index1 >= 0) return currentBB->allocConstraintsSorted[index1].physicalReg;
        return -1;
    }
    /* handle request from a temporary variable or a glue variable */
    else {
        bool is8Bit = isTemp8Bit(type, reg);

        /* if the temporary variable is linked to a VR and
              the VR is not yet allocated to any physical register */
        int vr_num = compileTable[indexToCompileTable].linkageToVR;
        if(vr_num >= 0) {
            int index3 = searchCompileTable(LowOpndRegType_gp | LowOpndRegType_virtual, vr_num);
            if(index3 < 0) {
                ALOGE("2 in tracing linkage to VR %d", vr_num);
                dvmAbort();
            }

            if(compileTable[index3].physicalReg == PhysicalReg_Null) {
                int index2 = searchVirtualInfoOfBB(LowOpndRegType_gp, vr_num, currentBB);
                if(index2 < 0) {
                    ALOGE("1 in tracing linkage to VR %d", vr_num);
                    dvmAbort();
                }
#ifdef DEBUG_REGALLOC
                ALOGI("in getFreeReg for temporary reg %d, trace the linkage to VR %d",
                     reg, vr_num);
#endif

                /* check allocConstraints on the VR
                   return an available physical register with the highest constraint > 0
                */
                for(k = 0; k < 8; k++) {
                    if(currentBB->infoBasicBlock[index2].allocConstraintsSorted[k].count == 0) break;
                    int regCandidateT = currentBB->infoBasicBlock[index2].allocConstraintsSorted[k].physicalReg;
#ifdef DEBUG_REGALLOC
                    ALOGI("check register %d with count %d", regCandidateT,
                          currentBB->infoBasicBlock[index2].allocConstraintsSorted[k].count);
#endif
                    /* if the requesting variable is 8 bit */
                    if(is8Bit && regCandidateT > PhysicalReg_EDX) continue;
                    assert(regCandidateT < PhysicalReg_Null);
                    if(!allRegs[regCandidateT].isUsed) return regCandidateT;
                }
            }
        }
        /* check allocConstraints of the basic block
           if 2 available physical registers have the same constraint count,
              return the non callee-saved physical reg */
        /* enhancement: record the time when a register is freed (freeTimeStamp)
                        the purpose is to reduce false dependency
           priority: constraint count, non callee-saved, time freed
               let x be the lowest constraint count
               set A be available callee-saved physical registers with count == x
               set B be available non callee-saved physical registers with count == x
               if set B is not null, return the one with smallest free time
               otherwise, return the one in A with smallest free time
           To ignore whether it is callee-saved, add all candidates to set A
        */
        int setAIndex[8];
        int num_A = 0;
        int setBIndex[8];
        int num_B = 0;
        int index1 = -1; //points to an available physical reg with lowest count
        int currentCount = -1;
        for(k = 0; k < 8; k++) {
            int regCandidateT = currentBB->allocConstraintsSorted[k].physicalReg;
            if(is8Bit && regCandidateT > PhysicalReg_EDX) continue;

            if(index1 >= 0 && currentBB->allocConstraintsSorted[k].count > currentCount)
                break; //candidate has higher count than index1
            assert(regCandidateT < PhysicalReg_Null);
            if(!allRegs[regCandidateT].isUsed) {
                /*To ignore whether it is callee-saved, add all candidates to set A */
                if(false) {//!allRegs[regCandidateT].isCalleeSaved) { //add to set B
                    setBIndex[num_B++] = k;
                } else { //add to set A
                    setAIndex[num_A++] = k;
                }
                if(index1 < 0) {
                    /* index1 points to a physical reg with lowest count */
                    index1 = k;
                    currentCount = currentBB->allocConstraintsSorted[k].count;
                }
            }
        }

        int kk;
        int smallestTime = -1;
        index1 = -1;
        for(kk = 0; kk < num_B; kk++) {
            k = setBIndex[kk];
            int regCandidateT = currentBB->allocConstraintsSorted[k].physicalReg;
            assert(regCandidateT < PhysicalReg_Null);
            if(kk == 0 || allRegs[regCandidateT].freeTimeStamp < smallestTime) {
                index1 = k;
                smallestTime = allRegs[regCandidateT].freeTimeStamp;
            }
        }
        if(index1 >= 0)
            return currentBB->allocConstraintsSorted[index1].physicalReg;
        index1 = -1;
        for(kk = 0; kk < num_A; kk++) {
            k = setAIndex[kk];
            int regCandidateT = currentBB->allocConstraintsSorted[k].physicalReg;
            if(kk == 0 || allRegs[regCandidateT].freeTimeStamp < smallestTime) {
                index1 = k;
                smallestTime = allRegs[regCandidateT].freeTimeStamp;
            }
        }
        if(index1 >= 0) return currentBB->allocConstraintsSorted[index1].physicalReg;
        return -1;
    }
    return -1;
}

//! find a candidate physical register for a variable and spill all variables that are mapped to the candidate

//!
PhysicalReg spillForLogicalReg(int type, int reg, int indexToCompileTable) {
    //choose a used register to spill
    //when a GG virtual register is spilled, write it to interpretd stack, set physicalReg to Null
    //  at end of the basic block, load spilled GG VR to physical reg
    //when other types of VR is spilled, write it to interpreted stack, set physicalReg to Null
    //when a temporary (non-virtual) register is spilled, write it to stack, set physicalReg to Null
    //can we spill a hard-coded temporary register? YES
    int k, k2;
    PhysicalReg allocR;

    //do not try to free a physical reg that is used by more than one logical registers
    //fix on sep 28, 2009
    //do not try to spill a hard-coded logical register
    //do not try to free a physical reg that is outside of the range for 8-bit logical reg
    /* for each physical register,
       collect number of non-hardcode entries that are mapped to the physical register */
    int numOfUses[PhysicalReg_Null];
    for(k = PhysicalReg_EAX; k < PhysicalReg_Null; k++)
        numOfUses[k] = 0;
    for(k = 0; k < num_compile_entries; k++) {
        if((compileTable[k].physicalReg != PhysicalReg_Null) &&
           matchType(type, compileTable[k].physicalType) &&
           (compileTable[k].physicalType & LowOpndRegType_hard) == 0) {
            numOfUses[compileTable[k].physicalReg]++;
        }
    }

    /* candidates: all non-hardcode entries that are mapped to
           a physical register that is used by only one entry*/
    bool is8Bit = isTemp8Bit(type, reg);
    int candidates[COMPILE_TABLE_SIZE];
    int num_cand = 0;
    for(k = 0; k < num_compile_entries; k++) {
        if(matchType(type, compileTable[k].physicalType) &&
           compileTable[k].physicalReg != PhysicalReg_Null) {
            if(is8Bit && compileTable[k].physicalReg > PhysicalReg_EDX) continue; //not a candidate
            if(!canSpillReg[compileTable[k].physicalReg]) continue; //not a candidate
            if((compileTable[k].physicalType & LowOpndRegType_hard) == 0 &&
               numOfUses[compileTable[k].physicalReg] <= 1) {
                candidates[num_cand++] = k;
            }
        }
    }

    /* go through all candidates:
       first check GLUE-related entries */
    int spill_index = -1;
    for(k2 = 0; k2 < num_cand; k2++) {
        k = candidates[k2];
        if((compileTable[k].physicalReg != PhysicalReg_Null) &&
           matchType(type, compileTable[k].physicalType) &&
           (compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX &&
            compileTable[k].regNum != PhysicalReg_GLUE)) {
            allocR = (PhysicalReg)spillLogicalReg(k, true);
#ifdef DEBUG_REGALLOC
            ALOGI("SPILL register used by num %d type %d it is a GLUE register with refCount %d",
                  compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].refCount);
#endif
            return allocR;
        }
    }

    /* out of the candates, find a VR that has the furthest next use */
    int furthestUse = offsetPC;
    for(k2 = 0; k2 < num_cand; k2++) {
        k = candidates[k2];
        if((compileTable[k].physicalReg != PhysicalReg_Null) &&
           matchType(type, compileTable[k].physicalType) &&
           isVirtualReg(compileTable[k].physicalType)) {
            int nextUse = getNextAccess(k);
            if(spill_index < 0 || nextUse > furthestUse) {
                spill_index = k;
                furthestUse = nextUse;
            }
        }
    }

    /* spill the VR with the furthest next use */
    if(spill_index >= 0) {
        allocR = (PhysicalReg)spillLogicalReg(spill_index, true);
        return allocR; //the register is still being used
    }

    /* spill an entry with the smallest refCount */
    int baseLeftOver = 0;
    int index = -1;
    for(k2 = 0; k2 < num_cand; k2++) {
        k = candidates[k2];
        if(k != indexForGlue &&
           (compileTable[k].physicalReg != PhysicalReg_Null) &&
           (compileTable[k].physicalType & LowOpndRegType_hard) == 0 && //not hard-coded
           matchType(type, compileTable[k].physicalType)) {
            if((index < 0) || (compileTable[k].refCount < baseLeftOver)) {
                baseLeftOver = compileTable[k].refCount;
                index = k;
            }
        }
    }
    if(index < 0) {
        dumpCompileTable();
        ALOGE("no register to spill for logical %d %d", reg, type);
        dvmAbort();
    }
    allocR = (PhysicalReg)spillLogicalReg(index, true);
#ifdef DEBUG_REGALLOC
    ALOGI("SPILL register used by num %d type %d it is a temporary register with refCount %d",
           compileTable[index].regNum, compileTable[index].physicalType, compileTable[index].refCount);
#endif
    return allocR;
}
//!spill a variable to memory, the variable is specified by an index to compileTable

//!If the variable is a temporary, get a spill location that is not in use and spill the content to the spill location;
//!If updateTable is true, set physicalReg to Null;
//!Return the physical register that was allocated to the variable
int spillLogicalReg(int spill_index, bool updateTable) {
    if((compileTable[spill_index].physicalType & LowOpndRegType_hard) != 0) {
        ALOGE("can't spill a hard-coded register");
        dvmAbort();
    }
    int physicalReg = compileTable[spill_index].physicalReg;
    if(!canSpillReg[physicalReg]) {
#ifdef PRINT_WARNING
        ALOGW("can't spill register %d", physicalReg);
#endif
        //dvmAbort(); //this happens in get_virtual_reg where VR is allocated to the same reg as the hardcoded temporary
    }
    if(isVirtualReg(compileTable[spill_index].physicalType)) {
        //spill back to memory
        dumpToMem(compileTable[spill_index].regNum,
                  (LowOpndRegType)(compileTable[spill_index].physicalType&MASK_FOR_TYPE),
                  compileTable[spill_index].physicalReg);
    }
    else {
        //update spill_loc_index
        int k = getSpillIndex(spill_index == indexForGlue,
                    getRegSize(compileTable[spill_index].physicalType));
        compileTable[spill_index].spill_loc_index = 4*k;
        if(k >= 0)
            spillIndexUsed[k] = 1;
        saveToSpillRegion(getRegSize(compileTable[spill_index].physicalType),
                          compileTable[spill_index].physicalReg, 4*k);
    }
    //compileTable[spill_index].physicalReg_prev = compileTable[spill_index].physicalReg;
#ifdef DEBUG_REGALLOC
    ALOGI("REGALLOC: SPILL logical reg %d %d with refCount %d allocated to %d",
           compileTable[spill_index].regNum,
           compileTable[spill_index].physicalType, compileTable[spill_index].refCount,
           compileTable[spill_index].physicalReg);
#endif
    if(!updateTable) return PhysicalReg_Null;

    int allocR = compileTable[spill_index].physicalReg;
    compileTable[spill_index].physicalReg = PhysicalReg_Null;
    return allocR;
}
//! load a varible from memory to physical register, the variable is specified with an index to compileTable

//!If the variable is a temporary, load from spill location and set the flag for the spill location to not used
int unspillLogicalReg(int spill_index, int physicalReg) {
    //can't un-spill to %eax in afterCall!!!
    //what if GG VR is allocated to %eax!!!
    if(isVirtualReg(compileTable[spill_index].physicalType)) {
        get_virtual_reg_noalloc(compileTable[spill_index].regNum,
                                getRegSize(compileTable[spill_index].physicalType),
                                physicalReg, true);
    }
    else {
        loadFromSpillRegion(getRegSize(compileTable[spill_index].physicalType),
                            physicalReg, compileTable[spill_index].spill_loc_index);
        spillIndexUsed[compileTable[spill_index].spill_loc_index >> 2] = 0;
        compileTable[spill_index].spill_loc_index = -1;
    }
#ifdef DEBUG_REGALLOC
    ALOGI("REGALLOC: UNSPILL logical reg %d %d with refCount %d", compileTable[spill_index].regNum,
           compileTable[spill_index].physicalType, compileTable[spill_index].refCount);
#endif
    return PhysicalReg_Null;
}

//!spill a virtual register to memory

//!if the current value of a VR is constant, write immediate to memory;
//!if the current value of a VR is in a physical register, call spillLogicalReg to dump content of the physical register to memory;
//!ifupdateTable is true, set the physical register for VR to Null and decrease reference count of the virtual register
int spillVirtualReg(int vrNum, LowOpndRegType type, bool updateTable) {
    int index = searchCompileTable(type | LowOpndRegType_virtual, vrNum);
    if(index < 0) {
        ALOGE("can't find VR %d %d in spillVirtualReg", vrNum, type);
        return -1;
    }
    //check whether it is const
    int value[2];
    int isConst = isVirtualRegConstant(vrNum, type, value, false); //do not update refCount
    if(isConst == 1 || isConst == 3) {
        dumpImmToMem(vrNum, OpndSize_32, value[0]);
    }
    if(getRegSize(type) == OpndSize_64 && (isConst == 2 || isConst == 3)) {
        dumpImmToMem(vrNum+1, OpndSize_32, value[1]);
    }
    if(isConst != 3 && compileTable[index].physicalReg != PhysicalReg_Null)
        spillLogicalReg(index, updateTable);
    if(updateTable) decreaseRefCount(index);
    return -1;
}

//! spill variables that are mapped to physical register (regNum)

//!
int spillForHardReg(int regNum, int type) {
    //find an entry that uses the physical register
    int spill_index = -1;
    int k;
    for(k = 0; k < num_compile_entries; k++) {
        if(k != indexForGlue &&
           compileTable[k].physicalReg == regNum &&
           matchType(type, compileTable[k].physicalType)) {
            spill_index = k;
            if(compileTable[k].regNum == regNum && compileTable[k].physicalType == type)
                continue;
            if(inGetVR_num >= 0 && compileTable[k].regNum == inGetVR_num && compileTable[k].physicalType == (type | LowOpndRegType_virtual))
                continue;
#ifdef DEBUG_REGALLOC
            ALOGI("SPILL logical reg %d %d to free hard-coded reg %d %d",
                   compileTable[spill_index].regNum, compileTable[spill_index].physicalType,
                   regNum, type);
            if(compileTable[spill_index].physicalType & LowOpndRegType_hard) dumpCompileTable();
#endif
            assert(spill_index < COMPILE_TABLE_SIZE);
            spillLogicalReg(spill_index, true);
        }
    }
    return regNum;
}
////////////////////////////////////////////////////////////////
//! update allocConstraints of the current basic block

//! allocConstraints specify how many times a hardcoded register is used in this basic block
void updateCurrentBBWithConstraints(PhysicalReg reg) {
    if(reg > PhysicalReg_EBP) {
        ALOGE("register %d out of range in updateCurrentBBWithConstraints", reg);
    }
    currentBB->allocConstraints[reg].count++;
}
//! sort allocConstraints and save the result in allocConstraintsSorted

//! allocConstraints specify how many times a virtual register is linked to a hardcode register
//! it is updated in getVirtualRegInfo and merged by mergeEntry2
int sortAllocConstraint(RegAllocConstraint* allocConstraints,
                        RegAllocConstraint* allocConstraintsSorted, bool fromHighToLow) {
    int ii, jj;
    int num_sorted = 0;
    for(jj = 0; jj < 8; jj++) {
        //figure out where to insert allocConstraints[jj]
        int count = allocConstraints[jj].count;
        int regT = allocConstraints[jj].physicalReg;
        assert(regT < PhysicalReg_Null);
        int insertIndex = -1;
        for(ii = 0; ii < num_sorted; ii++) {
            int regT2 = allocConstraintsSorted[ii].physicalReg;
            assert(regT2 < PhysicalReg_Null);
            if(allRegs[regT].isCalleeSaved &&
               count == allocConstraintsSorted[ii].count) {
                insertIndex = ii;
                break;
            }
            if((!allRegs[regT].isCalleeSaved) &&
               count == allocConstraintsSorted[ii].count &&
               (!allRegs[regT2].isCalleeSaved)) { //skip until found one that is not callee-saved
                insertIndex = ii;
                break;
            }
            if((fromHighToLow && count > allocConstraintsSorted[ii].count) ||
               ((!fromHighToLow) && count < allocConstraintsSorted[ii].count)) {
                insertIndex = ii;
                break;
            }
        }
        if(insertIndex < 0) {
            allocConstraintsSorted[num_sorted].physicalReg = (PhysicalReg)regT;
            allocConstraintsSorted[num_sorted].count = count;
            num_sorted++;
        } else {
            for(ii = num_sorted-1; ii >= insertIndex; ii--) {
                allocConstraintsSorted[ii+1] = allocConstraintsSorted[ii];
            }
            allocConstraintsSorted[insertIndex] = allocConstraints[jj];
            num_sorted++;
        }
    } //for jj
#ifdef DEBUG_ALLOC_CONSTRAINT
    for(jj = 0; jj < 8; jj++) {
        if(allocConstraintsSorted[jj].count > 0)
            ALOGI("%d: register %d has count %d", jj, allocConstraintsSorted[jj].physicalReg, allocConstraintsSorted[jj].count);
    }
#endif
    return 0;
}
//! find the entry for a given virtual register in compileTable

//!
int findVirtualRegInTable(u2 vA, LowOpndRegType type, bool printError) {
    int k = searchCompileTable(type | LowOpndRegType_virtual, vA);
    if(k < 0 && printError) {
        ALOGE("findVirtualRegInTable virtual register %d type %d", vA, type);
        dvmAbort();
    }
    return k;
}

//! check whether a virtual register is constant

//! the value of the constant is stored in valuePtr; if updateRefCount is true & the VR is constant, reference count for the VR will be reduced by 1
int isVirtualRegConstant(int regNum, LowOpndRegType type, int* valuePtr, bool updateRefCount) {

    OpndSize size = getRegSize(type);
    int k;
    int indexL = -1;
    int indexH = -1;
    for(k = 0; k < num_const_vr; k++) {
#ifdef DEBUG_CONST
        ALOGI("constVRTable VR %d isConst %d value %x", constVRTable[k].regNum, constVRTable[k].isConst, constVRTable[k].value);
#endif
        if(constVRTable[k].regNum == regNum) {
            indexL = k;
            continue;
        }
        if(constVRTable[k].regNum == regNum + 1 && size == OpndSize_64) {
            indexH = k;
            continue;
        }
    }
    bool isConstL = false;
    bool isConstH = false;
    if(indexL >= 0) {
        isConstL = constVRTable[indexL].isConst;
    }
    if(size == OpndSize_64 && indexH >= 0) {
        isConstH = constVRTable[indexH].isConst;
    }

    if((isConstL || isConstH)) {
        if(size == OpndSize_64 && isConstH)
            valuePtr[1] = constVRTable[indexH].value;
        if(isConstL)
            *valuePtr = constVRTable[indexL].value;
    }
    if((isConstL && size == OpndSize_32) || (isConstL && isConstH)) {
        if(updateRefCount) {
            int indexOrig = searchCompileTable(type | LowOpndRegType_virtual, regNum);
            if(indexOrig < 0) ALOGE("can't find VR in isVirtualRegConstant num %d type %d", regNum, type);
            decreaseRefCount(indexOrig);
        }
#ifdef DEBUG_CONST
        ALOGI("VR %d %d is const case", regNum, type);
#endif
        return 3;
    }
    if(size == OpndSize_32) return 0;
    if(isConstL) return 1;
    if(isConstH) return 2;
    return 0;
}

//!update RegAccessType of virtual register vB given RegAccessType of vA

//!RegAccessType can be D, L, H
//!D means full definition, L means only lower-half is defined, H means only higher half is defined
//!we say a VR has no exposed usage in a basic block if the accessType is D or DU
//!we say a VR has exposed usage in a basic block if the accessType is not D nor DU
//!we say a VR has exposed usage in other basic blocks (hasOtherExposedUsage) if
//!  there exists another basic block where VR has exposed usage in that basic block
//!A can be U, D, L, H, UD, UL, UH, DU, LU, HU (merged result)
//!B can be U, D, UD, DU (an entry for the current bytecode)
//!input isAPartiallyOverlapB can be any value between -1 to 6
//!if A is xmm: gp B lower half of A, (isAPartiallyOverlapB is 1)
//!             gp B higher half of A, (isAPartiallyOverlapB is 2)
//!             lower half of A covers the higher half of xmm B  (isAPartiallyOverlapB is 4)
//!             higher half of A covers the lower half of xmm B   (isAPartiallyOverlapB is 3)
//!if A is gp:  A covers the lower half of xmm B, (isAPartiallyOverlapB is 5)
//!             A covers the higher half of xmm B (isAPartiallyOverlapB is 6)
RegAccessType updateAccess1(RegAccessType A, OverlapCase isAPartiallyOverlapB) {
    if(A == REGACCESS_D || A == REGACCESS_DU || A == REGACCESS_UD) {
        if(isAPartiallyOverlapB == OVERLAP_ALIGN) return REGACCESS_D;
        if(isAPartiallyOverlapB == OVERLAP_B_IS_LOW_OF_A || isAPartiallyOverlapB == OVERLAP_B_IS_HIGH_OF_A)
            return REGACCESS_D;
        if(isAPartiallyOverlapB == OVERLAP_LOW_OF_A_IS_HIGH_OF_B || isAPartiallyOverlapB == OVERLAP_A_IS_LOW_OF_B)
            return REGACCESS_L;
        return REGACCESS_H;
    }
    if(A == REGACCESS_L || A == REGACCESS_LU || A == REGACCESS_UL) {
        if(isAPartiallyOverlapB == OVERLAP_ALIGN || isAPartiallyOverlapB == OVERLAP_A_IS_LOW_OF_B)
            return REGACCESS_L;
        if(isAPartiallyOverlapB == OVERLAP_B_IS_LOW_OF_A) return REGACCESS_D;
        if(isAPartiallyOverlapB == OVERLAP_B_IS_HIGH_OF_A || isAPartiallyOverlapB == OVERLAP_LOW_OF_A_IS_HIGH_OF_B)
            return REGACCESS_N;
        if(isAPartiallyOverlapB == OVERLAP_HIGH_OF_A_IS_LOW_OF_B || isAPartiallyOverlapB == OVERLAP_A_IS_HIGH_OF_B)
            return REGACCESS_H;
    }
    if(A == REGACCESS_H || A == REGACCESS_HU || A == REGACCESS_UH) {
        if(isAPartiallyOverlapB == OVERLAP_ALIGN || isAPartiallyOverlapB == OVERLAP_A_IS_HIGH_OF_B)
            return REGACCESS_H;
        if(isAPartiallyOverlapB == OVERLAP_B_IS_LOW_OF_A || isAPartiallyOverlapB == OVERLAP_HIGH_OF_A_IS_LOW_OF_B)
            return REGACCESS_N;
        if(isAPartiallyOverlapB == OVERLAP_B_IS_HIGH_OF_A) return REGACCESS_D;
        if(isAPartiallyOverlapB == OVERLAP_LOW_OF_A_IS_HIGH_OF_B || isAPartiallyOverlapB == OVERLAP_A_IS_LOW_OF_B)
            return REGACCESS_L;
    }
    return REGACCESS_N;
}
//! merge RegAccessType C1 with RegAccessType C2

//!C can be N,L,H,D
RegAccessType updateAccess2(RegAccessType C1, RegAccessType C2) {
    if(C1 == REGACCESS_D || C2 == REGACCESS_D) return REGACCESS_D;
    if(C1 == REGACCESS_N) return C2;
    if(C2 == REGACCESS_N) return C1;
    if(C1 == REGACCESS_L && C2 == REGACCESS_H) return REGACCESS_D;
    if(C1 == REGACCESS_H && C2 == REGACCESS_L) return REGACCESS_D;
    return C1;
}
//! merge RegAccessType C with RegAccessType B

//!C can be N,L,H,D
//!B can be U, D, UD, DU
RegAccessType updateAccess3(RegAccessType C, RegAccessType B) {
    if(B == REGACCESS_D || B == REGACCESS_DU) return B; //no exposed usage
    if(B == REGACCESS_U || B == REGACCESS_UD) {
        if(C == REGACCESS_N) return B;
        if(C == REGACCESS_L) return REGACCESS_LU;
        if(C == REGACCESS_H) return REGACCESS_HU;
        if(C == REGACCESS_D) return REGACCESS_DU;
    }
    return B;
}
//! merge RegAccessType A with RegAccessType B

//!argument isBPartiallyOverlapA can be any value between -1 and 2
//!0 means fully overlapping, 1 means B is the lower half, 2 means B is the higher half
RegAccessType mergeAccess2(RegAccessType A, RegAccessType B, OverlapCase isBPartiallyOverlapA) {
    if(A == REGACCESS_UD || A == REGACCESS_UL || A == REGACCESS_UH ||
       A == REGACCESS_DU || A == REGACCESS_LU || A == REGACCESS_HU) return A;
    if(A == REGACCESS_D) {
        if(B == REGACCESS_D) return REGACCESS_D;
        if(B == REGACCESS_U) return REGACCESS_DU;
        if(B == REGACCESS_UD) return REGACCESS_DU;
        if(B == REGACCESS_DU) return B;
    }
    if(A == REGACCESS_U) {
        if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_UL;
        if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_UH;
        if(B == REGACCESS_D && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_UD;
        if(B == REGACCESS_U) return A;
        if(B == REGACCESS_UD && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_UL;
        if(B == REGACCESS_UD && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_UH;
        if(B == REGACCESS_UD && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_UD;
        if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_UL;
        if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_UH;
        if(B == REGACCESS_DU && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_UD;
    }
    if(A == REGACCESS_L) {
        if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_L;
        if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_D;
        if(B == REGACCESS_D && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_D;
        if(B == REGACCESS_U) return REGACCESS_LU;
        if(B == REGACCESS_UD) return REGACCESS_LU;
        if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_LU;
        if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_DU;
        if(B == REGACCESS_DU && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_DU;
    }
    if(A == REGACCESS_H) {
        if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_D;
        if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_H;
        if(B == REGACCESS_D && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_D;
        if(B == REGACCESS_U) return REGACCESS_HU;
        if(B == REGACCESS_UD) return REGACCESS_HU;
        if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_DU;
        if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_HU;
        if(B == REGACCESS_DU && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_DU;
    }
    return REGACCESS_N;
}

//!determines which part of a use is from a given definition

//!reachingDefLive tells us which part of the def is live at this point
//!isDefPartiallyOverlapUse can be any value between -1 and 2
RegAccessType setAccessTypeOfUse(OverlapCase isDefPartiallyOverlapUse, RegAccessType reachingDefLive) {
    if(isDefPartiallyOverlapUse == OVERLAP_B_COVER_A)
        return reachingDefLive;
    if(isDefPartiallyOverlapUse == OVERLAP_B_COVER_LOW_OF_A) { //def covers the low half of use
        return REGACCESS_L;
    }
    if(isDefPartiallyOverlapUse == OVERLAP_B_COVER_HIGH_OF_A) {
        return REGACCESS_H;
    }
    return REGACCESS_N;
}

//! search currentBB->defUseTable to find a def for regNum at offsetPC

//!
DefUsePair* searchDefUseTable(int offsetPC, int regNum, LowOpndRegType pType) {
    DefUsePair* ptr = currentBB->defUseTable;
    while(ptr != NULL) {
        if(ptr->def.offsetPC == offsetPC &&
           ptr->def.regNum == regNum &&
           ptr->def.physicalType == pType) {
            return ptr;
        }
        ptr = ptr->next;
    }
    return NULL;
}
void printDefUseTable() {
    ALOGI("PRINT defUseTable --------");
    DefUsePair* ptr = currentBB->defUseTable;
    while(ptr != NULL) {
        ALOGI("  def @ %x of VR %d %d has %d uses", ptr->def.offsetPC,
              ptr->def.regNum, ptr->def.physicalType,
              ptr->num_uses);
        DefOrUseLink* ptr2 = ptr->uses;
        while(ptr2 != NULL) {
            ALOGI("    use @ %x of VR %d %d accessType %d", ptr2->offsetPC,
                  ptr2->regNum,
                  ptr2->physicalType,
                  ptr2->accessType);
            ptr2 = ptr2->next;
        }
        ptr = ptr->next;
    }
}
//! when a VR is used, check whether a transfer from memory to XMM is necessary

//!
int updateVRAtUse(int reg, LowOpndRegType pType, int regAll) {
    int k;
    for(k = 0; k < currentBB->num_xfer_points; k++) {
        if(currentBB->xferPoints[k].offsetPC == offsetPC &&
           currentBB->xferPoints[k].xtype == XFER_MEM_TO_XMM &&
           currentBB->xferPoints[k].regNum == reg &&
           currentBB->xferPoints[k].physicalType == pType) {
#ifdef DEBUG_XFER_POINTS
            ALOGI("XFER from memory to xmm %d", reg);
#endif
            move_mem_to_reg_noalloc(OpndSize_64,
                                    4*currentBB->xferPoints[k].regNum, PhysicalReg_FP, true,
                                    MemoryAccess_VR, currentBB->xferPoints[k].regNum,
                                    regAll, true);
        }
    }
    return 0;
}
///////////////////////////////////////////////////////////////////////////////
// DEAD/USELESS STATEMENT ELMINATION
// bytecodes can be removed if a bytecode has no side effect and the defs are not used
// this optimization is guarded with DSE_OPT
// currently, this optimization is not on, since it does not provide observable performance improvement
//     and it increases compilation time

/* we remove a maximal of 40 bytecodes within a single basic block */
#define MAX_NUM_DEAD_PC_IN_BB 40
int deadPCs[MAX_NUM_DEAD_PC_IN_BB];
int num_dead_pc = 0;
//! collect all PCs that can be removed

//! traverse each byte code in the current basic block and check whether it can be removed, if yes, update deadPCs
void getDeadStmts() {
    BasicBlock_O1* bb = currentBB;
    int k;
    num_dead_pc = 0;
    //traverse each bytecode in the basic block
    //update offsetPC, rPC & inst
    u2* rPC_start = (u2*)currentMethod->insns;
    MIR* mir;
    for(mir = bb->jitBasicBlock->firstMIRInsn; mir; mir = mir->next) {
        offsetPC = mir->seqNum;
        rPC = rPC_start + mir->offset;
        if(mir->dalvikInsn.opcode >= kNumPackedOpcodes) continue;
#ifdef DEBUG_DSE
        ALOGI("DSE: offsetPC %x", offsetPC);
#endif
        inst = FETCH(0);
        bool isDeadStmt = true;
        getVirtualRegInfo(infoByteCode);
        u2 inst_op = INST_INST(inst);
	//skip bytecodes with side effect
        if(inst_op != OP_CONST_STRING && inst_op != OP_CONST_STRING_JUMBO &&
           inst_op != OP_MOVE && inst_op != OP_MOVE_OBJECT &&
           inst_op != OP_MOVE_FROM16 && inst_op != OP_MOVE_OBJECT_FROM16 &&
           inst_op != OP_MOVE_16 && inst_op != OP_CONST_CLASS &&
           inst_op != OP_MOVE_OBJECT_16 && inst_op != OP_MOVE_WIDE &&
           inst_op != OP_MOVE_WIDE_FROM16 && inst_op != OP_MOVE_WIDE_16 &&
           inst_op != OP_MOVE_RESULT && inst_op != OP_MOVE_RESULT_OBJECT) {
            continue;
        }
        //some statements do not define any VR!!!
        int num_defs = 0;
        for(k = 0; k < num_regs_per_bytecode; k++) {
            if(infoByteCode[k].accessType == REGACCESS_D ||
               infoByteCode[k].accessType == REGACCESS_UD ||
               infoByteCode[k].accessType == REGACCESS_DU) { //search defUseTable
                num_defs++;
                DefUsePair* indexT = searchDefUseTable(offsetPC, infoByteCode[k].regNum, infoByteCode[k].physicalType);
                if(indexT == NULL) {
                    ALOGE("def at %x of VR %d %d not in table",
                           offsetPC, infoByteCode[k].regNum, infoByteCode[k].physicalType);
                    return;
                }
                if(indexT->num_uses > 0) {
                    isDeadStmt = false;
                    break;
                } else {
#ifdef DEBUG_DSE
                    ALOGI("DSE: num_uses is %d for def at %d for VR %d %d", indexT->num_uses,
                          offsetPC, infoByteCode[k].regNum, infoByteCode[k].physicalType);
#endif
                }
            }
        } //for k
        if(num_defs == 0) isDeadStmt = false;
        if(isDeadStmt && num_dead_pc < MAX_NUM_DEAD_PC_IN_BB) {
#ifdef DEBUG_DSE
            ALOGI("DSE: stmt at %x is dead", offsetPC);
#endif
            deadPCs[num_dead_pc++] = offsetPC;
        }
    } //for offsetPC
#ifdef DEBUG_DSE
    ALOGI("Dead Stmts: ");
    for(k = 0; k < num_dead_pc; k++) ALOGI("%x ", deadPCs[k]);
    ALOGI("");
#endif
}
//! entry point to remove dead statements

//! recursively call getDeadStmts and remove uses in defUseTable that are from a dead PC
//! until there is no change to number of dead PCs
void removeDeadDefs() {
    int k;
    int deadPCs_2[MAX_NUM_DEAD_PC_IN_BB];
    int num_dead_pc_2 = 0;
    getDeadStmts();
    if(num_dead_pc == 0) return;
    DefUsePair* ptr = NULL;
    DefOrUseLink* ptrUse = NULL;
    DefOrUseLink* ptrUse_prev = NULL;
    while(true) {
        //check all the uses in defUseTable and remove any use that is from a dead PC
        ptr = currentBB->defUseTable;
        while(ptr != NULL) {
            int k3;
            ptrUse = ptr->uses;
            ptrUse_prev = NULL;
            while(ptrUse != NULL) {
                bool isIn = false;
                for(k3 = 0; k3 < num_dead_pc; k3++) {
                    if(ptrUse->offsetPC == deadPCs[k3]) {
                        isIn = true;
                        break;
                    }
                }//k3
                if(!isIn) {
                    ptrUse_prev = ptrUse;
                    ptrUse = ptrUse->next; //next use
                }
                else {
                    //go to next use and remove ptrUse
#ifdef DEBUG_DSE
                    ALOGI("DSE: remove usage at offsetPC %d reached by def at %d", ptrUse->offsetPC,
                           ptr->def.offsetPC);
#endif
                    DefOrUseLink* nextP = ptrUse->next;
                    if(ptrUse == ptr->useTail) ptr->useTail = ptrUse_prev;
                    free(ptrUse);
                    if(ptrUse_prev == NULL) {
                        ptr->uses = nextP;
                    } else {
                        ptrUse_prev->next = nextP;
                    }
                    ptrUse = nextP; //do not update ptrUse_prev
                    ptr->num_uses--;
                }
            }//while ptrUse
            ptr = ptr->next;
        }//while ptr
	//save deadPCs in deadPCs_2
        num_dead_pc_2 = num_dead_pc;
        for(k = 0; k < num_dead_pc_2; k++)
            deadPCs_2[k] = deadPCs[k];
	//update deadPCs
        getDeadStmts();
	//if no change to number of dead PCs, break out of the while loop
        if(num_dead_pc_2 == num_dead_pc) break;
    }//while
#ifdef DEBUG_DSE
    ALOGI("DSE: DEAD STMTS: ");
    for(k = 0; k < num_dead_pc; k++) {
        ALOGI("%d ", deadPCs[k]);
    }
    ALOGI("");
#endif
}
/////////////////////////////////////////////////////////////
//!search memVRTable for a given virtual register

//!
int searchMemTable(int regNum) {
    int k;
    for(k = 0; k < num_memory_vr; k++) {
        if(memVRTable[k].regNum == regNum) {
            return k;
        }
    }
    ALOGW("in searchMemTable can't find VR %d num_memory_vr %d", regNum, num_memory_vr);
    return -1;
}
/////////////////////////////////////////////////////////////////////////
// A VR is already in memory && NULL CHECK
//!check whether the latest content of a VR is in memory

//!
bool isInMemory(int regNum, OpndSize size) {
    int indexL = searchMemTable(regNum);
    int indexH = -1;
    if(size == OpndSize_64) indexH = searchMemTable(regNum+1);
    if(indexL < 0) return false;
    if(size == OpndSize_64 && indexH < 0) return false;
    if(!memVRTable[indexL].inMemory) return false;
    if(size == OpndSize_64 && (!memVRTable[indexH].inMemory)) return false;
    return true;
}
//!set field inMemory of memVRTable to true

//!
void setVRToMemory(int regNum, OpndSize size) {
    int indexL = searchMemTable(regNum);
    int indexH = -1;
    if(size == OpndSize_64) indexH = searchMemTable(regNum+1);
    if(indexL < 0) {
        ALOGE("VR %d not in memVRTable", regNum);
        return;
    }
    memVRTable[indexL].inMemory = true;
    if(size == OpndSize_64) {
        if(indexH < 0) {
            ALOGE("VR %d not in memVRTable", regNum+1);
            return;
        }
        memVRTable[indexH].inMemory = true;
    }
}
//! check whether null check for a VR is performed previously

//!
bool isVRNullCheck(int regNum, OpndSize size) {
    if(size != OpndSize_32) {
        ALOGE("isVRNullCheck size should be 32");
        dvmAbort();
    }
    int indexL = searchMemTable(regNum);
    if(indexL < 0) {
        ALOGE("VR %d not in memVRTable", regNum);
        return false;
    }
    return memVRTable[indexL].nullCheckDone;
}
bool isVRBoundCheck(int vr_array, int vr_index) {
    int indexL = searchMemTable(vr_array);
    if(indexL < 0) {
        ALOGE("isVRBoundCheck: VR %d not in memVRTable", vr_array);
        return false;
    }
    if(memVRTable[indexL].boundCheck.indexVR == vr_index)
        return memVRTable[indexL].boundCheck.checkDone;
    return false;
}
//! set nullCheckDone in memVRTable to true

//!
void setVRNullCheck(int regNum, OpndSize size) {
    if(size != OpndSize_32) {
        ALOGE("setVRNullCheck size should be 32");
        dvmAbort();
    }
    int indexL = searchMemTable(regNum);
    if(indexL < 0) {
        ALOGE("VR %d not in memVRTable", regNum);
        return;
    }
    memVRTable[indexL].nullCheckDone = true;
}
void setVRBoundCheck(int vr_array, int vr_index) {
    int indexL = searchMemTable(vr_array);
    if(indexL < 0) {
        ALOGE("setVRBoundCheck: VR %d not in memVRTable", vr_array);
        return;
    }
    memVRTable[indexL].boundCheck.indexVR = vr_index;
    memVRTable[indexL].boundCheck.checkDone = true;
}
void clearVRBoundCheck(int regNum, OpndSize size) {
    int k;
    for(k = 0; k < num_memory_vr; k++) {
        if(memVRTable[k].regNum == regNum ||
           (size == OpndSize_64 && memVRTable[k].regNum == regNum+1)) {
            memVRTable[k].boundCheck.checkDone = false;
        }
        if(memVRTable[k].boundCheck.indexVR == regNum ||
           (size == OpndSize_64 && memVRTable[k].boundCheck.indexVR == regNum+1)) {
            memVRTable[k].boundCheck.checkDone = false;
        }
    }
}
//! set inMemory of memVRTable to false

//!
void clearVRToMemory(int regNum, OpndSize size) {
    int indexL = searchMemTable(regNum);
    int indexH = -1;
    if(size == OpndSize_64) indexH = searchMemTable(regNum+1);
    if(indexL >= 0) {
        memVRTable[indexL].inMemory = false;
    }
    if(size == OpndSize_64 && indexH >= 0) {
        memVRTable[indexH].inMemory = false;
    }
}
//! set nullCheckDone of memVRTable to false

//!
void clearVRNullCheck(int regNum, OpndSize size) {
    int indexL = searchMemTable(regNum);
    int indexH = -1;
    if(size == OpndSize_64) indexH = searchMemTable(regNum+1);
    if(indexL >= 0) {
        memVRTable[indexL].nullCheckDone = false;
    }
    if(size == OpndSize_64 && indexH >= 0) {
        memVRTable[indexH].nullCheckDone = false;
    }
}

//! Extend Virtual Register life

//! Requests that the life of a specific virtual register be extended. This ensures
//! that its mapping to a physical register won't be canceled while the extension
//! request is valid. NOTE: This does not support 64-bit values (when two adjacent
//! VRs are used)
//! @see cancelVRFreeDelayRequest
//! @see getVRFreeDelayRequested
//! @see VRFreeDelayFlags
//! @param regNum is the VR number
//! @param reason explains why freeing must be delayed. A single or combination
//! of VRFreeDelayFlags should be used.
//! @return negative value if request failed
int requestVRFreeDelay(int regNum, u4 reason) {
    //TODO Add 64-bit operand support when needed
    int indexL = searchMemTable(regNum);
    if(indexL >= 0) {
        memVRTable[indexL].delayFreeFlags |= reason;
    } else {
        ALOGE("requestVRFreeDelay: VR %d not in memVRTable", regNum);
    }
    return indexL;
}

//! Cancel request for virtual register life extension

//! Cancels any outstanding requests to extended liveness of VR. Additionally,
//! this ensures that if the VR is no longer life after this point, it will
//! no longer be associated with a physical register which can then be reused.
//! NOTE: This does not support 64-bit values (when two adjacent VRs are used)
//! @see requestVRFreeDelay
//! @see getVRFreeDelayRequested
//! @see VRFreeDelayFlags
//! @param regNum is the VR number
//! @param reason explains what freeing delay request should be canceled. A single
//! or combination of VRFreeDelayFlags should be used.
void cancelVRFreeDelayRequest(int regNum, u4 reason) {
    //TODO Add 64-bit operand support when needed
    bool needCallToFreeReg = false;
    int indexL = searchMemTable(regNum);
    if(indexL >= 0) {
        if((memVRTable[indexL].delayFreeFlags & reason) != VRDELAY_NONE) { // don't cancel delay if it wasn't requested
            memVRTable[indexL].delayFreeFlags ^= reason; // only cancel this particular reason, not all others
            if(memVRTable[indexL].delayFreeFlags == VRDELAY_NONE)
                needCallToFreeReg = true; // freeReg might want to free this VR now if there is no longer a valid delay
        }
    }
    if(needCallToFreeReg)
        freeReg(true);
}

//! Gets status of virtual register free delay request

//! Finds out if there was a delay request for freeing this VR.
//! NOTE: This does not support 64-bit values (when two adjacent VRs are used)
//! @see requestVRFreeDelay
//! @see cancelVRFreeDelayRequest
//! @param regNum is the VR number
//! @return true if VR has an active delay request
bool getVRFreeDelayRequested(int regNum) {
    //TODO Add 64-bit operand support when needed
    int indexL = searchMemTable(regNum);
    if(indexL >= 0) {
        if(memVRTable[indexL].delayFreeFlags != VRDELAY_NONE)
            return true;
        return false;
    }
    return false;
}

//! find the basic block that a bytecode is in

//!
BasicBlock_O1* findForOffset(int offset) {
    int k;
    for(k = 0; k < num_bbs_for_method; k++) {
        if(method_bbs_sorted[k]->pc_start <= offset && method_bbs_sorted[k]->pc_end > offset)
            return method_bbs_sorted[k];
    }
    return NULL;
}
void dump_CFG(Method* method);

int current_bc_size = -1;

//! check whether a virtual register is used in a basic block

//!
bool isUsedInBB(int regNum, int type, BasicBlock_O1* bb) {
    int k;
    for(k = 0; k < bb->num_regs; k++) {
        if(bb->infoBasicBlock[k].physicalType == (type&MASK_FOR_TYPE) && bb->infoBasicBlock[k].regNum == regNum)
            return true;
    }
    return false;
}
//! return the index to infoBasicBlock for a given virtual register

//! return -1 if not found
int searchVirtualInfoOfBB(LowOpndRegType type, int regNum, BasicBlock_O1* bb) {
    int k;
    for(k = 0; k < bb->num_regs; k++) {
        if(bb->infoBasicBlock[k].physicalType == type && bb->infoBasicBlock[k].regNum == regNum)
            return k;
    }
    return -1;
}
//! return the index to compileTable for a given virtual register

//! return -1 if not found
int searchCompileTable(int type, int regNum) { //returns the index
    int k;
    for(k = 0; k < num_compile_entries; k++) {
        if(compileTable[k].physicalType == type && compileTable[k].regNum == regNum)
            return k;
    }
    return -1;
}
//!check whether a physical register for a variable with typeA will work for another variable with typeB

//!Type LowOpndRegType_ss is compatible with type LowOpndRegType_xmm
bool matchType(int typeA, int typeB) {
    if((typeA & MASK_FOR_TYPE) == (typeB & MASK_FOR_TYPE)) return true;
    if((typeA & MASK_FOR_TYPE) == LowOpndRegType_ss &&
       (typeB & MASK_FOR_TYPE) == LowOpndRegType_xmm) return true;
    if((typeA & MASK_FOR_TYPE) == LowOpndRegType_xmm &&
       (typeB & MASK_FOR_TYPE) == LowOpndRegType_ss) return true;
    return false;
}
//!check whether a virtual register is used in the current bytecode

//!
bool isUsedInByteCode(int regNum, int type) {
    getVirtualRegInfo(infoByteCode);
    int k;
    for(k = 0; k < num_regs_per_bytecode; k++) {
        if(infoByteCode[k].physicalType == (type&MASK_FOR_TYPE) && infoByteCode[k].regNum == regNum)
            return true;
    }
    return false;
}
//! obsolete
bool defineFirst(int atype) {
    if(atype == REGACCESS_D || atype == REGACCESS_L || atype == REGACCESS_H || atype == REGACCESS_DU)
        return true;
    return false;
}
//!check whether a virtual register is updated in a basic block

//!
bool notUpdated(RegAccessType atype) {
    if(atype == REGACCESS_U) return true;
    return false;
}
//!check whether a virtual register has exposed usage within a given basic block

//!
bool hasExposedUsage2(BasicBlock_O1* bb, int index) {
    RegAccessType atype = bb->infoBasicBlock[index].accessType;
    if(atype == REGACCESS_D || atype == REGACCESS_L || atype == REGACCESS_H || atype == REGACCESS_DU)
        return false;
    return true;
}
//! return the spill location that is not used

//!
int getSpillIndex(bool isGLUE, OpndSize size) {
    if(isGLUE) return 0;
    int k;
    for(k = 1; k <= MAX_SPILL_JIT_IA-1; k++) {
        if(size == OpndSize_64) {
            if(k < MAX_SPILL_JIT_IA-1 && spillIndexUsed[k] == 0 && spillIndexUsed[k+1] == 0)
                return k;
        }
        else if(spillIndexUsed[k] == 0) {
            return k;
        }
    }
    ALOGE("can't find spill position in spillLogicalReg");
    return -1;
}
//!this is called before generating a native code, it sets entries in array canSpillReg to true

//!startNativeCode must be paired with endNativeCode
void startNativeCode(int vr_num, int vr_type) {
    int k;
    for(k = 0; k < PhysicalReg_Null; k++) {
        canSpillReg[k] = true;
    }
    inGetVR_num = vr_num;
    inGetVR_type = vr_type;
}
//! called right after generating a native code

//!It sets entries in array canSpillReg to true and reset inGetVR_num to -1
void endNativeCode() {
    int k;
    for(k = 0; k < PhysicalReg_Null; k++) {
        canSpillReg[k] = true;
    }
    inGetVR_num = -1;
}
//! set canSpillReg[physicalReg] to false

//!
void donotSpillReg(int physicalReg) {
    canSpillReg[physicalReg] = false;
}
//! set canSpillReg[physicalReg] to true

//!
void doSpillReg(int physicalReg) {
    canSpillReg[physicalReg] = true;
}
//! touch hardcoded register %ecx and reduce its reference count

//!
int touchEcx() {
    //registerAlloc will spill logical reg that is mapped to ecx
    //registerAlloc will reduce refCount
    registerAlloc(LowOpndRegType_gp, PhysicalReg_ECX, true, true);
    return 0;
}
//! touch hardcoded register %eax and reduce its reference count

//!
int touchEax() {
    registerAlloc(LowOpndRegType_gp, PhysicalReg_EAX, true, true);
    return 0;
}
int touchEsi() {
    registerAlloc(LowOpndRegType_gp, PhysicalReg_ESI, true, true);
    return 0;
}
int touchXmm1() {
    registerAlloc(LowOpndRegType_xmm, XMM_1, true, true);
    return 0;
}
int touchEbx() {
    registerAlloc(LowOpndRegType_gp, PhysicalReg_EBX, true, true);
    return 0;
}

//! touch hardcoded register %edx and reduce its reference count

//!
int touchEdx() {
    registerAlloc(LowOpndRegType_gp, PhysicalReg_EDX, true, true);
    return 0;
}

#ifdef HACK_FOR_DEBUG
//for debugging purpose, instructions are added at a certain place
bool hacked = false;
void hackBug() {
  if(!hacked && iget_obj_inst == 13) {
#if 0
    move_reg_to_reg_noalloc(OpndSize_32, PhysicalReg_EBX, true, PhysicalReg_ECX, true);
    //move from ebx to ecx & update compileTable for v3
    int tIndex = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, 3);
    if(tIndex < 0) ALOGE("hack can't find VR3");
    compileTable[tIndex].physicalReg = PhysicalReg_ECX;
#else
    move_reg_to_mem_noalloc(OpndSize_32, PhysicalReg_EBX, true, 12, PhysicalReg_FP, true);
#endif
  }
}
void hackBug2() {
  if(!hacked && iget_obj_inst == 13) {
    dump_imm_mem_noalloc(Mnemonic_MOV, OpndSize_32, 0, 12, PhysicalReg_FP, true);
    hacked = true;
  }
}
#endif

//! this function is called before calling a helper function or a vm function
int beforeCall(const char* target) { //spill all live registers
    if(currentBB == NULL) return -1;

    /* special case for ncgGetEIP: this function only updates %edx */
    if(!strcmp(target, "ncgGetEIP")) {
        touchEdx();
        return -1;
    }

    /* these functions use %eax for the return value */
    if((!strcmp(target, "dvmInstanceofNonTrivial")) ||
       (!strcmp(target, "dvmUnlockObject")) ||
       (!strcmp(target, "dvmAllocObject")) ||
       (!strcmp(target, "dvmAllocArrayByClass")) ||
       (!strcmp(target, "dvmAllocPrimitiveArray")) ||
       (!strcmp(target, "dvmInterpHandleFillArrayData")) ||
       (!strcmp(target, "dvmFindInterfaceMethodInCache")) ||
       (!strcmp(target, "dvmNcgHandlePackedSwitch")) ||
       (!strcmp(target, "dvmNcgHandleSparseSwitch")) ||
       (!strcmp(target, "dvmCanPutArrayElement")) ||
       (!strcmp(target, "moddi3")) || (!strcmp(target, "divdi3")) ||
       (!strcmp(target, "execute_inline"))
       || (!strcmp(target, "dvmJitToPatchPredictedChain"))
       || (!strcmp(target, "dvmJitHandlePackedSwitch"))
       || (!strcmp(target, "dvmJitHandleSparseSwitch"))
       ) {
        touchEax();
    }

    //these two functions also use %edx for the return value
    if((!strcmp(target, "moddi3")) || (!strcmp(target, "divdi3"))) {
        touchEdx();
    }
    if((!strcmp(target, ".new_instance_helper"))) {
        touchEsi(); touchEax();
    }
#if defined(ENABLE_TRACING)
    if((!strcmp(target, "common_periodicChecks4"))) {
        touchEdx();
    }
#endif
    if((!strcmp(target, ".const_string_helper"))) {
        touchEcx(); touchEax();
    }
    if((!strcmp(target, ".check_cast_helper"))) {
        touchEbx(); touchEsi();
    }
    if((!strcmp(target, ".instance_of_helper"))) {
        touchEbx(); touchEsi(); touchEcx();
    }
    if((!strcmp(target, ".monitor_enter_helper"))) {
        touchEbx();
    }
    if((!strcmp(target, ".monitor_exit_helper"))) {
        touchEbx();
    }
    if((!strcmp(target, ".aget_wide_helper"))) {
        touchEbx(); touchEcx(); touchXmm1();
    }
    if((!strcmp(target, ".aget_helper")) || (!strcmp(target, ".aget_char_helper")) ||
       (!strcmp(target, ".aget_short_helper")) || (!strcmp(target, ".aget_bool_helper")) ||
       (!strcmp(target, ".aget_byte_helper"))) {
        touchEbx(); touchEcx(); touchEdx();
    }
    if((!strcmp(target, ".aput_helper")) || (!strcmp(target, ".aput_char_helper")) ||
       (!strcmp(target, ".aput_short_helper")) || (!strcmp(target, ".aput_bool_helper")) ||
       (!strcmp(target, ".aput_byte_helper")) || (!strcmp(target, ".aput_wide_helper"))) {
        touchEbx(); touchEcx(); touchEdx();
    }
    if((!strcmp(target, ".sput_helper")) || (!strcmp(target, ".sput_wide_helper"))) {
        touchEdx(); touchEax();
    }
    if((!strcmp(target, ".sget_helper"))) {
        touchEdx(); touchEcx();
    }
    if((!strcmp(target, ".sget_wide_helper"))) {
        touchEdx(); touchXmm1();
    }
    if((!strcmp(target, ".aput_obj_helper"))) {
        touchEdx(); touchEcx(); touchEax();
    }
    if((!strcmp(target, ".iput_helper")) || (!strcmp(target, ".iput_wide_helper"))) {
        touchEbx(); touchEcx(); touchEsi();
    }
    if((!strcmp(target, ".iget_helper"))) {
        touchEbx(); touchEcx(); touchEdx();
    }
    if((!strcmp(target, ".iget_wide_helper"))) {
        touchEbx(); touchEcx(); touchXmm1();
    }
    if((!strcmp(target, ".new_array_helper"))) {
        touchEbx(); touchEdx(); touchEax();
    }
    if((!strcmp(target, ".invoke_virtual_helper"))) {
        touchEbx(); touchEcx();
    }
    if((!strcmp(target, ".invoke_direct_helper"))) {
        touchEsi(); touchEcx();
    }
    if((!strcmp(target, ".invoke_super_helper"))) {
        touchEbx(); touchEcx();
    }
    if((!strcmp(target, ".invoke_interface_helper"))) {
        touchEbx(); touchEcx();
    }
    if((!strcmp(target, ".invokeMethodNoRange_5_helper")) ||
       (!strcmp(target, ".invokeMethodNoRange_4_helper"))) {
        touchEbx(); touchEsi(); touchEax(); touchEdx();
    }
    if((!strcmp(target, ".invokeMethodNoRange_3_helper"))) {
        touchEbx(); touchEsi(); touchEax();
    }
    if((!strcmp(target, ".invokeMethodNoRange_2_helper"))) {
        touchEbx(); touchEsi();
    }
    if((!strcmp(target, ".invokeMethodNoRange_1_helper"))) {
        touchEbx();
    }
    if((!strcmp(target, ".invokeMethodRange_helper"))) {
        touchEdx(); touchEsi();
    }
#ifdef DEBUG_REGALLOC
    ALOGI("enter beforeCall");
#endif
    if(!strncmp(target, ".invokeArgsDone", 15)) resetGlue(PhysicalReg_GLUE_DVMDEX);

    freeReg(true); //to avoid spilling dead logical registers
    int k;
    for(k = 0; k < num_compile_entries; k++) {
        /* before throwing an exception, if GLUE is spilled, load to %ebp
           this should happen at last */
        if(k == indexForGlue) continue;
        if(compileTable[k].physicalReg != PhysicalReg_Null &&
           (compileTable[k].physicalType & LowOpndRegType_hard) == 0) {
            /* handles non hardcoded variables that are in physical registers */
            if(!strcmp(target, "exception")) {
                /* before throwing an exception
                   update contents of all VRs in Java stack */
                if(!isVirtualReg(compileTable[k].physicalType)) continue;
                /* to have correct GC, we should update contents for L VRs as well */
                //if(compileTable[k].gType == GLOBALTYPE_L) continue;
            }
            if((!strcmp(target, ".const_string_resolve")) ||
               (!strcmp(target, ".static_field_resolve")) ||
               (!strcmp(target, ".inst_field_resolve")) ||
               (!strcmp(target, ".class_resolve")) ||
               (!strcmp(target, ".direct_method_resolve")) ||
               (!strcmp(target, ".virtual_method_resolve")) ||
               (!strcmp(target, ".static_method_resolve"))) {
               /* physical register %ebx will keep its content
                  but to have correct GC, we should dump content of a VR
                     that is mapped to %ebx */
                if(compileTable[k].physicalReg == PhysicalReg_EBX &&
                   (!isVirtualReg(compileTable[k].physicalType)))
                    continue;
            }
            if((!strncmp(target, "dvm", 3)) || (!strcmp(target, "moddi3")) ||
               (!strcmp(target, "divdi3")) ||
               (!strcmp(target, "fmod")) || (!strcmp(target, "fmodf"))) {
                /* callee-saved registers (%ebx, %esi, %ebp, %edi) will keep the content
                   but to have correct GC, we should dump content of a VR
                      that is mapped to a callee-saved register */
                if((compileTable[k].physicalReg == PhysicalReg_EBX ||
                    compileTable[k].physicalReg == PhysicalReg_ESI) &&
                   (!isVirtualReg(compileTable[k].physicalType)))
                    continue;
            }
#ifdef DEBUG_REGALLOC
            ALOGI("SPILL logical register %d %d in beforeCall",
                  compileTable[k].regNum, compileTable[k].physicalType);
#endif
            spillLogicalReg(k, true);
        }
    }
    if(indexForGlue >= 0 && !strcmp(target, "exception") &&
       compileTable[indexForGlue].physicalReg == PhysicalReg_Null) {
        unspillLogicalReg(indexForGlue, PhysicalReg_EBP); //load %ebp
    }
#ifdef DEBUG_REGALLOC
    ALOGI("exit beforeCall");
#endif
    return 0;
}
int getFreeReg(int type, int reg, int indexToCompileTable);
//! after calling a helper function or a VM function

//!
int afterCall(const char* target) { //un-spill
    if(currentBB == NULL) return -1;
    if(!strcmp(target, "ncgGetEIP")) return -1;

    return 0;
}
//! check whether a temporary is 8-bit

//!
bool isTemp8Bit(int type, int reg) {
    if(currentBB == NULL) return false;
    if(!isTemporary(type, reg)) return false;
    int k;
    for(k = 0; k < num_temp_regs_per_bytecode; k++) {
        if(infoByteCodeTemp[k].physicalType == type &&
           infoByteCodeTemp[k].regNum == reg) {
            return infoByteCodeTemp[k].is8Bit;
        }
    }
    ALOGE("isTemp8Bit %d %d", type, reg);
    return false;
}

/* functions to access live ranges of a VR
   Live range info is stored in memVRTable[].ranges, which is a linked list
*/
//! check whether a VR is live at the current bytecode

//!
bool isVRLive(int vA) {
    int index = searchMemTable(vA);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", vA);
        return false;
    }
    LiveRange* ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(offsetPC >= ptr->start && offsetPC <= ptr->end) return true;
        ptr = ptr->next;
    }
    return false;
}

//! check whether the current bytecode is the last access to a VR within a live range

//!for 64-bit VR, return true only when true for both low half and high half
bool isLastByteCodeOfLiveRange(int compileIndex) {
    int k = compileIndex;
    OpndSize tSize = getRegSize(compileTable[k].physicalType);
    int index;
    LiveRange* ptr = NULL;
    if(tSize == OpndSize_32) {
        /* check live ranges for the VR */
        index = searchMemTable(compileTable[k].regNum);
        if(index < 0) {
            ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
            return false;
        }
        ptr = memVRTable[index].ranges;
        while(ptr != NULL) {
            if(offsetPC == ptr->end) return true;
            ptr = ptr->next;
        }
        return false;
    }
    /* size of the VR is 64 */
    /* check live ranges of the low half */
    index = searchMemTable(compileTable[k].regNum);
    bool tmpB = false;
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
        return false;
    }
    ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(offsetPC == ptr->end) {
            tmpB = true;
            break;
        }
        ptr = ptr->next;
    }
    if(!tmpB) return false;
    /* check live ranges of the high half */
    index = searchMemTable(compileTable[k].regNum+1);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
        return false;
    }
    ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(offsetPC == ptr->end) {
            return true;
        }
        ptr = ptr->next;
    }
    return false;
}

//! check whether the current bytecode is in a live range that extends to end of a basic block

//!for 64 bit, return true if true for both low half and high half
bool reachEndOfBB(int compileIndex) {
    int k = compileIndex;
    OpndSize tSize = getRegSize(compileTable[k].physicalType);
    int index;
    bool retCode = false;
    /* check live ranges of the low half */
    index = searchMemTable(compileTable[k].regNum);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
        return false;
    }
    LiveRange* ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(offsetPC >= ptr->start &&
           offsetPC <= ptr->end) {
            if(ptr->end == currentBB->pc_end) {
                retCode = true;
            }
            break;
        }
        ptr = ptr->next;
    }
    if(!retCode) return false;
    if(tSize == OpndSize_32) return true;
    /* check live ranges of the high half */
    index = searchMemTable(compileTable[k].regNum+1);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
        return false;
    }
    ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(offsetPC >= ptr->start &&
           offsetPC <= ptr->end) {
            if(ptr->end == currentBB->pc_end) return true;
            return false;
        }
        ptr = ptr->next;
    }
#ifdef PRINT_WARNING
    ALOGW("offsetPC %d not in live range of VR %d", offsetPC, compileTable[k].regNum+1);
#endif
    return false;
}

//!check whether the current bytecode is the next to last access to a VR within a live range

//!for 64 bit, return true if true for both low half and high half
bool isNextToLastAccess(int compileIndex) {
    int k = compileIndex;
    OpndSize tSize = getRegSize(compileTable[k].physicalType);
    int index;
    /* check live ranges for the low half */
    bool retCode = false;
    index = searchMemTable(compileTable[k].regNum);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
        return false;
    }
    LiveRange* ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        int num_access = ptr->num_access;

        if(num_access < 2) {
           ptr = ptr->next;
           continue;
        }

        if(offsetPC == ptr->accessPC[num_access-2]) {
           retCode = true;
           break;
        }
        ptr = ptr->next;
    }
    if(!retCode) return false;
    if(tSize == OpndSize_32) return true;
    /* check live ranges for the high half */
    index = searchMemTable(compileTable[k].regNum+1);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
        return false;
    }
    ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        int num_access = ptr->num_access;

        if(num_access < 2) {
           ptr = ptr->next;
           continue;
        }

        if(offsetPC == ptr->accessPC[num_access-2]) return true;
        ptr = ptr->next;
    }
    return false;
}

/** return the start of the next live range
    if there does not exist a next live range, return pc_end of the basic block
    for 64 bits, return the larger one for low half and high half
    Assume live ranges are sorted in order
*/
int getNextLiveRange(int compileIndex) {
    int k = compileIndex;
    OpndSize tSize = getRegSize(compileTable[k].physicalType);
    /* check live ranges of the low half */
    int index;
    index = searchMemTable(compileTable[k].regNum);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
        return offsetPC;
    }
    bool found = false;
    int nextUse = offsetPC;
    LiveRange* ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(ptr->start > offsetPC) {
            nextUse = ptr->start;
            found = true;
            break;
        }
        ptr = ptr->next;
    }
    if(!found) return currentBB->pc_end;
    if(tSize == OpndSize_32) return nextUse;

    /* check live ranges of the high half */
    found = false;
    index = searchMemTable(compileTable[k].regNum+1);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
        return offsetPC;
    }
    int nextUse2 = offsetPC;
    ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(ptr->start > offsetPC) {
            nextUse2 = ptr->start;
            found = true;
            break;
        }
        ptr = ptr->next;
    }
    if(!found) return currentBB->pc_end;
    /* return the larger one */
    return (nextUse2 > nextUse ? nextUse2 : nextUse);
}

/** return the next access to a variable
    If variable is 64-bit, get the next access to the lower half and the high half
        return the eariler one
*/
int getNextAccess(int compileIndex) {
    int k = compileIndex;
    OpndSize tSize = getRegSize(compileTable[k].physicalType);
    int index, k3;
    /* check live ranges of the low half */
    index = searchMemTable(compileTable[k].regNum);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
        return offsetPC;
    }
    bool found = false;
    int nextUse = offsetPC;
    LiveRange* ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(offsetPC >= ptr->start &&
           offsetPC <= ptr->end) {
            /* offsetPC belongs to this live range */
            for(k3 = 0; k3 < ptr->num_access; k3++) {
                if(ptr->accessPC[k3] > offsetPC) {
                    nextUse = ptr->accessPC[k3];
                    break;
                }
            }
            found = true;
            break;
        }
        ptr = ptr->next;
    }
#ifdef PRINT_WARNING
    if(!found)
        ALOGW("offsetPC %d not in live range of VR %d", offsetPC, compileTable[k].regNum);
#endif
    if(tSize == OpndSize_32) return nextUse;

    /* check live ranges of the high half */
    found = false;
    index = searchMemTable(compileTable[k].regNum+1);
    if(index < 0) {
        ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
        return offsetPC;
    }
    int nextUse2 = offsetPC;
    ptr = memVRTable[index].ranges;
    while(ptr != NULL) {
        if(offsetPC >= ptr->start &&
           offsetPC <= ptr->end) {
            for(k3 = 0; k3 < ptr->num_access; k3++) {
                if(ptr->accessPC[k3] > offsetPC) {
                    nextUse2 = ptr->accessPC[k3];
                    break;
                }
            }
            found = true;
            break;
        }
        ptr = ptr->next;
    }
#ifdef PRINT_WARNING
    if(!found) ALOGW("offsetPC %d not in live range of VR %d", offsetPC, compileTable[k].regNum+1);
#endif
    /* return the earlier one */
    if(nextUse2 < nextUse) return nextUse2;
    return nextUse;
}

/** free variables that are no longer in use
    free a temporary with reference count of zero
    will dump content of a GL VR to memory if necessary
*/
int freeReg(bool spillGL) {
    if(currentBB == NULL) return 0;
    int k;
    for(k = 0; k < num_compile_entries; k++) {
        if(compileTable[k].refCount == 0 && compileTable[k].physicalReg != PhysicalReg_Null) {
            /* check entries with reference count of zero and is mapped to a physical register */
            bool typeA = !isVirtualReg(compileTable[k].physicalType);
            bool freeCrit = true, delayFreeing = false;
            bool typeC = false, typeB = false, reachEnd = false;
            if(isVirtualReg(compileTable[k].physicalType)) {
                /* VRs in the compile table */

                /* Check if delay for freeing was requested for this VR */
                delayFreeing = getVRFreeDelayRequested(compileTable[k].regNum);

                freeCrit = isLastByteCodeOfLiveRange(k); /* last bytecode of a live range */
                reachEnd = reachEndOfBB(k); /* in a live range that extends to end of a basic block */
#ifdef DEBUG_LIVE_RANGE
                ALOGI("IN freeReg: VR %d offsetPC %x freecrit %d reachEnd %d nextToLast %d", compileTable[k].regNum, offsetPC, freeCrit, reachEnd, isNextToLastAccess(k));
#endif
                /* Bug: spilling of VRs after edi(rFP) is updated in RETURN bytecode
                        will cause variables for callee to be spilled to the caller stack frame and
                                                        to overwrite varaibles for caller
                */
                /* last bytecode of a live range reaching end of BB if not counting the fake usage at end */
                bool boolB = reachEnd && isNextToLastAccess(k);
                /* Bug: when a GG VR is checked at end of a basic block,
                        freeCrit will be true and physicalReg will be set to Null
                   Fix: change free condition from freeCrit to (freeCrit && offsetPC != currentBB->pc_end)
                */
                /* conditions to free a GG VR:
                       last bytecode of a live range reaching end of BB if not counting the fake usage at end && endsWithReturn
                       or
                       last bytecode of a live range && offsetPC != currentBB->pc_end
                           -> last bytecode of a live range not reaching end
                */
                typeC = ((freeCrit && offsetPC != currentBB->pc_end) ||
                         (currentBB->endsWithReturn && boolB)) &&
                        compileTable[k].gType == GLOBALTYPE_GG &&
                        !delayFreeing;
                /* conditions to free a L|GL VR:
                       last bytecode of a live range
                       or
                       last bytecode of a live range reaching end of BB if not counting the fake usage at end
                */
                typeB = (freeCrit || boolB) &&
                        (compileTable[k].gType != GLOBALTYPE_GG) &&
                        !delayFreeing;
            }
            if(typeA || typeB || typeC) {
#ifdef DEBUG_REGALLOC
                if(typeA)
                    ALOGI("FREE TEMP %d with type %d allocated to %d",
                           compileTable[k].regNum, compileTable[k].physicalType,
                           compileTable[k].physicalReg);
                else if(typeB)
                    ALOGI("FREE VR L|GL %d with type %d allocated to %d",
                           compileTable[k].regNum, compileTable[k].physicalType,
                           compileTable[k].physicalReg);
                else if(typeC)
                    ALOGI("FREE VR GG %d with type %d allocated to %d",
                           compileTable[k].regNum, compileTable[k].physicalType,
                           compileTable[k].physicalReg);
#endif
                bool dumpGL = false;
                if(compileTable[k].gType == GLOBALTYPE_GL && !reachEnd) {
                    /* if the live range does not reach end of basic block
                       and there exists a try block from offsetPC to the next live range
                           dump VR to interpreted stack */
                    int tmpPC = getNextLiveRange(k);
                    if(existATryBlock(currentMethod, offsetPC, tmpPC)) dumpGL = true;
                }
                /* if the live range reach end of basic block, dump VR to interpreted stack */
                if(compileTable[k].gType == GLOBALTYPE_GL && reachEnd) dumpGL = true;
                if(dumpGL) {
                    if(spillGL) {
#ifdef DEBUG_REGALLOC
                        ALOGI("SPILL VR GL %d %d", compileTable[k].regNum, compileTable[k].physicalType);
#endif
                        spillLogicalReg(k, true); //will dump VR to memory & update physicalReg
                    }
                }
                else
                     compileTable[k].physicalReg = PhysicalReg_Null;
            }
            if(typeA) {
                if(compileTable[k].spill_loc_index >= 0) {
                    /* update spill info for temporaries */
                    spillIndexUsed[compileTable[k].spill_loc_index >> 2] = 0;
                    compileTable[k].spill_loc_index = -1;
                    ALOGE("free a temporary register with TRSTATE_SPILLED");
                }
            }
        }
    }
    syncAllRegs(); //sync up allRegs (isUsed & freeTimeStamp) with compileTable
    return 0;
}

//! reduce the reference count by 1

//! input: index to compileTable
void decreaseRefCount(int index) {
#ifdef DEBUG_REFCOUNT
    ALOGI("REFCOUNT: %d in decreaseRefCount %d %d", compileTable[index].refCount,
            compileTable[index].regNum, compileTable[index].physicalType);
#endif
    compileTable[index].refCount--;
    if(compileTable[index].refCount < 0) {
        ALOGE("refCount is negative for REG %d %d", compileTable[index].regNum, compileTable[index].physicalType);
        dvmAbort();
    }
}
//! reduce the reference count of a VR by 1

//! input: reg & type
int updateRefCount(int reg, LowOpndRegType type) {
    if(currentBB == NULL) return 0;
    int index = searchCompileTable(LowOpndRegType_virtual | type, reg);
    if(index < 0) {
        ALOGE("virtual reg %d type %d not found in updateRefCount", reg, type);
        return -1;
    }
    decreaseRefCount(index);
    return 0;
}
//! reduce the reference count of a variable by 1

//! The variable is named with lowering module's naming mechanism
int updateRefCount2(int reg, int type, bool isPhysical) {
    if(currentBB == NULL) return 0;
    int newType = convertType(type, reg, isPhysical);
    if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
    int index = searchCompileTable(newType, reg);
    if(index < 0) {
        ALOGE("reg %d type %d not found in updateRefCount", reg, newType);
        return -1;
    }
    decreaseRefCount(index);
    return 0;
}
//! check whether a glue variable is in physical register or spilled

//!
bool isGlueHandled(int glue_reg) {
    if(currentBB == NULL) return false;
    int index = searchCompileTable(LowOpndRegType_gp, glue_reg);
    if(index < 0) {
        ALOGE("glue reg %d not found in isGlueHandled", glue_reg);
        return -1;
    }
    if(compileTable[index].spill_loc_index >= 0 ||
       compileTable[index].physicalReg != PhysicalReg_Null) {
#ifdef DEBUG_GLUE
        ALOGI("GLUE isGlueHandled for %d returns true", glue_reg);
#endif
        return true;
    }
#ifdef DEBUG_GLUE
    ALOGI("GLUE isGlueHandled for %d returns false", glue_reg);
#endif
    return false;
}
//! reset the state of a glue variable to not existant (not in physical register nor spilled)

//!
void resetGlue(int glue_reg) {
    if(currentBB == NULL) return;
    int index = searchCompileTable(LowOpndRegType_gp, glue_reg);
    if(index < 0) {
        ALOGE("glue reg %d not found in resetGlue", glue_reg);
        return;
    }
#ifdef DEBUG_GLUE
    ALOGI("GLUE reset for %d", glue_reg);
#endif
    compileTable[index].physicalReg = PhysicalReg_Null;
    if(compileTable[index].spill_loc_index >= 0)
        spillIndexUsed[compileTable[index].spill_loc_index >> 2] = 0;
    compileTable[index].spill_loc_index = -1;
}
//! set a glue variable in a physical register allocated for a variable

//! Variable is using lowering module's naming convention
void updateGlue(int reg, bool isPhysical, int glue_reg) {
    if(currentBB == NULL) return;
    int index = searchCompileTable(LowOpndRegType_gp, glue_reg);
    if(index < 0) {
        ALOGE("glue reg %d not found in updateGlue", glue_reg);
        return;
    }
    /* find the compileTable entry for variable <reg, isPhysical> */
    int newType = convertType(LowOpndRegType_gp, reg, isPhysical);
    if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
    int index2 = searchCompileTable(newType, reg);
    if(index2 < 0 || compileTable[index2].physicalReg == PhysicalReg_Null) {
        ALOGE("updateGlue reg %d type %d", reg, newType);
        return;
    }
#ifdef DEBUG_GLUE
    ALOGI("physical register for GLUE %d set to %d", glue_reg, compileTable[index2].physicalReg);
#endif
    compileTable[index].physicalReg = compileTable[index2].physicalReg;
    compileTable[index].spill_loc_index = -1;
}

//! check whether a virtual register is in a physical register

//! If updateRefCount is 0, do not update reference count;
//!If updateRefCount is 1, update reference count only when VR is in a physical register
//!If updateRefCount is 2, update reference count
int checkVirtualReg(int reg, LowOpndRegType type, int updateRefCount) {
    if(currentBB == NULL) return PhysicalReg_Null;
    int index = searchCompileTable(LowOpndRegType_virtual | type, reg);
    if(index < 0) {
        ALOGE("virtual reg %d type %d not found in checkVirtualReg", reg, type);
        return PhysicalReg_Null;
    }
    //reduce reference count
    if(compileTable[index].physicalReg != PhysicalReg_Null) {
        if(updateRefCount != 0) decreaseRefCount(index);
        return compileTable[index].physicalReg;
    }
    if(updateRefCount == 2) decreaseRefCount(index);
    return PhysicalReg_Null;
}
//!check whether a temporary can share the same physical register with a VR

//!This is called in get_virtual_reg
//!If this function returns false, new register will be allocated for this temporary
bool checkTempReg2(int reg, int type, bool isPhysical, int physicalRegForVR) {
    if(currentBB == NULL) return false;
    if(isPhysical) return false;

    int newType = convertType(type, reg, isPhysical);
    if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
    int k;
    for(k = 0; k < num_temp_regs_per_bytecode; k++) {
        if(infoByteCodeTemp[k].physicalType == newType &&
           infoByteCodeTemp[k].regNum == reg) {
#ifdef DEBUG_MOVE_OPT
            ALOGI("MOVE_OPT checkTempRegs for %d %d returns %d %d",
                   reg, newType, infoByteCodeTemp[k].shareWithVR, infoByteCodeTemp[k].is8Bit);
#endif
            if(!infoByteCodeTemp[k].is8Bit) return infoByteCodeTemp[k].shareWithVR;
            //is8Bit true for gp type only
            if(!infoByteCodeTemp[k].shareWithVR) return false;
            //both true
            if(physicalRegForVR >= PhysicalReg_EAX && physicalRegForVR <= PhysicalReg_EDX) return true;
#ifdef DEBUG_MOVE_OPT
            ALOGI("MOVE_OPT registerAllocMove not used for 8-bit register");
#endif
            return false;
        }
    }
    ALOGE("checkTempReg2 %d %d", reg, newType);
    return false;
}
//!check whether a temporary can share the same physical register with a VR

//!This is called in set_virtual_reg
int checkTempReg(int reg, int type, bool isPhysical, int vrNum) {
    if(currentBB == NULL) return PhysicalReg_Null;

    int newType = convertType(type, reg, isPhysical);
    if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
    int index = searchCompileTable(newType, reg);
    if(index < 0) {
        ALOGE("temp reg %d type %d not found in checkTempReg", reg, newType);
        return PhysicalReg_Null;
    }

    //a temporary register can share the same physical reg with a VR if registerAllocMove is called
    //this will cause problem with move bytecode
    //get_VR(v1, t1) t1 and v1 point to the same physical reg
    //set_VR(t1, v2) t1 and v2 point to the same physical reg
    //this will cause v1 and v2 point to the same physical reg
    //FIX: if this temp reg shares a physical reg with another reg
    if(compileTable[index].physicalReg != PhysicalReg_Null) {
        int k;
        for(k = 0; k < num_compile_entries; k++) {
            if(k == index) continue;
            if(compileTable[k].physicalReg == compileTable[index].physicalReg) {
                return PhysicalReg_Null; //will allocate a register for VR
            }
        }
        decreaseRefCount(index);
        return compileTable[index].physicalReg;
    }
    if(compileTable[index].spill_loc_index >= 0) {
        //registerAlloc will call unspillLogicalReg (load from memory)
#ifdef DEBUG_REGALLOC
        ALOGW("in checkTempReg, the temporary register %d %d was spilled", reg, type);
#endif
        int regAll = registerAlloc(type, reg, isPhysical, true/* updateRefCount */);
        return regAll;
    }
    return PhysicalReg_Null;
}
//!check whether a variable has exposed usage in a basic block

//!It calls hasExposedUsage2
bool hasExposedUsage(LowOpndRegType type, int regNum, BasicBlock_O1* bb) {
    int index = searchVirtualInfoOfBB(type, regNum, bb);
    if(index >= 0 && hasExposedUsage2(bb, index)) {
        return true;
    }
    return false;
}
//!check whether a variable has exposed usage in other basic blocks

//!
bool hasOtherExposedUsage(OpndSize size, int regNum, BasicBlock_O1* bb) {
    return true; //assume the worst case
}

//! handles constant VRs at end of a basic block

//!If a VR is constant at end of a basic block and (it has exposed usage in other basic blocks or reaches a GG VR), dump immediate to memory
void constVREndOfBB() {
    BasicBlock_O1* bb = currentBB;
    int k, k2;
    //go through GG VRs, update a bool array
    int constUsedByGG[MAX_CONST_REG];
    for(k = 0; k < num_const_vr; k++)
        constUsedByGG[k] = 0;
    for(k = 0; k < num_compile_entries; k++) {
        if(isVirtualReg(compileTable[k].physicalType) && compileTable[k].gType == GLOBALTYPE_GG) {
            OpndSize size = getRegSize(compileTable[k].physicalType);
            int regNum = compileTable[k].regNum;
            int indexL = -1;
            int indexH = -1;
            for(k2 = 0; k2 < num_const_vr; k2++) {
                if(constVRTable[k2].regNum == regNum) {
                    indexL = k2;
                    continue;
                }
                if(constVRTable[k2].regNum == regNum + 1 && size == OpndSize_64) {
                    indexH = k2;
                    continue;
                }
            }
            if(indexL >= 0) constUsedByGG[indexL] = 1;
            if(indexH >= 0) constUsedByGG[indexH] = 1;
        } //GG VR
    }
    for(k = 0; k < num_const_vr; k++) {
        if(!constVRTable[k].isConst) continue;
        bool hasExp = false;
        if(constUsedByGG[k] == 0)
            hasExp = hasOtherExposedUsage(OpndSize_32, constVRTable[k].regNum, bb);
        if(constUsedByGG[k] != 0 || hasExp) {
            dumpImmToMem(constVRTable[k].regNum, OpndSize_32, constVRTable[k].value);
            setVRToMemory(constVRTable[k].regNum, OpndSize_32);
#ifdef DEBUG_ENDOFBB
            ALOGI("ENDOFBB: exposed VR %d is const %d (%x)",
                  constVRTable[k].regNum, constVRTable[k].value, constVRTable[k].value);
#endif
        } else {
#ifdef DEBUG_ENDOFBB
            ALOGI("ENDOFBB: unexposed VR %d is const %d (%x)",
                  constVRTable[k].regNum, constVRTable[k].value, constVRTable[k].value);
#endif
        }
    }
}

//!handles GG VRs at end of a basic block

//!make sure all GG VRs are in pre-defined physical registers
void globalVREndOfBB(const Method* method) {
    //fix: freeReg first to write LL VR back to memory to avoid it gets overwritten by GG VRs
    freeReg(true);
    int k;
    //spill GG VR first if it is not mapped to the specific reg
    //release GLUE regs
    for(k = 0; k < num_compile_entries; k++) {
        if(compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX &&
           compileTable[k].regNum != PhysicalReg_GLUE) {
            compileTable[k].physicalReg = PhysicalReg_Null;
            compileTable[k].spill_loc_index = -1;
        }
        //if part of a GG VR is const, the physical reg is set to null
        if(isVirtualReg(compileTable[k].physicalType) &&
           compileTable[k].gType == GLOBALTYPE_GG && compileTable[k].physicalReg != PhysicalReg_Null &&
           compileTable[k].physicalReg != compileTable[k].physicalReg_prev) {
#ifdef DEBUG_ENDOFBB
            ALOGW("end of BB GG VR is not mapped to the specific reg: %d %d %d",
                  compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].physicalReg);
            ALOGW("ENDOFBB SPILL VR %d %d", compileTable[k].regNum, compileTable[k].physicalType);
#endif
            spillLogicalReg(k, true); //the next section will load VR from memory to the specific reg
        }
    }
    syncAllRegs();
    for(k = 0; k < num_compile_entries; k++) {
        if(isVirtualReg(compileTable[k].physicalType)) {
            if(compileTable[k].gType == GLOBALTYPE_GG &&
               compileTable[k].physicalReg == PhysicalReg_Null && (!currentBB->endsWithReturn)) {
#ifdef DEBUG_ENDOFBB
                ALOGI("ENDOFBB GET GG VR %d %d to physical register %d", compileTable[k].regNum,
                      compileTable[k].physicalType, compileTable[k].physicalReg_prev);
#endif
                compileTable[k].physicalReg = compileTable[k].physicalReg_prev;
                if(allRegs[compileTable[k].physicalReg_prev].isUsed) {
                    ALOGE("physical register for GG VR is still used");
                }
                get_virtual_reg_noalloc(compileTable[k].regNum,
                                        getRegSize(compileTable[k].physicalType),
                                        compileTable[k].physicalReg_prev,
                                        true);
            }
        }//not const
    }
    if(indexForGlue >= 0 &&
        compileTable[indexForGlue].physicalReg == PhysicalReg_Null) {
        unspillLogicalReg(indexForGlue, PhysicalReg_EBP); //load %ebp
    }
}

//! get ready for the next version of a hard-coded register

//!set its physicalReg to Null and update its reference count
int nextVersionOfHardReg(PhysicalReg pReg, int refCount) {
    int indexT = searchCompileTable(LowOpndRegType_gp | LowOpndRegType_hard, pReg);
    if(indexT < 0)
        return -1;
    compileTable[indexT].physicalReg = PhysicalReg_Null;
#ifdef DEBUG_REFCOUNT
    ALOGI("REFCOUNT: to %d in nextVersionOfHardReg %d", refCount, pReg);
#endif
    compileTable[indexT].refCount = refCount;
    return 0;
}

/** update compileTable with bb->infoBasicBlock[k]
*/
void insertFromVirtualInfo(BasicBlock_O1* bb, int k) {
    int index = searchCompileTable(LowOpndRegType_virtual | bb->infoBasicBlock[k].physicalType, bb->infoBasicBlock[k].regNum);
    if(index < 0) {
        /* the virtual register is not in compileTable, insert it */
        index = num_compile_entries;
        compileTable[num_compile_entries].physicalType = (LowOpndRegType_virtual | bb->infoBasicBlock[k].physicalType);
        compileTable[num_compile_entries].regNum = bb->infoBasicBlock[k].regNum;
        compileTable[num_compile_entries].physicalReg = PhysicalReg_Null;
        compileTable[num_compile_entries].bb = bb;
        compileTable[num_compile_entries].indexToInfoBB = k;
        compileTable[num_compile_entries].spill_loc_index = -1;
        compileTable[num_compile_entries].gType = bb->infoBasicBlock[k].gType;
        num_compile_entries++;
        if(num_compile_entries >= COMPILE_TABLE_SIZE) {
            ALOGE("compileTable overflow");
            dvmAbort();
        }
    }
    /* re-set reference count of all VRs */
    compileTable[index].refCount = bb->infoBasicBlock[k].refCount;
    compileTable[index].accessType = bb->infoBasicBlock[k].accessType;
    if(compileTable[index].gType == GLOBALTYPE_GG)
        compileTable[index].physicalReg_prev = bb->infoBasicBlock[k].physicalReg_GG;
}

/** update compileTable with infoByteCodeTemp[k]
*/
void insertFromTempInfo(int k) {
    int index = searchCompileTable(infoByteCodeTemp[k].physicalType, infoByteCodeTemp[k].regNum);
    if(index < 0) {
        /* the temporary is not in compileTable, insert it */
        index = num_compile_entries;
        compileTable[num_compile_entries].physicalType = infoByteCodeTemp[k].physicalType;
        compileTable[num_compile_entries].regNum = infoByteCodeTemp[k].regNum;
        num_compile_entries++;
        if(num_compile_entries >= COMPILE_TABLE_SIZE) {
            ALOGE("compileTable overflow");
            dvmAbort();
        }
    }
    compileTable[index].physicalReg = PhysicalReg_Null;
    compileTable[index].refCount = infoByteCodeTemp[k].refCount;
    compileTable[index].linkageToVR = infoByteCodeTemp[k].linkageToVR;
    compileTable[index].gType = GLOBALTYPE_L;
    compileTable[index].spill_loc_index = -1;
}

/* insert a glue-related register GLUE_DVMDEX to compileTable */
void insertGlueReg() {
    compileTable[num_compile_entries].physicalType = LowOpndRegType_gp;
    compileTable[num_compile_entries].regNum = PhysicalReg_GLUE_DVMDEX;
    compileTable[num_compile_entries].refCount = 2;
    compileTable[num_compile_entries].physicalReg = PhysicalReg_Null;
    compileTable[num_compile_entries].bb = NULL;
    compileTable[num_compile_entries].spill_loc_index = -1;
    compileTable[num_compile_entries].accessType = REGACCESS_N;
    compileTable[num_compile_entries].linkageToVR = -1;
    compileTable[num_compile_entries].gType = GLOBALTYPE_L;

    num_compile_entries++;
    if(num_compile_entries >= COMPILE_TABLE_SIZE) {
        ALOGE("compileTable overflow");
        dvmAbort();
    }
}

/** print infoBasicBlock of the given basic block
*/
void dumpVirtualInfoOfBasicBlock(BasicBlock_O1* bb) {
    int jj;
    ALOGI("Virtual Info for BB%d --------", bb->bb_index);
    for(jj = 0; jj < bb->num_regs; jj++) {
        ALOGI("regNum %d physicalType %d accessType %d refCount %d def ",
               bb->infoBasicBlock[jj].regNum, bb->infoBasicBlock[jj].physicalType,
               bb->infoBasicBlock[jj].accessType, bb->infoBasicBlock[jj].refCount);
        int k;
        for(k = 0; k < bb->infoBasicBlock[jj].num_reaching_defs; k++)
            ALOGI("[%x %d %d %d] ", bb->infoBasicBlock[jj].reachingDefs[k].offsetPC,
                   bb->infoBasicBlock[jj].reachingDefs[k].regNum,
                   bb->infoBasicBlock[jj].reachingDefs[k].physicalType,
                   bb->infoBasicBlock[jj].reachingDefs[k].accessType);
        ALOGI("");
    }
}

/** print compileTable
*/
void dumpCompileTable() {
    int jj;
    ALOGI("Compile Table for method ----------");
    for(jj = 0; jj < num_compile_entries; jj++) {
        ALOGI("regNum %d physicalType %d refCount %d isConst %d physicalReg %d type %d",
               compileTable[jj].regNum, compileTable[jj].physicalType,
               compileTable[jj].refCount, compileTable[jj].isConst, compileTable[jj].physicalReg, compileTable[jj].gType);
    }
}

//!check whether a basic block is the start of an exception handler

//!
bool isFirstOfHandler(BasicBlock_O1* bb) {
    int i;
    for(i = 0; i < num_exception_handlers; i++) {
        if(bb->pc_start == exceptionHandlers[i]) return true;
    }
    return false;
}

//! create a basic block that starts at src_pc and ends at end_pc

//!
BasicBlock_O1* createBasicBlock(int src_pc, int end_pc) {
    BasicBlock_O1* bb = (BasicBlock_O1*)malloc(sizeof(BasicBlock_O1));
    if(bb == NULL) {
        ALOGE("out of memory");
        return NULL;
    }
    bb->pc_start = src_pc;
    bb->bb_index = num_bbs_for_method;
    if(bb_entry == NULL) bb_entry = bb;

    /* insert the basic block to method_bbs_sorted in ascending order of pc_start */
    int k;
    int index = -1;
    for(k = 0; k < num_bbs_for_method; k++)
        if(method_bbs_sorted[k]->pc_start > src_pc) {
            index = k;
            break;
        }
    if(index == -1)
        method_bbs_sorted[num_bbs_for_method] = bb;
    else {
        /* push the elements from index by 1 */
        for(k = num_bbs_for_method-1; k >= index; k--)
            method_bbs_sorted[k+1] = method_bbs_sorted[k];
        method_bbs_sorted[index] = bb;
    }
    num_bbs_for_method++;
    if(num_bbs_for_method >= MAX_NUM_BBS_PER_METHOD) {
        ALOGE("too many basic blocks");
        dvmAbort();
    }
    return bb;
}

/* BEGIN code to handle state transfers */
//! save the current state of register allocator to a state table

//!
void rememberState(int stateNum) {
#ifdef DEBUG_STATE
    ALOGI("STATE: remember state %d", stateNum);
#endif
    int k;
    for(k = 0; k < num_compile_entries; k++) {
        if(stateNum == 1) {
            stateTable1_1[k].physicalReg = compileTable[k].physicalReg;
            stateTable1_1[k].spill_loc_index = compileTable[k].spill_loc_index;
        }
        else if(stateNum == 2) {
            stateTable1_2[k].physicalReg = compileTable[k].physicalReg;
            stateTable1_2[k].spill_loc_index = compileTable[k].spill_loc_index;
        }
        else if(stateNum == 3) {
            stateTable1_3[k].physicalReg = compileTable[k].physicalReg;
            stateTable1_3[k].spill_loc_index = compileTable[k].spill_loc_index;
        }
        else if(stateNum == 4) {
            stateTable1_4[k].physicalReg = compileTable[k].physicalReg;
            stateTable1_4[k].spill_loc_index = compileTable[k].spill_loc_index;
        }
        else ALOGE("state table overflow");
#ifdef DEBUG_STATE
        ALOGI("logical reg %d %d mapped to physical reg %d with spill index %d refCount %d",
               compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].physicalReg,
               compileTable[k].spill_loc_index, compileTable[k].refCount);
#endif
    }
    for(k = 0; k < num_memory_vr; k++) {
        if(stateNum == 1) {
            stateTable2_1[k].regNum = memVRTable[k].regNum;
            stateTable2_1[k].inMemory = memVRTable[k].inMemory;
        }
        else if(stateNum == 2) {
            stateTable2_2[k].regNum = memVRTable[k].regNum;
            stateTable2_2[k].inMemory = memVRTable[k].inMemory;
        }
        else if(stateNum == 3) {
            stateTable2_3[k].regNum = memVRTable[k].regNum;
            stateTable2_3[k].inMemory = memVRTable[k].inMemory;
        }
        else if(stateNum == 4) {
            stateTable2_4[k].regNum = memVRTable[k].regNum;
            stateTable2_4[k].inMemory = memVRTable[k].inMemory;
        }
        else ALOGE("state table overflow");
#ifdef DEBUG_STATE
        ALOGI("virtual reg %d in memory %d", memVRTable[k].regNum, memVRTable[k].inMemory);
#endif
    }
}

//!update current state of register allocator with a state table

//!
void goToState(int stateNum) {
    int k;
#ifdef DEBUG_STATE
    ALOGI("STATE: go to state %d", stateNum);
#endif
    for(k = 0; k < num_compile_entries; k++) {
        if(stateNum == 1) {
            compileTable[k].physicalReg = stateTable1_1[k].physicalReg;
            compileTable[k].spill_loc_index = stateTable1_1[k].spill_loc_index;
        }
        else if(stateNum == 2) {
            compileTable[k].physicalReg = stateTable1_2[k].physicalReg;
            compileTable[k].spill_loc_index = stateTable1_2[k].spill_loc_index;
        }
        else if(stateNum == 3) {
            compileTable[k].physicalReg = stateTable1_3[k].physicalReg;
            compileTable[k].spill_loc_index = stateTable1_3[k].spill_loc_index;
        }
        else if(stateNum == 4) {
            compileTable[k].physicalReg = stateTable1_4[k].physicalReg;
            compileTable[k].spill_loc_index = stateTable1_4[k].spill_loc_index;
        }
        else ALOGE("state table overflow");
    }
    updateSpillIndexUsed();
    syncAllRegs(); //to sync up allRegs CAN'T call freeReg here
    //since it will change the state!!!
    for(k = 0; k < num_memory_vr; k++) {
        if(stateNum == 1) {
            memVRTable[k].regNum = stateTable2_1[k].regNum;
            memVRTable[k].inMemory = stateTable2_1[k].inMemory;
        }
        else if(stateNum == 2) {
            memVRTable[k].regNum = stateTable2_2[k].regNum;
            memVRTable[k].inMemory = stateTable2_2[k].inMemory;
        }
        else if(stateNum == 3) {
            memVRTable[k].regNum = stateTable2_3[k].regNum;
            memVRTable[k].inMemory = stateTable2_3[k].inMemory;
        }
        else if(stateNum == 4) {
            memVRTable[k].regNum = stateTable2_4[k].regNum;
            memVRTable[k].inMemory = stateTable2_4[k].inMemory;
        }
        else ALOGE("state table overflow");
    }
}
typedef struct TransferOrder {
    int targetReg;
    int targetSpill;
    int compileIndex;
} TransferOrder;
#define MAX_NUM_DEST 20
//! a source register is used as a source in transfer
//! it can have a maximum of MAX_NUM_DEST destinations
typedef struct SourceReg {
    int physicalReg;
    int num_dests; //check bound
    TransferOrder dsts[MAX_NUM_DEST];
} SourceReg;
int num_src_regs = 0; //check bound
//! physical registers that are used as a source in transfer
//! we allow a maximum of MAX_NUM_DEST sources in a transfer
SourceReg srcRegs[MAX_NUM_DEST];
//! tell us whether a source register is handled already
bool handledSrc[MAX_NUM_DEST];
//! in what order should the source registers be handled
int handledOrder[MAX_NUM_DEST];
//! insert a source register with a single destination

//!
void insertSrcReg(int srcPhysical, int targetReg, int targetSpill, int index) {
    int k = 0;
    for(k = 0; k < num_src_regs; k++) {
        if(srcRegs[k].physicalReg == srcPhysical) { //increase num_dests
            if(srcRegs[k].num_dests >= MAX_NUM_DEST) {
                ALOGE("exceed number dst regs for a source reg");
                dvmAbort();
            }
            srcRegs[k].dsts[srcRegs[k].num_dests].targetReg = targetReg;
            srcRegs[k].dsts[srcRegs[k].num_dests].targetSpill = targetSpill;
            srcRegs[k].dsts[srcRegs[k].num_dests].compileIndex = index;
            srcRegs[k].num_dests++;
            return;
        }
    }
    if(num_src_regs >= MAX_NUM_DEST) {
        ALOGE("exceed number of source regs");
        dvmAbort();
    }
    srcRegs[num_src_regs].physicalReg = srcPhysical;
    srcRegs[num_src_regs].num_dests = 1;
    srcRegs[num_src_regs].dsts[0].targetReg = targetReg;
    srcRegs[num_src_regs].dsts[0].targetSpill = targetSpill;
    srcRegs[num_src_regs].dsts[0].compileIndex = index;
    num_src_regs++;
}
//! check whether a register is a source and the source is not yet handled

//!
bool dstStillInUse(int dstReg) {
    if(dstReg == PhysicalReg_Null) return false;
    int k;
    int index = -1;
    for(k = 0; k < num_src_regs; k++) {
        if(dstReg == srcRegs[k].physicalReg) {
            index = k;
            break;
        }
    }
    if(index < 0) return false; //not in use
    if(handledSrc[index]) return false; //not in use
    return true;
}
//! reset the state of glue variables in a state table

//!
void resetStateOfGlue(int stateNum, int k) {
#ifdef DEBUG_STATE
    ALOGI("resetStateOfGlue state %d regNum %d", stateNum, compileTable[k].regNum);
#endif
    if(stateNum == 1) {
        stateTable1_1[k].physicalReg = PhysicalReg_Null;
        stateTable1_1[k].spill_loc_index = -1;
    }
    else if(stateNum == 2) {
        stateTable1_2[k].physicalReg = PhysicalReg_Null;
        stateTable1_2[k].spill_loc_index = -1;
    }
    else if(stateNum == 3) {
        stateTable1_3[k].physicalReg = PhysicalReg_Null;
        stateTable1_3[k].spill_loc_index = -1;
    }
    else if(stateNum == 4) {
        stateTable1_4[k].physicalReg = PhysicalReg_Null;
        stateTable1_4[k].spill_loc_index = -1;
    }
}
//! construct a legal order of the source registers in this transfer

//!
void constructSrcRegs(int stateNum) {
    int k;
    num_src_regs = 0;
#ifdef DEBUG_STATE
    ALOGI("IN constructSrcRegs");
#endif

    for(k = 0; k < num_compile_entries; k++) {
#ifdef DEBUG_STATE
        ALOGI("logical reg %d %d mapped to physical reg %d with spill index %d refCount %d",
               compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].physicalReg,
               compileTable[k].spill_loc_index, compileTable[k].refCount);
#endif

        int pType = compileTable[k].physicalType;
        //ignore hardcoded logical registers
        if((pType & LowOpndRegType_hard) != 0) continue;
        //ignore type _fs
        if((pType & MASK_FOR_TYPE) == LowOpndRegType_fs) continue;
        if((pType & MASK_FOR_TYPE) == LowOpndRegType_fs_s) continue;

        //GL VR refCount is zero, can't ignore
        //L VR refCount is zero, ignore
        //GG VR refCount is zero, can't ignore
        //temporary refCount is zero, ignore

        //for GLUE variables, if they do not exist, reset the entries in state table
        if(compileTable[k].physicalReg == PhysicalReg_Null &&
           compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX &&
           compileTable[k].regNum != PhysicalReg_GLUE &&
           compileTable[k].spill_loc_index < 0) {
            resetStateOfGlue(stateNum, k);
        }

        /* get the target state */
        int targetReg = PhysicalReg_Null;
        int targetSpill = -1;
        if(stateNum == 1) {
            targetReg = stateTable1_1[k].physicalReg;
            targetSpill = stateTable1_1[k].spill_loc_index;
        }
        else if(stateNum == 2) {
            targetReg = stateTable1_2[k].physicalReg;
            targetSpill = stateTable1_2[k].spill_loc_index;
        }
        else if(stateNum == 3) {
            targetReg = stateTable1_3[k].physicalReg;
            targetSpill = stateTable1_3[k].spill_loc_index;
        }
        else if(stateNum == 4) {
            targetReg = stateTable1_4[k].physicalReg;
            targetSpill = stateTable1_4[k].spill_loc_index;
        }

        /* there exists an ordering problem
           for example:
             for a VR, move from memory to a physical reg esi
             for a temporary regsiter, from esi to ecx
             if we handle VR first, content of the temporary reg. will be overwritten
           there are 4 cases:
             I: a variable is currently in memory and its target is in physical reg
             II: a variable is currently in a register and its target is in memory
             III: a variable is currently in a different register
             IV: a variable is currently in a different memory location (for non-VRs)
           for GLUE, since it can only be allocated to %ebp, we don't have case III
           For now, case IV is not handled since it didn't show
        */
        if(compileTable[k].physicalReg != targetReg &&
           isVirtualReg(compileTable[k].physicalType)) {
            /* handles VR for case I to III */

            if(compileTable[k].physicalReg == PhysicalReg_Null && targetReg != PhysicalReg_Null) {
                /* handles VR for case I:
                   insert a xfer order from PhysicalReg_Null to targetReg */
                insertSrcReg(PhysicalReg_Null, targetReg, targetSpill, k);
#ifdef DEBUG_STATE
                ALOGI("insert for VR Null %d %d %d", targetReg, targetSpill, k);
#endif
            }

            if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg != PhysicalReg_Null) {
                /* handles VR for case III
                   insert a xfer order from srcReg to targetReg */
                insertSrcReg(compileTable[k].physicalReg, targetReg, targetSpill, k);
            }

            if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg == PhysicalReg_Null) {
                /* handles VR for case II
                   insert a xfer order from srcReg to memory */
                insertSrcReg(compileTable[k].physicalReg, targetReg, targetSpill, k);
            }
        }

        if(compileTable[k].physicalReg != targetReg &&
           !isVirtualReg(compileTable[k].physicalType)) {
            /* handles non-VR for case I to III */

            if(compileTable[k].physicalReg == PhysicalReg_Null && targetReg != PhysicalReg_Null) {
                /* handles non-VR for case I */
                if(compileTable[k].spill_loc_index < 0) {
                    /* this variable is freed, no need to transfer */
#ifdef DEBUG_STATE
                    ALOGW("in transferToState spill_loc_index is negative for temporary %d", compileTable[k].regNum);
#endif
                } else {
                    /* insert a xfer order from memory to targetReg */
#ifdef DEBUG_STATE
                    ALOGI("insert Null %d %d %d", targetReg, targetSpill, k);
#endif
                    insertSrcReg(PhysicalReg_Null, targetReg, targetSpill, k);
                }
            }

            if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg != PhysicalReg_Null) {
                /* handles non-VR for case III
                   insert a xfer order from srcReg to targetReg */
                insertSrcReg(compileTable[k].physicalReg, targetReg, targetSpill, k);
            }

            if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg == PhysicalReg_Null) {
                /* handles non-VR for case II */
                if(targetSpill < 0) {
                    /* this variable is freed, no need to transfer */
#ifdef DEBUG_STATE
                    ALOGW("in transferToState spill_loc_index is negative for temporary %d", compileTable[k].regNum);
#endif
                } else {
                    /* insert a xfer order from srcReg to memory */
                    insertSrcReg(compileTable[k].physicalReg, targetReg, targetSpill, k);
                }
            }

        }
    }//for compile entries

    int k2;
#ifdef DEBUG_STATE
    for(k = 0; k < num_src_regs; k++) {
        ALOGI("SRCREG %d: ", srcRegs[k].physicalReg);
        for(k2 = 0; k2 < srcRegs[k].num_dests; k2++) {
            int index = srcRegs[k].dsts[k2].compileIndex;
            ALOGI("[%d %d %d: %d %d %d] ", srcRegs[k].dsts[k2].targetReg,
                   srcRegs[k].dsts[k2].targetSpill, srcRegs[k].dsts[k2].compileIndex,
                   compileTable[index].regNum, compileTable[index].physicalType,
                   compileTable[index].spill_loc_index);
        }
        ALOGI("");
    }
#endif

    /* construct an order: xfers from srcReg first, then xfers from memory */
    int num_handled = 0;
    int num_in_order = 0;
    for(k = 0; k < num_src_regs; k++) {
        if(srcRegs[k].physicalReg == PhysicalReg_Null) {
            handledSrc[k] = true;
            num_handled++;
        } else {
            handledSrc[k] = false;
        }
    }
    while(num_handled < num_src_regs) {
        int prev_handled = num_handled;
        for(k = 0; k < num_src_regs; k++) {
            if(handledSrc[k]) continue;
            bool canHandleNow = true;
            for(k2 = 0; k2 < srcRegs[k].num_dests; k2++) {
                if(dstStillInUse(srcRegs[k].dsts[k2].targetReg)) {
                    canHandleNow = false;
                    break;
                }
            }
            if(canHandleNow) {
                handledSrc[k] = true;
                num_handled++;
                handledOrder[num_in_order] = k;
                num_in_order++;
            }
        } //for k
        if(num_handled == prev_handled) {
            ALOGE("no progress in selecting order");
            dvmAbort();
        }
    } //while
    for(k = 0; k < num_src_regs; k++) {
        if(srcRegs[k].physicalReg == PhysicalReg_Null) {
            handledOrder[num_in_order] = k;
            num_in_order++;
        }
    }
    if(num_in_order != num_src_regs) {
        ALOGE("num_in_order != num_src_regs");
        dvmAbort();
    }
#ifdef DEBUG_STATE
    ALOGI("ORDER: ");
    for(k = 0; k < num_src_regs; k++) {
        ALOGI("%d ", handledOrder[k]);
    }
    ALOGI("");
#endif
}
//! transfer the state of register allocator to a state specified in a state table

//!
void transferToState(int stateNum) {
    freeReg(false); //do not spill GL
    int k;
#ifdef DEBUG_STATE
    ALOGI("STATE: transfer to state %d", stateNum);
#endif
    if(stateNum > 4 || stateNum < 1) ALOGE("state table overflow");
    constructSrcRegs(stateNum);
    int k4, k3;
    for(k4 = 0; k4 < num_src_regs; k4++) {
        int k2 = handledOrder[k4]; //index to srcRegs
        for(k3 = 0; k3 < srcRegs[k2].num_dests; k3++) {
            k = srcRegs[k2].dsts[k3].compileIndex;
            int targetReg = srcRegs[k2].dsts[k3].targetReg;
            int targetSpill = srcRegs[k2].dsts[k3].targetSpill;
            if(compileTable[k].physicalReg != targetReg && isVirtualReg(compileTable[k].physicalType)) {
                OpndSize oSize = getRegSize(compileTable[k].physicalType);
                bool isSS = ((compileTable[k].physicalType & MASK_FOR_TYPE) == LowOpndRegType_ss);
                if(compileTable[k].physicalReg == PhysicalReg_Null && targetReg != PhysicalReg_Null) {
                    if(isSS)
                        move_ss_mem_to_reg_noalloc(4*compileTable[k].regNum,
                                                   PhysicalReg_FP, true,
                                                   MemoryAccess_VR, compileTable[k].regNum,
                                                   targetReg, true);
                    else
                        move_mem_to_reg_noalloc(oSize, 4*compileTable[k].regNum,
                                                PhysicalReg_FP, true,
                                                MemoryAccess_VR, compileTable[k].regNum,
                                                targetReg, true);
                }
                if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg != PhysicalReg_Null) {
                    move_reg_to_reg_noalloc((isSS ? OpndSize_64 : oSize),
                                            compileTable[k].physicalReg, true,
                                            targetReg, true);
                }
                if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg == PhysicalReg_Null) {
                    dumpToMem(compileTable[k].regNum, (LowOpndRegType)(compileTable[k].physicalType & MASK_FOR_TYPE),
                              compileTable[k].physicalReg);
                }
            } //VR
            if(compileTable[k].physicalReg != targetReg && !isVirtualReg(compileTable[k].physicalType)) {
                OpndSize oSize = getRegSize(compileTable[k].physicalType);
                if(compileTable[k].physicalReg == PhysicalReg_Null && targetReg != PhysicalReg_Null) {
                    loadFromSpillRegion(oSize, targetReg,
                                        compileTable[k].spill_loc_index);
                }
                //both are not null, move from one to the other
                if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg != PhysicalReg_Null) {
                    move_reg_to_reg_noalloc(oSize, compileTable[k].physicalReg, true,
                                            targetReg, true);
                }
                //current is not null, target is null (move from reg to memory)
                if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg == PhysicalReg_Null) {
                    saveToSpillRegion(oSize, compileTable[k].physicalReg, targetSpill);
                }
            } //temporary
        }//for
    }//for
    for(k = 0; k < num_memory_vr; k++) {
        bool targetBool = false;
        int targetReg = -1;
        if(stateNum == 1) {
            targetReg = stateTable2_1[k].regNum;
            targetBool = stateTable2_1[k].inMemory;
        }
        else if(stateNum == 2) {
            targetReg = stateTable2_2[k].regNum;
            targetBool = stateTable2_2[k].inMemory;
        }
        else if(stateNum == 3) {
            targetReg = stateTable2_3[k].regNum;
            targetBool = stateTable2_3[k].inMemory;
        }
        else if(stateNum == 4) {
            targetReg = stateTable2_4[k].regNum;
            targetBool = stateTable2_4[k].inMemory;
        }
        if(targetReg != memVRTable[k].regNum)
            ALOGE("regNum mismatch in transferToState");
        if(targetBool && (!memVRTable[k].inMemory)) {
            //dump to memory, check entries in compileTable: vA gp vA xmm vA ss
#ifdef DEBUG_STATE
            ALOGW("inMemory mismatch for VR %d in transferToState", targetReg);
#endif
            bool doneXfer = false;
            int index = searchCompileTable(LowOpndRegType_xmm | LowOpndRegType_virtual, targetReg);
            if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
                dumpToMem(targetReg, LowOpndRegType_xmm, compileTable[index].physicalReg);
                doneXfer = true;
            }
            if(!doneXfer) { //vA-1, xmm
                index = searchCompileTable(LowOpndRegType_xmm | LowOpndRegType_virtual, targetReg-1);
                if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
                    dumpToMem(targetReg-1, LowOpndRegType_xmm, compileTable[index].physicalReg);
                    doneXfer = true;
                }
            }
            if(!doneXfer) { //vA gp
                index = searchCompileTable(LowOpndRegType_gp | LowOpndRegType_virtual, targetReg);
                if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
                    dumpToMem(targetReg, LowOpndRegType_gp, compileTable[index].physicalReg);
                    doneXfer = true;
                }
            }
            if(!doneXfer) { //vA, ss
                index = searchCompileTable(LowOpndRegType_ss | LowOpndRegType_virtual, targetReg);
                if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
                    dumpToMem(targetReg, LowOpndRegType_ss, compileTable[index].physicalReg);
                    doneXfer = true;
                }
            }
            if(!doneXfer) ALOGW("can't match inMemory of VR %d in transferToState", targetReg);
        }
        if((!targetBool) && memVRTable[k].inMemory) {
            //do nothing
        }
    }
#ifdef DEBUG_STATE
    ALOGI("END transferToState %d", stateNum);
#endif
    goToState(stateNum);
}
/* END code to handle state transfers */