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