diff options
39 files changed, 1143 insertions, 210 deletions
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk index 429c523249..d4e2cbbf24 100644 --- a/build/Android.gtest.mk +++ b/build/Android.gtest.mk @@ -78,6 +78,7 @@ COMPILER_GTEST_COMMON_SRC_FILES := \ compiler/oat_test.cc \ compiler/optimizing/codegen_test.cc \ compiler/optimizing/dominator_test.cc \ + compiler/optimizing/liveness_test.cc \ compiler/optimizing/pretty_printer_test.cc \ compiler/optimizing/ssa_test.cc \ compiler/output_stream_test.cc \ diff --git a/compiler/Android.mk b/compiler/Android.mk index e3201e7f8b..a993251fcf 100644 --- a/compiler/Android.mk +++ b/compiler/Android.mk @@ -79,6 +79,7 @@ LIBART_COMPILER_SRC_FILES := \ optimizing/nodes.cc \ optimizing/optimizing_compiler.cc \ optimizing/ssa_builder.cc \ + optimizing/ssa_liveness_analysis.cc \ trampolines/trampoline_compiler.cc \ utils/arena_allocator.cc \ utils/arena_bit_vector.cc \ diff --git a/compiler/dex/mir_graph.cc b/compiler/dex/mir_graph.cc index 30d0bc3d0a..ca90a833cc 100644 --- a/compiler/dex/mir_graph.cc +++ b/compiler/dex/mir_graph.cc @@ -1257,4 +1257,55 @@ void MIRGraph::InitializeSSATransformation() { DoDFSPreOrderSSARename(GetEntryBlock()); } +ChildBlockIterator::ChildBlockIterator(BasicBlock* bb, MIRGraph* mir_graph) + : basic_block_(bb), mir_graph_(mir_graph), visited_fallthrough_(false), + visited_taken_(false), have_successors_(false) { + // Check if we actually do have successors. + if (basic_block_ != 0 && basic_block_->successor_block_list_type != kNotUsed) { + have_successors_ = true; + successor_iter_.Reset(basic_block_->successor_blocks); + } +} + +BasicBlock* ChildBlockIterator::Next() { + // We check if we have a basic block. If we don't we cannot get next child. + if (basic_block_ == nullptr) { + return nullptr; + } + + // If we haven't visited fallthrough, return that. + if (visited_fallthrough_ == false) { + visited_fallthrough_ = true; + + BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->fall_through); + if (result != nullptr) { + return result; + } + } + + // If we haven't visited taken, return that. + if (visited_taken_ == false) { + visited_taken_ = true; + + BasicBlock* result = mir_graph_->GetBasicBlock(basic_block_->taken); + if (result != nullptr) { + return result; + } + } + + // We visited both taken and fallthrough. Now check if we have successors we need to visit. + if (have_successors_ == true) { + // Get information about next successor block. + SuccessorBlockInfo* successor_block_info = successor_iter_.Next(); + + // If we don't have anymore successors, return nullptr. + if (successor_block_info != nullptr) { + return mir_graph_->GetBasicBlock(successor_block_info->block); + } + } + + // We do not have anything. + return nullptr; +} + } // namespace art diff --git a/compiler/dex/mir_graph.h b/compiler/dex/mir_graph.h index c728d84942..85a2d04306 100644 --- a/compiler/dex/mir_graph.h +++ b/compiler/dex/mir_graph.h @@ -341,6 +341,29 @@ struct SuccessorBlockInfo { int key; }; +/** + * @class ChildBlockIterator + * @brief Enable an easy iteration of the children. + */ +class ChildBlockIterator { + public: + /** + * @brief Constructs a child iterator. + * @param bb The basic whose children we need to iterate through. + * @param mir_graph The MIRGraph used to get the basic block during iteration. + */ + ChildBlockIterator(BasicBlock* bb, MIRGraph* mir_graph); + BasicBlock* Next(); + + private: + BasicBlock* basic_block_; + MIRGraph* mir_graph_; + bool visited_fallthrough_; + bool visited_taken_; + bool have_successors_; + GrowableArray<SuccessorBlockInfo*>::Iterator successor_iter_; +}; + /* * Whereas a SSA name describes a definition of a Dalvik vreg, the RegLocation describes * the type of an SSA name (and, can also be used by code generators to record where the diff --git a/compiler/dex/mir_optimization.cc b/compiler/dex/mir_optimization.cc index 5cc994f692..413b4e0f75 100644 --- a/compiler/dex/mir_optimization.cc +++ b/compiler/dex/mir_optimization.cc @@ -735,18 +735,20 @@ bool MIRGraph::EliminateNullChecksAndInferTypes(BasicBlock* bb) { if (pred_bb->block_type == kDalvikByteCode) { // Check to see if predecessor had an explicit null-check. MIR* last_insn = pred_bb->last_mir_insn; - Instruction::Code last_opcode = last_insn->dalvikInsn.opcode; - if (last_opcode == Instruction::IF_EQZ) { - if (pred_bb->fall_through == bb->id) { - // The fall-through of a block following a IF_EQZ, set the vA of the IF_EQZ to show that - // it can't be null. - ssa_regs_to_check->ClearBit(last_insn->ssa_rep->uses[0]); - } - } else if (last_opcode == Instruction::IF_NEZ) { - if (pred_bb->taken == bb->id) { - // The taken block following a IF_NEZ, set the vA of the IF_NEZ to show that it can't be - // null. - ssa_regs_to_check->ClearBit(last_insn->ssa_rep->uses[0]); + if (last_insn != nullptr) { + Instruction::Code last_opcode = last_insn->dalvikInsn.opcode; + if (last_opcode == Instruction::IF_EQZ) { + if (pred_bb->fall_through == bb->id) { + // The fall-through of a block following a IF_EQZ, set the vA of the IF_EQZ to show that + // it can't be null. + ssa_regs_to_check->ClearBit(last_insn->ssa_rep->uses[0]); + } + } else if (last_opcode == Instruction::IF_NEZ) { + if (pred_bb->taken == bb->id) { + // The taken block following a IF_NEZ, set the vA of the IF_NEZ to show that it can't be + // null. + ssa_regs_to_check->ClearBit(last_insn->ssa_rep->uses[0]); + } } } } @@ -895,7 +897,7 @@ bool MIRGraph::EliminateNullChecksAndInferTypes(BasicBlock* bb) { temp_scoped_alloc_.get(), temp_bit_vector_size_, false, kBitMapNullCheck); nce_changed = ssa_regs_to_check->GetHighestBitSet() != -1; bb->data_flow_info->ending_check_v->Copy(ssa_regs_to_check); - } else if (!ssa_regs_to_check->Equal(bb->data_flow_info->ending_check_v)) { + } else if (!ssa_regs_to_check->SameBitsSet(bb->data_flow_info->ending_check_v)) { nce_changed = true; bb->data_flow_info->ending_check_v->Copy(ssa_regs_to_check); } diff --git a/compiler/dex/quick/arm/codegen_arm.h b/compiler/dex/quick/arm/codegen_arm.h index 9d1723a55f..8b4576c56a 100644 --- a/compiler/dex/quick/arm/codegen_arm.h +++ b/compiler/dex/quick/arm/codegen_arm.h @@ -34,7 +34,6 @@ class ArmMir2Lir FINAL : public Mir2Lir { RegStorage LoadHelper(ThreadOffset<4> offset); LIR* LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_dest, OpSize size, int s_reg); - LIR* LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, int s_reg); LIR* LoadBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_dest, int scale, OpSize size); LIR* LoadBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, @@ -42,7 +41,6 @@ class ArmMir2Lir FINAL : public Mir2Lir { LIR* LoadConstantNoClobber(RegStorage r_dest, int value); LIR* LoadConstantWide(RegStorage r_dest, int64_t value); LIR* StoreBaseDisp(RegStorage r_base, int displacement, RegStorage r_src, OpSize size); - LIR* StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src); LIR* StoreBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_src, int scale, OpSize size); LIR* StoreBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, diff --git a/compiler/dex/quick/arm/int_arm.cc b/compiler/dex/quick/arm/int_arm.cc index 8391c0366b..8dd31d18ee 100644 --- a/compiler/dex/quick/arm/int_arm.cc +++ b/compiler/dex/quick/arm/int_arm.cc @@ -1170,19 +1170,14 @@ void ArmMir2Lir::GenArrayGet(int opt_flags, OpSize size, RegLocation rl_array, } FreeTemp(reg_len); } + LoadBaseDisp(reg_ptr, data_offset, rl_result.reg, size, INVALID_SREG); + MarkPossibleNullPointerException(opt_flags); + if (!constant_index) { + FreeTemp(reg_ptr); + } if (rl_dest.wide) { - LoadBaseDispWide(reg_ptr, data_offset, rl_result.reg, INVALID_SREG); - MarkPossibleNullPointerException(opt_flags); - if (!constant_index) { - FreeTemp(reg_ptr); - } StoreValueWide(rl_dest, rl_result); } else { - LoadBaseDisp(reg_ptr, data_offset, rl_result.reg, size, INVALID_SREG); - MarkPossibleNullPointerException(opt_flags); - if (!constant_index) { - FreeTemp(reg_ptr); - } StoreValue(rl_dest, rl_result); } } else { @@ -1275,11 +1270,7 @@ void ArmMir2Lir::GenArrayPut(int opt_flags, OpSize size, RegLocation rl_array, FreeTemp(reg_len); } - if (rl_src.wide) { - StoreBaseDispWide(reg_ptr, data_offset, rl_src.reg); - } else { - StoreBaseDisp(reg_ptr, data_offset, rl_src.reg, size); - } + StoreBaseDisp(reg_ptr, data_offset, rl_src.reg, size); MarkPossibleNullPointerException(opt_flags); } else { /* reg_ptr -> array data */ diff --git a/compiler/dex/quick/arm/utility_arm.cc b/compiler/dex/quick/arm/utility_arm.cc index 08acef7873..b7b9093b1d 100644 --- a/compiler/dex/quick/arm/utility_arm.cc +++ b/compiler/dex/quick/arm/utility_arm.cc @@ -957,7 +957,6 @@ LIR* ArmMir2Lir::LoadBaseDispBody(RegStorage r_base, int displacement, RegStorag LIR* ArmMir2Lir::LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_dest, OpSize size, int s_reg) { - DCHECK(!((size == k64) || (size == kDouble))); // TODO: base this on target. if (size == kWord) { size = k32; @@ -965,11 +964,6 @@ LIR* ArmMir2Lir::LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_ return LoadBaseDispBody(r_base, displacement, r_dest, size, s_reg); } -LIR* ArmMir2Lir::LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, - int s_reg) { - return LoadBaseDispBody(r_base, displacement, r_dest, k64, s_reg); -} - LIR* ArmMir2Lir::StoreBaseDispBody(RegStorage r_base, int displacement, RegStorage r_src, OpSize size) { @@ -1091,14 +1085,9 @@ LIR* ArmMir2Lir::StoreBaseDisp(RegStorage r_base, int displacement, RegStorage r if (size == kWord) { size = k32; } - DCHECK(!((size == k64) || (size == kDouble))); return StoreBaseDispBody(r_base, displacement, r_src, size); } -LIR* ArmMir2Lir::StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src) { - return StoreBaseDispBody(r_base, displacement, r_src, k64); -} - LIR* ArmMir2Lir::OpFpRegCopy(RegStorage r_dest, RegStorage r_src) { int opcode; DCHECK_EQ(r_dest.IsDouble(), r_src.IsDouble()); diff --git a/compiler/dex/quick/arm64/codegen_arm64.h b/compiler/dex/quick/arm64/codegen_arm64.h index 94c2563ae3..4e784c6b38 100644 --- a/compiler/dex/quick/arm64/codegen_arm64.h +++ b/compiler/dex/quick/arm64/codegen_arm64.h @@ -34,7 +34,6 @@ class Arm64Mir2Lir FINAL : public Mir2Lir { RegStorage LoadHelper(ThreadOffset<4> offset); LIR* LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_dest, OpSize size, int s_reg); - LIR* LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, int s_reg); LIR* LoadBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_dest, int scale, OpSize size); LIR* LoadBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, @@ -42,7 +41,6 @@ class Arm64Mir2Lir FINAL : public Mir2Lir { LIR* LoadConstantNoClobber(RegStorage r_dest, int value); LIR* LoadConstantWide(RegStorage r_dest, int64_t value); LIR* StoreBaseDisp(RegStorage r_base, int displacement, RegStorage r_src, OpSize size); - LIR* StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src); LIR* StoreBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_src, int scale, OpSize size); LIR* StoreBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, diff --git a/compiler/dex/quick/arm64/int_arm64.cc b/compiler/dex/quick/arm64/int_arm64.cc index 11fb76571f..c5a3ab6b39 100644 --- a/compiler/dex/quick/arm64/int_arm64.cc +++ b/compiler/dex/quick/arm64/int_arm64.cc @@ -1170,19 +1170,14 @@ void Arm64Mir2Lir::GenArrayGet(int opt_flags, OpSize size, RegLocation rl_array, } FreeTemp(reg_len); } + LoadBaseDisp(reg_ptr, data_offset, rl_result.reg, size, INVALID_SREG); + MarkPossibleNullPointerException(opt_flags); + if (!constant_index) { + FreeTemp(reg_ptr); + } if (rl_dest.wide) { - LoadBaseDispWide(reg_ptr, data_offset, rl_result.reg, INVALID_SREG); - MarkPossibleNullPointerException(opt_flags); - if (!constant_index) { - FreeTemp(reg_ptr); - } StoreValueWide(rl_dest, rl_result); } else { - LoadBaseDisp(reg_ptr, data_offset, rl_result.reg, size, INVALID_SREG); - MarkPossibleNullPointerException(opt_flags); - if (!constant_index) { - FreeTemp(reg_ptr); - } StoreValue(rl_dest, rl_result); } } else { @@ -1275,11 +1270,7 @@ void Arm64Mir2Lir::GenArrayPut(int opt_flags, OpSize size, RegLocation rl_array, FreeTemp(reg_len); } - if (rl_src.wide) { - StoreBaseDispWide(reg_ptr, data_offset, rl_src.reg); - } else { - StoreBaseDisp(reg_ptr, data_offset, rl_src.reg, size); - } + StoreBaseDisp(reg_ptr, data_offset, rl_src.reg, size); MarkPossibleNullPointerException(opt_flags); } else { /* reg_ptr -> array data */ diff --git a/compiler/dex/quick/arm64/utility_arm64.cc b/compiler/dex/quick/arm64/utility_arm64.cc index d66b834131..8ff1830050 100644 --- a/compiler/dex/quick/arm64/utility_arm64.cc +++ b/compiler/dex/quick/arm64/utility_arm64.cc @@ -957,7 +957,6 @@ LIR* Arm64Mir2Lir::LoadBaseDispBody(RegStorage r_base, int displacement, RegStor LIR* Arm64Mir2Lir::LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_dest, OpSize size, int s_reg) { - DCHECK(!((size == k64) || (size == kDouble))); // TODO: base this on target. if (size == kWord) { size = k32; @@ -965,11 +964,6 @@ LIR* Arm64Mir2Lir::LoadBaseDisp(RegStorage r_base, int displacement, RegStorage return LoadBaseDispBody(r_base, displacement, r_dest, size, s_reg); } -LIR* Arm64Mir2Lir::LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, - int s_reg) { - return LoadBaseDispBody(r_base, displacement, r_dest, k64, s_reg); -} - LIR* Arm64Mir2Lir::StoreBaseDispBody(RegStorage r_base, int displacement, RegStorage r_src, OpSize size) { @@ -1091,14 +1085,9 @@ LIR* Arm64Mir2Lir::StoreBaseDisp(RegStorage r_base, int displacement, RegStorage if (size == kWord) { size = k32; } - DCHECK(!((size == k64) || (size == kDouble))); return StoreBaseDispBody(r_base, displacement, r_src, size); } -LIR* Arm64Mir2Lir::StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src) { - return StoreBaseDispBody(r_base, displacement, r_src, k64); -} - LIR* Arm64Mir2Lir::OpFpRegCopy(RegStorage r_dest, RegStorage r_src) { int opcode; DCHECK_EQ(r_dest.IsDouble(), r_src.IsDouble()); diff --git a/compiler/dex/quick/gen_common.cc b/compiler/dex/quick/gen_common.cc index 2cd17ccffc..395cff7d61 100644 --- a/compiler/dex/quick/gen_common.cc +++ b/compiler/dex/quick/gen_common.cc @@ -564,13 +564,8 @@ void Mir2Lir::GenSput(MIR* mir, RegLocation rl_src, bool is_long_or_double, // There might have been a store before this volatile one so insert StoreStore barrier. GenMemBarrier(kStoreStore); } - if (is_long_or_double) { - StoreBaseDispWide(r_base, field_info.FieldOffset().Int32Value(), rl_src.reg); - } else if (rl_src.ref) { - StoreRefDisp(r_base, field_info.FieldOffset().Int32Value(), rl_src.reg); - } else { - Store32Disp(r_base, field_info.FieldOffset().Int32Value(), rl_src.reg); - } + OpSize size = LoadStoreOpSize(is_long_or_double, rl_src.ref); + StoreBaseDisp(r_base, field_info.FieldOffset().Int32Value(), rl_src.reg, size); if (field_info.IsVolatile()) { // A load might follow the volatile store so insert a StoreLoad barrier. GenMemBarrier(kStoreLoad); @@ -646,13 +641,8 @@ void Mir2Lir::GenSget(MIR* mir, RegLocation rl_dest, } RegLocation rl_result = EvalLoc(rl_dest, result_reg_kind, true); - if (is_long_or_double) { - LoadBaseDispWide(r_base, field_info.FieldOffset().Int32Value(), rl_result.reg, INVALID_SREG); - } else if (rl_result.ref) { - LoadRefDisp(r_base, field_info.FieldOffset().Int32Value(), rl_result.reg); - } else { - Load32Disp(r_base, field_info.FieldOffset().Int32Value(), rl_result.reg); - } + OpSize size = LoadStoreOpSize(is_long_or_double, rl_result.ref); + LoadBaseDisp(r_base, field_info.FieldOffset().Int32Value(), rl_result.reg, size, INVALID_SREG); FreeTemp(r_base); if (field_info.IsVolatile()) { @@ -714,8 +704,8 @@ void Mir2Lir::GenIGet(MIR* mir, int opt_flags, OpSize size, result_reg_kind = kFPReg; } rl_result = EvalLoc(rl_dest, result_reg_kind, true); - LoadBaseDispWide(rl_obj.reg, field_info.FieldOffset().Int32Value(), rl_result.reg, - rl_obj.s_reg_low); + LoadBaseDisp(rl_obj.reg, field_info.FieldOffset().Int32Value(), rl_result.reg, + size, rl_obj.s_reg_low); MarkPossibleNullPointerException(opt_flags); if (field_info.IsVolatile()) { // Without context sensitive analysis, we must issue the most conservative barriers. @@ -727,7 +717,7 @@ void Mir2Lir::GenIGet(MIR* mir, int opt_flags, OpSize size, RegStorage reg_ptr = AllocTemp(); OpRegRegImm(kOpAdd, reg_ptr, rl_obj.reg, field_info.FieldOffset().Int32Value()); rl_result = EvalLoc(rl_dest, reg_class, true); - LoadBaseDispWide(reg_ptr, 0, rl_result.reg, INVALID_SREG); + LoadBaseDisp(reg_ptr, 0, rl_result.reg, size, INVALID_SREG); MarkPossibleNullPointerException(opt_flags); if (field_info.IsVolatile()) { // Without context sensitive analysis, we must issue the most conservative barriers. @@ -791,7 +781,7 @@ void Mir2Lir::GenIPut(MIR* mir, int opt_flags, OpSize size, // There might have been a store before this volatile one so insert StoreStore barrier. GenMemBarrier(kStoreStore); } - StoreBaseDispWide(reg_ptr, 0, rl_src.reg); + StoreBaseDisp(reg_ptr, 0, rl_src.reg, size); MarkPossibleNullPointerException(opt_flags); if (field_info.IsVolatile()) { // A load might follow the volatile store so insert a StoreLoad barrier. diff --git a/compiler/dex/quick/gen_invoke.cc b/compiler/dex/quick/gen_invoke.cc index 9c1fbe4389..960ac10528 100644 --- a/compiler/dex/quick/gen_invoke.cc +++ b/compiler/dex/quick/gen_invoke.cc @@ -791,7 +791,7 @@ int Mir2Lir::GenDalvikArgsNoRange(CallInfo* info, } int outs_offset = (next_use + 1) * 4; if (rl_arg.wide) { - StoreBaseDispWide(TargetReg(kSp), outs_offset, arg_reg); + StoreBaseDisp(TargetReg(kSp), outs_offset, arg_reg, k64); next_use += 2; } else { Store32Disp(TargetReg(kSp), outs_offset, arg_reg); @@ -859,7 +859,7 @@ int Mir2Lir::GenDalvikArgsRange(CallInfo* info, int call_state, if (loc.wide) { loc = UpdateLocWide(loc); if ((next_arg >= 2) && (loc.location == kLocPhysReg)) { - StoreBaseDispWide(TargetReg(kSp), SRegOffset(loc.s_reg_low), loc.reg); + StoreBaseDisp(TargetReg(kSp), SRegOffset(loc.s_reg_low), loc.reg, k64); } next_arg += 2; } else { @@ -1433,7 +1433,7 @@ bool Mir2Lir::GenInlinedUnsafeGet(CallInfo* info, } else { RegStorage rl_temp_offset = AllocTemp(); OpRegRegReg(kOpAdd, rl_temp_offset, rl_object.reg, rl_offset.reg); - LoadBaseDispWide(rl_temp_offset, 0, rl_result.reg, INVALID_SREG); + LoadBaseDisp(rl_temp_offset, 0, rl_result.reg, k64, INVALID_SREG); FreeTemp(rl_temp_offset); } } else { @@ -1480,7 +1480,7 @@ bool Mir2Lir::GenInlinedUnsafePut(CallInfo* info, bool is_long, } else { RegStorage rl_temp_offset = AllocTemp(); OpRegRegReg(kOpAdd, rl_temp_offset, rl_object.reg, rl_offset.reg); - StoreBaseDispWide(rl_temp_offset, 0, rl_value.reg); + StoreBaseDisp(rl_temp_offset, 0, rl_value.reg, k64); FreeTemp(rl_temp_offset); } } else { diff --git a/compiler/dex/quick/gen_loadstore.cc b/compiler/dex/quick/gen_loadstore.cc index e6911cd391..6fe1e3169b 100644 --- a/compiler/dex/quick/gen_loadstore.cc +++ b/compiler/dex/quick/gen_loadstore.cc @@ -123,7 +123,7 @@ void Mir2Lir::LoadValueDirectWide(RegLocation rl_src, RegStorage r_dest) { } else { DCHECK((rl_src.location == kLocDalvikFrame) || (rl_src.location == kLocCompilerTemp)); - LoadBaseDispWide(TargetReg(kSp), SRegOffset(rl_src.s_reg_low), r_dest, INVALID_SREG); + LoadBaseDisp(TargetReg(kSp), SRegOffset(rl_src.s_reg_low), r_dest, k64, INVALID_SREG); } } @@ -258,7 +258,7 @@ void Mir2Lir::StoreValueWide(RegLocation rl_dest, RegLocation rl_src) { def_start = last_lir_insn_; DCHECK_EQ((mir_graph_->SRegToVReg(rl_dest.s_reg_low)+1), mir_graph_->SRegToVReg(GetSRegHi(rl_dest.s_reg_low))); - StoreBaseDispWide(TargetReg(kSp), SRegOffset(rl_dest.s_reg_low), rl_dest.reg); + StoreBaseDisp(TargetReg(kSp), SRegOffset(rl_dest.s_reg_low), rl_dest.reg, k64); MarkClean(rl_dest); def_end = last_lir_insn_; MarkDefWide(rl_dest, def_start, def_end); @@ -320,7 +320,7 @@ void Mir2Lir::StoreFinalValueWide(RegLocation rl_dest, RegLocation rl_src) { LIR *def_start = last_lir_insn_; DCHECK_EQ((mir_graph_->SRegToVReg(rl_dest.s_reg_low)+1), mir_graph_->SRegToVReg(GetSRegHi(rl_dest.s_reg_low))); - StoreBaseDispWide(TargetReg(kSp), SRegOffset(rl_dest.s_reg_low), rl_dest.reg); + StoreBaseDisp(TargetReg(kSp), SRegOffset(rl_dest.s_reg_low), rl_dest.reg, k64); MarkClean(rl_dest); LIR *def_end = last_lir_insn_; MarkDefWide(rl_dest, def_start, def_end); diff --git a/compiler/dex/quick/mips/codegen_mips.h b/compiler/dex/quick/mips/codegen_mips.h index 7a8376e8b1..cdabf8ebc1 100644 --- a/compiler/dex/quick/mips/codegen_mips.h +++ b/compiler/dex/quick/mips/codegen_mips.h @@ -35,7 +35,6 @@ class MipsMir2Lir FINAL : public Mir2Lir { LIR* LoadBaseDisp(int r_base, int displacement, int r_dest, OpSize size, int s_reg); LIR* LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_dest, OpSize size, int s_reg); - LIR* LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, int s_reg); LIR* LoadBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_dest, int scale, OpSize size); LIR* LoadBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, @@ -43,7 +42,6 @@ class MipsMir2Lir FINAL : public Mir2Lir { LIR* LoadConstantNoClobber(RegStorage r_dest, int value); LIR* LoadConstantWide(RegStorage r_dest, int64_t value); LIR* StoreBaseDisp(RegStorage r_base, int displacement, RegStorage r_src, OpSize size); - LIR* StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src); LIR* StoreBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_src, int scale, OpSize size); LIR* StoreBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, diff --git a/compiler/dex/quick/mips/int_mips.cc b/compiler/dex/quick/mips/int_mips.cc index 1410e14925..fe2e495121 100644 --- a/compiler/dex/quick/mips/int_mips.cc +++ b/compiler/dex/quick/mips/int_mips.cc @@ -511,7 +511,7 @@ void MipsMir2Lir::GenArrayGet(int opt_flags, OpSize size, RegLocation rl_array, GenArrayBoundsCheck(rl_index.reg, reg_len); FreeTemp(reg_len); } - LoadBaseDispWide(reg_ptr, 0, rl_result.reg, INVALID_SREG); + LoadBaseDisp(reg_ptr, 0, rl_result.reg, size, INVALID_SREG); FreeTemp(reg_ptr); StoreValueWide(rl_dest, rl_result); @@ -589,7 +589,7 @@ void MipsMir2Lir::GenArrayPut(int opt_flags, OpSize size, RegLocation rl_array, FreeTemp(reg_len); } - StoreBaseDispWide(reg_ptr, 0, rl_src.reg); + StoreBaseDisp(reg_ptr, 0, rl_src.reg, size); } else { rl_src = LoadValue(rl_src, reg_class); if (needs_range_check) { diff --git a/compiler/dex/quick/mips/utility_mips.cc b/compiler/dex/quick/mips/utility_mips.cc index 50b945a956..9aa929cbf3 100644 --- a/compiler/dex/quick/mips/utility_mips.cc +++ b/compiler/dex/quick/mips/utility_mips.cc @@ -551,15 +551,15 @@ LIR* MipsMir2Lir::LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r if (size == kWord) { size = k32; } - return LoadBaseDispBody(r_base, displacement, r_dest, RegStorage::InvalidReg(), size, - s_reg); -} - -LIR* MipsMir2Lir::LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, - int s_reg) { - return LoadBaseDispBody(r_base, displacement, r_dest.GetLow(), r_dest.GetHigh(), k64, s_reg); + if (size == k64 || size == kDouble) { + return LoadBaseDispBody(r_base, displacement, r_dest.GetLow(), r_dest.GetHigh(), k64, s_reg); + } else { + return LoadBaseDispBody(r_base, displacement, r_dest, RegStorage::InvalidReg(), size, + s_reg); + } } +// FIXME: don't split r_dest into 2 containers. LIR* MipsMir2Lir::StoreBaseDispBody(RegStorage r_base, int displacement, RegStorage r_src, RegStorage r_src_hi, OpSize size) { LIR *res; @@ -647,11 +647,11 @@ LIR* MipsMir2Lir::StoreBaseDisp(RegStorage r_base, int displacement, RegStorage if (size == kWord) { size = k32; } - return StoreBaseDispBody(r_base, displacement, r_src, RegStorage::InvalidReg(), size); -} - -LIR* MipsMir2Lir::StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src) { - return StoreBaseDispBody(r_base, displacement, r_src.GetLow(), r_src.GetHigh(), k64); + if (size == k64 || size == kDouble) { + return StoreBaseDispBody(r_base, displacement, r_src.GetLow(), r_src.GetHigh(), size); + } else { + return StoreBaseDispBody(r_base, displacement, r_src, RegStorage::InvalidReg(), size); + } } LIR* MipsMir2Lir::OpThreadMem(OpKind op, ThreadOffset<4> thread_offset) { diff --git a/compiler/dex/quick/mir_to_lir.cc b/compiler/dex/quick/mir_to_lir.cc index c9e1950de5..9915ff6f3a 100644 --- a/compiler/dex/quick/mir_to_lir.cc +++ b/compiler/dex/quick/mir_to_lir.cc @@ -59,7 +59,7 @@ RegStorage Mir2Lir::LoadArg(int in_position, bool wide) { RegStorage new_regs = AllocTypedTempWide(false, kAnyReg); reg_arg_low = new_regs.GetLow(); reg_arg_high = new_regs.GetHigh(); - LoadBaseDispWide(TargetReg(kSp), offset, new_regs, INVALID_SREG); + LoadBaseDisp(TargetReg(kSp), offset, new_regs, k64, INVALID_SREG); } else { reg_arg_high = AllocTemp(); int offset_high = offset + sizeof(uint32_t); @@ -112,7 +112,7 @@ void Mir2Lir::LoadArgDirect(int in_position, RegLocation rl_dest) { OpRegCopy(rl_dest.reg.GetHigh(), reg_arg_high); Load32Disp(TargetReg(kSp), offset, rl_dest.reg.GetLow()); } else { - LoadBaseDispWide(TargetReg(kSp), offset, rl_dest.reg, INVALID_SREG); + LoadBaseDisp(TargetReg(kSp), offset, rl_dest.reg, k64, INVALID_SREG); } } } @@ -126,6 +126,9 @@ bool Mir2Lir::GenSpecialIGet(MIR* mir, const InlineMethod& special) { } bool wide = (data.op_variant == InlineMethodAnalyser::IGetVariant(Instruction::IGET_WIDE)); + bool ref = (data.op_variant == InlineMethodAnalyser::IGetVariant(Instruction::IGET_OBJECT)); + OpSize size = LoadStoreOpSize(wide, ref); + // The inliner doesn't distinguish kDouble or kFloat, use shorty. bool double_or_float = cu_->shorty[0] == 'F' || cu_->shorty[0] == 'D'; @@ -134,11 +137,7 @@ bool Mir2Lir::GenSpecialIGet(MIR* mir, const InlineMethod& special) { LockArg(data.object_arg); RegLocation rl_dest = wide ? GetReturnWide(double_or_float) : GetReturn(double_or_float); RegStorage reg_obj = LoadArg(data.object_arg); - if (wide) { - LoadBaseDispWide(reg_obj, data.field_offset, rl_dest.reg, INVALID_SREG); - } else { - Load32Disp(reg_obj, data.field_offset, rl_dest.reg); - } + LoadBaseDisp(reg_obj, data.field_offset, rl_dest.reg, size, INVALID_SREG); if (data.is_volatile) { // Without context sensitive analysis, we must issue the most conservative barriers. // In this case, either a load or store may follow so we issue both barriers. @@ -161,6 +160,8 @@ bool Mir2Lir::GenSpecialIPut(MIR* mir, const InlineMethod& special) { } bool wide = (data.op_variant == InlineMethodAnalyser::IPutVariant(Instruction::IPUT_WIDE)); + bool ref = (data.op_variant == InlineMethodAnalyser::IGetVariant(Instruction::IGET_OBJECT)); + OpSize size = LoadStoreOpSize(wide, ref); // Point of no return - no aborts after this GenPrintLabel(mir); @@ -172,16 +173,12 @@ bool Mir2Lir::GenSpecialIPut(MIR* mir, const InlineMethod& special) { // There might have been a store before this volatile one so insert StoreStore barrier. GenMemBarrier(kStoreStore); } - if (wide) { - StoreBaseDispWide(reg_obj, data.field_offset, reg_src); - } else { - Store32Disp(reg_obj, data.field_offset, reg_src); - } + StoreBaseDisp(reg_obj, data.field_offset, reg_src, size); if (data.is_volatile) { // A load might follow the volatile store so insert a StoreLoad barrier. GenMemBarrier(kStoreLoad); } - if (data.op_variant == InlineMethodAnalyser::IPutVariant(Instruction::IPUT_OBJECT)) { + if (ref) { MarkGCCard(reg_src, reg_obj); } return true; diff --git a/compiler/dex/quick/mir_to_lir.h b/compiler/dex/quick/mir_to_lir.h index cb4396f4cf..cc6532c76c 100644 --- a/compiler/dex/quick/mir_to_lir.h +++ b/compiler/dex/quick/mir_to_lir.h @@ -977,8 +977,6 @@ class Mir2Lir : public Backend { virtual RegStorage LoadHelper(ThreadOffset<4> offset) = 0; virtual LIR* LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_dest, OpSize size, int s_reg) = 0; - virtual LIR* LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, - int s_reg) = 0; virtual LIR* LoadBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_dest, int scale, OpSize size) = 0; virtual LIR* LoadBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, @@ -988,7 +986,6 @@ class Mir2Lir : public Backend { virtual LIR* LoadConstantWide(RegStorage r_dest, int64_t value) = 0; virtual LIR* StoreBaseDisp(RegStorage r_base, int displacement, RegStorage r_src, OpSize size) = 0; - virtual LIR* StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src) = 0; virtual LIR* StoreBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_src, int scale, OpSize size) = 0; virtual LIR* StoreBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, @@ -1263,6 +1260,10 @@ class Mir2Lir : public Backend { */ RegLocation ForceTempWide(RegLocation loc); + static constexpr OpSize LoadStoreOpSize(bool wide, bool ref) { + return wide ? k64 : ref ? kReference : k32; + } + virtual void GenInstanceofFinal(bool use_declaring_class, uint32_t type_idx, RegLocation rl_dest, RegLocation rl_src); diff --git a/compiler/dex/quick/ralloc_util.cc b/compiler/dex/quick/ralloc_util.cc index a39611e195..76553af9d7 100644 --- a/compiler/dex/quick/ralloc_util.cc +++ b/compiler/dex/quick/ralloc_util.cc @@ -634,14 +634,14 @@ void Mir2Lir::FlushRegWide(RegStorage reg) { info1 = info2; } int v_reg = mir_graph_->SRegToVReg(info1->SReg()); - StoreBaseDispWide(TargetReg(kSp), VRegOffset(v_reg), reg); + StoreBaseDisp(TargetReg(kSp), VRegOffset(v_reg), reg, k64); } } else { RegisterInfo* info = GetRegInfo(reg); if (info->IsLive() && info->IsDirty()) { info->SetIsDirty(false); int v_reg = mir_graph_->SRegToVReg(info->SReg()); - StoreBaseDispWide(TargetReg(kSp), VRegOffset(v_reg), reg); + StoreBaseDisp(TargetReg(kSp), VRegOffset(v_reg), reg, k64); } } } diff --git a/compiler/dex/quick/x86/codegen_x86.h b/compiler/dex/quick/x86/codegen_x86.h index 8f0490c361..1898738930 100644 --- a/compiler/dex/quick/x86/codegen_x86.h +++ b/compiler/dex/quick/x86/codegen_x86.h @@ -34,7 +34,6 @@ class X86Mir2Lir FINAL : public Mir2Lir { RegStorage LoadHelper(ThreadOffset<4> offset); LIR* LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_dest, OpSize size, int s_reg); - LIR* LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, int s_reg); LIR* LoadBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_dest, int scale, OpSize size); LIR* LoadBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, @@ -42,7 +41,6 @@ class X86Mir2Lir FINAL : public Mir2Lir { LIR* LoadConstantNoClobber(RegStorage r_dest, int value); LIR* LoadConstantWide(RegStorage r_dest, int64_t value); LIR* StoreBaseDisp(RegStorage r_base, int displacement, RegStorage r_src, OpSize size); - LIR* StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src); LIR* StoreBaseIndexed(RegStorage r_base, RegStorage r_index, RegStorage r_src, int scale, OpSize size); LIR* StoreBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, diff --git a/compiler/dex/quick/x86/fp_x86.cc b/compiler/dex/quick/x86/fp_x86.cc index 1ed0b63d43..74828c7ad9 100644 --- a/compiler/dex/quick/x86/fp_x86.cc +++ b/compiler/dex/quick/x86/fp_x86.cc @@ -149,7 +149,7 @@ void X86Mir2Lir::GenLongToFP(RegLocation rl_dest, RegLocation rl_src, bool is_do } else { // It must have been register promoted if it is not a temp but is still in physical // register. Since we need it to be in memory to convert, we place it there now. - StoreBaseDispWide(TargetReg(kSp), src_v_reg_offset, rl_src.reg); + StoreBaseDisp(TargetReg(kSp), src_v_reg_offset, rl_src.reg, k64); } } @@ -183,7 +183,7 @@ void X86Mir2Lir::GenLongToFP(RegLocation rl_dest, RegLocation rl_src, bool is_do if (is_double) { rl_result = EvalLocWide(rl_dest, kFPReg, true); - LoadBaseDispWide(TargetReg(kSp), dest_v_reg_offset, rl_result.reg, INVALID_SREG); + LoadBaseDisp(TargetReg(kSp), dest_v_reg_offset, rl_result.reg, k64, INVALID_SREG); StoreFinalValueWide(rl_dest, rl_result); } else { diff --git a/compiler/dex/quick/x86/int_x86.cc b/compiler/dex/quick/x86/int_x86.cc index b747102bc1..315d5804ff 100644 --- a/compiler/dex/quick/x86/int_x86.cc +++ b/compiler/dex/quick/x86/int_x86.cc @@ -142,8 +142,10 @@ void X86Mir2Lir::OpRegCopyWide(RegStorage r_dest, RegStorage r_src) { } else { if (src_fp) { NewLIR2(kX86MovdrxRR, r_dest.GetLowReg(), r_src.GetReg()); - NewLIR2(kX86PsrlqRI, r_src.GetReg(), 32); - NewLIR2(kX86MovdrxRR, r_dest.GetHighReg(), r_src.GetReg()); + RegStorage temp_reg = AllocTempDouble(); + NewLIR2(kX86MovsdRR, temp_reg.GetReg(), r_src.GetReg()); + NewLIR2(kX86PsrlqRI, temp_reg.GetReg(), 32); + NewLIR2(kX86MovdrxRR, r_dest.GetHighReg(), temp_reg.GetReg()); } else { DCHECK(r_dest.IsPair()); DCHECK(r_src.IsPair()); @@ -688,14 +690,12 @@ bool X86Mir2Lir::GenInlinedPeek(CallInfo* info, OpSize size) { RegLocation rl_dest = size == k64 ? InlineTargetWide(info) : InlineTarget(info); RegLocation rl_address = LoadValue(rl_src_address, kCoreReg); RegLocation rl_result = EvalLoc(rl_dest, kCoreReg, true); + // Unaligned access is allowed on x86. + LoadBaseDisp(rl_address.reg, 0, rl_result.reg, size, INVALID_SREG); if (size == k64) { - // Unaligned access is allowed on x86. - LoadBaseDispWide(rl_address.reg, 0, rl_result.reg, INVALID_SREG); StoreValueWide(rl_dest, rl_result); } else { DCHECK(size == kSignedByte || size == kSignedHalf || size == k32); - // Unaligned access is allowed on x86. - LoadBaseDisp(rl_address.reg, 0, rl_result.reg, size, INVALID_SREG); StoreValue(rl_dest, rl_result); } return true; @@ -709,7 +709,7 @@ bool X86Mir2Lir::GenInlinedPoke(CallInfo* info, OpSize size) { if (size == k64) { // Unaligned access is allowed on x86. RegLocation rl_value = LoadValueWide(rl_src_value, kCoreReg); - StoreBaseDispWide(rl_address.reg, 0, rl_value.reg); + StoreBaseDisp(rl_address.reg, 0, rl_value.reg, size); } else { DCHECK(size == kSignedByte || size == kSignedHalf || size == k32); // Unaligned access is allowed on x86. diff --git a/compiler/dex/quick/x86/utility_x86.cc b/compiler/dex/quick/x86/utility_x86.cc index da6ded5b15..7fe0d1f4d6 100644 --- a/compiler/dex/quick/x86/utility_x86.cc +++ b/compiler/dex/quick/x86/utility_x86.cc @@ -676,11 +676,6 @@ LIR* X86Mir2Lir::LoadBaseDisp(RegStorage r_base, int displacement, RegStorage r_ size, s_reg); } -LIR* X86Mir2Lir::LoadBaseDispWide(RegStorage r_base, int displacement, RegStorage r_dest, - int s_reg) { - return LoadBaseIndexedDisp(r_base, RegStorage::InvalidReg(), 0, displacement, r_dest, k64, s_reg); -} - LIR* X86Mir2Lir::StoreBaseIndexedDisp(RegStorage r_base, RegStorage r_index, int scale, int displacement, RegStorage r_src, OpSize size, int s_reg) { LIR *store = NULL; @@ -770,11 +765,6 @@ LIR* X86Mir2Lir::StoreBaseDisp(RegStorage r_base, int displacement, INVALID_SREG); } -LIR* X86Mir2Lir::StoreBaseDispWide(RegStorage r_base, int displacement, RegStorage r_src) { - return StoreBaseIndexedDisp(r_base, RegStorage::InvalidReg(), 0, displacement, - r_src, k64, INVALID_SREG); -} - LIR* X86Mir2Lir::OpCmpMemImmBranch(ConditionCode cond, RegStorage temp_reg, RegStorage base_reg, int offset, int check_value, LIR* target) { NewLIR3(IS_SIMM8(check_value) ? kX86Cmp32MI8 : kX86Cmp32MI, base_reg.GetReg(), offset, diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc index 8b85d71dae..bbebd3af24 100644 --- a/compiler/optimizing/code_generator.cc +++ b/compiler/optimizing/code_generator.cc @@ -30,12 +30,12 @@ namespace art { void CodeGenerator::Compile(CodeAllocator* allocator) { - const GrowableArray<HBasicBlock*>* blocks = GetGraph()->GetBlocks(); - DCHECK(blocks->Get(0) == GetGraph()->GetEntryBlock()); - DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks->Get(1))); + const GrowableArray<HBasicBlock*>& blocks = GetGraph()->GetBlocks(); + DCHECK(blocks.Get(0) == GetGraph()->GetEntryBlock()); + DCHECK(GoesToNextBlock(GetGraph()->GetEntryBlock(), blocks.Get(1))); GenerateFrameEntry(); - for (size_t i = 0; i < blocks->Size(); i++) { - CompileBlock(blocks->Get(i)); + for (size_t i = 0, e = blocks.Size(); i < e; ++i) { + CompileBlock(blocks.Get(i)); } size_t code_size = GetAssembler()->CodeSize(); uint8_t* buffer = allocator->Allocate(code_size); diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h index 74cbccc4b8..aafd801eab 100644 --- a/compiler/optimizing/code_generator.h +++ b/compiler/optimizing/code_generator.h @@ -354,7 +354,7 @@ class CodeGenerator : public ArenaObject { pc_infos_(graph->GetArena(), 32), blocked_registers_(static_cast<bool*>( graph->GetArena()->Alloc(number_of_registers * sizeof(bool), kArenaAllocData))) { - block_labels_.SetSize(graph->GetBlocks()->Size()); + block_labels_.SetSize(graph->GetBlocks().Size()); } ~CodeGenerator() { } diff --git a/compiler/optimizing/dominator_test.cc b/compiler/optimizing/dominator_test.cc index 1c30b795c8..04170502d5 100644 --- a/compiler/optimizing/dominator_test.cc +++ b/compiler/optimizing/dominator_test.cc @@ -32,13 +32,13 @@ static void TestCode(const uint16_t* data, const int* blocks, size_t blocks_leng HGraph* graph = builder.BuildGraph(*item); ASSERT_NE(graph, nullptr); graph->BuildDominatorTree(); - ASSERT_EQ(graph->GetBlocks()->Size(), blocks_length); - for (size_t i = 0; i < blocks_length; i++) { + ASSERT_EQ(graph->GetBlocks().Size(), blocks_length); + for (size_t i = 0, e = blocks_length; i < e; ++i) { if (blocks[i] == -1) { - ASSERT_EQ(nullptr, graph->GetBlocks()->Get(i)->GetDominator()); + ASSERT_EQ(nullptr, graph->GetBlocks().Get(i)->GetDominator()); } else { - ASSERT_NE(nullptr, graph->GetBlocks()->Get(i)->GetDominator()); - ASSERT_EQ(blocks[i], graph->GetBlocks()->Get(i)->GetDominator()->GetBlockId()); + ASSERT_NE(nullptr, graph->GetBlocks().Get(i)->GetDominator()); + ASSERT_EQ(blocks[i], graph->GetBlocks().Get(i)->GetDominator()->GetBlockId()); } } } diff --git a/compiler/optimizing/liveness_test.cc b/compiler/optimizing/liveness_test.cc new file mode 100644 index 0000000000..aa4d35e92c --- /dev/null +++ b/compiler/optimizing/liveness_test.cc @@ -0,0 +1,515 @@ +/* + * Copyright (C) 2014 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 "builder.h" +#include "dex_file.h" +#include "dex_instruction.h" +#include "nodes.h" +#include "optimizing_unit_test.h" +#include "ssa_liveness_analysis.h" +#include "utils/arena_allocator.h" + +#include "gtest/gtest.h" + +namespace art { + +static void TestCode(const uint16_t* data, const char* expected) { + ArenaPool pool; + ArenaAllocator allocator(&pool); + HGraphBuilder builder(&allocator); + const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); + HGraph* graph = builder.BuildGraph(*item); + ASSERT_NE(graph, nullptr); + graph->BuildDominatorTree(); + graph->TransformToSSA(); + SsaLivenessAnalysis liveness(*graph); + liveness.Analyze(); + + std::ostringstream buffer; + for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + buffer << "Block " << block->GetBlockId() << std::endl; + BitVector* live_in = liveness.GetLiveInSet(*block); + live_in->Dump(buffer, " live in: "); + BitVector* live_out = liveness.GetLiveOutSet(*block); + live_out->Dump(buffer, " live out: "); + BitVector* kill = liveness.GetKillSet(*block); + kill->Dump(buffer, " kill: "); + } + ASSERT_STREQ(expected, buffer.str().c_str()); +} + +TEST(LivenessTest, CFG1) { + const char* expected = + "Block 0\n" + " live in: ()\n" + " live out: ()\n" + " kill: ()\n" + "Block 1\n" + " live in: ()\n" + " live out: ()\n" + " kill: ()\n" + "Block 2\n" + " live in: ()\n" + " live out: ()\n" + " kill: ()\n"; + + // Constant is not used. + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::RETURN_VOID); + + TestCode(data, expected); +} + +TEST(LivenessTest, CFG2) { + const char* expected = + "Block 0\n" + " live in: (0)\n" + " live out: (1)\n" + " kill: (1)\n" + "Block 1\n" + " live in: (1)\n" + " live out: (0)\n" + " kill: (0)\n" + "Block 2\n" + " live in: (0)\n" + " live out: (0)\n" + " kill: (0)\n"; + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::RETURN); + + TestCode(data, expected); +} + +TEST(LivenessTest, CFG3) { + const char* expected = + "Block 0\n" // entry block + " live in: (000)\n" + " live out: (110)\n" + " kill: (110)\n" + "Block 1\n" // block with add + " live in: (110)\n" + " live out: (001)\n" + " kill: (001)\n" + "Block 2\n" // block with return + " live in: (001)\n" + " live out: (000)\n" + " kill: (000)\n" + "Block 3\n" // exit block + " live in: (000)\n" + " live out: (000)\n" + " kill: (000)\n"; + + const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( + Instruction::CONST_4 | 3 << 12 | 0, + Instruction::CONST_4 | 4 << 12 | 1 << 8, + Instruction::ADD_INT_2ADDR | 1 << 12, + Instruction::GOTO | 0x100, + Instruction::RETURN); + + TestCode(data, expected); +} + +TEST(LivenessTest, CFG4) { + // var a; + // if (0 == 0) { + // a = 5; + // } else { + // a = 4; + // } + // return a; + // + // Bitsets are made of: + // (constant0, constant4, constant5, phi, equal test) + const char* expected = + "Block 0\n" // entry block + " live in: (00000)\n" + " live out: (11100)\n" + " kill: (11100)\n" + "Block 1\n" // block with if + " live in: (11100)\n" + " live out: (01100)\n" + " kill: (00010)\n" + "Block 2\n" // else block + " live in: (01000)\n" + " live out: (00000)\n" + " kill: (00000)\n" + "Block 3\n" // then block + " live in: (00100)\n" + " live out: (00000)\n" + " kill: (00000)\n" + "Block 4\n" // return block + " live in: (00000)\n" + " live out: (00000)\n" + " kill: (00001)\n" + "Block 5\n" // exit block + " live in: (00000)\n" + " live out: (00000)\n" + " kill: (00000)\n"; + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 4, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::GOTO | 0x200, + Instruction::CONST_4 | 5 << 12 | 0, + Instruction::RETURN | 0 << 8); + + TestCode(data, expected); +} + +TEST(LivenessTest, CFG5) { + // var a = 0; + // if (0 == 0) { + // } else { + // a = 4; + // } + // return a; + const char* expected = + "Block 0\n" // entry block + " live in: (0000)\n" + " live out: (1100)\n" + " kill: (1100)\n" + "Block 1\n" // block with if + " live in: (1100)\n" + " live out: (0100)\n" + " kill: (0010)\n" + "Block 2\n" // else block + " live in: (0100)\n" + " live out: (0000)\n" + " kill: (0000)\n" + "Block 3\n" // return block + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0001)\n" + "Block 4\n" // exit block + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0000)\n"; + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 3, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::RETURN | 0 << 8); + + TestCode(data, expected); +} + +TEST(LivenessTest, Loop1) { + // Simple loop with one preheader and one back edge. + // var a = 0; + // while (a == a) { + // a = 4; + // } + // return; + const char* expected = + "Block 0\n" // entry block + " live in: (0000)\n" + " live out: (1100)\n" + " kill: (1100)\n" + "Block 1\n" // pre header + " live in: (1100)\n" + " live out: (0100)\n" + " kill: (0000)\n" + "Block 2\n" // loop header + " live in: (0100)\n" + " live out: (0100)\n" + " kill: (0011)\n" + "Block 3\n" // back edge + " live in: (0100)\n" + " live out: (0100)\n" + " kill: (0000)\n" + "Block 4\n" // return block + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0000)\n" + "Block 5\n" // exit block + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0000)\n"; + + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 4, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::GOTO | 0xFD00, + Instruction::RETURN_VOID); + + TestCode(data, expected); +} + +TEST(LivenessTest, Loop3) { + // Test that the returned value stays live in a preceding loop. + // var a = 0; + // while (a == a) { + // a = 4; + // } + // return 5; + const char* expected = + "Block 0\n" + " live in: (00000)\n" + " live out: (11100)\n" + " kill: (11100)\n" + "Block 1\n" + " live in: (11100)\n" + " live out: (01100)\n" + " kill: (00000)\n" + "Block 2\n" // loop header + " live in: (01100)\n" + " live out: (01100)\n" + " kill: (00011)\n" + "Block 3\n" // back edge + " live in: (01100)\n" + " live out: (01100)\n" + " kill: (00000)\n" + "Block 4\n" // return block + " live in: (00100)\n" + " live out: (00000)\n" + " kill: (00000)\n" + "Block 5\n" // exit block + " live in: (00000)\n" + " live out: (00000)\n" + " kill: (00000)\n"; + + const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 4, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::GOTO | 0xFD00, + Instruction::CONST_4 | 5 << 12 | 1 << 8, + Instruction::RETURN | 1 << 8); + + TestCode(data, expected); +} + + +TEST(LivenessTest, Loop4) { + // Make sure we support a preheader of a loop not being the first predecessor + // in the predecessor list of the header. + // var a = 0; + // while (a == a) { + // a = 4; + // } + // return a; + // Bitsets are made of: + // (constant0, constant4, phi, equal test) + const char* expected = + "Block 0\n" + " live in: (0000)\n" + " live out: (1100)\n" + " kill: (1100)\n" + "Block 1\n" + " live in: (1100)\n" + " live out: (1100)\n" + " kill: (0000)\n" + "Block 2\n" // loop header + " live in: (0100)\n" + " live out: (0110)\n" + " kill: (0011)\n" + "Block 3\n" // back edge + " live in: (0100)\n" + " live out: (0100)\n" + " kill: (0000)\n" + "Block 4\n" // pre loop header + " live in: (1100)\n" + " live out: (0100)\n" + " kill: (0000)\n" + "Block 5\n" // return block + " live in: (0010)\n" + " live out: (0000)\n" + " kill: (0000)\n" + "Block 6\n" // exit block + " live in: (0000)\n" + " live out: (0000)\n" + " kill: (0000)\n"; + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::GOTO | 0x500, + Instruction::IF_EQ, 5, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::GOTO | 0xFD00, + Instruction::GOTO | 0xFC00, + Instruction::RETURN | 0 << 8); + + TestCode(data, expected); +} + +TEST(LivenessTest, Loop5) { + // Make sure we create a preheader of a loop when a header originally has two + // incoming blocks and one back edge. + // Bitsets are made of: + // (constant0, constant4, constant5, equal in block 1, phi in block 8, phi in block 4, + // equal in block 4) + const char* expected = + "Block 0\n" + " live in: (0000000)\n" + " live out: (1110000)\n" + " kill: (1110000)\n" + "Block 1\n" + " live in: (1110000)\n" + " live out: (0110000)\n" + " kill: (0001000)\n" + "Block 2\n" + " live in: (0100000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" + "Block 3\n" + " live in: (0010000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" + "Block 4\n" // loop header + " live in: (0000000)\n" + " live out: (0000010)\n" + " kill: (0000011)\n" + "Block 5\n" // back edge + " live in: (0000010)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" + "Block 6\n" // return block + " live in: (0000010)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" + "Block 7\n" // exit block + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" + "Block 8\n" // synthesized pre header + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000100)\n"; + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 4, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::GOTO | 0x200, + Instruction::CONST_4 | 5 << 12 | 0, + Instruction::IF_EQ, 3, + Instruction::GOTO | 0xFE00, + Instruction::RETURN | 0 << 8); + + TestCode(data, expected); +} + +TEST(LivenessTest, Loop6) { + // Bitsets are made of: + // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3) + const char* expected = + "Block 0\n" + " live in: (000000)\n" + " live out: (111000)\n" + " kill: (111000)\n" + "Block 1\n" + " live in: (111000)\n" + " live out: (011000)\n" + " kill: (000000)\n" + "Block 2\n" // loop header + " live in: (011000)\n" + " live out: (011100)\n" + " kill: (000110)\n" + "Block 3\n" + " live in: (011000)\n" + " live out: (011000)\n" + " kill: (000001)\n" + "Block 4\n" // back edge + " live in: (011000)\n" + " live out: (011000)\n" + " kill: (000000)\n" + "Block 5\n" // back edge + " live in: (011000)\n" + " live out: (011000)\n" + " kill: (000000)\n" + "Block 6\n" // return block + " live in: (000100)\n" + " live out: (000000)\n" + " kill: (000000)\n" + "Block 7\n" // exit block + " live in: (000000)\n" + " live out: (000000)\n" + " kill: (000000)\n"; + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 8, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::IF_EQ, 4, + Instruction::CONST_4 | 5 << 12 | 0, + Instruction::GOTO | 0xFA00, + Instruction::GOTO | 0xF900, + Instruction::RETURN | 0 << 8); + + TestCode(data, expected); +} + + +TEST(LivenessTest, Loop7) { + // Bitsets are made of: + // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3, + // phi in block 6) + const char* expected = + "Block 0\n" + " live in: (0000000)\n" + " live out: (1110000)\n" + " kill: (1110000)\n" + "Block 1\n" + " live in: (1110000)\n" + " live out: (0110000)\n" + " kill: (0000000)\n" + "Block 2\n" // loop header + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0001100)\n" + "Block 3\n" + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0000010)\n" + "Block 4\n" // loop exit + " live in: (0010000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n" + "Block 5\n" // back edge + " live in: (0110000)\n" + " live out: (0110000)\n" + " kill: (0000000)\n" + "Block 6\n" // return block + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000001)\n" + "Block 7\n" // exit block + " live in: (0000000)\n" + " live out: (0000000)\n" + " kill: (0000000)\n"; + + const uint16_t data[] = ONE_REGISTER_CODE_ITEM( + Instruction::CONST_4 | 0 | 0, + Instruction::IF_EQ, 8, + Instruction::CONST_4 | 4 << 12 | 0, + Instruction::IF_EQ, 4, + Instruction::CONST_4 | 5 << 12 | 0, + Instruction::GOTO | 0x0200, + Instruction::GOTO | 0xF900, + Instruction::RETURN | 0 << 8); + + TestCode(data, expected); +} + +} // namespace art diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 3d6aeb7300..d153bf76b8 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -25,7 +25,7 @@ void HGraph::AddBlock(HBasicBlock* block) { blocks_.Add(block); } -void HGraph::FindBackEdges(ArenaBitVector* visited) const { +void HGraph::FindBackEdges(ArenaBitVector* visited) { ArenaBitVector visiting(arena_, blocks_.Size(), false); VisitBlockForBackEdges(entry_block_, visited, &visiting); } @@ -49,7 +49,7 @@ void HGraph::RemoveDeadBlocks(const ArenaBitVector& visited) const { void HGraph::VisitBlockForBackEdges(HBasicBlock* block, ArenaBitVector* visited, - ArenaBitVector* visiting) const { + ArenaBitVector* visiting) { int id = block->GetBlockId(); if (visited->IsBitSet(id)) return; @@ -63,6 +63,7 @@ void HGraph::VisitBlockForBackEdges(HBasicBlock* block, VisitBlockForBackEdges(successor, visited, visiting); } } + post_order_.Add(block); visiting->ClearBit(id); } @@ -82,7 +83,6 @@ void HGraph::BuildDominatorTree() { // have been processed. GrowableArray<size_t> visits(arena_, blocks_.Size()); visits.SetSize(blocks_.Size()); - dominator_order_.Add(entry_block_); for (size_t i = 0; i < entry_block_->GetSuccessors()->Size(); i++) { VisitBlockForDominatorTree(entry_block_->GetSuccessors()->Get(i), entry_block_, &visits); } @@ -120,7 +120,6 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, // dominator of the block. We can then start visiting its successors. if (visits->Get(block->GetBlockId()) == block->GetPredecessors()->Size() - block->NumberOfBackEdges()) { - dominator_order_.Add(block); for (size_t i = 0; i < block->GetSuccessors()->Size(); i++) { VisitBlockForDominatorTree(block->GetSuccessors()->Get(i), block, visits); } @@ -128,15 +127,15 @@ void HGraph::VisitBlockForDominatorTree(HBasicBlock* block, } void HGraph::TransformToSSA() { - DCHECK(!dominator_order_.IsEmpty()); + DCHECK(!post_order_.IsEmpty()); SimplifyCFG(); SsaBuilder ssa_builder(this); ssa_builder.BuildSsa(); } void HGraph::SimplifyCFG() { - for (size_t i = 0; i < dominator_order_.Size(); i++) { - HBasicBlock* current = dominator_order_.Get(i); + for (size_t i = post_order_.Size(); i > 0; --i) { + HBasicBlock* current = post_order_.Get(i - 1); if (current->IsLoopHeader()) { // Make sure the loop has only one pre header. This simplifies SSA building by having // to just look at the pre header to know which locals are initialized at entry of the @@ -149,10 +148,9 @@ void HGraph::SimplifyCFG() { pre_header->AddInstruction(new (arena_) HGoto()); pre_header->SetDominator(current->GetDominator()); current->SetDominator(pre_header); - dominator_order_.InsertAt(i, pre_header); - i++; + post_order_.InsertAt(i, pre_header); - ArenaBitVector back_edges(arena_, GetBlocks()->Size(), false); + ArenaBitVector back_edges(arena_, GetBlocks().Size(), false); for (size_t pred = 0; pred < info->GetBackEdges()->Size(); pred++) { back_edges.SetBit(info->GetBackEdges()->Get(pred)->GetBlockId()); } @@ -298,9 +296,9 @@ FOR_EACH_INSTRUCTION(DEFINE_ACCEPT) #undef DEFINE_ACCEPT void HGraphVisitor::VisitInsertionOrder() { - const GrowableArray<HBasicBlock*>* blocks = graph_->GetBlocks(); - for (size_t i = 0 ; i < blocks->Size(); i++) { - VisitBasicBlock(blocks->Get(i)); + const GrowableArray<HBasicBlock*>& blocks = graph_->GetBlocks(); + for (size_t i = 0 ; i < blocks.Size(); i++) { + VisitBasicBlock(blocks.Get(i)); } } diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index 581c1d56f2..bd3d703e86 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -49,6 +49,7 @@ class HInstructionList { friend class HBasicBlock; friend class HInstructionIterator; + friend class HBackwardInstructionIterator; DISALLOW_COPY_AND_ASSIGN(HInstructionList); }; @@ -59,14 +60,14 @@ class HGraph : public ArenaObject { explicit HGraph(ArenaAllocator* arena) : arena_(arena), blocks_(arena, kDefaultNumberOfBlocks), - dominator_order_(arena, kDefaultNumberOfBlocks), + post_order_(arena, kDefaultNumberOfBlocks), maximum_number_of_out_vregs_(0), number_of_vregs_(0), number_of_in_vregs_(0), current_instruction_id_(0) { } ArenaAllocator* GetArena() const { return arena_; } - const GrowableArray<HBasicBlock*>* GetBlocks() const { return &blocks_; } + const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; } HBasicBlock* GetEntryBlock() const { return entry_block_; } HBasicBlock* GetExitBlock() const { return exit_block_; } @@ -108,8 +109,8 @@ class HGraph : public ArenaObject { return number_of_in_vregs_; } - GrowableArray<HBasicBlock*>* GetDominatorOrder() { - return &dominator_order_; + const GrowableArray<HBasicBlock*>& GetPostOrder() const { + return post_order_; } private: @@ -117,10 +118,10 @@ class HGraph : public ArenaObject { void VisitBlockForDominatorTree(HBasicBlock* block, HBasicBlock* predecessor, GrowableArray<size_t>* visits); - void FindBackEdges(ArenaBitVector* visited) const; + void FindBackEdges(ArenaBitVector* visited); void VisitBlockForBackEdges(HBasicBlock* block, ArenaBitVector* visited, - ArenaBitVector* visiting) const; + ArenaBitVector* visiting); void RemoveDeadBlocks(const ArenaBitVector& visited) const; ArenaAllocator* const arena_; @@ -128,8 +129,8 @@ class HGraph : public ArenaObject { // List of blocks in insertion order. GrowableArray<HBasicBlock*> blocks_; - // List of blocks to perform a pre-order dominator tree traversal. - GrowableArray<HBasicBlock*> dominator_order_; + // List of blocks to perform a post order tree traversal. + GrowableArray<HBasicBlock*> post_order_; HBasicBlock* entry_block_; HBasicBlock* exit_block_; @@ -322,6 +323,7 @@ class HInstruction : public ArenaObject { next_(nullptr), block_(nullptr), id_(-1), + ssa_index_(-1), uses_(nullptr), env_uses_(nullptr), environment_(nullptr), @@ -360,11 +362,17 @@ class HInstruction : public ArenaObject { HUseListNode<HInstruction>* GetUses() const { return uses_; } HUseListNode<HEnvironment>* GetEnvUses() const { return env_uses_; } - bool HasUses() const { return uses_ != nullptr; } + bool HasUses() const { return uses_ != nullptr || env_uses_ != nullptr; } int GetId() const { return id_; } void SetId(int id) { id_ = id; } + int GetSsaIndex() const { return ssa_index_; } + void SetSsaIndex(int ssa_index) { ssa_index_ = ssa_index; } + bool HasSsaIndex() const { return ssa_index_ != -1; } + + bool HasEnvironment() const { return environment_ != nullptr; } + HEnvironment* GetEnvironment() const { return environment_; } void SetEnvironment(HEnvironment* environment) { environment_ = environment; } LocationSummary* GetLocations() const { return locations_; } @@ -388,6 +396,9 @@ class HInstruction : public ArenaObject { // has not beed added to the graph. int id_; + // When doing liveness analysis, instructions that have uses get an SSA index. + int ssa_index_; + // List of instructions that have this instruction as input. HUseListNode<HInstruction>* uses_; @@ -496,6 +507,25 @@ class HInstructionIterator : public ValueObject { HInstruction* next_; }; +class HBackwardInstructionIterator : public ValueObject { + public: + explicit HBackwardInstructionIterator(const HInstructionList& instructions) + : instruction_(instructions.last_instruction_) { + next_ = Done() ? nullptr : instruction_->GetPrevious(); + } + + bool Done() const { return instruction_ == nullptr; } + HInstruction* Current() const { return instruction_; } + void Advance() { + instruction_ = next_; + next_ = Done() ? nullptr : instruction_->GetPrevious(); + } + + private: + HInstruction* instruction_; + HInstruction* next_; +}; + // An embedded container with N elements of type T. Used (with partial // specialization for N=0) because embedded arrays cannot have size 0. template<typename T, intptr_t N> @@ -966,6 +996,52 @@ class HGraphVisitor : public ValueObject { DISALLOW_COPY_AND_ASSIGN(HGraphVisitor); }; +class HInsertionOrderIterator : public ValueObject { + public: + explicit HInsertionOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} + + bool Done() const { return index_ == graph_.GetBlocks().Size(); } + HBasicBlock* Current() const { return graph_.GetBlocks().Get(index_); } + void Advance() { ++index_; } + + private: + const HGraph& graph_; + size_t index_; + + DISALLOW_COPY_AND_ASSIGN(HInsertionOrderIterator); +}; + +class HPostOrderIterator : public ValueObject { + public: + explicit HPostOrderIterator(const HGraph& graph) : graph_(graph), index_(0) {} + + bool Done() const { return index_ == graph_.GetPostOrder().Size(); } + HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_); } + void Advance() { ++index_; } + + private: + const HGraph& graph_; + size_t index_; + + DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator); +}; + +class HReversePostOrderIterator : public ValueObject { + public: + explicit HReversePostOrderIterator(const HGraph& graph) + : graph_(graph), index_(graph_.GetPostOrder().Size()) {} + + bool Done() const { return index_ == 0; } + HBasicBlock* Current() const { return graph_.GetPostOrder().Get(index_ - 1); } + void Advance() { --index_; } + + private: + const HGraph& graph_; + size_t index_; + + DISALLOW_COPY_AND_ASSIGN(HReversePostOrderIterator); +}; + } // namespace art #endif // ART_COMPILER_OPTIMIZING_NODES_H_ diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index b2c3c2df2f..8594c69159 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -22,6 +22,7 @@ #include "driver/compiler_driver.h" #include "driver/dex_compilation_unit.h" #include "nodes.h" +#include "ssa_liveness_analysis.h" #include "utils/arena_allocator.h" namespace art { @@ -103,6 +104,7 @@ CompiledMethod* OptimizingCompiler::TryCompile(const DexFile::CodeItem* code_ite // Run these phases to get some test coverage. graph->BuildDominatorTree(); graph->TransformToSSA(); + SsaLivenessAnalysis(*graph).Analyze(); return new CompiledMethod(GetCompilerDriver(), instruction_set, diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index bfb4f38f50..ee1e1e40cc 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -20,11 +20,11 @@ namespace art { void SsaBuilder::BuildSsa() { - // 1) Visit in dominator order. We need to have all predecessors of a block visited + // 1) Visit in reverse post order. We need to have all predecessors of a block visited // (with the exception of loops) in order to create the right environment for that // block. For loops, we create phis whose inputs will be set in 2). - for (size_t i = 0; i < GetGraph()->GetDominatorOrder()->Size(); i++) { - VisitBasicBlock(GetGraph()->GetDominatorOrder()->Get(i)); + for (HReversePostOrderIterator it(*GetGraph()); !it.Done(); it.Advance()) { + VisitBasicBlock(it.Current()); } // 2) Set inputs of loop phis. @@ -59,7 +59,7 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { if (block->IsLoopHeader()) { // If the block is a loop header, we know we only have visited the pre header - // because we are visiting in dominator order. We create phis for all initialized + // because we are visiting in reverse post order. We create phis for all initialized // locals from the pre header. Their inputs will be populated at the end of // the analysis. for (size_t local = 0; local < current_locals_->Size(); local++) { @@ -76,7 +76,7 @@ void SsaBuilder::VisitBasicBlock(HBasicBlock* block) { // blocks need to be updated. loop_headers_.Add(block); } else if (block->GetPredecessors()->Size() > 0) { - // All predecessors have already been visited because we are visiting in dominator order. + // All predecessors have already been visited because we are visiting in reverse post order. // We merge the values of all locals, creating phis if those values differ. for (size_t local = 0; local < current_locals_->Size(); local++) { bool is_different = false; diff --git a/compiler/optimizing/ssa_builder.h b/compiler/optimizing/ssa_builder.h index b6c6c0b658..9d8c0729ae 100644 --- a/compiler/optimizing/ssa_builder.h +++ b/compiler/optimizing/ssa_builder.h @@ -29,8 +29,8 @@ class SsaBuilder : public HGraphVisitor { : HGraphVisitor(graph), current_locals_(nullptr), loop_headers_(graph->GetArena(), kDefaultNumberOfLoops), - locals_for_(graph->GetArena(), graph->GetBlocks()->Size()) { - locals_for_.SetSize(graph->GetBlocks()->Size()); + locals_for_(graph->GetArena(), graph->GetBlocks().Size()) { + locals_for_.SetSize(graph->GetBlocks().Size()); } void BuildSsa(); diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc new file mode 100644 index 0000000000..838597d4ac --- /dev/null +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -0,0 +1,170 @@ +/* + * Copyright (C) 2014 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 "ssa_liveness_analysis.h" +#include "nodes.h" + +namespace art { + +void SsaLivenessAnalysis::Analyze() { + NumberInstructions(); + ComputeSets(); +} + +void SsaLivenessAnalysis::NumberInstructions() { + int ssa_index = 0; + for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + + for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) { + HInstruction* current = it.Current(); + if (current->HasUses()) { + current->SetSsaIndex(ssa_index++); + } + } + + for (HInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) { + HInstruction* current = it.Current(); + if (current->HasUses()) { + current->SetSsaIndex(ssa_index++); + } + } + } + number_of_ssa_values_ = ssa_index; +} + +void SsaLivenessAnalysis::ComputeSets() { + for (HReversePostOrderIterator it(graph_); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + block_infos_.Put( + block->GetBlockId(), + new (graph_.GetArena()) BlockInfo(graph_.GetArena(), *block, number_of_ssa_values_)); + } + + // Compute the initial live_in, live_out, and kill sets. This method does not handle + // backward branches, therefore live_in and live_out sets are not yet correct. + ComputeInitialSets(); + + // Do a fixed point calculation to take into account backward branches, + // that will update live_in of loop headers, and therefore live_out and live_in + // of blocks in the loop. + ComputeLiveInAndLiveOutSets(); +} + +void SsaLivenessAnalysis::ComputeInitialSets() { + // Do a post orderr visit, adding inputs of instructions live in the block where + // that instruction is defined, and killing instructions that are being visited. + for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + + BitVector* kill = GetKillSet(*block); + BitVector* live_in = GetLiveInSet(*block); + + for (HBackwardInstructionIterator it(*block->GetInstructions()); !it.Done(); it.Advance()) { + HInstruction* current = it.Current(); + if (current->HasSsaIndex()) { + kill->SetBit(current->GetSsaIndex()); + live_in->ClearBit(current->GetSsaIndex()); + } + + // All inputs of an instruction must be live. + for (size_t i = 0, e = current->InputCount(); i < e; ++i) { + DCHECK(current->InputAt(i)->HasSsaIndex()); + live_in->SetBit(current->InputAt(i)->GetSsaIndex()); + } + + if (current->HasEnvironment()) { + // All instructions in the environment must be live. + GrowableArray<HInstruction*>* environment = current->GetEnvironment()->GetVRegs(); + for (size_t i = 0, e = environment->Size(); i < e; ++i) { + HInstruction* instruction = environment->Get(i); + if (instruction != nullptr) { + DCHECK(instruction->HasSsaIndex()); + live_in->SetBit(instruction->GetSsaIndex()); + } + } + } + } + + for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) { + HInstruction* current = it.Current(); + if (current->HasSsaIndex()) { + kill->SetBit(current->GetSsaIndex()); + live_in->ClearBit(current->GetSsaIndex()); + } + + // Mark a phi input live_in for its corresponding predecessor. + for (size_t i = 0, e = current->InputCount(); i < e; ++i) { + HInstruction* input = current->InputAt(i); + + HBasicBlock* predecessor = block->GetPredecessors()->Get(i); + size_t ssa_index = input->GetSsaIndex(); + BitVector* predecessor_kill = GetKillSet(*predecessor); + BitVector* predecessor_live_in = GetLiveInSet(*predecessor); + + // Phi inputs from a back edge have already been visited. If the back edge + // block defines that input, we should not add it to its live_in. + if (!predecessor_kill->IsBitSet(ssa_index)) { + predecessor_live_in->SetBit(ssa_index); + } + } + } + } +} + +void SsaLivenessAnalysis::ComputeLiveInAndLiveOutSets() { + bool changed; + do { + changed = false; + + for (HPostOrderIterator it(graph_); !it.Done(); it.Advance()) { + const HBasicBlock& block = *it.Current(); + + // The live_in set depends on the kill set (which does not + // change in this loop), and the live_out set. If the live_out + // set does not change, there is no need to update the live_in set. + if (UpdateLiveOut(block) && UpdateLiveIn(block)) { + changed = true; + } + } + } while (changed); +} + +bool SsaLivenessAnalysis::UpdateLiveOut(const HBasicBlock& block) { + BitVector* live_out = GetLiveOutSet(block); + bool changed = false; + // The live_out set of a block is the union of live_in sets of its successors. + for (size_t i = 0, e = block.GetSuccessors()->Size(); i < e; ++i) { + HBasicBlock* successor = block.GetSuccessors()->Get(i); + if (live_out->Union(GetLiveInSet(*successor))) { + changed = true; + } + } + return changed; +} + + +bool SsaLivenessAnalysis::UpdateLiveIn(const HBasicBlock& block) { + BitVector* live_out = GetLiveOutSet(block); + BitVector* kill = GetKillSet(block); + BitVector* live_in = GetLiveInSet(block); + // If live_out is updated (because of backward branches), we need to make + // sure instructions in live_out are also in live_in, unless they are killed + // by this block. + return live_in->UnionIfNotIn(live_out, kill); +} + +} // namespace art diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h new file mode 100644 index 0000000000..6a901d1c04 --- /dev/null +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -0,0 +1,101 @@ +/* + * Copyright (C) 2014 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. + */ + +#ifndef ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ +#define ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ + +#include "nodes.h" + +namespace art { + +class BlockInfo : public ArenaObject { + public: + BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values) + : block_(block), + live_in_(allocator, number_of_ssa_values, false), + live_out_(allocator, number_of_ssa_values, false), + kill_(allocator, number_of_ssa_values, false) { + live_in_.ClearAllBits(); + live_out_.ClearAllBits(); + kill_.ClearAllBits(); + } + + private: + const HBasicBlock& block_; + ArenaBitVector live_in_; + ArenaBitVector live_out_; + ArenaBitVector kill_; + + friend class SsaLivenessAnalysis; + + DISALLOW_COPY_AND_ASSIGN(BlockInfo); +}; + +class SsaLivenessAnalysis : public ValueObject { + public: + explicit SsaLivenessAnalysis(const HGraph& graph) + : graph_(graph), + block_infos_(graph.GetArena(), graph.GetBlocks().Size()), + number_of_ssa_values_(0) { + block_infos_.SetSize(graph.GetBlocks().Size()); + } + + void Analyze(); + + BitVector* GetLiveInSet(const HBasicBlock& block) const { + return &block_infos_.Get(block.GetBlockId())->live_in_; + } + + BitVector* GetLiveOutSet(const HBasicBlock& block) const { + return &block_infos_.Get(block.GetBlockId())->live_out_; + } + + BitVector* GetKillSet(const HBasicBlock& block) const { + return &block_infos_.Get(block.GetBlockId())->kill_; + } + + private: + // Give an SSA number to each instruction that defines a value used by another instruction. + void NumberInstructions(); + + // Compute live_in, live_out and kill sets. + void ComputeSets(); + + // Compute the initial live_in, live_out and kill sets, without analyzing + // backward branches. + void ComputeInitialSets(); + + // After computing the initial sets, this method does a fixed point + // calculation over the live_in and live_out set to take into account + // backwards branches. + void ComputeLiveInAndLiveOutSets(); + + // Update the live_in set of the block and returns whether it has changed. + bool UpdateLiveIn(const HBasicBlock& block); + + // Update the live_out set of the block and returns whether it has changed. + bool UpdateLiveOut(const HBasicBlock& block); + + const HGraph& graph_; + GrowableArray<BlockInfo*> block_infos_; + size_t number_of_ssa_values_; + + DISALLOW_COPY_AND_ASSIGN(SsaLivenessAnalysis); +}; + +} // namespace art + +#endif // ART_COMPILER_OPTIMIZING_SSA_LIVENESS_ANALYSIS_H_ diff --git a/compiler/optimizing/ssa_test.cc b/compiler/optimizing/ssa_test.cc index 7c3633b5e9..e4aafb7af3 100644 --- a/compiler/optimizing/ssa_test.cc +++ b/compiler/optimizing/ssa_test.cc @@ -64,8 +64,8 @@ class StringPrettyPrinter : public HPrettyPrinter { static void ReNumberInstructions(HGraph* graph) { int id = 0; - for (size_t i = 0; i < graph->GetBlocks()->Size(); i++) { - HBasicBlock* block = graph->GetBlocks()->Get(i); + for (size_t i = 0, e = graph->GetBlocks().Size(); i < e; ++i) { + HBasicBlock* block = graph->GetBlocks().Get(i); for (HInstructionIterator it(*block->GetPhis()); !it.Done(); it.Advance()) { it.Current()->SetId(id++); } @@ -147,7 +147,7 @@ TEST(SsaTest, CFG2) { TEST(SsaTest, CFG3) { // Test that we create a phi for the join block of an if control flow instruction - // when there both branches update a local. + // when both branches update a local. const char* expected = "BasicBlock 0, succ: 1\n" " 0: IntConstant 0 [4, 4]\n" diff --git a/compiler/utils/growable_array.h b/compiler/utils/growable_array.h index 659b4f76a0..e703d8e25a 100644 --- a/compiler/utils/growable_array.h +++ b/compiler/utils/growable_array.h @@ -78,7 +78,7 @@ class GrowableArray { private: size_t idx_; - GrowableArray* const g_list_; + GrowableArray* g_list_; }; GrowableArray(ArenaAllocator* arena, size_t init_length, OatListKind kind = kGrowableArrayMisc) diff --git a/runtime/base/bit_vector.cc b/runtime/base/bit_vector.cc index 3df5101fa3..0e01dc2349 100644 --- a/runtime/base/bit_vector.cc +++ b/runtime/base/bit_vector.cc @@ -43,7 +43,8 @@ BitVector::BitVector(uint32_t start_bits, : allocator_(allocator), expandable_(expandable), storage_size_(storage_size), - storage_(storage) { + storage_(storage), + number_of_bits_(start_bits) { DCHECK_EQ(sizeof(*storage_), 4U); // Assuming 32-bit units. if (storage_ == nullptr) { storage_size_ = BitsToWords(start_bits); @@ -93,6 +94,7 @@ void BitVector::SetBit(uint32_t num) { // TOTO: collect stats on space wasted because of resize. storage_ = new_storage; storage_size_ = new_size; + number_of_bits_ = num; } storage_[num >> 5] |= check_masks[num & 0x1f]; @@ -113,23 +115,24 @@ bool BitVector::SameBitsSet(const BitVector *src) { // If the highest bit set is different, we are different. if (our_highest != src_highest) { - return true; + return false; } // If the highest bit set is -1, both are cleared, we are the same. // If the highest bit set is 0, both have a unique bit set, we are the same. - if (our_highest >= 0) { + if (our_highest <= 0) { return true; } - // Get the highest bit set's cell's index. - int our_highest_index = (our_highest >> 5); + // Get the highest bit set's cell's index + // No need of highest + 1 here because it can't be 0 so BitsToWords will work here. + int our_highest_index = BitsToWords(our_highest); // This memcmp is enough: we know that the highest bit set is the same for both: // - Therefore, min_size goes up to at least that, we are thus comparing at least what we need to, but not less. // ie. we are comparing all storage cells that could have difference, if both vectors have cells above our_highest_index, // they are automatically at 0. - return (memcmp(storage_, src->GetRawStorage(), our_highest_index * sizeof(*storage_)) != 0); + return (memcmp(storage_, src->GetRawStorage(), our_highest_index * sizeof(*storage_)) == 0); } // Intersect with another bit vector. @@ -156,13 +159,14 @@ void BitVector::Intersect(const BitVector* src) { /* * Union with another bit vector. */ -void BitVector::Union(const BitVector* src) { +bool BitVector::Union(const BitVector* src) { // Get the highest bit to determine how much we need to expand. int highest_bit = src->GetHighestBitSet(); + bool changed = false; // If src has no bit set, we are done: there is no need for a union with src. if (highest_bit == -1) { - return; + return changed; } // Update src_size to how many cells we actually care about: where the bit is + 1. @@ -170,6 +174,8 @@ void BitVector::Union(const BitVector* src) { // Is the storage size smaller than src's? if (storage_size_ < src_size) { + changed = true; + // Set it to reallocate. SetBit(highest_bit); @@ -178,8 +184,62 @@ void BitVector::Union(const BitVector* src) { } for (uint32_t idx = 0; idx < src_size; idx++) { - storage_[idx] |= src->GetRawStorageWord(idx); + uint32_t existing = storage_[idx]; + uint32_t update = existing | src->GetRawStorageWord(idx); + if (existing != update) { + changed = true; + storage_[idx] = update; + } } + return changed; +} + +bool BitVector::UnionIfNotIn(const BitVector* union_with, const BitVector* not_in) { + // Get the highest bit to determine how much we need to expand. + int highest_bit = union_with->GetHighestBitSet(); + bool changed = false; + + // If src has no bit set, we are done: there is no need for a union with src. + if (highest_bit == -1) { + return changed; + } + + // Update union_with_size to how many cells we actually care about: where the bit is + 1. + uint32_t union_with_size = BitsToWords(highest_bit + 1); + + // Is the storage size smaller than src's? + if (storage_size_ < union_with_size) { + changed = true; + + // Set it to reallocate. + SetBit(highest_bit); + + // Paranoid: storage size should be big enough to hold this bit now. + DCHECK_LT(static_cast<uint32_t> (highest_bit), storage_size_ * sizeof(*(storage_)) * 8); + } + + uint32_t not_in_size = not_in->GetStorageSize(); + + uint32_t idx = 0; + for (; idx < std::min(not_in_size, union_with_size); idx++) { + uint32_t existing = storage_[idx]; + uint32_t update = existing | + (union_with->GetRawStorageWord(idx) & ~not_in->GetRawStorageWord(idx)); + if (existing != update) { + changed = true; + storage_[idx] = update; + } + } + + for (; idx < union_with_size; idx++) { + uint32_t existing = storage_[idx]; + uint32_t update = existing | union_with->GetRawStorageWord(idx); + if (existing != update) { + changed = true; + storage_[idx] = update; + } + } + return changed; } void BitVector::Subtract(const BitVector *src) { @@ -342,7 +402,7 @@ uint32_t BitVector::NumSetBits(const uint32_t* storage, uint32_t end) { void BitVector::Dump(std::ostream& os, const char *prefix) { std::ostringstream buffer; DumpHelper(buffer, prefix); - os << buffer << std::endl; + os << buffer.str() << std::endl; } void BitVector::DumpDot(FILE* file, const char* prefix, bool last_entry) { @@ -367,13 +427,11 @@ void BitVector::DumpHelper(std::ostringstream& buffer, const char* prefix) { buffer << prefix; } - int max = GetHighestBitSet(); - - for (int i = 0; i <= max; i++) { - if (IsBitSet(i)) { - buffer << i << " "; - } + buffer << '('; + for (size_t i = 0; i < number_of_bits_; i++) { + buffer << IsBitSet(i); } + buffer << ')'; } } // namespace art diff --git a/runtime/base/bit_vector.h b/runtime/base/bit_vector.h index db29c4969e..6ee6b00e07 100644 --- a/runtime/base/bit_vector.h +++ b/runtime/base/bit_vector.h @@ -103,7 +103,11 @@ class BitVector { void Copy(const BitVector* src); void Intersect(const BitVector* src2); - void Union(const BitVector* src); + bool Union(const BitVector* src); + + // Set bits of union_with that are not in not_in. + bool UnionIfNotIn(const BitVector* union_with, const BitVector* not_in); + void Subtract(const BitVector* src); // Are we equal to another bit vector? Note: expandability attributes must also match. bool Equal(const BitVector* src) { @@ -155,6 +159,7 @@ class BitVector { const bool expandable_; // expand bitmap if we run out? uint32_t storage_size_; // current size, in 32-bit words. uint32_t* storage_; + uint32_t number_of_bits_; }; |