diff options
Diffstat (limited to 'compiler/dex/quick/local_optimizations.cc')
| -rw-r--r-- | compiler/dex/quick/local_optimizations.cc | 518 |
1 files changed, 0 insertions, 518 deletions
diff --git a/compiler/dex/quick/local_optimizations.cc b/compiler/dex/quick/local_optimizations.cc deleted file mode 100644 index 6cdf56773e..0000000000 --- a/compiler/dex/quick/local_optimizations.cc +++ /dev/null @@ -1,518 +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 "dex/quick/mir_to_lir-inl.h" - -#include "base/logging.h" - -namespace art { - -#define DEBUG_OPT(X) - -#define LOAD_STORE_CHECK_REG_DEP(mask, check) (mask.Intersects(*check->u.m.def_mask)) - -/* Check RAW, WAR, and RAW dependency on the register operands */ -#define CHECK_REG_DEP(use, def, check) (def.Intersects(*check->u.m.use_mask)) || \ - (use.Union(def).Intersects(*check->u.m.def_mask)) - -/* Load Store Elimination filter: - * - Wide Load/Store - * - Exclusive Load/Store - * - Quad operand Load/Store - * - List Load/Store - * - IT blocks - * - Branch - * - Dmb - */ -#define LOAD_STORE_FILTER(flags) ((flags & (IS_QUAD_OP|IS_STORE)) == (IS_QUAD_OP|IS_STORE) || \ - (flags & (IS_QUAD_OP|IS_LOAD)) == (IS_QUAD_OP|IS_LOAD) || \ - (flags & REG_USE012) == REG_USE012 || \ - (flags & REG_DEF01) == REG_DEF01 || \ - (flags & REG_DEF_LIST0) || \ - (flags & REG_DEF_LIST1) || \ - (flags & REG_USE_LIST0) || \ - (flags & REG_USE_LIST1) || \ - (flags & REG_DEF_FPCS_LIST0) || \ - (flags & REG_DEF_FPCS_LIST2) || \ - (flags & REG_USE_FPCS_LIST0) || \ - (flags & REG_USE_FPCS_LIST2) || \ - (flags & IS_VOLATILE) || \ - (flags & IS_BRANCH) || \ - (flags & IS_IT)) - -/* 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->flags.alias_info); - int reg1Hi = reg1Lo + DECODE_ALIAS_INFO_WIDE(lir1->flags.alias_info); - int reg2Lo = DECODE_ALIAS_INFO_REG(lir2->flags.alias_info); - int reg2Hi = reg2Lo + DECODE_ALIAS_INFO_WIDE(lir2->flags.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, RegStorage dest, RegStorage src) { - /* Insert a move to replace the load */ - LIR* move_lir; - move_lir = OpRegCopyNoInsert(dest, src); - move_lir->dalvik_offset = orig_lir->dalvik_offset; - /* - * 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); -} - -void Mir2Lir::DumpDependentInsnPair(LIR* check_lir, LIR* this_lir, const char* type) { - LOG(INFO) << type; - LOG(INFO) << "Check LIR:"; - DumpLIRInsn(check_lir, 0); - LOG(INFO) << "This LIR:"; - DumpLIRInsn(this_lir, 0); -} - -inline void Mir2Lir::EliminateLoad(LIR* lir, int reg_id) { - DCHECK(RegStorage::SameRegType(lir->operands[0], reg_id)); - RegStorage dest_reg, src_reg; - - /* Same Register - Nop */ - if (lir->operands[0] == reg_id) { - NopLIR(lir); - return; - } - - /* different Regsister - Move + Nop */ - switch (reg_id & RegStorage::kShapeTypeMask) { - case RegStorage::k32BitSolo | RegStorage::kCoreRegister: - dest_reg = RegStorage::Solo32(lir->operands[0]); - src_reg = RegStorage::Solo32(reg_id); - break; - case RegStorage::k64BitSolo | RegStorage::kCoreRegister: - dest_reg = RegStorage::Solo64(lir->operands[0]); - src_reg = RegStorage::Solo64(reg_id); - break; - case RegStorage::k32BitSolo | RegStorage::kFloatingPoint: - dest_reg = RegStorage::FloatSolo32(lir->operands[0]); - src_reg = RegStorage::FloatSolo32(reg_id); - break; - case RegStorage::k64BitSolo | RegStorage::kFloatingPoint: - dest_reg = RegStorage::FloatSolo64(lir->operands[0]); - src_reg = RegStorage::FloatSolo64(reg_id); - break; - default: - LOG(INFO) << "Load Store: Unsuported register type!"; - return; - } - ConvertMemOpIntoMove(lir, dest_reg, src_reg); - NopLIR(lir); - return; -} - -/* - * Perform a pass of top-down walk, from the first to the 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 - * - * An earlier store can eliminate a later 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, *check_lir; - std::vector<int> alias_list; - - if (head_lir == tail_lir) { - return; - } - - for (this_lir = head_lir; this_lir != tail_lir; this_lir = NEXT_LIR(this_lir)) { - if (this_lir->flags.is_nop || IsPseudoLirOp(this_lir->opcode)) { - continue; - } - - uint64_t target_flags = GetTargetInstFlags(this_lir->opcode); - /* Target LIR - skip if instr is: - * - NOP - * - Branch - * - Load and store - * - Wide load - * - Wide store - * - Exclusive load/store - */ - if (LOAD_STORE_FILTER(target_flags) || - ((target_flags & (IS_LOAD | IS_STORE)) == (IS_LOAD | IS_STORE)) || - !(target_flags & (IS_LOAD | IS_STORE))) { - continue; - } - int native_reg_id = this_lir->operands[0]; - int dest_reg_id = this_lir->operands[1]; - bool is_this_lir_load = target_flags & IS_LOAD; - ResourceMask this_mem_mask = kEncodeMem.Intersection(this_lir->u.m.use_mask->Union( - *this_lir->u.m.def_mask)); - - /* Memory region */ - if (!this_mem_mask.Intersects(kEncodeLiteral.Union(kEncodeDalvikReg)) && - (!this_mem_mask.Intersects(kEncodeLiteral.Union(kEncodeHeapRef)))) { - continue; - } - - /* Does not redefine the address */ - if (this_lir->u.m.def_mask->Intersects(*this_lir->u.m.use_mask)) { - continue; - } - - ResourceMask stop_def_reg_mask = this_lir->u.m.def_mask->Without(kEncodeMem); - ResourceMask stop_use_reg_mask = this_lir->u.m.use_mask->Without(kEncodeMem); - - /* The ARM backend can load/store PC */ - ResourceMask uses_pc = GetPCUseDefEncoding(); - if (uses_pc.Intersects(this_lir->u.m.use_mask->Union(*this_lir->u.m.def_mask))) { - continue; - } - - /* Initialize alias list */ - alias_list.clear(); - ResourceMask alias_reg_list_mask = kEncodeNone; - if (!this_mem_mask.Intersects(kEncodeMem) && !this_mem_mask.Intersects(kEncodeLiteral)) { - alias_list.push_back(dest_reg_id); - SetupRegMask(&alias_reg_list_mask, dest_reg_id); - } - - /* Scan through the BB for posible elimination candidates */ - for (check_lir = NEXT_LIR(this_lir); check_lir != tail_lir; check_lir = NEXT_LIR(check_lir)) { - if (check_lir->flags.is_nop || IsPseudoLirOp(check_lir->opcode)) { - continue; - } - - if (uses_pc.Intersects(check_lir->u.m.use_mask->Union(*check_lir->u.m.def_mask))) { - break; - } - - ResourceMask check_mem_mask = kEncodeMem.Intersection(check_lir->u.m.use_mask->Union( - *check_lir->u.m.def_mask)); - ResourceMask alias_mem_mask = this_mem_mask.Intersection(check_mem_mask); - uint64_t check_flags = GetTargetInstFlags(check_lir->opcode); - bool stop_here = false; - bool pass_over = false; - - /* Check LIR - skip if instr is: - * - Wide Load - * - Wide Store - * - Branch - * - Dmb - * - Exclusive load/store - * - IT blocks - * - Quad loads - */ - if (LOAD_STORE_FILTER(check_flags)) { - stop_here = true; - /* Possible alias or result of earlier pass */ - } else if (check_flags & IS_MOVE) { - for (auto ® : alias_list) { - if (RegStorage::RegNum(check_lir->operands[1]) == RegStorage::RegNum(reg)) { - pass_over = true; - alias_list.push_back(check_lir->operands[0]); - SetupRegMask(&alias_reg_list_mask, check_lir->operands[0]); - } - } - /* Memory regions */ - } else if (!alias_mem_mask.Equals(kEncodeNone)) { - DCHECK((check_flags & IS_LOAD) || (check_flags & IS_STORE)); - bool is_check_lir_load = check_flags & IS_LOAD; - bool reg_compatible = RegStorage::SameRegType(check_lir->operands[0], native_reg_id); - - if (!alias_mem_mask.Intersects(kEncodeMem) && alias_mem_mask.Equals(kEncodeLiteral)) { - DCHECK(check_flags & IS_LOAD); - /* Same value && same register type */ - if (reg_compatible && (this_lir->target == check_lir->target)) { - DEBUG_OPT(DumpDependentInsnPair(check_lir, this_lir, "LITERAL")); - EliminateLoad(check_lir, native_reg_id); - } - } else if (((alias_mem_mask.Equals(kEncodeDalvikReg)) || (alias_mem_mask.Equals(kEncodeHeapRef))) && - alias_reg_list_mask.Intersects((check_lir->u.m.use_mask)->Without(kEncodeMem))) { - bool same_offset = (GetInstructionOffset(this_lir) == GetInstructionOffset(check_lir)); - if (same_offset && !is_check_lir_load) { - if (check_lir->operands[0] != native_reg_id) { - DEBUG_OPT(DumpDependentInsnPair(check_lir, this_lir, "STORE STOP")); - stop_here = true; - break; - } - } - - if (reg_compatible && same_offset && - ((is_this_lir_load && is_check_lir_load) /* LDR - LDR */ || - (!is_this_lir_load && is_check_lir_load) /* STR - LDR */ || - (!is_this_lir_load && !is_check_lir_load) /* STR - STR */)) { - DEBUG_OPT(DumpDependentInsnPair(check_lir, this_lir, "LOAD STORE")); - EliminateLoad(check_lir, native_reg_id); - } - } else { - /* Unsupported memory region */ - } - } - - if (pass_over) { - continue; - } - - if (stop_here == false) { - bool stop_alias = LOAD_STORE_CHECK_REG_DEP(alias_reg_list_mask, check_lir); - if (stop_alias) { - /* Scan through alias list and if alias remove from alias list. */ - for (auto ® : alias_list) { - stop_alias = false; - ResourceMask alias_reg_mask = kEncodeNone; - SetupRegMask(&alias_reg_mask, reg); - stop_alias = LOAD_STORE_CHECK_REG_DEP(alias_reg_mask, check_lir); - if (stop_alias) { - ClearRegMask(&alias_reg_list_mask, reg); - alias_list.erase(std::remove(alias_list.begin(), alias_list.end(), - reg), alias_list.end()); - } - } - } - ResourceMask stop_search_mask = stop_def_reg_mask.Union(stop_use_reg_mask); - stop_search_mask = stop_search_mask.Union(alias_reg_list_mask); - stop_here = LOAD_STORE_CHECK_REG_DEP(stop_search_mask, check_lir); - if (stop_here) { - break; - } - } else { - break; - } - } - } -} - -/* - * 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 (IsPseudoLirOp(this_lir->opcode)) { - continue; - } - - uint64_t target_flags = GetTargetInstFlags(this_lir->opcode); - /* Skip non-interesting instructions */ - if (!(target_flags & IS_LOAD) || - (this_lir->flags.is_nop == true) || - ((target_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) || - ((target_flags & (IS_STORE | IS_LOAD)) == (IS_STORE | IS_LOAD))) { - continue; - } - - ResourceMask stop_use_all_mask = *this_lir->u.m.use_mask; - - /* - * 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. - * - * Note: on x86(-64) and Arm64 this will add kEncodeNone. - * TODO: Sanity check. LoadStoreElimination uses kBranchBit to fake a PC. - */ - if (stop_use_all_mask.HasBit(ResourceMask::kHeapRef)) { - stop_use_all_mask.SetBits(GetPCUseDefEncoding()); - } - - /* Similar as above, but just check for pure register dependency */ - ResourceMask stop_use_reg_mask = stop_use_all_mask.Without(kEncodeMem); - ResourceMask stop_def_reg_mask = this_lir->u.m.def_mask->Without(kEncodeMem); - - 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; - } - - ResourceMask check_mem_mask = check_lir->u.m.def_mask->Intersection(kEncodeMem); - ResourceMask alias_condition = stop_use_all_mask.Intersection(check_mem_mask); - stop_here = false; - - /* Potential WAR alias seen - check the exact relation */ - if (!check_mem_mask.Equals(kEncodeMem) && !alias_condition.Equals(kEncodeNone)) { - /* We can fully disambiguate Dalvik references */ - if (alias_condition.Equals(kEncodeDalvikReg)) { - /* Must alias or partially overlap */ - if ((check_lir->flags.alias_info == this_lir->flags.alias_info) || - IsDalvikRegisterClobbered(this_lir, check_lir)) { - stop_here = true; - } - /* Conservatively treat all heap refs as may-alias */ - } else { - DCHECK(alias_condition.Equals(kEncodeHeapRef)); - 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 || !IsPseudoLirOp(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(DumpDependentInsnPair(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 (!IsPseudoLirOp(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->u.m.def_mask->Equals(kEncodeAll)) { - /* - * 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 = IsPseudoLirOp(prev_lir->opcode) ? false : - (GetTargetInstFlags(prev_lir->opcode) & IS_LOAD); - if ((prev_is_load && (cur_lir->u.m.use_mask->Intersects(*prev_lir->u.m.def_mask))) || - (slot < LD_LATENCY)) { - break; - } - } - - /* Found a slot to hoist to */ - if (slot >= 0) { - LIR* cur_lir = prev_inst_list[slot]; - LIR* prev_lir = PREV_LIR(this_lir); - UnlinkLIR(this_lir); - /* - * Insertion is guaranteed to succeed since check_lir - * is never the first LIR on the list - */ - InsertLIRBefore(cur_lir, this_lir); - this_lir = prev_lir; // Continue the loop with the next LIR. - } - } - } -} - -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); - } -} - -} // namespace art |