buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2011 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 | |
Elliott Hughes | 11d1b0c | 2012-01-23 16:57:47 -0800 | [diff] [blame] | 17 | namespace art { |
| 18 | |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 19 | #define DEBUG_OPT(X) |
| 20 | |
| 21 | /* Check RAW, WAR, and WAR dependency on the register operands */ |
| 22 | #define CHECK_REG_DEP(use, def, check) ((def & check->useMask) || \ |
| 23 | ((use | def) & check->defMask)) |
| 24 | |
| 25 | /* Scheduler heuristics */ |
| 26 | #define MAX_HOIST_DISTANCE 20 |
| 27 | #define LDLD_DISTANCE 4 |
| 28 | #define LD_LATENCY 2 |
| 29 | |
buzbee | 31a4a6f | 2012-02-28 15:36:15 -0800 | [diff] [blame] | 30 | inline bool isDalvikRegisterClobbered(LIR* lir1, LIR* lir2) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 31 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 32 | int reg1Lo = DECODE_ALIAS_INFO_REG(lir1->aliasInfo); |
| 33 | int reg1Hi = reg1Lo + DECODE_ALIAS_INFO_WIDE(lir1->aliasInfo); |
| 34 | int reg2Lo = DECODE_ALIAS_INFO_REG(lir2->aliasInfo); |
| 35 | int reg2Hi = reg2Lo + DECODE_ALIAS_INFO_WIDE(lir2->aliasInfo); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 36 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 37 | return (reg1Lo == reg2Lo) || (reg1Lo == reg2Hi) || (reg1Hi == reg2Lo); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 38 | } |
| 39 | |
| 40 | /* Convert a more expensive instruction (ie load) into a move */ |
buzbee | 31a4a6f | 2012-02-28 15:36:15 -0800 | [diff] [blame] | 41 | void convertMemOpIntoMove(CompilationUnit* cUnit, LIR* origLIR, int dest, |
| 42 | int src) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 43 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 44 | /* Insert a move to replace the load */ |
| 45 | LIR* moveLIR; |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame^] | 46 | moveLIR = opRegCopyNoInsert( cUnit, dest, src); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 47 | /* |
| 48 | * Insert the converted instruction after the original since the |
| 49 | * optimization is scannng in the top-down order and the new instruction |
| 50 | * will need to be re-checked (eg the new dest clobbers the src used in |
| 51 | * thisLIR). |
| 52 | */ |
| 53 | oatInsertLIRAfter((LIR*) origLIR, (LIR*) moveLIR); |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 54 | } |
| 55 | |
| 56 | /* |
| 57 | * Perform a pass of top-down walk, from the second-last instruction in the |
| 58 | * superblock, to eliminate redundant loads and stores. |
| 59 | * |
| 60 | * An earlier load can eliminate a later load iff |
| 61 | * 1) They are must-aliases |
| 62 | * 2) The native register is not clobbered in between |
| 63 | * 3) The memory location is not written to in between |
| 64 | * |
| 65 | * An earlier store can eliminate a later load iff |
| 66 | * 1) They are must-aliases |
| 67 | * 2) The native register is not clobbered in between |
| 68 | * 3) The memory location is not written to in between |
| 69 | * |
| 70 | * A later store can be eliminated by an earlier store iff |
| 71 | * 1) They are must-aliases |
| 72 | * 2) The memory location is not written to in between |
| 73 | */ |
buzbee | 31a4a6f | 2012-02-28 15:36:15 -0800 | [diff] [blame] | 74 | void applyLoadStoreElimination(CompilationUnit* cUnit, LIR* headLIR, |
| 75 | LIR* tailLIR) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 76 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 77 | LIR* thisLIR; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 78 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 79 | if (headLIR == tailLIR) return; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 80 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 81 | for (thisLIR = PREV_LIR(tailLIR); |
| 82 | thisLIR != headLIR; |
| 83 | thisLIR = PREV_LIR(thisLIR)) { |
| 84 | int sinkDistance = 0; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 85 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 86 | /* Skip non-interesting instructions */ |
| 87 | if ((thisLIR->flags.isNop == true) || |
| 88 | isPseudoOpcode(thisLIR->opcode) || |
jeffhao | e296248 | 2012-06-28 11:29:57 -0700 | [diff] [blame] | 89 | (EncodingMap[thisLIR->opcode].flags & IS_BRANCH) || |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 90 | !(EncodingMap[thisLIR->opcode].flags & (IS_LOAD | IS_STORE))) { |
| 91 | continue; |
| 92 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 93 | |
buzbee | b046e16 | 2012-10-30 15:48:42 -0700 | [diff] [blame] | 94 | int nativeRegId; |
| 95 | if (cUnit->instructionSet == kX86) { |
| 96 | // If x86, location differs depending on whether memory/reg operation. |
| 97 | nativeRegId = (EncodingMap[thisLIR->opcode].flags & IS_STORE) ? thisLIR->operands[2] |
| 98 | : thisLIR->operands[0]; |
| 99 | } else { |
| 100 | nativeRegId = thisLIR->operands[0]; |
| 101 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 102 | bool isThisLIRLoad = EncodingMap[thisLIR->opcode].flags & IS_LOAD; |
| 103 | LIR* checkLIR; |
| 104 | /* Use the mem mask to determine the rough memory location */ |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame^] | 105 | uint64_t thisMemMask = (thisLIR->useMask | thisLIR->defMask) & ENCODE_MEM; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 106 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 107 | /* |
| 108 | * Currently only eliminate redundant ld/st for constant and Dalvik |
| 109 | * register accesses. |
| 110 | */ |
| 111 | if (!(thisMemMask & (ENCODE_LITERAL | ENCODE_DALVIK_REG))) continue; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 112 | |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame^] | 113 | uint64_t stopDefRegMask = thisLIR->defMask & ~ENCODE_MEM; |
| 114 | uint64_t stopUseRegMask; |
buzbee | b046e16 | 2012-10-30 15:48:42 -0700 | [diff] [blame] | 115 | if (cUnit->instructionSet == kX86) { |
| 116 | stopUseRegMask = (IS_BRANCH | thisLIR->useMask) & ~ENCODE_MEM; |
| 117 | } else { |
| 118 | /* |
| 119 | * Add pc to the resource mask to prevent this instruction |
| 120 | * from sinking past branch instructions. Also take out the memory |
| 121 | * region bits since stopMask is used to check data/control |
| 122 | * dependencies. |
| 123 | */ |
buzbee | ec13743 | 2012-11-13 12:13:16 -0800 | [diff] [blame] | 124 | stopUseRegMask = (getPCUseDefEncoding() | thisLIR->useMask) & ~ENCODE_MEM; |
buzbee | b046e16 | 2012-10-30 15:48:42 -0700 | [diff] [blame] | 125 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 126 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 127 | for (checkLIR = NEXT_LIR(thisLIR); |
| 128 | checkLIR != tailLIR; |
| 129 | checkLIR = NEXT_LIR(checkLIR)) { |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 130 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 131 | /* |
| 132 | * Skip already dead instructions (whose dataflow information is |
| 133 | * outdated and misleading). |
| 134 | */ |
| 135 | if (checkLIR->flags.isNop) continue; |
| 136 | |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame^] | 137 | uint64_t checkMemMask = (checkLIR->useMask | checkLIR->defMask) & ENCODE_MEM; |
| 138 | uint64_t aliasCondition = thisMemMask & checkMemMask; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 139 | bool stopHere = false; |
| 140 | |
| 141 | /* |
| 142 | * Potential aliases seen - check the alias relations |
| 143 | */ |
| 144 | if (checkMemMask != ENCODE_MEM && aliasCondition != 0) { |
| 145 | bool isCheckLIRLoad = EncodingMap[checkLIR->opcode].flags & IS_LOAD; |
| 146 | if (aliasCondition == ENCODE_LITERAL) { |
| 147 | /* |
| 148 | * Should only see literal loads in the instruction |
| 149 | * stream. |
| 150 | */ |
| 151 | DCHECK(!(EncodingMap[checkLIR->opcode].flags & IS_STORE)); |
| 152 | /* Same value && same register type */ |
| 153 | if (checkLIR->aliasInfo == thisLIR->aliasInfo && |
buzbee | f0504cd | 2012-11-13 16:31:10 -0800 | [diff] [blame] | 154 | sameRegType(checkLIR->operands[0], nativeRegId)) { |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 155 | /* |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 156 | * Different destination register - insert |
| 157 | * a move |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 158 | */ |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 159 | if (checkLIR->operands[0] != nativeRegId) { |
| 160 | convertMemOpIntoMove(cUnit, checkLIR, checkLIR->operands[0], |
| 161 | nativeRegId); |
| 162 | } |
| 163 | checkLIR->flags.isNop = true; |
| 164 | } |
| 165 | } else if (aliasCondition == ENCODE_DALVIK_REG) { |
| 166 | /* Must alias */ |
| 167 | if (checkLIR->aliasInfo == thisLIR->aliasInfo) { |
| 168 | /* Only optimize compatible registers */ |
buzbee | f0504cd | 2012-11-13 16:31:10 -0800 | [diff] [blame] | 169 | bool regCompatible = sameRegType(checkLIR->operands[0], nativeRegId); |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 170 | if ((isThisLIRLoad && isCheckLIRLoad) || |
| 171 | (!isThisLIRLoad && isCheckLIRLoad)) { |
| 172 | /* RAR or RAW */ |
| 173 | if (regCompatible) { |
| 174 | /* |
| 175 | * Different destination register - |
| 176 | * insert a move |
| 177 | */ |
| 178 | if (checkLIR->operands[0] != |
| 179 | nativeRegId) { |
| 180 | convertMemOpIntoMove(cUnit, checkLIR, checkLIR->operands[0], |
| 181 | nativeRegId); |
| 182 | } |
| 183 | checkLIR->flags.isNop = true; |
| 184 | } else { |
| 185 | /* |
| 186 | * Destinaions are of different types - |
| 187 | * something complicated going on so |
| 188 | * stop looking now. |
| 189 | */ |
| 190 | stopHere = true; |
| 191 | } |
| 192 | } else if (isThisLIRLoad && !isCheckLIRLoad) { |
| 193 | /* WAR - register value is killed */ |
| 194 | stopHere = true; |
| 195 | } else if (!isThisLIRLoad && !isCheckLIRLoad) { |
| 196 | /* WAW - nuke the earlier store */ |
| 197 | thisLIR->flags.isNop = true; |
| 198 | stopHere = true; |
| 199 | } |
| 200 | /* Partial overlap */ |
| 201 | } else if (isDalvikRegisterClobbered(thisLIR, checkLIR)) { |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 202 | /* |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 203 | * It is actually ok to continue if checkLIR |
| 204 | * is a read. But it is hard to make a test |
| 205 | * case for this so we just stop here to be |
| 206 | * conservative. |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 207 | */ |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 208 | stopHere = true; |
| 209 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 210 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 211 | /* Memory content may be updated. Stop looking now. */ |
| 212 | if (stopHere) { |
| 213 | break; |
| 214 | /* The checkLIR has been transformed - check the next one */ |
| 215 | } else if (checkLIR->flags.isNop) { |
| 216 | continue; |
| 217 | } |
| 218 | } |
| 219 | |
| 220 | |
| 221 | /* |
| 222 | * this and check LIRs have no memory dependency. Now check if |
| 223 | * their register operands have any RAW, WAR, and WAW |
| 224 | * dependencies. If so, stop looking. |
| 225 | */ |
| 226 | if (stopHere == false) { |
| 227 | stopHere = CHECK_REG_DEP(stopUseRegMask, stopDefRegMask, checkLIR); |
| 228 | } |
| 229 | |
| 230 | if (stopHere == true) { |
buzbee | b046e16 | 2012-10-30 15:48:42 -0700 | [diff] [blame] | 231 | if (cUnit->instructionSet == kX86) { |
| 232 | // Prevent stores from being sunk between ops that generate ccodes and |
| 233 | // ops that use them. |
buzbee | ec13743 | 2012-11-13 12:13:16 -0800 | [diff] [blame] | 234 | uint64_t flags = EncodingMap[checkLIR->opcode].flags; |
buzbee | b046e16 | 2012-10-30 15:48:42 -0700 | [diff] [blame] | 235 | if (sinkDistance > 0 && (flags & IS_BRANCH) && (flags & USES_CCODES)) { |
| 236 | checkLIR = PREV_LIR(checkLIR); |
| 237 | sinkDistance--; |
| 238 | } |
jeffhao | 573b429 | 2012-07-30 16:37:41 -0700 | [diff] [blame] | 239 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 240 | DEBUG_OPT(dumpDependentInsnPair(thisLIR, checkLIR, "REG CLOBBERED")); |
| 241 | /* Only sink store instructions */ |
| 242 | if (sinkDistance && !isThisLIRLoad) { |
| 243 | LIR* newStoreLIR = |
| 244 | (LIR* ) oatNew(cUnit, sizeof(LIR), true, kAllocLIR); |
| 245 | *newStoreLIR = *thisLIR; |
| 246 | /* |
| 247 | * Stop point found - insert *before* the checkLIR |
| 248 | * since the instruction list is scanned in the |
| 249 | * top-down order. |
| 250 | */ |
| 251 | oatInsertLIRBefore((LIR*) checkLIR, (LIR*) newStoreLIR); |
| 252 | thisLIR->flags.isNop = true; |
| 253 | } |
| 254 | break; |
| 255 | } else if (!checkLIR->flags.isNop) { |
| 256 | sinkDistance++; |
| 257 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 258 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 259 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 260 | } |
| 261 | |
| 262 | /* |
| 263 | * Perform a pass of bottom-up walk, from the second instruction in the |
| 264 | * superblock, to try to hoist loads to earlier slots. |
| 265 | */ |
buzbee | 31a4a6f | 2012-02-28 15:36:15 -0800 | [diff] [blame] | 266 | void applyLoadHoisting(CompilationUnit* cUnit, LIR* headLIR, LIR* tailLIR) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 267 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 268 | LIR* thisLIR, *checkLIR; |
| 269 | /* |
| 270 | * Store the list of independent instructions that can be hoisted past. |
| 271 | * Will decide the best place to insert later. |
| 272 | */ |
| 273 | LIR* prevInstList[MAX_HOIST_DISTANCE]; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 274 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 275 | /* Empty block */ |
| 276 | if (headLIR == tailLIR) return; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 277 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 278 | /* Start from the second instruction */ |
| 279 | for (thisLIR = NEXT_LIR(headLIR); |
| 280 | thisLIR != tailLIR; |
| 281 | thisLIR = NEXT_LIR(thisLIR)) { |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 282 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 283 | /* Skip non-interesting instructions */ |
| 284 | if ((thisLIR->flags.isNop == true) || |
| 285 | isPseudoOpcode(thisLIR->opcode) || |
| 286 | !(EncodingMap[thisLIR->opcode].flags & IS_LOAD)) { |
| 287 | continue; |
| 288 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 289 | |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame^] | 290 | uint64_t stopUseAllMask = thisLIR->useMask; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 291 | |
buzbee | b046e16 | 2012-10-30 15:48:42 -0700 | [diff] [blame] | 292 | if (cUnit->instructionSet != kX86) { |
| 293 | /* |
| 294 | * Branches for null/range checks are marked with the true resource |
| 295 | * bits, and loads to Dalvik registers, constant pools, and non-alias |
| 296 | * locations are safe to be hoisted. So only mark the heap references |
| 297 | * conservatively here. |
| 298 | */ |
| 299 | if (stopUseAllMask & ENCODE_HEAP_REF) { |
buzbee | ec13743 | 2012-11-13 12:13:16 -0800 | [diff] [blame] | 300 | stopUseAllMask |= getPCUseDefEncoding(); |
buzbee | b046e16 | 2012-10-30 15:48:42 -0700 | [diff] [blame] | 301 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 302 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 303 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 304 | /* Similar as above, but just check for pure register dependency */ |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame^] | 305 | uint64_t stopUseRegMask = stopUseAllMask & ~ENCODE_MEM; |
| 306 | uint64_t stopDefRegMask = thisLIR->defMask & ~ENCODE_MEM; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 307 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 308 | int nextSlot = 0; |
| 309 | bool stopHere = false; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 310 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 311 | /* Try to hoist the load to a good spot */ |
| 312 | for (checkLIR = PREV_LIR(thisLIR); |
| 313 | checkLIR != headLIR; |
| 314 | checkLIR = PREV_LIR(checkLIR)) { |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 315 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 316 | /* |
| 317 | * Skip already dead instructions (whose dataflow information is |
| 318 | * outdated and misleading). |
| 319 | */ |
| 320 | if (checkLIR->flags.isNop) continue; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 321 | |
buzbee | eaf09bc | 2012-11-15 14:51:41 -0800 | [diff] [blame^] | 322 | uint64_t checkMemMask = checkLIR->defMask & ENCODE_MEM; |
| 323 | uint64_t aliasCondition = stopUseAllMask & checkMemMask; |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 324 | stopHere = false; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 325 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 326 | /* Potential WAR alias seen - check the exact relation */ |
| 327 | if (checkMemMask != ENCODE_MEM && aliasCondition != 0) { |
| 328 | /* We can fully disambiguate Dalvik references */ |
| 329 | if (aliasCondition == ENCODE_DALVIK_REG) { |
| 330 | /* Must alias or partually overlap */ |
| 331 | if ((checkLIR->aliasInfo == thisLIR->aliasInfo) || |
| 332 | isDalvikRegisterClobbered(thisLIR, checkLIR)) { |
| 333 | stopHere = true; |
| 334 | } |
| 335 | /* Conservatively treat all heap refs as may-alias */ |
| 336 | } else { |
| 337 | DCHECK_EQ(aliasCondition, ENCODE_HEAP_REF); |
| 338 | stopHere = true; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 339 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 340 | /* Memory content may be updated. Stop looking now. */ |
| 341 | if (stopHere) { |
| 342 | prevInstList[nextSlot++] = checkLIR; |
| 343 | break; |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 344 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 345 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 346 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 347 | if (stopHere == false) { |
| 348 | stopHere = CHECK_REG_DEP(stopUseRegMask, stopDefRegMask, |
| 349 | checkLIR); |
| 350 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 351 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 352 | /* |
| 353 | * Store the dependent or non-pseudo/indepedent instruction to the |
| 354 | * list. |
| 355 | */ |
| 356 | if (stopHere || !isPseudoOpcode(checkLIR->opcode)) { |
| 357 | prevInstList[nextSlot++] = checkLIR; |
| 358 | if (nextSlot == MAX_HOIST_DISTANCE) break; |
| 359 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 360 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 361 | /* Found a new place to put the load - move it here */ |
| 362 | if (stopHere == true) { |
| 363 | DEBUG_OPT(dumpDependentInsnPair(checkLIR, thisLIR "HOIST STOP")); |
| 364 | break; |
| 365 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 366 | } |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 367 | |
| 368 | /* |
| 369 | * Reached the top - use headLIR as the dependent marker as all labels |
| 370 | * are barriers. |
| 371 | */ |
| 372 | if (stopHere == false && nextSlot < MAX_HOIST_DISTANCE) { |
| 373 | prevInstList[nextSlot++] = headLIR; |
| 374 | } |
| 375 | |
| 376 | /* |
| 377 | * At least one independent instruction is found. Scan in the reversed |
| 378 | * direction to find a beneficial slot. |
| 379 | */ |
| 380 | if (nextSlot >= 2) { |
| 381 | int firstSlot = nextSlot - 2; |
| 382 | int slot; |
| 383 | LIR* depLIR = prevInstList[nextSlot-1]; |
| 384 | /* If there is ld-ld dependency, wait LDLD_DISTANCE cycles */ |
| 385 | if (!isPseudoOpcode(depLIR->opcode) && |
| 386 | (EncodingMap[depLIR->opcode].flags & IS_LOAD)) { |
| 387 | firstSlot -= LDLD_DISTANCE; |
| 388 | } |
| 389 | /* |
| 390 | * Make sure we check slot >= 0 since firstSlot may be negative |
| 391 | * when the loop is first entered. |
| 392 | */ |
| 393 | for (slot = firstSlot; slot >= 0; slot--) { |
| 394 | LIR* curLIR = prevInstList[slot]; |
| 395 | LIR* prevLIR = prevInstList[slot+1]; |
| 396 | |
| 397 | /* Check the highest instruction */ |
| 398 | if (prevLIR->defMask == ENCODE_ALL) { |
| 399 | /* |
| 400 | * If the first instruction is a load, don't hoist anything |
| 401 | * above it since it is unlikely to be beneficial. |
| 402 | */ |
| 403 | if (EncodingMap[curLIR->opcode].flags & IS_LOAD) continue; |
| 404 | /* |
| 405 | * If the remaining number of slots is less than LD_LATENCY, |
| 406 | * insert the hoisted load here. |
| 407 | */ |
| 408 | if (slot < LD_LATENCY) break; |
| 409 | } |
| 410 | |
buzbee | 8320f38 | 2012-09-11 16:29:42 -0700 | [diff] [blame] | 411 | // Don't look across a barrier label |
| 412 | if ((prevLIR->opcode == kPseudoTargetLabel) || |
| 413 | (prevLIR->opcode == kPseudoSafepointPC) || |
| 414 | (prevLIR->opcode == kPseudoBarrier)) { |
| 415 | break; |
| 416 | } |
| 417 | |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 418 | /* |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 419 | * Try to find two instructions with load/use dependency until |
| 420 | * the remaining instructions are less than LD_LATENCY. |
| 421 | */ |
buzbee | 8320f38 | 2012-09-11 16:29:42 -0700 | [diff] [blame] | 422 | bool prevIsLoad = isPseudoOpcode(prevLIR->opcode) ? false : |
| 423 | (EncodingMap[prevLIR->opcode].flags & IS_LOAD); |
| 424 | if (((curLIR->useMask & prevLIR->defMask) && prevIsLoad) || (slot < LD_LATENCY)) { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 425 | break; |
| 426 | } |
| 427 | } |
| 428 | |
| 429 | /* Found a slot to hoist to */ |
| 430 | if (slot >= 0) { |
| 431 | LIR* curLIR = prevInstList[slot]; |
| 432 | LIR* newLoadLIR = (LIR* ) oatNew(cUnit, sizeof(LIR), |
| 433 | true, kAllocLIR); |
| 434 | *newLoadLIR = *thisLIR; |
| 435 | /* |
| 436 | * Insertion is guaranteed to succeed since checkLIR |
| 437 | * is never the first LIR on the list |
| 438 | */ |
| 439 | oatInsertLIRBefore((LIR*) curLIR, (LIR*) newLoadLIR); |
| 440 | thisLIR->flags.isNop = true; |
| 441 | } |
| 442 | } |
| 443 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 444 | } |
| 445 | |
| 446 | void oatApplyLocalOptimizations(CompilationUnit* cUnit, LIR* headLIR, |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 447 | LIR* tailLIR) |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 448 | { |
Bill Buzbee | a114add | 2012-05-03 15:00:40 -0700 | [diff] [blame] | 449 | if (!(cUnit->disableOpt & (1 << kLoadStoreElimination))) { |
| 450 | applyLoadStoreElimination(cUnit, (LIR* ) headLIR, |
| 451 | (LIR* ) tailLIR); |
| 452 | } |
| 453 | if (!(cUnit->disableOpt & (1 << kLoadHoisting))) { |
| 454 | applyLoadHoisting(cUnit, (LIR* ) headLIR, (LIR* ) tailLIR); |
| 455 | } |
buzbee | 67bf885 | 2011-08-17 17:51:35 -0700 | [diff] [blame] | 456 | } |
Elliott Hughes | 11d1b0c | 2012-01-23 16:57:47 -0800 | [diff] [blame] | 457 | |
| 458 | } // namespace art |