1 /*
2 * Copyright (C) 2009 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 #include "Dalvik.h"
18 #include "vm/compiler/CompilerInternals.h"
19 #include "ArmLIR.h"
20 #include "Codegen.h"
21
22 #define DEBUG_OPT(X)
23
24 ArmLIR* dvmCompilerGenCopy(CompilationUnit *cUnit, int rDest, int rSrc);
25
26 /* Is this a Dalvik register access? */
isDalvikLoad(ArmLIR * lir)27 static inline bool isDalvikLoad(ArmLIR *lir)
28 {
29 return (lir->useMask != ENCODE_ALL) && (lir->useMask & ENCODE_DALVIK_REG);
30 }
31
32 /* Is this a load from the literal pool? */
isLiteralLoad(ArmLIR * lir)33 static inline bool isLiteralLoad(ArmLIR *lir)
34 {
35 return (lir->useMask != ENCODE_ALL) && (lir->useMask & ENCODE_LITERAL);
36 }
37
isDalvikStore(ArmLIR * lir)38 static inline bool isDalvikStore(ArmLIR *lir)
39 {
40 return (lir->defMask != ENCODE_ALL) && (lir->defMask & ENCODE_DALVIK_REG);
41 }
42
isDalvikRegisterClobbered(ArmLIR * lir1,ArmLIR * lir2)43 static inline bool isDalvikRegisterClobbered(ArmLIR *lir1, ArmLIR *lir2)
44 {
45 int reg1Lo = DECODE_ALIAS_INFO_REG(lir1->aliasInfo);
46 int reg1Hi = reg1Lo + DECODE_ALIAS_INFO_WIDE(lir1->aliasInfo);
47 int reg2Lo = DECODE_ALIAS_INFO_REG(lir2->aliasInfo);
48 int reg2Hi = reg2Lo + DECODE_ALIAS_INFO_WIDE(lir2->aliasInfo);
49
50 return (reg1Lo == reg2Lo) || (reg1Lo == reg2Hi) || (reg1Hi == reg2Lo);
51 }
52
53 #if 0
54 /* Debugging utility routine */
55 static void dumpDependentInsnPair(ArmLIR *thisLIR, ArmLIR *checkLIR,
56 const char *optimization)
57 {
58 LOGD("************ %s ************", optimization);
59 dvmDumpLIRInsn((LIR *) thisLIR, 0);
60 dvmDumpLIRInsn((LIR *) checkLIR, 0);
61 }
62 #endif
63
64 /*
65 * Perform a pass of top-down walk to
66 * 1) Eliminate redundant loads and stores
67 * 2) Sink stores to latest possible slot
68 */
applyLoadStoreElimination(CompilationUnit * cUnit,ArmLIR * headLIR,ArmLIR * tailLIR)69 static void applyLoadStoreElimination(CompilationUnit *cUnit,
70 ArmLIR *headLIR,
71 ArmLIR *tailLIR)
72 {
73 ArmLIR *thisLIR;
74
75 cUnit->optRound++;
76 for (thisLIR = headLIR;
77 thisLIR != tailLIR;
78 thisLIR = NEXT_LIR(thisLIR)) {
79 /* Skip newly added instructions */
80 if (thisLIR->age >= cUnit->optRound) {
81 continue;
82 }
83 if (isDalvikStore(thisLIR)) {
84 int nativeRegId = thisLIR->operands[0];
85 ArmLIR *checkLIR;
86 int sinkDistance = 0;
87 /*
88 * Add r15 (pc) to the mask to prevent this instruction
89 * from sinking past branch instructions. Unset the Dalvik register
90 * bit when checking with native resource constraints.
91 */
92 u8 stopMask = (ENCODE_REG_PC | thisLIR->useMask) &
93 ~ENCODE_DALVIK_REG;
94
95 for (checkLIR = NEXT_LIR(thisLIR);
96 checkLIR != tailLIR;
97 checkLIR = NEXT_LIR(checkLIR)) {
98
99 /* Check if a Dalvik register load is redundant */
100 if (isDalvikLoad(checkLIR) &&
101 (checkLIR->aliasInfo == thisLIR->aliasInfo) &&
102 (REGTYPE(checkLIR->operands[0]) == REGTYPE(nativeRegId))) {
103 /* Insert a move to replace the load */
104 if (checkLIR->operands[0] != nativeRegId) {
105 ArmLIR *moveLIR;
106 moveLIR = dvmCompilerRegCopyNoInsert(
107 cUnit, checkLIR->operands[0], nativeRegId);
108 /*
109 * Insert the converted checkLIR instruction after the
110 * the original checkLIR since the optimization is
111 * scannng in the top-down order and the new instruction
112 * will need to be checked.
113 */
114 dvmCompilerInsertLIRAfter((LIR *) checkLIR,
115 (LIR *) moveLIR);
116 }
117 checkLIR->isNop = true;
118 continue;
119
120 /*
121 * Found a true output dependency - nuke the previous store.
122 * The register type doesn't matter here.
123 */
124 } else if (isDalvikStore(checkLIR) &&
125 (checkLIR->aliasInfo == thisLIR->aliasInfo)) {
126 thisLIR->isNop = true;
127 break;
128 /* Find out the latest slot that the store can be sunk into */
129 } else {
130 /* Last instruction reached */
131 bool stopHere = (NEXT_LIR(checkLIR) == tailLIR);
132
133 /* Store data is clobbered */
134 stopHere |= ((stopMask & checkLIR->defMask) != 0);
135
136 /* Store data partially clobbers the Dalvik register */
137 if (stopHere == false &&
138 ((checkLIR->useMask | checkLIR->defMask) &
139 ENCODE_DALVIK_REG)) {
140 stopHere = isDalvikRegisterClobbered(thisLIR, checkLIR);
141 }
142
143 /* Found a new place to put the store - move it here */
144 if (stopHere == true) {
145 DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR,
146 "SINK STORE"));
147 /* The store can be sunk for at least one cycle */
148 if (sinkDistance != 0) {
149 ArmLIR *newStoreLIR =
150 dvmCompilerNew(sizeof(ArmLIR), true);
151 *newStoreLIR = *thisLIR;
152 newStoreLIR->age = cUnit->optRound;
153 /*
154 * Stop point found - insert *before* the checkLIR
155 * since the instruction list is scanned in the
156 * top-down order.
157 */
158 dvmCompilerInsertLIRBefore((LIR *) checkLIR,
159 (LIR *) newStoreLIR);
160 thisLIR->isNop = true;
161 }
162 break;
163 }
164
165 /*
166 * Saw a real instruction that the store can be sunk after
167 */
168 if (!isPseudoOpCode(checkLIR->opCode)) {
169 sinkDistance++;
170 }
171 }
172 }
173 }
174 }
175 }
176
applyLoadHoisting(CompilationUnit * cUnit,ArmLIR * headLIR,ArmLIR * tailLIR)177 static void applyLoadHoisting(CompilationUnit *cUnit,
178 ArmLIR *headLIR,
179 ArmLIR *tailLIR)
180 {
181 ArmLIR *thisLIR;
182 /*
183 * Don't want to hoist in front of first load following a barrier (or
184 * first instruction of the block.
185 */
186 bool firstLoad = true;
187 int maxHoist = dvmCompilerTargetOptHint(kMaxHoistDistance);
188
189 cUnit->optRound++;
190 for (thisLIR = headLIR;
191 thisLIR != tailLIR;
192 thisLIR = NEXT_LIR(thisLIR)) {
193 /* Skip newly added instructions */
194 if (thisLIR->age >= cUnit->optRound ||
195 thisLIR->isNop == true) {
196 continue;
197 }
198
199 if (firstLoad && (EncodingMap[thisLIR->opCode].flags & IS_LOAD)) {
200 /*
201 * Ensure nothing will be hoisted in front of this load because
202 * it's result will likely be needed soon.
203 */
204 thisLIR->defMask |= ENCODE_MEM_USE;
205 firstLoad = false;
206 }
207
208 firstLoad |= (thisLIR->defMask == ENCODE_ALL);
209
210 if (isDalvikLoad(thisLIR)) {
211 int dRegId = DECODE_ALIAS_INFO_REG(thisLIR->aliasInfo);
212 int nativeRegId = thisLIR->operands[0];
213 ArmLIR *checkLIR;
214 int hoistDistance = 0;
215 u8 stopUseMask = (ENCODE_REG_PC | thisLIR->useMask);
216 u8 stopDefMask = thisLIR->defMask;
217 u8 checkResult;
218
219 /* First check if the load can be completely elinimated */
220 for (checkLIR = PREV_LIR(thisLIR);
221 checkLIR != headLIR;
222 checkLIR = PREV_LIR(checkLIR)) {
223
224 if (checkLIR->isNop) continue;
225
226 /*
227 * Check if the Dalvik register is previously accessed
228 * with exactly the same type.
229 */
230 if ((isDalvikLoad(checkLIR) || isDalvikStore(checkLIR)) &&
231 (checkLIR->aliasInfo == thisLIR->aliasInfo) &&
232 (checkLIR->operands[0] == nativeRegId)) {
233 /*
234 * If it is previously accessed but with a different type,
235 * the search will terminate later at the point checking
236 * for partially overlapping stores.
237 */
238 thisLIR->isNop = true;
239 break;
240 }
241
242 /*
243 * No earlier use/def can reach this load if:
244 * 1) Head instruction is reached
245 */
246 if (checkLIR == headLIR) {
247 break;
248 }
249
250 checkResult = (stopUseMask | stopDefMask) & checkLIR->defMask;
251
252 /*
253 * If both instructions are verified Dalvik accesses, clear the
254 * may- and must-alias bits to detect true resource
255 * dependencies.
256 */
257 if (checkResult & ENCODE_DALVIK_REG) {
258 checkResult &= ~(ENCODE_DALVIK_REG | ENCODE_FRAME_REF);
259 }
260
261 /*
262 * 2) load target register is clobbered
263 * 3) A branch is seen (stopUseMask has the PC bit set).
264 */
265 if (checkResult) {
266 break;
267 }
268
269 /* Store data partially clobbers the Dalvik register */
270 if (isDalvikStore(checkLIR) &&
271 isDalvikRegisterClobbered(thisLIR, checkLIR)) {
272 break;
273 }
274 }
275
276 /* The load has been eliminated */
277 if (thisLIR->isNop) continue;
278
279 /*
280 * The load cannot be eliminated. See if it can be hoisted to an
281 * earlier spot.
282 */
283 for (checkLIR = PREV_LIR(thisLIR);
284 /* empty by intention */;
285 checkLIR = PREV_LIR(checkLIR)) {
286
287 if (checkLIR->isNop) continue;
288
289 /*
290 * Check if the "thisLIR" load is redundant
291 * NOTE: At one point, we also triggered if the checkLIR
292 * instruction was a load. However, that tended to insert
293 * a load/use dependency because the full scheduler is
294 * not yet complete. When it is, we chould also trigger
295 * on loads.
296 */
297 if (isDalvikStore(checkLIR) &&
298 (checkLIR->aliasInfo == thisLIR->aliasInfo) &&
299 (REGTYPE(checkLIR->operands[0]) == REGTYPE(nativeRegId))) {
300 /* Insert a move to replace the load */
301 if (checkLIR->operands[0] != nativeRegId) {
302 ArmLIR *moveLIR;
303 moveLIR = dvmCompilerRegCopyNoInsert(
304 cUnit, nativeRegId, checkLIR->operands[0]);
305 /*
306 * Convert *thisLIR* load into a move
307 */
308 dvmCompilerInsertLIRAfter((LIR *) checkLIR,
309 (LIR *) moveLIR);
310 }
311 thisLIR->isNop = true;
312 break;
313
314 /* Find out if the load can be yanked past the checkLIR */
315 } else {
316 /* Last instruction reached */
317 bool stopHere = (checkLIR == headLIR);
318
319 /* Base address is clobbered by checkLIR */
320 checkResult = stopUseMask & checkLIR->defMask;
321 if (checkResult & ENCODE_DALVIK_REG) {
322 checkResult &= ~(ENCODE_DALVIK_REG | ENCODE_FRAME_REF);
323 }
324 stopHere |= (checkResult != 0);
325
326 /* Load target clobbers use/def in checkLIR */
327 checkResult = stopDefMask &
328 (checkLIR->useMask | checkLIR->defMask);
329 if (checkResult & ENCODE_DALVIK_REG) {
330 checkResult &= ~(ENCODE_DALVIK_REG | ENCODE_FRAME_REF);
331 }
332 stopHere |= (checkResult != 0);
333
334 /* Store data partially clobbers the Dalvik register */
335 if (stopHere == false &&
336 (checkLIR->defMask & ENCODE_DALVIK_REG)) {
337 stopHere = isDalvikRegisterClobbered(thisLIR, checkLIR);
338 }
339
340 /*
341 * Stop at an earlier Dalvik load if the offset of checkLIR
342 * is not less than thisLIR
343 *
344 * Experiments show that doing
345 *
346 * ldr r1, [r5, #16]
347 * ldr r0, [r5, #20]
348 *
349 * is much faster than
350 *
351 * ldr r0, [r5, #20]
352 * ldr r1, [r5, #16]
353 */
354 if (isDalvikLoad(checkLIR)) {
355 int dRegId2 =
356 DECODE_ALIAS_INFO_REG(checkLIR->aliasInfo);
357 if (dRegId2 <= dRegId) {
358 stopHere = true;
359 }
360 }
361
362 /* Don't go too far */
363 stopHere |= (hoistDistance >= maxHoist);
364
365 /* Found a new place to put the load - move it here */
366 if (stopHere == true) {
367 DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR,
368 "HOIST LOAD"));
369 /* The load can be hoisted for at least one cycle */
370 if (hoistDistance != 0) {
371 ArmLIR *newLoadLIR =
372 dvmCompilerNew(sizeof(ArmLIR), true);
373 *newLoadLIR = *thisLIR;
374 newLoadLIR->age = cUnit->optRound;
375 /*
376 * Stop point found - insert *after* the checkLIR
377 * since the instruction list is scanned in the
378 * bottom-up order.
379 */
380 dvmCompilerInsertLIRAfter((LIR *) checkLIR,
381 (LIR *) newLoadLIR);
382 thisLIR->isNop = true;
383 }
384 break;
385 }
386
387 /*
388 * Saw a real instruction that hosting the load is
389 * beneficial
390 */
391 if (!isPseudoOpCode(checkLIR->opCode)) {
392 hoistDistance++;
393 }
394 }
395 }
396 } else if (isLiteralLoad(thisLIR)) {
397 int litVal = thisLIR->aliasInfo;
398 int nativeRegId = thisLIR->operands[0];
399 ArmLIR *checkLIR;
400 int hoistDistance = 0;
401 u8 stopUseMask = (ENCODE_REG_PC | thisLIR->useMask) &
402 ~ENCODE_LITPOOL_REF;
403 u8 stopDefMask = thisLIR->defMask & ~ENCODE_LITPOOL_REF;
404
405 /* First check if the load can be completely elinimated */
406 for (checkLIR = PREV_LIR(thisLIR);
407 checkLIR != headLIR;
408 checkLIR = PREV_LIR(checkLIR)) {
409
410 if (checkLIR->isNop) continue;
411
412 /* Reloading same literal into same tgt reg? Eliminate if so */
413 if (isLiteralLoad(checkLIR) &&
414 (checkLIR->aliasInfo == litVal) &&
415 (checkLIR->operands[0] == nativeRegId)) {
416 thisLIR->isNop = true;
417 break;
418 }
419
420 /*
421 * No earlier use/def can reach this load if:
422 * 1) Head instruction is reached
423 * 2) load target register is clobbered
424 * 3) A branch is seen (stopUseMask has the PC bit set).
425 */
426 if ((checkLIR == headLIR) ||
427 (stopUseMask | stopDefMask) & checkLIR->defMask) {
428 break;
429 }
430 }
431
432 /* The load has been eliminated */
433 if (thisLIR->isNop) continue;
434
435 /*
436 * The load cannot be eliminated. See if it can be hoisted to an
437 * earlier spot.
438 */
439 for (checkLIR = PREV_LIR(thisLIR);
440 /* empty by intention */;
441 checkLIR = PREV_LIR(checkLIR)) {
442
443 if (checkLIR->isNop) continue;
444
445 /*
446 * TUNING: once a full scheduler exists, check here
447 * for conversion of a redundant load into a copy similar
448 * to the way redundant loads are handled above.
449 */
450
451 /* Find out if the load can be yanked past the checkLIR */
452
453 /* Last instruction reached */
454 bool stopHere = (checkLIR == headLIR);
455
456 /* Base address is clobbered by checkLIR */
457 stopHere |= ((stopUseMask & checkLIR->defMask) != 0);
458
459 /* Load target clobbers use/def in checkLIR */
460 stopHere |= ((stopDefMask &
461 (checkLIR->useMask | checkLIR->defMask)) != 0);
462
463 /* Avoid re-ordering literal pool loads */
464 stopHere |= isLiteralLoad(checkLIR);
465
466 /* Don't go too far */
467 stopHere |= (hoistDistance >= maxHoist);
468
469 /* Found a new place to put the load - move it here */
470 if (stopHere == true) {
471 DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR,
472 "HOIST LOAD"));
473 /* The store can be hoisted for at least one cycle */
474 if (hoistDistance != 0) {
475 ArmLIR *newLoadLIR =
476 dvmCompilerNew(sizeof(ArmLIR), true);
477 *newLoadLIR = *thisLIR;
478 newLoadLIR->age = cUnit->optRound;
479 /*
480 * Insertion is guaranteed to succeed since checkLIR
481 * is never the first LIR on the list
482 */
483 dvmCompilerInsertLIRAfter((LIR *) checkLIR,
484 (LIR *) newLoadLIR);
485 thisLIR->isNop = true;
486 }
487 break;
488 }
489
490 /*
491 * Saw a real instruction that hosting the load is
492 * beneficial
493 */
494 if (!isPseudoOpCode(checkLIR->opCode)) {
495 hoistDistance++;
496 }
497 }
498 }
499 }
500 }
501
dvmCompilerApplyLocalOptimizations(CompilationUnit * cUnit,LIR * headLIR,LIR * tailLIR)502 void dvmCompilerApplyLocalOptimizations(CompilationUnit *cUnit, LIR *headLIR,
503 LIR *tailLIR)
504 {
505 if (!(gDvmJit.disableOpt & (1 << kLoadStoreElimination))) {
506 applyLoadStoreElimination(cUnit, (ArmLIR *) headLIR,
507 (ArmLIR *) tailLIR);
508 }
509 if (!(gDvmJit.disableOpt & (1 << kLoadHoisting))) {
510 applyLoadHoisting(cUnit, (ArmLIR *) headLIR, (ArmLIR *) tailLIR);
511 }
512 }
513