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