local_optimizations.cc revision 7940e44f4517de5e2634a7e07d58d0fb26160513
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 17#include "dex/compiler_internals.h" 18 19namespace art { 20 21#define DEBUG_OPT(X) 22 23/* Check RAW, WAR, and RAW dependency on the register operands */ 24#define CHECK_REG_DEP(use, def, check) ((def & check->use_mask) || \ 25 ((use | def) & check->def_mask)) 26 27/* Scheduler heuristics */ 28#define MAX_HOIST_DISTANCE 20 29#define LDLD_DISTANCE 4 30#define LD_LATENCY 2 31 32static bool IsDalvikRegisterClobbered(LIR* lir1, LIR* lir2) 33{ 34 int reg1Lo = DECODE_ALIAS_INFO_REG(lir1->alias_info); 35 int reg1Hi = reg1Lo + DECODE_ALIAS_INFO_WIDE(lir1->alias_info); 36 int reg2Lo = DECODE_ALIAS_INFO_REG(lir2->alias_info); 37 int reg2Hi = reg2Lo + DECODE_ALIAS_INFO_WIDE(lir2->alias_info); 38 39 return (reg1Lo == reg2Lo) || (reg1Lo == reg2Hi) || (reg1Hi == reg2Lo); 40} 41 42/* Convert a more expensive instruction (ie load) into a move */ 43void Mir2Lir::ConvertMemOpIntoMove(LIR* orig_lir, int dest, int src) 44{ 45 /* Insert a move to replace the load */ 46 LIR* move_lir; 47 move_lir = OpRegCopyNoInsert(dest, src); 48 /* 49 * Insert the converted instruction after the original since the 50 * optimization is scannng in the top-down order and the new instruction 51 * will need to be re-checked (eg the new dest clobbers the src used in 52 * this_lir). 53 */ 54 InsertLIRAfter(orig_lir, move_lir); 55} 56 57/* 58 * Perform a pass of top-down walk, from the second-last instruction in the 59 * superblock, to eliminate redundant loads and stores. 60 * 61 * An earlier load can eliminate a later load iff 62 * 1) They are must-aliases 63 * 2) The native register is not clobbered in between 64 * 3) The memory location is not written to in between 65 * 66 * An earlier store can eliminate a later load iff 67 * 1) They are must-aliases 68 * 2) The native register is not clobbered in between 69 * 3) The memory location is not written to in between 70 * 71 * A later store can be eliminated by an earlier store iff 72 * 1) They are must-aliases 73 * 2) The memory location is not written to in between 74 */ 75void Mir2Lir::ApplyLoadStoreElimination(LIR* head_lir, LIR* tail_lir) 76{ 77 LIR* this_lir; 78 79 if (head_lir == tail_lir) return; 80 81 for (this_lir = PREV_LIR(tail_lir); this_lir != head_lir; this_lir = PREV_LIR(this_lir)) { 82 83 if (is_pseudo_opcode(this_lir->opcode)) continue; 84 85 int sink_distance = 0; 86 87 uint64_t target_flags = GetTargetInstFlags(this_lir->opcode); 88 89 /* Skip non-interesting instructions */ 90 if ((this_lir->flags.is_nop == true) || 91 (target_flags & IS_BRANCH) || 92 ((target_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) || // Skip wide loads. 93 ((target_flags & (REG_USE0 | REG_USE1 | REG_USE2)) == 94 (REG_USE0 | REG_USE1 | REG_USE2)) || // Skip wide stores. 95 !(target_flags & (IS_LOAD | IS_STORE))) { 96 continue; 97 } 98 99 int native_reg_id; 100 if (cu_->instruction_set == kX86) { 101 // If x86, location differs depending on whether memory/reg operation. 102 native_reg_id = (GetTargetInstFlags(this_lir->opcode) & IS_STORE) ? this_lir->operands[2] 103 : this_lir->operands[0]; 104 } else { 105 native_reg_id = this_lir->operands[0]; 106 } 107 bool is_this_lir_load = GetTargetInstFlags(this_lir->opcode) & IS_LOAD; 108 LIR* check_lir; 109 /* Use the mem mask to determine the rough memory location */ 110 uint64_t this_mem_mask = (this_lir->use_mask | this_lir->def_mask) & ENCODE_MEM; 111 112 /* 113 * Currently only eliminate redundant ld/st for constant and Dalvik 114 * register accesses. 115 */ 116 if (!(this_mem_mask & (ENCODE_LITERAL | ENCODE_DALVIK_REG))) continue; 117 118 uint64_t stop_def_reg_mask = this_lir->def_mask & ~ENCODE_MEM; 119 uint64_t stop_use_reg_mask; 120 if (cu_->instruction_set == kX86) { 121 stop_use_reg_mask = (IS_BRANCH | this_lir->use_mask) & ~ENCODE_MEM; 122 } else { 123 /* 124 * Add pc to the resource mask to prevent this instruction 125 * from sinking past branch instructions. Also take out the memory 126 * region bits since stop_mask is used to check data/control 127 * dependencies. 128 */ 129 stop_use_reg_mask = (GetPCUseDefEncoding() | this_lir->use_mask) & ~ENCODE_MEM; 130 } 131 132 for (check_lir = NEXT_LIR(this_lir); check_lir != tail_lir; check_lir = NEXT_LIR(check_lir)) { 133 134 /* 135 * Skip already dead instructions (whose dataflow information is 136 * outdated and misleading). 137 */ 138 if (check_lir->flags.is_nop || is_pseudo_opcode(check_lir->opcode)) continue; 139 140 uint64_t check_mem_mask = (check_lir->use_mask | check_lir->def_mask) & ENCODE_MEM; 141 uint64_t alias_condition = this_mem_mask & check_mem_mask; 142 bool stop_here = false; 143 144 /* 145 * Potential aliases seen - check the alias relations 146 */ 147 uint64_t check_flags = GetTargetInstFlags(check_lir->opcode); 148 // TUNING: Support instructions with multiple register targets. 149 if ((check_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) { 150 stop_here = true; 151 } else if (check_mem_mask != ENCODE_MEM && alias_condition != 0) { 152 bool is_check_lir_load = check_flags & IS_LOAD; 153 if (alias_condition == ENCODE_LITERAL) { 154 /* 155 * Should only see literal loads in the instruction 156 * stream. 157 */ 158 DCHECK(!(check_flags & IS_STORE)); 159 /* Same value && same register type */ 160 if (check_lir->alias_info == this_lir->alias_info && 161 SameRegType(check_lir->operands[0], native_reg_id)) { 162 /* 163 * Different destination register - insert 164 * a move 165 */ 166 if (check_lir->operands[0] != native_reg_id) { 167 ConvertMemOpIntoMove(check_lir, check_lir->operands[0], native_reg_id); 168 } 169 check_lir->flags.is_nop = true; 170 } 171 } else if (alias_condition == ENCODE_DALVIK_REG) { 172 /* Must alias */ 173 if (check_lir->alias_info == this_lir->alias_info) { 174 /* Only optimize compatible registers */ 175 bool reg_compatible = SameRegType(check_lir->operands[0], native_reg_id); 176 if ((is_this_lir_load && is_check_lir_load) || 177 (!is_this_lir_load && is_check_lir_load)) { 178 /* RAR or RAW */ 179 if (reg_compatible) { 180 /* 181 * Different destination register - 182 * insert a move 183 */ 184 if (check_lir->operands[0] != 185 native_reg_id) { 186 ConvertMemOpIntoMove(check_lir, check_lir->operands[0], native_reg_id); 187 } 188 check_lir->flags.is_nop = true; 189 } else { 190 /* 191 * Destinaions are of different types - 192 * something complicated going on so 193 * stop looking now. 194 */ 195 stop_here = true; 196 } 197 } else if (is_this_lir_load && !is_check_lir_load) { 198 /* WAR - register value is killed */ 199 stop_here = true; 200 } else if (!is_this_lir_load && !is_check_lir_load) { 201 /* WAW - nuke the earlier store */ 202 this_lir->flags.is_nop = true; 203 stop_here = true; 204 } 205 /* Partial overlap */ 206 } else if (IsDalvikRegisterClobbered(this_lir, check_lir)) { 207 /* 208 * It is actually ok to continue if check_lir 209 * is a read. But it is hard to make a test 210 * case for this so we just stop here to be 211 * conservative. 212 */ 213 stop_here = true; 214 } 215 } 216 /* Memory content may be updated. Stop looking now. */ 217 if (stop_here) { 218 break; 219 /* The check_lir has been transformed - check the next one */ 220 } else if (check_lir->flags.is_nop) { 221 continue; 222 } 223 } 224 225 226 /* 227 * this and check LIRs have no memory dependency. Now check if 228 * their register operands have any RAW, WAR, and WAW 229 * dependencies. If so, stop looking. 230 */ 231 if (stop_here == false) { 232 stop_here = CHECK_REG_DEP(stop_use_reg_mask, stop_def_reg_mask, check_lir); 233 } 234 235 if (stop_here == true) { 236 if (cu_->instruction_set == kX86) { 237 // Prevent stores from being sunk between ops that generate ccodes and 238 // ops that use them. 239 uint64_t flags = GetTargetInstFlags(check_lir->opcode); 240 if (sink_distance > 0 && (flags & IS_BRANCH) && (flags & USES_CCODES)) { 241 check_lir = PREV_LIR(check_lir); 242 sink_distance--; 243 } 244 } 245 DEBUG_OPT(dump_dependent_insn_pair(this_lir, check_lir, "REG CLOBBERED")); 246 /* Only sink store instructions */ 247 if (sink_distance && !is_this_lir_load) { 248 LIR* new_store_lir = 249 static_cast<LIR*>(arena_->NewMem(sizeof(LIR), true, ArenaAllocator::kAllocLIR)); 250 *new_store_lir = *this_lir; 251 /* 252 * Stop point found - insert *before* the check_lir 253 * since the instruction list is scanned in the 254 * top-down order. 255 */ 256 InsertLIRBefore(check_lir, new_store_lir); 257 this_lir->flags.is_nop = true; 258 } 259 break; 260 } else if (!check_lir->flags.is_nop) { 261 sink_distance++; 262 } 263 } 264 } 265} 266 267/* 268 * Perform a pass of bottom-up walk, from the second instruction in the 269 * superblock, to try to hoist loads to earlier slots. 270 */ 271void Mir2Lir::ApplyLoadHoisting(LIR* head_lir, LIR* tail_lir) 272{ 273 LIR* this_lir, *check_lir; 274 /* 275 * Store the list of independent instructions that can be hoisted past. 276 * Will decide the best place to insert later. 277 */ 278 LIR* prev_inst_list[MAX_HOIST_DISTANCE]; 279 280 /* Empty block */ 281 if (head_lir == tail_lir) return; 282 283 /* Start from the second instruction */ 284 for (this_lir = NEXT_LIR(head_lir); this_lir != tail_lir; this_lir = NEXT_LIR(this_lir)) { 285 286 if (is_pseudo_opcode(this_lir->opcode)) continue; 287 288 uint64_t target_flags = GetTargetInstFlags(this_lir->opcode); 289 /* Skip non-interesting instructions */ 290 if ((this_lir->flags.is_nop == true) || 291 ((target_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) || 292 !(target_flags & IS_LOAD)) { 293 continue; 294 } 295 296 uint64_t stop_use_all_mask = this_lir->use_mask; 297 298 if (cu_->instruction_set != kX86) { 299 /* 300 * Branches for null/range checks are marked with the true resource 301 * bits, and loads to Dalvik registers, constant pools, and non-alias 302 * locations are safe to be hoisted. So only mark the heap references 303 * conservatively here. 304 */ 305 if (stop_use_all_mask & ENCODE_HEAP_REF) { 306 stop_use_all_mask |= GetPCUseDefEncoding(); 307 } 308 } 309 310 /* Similar as above, but just check for pure register dependency */ 311 uint64_t stop_use_reg_mask = stop_use_all_mask & ~ENCODE_MEM; 312 uint64_t stop_def_reg_mask = this_lir->def_mask & ~ENCODE_MEM; 313 314 int next_slot = 0; 315 bool stop_here = false; 316 317 /* Try to hoist the load to a good spot */ 318 for (check_lir = PREV_LIR(this_lir); check_lir != head_lir; check_lir = PREV_LIR(check_lir)) { 319 320 /* 321 * Skip already dead instructions (whose dataflow information is 322 * outdated and misleading). 323 */ 324 if (check_lir->flags.is_nop) continue; 325 326 uint64_t check_mem_mask = check_lir->def_mask & ENCODE_MEM; 327 uint64_t alias_condition = stop_use_all_mask & check_mem_mask; 328 stop_here = false; 329 330 /* Potential WAR alias seen - check the exact relation */ 331 if (check_mem_mask != ENCODE_MEM && alias_condition != 0) { 332 /* We can fully disambiguate Dalvik references */ 333 if (alias_condition == ENCODE_DALVIK_REG) { 334 /* Must alias or partually overlap */ 335 if ((check_lir->alias_info == this_lir->alias_info) || 336 IsDalvikRegisterClobbered(this_lir, check_lir)) { 337 stop_here = true; 338 } 339 /* Conservatively treat all heap refs as may-alias */ 340 } else { 341 DCHECK_EQ(alias_condition, ENCODE_HEAP_REF); 342 stop_here = true; 343 } 344 /* Memory content may be updated. Stop looking now. */ 345 if (stop_here) { 346 prev_inst_list[next_slot++] = check_lir; 347 break; 348 } 349 } 350 351 if (stop_here == false) { 352 stop_here = CHECK_REG_DEP(stop_use_reg_mask, stop_def_reg_mask, 353 check_lir); 354 } 355 356 /* 357 * Store the dependent or non-pseudo/indepedent instruction to the 358 * list. 359 */ 360 if (stop_here || !is_pseudo_opcode(check_lir->opcode)) { 361 prev_inst_list[next_slot++] = check_lir; 362 if (next_slot == MAX_HOIST_DISTANCE) break; 363 } 364 365 /* Found a new place to put the load - move it here */ 366 if (stop_here == true) { 367 DEBUG_OPT(dump_dependent_insn_pair(check_lir, this_lir "HOIST STOP")); 368 break; 369 } 370 } 371 372 /* 373 * Reached the top - use head_lir as the dependent marker as all labels 374 * are barriers. 375 */ 376 if (stop_here == false && next_slot < MAX_HOIST_DISTANCE) { 377 prev_inst_list[next_slot++] = head_lir; 378 } 379 380 /* 381 * At least one independent instruction is found. Scan in the reversed 382 * direction to find a beneficial slot. 383 */ 384 if (next_slot >= 2) { 385 int first_slot = next_slot - 2; 386 int slot; 387 LIR* dep_lir = prev_inst_list[next_slot-1]; 388 /* If there is ld-ld dependency, wait LDLD_DISTANCE cycles */ 389 if (!is_pseudo_opcode(dep_lir->opcode) && 390 (GetTargetInstFlags(dep_lir->opcode) & IS_LOAD)) { 391 first_slot -= LDLD_DISTANCE; 392 } 393 /* 394 * Make sure we check slot >= 0 since first_slot may be negative 395 * when the loop is first entered. 396 */ 397 for (slot = first_slot; slot >= 0; slot--) { 398 LIR* cur_lir = prev_inst_list[slot]; 399 LIR* prev_lir = prev_inst_list[slot+1]; 400 401 /* Check the highest instruction */ 402 if (prev_lir->def_mask == ENCODE_ALL) { 403 /* 404 * If the first instruction is a load, don't hoist anything 405 * above it since it is unlikely to be beneficial. 406 */ 407 if (GetTargetInstFlags(cur_lir->opcode) & IS_LOAD) continue; 408 /* 409 * If the remaining number of slots is less than LD_LATENCY, 410 * insert the hoisted load here. 411 */ 412 if (slot < LD_LATENCY) break; 413 } 414 415 // Don't look across a barrier label 416 if ((prev_lir->opcode == kPseudoTargetLabel) || 417 (prev_lir->opcode == kPseudoSafepointPC) || 418 (prev_lir->opcode == kPseudoBarrier)) { 419 break; 420 } 421 422 /* 423 * Try to find two instructions with load/use dependency until 424 * the remaining instructions are less than LD_LATENCY. 425 */ 426 bool prev_is_load = is_pseudo_opcode(prev_lir->opcode) ? false : 427 (GetTargetInstFlags(prev_lir->opcode) & IS_LOAD); 428 if (((cur_lir->use_mask & prev_lir->def_mask) && prev_is_load) || (slot < LD_LATENCY)) { 429 break; 430 } 431 } 432 433 /* Found a slot to hoist to */ 434 if (slot >= 0) { 435 LIR* cur_lir = prev_inst_list[slot]; 436 LIR* new_load_lir = 437 static_cast<LIR*>(arena_->NewMem(sizeof(LIR), true, ArenaAllocator::kAllocLIR)); 438 *new_load_lir = *this_lir; 439 /* 440 * Insertion is guaranteed to succeed since check_lir 441 * is never the first LIR on the list 442 */ 443 InsertLIRBefore(cur_lir, new_load_lir); 444 this_lir->flags.is_nop = true; 445 } 446 } 447 } 448} 449 450void Mir2Lir::ApplyLocalOptimizations(LIR* head_lir, LIR* tail_lir) 451{ 452 if (!(cu_->disable_opt & (1 << kLoadStoreElimination))) { 453 ApplyLoadStoreElimination(head_lir, tail_lir); 454 } 455 if (!(cu_->disable_opt & (1 << kLoadHoisting))) { 456 ApplyLoadHoisting(head_lir, tail_lir); 457 } 458} 459 460/* 461 * Nop any unconditional branches that go to the next instruction. 462 * Note: new redundant branches may be inserted later, and we'll 463 * use a check in final instruction assembly to nop those out. 464 */ 465void Mir2Lir::RemoveRedundantBranches() 466{ 467 LIR* this_lir; 468 469 for (this_lir = first_lir_insn_; this_lir != last_lir_insn_; this_lir = NEXT_LIR(this_lir)) { 470 471 /* Branch to the next instruction */ 472 if (IsUnconditionalBranch(this_lir)) { 473 LIR* next_lir = this_lir; 474 475 while (true) { 476 next_lir = NEXT_LIR(next_lir); 477 478 /* 479 * Is the branch target the next instruction? 480 */ 481 if (next_lir == this_lir->target) { 482 this_lir->flags.is_nop = true; 483 break; 484 } 485 486 /* 487 * Found real useful stuff between the branch and the target. 488 * Need to explicitly check the last_lir_insn_ here because it 489 * might be the last real instruction. 490 */ 491 if (!is_pseudo_opcode(next_lir->opcode) || 492 (next_lir == last_lir_insn_)) 493 break; 494 } 495 } 496 } 497} 498 499} // namespace art 500