Merge "Revert "Revert "Keep internal stack trace methods declaring classes live"""
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index 42b3541..960f4d9 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -410,7 +410,7 @@
* of an existing value range, NewArray or a loop phi corresponding to an
* incrementing/decrementing array index (MonotonicValueRange).
*/
-class ValueRange : public ArenaObject<kArenaAllocMisc> {
+class ValueRange : public ArenaObject<kArenaAllocBoundsCheckElimination> {
public:
ValueRange(ArenaAllocator* allocator, ValueBound lower, ValueBound upper)
: allocator_(allocator), lower_(lower), upper_(upper) {}
@@ -1112,7 +1112,14 @@
BCEVisitor(HGraph* graph, HInductionVarAnalysis* induction_analysis)
: HGraphVisitor(graph),
- maps_(graph->GetBlocks().size()),
+ maps_(graph->GetBlocks().size(),
+ ArenaSafeMap<int, ValueRange*>(
+ std::less<int>(),
+ graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
+ graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
+ first_constant_index_bounds_check_map_(
+ std::less<int>(),
+ graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
need_to_revisit_block_(false),
initial_block_size_(graph->GetBlocks().size()),
induction_range_(induction_analysis) {}
@@ -1137,14 +1144,9 @@
// Added blocks don't keep value ranges.
return nullptr;
}
- int block_id = basic_block->GetBlockId();
- if (maps_.at(block_id) == nullptr) {
- std::unique_ptr<ArenaSafeMap<int, ValueRange*>> map(
- new ArenaSafeMap<int, ValueRange*>(
- std::less<int>(), GetGraph()->GetArena()->Adapter()));
- maps_.at(block_id) = std::move(map);
- }
- return maps_.at(block_id).get();
+ uint32_t block_id = basic_block->GetBlockId();
+ DCHECK_LT(block_id, maps_.size());
+ return &maps_[block_id];
}
// Traverse up the dominator tree to look for value range info.
@@ -1842,11 +1844,11 @@
}
}
- std::vector<std::unique_ptr<ArenaSafeMap<int, ValueRange*>>> maps_;
+ ArenaVector<ArenaSafeMap<int, ValueRange*>> maps_;
// Map an HArrayLength instruction's id to the first HBoundsCheck instruction in
// a block that checks a constant index against that HArrayLength.
- SafeMap<int, HBoundsCheck*> first_constant_index_bounds_check_map_;
+ ArenaSafeMap<int, HBoundsCheck*> first_constant_index_bounds_check_map_;
// For the block, there is at least one HArrayLength instruction for which there
// is more than one bounds check instruction with constant indexing. And it's
diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc
index 7ae405a..cb36f62 100644
--- a/compiler/optimizing/builder.cc
+++ b/compiler/optimizing/builder.cc
@@ -324,7 +324,7 @@
// Keep a map of all try blocks and their respective TryItems. We do not use
// the block's pointer but rather its id to ensure deterministic iteration.
ArenaSafeMap<uint32_t, const DexFile::TryItem*> try_block_info(
- std::less<uint32_t>(), arena_->Adapter());
+ std::less<uint32_t>(), arena_->Adapter(kArenaAllocGraphBuilder));
// Obtain TryItem information for blocks with throwing instructions, and split
// blocks which are both try & catch to simplify the graph.
diff --git a/compiler/optimizing/code_generator.h b/compiler/optimizing/code_generator.h
index b58a3ff..5da0e59 100644
--- a/compiler/optimizing/code_generator.h
+++ b/compiler/optimizing/code_generator.h
@@ -425,9 +425,12 @@
core_spill_mask_(0),
fpu_spill_mask_(0),
first_register_slot_in_slow_path_(0),
- blocked_core_registers_(graph->GetArena()->AllocArray<bool>(number_of_core_registers)),
- blocked_fpu_registers_(graph->GetArena()->AllocArray<bool>(number_of_fpu_registers)),
- blocked_register_pairs_(graph->GetArena()->AllocArray<bool>(number_of_register_pairs)),
+ blocked_core_registers_(graph->GetArena()->AllocArray<bool>(number_of_core_registers,
+ kArenaAllocCodeGenerator)),
+ blocked_fpu_registers_(graph->GetArena()->AllocArray<bool>(number_of_fpu_registers,
+ kArenaAllocCodeGenerator)),
+ blocked_register_pairs_(graph->GetArena()->AllocArray<bool>(number_of_register_pairs,
+ kArenaAllocCodeGenerator)),
number_of_core_registers_(number_of_core_registers),
number_of_fpu_registers_(number_of_fpu_registers),
number_of_register_pairs_(number_of_register_pairs),
diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc
index da7a675..c775e03 100644
--- a/compiler/optimizing/code_generator_arm.cc
+++ b/compiler/optimizing/code_generator_arm.cc
@@ -428,8 +428,12 @@
kNumberOfRegisterPairs,
ComputeRegisterMask(reinterpret_cast<const int*>(kCoreCalleeSaves),
arraysize(kCoreCalleeSaves)),
- ComputeRegisterMask(reinterpret_cast<const int*>(kFpuCalleeSaves),
- arraysize(kFpuCalleeSaves)),
+ graph->IsDebuggable()
+ // If the graph is debuggable, we need to save the fpu registers ourselves,
+ // as the stubs do not do it.
+ ? 0
+ : ComputeRegisterMask(reinterpret_cast<const int*>(kFpuCalleeSaves),
+ arraysize(kFpuCalleeSaves)),
compiler_options,
stats),
block_labels_(nullptr),
@@ -438,9 +442,11 @@
move_resolver_(graph->GetArena(), this),
assembler_(),
isa_features_(isa_features),
- method_patches_(MethodReferenceComparator(), graph->GetArena()->Adapter()),
- call_patches_(MethodReferenceComparator(), graph->GetArena()->Adapter()),
- relative_call_patches_(graph->GetArena()->Adapter()) {
+ method_patches_(MethodReferenceComparator(),
+ graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ call_patches_(MethodReferenceComparator(),
+ graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ relative_call_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)) {
// Always save the LR register to mimic Quick.
AddAllocatedRegister(Location::RegisterLocation(LR));
}
diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc
index 31900d5..70327af 100644
--- a/compiler/optimizing/code_generator_arm64.cc
+++ b/compiler/optimizing/code_generator_arm64.cc
@@ -119,8 +119,11 @@
CPURegList core_list = CPURegList(CPURegister::kRegister, kXRegSize,
register_set->GetCoreRegisters() & (~callee_saved_core_registers.list()));
- CPURegList fp_list = CPURegList(CPURegister::kFPRegister, kDRegSize,
- register_set->GetFloatingPointRegisters() & (~callee_saved_fp_registers.list()));
+ CPURegList fp_list = CPURegList(
+ CPURegister::kFPRegister,
+ kDRegSize,
+ register_set->GetFloatingPointRegisters()
+ & (~(codegen->GetGraph()->IsDebuggable() ? 0 : callee_saved_fp_registers.list())));
MacroAssembler* masm = down_cast<CodeGeneratorARM64*>(codegen)->GetVIXLAssembler();
UseScratchRegisterScope temps(masm);
@@ -534,7 +537,9 @@
kNumberOfAllocatableFPRegisters,
kNumberOfAllocatableRegisterPairs,
callee_saved_core_registers.list(),
- callee_saved_fp_registers.list(),
+ // If the graph is debuggable, we need to save the fpu registers ourselves,
+ // as the stubs do not do it.
+ graph->IsDebuggable() ? 0 : callee_saved_fp_registers.list(),
compiler_options,
stats),
block_labels_(nullptr),
@@ -542,11 +547,14 @@
instruction_visitor_(graph, this),
move_resolver_(graph->GetArena(), this),
isa_features_(isa_features),
- uint64_literals_(std::less<uint64_t>(), graph->GetArena()->Adapter()),
- method_patches_(MethodReferenceComparator(), graph->GetArena()->Adapter()),
- call_patches_(MethodReferenceComparator(), graph->GetArena()->Adapter()),
- relative_call_patches_(graph->GetArena()->Adapter()),
- pc_rel_dex_cache_patches_(graph->GetArena()->Adapter()) {
+ uint64_literals_(std::less<uint64_t>(),
+ graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ method_patches_(MethodReferenceComparator(),
+ graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ call_patches_(MethodReferenceComparator(),
+ graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ relative_call_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ pc_rel_dex_cache_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)) {
// Save the link register (containing the return address) to mimic Quick.
AddAllocatedRegister(LocationFrom(lr));
}
diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc
index 277f6b4..a47a95e 100644
--- a/compiler/optimizing/code_generator_x86.cc
+++ b/compiler/optimizing/code_generator_x86.cc
@@ -475,8 +475,8 @@
instruction_visitor_(graph, this),
move_resolver_(graph->GetArena(), this),
isa_features_(isa_features),
- method_patches_(graph->GetArena()->Adapter()),
- relative_call_patches_(graph->GetArena()->Adapter()) {
+ method_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ relative_call_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)) {
// Use a fake return address register to mimic Quick.
AddAllocatedRegister(Location::RegisterLocation(kFakeReturnRegister));
}
@@ -5623,7 +5623,7 @@
/**
* Class to handle late fixup of offsets into constant area.
*/
-class RIPFixup : public AssemblerFixup, public ArenaObject<kArenaAllocMisc> {
+class RIPFixup : public AssemblerFixup, public ArenaObject<kArenaAllocCodeGenerator> {
public:
RIPFixup(const CodeGeneratorX86& codegen, int offset)
: codegen_(codegen), offset_into_constant_area_(offset) {}
diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc
index 453c6fd..b845a27 100644
--- a/compiler/optimizing/code_generator_x86_64.cc
+++ b/compiler/optimizing/code_generator_x86_64.cc
@@ -626,9 +626,9 @@
move_resolver_(graph->GetArena(), this),
isa_features_(isa_features),
constant_area_start_(0),
- method_patches_(graph->GetArena()->Adapter()),
- relative_call_patches_(graph->GetArena()->Adapter()),
- pc_rel_dex_cache_patches_(graph->GetArena()->Adapter()) {
+ method_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ relative_call_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)),
+ pc_rel_dex_cache_patches_(graph->GetArena()->Adapter(kArenaAllocCodeGenerator)) {
AddAllocatedRegister(Location::RegisterLocation(kFakeReturnRegister));
}
@@ -5279,7 +5279,7 @@
/**
* Class to handle late fixup of offsets into constant area.
*/
-class RIPFixup : public AssemblerFixup, public ArenaObject<kArenaAllocMisc> {
+class RIPFixup : public AssemblerFixup, public ArenaObject<kArenaAllocCodeGenerator> {
public:
RIPFixup(const CodeGeneratorX86_64& codegen, int offset)
: codegen_(codegen), offset_into_constant_area_(offset) {}
diff --git a/compiler/optimizing/gvn.cc b/compiler/optimizing/gvn.cc
index 5050e15..7cf0617 100644
--- a/compiler/optimizing/gvn.cc
+++ b/compiler/optimizing/gvn.cc
@@ -39,7 +39,7 @@
explicit ValueSet(ArenaAllocator* allocator)
: allocator_(allocator),
num_buckets_(kMinimumNumberOfBuckets),
- buckets_(allocator->AllocArray<Node*>(num_buckets_)),
+ buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)),
buckets_owned_(allocator, num_buckets_, false),
num_entries_(0) {
// ArenaAllocator returns zeroed memory, so no need to set buckets to null.
@@ -52,7 +52,7 @@
ValueSet(ArenaAllocator* allocator, const ValueSet& to_copy)
: allocator_(allocator),
num_buckets_(to_copy.IdealBucketCount()),
- buckets_(allocator->AllocArray<Node*>(num_buckets_)),
+ buckets_(allocator->AllocArray<Node*>(num_buckets_, kArenaAllocGvn)),
buckets_owned_(allocator, num_buckets_, false),
num_entries_(to_copy.num_entries_) {
// ArenaAllocator returns zeroed memory, so entries of buckets_ and
diff --git a/compiler/optimizing/induction_var_analysis.cc b/compiler/optimizing/induction_var_analysis.cc
index 9fb4304..e5123de 100644
--- a/compiler/optimizing/induction_var_analysis.cc
+++ b/compiler/optimizing/induction_var_analysis.cc
@@ -74,11 +74,14 @@
HInductionVarAnalysis::HInductionVarAnalysis(HGraph* graph)
: HOptimization(graph, kInductionPassName),
global_depth_(0),
- stack_(graph->GetArena()->Adapter()),
- scc_(graph->GetArena()->Adapter()),
- map_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
- cycle_(std::less<HInstruction*>(), graph->GetArena()->Adapter()),
- induction_(std::less<HLoopInformation*>(), graph->GetArena()->Adapter()) {
+ stack_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
+ scc_(graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
+ map_(std::less<HInstruction*>(),
+ graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
+ cycle_(std::less<HInstruction*>(),
+ graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)),
+ induction_(std::less<HLoopInformation*>(),
+ graph->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)) {
}
void HInductionVarAnalysis::Run() {
@@ -228,7 +231,7 @@
// Rotate proper entry-phi to front.
if (size > 1) {
- ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter());
+ ArenaVector<HInstruction*> other(graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis));
RotateEntryPhiFirst(loop, &scc_, &other);
}
@@ -553,44 +556,33 @@
}
} else if (a->induction_class == kLinear && b->induction_class == kInvariant) {
// Analyze condition with induction at left-hand-side (e.g. i < U).
+ InductionInfo* lower_expr = a->op_b;
+ InductionInfo* upper_expr = b;
InductionInfo* stride = a->op_a;
- InductionInfo* lo_val = a->op_b;
- InductionInfo* hi_val = b;
- // Analyze stride (may be compound).
- InductionVarRange::Value v1 = InductionVarRange::GetVal(stride, nullptr, /* is_min */ true);
- InductionVarRange::Value v2 = InductionVarRange::GetVal(stride, nullptr, /* is_min */ false);
- if (v1.a_constant != 0 || v2.a_constant != 0 || v1.b_constant != v2.b_constant) {
+ int64_t stride_value = 0;
+ if (!IsIntAndGet(stride, &stride_value)) {
return;
}
- // Rewrite safe condition i != U with unit stride into i < U or i > U
- // (unit stride guarantees that the end condition is always reached).
- const int32_t stride_value = v1.b_constant;
- int64_t lo_value = 0;
- int64_t hi_value = 0;
- if (cmp == kCondNE && IsIntAndGet(lo_val, &lo_value) && IsIntAndGet(hi_val, &hi_value)) {
- if ((stride_value == +1 && lo_value < hi_value) ||
- (stride_value == -1 && lo_value > hi_value)) {
- cmp = stride_value > 0 ? kCondLT : kCondGT;
- }
+ // Rewrite condition i != U into i < U or i > U if end condition is reached exactly.
+ if (cmp == kCondNE && ((stride_value == +1 && IsTaken(lower_expr, upper_expr, kCondLT)) ||
+ (stride_value == -1 && IsTaken(lower_expr, upper_expr, kCondGT)))) {
+ cmp = stride_value > 0 ? kCondLT : kCondGT;
}
// Normalize a linear loop control with a nonzero stride:
// stride > 0, either i < U or i <= U
// stride < 0, either i > U or i >= U
- //
- // TODO: construct conditions for constant/symbolic safety of trip-count
- //
if ((stride_value > 0 && (cmp == kCondLT || cmp == kCondLE)) ||
(stride_value < 0 && (cmp == kCondGT || cmp == kCondGE))) {
- VisitTripCount(loop, lo_val, hi_val, stride, stride_value, type, cmp);
+ VisitTripCount(loop, lower_expr, upper_expr, stride, stride_value, type, cmp);
}
}
}
void HInductionVarAnalysis::VisitTripCount(HLoopInformation* loop,
- InductionInfo* lo_val,
- InductionInfo* hi_val,
+ InductionInfo* lower_expr,
+ InductionInfo* upper_expr,
InductionInfo* stride,
- int32_t stride_value,
+ int64_t stride_value,
Primitive::Type type,
IfCondition cmp) {
// Any loop of the general form:
@@ -604,30 +596,95 @@
// for (n = 0; n < TC; n++) // where TC = (U + S - L) / S
// .. L + S * n ..
//
- // NOTE: The TC (trip-count) expression is only valid when safe. Otherwise TC is 0
- // (or possibly infinite). Also, the expression assumes the loop does not have
- // early-exits. Otherwise, TC is an upper bound.
+ // taking the following into consideration:
//
- bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1;
+ // (1) Using the same precision, the TC (trip-count) expression should be interpreted as
+ // an unsigned entity, for example, as in the following loop that uses the full range:
+ // for (int i = INT_MIN; i < INT_MAX; i++) // TC = UINT_MAX
+ // (2) The TC is only valid if the loop is taken, otherwise TC = 0, as in:
+ // for (int i = 12; i < U; i++) // TC = 0 when U >= 12
+ // If this cannot be determined at compile-time, the TC is only valid within the
+ // loop-body proper, not the loop-header unless enforced with an explicit condition.
+ // (3) The TC is only valid if the loop is finite, otherwise TC has no value, as in:
+ // for (int i = 0; i <= U; i++) // TC = Inf when U = INT_MAX
+ // If this cannot be determined at compile-time, the TC is only valid when enforced
+ // with an explicit condition.
+ // (4) For loops which early-exits, the TC forms an upper bound, as in:
+ // for (int i = 0; i < 10 && ....; i++) // TC <= 10
+ const bool is_taken = IsTaken(lower_expr, upper_expr, cmp);
+ const bool is_finite = IsFinite(upper_expr, stride_value, type, cmp);
+ const bool cancels = (cmp == kCondLT || cmp == kCondGT) && std::abs(stride_value) == 1;
if (!cancels) {
// Convert exclusive integral inequality into inclusive integral inequality,
// viz. condition i < U is i <= U - 1 and condition i > U is i >= U + 1.
if (cmp == kCondLT) {
- hi_val = CreateInvariantOp(kSub, hi_val, CreateConstant(1, type));
+ upper_expr = CreateInvariantOp(kSub, upper_expr, CreateConstant(1, type));
} else if (cmp == kCondGT) {
- hi_val = CreateInvariantOp(kAdd, hi_val, CreateConstant(1, type));
+ upper_expr = CreateInvariantOp(kAdd, upper_expr, CreateConstant(1, type));
}
// Compensate for stride.
- hi_val = CreateInvariantOp(kAdd, hi_val, stride);
+ upper_expr = CreateInvariantOp(kAdd, upper_expr, stride);
}
-
+ InductionInfo* trip_count
+ = CreateInvariantOp(kDiv, CreateInvariantOp(kSub, upper_expr, lower_expr), stride);
// Assign the trip-count expression to the loop control. Clients that use the information
- // should be aware that the expression is only valid in the loop-body proper (when symbolically
- // safe), and not yet in the loop-header (unless constant safe). If the loop has any early exits,
- // the trip-count forms a conservative upper bound on the number of loop iterations.
- InductionInfo* trip_count =
- CreateInvariantOp(kDiv, CreateInvariantOp(kSub, hi_val, lo_val), stride);
- AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), trip_count);
+ // should be aware that the expression is only valid under the conditions listed above.
+ InductionOp tcKind = kTripCountInBodyUnsafe;
+ if (is_taken && is_finite) {
+ tcKind = kTripCountInLoop;
+ } else if (is_finite) {
+ tcKind = kTripCountInBody;
+ } else if (is_taken) {
+ tcKind = kTripCountInLoopUnsafe;
+ }
+ AssignInfo(loop, loop->GetHeader()->GetLastInstruction(), CreateTripCount(tcKind, trip_count));
+}
+
+bool HInductionVarAnalysis::IsTaken(InductionInfo* lower_expr,
+ InductionInfo* upper_expr,
+ IfCondition cmp) {
+ int64_t lower_value;
+ int64_t upper_value;
+ if (IsIntAndGet(lower_expr, &lower_value) && IsIntAndGet(upper_expr, &upper_value)) {
+ switch (cmp) {
+ case kCondLT: return lower_value < upper_value;
+ case kCondLE: return lower_value <= upper_value;
+ case kCondGT: return lower_value > upper_value;
+ case kCondGE: return lower_value >= upper_value;
+ case kCondEQ:
+ case kCondNE: LOG(FATAL) << "CONDITION UNREACHABLE";
+ }
+ }
+ return false; // not certain, may be untaken
+}
+
+bool HInductionVarAnalysis::IsFinite(InductionInfo* upper_expr,
+ int64_t stride_value,
+ Primitive::Type type,
+ IfCondition cmp) {
+ const int64_t min = type == Primitive::kPrimInt
+ ? std::numeric_limits<int32_t>::min()
+ : std::numeric_limits<int64_t>::min();
+ const int64_t max = type == Primitive::kPrimInt
+ ? std::numeric_limits<int32_t>::max()
+ : std::numeric_limits<int64_t>::max();
+ // Some rules under which it is certain at compile-time that the loop is finite.
+ int64_t value;
+ switch (cmp) {
+ case kCondLT:
+ return stride_value == 1 ||
+ (IsIntAndGet(upper_expr, &value) && value <= (max - stride_value + 1));
+ case kCondLE:
+ return (IsIntAndGet(upper_expr, &value) && value <= (max - stride_value));
+ case kCondGT:
+ return stride_value == -1 ||
+ (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value - 1));
+ case kCondGE:
+ return (IsIntAndGet(upper_expr, &value) && value >= (min - stride_value));
+ case kCondEQ:
+ case kCondNE: LOG(FATAL) << "CONDITION UNREACHABLE";
+ }
+ return false; // not certain, may be infinite
}
void HInductionVarAnalysis::AssignInfo(HLoopInformation* loop,
@@ -637,7 +694,8 @@
if (it == induction_.end()) {
it = induction_.Put(loop,
ArenaSafeMap<HInstruction*, InductionInfo*>(
- std::less<HInstruction*>(), graph_->GetArena()->Adapter()));
+ std::less<HInstruction*>(),
+ graph_->GetArena()->Adapter(kArenaAllocInductionVarAnalysis)));
}
it->second.Put(instruction, info);
}
@@ -744,13 +802,22 @@
}
bool HInductionVarAnalysis::IsIntAndGet(InductionInfo* info, int64_t* value) {
- if (info != nullptr && info->induction_class == kInvariant && info->operation == kFetch) {
- DCHECK(info->fetch);
- if (info->fetch->IsIntConstant()) {
- *value = info->fetch->AsIntConstant()->GetValue();
- return true;
- } else if (info->fetch->IsLongConstant()) {
- *value = info->fetch->AsLongConstant()->GetValue();
+ if (info != nullptr && info->induction_class == kInvariant) {
+ // A direct constant fetch.
+ if (info->operation == kFetch) {
+ DCHECK(info->fetch);
+ if (info->fetch->IsIntConstant()) {
+ *value = info->fetch->AsIntConstant()->GetValue();
+ return true;
+ } else if (info->fetch->IsLongConstant()) {
+ *value = info->fetch->AsLongConstant()->GetValue();
+ return true;
+ }
+ }
+ // Use range analysis to resolve compound values.
+ int32_t range_value;
+ if (InductionVarRange::GetConstant(info, &range_value)) {
+ *value = range_value;
return true;
}
}
@@ -778,6 +845,10 @@
inv += std::to_string(info->fetch->GetId()) + ":" + info->fetch->DebugName();
}
break;
+ case kTripCountInLoop: inv += "TC-loop:"; break;
+ case kTripCountInBody: inv += "TC-body:"; break;
+ case kTripCountInLoopUnsafe: inv += "TC-loop-unsafe:"; break;
+ case kTripCountInBodyUnsafe: inv += "TC-body-unsafe:"; break;
}
inv += InductionToString(info->op_b);
return inv + ")";
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 190a0db..7ab80cd 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -56,13 +56,20 @@
};
enum InductionOp {
- kNop, // no-operation: a true induction
+ // No-operation: a true induction.
+ kNop,
+ // Various invariant operations.
kAdd,
kSub,
kNeg,
kMul,
kDiv,
- kFetch
+ kFetch,
+ // Trip counts (valid in full loop or only body proper; unsafe implies loop may be infinite).
+ kTripCountInLoop,
+ kTripCountInBody,
+ kTripCountInLoopUnsafe,
+ kTripCountInBodyUnsafe
};
/**
@@ -77,8 +84,10 @@
* nop: a, then defined by b
* (4) periodic
* nop: a, then defined by b (repeated when exhausted)
+ * (5) trip-count:
+ * tc: defined by b
*/
- struct InductionInfo : public ArenaObject<kArenaAllocMisc> {
+ struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
InductionInfo(InductionClass ic,
InductionOp op,
InductionInfo* a,
@@ -110,6 +119,10 @@
return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f);
}
+ InductionInfo* CreateTripCount(InductionOp op, InductionInfo* b) {
+ return new (graph_->GetArena()) InductionInfo(kInvariant, op, nullptr, b, nullptr);
+ }
+
InductionInfo* CreateInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) {
DCHECK(a != nullptr && b != nullptr);
return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr);
@@ -151,12 +164,17 @@
Primitive::Type type,
IfCondition cmp);
void VisitTripCount(HLoopInformation* loop,
- InductionInfo* lo_val,
- InductionInfo* hi_val,
+ InductionInfo* lower_expr,
+ InductionInfo* upper_expr,
InductionInfo* stride,
- int32_t stride_value,
+ int64_t stride_value,
Primitive::Type type,
IfCondition cmp);
+ bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
+ bool IsFinite(InductionInfo* upper_expr,
+ int64_t stride_value,
+ Primitive::Type type,
+ IfCondition cmp);
// Assign and lookup.
void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
diff --git a/compiler/optimizing/induction_var_analysis_test.cc b/compiler/optimizing/induction_var_analysis_test.cc
index e519e77..20492e7 100644
--- a/compiler/optimizing/induction_var_analysis_test.cc
+++ b/compiler/optimizing/induction_var_analysis_test.cc
@@ -234,7 +234,8 @@
EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[0], 0).c_str());
// Trip-count.
- EXPECT_STREQ("(100)", GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
+ EXPECT_STREQ("(TC-loop:(100))",
+ GetInductionInfo(loop_header_[0]->GetLastInstruction(), 0).c_str());
}
TEST_F(InductionVarAnalysisTest, FindDerivedInduction) {
@@ -543,8 +544,10 @@
InductionVarRange range(iva_);
InductionVarRange::Value v_min = range.GetMinInduction(store, store->InputAt(1));
InductionVarRange::Value v_max = range.GetMaxInduction(store, store->InputAt(1));
+ ASSERT_TRUE(v_min.is_known);
EXPECT_EQ(0, v_min.a_constant);
EXPECT_EQ(1, v_min.b_constant);
+ ASSERT_TRUE(v_max.is_known);
EXPECT_EQ(0, v_max.a_constant);
EXPECT_EQ(199, v_max.b_constant);
}
@@ -579,7 +582,8 @@
}
EXPECT_STREQ("((1) * i + (1))", GetInductionInfo(increment_[d], d).c_str());
// Trip-count.
- EXPECT_STREQ("(100)", GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str());
+ EXPECT_STREQ("(TC-loop:(100))",
+ GetInductionInfo(loop_header_[d]->GetLastInstruction(), d).c_str());
}
}
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 119a80b..db12819 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -86,51 +86,36 @@
InductionVarRange::Value InductionVarRange::GetMinInduction(HInstruction* context,
HInstruction* instruction) {
- HLoopInformation* loop = context->GetBlock()->GetLoopInformation();
- if (loop != nullptr) {
- return GetVal(induction_analysis_->LookupInfo(loop, instruction),
- GetTripCount(loop, context), /* is_min */ true);
- }
- return Value();
+ return GetInduction(context, instruction, /* is_min */ true);
}
InductionVarRange::Value InductionVarRange::GetMaxInduction(HInstruction* context,
HInstruction* instruction) {
- HLoopInformation* loop = context->GetBlock()->GetLoopInformation();
- if (loop != nullptr) {
- return SimplifyMax(
- GetVal(induction_analysis_->LookupInfo(loop, instruction),
- GetTripCount(loop, context), /* is_min */ false));
- }
- return Value();
+ return SimplifyMax(GetInduction(context, instruction, /* is_min */ false));
}
//
// Private class methods.
//
-HInductionVarAnalysis::InductionInfo* InductionVarRange::GetTripCount(HLoopInformation* loop,
- HInstruction* context) {
- // The trip-count expression is only valid when the top-test is taken at least once,
- // that means, when the analyzed context appears outside the loop header itself.
- // Early-exit loops are okay, since in those cases, the trip-count is conservative.
- //
- // TODO: deal with runtime safety issues on TCs
- //
- if (context->GetBlock() != loop->GetHeader()) {
- HInductionVarAnalysis::InductionInfo* trip =
- induction_analysis_->LookupInfo(loop, loop->GetHeader()->GetLastInstruction());
- if (trip != nullptr) {
- // Wrap the trip-count representation in its own unusual NOP node, so that range analysis
- // is able to determine the [0, TC - 1] interval without having to construct constants.
- return induction_analysis_->CreateInvariantOp(HInductionVarAnalysis::kNop, trip, trip);
- }
+InductionVarRange::Value InductionVarRange::GetInduction(HInstruction* context,
+ HInstruction* instruction,
+ bool is_min) {
+ HLoopInformation* loop = context->GetBlock()->GetLoopInformation(); // closest enveloping loop
+ if (loop != nullptr) {
+ HBasicBlock* header = loop->GetHeader();
+ bool in_body = context->GetBlock() != header;
+ return GetVal(induction_analysis_->LookupInfo(loop, instruction),
+ induction_analysis_->LookupInfo(loop, header->GetLastInstruction()),
+ in_body,
+ is_min);
}
- return nullptr;
+ return Value();
}
InductionVarRange::Value InductionVarRange::GetFetch(HInstruction* instruction,
HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
bool is_min) {
// Detect constants and chase the fetch a bit deeper into the HIR tree, so that it becomes
// more likely range analysis will compare the same instructions as terminal nodes.
@@ -139,13 +124,13 @@
return Value(value);
} else if (instruction->IsAdd()) {
if (IsIntAndGet(instruction->InputAt(0), &value)) {
- return AddValue(Value(value), GetFetch(instruction->InputAt(1), trip, is_min));
+ return AddValue(Value(value), GetFetch(instruction->InputAt(1), trip, in_body, is_min));
} else if (IsIntAndGet(instruction->InputAt(1), &value)) {
- return AddValue(GetFetch(instruction->InputAt(0), trip, is_min), Value(value));
+ return AddValue(GetFetch(instruction->InputAt(0), trip, in_body, is_min), Value(value));
}
} else if (is_min) {
- // Special case for finding minimum: minimum of trip-count is 1.
- if (trip != nullptr && instruction == trip->op_b->fetch) {
+ // Special case for finding minimum: minimum of trip-count in loop-body is 1.
+ if (trip != nullptr && in_body && instruction == trip->op_b->fetch) {
return Value(1);
}
}
@@ -154,42 +139,53 @@
InductionVarRange::Value InductionVarRange::GetVal(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
bool is_min) {
if (info != nullptr) {
switch (info->induction_class) {
case HInductionVarAnalysis::kInvariant:
// Invariants.
switch (info->operation) {
- case HInductionVarAnalysis::kNop: // normalized: 0 or TC-1
- DCHECK_EQ(info->op_a, info->op_b);
- return is_min ? Value(0)
- : SubValue(GetVal(info->op_b, trip, is_min), Value(1));
case HInductionVarAnalysis::kAdd:
- return AddValue(GetVal(info->op_a, trip, is_min),
- GetVal(info->op_b, trip, is_min));
+ return AddValue(GetVal(info->op_a, trip, in_body, is_min),
+ GetVal(info->op_b, trip, in_body, is_min));
case HInductionVarAnalysis::kSub: // second reversed!
- return SubValue(GetVal(info->op_a, trip, is_min),
- GetVal(info->op_b, trip, !is_min));
+ return SubValue(GetVal(info->op_a, trip, in_body, is_min),
+ GetVal(info->op_b, trip, in_body, !is_min));
case HInductionVarAnalysis::kNeg: // second reversed!
return SubValue(Value(0),
- GetVal(info->op_b, trip, !is_min));
+ GetVal(info->op_b, trip, in_body, !is_min));
case HInductionVarAnalysis::kMul:
- return GetMul(info->op_a, info->op_b, trip, is_min);
+ return GetMul(info->op_a, info->op_b, trip, in_body, is_min);
case HInductionVarAnalysis::kDiv:
- return GetDiv(info->op_a, info->op_b, trip, is_min);
+ return GetDiv(info->op_a, info->op_b, trip, in_body, is_min);
case HInductionVarAnalysis::kFetch:
- return GetFetch(info->fetch, trip, is_min);
+ return GetFetch(info->fetch, trip, in_body, is_min);
+ case HInductionVarAnalysis::kTripCountInLoop:
+ if (!in_body) {
+ return is_min ? Value(0)
+ : GetVal(info->op_b, trip, in_body, is_min); // one extra!
+ }
+ FALLTHROUGH_INTENDED;
+ case HInductionVarAnalysis::kTripCountInBody:
+ if (in_body) {
+ return is_min ? Value(0)
+ : SubValue(GetVal(info->op_b, trip, in_body, is_min), Value(1));
+ }
+ break;
+ default:
+ break;
}
break;
case HInductionVarAnalysis::kLinear:
// Linear induction a * i + b, for normalized 0 <= i < TC.
- return AddValue(GetMul(info->op_a, trip, trip, is_min),
- GetVal(info->op_b, trip, is_min));
+ return AddValue(GetMul(info->op_a, trip, trip, in_body, is_min),
+ GetVal(info->op_b, trip, in_body, is_min));
case HInductionVarAnalysis::kWrapAround:
case HInductionVarAnalysis::kPeriodic:
// Merge values in the wrap-around/periodic.
- return MergeVal(GetVal(info->op_a, trip, is_min),
- GetVal(info->op_b, trip, is_min), is_min);
+ return MergeVal(GetVal(info->op_a, trip, in_body, is_min),
+ GetVal(info->op_b, trip, in_body, is_min), is_min);
}
}
return Value();
@@ -198,11 +194,12 @@
InductionVarRange::Value InductionVarRange::GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
bool is_min) {
- Value v1_min = GetVal(info1, trip, /* is_min */ true);
- Value v1_max = GetVal(info1, trip, /* is_min */ false);
- Value v2_min = GetVal(info2, trip, /* is_min */ true);
- Value v2_max = GetVal(info2, trip, /* is_min */ false);
+ Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true);
+ Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false);
+ Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true);
+ Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false);
if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
// Positive range vs. positive or negative range.
if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
@@ -228,11 +225,12 @@
InductionVarRange::Value InductionVarRange::GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
bool is_min) {
- Value v1_min = GetVal(info1, trip, /* is_min */ true);
- Value v1_max = GetVal(info1, trip, /* is_min */ false);
- Value v2_min = GetVal(info2, trip, /* is_min */ true);
- Value v2_max = GetVal(info2, trip, /* is_min */ false);
+ Value v1_min = GetVal(info1, trip, in_body, /* is_min */ true);
+ Value v1_max = GetVal(info1, trip, in_body, /* is_min */ false);
+ Value v2_min = GetVal(info2, trip, in_body, /* is_min */ true);
+ Value v2_max = GetVal(info2, trip, in_body, /* is_min */ false);
if (v1_min.is_known && v1_min.a_constant == 0 && v1_min.b_constant >= 0) {
// Positive range vs. positive or negative range.
if (v2_min.is_known && v2_min.a_constant == 0 && v2_min.b_constant >= 0) {
@@ -255,6 +253,16 @@
return Value();
}
+bool InductionVarRange::GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value) {
+ Value v_min = GetVal(info, nullptr, false, /* is_min */ true);
+ Value v_max = GetVal(info, nullptr, false, /* is_min */ false);
+ if (v_min.a_constant == 0 && v_max.a_constant == 0 && v_min.b_constant == v_max.b_constant) {
+ *value = v_min.b_constant;
+ return true;
+ }
+ return false;
+}
+
InductionVarRange::Value InductionVarRange::AddValue(Value v1, Value v2) {
if (v1.is_known && v2.is_known && IsSafeAdd(v1.b_constant, v2.b_constant)) {
const int32_t b = v1.b_constant + v2.b_constant;
diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index 8280c8b..dbdd2ee 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -73,24 +73,29 @@
// Private helper methods.
//
- HInductionVarAnalysis::InductionInfo* GetTripCount(HLoopInformation* loop, HInstruction* context);
+ Value GetInduction(HInstruction* context, HInstruction* instruction, bool is_min);
static Value GetFetch(HInstruction* instruction,
HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
bool is_min);
-
static Value GetVal(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
bool is_min);
static Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
bool is_min);
static Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
HInductionVarAnalysis::InductionInfo* trip,
+ bool in_body,
bool is_min);
+ static bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t *value);
+
static Value AddValue(Value v1, Value v2);
static Value SubValue(Value v1, Value v2);
static Value MulValue(Value v1, Value v2);
diff --git a/compiler/optimizing/induction_var_range_test.cc b/compiler/optimizing/induction_var_range_test.cc
index 5d9a075..4497a88 100644
--- a/compiler/optimizing/induction_var_range_test.cc
+++ b/compiler/optimizing/induction_var_range_test.cc
@@ -85,8 +85,7 @@
/** Constructs a trip-count. */
HInductionVarAnalysis::InductionInfo* CreateTripCount(int32_t tc) {
- HInductionVarAnalysis::InductionInfo* trip = CreateConst(tc);
- return CreateInvariant('@', trip, trip);
+ return iva_->CreateTripCount(HInductionVarAnalysis::kTripCountInLoop, CreateConst(tc));
}
/** Constructs a linear a * i + b induction. */
@@ -112,24 +111,28 @@
Value GetMin(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* induc) {
- return InductionVarRange::GetVal(info, induc, /* is_min */ true);
+ return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ true);
}
Value GetMax(HInductionVarAnalysis::InductionInfo* info,
HInductionVarAnalysis::InductionInfo* induc) {
- return InductionVarRange::GetVal(info, induc, /* is_min */ false);
+ return InductionVarRange::GetVal(info, induc, /* in_body */ true, /* is_min */ false);
}
Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
bool is_min) {
- return InductionVarRange::GetMul(info1, info2, nullptr, is_min);
+ return InductionVarRange::GetMul(info1, info2, nullptr, /* in_body */ true, is_min);
}
Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
HInductionVarAnalysis::InductionInfo* info2,
bool is_min) {
- return InductionVarRange::GetDiv(info1, info2, nullptr, is_min);
+ return InductionVarRange::GetDiv(info1, info2, nullptr, /* in_body */ true, is_min);
+ }
+
+ bool GetConstant(HInductionVarAnalysis::InductionInfo* info, int32_t* value) {
+ return InductionVarRange::GetConstant(info, value);
}
Value AddValue(Value v1, Value v2) { return InductionVarRange::AddValue(v1, v2); }
@@ -279,6 +282,13 @@
ExpectEqual(Value(500), GetDiv(CreateRange(-1000, -40), CreateRange(-4, -2), false));
}
+TEST_F(InductionVarRangeTest, GetConstant) {
+ int32_t value;
+ ASSERT_TRUE(GetConstant(CreateConst(12345), &value));
+ EXPECT_EQ(12345, value);
+ EXPECT_FALSE(GetConstant(CreateRange(1, 2), &value));
+}
+
TEST_F(InductionVarRangeTest, AddValue) {
ExpectEqual(Value(110), AddValue(Value(10), Value(100)));
ExpectEqual(Value(-5), AddValue(Value(&x_, 1, -4), Value(&x_, -1, -1)));
diff --git a/compiler/optimizing/locations.h b/compiler/optimizing/locations.h
index 76bd595..de4fb7e 100644
--- a/compiler/optimizing/locations.h
+++ b/compiler/optimizing/locations.h
@@ -468,7 +468,7 @@
* The intent is to have the code for generating the instruction independent of
* register allocation. A register allocator just has to provide a LocationSummary.
*/
-class LocationSummary : public ArenaObject<kArenaAllocMisc> {
+class LocationSummary : public ArenaObject<kArenaAllocLocationSummary> {
public:
enum CallKind {
kNoCall,
diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc
index c43e58f..9cdb89b 100644
--- a/compiler/optimizing/register_allocator.cc
+++ b/compiler/optimizing/register_allocator.cc
@@ -187,7 +187,8 @@
}
number_of_registers_ = codegen_->GetNumberOfCoreRegisters();
- registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_);
+ registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_,
+ kArenaAllocRegisterAllocator);
processing_core_registers_ = true;
unhandled_ = &unhandled_core_intervals_;
for (LiveInterval* fixed : physical_core_register_intervals_) {
@@ -206,7 +207,8 @@
handled_.clear();
number_of_registers_ = codegen_->GetNumberOfFloatingPointRegisters();
- registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_);
+ registers_array_ = allocator_->AllocArray<size_t>(number_of_registers_,
+ kArenaAllocRegisterAllocator);
processing_core_registers_ = false;
unhandled_ = &unhandled_fp_intervals_;
for (LiveInterval* fixed : physical_fp_register_intervals_) {
diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h
index 414cc7d..e4b0999 100644
--- a/compiler/optimizing/ssa_liveness_analysis.h
+++ b/compiler/optimizing/ssa_liveness_analysis.h
@@ -27,7 +27,7 @@
static constexpr int kNoRegister = -1;
-class BlockInfo : public ArenaObject<kArenaAllocMisc> {
+class BlockInfo : public ArenaObject<kArenaAllocSsaLiveness> {
public:
BlockInfo(ArenaAllocator* allocator, const HBasicBlock& block, size_t number_of_ssa_values)
: block_(block),
@@ -55,7 +55,7 @@
* A live range contains the start and end of a range where an instruction or a temporary
* is live.
*/
-class LiveRange FINAL : public ArenaObject<kArenaAllocMisc> {
+class LiveRange FINAL : public ArenaObject<kArenaAllocSsaLiveness> {
public:
LiveRange(size_t start, size_t end, LiveRange* next) : start_(start), end_(end), next_(next) {
DCHECK_LT(start, end);
@@ -101,7 +101,7 @@
/**
* A use position represents a live interval use at a given position.
*/
-class UsePosition : public ArenaObject<kArenaAllocMisc> {
+class UsePosition : public ArenaObject<kArenaAllocSsaLiveness> {
public:
UsePosition(HInstruction* user,
HEnvironment* environment,
@@ -169,7 +169,7 @@
DISALLOW_COPY_AND_ASSIGN(UsePosition);
};
-class SafepointPosition : public ArenaObject<kArenaAllocMisc> {
+class SafepointPosition : public ArenaObject<kArenaAllocSsaLiveness> {
public:
explicit SafepointPosition(HInstruction* instruction)
: instruction_(instruction),
diff --git a/runtime/base/arena_allocator.cc b/runtime/base/arena_allocator.cc
index 691b57f..345428c 100644
--- a/runtime/base/arena_allocator.cc
+++ b/runtime/base/arena_allocator.cc
@@ -83,6 +83,8 @@
"BaselineMaps ",
"Optimization ",
"GVN ",
+ "InductionVar ",
+ "BCE ",
"SsaLiveness ",
"SsaPhiElim ",
"RefTypeProp ",
diff --git a/runtime/base/arena_allocator.h b/runtime/base/arena_allocator.h
index 17045c6..b4f19ee 100644
--- a/runtime/base/arena_allocator.h
+++ b/runtime/base/arena_allocator.h
@@ -93,6 +93,8 @@
kArenaAllocBaselineMaps,
kArenaAllocOptimization,
kArenaAllocGvn,
+ kArenaAllocInductionVarAnalysis,
+ kArenaAllocBoundsCheckElimination,
kArenaAllocSsaLiveness,
kArenaAllocSsaPhiElimination,
kArenaAllocReferenceTypePropagation,
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index 1c5b5d6..58c92f1 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -22,7 +22,7 @@
static int sResult;
//
- // Various sequence variables where bound checks can be removed from loop.
+ // Various sequence variables used in bound checks.
//
/// CHECK-START: int Main.linear(int[]) BCE (before)
@@ -262,11 +262,11 @@
return result;
}
- /// CHECK-START: int Main.linearForNE() BCE (before)
+ /// CHECK-START: int Main.linearForNEUp() BCE (before)
/// CHECK-DAG: BoundsCheck
- /// CHECK-START: int Main.linearForNE() BCE (after)
+ /// CHECK-START: int Main.linearForNEUp() BCE (after)
/// CHECK-NOT: BoundsCheck
- private static int linearForNE() {
+ private static int linearForNEUp() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
for (int i = 0; i != 10; i++) {
@@ -275,21 +275,47 @@
return result;
}
- /// CHECK-START: int Main.linearDoWhile() BCE (before)
+ /// CHECK-START: int Main.linearForNEDown() BCE (before)
/// CHECK-DAG: BoundsCheck
- /// CHECK-START: int Main.linearDoWhile() BCE (after)
+ /// CHECK-START: int Main.linearForNEDown() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearForNEDown() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ for (int i = 9; i != -1; i--) {
+ result += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearDoWhileUp() BCE (before)
/// CHECK-DAG: BoundsCheck
- private static int linearDoWhile() {
+ /// CHECK-START: int Main.linearDoWhileUp() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearDoWhileUp() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
int i = 0;
- // TODO: make this work
do {
result += x[i++];
} while (i < 10);
return result;
}
+ /// CHECK-START: int Main.linearDoWhileDown() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearDoWhileDown() BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ private static int linearDoWhileDown() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int result = 0;
+ int i = 9;
+ do {
+ result += x[i--];
+ } while (0 <= i);
+ return result;
+ }
+
/// CHECK-START: int Main.linearShort() BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearShort() BCE (after)
@@ -471,23 +497,50 @@
return result;
}
- //
- // Cases that actually go out of bounds. These test cases
- // ensure the exceptions are thrown at the right places.
- //
-
+ /// CHECK-START: void Main.lowerOOB(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: void Main.lowerOOB(int[]) BCE (after)
+ /// CHECK-DAG: BoundsCheck
private static void lowerOOB(int[] x) {
for (int i = -1; i < x.length; i++) {
sResult += x[i];
}
}
+ /// CHECK-START: void Main.upperOOB(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: void Main.upperOOB(int[]) BCE (after)
+ /// CHECK-DAG: BoundsCheck
private static void upperOOB(int[] x) {
for (int i = 0; i <= x.length; i++) {
sResult += x[i];
}
}
+ /// CHECK-START: void Main.doWhileUpOOB() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: void Main.doWhileUpOOB() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static void doWhileUpOOB() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int i = 0;
+ do {
+ sResult += x[i++];
+ } while (i <= x.length);
+ }
+
+ /// CHECK-START: void Main.doWhileDownOOB() BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: void Main.doWhileDownOOB() BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ private static void doWhileDownOOB() {
+ int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
+ int i = x.length - 1;
+ do {
+ sResult += x[i--];
+ } while (-1 <= i);
+ }
+
//
// Verifier.
//
@@ -550,8 +603,10 @@
expectEquals(66, linearWithVeryLargeNegativeStride());
// Special forms.
- expectEquals(55, linearForNE());
- expectEquals(55, linearDoWhile());
+ expectEquals(55, linearForNEUp());
+ expectEquals(55, linearForNEDown());
+ expectEquals(55, linearDoWhileUp());
+ expectEquals(55, linearDoWhileDown());
expectEquals(55, linearShort());
// Periodic adds (1, 3), one at the time.
@@ -618,6 +673,23 @@
}
expectEquals(1055, sResult);
+ // Do while up goes OOB.
+ sResult = 0;
+ try {
+ doWhileUpOOB();
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult += 1000;
+ }
+ expectEquals(1055, sResult);
+
+ // Do while down goes OOB.
+ sResult = 0;
+ try {
+ doWhileDownOOB();
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult += 1000;
+ }
+ expectEquals(1055, sResult);
}
private static void expectEquals(int expected, int result) {