| /* |
| * 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 |
