diff options
Diffstat (limited to 'compiler/dex/quick/local_optimizations.cc')
| -rw-r--r-- | compiler/dex/quick/local_optimizations.cc | 499 |
1 files changed, 499 insertions, 0 deletions
diff --git a/compiler/dex/quick/local_optimizations.cc b/compiler/dex/quick/local_optimizations.cc new file mode 100644 index 0000000000..ac654d8f21 --- /dev/null +++ b/compiler/dex/quick/local_optimizations.cc @@ -0,0 +1,499 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "dex/compiler_internals.h" + +namespace art { + +#define DEBUG_OPT(X) + +/* Check RAW, WAR, and RAW dependency on the register operands */ +#define CHECK_REG_DEP(use, def, check) ((def & check->use_mask) || \ + ((use | def) & check->def_mask)) + +/* Scheduler heuristics */ +#define MAX_HOIST_DISTANCE 20 +#define LDLD_DISTANCE 4 +#define LD_LATENCY 2 + +static bool IsDalvikRegisterClobbered(LIR* lir1, LIR* lir2) +{ + int reg1Lo = DECODE_ALIAS_INFO_REG(lir1->alias_info); + int reg1Hi = reg1Lo + DECODE_ALIAS_INFO_WIDE(lir1->alias_info); + int reg2Lo = DECODE_ALIAS_INFO_REG(lir2->alias_info); + int reg2Hi = reg2Lo + DECODE_ALIAS_INFO_WIDE(lir2->alias_info); + + return (reg1Lo == reg2Lo) || (reg1Lo == reg2Hi) || (reg1Hi == reg2Lo); +} + +/* Convert a more expensive instruction (ie load) into a move */ +void Mir2Lir::ConvertMemOpIntoMove(LIR* orig_lir, int dest, int src) +{ + /* Insert a move to replace the load */ + LIR* move_lir; + move_lir = OpRegCopyNoInsert(dest, src); + /* + * Insert the converted instruction after the original since the + * optimization is scannng in the top-down order and the new instruction + * will need to be re-checked (eg the new dest clobbers the src used in + * this_lir). + */ + InsertLIRAfter(orig_lir, move_lir); +} + +/* + * Perform a pass of top-down walk, from the second-last instruction in the + * superblock, to eliminate redundant loads and stores. + * + * An earlier load can eliminate a later load iff + * 1) They are must-aliases + * 2) The native register is not clobbered in between + * 3) The memory location is not written to in between + * + * An earlier store can eliminate a later load iff + * 1) They are must-aliases + * 2) The native register is not clobbered in between + * 3) The memory location is not written to in between + * + * A later store can be eliminated by an earlier store iff + * 1) They are must-aliases + * 2) The memory location is not written to in between + */ +void Mir2Lir::ApplyLoadStoreElimination(LIR* head_lir, LIR* tail_lir) +{ + LIR* this_lir; + + if (head_lir == tail_lir) return; + + for (this_lir = PREV_LIR(tail_lir); this_lir != head_lir; this_lir = PREV_LIR(this_lir)) { + + if (is_pseudo_opcode(this_lir->opcode)) continue; + + int sink_distance = 0; + + uint64_t target_flags = GetTargetInstFlags(this_lir->opcode); + + /* Skip non-interesting instructions */ + if ((this_lir->flags.is_nop == true) || + (target_flags & IS_BRANCH) || + ((target_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) || // Skip wide loads. + ((target_flags & (REG_USE0 | REG_USE1 | REG_USE2)) == + (REG_USE0 | REG_USE1 | REG_USE2)) || // Skip wide stores. + !(target_flags & (IS_LOAD | IS_STORE))) { + continue; + } + + int native_reg_id; + if (cu_->instruction_set == kX86) { + // If x86, location differs depending on whether memory/reg operation. + native_reg_id = (GetTargetInstFlags(this_lir->opcode) & IS_STORE) ? this_lir->operands[2] + : this_lir->operands[0]; + } else { + native_reg_id = this_lir->operands[0]; + } + bool is_this_lir_load = GetTargetInstFlags(this_lir->opcode) & IS_LOAD; + LIR* check_lir; + /* Use the mem mask to determine the rough memory location */ + uint64_t this_mem_mask = (this_lir->use_mask | this_lir->def_mask) & ENCODE_MEM; + + /* + * Currently only eliminate redundant ld/st for constant and Dalvik + * register accesses. + */ + if (!(this_mem_mask & (ENCODE_LITERAL | ENCODE_DALVIK_REG))) continue; + + uint64_t stop_def_reg_mask = this_lir->def_mask & ~ENCODE_MEM; + uint64_t stop_use_reg_mask; + if (cu_->instruction_set == kX86) { + stop_use_reg_mask = (IS_BRANCH | this_lir->use_mask) & ~ENCODE_MEM; + } else { + /* + * Add pc to the resource mask to prevent this instruction + * from sinking past branch instructions. Also take out the memory + * region bits since stop_mask is used to check data/control + * dependencies. + */ + stop_use_reg_mask = (GetPCUseDefEncoding() | this_lir->use_mask) & ~ENCODE_MEM; + } + + for (check_lir = NEXT_LIR(this_lir); check_lir != tail_lir; check_lir = NEXT_LIR(check_lir)) { + + /* + * Skip already dead instructions (whose dataflow information is + * outdated and misleading). + */ + if (check_lir->flags.is_nop || is_pseudo_opcode(check_lir->opcode)) continue; + + uint64_t check_mem_mask = (check_lir->use_mask | check_lir->def_mask) & ENCODE_MEM; + uint64_t alias_condition = this_mem_mask & check_mem_mask; + bool stop_here = false; + + /* + * Potential aliases seen - check the alias relations + */ + uint64_t check_flags = GetTargetInstFlags(check_lir->opcode); + // TUNING: Support instructions with multiple register targets. + if ((check_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) { + stop_here = true; + } else if (check_mem_mask != ENCODE_MEM && alias_condition != 0) { + bool is_check_lir_load = check_flags & IS_LOAD; + if (alias_condition == ENCODE_LITERAL) { + /* + * Should only see literal loads in the instruction + * stream. + */ + DCHECK(!(check_flags & IS_STORE)); + /* Same value && same register type */ + if (check_lir->alias_info == this_lir->alias_info && + SameRegType(check_lir->operands[0], native_reg_id)) { + /* + * Different destination register - insert + * a move + */ + if (check_lir->operands[0] != native_reg_id) { + ConvertMemOpIntoMove(check_lir, check_lir->operands[0], native_reg_id); + } + check_lir->flags.is_nop = true; + } + } else if (alias_condition == ENCODE_DALVIK_REG) { + /* Must alias */ + if (check_lir->alias_info == this_lir->alias_info) { + /* Only optimize compatible registers */ + bool reg_compatible = SameRegType(check_lir->operands[0], native_reg_id); + if ((is_this_lir_load && is_check_lir_load) || + (!is_this_lir_load && is_check_lir_load)) { + /* RAR or RAW */ + if (reg_compatible) { + /* + * Different destination register - + * insert a move + */ + if (check_lir->operands[0] != + native_reg_id) { + ConvertMemOpIntoMove(check_lir, check_lir->operands[0], native_reg_id); + } + check_lir->flags.is_nop = true; + } else { + /* + * Destinaions are of different types - + * something complicated going on so + * stop looking now. + */ + stop_here = true; + } + } else if (is_this_lir_load && !is_check_lir_load) { + /* WAR - register value is killed */ + stop_here = true; + } else if (!is_this_lir_load && !is_check_lir_load) { + /* WAW - nuke the earlier store */ + this_lir->flags.is_nop = true; + stop_here = true; + } + /* Partial overlap */ + } else if (IsDalvikRegisterClobbered(this_lir, check_lir)) { + /* + * It is actually ok to continue if check_lir + * is a read. But it is hard to make a test + * case for this so we just stop here to be + * conservative. + */ + stop_here = true; + } + } + /* Memory content may be updated. Stop looking now. */ + if (stop_here) { + break; + /* The check_lir has been transformed - check the next one */ + } else if (check_lir->flags.is_nop) { + continue; + } + } + + + /* + * this and check LIRs have no memory dependency. Now check if + * their register operands have any RAW, WAR, and WAW + * dependencies. If so, stop looking. + */ + if (stop_here == false) { + stop_here = CHECK_REG_DEP(stop_use_reg_mask, stop_def_reg_mask, check_lir); + } + + if (stop_here == true) { + if (cu_->instruction_set == kX86) { + // Prevent stores from being sunk between ops that generate ccodes and + // ops that use them. + uint64_t flags = GetTargetInstFlags(check_lir->opcode); + if (sink_distance > 0 && (flags & IS_BRANCH) && (flags & USES_CCODES)) { + check_lir = PREV_LIR(check_lir); + sink_distance--; + } + } + DEBUG_OPT(dump_dependent_insn_pair(this_lir, check_lir, "REG CLOBBERED")); + /* Only sink store instructions */ + if (sink_distance && !is_this_lir_load) { + LIR* new_store_lir = + static_cast<LIR*>(arena_->NewMem(sizeof(LIR), true, ArenaAllocator::kAllocLIR)); + *new_store_lir = *this_lir; + /* + * Stop point found - insert *before* the check_lir + * since the instruction list is scanned in the + * top-down order. + */ + InsertLIRBefore(check_lir, new_store_lir); + this_lir->flags.is_nop = true; + } + break; + } else if (!check_lir->flags.is_nop) { + sink_distance++; + } + } + } +} + +/* + * Perform a pass of bottom-up walk, from the second instruction in the + * superblock, to try to hoist loads to earlier slots. + */ +void Mir2Lir::ApplyLoadHoisting(LIR* head_lir, LIR* tail_lir) +{ + LIR* this_lir, *check_lir; + /* + * Store the list of independent instructions that can be hoisted past. + * Will decide the best place to insert later. + */ + LIR* prev_inst_list[MAX_HOIST_DISTANCE]; + + /* Empty block */ + if (head_lir == tail_lir) return; + + /* Start from the second instruction */ + for (this_lir = NEXT_LIR(head_lir); this_lir != tail_lir; this_lir = NEXT_LIR(this_lir)) { + + if (is_pseudo_opcode(this_lir->opcode)) continue; + + uint64_t target_flags = GetTargetInstFlags(this_lir->opcode); + /* Skip non-interesting instructions */ + if ((this_lir->flags.is_nop == true) || + ((target_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) || + !(target_flags & IS_LOAD)) { + continue; + } + + uint64_t stop_use_all_mask = this_lir->use_mask; + + if (cu_->instruction_set != kX86) { + /* + * Branches for null/range checks are marked with the true resource + * bits, and loads to Dalvik registers, constant pools, and non-alias + * locations are safe to be hoisted. So only mark the heap references + * conservatively here. + */ + if (stop_use_all_mask & ENCODE_HEAP_REF) { + stop_use_all_mask |= GetPCUseDefEncoding(); + } + } + + /* Similar as above, but just check for pure register dependency */ + uint64_t stop_use_reg_mask = stop_use_all_mask & ~ENCODE_MEM; + uint64_t stop_def_reg_mask = this_lir->def_mask & ~ENCODE_MEM; + + int next_slot = 0; + bool stop_here = false; + + /* Try to hoist the load to a good spot */ + for (check_lir = PREV_LIR(this_lir); check_lir != head_lir; check_lir = PREV_LIR(check_lir)) { + + /* + * Skip already dead instructions (whose dataflow information is + * outdated and misleading). + */ + if (check_lir->flags.is_nop) continue; + + uint64_t check_mem_mask = check_lir->def_mask & ENCODE_MEM; + uint64_t alias_condition = stop_use_all_mask & check_mem_mask; + stop_here = false; + + /* Potential WAR alias seen - check the exact relation */ + if (check_mem_mask != ENCODE_MEM && alias_condition != 0) { + /* We can fully disambiguate Dalvik references */ + if (alias_condition == ENCODE_DALVIK_REG) { + /* Must alias or partually overlap */ + if ((check_lir->alias_info == this_lir->alias_info) || + IsDalvikRegisterClobbered(this_lir, check_lir)) { + stop_here = true; + } + /* Conservatively treat all heap refs as may-alias */ + } else { + DCHECK_EQ(alias_condition, ENCODE_HEAP_REF); + stop_here = true; + } + /* Memory content may be updated. Stop looking now. */ + if (stop_here) { + prev_inst_list[next_slot++] = check_lir; + break; + } + } + + if (stop_here == false) { + stop_here = CHECK_REG_DEP(stop_use_reg_mask, stop_def_reg_mask, + check_lir); + } + + /* + * Store the dependent or non-pseudo/indepedent instruction to the + * list. + */ + if (stop_here || !is_pseudo_opcode(check_lir->opcode)) { + prev_inst_list[next_slot++] = check_lir; + if (next_slot == MAX_HOIST_DISTANCE) break; + } + + /* Found a new place to put the load - move it here */ + if (stop_here == true) { + DEBUG_OPT(dump_dependent_insn_pair(check_lir, this_lir "HOIST STOP")); + break; + } + } + + /* + * Reached the top - use head_lir as the dependent marker as all labels + * are barriers. + */ + if (stop_here == false && next_slot < MAX_HOIST_DISTANCE) { + prev_inst_list[next_slot++] = head_lir; + } + + /* + * At least one independent instruction is found. Scan in the reversed + * direction to find a beneficial slot. + */ + if (next_slot >= 2) { + int first_slot = next_slot - 2; + int slot; + LIR* dep_lir = prev_inst_list[next_slot-1]; + /* If there is ld-ld dependency, wait LDLD_DISTANCE cycles */ + if (!is_pseudo_opcode(dep_lir->opcode) && + (GetTargetInstFlags(dep_lir->opcode) & IS_LOAD)) { + first_slot -= LDLD_DISTANCE; + } + /* + * Make sure we check slot >= 0 since first_slot may be negative + * when the loop is first entered. + */ + for (slot = first_slot; slot >= 0; slot--) { + LIR* cur_lir = prev_inst_list[slot]; + LIR* prev_lir = prev_inst_list[slot+1]; + + /* Check the highest instruction */ + if (prev_lir->def_mask == ENCODE_ALL) { + /* + * If the first instruction is a load, don't hoist anything + * above it since it is unlikely to be beneficial. + */ + if (GetTargetInstFlags(cur_lir->opcode) & IS_LOAD) continue; + /* + * If the remaining number of slots is less than LD_LATENCY, + * insert the hoisted load here. + */ + if (slot < LD_LATENCY) break; + } + + // Don't look across a barrier label + if ((prev_lir->opcode == kPseudoTargetLabel) || + (prev_lir->opcode == kPseudoSafepointPC) || + (prev_lir->opcode == kPseudoBarrier)) { + break; + } + + /* + * Try to find two instructions with load/use dependency until + * the remaining instructions are less than LD_LATENCY. + */ + bool prev_is_load = is_pseudo_opcode(prev_lir->opcode) ? false : + (GetTargetInstFlags(prev_lir->opcode) & IS_LOAD); + if (((cur_lir->use_mask & prev_lir->def_mask) && prev_is_load) || (slot < LD_LATENCY)) { + break; + } + } + + /* Found a slot to hoist to */ + if (slot >= 0) { + LIR* cur_lir = prev_inst_list[slot]; + LIR* new_load_lir = + static_cast<LIR*>(arena_->NewMem(sizeof(LIR), true, ArenaAllocator::kAllocLIR)); + *new_load_lir = *this_lir; + /* + * Insertion is guaranteed to succeed since check_lir + * is never the first LIR on the list + */ + InsertLIRBefore(cur_lir, new_load_lir); + this_lir->flags.is_nop = true; + } + } + } +} + +void Mir2Lir::ApplyLocalOptimizations(LIR* head_lir, LIR* tail_lir) +{ + if (!(cu_->disable_opt & (1 << kLoadStoreElimination))) { + ApplyLoadStoreElimination(head_lir, tail_lir); + } + if (!(cu_->disable_opt & (1 << kLoadHoisting))) { + ApplyLoadHoisting(head_lir, tail_lir); + } +} + +/* + * Nop any unconditional branches that go to the next instruction. + * Note: new redundant branches may be inserted later, and we'll + * use a check in final instruction assembly to nop those out. + */ +void Mir2Lir::RemoveRedundantBranches() +{ + LIR* this_lir; + + for (this_lir = first_lir_insn_; this_lir != last_lir_insn_; this_lir = NEXT_LIR(this_lir)) { + + /* Branch to the next instruction */ + if (IsUnconditionalBranch(this_lir)) { + LIR* next_lir = this_lir; + + while (true) { + next_lir = NEXT_LIR(next_lir); + + /* + * Is the branch target the next instruction? + */ + if (next_lir == this_lir->target) { + this_lir->flags.is_nop = true; + break; + } + + /* + * Found real useful stuff between the branch and the target. + * Need to explicitly check the last_lir_insn_ here because it + * might be the last real instruction. + */ + if (!is_pseudo_opcode(next_lir->opcode) || + (next_lir == last_lir_insn_)) + break; + } + } + } +} + +} // namespace art |