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 */
isVirtualReg(int type)64 bool isVirtualReg(int type) {
65 if((type & LowOpndRegType_virtual) != 0) return true;
66 return false;
67 }
isTemporary(int type,int regNum)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 */
convertType(int type,int reg,bool isPhysical)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 */
getRegSize(int type)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 */
getBPartiallyOverlapA(int regB,LowOpndRegType tB,int regA,LowOpndRegType tA)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 */
getAPartiallyOverlapB(int regA,LowOpndRegType tA,int regB,LowOpndRegType tB)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 */
isAFullyCoverB(int regA,LowOpndRegType tA,int regB,LowOpndRegType tB)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 */
isCurrentByteCodeJump()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 */
initializeAllRegs()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 */
syncAllRegs()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 //!
updateSpillIndexUsed()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 */
freeCFG()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 */
initializeRegStateOfBB(BasicBlock_O1 * bb)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 */
initializeNullCheck(int indexToMemVR)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 */
initializeMemVRTable()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 */
createBasicBlockO1(BasicBlock * bb)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 */
preprocessingBB(BasicBlock * bb)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
preprocessingTrace()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
printJitTraceInfoAtRunTime(const Method * method,int offset)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
startOfTraceO1(const Method * method,LowOpBlockLabel * labelList,int exceptionBlockId,CompilationUnit * cUnit)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 */
codeGenBasicBlockJit(const Method * method,BasicBlock * bb)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 }
endOfBasicBlock(BasicBlock * bb)638 void endOfBasicBlock(BasicBlock* bb) {
639 isScratchPhysical = true;
640 currentBB = NULL;
641 }
endOfTraceO1()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 */
collectInfoOfBasicBlock(Method * method,BasicBlock_O1 * bb)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 */
codeGenBasicBlock(const Method * method,BasicBlock_O1 * bb)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