Home | History | Annotate | Download | only in x86
      1 /*
      2  * Copyright (C) 2012 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 
     18 /*! \file AnalysisO1.cpp
     19   \brief This file implements register allocator, constant folding
     20 */
     21 #include "libdex/DexOpcodes.h"
     22 #include "libdex/DexFile.h"
     23 #include "Lower.h"
     24 #include "interp/InterpState.h"
     25 #include "interp/InterpDefs.h"
     26 #include "libdex/Leb128.h"
     27 
     28 /* compilation flags to turn on debug printout */
     29 //#define DEBUG_COMPILE_TABLE
     30 //#define DEBUG_ALLOC_CONSTRAINT
     31 //#define DEBUG_REGALLOC
     32 //#define DEBUG_REG_USED
     33 //#define DEBUG_REFCOUNT
     34 //#define DEBUG_REACHING_DEF2
     35 //#define DEBUG_REACHING_DEF
     36 //#define DEBUG_LIVE_RANGE
     37 //#define DEBUG_MOVE_OPT
     38 //#define DEBUG_SPILL
     39 //#define DEBUG_ENDOFBB
     40 //#define DEBUG_CONST
     41 /*
     42   #define DEBUG_XFER_POINTS
     43   #define DEBUG_DSE
     44   #define DEBUG_CFG
     45   #define DEBUG_GLOBALTYPE
     46   #define DEBUG_STATE
     47   #define DEBUG_COMPILE_TABLE
     48   #define DEBUG_VIRTUAL_INFO
     49   #define DEBUG_MOVE_OPT
     50   #define DEBUG_MERGE_ENTRY
     51   #define DEBUG_INVALIDATE
     52 */
     53 #include "AnalysisO1.h"
     54 
     55 void dumpCompileTable();
     56 
     57 /* There are 3 kinds of variables that are handled in this file:
     58    1> virtual register (isVirtualReg())
     59    2> temporary (!isVirtualReg() && regNum < PhysicalReg_GLUE_DVMDEX)
     60    3> glue variables: regNum >= PhysicalReg_GLUE_DVMDEX
     61 */
     62 /** check whether a variable is a virtual register
     63  */
     64 bool isVirtualReg(int type) {
     65     if((type & LowOpndRegType_virtual) != 0) return true;
     66     return false;
     67 }
     68 bool isTemporary(int type, int regNum) {
     69     if(!isVirtualReg(type) && regNum < PhysicalReg_GLUE_DVMDEX) return true;
     70     return false;
     71 }
     72 
     73 /** convert type defined in lowering module to type defined in register allocator
     74     in lowering module <type, isPhysical>
     75     in register allocator: LowOpndRegType_hard LowOpndRegType_virtual LowOpndRegType_scratch
     76 */
     77 int convertType(int type, int reg, bool isPhysical) {
     78     int newType = type;
     79     if(isPhysical) newType |= LowOpndRegType_hard;
     80     if(isVirtualReg(type)) newType |= LowOpndRegType_virtual;
     81     else {
     82         /* reg number for a VR can exceed PhysicalReg_SCRATCH_1 */
     83         if(reg >= PhysicalReg_SCRATCH_1 && reg < PhysicalReg_GLUE_DVMDEX)
     84             newType |= LowOpndRegType_scratch;
     85     }
     86     return newType;
     87 }
     88 
     89 /** return the size of a variable
     90  */
     91 OpndSize getRegSize(int type) {
     92     if((type & MASK_FOR_TYPE) == LowOpndRegType_xmm) return OpndSize_64;
     93     if((type & MASK_FOR_TYPE) == LowOpndRegType_fs) return OpndSize_64;
     94     /* for type _gp, _fs_s, _ss */
     95     return OpndSize_32;
     96 }
     97 
     98 /*
     99    Overlapping cases between two variables A and B
    100    layout for A,B   isAPartiallyOverlapB  isBPartiallyOverlapA
    101    1> |__|  |____|         OVERLAP_ALIGN        OVERLAP_B_COVER_A
    102       |__|  |____|
    103    2> |____|           OVERLAP_B_IS_LOW_OF_A    OVERLAP_B_COVER_LOW_OF_A
    104         |__|
    105    3> |____|           OVERLAP_B_IS_HIGH_OF_A   OVERLAP_B_COVER_HIGH_OF_A
    106       |__|
    107    4> |____|      OVERLAP_LOW_OF_A_IS_HIGH_OF_B OVERLAP_B_COVER_LOW_OF_A
    108          |____|
    109    5>    |____|   OVERLAP_HIGH_OF_A_IS_LOW_OF_B OVERLAP_B_COVER_HIGH_OF_A
    110       |____|
    111    6>   |__|           OVERLAP_A_IS_LOW_OF_B    OVERLAP_B_COVER_A
    112       |____|
    113    7> |__|             OVERLAP_A_IS_HIGH_OF_B   OVERLAP_B_COVER_A
    114       |____|
    115 */
    116 /** determine the overlapping between variable B and A
    117 */
    118 OverlapCase getBPartiallyOverlapA(int regB, LowOpndRegType tB, int regA, LowOpndRegType tA) {
    119     if(getRegSize(tA) == getRegSize(tB) && regA == regB) return OVERLAP_B_COVER_A;
    120     if(getRegSize(tA) == OpndSize_64 && getRegSize(tB) == OpndSize_32 && regA == regB) return OVERLAP_B_COVER_LOW_OF_A;
    121     if(getRegSize(tA) == OpndSize_64 && getRegSize(tB) == OpndSize_32 && regB == regA + 1) return OVERLAP_B_COVER_HIGH_OF_A;
    122     if(getRegSize(tA) == OpndSize_32 && getRegSize(tB) == OpndSize_64 && (regA == regB || regA == regB+1)) return OVERLAP_B_COVER_A;
    123     if(getRegSize(tB) == OpndSize_64 && getRegSize(tA) == OpndSize_64 && regA == regB+1) return OVERLAP_B_COVER_LOW_OF_A;
    124     if(getRegSize(tB) == OpndSize_64 && getRegSize(tA) == OpndSize_64 && regB == regA+1) return OVERLAP_B_COVER_HIGH_OF_A;
    125     return OVERLAP_NO;
    126 }
    127 
    128 /** determine overlapping between variable A and B
    129 */
    130 OverlapCase getAPartiallyOverlapB(int regA, LowOpndRegType tA, int regB, LowOpndRegType tB) {
    131     if(getRegSize(tA) == getRegSize(tB) && regA == regB) return OVERLAP_ALIGN;
    132     if(getRegSize(tA) == OpndSize_64 && getRegSize(tB) == OpndSize_32 && regA == regB)
    133         return OVERLAP_B_IS_LOW_OF_A;
    134     if(getRegSize(tA) == OpndSize_64 && getRegSize(tB) == OpndSize_32 && regB == regA+1)
    135         return OVERLAP_B_IS_HIGH_OF_A;
    136     if(getRegSize(tB) == OpndSize_64 && getRegSize(tA) == OpndSize_64 && regA == regB+1)
    137         return OVERLAP_LOW_OF_A_IS_HIGH_OF_B;
    138     if(getRegSize(tB) == OpndSize_64 && getRegSize(tA) == OpndSize_64 && regB == regA+1)
    139         return OVERLAP_HIGH_OF_A_IS_LOW_OF_B;
    140     if(getRegSize(tA) == OpndSize_32 && getRegSize(tB) == OpndSize_64 && regA == regB)
    141         return OVERLAP_A_IS_LOW_OF_B;
    142     if(getRegSize(tA) == OpndSize_32 && getRegSize(tB) == OpndSize_64 && regA == regB+1)
    143         return OVERLAP_A_IS_HIGH_OF_B;
    144     return OVERLAP_NO;
    145 }
    146 
    147 /** determine whether variable A fully covers B
    148  */
    149 bool isAFullyCoverB(int regA, LowOpndRegType tA, int regB, LowOpndRegType tB) {
    150     if(getRegSize(tB) == OpndSize_32) return true;
    151     if(getRegSize(tA) == getRegSize(tB) && regA == regB) return true;
    152     return false;
    153 }
    154 
    155 /*
    156    RegAccessType accessType
    157    1> DefOrUse.accessType
    158       can only be D(VR), L(low part of VR), H(high part of VR), N(none)
    159       for def, it means which part of the VR is live
    160       for use, it means which part of the VR comes from the def
    161    2> VirtualRegInfo.accessType
    162       for currentInfo, it can only be a combination of U & D
    163       for entries in infoBasicBlock, it can be a combination of U & D|L|H
    164 */
    165 
    166 /*
    167    Key data structures used:
    168    1> BasicBlock_O1
    169       VirtualRegInfo infoBasicBlock[]
    170       DefUsePair* defUseTable
    171       XferPoint xferPoints[]
    172    2> MemoryVRInfo memVRTable[]
    173       LiveRange* ranges
    174    3> compileTableEntry compileTable[]
    175    4> VirtualRegInfo
    176       DefOrUse reachingDefs[3]
    177    5> DefUsePair, LiveRange
    178 */
    179 
    180 //! one entry for each variable used
    181 
    182 //! a variable can be virtual register, or a temporary (can be hard-coded)
    183 compileTableEntry compileTable[COMPILE_TABLE_SIZE];
    184 int num_compile_entries;
    185 //! tables to save the states of register allocation
    186 regAllocStateEntry1 stateTable1_1[COMPILE_TABLE_SIZE];
    187 regAllocStateEntry1 stateTable1_2[COMPILE_TABLE_SIZE];
    188 regAllocStateEntry1 stateTable1_3[COMPILE_TABLE_SIZE];
    189 regAllocStateEntry1 stateTable1_4[COMPILE_TABLE_SIZE];
    190 regAllocStateEntry2 stateTable2_1[COMPILE_TABLE_SIZE];
    191 regAllocStateEntry2 stateTable2_2[COMPILE_TABLE_SIZE];
    192 regAllocStateEntry2 stateTable2_3[COMPILE_TABLE_SIZE];
    193 regAllocStateEntry2 stateTable2_4[COMPILE_TABLE_SIZE];
    194 
    195 //! array of VirtualRegInfo to store VRs accessed by a single bytecode
    196 VirtualRegInfo infoByteCode[MAX_REG_PER_BYTECODE];
    197 int num_regs_per_bytecode;
    198 //! array of TempRegInfo to store temporaries accessed by a single bytecode
    199 TempRegInfo infoByteCodeTemp[MAX_TEMP_REG_PER_BYTECODE];
    200 int num_temp_regs_per_bytecode;
    201 //! array of MemoryVRInfo to store whether a VR is in memory
    202 #define NUM_MEM_VR_ENTRY 140
    203 MemoryVRInfo memVRTable[NUM_MEM_VR_ENTRY];
    204 int num_memory_vr;
    205 
    206 CompilationUnit* currentUnit = NULL;
    207 
    208 //! the current basic block
    209 BasicBlock_O1* currentBB = NULL;
    210 //! array of RegisterInfo for all the physical registers
    211 RegisterInfo allRegs[PhysicalReg_GLUE+1]; //initialized in codeGen
    212 
    213 VirtualRegInfo currentInfo;
    214 VirtualRegInfo tmpInfo;
    215 
    216 //! this array says whether a spill location is used (0 means not used, 1 means used)
    217 int spillIndexUsed[MAX_SPILL_JIT_IA];
    218 int indexForGlue = -1;
    219 
    220 int num_bbs_for_method;
    221 //! array of basic blocks in a method in program order
    222 BasicBlock_O1* method_bbs_sorted[MAX_NUM_BBS_PER_METHOD];
    223 //! the entry basic block
    224 BasicBlock_O1* bb_entry;
    225 int pc_start = -1;
    226 int pc_end = -1;
    227 
    228 //!array of PCs for exception handlers
    229 int exceptionHandlers[10];
    230 int num_exception_handlers;
    231 
    232 bool canSpillReg[PhysicalReg_Null]; //physical registers that should not be spilled
    233 int inGetVR_num = -1;
    234 int inGetVR_type;
    235 
    236 ///////////////////////////////////////////////////////////////////////////////
    237 // FORWARD FUNCTION DECLARATION
    238 void addExceptionHandler(s4 tmp);
    239 
    240 int createCFG(Method* method);
    241 int collectInfoOfBasicBlock(Method* method, BasicBlock_O1* bb);
    242 void dumpVirtualInfoOfBasicBlock(BasicBlock_O1* bb);
    243 void setTypeOfVR();
    244 void insertGlueReg();
    245 void dumpVirtualInfoOfMethod();
    246 int codeGenBasicBlock(const Method* method, BasicBlock_O1* bb);
    247 
    248 //used in collectInfoOfBasicBlock: getVirtualRegInfo
    249 int mergeEntry2(BasicBlock_O1* bb);
    250 int sortAllocConstraint(RegAllocConstraint* allocConstraints,
    251                         RegAllocConstraint* allocConstraintsSorted, bool fromHighToLow);
    252 
    253 //used in codeGenBasicBlock
    254 void insertFromVirtualInfo(BasicBlock_O1* bb, int k); //update compileTable
    255 void insertFromTempInfo(int k); //update compileTable
    256 int updateXferPoints();
    257 void updateLiveTable();
    258 void printDefUseTable();
    259 bool isFirstOfHandler(BasicBlock_O1* bb);
    260 
    261 //used in mergeEntry2
    262 //following functions will not update global data structure
    263 RegAccessType mergeAccess2(RegAccessType A, RegAccessType B, OverlapCase isBPartiallyOverlapA);
    264 RegAccessType updateAccess1(RegAccessType A, OverlapCase isAPartiallyOverlapB); //will not update global data structure
    265 RegAccessType updateAccess2(RegAccessType C1, RegAccessType C2);
    266 RegAccessType updateAccess3(RegAccessType C, RegAccessType B);
    267 
    268 void updateDefUseTable();
    269 void updateReachingDefA(int indexToA, OverlapCase isBPartiallyOverlapA);
    270 void updateReachingDefB1(int indexToA);
    271 void updateReachingDefB2();
    272 void updateReachingDefB3();
    273 
    274 RegAccessType insertAUse(DefUsePair* ptr, int offsetPC, int regNum, LowOpndRegType physicalType);
    275 DefUsePair* insertADef(int offsetPC, int regNum, LowOpndRegType pType, RegAccessType rType);
    276 RegAccessType insertDefUsePair(int reachingDefIndex);
    277 
    278 //used in updateXferPoints
    279 int fakeUsageAtEndOfBB(BasicBlock_O1* bb);
    280 void insertLoadXfer(int offset, int regNum, LowOpndRegType pType);
    281 int searchMemTable(int regNum);
    282 void mergeLiveRange(int tableIndex, int rangeStart, int rangeEnd);
    283 //used in updateLiveTable
    284 RegAccessType setAccessTypeOfUse(OverlapCase isDefPartiallyOverlapUse, RegAccessType reachingDefLive);
    285 DefUsePair* searchDefUseTable(int offsetPC, int regNum, LowOpndRegType pType);
    286 void insertAccess(int tableIndex, LiveRange* startP, int rangeStart);
    287 
    288 //register allocation
    289 int spillLogicalReg(int spill_index, bool updateTable);
    290 
    291 /** check whether the current bytecode is IF or GOTO or SWITCH
    292  */
    293 bool isCurrentByteCodeJump() {
    294     u2 inst_op = INST_INST(inst);
    295     if(inst_op == OP_IF_EQ || inst_op == OP_IF_NE || inst_op == OP_IF_LT ||
    296        inst_op == OP_IF_GE || inst_op == OP_IF_GT || inst_op == OP_IF_LE) return true;
    297     if(inst_op == OP_IF_EQZ || inst_op == OP_IF_NEZ || inst_op == OP_IF_LTZ ||
    298        inst_op == OP_IF_GEZ || inst_op == OP_IF_GTZ || inst_op == OP_IF_LEZ) return true;
    299     if(inst_op == OP_GOTO || inst_op == OP_GOTO_16 || inst_op == OP_GOTO_32) return true;
    300     if(inst_op == OP_PACKED_SWITCH || inst_op == OP_SPARSE_SWITCH) return true;
    301     return false;
    302 }
    303 
    304 /* this function is called before code generation of basic blocks
    305    initialize data structure allRegs, which stores information for each physical register,
    306    whether it is used, when it was last freed, whether it is callee-saved */
    307 void initializeAllRegs() {
    308     int k;
    309     for(k = PhysicalReg_EAX; k <= PhysicalReg_EBP; k++) {
    310         allRegs[k].physicalReg = (PhysicalReg) k;
    311         if(k == PhysicalReg_EDI || k == PhysicalReg_ESP || k == PhysicalReg_EBP)
    312             allRegs[k].isUsed = true;
    313         else {
    314             allRegs[k].isUsed = false;
    315             allRegs[k].freeTimeStamp = -1;
    316         }
    317         if(k == PhysicalReg_EBX || k == PhysicalReg_EBP || k == PhysicalReg_ESI || k == PhysicalReg_EDI)
    318             allRegs[k].isCalleeSaved = true;
    319         else
    320             allRegs[k].isCalleeSaved = false;
    321     }
    322     for(k = PhysicalReg_XMM0; k <= PhysicalReg_XMM7; k++) {
    323         allRegs[k].physicalReg = (PhysicalReg) k;
    324         allRegs[k].isUsed = false;
    325         allRegs[k].freeTimeStamp = -1;
    326         allRegs[k].isCalleeSaved = false;
    327     }
    328 }
    329 
    330 /** sync up allRegs (isUsed & freeTimeStamp) with compileTable
    331     global data: RegisterInfo allRegs[PhysicalReg_Null]
    332     update allRegs[EAX to XMM7] except EDI,ESP,EBP
    333     update RegisterInfo.isUsed & RegisterInfo.freeTimeStamp
    334         if the physical register was used and is not used now
    335 */
    336 void syncAllRegs() {
    337     int k, k2;
    338     for(k = PhysicalReg_EAX; k <= PhysicalReg_XMM7; k++) {
    339         if(k == PhysicalReg_EDI || k == PhysicalReg_ESP || k == PhysicalReg_EBP)
    340             continue;
    341         //check whether the physical register is used by any logical register
    342         bool stillUsed = false;
    343         for(k2 = 0; k2 < num_compile_entries; k2++) {
    344             if(compileTable[k2].physicalReg == k) {
    345                 stillUsed = true;
    346                 break;
    347             }
    348         }
    349         if(stillUsed && !allRegs[k].isUsed) {
    350             allRegs[k].isUsed = true;
    351         }
    352         if(!stillUsed && allRegs[k].isUsed) {
    353             allRegs[k].isUsed = false;
    354             allRegs[k].freeTimeStamp = lowOpTimeStamp;
    355         }
    356     }
    357     return;
    358 }
    359 
    360 //!sync up spillIndexUsed with compileTable
    361 
    362 //!
    363 void updateSpillIndexUsed() {
    364     int k;
    365     for(k = 0; k <= MAX_SPILL_JIT_IA-1; k++) spillIndexUsed[k] = 0;
    366     for(k = 0; k < num_compile_entries; k++) {
    367         if(isVirtualReg(compileTable[k].physicalType)) continue;
    368         if(compileTable[k].spill_loc_index >= 0) {
    369             if(compileTable[k].spill_loc_index > 4*(MAX_SPILL_JIT_IA-1))
    370                 ALOGE("spill_loc_index is wrong for entry %d: %d",
    371                       k, compileTable[k].spill_loc_index);
    372             spillIndexUsed[compileTable[k].spill_loc_index >> 2] = 1;
    373         }
    374     }
    375 }
    376 
    377 /* free memory used in all basic blocks */
    378 void freeCFG() {
    379     int k;
    380     for(k = 0; k < num_bbs_for_method; k++) {
    381         /* free defUseTable for method_bbs_sorted[k] */
    382         DefUsePair* ptr = method_bbs_sorted[k]->defUseTable;
    383         while(ptr != NULL) {
    384             DefUsePair* tmp = ptr->next;
    385             /* free ptr->uses */
    386             DefOrUseLink* ptrUse = ptr->uses;
    387             while(ptrUse != NULL) {
    388                 DefOrUseLink* tmp2 = ptrUse->next;
    389                 free(ptrUse);
    390                 ptrUse = tmp2;
    391             }
    392             free(ptr);
    393             ptr = tmp;
    394         }
    395         free(method_bbs_sorted[k]);
    396     }
    397 }
    398 
    399 /* update compileTable.physicalReg, compileTable.spill_loc_index & allRegs.isUsed
    400    for glue-related variables, they do not exist
    401        not in a physical register (physicalReg is Null)
    402        not in a spilled memory location (spill_loc_index is -1)
    403 */
    404 void initializeRegStateOfBB(BasicBlock_O1* bb) {
    405     //for GLUE variables, do not exist
    406     int k;
    407     for(k = 0; k < num_compile_entries; k++) {
    408         /* trace-based JIT: there is no VR with GG type */
    409         if(isVirtualReg(compileTable[k].physicalType) && compileTable[k].gType == GLOBALTYPE_GG) {
    410             if(bb->bb_index > 0) { //non-entry block
    411                 if(isFirstOfHandler(bb)) {
    412                     /* at the beginning of an exception handler, GG VR is in the interpreted stack */
    413                     compileTable[k].physicalReg = PhysicalReg_Null;
    414 #ifdef DEBUG_COMPILE_TABLE
    415                     ALOGI("at the first basic block of an exception handler, GG VR %d type %d is in memory",
    416                           compileTable[k].regNum, compileTable[k].physicalType);
    417 #endif
    418                 } else {
    419                     if(compileTable[k].physicalReg == PhysicalReg_Null) {
    420                         /* GG VR is in a specific physical register */
    421                         compileTable[k].physicalReg = compileTable[k].physicalReg_prev;
    422                     }
    423                     int tReg = compileTable[k].physicalReg;
    424                     allRegs[tReg].isUsed = true;
    425 #ifdef DEBUG_REG_USED
    426                     ALOGI("REGALLOC: physical reg %d is used by a GG VR %d %d at beginning of BB", tReg, compileTable[k].regNum, compileTable[k].physicalType);
    427 #endif
    428                 }
    429             } //non-entry block
    430         } //if GG VR
    431         if(compileTable[k].regNum != PhysicalReg_GLUE &&
    432            compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX) {
    433             /* glue related registers */
    434             compileTable[k].physicalReg = PhysicalReg_Null;
    435             compileTable[k].spill_loc_index = -1;
    436         }
    437     }
    438 }
    439 
    440 /* update memVRTable[].nullCheckDone */
    441 void initializeNullCheck(int indexToMemVR) {
    442     bool found = false;
    443 #ifdef GLOBAL_NULLCHECK_OPT
    444     /* search nullCheck_inB of the current Basic Block */
    445     for(k = 0; k < nullCheck_inSize[currentBB->bb_index2]; k++) {
    446         if(nullCheck_inB[currentBB->bb_index2][k] == memVRTable[indexToMemVR].regNum) {
    447             found = true;
    448             break;
    449         }
    450     }
    451 #endif
    452     memVRTable[indexToMemVR].nullCheckDone = found;
    453 }
    454 
    455 /* initialize memVRTable */
    456 void initializeMemVRTable() {
    457     num_memory_vr = 0;
    458     int k;
    459     for(k = 0; k < num_compile_entries; k++) {
    460         if(!isVirtualReg(compileTable[k].physicalType)) continue;
    461         /* VRs in compileTable */
    462         bool setToInMemory = (compileTable[k].physicalReg == PhysicalReg_Null);
    463         int regNum = compileTable[k].regNum;
    464         OpndSize sizeVR = getRegSize(compileTable[k].physicalType);
    465         /* search memVRTable for the VR in compileTable */
    466         int kk;
    467         int indexL = -1;
    468         int indexH = -1;
    469         for(kk = 0; kk < num_memory_vr; kk++) {
    470             if(memVRTable[kk].regNum == regNum) {
    471                 indexL = kk;
    472                 continue;
    473             }
    474             if(memVRTable[kk].regNum == regNum+1 && sizeVR == OpndSize_64) {
    475                 indexH = kk;
    476                 continue;
    477             }
    478         }
    479         if(indexL < 0) {
    480             /* the low half of VR is not in memVRTable
    481                add an entry for the low half in memVRTable */
    482             if(num_memory_vr >= NUM_MEM_VR_ENTRY) {
    483                 ALOGE("exceeds size of memVRTable");
    484                 dvmAbort();
    485             }
    486             memVRTable[num_memory_vr].regNum = regNum;
    487             memVRTable[num_memory_vr].inMemory = setToInMemory;
    488             initializeNullCheck(num_memory_vr); //set nullCheckDone
    489             memVRTable[num_memory_vr].boundCheck.checkDone = false;
    490             memVRTable[num_memory_vr].num_ranges = 0;
    491             memVRTable[num_memory_vr].ranges = NULL;
    492             memVRTable[num_memory_vr].delayFreeFlags = VRDELAY_NONE;
    493             num_memory_vr++;
    494         }
    495         if(sizeVR == OpndSize_64 && indexH < 0) {
    496             /* the high half of VR is not in memVRTable
    497                add an entry for the high half in memVRTable */
    498             if(num_memory_vr >= NUM_MEM_VR_ENTRY) {
    499                 ALOGE("exceeds size of memVRTable");
    500                 dvmAbort();
    501             }
    502             memVRTable[num_memory_vr].regNum = regNum+1;
    503             memVRTable[num_memory_vr].inMemory = setToInMemory;
    504             initializeNullCheck(num_memory_vr);
    505             memVRTable[num_memory_vr].boundCheck.checkDone = false;
    506             memVRTable[num_memory_vr].num_ranges = 0;
    507             memVRTable[num_memory_vr].ranges = NULL;
    508             memVRTable[num_memory_vr].delayFreeFlags = VRDELAY_NONE;
    509             num_memory_vr++;
    510         }
    511     }
    512 }
    513 
    514 /* create a O1 basic block from basic block constructed in JIT MIR */
    515 BasicBlock_O1* createBasicBlockO1(BasicBlock* bb) {
    516     BasicBlock_O1* bb1 = createBasicBlock(0, -1);
    517     bb1->jitBasicBlock = bb;
    518     return bb1;
    519 }
    520 
    521 /* a basic block in JIT MIR can contain bytecodes that are not in program order
    522    for example, a "goto" bytecode will be followed by the goto target */
    523 void preprocessingBB(BasicBlock* bb) {
    524     currentBB = createBasicBlockO1(bb);
    525     /* initialize currentBB->allocConstraints */
    526     int ii;
    527     for(ii = 0; ii < 8; ii++) {
    528         currentBB->allocConstraints[ii].physicalReg = (PhysicalReg)ii;
    529         currentBB->allocConstraints[ii].count = 0;
    530     }
    531     collectInfoOfBasicBlock(currentMethod, currentBB);
    532 #ifdef DEBUG_COMPILE_TABLE
    533     dumpVirtualInfoOfBasicBlock(currentBB);
    534 #endif
    535     currentBB = NULL;
    536 }
    537 
    538 void preprocessingTrace() {
    539     int k, k2, k3, jj;
    540     /* this is a simplified verson of setTypeOfVR()
    541         all VRs are assumed to be GL, no VR will be GG
    542     */
    543     for(k = 0; k < num_bbs_for_method; k++)
    544         for(jj = 0; jj < method_bbs_sorted[k]->num_regs; jj++)
    545             method_bbs_sorted[k]->infoBasicBlock[jj].gType = GLOBALTYPE_GL;
    546 
    547     /* insert a glue-related register GLUE_DVMDEX to compileTable */
    548     insertGlueReg();
    549 
    550     int compile_entries_old = num_compile_entries;
    551     for(k2 = 0; k2 < num_bbs_for_method; k2++) {
    552         currentBB = method_bbs_sorted[k2];
    553         /* update compileTable with virtual register from currentBB */
    554         for(k3 = 0; k3 < currentBB->num_regs; k3++) {
    555             insertFromVirtualInfo(currentBB, k3);
    556         }
    557 
    558         /* for each GL|GG type VR, insert fake usage at end of basic block to keep it live */
    559         int offsetPC_back = offsetPC;
    560         offsetPC = PC_FOR_END_OF_BB;
    561         for(k = 0; k < num_compile_entries; k++) {
    562             currentInfo.regNum = compileTable[k].regNum;
    563             currentInfo.physicalType = (LowOpndRegType)compileTable[k].physicalType;
    564             if(isVirtualReg(compileTable[k].physicalType) &&
    565                compileTable[k].gType == GLOBALTYPE_GL) {
    566                 /* update defUseTable by assuming a fake usage at END of a basic block for variable @ currentInfo */
    567                 fakeUsageAtEndOfBB(currentBB);
    568             }
    569             if(isVirtualReg(compileTable[k].physicalType) &&
    570                compileTable[k].gType == GLOBALTYPE_GG) {
    571                 fakeUsageAtEndOfBB(currentBB);
    572             }
    573         }
    574         offsetPC = offsetPC_back;
    575         num_compile_entries = compile_entries_old;
    576     }
    577     /* initialize data structure allRegs */
    578     initializeAllRegs();
    579 #ifdef DEBUG_COMPILE_TABLE
    580     dumpCompileTable();
    581 #endif
    582     currentBB = NULL;
    583 }
    584 
    585 void printJitTraceInfoAtRunTime(const Method* method, int offset) {
    586     ALOGI("execute trace for %s%s at offset %x", method->clazz->descriptor, method->name, offset);
    587 }
    588 
    589 void startOfTraceO1(const Method* method, LowOpBlockLabel* labelList, int exceptionBlockId, CompilationUnit *cUnit) {
    590     num_exception_handlers = 0;
    591     num_compile_entries = 0;
    592     currentBB = NULL;
    593     pc_start = -1;
    594     bb_entry = NULL;
    595     num_bbs_for_method = 0;
    596     currentUnit = cUnit;
    597     lowOpTimeStamp = 0;
    598 
    599 // dumpDebuggingInfo is gone in CompilationUnit struct
    600 #if 0
    601     /* add code to dump debugging information */
    602     if(cUnit->dumpDebuggingInfo) {
    603         move_imm_to_mem(OpndSize_32, cUnit->startOffset, -4, PhysicalReg_ESP, true); //2nd argument: offset
    604         move_imm_to_mem(OpndSize_32, (int)currentMethod, -8, PhysicalReg_ESP, true); //1st argument: method
    605         load_effective_addr(-8, PhysicalReg_ESP, true, PhysicalReg_ESP, true);
    606 
    607         typedef void (*vmHelper)(const Method*, int);
    608         vmHelper funcPtr = printJitTraceInfoAtRunTime;
    609         move_imm_to_reg(OpndSize_32, (int)funcPtr, PhysicalReg_ECX, true);
    610         call_reg(PhysicalReg_ECX, true);
    611 
    612         load_effective_addr(8, PhysicalReg_ESP, true, PhysicalReg_ESP, true);
    613     }
    614 #endif
    615 }
    616 
    617 
    618 /* Code generation for a basic block defined for JIT
    619    We have two data structures for a basic block:
    620        BasicBlock defined in vm/compiler by JIT
    621        BasicBlock_O1 defined in o1 */
    622 int codeGenBasicBlockJit(const Method* method, BasicBlock* bb) {
    623     /* search method_bbs_sorted to find the O1 basic block corresponding to bb */
    624     int k;
    625     for(k = 0; k < num_bbs_for_method; k++) {
    626         if(method_bbs_sorted[k]->jitBasicBlock == bb) {
    627             lowOpTimeStamp = 0; //reset time stamp at start of a basic block
    628             currentBB = method_bbs_sorted[k];
    629             int cg_ret = codeGenBasicBlock(method, currentBB);
    630             currentBB = NULL;
    631             return cg_ret;
    632         }
    633     }
    634     ALOGE("can't find the corresponding O1 basic block for id %d type %d",
    635          bb->id, bb->blockType);
    636     return -1;
    637 }
    638 void endOfBasicBlock(BasicBlock* bb) {
    639     isScratchPhysical = true;
    640     currentBB = NULL;
    641 }
    642 void endOfTraceO1() {
    643      freeCFG();
    644 }
    645 
    646 /** entry point to collect information about virtual registers used in a basic block
    647     Initialize data structure BasicBlock_O1
    648     The usage information of virtual registers is stoerd in bb->infoBasicBlock
    649 
    650     Global variables accessed: offsetPC, rPC
    651 */
    652 int collectInfoOfBasicBlock(Method* method, BasicBlock_O1* bb) {
    653     bb->num_regs = 0;
    654     bb->num_defs = 0;
    655     bb->defUseTable = NULL;
    656     bb->defUseTail = NULL;
    657     u2* rPC_start = (u2*)method->insns;
    658     int kk;
    659     bb->endsWithReturn = false;
    660     bb->hasAccessToGlue = false;
    661 
    662     MIR* mir;
    663     int seqNum = 0;
    664     /* traverse the MIR in basic block
    665        sequence number is used to make sure next bytecode will have a larger sequence number */
    666     for(mir = bb->jitBasicBlock->firstMIRInsn; mir; mir = mir->next) {
    667         offsetPC = seqNum;
    668         mir->seqNum = seqNum++;
    669         rPC = rPC_start + mir->offset;
    670 #ifdef WITH_JIT_INLINING
    671         if(mir->dalvikInsn.opcode >= kMirOpFirst &&
    672            mir->dalvikInsn.opcode != kMirOpCheckInlinePrediction) continue;
    673         if(ir->dalvikInsn.opcode == kMirOpCheckInlinePrediction) { //TODO
    674         }
    675 #else
    676         if(mir->dalvikInsn.opcode >= kNumPackedOpcodes) continue;
    677 #endif
    678         inst = FETCH(0);
    679         u2 inst_op = INST_INST(inst);
    680         /* update bb->hasAccessToGlue */
    681         if((inst_op >= OP_MOVE_RESULT && inst_op <= OP_RETURN_OBJECT) ||
    682            (inst_op >= OP_MONITOR_ENTER && inst_op <= OP_INSTANCE_OF) ||
    683            (inst_op == OP_FILLED_NEW_ARRAY) ||
    684            (inst_op == OP_FILLED_NEW_ARRAY_RANGE) ||
    685            (inst_op == OP_THROW) ||
    686            (inst_op >= OP_INVOKE_VIRTUAL && inst_op <= OP_INVOKE_INTERFACE_RANGE) ||
    687            (inst_op >= OP_THROW_VERIFICATION_ERROR &&
    688             inst_op <= OP_EXECUTE_INLINE_RANGE) ||
    689            (inst_op >= OP_INVOKE_VIRTUAL_QUICK && inst_op <= OP_INVOKE_SUPER_QUICK_RANGE))
    690             bb->hasAccessToGlue = true;
    691         /* update bb->endsWithReturn */
    692         if(inst_op == OP_RETURN_VOID || inst_op == OP_RETURN || inst_op == OP_RETURN_VOID_BARRIER ||
    693            inst_op == OP_RETURN_OBJECT || inst_op == OP_RETURN_WIDE)
    694             bb->endsWithReturn = true;
    695 
    696         /* get virtual register usage in current bytecode */
    697         getVirtualRegInfo(infoByteCode);
    698         int num_regs = num_regs_per_bytecode;
    699         for(kk = 0; kk < num_regs; kk++) {
    700             currentInfo = infoByteCode[kk];
    701 #ifdef DEBUG_MERGE_ENTRY
    702             ALOGI("call mergeEntry2 at offsetPC %x kk %d VR %d %d", offsetPC, kk,
    703                   currentInfo.regNum, currentInfo.physicalType);
    704 #endif
    705             mergeEntry2(bb); //update defUseTable of the basic block
    706         }
    707 
    708         //dumpVirtualInfoOfBasicBlock(bb);
    709     }//for each bytecode
    710 
    711     bb->pc_end = seqNum;
    712 
    713     //sort allocConstraints of each basic block
    714     for(kk = 0; kk < bb->num_regs; kk++) {
    715 #ifdef DEBUG_ALLOC_CONSTRAINT
    716         ALOGI("sort virtual reg %d type %d -------", bb->infoBasicBlock[kk].regNum,
    717               bb->infoBasicBlock[kk].physicalType);
    718 #endif
    719         sortAllocConstraint(bb->infoBasicBlock[kk].allocConstraints,
    720                             bb->infoBasicBlock[kk].allocConstraintsSorted, true);
    721     }
    722 #ifdef DEBUG_ALLOC_CONSTRAINT
    723     ALOGI("sort constraints for BB %d --------", bb->bb_index);
    724 #endif
    725     sortAllocConstraint(bb->allocConstraints, bb->allocConstraintsSorted, false);
    726     return 0;
    727 }
    728 
    729 /** entry point to generate native code for a O1 basic block
    730     There are 3 kinds of virtual registers in a O1 basic block:
    731     1> L VR: local within the basic block
    732     2> GG VR: is live in other basic blocks,
    733               its content is in a pre-defined GPR at the beginning of a basic block
    734     3> GL VR: is live in other basic blocks,
    735               its content is in the interpreted stack at the beginning of a basic block
    736     compileTable is updated with infoBasicBlock at the start of the basic block;
    737     Before lowering each bytecode, compileTable is updated with infoByteCodeTemp;
    738     At end of the basic block, right before the jump instruction, handles constant VRs and GG VRs
    739 */
    740 int codeGenBasicBlock(const Method* method, BasicBlock_O1* bb) {
    741     /* we assume at the beginning of each basic block,
    742        all GL VRs reside in memory and all GG VRs reside in predefined physical registers,
    743        so at the end of a basic block, recover a spilled GG VR, store a GL VR to memory */
    744     /* update compileTable with entries in bb->infoBasicBlock */
    745     int k;
    746     for(k = 0; k < bb->num_regs; k++) {
    747         insertFromVirtualInfo(bb, k);
    748     }
    749     updateXferPoints(); //call fakeUsageAtEndOfBB
    750 #ifdef DEBUG_REACHING_DEF
    751     printDefUseTable();
    752 #endif
    753 #ifdef DSE_OPT
    754     removeDeadDefs();
    755     printDefUseTable();
    756 #endif
    757     //clear const section of compileTable
    758     for(k = 0; k < num_compile_entries; k++) compileTable[k].isConst = false;
    759     num_const_vr = 0;
    760 #ifdef DEBUG_COMPILE_TABLE
    761     ALOGI("At start of basic block %d (num of VRs %d) -------", bb->bb_index, bb->num_regs);
    762     dumpCompileTable();
    763 #endif
    764     initializeRegStateOfBB(bb);
    765     initializeMemVRTable();
    766     updateLiveTable();
    767     freeReg(true);  //before code gen of a basic block, also called at end of a basic block?
    768 #ifdef DEBUG_COMPILE_TABLE
    769     ALOGI("At start of basic block %d (num of VRs %d) -------", bb->bb_index, bb->num_regs);
    770 #endif
    771 
    772     u2* rPC_start = (u2*)method->insns;
    773     bool lastByteCodeIsJump = false;
    774     MIR* mir;
    775     for(mir = bb->jitBasicBlock->firstMIRInsn; mir; mir = mir->next) {
    776         offsetPC = mir->seqNum;
    777         rPC = rPC_start + mir->offset;
    778 #ifdef WITH_JIT_INLINING
    779         if(mir->dalvikInsn.opcode >= kMirOpFirst &&
    780            mir->dalvikInsn.opcode != kMirOpCheckInlinePrediction) {
    781 #else
    782         if(mir->dalvikInsn.opcode >= kNumPackedOpcodes) {
    783 #endif
    784             handleExtendedMIR(currentUnit, mir);
    785             continue;
    786         }
    787 
    788         inst = FETCH(0);
    789         //before handling a bytecode, import info of temporary registers to compileTable including refCount
    790         num_temp_regs_per_bytecode = getTempRegInfo(infoByteCodeTemp);
    791         for(k = 0; k < num_temp_regs_per_bytecode; k++) {
    792             if(infoByteCodeTemp[k].versionNum > 0) continue;
    793             insertFromTempInfo(k);
    794         }
    795         startNativeCode(-1, -1);
    796         for(k = 0; k <= MAX_SPILL_JIT_IA-1; k++) spillIndexUsed[k] = 0;
    797         //update spillIndexUsed if a glue variable was spilled
    798         for(k = 0; k < num_compile_entries; k++) {
    799             if(compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX) {
    800                 if(compileTable[k].spill_loc_index >= 0)
    801                     spillIndexUsed[compileTable[k].spill_loc_index >> 2] = 1;
    802             }
    803         }
    804 #ifdef DEBUG_COMPILE_TABLE
    805         ALOGI("compile table size after importing temporary info %d", num_compile_entries);
    806         ALOGI("before one bytecode %d (num of VRs %d) -------", bb->bb_index, bb->num_regs);
    807 #endif
    808         //set isConst to true for CONST & MOVE MOVE_OBJ?
    809         //clear isConst to true for MOVE, MOVE_OBJ, MOVE_RESULT, MOVE_EXCEPTION ...
    810         bool isConst = getConstInfo(bb); //will reset isConst if a VR is updated by the bytecode
    811         bool isDeadStmt = false;
    812 #ifdef DSE_OPT
    813         for(k = 0; k < num_dead_pc; k++) {
    814             if(deadPCs[k] == offsetPC) {
    815                 isDeadStmt = true;
    816                 break;
    817             }
    818         }
    819 #endif
    820         getVirtualRegInfo(infoByteCode);
    821         //call something similar to mergeEntry2, but only update refCount
    822         //clear refCount
    823         for(k = 0; k < num_regs_per_bytecode; k++) {
    824             int indexT = searchCompileTable(LowOpndRegType_virtual | infoByteCode[k].physicalType,
    825                                             infoByteCode[k].regNum);
    826             if(indexT >= 0)
    827                 compileTable[indexT].refCount = 0;
    828         }
    829         for(k = 0; k < num_regs_per_bytecode; k++) {
    830             int indexT = searchCompileTable(LowOpndRegType_virtual | infoByteCode[k].physicalType,
    831                                             infoByteCode[k].regNum);
    832             if(indexT >= 0)
    833                 compileTable[indexT].refCount += infoByteCode[k].refCount;
    834         } //for k
    835 #ifdef DSE_OPT
    836         if(isDeadStmt) { //search compileTable
    837             getVirtualRegInfo(infoByteCode);
    838 #ifdef DEBUG_DSE
    839             ALOGI("DSE: stmt at offsetPC %d is dead", offsetPC);
    840 #endif
    841             for(k = 0; k < num_regs_per_bytecode; k++) {
    842                 int indexT = searchCompileTable(LowOpndRegType_virtual | infoByteCode[k].physicalType,
    843                                                 infoByteCode[k].regNum);
    844                 if(indexT >= 0)
    845                     compileTable[indexT].refCount -= infoByteCode[k].refCount;
    846             }
    847         }
    848 #endif
    849         lastByteCodeIsJump = false;
    850         if(!isConst && !isDeadStmt)  //isDeadStmt is false when DSE_OPT is not enabled
    851         {
    852 #ifdef DEBUG_COMPILE_TABLE
    853             dumpCompileTable();
    854 #endif
    855             globalShortMap = NULL;
    856             if(isCurrentByteCodeJump()) lastByteCodeIsJump = true;
    857             //lowerByteCode will call globalVREndOfBB if it is jump
    858             int retCode = lowerByteCodeJit(method, rPC, mir);
    859             if(gDvmJit.codeCacheByteUsed + (stream - streamStart) +
    860                  CODE_CACHE_PADDING > gDvmJit.codeCacheSize) {
    861                  ALOGE("JIT code cache full");
    862                  gDvmJit.codeCacheFull = true;
    863                  return -1;
    864             }
    865 
    866             if (retCode == 1) {
    867                 // We always fall back to the interpreter for OP_INVOKE_OBJECT_INIT_RANGE,
    868                 // but any other failure is unexpected and should be logged.
    869                 if (mir->dalvikInsn.opcode != OP_INVOKE_OBJECT_INIT_RANGE) {
    870                     ALOGE("JIT couldn't compile %s%s dex_pc=%d opcode=%d",
    871                           method->clazz->descriptor,
    872                           method->name,
    873                           offsetPC,
    874                           mir->dalvikInsn.opcode);
    875                 }
    876                 return -1;
    877             }
    878             updateConstInfo(bb);
    879             freeShortMap();
    880             if(retCode < 0) {
    881                 ALOGE("error in lowering the bytecode");
    882                 return retCode;
    883             }
    884             freeReg(true); //may dump GL VR to memory (this is necessary)
    885             //after each bytecode, make sure non-VRs have refCount of zero
    886             for(k = 0; k < num_compile_entries; k++) {
    887                 if(isTemporary(compileTable[k].physicalType, compileTable[k].regNum)) {
    888 #ifdef PRINT_WARNING
    889                     if(compileTable[k].refCount > 0) {
    890                         ALOGW("refCount for a temporary reg %d %d is %d after a bytecode", compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].refCount);
    891                     }
    892 #endif
    893                     compileTable[k].refCount = 0;
    894                 }
    895             }
    896         } else { //isConst || isDeadStmt
    897             //if this bytecode is the target of a jump, the mapFromBCtoNCG should be updated
    898             offsetNCG = stream - streamMethodStart;
    899             mapFromBCtoNCG[offsetPC] = offsetNCG;
    900 #ifdef DEBUG_COMPILE_TABLE
    901             ALOGI("this bytecode generates a constant and has no side effect");
    902 #endif
    903             freeReg(true); //may dump GL VR to memory (this is necessary)
    904         }
    905 #ifdef DEBUG_COMPILE_TABLE
    906         ALOGI("after one bytecode BB %d (num of VRs %d)", bb->bb_index, bb->num_regs);
    907 #endif
    908     }//for each bytecode
    909 #ifdef DEBUG_COMPILE_TABLE
    910     dumpCompileTable();
    911 #endif
    912     if(!lastByteCodeIsJump) constVREndOfBB();
    913     //at end of a basic block, get spilled GG VR & dump GL VR
    914     if(!lastByteCodeIsJump) globalVREndOfBB(method);
    915     //remove entries for temporary registers, L VR and GL VR
    916     int jj;
    917     for(k = 0; k < num_compile_entries; ) {
    918         bool removeEntry = false;
    919         if(isVirtualReg(compileTable[k].physicalType) && compileTable[k].gType != GLOBALTYPE_GG) {
    920             removeEntry = true;
    921         }
    922         if(isTemporary(compileTable[k].physicalType, compileTable[k].regNum))
    923             removeEntry = true;
    924         if(removeEntry) {
    925 #ifdef PRINT_WARNING
    926             if(compileTable[k].refCount > 0)
    927                 ALOGW("refCount for REG %d %d is %d at end of a basic block", compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].refCount);
    928 #endif
    929             compileTable[k].refCount = 0;
    930             for(jj = k+1; jj < num_compile_entries; jj++) {
    931                 compileTable[jj-1] = compileTable[jj];
    932             }
    933             num_compile_entries--;
    934         } else {
    935             k++;
    936         }
    937     }
    938     freeReg(true);
    939     //free LIVE TABLE
    940     for(k = 0; k < num_memory_vr; k++) {
    941         LiveRange* ptr2 = memVRTable[k].ranges;
    942         while(ptr2 != NULL) {
    943             LiveRange* tmpP = ptr2->next;
    944             free(ptr2->accessPC);
    945             free(ptr2);
    946             ptr2 = tmpP;
    947         }
    948     }
    949 #ifdef DEBUG_COMPILE_TABLE
    950     ALOGI("At end of basic block -------");
    951     dumpCompileTable();
    952 #endif
    953     return 0;
    954 }
    955 
    956 /** update infoBasicBlock & defUseTable
    957     input: currentInfo
    958     side effect: update currentInfo.reachingDefs
    959 
    960     update entries in infoBasicBlock by calling updateReachingDefA
    961     if there is no entry in infoBasicBlock for B, an entry will be created and inserted to infoBasicBlock
    962 
    963     defUseTable is updated to account for the access at currentInfo
    964     if accessType of B is U or UD, we call updateReachingDefB to update currentInfo.reachingDefs
    965         in order to correctly insert the usage to defUseTable
    966 */
    967 int mergeEntry2(BasicBlock_O1* bb) {
    968     LowOpndRegType typeB = currentInfo.physicalType;
    969     int regB = currentInfo.regNum;
    970     int jj, k;
    971     int jjend = bb->num_regs;
    972     bool isMerged = false;
    973     bool hasAlias = false;
    974     OverlapCase isBPartiallyOverlapA, isAPartiallyOverlapB;
    975     RegAccessType tmpType = REGACCESS_N;
    976     currentInfo.num_reaching_defs = 0;
    977 
    978     /* traverse variable A in infoBasicBlock */
    979     for(jj = 0; jj < jjend; jj++) {
    980         int regA = bb->infoBasicBlock[jj].regNum;
    981         LowOpndRegType typeA = bb->infoBasicBlock[jj].physicalType;
    982         isBPartiallyOverlapA = getBPartiallyOverlapA(regB, typeB, regA, typeA);
    983         isAPartiallyOverlapB = getAPartiallyOverlapB(regA, typeA, regB, typeB);
    984         if(regA == regB && typeA == typeB) {
    985             /* variable A and B are aligned */
    986             bb->infoBasicBlock[jj].accessType = mergeAccess2(bb->infoBasicBlock[jj].accessType, currentInfo.accessType,
    987                                                              OVERLAP_B_COVER_A);
    988             bb->infoBasicBlock[jj].refCount += currentInfo.refCount;
    989             /* copy reaching defs of variable B from variable A */
    990             currentInfo.num_reaching_defs = bb->infoBasicBlock[jj].num_reaching_defs;
    991             for(k = 0; k < currentInfo.num_reaching_defs; k++)
    992                 currentInfo.reachingDefs[k] = bb->infoBasicBlock[jj].reachingDefs[k];
    993             updateDefUseTable(); //use currentInfo to update defUseTable
    994             updateReachingDefA(jj, OVERLAP_B_COVER_A); //update reachingDefs of A
    995             isMerged = true;
    996             hasAlias = true;
    997             if(typeB == LowOpndRegType_gp) {
    998                 //merge allocConstraints
    999                 for(k = 0; k < 8; k++) {
   1000                     bb->infoBasicBlock[jj].allocConstraints[k].count += currentInfo.allocConstraints[k].count;
   1001                 }
   1002             }
   1003         }
   1004         else if(isBPartiallyOverlapA != OVERLAP_NO) {
   1005             tmpType = updateAccess2(tmpType, updateAccess1(bb->infoBasicBlock[jj].accessType, isAPartiallyOverlapB));
   1006             bb->infoBasicBlock[jj].accessType = mergeAccess2(bb->infoBasicBlock[jj].accessType, currentInfo.accessType,
   1007                                                              isBPartiallyOverlapA);
   1008 #ifdef DEBUG_MERGE_ENTRY
   1009             ALOGI("update accessType in case 2: VR %d %d accessType %d", regA, typeA, bb->infoBasicBlock[jj].accessType);
   1010 #endif
   1011             hasAlias = true;
   1012             if(currentInfo.accessType == REGACCESS_U || currentInfo.accessType == REGACCESS_UD) {
   1013                 /* update currentInfo.reachingDefs */
   1014                 updateReachingDefB1(jj);
   1015                 updateReachingDefB2();
   1016             }
   1017             updateReachingDefA(jj, isBPartiallyOverlapA);
   1018         }
   1019         else {
   1020             //even if B does not overlap with A, B can affect the reaching defs of A
   1021             //for example, B is a def of "v0", A is "v1"
   1022             //  B can kill some reaching defs of A or affect the accessType of a reaching def
   1023             updateReachingDefA(jj, OVERLAP_NO); //update reachingDefs of A
   1024         }
   1025     }//for each variable A in infoBasicBlock
   1026     if(!isMerged) {
   1027         /* create a new entry in infoBasicBlock */
   1028         bb->infoBasicBlock[bb->num_regs].refCount = currentInfo.refCount;
   1029         bb->infoBasicBlock[bb->num_regs].physicalType = typeB;
   1030         if(hasAlias)
   1031             bb->infoBasicBlock[bb->num_regs].accessType = updateAccess3(tmpType, currentInfo.accessType);
   1032         else
   1033             bb->infoBasicBlock[bb->num_regs].accessType = currentInfo.accessType;
   1034 #ifdef DEBUG_MERGE_ENTRY
   1035         ALOGI("update accessType in case 3: VR %d %d accessType %d", regB, typeB, bb->infoBasicBlock[bb->num_regs].accessType);
   1036 #endif
   1037         bb->infoBasicBlock[bb->num_regs].regNum = regB;
   1038         for(k = 0; k < 8; k++)
   1039             bb->infoBasicBlock[bb->num_regs].allocConstraints[k] = currentInfo.allocConstraints[k];
   1040 #ifdef DEBUG_MERGE_ENTRY
   1041         ALOGI("isMerged is false, call updateDefUseTable");
   1042 #endif
   1043         updateDefUseTable(); //use currentInfo to update defUseTable
   1044         updateReachingDefB3(); //update currentInfo.reachingDefs if currentInfo defines variable B
   1045 
   1046         //copy from currentInfo.reachingDefs to bb->infoBasicBlock[bb->num_regs]
   1047         bb->infoBasicBlock[bb->num_regs].num_reaching_defs = currentInfo.num_reaching_defs;
   1048         for(k = 0; k < currentInfo.num_reaching_defs; k++)
   1049             bb->infoBasicBlock[bb->num_regs].reachingDefs[k] = currentInfo.reachingDefs[k];
   1050 #ifdef DEBUG_MERGE_ENTRY
   1051         ALOGI("try to update reaching defs for VR %d %d", regB, typeB);
   1052         for(k = 0; k < bb->infoBasicBlock[bb->num_regs].num_reaching_defs; k++)
   1053             ALOGI("reaching def %d @ %d for VR %d %d access %d", k, currentInfo.reachingDefs[k].offsetPC,
   1054                   currentInfo.reachingDefs[k].regNum, currentInfo.reachingDefs[k].physicalType,
   1055                   currentInfo.reachingDefs[k].accessType);
   1056 #endif
   1057         bb->num_regs++;
   1058         if(bb->num_regs >= MAX_REG_PER_BASICBLOCK) {
   1059             ALOGE("too many VRs in a basic block");
   1060             dvmAbort();
   1061         }
   1062         return -1;
   1063     }
   1064     return 0;
   1065 }
   1066 
   1067 //!update reaching defs for infoBasicBlock[indexToA]
   1068 
   1069 //!use currentInfo.reachingDefs to update reaching defs for variable A
   1070 void updateReachingDefA(int indexToA, OverlapCase isBPartiallyOverlapA) {
   1071     if(indexToA < 0) return;
   1072     int k, k2;
   1073     OverlapCase isBPartiallyOverlapDef;
   1074     if(currentInfo.accessType == REGACCESS_U) {
   1075         return; //no update to reachingDefs of the VR
   1076     }
   1077     /* access in currentInfo is DU, D, or UD */
   1078     if(isBPartiallyOverlapA == OVERLAP_B_COVER_A) {
   1079         /* from this point on, the reachingDefs for variable A is a single def to currentInfo at offsetPC */
   1080         currentBB->infoBasicBlock[indexToA].num_reaching_defs = 1;
   1081         currentBB->infoBasicBlock[indexToA].reachingDefs[0].offsetPC = offsetPC;
   1082         currentBB->infoBasicBlock[indexToA].reachingDefs[0].regNum = currentInfo.regNum;
   1083         currentBB->infoBasicBlock[indexToA].reachingDefs[0].physicalType = currentInfo.physicalType;
   1084         currentBB->infoBasicBlock[indexToA].reachingDefs[0].accessType = REGACCESS_D;
   1085 #ifdef DEBUG_REACHING_DEF
   1086         ALOGI("single reaching def @ %d for VR %d %d", offsetPC, currentInfo.regNum, currentInfo.physicalType);
   1087 #endif
   1088         return;
   1089     }
   1090     /* update reachingDefs for variable A to get rid of dead defs */
   1091     /* Bug fix: it is possible that more than one reaching defs need to be removed
   1092                 after one reaching def is removed, num_reaching_defs--, but k should not change
   1093     */
   1094     for(k = 0; k < currentBB->infoBasicBlock[indexToA].num_reaching_defs; ) {
   1095         /* remove one reaching def in one interation of the loop */
   1096         //check overlapping between def & B
   1097         isBPartiallyOverlapDef = getBPartiallyOverlapA(currentInfo.regNum, currentInfo.physicalType,
   1098                                                        currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum,
   1099                                                        currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType);
   1100 #ifdef DEBUG_REACHING_DEF
   1101         ALOGI("DEBUG B %d %d def %d %d %d", currentInfo.regNum, currentInfo.physicalType,
   1102               currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum,
   1103               currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType,
   1104               currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType);
   1105 #endif
   1106         /* cases where one def nees to be removed:
   1107            if B fully covers def, def is removed
   1108            if B overlaps high half of def & def's accessType is H, def is removed
   1109            if B overlaps low half of def & def's accessType is L, def is removed
   1110         */
   1111         if((isBPartiallyOverlapDef == OVERLAP_B_COVER_HIGH_OF_A &&
   1112             currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType == REGACCESS_H) ||
   1113            (isBPartiallyOverlapDef == OVERLAP_B_COVER_LOW_OF_A &&
   1114             currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType == REGACCESS_L) ||
   1115            isBPartiallyOverlapDef == OVERLAP_B_COVER_A
   1116            ) { //remove def
   1117             //shift from k+1 to end
   1118             for(k2 = k+1; k2 < currentBB->infoBasicBlock[indexToA].num_reaching_defs; k2++)
   1119                 currentBB->infoBasicBlock[indexToA].reachingDefs[k2-1] = currentBB->infoBasicBlock[indexToA].reachingDefs[k2];
   1120             currentBB->infoBasicBlock[indexToA].num_reaching_defs--;
   1121         }
   1122         /*
   1123            if B overlaps high half of def & def's accessType is not H --> update accessType of def
   1124         */
   1125         else if(isBPartiallyOverlapDef == OVERLAP_B_COVER_HIGH_OF_A &&
   1126                 currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType != REGACCESS_H) {
   1127             //low half is still valid
   1128             if(getRegSize(currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType) == OpndSize_32)
   1129                 currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType = REGACCESS_D;
   1130             else
   1131                 currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType = REGACCESS_L;
   1132 #ifdef DEBUG_REACHING_DEF
   1133             ALOGI("DEBUG: set accessType of def to L");
   1134 #endif
   1135             k++;
   1136         }
   1137         /*
   1138            if B overlaps low half of def & def's accessType is not L --> update accessType of def
   1139         */
   1140         else if(isBPartiallyOverlapDef == OVERLAP_B_COVER_LOW_OF_A &&
   1141                 currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType != REGACCESS_L) {
   1142             //high half of def is still valid
   1143             currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType = REGACCESS_H;
   1144 #ifdef DEBUG_REACHING_DEF
   1145             ALOGI("DEBUG: set accessType of def to H");
   1146 #endif
   1147             k++;
   1148         }
   1149         else {
   1150             k++;
   1151         }
   1152     }//for k
   1153     if(isBPartiallyOverlapA != OVERLAP_NO) {
   1154         //insert the def to variable @ currentInfo
   1155         k = currentBB->infoBasicBlock[indexToA].num_reaching_defs;
   1156         if(k >= 3) {
   1157           ALOGE("more than 3 reaching defs");
   1158         }
   1159         currentBB->infoBasicBlock[indexToA].reachingDefs[k].offsetPC = offsetPC;
   1160         currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum = currentInfo.regNum;
   1161         currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType = currentInfo.physicalType;
   1162         currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType = REGACCESS_D;
   1163         currentBB->infoBasicBlock[indexToA].num_reaching_defs++;
   1164     }
   1165 #ifdef DEBUG_REACHING_DEF2
   1166     ALOGI("IN updateReachingDefA for VR %d %d", currentBB->infoBasicBlock[indexToA].regNum,
   1167           currentBB->infoBasicBlock[indexToA].physicalType);
   1168     for(k = 0; k < currentBB->infoBasicBlock[indexToA].num_reaching_defs; k++)
   1169         ALOGI("reaching def %d @ %d for VR %d %d access %d", k,
   1170               currentBB->infoBasicBlock[indexToA].reachingDefs[k].offsetPC,
   1171               currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum,
   1172               currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType,
   1173               currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType);
   1174 #endif
   1175 }
   1176 
   1177 /** Given a variable B @currentInfo,
   1178     updates its reaching defs by checking reaching defs of variable A @currentBB->infoBasicBlock[indexToA]
   1179     The result is stored in tmpInfo.reachingDefs
   1180 */
   1181 void updateReachingDefB1(int indexToA) {
   1182     if(indexToA < 0) return;
   1183     int k;
   1184     tmpInfo.num_reaching_defs = 0;
   1185     for(k = 0; k < currentBB->infoBasicBlock[indexToA].num_reaching_defs; k++) {
   1186         /* go through reachingDefs of variable A @currentBB->infoBasicBlock[indexToA]
   1187            for each def, check whether it overlaps with variable B @currentInfo
   1188                if the def overlaps with variable B, insert it to tmpInfo.reachingDefs
   1189         */
   1190         OverlapCase isDefPartiallyOverlapB = getAPartiallyOverlapB(
   1191                                                  currentBB->infoBasicBlock[indexToA].reachingDefs[k].regNum,
   1192                                                  currentBB->infoBasicBlock[indexToA].reachingDefs[k].physicalType,
   1193                                                  currentInfo.regNum, currentInfo.physicalType
   1194                                                  );
   1195         bool insert1 = false; //whether to insert the def to tmpInfo.reachingDefs
   1196         if(isDefPartiallyOverlapB == OVERLAP_ALIGN ||
   1197            isDefPartiallyOverlapB == OVERLAP_A_IS_LOW_OF_B ||
   1198            isDefPartiallyOverlapB == OVERLAP_A_IS_HIGH_OF_B) {
   1199             /* B aligns with def */
   1200             /* def is low half of B, def is high half of B
   1201                in these two cases, def is 32 bits */
   1202             insert1 = true;
   1203         }
   1204         RegAccessType deftype = currentBB->infoBasicBlock[indexToA].reachingDefs[k].accessType;
   1205         if(isDefPartiallyOverlapB == OVERLAP_B_IS_LOW_OF_A ||
   1206            isDefPartiallyOverlapB == OVERLAP_LOW_OF_A_IS_HIGH_OF_B) {
   1207             /* B is the low half of def */
   1208             /* the low half of def is the high half of B */
   1209             if(deftype != REGACCESS_H) insert1 = true;
   1210         }
   1211         if(isDefPartiallyOverlapB == OVERLAP_B_IS_HIGH_OF_A ||
   1212            isDefPartiallyOverlapB == OVERLAP_HIGH_OF_A_IS_LOW_OF_B) {
   1213             /* B is the high half of def */
   1214             /* the high half of def is the low half of B */
   1215             if(deftype != REGACCESS_L) insert1 = true;
   1216         }
   1217         if(insert1) {
   1218             if(tmpInfo.num_reaching_defs >= 3) {
   1219                 ALOGE("more than 3 reaching defs for tmpInfo");
   1220             }
   1221             tmpInfo.reachingDefs[tmpInfo.num_reaching_defs] = currentBB->infoBasicBlock[indexToA].reachingDefs[k];
   1222             tmpInfo.num_reaching_defs++;
   1223 #ifdef DEBUG_REACHING_DEF2
   1224             ALOGI("insert from entry %d %d: index %d", currentBB->infoBasicBlock[indexToA].regNum,
   1225                   currentBB->infoBasicBlock[indexToA].physicalType, k);
   1226 #endif
   1227         }
   1228     }
   1229 }
   1230 
   1231 /** update currentInfo.reachingDefs by merging currentInfo.reachingDefs with tmpInfo.reachingDefs
   1232 */
   1233 void updateReachingDefB2() {
   1234     int k, k2;
   1235     for(k2 = 0; k2 < tmpInfo.num_reaching_defs; k2++ ) {
   1236         bool merged = false;
   1237         for(k = 0; k < currentInfo.num_reaching_defs; k++) {
   1238             /* check whether it is the same def, if yes, do nothing */
   1239             if(currentInfo.reachingDefs[k].regNum == tmpInfo.reachingDefs[k2].regNum &&
   1240                currentInfo.reachingDefs[k].physicalType == tmpInfo.reachingDefs[k2].physicalType) {
   1241                 merged = true;
   1242                 if(currentInfo.reachingDefs[k].offsetPC != tmpInfo.reachingDefs[k2].offsetPC) {
   1243                     ALOGE("defs on the same VR %d %d with different offsetPC %d vs %d",
   1244                           currentInfo.reachingDefs[k].regNum, currentInfo.reachingDefs[k].physicalType,
   1245                           currentInfo.reachingDefs[k].offsetPC, tmpInfo.reachingDefs[k2].offsetPC);
   1246                 }
   1247                 if(currentInfo.reachingDefs[k].accessType != tmpInfo.reachingDefs[k2].accessType)
   1248                     ALOGE("defs on the same VR %d %d with different accessType",
   1249                           currentInfo.reachingDefs[k].regNum, currentInfo.reachingDefs[k].physicalType);
   1250                 break;
   1251             }
   1252         }
   1253         if(!merged) {
   1254             if(currentInfo.num_reaching_defs >= 3) {
   1255                ALOGE("more than 3 reaching defs for currentInfo");
   1256             }
   1257             currentInfo.reachingDefs[currentInfo.num_reaching_defs] = tmpInfo.reachingDefs[k2];
   1258             currentInfo.num_reaching_defs++;
   1259         }
   1260     }
   1261 }
   1262 
   1263 //!update currentInfo.reachingDefs with currentInfo if variable is defined in currentInfo
   1264 
   1265 //!
   1266 void updateReachingDefB3() {
   1267     if(currentInfo.accessType == REGACCESS_U) {
   1268         return; //no need to update currentInfo.reachingDefs
   1269     }
   1270     currentInfo.num_reaching_defs = 1;
   1271     currentInfo.reachingDefs[0].regNum = currentInfo.regNum;
   1272     currentInfo.reachingDefs[0].physicalType = currentInfo.physicalType;
   1273     currentInfo.reachingDefs[0].offsetPC = offsetPC;
   1274     currentInfo.reachingDefs[0].accessType = REGACCESS_D;
   1275 }
   1276 
   1277 /** update defUseTable by checking currentInfo
   1278 */
   1279 void updateDefUseTable() {
   1280     /* no access */
   1281     if(currentInfo.accessType == REGACCESS_N) return;
   1282     /* define then use, or define only */
   1283     if(currentInfo.accessType == REGACCESS_DU || currentInfo.accessType == REGACCESS_D) {
   1284         /* insert a definition at offsetPC to variable @ currentInfo */
   1285         DefUsePair* ptr = insertADef(offsetPC, currentInfo.regNum, currentInfo.physicalType, REGACCESS_D);
   1286         if(currentInfo.accessType != REGACCESS_D) {
   1287              /* if access is define then use, insert a use at offsetPC */
   1288             insertAUse(ptr, offsetPC, currentInfo.regNum, currentInfo.physicalType);
   1289         }
   1290         return;
   1291     }
   1292     /* use only or use then define
   1293        check the reaching defs for the usage */
   1294     int k;
   1295     bool isLCovered = false, isHCovered = false, isDCovered = false;
   1296     for(k = 0; k < currentInfo.num_reaching_defs; k++) {
   1297         /* insert a def currentInfo.reachingDefs[k] and a use of variable at offsetPC */
   1298         RegAccessType useType = insertDefUsePair(k);
   1299         if(useType == REGACCESS_D) isDCovered = true;
   1300         if(useType == REGACCESS_L) isLCovered = true;
   1301         if(useType == REGACCESS_H) isHCovered = true;
   1302     }
   1303     OpndSize useSize = getRegSize(currentInfo.physicalType);
   1304     if((!isDCovered) && (!isLCovered)) {
   1305         /* the low half of variable is not defined in the basic block
   1306            so insert a def to the low half at START of the basic block */
   1307         insertDefUsePair(-1);
   1308     }
   1309     if(useSize == OpndSize_64 && (!isDCovered) && (!isHCovered)) {
   1310         /* the high half of variable is not defined in the basic block
   1311            so insert a def to the high half at START of the basic block */
   1312         insertDefUsePair(-2);
   1313     }
   1314     if(currentInfo.accessType == REGACCESS_UD) {
   1315         /* insert a def at offsetPC to variable @ currentInfo */
   1316         insertADef(offsetPC, currentInfo.regNum, currentInfo.physicalType, REGACCESS_D);
   1317         return;
   1318     }
   1319 }
   1320 
   1321 //! insert a use at offsetPC of given variable at end of DefUsePair
   1322 
   1323 //!
   1324 RegAccessType insertAUse(DefUsePair* ptr, int offsetPC, int regNum, LowOpndRegType physicalType) {
   1325     DefOrUseLink* tLink = (DefOrUseLink*)malloc(sizeof(DefOrUseLink));
   1326     if(tLink == NULL) {
   1327         ALOGE("Memory allocation failed");
   1328         return REGACCESS_UNKNOWN;
   1329     }
   1330     tLink->offsetPC = offsetPC;
   1331     tLink->regNum = regNum;
   1332     tLink->physicalType = physicalType;
   1333     tLink->next = NULL;
   1334     if(ptr->useTail != NULL)
   1335         ptr->useTail->next = tLink;
   1336     ptr->useTail = tLink;
   1337     if(ptr->uses == NULL)
   1338         ptr->uses = tLink;
   1339     ptr->num_uses++;
   1340 
   1341     //check whether the def is partially overlapping with the variable
   1342     OverlapCase isDefPartiallyOverlapB = getBPartiallyOverlapA(ptr->def.regNum,
   1343                                                        ptr->def.physicalType,
   1344                                                        regNum, physicalType);
   1345     RegAccessType useType = setAccessTypeOfUse(isDefPartiallyOverlapB, ptr->def.accessType);
   1346     tLink->accessType = useType;
   1347     return useType;
   1348 }
   1349 
   1350 //! insert a def to currentBB->defUseTable
   1351 
   1352 //! update currentBB->defUseTail if necessary
   1353 DefUsePair* insertADef(int offsetPC, int regNum, LowOpndRegType pType, RegAccessType rType) {
   1354     DefUsePair* ptr = (DefUsePair*)malloc(sizeof(DefUsePair));
   1355     if(ptr == NULL) {
   1356         ALOGE("Memory allocation failed");
   1357         return NULL;
   1358     }
   1359     ptr->next = NULL;
   1360     ptr->def.offsetPC = offsetPC;
   1361     ptr->def.regNum = regNum;
   1362     ptr->def.physicalType = pType;
   1363     ptr->def.accessType = rType;
   1364     ptr->num_uses = 0;
   1365     ptr->useTail = NULL;
   1366     ptr->uses = NULL;
   1367     if(currentBB->defUseTail != NULL) {
   1368         currentBB->defUseTail->next = ptr;
   1369     }
   1370     currentBB->defUseTail = ptr;
   1371     if(currentBB->defUseTable == NULL)
   1372         currentBB->defUseTable = ptr;
   1373     currentBB->num_defs++;
   1374 #ifdef DEBUG_REACHING_DEF
   1375     ALOGI("insert a def at %d to defUseTable for VR %d %d", offsetPC,
   1376           regNum, pType);
   1377 #endif
   1378     return ptr;
   1379 }
   1380 
   1381 /** insert a def to defUseTable, then insert a use of variable @ currentInfo
   1382     if reachingDefIndex >= 0, the def is currentInfo.reachingDefs[index]
   1383     if reachingDefIndex is -1, the low half is defined at START of the basic block
   1384     if reachingDefIndex is -2, the high half is defined at START of the basic block
   1385 */
   1386 RegAccessType insertDefUsePair(int reachingDefIndex) {
   1387     int k = reachingDefIndex;
   1388     DefUsePair* tableIndex = NULL;
   1389     DefOrUse theDef;
   1390     theDef.regNum = 0;
   1391     if(k < 0) {
   1392         /* def at start of the basic blcok */
   1393         theDef.offsetPC = PC_FOR_START_OF_BB;
   1394         theDef.accessType = REGACCESS_D;
   1395         if(k == -1) //low half of variable
   1396             theDef.regNum = currentInfo.regNum;
   1397         if(k == -2) //high half of variable
   1398             theDef.regNum = currentInfo.regNum+1;
   1399         theDef.physicalType = LowOpndRegType_gp;
   1400     }
   1401     else {
   1402         theDef = currentInfo.reachingDefs[k];
   1403     }
   1404     tableIndex = searchDefUseTable(theDef.offsetPC, theDef.regNum, theDef.physicalType);
   1405     if(tableIndex == NULL) //insert an entry
   1406         tableIndex = insertADef(theDef.offsetPC, theDef.regNum, theDef.physicalType, theDef.accessType);
   1407     else
   1408         tableIndex->def.accessType = theDef.accessType;
   1409     RegAccessType useType = insertAUse(tableIndex, offsetPC, currentInfo.regNum, currentInfo.physicalType);
   1410     return useType;
   1411 }
   1412 
   1413 //! insert a XFER_MEM_TO_XMM to currentBB->xferPoints
   1414 
   1415 //!
   1416 void insertLoadXfer(int offset, int regNum, LowOpndRegType pType) {
   1417     //check whether it is already in currentBB->xferPoints
   1418     int k;
   1419     for(k = 0; k < currentBB->num_xfer_points; k++) {
   1420         if(currentBB->xferPoints[k].xtype == XFER_MEM_TO_XMM &&
   1421            currentBB->xferPoints[k].offsetPC == offset &&
   1422            currentBB->xferPoints[k].regNum == regNum &&
   1423            currentBB->xferPoints[k].physicalType == pType)
   1424             return;
   1425     }
   1426     currentBB->xferPoints[currentBB->num_xfer_points].xtype = XFER_MEM_TO_XMM;
   1427     currentBB->xferPoints[currentBB->num_xfer_points].regNum = regNum;
   1428     currentBB->xferPoints[currentBB->num_xfer_points].offsetPC = offset;
   1429     currentBB->xferPoints[currentBB->num_xfer_points].physicalType = pType;
   1430 #ifdef DEBUG_XFER_POINTS
   1431     ALOGI("insert to xferPoints %d: XFER_MEM_TO_XMM of VR %d %d at %d", currentBB->num_xfer_points, regNum, pType, offset);
   1432 #endif
   1433     currentBB->num_xfer_points++;
   1434     if(currentBB->num_xfer_points >= MAX_XFER_PER_BB) {
   1435         ALOGE("too many xfer points");
   1436         dvmAbort();
   1437     }
   1438 }
   1439 
   1440 /** update defUseTable by assuming a fake usage at END of a basic block for variable @ currentInfo
   1441     create a fake usage at end of a basic block for variable B (currentInfo.physicalType, currentInfo.regNum)
   1442     get reaching def info for variable B and store the info in currentInfo.reachingDefs
   1443         for each virtual register (variable A) accessed in the basic block
   1444             update reaching defs of B by checking reaching defs of variable A
   1445     update defUseTable
   1446 */
   1447 int fakeUsageAtEndOfBB(BasicBlock_O1* bb) {
   1448     currentInfo.accessType = REGACCESS_U;
   1449     LowOpndRegType typeB = currentInfo.physicalType;
   1450     int regB = currentInfo.regNum;
   1451     int jj, k;
   1452     currentInfo.num_reaching_defs = 0;
   1453     for(jj = 0; jj < bb->num_regs; jj++) {
   1454         int regA = bb->infoBasicBlock[jj].regNum;
   1455         LowOpndRegType typeA = bb->infoBasicBlock[jj].physicalType;
   1456         OverlapCase isBPartiallyOverlapA = getBPartiallyOverlapA(regB, typeB, regA, typeA);
   1457         if(regA == regB && typeA == typeB) {
   1458             /* copy reachingDefs from variable A */
   1459             currentInfo.num_reaching_defs = bb->infoBasicBlock[jj].num_reaching_defs;
   1460             for(k = 0; k < currentInfo.num_reaching_defs; k++)
   1461                 currentInfo.reachingDefs[k] = bb->infoBasicBlock[jj].reachingDefs[k];
   1462             break;
   1463         }
   1464         else if(isBPartiallyOverlapA != OVERLAP_NO) {
   1465             /* B overlaps with A */
   1466             /* update reaching defs of variable B by checking reaching defs of bb->infoBasicBlock[jj] */
   1467             updateReachingDefB1(jj);
   1468             updateReachingDefB2(); //merge currentInfo with tmpInfo
   1469         }
   1470     }
   1471     /* update defUseTable by checking currentInfo */
   1472     updateDefUseTable();
   1473     return 0;
   1474 }
   1475 
   1476 /** update xferPoints of currentBB
   1477     Traverse currentBB->defUseTable
   1478 */
   1479 int updateXferPoints() {
   1480     int k = 0;
   1481     currentBB->num_xfer_points = 0;
   1482     DefUsePair* ptr = currentBB->defUseTable;
   1483     DefOrUseLink* ptrUse = NULL;
   1484     /* traverse the def use chain of the basic block */
   1485     while(ptr != NULL) {
   1486         LowOpndRegType defType = ptr->def.physicalType;
   1487         //if definition is for a variable of 32 bits
   1488         if(getRegSize(defType) == OpndSize_32) {
   1489             /* check usages of the definition, whether it reaches a GPR, a XMM, a FS, or a SS */
   1490             bool hasGpUsage = false;
   1491             bool hasGpUsage2 = false; //not a fake usage
   1492             bool hasXmmUsage = false;
   1493             bool hasFSUsage = false;
   1494             bool hasSSUsage = false;
   1495             ptrUse = ptr->uses;
   1496             while(ptrUse != NULL) {
   1497                 if(ptrUse->physicalType == LowOpndRegType_gp) {
   1498                     hasGpUsage = true;
   1499                     if(ptrUse->offsetPC != PC_FOR_END_OF_BB)
   1500                         hasGpUsage2 = true;
   1501                 }
   1502                 if(ptrUse->physicalType == LowOpndRegType_ss) hasSSUsage = true;
   1503                 if(ptrUse->physicalType == LowOpndRegType_fs ||
   1504                    ptrUse->physicalType == LowOpndRegType_fs_s)
   1505                     hasFSUsage = true;
   1506                 if(ptrUse->physicalType == LowOpndRegType_xmm) {
   1507                     hasXmmUsage = true;
   1508                 }
   1509                 if(ptrUse->physicalType == LowOpndRegType_xmm ||
   1510                    ptrUse->physicalType == LowOpndRegType_ss) {
   1511                     /* if a 32-bit definition reaches a xmm usage or a SS usage,
   1512                        insert a XFER_MEM_TO_XMM */
   1513                     insertLoadXfer(ptrUse->offsetPC,
   1514                                    ptrUse->regNum, LowOpndRegType_xmm);
   1515                 }
   1516                 ptrUse = ptrUse->next;
   1517             }
   1518             if(((hasXmmUsage || hasFSUsage || hasSSUsage) && defType == LowOpndRegType_gp) ||
   1519                (hasGpUsage && defType == LowOpndRegType_fs) ||
   1520                (defType == LowOpndRegType_ss && (hasGpUsage || hasXmmUsage || hasFSUsage))) {
   1521                 /* insert a transfer if def is on a GPR, usage is on a XMM, FS or SS
   1522                                      if def is on a FS, usage is on a GPR
   1523                                      if def is on a SS, usage is on a GPR, XMM or FS
   1524                    transfer type is XFER_DEF_TO_GP_MEM if a real GPR usage exisits
   1525                    transfer type is XFER_DEF_TO_GP otherwise*/
   1526                 currentBB->xferPoints[currentBB->num_xfer_points].offsetPC = ptr->def.offsetPC;
   1527                 currentBB->xferPoints[currentBB->num_xfer_points].regNum = ptr->def.regNum;
   1528                 currentBB->xferPoints[currentBB->num_xfer_points].physicalType = ptr->def.physicalType;
   1529                 if(hasGpUsage2) { //create an entry XFER_DEF_TO_GP_MEM
   1530                     currentBB->xferPoints[currentBB->num_xfer_points].xtype = XFER_DEF_TO_GP_MEM;
   1531                 }
   1532                 else { //create an entry XFER_DEF_TO_MEM
   1533                     currentBB->xferPoints[currentBB->num_xfer_points].xtype = XFER_DEF_TO_MEM;
   1534                 }
   1535                 currentBB->xferPoints[currentBB->num_xfer_points].tableIndex = k;
   1536 #ifdef DEBUG_XFER_POINTS
   1537                 ALOGI("insert XFER %d at def %d: V%d %d", currentBB->num_xfer_points, ptr->def.offsetPC, ptr->def.regNum, defType);
   1538 #endif
   1539                 currentBB->num_xfer_points++;
   1540                 if(currentBB->num_xfer_points >= MAX_XFER_PER_BB) {
   1541                     ALOGE("too many xfer points");
   1542                     dvmAbort();
   1543                 }
   1544             }
   1545         }
   1546         else { /* def is on 64 bits */
   1547             bool hasGpUsageOfL = false; //exist a GPR usage of the low half
   1548             bool hasGpUsageOfH = false; //exist a GPR usage of the high half
   1549             bool hasGpUsageOfL2 = false;
   1550             bool hasGpUsageOfH2 = false;
   1551             bool hasMisaligned = false;
   1552             bool hasAligned = false;
   1553             bool hasFSUsage = false;
   1554             bool hasSSUsage = false;
   1555             ptrUse = ptr->uses;
   1556             while(ptrUse != NULL) {
   1557                 if(ptrUse->physicalType == LowOpndRegType_gp &&
   1558                    ptrUse->regNum == ptr->def.regNum) {
   1559                     hasGpUsageOfL = true;
   1560                     if(ptrUse->offsetPC != PC_FOR_END_OF_BB)
   1561                         hasGpUsageOfL2 = true;
   1562                 }
   1563                 if(ptrUse->physicalType == LowOpndRegType_gp &&
   1564                    ptrUse->regNum == ptr->def.regNum + 1) {
   1565                     hasGpUsageOfH = true;
   1566                     if(ptrUse->offsetPC != PC_FOR_END_OF_BB)
   1567                         hasGpUsageOfH2 = true;
   1568                 }
   1569                 if(ptrUse->physicalType == LowOpndRegType_xmm &&
   1570                    ptrUse->regNum == ptr->def.regNum) {
   1571                     hasAligned = true;
   1572                     /* if def is on FS and use is on XMM, insert a XFER_MEM_TO_XMM */
   1573                     if(defType == LowOpndRegType_fs)
   1574                         insertLoadXfer(ptrUse->offsetPC,
   1575                                        ptrUse->regNum, LowOpndRegType_xmm);
   1576                 }
   1577                 if(ptrUse->physicalType == LowOpndRegType_fs ||
   1578                    ptrUse->physicalType == LowOpndRegType_fs_s)
   1579                     hasFSUsage = true;
   1580                 if(ptrUse->physicalType == LowOpndRegType_xmm &&
   1581                    ptrUse->regNum != ptr->def.regNum) {
   1582                     hasMisaligned = true;
   1583                     /* if use is on XMM and use and def are misaligned, insert a XFER_MEM_TO_XMM */
   1584                     insertLoadXfer(ptrUse->offsetPC,
   1585                                    ptrUse->regNum, LowOpndRegType_xmm);
   1586                 }
   1587                 if(ptrUse->physicalType == LowOpndRegType_ss) {
   1588                     hasSSUsage = true;
   1589                     /* if use is on SS, insert a XFER_MEM_TO_XMM */
   1590                     insertLoadXfer(ptrUse->offsetPC,
   1591                                    ptrUse->regNum, LowOpndRegType_ss);
   1592                 }
   1593                 ptrUse = ptrUse->next;
   1594             }
   1595             if(defType == LowOpndRegType_fs && !hasGpUsageOfL && !hasGpUsageOfH) {
   1596                 ptr = ptr->next;
   1597                 continue;
   1598             }
   1599             if(defType == LowOpndRegType_xmm && !hasFSUsage &&
   1600                !hasGpUsageOfL && !hasGpUsageOfH && !hasMisaligned && !hasSSUsage) {
   1601                 ptr = ptr->next;
   1602                 continue;
   1603             }
   1604             /* insert a XFER_DEF_IS_XMM */
   1605             currentBB->xferPoints[currentBB->num_xfer_points].regNum = ptr->def.regNum;
   1606             currentBB->xferPoints[currentBB->num_xfer_points].offsetPC = ptr->def.offsetPC;
   1607             currentBB->xferPoints[currentBB->num_xfer_points].physicalType = ptr->def.physicalType;
   1608             currentBB->xferPoints[currentBB->num_xfer_points].xtype = XFER_DEF_IS_XMM;
   1609             currentBB->xferPoints[currentBB->num_xfer_points].vr_gpl = -1;
   1610             currentBB->xferPoints[currentBB->num_xfer_points].vr_gph = -1;
   1611             if(hasGpUsageOfL2) currentBB->xferPoints[currentBB->num_xfer_points].vr_gpl = ptr->def.regNum;
   1612             if(hasGpUsageOfH2) currentBB->xferPoints[currentBB->num_xfer_points].vr_gph = ptr->def.regNum+1;
   1613             currentBB->xferPoints[currentBB->num_xfer_points].dumpToMem = true;
   1614             currentBB->xferPoints[currentBB->num_xfer_points].dumpToXmm = false; //not used in updateVirtualReg
   1615             if(hasAligned) currentBB->xferPoints[currentBB->num_xfer_points].dumpToXmm = true;
   1616             currentBB->xferPoints[currentBB->num_xfer_points].tableIndex = k;
   1617 #ifdef DEBUG_XFER_POINTS
   1618             ALOGI("insert XFER %d at def %d: V%d %d", currentBB->num_xfer_points, ptr->def.offsetPC, ptr->def.regNum, defType);
   1619 #endif
   1620             currentBB->num_xfer_points++;
   1621             if(currentBB->num_xfer_points >= MAX_XFER_PER_BB) {
   1622                 ALOGE("too many xfer points");
   1623                 dvmAbort();
   1624             }
   1625         }
   1626         ptr = ptr->next;
   1627     } //while ptr
   1628 #ifdef DEBUG_XFER_POINTS
   1629     ALOGI("XFER points for current basic block ------");
   1630     for(k = 0; k < currentBB->num_xfer_points; k++) {
   1631         ALOGI("  at offset %x, VR %d %d: type %d, vr_gpl %d, vr_gph %d, dumpToMem %d, dumpToXmm %d",
   1632               currentBB->xferPoints[k].offsetPC, currentBB->xferPoints[k].regNum,
   1633               currentBB->xferPoints[k].physicalType, currentBB->xferPoints[k].xtype,
   1634               currentBB->xferPoints[k].vr_gpl, currentBB->xferPoints[k].vr_gph,
   1635               currentBB->xferPoints[k].dumpToMem, currentBB->xferPoints[k].dumpToXmm);
   1636     }
   1637 #endif
   1638     return -1;
   1639 }
   1640 
   1641 //! update memVRTable[].ranges by browsing the defUseTable
   1642 
   1643 //! each virtual register has a list of live ranges, and each live range has a list of PCs that access the VR
   1644 void updateLiveTable() {
   1645     DefUsePair* ptr = currentBB->defUseTable;
   1646     while(ptr != NULL) {
   1647         bool updateUse = false;
   1648         if(ptr->num_uses == 0) {
   1649             ptr->num_uses = 1;
   1650             ptr->uses = (DefOrUseLink*)malloc(sizeof(DefOrUseLink));
   1651             if(ptr->uses == NULL) {
   1652                 ALOGE("Memory allocation failed");
   1653                 return;
   1654             }
   1655             ptr->uses->accessType = REGACCESS_D;
   1656             ptr->uses->regNum = ptr->def.regNum;
   1657             ptr->uses->offsetPC = ptr->def.offsetPC;
   1658             ptr->uses->physicalType = ptr->def.physicalType;
   1659             ptr->uses->next = NULL;
   1660             ptr->useTail = ptr->uses;
   1661             updateUse = true;
   1662         }
   1663         DefOrUseLink* ptrUse = ptr->uses;
   1664         while(ptrUse != NULL) {
   1665             RegAccessType useType = ptrUse->accessType;
   1666             if(useType == REGACCESS_L || useType == REGACCESS_D) {
   1667                 int indexL = searchMemTable(ptrUse->regNum);
   1668                 if(indexL >= 0)
   1669                     mergeLiveRange(indexL, ptr->def.offsetPC,
   1670                                    ptrUse->offsetPC); //tableIndex, start PC, end PC
   1671             }
   1672             if(getRegSize(ptrUse->physicalType) == OpndSize_64 &&
   1673                (useType == REGACCESS_H || useType == REGACCESS_D)) {
   1674                 int indexH = searchMemTable(ptrUse->regNum+1);
   1675                 if(indexH >= 0)
   1676                     mergeLiveRange(indexH, ptr->def.offsetPC,
   1677                                    ptrUse->offsetPC);
   1678             }
   1679             ptrUse = ptrUse->next;
   1680         }//while ptrUse
   1681         if(updateUse) {
   1682             ptr->num_uses = 0;
   1683             free(ptr->uses);
   1684             ptr->uses = NULL;
   1685             ptr->useTail = NULL;
   1686         }
   1687         ptr = ptr->next;
   1688     }//while ptr
   1689 #ifdef DEBUG_LIVE_RANGE
   1690     ALOGI("LIVE TABLE");
   1691     for(int k = 0; k < num_memory_vr; k++) {
   1692         ALOGI("VR %d live ", memVRTable[k].regNum);
   1693         LiveRange* ptr = memVRTable[k].ranges;
   1694         while(ptr != NULL) {
   1695             ALOGI("[%x %x] (", ptr->start, ptr->end);
   1696             for(int k3 = 0; k3 < ptr->num_access; k3++)
   1697                 ALOGI("%x ", ptr->accessPC[k3]);
   1698             ALOGI(") ");
   1699             ptr = ptr->next;
   1700         }
   1701         ALOGI("");
   1702     }
   1703 #endif
   1704 }
   1705 
   1706 //!add a live range [rangeStart, rangeEnd] to ranges of memVRTable, merge to existing live ranges if necessary
   1707 
   1708 //!ranges are in increasing order of startPC
   1709 void mergeLiveRange(int tableIndex, int rangeStart, int rangeEnd) {
   1710     if(rangeStart == PC_FOR_START_OF_BB) rangeStart = currentBB->pc_start;
   1711     if(rangeEnd == PC_FOR_END_OF_BB) rangeEnd = currentBB->pc_end;
   1712 #ifdef DEBUG_LIVE_RANGE
   1713     ALOGI("LIVERANGE call mergeLiveRange on tableIndex %d with [%x %x]", tableIndex, rangeStart, rangeEnd);
   1714 #endif
   1715     int startIndex = -1, endIndex = -1;
   1716     bool startBeforeRange = false, endBeforeRange = false; //before the index or in the range
   1717     bool startDone = false, endDone = false;
   1718     LiveRange* ptr = memVRTable[tableIndex].ranges;
   1719     LiveRange* ptrStart = NULL;
   1720     LiveRange* ptrStart_prev = NULL;
   1721     LiveRange* ptrEnd = NULL;
   1722     LiveRange* ptrEnd_prev = NULL;
   1723     int k = 0;
   1724     while(ptr != NULL) {
   1725         if(!startDone) {
   1726             if(ptr->start <= rangeStart &&
   1727                ptr->end >= rangeStart) {
   1728                 startIndex = k;
   1729                 ptrStart = ptr;
   1730                 startBeforeRange = false;
   1731                 startDone = true;
   1732             }
   1733             else if(ptr->start > rangeStart) {
   1734                 startIndex = k;
   1735                 ptrStart = ptr;
   1736                 startBeforeRange = true;
   1737                 startDone = true;
   1738             }
   1739         }
   1740         if(!startDone) ptrStart_prev = ptr;
   1741         if(!endDone) {
   1742             if(ptr->start <= rangeEnd &&
   1743                ptr->end >= rangeEnd) {
   1744                 endIndex = k;
   1745                 ptrEnd = ptr;
   1746                 endBeforeRange = false;
   1747                 endDone = true;
   1748             }
   1749             else if(ptr->start > rangeEnd) {
   1750                 endIndex = k;
   1751                 ptrEnd = ptr;
   1752                 endBeforeRange = true;
   1753                 endDone = true;
   1754             }
   1755         }
   1756         if(!endDone) ptrEnd_prev = ptr;
   1757         ptr = ptr->next;
   1758         k++;
   1759     } //while
   1760     if(!startDone) { //both can be NULL
   1761         startIndex = memVRTable[tableIndex].num_ranges;
   1762         ptrStart = NULL; //ptrStart_prev should be the last live range
   1763         startBeforeRange = true;
   1764     }
   1765     //if endDone, ptrEnd is not NULL, ptrEnd_prev can be NULL
   1766     if(!endDone) { //both can be NULL
   1767         endIndex = memVRTable[tableIndex].num_ranges;
   1768         ptrEnd = NULL;
   1769         endBeforeRange = true;
   1770     }
   1771     if(startIndex == endIndex && startBeforeRange && endBeforeRange) { //insert at startIndex
   1772         //3 cases depending on BeforeRange when startIndex == endIndex
   1773         //insert only if both true
   1774         //merge otherwise
   1775         /////////// insert before ptrStart
   1776         LiveRange* currRange = (LiveRange *)malloc(sizeof(LiveRange));
   1777         if(ptrStart_prev == NULL) {
   1778             currRange->next = memVRTable[tableIndex].ranges;
   1779             memVRTable[tableIndex].ranges = currRange;
   1780         } else {
   1781             currRange->next = ptrStart_prev->next;
   1782             ptrStart_prev->next = currRange;
   1783         }
   1784         currRange->start = rangeStart;
   1785         currRange->end = rangeEnd;
   1786         currRange->accessPC = (int *)malloc(sizeof(int) * NUM_ACCESS_IN_LIVERANGE);
   1787         currRange->num_alloc = NUM_ACCESS_IN_LIVERANGE;
   1788         if(rangeStart != rangeEnd) {
   1789             currRange->num_access = 2;
   1790             currRange->accessPC[0] = rangeStart;
   1791             currRange->accessPC[1] = rangeEnd;
   1792         } else {
   1793             currRange->num_access = 1;
   1794             currRange->accessPC[0] = rangeStart;
   1795         }
   1796         memVRTable[tableIndex].num_ranges++;
   1797 #ifdef DEBUG_LIVE_RANGE
   1798         ALOGI("LIVERANGE insert one live range [%x %x] to tableIndex %d", rangeStart, rangeEnd, tableIndex);
   1799 #endif
   1800         return;
   1801     }
   1802     if(!endBeforeRange) { //here ptrEnd is not NULL
   1803         endIndex++; //next
   1804         ptrEnd_prev = ptrEnd; //ptrEnd_prev is not NULL
   1805         ptrEnd = ptrEnd->next; //ptrEnd can be NULL
   1806     }
   1807     if(endIndex < startIndex+1) ALOGE("mergeLiveRange endIndex %d startIndex %d", endIndex, startIndex);
   1808     ///////// use ptrStart & ptrEnd_prev
   1809     if(ptrStart == NULL || ptrEnd_prev == NULL) {
   1810         ALOGE("mergeLiveRange ptr is NULL");
   1811         return;
   1812     }
   1813     //endIndex > startIndex (merge the ranges between startIndex and endIndex-1)
   1814     //update ptrStart
   1815     if(ptrStart->start > rangeStart)
   1816         ptrStart->start = rangeStart; //min of old start & rangeStart
   1817     ptrStart->end = ptrEnd_prev->end; //max of old end & rangeEnd
   1818     if(rangeEnd > ptrStart->end)
   1819         ptrStart->end = rangeEnd;
   1820 #ifdef DEBUG_LIVE_RANGE
   1821     ALOGI("LIVERANGE merge entries for tableIndex %d from %d to %d", tableIndex, startIndex+1, endIndex-1);
   1822 #endif
   1823     if(ptrStart->num_access <= 0) ALOGE("mergeLiveRange number of access");
   1824 #ifdef DEBUG_LIVE_RANGE
   1825     ALOGI("LIVERANGE tableIndex %d startIndex %d num_access %d (", tableIndex, startIndex, ptrStart->num_access);
   1826     for(k = 0; k < ptrStart->num_access; k++)
   1827         ALOGI("%x ", ptrStart->accessPC[k]);
   1828     ALOGI(")");
   1829 #endif
   1830     ///// go through pointers from ptrStart->next to ptrEnd
   1831     //from startIndex+1 to endIndex-1
   1832     ptr = ptrStart->next;
   1833     while(ptr != NULL && ptr != ptrEnd) {
   1834         int k2;
   1835         for(k2 = 0; k2 < ptr->num_access; k2++) { //merge to startIndex
   1836             insertAccess(tableIndex, ptrStart, ptr->accessPC[k2]);
   1837         }//k2
   1838         ptr = ptr->next;
   1839     }
   1840     insertAccess(tableIndex, ptrStart, rangeStart);
   1841     insertAccess(tableIndex, ptrStart, rangeEnd);
   1842     //remove startIndex+1 to endIndex-1
   1843     if(startIndex+1 < endIndex) {
   1844         ptr = ptrStart->next;
   1845         while(ptr != NULL && ptr != ptrEnd) {
   1846             LiveRange* tmpP = ptr->next;
   1847             free(ptr->accessPC);
   1848             free(ptr);
   1849             ptr = tmpP;
   1850         }
   1851         ptrStart->next = ptrEnd;
   1852     }
   1853     memVRTable[tableIndex].num_ranges -= (endIndex - startIndex - 1);
   1854 #ifdef DEBUG_LIVE_RANGE
   1855     ALOGI("num_ranges for VR %d: %d", memVRTable[tableIndex].regNum, memVRTable[tableIndex].num_ranges);
   1856 #endif
   1857 }
   1858 //! insert an access to a given live range, in order
   1859 
   1860 //!
   1861 void insertAccess(int tableIndex, LiveRange* startP, int rangeStart) {
   1862     int k3, k4;
   1863 #ifdef DEBUG_LIVE_RANGE
   1864     ALOGI("LIVERANGE insertAccess %d %x", tableIndex, rangeStart);
   1865 #endif
   1866     int insertIndex = -1;
   1867     for(k3 = 0; k3 < startP->num_access; k3++) {
   1868         if(startP->accessPC[k3] == rangeStart) {
   1869             return;
   1870         }
   1871         if(startP->accessPC[k3] > rangeStart) {
   1872             insertIndex = k3;
   1873             break;
   1874         }
   1875     }
   1876 
   1877     //insert here
   1878     k3 = insertIndex;
   1879     if(insertIndex == -1) {
   1880         k3 = startP->num_access;
   1881     }
   1882     if(startP->num_access == startP->num_alloc) {
   1883         int currentAlloc = startP->num_alloc;
   1884         startP->num_alloc += NUM_ACCESS_IN_LIVERANGE;
   1885         int* tmpPtr = (int *)malloc(sizeof(int) * startP->num_alloc);
   1886         for(k4 = 0; k4 < currentAlloc; k4++)
   1887             tmpPtr[k4] = startP->accessPC[k4];
   1888         free(startP->accessPC);
   1889         startP->accessPC = tmpPtr;
   1890     }
   1891     //insert accessPC
   1892     for(k4 = startP->num_access-1; k4 >= k3; k4--)
   1893         startP->accessPC[k4+1] = startP->accessPC[k4];
   1894     startP->accessPC[k3] = rangeStart;
   1895 #ifdef DEBUG_LIVE_RANGE
   1896     ALOGI("LIVERANGE insert %x to tableIndex %d", rangeStart, tableIndex);
   1897 #endif
   1898     startP->num_access++;
   1899     return;
   1900 }
   1901 
   1902 /////////////////////////////////////////////////////////////////////
   1903 bool isInMemory(int regNum, OpndSize size);
   1904 void setVRToMemory(int regNum, OpndSize size);
   1905 bool isVRLive(int vA);
   1906 int getSpillIndex(bool isGLUE, OpndSize size);
   1907 void clearVRToMemory(int regNum, OpndSize size);
   1908 void clearVRNullCheck(int regNum, OpndSize size);
   1909 
   1910 inline int getSpillLocDisp(int offset) {
   1911 #ifdef SPILL_IN_THREAD
   1912     return offset+offsetof(Thread, spillRegion);;
   1913 #else
   1914     return offset+offEBP_spill;
   1915 #endif
   1916 }
   1917 #if 0
   1918 /* used if we keep self pointer in a physical register */
   1919 inline int getSpillLocReg(int offset) {
   1920     return PhysicalReg_Glue;
   1921 }
   1922 #endif
   1923 #ifdef SPILL_IN_THREAD
   1924 inline void loadFromSpillRegion_with_self(OpndSize size, int reg_self, bool selfPhysical, int reg, int offset) {
   1925     /* only 1 instruction is generated by move_mem_to_reg_noalloc */
   1926     move_mem_to_reg_noalloc(size,
   1927                             getSpillLocDisp(offset), reg_self, selfPhysical,
   1928                             MemoryAccess_SPILL, offset,
   1929                             reg, true);
   1930 }
   1931 inline void loadFromSpillRegion(OpndSize size, int reg, int offset) {
   1932     get_self_pointer(C_SCRATCH_1, isScratchPhysical);
   1933     int reg_self = registerAlloc(LowOpndRegType_scratch, C_SCRATCH_1, isScratchPhysical, false);
   1934     /* only 1 instruction is generated by move_mem_to_reg_noalloc */
   1935     move_mem_to_reg_noalloc(size,
   1936                             getSpillLocDisp(offset), reg_self, true,
   1937                             MemoryAccess_SPILL, offset,
   1938                             reg, true);
   1939 }
   1940 inline void saveToSpillRegion_with_self(OpndSize size, int selfReg, bool selfPhysical, int reg, int offset) {
   1941     move_reg_to_mem_noalloc(size,
   1942                             reg, true,
   1943                             getSpillLocDisp(offset), selfReg, selfPhysical,
   1944                             MemoryAccess_SPILL, offset);
   1945 }
   1946 inline void saveToSpillRegion(OpndSize size, int reg, int offset) {
   1947     get_self_pointer(C_SCRATCH_1, isScratchPhysical);
   1948     int reg_self = registerAlloc(LowOpndRegType_scratch, C_SCRATCH_1, isScratchPhysical, false);
   1949     move_reg_to_mem_noalloc(size,
   1950                             reg, true,
   1951                             getSpillLocDisp(offset), reg_self, true,
   1952                             MemoryAccess_SPILL, offset);
   1953 }
   1954 #else
   1955 inline void loadFromSpillRegion(OpndSize size, int reg, int offset) {
   1956     /* only 1 instruction is generated by move_mem_to_reg_noalloc */
   1957     move_mem_to_reg_noalloc(size,
   1958                             getSpillLocDisp(offset), PhysicalReg_EBP, true,
   1959                             MemoryAccess_SPILL, offset,
   1960                             reg, true);
   1961 }
   1962 inline void saveToSpillRegion(OpndSize size, int reg, int offset) {
   1963     move_reg_to_mem_noalloc(size,
   1964                             reg, true,
   1965                             getSpillLocDisp(offset), PhysicalReg_EBP, true,
   1966                             MemoryAccess_SPILL, offset);
   1967 }
   1968 #endif
   1969 
   1970 //! dump an immediate to memory, set inMemory to true
   1971 
   1972 //!
   1973 void dumpImmToMem(int vrNum, OpndSize size, int value) {
   1974     if(isInMemory(vrNum, size)) {
   1975 #ifdef DEBUG_SPILL
   1976         ALOGI("Skip dumpImmToMem vA %d size %d", vrNum, size);
   1977 #endif
   1978         return;
   1979     }
   1980     set_VR_to_imm_noalloc(vrNum, size, value);
   1981     setVRToMemory(vrNum, size);
   1982 }
   1983 //! dump content of a VR to memory, set inMemory to true
   1984 
   1985 //!
   1986 void dumpToMem(int vrNum, LowOpndRegType type, int regAll) { //ss,gp,xmm
   1987     if(isInMemory(vrNum, getRegSize(type))) {
   1988 #ifdef DEBUG_SPILL
   1989         ALOGI("Skip dumpToMem vA %d type %d", vrNum, type);
   1990 #endif
   1991         return;
   1992     }
   1993     if(type == LowOpndRegType_gp || type == LowOpndRegType_xmm)
   1994         set_virtual_reg_noalloc(vrNum, getRegSize(type), regAll, true);
   1995     if(type == LowOpndRegType_ss)
   1996         move_ss_reg_to_mem_noalloc(regAll, true,
   1997                                    4*vrNum, PhysicalReg_FP, true,
   1998                                    MemoryAccess_VR, vrNum);
   1999     setVRToMemory(vrNum, getRegSize(type));
   2000 }
   2001 //! dump part of a 64-bit VR to memory and update inMemory
   2002 
   2003 //! isLow tells whether low half or high half is dumped
   2004 void dumpPartToMem(int reg /*xmm physical reg*/, int vA, bool isLow) {
   2005     if(isLow) {
   2006         if(isInMemory(vA, OpndSize_32)) {
   2007 #ifdef DEBUG_SPILL
   2008             ALOGI("Skip dumpPartToMem isLow %d vA %d", isLow, vA);
   2009 #endif
   2010             return;
   2011         }
   2012     }
   2013     else {
   2014         if(isInMemory(vA+1, OpndSize_32)) {
   2015 #ifdef DEBUG_SPILL
   2016             ALOGI("Skip dumpPartToMem isLow %d vA %d", isLow, vA);
   2017 #endif
   2018             return;
   2019         }
   2020     }
   2021     if(isLow) {
   2022         if(!isVRLive(vA)) return;
   2023     }
   2024     else {
   2025         if(!isVRLive(vA+1)) return;
   2026     }
   2027     //move part to vA or vA+1
   2028     if(isLow) {
   2029         move_ss_reg_to_mem_noalloc(reg, true,
   2030                                    4*vA, PhysicalReg_FP, true, MemoryAccess_VR, vA);
   2031     } else {
   2032         int k = getSpillIndex(false, OpndSize_64);
   2033         //H, L in 4*k+4 & 4*k
   2034 #ifdef SPILL_IN_THREAD
   2035         get_self_pointer(PhysicalReg_SCRATCH_1, isScratchPhysical);
   2036         saveToSpillRegion_with_self(OpndSize_64, PhysicalReg_SCRATCH_1, isScratchPhysical, reg, 4*k);
   2037         //update low 32 bits of xmm reg from 4*k+4
   2038         move_ss_mem_to_reg(NULL,
   2039                                    getSpillLocDisp(4*k+4), PhysicalReg_SCRATCH_1, isScratchPhysical,
   2040                                    reg, true);
   2041 #else
   2042         saveToSpillRegion(OpndSize_64, reg, 4*k);
   2043         //update low 32 bits of xmm reg from 4*k+4
   2044         move_ss_mem_to_reg_noalloc(
   2045                                    getSpillLocDisp(4*k+4), PhysicalReg_EBP, true,
   2046                                    MemoryAccess_SPILL, 4*k+4,
   2047                                    reg, true);
   2048 #endif
   2049         //move low 32 bits of xmm reg to vA+1
   2050         move_ss_reg_to_mem_noalloc(reg, true, 4*(vA+1), PhysicalReg_FP, true, MemoryAccess_VR, vA+1);
   2051     }
   2052     if(isLow)
   2053         setVRToMemory(vA, OpndSize_32);
   2054     else
   2055         setVRToMemory(vA+1, OpndSize_32);
   2056 }
   2057 void clearVRBoundCheck(int regNum, OpndSize size);
   2058 //! the content of a VR is no longer in memory or in physical register if the latest content of a VR is constant
   2059 
   2060 //! clear nullCheckDone; if another VR is overlapped with the given VR, the content of that VR is no longer in physical register
   2061 void invalidateVRDueToConst(int reg, OpndSize size) {
   2062     clearVRToMemory(reg, size); //memory content is out-dated
   2063     clearVRNullCheck(reg, size);
   2064     clearVRBoundCheck(reg, size);
   2065     //check reg,gp reg,ss reg,xmm reg-1,xmm
   2066     //if size is 64: check reg+1,gp|ss reg+1,xmm
   2067     int index;
   2068     //if VR is xmm, check whether we need to dump part of VR to memory
   2069     index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg);
   2070     if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2071 #ifdef DEBUG_INVALIDATE
   2072         ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_xmm);
   2073 #endif
   2074         if(size == OpndSize_32)
   2075             dumpPartToMem(compileTable[index].physicalReg, reg, false); //dump high of xmm to memory
   2076         compileTable[index].physicalReg = PhysicalReg_Null;
   2077     }
   2078     index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg-1);
   2079     if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2080 #ifdef DEBUG_INVALIDATE
   2081         ALOGI("INVALIDATE virtual reg %d type %d", reg-1, LowOpndRegType_xmm);
   2082 #endif
   2083         dumpPartToMem(compileTable[index].physicalReg, reg-1, true); //dump low of xmm to memory
   2084         compileTable[index].physicalReg = PhysicalReg_Null;
   2085     }
   2086     index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, reg);
   2087     if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2088 #ifdef DEBUG_INVALIDATE
   2089         ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_gp);
   2090 #endif
   2091         compileTable[index].physicalReg = PhysicalReg_Null;
   2092     }
   2093     index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_ss, reg);
   2094     if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2095 #ifdef DEBUG_INVALIDATE
   2096         ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_ss);
   2097 #endif
   2098         compileTable[index].physicalReg = PhysicalReg_Null;
   2099     }
   2100     if(size == OpndSize_64) {
   2101         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg+1);
   2102         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2103 #ifdef DEBUG_INVALIDATE
   2104             ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_xmm);
   2105 #endif
   2106             dumpPartToMem(compileTable[index].physicalReg, reg+1, false); //dump high of xmm to memory
   2107             compileTable[index].physicalReg = PhysicalReg_Null;
   2108         }
   2109         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, reg+1);
   2110         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2111 #ifdef DEBUG_INVALIDATE
   2112             ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_gp);
   2113 #endif
   2114             compileTable[index].physicalReg = PhysicalReg_Null;
   2115         }
   2116         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_ss, reg+1);
   2117         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2118 #ifdef DEBUG_INVALIDATE
   2119             ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_ss);
   2120 #endif
   2121             compileTable[index].physicalReg = PhysicalReg_Null;
   2122         }
   2123     }
   2124 }
   2125 //! check which physical registers hold out-dated content if there is a def
   2126 
   2127 //! if another VR is overlapped with the given VR, the content of that VR is no longer in physical register
   2128 //! should we update inMemory?
   2129 void invalidateVR(int reg, LowOpndRegType pType) {
   2130     //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)
   2131     //def at xmm: content of misaligned xmm & gp are out-dated (reg-1,xmm reg+1,xmm) (reg,gp|ss reg+1,gp|ss)
   2132     //def at fs_s: content of xmm & gp are out-dated (reg-1,xmm reg,xmm) (reg,gp|ss)
   2133     //def at gp:   content of xmm is out-dated (reg-1,xmm reg,xmm) (reg,ss)
   2134     //def at ss:   content of xmm & gp are out-dated (reg-1,xmm reg,xmm) (reg,gp)
   2135     int index;
   2136     if(pType != LowOpndRegType_xmm) { //check xmm @reg
   2137         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg);
   2138         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2139 #ifdef DEBUG_INVALIDATE
   2140             ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_xmm);
   2141 #endif
   2142             if(getRegSize(pType) == OpndSize_32)
   2143                 dumpPartToMem(compileTable[index].physicalReg, reg, false); //dump high of xmm to memory
   2144             compileTable[index].physicalReg = PhysicalReg_Null;
   2145         }
   2146     }
   2147     //check misaligned xmm @ reg-1
   2148     index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg-1);
   2149     if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2150 #ifdef DEBUG_INVALIDATE
   2151         ALOGI("INVALIDATE virtual reg %d type %d", reg-1, LowOpndRegType_xmm);
   2152 #endif
   2153         dumpPartToMem(compileTable[index].physicalReg, reg-1, true); //dump low of xmm to memory
   2154         compileTable[index].physicalReg = PhysicalReg_Null;
   2155     }
   2156     //check misaligned xmm @ reg+1
   2157     if(pType == LowOpndRegType_xmm || pType == LowOpndRegType_fs) {
   2158         //check reg+1,xmm
   2159         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_xmm, reg+1);
   2160         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2161 #ifdef DEBUG_INVALIDATE
   2162             ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_xmm);
   2163 #endif
   2164             dumpPartToMem(compileTable[index].physicalReg, reg+1, false); //dump high of xmm to memory
   2165             compileTable[index].physicalReg = PhysicalReg_Null;
   2166         }
   2167     }
   2168     if(pType != LowOpndRegType_gp) {
   2169         //check reg,gp
   2170         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, reg);
   2171         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2172 #ifdef DEBUG_INVALIDATE
   2173             ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_gp);
   2174 #endif
   2175             compileTable[index].physicalReg = PhysicalReg_Null;
   2176         }
   2177     }
   2178     if(pType == LowOpndRegType_xmm || pType == LowOpndRegType_fs) {
   2179         //check reg+1,gp
   2180         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, reg+1);
   2181         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2182 #ifdef DEBUG_INVALIDATE
   2183             ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_gp);
   2184 #endif
   2185             compileTable[index].physicalReg = PhysicalReg_Null;
   2186         }
   2187     }
   2188     if(pType != LowOpndRegType_ss) {
   2189         //check reg,ss
   2190         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_ss, reg);
   2191         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2192 #ifdef DEBUG_INVALIDATE
   2193             ALOGI("INVALIDATE virtual reg %d type %d", reg, LowOpndRegType_ss);
   2194 #endif
   2195             compileTable[index].physicalReg = PhysicalReg_Null;
   2196         }
   2197     }
   2198     if(pType == LowOpndRegType_xmm || pType == LowOpndRegType_fs) {
   2199         //check reg+1,ss
   2200         index = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_ss, reg+1);
   2201         if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   2202 #ifdef DEBUG_INVALIDATE
   2203             ALOGI("INVALIDATE virtual reg %d type %d", reg+1, LowOpndRegType_ss);
   2204 #endif
   2205             compileTable[index].physicalReg = PhysicalReg_Null;
   2206         }
   2207     }
   2208 }
   2209 //! bookkeeping when a VR is updated
   2210 
   2211 //! invalidate contents of some physical registers, clear nullCheckDone, and update inMemory;
   2212 //! check whether there exist tranfer points for this bytecode, if yes, perform the transfer
   2213 int updateVirtualReg(int reg, LowOpndRegType pType) {
   2214     int k;
   2215     OpndSize size = getRegSize(pType);
   2216     //WAS only invalidate xmm VRs for the following cases:
   2217     //if def reaches a use of vA,xmm and (the def is not xmm or is misaligned xmm)
   2218     //  invalidate "vA,xmm"
   2219     invalidateVR(reg, pType);
   2220     clearVRNullCheck(reg, size);
   2221     clearVRBoundCheck(reg, size);
   2222     if(pType == LowOpndRegType_fs || pType == LowOpndRegType_fs_s)
   2223         setVRToMemory(reg, size);
   2224     else {
   2225         clearVRToMemory(reg, size);
   2226     }
   2227     for(k = 0; k < currentBB->num_xfer_points; k++) {
   2228         if(currentBB->xferPoints[k].offsetPC == offsetPC &&
   2229            currentBB->xferPoints[k].regNum == reg &&
   2230            currentBB->xferPoints[k].physicalType == pType &&
   2231            currentBB->xferPoints[k].xtype != XFER_MEM_TO_XMM) {
   2232             //perform the corresponding action for the def
   2233             PhysicalReg regAll;
   2234             if(currentBB->xferPoints[k].xtype == XFER_DEF_IS_XMM) {
   2235                 //def at fs: content of xmm is out-dated
   2236                 //def at xmm: content of misaligned xmm is out-dated
   2237                 //invalidateXmmVR(currentBB->xferPoints[k].tableIndex);
   2238 #ifdef DEBUG_XFER_POINTS
   2239                 if(currentBB->xferPoints[k].dumpToXmm) ALOGI("XFER set_virtual_reg to xmm: xmm VR %d", reg);
   2240 #endif
   2241                 if(pType == LowOpndRegType_xmm)  {
   2242 #ifdef DEBUG_XFER_POINTS
   2243                     ALOGI("XFER set_virtual_reg to memory: xmm VR %d", reg);
   2244 #endif
   2245                     PhysicalReg regAll = (PhysicalReg)checkVirtualReg(reg, LowOpndRegType_xmm, 0 /* do not update*/);
   2246                     dumpToMem(reg, LowOpndRegType_xmm, regAll);
   2247                 }
   2248                 if(currentBB->xferPoints[k].vr_gpl >= 0) { //
   2249                 }
   2250                 if(currentBB->xferPoints[k].vr_gph >= 0) {
   2251                 }
   2252             }
   2253             if((pType == LowOpndRegType_gp || pType == LowOpndRegType_ss) &&
   2254                (currentBB->xferPoints[k].xtype == XFER_DEF_TO_MEM ||
   2255                 currentBB->xferPoints[k].xtype == XFER_DEF_TO_GP_MEM)) {
   2256                 //the defined gp VR already in register
   2257                 //invalidateXmmVR(currentBB->xferPoints[k].tableIndex);
   2258                 regAll = (PhysicalReg)checkVirtualReg(reg, pType, 0 /* do not update*/);
   2259                 dumpToMem(reg, pType, regAll);
   2260 #ifdef DEBUG_XFER_POINTS
   2261                 ALOGI("XFER set_virtual_reg to memory: gp VR %d", reg);
   2262 #endif
   2263             }
   2264             if((pType == LowOpndRegType_fs_s || pType == LowOpndRegType_ss) &&
   2265                currentBB->xferPoints[k].xtype == XFER_DEF_TO_GP_MEM) {
   2266             }
   2267         }
   2268     }
   2269     return -1;
   2270 }
   2271 ////////////////////////////////////////////////////////////////
   2272 //REGISTER ALLOCATION
   2273 int spillForHardReg(int regNum, int type);
   2274 void decreaseRefCount(int index);
   2275 int getFreeReg(int type, int reg, int indexToCompileTable);
   2276 PhysicalReg spillForLogicalReg(int type, int reg, int indexToCompileTable);
   2277 int unspillLogicalReg(int spill_index, int physicalReg);
   2278 int searchVirtualInfoOfBB(LowOpndRegType type, int regNum, BasicBlock_O1* bb);
   2279 bool isTemp8Bit(int type, int reg);
   2280 bool matchType(int typeA, int typeB);
   2281 int getNextAccess(int compileIndex);
   2282 void dumpCompileTable();
   2283 
   2284 //! allocate a register for a variable
   2285 
   2286 //!if no physical register is free, call spillForLogicalReg to free up a physical register;
   2287 //!if the variable is a temporary and it was spilled, call unspillLogicalReg to load from spill location to the allocated physical register;
   2288 //!if updateRefCount is true, reduce reference count of the variable by 1
   2289 int registerAlloc(int type, int reg, bool isPhysical, bool updateRefCount) {
   2290 #ifdef DEBUG_REGALLOC
   2291     ALOGI("%p: try to allocate register %d type %d isPhysical %d", currentBB, reg, type, isPhysical);
   2292 #endif
   2293     if(currentBB == NULL) {
   2294         if(type & LowOpndRegType_virtual) return PhysicalReg_Null;
   2295         if(isPhysical) return reg; //for helper functions
   2296         return PhysicalReg_Null;
   2297     }
   2298     //ignore EDI, ESP, EBP (glue)
   2299     if(isPhysical && (reg == PhysicalReg_EDI || reg == PhysicalReg_ESP ||
   2300                       reg == PhysicalReg_EBP || reg == PhysicalReg_Null))
   2301         return reg;
   2302 
   2303     int newType = convertType(type, reg, isPhysical);
   2304     if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
   2305     int tIndex = searchCompileTable(newType, reg);
   2306     if(tIndex < 0) {
   2307       ALOGE("reg %d type %d not found in registerAlloc", reg, newType);
   2308       return PhysicalReg_Null;
   2309     }
   2310 
   2311     //physical register
   2312     if(isPhysical) {
   2313         if(allRegs[reg].isUsed) { //if used by a non hard-coded register
   2314             spillForHardReg(reg, newType);
   2315         }
   2316         allRegs[reg].isUsed = true;
   2317 #ifdef DEBUG_REG_USED
   2318         ALOGI("REGALLOC: allocate a reg %d", reg);
   2319 #endif
   2320         compileTable[tIndex].physicalReg = reg;
   2321         if(updateRefCount)
   2322             decreaseRefCount(tIndex);
   2323 #ifdef DEBUG_REGALLOC
   2324         ALOGI("REGALLOC: allocate register %d for logical register %d %d",
   2325                compileTable[tIndex].physicalReg, reg, newType);
   2326 #endif
   2327         return reg;
   2328     }
   2329     //already allocated
   2330     if(compileTable[tIndex].physicalReg != PhysicalReg_Null) {
   2331 #ifdef DEBUG_REGALLOC
   2332         ALOGI("already allocated to physical register %d", compileTable[tIndex].physicalReg);
   2333 #endif
   2334         if(updateRefCount)
   2335             decreaseRefCount(tIndex);
   2336         return compileTable[tIndex].physicalReg;
   2337     }
   2338 
   2339     //at this point, the logical register is not hard-coded and is mapped to Reg_Null
   2340     //first check whether there is a free reg
   2341     //if not, call spillForLogicalReg
   2342     int index = getFreeReg(newType, reg, tIndex);
   2343     if(index >= 0 && index < PhysicalReg_Null) {
   2344         //update compileTable & allRegs
   2345         compileTable[tIndex].physicalReg = allRegs[index].physicalReg;
   2346         allRegs[index].isUsed = true;
   2347 #ifdef DEBUG_REG_USED
   2348         ALOGI("REGALLOC: register %d is free", allRegs[index].physicalReg);
   2349 #endif
   2350     } else {
   2351         PhysicalReg allocR = spillForLogicalReg(newType, reg, tIndex);
   2352         compileTable[tIndex].physicalReg = allocR;
   2353     }
   2354     if(compileTable[tIndex].spill_loc_index >= 0) {
   2355         unspillLogicalReg(tIndex, compileTable[tIndex].physicalReg);
   2356     }
   2357     if(updateRefCount)
   2358         decreaseRefCount(tIndex);
   2359 #ifdef DEBUG_REGALLOC
   2360     ALOGI("REGALLOC: allocate register %d for logical register %d %d",
   2361            compileTable[tIndex].physicalReg, reg, newType);
   2362 #endif
   2363     return compileTable[tIndex].physicalReg;
   2364 }
   2365 //!a variable will use a physical register allocated for another variable
   2366 
   2367 //!This is used when MOVE_OPT is on, it tries to alias a virtual register with a temporary to remove a move
   2368 int registerAllocMove(int reg, int type, bool isPhysical, int srcReg) {
   2369     if(srcReg == PhysicalReg_EDI || srcReg == PhysicalReg_ESP || srcReg == PhysicalReg_EBP)
   2370         ALOGE("can't move from srcReg EDI or ESP or EBP");
   2371 #ifdef DEBUG_REGALLOC
   2372     ALOGI("in registerAllocMove: reg %d type %d srcReg %d", reg, type, srcReg);
   2373 #endif
   2374     int newType = convertType(type, reg, isPhysical);
   2375     if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
   2376     int index = searchCompileTable(newType, reg);
   2377     if(index < 0) {
   2378         ALOGE("reg %d type %d not found in registerAllocMove", reg, newType);
   2379         return -1;
   2380     }
   2381 
   2382     decreaseRefCount(index);
   2383     compileTable[index].physicalReg = srcReg;
   2384 #ifdef DEBUG_REGALLOC
   2385     ALOGI("REGALLOC: registerAllocMove %d for logical register %d %d",
   2386            compileTable[index].physicalReg, reg, newType);
   2387 #endif
   2388     return srcReg;
   2389 }
   2390 
   2391 //! check whether a physical register is available to be used by a variable
   2392 
   2393 //! data structures accessed:
   2394 //! 1> currentBB->infoBasicBlock[index].allocConstraintsSorted
   2395 //!    sorted from high count to low count
   2396 //! 2> currentBB->allocConstraintsSorted
   2397 //!    sorted from low count to high count
   2398 //! 3> allRegs: whether a physical register is available, indexed by PhysicalReg
   2399 //! NOTE: if a temporary variable is 8-bit, only %eax, %ebx, %ecx, %edx can be used
   2400 int getFreeReg(int type, int reg, int indexToCompileTable) {
   2401     syncAllRegs();
   2402     /* handles requests for xmm or ss registers */
   2403     int k;
   2404     if(((type & MASK_FOR_TYPE) == LowOpndRegType_xmm) ||
   2405        ((type & MASK_FOR_TYPE) == LowOpndRegType_ss)) {
   2406         for(k = PhysicalReg_XMM0; k <= PhysicalReg_XMM7; k++) {
   2407             if(!allRegs[k].isUsed) return k;
   2408         }
   2409         return -1;
   2410     }
   2411 #ifdef DEBUG_REGALLOC
   2412     ALOGI("USED registers: ");
   2413     for(k = 0; k < 8; k++)
   2414         ALOGI("%d used: %d time freed: %d callee-saveld: %d", k, allRegs[k].isUsed,
   2415              allRegs[k].freeTimeStamp, allRegs[k].isCalleeSaved);
   2416     ALOGI("");
   2417 #endif
   2418 
   2419     /* a VR is requesting a physical register */
   2420     if(isVirtualReg(type)) { //find a callee-saved register
   2421         /* if VR is type GG, check the pre-allocated physical register first */
   2422         bool isGGVR = compileTable[indexToCompileTable].gType == GLOBALTYPE_GG;
   2423         if(isGGVR) {
   2424             int regCandidateT = compileTable[indexToCompileTable].physicalReg_prev;
   2425             if(!allRegs[regCandidateT].isUsed) return regCandidateT;
   2426         }
   2427 
   2428         int index = searchVirtualInfoOfBB((LowOpndRegType)(type&MASK_FOR_TYPE), reg, currentBB);
   2429         if(index < 0) {
   2430             ALOGE("VR %d %d not found in infoBasicBlock of currentBB %d (num of VRs %d)",
   2431                   reg, type, currentBB->bb_index, currentBB->num_regs);
   2432             dvmAbort();
   2433         }
   2434 
   2435         /* check allocConstraints for this VR,
   2436            return an available physical register with the highest constraint > 0 */
   2437         for(k = 0; k < 8; k++) {
   2438             if(currentBB->infoBasicBlock[index].allocConstraintsSorted[k].count == 0) break;
   2439             int regCandidateT = currentBB->infoBasicBlock[index].allocConstraintsSorted[k].physicalReg;
   2440             assert(regCandidateT < PhysicalReg_Null);
   2441             if(!allRegs[regCandidateT].isUsed) return regCandidateT;
   2442         }
   2443 
   2444         /* WAS: return an available physical register with the lowest constraint
   2445            NOW: consider a new factor (freeTime) when there is a tie
   2446                 if 2 available physical registers have the same number of constraints
   2447                 choose the one with smaller free time stamp */
   2448         int currentCount = -1;
   2449         int index1 = -1;
   2450         int smallestTime = -1;
   2451         for(k = 0; k < 8; k++) {
   2452             int regCandidateT = currentBB->allocConstraintsSorted[k].physicalReg;
   2453             assert(regCandidateT < PhysicalReg_Null);
   2454             if(index1 >= 0 && currentBB->allocConstraintsSorted[k].count > currentCount)
   2455                 break; //candidate has higher count than index1
   2456             if(!allRegs[regCandidateT].isUsed) {
   2457                 if(index1 < 0) {
   2458                     index1 = k;
   2459                     currentCount = currentBB->allocConstraintsSorted[k].count;
   2460                     smallestTime = allRegs[regCandidateT].freeTimeStamp;
   2461                 } else if(allRegs[regCandidateT].freeTimeStamp < smallestTime) {
   2462                     index1 = k;
   2463                     smallestTime = allRegs[regCandidateT].freeTimeStamp;
   2464                 }
   2465             }
   2466         }
   2467         if(index1 >= 0) return currentBB->allocConstraintsSorted[index1].physicalReg;
   2468         return -1;
   2469     }
   2470     /* handle request from a temporary variable or a glue variable */
   2471     else {
   2472         bool is8Bit = isTemp8Bit(type, reg);
   2473 
   2474         /* if the temporary variable is linked to a VR and
   2475               the VR is not yet allocated to any physical register */
   2476         int vr_num = compileTable[indexToCompileTable].linkageToVR;
   2477         if(vr_num >= 0) {
   2478             int index3 = searchCompileTable(LowOpndRegType_gp | LowOpndRegType_virtual, vr_num);
   2479             if(index3 < 0) {
   2480                 ALOGE("2 in tracing linkage to VR %d", vr_num);
   2481                 dvmAbort();
   2482             }
   2483 
   2484             if(compileTable[index3].physicalReg == PhysicalReg_Null) {
   2485                 int index2 = searchVirtualInfoOfBB(LowOpndRegType_gp, vr_num, currentBB);
   2486                 if(index2 < 0) {
   2487                     ALOGE("1 in tracing linkage to VR %d", vr_num);
   2488                     dvmAbort();
   2489                 }
   2490 #ifdef DEBUG_REGALLOC
   2491                 ALOGI("in getFreeReg for temporary reg %d, trace the linkage to VR %d",
   2492                      reg, vr_num);
   2493 #endif
   2494 
   2495                 /* check allocConstraints on the VR
   2496                    return an available physical register with the highest constraint > 0
   2497                 */
   2498                 for(k = 0; k < 8; k++) {
   2499                     if(currentBB->infoBasicBlock[index2].allocConstraintsSorted[k].count == 0) break;
   2500                     int regCandidateT = currentBB->infoBasicBlock[index2].allocConstraintsSorted[k].physicalReg;
   2501 #ifdef DEBUG_REGALLOC
   2502                     ALOGI("check register %d with count %d", regCandidateT,
   2503                           currentBB->infoBasicBlock[index2].allocConstraintsSorted[k].count);
   2504 #endif
   2505                     /* if the requesting variable is 8 bit */
   2506                     if(is8Bit && regCandidateT > PhysicalReg_EDX) continue;
   2507                     assert(regCandidateT < PhysicalReg_Null);
   2508                     if(!allRegs[regCandidateT].isUsed) return regCandidateT;
   2509                 }
   2510             }
   2511         }
   2512         /* check allocConstraints of the basic block
   2513            if 2 available physical registers have the same constraint count,
   2514               return the non callee-saved physical reg */
   2515         /* enhancement: record the time when a register is freed (freeTimeStamp)
   2516                         the purpose is to reduce false dependency
   2517            priority: constraint count, non callee-saved, time freed
   2518                let x be the lowest constraint count
   2519                set A be available callee-saved physical registers with count == x
   2520                set B be available non callee-saved physical registers with count == x
   2521                if set B is not null, return the one with smallest free time
   2522                otherwise, return the one in A with smallest free time
   2523            To ignore whether it is callee-saved, add all candidates to set A
   2524         */
   2525         int setAIndex[8];
   2526         int num_A = 0;
   2527         int setBIndex[8];
   2528         int num_B = 0;
   2529         int index1 = -1; //points to an available physical reg with lowest count
   2530         int currentCount = -1;
   2531         for(k = 0; k < 8; k++) {
   2532             int regCandidateT = currentBB->allocConstraintsSorted[k].physicalReg;
   2533             if(is8Bit && regCandidateT > PhysicalReg_EDX) continue;
   2534 
   2535             if(index1 >= 0 && currentBB->allocConstraintsSorted[k].count > currentCount)
   2536                 break; //candidate has higher count than index1
   2537             assert(regCandidateT < PhysicalReg_Null);
   2538             if(!allRegs[regCandidateT].isUsed) {
   2539                 /*To ignore whether it is callee-saved, add all candidates to set A */
   2540                 if(false) {//!allRegs[regCandidateT].isCalleeSaved) { //add to set B
   2541                     setBIndex[num_B++] = k;
   2542                 } else { //add to set A
   2543                     setAIndex[num_A++] = k;
   2544                 }
   2545                 if(index1 < 0) {
   2546                     /* index1 points to a physical reg with lowest count */
   2547                     index1 = k;
   2548                     currentCount = currentBB->allocConstraintsSorted[k].count;
   2549                 }
   2550             }
   2551         }
   2552 
   2553         int kk;
   2554         int smallestTime = -1;
   2555         index1 = -1;
   2556         for(kk = 0; kk < num_B; kk++) {
   2557             k = setBIndex[kk];
   2558             int regCandidateT = currentBB->allocConstraintsSorted[k].physicalReg;
   2559             assert(regCandidateT < PhysicalReg_Null);
   2560             if(kk == 0 || allRegs[regCandidateT].freeTimeStamp < smallestTime) {
   2561                 index1 = k;
   2562                 smallestTime = allRegs[regCandidateT].freeTimeStamp;
   2563             }
   2564         }
   2565         if(index1 >= 0)
   2566             return currentBB->allocConstraintsSorted[index1].physicalReg;
   2567         index1 = -1;
   2568         for(kk = 0; kk < num_A; kk++) {
   2569             k = setAIndex[kk];
   2570             int regCandidateT = currentBB->allocConstraintsSorted[k].physicalReg;
   2571             if(kk == 0 || allRegs[regCandidateT].freeTimeStamp < smallestTime) {
   2572                 index1 = k;
   2573                 smallestTime = allRegs[regCandidateT].freeTimeStamp;
   2574             }
   2575         }
   2576         if(index1 >= 0) return currentBB->allocConstraintsSorted[index1].physicalReg;
   2577         return -1;
   2578     }
   2579     return -1;
   2580 }
   2581 
   2582 //! find a candidate physical register for a variable and spill all variables that are mapped to the candidate
   2583 
   2584 //!
   2585 PhysicalReg spillForLogicalReg(int type, int reg, int indexToCompileTable) {
   2586     //choose a used register to spill
   2587     //when a GG virtual register is spilled, write it to interpretd stack, set physicalReg to Null
   2588     //  at end of the basic block, load spilled GG VR to physical reg
   2589     //when other types of VR is spilled, write it to interpreted stack, set physicalReg to Null
   2590     //when a temporary (non-virtual) register is spilled, write it to stack, set physicalReg to Null
   2591     //can we spill a hard-coded temporary register? YES
   2592     int k, k2;
   2593     PhysicalReg allocR;
   2594 
   2595     //do not try to free a physical reg that is used by more than one logical registers
   2596     //fix on sep 28, 2009
   2597     //do not try to spill a hard-coded logical register
   2598     //do not try to free a physical reg that is outside of the range for 8-bit logical reg
   2599     /* for each physical register,
   2600        collect number of non-hardcode entries that are mapped to the physical register */
   2601     int numOfUses[PhysicalReg_Null];
   2602     for(k = PhysicalReg_EAX; k < PhysicalReg_Null; k++)
   2603         numOfUses[k] = 0;
   2604     for(k = 0; k < num_compile_entries; k++) {
   2605         if((compileTable[k].physicalReg != PhysicalReg_Null) &&
   2606            matchType(type, compileTable[k].physicalType) &&
   2607            (compileTable[k].physicalType & LowOpndRegType_hard) == 0) {
   2608             numOfUses[compileTable[k].physicalReg]++;
   2609         }
   2610     }
   2611 
   2612     /* candidates: all non-hardcode entries that are mapped to
   2613            a physical register that is used by only one entry*/
   2614     bool is8Bit = isTemp8Bit(type, reg);
   2615     int candidates[COMPILE_TABLE_SIZE];
   2616     int num_cand = 0;
   2617     for(k = 0; k < num_compile_entries; k++) {
   2618         if(matchType(type, compileTable[k].physicalType) &&
   2619            compileTable[k].physicalReg != PhysicalReg_Null) {
   2620             if(is8Bit && compileTable[k].physicalReg > PhysicalReg_EDX) continue; //not a candidate
   2621             if(!canSpillReg[compileTable[k].physicalReg]) continue; //not a candidate
   2622             if((compileTable[k].physicalType & LowOpndRegType_hard) == 0 &&
   2623                numOfUses[compileTable[k].physicalReg] <= 1) {
   2624                 candidates[num_cand++] = k;
   2625             }
   2626         }
   2627     }
   2628 
   2629     /* go through all candidates:
   2630        first check GLUE-related entries */
   2631     int spill_index = -1;
   2632     for(k2 = 0; k2 < num_cand; k2++) {
   2633         k = candidates[k2];
   2634         if((compileTable[k].physicalReg != PhysicalReg_Null) &&
   2635            matchType(type, compileTable[k].physicalType) &&
   2636            (compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX &&
   2637             compileTable[k].regNum != PhysicalReg_GLUE)) {
   2638             allocR = (PhysicalReg)spillLogicalReg(k, true);
   2639 #ifdef DEBUG_REGALLOC
   2640             ALOGI("SPILL register used by num %d type %d it is a GLUE register with refCount %d",
   2641                   compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].refCount);
   2642 #endif
   2643             return allocR;
   2644         }
   2645     }
   2646 
   2647     /* out of the candates, find a VR that has the furthest next use */
   2648     int furthestUse = offsetPC;
   2649     for(k2 = 0; k2 < num_cand; k2++) {
   2650         k = candidates[k2];
   2651         if((compileTable[k].physicalReg != PhysicalReg_Null) &&
   2652            matchType(type, compileTable[k].physicalType) &&
   2653            isVirtualReg(compileTable[k].physicalType)) {
   2654             int nextUse = getNextAccess(k);
   2655             if(spill_index < 0 || nextUse > furthestUse) {
   2656                 spill_index = k;
   2657                 furthestUse = nextUse;
   2658             }
   2659         }
   2660     }
   2661 
   2662     /* spill the VR with the furthest next use */
   2663     if(spill_index >= 0) {
   2664         allocR = (PhysicalReg)spillLogicalReg(spill_index, true);
   2665         return allocR; //the register is still being used
   2666     }
   2667 
   2668     /* spill an entry with the smallest refCount */
   2669     int baseLeftOver = 0;
   2670     int index = -1;
   2671     for(k2 = 0; k2 < num_cand; k2++) {
   2672         k = candidates[k2];
   2673         if(k != indexForGlue &&
   2674            (compileTable[k].physicalReg != PhysicalReg_Null) &&
   2675            (compileTable[k].physicalType & LowOpndRegType_hard) == 0 && //not hard-coded
   2676            matchType(type, compileTable[k].physicalType)) {
   2677             if((index < 0) || (compileTable[k].refCount < baseLeftOver)) {
   2678                 baseLeftOver = compileTable[k].refCount;
   2679                 index = k;
   2680             }
   2681         }
   2682     }
   2683     if(index < 0) {
   2684         dumpCompileTable();
   2685         ALOGE("no register to spill for logical %d %d", reg, type);
   2686         dvmAbort();
   2687     }
   2688     allocR = (PhysicalReg)spillLogicalReg(index, true);
   2689 #ifdef DEBUG_REGALLOC
   2690     ALOGI("SPILL register used by num %d type %d it is a temporary register with refCount %d",
   2691            compileTable[index].regNum, compileTable[index].physicalType, compileTable[index].refCount);
   2692 #endif
   2693     return allocR;
   2694 }
   2695 //!spill a variable to memory, the variable is specified by an index to compileTable
   2696 
   2697 //!If the variable is a temporary, get a spill location that is not in use and spill the content to the spill location;
   2698 //!If updateTable is true, set physicalReg to Null;
   2699 //!Return the physical register that was allocated to the variable
   2700 int spillLogicalReg(int spill_index, bool updateTable) {
   2701     if((compileTable[spill_index].physicalType & LowOpndRegType_hard) != 0) {
   2702         ALOGE("can't spill a hard-coded register");
   2703         dvmAbort();
   2704     }
   2705     int physicalReg = compileTable[spill_index].physicalReg;
   2706     if(!canSpillReg[physicalReg]) {
   2707 #ifdef PRINT_WARNING
   2708         ALOGW("can't spill register %d", physicalReg);
   2709 #endif
   2710         //dvmAbort(); //this happens in get_virtual_reg where VR is allocated to the same reg as the hardcoded temporary
   2711     }
   2712     if(isVirtualReg(compileTable[spill_index].physicalType)) {
   2713         //spill back to memory
   2714         dumpToMem(compileTable[spill_index].regNum,
   2715                   (LowOpndRegType)(compileTable[spill_index].physicalType&MASK_FOR_TYPE),
   2716                   compileTable[spill_index].physicalReg);
   2717     }
   2718     else {
   2719         //update spill_loc_index
   2720         int k = getSpillIndex(spill_index == indexForGlue,
   2721                     getRegSize(compileTable[spill_index].physicalType));
   2722         compileTable[spill_index].spill_loc_index = 4*k;
   2723         if(k >= 0)
   2724             spillIndexUsed[k] = 1;
   2725         saveToSpillRegion(getRegSize(compileTable[spill_index].physicalType),
   2726                           compileTable[spill_index].physicalReg, 4*k);
   2727     }
   2728     //compileTable[spill_index].physicalReg_prev = compileTable[spill_index].physicalReg;
   2729 #ifdef DEBUG_REGALLOC
   2730     ALOGI("REGALLOC: SPILL logical reg %d %d with refCount %d allocated to %d",
   2731            compileTable[spill_index].regNum,
   2732            compileTable[spill_index].physicalType, compileTable[spill_index].refCount,
   2733            compileTable[spill_index].physicalReg);
   2734 #endif
   2735     if(!updateTable) return PhysicalReg_Null;
   2736 
   2737     int allocR = compileTable[spill_index].physicalReg;
   2738     compileTable[spill_index].physicalReg = PhysicalReg_Null;
   2739     return allocR;
   2740 }
   2741 //! load a varible from memory to physical register, the variable is specified with an index to compileTable
   2742 
   2743 //!If the variable is a temporary, load from spill location and set the flag for the spill location to not used
   2744 int unspillLogicalReg(int spill_index, int physicalReg) {
   2745     //can't un-spill to %eax in afterCall!!!
   2746     //what if GG VR is allocated to %eax!!!
   2747     if(isVirtualReg(compileTable[spill_index].physicalType)) {
   2748         get_virtual_reg_noalloc(compileTable[spill_index].regNum,
   2749                                 getRegSize(compileTable[spill_index].physicalType),
   2750                                 physicalReg, true);
   2751     }
   2752     else {
   2753         loadFromSpillRegion(getRegSize(compileTable[spill_index].physicalType),
   2754                             physicalReg, compileTable[spill_index].spill_loc_index);
   2755         spillIndexUsed[compileTable[spill_index].spill_loc_index >> 2] = 0;
   2756         compileTable[spill_index].spill_loc_index = -1;
   2757     }
   2758 #ifdef DEBUG_REGALLOC
   2759     ALOGI("REGALLOC: UNSPILL logical reg %d %d with refCount %d", compileTable[spill_index].regNum,
   2760            compileTable[spill_index].physicalType, compileTable[spill_index].refCount);
   2761 #endif
   2762     return PhysicalReg_Null;
   2763 }
   2764 
   2765 //!spill a virtual register to memory
   2766 
   2767 //!if the current value of a VR is constant, write immediate to memory;
   2768 //!if the current value of a VR is in a physical register, call spillLogicalReg to dump content of the physical register to memory;
   2769 //!ifupdateTable is true, set the physical register for VR to Null and decrease reference count of the virtual register
   2770 int spillVirtualReg(int vrNum, LowOpndRegType type, bool updateTable) {
   2771     int index = searchCompileTable(type | LowOpndRegType_virtual, vrNum);
   2772     if(index < 0) {
   2773         ALOGE("can't find VR %d %d in spillVirtualReg", vrNum, type);
   2774         return -1;
   2775     }
   2776     //check whether it is const
   2777     int value[2];
   2778     int isConst = isVirtualRegConstant(vrNum, type, value, false); //do not update refCount
   2779     if(isConst == 1 || isConst == 3) {
   2780         dumpImmToMem(vrNum, OpndSize_32, value[0]);
   2781     }
   2782     if(getRegSize(type) == OpndSize_64 && (isConst == 2 || isConst == 3)) {
   2783         dumpImmToMem(vrNum+1, OpndSize_32, value[1]);
   2784     }
   2785     if(isConst != 3 && compileTable[index].physicalReg != PhysicalReg_Null)
   2786         spillLogicalReg(index, updateTable);
   2787     if(updateTable) decreaseRefCount(index);
   2788     return -1;
   2789 }
   2790 
   2791 //! spill variables that are mapped to physical register (regNum)
   2792 
   2793 //!
   2794 int spillForHardReg(int regNum, int type) {
   2795     //find an entry that uses the physical register
   2796     int spill_index = -1;
   2797     int k;
   2798     for(k = 0; k < num_compile_entries; k++) {
   2799         if(k != indexForGlue &&
   2800            compileTable[k].physicalReg == regNum &&
   2801            matchType(type, compileTable[k].physicalType)) {
   2802             spill_index = k;
   2803             if(compileTable[k].regNum == regNum && compileTable[k].physicalType == type)
   2804                 continue;
   2805             if(inGetVR_num >= 0 && compileTable[k].regNum == inGetVR_num && compileTable[k].physicalType == (type | LowOpndRegType_virtual))
   2806                 continue;
   2807 #ifdef DEBUG_REGALLOC
   2808             ALOGI("SPILL logical reg %d %d to free hard-coded reg %d %d",
   2809                    compileTable[spill_index].regNum, compileTable[spill_index].physicalType,
   2810                    regNum, type);
   2811             if(compileTable[spill_index].physicalType & LowOpndRegType_hard) dumpCompileTable();
   2812 #endif
   2813             assert(spill_index < COMPILE_TABLE_SIZE);
   2814             spillLogicalReg(spill_index, true);
   2815         }
   2816     }
   2817     return regNum;
   2818 }
   2819 ////////////////////////////////////////////////////////////////
   2820 //! update allocConstraints of the current basic block
   2821 
   2822 //! allocConstraints specify how many times a hardcoded register is used in this basic block
   2823 void updateCurrentBBWithConstraints(PhysicalReg reg) {
   2824     if(reg > PhysicalReg_EBP) {
   2825         ALOGE("register %d out of range in updateCurrentBBWithConstraints", reg);
   2826     }
   2827     currentBB->allocConstraints[reg].count++;
   2828 }
   2829 //! sort allocConstraints and save the result in allocConstraintsSorted
   2830 
   2831 //! allocConstraints specify how many times a virtual register is linked to a hardcode register
   2832 //! it is updated in getVirtualRegInfo and merged by mergeEntry2
   2833 int sortAllocConstraint(RegAllocConstraint* allocConstraints,
   2834                         RegAllocConstraint* allocConstraintsSorted, bool fromHighToLow) {
   2835     int ii, jj;
   2836     int num_sorted = 0;
   2837     for(jj = 0; jj < 8; jj++) {
   2838         //figure out where to insert allocConstraints[jj]
   2839         int count = allocConstraints[jj].count;
   2840         int regT = allocConstraints[jj].physicalReg;
   2841         assert(regT < PhysicalReg_Null);
   2842         int insertIndex = -1;
   2843         for(ii = 0; ii < num_sorted; ii++) {
   2844             int regT2 = allocConstraintsSorted[ii].physicalReg;
   2845             assert(regT2 < PhysicalReg_Null);
   2846             if(allRegs[regT].isCalleeSaved &&
   2847                count == allocConstraintsSorted[ii].count) {
   2848                 insertIndex = ii;
   2849                 break;
   2850             }
   2851             if((!allRegs[regT].isCalleeSaved) &&
   2852                count == allocConstraintsSorted[ii].count &&
   2853                (!allRegs[regT2].isCalleeSaved)) { //skip until found one that is not callee-saved
   2854                 insertIndex = ii;
   2855                 break;
   2856             }
   2857             if((fromHighToLow && count > allocConstraintsSorted[ii].count) ||
   2858                ((!fromHighToLow) && count < allocConstraintsSorted[ii].count)) {
   2859                 insertIndex = ii;
   2860                 break;
   2861             }
   2862         }
   2863         if(insertIndex < 0) {
   2864             allocConstraintsSorted[num_sorted].physicalReg = (PhysicalReg)regT;
   2865             allocConstraintsSorted[num_sorted].count = count;
   2866             num_sorted++;
   2867         } else {
   2868             for(ii = num_sorted-1; ii >= insertIndex; ii--) {
   2869                 allocConstraintsSorted[ii+1] = allocConstraintsSorted[ii];
   2870             }
   2871             allocConstraintsSorted[insertIndex] = allocConstraints[jj];
   2872             num_sorted++;
   2873         }
   2874     } //for jj
   2875 #ifdef DEBUG_ALLOC_CONSTRAINT
   2876     for(jj = 0; jj < 8; jj++) {
   2877         if(allocConstraintsSorted[jj].count > 0)
   2878             ALOGI("%d: register %d has count %d", jj, allocConstraintsSorted[jj].physicalReg, allocConstraintsSorted[jj].count);
   2879     }
   2880 #endif
   2881     return 0;
   2882 }
   2883 //! find the entry for a given virtual register in compileTable
   2884 
   2885 //!
   2886 int findVirtualRegInTable(u2 vA, LowOpndRegType type, bool printError) {
   2887     int k = searchCompileTable(type | LowOpndRegType_virtual, vA);
   2888     if(k < 0 && printError) {
   2889         ALOGE("findVirtualRegInTable virtual register %d type %d", vA, type);
   2890         dvmAbort();
   2891     }
   2892     return k;
   2893 }
   2894 
   2895 //! check whether a virtual register is constant
   2896 
   2897 //! 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
   2898 int isVirtualRegConstant(int regNum, LowOpndRegType type, int* valuePtr, bool updateRefCount) {
   2899 
   2900     OpndSize size = getRegSize(type);
   2901     int k;
   2902     int indexL = -1;
   2903     int indexH = -1;
   2904     for(k = 0; k < num_const_vr; k++) {
   2905 #ifdef DEBUG_CONST
   2906         ALOGI("constVRTable VR %d isConst %d value %x", constVRTable[k].regNum, constVRTable[k].isConst, constVRTable[k].value);
   2907 #endif
   2908         if(constVRTable[k].regNum == regNum) {
   2909             indexL = k;
   2910             continue;
   2911         }
   2912         if(constVRTable[k].regNum == regNum + 1 && size == OpndSize_64) {
   2913             indexH = k;
   2914             continue;
   2915         }
   2916     }
   2917     bool isConstL = false;
   2918     bool isConstH = false;
   2919     if(indexL >= 0) {
   2920         isConstL = constVRTable[indexL].isConst;
   2921     }
   2922     if(size == OpndSize_64 && indexH >= 0) {
   2923         isConstH = constVRTable[indexH].isConst;
   2924     }
   2925 
   2926     if((isConstL || isConstH)) {
   2927         if(size == OpndSize_64 && isConstH)
   2928             valuePtr[1] = constVRTable[indexH].value;
   2929         if(isConstL)
   2930             *valuePtr = constVRTable[indexL].value;
   2931     }
   2932     if((isConstL && size == OpndSize_32) || (isConstL && isConstH)) {
   2933         if(updateRefCount) {
   2934             int indexOrig = searchCompileTable(type | LowOpndRegType_virtual, regNum);
   2935             if(indexOrig < 0) ALOGE("can't find VR in isVirtualRegConstant num %d type %d", regNum, type);
   2936             decreaseRefCount(indexOrig);
   2937         }
   2938 #ifdef DEBUG_CONST
   2939         ALOGI("VR %d %d is const case", regNum, type);
   2940 #endif
   2941         return 3;
   2942     }
   2943     if(size == OpndSize_32) return 0;
   2944     if(isConstL) return 1;
   2945     if(isConstH) return 2;
   2946     return 0;
   2947 }
   2948 
   2949 //!update RegAccessType of virtual register vB given RegAccessType of vA
   2950 
   2951 //!RegAccessType can be D, L, H
   2952 //!D means full definition, L means only lower-half is defined, H means only higher half is defined
   2953 //!we say a VR has no exposed usage in a basic block if the accessType is D or DU
   2954 //!we say a VR has exposed usage in a basic block if the accessType is not D nor DU
   2955 //!we say a VR has exposed usage in other basic blocks (hasOtherExposedUsage) if
   2956 //!  there exists another basic block where VR has exposed usage in that basic block
   2957 //!A can be U, D, L, H, UD, UL, UH, DU, LU, HU (merged result)
   2958 //!B can be U, D, UD, DU (an entry for the current bytecode)
   2959 //!input isAPartiallyOverlapB can be any value between -1 to 6
   2960 //!if A is xmm: gp B lower half of A, (isAPartiallyOverlapB is 1)
   2961 //!             gp B higher half of A, (isAPartiallyOverlapB is 2)
   2962 //!             lower half of A covers the higher half of xmm B  (isAPartiallyOverlapB is 4)
   2963 //!             higher half of A covers the lower half of xmm B   (isAPartiallyOverlapB is 3)
   2964 //!if A is gp:  A covers the lower half of xmm B, (isAPartiallyOverlapB is 5)
   2965 //!             A covers the higher half of xmm B (isAPartiallyOverlapB is 6)
   2966 RegAccessType updateAccess1(RegAccessType A, OverlapCase isAPartiallyOverlapB) {
   2967     if(A == REGACCESS_D || A == REGACCESS_DU || A == REGACCESS_UD) {
   2968         if(isAPartiallyOverlapB == OVERLAP_ALIGN) return REGACCESS_D;
   2969         if(isAPartiallyOverlapB == OVERLAP_B_IS_LOW_OF_A || isAPartiallyOverlapB == OVERLAP_B_IS_HIGH_OF_A)
   2970             return REGACCESS_D;
   2971         if(isAPartiallyOverlapB == OVERLAP_LOW_OF_A_IS_HIGH_OF_B || isAPartiallyOverlapB == OVERLAP_A_IS_LOW_OF_B)
   2972             return REGACCESS_L;
   2973         return REGACCESS_H;
   2974     }
   2975     if(A == REGACCESS_L || A == REGACCESS_LU || A == REGACCESS_UL) {
   2976         if(isAPartiallyOverlapB == OVERLAP_ALIGN || isAPartiallyOverlapB == OVERLAP_A_IS_LOW_OF_B)
   2977             return REGACCESS_L;
   2978         if(isAPartiallyOverlapB == OVERLAP_B_IS_LOW_OF_A) return REGACCESS_D;
   2979         if(isAPartiallyOverlapB == OVERLAP_B_IS_HIGH_OF_A || isAPartiallyOverlapB == OVERLAP_LOW_OF_A_IS_HIGH_OF_B)
   2980             return REGACCESS_N;
   2981         if(isAPartiallyOverlapB == OVERLAP_HIGH_OF_A_IS_LOW_OF_B || isAPartiallyOverlapB == OVERLAP_A_IS_HIGH_OF_B)
   2982             return REGACCESS_H;
   2983     }
   2984     if(A == REGACCESS_H || A == REGACCESS_HU || A == REGACCESS_UH) {
   2985         if(isAPartiallyOverlapB == OVERLAP_ALIGN || isAPartiallyOverlapB == OVERLAP_A_IS_HIGH_OF_B)
   2986             return REGACCESS_H;
   2987         if(isAPartiallyOverlapB == OVERLAP_B_IS_LOW_OF_A || isAPartiallyOverlapB == OVERLAP_HIGH_OF_A_IS_LOW_OF_B)
   2988             return REGACCESS_N;
   2989         if(isAPartiallyOverlapB == OVERLAP_B_IS_HIGH_OF_A) return REGACCESS_D;
   2990         if(isAPartiallyOverlapB == OVERLAP_LOW_OF_A_IS_HIGH_OF_B || isAPartiallyOverlapB == OVERLAP_A_IS_LOW_OF_B)
   2991             return REGACCESS_L;
   2992     }
   2993     return REGACCESS_N;
   2994 }
   2995 //! merge RegAccessType C1 with RegAccessType C2
   2996 
   2997 //!C can be N,L,H,D
   2998 RegAccessType updateAccess2(RegAccessType C1, RegAccessType C2) {
   2999     if(C1 == REGACCESS_D || C2 == REGACCESS_D) return REGACCESS_D;
   3000     if(C1 == REGACCESS_N) return C2;
   3001     if(C2 == REGACCESS_N) return C1;
   3002     if(C1 == REGACCESS_L && C2 == REGACCESS_H) return REGACCESS_D;
   3003     if(C1 == REGACCESS_H && C2 == REGACCESS_L) return REGACCESS_D;
   3004     return C1;
   3005 }
   3006 //! merge RegAccessType C with RegAccessType B
   3007 
   3008 //!C can be N,L,H,D
   3009 //!B can be U, D, UD, DU
   3010 RegAccessType updateAccess3(RegAccessType C, RegAccessType B) {
   3011     if(B == REGACCESS_D || B == REGACCESS_DU) return B; //no exposed usage
   3012     if(B == REGACCESS_U || B == REGACCESS_UD) {
   3013         if(C == REGACCESS_N) return B;
   3014         if(C == REGACCESS_L) return REGACCESS_LU;
   3015         if(C == REGACCESS_H) return REGACCESS_HU;
   3016         if(C == REGACCESS_D) return REGACCESS_DU;
   3017     }
   3018     return B;
   3019 }
   3020 //! merge RegAccessType A with RegAccessType B
   3021 
   3022 //!argument isBPartiallyOverlapA can be any value between -1 and 2
   3023 //!0 means fully overlapping, 1 means B is the lower half, 2 means B is the higher half
   3024 RegAccessType mergeAccess2(RegAccessType A, RegAccessType B, OverlapCase isBPartiallyOverlapA) {
   3025     if(A == REGACCESS_UD || A == REGACCESS_UL || A == REGACCESS_UH ||
   3026        A == REGACCESS_DU || A == REGACCESS_LU || A == REGACCESS_HU) return A;
   3027     if(A == REGACCESS_D) {
   3028         if(B == REGACCESS_D) return REGACCESS_D;
   3029         if(B == REGACCESS_U) return REGACCESS_DU;
   3030         if(B == REGACCESS_UD) return REGACCESS_DU;
   3031         if(B == REGACCESS_DU) return B;
   3032     }
   3033     if(A == REGACCESS_U) {
   3034         if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_UL;
   3035         if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_UH;
   3036         if(B == REGACCESS_D && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_UD;
   3037         if(B == REGACCESS_U) return A;
   3038         if(B == REGACCESS_UD && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_UL;
   3039         if(B == REGACCESS_UD && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_UH;
   3040         if(B == REGACCESS_UD && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_UD;
   3041         if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_UL;
   3042         if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_UH;
   3043         if(B == REGACCESS_DU && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_UD;
   3044     }
   3045     if(A == REGACCESS_L) {
   3046         if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_L;
   3047         if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_D;
   3048         if(B == REGACCESS_D && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_D;
   3049         if(B == REGACCESS_U) return REGACCESS_LU;
   3050         if(B == REGACCESS_UD) return REGACCESS_LU;
   3051         if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_LU;
   3052         if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_DU;
   3053         if(B == REGACCESS_DU && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_DU;
   3054     }
   3055     if(A == REGACCESS_H) {
   3056         if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_D;
   3057         if(B == REGACCESS_D && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_H;
   3058         if(B == REGACCESS_D && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_D;
   3059         if(B == REGACCESS_U) return REGACCESS_HU;
   3060         if(B == REGACCESS_UD) return REGACCESS_HU;
   3061         if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_LOW_OF_A) return REGACCESS_DU;
   3062         if(B == REGACCESS_DU && isBPartiallyOverlapA == OVERLAP_B_COVER_HIGH_OF_A) return REGACCESS_HU;
   3063         if(B == REGACCESS_DU && (isBPartiallyOverlapA == OVERLAP_B_COVER_A)) return REGACCESS_DU;
   3064     }
   3065     return REGACCESS_N;
   3066 }
   3067 
   3068 //!determines which part of a use is from a given definition
   3069 
   3070 //!reachingDefLive tells us which part of the def is live at this point
   3071 //!isDefPartiallyOverlapUse can be any value between -1 and 2
   3072 RegAccessType setAccessTypeOfUse(OverlapCase isDefPartiallyOverlapUse, RegAccessType reachingDefLive) {
   3073     if(isDefPartiallyOverlapUse == OVERLAP_B_COVER_A)
   3074         return reachingDefLive;
   3075     if(isDefPartiallyOverlapUse == OVERLAP_B_COVER_LOW_OF_A) { //def covers the low half of use
   3076         return REGACCESS_L;
   3077     }
   3078     if(isDefPartiallyOverlapUse == OVERLAP_B_COVER_HIGH_OF_A) {
   3079         return REGACCESS_H;
   3080     }
   3081     return REGACCESS_N;
   3082 }
   3083 
   3084 //! search currentBB->defUseTable to find a def for regNum at offsetPC
   3085 
   3086 //!
   3087 DefUsePair* searchDefUseTable(int offsetPC, int regNum, LowOpndRegType pType) {
   3088     DefUsePair* ptr = currentBB->defUseTable;
   3089     while(ptr != NULL) {
   3090         if(ptr->def.offsetPC == offsetPC &&
   3091            ptr->def.regNum == regNum &&
   3092            ptr->def.physicalType == pType) {
   3093             return ptr;
   3094         }
   3095         ptr = ptr->next;
   3096     }
   3097     return NULL;
   3098 }
   3099 void printDefUseTable() {
   3100     ALOGI("PRINT defUseTable --------");
   3101     DefUsePair* ptr = currentBB->defUseTable;
   3102     while(ptr != NULL) {
   3103         ALOGI("  def @ %x of VR %d %d has %d uses", ptr->def.offsetPC,
   3104               ptr->def.regNum, ptr->def.physicalType,
   3105               ptr->num_uses);
   3106         DefOrUseLink* ptr2 = ptr->uses;
   3107         while(ptr2 != NULL) {
   3108             ALOGI("    use @ %x of VR %d %d accessType %d", ptr2->offsetPC,
   3109                   ptr2->regNum,
   3110                   ptr2->physicalType,
   3111                   ptr2->accessType);
   3112             ptr2 = ptr2->next;
   3113         }
   3114         ptr = ptr->next;
   3115     }
   3116 }
   3117 //! when a VR is used, check whether a transfer from memory to XMM is necessary
   3118 
   3119 //!
   3120 int updateVRAtUse(int reg, LowOpndRegType pType, int regAll) {
   3121     int k;
   3122     for(k = 0; k < currentBB->num_xfer_points; k++) {
   3123         if(currentBB->xferPoints[k].offsetPC == offsetPC &&
   3124            currentBB->xferPoints[k].xtype == XFER_MEM_TO_XMM &&
   3125            currentBB->xferPoints[k].regNum == reg &&
   3126            currentBB->xferPoints[k].physicalType == pType) {
   3127 #ifdef DEBUG_XFER_POINTS
   3128             ALOGI("XFER from memory to xmm %d", reg);
   3129 #endif
   3130             move_mem_to_reg_noalloc(OpndSize_64,
   3131                                     4*currentBB->xferPoints[k].regNum, PhysicalReg_FP, true,
   3132                                     MemoryAccess_VR, currentBB->xferPoints[k].regNum,
   3133                                     regAll, true);
   3134         }
   3135     }
   3136     return 0;
   3137 }
   3138 ///////////////////////////////////////////////////////////////////////////////
   3139 // DEAD/USELESS STATEMENT ELMINATION
   3140 // bytecodes can be removed if a bytecode has no side effect and the defs are not used
   3141 // this optimization is guarded with DSE_OPT
   3142 // currently, this optimization is not on, since it does not provide observable performance improvement
   3143 //     and it increases compilation time
   3144 
   3145 /* we remove a maximal of 40 bytecodes within a single basic block */
   3146 #define MAX_NUM_DEAD_PC_IN_BB 40
   3147 int deadPCs[MAX_NUM_DEAD_PC_IN_BB];
   3148 int num_dead_pc = 0;
   3149 //! collect all PCs that can be removed
   3150 
   3151 //! traverse each byte code in the current basic block and check whether it can be removed, if yes, update deadPCs
   3152 void getDeadStmts() {
   3153     BasicBlock_O1* bb = currentBB;
   3154     int k;
   3155     num_dead_pc = 0;
   3156     //traverse each bytecode in the basic block
   3157     //update offsetPC, rPC & inst
   3158     u2* rPC_start = (u2*)currentMethod->insns;
   3159     MIR* mir;
   3160     for(mir = bb->jitBasicBlock->firstMIRInsn; mir; mir = mir->next) {
   3161         offsetPC = mir->seqNum;
   3162         rPC = rPC_start + mir->offset;
   3163         if(mir->dalvikInsn.opcode >= kNumPackedOpcodes) continue;
   3164 #ifdef DEBUG_DSE
   3165         ALOGI("DSE: offsetPC %x", offsetPC);
   3166 #endif
   3167         inst = FETCH(0);
   3168         bool isDeadStmt = true;
   3169         getVirtualRegInfo(infoByteCode);
   3170         u2 inst_op = INST_INST(inst);
   3171 	//skip bytecodes with side effect
   3172         if(inst_op != OP_CONST_STRING && inst_op != OP_CONST_STRING_JUMBO &&
   3173            inst_op != OP_MOVE && inst_op != OP_MOVE_OBJECT &&
   3174            inst_op != OP_MOVE_FROM16 && inst_op != OP_MOVE_OBJECT_FROM16 &&
   3175            inst_op != OP_MOVE_16 && inst_op != OP_CONST_CLASS &&
   3176            inst_op != OP_MOVE_OBJECT_16 && inst_op != OP_MOVE_WIDE &&
   3177            inst_op != OP_MOVE_WIDE_FROM16 && inst_op != OP_MOVE_WIDE_16 &&
   3178            inst_op != OP_MOVE_RESULT && inst_op != OP_MOVE_RESULT_OBJECT) {
   3179             continue;
   3180         }
   3181         //some statements do not define any VR!!!
   3182         int num_defs = 0;
   3183         for(k = 0; k < num_regs_per_bytecode; k++) {
   3184             if(infoByteCode[k].accessType == REGACCESS_D ||
   3185                infoByteCode[k].accessType == REGACCESS_UD ||
   3186                infoByteCode[k].accessType == REGACCESS_DU) { //search defUseTable
   3187                 num_defs++;
   3188                 DefUsePair* indexT = searchDefUseTable(offsetPC, infoByteCode[k].regNum, infoByteCode[k].physicalType);
   3189                 if(indexT == NULL) {
   3190                     ALOGE("def at %x of VR %d %d not in table",
   3191                            offsetPC, infoByteCode[k].regNum, infoByteCode[k].physicalType);
   3192                     return;
   3193                 }
   3194                 if(indexT->num_uses > 0) {
   3195                     isDeadStmt = false;
   3196                     break;
   3197                 } else {
   3198 #ifdef DEBUG_DSE
   3199                     ALOGI("DSE: num_uses is %d for def at %d for VR %d %d", indexT->num_uses,
   3200                           offsetPC, infoByteCode[k].regNum, infoByteCode[k].physicalType);
   3201 #endif
   3202                 }
   3203             }
   3204         } //for k
   3205         if(num_defs == 0) isDeadStmt = false;
   3206         if(isDeadStmt && num_dead_pc < MAX_NUM_DEAD_PC_IN_BB) {
   3207 #ifdef DEBUG_DSE
   3208             ALOGI("DSE: stmt at %x is dead", offsetPC);
   3209 #endif
   3210             deadPCs[num_dead_pc++] = offsetPC;
   3211         }
   3212     } //for offsetPC
   3213 #ifdef DEBUG_DSE
   3214     ALOGI("Dead Stmts: ");
   3215     for(k = 0; k < num_dead_pc; k++) ALOGI("%x ", deadPCs[k]);
   3216     ALOGI("");
   3217 #endif
   3218 }
   3219 //! entry point to remove dead statements
   3220 
   3221 //! recursively call getDeadStmts and remove uses in defUseTable that are from a dead PC
   3222 //! until there is no change to number of dead PCs
   3223 void removeDeadDefs() {
   3224     int k;
   3225     int deadPCs_2[MAX_NUM_DEAD_PC_IN_BB];
   3226     int num_dead_pc_2 = 0;
   3227     getDeadStmts();
   3228     if(num_dead_pc == 0) return;
   3229     DefUsePair* ptr = NULL;
   3230     DefOrUseLink* ptrUse = NULL;
   3231     DefOrUseLink* ptrUse_prev = NULL;
   3232     while(true) {
   3233         //check all the uses in defUseTable and remove any use that is from a dead PC
   3234         ptr = currentBB->defUseTable;
   3235         while(ptr != NULL) {
   3236             int k3;
   3237             ptrUse = ptr->uses;
   3238             ptrUse_prev = NULL;
   3239             while(ptrUse != NULL) {
   3240                 bool isIn = false;
   3241                 for(k3 = 0; k3 < num_dead_pc; k3++) {
   3242                     if(ptrUse->offsetPC == deadPCs[k3]) {
   3243                         isIn = true;
   3244                         break;
   3245                     }
   3246                 }//k3
   3247                 if(!isIn) {
   3248                     ptrUse_prev = ptrUse;
   3249                     ptrUse = ptrUse->next; //next use
   3250                 }
   3251                 else {
   3252                     //go to next use and remove ptrUse
   3253 #ifdef DEBUG_DSE
   3254                     ALOGI("DSE: remove usage at offsetPC %d reached by def at %d", ptrUse->offsetPC,
   3255                            ptr->def.offsetPC);
   3256 #endif
   3257                     DefOrUseLink* nextP = ptrUse->next;
   3258                     if(ptrUse == ptr->useTail) ptr->useTail = ptrUse_prev;
   3259                     free(ptrUse);
   3260                     if(ptrUse_prev == NULL) {
   3261                         ptr->uses = nextP;
   3262                     } else {
   3263                         ptrUse_prev->next = nextP;
   3264                     }
   3265                     ptrUse = nextP; //do not update ptrUse_prev
   3266                     ptr->num_uses--;
   3267                 }
   3268             }//while ptrUse
   3269             ptr = ptr->next;
   3270         }//while ptr
   3271 	//save deadPCs in deadPCs_2
   3272         num_dead_pc_2 = num_dead_pc;
   3273         for(k = 0; k < num_dead_pc_2; k++)
   3274             deadPCs_2[k] = deadPCs[k];
   3275 	//update deadPCs
   3276         getDeadStmts();
   3277 	//if no change to number of dead PCs, break out of the while loop
   3278         if(num_dead_pc_2 == num_dead_pc) break;
   3279     }//while
   3280 #ifdef DEBUG_DSE
   3281     ALOGI("DSE: DEAD STMTS: ");
   3282     for(k = 0; k < num_dead_pc; k++) {
   3283         ALOGI("%d ", deadPCs[k]);
   3284     }
   3285     ALOGI("");
   3286 #endif
   3287 }
   3288 /////////////////////////////////////////////////////////////
   3289 //!search memVRTable for a given virtual register
   3290 
   3291 //!
   3292 int searchMemTable(int regNum) {
   3293     int k;
   3294     for(k = 0; k < num_memory_vr; k++) {
   3295         if(memVRTable[k].regNum == regNum) {
   3296             return k;
   3297         }
   3298     }
   3299     ALOGW("in searchMemTable can't find VR %d num_memory_vr %d", regNum, num_memory_vr);
   3300     return -1;
   3301 }
   3302 /////////////////////////////////////////////////////////////////////////
   3303 // A VR is already in memory && NULL CHECK
   3304 //!check whether the latest content of a VR is in memory
   3305 
   3306 //!
   3307 bool isInMemory(int regNum, OpndSize size) {
   3308     int indexL = searchMemTable(regNum);
   3309     int indexH = -1;
   3310     if(size == OpndSize_64) indexH = searchMemTable(regNum+1);
   3311     if(indexL < 0) return false;
   3312     if(size == OpndSize_64 && indexH < 0) return false;
   3313     if(!memVRTable[indexL].inMemory) return false;
   3314     if(size == OpndSize_64 && (!memVRTable[indexH].inMemory)) return false;
   3315     return true;
   3316 }
   3317 //!set field inMemory of memVRTable to true
   3318 
   3319 //!
   3320 void setVRToMemory(int regNum, OpndSize size) {
   3321     int indexL = searchMemTable(regNum);
   3322     int indexH = -1;
   3323     if(size == OpndSize_64) indexH = searchMemTable(regNum+1);
   3324     if(indexL < 0) {
   3325         ALOGE("VR %d not in memVRTable", regNum);
   3326         return;
   3327     }
   3328     memVRTable[indexL].inMemory = true;
   3329     if(size == OpndSize_64) {
   3330         if(indexH < 0) {
   3331             ALOGE("VR %d not in memVRTable", regNum+1);
   3332             return;
   3333         }
   3334         memVRTable[indexH].inMemory = true;
   3335     }
   3336 }
   3337 //! check whether null check for a VR is performed previously
   3338 
   3339 //!
   3340 bool isVRNullCheck(int regNum, OpndSize size) {
   3341     if(size != OpndSize_32) {
   3342         ALOGE("isVRNullCheck size should be 32");
   3343         dvmAbort();
   3344     }
   3345     int indexL = searchMemTable(regNum);
   3346     if(indexL < 0) {
   3347         ALOGE("VR %d not in memVRTable", regNum);
   3348         return false;
   3349     }
   3350     return memVRTable[indexL].nullCheckDone;
   3351 }
   3352 bool isVRBoundCheck(int vr_array, int vr_index) {
   3353     int indexL = searchMemTable(vr_array);
   3354     if(indexL < 0) {
   3355         ALOGE("isVRBoundCheck: VR %d not in memVRTable", vr_array);
   3356         return false;
   3357     }
   3358     if(memVRTable[indexL].boundCheck.indexVR == vr_index)
   3359         return memVRTable[indexL].boundCheck.checkDone;
   3360     return false;
   3361 }
   3362 //! set nullCheckDone in memVRTable to true
   3363 
   3364 //!
   3365 void setVRNullCheck(int regNum, OpndSize size) {
   3366     if(size != OpndSize_32) {
   3367         ALOGE("setVRNullCheck size should be 32");
   3368         dvmAbort();
   3369     }
   3370     int indexL = searchMemTable(regNum);
   3371     if(indexL < 0) {
   3372         ALOGE("VR %d not in memVRTable", regNum);
   3373         return;
   3374     }
   3375     memVRTable[indexL].nullCheckDone = true;
   3376 }
   3377 void setVRBoundCheck(int vr_array, int vr_index) {
   3378     int indexL = searchMemTable(vr_array);
   3379     if(indexL < 0) {
   3380         ALOGE("setVRBoundCheck: VR %d not in memVRTable", vr_array);
   3381         return;
   3382     }
   3383     memVRTable[indexL].boundCheck.indexVR = vr_index;
   3384     memVRTable[indexL].boundCheck.checkDone = true;
   3385 }
   3386 void clearVRBoundCheck(int regNum, OpndSize size) {
   3387     int k;
   3388     for(k = 0; k < num_memory_vr; k++) {
   3389         if(memVRTable[k].regNum == regNum ||
   3390            (size == OpndSize_64 && memVRTable[k].regNum == regNum+1)) {
   3391             memVRTable[k].boundCheck.checkDone = false;
   3392         }
   3393         if(memVRTable[k].boundCheck.indexVR == regNum ||
   3394            (size == OpndSize_64 && memVRTable[k].boundCheck.indexVR == regNum+1)) {
   3395             memVRTable[k].boundCheck.checkDone = false;
   3396         }
   3397     }
   3398 }
   3399 //! set inMemory of memVRTable to false
   3400 
   3401 //!
   3402 void clearVRToMemory(int regNum, OpndSize size) {
   3403     int indexL = searchMemTable(regNum);
   3404     int indexH = -1;
   3405     if(size == OpndSize_64) indexH = searchMemTable(regNum+1);
   3406     if(indexL >= 0) {
   3407         memVRTable[indexL].inMemory = false;
   3408     }
   3409     if(size == OpndSize_64 && indexH >= 0) {
   3410         memVRTable[indexH].inMemory = false;
   3411     }
   3412 }
   3413 //! set nullCheckDone of memVRTable to false
   3414 
   3415 //!
   3416 void clearVRNullCheck(int regNum, OpndSize size) {
   3417     int indexL = searchMemTable(regNum);
   3418     int indexH = -1;
   3419     if(size == OpndSize_64) indexH = searchMemTable(regNum+1);
   3420     if(indexL >= 0) {
   3421         memVRTable[indexL].nullCheckDone = false;
   3422     }
   3423     if(size == OpndSize_64 && indexH >= 0) {
   3424         memVRTable[indexH].nullCheckDone = false;
   3425     }
   3426 }
   3427 
   3428 //! Extend Virtual Register life
   3429 
   3430 //! Requests that the life of a specific virtual register be extended. This ensures
   3431 //! that its mapping to a physical register won't be canceled while the extension
   3432 //! request is valid. NOTE: This does not support 64-bit values (when two adjacent
   3433 //! VRs are used)
   3434 //! @see cancelVRFreeDelayRequest
   3435 //! @see getVRFreeDelayRequested
   3436 //! @see VRFreeDelayFlags
   3437 //! @param regNum is the VR number
   3438 //! @param reason explains why freeing must be delayed. A single or combination
   3439 //! of VRFreeDelayFlags should be used.
   3440 //! @return negative value if request failed
   3441 int requestVRFreeDelay(int regNum, u4 reason) {
   3442     //TODO Add 64-bit operand support when needed
   3443     int indexL = searchMemTable(regNum);
   3444     if(indexL >= 0) {
   3445         memVRTable[indexL].delayFreeFlags |= reason;
   3446     } else {
   3447         ALOGE("requestVRFreeDelay: VR %d not in memVRTable", regNum);
   3448     }
   3449     return indexL;
   3450 }
   3451 
   3452 //! Cancel request for virtual register life extension
   3453 
   3454 //! Cancels any outstanding requests to extended liveness of VR. Additionally,
   3455 //! this ensures that if the VR is no longer life after this point, it will
   3456 //! no longer be associated with a physical register which can then be reused.
   3457 //! NOTE: This does not support 64-bit values (when two adjacent VRs are used)
   3458 //! @see requestVRFreeDelay
   3459 //! @see getVRFreeDelayRequested
   3460 //! @see VRFreeDelayFlags
   3461 //! @param regNum is the VR number
   3462 //! @param reason explains what freeing delay request should be canceled. A single
   3463 //! or combination of VRFreeDelayFlags should be used.
   3464 void cancelVRFreeDelayRequest(int regNum, u4 reason) {
   3465     //TODO Add 64-bit operand support when needed
   3466     bool needCallToFreeReg = false;
   3467     int indexL = searchMemTable(regNum);
   3468     if(indexL >= 0) {
   3469         if((memVRTable[indexL].delayFreeFlags & reason) != VRDELAY_NONE) { // don't cancel delay if it wasn't requested
   3470             memVRTable[indexL].delayFreeFlags ^= reason; // only cancel this particular reason, not all others
   3471             if(memVRTable[indexL].delayFreeFlags == VRDELAY_NONE)
   3472                 needCallToFreeReg = true; // freeReg might want to free this VR now if there is no longer a valid delay
   3473         }
   3474     }
   3475     if(needCallToFreeReg)
   3476         freeReg(true);
   3477 }
   3478 
   3479 //! Gets status of virtual register free delay request
   3480 
   3481 //! Finds out if there was a delay request for freeing this VR.
   3482 //! NOTE: This does not support 64-bit values (when two adjacent VRs are used)
   3483 //! @see requestVRFreeDelay
   3484 //! @see cancelVRFreeDelayRequest
   3485 //! @param regNum is the VR number
   3486 //! @return true if VR has an active delay request
   3487 bool getVRFreeDelayRequested(int regNum) {
   3488     //TODO Add 64-bit operand support when needed
   3489     int indexL = searchMemTable(regNum);
   3490     if(indexL >= 0) {
   3491         if(memVRTable[indexL].delayFreeFlags != VRDELAY_NONE)
   3492             return true;
   3493         return false;
   3494     }
   3495     return false;
   3496 }
   3497 
   3498 //! find the basic block that a bytecode is in
   3499 
   3500 //!
   3501 BasicBlock_O1* findForOffset(int offset) {
   3502     int k;
   3503     for(k = 0; k < num_bbs_for_method; k++) {
   3504         if(method_bbs_sorted[k]->pc_start <= offset && method_bbs_sorted[k]->pc_end > offset)
   3505             return method_bbs_sorted[k];
   3506     }
   3507     return NULL;
   3508 }
   3509 void dump_CFG(Method* method);
   3510 
   3511 int current_bc_size = -1;
   3512 
   3513 //! check whether a virtual register is used in a basic block
   3514 
   3515 //!
   3516 bool isUsedInBB(int regNum, int type, BasicBlock_O1* bb) {
   3517     int k;
   3518     for(k = 0; k < bb->num_regs; k++) {
   3519         if(bb->infoBasicBlock[k].physicalType == (type&MASK_FOR_TYPE) && bb->infoBasicBlock[k].regNum == regNum)
   3520             return true;
   3521     }
   3522     return false;
   3523 }
   3524 //! return the index to infoBasicBlock for a given virtual register
   3525 
   3526 //! return -1 if not found
   3527 int searchVirtualInfoOfBB(LowOpndRegType type, int regNum, BasicBlock_O1* bb) {
   3528     int k;
   3529     for(k = 0; k < bb->num_regs; k++) {
   3530         if(bb->infoBasicBlock[k].physicalType == type && bb->infoBasicBlock[k].regNum == regNum)
   3531             return k;
   3532     }
   3533     return -1;
   3534 }
   3535 //! return the index to compileTable for a given virtual register
   3536 
   3537 //! return -1 if not found
   3538 int searchCompileTable(int type, int regNum) { //returns the index
   3539     int k;
   3540     for(k = 0; k < num_compile_entries; k++) {
   3541         if(compileTable[k].physicalType == type && compileTable[k].regNum == regNum)
   3542             return k;
   3543     }
   3544     return -1;
   3545 }
   3546 //!check whether a physical register for a variable with typeA will work for another variable with typeB
   3547 
   3548 //!Type LowOpndRegType_ss is compatible with type LowOpndRegType_xmm
   3549 bool matchType(int typeA, int typeB) {
   3550     if((typeA & MASK_FOR_TYPE) == (typeB & MASK_FOR_TYPE)) return true;
   3551     if((typeA & MASK_FOR_TYPE) == LowOpndRegType_ss &&
   3552        (typeB & MASK_FOR_TYPE) == LowOpndRegType_xmm) return true;
   3553     if((typeA & MASK_FOR_TYPE) == LowOpndRegType_xmm &&
   3554        (typeB & MASK_FOR_TYPE) == LowOpndRegType_ss) return true;
   3555     return false;
   3556 }
   3557 //!check whether a virtual register is used in the current bytecode
   3558 
   3559 //!
   3560 bool isUsedInByteCode(int regNum, int type) {
   3561     getVirtualRegInfo(infoByteCode);
   3562     int k;
   3563     for(k = 0; k < num_regs_per_bytecode; k++) {
   3564         if(infoByteCode[k].physicalType == (type&MASK_FOR_TYPE) && infoByteCode[k].regNum == regNum)
   3565             return true;
   3566     }
   3567     return false;
   3568 }
   3569 //! obsolete
   3570 bool defineFirst(int atype) {
   3571     if(atype == REGACCESS_D || atype == REGACCESS_L || atype == REGACCESS_H || atype == REGACCESS_DU)
   3572         return true;
   3573     return false;
   3574 }
   3575 //!check whether a virtual register is updated in a basic block
   3576 
   3577 //!
   3578 bool notUpdated(RegAccessType atype) {
   3579     if(atype == REGACCESS_U) return true;
   3580     return false;
   3581 }
   3582 //!check whether a virtual register has exposed usage within a given basic block
   3583 
   3584 //!
   3585 bool hasExposedUsage2(BasicBlock_O1* bb, int index) {
   3586     RegAccessType atype = bb->infoBasicBlock[index].accessType;
   3587     if(atype == REGACCESS_D || atype == REGACCESS_L || atype == REGACCESS_H || atype == REGACCESS_DU)
   3588         return false;
   3589     return true;
   3590 }
   3591 //! return the spill location that is not used
   3592 
   3593 //!
   3594 int getSpillIndex(bool isGLUE, OpndSize size) {
   3595     if(isGLUE) return 0;
   3596     int k;
   3597     for(k = 1; k <= MAX_SPILL_JIT_IA-1; k++) {
   3598         if(size == OpndSize_64) {
   3599             if(k < MAX_SPILL_JIT_IA-1 && spillIndexUsed[k] == 0 && spillIndexUsed[k+1] == 0)
   3600                 return k;
   3601         }
   3602         else if(spillIndexUsed[k] == 0) {
   3603             return k;
   3604         }
   3605     }
   3606     ALOGE("can't find spill position in spillLogicalReg");
   3607     return -1;
   3608 }
   3609 //!this is called before generating a native code, it sets entries in array canSpillReg to true
   3610 
   3611 //!startNativeCode must be paired with endNativeCode
   3612 void startNativeCode(int vr_num, int vr_type) {
   3613     int k;
   3614     for(k = 0; k < PhysicalReg_Null; k++) {
   3615         canSpillReg[k] = true;
   3616     }
   3617     inGetVR_num = vr_num;
   3618     inGetVR_type = vr_type;
   3619 }
   3620 //! called right after generating a native code
   3621 
   3622 //!It sets entries in array canSpillReg to true and reset inGetVR_num to -1
   3623 void endNativeCode() {
   3624     int k;
   3625     for(k = 0; k < PhysicalReg_Null; k++) {
   3626         canSpillReg[k] = true;
   3627     }
   3628     inGetVR_num = -1;
   3629 }
   3630 //! set canSpillReg[physicalReg] to false
   3631 
   3632 //!
   3633 void donotSpillReg(int physicalReg) {
   3634     canSpillReg[physicalReg] = false;
   3635 }
   3636 //! set canSpillReg[physicalReg] to true
   3637 
   3638 //!
   3639 void doSpillReg(int physicalReg) {
   3640     canSpillReg[physicalReg] = true;
   3641 }
   3642 //! touch hardcoded register %ecx and reduce its reference count
   3643 
   3644 //!
   3645 int touchEcx() {
   3646     //registerAlloc will spill logical reg that is mapped to ecx
   3647     //registerAlloc will reduce refCount
   3648     registerAlloc(LowOpndRegType_gp, PhysicalReg_ECX, true, true);
   3649     return 0;
   3650 }
   3651 //! touch hardcoded register %eax and reduce its reference count
   3652 
   3653 //!
   3654 int touchEax() {
   3655     registerAlloc(LowOpndRegType_gp, PhysicalReg_EAX, true, true);
   3656     return 0;
   3657 }
   3658 int touchEsi() {
   3659     registerAlloc(LowOpndRegType_gp, PhysicalReg_ESI, true, true);
   3660     return 0;
   3661 }
   3662 int touchXmm1() {
   3663     registerAlloc(LowOpndRegType_xmm, XMM_1, true, true);
   3664     return 0;
   3665 }
   3666 int touchEbx() {
   3667     registerAlloc(LowOpndRegType_gp, PhysicalReg_EBX, true, true);
   3668     return 0;
   3669 }
   3670 
   3671 //! touch hardcoded register %edx and reduce its reference count
   3672 
   3673 //!
   3674 int touchEdx() {
   3675     registerAlloc(LowOpndRegType_gp, PhysicalReg_EDX, true, true);
   3676     return 0;
   3677 }
   3678 
   3679 #ifdef HACK_FOR_DEBUG
   3680 //for debugging purpose, instructions are added at a certain place
   3681 bool hacked = false;
   3682 void hackBug() {
   3683   if(!hacked && iget_obj_inst == 13) {
   3684 #if 0
   3685     move_reg_to_reg_noalloc(OpndSize_32, PhysicalReg_EBX, true, PhysicalReg_ECX, true);
   3686     //move from ebx to ecx & update compileTable for v3
   3687     int tIndex = searchCompileTable(LowOpndRegType_virtual | LowOpndRegType_gp, 3);
   3688     if(tIndex < 0) ALOGE("hack can't find VR3");
   3689     compileTable[tIndex].physicalReg = PhysicalReg_ECX;
   3690 #else
   3691     move_reg_to_mem_noalloc(OpndSize_32, PhysicalReg_EBX, true, 12, PhysicalReg_FP, true);
   3692 #endif
   3693   }
   3694 }
   3695 void hackBug2() {
   3696   if(!hacked && iget_obj_inst == 13) {
   3697     dump_imm_mem_noalloc(Mnemonic_MOV, OpndSize_32, 0, 12, PhysicalReg_FP, true);
   3698     hacked = true;
   3699   }
   3700 }
   3701 #endif
   3702 
   3703 //! this function is called before calling a helper function or a vm function
   3704 int beforeCall(const char* target) { //spill all live registers
   3705     if(currentBB == NULL) return -1;
   3706 
   3707     /* special case for ncgGetEIP: this function only updates %edx */
   3708     if(!strcmp(target, "ncgGetEIP")) {
   3709         touchEdx();
   3710         return -1;
   3711     }
   3712 
   3713     /* these functions use %eax for the return value */
   3714     if((!strcmp(target, "dvmInstanceofNonTrivial")) ||
   3715        (!strcmp(target, "dvmUnlockObject")) ||
   3716        (!strcmp(target, "dvmAllocObject")) ||
   3717        (!strcmp(target, "dvmAllocArrayByClass")) ||
   3718        (!strcmp(target, "dvmAllocPrimitiveArray")) ||
   3719        (!strcmp(target, "dvmInterpHandleFillArrayData")) ||
   3720        (!strcmp(target, "dvmFindInterfaceMethodInCache")) ||
   3721        (!strcmp(target, "dvmNcgHandlePackedSwitch")) ||
   3722        (!strcmp(target, "dvmNcgHandleSparseSwitch")) ||
   3723        (!strcmp(target, "dvmCanPutArrayElement")) ||
   3724        (!strcmp(target, "moddi3")) || (!strcmp(target, "divdi3")) ||
   3725        (!strcmp(target, "execute_inline"))
   3726        || (!strcmp(target, "dvmJitToPatchPredictedChain"))
   3727        || (!strcmp(target, "dvmJitHandlePackedSwitch"))
   3728        || (!strcmp(target, "dvmJitHandleSparseSwitch"))
   3729        ) {
   3730         touchEax();
   3731     }
   3732 
   3733     //these two functions also use %edx for the return value
   3734     if((!strcmp(target, "moddi3")) || (!strcmp(target, "divdi3"))) {
   3735         touchEdx();
   3736     }
   3737     if((!strcmp(target, ".new_instance_helper"))) {
   3738         touchEsi(); touchEax();
   3739     }
   3740 #if defined(ENABLE_TRACING)
   3741     if((!strcmp(target, "common_periodicChecks4"))) {
   3742         touchEdx();
   3743     }
   3744 #endif
   3745     if((!strcmp(target, ".const_string_helper"))) {
   3746         touchEcx(); touchEax();
   3747     }
   3748     if((!strcmp(target, ".check_cast_helper"))) {
   3749         touchEbx(); touchEsi();
   3750     }
   3751     if((!strcmp(target, ".instance_of_helper"))) {
   3752         touchEbx(); touchEsi(); touchEcx();
   3753     }
   3754     if((!strcmp(target, ".monitor_enter_helper"))) {
   3755         touchEbx();
   3756     }
   3757     if((!strcmp(target, ".monitor_exit_helper"))) {
   3758         touchEbx();
   3759     }
   3760     if((!strcmp(target, ".aget_wide_helper"))) {
   3761         touchEbx(); touchEcx(); touchXmm1();
   3762     }
   3763     if((!strcmp(target, ".aget_helper")) || (!strcmp(target, ".aget_char_helper")) ||
   3764        (!strcmp(target, ".aget_short_helper")) || (!strcmp(target, ".aget_bool_helper")) ||
   3765        (!strcmp(target, ".aget_byte_helper"))) {
   3766         touchEbx(); touchEcx(); touchEdx();
   3767     }
   3768     if((!strcmp(target, ".aput_helper")) || (!strcmp(target, ".aput_char_helper")) ||
   3769        (!strcmp(target, ".aput_short_helper")) || (!strcmp(target, ".aput_bool_helper")) ||
   3770        (!strcmp(target, ".aput_byte_helper")) || (!strcmp(target, ".aput_wide_helper"))) {
   3771         touchEbx(); touchEcx(); touchEdx();
   3772     }
   3773     if((!strcmp(target, ".sput_helper")) || (!strcmp(target, ".sput_wide_helper"))) {
   3774         touchEdx(); touchEax();
   3775     }
   3776     if((!strcmp(target, ".sget_helper"))) {
   3777         touchEdx(); touchEcx();
   3778     }
   3779     if((!strcmp(target, ".sget_wide_helper"))) {
   3780         touchEdx(); touchXmm1();
   3781     }
   3782     if((!strcmp(target, ".aput_obj_helper"))) {
   3783         touchEdx(); touchEcx(); touchEax();
   3784     }
   3785     if((!strcmp(target, ".iput_helper")) || (!strcmp(target, ".iput_wide_helper"))) {
   3786         touchEbx(); touchEcx(); touchEsi();
   3787     }
   3788     if((!strcmp(target, ".iget_helper"))) {
   3789         touchEbx(); touchEcx(); touchEdx();
   3790     }
   3791     if((!strcmp(target, ".iget_wide_helper"))) {
   3792         touchEbx(); touchEcx(); touchXmm1();
   3793     }
   3794     if((!strcmp(target, ".new_array_helper"))) {
   3795         touchEbx(); touchEdx(); touchEax();
   3796     }
   3797     if((!strcmp(target, ".invoke_virtual_helper"))) {
   3798         touchEbx(); touchEcx();
   3799     }
   3800     if((!strcmp(target, ".invoke_direct_helper"))) {
   3801         touchEsi(); touchEcx();
   3802     }
   3803     if((!strcmp(target, ".invoke_super_helper"))) {
   3804         touchEbx(); touchEcx();
   3805     }
   3806     if((!strcmp(target, ".invoke_interface_helper"))) {
   3807         touchEbx(); touchEcx();
   3808     }
   3809     if((!strcmp(target, ".invokeMethodNoRange_5_helper")) ||
   3810        (!strcmp(target, ".invokeMethodNoRange_4_helper"))) {
   3811         touchEbx(); touchEsi(); touchEax(); touchEdx();
   3812     }
   3813     if((!strcmp(target, ".invokeMethodNoRange_3_helper"))) {
   3814         touchEbx(); touchEsi(); touchEax();
   3815     }
   3816     if((!strcmp(target, ".invokeMethodNoRange_2_helper"))) {
   3817         touchEbx(); touchEsi();
   3818     }
   3819     if((!strcmp(target, ".invokeMethodNoRange_1_helper"))) {
   3820         touchEbx();
   3821     }
   3822     if((!strcmp(target, ".invokeMethodRange_helper"))) {
   3823         touchEdx(); touchEsi();
   3824     }
   3825 #ifdef DEBUG_REGALLOC
   3826     ALOGI("enter beforeCall");
   3827 #endif
   3828     if(!strncmp(target, ".invokeArgsDone", 15)) resetGlue(PhysicalReg_GLUE_DVMDEX);
   3829 
   3830     freeReg(true); //to avoid spilling dead logical registers
   3831     int k;
   3832     for(k = 0; k < num_compile_entries; k++) {
   3833         /* before throwing an exception, if GLUE is spilled, load to %ebp
   3834            this should happen at last */
   3835         if(k == indexForGlue) continue;
   3836         if(compileTable[k].physicalReg != PhysicalReg_Null &&
   3837            (compileTable[k].physicalType & LowOpndRegType_hard) == 0) {
   3838             /* handles non hardcoded variables that are in physical registers */
   3839             if(!strcmp(target, "exception")) {
   3840                 /* before throwing an exception
   3841                    update contents of all VRs in Java stack */
   3842                 if(!isVirtualReg(compileTable[k].physicalType)) continue;
   3843                 /* to have correct GC, we should update contents for L VRs as well */
   3844                 //if(compileTable[k].gType == GLOBALTYPE_L) continue;
   3845             }
   3846             if((!strcmp(target, ".const_string_resolve")) ||
   3847                (!strcmp(target, ".static_field_resolve")) ||
   3848                (!strcmp(target, ".inst_field_resolve")) ||
   3849                (!strcmp(target, ".class_resolve")) ||
   3850                (!strcmp(target, ".direct_method_resolve")) ||
   3851                (!strcmp(target, ".virtual_method_resolve")) ||
   3852                (!strcmp(target, ".static_method_resolve"))) {
   3853                /* physical register %ebx will keep its content
   3854                   but to have correct GC, we should dump content of a VR
   3855                      that is mapped to %ebx */
   3856                 if(compileTable[k].physicalReg == PhysicalReg_EBX &&
   3857                    (!isVirtualReg(compileTable[k].physicalType)))
   3858                     continue;
   3859             }
   3860             if((!strncmp(target, "dvm", 3)) || (!strcmp(target, "moddi3")) ||
   3861                (!strcmp(target, "divdi3")) ||
   3862                (!strcmp(target, "fmod")) || (!strcmp(target, "fmodf"))) {
   3863                 /* callee-saved registers (%ebx, %esi, %ebp, %edi) will keep the content
   3864                    but to have correct GC, we should dump content of a VR
   3865                       that is mapped to a callee-saved register */
   3866                 if((compileTable[k].physicalReg == PhysicalReg_EBX ||
   3867                     compileTable[k].physicalReg == PhysicalReg_ESI) &&
   3868                    (!isVirtualReg(compileTable[k].physicalType)))
   3869                     continue;
   3870             }
   3871 #ifdef DEBUG_REGALLOC
   3872             ALOGI("SPILL logical register %d %d in beforeCall",
   3873                   compileTable[k].regNum, compileTable[k].physicalType);
   3874 #endif
   3875             spillLogicalReg(k, true);
   3876         }
   3877     }
   3878     if(indexForGlue >= 0 && !strcmp(target, "exception") &&
   3879        compileTable[indexForGlue].physicalReg == PhysicalReg_Null) {
   3880         unspillLogicalReg(indexForGlue, PhysicalReg_EBP); //load %ebp
   3881     }
   3882 #ifdef DEBUG_REGALLOC
   3883     ALOGI("exit beforeCall");
   3884 #endif
   3885     return 0;
   3886 }
   3887 int getFreeReg(int type, int reg, int indexToCompileTable);
   3888 //! after calling a helper function or a VM function
   3889 
   3890 //!
   3891 int afterCall(const char* target) { //un-spill
   3892     if(currentBB == NULL) return -1;
   3893     if(!strcmp(target, "ncgGetEIP")) return -1;
   3894 
   3895     return 0;
   3896 }
   3897 //! check whether a temporary is 8-bit
   3898 
   3899 //!
   3900 bool isTemp8Bit(int type, int reg) {
   3901     if(currentBB == NULL) return false;
   3902     if(!isTemporary(type, reg)) return false;
   3903     int k;
   3904     for(k = 0; k < num_temp_regs_per_bytecode; k++) {
   3905         if(infoByteCodeTemp[k].physicalType == type &&
   3906            infoByteCodeTemp[k].regNum == reg) {
   3907             return infoByteCodeTemp[k].is8Bit;
   3908         }
   3909     }
   3910     ALOGE("isTemp8Bit %d %d", type, reg);
   3911     return false;
   3912 }
   3913 
   3914 /* functions to access live ranges of a VR
   3915    Live range info is stored in memVRTable[].ranges, which is a linked list
   3916 */
   3917 //! check whether a VR is live at the current bytecode
   3918 
   3919 //!
   3920 bool isVRLive(int vA) {
   3921     int index = searchMemTable(vA);
   3922     if(index < 0) {
   3923         ALOGE("couldn't find VR %d in memTable", vA);
   3924         return false;
   3925     }
   3926     LiveRange* ptr = memVRTable[index].ranges;
   3927     while(ptr != NULL) {
   3928         if(offsetPC >= ptr->start && offsetPC <= ptr->end) return true;
   3929         ptr = ptr->next;
   3930     }
   3931     return false;
   3932 }
   3933 
   3934 //! check whether the current bytecode is the last access to a VR within a live range
   3935 
   3936 //!for 64-bit VR, return true only when true for both low half and high half
   3937 bool isLastByteCodeOfLiveRange(int compileIndex) {
   3938     int k = compileIndex;
   3939     OpndSize tSize = getRegSize(compileTable[k].physicalType);
   3940     int index;
   3941     LiveRange* ptr = NULL;
   3942     if(tSize == OpndSize_32) {
   3943         /* check live ranges for the VR */
   3944         index = searchMemTable(compileTable[k].regNum);
   3945         if(index < 0) {
   3946             ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
   3947             return false;
   3948         }
   3949         ptr = memVRTable[index].ranges;
   3950         while(ptr != NULL) {
   3951             if(offsetPC == ptr->end) return true;
   3952             ptr = ptr->next;
   3953         }
   3954         return false;
   3955     }
   3956     /* size of the VR is 64 */
   3957     /* check live ranges of the low half */
   3958     index = searchMemTable(compileTable[k].regNum);
   3959     bool tmpB = false;
   3960     if(index < 0) {
   3961         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
   3962         return false;
   3963     }
   3964     ptr = memVRTable[index].ranges;
   3965     while(ptr != NULL) {
   3966         if(offsetPC == ptr->end) {
   3967             tmpB = true;
   3968             break;
   3969         }
   3970         ptr = ptr->next;
   3971     }
   3972     if(!tmpB) return false;
   3973     /* check live ranges of the high half */
   3974     index = searchMemTable(compileTable[k].regNum+1);
   3975     if(index < 0) {
   3976         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
   3977         return false;
   3978     }
   3979     ptr = memVRTable[index].ranges;
   3980     while(ptr != NULL) {
   3981         if(offsetPC == ptr->end) {
   3982             return true;
   3983         }
   3984         ptr = ptr->next;
   3985     }
   3986     return false;
   3987 }
   3988 
   3989 //! check whether the current bytecode is in a live range that extends to end of a basic block
   3990 
   3991 //!for 64 bit, return true if true for both low half and high half
   3992 bool reachEndOfBB(int compileIndex) {
   3993     int k = compileIndex;
   3994     OpndSize tSize = getRegSize(compileTable[k].physicalType);
   3995     int index;
   3996     bool retCode = false;
   3997     /* check live ranges of the low half */
   3998     index = searchMemTable(compileTable[k].regNum);
   3999     if(index < 0) {
   4000         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
   4001         return false;
   4002     }
   4003     LiveRange* ptr = memVRTable[index].ranges;
   4004     while(ptr != NULL) {
   4005         if(offsetPC >= ptr->start &&
   4006            offsetPC <= ptr->end) {
   4007             if(ptr->end == currentBB->pc_end) {
   4008                 retCode = true;
   4009             }
   4010             break;
   4011         }
   4012         ptr = ptr->next;
   4013     }
   4014     if(!retCode) return false;
   4015     if(tSize == OpndSize_32) return true;
   4016     /* check live ranges of the high half */
   4017     index = searchMemTable(compileTable[k].regNum+1);
   4018     if(index < 0) {
   4019         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
   4020         return false;
   4021     }
   4022     ptr = memVRTable[index].ranges;
   4023     while(ptr != NULL) {
   4024         if(offsetPC >= ptr->start &&
   4025            offsetPC <= ptr->end) {
   4026             if(ptr->end == currentBB->pc_end) return true;
   4027             return false;
   4028         }
   4029         ptr = ptr->next;
   4030     }
   4031 #ifdef PRINT_WARNING
   4032     ALOGW("offsetPC %d not in live range of VR %d", offsetPC, compileTable[k].regNum+1);
   4033 #endif
   4034     return false;
   4035 }
   4036 
   4037 //!check whether the current bytecode is the next to last access to a VR within a live range
   4038 
   4039 //!for 64 bit, return true if true for both low half and high half
   4040 bool isNextToLastAccess(int compileIndex) {
   4041     int k = compileIndex;
   4042     OpndSize tSize = getRegSize(compileTable[k].physicalType);
   4043     int index;
   4044     /* check live ranges for the low half */
   4045     bool retCode = false;
   4046     index = searchMemTable(compileTable[k].regNum);
   4047     if(index < 0) {
   4048         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
   4049         return false;
   4050     }
   4051     LiveRange* ptr = memVRTable[index].ranges;
   4052     while(ptr != NULL) {
   4053         int num_access = ptr->num_access;
   4054 
   4055         if(num_access < 2) {
   4056            ptr = ptr->next;
   4057            continue;
   4058         }
   4059 
   4060         if(offsetPC == ptr->accessPC[num_access-2]) {
   4061            retCode = true;
   4062            break;
   4063         }
   4064         ptr = ptr->next;
   4065     }
   4066     if(!retCode) return false;
   4067     if(tSize == OpndSize_32) return true;
   4068     /* check live ranges for the high half */
   4069     index = searchMemTable(compileTable[k].regNum+1);
   4070     if(index < 0) {
   4071         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
   4072         return false;
   4073     }
   4074     ptr = memVRTable[index].ranges;
   4075     while(ptr != NULL) {
   4076         int num_access = ptr->num_access;
   4077 
   4078         if(num_access < 2) {
   4079            ptr = ptr->next;
   4080            continue;
   4081         }
   4082 
   4083         if(offsetPC == ptr->accessPC[num_access-2]) return true;
   4084         ptr = ptr->next;
   4085     }
   4086     return false;
   4087 }
   4088 
   4089 /** return the start of the next live range
   4090     if there does not exist a next live range, return pc_end of the basic block
   4091     for 64 bits, return the larger one for low half and high half
   4092     Assume live ranges are sorted in order
   4093 */
   4094 int getNextLiveRange(int compileIndex) {
   4095     int k = compileIndex;
   4096     OpndSize tSize = getRegSize(compileTable[k].physicalType);
   4097     /* check live ranges of the low half */
   4098     int index;
   4099     index = searchMemTable(compileTable[k].regNum);
   4100     if(index < 0) {
   4101         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
   4102         return offsetPC;
   4103     }
   4104     bool found = false;
   4105     int nextUse = offsetPC;
   4106     LiveRange* ptr = memVRTable[index].ranges;
   4107     while(ptr != NULL) {
   4108         if(ptr->start > offsetPC) {
   4109             nextUse = ptr->start;
   4110             found = true;
   4111             break;
   4112         }
   4113         ptr = ptr->next;
   4114     }
   4115     if(!found) return currentBB->pc_end;
   4116     if(tSize == OpndSize_32) return nextUse;
   4117 
   4118     /* check live ranges of the high half */
   4119     found = false;
   4120     index = searchMemTable(compileTable[k].regNum+1);
   4121     if(index < 0) {
   4122         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
   4123         return offsetPC;
   4124     }
   4125     int nextUse2 = offsetPC;
   4126     ptr = memVRTable[index].ranges;
   4127     while(ptr != NULL) {
   4128         if(ptr->start > offsetPC) {
   4129             nextUse2 = ptr->start;
   4130             found = true;
   4131             break;
   4132         }
   4133         ptr = ptr->next;
   4134     }
   4135     if(!found) return currentBB->pc_end;
   4136     /* return the larger one */
   4137     return (nextUse2 > nextUse ? nextUse2 : nextUse);
   4138 }
   4139 
   4140 /** return the next access to a variable
   4141     If variable is 64-bit, get the next access to the lower half and the high half
   4142         return the eariler one
   4143 */
   4144 int getNextAccess(int compileIndex) {
   4145     int k = compileIndex;
   4146     OpndSize tSize = getRegSize(compileTable[k].physicalType);
   4147     int index, k3;
   4148     /* check live ranges of the low half */
   4149     index = searchMemTable(compileTable[k].regNum);
   4150     if(index < 0) {
   4151         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum);
   4152         return offsetPC;
   4153     }
   4154     bool found = false;
   4155     int nextUse = offsetPC;
   4156     LiveRange* ptr = memVRTable[index].ranges;
   4157     while(ptr != NULL) {
   4158         if(offsetPC >= ptr->start &&
   4159            offsetPC <= ptr->end) {
   4160             /* offsetPC belongs to this live range */
   4161             for(k3 = 0; k3 < ptr->num_access; k3++) {
   4162                 if(ptr->accessPC[k3] > offsetPC) {
   4163                     nextUse = ptr->accessPC[k3];
   4164                     break;
   4165                 }
   4166             }
   4167             found = true;
   4168             break;
   4169         }
   4170         ptr = ptr->next;
   4171     }
   4172 #ifdef PRINT_WARNING
   4173     if(!found)
   4174         ALOGW("offsetPC %d not in live range of VR %d", offsetPC, compileTable[k].regNum);
   4175 #endif
   4176     if(tSize == OpndSize_32) return nextUse;
   4177 
   4178     /* check live ranges of the high half */
   4179     found = false;
   4180     index = searchMemTable(compileTable[k].regNum+1);
   4181     if(index < 0) {
   4182         ALOGE("couldn't find VR %d in memTable", compileTable[k].regNum+1);
   4183         return offsetPC;
   4184     }
   4185     int nextUse2 = offsetPC;
   4186     ptr = memVRTable[index].ranges;
   4187     while(ptr != NULL) {
   4188         if(offsetPC >= ptr->start &&
   4189            offsetPC <= ptr->end) {
   4190             for(k3 = 0; k3 < ptr->num_access; k3++) {
   4191                 if(ptr->accessPC[k3] > offsetPC) {
   4192                     nextUse2 = ptr->accessPC[k3];
   4193                     break;
   4194                 }
   4195             }
   4196             found = true;
   4197             break;
   4198         }
   4199         ptr = ptr->next;
   4200     }
   4201 #ifdef PRINT_WARNING
   4202     if(!found) ALOGW("offsetPC %d not in live range of VR %d", offsetPC, compileTable[k].regNum+1);
   4203 #endif
   4204     /* return the earlier one */
   4205     if(nextUse2 < nextUse) return nextUse2;
   4206     return nextUse;
   4207 }
   4208 
   4209 /** free variables that are no longer in use
   4210     free a temporary with reference count of zero
   4211     will dump content of a GL VR to memory if necessary
   4212 */
   4213 int freeReg(bool spillGL) {
   4214     if(currentBB == NULL) return 0;
   4215     int k;
   4216     for(k = 0; k < num_compile_entries; k++) {
   4217         if(compileTable[k].refCount == 0 && compileTable[k].physicalReg != PhysicalReg_Null) {
   4218             /* check entries with reference count of zero and is mapped to a physical register */
   4219             bool typeA = !isVirtualReg(compileTable[k].physicalType);
   4220             bool freeCrit = true, delayFreeing = false;
   4221             bool typeC = false, typeB = false, reachEnd = false;
   4222             if(isVirtualReg(compileTable[k].physicalType)) {
   4223                 /* VRs in the compile table */
   4224 
   4225                 /* Check if delay for freeing was requested for this VR */
   4226                 delayFreeing = getVRFreeDelayRequested(compileTable[k].regNum);
   4227 
   4228                 freeCrit = isLastByteCodeOfLiveRange(k); /* last bytecode of a live range */
   4229                 reachEnd = reachEndOfBB(k); /* in a live range that extends to end of a basic block */
   4230 #ifdef DEBUG_LIVE_RANGE
   4231                 ALOGI("IN freeReg: VR %d offsetPC %x freecrit %d reachEnd %d nextToLast %d", compileTable[k].regNum, offsetPC, freeCrit, reachEnd, isNextToLastAccess(k));
   4232 #endif
   4233                 /* Bug: spilling of VRs after edi(rFP) is updated in RETURN bytecode
   4234                         will cause variables for callee to be spilled to the caller stack frame and
   4235                                                         to overwrite varaibles for caller
   4236                 */
   4237                 /* last bytecode of a live range reaching end of BB if not counting the fake usage at end */
   4238                 bool boolB = reachEnd && isNextToLastAccess(k);
   4239                 /* Bug: when a GG VR is checked at end of a basic block,
   4240                         freeCrit will be true and physicalReg will be set to Null
   4241                    Fix: change free condition from freeCrit to (freeCrit && offsetPC != currentBB->pc_end)
   4242                 */
   4243                 /* conditions to free a GG VR:
   4244                        last bytecode of a live range reaching end of BB if not counting the fake usage at end && endsWithReturn
   4245                        or
   4246                        last bytecode of a live range && offsetPC != currentBB->pc_end
   4247                            -> last bytecode of a live range not reaching end
   4248                 */
   4249                 typeC = ((freeCrit && offsetPC != currentBB->pc_end) ||
   4250                          (currentBB->endsWithReturn && boolB)) &&
   4251                         compileTable[k].gType == GLOBALTYPE_GG &&
   4252                         !delayFreeing;
   4253                 /* conditions to free a L|GL VR:
   4254                        last bytecode of a live range
   4255                        or
   4256                        last bytecode of a live range reaching end of BB if not counting the fake usage at end
   4257                 */
   4258                 typeB = (freeCrit || boolB) &&
   4259                         (compileTable[k].gType != GLOBALTYPE_GG) &&
   4260                         !delayFreeing;
   4261             }
   4262             if(typeA || typeB || typeC) {
   4263 #ifdef DEBUG_REGALLOC
   4264                 if(typeA)
   4265                     ALOGI("FREE TEMP %d with type %d allocated to %d",
   4266                            compileTable[k].regNum, compileTable[k].physicalType,
   4267                            compileTable[k].physicalReg);
   4268                 else if(typeB)
   4269                     ALOGI("FREE VR L|GL %d with type %d allocated to %d",
   4270                            compileTable[k].regNum, compileTable[k].physicalType,
   4271                            compileTable[k].physicalReg);
   4272                 else if(typeC)
   4273                     ALOGI("FREE VR GG %d with type %d allocated to %d",
   4274                            compileTable[k].regNum, compileTable[k].physicalType,
   4275                            compileTable[k].physicalReg);
   4276 #endif
   4277                 bool dumpGL = false;
   4278                 if(compileTable[k].gType == GLOBALTYPE_GL && !reachEnd) {
   4279                     /* if the live range does not reach end of basic block
   4280                        and there exists a try block from offsetPC to the next live range
   4281                            dump VR to interpreted stack */
   4282                     int tmpPC = getNextLiveRange(k);
   4283                     if(existATryBlock(currentMethod, offsetPC, tmpPC)) dumpGL = true;
   4284                 }
   4285                 /* if the live range reach end of basic block, dump VR to interpreted stack */
   4286                 if(compileTable[k].gType == GLOBALTYPE_GL && reachEnd) dumpGL = true;
   4287                 if(dumpGL) {
   4288                     if(spillGL) {
   4289 #ifdef DEBUG_REGALLOC
   4290                         ALOGI("SPILL VR GL %d %d", compileTable[k].regNum, compileTable[k].physicalType);
   4291 #endif
   4292                         spillLogicalReg(k, true); //will dump VR to memory & update physicalReg
   4293                     }
   4294                 }
   4295                 else
   4296                      compileTable[k].physicalReg = PhysicalReg_Null;
   4297             }
   4298             if(typeA) {
   4299                 if(compileTable[k].spill_loc_index >= 0) {
   4300                     /* update spill info for temporaries */
   4301                     spillIndexUsed[compileTable[k].spill_loc_index >> 2] = 0;
   4302                     compileTable[k].spill_loc_index = -1;
   4303                     ALOGE("free a temporary register with TRSTATE_SPILLED");
   4304                 }
   4305             }
   4306         }
   4307     }
   4308     syncAllRegs(); //sync up allRegs (isUsed & freeTimeStamp) with compileTable
   4309     return 0;
   4310 }
   4311 
   4312 //! reduce the reference count by 1
   4313 
   4314 //! input: index to compileTable
   4315 void decreaseRefCount(int index) {
   4316 #ifdef DEBUG_REFCOUNT
   4317     ALOGI("REFCOUNT: %d in decreaseRefCount %d %d", compileTable[index].refCount,
   4318             compileTable[index].regNum, compileTable[index].physicalType);
   4319 #endif
   4320     compileTable[index].refCount--;
   4321     if(compileTable[index].refCount < 0) {
   4322         ALOGE("refCount is negative for REG %d %d", compileTable[index].regNum, compileTable[index].physicalType);
   4323         dvmAbort();
   4324     }
   4325 }
   4326 //! reduce the reference count of a VR by 1
   4327 
   4328 //! input: reg & type
   4329 int updateRefCount(int reg, LowOpndRegType type) {
   4330     if(currentBB == NULL) return 0;
   4331     int index = searchCompileTable(LowOpndRegType_virtual | type, reg);
   4332     if(index < 0) {
   4333         ALOGE("virtual reg %d type %d not found in updateRefCount", reg, type);
   4334         return -1;
   4335     }
   4336     decreaseRefCount(index);
   4337     return 0;
   4338 }
   4339 //! reduce the reference count of a variable by 1
   4340 
   4341 //! The variable is named with lowering module's naming mechanism
   4342 int updateRefCount2(int reg, int type, bool isPhysical) {
   4343     if(currentBB == NULL) return 0;
   4344     int newType = convertType(type, reg, isPhysical);
   4345     if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
   4346     int index = searchCompileTable(newType, reg);
   4347     if(index < 0) {
   4348         ALOGE("reg %d type %d not found in updateRefCount", reg, newType);
   4349         return -1;
   4350     }
   4351     decreaseRefCount(index);
   4352     return 0;
   4353 }
   4354 //! check whether a glue variable is in physical register or spilled
   4355 
   4356 //!
   4357 bool isGlueHandled(int glue_reg) {
   4358     if(currentBB == NULL) return false;
   4359     int index = searchCompileTable(LowOpndRegType_gp, glue_reg);
   4360     if(index < 0) {
   4361         ALOGE("glue reg %d not found in isGlueHandled", glue_reg);
   4362         return -1;
   4363     }
   4364     if(compileTable[index].spill_loc_index >= 0 ||
   4365        compileTable[index].physicalReg != PhysicalReg_Null) {
   4366 #ifdef DEBUG_GLUE
   4367         ALOGI("GLUE isGlueHandled for %d returns true", glue_reg);
   4368 #endif
   4369         return true;
   4370     }
   4371 #ifdef DEBUG_GLUE
   4372     ALOGI("GLUE isGlueHandled for %d returns false", glue_reg);
   4373 #endif
   4374     return false;
   4375 }
   4376 //! reset the state of a glue variable to not existant (not in physical register nor spilled)
   4377 
   4378 //!
   4379 void resetGlue(int glue_reg) {
   4380     if(currentBB == NULL) return;
   4381     int index = searchCompileTable(LowOpndRegType_gp, glue_reg);
   4382     if(index < 0) {
   4383         ALOGE("glue reg %d not found in resetGlue", glue_reg);
   4384         return;
   4385     }
   4386 #ifdef DEBUG_GLUE
   4387     ALOGI("GLUE reset for %d", glue_reg);
   4388 #endif
   4389     compileTable[index].physicalReg = PhysicalReg_Null;
   4390     if(compileTable[index].spill_loc_index >= 0)
   4391         spillIndexUsed[compileTable[index].spill_loc_index >> 2] = 0;
   4392     compileTable[index].spill_loc_index = -1;
   4393 }
   4394 //! set a glue variable in a physical register allocated for a variable
   4395 
   4396 //! Variable is using lowering module's naming convention
   4397 void updateGlue(int reg, bool isPhysical, int glue_reg) {
   4398     if(currentBB == NULL) return;
   4399     int index = searchCompileTable(LowOpndRegType_gp, glue_reg);
   4400     if(index < 0) {
   4401         ALOGE("glue reg %d not found in updateGlue", glue_reg);
   4402         return;
   4403     }
   4404     /* find the compileTable entry for variable <reg, isPhysical> */
   4405     int newType = convertType(LowOpndRegType_gp, reg, isPhysical);
   4406     if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
   4407     int index2 = searchCompileTable(newType, reg);
   4408     if(index2 < 0 || compileTable[index2].physicalReg == PhysicalReg_Null) {
   4409         ALOGE("updateGlue reg %d type %d", reg, newType);
   4410         return;
   4411     }
   4412 #ifdef DEBUG_GLUE
   4413     ALOGI("physical register for GLUE %d set to %d", glue_reg, compileTable[index2].physicalReg);
   4414 #endif
   4415     compileTable[index].physicalReg = compileTable[index2].physicalReg;
   4416     compileTable[index].spill_loc_index = -1;
   4417 }
   4418 
   4419 //! check whether a virtual register is in a physical register
   4420 
   4421 //! If updateRefCount is 0, do not update reference count;
   4422 //!If updateRefCount is 1, update reference count only when VR is in a physical register
   4423 //!If updateRefCount is 2, update reference count
   4424 int checkVirtualReg(int reg, LowOpndRegType type, int updateRefCount) {
   4425     if(currentBB == NULL) return PhysicalReg_Null;
   4426     int index = searchCompileTable(LowOpndRegType_virtual | type, reg);
   4427     if(index < 0) {
   4428         ALOGE("virtual reg %d type %d not found in checkVirtualReg", reg, type);
   4429         return PhysicalReg_Null;
   4430     }
   4431     //reduce reference count
   4432     if(compileTable[index].physicalReg != PhysicalReg_Null) {
   4433         if(updateRefCount != 0) decreaseRefCount(index);
   4434         return compileTable[index].physicalReg;
   4435     }
   4436     if(updateRefCount == 2) decreaseRefCount(index);
   4437     return PhysicalReg_Null;
   4438 }
   4439 //!check whether a temporary can share the same physical register with a VR
   4440 
   4441 //!This is called in get_virtual_reg
   4442 //!If this function returns false, new register will be allocated for this temporary
   4443 bool checkTempReg2(int reg, int type, bool isPhysical, int physicalRegForVR) {
   4444     if(currentBB == NULL) return false;
   4445     if(isPhysical) return false;
   4446 
   4447     int newType = convertType(type, reg, isPhysical);
   4448     if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
   4449     int k;
   4450     for(k = 0; k < num_temp_regs_per_bytecode; k++) {
   4451         if(infoByteCodeTemp[k].physicalType == newType &&
   4452            infoByteCodeTemp[k].regNum == reg) {
   4453 #ifdef DEBUG_MOVE_OPT
   4454             ALOGI("MOVE_OPT checkTempRegs for %d %d returns %d %d",
   4455                    reg, newType, infoByteCodeTemp[k].shareWithVR, infoByteCodeTemp[k].is8Bit);
   4456 #endif
   4457             if(!infoByteCodeTemp[k].is8Bit) return infoByteCodeTemp[k].shareWithVR;
   4458             //is8Bit true for gp type only
   4459             if(!infoByteCodeTemp[k].shareWithVR) return false;
   4460             //both true
   4461             if(physicalRegForVR >= PhysicalReg_EAX && physicalRegForVR <= PhysicalReg_EDX) return true;
   4462 #ifdef DEBUG_MOVE_OPT
   4463             ALOGI("MOVE_OPT registerAllocMove not used for 8-bit register");
   4464 #endif
   4465             return false;
   4466         }
   4467     }
   4468     ALOGE("checkTempReg2 %d %d", reg, newType);
   4469     return false;
   4470 }
   4471 //!check whether a temporary can share the same physical register with a VR
   4472 
   4473 //!This is called in set_virtual_reg
   4474 int checkTempReg(int reg, int type, bool isPhysical, int vrNum) {
   4475     if(currentBB == NULL) return PhysicalReg_Null;
   4476 
   4477     int newType = convertType(type, reg, isPhysical);
   4478     if(newType & LowOpndRegType_scratch) reg = reg - PhysicalReg_SCRATCH_1 + 1;
   4479     int index = searchCompileTable(newType, reg);
   4480     if(index < 0) {
   4481         ALOGE("temp reg %d type %d not found in checkTempReg", reg, newType);
   4482         return PhysicalReg_Null;
   4483     }
   4484 
   4485     //a temporary register can share the same physical reg with a VR if registerAllocMove is called
   4486     //this will cause problem with move bytecode
   4487     //get_VR(v1, t1) t1 and v1 point to the same physical reg
   4488     //set_VR(t1, v2) t1 and v2 point to the same physical reg
   4489     //this will cause v1 and v2 point to the same physical reg
   4490     //FIX: if this temp reg shares a physical reg with another reg
   4491     if(compileTable[index].physicalReg != PhysicalReg_Null) {
   4492         int k;
   4493         for(k = 0; k < num_compile_entries; k++) {
   4494             if(k == index) continue;
   4495             if(compileTable[k].physicalReg == compileTable[index].physicalReg) {
   4496                 return PhysicalReg_Null; //will allocate a register for VR
   4497             }
   4498         }
   4499         decreaseRefCount(index);
   4500         return compileTable[index].physicalReg;
   4501     }
   4502     if(compileTable[index].spill_loc_index >= 0) {
   4503         //registerAlloc will call unspillLogicalReg (load from memory)
   4504 #ifdef DEBUG_REGALLOC
   4505         ALOGW("in checkTempReg, the temporary register %d %d was spilled", reg, type);
   4506 #endif
   4507         int regAll = registerAlloc(type, reg, isPhysical, true/* updateRefCount */);
   4508         return regAll;
   4509     }
   4510     return PhysicalReg_Null;
   4511 }
   4512 //!check whether a variable has exposed usage in a basic block
   4513 
   4514 //!It calls hasExposedUsage2
   4515 bool hasExposedUsage(LowOpndRegType type, int regNum, BasicBlock_O1* bb) {
   4516     int index = searchVirtualInfoOfBB(type, regNum, bb);
   4517     if(index >= 0 && hasExposedUsage2(bb, index)) {
   4518         return true;
   4519     }
   4520     return false;
   4521 }
   4522 //!check whether a variable has exposed usage in other basic blocks
   4523 
   4524 //!
   4525 bool hasOtherExposedUsage(OpndSize size, int regNum, BasicBlock_O1* bb) {
   4526     return true; //assume the worst case
   4527 }
   4528 
   4529 //! handles constant VRs at end of a basic block
   4530 
   4531 //!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
   4532 void constVREndOfBB() {
   4533     BasicBlock_O1* bb = currentBB;
   4534     int k, k2;
   4535     //go through GG VRs, update a bool array
   4536     int constUsedByGG[MAX_CONST_REG];
   4537     for(k = 0; k < num_const_vr; k++)
   4538         constUsedByGG[k] = 0;
   4539     for(k = 0; k < num_compile_entries; k++) {
   4540         if(isVirtualReg(compileTable[k].physicalType) && compileTable[k].gType == GLOBALTYPE_GG) {
   4541             OpndSize size = getRegSize(compileTable[k].physicalType);
   4542             int regNum = compileTable[k].regNum;
   4543             int indexL = -1;
   4544             int indexH = -1;
   4545             for(k2 = 0; k2 < num_const_vr; k2++) {
   4546                 if(constVRTable[k2].regNum == regNum) {
   4547                     indexL = k2;
   4548                     continue;
   4549                 }
   4550                 if(constVRTable[k2].regNum == regNum + 1 && size == OpndSize_64) {
   4551                     indexH = k2;
   4552                     continue;
   4553                 }
   4554             }
   4555             if(indexL >= 0) constUsedByGG[indexL] = 1;
   4556             if(indexH >= 0) constUsedByGG[indexH] = 1;
   4557         } //GG VR
   4558     }
   4559     for(k = 0; k < num_const_vr; k++) {
   4560         if(!constVRTable[k].isConst) continue;
   4561         bool hasExp = false;
   4562         if(constUsedByGG[k] == 0)
   4563             hasExp = hasOtherExposedUsage(OpndSize_32, constVRTable[k].regNum, bb);
   4564         if(constUsedByGG[k] != 0 || hasExp) {
   4565             dumpImmToMem(constVRTable[k].regNum, OpndSize_32, constVRTable[k].value);
   4566             setVRToMemory(constVRTable[k].regNum, OpndSize_32);
   4567 #ifdef DEBUG_ENDOFBB
   4568             ALOGI("ENDOFBB: exposed VR %d is const %d (%x)",
   4569                   constVRTable[k].regNum, constVRTable[k].value, constVRTable[k].value);
   4570 #endif
   4571         } else {
   4572 #ifdef DEBUG_ENDOFBB
   4573             ALOGI("ENDOFBB: unexposed VR %d is const %d (%x)",
   4574                   constVRTable[k].regNum, constVRTable[k].value, constVRTable[k].value);
   4575 #endif
   4576         }
   4577     }
   4578 }
   4579 
   4580 //!handles GG VRs at end of a basic block
   4581 
   4582 //!make sure all GG VRs are in pre-defined physical registers
   4583 void globalVREndOfBB(const Method* method) {
   4584     //fix: freeReg first to write LL VR back to memory to avoid it gets overwritten by GG VRs
   4585     freeReg(true);
   4586     int k;
   4587     //spill GG VR first if it is not mapped to the specific reg
   4588     //release GLUE regs
   4589     for(k = 0; k < num_compile_entries; k++) {
   4590         if(compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX &&
   4591            compileTable[k].regNum != PhysicalReg_GLUE) {
   4592             compileTable[k].physicalReg = PhysicalReg_Null;
   4593             compileTable[k].spill_loc_index = -1;
   4594         }
   4595         //if part of a GG VR is const, the physical reg is set to null
   4596         if(isVirtualReg(compileTable[k].physicalType) &&
   4597            compileTable[k].gType == GLOBALTYPE_GG && compileTable[k].physicalReg != PhysicalReg_Null &&
   4598            compileTable[k].physicalReg != compileTable[k].physicalReg_prev) {
   4599 #ifdef DEBUG_ENDOFBB
   4600             ALOGW("end of BB GG VR is not mapped to the specific reg: %d %d %d",
   4601                   compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].physicalReg);
   4602             ALOGW("ENDOFBB SPILL VR %d %d", compileTable[k].regNum, compileTable[k].physicalType);
   4603 #endif
   4604             spillLogicalReg(k, true); //the next section will load VR from memory to the specific reg
   4605         }
   4606     }
   4607     syncAllRegs();
   4608     for(k = 0; k < num_compile_entries; k++) {
   4609         if(isVirtualReg(compileTable[k].physicalType)) {
   4610             if(compileTable[k].gType == GLOBALTYPE_GG &&
   4611                compileTable[k].physicalReg == PhysicalReg_Null && (!currentBB->endsWithReturn)) {
   4612 #ifdef DEBUG_ENDOFBB
   4613                 ALOGI("ENDOFBB GET GG VR %d %d to physical register %d", compileTable[k].regNum,
   4614                       compileTable[k].physicalType, compileTable[k].physicalReg_prev);
   4615 #endif
   4616                 compileTable[k].physicalReg = compileTable[k].physicalReg_prev;
   4617                 if(allRegs[compileTable[k].physicalReg_prev].isUsed) {
   4618                     ALOGE("physical register for GG VR is still used");
   4619                 }
   4620                 get_virtual_reg_noalloc(compileTable[k].regNum,
   4621                                         getRegSize(compileTable[k].physicalType),
   4622                                         compileTable[k].physicalReg_prev,
   4623                                         true);
   4624             }
   4625         }//not const
   4626     }
   4627     if(indexForGlue >= 0 &&
   4628         compileTable[indexForGlue].physicalReg == PhysicalReg_Null) {
   4629         unspillLogicalReg(indexForGlue, PhysicalReg_EBP); //load %ebp
   4630     }
   4631 }
   4632 
   4633 //! get ready for the next version of a hard-coded register
   4634 
   4635 //!set its physicalReg to Null and update its reference count
   4636 int nextVersionOfHardReg(PhysicalReg pReg, int refCount) {
   4637     int indexT = searchCompileTable(LowOpndRegType_gp | LowOpndRegType_hard, pReg);
   4638     if(indexT < 0)
   4639         return -1;
   4640     compileTable[indexT].physicalReg = PhysicalReg_Null;
   4641 #ifdef DEBUG_REFCOUNT
   4642     ALOGI("REFCOUNT: to %d in nextVersionOfHardReg %d", refCount, pReg);
   4643 #endif
   4644     compileTable[indexT].refCount = refCount;
   4645     return 0;
   4646 }
   4647 
   4648 /** update compileTable with bb->infoBasicBlock[k]
   4649 */
   4650 void insertFromVirtualInfo(BasicBlock_O1* bb, int k) {
   4651     int index = searchCompileTable(LowOpndRegType_virtual | bb->infoBasicBlock[k].physicalType, bb->infoBasicBlock[k].regNum);
   4652     if(index < 0) {
   4653         /* the virtual register is not in compileTable, insert it */
   4654         index = num_compile_entries;
   4655         compileTable[num_compile_entries].physicalType = (LowOpndRegType_virtual | bb->infoBasicBlock[k].physicalType);
   4656         compileTable[num_compile_entries].regNum = bb->infoBasicBlock[k].regNum;
   4657         compileTable[num_compile_entries].physicalReg = PhysicalReg_Null;
   4658         compileTable[num_compile_entries].bb = bb;
   4659         compileTable[num_compile_entries].indexToInfoBB = k;
   4660         compileTable[num_compile_entries].spill_loc_index = -1;
   4661         compileTable[num_compile_entries].gType = bb->infoBasicBlock[k].gType;
   4662         num_compile_entries++;
   4663         if(num_compile_entries >= COMPILE_TABLE_SIZE) {
   4664             ALOGE("compileTable overflow");
   4665             dvmAbort();
   4666         }
   4667     }
   4668     /* re-set reference count of all VRs */
   4669     compileTable[index].refCount = bb->infoBasicBlock[k].refCount;
   4670     compileTable[index].accessType = bb->infoBasicBlock[k].accessType;
   4671     if(compileTable[index].gType == GLOBALTYPE_GG)
   4672         compileTable[index].physicalReg_prev = bb->infoBasicBlock[k].physicalReg_GG;
   4673 }
   4674 
   4675 /** update compileTable with infoByteCodeTemp[k]
   4676 */
   4677 void insertFromTempInfo(int k) {
   4678     int index = searchCompileTable(infoByteCodeTemp[k].physicalType, infoByteCodeTemp[k].regNum);
   4679     if(index < 0) {
   4680         /* the temporary is not in compileTable, insert it */
   4681         index = num_compile_entries;
   4682         compileTable[num_compile_entries].physicalType = infoByteCodeTemp[k].physicalType;
   4683         compileTable[num_compile_entries].regNum = infoByteCodeTemp[k].regNum;
   4684         num_compile_entries++;
   4685         if(num_compile_entries >= COMPILE_TABLE_SIZE) {
   4686             ALOGE("compileTable overflow");
   4687             dvmAbort();
   4688         }
   4689     }
   4690     compileTable[index].physicalReg = PhysicalReg_Null;
   4691     compileTable[index].refCount = infoByteCodeTemp[k].refCount;
   4692     compileTable[index].linkageToVR = infoByteCodeTemp[k].linkageToVR;
   4693     compileTable[index].gType = GLOBALTYPE_L;
   4694     compileTable[index].spill_loc_index = -1;
   4695 }
   4696 
   4697 /* insert a glue-related register GLUE_DVMDEX to compileTable */
   4698 void insertGlueReg() {
   4699     compileTable[num_compile_entries].physicalType = LowOpndRegType_gp;
   4700     compileTable[num_compile_entries].regNum = PhysicalReg_GLUE_DVMDEX;
   4701     compileTable[num_compile_entries].refCount = 2;
   4702     compileTable[num_compile_entries].physicalReg = PhysicalReg_Null;
   4703     compileTable[num_compile_entries].bb = NULL;
   4704     compileTable[num_compile_entries].spill_loc_index = -1;
   4705     compileTable[num_compile_entries].accessType = REGACCESS_N;
   4706     compileTable[num_compile_entries].linkageToVR = -1;
   4707     compileTable[num_compile_entries].gType = GLOBALTYPE_L;
   4708 
   4709     num_compile_entries++;
   4710     if(num_compile_entries >= COMPILE_TABLE_SIZE) {
   4711         ALOGE("compileTable overflow");
   4712         dvmAbort();
   4713     }
   4714 }
   4715 
   4716 /** print infoBasicBlock of the given basic block
   4717 */
   4718 void dumpVirtualInfoOfBasicBlock(BasicBlock_O1* bb) {
   4719     int jj;
   4720     ALOGI("Virtual Info for BB%d --------", bb->bb_index);
   4721     for(jj = 0; jj < bb->num_regs; jj++) {
   4722         ALOGI("regNum %d physicalType %d accessType %d refCount %d def ",
   4723                bb->infoBasicBlock[jj].regNum, bb->infoBasicBlock[jj].physicalType,
   4724                bb->infoBasicBlock[jj].accessType, bb->infoBasicBlock[jj].refCount);
   4725         int k;
   4726         for(k = 0; k < bb->infoBasicBlock[jj].num_reaching_defs; k++)
   4727             ALOGI("[%x %d %d %d] ", bb->infoBasicBlock[jj].reachingDefs[k].offsetPC,
   4728                    bb->infoBasicBlock[jj].reachingDefs[k].regNum,
   4729                    bb->infoBasicBlock[jj].reachingDefs[k].physicalType,
   4730                    bb->infoBasicBlock[jj].reachingDefs[k].accessType);
   4731         ALOGI("");
   4732     }
   4733 }
   4734 
   4735 /** print compileTable
   4736 */
   4737 void dumpCompileTable() {
   4738     int jj;
   4739     ALOGI("Compile Table for method ----------");
   4740     for(jj = 0; jj < num_compile_entries; jj++) {
   4741         ALOGI("regNum %d physicalType %d refCount %d isConst %d physicalReg %d type %d",
   4742                compileTable[jj].regNum, compileTable[jj].physicalType,
   4743                compileTable[jj].refCount, compileTable[jj].isConst, compileTable[jj].physicalReg, compileTable[jj].gType);
   4744     }
   4745 }
   4746 
   4747 //!check whether a basic block is the start of an exception handler
   4748 
   4749 //!
   4750 bool isFirstOfHandler(BasicBlock_O1* bb) {
   4751     int i;
   4752     for(i = 0; i < num_exception_handlers; i++) {
   4753         if(bb->pc_start == exceptionHandlers[i]) return true;
   4754     }
   4755     return false;
   4756 }
   4757 
   4758 //! create a basic block that starts at src_pc and ends at end_pc
   4759 
   4760 //!
   4761 BasicBlock_O1* createBasicBlock(int src_pc, int end_pc) {
   4762     BasicBlock_O1* bb = (BasicBlock_O1*)malloc(sizeof(BasicBlock_O1));
   4763     if(bb == NULL) {
   4764         ALOGE("out of memory");
   4765         return NULL;
   4766     }
   4767     bb->pc_start = src_pc;
   4768     bb->bb_index = num_bbs_for_method;
   4769     if(bb_entry == NULL) bb_entry = bb;
   4770 
   4771     /* insert the basic block to method_bbs_sorted in ascending order of pc_start */
   4772     int k;
   4773     int index = -1;
   4774     for(k = 0; k < num_bbs_for_method; k++)
   4775         if(method_bbs_sorted[k]->pc_start > src_pc) {
   4776             index = k;
   4777             break;
   4778         }
   4779     if(index == -1)
   4780         method_bbs_sorted[num_bbs_for_method] = bb;
   4781     else {
   4782         /* push the elements from index by 1 */
   4783         for(k = num_bbs_for_method-1; k >= index; k--)
   4784             method_bbs_sorted[k+1] = method_bbs_sorted[k];
   4785         method_bbs_sorted[index] = bb;
   4786     }
   4787     num_bbs_for_method++;
   4788     if(num_bbs_for_method >= MAX_NUM_BBS_PER_METHOD) {
   4789         ALOGE("too many basic blocks");
   4790         dvmAbort();
   4791     }
   4792     return bb;
   4793 }
   4794 
   4795 /* BEGIN code to handle state transfers */
   4796 //! save the current state of register allocator to a state table
   4797 
   4798 //!
   4799 void rememberState(int stateNum) {
   4800 #ifdef DEBUG_STATE
   4801     ALOGI("STATE: remember state %d", stateNum);
   4802 #endif
   4803     int k;
   4804     for(k = 0; k < num_compile_entries; k++) {
   4805         if(stateNum == 1) {
   4806             stateTable1_1[k].physicalReg = compileTable[k].physicalReg;
   4807             stateTable1_1[k].spill_loc_index = compileTable[k].spill_loc_index;
   4808         }
   4809         else if(stateNum == 2) {
   4810             stateTable1_2[k].physicalReg = compileTable[k].physicalReg;
   4811             stateTable1_2[k].spill_loc_index = compileTable[k].spill_loc_index;
   4812         }
   4813         else if(stateNum == 3) {
   4814             stateTable1_3[k].physicalReg = compileTable[k].physicalReg;
   4815             stateTable1_3[k].spill_loc_index = compileTable[k].spill_loc_index;
   4816         }
   4817         else if(stateNum == 4) {
   4818             stateTable1_4[k].physicalReg = compileTable[k].physicalReg;
   4819             stateTable1_4[k].spill_loc_index = compileTable[k].spill_loc_index;
   4820         }
   4821         else ALOGE("state table overflow");
   4822 #ifdef DEBUG_STATE
   4823         ALOGI("logical reg %d %d mapped to physical reg %d with spill index %d refCount %d",
   4824                compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].physicalReg,
   4825                compileTable[k].spill_loc_index, compileTable[k].refCount);
   4826 #endif
   4827     }
   4828     for(k = 0; k < num_memory_vr; k++) {
   4829         if(stateNum == 1) {
   4830             stateTable2_1[k].regNum = memVRTable[k].regNum;
   4831             stateTable2_1[k].inMemory = memVRTable[k].inMemory;
   4832         }
   4833         else if(stateNum == 2) {
   4834             stateTable2_2[k].regNum = memVRTable[k].regNum;
   4835             stateTable2_2[k].inMemory = memVRTable[k].inMemory;
   4836         }
   4837         else if(stateNum == 3) {
   4838             stateTable2_3[k].regNum = memVRTable[k].regNum;
   4839             stateTable2_3[k].inMemory = memVRTable[k].inMemory;
   4840         }
   4841         else if(stateNum == 4) {
   4842             stateTable2_4[k].regNum = memVRTable[k].regNum;
   4843             stateTable2_4[k].inMemory = memVRTable[k].inMemory;
   4844         }
   4845         else ALOGE("state table overflow");
   4846 #ifdef DEBUG_STATE
   4847         ALOGI("virtual reg %d in memory %d", memVRTable[k].regNum, memVRTable[k].inMemory);
   4848 #endif
   4849     }
   4850 }
   4851 
   4852 //!update current state of register allocator with a state table
   4853 
   4854 //!
   4855 void goToState(int stateNum) {
   4856     int k;
   4857 #ifdef DEBUG_STATE
   4858     ALOGI("STATE: go to state %d", stateNum);
   4859 #endif
   4860     for(k = 0; k < num_compile_entries; k++) {
   4861         if(stateNum == 1) {
   4862             compileTable[k].physicalReg = stateTable1_1[k].physicalReg;
   4863             compileTable[k].spill_loc_index = stateTable1_1[k].spill_loc_index;
   4864         }
   4865         else if(stateNum == 2) {
   4866             compileTable[k].physicalReg = stateTable1_2[k].physicalReg;
   4867             compileTable[k].spill_loc_index = stateTable1_2[k].spill_loc_index;
   4868         }
   4869         else if(stateNum == 3) {
   4870             compileTable[k].physicalReg = stateTable1_3[k].physicalReg;
   4871             compileTable[k].spill_loc_index = stateTable1_3[k].spill_loc_index;
   4872         }
   4873         else if(stateNum == 4) {
   4874             compileTable[k].physicalReg = stateTable1_4[k].physicalReg;
   4875             compileTable[k].spill_loc_index = stateTable1_4[k].spill_loc_index;
   4876         }
   4877         else ALOGE("state table overflow");
   4878     }
   4879     updateSpillIndexUsed();
   4880     syncAllRegs(); //to sync up allRegs CAN'T call freeReg here
   4881     //since it will change the state!!!
   4882     for(k = 0; k < num_memory_vr; k++) {
   4883         if(stateNum == 1) {
   4884             memVRTable[k].regNum = stateTable2_1[k].regNum;
   4885             memVRTable[k].inMemory = stateTable2_1[k].inMemory;
   4886         }
   4887         else if(stateNum == 2) {
   4888             memVRTable[k].regNum = stateTable2_2[k].regNum;
   4889             memVRTable[k].inMemory = stateTable2_2[k].inMemory;
   4890         }
   4891         else if(stateNum == 3) {
   4892             memVRTable[k].regNum = stateTable2_3[k].regNum;
   4893             memVRTable[k].inMemory = stateTable2_3[k].inMemory;
   4894         }
   4895         else if(stateNum == 4) {
   4896             memVRTable[k].regNum = stateTable2_4[k].regNum;
   4897             memVRTable[k].inMemory = stateTable2_4[k].inMemory;
   4898         }
   4899         else ALOGE("state table overflow");
   4900     }
   4901 }
   4902 typedef struct TransferOrder {
   4903     int targetReg;
   4904     int targetSpill;
   4905     int compileIndex;
   4906 } TransferOrder;
   4907 #define MAX_NUM_DEST 20
   4908 //! a source register is used as a source in transfer
   4909 //! it can have a maximum of MAX_NUM_DEST destinations
   4910 typedef struct SourceReg {
   4911     int physicalReg;
   4912     int num_dests; //check bound
   4913     TransferOrder dsts[MAX_NUM_DEST];
   4914 } SourceReg;
   4915 int num_src_regs = 0; //check bound
   4916 //! physical registers that are used as a source in transfer
   4917 //! we allow a maximum of MAX_NUM_DEST sources in a transfer
   4918 SourceReg srcRegs[MAX_NUM_DEST];
   4919 //! tell us whether a source register is handled already
   4920 bool handledSrc[MAX_NUM_DEST];
   4921 //! in what order should the source registers be handled
   4922 int handledOrder[MAX_NUM_DEST];
   4923 //! insert a source register with a single destination
   4924 
   4925 //!
   4926 void insertSrcReg(int srcPhysical, int targetReg, int targetSpill, int index) {
   4927     int k = 0;
   4928     for(k = 0; k < num_src_regs; k++) {
   4929         if(srcRegs[k].physicalReg == srcPhysical) { //increase num_dests
   4930             if(srcRegs[k].num_dests >= MAX_NUM_DEST) {
   4931                 ALOGE("exceed number dst regs for a source reg");
   4932                 dvmAbort();
   4933             }
   4934             srcRegs[k].dsts[srcRegs[k].num_dests].targetReg = targetReg;
   4935             srcRegs[k].dsts[srcRegs[k].num_dests].targetSpill = targetSpill;
   4936             srcRegs[k].dsts[srcRegs[k].num_dests].compileIndex = index;
   4937             srcRegs[k].num_dests++;
   4938             return;
   4939         }
   4940     }
   4941     if(num_src_regs >= MAX_NUM_DEST) {
   4942         ALOGE("exceed number of source regs");
   4943         dvmAbort();
   4944     }
   4945     srcRegs[num_src_regs].physicalReg = srcPhysical;
   4946     srcRegs[num_src_regs].num_dests = 1;
   4947     srcRegs[num_src_regs].dsts[0].targetReg = targetReg;
   4948     srcRegs[num_src_regs].dsts[0].targetSpill = targetSpill;
   4949     srcRegs[num_src_regs].dsts[0].compileIndex = index;
   4950     num_src_regs++;
   4951 }
   4952 //! check whether a register is a source and the source is not yet handled
   4953 
   4954 //!
   4955 bool dstStillInUse(int dstReg) {
   4956     if(dstReg == PhysicalReg_Null) return false;
   4957     int k;
   4958     int index = -1;
   4959     for(k = 0; k < num_src_regs; k++) {
   4960         if(dstReg == srcRegs[k].physicalReg) {
   4961             index = k;
   4962             break;
   4963         }
   4964     }
   4965     if(index < 0) return false; //not in use
   4966     if(handledSrc[index]) return false; //not in use
   4967     return true;
   4968 }
   4969 //! reset the state of glue variables in a state table
   4970 
   4971 //!
   4972 void resetStateOfGlue(int stateNum, int k) {
   4973 #ifdef DEBUG_STATE
   4974     ALOGI("resetStateOfGlue state %d regNum %d", stateNum, compileTable[k].regNum);
   4975 #endif
   4976     if(stateNum == 1) {
   4977         stateTable1_1[k].physicalReg = PhysicalReg_Null;
   4978         stateTable1_1[k].spill_loc_index = -1;
   4979     }
   4980     else if(stateNum == 2) {
   4981         stateTable1_2[k].physicalReg = PhysicalReg_Null;
   4982         stateTable1_2[k].spill_loc_index = -1;
   4983     }
   4984     else if(stateNum == 3) {
   4985         stateTable1_3[k].physicalReg = PhysicalReg_Null;
   4986         stateTable1_3[k].spill_loc_index = -1;
   4987     }
   4988     else if(stateNum == 4) {
   4989         stateTable1_4[k].physicalReg = PhysicalReg_Null;
   4990         stateTable1_4[k].spill_loc_index = -1;
   4991     }
   4992 }
   4993 //! construct a legal order of the source registers in this transfer
   4994 
   4995 //!
   4996 void constructSrcRegs(int stateNum) {
   4997     int k;
   4998     num_src_regs = 0;
   4999 #ifdef DEBUG_STATE
   5000     ALOGI("IN constructSrcRegs");
   5001 #endif
   5002 
   5003     for(k = 0; k < num_compile_entries; k++) {
   5004 #ifdef DEBUG_STATE
   5005         ALOGI("logical reg %d %d mapped to physical reg %d with spill index %d refCount %d",
   5006                compileTable[k].regNum, compileTable[k].physicalType, compileTable[k].physicalReg,
   5007                compileTable[k].spill_loc_index, compileTable[k].refCount);
   5008 #endif
   5009 
   5010         int pType = compileTable[k].physicalType;
   5011         //ignore hardcoded logical registers
   5012         if((pType & LowOpndRegType_hard) != 0) continue;
   5013         //ignore type _fs
   5014         if((pType & MASK_FOR_TYPE) == LowOpndRegType_fs) continue;
   5015         if((pType & MASK_FOR_TYPE) == LowOpndRegType_fs_s) continue;
   5016 
   5017         //GL VR refCount is zero, can't ignore
   5018         //L VR refCount is zero, ignore
   5019         //GG VR refCount is zero, can't ignore
   5020         //temporary refCount is zero, ignore
   5021 
   5022         //for GLUE variables, if they do not exist, reset the entries in state table
   5023         if(compileTable[k].physicalReg == PhysicalReg_Null &&
   5024            compileTable[k].regNum >= PhysicalReg_GLUE_DVMDEX &&
   5025            compileTable[k].regNum != PhysicalReg_GLUE &&
   5026            compileTable[k].spill_loc_index < 0) {
   5027             resetStateOfGlue(stateNum, k);
   5028         }
   5029 
   5030         /* get the target state */
   5031         int targetReg = PhysicalReg_Null;
   5032         int targetSpill = -1;
   5033         if(stateNum == 1) {
   5034             targetReg = stateTable1_1[k].physicalReg;
   5035             targetSpill = stateTable1_1[k].spill_loc_index;
   5036         }
   5037         else if(stateNum == 2) {
   5038             targetReg = stateTable1_2[k].physicalReg;
   5039             targetSpill = stateTable1_2[k].spill_loc_index;
   5040         }
   5041         else if(stateNum == 3) {
   5042             targetReg = stateTable1_3[k].physicalReg;
   5043             targetSpill = stateTable1_3[k].spill_loc_index;
   5044         }
   5045         else if(stateNum == 4) {
   5046             targetReg = stateTable1_4[k].physicalReg;
   5047             targetSpill = stateTable1_4[k].spill_loc_index;
   5048         }
   5049 
   5050         /* there exists an ordering problem
   5051            for example:
   5052              for a VR, move from memory to a physical reg esi
   5053              for a temporary regsiter, from esi to ecx
   5054              if we handle VR first, content of the temporary reg. will be overwritten
   5055            there are 4 cases:
   5056              I: a variable is currently in memory and its target is in physical reg
   5057              II: a variable is currently in a register and its target is in memory
   5058              III: a variable is currently in a different register
   5059              IV: a variable is currently in a different memory location (for non-VRs)
   5060            for GLUE, since it can only be allocated to %ebp, we don't have case III
   5061            For now, case IV is not handled since it didn't show
   5062         */
   5063         if(compileTable[k].physicalReg != targetReg &&
   5064            isVirtualReg(compileTable[k].physicalType)) {
   5065             /* handles VR for case I to III */
   5066 
   5067             if(compileTable[k].physicalReg == PhysicalReg_Null && targetReg != PhysicalReg_Null) {
   5068                 /* handles VR for case I:
   5069                    insert a xfer order from PhysicalReg_Null to targetReg */
   5070                 insertSrcReg(PhysicalReg_Null, targetReg, targetSpill, k);
   5071 #ifdef DEBUG_STATE
   5072                 ALOGI("insert for VR Null %d %d %d", targetReg, targetSpill, k);
   5073 #endif
   5074             }
   5075 
   5076             if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg != PhysicalReg_Null) {
   5077                 /* handles VR for case III
   5078                    insert a xfer order from srcReg to targetReg */
   5079                 insertSrcReg(compileTable[k].physicalReg, targetReg, targetSpill, k);
   5080             }
   5081 
   5082             if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg == PhysicalReg_Null) {
   5083                 /* handles VR for case II
   5084                    insert a xfer order from srcReg to memory */
   5085                 insertSrcReg(compileTable[k].physicalReg, targetReg, targetSpill, k);
   5086             }
   5087         }
   5088 
   5089         if(compileTable[k].physicalReg != targetReg &&
   5090            !isVirtualReg(compileTable[k].physicalType)) {
   5091             /* handles non-VR for case I to III */
   5092 
   5093             if(compileTable[k].physicalReg == PhysicalReg_Null && targetReg != PhysicalReg_Null) {
   5094                 /* handles non-VR for case I */
   5095                 if(compileTable[k].spill_loc_index < 0) {
   5096                     /* this variable is freed, no need to transfer */
   5097 #ifdef DEBUG_STATE
   5098                     ALOGW("in transferToState spill_loc_index is negative for temporary %d", compileTable[k].regNum);
   5099 #endif
   5100                 } else {
   5101                     /* insert a xfer order from memory to targetReg */
   5102 #ifdef DEBUG_STATE
   5103                     ALOGI("insert Null %d %d %d", targetReg, targetSpill, k);
   5104 #endif
   5105                     insertSrcReg(PhysicalReg_Null, targetReg, targetSpill, k);
   5106                 }
   5107             }
   5108 
   5109             if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg != PhysicalReg_Null) {
   5110                 /* handles non-VR for case III
   5111                    insert a xfer order from srcReg to targetReg */
   5112                 insertSrcReg(compileTable[k].physicalReg, targetReg, targetSpill, k);
   5113             }
   5114 
   5115             if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg == PhysicalReg_Null) {
   5116                 /* handles non-VR for case II */
   5117                 if(targetSpill < 0) {
   5118                     /* this variable is freed, no need to transfer */
   5119 #ifdef DEBUG_STATE
   5120                     ALOGW("in transferToState spill_loc_index is negative for temporary %d", compileTable[k].regNum);
   5121 #endif
   5122                 } else {
   5123                     /* insert a xfer order from srcReg to memory */
   5124                     insertSrcReg(compileTable[k].physicalReg, targetReg, targetSpill, k);
   5125                 }
   5126             }
   5127 
   5128         }
   5129     }//for compile entries
   5130 
   5131     int k2;
   5132 #ifdef DEBUG_STATE
   5133     for(k = 0; k < num_src_regs; k++) {
   5134         ALOGI("SRCREG %d: ", srcRegs[k].physicalReg);
   5135         for(k2 = 0; k2 < srcRegs[k].num_dests; k2++) {
   5136             int index = srcRegs[k].dsts[k2].compileIndex;
   5137             ALOGI("[%d %d %d: %d %d %d] ", srcRegs[k].dsts[k2].targetReg,
   5138                    srcRegs[k].dsts[k2].targetSpill, srcRegs[k].dsts[k2].compileIndex,
   5139                    compileTable[index].regNum, compileTable[index].physicalType,
   5140                    compileTable[index].spill_loc_index);
   5141         }
   5142         ALOGI("");
   5143     }
   5144 #endif
   5145 
   5146     /* construct an order: xfers from srcReg first, then xfers from memory */
   5147     int num_handled = 0;
   5148     int num_in_order = 0;
   5149     for(k = 0; k < num_src_regs; k++) {
   5150         if(srcRegs[k].physicalReg == PhysicalReg_Null) {
   5151             handledSrc[k] = true;
   5152             num_handled++;
   5153         } else {
   5154             handledSrc[k] = false;
   5155         }
   5156     }
   5157     while(num_handled < num_src_regs) {
   5158         int prev_handled = num_handled;
   5159         for(k = 0; k < num_src_regs; k++) {
   5160             if(handledSrc[k]) continue;
   5161             bool canHandleNow = true;
   5162             for(k2 = 0; k2 < srcRegs[k].num_dests; k2++) {
   5163                 if(dstStillInUse(srcRegs[k].dsts[k2].targetReg)) {
   5164                     canHandleNow = false;
   5165                     break;
   5166                 }
   5167             }
   5168             if(canHandleNow) {
   5169                 handledSrc[k] = true;
   5170                 num_handled++;
   5171                 handledOrder[num_in_order] = k;
   5172                 num_in_order++;
   5173             }
   5174         } //for k
   5175         if(num_handled == prev_handled) {
   5176             ALOGE("no progress in selecting order");
   5177             dvmAbort();
   5178         }
   5179     } //while
   5180     for(k = 0; k < num_src_regs; k++) {
   5181         if(srcRegs[k].physicalReg == PhysicalReg_Null) {
   5182             handledOrder[num_in_order] = k;
   5183             num_in_order++;
   5184         }
   5185     }
   5186     if(num_in_order != num_src_regs) {
   5187         ALOGE("num_in_order != num_src_regs");
   5188         dvmAbort();
   5189     }
   5190 #ifdef DEBUG_STATE
   5191     ALOGI("ORDER: ");
   5192     for(k = 0; k < num_src_regs; k++) {
   5193         ALOGI("%d ", handledOrder[k]);
   5194     }
   5195     ALOGI("");
   5196 #endif
   5197 }
   5198 //! transfer the state of register allocator to a state specified in a state table
   5199 
   5200 //!
   5201 void transferToState(int stateNum) {
   5202     freeReg(false); //do not spill GL
   5203     int k;
   5204 #ifdef DEBUG_STATE
   5205     ALOGI("STATE: transfer to state %d", stateNum);
   5206 #endif
   5207     if(stateNum > 4 || stateNum < 1) ALOGE("state table overflow");
   5208     constructSrcRegs(stateNum);
   5209     int k4, k3;
   5210     for(k4 = 0; k4 < num_src_regs; k4++) {
   5211         int k2 = handledOrder[k4]; //index to srcRegs
   5212         for(k3 = 0; k3 < srcRegs[k2].num_dests; k3++) {
   5213             k = srcRegs[k2].dsts[k3].compileIndex;
   5214             int targetReg = srcRegs[k2].dsts[k3].targetReg;
   5215             int targetSpill = srcRegs[k2].dsts[k3].targetSpill;
   5216             if(compileTable[k].physicalReg != targetReg && isVirtualReg(compileTable[k].physicalType)) {
   5217                 OpndSize oSize = getRegSize(compileTable[k].physicalType);
   5218                 bool isSS = ((compileTable[k].physicalType & MASK_FOR_TYPE) == LowOpndRegType_ss);
   5219                 if(compileTable[k].physicalReg == PhysicalReg_Null && targetReg != PhysicalReg_Null) {
   5220                     if(isSS)
   5221                         move_ss_mem_to_reg_noalloc(4*compileTable[k].regNum,
   5222                                                    PhysicalReg_FP, true,
   5223                                                    MemoryAccess_VR, compileTable[k].regNum,
   5224                                                    targetReg, true);
   5225                     else
   5226                         move_mem_to_reg_noalloc(oSize, 4*compileTable[k].regNum,
   5227                                                 PhysicalReg_FP, true,
   5228                                                 MemoryAccess_VR, compileTable[k].regNum,
   5229                                                 targetReg, true);
   5230                 }
   5231                 if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg != PhysicalReg_Null) {
   5232                     move_reg_to_reg_noalloc((isSS ? OpndSize_64 : oSize),
   5233                                             compileTable[k].physicalReg, true,
   5234                                             targetReg, true);
   5235                 }
   5236                 if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg == PhysicalReg_Null) {
   5237                     dumpToMem(compileTable[k].regNum, (LowOpndRegType)(compileTable[k].physicalType & MASK_FOR_TYPE),
   5238                               compileTable[k].physicalReg);
   5239                 }
   5240             } //VR
   5241             if(compileTable[k].physicalReg != targetReg && !isVirtualReg(compileTable[k].physicalType)) {
   5242                 OpndSize oSize = getRegSize(compileTable[k].physicalType);
   5243                 if(compileTable[k].physicalReg == PhysicalReg_Null && targetReg != PhysicalReg_Null) {
   5244                     loadFromSpillRegion(oSize, targetReg,
   5245                                         compileTable[k].spill_loc_index);
   5246                 }
   5247                 //both are not null, move from one to the other
   5248                 if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg != PhysicalReg_Null) {
   5249                     move_reg_to_reg_noalloc(oSize, compileTable[k].physicalReg, true,
   5250                                             targetReg, true);
   5251                 }
   5252                 //current is not null, target is null (move from reg to memory)
   5253                 if(compileTable[k].physicalReg != PhysicalReg_Null && targetReg == PhysicalReg_Null) {
   5254                     saveToSpillRegion(oSize, compileTable[k].physicalReg, targetSpill);
   5255                 }
   5256             } //temporary
   5257         }//for
   5258     }//for
   5259     for(k = 0; k < num_memory_vr; k++) {
   5260         bool targetBool = false;
   5261         int targetReg = -1;
   5262         if(stateNum == 1) {
   5263             targetReg = stateTable2_1[k].regNum;
   5264             targetBool = stateTable2_1[k].inMemory;
   5265         }
   5266         else if(stateNum == 2) {
   5267             targetReg = stateTable2_2[k].regNum;
   5268             targetBool = stateTable2_2[k].inMemory;
   5269         }
   5270         else if(stateNum == 3) {
   5271             targetReg = stateTable2_3[k].regNum;
   5272             targetBool = stateTable2_3[k].inMemory;
   5273         }
   5274         else if(stateNum == 4) {
   5275             targetReg = stateTable2_4[k].regNum;
   5276             targetBool = stateTable2_4[k].inMemory;
   5277         }
   5278         if(targetReg != memVRTable[k].regNum)
   5279             ALOGE("regNum mismatch in transferToState");
   5280         if(targetBool && (!memVRTable[k].inMemory)) {
   5281             //dump to memory, check entries in compileTable: vA gp vA xmm vA ss
   5282 #ifdef DEBUG_STATE
   5283             ALOGW("inMemory mismatch for VR %d in transferToState", targetReg);
   5284 #endif
   5285             bool doneXfer = false;
   5286             int index = searchCompileTable(LowOpndRegType_xmm | LowOpndRegType_virtual, targetReg);
   5287             if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   5288                 dumpToMem(targetReg, LowOpndRegType_xmm, compileTable[index].physicalReg);
   5289                 doneXfer = true;
   5290             }
   5291             if(!doneXfer) { //vA-1, xmm
   5292                 index = searchCompileTable(LowOpndRegType_xmm | LowOpndRegType_virtual, targetReg-1);
   5293                 if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   5294                     dumpToMem(targetReg-1, LowOpndRegType_xmm, compileTable[index].physicalReg);
   5295                     doneXfer = true;
   5296                 }
   5297             }
   5298             if(!doneXfer) { //vA gp
   5299                 index = searchCompileTable(LowOpndRegType_gp | LowOpndRegType_virtual, targetReg);
   5300                 if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   5301                     dumpToMem(targetReg, LowOpndRegType_gp, compileTable[index].physicalReg);
   5302                     doneXfer = true;
   5303                 }
   5304             }
   5305             if(!doneXfer) { //vA, ss
   5306                 index = searchCompileTable(LowOpndRegType_ss | LowOpndRegType_virtual, targetReg);
   5307                 if(index >= 0 && compileTable[index].physicalReg != PhysicalReg_Null) {
   5308                     dumpToMem(targetReg, LowOpndRegType_ss, compileTable[index].physicalReg);
   5309                     doneXfer = true;
   5310                 }
   5311             }
   5312             if(!doneXfer) ALOGW("can't match inMemory of VR %d in transferToState", targetReg);
   5313         }
   5314         if((!targetBool) && memVRTable[k].inMemory) {
   5315             //do nothing
   5316         }
   5317     }
   5318 #ifdef DEBUG_STATE
   5319     ALOGI("END transferToState %d", stateNum);
   5320 #endif
   5321     goToState(stateNum);
   5322 }
   5323 /* END code to handle state transfers */
   5324