Merge "AArch64: Add fake arm64 backend, and disable it by method filter."
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 429c523..d4e2cbb 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -78,6 +78,7 @@
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 e3201e7..a993251 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -79,6 +79,7 @@
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 30d0bc3..ca90a83 100644
--- a/compiler/dex/mir_graph.cc
+++ b/compiler/dex/mir_graph.cc
@@ -1257,4 +1257,55 @@
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 c728d84..85a2d04 100644
--- a/compiler/dex/mir_graph.h
+++ b/compiler/dex/mir_graph.h
@@ -341,6 +341,29 @@
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 5cc994f..413b4e0 100644
--- a/compiler/dex/mir_optimization.cc
+++ b/compiler/dex/mir_optimization.cc
@@ -735,18 +735,20 @@
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 @@
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 9d1723a..8b4576c 100644
--- a/compiler/dex/quick/arm/codegen_arm.h
+++ b/compiler/dex/quick/arm/codegen_arm.h
@@ -34,7 +34,6 @@
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 @@
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 8391c03..8dd31d1 100644
--- a/compiler/dex/quick/arm/int_arm.cc
+++ b/compiler/dex/quick/arm/int_arm.cc
@@ -1170,19 +1170,14 @@
}
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 @@
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 08acef7..b7b9093 100644
--- a/compiler/dex/quick/arm/utility_arm.cc
+++ b/compiler/dex/quick/arm/utility_arm.cc
@@ -957,7 +957,6 @@
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 @@
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 @@
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 94c2563..4e784c6 100644
--- a/compiler/dex/quick/arm64/codegen_arm64.h
+++ b/compiler/dex/quick/arm64/codegen_arm64.h
@@ -34,7 +34,6 @@
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 @@
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 11fb765..c5a3ab6 100644
--- a/compiler/dex/quick/arm64/int_arm64.cc
+++ b/compiler/dex/quick/arm64/int_arm64.cc
@@ -1170,19 +1170,14 @@
}
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 @@
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 d66b834..8ff1830 100644
--- a/compiler/dex/quick/arm64/utility_arm64.cc
+++ b/compiler/dex/quick/arm64/utility_arm64.cc
@@ -957,7 +957,6 @@
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 @@
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 @@
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 2cd17cc..395cff7 100644
--- a/compiler/dex/quick/gen_common.cc
+++ b/compiler/dex/quick/gen_common.cc
@@ -564,13 +564,8 @@
// 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 @@
}
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 @@
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 @@
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 @@
// 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 9c1fbe4..960ac10 100644
--- a/compiler/dex/quick/gen_invoke.cc
+++ b/compiler/dex/quick/gen_invoke.cc
@@ -791,7 +791,7 @@
}
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 @@
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 @@
} 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 @@
} 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 e6911cd..6fe1e31 100644
--- a/compiler/dex/quick/gen_loadstore.cc
+++ b/compiler/dex/quick/gen_loadstore.cc
@@ -123,7 +123,7 @@
} 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 @@
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 @@
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 7a8376e..cdabf8e 100644
--- a/compiler/dex/quick/mips/codegen_mips.h
+++ b/compiler/dex/quick/mips/codegen_mips.h
@@ -35,7 +35,6 @@
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 @@
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 1410e14..fe2e495 100644
--- a/compiler/dex/quick/mips/int_mips.cc
+++ b/compiler/dex/quick/mips/int_mips.cc
@@ -511,7 +511,7 @@
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 @@
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 50b945a..9aa929c 100644
--- a/compiler/dex/quick/mips/utility_mips.cc
+++ b/compiler/dex/quick/mips/utility_mips.cc
@@ -551,15 +551,15 @@
if (size == kWord) {
size = k32;
}
- return LoadBaseDispBody(r_base, displacement, r_dest, RegStorage::InvalidReg(), size,
- 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);
+ }
}
-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);
-}
-
+// 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 @@
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 c9e1950..9915ff6 100644
--- a/compiler/dex/quick/mir_to_lir.cc
+++ b/compiler/dex/quick/mir_to_lir.cc
@@ -59,7 +59,7 @@
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 @@
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 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 @@
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 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 @@
// 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 cb4396f..cc6532c 100644
--- a/compiler/dex/quick/mir_to_lir.h
+++ b/compiler/dex/quick/mir_to_lir.h
@@ -977,8 +977,6 @@
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 @@
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 @@
*/
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 a39611e..76553af 100644
--- a/compiler/dex/quick/ralloc_util.cc
+++ b/compiler/dex/quick/ralloc_util.cc
@@ -634,14 +634,14 @@
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 8f0490c..1898738 100644
--- a/compiler/dex/quick/x86/codegen_x86.h
+++ b/compiler/dex/quick/x86/codegen_x86.h
@@ -34,7 +34,6 @@
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 @@
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 1ed0b63..74828c7 100644
--- a/compiler/dex/quick/x86/fp_x86.cc
+++ b/compiler/dex/quick/x86/fp_x86.cc
@@ -149,7 +149,7 @@
} 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 @@
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 b747102..315d580 100644
--- a/compiler/dex/quick/x86/int_x86.cc
+++ b/compiler/dex/quick/x86/int_x86.cc
@@ -142,8 +142,10 @@
} 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 @@
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 @@
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 da6ded5..7fe0d1f 100644
--- a/compiler/dex/quick/x86/utility_x86.cc
+++ b/compiler/dex/quick/x86/utility_x86.cc
@@ -676,11 +676,6 @@
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 @@
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 8b85d71..bbebd3a 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 74cbccc..aafd801 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -354,7 +354,7 @@
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 1c30b79..0417050 100644
--- a/compiler/optimizing/dominator_test.cc
+++ b/compiler/optimizing/dominator_test.cc
@@ -32,13 +32,13 @@
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 0000000..aa4d35e
--- /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 3d6aeb7..d153bf7 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -25,7 +25,7 @@
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::VisitBlockForBackEdges(HBasicBlock* block,
ArenaBitVector* visited,
- ArenaBitVector* visiting) const {
+ ArenaBitVector* visiting) {
int id = block->GetBlockId();
if (visited->IsBitSet(id)) return;
@@ -63,6 +63,7 @@
VisitBlockForBackEdges(successor, visited, visiting);
}
}
+ post_order_.Add(block);
visiting->ClearBit(id);
}
@@ -82,7 +83,6 @@
// 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 @@
// 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::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 @@
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 @@
#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 581c1d5..bd3d703 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -49,6 +49,7 @@
friend class HBasicBlock;
friend class HInstructionIterator;
+ friend class HBackwardInstructionIterator;
DISALLOW_COPY_AND_ASSIGN(HInstructionList);
};
@@ -59,14 +60,14 @@
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 @@
return number_of_in_vregs_;
}
- GrowableArray<HBasicBlock*>* GetDominatorOrder() {
- return &dominator_order_;
+ const GrowableArray<HBasicBlock*>& GetPostOrder() const {
+ return post_order_;
}
private:
@@ -117,10 +118,10 @@
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 @@
// 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 @@
next_(nullptr),
block_(nullptr),
id_(-1),
+ ssa_index_(-1),
uses_(nullptr),
env_uses_(nullptr),
environment_(nullptr),
@@ -360,11 +362,17 @@
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 @@
// 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 @@
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 @@
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 b2c3c2d..8594c69 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 @@
// 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 bfb4f38..ee1e1e4 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 @@
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 @@
// 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 b6c6c0b..9d8c072 100644
--- a/compiler/optimizing/ssa_builder.h
+++ b/compiler/optimizing/ssa_builder.h
@@ -29,8 +29,8 @@
: 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 0000000..838597d
--- /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 0000000..6a901d1
--- /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 7c3633b..e4aafb7 100644
--- a/compiler/optimizing/ssa_test.cc
+++ b/compiler/optimizing/ssa_test.cc
@@ -64,8 +64,8 @@
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, 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 659b4f7..e703d8e 100644
--- a/compiler/utils/growable_array.h
+++ b/compiler/utils/growable_array.h
@@ -78,7 +78,7 @@
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 3df5101..0e01dc2 100644
--- a/runtime/base/bit_vector.cc
+++ b/runtime/base/bit_vector.cc
@@ -43,7 +43,8 @@
: 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 @@
// 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 @@
// 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 @@
/*
* 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 @@
// 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 @@
}
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 @@
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 @@
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 db29c49..6ee6b00 100644
--- a/runtime/base/bit_vector.h
+++ b/runtime/base/bit_vector.h
@@ -103,7 +103,11 @@
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 @@
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_;
};