summaryrefslogtreecommitdiff
path: root/compiler
diff options
context:
space:
mode:
Diffstat (limited to 'compiler')
-rw-r--r--compiler/jit/jit_compiler.cc4
-rw-r--r--compiler/optimizing/code_generator_mips.cc188
-rw-r--r--compiler/optimizing/code_generator_mips.h2
-rw-r--r--compiler/optimizing/induction_var_range.cc10
-rw-r--r--compiler/optimizing/induction_var_range.h1
-rw-r--r--compiler/optimizing/induction_var_range_test.cc12
-rw-r--r--compiler/optimizing/load_store_analysis.cc111
-rw-r--r--compiler/optimizing/load_store_analysis.h20
-rw-r--r--compiler/optimizing/load_store_analysis_test.cc194
-rw-r--r--compiler/optimizing/loop_optimization.cc20
-rw-r--r--compiler/optimizing/nodes.h4
-rw-r--r--compiler/optimizing/scheduler.cc8
-rw-r--r--compiler/optimizing/ssa_liveness_analysis.cc2
13 files changed, 449 insertions, 127 deletions
diff --git a/compiler/jit/jit_compiler.cc b/compiler/jit/jit_compiler.cc
index 715d97379e..28a3f1edae 100644
--- a/compiler/jit/jit_compiler.cc
+++ b/compiler/jit/jit_compiler.cc
@@ -100,6 +100,10 @@ JitCompiler::JitCompiler() {
// Set debuggability based on the runtime value.
compiler_options_->SetDebuggable(Runtime::Current()->IsJavaDebuggable());
+ // Special case max code units for inlining, whose default is "unset" (implictly
+ // meaning no limit).
+ compiler_options_->SetInlineMaxCodeUnits(CompilerOptions::kDefaultInlineMaxCodeUnits);
+
const InstructionSet instruction_set = kRuntimeISA;
for (const StringPiece option : Runtime::Current()->GetCompilerOptions()) {
VLOG(compiler) << "JIT compiler option " << option;
diff --git a/compiler/optimizing/code_generator_mips.cc b/compiler/optimizing/code_generator_mips.cc
index b39d412ac2..6828fed944 100644
--- a/compiler/optimizing/code_generator_mips.cc
+++ b/compiler/optimizing/code_generator_mips.cc
@@ -950,7 +950,9 @@ class ReadBarrierForHeapReferenceSlowPathMIPS : public SlowPathCodeMIPS {
this);
CheckEntrypointTypes<
kQuickReadBarrierSlow, mirror::Object*, mirror::Object*, mirror::Object*, uint32_t>();
- mips_codegen->Move32(out_, calling_convention.GetReturnLocation(Primitive::kPrimNot));
+ mips_codegen->MoveLocation(out_,
+ calling_convention.GetReturnLocation(Primitive::kPrimNot),
+ Primitive::kPrimNot);
RestoreLiveRegisters(codegen, locations);
__ B(GetExitLabel());
@@ -1013,13 +1015,17 @@ class ReadBarrierForRootSlowPathMIPS : public SlowPathCodeMIPS {
InvokeRuntimeCallingConvention calling_convention;
CodeGeneratorMIPS* mips_codegen = down_cast<CodeGeneratorMIPS*>(codegen);
- mips_codegen->Move32(Location::RegisterLocation(calling_convention.GetRegisterAt(0)), root_);
+ mips_codegen->MoveLocation(Location::RegisterLocation(calling_convention.GetRegisterAt(0)),
+ root_,
+ Primitive::kPrimNot);
mips_codegen->InvokeRuntime(kQuickReadBarrierForRootSlow,
instruction_,
instruction_->GetDexPc(),
this);
CheckEntrypointTypes<kQuickReadBarrierForRootSlow, mirror::Object*, GcRoot<mirror::Object>*>();
- mips_codegen->Move32(out_, calling_convention.GetReturnLocation(Primitive::kPrimNot));
+ mips_codegen->MoveLocation(out_,
+ calling_convention.GetReturnLocation(Primitive::kPrimNot),
+ Primitive::kPrimNot);
RestoreLiveRegisters(codegen, locations);
__ B(GetExitLabel());
@@ -1407,106 +1413,92 @@ void CodeGeneratorMIPS::Bind(HBasicBlock* block) {
__ Bind(GetLabelOf(block));
}
-void CodeGeneratorMIPS::MoveLocation(Location dst, Location src, Primitive::Type dst_type) {
- if (src.Equals(dst)) {
- return;
- }
-
- if (src.IsConstant()) {
- MoveConstant(dst, src.GetConstant());
- } else {
- if (Primitive::Is64BitType(dst_type)) {
- Move64(dst, src);
- } else {
- Move32(dst, src);
- }
- }
-}
-
-void CodeGeneratorMIPS::Move32(Location destination, Location source) {
- if (source.Equals(destination)) {
- return;
- }
-
- if (destination.IsRegister()) {
- if (source.IsRegister()) {
- __ Move(destination.AsRegister<Register>(), source.AsRegister<Register>());
- } else if (source.IsFpuRegister()) {
- __ Mfc1(destination.AsRegister<Register>(), source.AsFpuRegister<FRegister>());
- } else {
- DCHECK(source.IsStackSlot()) << "Cannot move from " << source << " to " << destination;
- __ LoadFromOffset(kLoadWord, destination.AsRegister<Register>(), SP, source.GetStackIndex());
- }
- } else if (destination.IsFpuRegister()) {
- if (source.IsRegister()) {
- __ Mtc1(source.AsRegister<Register>(), destination.AsFpuRegister<FRegister>());
- } else if (source.IsFpuRegister()) {
- __ MovS(destination.AsFpuRegister<FRegister>(), source.AsFpuRegister<FRegister>());
- } else {
- DCHECK(source.IsStackSlot()) << "Cannot move from " << source << " to " << destination;
- __ LoadSFromOffset(destination.AsFpuRegister<FRegister>(), SP, source.GetStackIndex());
- }
- } else {
- DCHECK(destination.IsStackSlot()) << destination;
- if (source.IsRegister()) {
- __ StoreToOffset(kStoreWord, source.AsRegister<Register>(), SP, destination.GetStackIndex());
- } else if (source.IsFpuRegister()) {
- __ StoreSToOffset(source.AsFpuRegister<FRegister>(), SP, destination.GetStackIndex());
- } else {
- DCHECK(source.IsStackSlot()) << "Cannot move from " << source << " to " << destination;
- __ LoadFromOffset(kLoadWord, TMP, SP, source.GetStackIndex());
- __ StoreToOffset(kStoreWord, TMP, SP, destination.GetStackIndex());
- }
- }
-}
-
-void CodeGeneratorMIPS::Move64(Location destination, Location source) {
+void CodeGeneratorMIPS::MoveLocation(Location destination,
+ Location source,
+ Primitive::Type dst_type) {
if (source.Equals(destination)) {
return;
}
- if (destination.IsRegisterPair()) {
- if (source.IsRegisterPair()) {
- __ Move(destination.AsRegisterPairHigh<Register>(), source.AsRegisterPairHigh<Register>());
- __ Move(destination.AsRegisterPairLow<Register>(), source.AsRegisterPairLow<Register>());
- } else if (source.IsFpuRegister()) {
- Register dst_high = destination.AsRegisterPairHigh<Register>();
- Register dst_low = destination.AsRegisterPairLow<Register>();
- FRegister src = source.AsFpuRegister<FRegister>();
- __ Mfc1(dst_low, src);
- __ MoveFromFpuHigh(dst_high, src);
- } else {
- DCHECK(source.IsDoubleStackSlot()) << "Cannot move from " << source << " to " << destination;
- int32_t off = source.GetStackIndex();
- Register r = destination.AsRegisterPairLow<Register>();
- __ LoadFromOffset(kLoadDoubleword, r, SP, off);
- }
- } else if (destination.IsFpuRegister()) {
- if (source.IsRegisterPair()) {
- FRegister dst = destination.AsFpuRegister<FRegister>();
- Register src_high = source.AsRegisterPairHigh<Register>();
- Register src_low = source.AsRegisterPairLow<Register>();
- __ Mtc1(src_low, dst);
- __ MoveToFpuHigh(src_high, dst);
- } else if (source.IsFpuRegister()) {
- __ MovD(destination.AsFpuRegister<FRegister>(), source.AsFpuRegister<FRegister>());
- } else {
- DCHECK(source.IsDoubleStackSlot()) << "Cannot move from " << source << " to " << destination;
- __ LoadDFromOffset(destination.AsFpuRegister<FRegister>(), SP, source.GetStackIndex());
- }
+ if (source.IsConstant()) {
+ MoveConstant(destination, source.GetConstant());
} else {
- DCHECK(destination.IsDoubleStackSlot()) << destination;
- int32_t off = destination.GetStackIndex();
- if (source.IsRegisterPair()) {
- __ StoreToOffset(kStoreDoubleword, source.AsRegisterPairLow<Register>(), SP, off);
- } else if (source.IsFpuRegister()) {
- __ StoreDToOffset(source.AsFpuRegister<FRegister>(), SP, off);
+ if (destination.IsRegister()) {
+ if (source.IsRegister()) {
+ __ Move(destination.AsRegister<Register>(), source.AsRegister<Register>());
+ } else if (source.IsFpuRegister()) {
+ __ Mfc1(destination.AsRegister<Register>(), source.AsFpuRegister<FRegister>());
+ } else {
+ DCHECK(source.IsStackSlot()) << "Cannot move from " << source << " to " << destination;
+ __ LoadFromOffset(kLoadWord, destination.AsRegister<Register>(), SP, source.GetStackIndex());
+ }
+ } else if (destination.IsRegisterPair()) {
+ if (source.IsRegisterPair()) {
+ __ Move(destination.AsRegisterPairHigh<Register>(), source.AsRegisterPairHigh<Register>());
+ __ Move(destination.AsRegisterPairLow<Register>(), source.AsRegisterPairLow<Register>());
+ } else if (source.IsFpuRegister()) {
+ Register dst_high = destination.AsRegisterPairHigh<Register>();
+ Register dst_low = destination.AsRegisterPairLow<Register>();
+ FRegister src = source.AsFpuRegister<FRegister>();
+ __ Mfc1(dst_low, src);
+ __ MoveFromFpuHigh(dst_high, src);
+ } else {
+ DCHECK(source.IsDoubleStackSlot()) << "Cannot move from " << source << " to " << destination;
+ int32_t off = source.GetStackIndex();
+ Register r = destination.AsRegisterPairLow<Register>();
+ __ LoadFromOffset(kLoadDoubleword, r, SP, off);
+ }
+ } else if (destination.IsFpuRegister()) {
+ if (source.IsRegister()) {
+ DCHECK(!Primitive::Is64BitType(dst_type));
+ __ Mtc1(source.AsRegister<Register>(), destination.AsFpuRegister<FRegister>());
+ } else if (source.IsRegisterPair()) {
+ DCHECK(Primitive::Is64BitType(dst_type));
+ FRegister dst = destination.AsFpuRegister<FRegister>();
+ Register src_high = source.AsRegisterPairHigh<Register>();
+ Register src_low = source.AsRegisterPairLow<Register>();
+ __ Mtc1(src_low, dst);
+ __ MoveToFpuHigh(src_high, dst);
+ } else if (source.IsFpuRegister()) {
+ if (Primitive::Is64BitType(dst_type)) {
+ __ MovD(destination.AsFpuRegister<FRegister>(), source.AsFpuRegister<FRegister>());
+ } else {
+ DCHECK_EQ(dst_type, Primitive::kPrimFloat);
+ __ MovS(destination.AsFpuRegister<FRegister>(), source.AsFpuRegister<FRegister>());
+ }
+ } else if (source.IsDoubleStackSlot()) {
+ DCHECK(Primitive::Is64BitType(dst_type));
+ __ LoadDFromOffset(destination.AsFpuRegister<FRegister>(), SP, source.GetStackIndex());
+ } else {
+ DCHECK(!Primitive::Is64BitType(dst_type));
+ DCHECK(source.IsStackSlot()) << "Cannot move from " << source << " to " << destination;
+ __ LoadSFromOffset(destination.AsFpuRegister<FRegister>(), SP, source.GetStackIndex());
+ }
+ } else if (destination.IsDoubleStackSlot()) {
+ int32_t dst_offset = destination.GetStackIndex();
+ if (source.IsRegisterPair()) {
+ __ StoreToOffset(kStoreDoubleword, source.AsRegisterPairLow<Register>(), SP, dst_offset);
+ } else if (source.IsFpuRegister()) {
+ __ StoreDToOffset(source.AsFpuRegister<FRegister>(), SP, dst_offset);
+ } else {
+ DCHECK(source.IsDoubleStackSlot()) << "Cannot move from " << source << " to " << destination;
+ __ LoadFromOffset(kLoadWord, TMP, SP, source.GetStackIndex());
+ __ StoreToOffset(kStoreWord, TMP, SP, dst_offset);
+ __ LoadFromOffset(kLoadWord, TMP, SP, source.GetStackIndex() + 4);
+ __ StoreToOffset(kStoreWord, TMP, SP, dst_offset + 4);
+ }
} else {
- DCHECK(source.IsDoubleStackSlot()) << "Cannot move from " << source << " to " << destination;
- __ LoadFromOffset(kLoadWord, TMP, SP, source.GetStackIndex());
- __ StoreToOffset(kStoreWord, TMP, SP, off);
- __ LoadFromOffset(kLoadWord, TMP, SP, source.GetStackIndex() + 4);
- __ StoreToOffset(kStoreWord, TMP, SP, off + 4);
+ DCHECK(destination.IsStackSlot()) << destination;
+ int32_t dst_offset = destination.GetStackIndex();
+ if (source.IsRegister()) {
+ __ StoreToOffset(kStoreWord, source.AsRegister<Register>(), SP, dst_offset);
+ } else if (source.IsFpuRegister()) {
+ __ StoreSToOffset(source.AsFpuRegister<FRegister>(), SP, dst_offset);
+ } else {
+ DCHECK(source.IsStackSlot()) << "Cannot move from " << source << " to " << destination;
+ __ LoadFromOffset(kLoadWord, TMP, SP, source.GetStackIndex());
+ __ StoreToOffset(kStoreWord, TMP, SP, dst_offset);
+ }
}
}
}
@@ -2285,7 +2277,7 @@ void InstructionCodeGeneratorMIPS::HandleShift(HBinaryOperation* instr) {
Register lhs_low = locations->InAt(0).AsRegisterPairLow<Register>();
if (use_imm) {
if (shift_value == 0) {
- codegen_->Move64(locations->Out(), locations->InAt(0));
+ codegen_->MoveLocation(locations->Out(), locations->InAt(0), type);
} else if (shift_value < kMipsBitsPerWord) {
if (has_ins_rotr) {
if (instr->IsShl()) {
diff --git a/compiler/optimizing/code_generator_mips.h b/compiler/optimizing/code_generator_mips.h
index e72e838dd9..4d73ad1cfb 100644
--- a/compiler/optimizing/code_generator_mips.h
+++ b/compiler/optimizing/code_generator_mips.h
@@ -368,8 +368,6 @@ class CodeGeneratorMIPS : public CodeGenerator {
void Bind(HBasicBlock* block) OVERRIDE;
- void Move32(Location destination, Location source);
- void Move64(Location destination, Location source);
void MoveConstant(Location location, HConstant* c);
size_t GetWordSize() const OVERRIDE { return kMipsWordSize; }
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index c0ec58f824..f35aace3a9 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -373,21 +373,23 @@ bool InductionVarRange::IsFinite(HLoopInformation* loop, /*out*/ int64_t* tc) co
bool InductionVarRange::IsUnitStride(HInstruction* context,
HInstruction* instruction,
+ HGraph* graph,
/*out*/ HInstruction** offset) const {
HLoopInformation* loop = nullptr;
HInductionVarAnalysis::InductionInfo* info = nullptr;
HInductionVarAnalysis::InductionInfo* trip = nullptr;
if (HasInductionInfo(context, instruction, &loop, &info, &trip)) {
if (info->induction_class == HInductionVarAnalysis::kLinear &&
- info->op_b->operation == HInductionVarAnalysis::kFetch &&
!HInductionVarAnalysis::IsNarrowingLinear(info)) {
int64_t stride_value = 0;
if (IsConstant(info->op_a, kExact, &stride_value) && stride_value == 1) {
int64_t off_value = 0;
- if (IsConstant(info->op_b, kExact, &off_value) && off_value == 0) {
- *offset = nullptr;
- } else {
+ if (IsConstant(info->op_b, kExact, &off_value)) {
+ *offset = graph->GetConstant(info->op_b->type, off_value);
+ } else if (info->op_b->operation == HInductionVarAnalysis::kFetch) {
*offset = info->op_b->fetch;
+ } else {
+ return false;
}
return true;
}
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index a8ee829d08..ab1772bf15 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -163,6 +163,7 @@ class InductionVarRange {
*/
bool IsUnitStride(HInstruction* context,
HInstruction* instruction,
+ HGraph* graph,
/*out*/ HInstruction** offset) const;
/**
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index d01d3146fc..67d2093829 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -770,8 +770,8 @@ TEST_F(InductionVarRangeTest, ConstantTripCountUp) {
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(1000, tc);
HInstruction* offset = nullptr;
- EXPECT_TRUE(range_.IsUnitStride(phi, phi, &offset));
- EXPECT_TRUE(offset == nullptr);
+ EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset));
+ ExpectInt(0, offset);
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
@@ -826,7 +826,7 @@ TEST_F(InductionVarRangeTest, ConstantTripCountDown) {
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(1000, tc);
HInstruction* offset = nullptr;
- EXPECT_FALSE(range_.IsUnitStride(phi, phi, &offset));
+ EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset));
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
@@ -908,8 +908,8 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountUp) {
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(0, tc); // unknown
HInstruction* offset = nullptr;
- EXPECT_TRUE(range_.IsUnitStride(phi, phi, &offset));
- EXPECT_TRUE(offset == nullptr);
+ EXPECT_TRUE(range_.IsUnitStride(phi, phi, graph_, &offset));
+ ExpectInt(0, offset);
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
@@ -994,7 +994,7 @@ TEST_F(InductionVarRangeTest, SymbolicTripCountDown) {
EXPECT_TRUE(range_.IsFinite(loop_header_->GetLoopInformation(), &tc));
EXPECT_EQ(0, tc); // unknown
HInstruction* offset = nullptr;
- EXPECT_FALSE(range_.IsUnitStride(phi, phi, &offset));
+ EXPECT_FALSE(range_.IsUnitStride(phi, phi, graph_, &offset));
HInstruction* tce = range_.GenerateTripCount(
loop_header_->GetLoopInformation(), graph_, loop_preheader_);
ASSERT_TRUE(tce != nullptr);
diff --git a/compiler/optimizing/load_store_analysis.cc b/compiler/optimizing/load_store_analysis.cc
index f2ee345c8c..5a8ac59195 100644
--- a/compiler/optimizing/load_store_analysis.cc
+++ b/compiler/optimizing/load_store_analysis.cc
@@ -22,6 +22,117 @@ namespace art {
// The number of heap locations for most of the methods stays below this threshold.
constexpr size_t kMaxNumberOfHeapLocations = 32;
+// Check if array indices array[idx1 +/- CONST] and array[idx2] MAY alias.
+static bool BinaryOpAndIndexMayAlias(const HBinaryOperation* idx1, const HInstruction* idx2) {
+ DCHECK(idx1 != nullptr);
+ DCHECK(idx2 != nullptr);
+
+ if (!idx1->IsAdd() && !idx1->IsSub()) {
+ // We currently only support Add and Sub operations.
+ return true;
+ }
+
+ HConstant* cst = idx1->GetConstantRight();
+ if (cst == nullptr || cst->IsArithmeticZero()) {
+ return true;
+ }
+
+ if (idx1->GetLeastConstantLeft() == idx2) {
+ // for example, array[idx1 + 1] and array[idx1]
+ return false;
+ }
+
+ return true;
+}
+
+// Check if Add and Sub MAY alias when used as indices in arrays.
+static bool BinaryOpsMayAlias(const HBinaryOperation* idx1, const HBinaryOperation* idx2) {
+ DCHECK(idx1!= nullptr);
+ DCHECK(idx2 != nullptr);
+
+ HConstant* idx1_cst = idx1->GetConstantRight();
+ HInstruction* idx1_other = idx1->GetLeastConstantLeft();
+ HConstant* idx2_cst = idx2->GetConstantRight();
+ HInstruction* idx2_other = idx2->GetLeastConstantLeft();
+
+ if (idx1_cst == nullptr || idx1_other == nullptr ||
+ idx2_cst == nullptr || idx2_other == nullptr) {
+ // We only analyze patterns like [i +/- CONST].
+ return true;
+ }
+
+ if (idx1_other != idx2_other) {
+ // For example, [j+1] and [k+1] MAY alias.
+ return true;
+ }
+
+ if ((idx1->IsAdd() && idx2->IsAdd()) ||
+ (idx1->IsSub() && idx2->IsSub())) {
+ return idx1_cst->AsIntConstant()->GetValue() == idx2_cst->AsIntConstant()->GetValue();
+ }
+
+ if ((idx1->IsAdd() && idx2->IsSub()) ||
+ (idx1->IsSub() && idx2->IsAdd())) {
+ // [i + CONST1] and [i - CONST2] MAY alias iff CONST1 == -CONST2.
+ // By checking CONST1 == -CONST2, following cases are handled:
+ // - Zero constants case [i+0] and [i-0] is handled.
+ // - Overflow cases are handled, for example:
+ // [i+0x80000000] and [i-0x80000000];
+ // [i+0x10] and [i-0xFFFFFFF0].
+ // - Other cases [i+CONST1] and [i-CONST2] without any overflow is handled.
+ return idx1_cst->AsIntConstant()->GetValue() == -(idx2_cst->AsIntConstant()->GetValue());
+ }
+
+ // All other cases, MAY alias.
+ return true;
+}
+
+// The following array index cases are handled:
+// [i] and [i]
+// [CONST1] and [CONST2]
+// [i] and [i+CONST]
+// [i] and [i-CONST]
+// [i+CONST1] and [i+CONST2]
+// [i-CONST1] and [i-CONST2]
+// [i+CONST1] and [i-CONST2]
+// [i-CONST1] and [i+CONST2]
+// For other complicated cases, we rely on other passes like GVN and simpilfier
+// to optimize these cases before this pass.
+// For example: [i+j+k+10] and [i+k+10+j] shall be optimized to [i7+10] and [i7+10].
+bool HeapLocationCollector::CanArrayIndicesAlias(const HInstruction* idx1,
+ const HInstruction* idx2) const {
+ DCHECK(idx1 != nullptr);
+ DCHECK(idx2 != nullptr);
+
+ if (idx1 == idx2) {
+ // [i] and [i]
+ return true;
+ }
+ if (idx1->IsIntConstant() && idx2->IsIntConstant()) {
+ // [CONST1] and [CONST2]
+ return idx1->AsIntConstant()->GetValue() == idx2->AsIntConstant()->GetValue();
+ }
+
+ if (idx1->IsBinaryOperation() && !BinaryOpAndIndexMayAlias(idx1->AsBinaryOperation(), idx2)) {
+ // [i] and [i+/-CONST]
+ return false;
+ }
+ if (idx2->IsBinaryOperation() && !BinaryOpAndIndexMayAlias(idx2->AsBinaryOperation(), idx1)) {
+ // [i+/-CONST] and [i]
+ return false;
+ }
+
+ if (idx1->IsBinaryOperation() && idx2->IsBinaryOperation()) {
+ // [i+/-CONST1] and [i+/-CONST2]
+ if (!BinaryOpsMayAlias(idx1->AsBinaryOperation(), idx2->AsBinaryOperation())) {
+ return false;
+ }
+ }
+
+ // By default, MAY alias.
+ return true;
+}
+
void LoadStoreAnalysis::Run() {
for (HBasicBlock* block : graph_->GetReversePostOrder()) {
heap_location_collector_.VisitBasicBlock(block);
diff --git a/compiler/optimizing/load_store_analysis.h b/compiler/optimizing/load_store_analysis.h
index 4e940f30bf..86fb8e0165 100644
--- a/compiler/optimizing/load_store_analysis.h
+++ b/compiler/optimizing/load_store_analysis.h
@@ -214,6 +214,17 @@ class HeapLocationCollector : public HGraphVisitor {
return nullptr;
}
+ size_t GetArrayAccessHeapLocation(HInstruction* array, HInstruction* index) const {
+ DCHECK(array != nullptr);
+ DCHECK(index != nullptr);
+ HInstruction* original_ref = HuntForOriginalReference(array);
+ ReferenceInfo* ref_info = FindReferenceInfoOf(original_ref);
+ return FindHeapLocationIndex(ref_info,
+ HeapLocation::kInvalidFieldOffset,
+ index,
+ HeapLocation::kDeclaringClassDefIndexForArrays);
+ }
+
bool HasHeapStores() const {
return has_heap_stores_;
}
@@ -300,6 +311,8 @@ class HeapLocationCollector : public HGraphVisitor {
return true;
}
+ bool CanArrayIndicesAlias(const HInstruction* i1, const HInstruction* i2) const;
+
// `index1` and `index2` are indices in the array of collected heap locations.
// Returns the position in the bit vector that tracks whether the two heap
// locations may alias.
@@ -336,12 +349,7 @@ class HeapLocationCollector : public HGraphVisitor {
if (loc1->IsArrayElement() && loc2->IsArrayElement()) {
HInstruction* array_index1 = loc1->GetIndex();
HInstruction* array_index2 = loc2->GetIndex();
- DCHECK(array_index1 != nullptr);
- DCHECK(array_index2 != nullptr);
- if (array_index1->IsIntConstant() &&
- array_index2->IsIntConstant() &&
- array_index1->AsIntConstant()->GetValue() != array_index2->AsIntConstant()->GetValue()) {
- // Different constant indices do not alias.
+ if (!CanArrayIndicesAlias(array_index1, array_index2)) {
return false;
}
ReferenceInfo* ref_info = loc1->GetReferenceInfo();
diff --git a/compiler/optimizing/load_store_analysis_test.cc b/compiler/optimizing/load_store_analysis_test.cc
index 24187777f6..81344b52f6 100644
--- a/compiler/optimizing/load_store_analysis_test.cc
+++ b/compiler/optimizing/load_store_analysis_test.cc
@@ -184,4 +184,198 @@ TEST_F(LoadStoreAnalysisTest, FieldHeapLocations) {
ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
}
+TEST_F(LoadStoreAnalysisTest, ArrayIndexAliasingTest) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ graph_->BuildDominatorTree();
+
+ HInstruction* array = new (&allocator_) HParameterValue(
+ graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
+ HInstruction* index = new (&allocator_) HParameterValue(
+ graph_->GetDexFile(), dex::TypeIndex(1), 1, Primitive::kPrimInt);
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c_neg1 = graph_->GetIntConstant(-1);
+ HInstruction* add0 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c0);
+ HInstruction* add1 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c1);
+ HInstruction* sub0 = new (&allocator_) HSub(Primitive::kPrimInt, index, c0);
+ HInstruction* sub1 = new (&allocator_) HSub(Primitive::kPrimInt, index, c1);
+ HInstruction* sub_neg1 = new (&allocator_) HSub(Primitive::kPrimInt, index, c_neg1);
+ HInstruction* rev_sub1 = new (&allocator_) HSub(Primitive::kPrimInt, c1, index);
+ HInstruction* arr_set1 = new (&allocator_) HArraySet(array, c0, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set2 = new (&allocator_) HArraySet(array, c1, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set3 = new (&allocator_) HArraySet(array, add0, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set4 = new (&allocator_) HArraySet(array, add1, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set5 = new (&allocator_) HArraySet(array, sub0, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set6 = new (&allocator_) HArraySet(array, sub1, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set7 = new (&allocator_) HArraySet(array, rev_sub1, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set8 = new (&allocator_) HArraySet(array, sub_neg1, c0, Primitive::kPrimInt, 0);
+
+ entry->AddInstruction(array);
+ entry->AddInstruction(index);
+ entry->AddInstruction(add0);
+ entry->AddInstruction(add1);
+ entry->AddInstruction(sub0);
+ entry->AddInstruction(sub1);
+ entry->AddInstruction(sub_neg1);
+ entry->AddInstruction(rev_sub1);
+
+ entry->AddInstruction(arr_set1); // array[0] = c0
+ entry->AddInstruction(arr_set2); // array[1] = c0
+ entry->AddInstruction(arr_set3); // array[i+0] = c0
+ entry->AddInstruction(arr_set4); // array[i+1] = c0
+ entry->AddInstruction(arr_set5); // array[i-0] = c0
+ entry->AddInstruction(arr_set6); // array[i-1] = c0
+ entry->AddInstruction(arr_set7); // array[1-i] = c0
+ entry->AddInstruction(arr_set8); // array[i-(-1)] = c0
+
+ LoadStoreAnalysis lsa(graph_);
+ lsa.Run();
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+
+ // LSA/HeapLocationCollector should see those ArrayGet instructions.
+ ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
+ ASSERT_TRUE(heap_location_collector.HasHeapStores());
+
+ // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
+ size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
+ size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
+
+ // Test alias: array[0] and array[1]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, c0);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, c1);
+ ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Test alias: array[i+0] and array[i-0]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add0);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub0);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Test alias: array[i+1] and array[i-1]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add1);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub1);
+ ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Test alias: array[i+1] and array[1-i]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add1);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, rev_sub1);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Test alias: array[i+1] and array[i-(-1)]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add1);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_neg1);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+}
+
+TEST_F(LoadStoreAnalysisTest, ArrayIndexCalculationOverflowTest) {
+ HBasicBlock* entry = new (&allocator_) HBasicBlock(graph_);
+ graph_->AddBlock(entry);
+ graph_->SetEntryBlock(entry);
+ graph_->BuildDominatorTree();
+
+ HInstruction* array = new (&allocator_) HParameterValue(
+ graph_->GetDexFile(), dex::TypeIndex(0), 0, Primitive::kPrimNot);
+ HInstruction* index = new (&allocator_) HParameterValue(
+ graph_->GetDexFile(), dex::TypeIndex(1), 1, Primitive::kPrimInt);
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c_0x80000000 = graph_->GetIntConstant(0x80000000);
+ HInstruction* c_0x10 = graph_->GetIntConstant(0x10);
+ HInstruction* c_0xFFFFFFF0 = graph_->GetIntConstant(0xFFFFFFF0);
+ HInstruction* c_0x7FFFFFFF = graph_->GetIntConstant(0x7FFFFFFF);
+ HInstruction* c_0x80000001 = graph_->GetIntConstant(0x80000001);
+
+ // `index+0x80000000` and `index-0x80000000` array indices MAY alias.
+ HInstruction* add_0x80000000 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c_0x80000000);
+ HInstruction* sub_0x80000000 = new (&allocator_) HSub(Primitive::kPrimInt, index, c_0x80000000);
+ HInstruction* arr_set_1 = new (&allocator_) HArraySet(
+ array, add_0x80000000, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_2 = new (&allocator_) HArraySet(
+ array, sub_0x80000000, c0, Primitive::kPrimInt, 0);
+
+ // `index+0x10` and `index-0xFFFFFFF0` array indices MAY alias.
+ HInstruction* add_0x10 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c_0x10);
+ HInstruction* sub_0xFFFFFFF0 = new (&allocator_) HSub(Primitive::kPrimInt, index, c_0xFFFFFFF0);
+ HInstruction* arr_set_3 = new (&allocator_) HArraySet(
+ array, add_0x10, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_4 = new (&allocator_) HArraySet(
+ array, sub_0xFFFFFFF0, c0, Primitive::kPrimInt, 0);
+
+ // `index+0x7FFFFFFF` and `index-0x80000001` array indices MAY alias.
+ HInstruction* add_0x7FFFFFFF = new (&allocator_) HAdd(Primitive::kPrimInt, index, c_0x7FFFFFFF);
+ HInstruction* sub_0x80000001 = new (&allocator_) HSub(Primitive::kPrimInt, index, c_0x80000001);
+ HInstruction* arr_set_5 = new (&allocator_) HArraySet(
+ array, add_0x7FFFFFFF, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_6 = new (&allocator_) HArraySet(
+ array, sub_0x80000001, c0, Primitive::kPrimInt, 0);
+
+ // `index+0` and `index-0` array indices MAY alias.
+ HInstruction* add_0 = new (&allocator_) HAdd(Primitive::kPrimInt, index, c0);
+ HInstruction* sub_0 = new (&allocator_) HSub(Primitive::kPrimInt, index, c0);
+ HInstruction* arr_set_7 = new (&allocator_) HArraySet(array, add_0, c0, Primitive::kPrimInt, 0);
+ HInstruction* arr_set_8 = new (&allocator_) HArraySet(array, sub_0, c0, Primitive::kPrimInt, 0);
+
+ entry->AddInstruction(array);
+ entry->AddInstruction(index);
+ entry->AddInstruction(add_0x80000000);
+ entry->AddInstruction(sub_0x80000000);
+ entry->AddInstruction(add_0x10);
+ entry->AddInstruction(sub_0xFFFFFFF0);
+ entry->AddInstruction(add_0x7FFFFFFF);
+ entry->AddInstruction(sub_0x80000001);
+ entry->AddInstruction(add_0);
+ entry->AddInstruction(sub_0);
+ entry->AddInstruction(arr_set_1);
+ entry->AddInstruction(arr_set_2);
+ entry->AddInstruction(arr_set_3);
+ entry->AddInstruction(arr_set_4);
+ entry->AddInstruction(arr_set_5);
+ entry->AddInstruction(arr_set_6);
+ entry->AddInstruction(arr_set_7);
+ entry->AddInstruction(arr_set_8);
+
+ LoadStoreAnalysis lsa(graph_);
+ lsa.Run();
+ const HeapLocationCollector& heap_location_collector = lsa.GetHeapLocationCollector();
+
+ // LSA/HeapLocationCollector should see those ArrayGet instructions.
+ ASSERT_EQ(heap_location_collector.GetNumberOfHeapLocations(), 8U);
+ ASSERT_TRUE(heap_location_collector.HasHeapStores());
+
+ // Test queries on HeapLocationCollector's aliasing matrix after load store analysis.
+ size_t loc1 = HeapLocationCollector::kHeapLocationNotFound;
+ size_t loc2 = HeapLocationCollector::kHeapLocationNotFound;
+
+ // Test alias: array[i+0x80000000] and array[i-0x80000000]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0x80000000);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000000);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Test alias: array[i+0x10] and array[i-0xFFFFFFF0]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0x10);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0xFFFFFFF0);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Test alias: array[i+0x7FFFFFFF] and array[i-0x80000001]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0x7FFFFFFF);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000001);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Test alias: array[i+0] and array[i-0]
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0);
+ ASSERT_TRUE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Should not alias:
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000000);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000001);
+ ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
+
+ // Should not alias:
+ loc1 = heap_location_collector.GetArrayAccessHeapLocation(array, add_0);
+ loc2 = heap_location_collector.GetArrayAccessHeapLocation(array, sub_0x80000000);
+ ASSERT_FALSE(heap_location_collector.MayAlias(loc1, loc2));
+}
+
} // namespace art
diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index 32f40024d3..b61d7b80d1 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -620,12 +620,15 @@ bool HLoopOptimization::ShouldVectorize(LoopNode* node, HBasicBlock* block, int6
// Conservatively assume a potential loop-carried data dependence otherwise, avoided by
// generating an explicit a != b disambiguation runtime test on the two references.
if (x != y) {
- // For now, we reject after one test to avoid excessive overhead.
- if (vector_runtime_test_a_ != nullptr) {
- return false;
+ // To avoid excessive overhead, we only accept one a != b test.
+ if (vector_runtime_test_a_ == nullptr) {
+ // First test found.
+ vector_runtime_test_a_ = a;
+ vector_runtime_test_b_ = b;
+ } else if ((vector_runtime_test_a_ != a || vector_runtime_test_b_ != b) &&
+ (vector_runtime_test_a_ != b || vector_runtime_test_b_ != a)) {
+ return false; // second test would be needed
}
- vector_runtime_test_a_ = a;
- vector_runtime_test_b_ = b;
}
}
}
@@ -842,7 +845,7 @@ bool HLoopOptimization::VectorizeDef(LoopNode* node,
HInstruction* offset = nullptr;
if (TrySetVectorType(type, &restrictions) &&
node->loop_info->IsDefinedOutOfTheLoop(base) &&
- induction_range_.IsUnitStride(instruction, index, &offset) &&
+ induction_range_.IsUnitStride(instruction, index, graph_, &offset) &&
VectorizeUse(node, value, generate_code, type, restrictions)) {
if (generate_code) {
GenerateVecSub(index, offset);
@@ -900,7 +903,7 @@ bool HLoopOptimization::VectorizeUse(LoopNode* node,
HInstruction* offset = nullptr;
if (type == instruction->GetType() &&
node->loop_info->IsDefinedOutOfTheLoop(base) &&
- induction_range_.IsUnitStride(instruction, index, &offset)) {
+ induction_range_.IsUnitStride(instruction, index, graph_, &offset)) {
if (generate_code) {
GenerateVecSub(index, offset);
GenerateVecMem(instruction, vector_map_->Get(index), nullptr, offset, type);
@@ -1216,7 +1219,8 @@ void HLoopOptimization::GenerateVecInv(HInstruction* org, Primitive::Type type)
void HLoopOptimization::GenerateVecSub(HInstruction* org, HInstruction* offset) {
if (vector_map_->find(org) == vector_map_->end()) {
HInstruction* subscript = vector_index_;
- if (offset != nullptr) {
+ int64_t value = 0;
+ if (!IsInt64AndGet(offset, &value) || value != 0) {
subscript = new (global_allocator_) HAdd(Primitive::kPrimInt, subscript, offset);
if (org->IsPhi()) {
Insert(vector_body_, subscript); // lacks layout placeholder
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index b21c4a5aa7..5e072cdb67 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -421,7 +421,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
void SimplifyLoop(HBasicBlock* header);
int32_t GetNextInstructionId() {
- DCHECK_NE(current_instruction_id_, INT32_MAX);
+ CHECK_NE(current_instruction_id_, INT32_MAX);
return current_instruction_id_++;
}
@@ -430,7 +430,7 @@ class HGraph : public ArenaObject<kArenaAllocGraph> {
}
void SetCurrentInstructionId(int32_t id) {
- DCHECK_GE(id, current_instruction_id_);
+ CHECK_GE(id, current_instruction_id_);
current_instruction_id_ = id;
}
diff --git a/compiler/optimizing/scheduler.cc b/compiler/optimizing/scheduler.cc
index 320f01a727..147fa1c05a 100644
--- a/compiler/optimizing/scheduler.cc
+++ b/compiler/optimizing/scheduler.cc
@@ -109,6 +109,10 @@ void SchedulingGraph::AddDependencies(HInstruction* instruction, bool is_schedul
// barrier depend on it.
for (HInstruction* other = instruction->GetNext(); other != nullptr; other = other->GetNext()) {
SchedulingNode* other_node = GetNode(other);
+ CHECK(other_node != nullptr)
+ << other->DebugName()
+ << " is in block " << other->GetBlock()->GetBlockId()
+ << ", and expected in block " << instruction->GetBlock()->GetBlockId();
bool other_is_barrier = other_node->IsSchedulingBarrier();
if (is_scheduling_barrier || other_is_barrier) {
AddOtherDependency(other_node, instruction_node);
@@ -377,6 +381,10 @@ void HScheduler::Schedule(HBasicBlock* block) {
scheduling_graph_.Clear();
for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* instruction = it.Current();
+ CHECK_EQ(instruction->GetBlock(), block)
+ << instruction->DebugName()
+ << " is in block " << instruction->GetBlock()->GetBlockId()
+ << ", and expected in block " << block->GetBlockId();
SchedulingNode* node = scheduling_graph_.AddNode(instruction, IsSchedulingBarrier(instruction));
CalculateLatency(node);
scheduling_nodes.push_back(node);
diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc
index 7b7495bf3b..185303bc8c 100644
--- a/compiler/optimizing/ssa_liveness_analysis.cc
+++ b/compiler/optimizing/ssa_liveness_analysis.cc
@@ -197,7 +197,7 @@ void SsaLivenessAnalysis::ComputeLiveRanges() {
HInstruction* instruction = environment->GetInstructionAt(i);
bool should_be_live = ShouldBeLiveForEnvironment(current, instruction);
if (should_be_live) {
- DCHECK(instruction->HasSsaIndex());
+ CHECK(instruction->HasSsaIndex()) << instruction->DebugName();
live_in->SetBit(instruction->GetSsaIndex());
}
if (instruction != nullptr) {
generated by cgit v1.2.3-59-g8ed1b (git 2.39.0) at 2026-01-05 23:04:55 +0000