diff options
Diffstat (limited to 'src/compiler/dex/quick/local_optimizations.cc')
| -rw-r--r-- | src/compiler/dex/quick/local_optimizations.cc | 499 |
1 files changed, 0 insertions, 499 deletions
diff --git a/src/compiler/dex/quick/local_optimizations.cc b/src/compiler/dex/quick/local_optimizations.cc deleted file mode 100644 index 1cafce4e0a..0000000000 --- a/src/compiler/dex/quick/local_optimizations.cc +++ /dev/null @@ -1,499 +0,0 @@ -/* - * 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 "compiler/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 |