Dynamic BCE (based on induction range analysis)
Rationale: A rewritten dynamic BCE that uses induction variable analysis
to generate the run-time tests before a loop in order to
eliminate bounds-checks from its body. This CL removes now
obsoleted induction related code inside the BCE module.
Also, the dynamic test generation is placed more strategically,
since we missed a few cases where static analysis does better.
Most significant performance improvements (after filtering noise) is about:
Linpack +20%
LU > +10%
Change-Id: I4e7b8bab0288beff6f98a14856e3536103d32742
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index cca0baf..a448302 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -20,6 +20,7 @@
#include "base/arena_containers.h"
#include "induction_var_range.h"
+#include "side_effects_analysis.h"
#include "nodes.h"
namespace art {
@@ -175,6 +176,24 @@
return false;
}
+ // Returns if it's certain this->bound > `bound`.
+ bool GreaterThan(ValueBound bound) const {
+ if (Equal(instruction_, bound.instruction_)) {
+ return constant_ > bound.constant_;
+ }
+ // Not comparable. Just return false.
+ return false;
+ }
+
+ // Returns if it's certain this->bound < `bound`.
+ bool LessThan(ValueBound bound) const {
+ if (Equal(instruction_, bound.instruction_)) {
+ return constant_ < bound.constant_;
+ }
+ // Not comparable. Just return false.
+ return false;
+ }
+
// Try to narrow lower bound. Returns the greatest of the two if possible.
// Pick one if they are not comparable.
static ValueBound NarrowLowerBound(ValueBound bound1, ValueBound bound2) {
@@ -252,157 +271,6 @@
int32_t constant_;
};
-// Collect array access data for a loop.
-// TODO: make it work for multiple arrays inside the loop.
-class ArrayAccessInsideLoopFinder : public ValueObject {
- public:
- explicit ArrayAccessInsideLoopFinder(HInstruction* induction_variable)
- : induction_variable_(induction_variable),
- found_array_length_(nullptr),
- offset_low_(std::numeric_limits<int32_t>::max()),
- offset_high_(std::numeric_limits<int32_t>::min()) {
- Run();
- }
-
- HArrayLength* GetFoundArrayLength() const { return found_array_length_; }
- bool HasFoundArrayLength() const { return found_array_length_ != nullptr; }
- int32_t GetOffsetLow() const { return offset_low_; }
- int32_t GetOffsetHigh() const { return offset_high_; }
-
- // Returns if `block` that is in loop_info may exit the loop, unless it's
- // the loop header for loop_info.
- static bool EarlyExit(HBasicBlock* block, HLoopInformation* loop_info) {
- DCHECK(loop_info->Contains(*block));
- if (block == loop_info->GetHeader()) {
- // Loop header of loop_info. Exiting loop is normal.
- return false;
- }
- for (HBasicBlock* successor : block->GetSuccessors()) {
- if (!loop_info->Contains(*successor)) {
- // One of the successors exits the loop.
- return true;
- }
- }
- return false;
- }
-
- static bool DominatesAllBackEdges(HBasicBlock* block, HLoopInformation* loop_info) {
- for (HBasicBlock* back_edge : loop_info->GetBackEdges()) {
- if (!block->Dominates(back_edge)) {
- return false;
- }
- }
- return true;
- }
-
- void Run() {
- HLoopInformation* loop_info = induction_variable_->GetBlock()->GetLoopInformation();
- HBlocksInLoopReversePostOrderIterator it_loop(*loop_info);
- HBasicBlock* block = it_loop.Current();
- DCHECK(block == induction_variable_->GetBlock());
- // Skip loop header. Since narrowed value range of a MonotonicValueRange only
- // applies to the loop body (after the test at the end of the loop header).
- it_loop.Advance();
- for (; !it_loop.Done(); it_loop.Advance()) {
- block = it_loop.Current();
- DCHECK(block->IsInLoop());
- if (!DominatesAllBackEdges(block, loop_info)) {
- // In order not to trigger deoptimization unnecessarily, make sure
- // that all array accesses collected are really executed in the loop.
- // For array accesses in a branch inside the loop, don't collect the
- // access. The bounds check in that branch might not be eliminated.
- continue;
- }
- if (EarlyExit(block, loop_info)) {
- // If the loop body can exit loop (like break, return, etc.), it's not guaranteed
- // that the loop will loop through the full monotonic value range from
- // initial_ to end_. So adding deoptimization might be too aggressive and can
- // trigger deoptimization unnecessarily even if the loop won't actually throw
- // AIOOBE.
- found_array_length_ = nullptr;
- return;
- }
- for (HInstruction* instruction = block->GetFirstInstruction();
- instruction != nullptr;
- instruction = instruction->GetNext()) {
- if (!instruction->IsBoundsCheck()) {
- continue;
- }
-
- HInstruction* length_value = instruction->InputAt(1);
- if (length_value->IsIntConstant()) {
- // TODO: may optimize for constant case.
- continue;
- }
-
- if (length_value->IsPhi()) {
- // When adding deoptimizations in outer loops, we might create
- // a phi for the array length, and update all uses of the
- // length in the loop to that phi. Therefore, inner loops having
- // bounds checks on the same array will use that phi.
- // TODO: handle these cases.
- continue;
- }
-
- DCHECK(length_value->IsArrayLength());
- HArrayLength* array_length = length_value->AsArrayLength();
-
- HInstruction* array = array_length->InputAt(0);
- if (array->IsNullCheck()) {
- array = array->AsNullCheck()->InputAt(0);
- }
- if (loop_info->Contains(*array->GetBlock())) {
- // Array is defined inside the loop. Skip.
- continue;
- }
-
- if (found_array_length_ != nullptr && found_array_length_ != array_length) {
- // There is already access for another array recorded for the loop.
- // TODO: handle multiple arrays.
- continue;
- }
-
- HInstruction* index = instruction->AsBoundsCheck()->InputAt(0);
- HInstruction* left = index;
- int32_t right = 0;
- if (left == induction_variable_ ||
- (ValueBound::IsAddOrSubAConstant(index, &left, &right) &&
- left == induction_variable_)) {
- // For patterns like array[i] or array[i + 2].
- if (right < offset_low_) {
- offset_low_ = right;
- }
- if (right > offset_high_) {
- offset_high_ = right;
- }
- } else {
- // Access not in induction_variable/(induction_variable_ + constant)
- // format. Skip.
- continue;
- }
- // Record this array.
- found_array_length_ = array_length;
- }
- }
- }
-
- private:
- // The instruction that corresponds to a MonotonicValueRange.
- HInstruction* induction_variable_;
-
- // The array length of the array that's accessed inside the loop body.
- HArrayLength* found_array_length_;
-
- // The lowest and highest constant offsets relative to induction variable
- // instruction_ in all array accesses.
- // If array access are: array[i-1], array[i], array[i+1],
- // offset_low_ is -1 and offset_high is 1.
- int32_t offset_low_;
- int32_t offset_high_;
-
- DISALLOW_COPY_AND_ASSIGN(ArrayAccessInsideLoopFinder);
-};
-
/**
* Represent a range of lower bound and upper bound, both being inclusive.
* Currently a ValueRange may be generated as a result of the following:
@@ -500,18 +368,13 @@
: ValueRange(allocator, ValueBound::Min(), ValueBound::Max()),
induction_variable_(induction_variable),
initial_(initial),
- end_(nullptr),
- inclusive_(false),
increment_(increment),
bound_(bound) {}
virtual ~MonotonicValueRange() {}
- HInstruction* GetInductionVariable() const { return induction_variable_; }
int32_t GetIncrement() const { return increment_; }
ValueBound GetBound() const { return bound_; }
- void SetEnd(HInstruction* end) { end_ = end; }
- void SetInclusive(bool inclusive) { inclusive_ = inclusive; }
HBasicBlock* GetLoopHeader() const {
DCHECK(induction_variable_->GetBlock()->IsLoopHeader());
return induction_variable_->GetBlock();
@@ -519,23 +382,6 @@
MonotonicValueRange* AsMonotonicValueRange() OVERRIDE { return this; }
- HBasicBlock* GetLoopHeaderSuccesorInLoop() {
- HBasicBlock* header = GetLoopHeader();
- HInstruction* instruction = header->GetLastInstruction();
- DCHECK(instruction->IsIf());
- HIf* h_if = instruction->AsIf();
- HLoopInformation* loop_info = header->GetLoopInformation();
- bool true_successor_in_loop = loop_info->Contains(*h_if->IfTrueSuccessor());
- bool false_successor_in_loop = loop_info->Contains(*h_if->IfFalseSuccessor());
-
- // Just in case it's some strange loop structure.
- if (true_successor_in_loop && false_successor_in_loop) {
- return nullptr;
- }
- DCHECK(true_successor_in_loop || false_successor_in_loop);
- return false_successor_in_loop ? h_if->IfFalseSuccessor() : h_if->IfTrueSuccessor();
- }
-
// If it's certain that this value range fits in other_range.
bool FitsIn(ValueRange* other_range) const OVERRIDE {
if (other_range == nullptr) {
@@ -627,467 +473,9 @@
}
}
- // Try to add HDeoptimize's in the loop pre-header first to narrow this range.
- // For example, this loop:
- //
- // for (int i = start; i < end; i++) {
- // array[i - 1] = array[i] + array[i + 1];
- // }
- //
- // will be transformed to:
- //
- // int array_length_in_loop_body_if_needed;
- // if (start >= end) {
- // array_length_in_loop_body_if_needed = 0;
- // } else {
- // if (start < 1) deoptimize();
- // if (array == null) deoptimize();
- // array_length = array.length;
- // if (end > array_length - 1) deoptimize;
- // array_length_in_loop_body_if_needed = array_length;
- // }
- // for (int i = start; i < end; i++) {
- // // No more null check and bounds check.
- // // array.length value is replaced with array_length_in_loop_body_if_needed
- // // in the loop body.
- // array[i - 1] = array[i] + array[i + 1];
- // }
- //
- // We basically first go through the loop body and find those array accesses whose
- // index is at a constant offset from the induction variable ('i' in the above example),
- // and update offset_low and offset_high along the way. We then add the following
- // deoptimizations in the loop pre-header (suppose end is not inclusive).
- // if (start < -offset_low) deoptimize();
- // if (end >= array.length - offset_high) deoptimize();
- // It might be necessary to first hoist array.length (and the null check on it) out of
- // the loop with another deoptimization.
- //
- // In order not to trigger deoptimization unnecessarily, we want to make a strong
- // guarantee that no deoptimization is triggered if the loop body itself doesn't
- // throw AIOOBE. (It's the same as saying if deoptimization is triggered, the loop
- // body must throw AIOOBE).
- // This is achieved by the following:
- // 1) We only process loops that iterate through the full monotonic range from
- // initial_ to end_. We do the following checks to make sure that's the case:
- // a) The loop doesn't have early exit (via break, return, etc.)
- // b) The increment_ is 1/-1. An increment of 2, for example, may skip end_.
- // 2) We only collect array accesses of blocks in the loop body that dominate
- // all loop back edges, these array accesses are guaranteed to happen
- // at each loop iteration.
- // With 1) and 2), if the loop body doesn't throw AIOOBE, collected array accesses
- // when the induction variable is at initial_ and end_ must be in a legal range.
- // Since the added deoptimizations are basically checking the induction variable
- // at initial_ and end_ values, no deoptimization will be triggered either.
- //
- // A special case is the loop body isn't entered at all. In that case, we may still
- // add deoptimization due to the analysis described above. In order not to trigger
- // deoptimization, we do a test between initial_ and end_ first and skip over
- // the added deoptimization.
- ValueRange* NarrowWithDeoptimization() {
- if (increment_ != 1 && increment_ != -1) {
- // In order not to trigger deoptimization unnecessarily, we want to
- // make sure the loop iterates through the full range from initial_ to
- // end_ so that boundaries are covered by the loop. An increment of 2,
- // for example, may skip end_.
- return this;
- }
-
- if (end_ == nullptr) {
- // No full info to add deoptimization.
- return this;
- }
-
- HBasicBlock* header = induction_variable_->GetBlock();
- DCHECK(header->IsLoopHeader());
- HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
- if (!initial_->GetBlock()->Dominates(pre_header) ||
- !end_->GetBlock()->Dominates(pre_header)) {
- // Can't add a check in loop pre-header if the value isn't available there.
- return this;
- }
-
- ArrayAccessInsideLoopFinder finder(induction_variable_);
-
- if (!finder.HasFoundArrayLength()) {
- // No array access was found inside the loop that can benefit
- // from deoptimization.
- return this;
- }
-
- if (!AddDeoptimization(finder)) {
- return this;
- }
-
- // After added deoptimizations, induction variable fits in
- // [-offset_low, array.length-1-offset_high], adjusted with collected offsets.
- ValueBound lower = ValueBound(0, -finder.GetOffsetLow());
- ValueBound upper = ValueBound(finder.GetFoundArrayLength(), -1 - finder.GetOffsetHigh());
- // We've narrowed the range after added deoptimizations.
- return new (GetAllocator()) ValueRange(GetAllocator(), lower, upper);
- }
-
- // Returns true if adding a (constant >= value) check for deoptimization
- // is allowed and will benefit compiled code.
- bool CanAddDeoptimizationConstant(HInstruction* value, int32_t constant, bool* is_proven) {
- *is_proven = false;
- HBasicBlock* header = induction_variable_->GetBlock();
- DCHECK(header->IsLoopHeader());
- HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
- DCHECK(value->GetBlock()->Dominates(pre_header));
-
- // See if we can prove the relationship first.
- if (value->IsIntConstant()) {
- if (value->AsIntConstant()->GetValue() >= constant) {
- // Already true.
- *is_proven = true;
- return true;
- } else {
- // May throw exception. Don't add deoptimization.
- // Keep bounds checks in the loops.
- return false;
- }
- }
- // Can benefit from deoptimization.
- return true;
- }
-
- // Try to filter out cases that the loop entry test will never be true.
- bool LoopEntryTestUseful() {
- if (initial_->IsIntConstant() && end_->IsIntConstant()) {
- int32_t initial_val = initial_->AsIntConstant()->GetValue();
- int32_t end_val = end_->AsIntConstant()->GetValue();
- if (increment_ == 1) {
- if (inclusive_) {
- return initial_val > end_val;
- } else {
- return initial_val >= end_val;
- }
- } else {
- DCHECK_EQ(increment_, -1);
- if (inclusive_) {
- return initial_val < end_val;
- } else {
- return initial_val <= end_val;
- }
- }
- }
- return true;
- }
-
- // Returns the block for adding deoptimization.
- HBasicBlock* TransformLoopForDeoptimizationIfNeeded() {
- HBasicBlock* header = induction_variable_->GetBlock();
- DCHECK(header->IsLoopHeader());
- HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
- // Deoptimization is only added when both initial_ and end_ are defined
- // before the loop.
- DCHECK(initial_->GetBlock()->Dominates(pre_header));
- DCHECK(end_->GetBlock()->Dominates(pre_header));
-
- // If it can be proven the loop body is definitely entered (unless exception
- // is thrown in the loop header for which triggering deoptimization is fine),
- // there is no need for tranforming the loop. In that case, deoptimization
- // will just be added in the loop pre-header.
- if (!LoopEntryTestUseful()) {
- return pre_header;
- }
-
- HGraph* graph = header->GetGraph();
- graph->TransformLoopHeaderForBCE(header);
- HBasicBlock* new_pre_header = header->GetDominator();
- DCHECK(new_pre_header == header->GetLoopInformation()->GetPreHeader());
- HBasicBlock* if_block = new_pre_header->GetDominator();
- HBasicBlock* dummy_block = if_block->GetSuccessors()[0]; // True successor.
- HBasicBlock* deopt_block = if_block->GetSuccessors()[1]; // False successor.
-
- dummy_block->AddInstruction(new (graph->GetArena()) HGoto());
- deopt_block->AddInstruction(new (graph->GetArena()) HGoto());
- new_pre_header->AddInstruction(new (graph->GetArena()) HGoto());
- return deopt_block;
- }
-
- // Adds a test between initial_ and end_ to see if the loop body is entered.
- // If the loop body isn't entered at all, it jumps to the loop pre-header (after
- // transformation) to avoid any deoptimization.
- void AddLoopBodyEntryTest() {
- HBasicBlock* header = induction_variable_->GetBlock();
- DCHECK(header->IsLoopHeader());
- HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
- HBasicBlock* if_block = pre_header->GetDominator();
- HGraph* graph = header->GetGraph();
-
- HCondition* cond;
- if (increment_ == 1) {
- if (inclusive_) {
- cond = new (graph->GetArena()) HGreaterThan(initial_, end_);
- } else {
- cond = new (graph->GetArena()) HGreaterThanOrEqual(initial_, end_);
- }
- } else {
- DCHECK_EQ(increment_, -1);
- if (inclusive_) {
- cond = new (graph->GetArena()) HLessThan(initial_, end_);
- } else {
- cond = new (graph->GetArena()) HLessThanOrEqual(initial_, end_);
- }
- }
- HIf* h_if = new (graph->GetArena()) HIf(cond);
- if_block->AddInstruction(cond);
- if_block->AddInstruction(h_if);
- }
-
- // Adds a check that (value >= constant), and HDeoptimize otherwise.
- void AddDeoptimizationConstant(HInstruction* value,
- int32_t constant,
- HBasicBlock* deopt_block,
- bool loop_entry_test_block_added) {
- HBasicBlock* header = induction_variable_->GetBlock();
- DCHECK(header->IsLoopHeader());
- HBasicBlock* pre_header = header->GetDominator();
- if (loop_entry_test_block_added) {
- DCHECK(deopt_block->GetSuccessors()[0] == pre_header);
- } else {
- DCHECK(deopt_block == pre_header);
- }
- HGraph* graph = header->GetGraph();
- HSuspendCheck* suspend_check = header->GetLoopInformation()->GetSuspendCheck();
- if (loop_entry_test_block_added) {
- DCHECK_EQ(deopt_block, header->GetDominator()->GetDominator()->GetSuccessors()[1]);
- }
-
- HIntConstant* const_instr = graph->GetIntConstant(constant);
- HCondition* cond = new (graph->GetArena()) HLessThan(value, const_instr);
- HDeoptimize* deoptimize = new (graph->GetArena())
- HDeoptimize(cond, suspend_check->GetDexPc());
- deopt_block->InsertInstructionBefore(cond, deopt_block->GetLastInstruction());
- deopt_block->InsertInstructionBefore(deoptimize, deopt_block->GetLastInstruction());
- deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
- suspend_check->GetEnvironment(), header);
- }
-
- // Returns true if adding a (value <= array_length + offset) check for deoptimization
- // is allowed and will benefit compiled code.
- bool CanAddDeoptimizationArrayLength(HInstruction* value,
- HArrayLength* array_length,
- int32_t offset,
- bool* is_proven) {
- *is_proven = false;
- HBasicBlock* header = induction_variable_->GetBlock();
- DCHECK(header->IsLoopHeader());
- HBasicBlock* pre_header = header->GetLoopInformation()->GetPreHeader();
- DCHECK(value->GetBlock()->Dominates(pre_header));
-
- if (array_length->GetBlock() == header) {
- // array_length_in_loop_body_if_needed only has correct value when the loop
- // body is entered. We bail out in this case. Usually array_length defined
- // in the loop header is already hoisted by licm.
- return false;
- } else {
- // array_length is defined either before the loop header already, or in
- // the loop body since it's used in the loop body. If it's defined in the loop body,
- // a phi array_length_in_loop_body_if_needed is used to replace it. In that case,
- // all the uses of array_length must be dominated by its definition in the loop
- // body. array_length_in_loop_body_if_needed is guaranteed to be the same as
- // array_length once the loop body is entered so all the uses of the phi will
- // use the correct value.
- }
-
- if (offset > 0) {
- // There might be overflow issue.
- // TODO: handle this, possibly with some distance relationship between
- // offset_low and offset_high, or using another deoptimization to make
- // sure (array_length + offset) doesn't overflow.
- return false;
- }
-
- // See if we can prove the relationship first.
- if (value == array_length) {
- if (offset >= 0) {
- // Already true.
- *is_proven = true;
- return true;
- } else {
- // May throw exception. Don't add deoptimization.
- // Keep bounds checks in the loops.
- return false;
- }
- }
- // Can benefit from deoptimization.
- return true;
- }
-
- // Adds a check that (value <= array_length + offset), and HDeoptimize otherwise.
- void AddDeoptimizationArrayLength(HInstruction* value,
- HArrayLength* array_length,
- int32_t offset,
- HBasicBlock* deopt_block,
- bool loop_entry_test_block_added) {
- HBasicBlock* header = induction_variable_->GetBlock();
- DCHECK(header->IsLoopHeader());
- HBasicBlock* pre_header = header->GetDominator();
- if (loop_entry_test_block_added) {
- DCHECK(deopt_block->GetSuccessors()[0] == pre_header);
- } else {
- DCHECK(deopt_block == pre_header);
- }
- HGraph* graph = header->GetGraph();
- HSuspendCheck* suspend_check = header->GetLoopInformation()->GetSuspendCheck();
-
- // We may need to hoist null-check and array_length out of loop first.
- if (!array_length->GetBlock()->Dominates(deopt_block)) {
- // array_length must be defined in the loop body.
- DCHECK(header->GetLoopInformation()->Contains(*array_length->GetBlock()));
- DCHECK(array_length->GetBlock() != header);
-
- HInstruction* array = array_length->InputAt(0);
- HNullCheck* null_check = array->AsNullCheck();
- if (null_check != nullptr) {
- array = null_check->InputAt(0);
- }
- // We've already made sure the array is defined before the loop when collecting
- // array accesses for the loop.
- DCHECK(array->GetBlock()->Dominates(deopt_block));
- if (null_check != nullptr && !null_check->GetBlock()->Dominates(deopt_block)) {
- // Hoist null check out of loop with a deoptimization.
- HNullConstant* null_constant = graph->GetNullConstant();
- HCondition* null_check_cond = new (graph->GetArena()) HEqual(array, null_constant);
- // TODO: for one dex_pc, share the same deoptimization slow path.
- HDeoptimize* null_check_deoptimize = new (graph->GetArena())
- HDeoptimize(null_check_cond, suspend_check->GetDexPc());
- deopt_block->InsertInstructionBefore(
- null_check_cond, deopt_block->GetLastInstruction());
- deopt_block->InsertInstructionBefore(
- null_check_deoptimize, deopt_block->GetLastInstruction());
- // Eliminate null check in the loop.
- null_check->ReplaceWith(array);
- null_check->GetBlock()->RemoveInstruction(null_check);
- null_check_deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
- suspend_check->GetEnvironment(), header);
- }
-
- HArrayLength* new_array_length
- = new (graph->GetArena()) HArrayLength(array, array->GetDexPc());
- deopt_block->InsertInstructionBefore(new_array_length, deopt_block->GetLastInstruction());
-
- if (loop_entry_test_block_added) {
- // Replace array_length defined inside the loop body with a phi
- // array_length_in_loop_body_if_needed. This is a synthetic phi so there is
- // no vreg number for it.
- HPhi* phi = new (graph->GetArena()) HPhi(
- graph->GetArena(), kNoRegNumber, 2, Primitive::kPrimInt);
- // Set to 0 if the loop body isn't entered.
- phi->SetRawInputAt(0, graph->GetIntConstant(0));
- // Set to array.length if the loop body is entered.
- phi->SetRawInputAt(1, new_array_length);
- pre_header->AddPhi(phi);
- array_length->ReplaceWith(phi);
- // Make sure phi is only used after the loop body is entered.
- if (kIsDebugBuild) {
- for (HUseIterator<HInstruction*> it(phi->GetUses());
- !it.Done();
- it.Advance()) {
- HInstruction* user = it.Current()->GetUser();
- DCHECK(GetLoopHeaderSuccesorInLoop()->Dominates(user->GetBlock()));
- }
- }
- } else {
- array_length->ReplaceWith(new_array_length);
- }
-
- array_length->GetBlock()->RemoveInstruction(array_length);
- // Use new_array_length for deopt.
- array_length = new_array_length;
- }
-
- HInstruction* added = array_length;
- if (offset != 0) {
- HIntConstant* offset_instr = graph->GetIntConstant(offset);
- added = new (graph->GetArena()) HAdd(Primitive::kPrimInt, array_length, offset_instr);
- deopt_block->InsertInstructionBefore(added, deopt_block->GetLastInstruction());
- }
- HCondition* cond = new (graph->GetArena()) HGreaterThan(value, added);
- HDeoptimize* deopt = new (graph->GetArena()) HDeoptimize(cond, suspend_check->GetDexPc());
- deopt_block->InsertInstructionBefore(cond, deopt_block->GetLastInstruction());
- deopt_block->InsertInstructionBefore(deopt, deopt_block->GetLastInstruction());
- deopt->CopyEnvironmentFromWithLoopPhiAdjustment(suspend_check->GetEnvironment(), header);
- }
-
- // Adds deoptimizations in loop pre-header with the collected array access
- // data so that value ranges can be established in loop body.
- // Returns true if deoptimizations are successfully added, or if it's proven
- // it's not necessary.
- bool AddDeoptimization(const ArrayAccessInsideLoopFinder& finder) {
- int32_t offset_low = finder.GetOffsetLow();
- int32_t offset_high = finder.GetOffsetHigh();
- HArrayLength* array_length = finder.GetFoundArrayLength();
-
- HBasicBlock* pre_header =
- induction_variable_->GetBlock()->GetLoopInformation()->GetPreHeader();
- if (!initial_->GetBlock()->Dominates(pre_header) ||
- !end_->GetBlock()->Dominates(pre_header)) {
- // Can't move initial_ or end_ into pre_header for comparisons.
- return false;
- }
-
- HBasicBlock* deopt_block;
- bool loop_entry_test_block_added = false;
- bool is_constant_proven, is_length_proven;
-
- HInstruction* const_comparing_instruction;
- int32_t const_compared_to;
- HInstruction* array_length_comparing_instruction;
- int32_t array_length_offset;
- if (increment_ == 1) {
- // Increasing from initial_ to end_.
- const_comparing_instruction = initial_;
- const_compared_to = -offset_low;
- array_length_comparing_instruction = end_;
- array_length_offset = inclusive_ ? -offset_high - 1 : -offset_high;
- } else {
- const_comparing_instruction = end_;
- const_compared_to = inclusive_ ? -offset_low : -offset_low - 1;
- array_length_comparing_instruction = initial_;
- array_length_offset = -offset_high - 1;
- }
-
- if (CanAddDeoptimizationConstant(const_comparing_instruction,
- const_compared_to,
- &is_constant_proven) &&
- CanAddDeoptimizationArrayLength(array_length_comparing_instruction,
- array_length,
- array_length_offset,
- &is_length_proven)) {
- if (!is_constant_proven || !is_length_proven) {
- deopt_block = TransformLoopForDeoptimizationIfNeeded();
- loop_entry_test_block_added = (deopt_block != pre_header);
- if (loop_entry_test_block_added) {
- // Loop body may be entered.
- AddLoopBodyEntryTest();
- }
- }
- if (!is_constant_proven) {
- AddDeoptimizationConstant(const_comparing_instruction,
- const_compared_to,
- deopt_block,
- loop_entry_test_block_added);
- }
- if (!is_length_proven) {
- AddDeoptimizationArrayLength(array_length_comparing_instruction,
- array_length,
- array_length_offset,
- deopt_block,
- loop_entry_test_block_added);
- }
- return true;
- }
- return false;
- }
-
private:
HPhi* const induction_variable_; // Induction variable for this monotonic value range.
HInstruction* const initial_; // Initial value.
- HInstruction* end_; // End value.
- bool inclusive_; // Whether end value is inclusive.
const int32_t increment_; // Increment for each loop iteration.
const ValueBound bound_; // Additional value bound info for initial_.
@@ -1111,7 +499,9 @@
return block->GetBlockId() >= initial_block_size_;
}
- BCEVisitor(HGraph* graph, HInductionVarAnalysis* induction_analysis)
+ BCEVisitor(HGraph* graph,
+ const SideEffectsAnalysis& side_effects,
+ HInductionVarAnalysis* induction_analysis)
: HGraphVisitor(graph),
maps_(graph->GetBlocks().size(),
ArenaSafeMap<int, ValueRange*>(
@@ -1121,8 +511,17 @@
first_constant_index_bounds_check_map_(
std::less<int>(),
graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
+ early_exit_loop_(
+ std::less<uint32_t>(),
+ graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
+ taken_test_loop_(
+ std::less<uint32_t>(),
+ graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
+ finite_loop_(graph->GetArena()->Adapter(kArenaAllocBoundsCheckElimination)),
need_to_revisit_block_(false),
+ has_deoptimization_on_constant_subscripts_(false),
initial_block_size_(graph->GetBlocks().size()),
+ side_effects_(side_effects),
induction_range_(induction_analysis) {}
void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
@@ -1138,6 +537,17 @@
}
}
+ void Finish() {
+ // Preserve SSA structure which may have been broken by adding one or more
+ // new taken-test structures (see TransformLoopForDeoptimizationIfNeeded()).
+ InsertPhiNodes();
+
+ // Clear the loop data structures.
+ early_exit_loop_.clear();
+ taken_test_loop_.clear();
+ finite_loop_.clear();
+ }
+
private:
// Return the map of proven value ranges at the beginning of a basic block.
ArenaSafeMap<int, ValueRange*>* GetValueRangeMap(HBasicBlock* basic_block) {
@@ -1166,25 +576,6 @@
return nullptr;
}
- // Return the range resulting from induction variable analysis of "instruction" when the value
- // is used from "context", for example, an index used from a bounds-check inside a loop body.
- ValueRange* LookupInductionRange(HInstruction* context, HInstruction* instruction) {
- InductionVarRange::Value v1;
- InductionVarRange::Value v2;
- bool needs_finite_test = false;
- induction_range_.GetInductionRange(context, instruction, &v1, &v2, &needs_finite_test);
- if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) &&
- v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) {
- DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
- DCHECK(v2.a_constant == 1 || v2.instruction == nullptr);
- ValueBound low = ValueBound(v1.instruction, v1.b_constant);
- ValueBound up = ValueBound(v2.instruction, v2.b_constant);
- return new (GetGraph()->GetArena()) ValueRange(GetGraph()->GetArena(), low, up);
- }
- // Didn't find anything useful.
- return nullptr;
- }
-
// Narrow the value range of `instruction` at the end of `basic_block` with `range`,
// and push the narrowed value range to `successor`.
void ApplyRangeFromComparison(HInstruction* instruction, HBasicBlock* basic_block,
@@ -1330,17 +721,6 @@
bool overflow, underflow;
if (cond == kCondLT || cond == kCondLE) {
- if (left_monotonic_range != nullptr) {
- // Update the info for monotonic value range.
- if (left_monotonic_range->GetInductionVariable() == left &&
- left_monotonic_range->GetIncrement() < 0 &&
- block == left_monotonic_range->GetLoopHeader() &&
- instruction->IfFalseSuccessor()->GetLoopInformation() == block->GetLoopInformation()) {
- left_monotonic_range->SetEnd(right);
- left_monotonic_range->SetInclusive(cond == kCondLT);
- }
- }
-
if (!upper.Equals(ValueBound::Max())) {
int32_t compensation = (cond == kCondLT) ? -1 : 0; // upper bound is inclusive
ValueBound new_upper = upper.Add(compensation, &overflow, &underflow);
@@ -1364,17 +744,6 @@
ApplyRangeFromComparison(left, block, false_successor, new_range);
}
} else if (cond == kCondGT || cond == kCondGE) {
- if (left_monotonic_range != nullptr) {
- // Update the info for monotonic value range.
- if (left_monotonic_range->GetInductionVariable() == left &&
- left_monotonic_range->GetIncrement() > 0 &&
- block == left_monotonic_range->GetLoopHeader() &&
- instruction->IfFalseSuccessor()->GetLoopInformation() == block->GetLoopInformation()) {
- left_monotonic_range->SetEnd(right);
- left_monotonic_range->SetInclusive(cond == kCondGT);
- }
- }
-
// array.length as a lower bound isn't considered useful.
if (!lower.Equals(ValueBound::Min()) && !lower.IsRelatedToArrayLength()) {
int32_t compensation = (cond == kCondGT) ? 1 : 0; // lower bound is inclusive
@@ -1400,38 +769,34 @@
}
}
- void VisitBoundsCheck(HBoundsCheck* bounds_check) {
+ void VisitBoundsCheck(HBoundsCheck* bounds_check) OVERRIDE {
HBasicBlock* block = bounds_check->GetBlock();
HInstruction* index = bounds_check->InputAt(0);
HInstruction* array_length = bounds_check->InputAt(1);
DCHECK(array_length->IsIntConstant() ||
array_length->IsArrayLength() ||
array_length->IsPhi());
-
- if (array_length->IsPhi()) {
- // Input 1 of the phi contains the real array.length once the loop body is
- // entered. That value will be used for bound analysis. The graph is still
- // strictly in SSA form.
- array_length = array_length->AsPhi()->InputAt(1)->AsArrayLength();
- }
+ bool try_dynamic_bce = true;
if (!index->IsIntConstant()) {
+ // Non-constant subscript.
ValueBound lower = ValueBound(nullptr, 0); // constant 0
ValueBound upper = ValueBound(array_length, -1); // array_length - 1
ValueRange array_range(GetGraph()->GetArena(), lower, upper);
- // Try range obtained by local analysis.
+ // Try range obtained by dominator-based analysis.
ValueRange* index_range = LookupValueRange(index, block);
if (index_range != nullptr && index_range->FitsIn(&array_range)) {
- ReplaceBoundsCheck(bounds_check, index);
+ ReplaceInstruction(bounds_check, index);
return;
}
// Try range obtained by induction variable analysis.
- index_range = LookupInductionRange(bounds_check, index);
- if (index_range != nullptr && index_range->FitsIn(&array_range)) {
- ReplaceBoundsCheck(bounds_check, index);
+ // Disables dynamic bce if OOB is certain.
+ if (InductionRangeFitsIn(&array_range, bounds_check, index, &try_dynamic_bce)) {
+ ReplaceInstruction(bounds_check, index);
return;
}
} else {
+ // Constant subscript.
int32_t constant = index->AsIntConstant()->GetValue();
if (constant < 0) {
// Will always throw exception.
@@ -1439,7 +804,7 @@
}
if (array_length->IsIntConstant()) {
if (constant < array_length->AsIntConstant()->GetValue()) {
- ReplaceBoundsCheck(bounds_check, index);
+ ReplaceInstruction(bounds_check, index);
}
return;
}
@@ -1450,7 +815,7 @@
ValueBound lower = existing_range->GetLower();
DCHECK(lower.IsConstant());
if (constant < lower.GetConstant()) {
- ReplaceBoundsCheck(bounds_check, index);
+ ReplaceInstruction(bounds_check, index);
return;
} else {
// Existing range isn't strong enough to eliminate the bounds check.
@@ -1485,11 +850,11 @@
ValueRange(GetGraph()->GetArena(), lower, upper);
GetValueRangeMap(block)->Overwrite(array_length->GetId(), range);
}
- }
- void ReplaceBoundsCheck(HInstruction* bounds_check, HInstruction* index) {
- bounds_check->ReplaceWith(index);
- bounds_check->GetBlock()->RemoveInstruction(bounds_check);
+ // If static analysis fails, and OOB is not certain, try dynamic elimination.
+ if (try_dynamic_bce) {
+ TryDynamicBCE(bounds_check);
+ }
}
static bool HasSameInputAtBackEdges(HPhi* phi) {
@@ -1508,7 +873,7 @@
return true;
}
- void VisitPhi(HPhi* phi) {
+ void VisitPhi(HPhi* phi) OVERRIDE {
if (phi->IsLoopHeaderPhi()
&& (phi->GetType() == Primitive::kPrimInt)
&& HasSameInputAtBackEdges(phi)) {
@@ -1555,7 +920,7 @@
}
}
- void VisitIf(HIf* instruction) {
+ void VisitIf(HIf* instruction) OVERRIDE {
if (instruction->InputAt(0)->IsCondition()) {
HCondition* cond = instruction->InputAt(0)->AsCondition();
IfCondition cmp = cond->GetCondition();
@@ -1564,42 +929,11 @@
HInstruction* left = cond->GetLeft();
HInstruction* right = cond->GetRight();
HandleIf(instruction, left, right, cmp);
-
- HBasicBlock* block = instruction->GetBlock();
- ValueRange* left_range = LookupValueRange(left, block);
- if (left_range == nullptr) {
- return;
- }
-
- if (left_range->IsMonotonicValueRange() &&
- block == left_range->AsMonotonicValueRange()->GetLoopHeader()) {
- // The comparison is for an induction variable in the loop header.
- DCHECK(left == left_range->AsMonotonicValueRange()->GetInductionVariable());
- HBasicBlock* loop_body_successor =
- left_range->AsMonotonicValueRange()->GetLoopHeaderSuccesorInLoop();
- if (loop_body_successor == nullptr) {
- // In case it's some strange loop structure.
- return;
- }
- ValueRange* new_left_range = LookupValueRange(left, loop_body_successor);
- if ((new_left_range == left_range) ||
- // Range narrowed with deoptimization is usually more useful than
- // a constant range.
- new_left_range->IsConstantValueRange()) {
- // We are not successful in narrowing the monotonic value range to
- // a regular value range. Try using deoptimization.
- new_left_range = left_range->AsMonotonicValueRange()->
- NarrowWithDeoptimization();
- if (new_left_range != left_range) {
- GetValueRangeMap(loop_body_successor)->Overwrite(left->GetId(), new_left_range);
- }
- }
- }
}
}
}
- void VisitAdd(HAdd* add) {
+ void VisitAdd(HAdd* add) OVERRIDE {
HInstruction* right = add->GetRight();
if (right->IsIntConstant()) {
ValueRange* left_range = LookupValueRange(add->GetLeft(), add->GetBlock());
@@ -1613,7 +947,7 @@
}
}
- void VisitSub(HSub* sub) {
+ void VisitSub(HSub* sub) OVERRIDE {
HInstruction* left = sub->GetLeft();
HInstruction* right = sub->GetRight();
if (right->IsIntConstant()) {
@@ -1715,19 +1049,19 @@
}
}
- void VisitDiv(HDiv* div) {
+ void VisitDiv(HDiv* div) OVERRIDE {
FindAndHandlePartialArrayLength(div);
}
- void VisitShr(HShr* shr) {
+ void VisitShr(HShr* shr) OVERRIDE {
FindAndHandlePartialArrayLength(shr);
}
- void VisitUShr(HUShr* ushr) {
+ void VisitUShr(HUShr* ushr) OVERRIDE {
FindAndHandlePartialArrayLength(ushr);
}
- void VisitAnd(HAnd* instruction) {
+ void VisitAnd(HAnd* instruction) OVERRIDE {
if (instruction->GetRight()->IsIntConstant()) {
int32_t constant = instruction->GetRight()->AsIntConstant()->GetValue();
if (constant > 0) {
@@ -1742,7 +1076,7 @@
}
}
- void VisitNewArray(HNewArray* new_array) {
+ void VisitNewArray(HNewArray* new_array) OVERRIDE {
HInstruction* len = new_array->InputAt(0);
if (!len->IsIntConstant()) {
HInstruction *left;
@@ -1766,9 +1100,12 @@
}
}
- void VisitDeoptimize(HDeoptimize* deoptimize) {
- // Right now it's only HLessThanOrEqual.
- DCHECK(deoptimize->InputAt(0)->IsLessThanOrEqual());
+ void VisitDeoptimize(HDeoptimize* deoptimize) OVERRIDE {
+ if (!deoptimize->InputAt(0)->IsLessThanOrEqual()) {
+ return;
+ }
+ // If this instruction was added by AddCompareWithDeoptimization(), narrow
+ // the range accordingly in subsequent basic blocks.
HLessThanOrEqual* less_than_or_equal = deoptimize->InputAt(0)->AsLessThanOrEqual();
HInstruction* instruction = less_than_or_equal->InputAt(0);
if (instruction->IsArrayLength()) {
@@ -1782,6 +1119,35 @@
}
}
+ /**
+ * After null/bounds checks are eliminated, some invariant array references
+ * may be exposed underneath which can be hoisted out of the loop to the
+ * preheader or, in combination with dynamic bce, the deoptimization block.
+ *
+ * for (int i = 0; i < n; i++) {
+ * <-------+
+ * for (int j = 0; j < n; j++) |
+ * a[i][j] = 0; --a[i]--+
+ * }
+ *
+ * Note: this optimization is no longer applied after deoptimization on array references
+ * with constant subscripts has occurred (see AddCompareWithDeoptimization()), since in
+ * those cases it would be unsafe to hoist array references across their deoptimization
+ * instruction inside a loop.
+ */
+ void VisitArrayGet(HArrayGet* array_get) OVERRIDE {
+ if (!has_deoptimization_on_constant_subscripts_ && array_get->IsInLoop()) {
+ HLoopInformation* loop = array_get->GetBlock()->GetLoopInformation();
+ if (loop->IsLoopInvariant(array_get->InputAt(0), false) &&
+ loop->IsLoopInvariant(array_get->InputAt(1), false)) {
+ SideEffects loop_effects = side_effects_.GetLoopEffects(loop->GetHeader());
+ if (!array_get->GetSideEffects().MayDependOn(loop_effects)) {
+ HoistToPreheaderOrDeoptBlock(loop, array_get);
+ }
+ }
+ }
+ }
+
void AddCompareWithDeoptimization(HInstruction* array_length,
HIntConstant* const_instr,
HBasicBlock* block) {
@@ -1803,6 +1169,9 @@
block->InsertInstructionBefore(cond, bounds_check);
block->InsertInstructionBefore(deoptimize, bounds_check);
deoptimize->CopyEnvironmentFrom(bounds_check->GetEnvironment());
+ // Flag that this kind of deoptimization on array references with constant
+ // subscripts has occurred to prevent further hoisting of these references.
+ has_deoptimization_on_constant_subscripts_ = true;
}
void AddComparesWithDeoptimization(HBasicBlock* block) {
@@ -1846,21 +1215,425 @@
}
}
+ /**
+ * Returns true if static range analysis based on induction variables can determine the bounds
+ * check on the given array range is always satisfied with the computed index range. The output
+ * parameter try_dynamic_bce is set to false if OOB is certain.
+ */
+ bool InductionRangeFitsIn(ValueRange* array_range,
+ HInstruction* context,
+ HInstruction* index,
+ bool* try_dynamic_bce) {
+ InductionVarRange::Value v1;
+ InductionVarRange::Value v2;
+ bool needs_finite_test = false;
+ induction_range_.GetInductionRange(context, index, &v1, &v2, &needs_finite_test);
+ if (v1.is_known && (v1.a_constant == 0 || v1.a_constant == 1) &&
+ v2.is_known && (v2.a_constant == 0 || v2.a_constant == 1)) {
+ DCHECK(v1.a_constant == 1 || v1.instruction == nullptr);
+ DCHECK(v2.a_constant == 1 || v2.instruction == nullptr);
+ ValueRange index_range(GetGraph()->GetArena(),
+ ValueBound(v1.instruction, v1.b_constant),
+ ValueBound(v2.instruction, v2.b_constant));
+ // If analysis reveals a certain OOB, disable dynamic BCE.
+ *try_dynamic_bce = !index_range.GetLower().LessThan(array_range->GetLower()) &&
+ !index_range.GetUpper().GreaterThan(array_range->GetUpper());
+ // Use analysis for static bce only if loop is finite.
+ return !needs_finite_test && index_range.FitsIn(array_range);
+ }
+ return false;
+ }
+
+ /**
+ * When the compiler fails to remove a bounds check statically, we try to remove the bounds
+ * check dynamically by adding runtime tests that trigger a deoptimization in case bounds
+ * will go out of range (we want to be rather certain of that given the slowdown of
+ * deoptimization). If no deoptimization occurs, the loop is executed with all corresponding
+ * bounds checks and related null checks removed.
+ */
+ void TryDynamicBCE(HBoundsCheck* instruction) {
+ HLoopInformation* loop = instruction->GetBlock()->GetLoopInformation();
+ HInstruction* index = instruction->InputAt(0);
+ HInstruction* length = instruction->InputAt(1);
+ // If dynamic bounds check elimination seems profitable and is possible, then proceed.
+ bool needs_finite_test = false;
+ bool needs_taken_test = false;
+ if (DynamicBCESeemsProfitable(loop, instruction->GetBlock()) &&
+ induction_range_.CanGenerateCode(
+ instruction, index, &needs_finite_test, &needs_taken_test) &&
+ CanHandleInfiniteLoop(loop, index, needs_finite_test) &&
+ CanHandleLength(loop, length, needs_taken_test)) { // do this test last (may code gen)
+ HInstruction* lower = nullptr;
+ HInstruction* upper = nullptr;
+ // Generate the following unsigned comparisons
+ // if (lower > upper) deoptimize;
+ // if (upper >= length) deoptimize;
+ // or, for a non-induction index, just the unsigned comparison on its 'upper' value
+ // if (upper >= length) deoptimize;
+ // as runtime test. By restricting dynamic bce to unit strides (with a maximum of 32-bit
+ // iterations) and by not combining access (e.g. a[i], a[i-3], a[i+5] etc.), these tests
+ // correctly guard against any possible OOB (including arithmetic wrap-around cases).
+ HBasicBlock* block = TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
+ induction_range_.GenerateRangeCode(instruction, index, GetGraph(), block, &lower, &upper);
+ if (lower != nullptr) {
+ InsertDeopt(loop, block, new (GetGraph()->GetArena()) HAbove(lower, upper));
+ }
+ InsertDeopt(loop, block, new (GetGraph()->GetArena()) HAboveOrEqual(upper, length));
+ ReplaceInstruction(instruction, index);
+ }
+ }
+
+ /**
+ * Returns true if heuristics indicate that dynamic bce may be profitable.
+ */
+ bool DynamicBCESeemsProfitable(HLoopInformation* loop, HBasicBlock* block) {
+ if (loop != nullptr) {
+ // A try boundary preheader is hard to handle.
+ // TODO: remove this restriction
+ if (loop->GetPreHeader()->GetLastInstruction()->IsTryBoundary()) {
+ return false;
+ }
+ // Does loop have early-exits? If so, the full range may not be covered by the loop
+ // at runtime and testing the range may apply deoptimization unnecessarily.
+ if (IsEarlyExitLoop(loop)) {
+ return false;
+ }
+ // Does the current basic block dominate all back edges? If not,
+ // don't apply dynamic bce to something that may not be executed.
+ for (HBasicBlock* back_edge : loop->GetBackEdges()) {
+ if (!block->Dominates(back_edge)) {
+ return false;
+ }
+ }
+ // Success!
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Returns true if the loop has early exits, which implies it may not cover
+ * the full range computed by range analysis based on induction variables.
+ */
+ bool IsEarlyExitLoop(HLoopInformation* loop) {
+ const uint32_t loop_id = loop->GetHeader()->GetBlockId();
+ // If loop has been analyzed earlier for early-exit, don't repeat the analysis.
+ auto it = early_exit_loop_.find(loop_id);
+ if (it != early_exit_loop_.end()) {
+ return it->second;
+ }
+ // First time early-exit analysis for this loop. Since analysis requires scanning
+ // the full loop-body, results of the analysis is stored for subsequent queries.
+ HBlocksInLoopReversePostOrderIterator it_loop(*loop);
+ for (it_loop.Advance(); !it_loop.Done(); it_loop.Advance()) {
+ for (HBasicBlock* successor : it_loop.Current()->GetSuccessors()) {
+ if (!loop->Contains(*successor)) {
+ early_exit_loop_.Put(loop_id, true);
+ return true;
+ }
+ }
+ }
+ early_exit_loop_.Put(loop_id, false);
+ return false;
+ }
+
+ /**
+ * Returns true if the array length is already loop invariant, or can be made so
+ * by handling the null check under the hood of the array length operation.
+ */
+ bool CanHandleLength(HLoopInformation* loop, HInstruction* length, bool needs_taken_test) {
+ if (loop->IsLoopInvariant(length, false)) {
+ return true;
+ } else if (length->IsArrayLength() && length->GetBlock()->GetLoopInformation() == loop) {
+ if (CanHandleNullCheck(loop, length->InputAt(0), needs_taken_test)) {
+ HoistToPreheaderOrDeoptBlock(loop, length);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Returns true if the null check is already loop invariant, or can be made so
+ * by generating a deoptimization test.
+ */
+ bool CanHandleNullCheck(HLoopInformation* loop, HInstruction* check, bool needs_taken_test) {
+ if (loop->IsLoopInvariant(check, false)) {
+ return true;
+ } else if (check->IsNullCheck() && check->GetBlock()->GetLoopInformation() == loop) {
+ HInstruction* array = check->InputAt(0);
+ if (loop->IsLoopInvariant(array, false)) {
+ // Generate: if (array == null) deoptimize;
+ HBasicBlock* block = TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
+ HInstruction* cond =
+ new (GetGraph()->GetArena()) HEqual(array, GetGraph()->GetNullConstant());
+ InsertDeopt(loop, block, cond);
+ ReplaceInstruction(check, array);
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Returns true if compiler can apply dynamic bce to loops that may be infinite
+ * (e.g. for (int i = 0; i <= U; i++) with U = MAX_INT), which would invalidate
+ * the range analysis evaluation code by "overshooting" the computed range.
+ * Since deoptimization would be a bad choice, and there is no other version
+ * of the loop to use, dynamic bce in such cases is only allowed if other tests
+ * ensure the loop is finite.
+ */
+ bool CanHandleInfiniteLoop(
+ HLoopInformation* loop, HInstruction* index, bool needs_infinite_test) {
+ if (needs_infinite_test) {
+ // If we already forced the loop to be finite, allow directly.
+ const uint32_t loop_id = loop->GetHeader()->GetBlockId();
+ if (finite_loop_.find(loop_id) != finite_loop_.end()) {
+ return true;
+ }
+ // Otherwise, allow dynamic bce if the index (which is necessarily an induction at
+ // this point) is the direct loop index (viz. a[i]), since then the runtime tests
+ // ensure upper bound cannot cause an infinite loop.
+ HInstruction* control = loop->GetHeader()->GetLastInstruction();
+ if (control->IsIf()) {
+ HInstruction* if_expr = control->AsIf()->InputAt(0);
+ if (if_expr->IsCondition()) {
+ HCondition* condition = if_expr->AsCondition();
+ if (index == condition->InputAt(0) ||
+ index == condition->InputAt(1)) {
+ finite_loop_.insert(loop_id);
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+ return true;
+ }
+
+ /** Inserts a deoptimization test. */
+ void InsertDeopt(HLoopInformation* loop, HBasicBlock* block, HInstruction* condition) {
+ HInstruction* suspend = loop->GetSuspendCheck();
+ block->InsertInstructionBefore(condition, block->GetLastInstruction());
+ HDeoptimize* deoptimize =
+ new (GetGraph()->GetArena()) HDeoptimize(condition, suspend->GetDexPc());
+ block->InsertInstructionBefore(deoptimize, block->GetLastInstruction());
+ if (suspend->HasEnvironment()) {
+ deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment(
+ suspend->GetEnvironment(), loop->GetHeader());
+ }
+ }
+
+ /** Hoists instruction out of the loop to preheader or deoptimization block. */
+ void HoistToPreheaderOrDeoptBlock(HLoopInformation* loop, HInstruction* instruction) {
+ // Use preheader unless there is an earlier generated deoptimization block since
+ // hoisted expressions may depend on and/or used by the deoptimization tests.
+ const uint32_t loop_id = loop->GetHeader()->GetBlockId();
+ HBasicBlock* preheader = loop->GetPreHeader();
+ HBasicBlock* block = preheader;
+ auto it = taken_test_loop_.find(loop_id);
+ if (it != taken_test_loop_.end()) {
+ block = it->second;
+ }
+ // Hoist the instruction.
+ DCHECK(!instruction->HasEnvironment());
+ instruction->MoveBefore(block->GetLastInstruction());
+ }
+
+ /**
+ * Adds a new taken-test structure to a loop if needed (and not already done).
+ * The taken-test protects range analysis evaluation code to avoid any
+ * deoptimization caused by incorrect trip-count evaluation in non-taken loops.
+ *
+ * Returns block in which deoptimizations/invariants can be put.
+ *
+ * old_preheader
+ * |
+ * if_block <- taken-test protects deoptimization block
+ * / \
+ * true_block false_block <- deoptimizations/invariants are placed in true_block
+ * \ /
+ * new_preheader <- may require phi nodes to preserve SSA structure
+ * |
+ * header
+ *
+ * For example, this loop:
+ *
+ * for (int i = lower; i < upper; i++) {
+ * array[i] = 0;
+ * }
+ *
+ * will be transformed to:
+ *
+ * if (lower < upper) {
+ * if (array == null) deoptimize;
+ * array_length = array.length;
+ * if (lower > upper) deoptimize; // unsigned
+ * if (upper >= array_length) deoptimize; // unsigned
+ * } else {
+ * array_length = 0;
+ * }
+ * for (int i = lower; i < upper; i++) {
+ * // Loop without null check and bounds check, and any array.length replaced with array_length.
+ * array[i] = 0;
+ * }
+ */
+ HBasicBlock* TransformLoopForDeoptimizationIfNeeded(HLoopInformation* loop, bool needs_taken_test) {
+ // Not needed (can use preheader), or already done (can reuse)?
+ const uint32_t loop_id = loop->GetHeader()->GetBlockId();
+ if (!needs_taken_test) {
+ return loop->GetPreHeader();
+ } else {
+ auto it = taken_test_loop_.find(loop_id);
+ if (it != taken_test_loop_.end()) {
+ return it->second;
+ }
+ }
+
+ // Generate top test structure.
+ HBasicBlock* header = loop->GetHeader();
+ GetGraph()->TransformLoopHeaderForBCE(header);
+ HBasicBlock* new_preheader = loop->GetPreHeader();
+ HBasicBlock* if_block = new_preheader->GetDominator();
+ HBasicBlock* true_block = if_block->GetSuccessors()[0]; // True successor.
+ HBasicBlock* false_block = if_block->GetSuccessors()[1]; // False successor.
+
+ // Goto instructions.
+ true_block->AddInstruction(new (GetGraph()->GetArena()) HGoto());
+ false_block->AddInstruction(new (GetGraph()->GetArena()) HGoto());
+ new_preheader->AddInstruction(new (GetGraph()->GetArena()) HGoto());
+
+ // Insert the taken-test to see if the loop body is entered. If the
+ // loop isn't entered at all, it jumps around the deoptimization block.
+ if_block->AddInstruction(new (GetGraph()->GetArena()) HGoto()); // placeholder
+ HInstruction* condition = nullptr;
+ induction_range_.GenerateTakenTest(header->GetLastInstruction(),
+ GetGraph(),
+ if_block,
+ &condition);
+ DCHECK(condition != nullptr);
+ if_block->RemoveInstruction(if_block->GetLastInstruction());
+ if_block->AddInstruction(new (GetGraph()->GetArena()) HIf(condition));
+
+ taken_test_loop_.Put(loop_id, true_block);
+ return true_block;
+ }
+
+ /**
+ * Inserts phi nodes that preserve SSA structure in generated top test structures.
+ * All uses of instructions in the deoptimization block that reach the loop need
+ * a phi node in the new loop preheader to fix the dominance relation.
+ *
+ * Example:
+ * if_block
+ * / \
+ * x_0 = .. false_block
+ * \ /
+ * x_1 = phi(x_0, null) <- synthetic phi
+ * |
+ * header
+ */
+ void InsertPhiNodes() {
+ // Scan all new deoptimization blocks.
+ for (auto it1 = taken_test_loop_.begin(); it1 != taken_test_loop_.end(); ++it1) {
+ HBasicBlock* true_block = it1->second;
+ HBasicBlock* new_preheader = true_block->GetSingleSuccessor();
+ // Scan all instructions in a new deoptimization block.
+ for (HInstructionIterator it(true_block->GetInstructions()); !it.Done(); it.Advance()) {
+ HInstruction* instruction = it.Current();
+ Primitive::Type type = instruction->GetType();
+ HPhi* phi = nullptr;
+ // Scan all uses of an instruction and replace each later use with a phi node.
+ for (HUseIterator<HInstruction*> it2(instruction->GetUses());
+ !it2.Done();
+ it2.Advance()) {
+ HInstruction* user = it2.Current()->GetUser();
+ if (user->GetBlock() != true_block) {
+ if (phi == nullptr) {
+ phi = NewPhi(new_preheader, instruction, type);
+ }
+ user->ReplaceInput(phi, it2.Current()->GetIndex());
+ }
+ }
+ // Scan all environment uses of an instruction and replace each later use with a phi node.
+ for (HUseIterator<HEnvironment*> it2(instruction->GetEnvUses());
+ !it2.Done();
+ it2.Advance()) {
+ HEnvironment* user = it2.Current()->GetUser();
+ if (user->GetHolder()->GetBlock() != true_block) {
+ if (phi == nullptr) {
+ phi = NewPhi(new_preheader, instruction, type);
+ }
+ user->RemoveAsUserOfInput(it2.Current()->GetIndex());
+ user->SetRawEnvAt(it2.Current()->GetIndex(), phi);
+ phi->AddEnvUseAt(user, it2.Current()->GetIndex());
+ }
+ }
+ }
+ }
+ }
+
+ /**
+ * Construct a phi(instruction, 0) in the new preheader to fix the dominance relation.
+ * These are synthetic phi nodes without a virtual register.
+ */
+ HPhi* NewPhi(HBasicBlock* new_preheader,
+ HInstruction* instruction,
+ Primitive::Type type) {
+ HGraph* graph = GetGraph();
+ HInstruction* zero;
+ switch (type) {
+ case Primitive::Type::kPrimNot: zero = graph->GetNullConstant(); break;
+ case Primitive::Type::kPrimFloat: zero = graph->GetFloatConstant(0); break;
+ case Primitive::Type::kPrimDouble: zero = graph->GetDoubleConstant(0); break;
+ default: zero = graph->GetConstant(type, 0); break;
+ }
+ HPhi* phi = new (graph->GetArena())
+ HPhi(graph->GetArena(), kNoRegNumber, /*number_of_inputs*/ 2, HPhi::ToPhiType(type));
+ phi->SetRawInputAt(0, instruction);
+ phi->SetRawInputAt(1, zero);
+ new_preheader->AddPhi(phi);
+ return phi;
+ }
+
+ /** Helper method to replace an instruction with another instruction. */
+ static void ReplaceInstruction(HInstruction* instruction, HInstruction* replacement) {
+ instruction->ReplaceWith(replacement);
+ instruction->GetBlock()->RemoveInstruction(instruction);
+ }
+
+ // A set of maps, one per basic block, from instruction to range.
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.
ArenaSafeMap<int, HBoundsCheck*> first_constant_index_bounds_check_map_;
+ // Early-exit loop bookkeeping.
+ ArenaSafeMap<uint32_t, bool> early_exit_loop_;
+
+ // Taken-test loop bookkeeping.
+ ArenaSafeMap<uint32_t, HBasicBlock*> taken_test_loop_;
+
+ // Finite loop bookkeeping.
+ ArenaSet<uint32_t> finite_loop_;
+
// 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
// beneficial to add a compare instruction that has deoptimization fallback and
// eliminate those bounds checks.
bool need_to_revisit_block_;
+ // Flag that denotes whether deoptimization has occurred on array references
+ // with constant subscripts (see AddCompareWithDeoptimization()).
+ bool has_deoptimization_on_constant_subscripts_;
+
// Initial number of blocks.
uint32_t initial_block_size_;
+ // Side effects.
+ const SideEffectsAnalysis& side_effects_;
+
// Range analysis based on induction variables.
InductionVarRange induction_range_;
@@ -1872,14 +1645,12 @@
return;
}
- BCEVisitor visitor(graph_, induction_analysis_);
// Reverse post order guarantees a node's dominators are visited first.
// We want to visit in the dominator-based order since if a value is known to
// be bounded by a range at one instruction, it must be true that all uses of
// that value dominated by that instruction fits in that range. Range of that
// value can be narrowed further down in the dominator tree.
- //
- // TODO: only visit blocks that dominate some array accesses.
+ BCEVisitor visitor(graph_, side_effects_, induction_analysis_);
HBasicBlock* last_visited_block = nullptr;
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* current = it.Current();
@@ -1896,6 +1667,9 @@
visitor.VisitBasicBlock(current);
last_visited_block = current;
}
+
+ // Perform cleanup.
+ visitor.Finish();
}
} // namespace art
diff --git a/compiler/optimizing/bounds_check_elimination.h b/compiler/optimizing/bounds_check_elimination.h
index cdff3ca..b9df686 100644
--- a/compiler/optimizing/bounds_check_elimination.h
+++ b/compiler/optimizing/bounds_check_elimination.h
@@ -21,12 +21,16 @@
namespace art {
+class SideEffectsAnalysis;
class HInductionVarAnalysis;
class BoundsCheckElimination : public HOptimization {
public:
- BoundsCheckElimination(HGraph* graph, HInductionVarAnalysis* induction_analysis)
+ BoundsCheckElimination(HGraph* graph,
+ const SideEffectsAnalysis& side_effects,
+ HInductionVarAnalysis* induction_analysis)
: HOptimization(graph, kBoundsCheckEliminiationPassName),
+ side_effects_(side_effects),
induction_analysis_(induction_analysis) {}
void Run() OVERRIDE;
@@ -34,6 +38,7 @@
static constexpr const char* kBoundsCheckEliminiationPassName = "BCE";
private:
+ const SideEffectsAnalysis& side_effects_;
HInductionVarAnalysis* induction_analysis_;
DISALLOW_COPY_AND_ASSIGN(BoundsCheckElimination);
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index c9afdf2..dbeb1cc 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -54,7 +54,7 @@
HInductionVarAnalysis induction(graph_);
induction.Run();
- BoundsCheckElimination(graph_, &induction).Run();
+ BoundsCheckElimination(graph_, side_effects, &induction).Run();
}
ArenaPool pool_;
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 5814d75..b3b09d2 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -735,26 +735,29 @@
}
}
- // Test phi equivalents. There should not be two of the same type and they
- // should only be created for constants which were untyped in DEX.
- for (HInstructionIterator phi_it(phi->GetBlock()->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
- HPhi* other_phi = phi_it.Current()->AsPhi();
- if (phi != other_phi && phi->GetRegNumber() == other_phi->GetRegNumber()) {
- if (phi->GetType() == other_phi->GetType()) {
- std::stringstream type_str;
- type_str << phi->GetType();
- AddError(StringPrintf("Equivalent phi (%d) found for VReg %d with type: %s.",
- phi->GetId(),
- phi->GetRegNumber(),
- type_str.str().c_str()));
- } else {
- ArenaBitVector visited(GetGraph()->GetArena(), 0, /* expandable */ true);
- if (!IsConstantEquivalent(phi, other_phi, &visited)) {
- AddError(StringPrintf("Two phis (%d and %d) found for VReg %d but they "
- "are not equivalents of constants.",
+ // Test phi equivalents. There should not be two of the same type and they should only be
+ // created for constants which were untyped in DEX. Note that this test can be skipped for
+ // a synthetic phi (indicated by lack of a virtual register).
+ if (phi->GetRegNumber() != kNoRegNumber) {
+ for (HInstructionIterator phi_it(phi->GetBlock()->GetPhis()); !phi_it.Done(); phi_it.Advance()) {
+ HPhi* other_phi = phi_it.Current()->AsPhi();
+ if (phi != other_phi && phi->GetRegNumber() == other_phi->GetRegNumber()) {
+ if (phi->GetType() == other_phi->GetType()) {
+ std::stringstream type_str;
+ type_str << phi->GetType();
+ AddError(StringPrintf("Equivalent phi (%d) found for VReg %d with type: %s.",
phi->GetId(),
- other_phi->GetId(),
- phi->GetRegNumber()));
+ phi->GetRegNumber(),
+ type_str.str().c_str()));
+ } else {
+ ArenaBitVector visited(GetGraph()->GetArena(), 0, /* expandable */ true);
+ if (!IsConstantEquivalent(phi, other_phi, &visited)) {
+ AddError(StringPrintf("Two phis (%d and %d) found for VReg %d but they "
+ "are not equivalents of constants.",
+ phi->GetId(),
+ other_phi->GetId(),
+ phi->GetRegNumber()));
+ }
}
}
}
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index b40ef5a..433c8f8 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -425,9 +425,13 @@
}
HInductionVarAnalysis::InductionInfo* trip =
induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
- // Determine what tests are needed.
+ // Determine what tests are needed. A finite test is needed if the evaluation code uses the
+ // trip-count and the loop maybe unsafe (because in such cases, the index could "overshoot"
+ // the computed range). A taken test is needed for any unknown trip-count, even if evaluation
+ // code does not use the trip-count explicitly (since there could be an implicit relation
+ // between e.g. an invariant subscript and a not-taken condition).
*needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
- *needs_taken_test = NeedsTripCount(info) && IsBodyTripCount(trip);
+ *needs_taken_test = IsBodyTripCount(trip);
// Code generation for taken test: generate the code when requested or otherwise analyze
// if code generation is feasible when taken test is needed.
if (taken_test != nullptr) {
@@ -545,29 +549,42 @@
}
break;
case HInductionVarAnalysis::kLinear: {
- // Linear induction a * i + b, for normalized 0 <= i < TC. Restrict to unit stride only
- // to avoid arithmetic wrap-around situations that are hard to guard against.
- int32_t stride_value = 0;
- if (GetConstant(info->op_a, &stride_value)) {
- if (stride_value == 1 || stride_value == -1) {
- const bool is_min_a = stride_value == 1 ? is_min : !is_min;
- if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) &&
- GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
- if (graph != nullptr) {
- HInstruction* oper;
- if (stride_value == 1) {
- oper = new (graph->GetArena()) HAdd(type, opa, opb);
- } else {
- oper = new (graph->GetArena()) HSub(type, opb, opa);
- }
- *result = Insert(block, oper);
+ // Linear induction a * i + b, for normalized 0 <= i < TC. Restrict to unit stride only
+ // to avoid arithmetic wrap-around situations that are hard to guard against.
+ int32_t stride_value = 0;
+ if (GetConstant(info->op_a, &stride_value)) {
+ if (stride_value == 1 || stride_value == -1) {
+ const bool is_min_a = stride_value == 1 ? is_min : !is_min;
+ if (GenerateCode(trip, trip, graph, block, &opa, in_body, is_min_a) &&
+ GenerateCode(info->op_b, trip, graph, block, &opb, in_body, is_min)) {
+ if (graph != nullptr) {
+ HInstruction* oper;
+ if (stride_value == 1) {
+ oper = new (graph->GetArena()) HAdd(type, opa, opb);
+ } else {
+ oper = new (graph->GetArena()) HSub(type, opb, opa);
}
- return true;
+ *result = Insert(block, oper);
}
+ return true;
}
}
}
break;
+ }
+ case HInductionVarAnalysis::kWrapAround:
+ case HInductionVarAnalysis::kPeriodic: {
+ // Wrap-around and periodic inductions are restricted to constants only, so that extreme
+ // values are easy to test at runtime without complications of arithmetic wrap-around.
+ Value extreme = GetVal(info, trip, in_body, is_min);
+ if (extreme.is_known && extreme.a_constant == 0) {
+ if (graph != nullptr) {
+ *result = graph->GetIntConstant(extreme.b_constant);
+ }
+ return true;
+ }
+ break;
+ }
default:
break;
}
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 0a39ff3..b76bce4 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1890,7 +1890,7 @@
* |
* if_block
* / \
- * dummy_block deopt_block
+ * true_block false_block
* \ /
* new_pre_header
* |
@@ -1898,62 +1898,73 @@
*/
void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) {
DCHECK(header->IsLoopHeader());
- HBasicBlock* pre_header = header->GetDominator();
+ HBasicBlock* old_pre_header = header->GetDominator();
- // Need this to avoid critical edge.
+ // Need extra block to avoid critical edge.
HBasicBlock* if_block = new (arena_) HBasicBlock(this, header->GetDexPc());
- // Need this to avoid critical edge.
- HBasicBlock* dummy_block = new (arena_) HBasicBlock(this, header->GetDexPc());
- HBasicBlock* deopt_block = new (arena_) HBasicBlock(this, header->GetDexPc());
+ HBasicBlock* true_block = new (arena_) HBasicBlock(this, header->GetDexPc());
+ HBasicBlock* false_block = new (arena_) HBasicBlock(this, header->GetDexPc());
HBasicBlock* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
AddBlock(if_block);
- AddBlock(dummy_block);
- AddBlock(deopt_block);
+ AddBlock(true_block);
+ AddBlock(false_block);
AddBlock(new_pre_header);
- header->ReplacePredecessor(pre_header, new_pre_header);
- pre_header->successors_.clear();
- pre_header->dominated_blocks_.clear();
+ header->ReplacePredecessor(old_pre_header, new_pre_header);
+ old_pre_header->successors_.clear();
+ old_pre_header->dominated_blocks_.clear();
- pre_header->AddSuccessor(if_block);
- if_block->AddSuccessor(dummy_block); // True successor
- if_block->AddSuccessor(deopt_block); // False successor
- dummy_block->AddSuccessor(new_pre_header);
- deopt_block->AddSuccessor(new_pre_header);
+ old_pre_header->AddSuccessor(if_block);
+ if_block->AddSuccessor(true_block); // True successor
+ if_block->AddSuccessor(false_block); // False successor
+ true_block->AddSuccessor(new_pre_header);
+ false_block->AddSuccessor(new_pre_header);
- pre_header->dominated_blocks_.push_back(if_block);
- if_block->SetDominator(pre_header);
- if_block->dominated_blocks_.push_back(dummy_block);
- dummy_block->SetDominator(if_block);
- if_block->dominated_blocks_.push_back(deopt_block);
- deopt_block->SetDominator(if_block);
+ old_pre_header->dominated_blocks_.push_back(if_block);
+ if_block->SetDominator(old_pre_header);
+ if_block->dominated_blocks_.push_back(true_block);
+ true_block->SetDominator(if_block);
+ if_block->dominated_blocks_.push_back(false_block);
+ false_block->SetDominator(if_block);
if_block->dominated_blocks_.push_back(new_pre_header);
new_pre_header->SetDominator(if_block);
new_pre_header->dominated_blocks_.push_back(header);
header->SetDominator(new_pre_header);
+ // Fix reverse post order.
size_t index_of_header = IndexOfElement(reverse_post_order_, header);
MakeRoomFor(&reverse_post_order_, 4, index_of_header - 1);
reverse_post_order_[index_of_header++] = if_block;
- reverse_post_order_[index_of_header++] = dummy_block;
- reverse_post_order_[index_of_header++] = deopt_block;
+ reverse_post_order_[index_of_header++] = true_block;
+ reverse_post_order_[index_of_header++] = false_block;
reverse_post_order_[index_of_header++] = new_pre_header;
- HLoopInformation* info = pre_header->GetLoopInformation();
- if (info != nullptr) {
- if_block->SetLoopInformation(info);
- dummy_block->SetLoopInformation(info);
- deopt_block->SetLoopInformation(info);
- new_pre_header->SetLoopInformation(info);
- for (HLoopInformationOutwardIterator loop_it(*pre_header);
+ // Fix loop information.
+ HLoopInformation* loop_info = old_pre_header->GetLoopInformation();
+ if (loop_info != nullptr) {
+ if_block->SetLoopInformation(loop_info);
+ true_block->SetLoopInformation(loop_info);
+ false_block->SetLoopInformation(loop_info);
+ new_pre_header->SetLoopInformation(loop_info);
+ // Add blocks to all enveloping loops.
+ for (HLoopInformationOutwardIterator loop_it(*old_pre_header);
!loop_it.Done();
loop_it.Advance()) {
loop_it.Current()->Add(if_block);
- loop_it.Current()->Add(dummy_block);
- loop_it.Current()->Add(deopt_block);
+ loop_it.Current()->Add(true_block);
+ loop_it.Current()->Add(false_block);
loop_it.Current()->Add(new_pre_header);
}
}
+
+ // Fix try/catch information.
+ TryCatchInformation* try_catch_info = old_pre_header->IsTryBlock()
+ ? old_pre_header->GetTryCatchInformation()
+ : nullptr;
+ if_block->SetTryCatchInformation(try_catch_info);
+ true_block->SetTryCatchInformation(try_catch_info);
+ false_block->SetTryCatchInformation(try_catch_info);
+ new_pre_header->SetTryCatchInformation(try_catch_info);
}
void HInstruction::SetReferenceTypeInfo(ReferenceTypeInfo rti) {
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 2204921..5194681 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -491,12 +491,13 @@
InstructionSimplifier* simplify1 = new (arena) InstructionSimplifier(graph, stats);
HBooleanSimplifier* boolean_simplify = new (arena) HBooleanSimplifier(graph);
HConstantFolding* fold2 = new (arena) HConstantFolding(graph, "constant_folding_after_inlining");
+ HConstantFolding* fold3 = new (arena) HConstantFolding(graph, "constant_folding_after_bce");
SideEffectsAnalysis* side_effects = new (arena) SideEffectsAnalysis(graph);
GVNOptimization* gvn = new (arena) GVNOptimization(graph, *side_effects);
LICM* licm = new (arena) LICM(graph, *side_effects);
LoadStoreElimination* lse = new (arena) LoadStoreElimination(graph, *side_effects);
HInductionVarAnalysis* induction = new (arena) HInductionVarAnalysis(graph);
- BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, induction);
+ BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, *side_effects, induction);
ReferenceTypePropagation* type_propagation =
new (arena) ReferenceTypePropagation(graph, &handles);
HSharpening* sharpening = new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver);
@@ -549,6 +550,7 @@
licm,
induction,
bce,
+ fold3, // evaluates code generated by dynamic bce
simplify3,
lse,
dce2,
diff --git a/test/449-checker-bce/src/Main.java b/test/449-checker-bce/src/Main.java
index ffeae7d..c3d2759 100644
--- a/test/449-checker-bce/src/Main.java
+++ b/test/449-checker-bce/src/Main.java
@@ -652,20 +652,19 @@
/// CHECK: ArraySet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
- // Added blocks for deoptimization.
+ // Added blocks at end for deoptimization.
+ /// CHECK: Exit
/// CHECK: If
- /// CHECK: Goto
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
- /// CHECK: Phi
+ /// CHECK: Goto
/// CHECK: Goto
void foo1(int[] array, int start, int end, boolean expectInterpreter) {
- // Three HDeoptimize will be added. One for
- // start >= 0, one for end <= array.length,
+ // Three HDeoptimize will be added. Two for the index
// and one for null check on array (to hoist null
// check and array.length out of loop).
for (int i = start ; i < end; i++) {
@@ -685,27 +684,25 @@
/// CHECK: ArraySet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
-
/// CHECK-START: void Main.foo2(int[], int, int, boolean) BCE (after)
/// CHECK: Phi
/// CHECK-NOT: BoundsCheck
/// CHECK: ArraySet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
- // Added blocks for deoptimization.
+ // Added blocks at end for deoptimization.
+ /// CHECK: Exit
/// CHECK: If
- /// CHECK: Goto
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
- /// CHECK: Phi
+ /// CHECK: Goto
/// CHECK: Goto
void foo2(int[] array, int start, int end, boolean expectInterpreter) {
- // Three HDeoptimize will be added. One for
- // start >= 0, one for end <= array.length,
+ // Three HDeoptimize will be added. Two for the index
// and one for null check on array (to hoist null
// check and array.length out of loop).
for (int i = start ; i <= end; i++) {
@@ -725,25 +722,25 @@
/// CHECK: ArraySet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
-
/// CHECK-START: void Main.foo3(int[], int, boolean) BCE (after)
/// CHECK: Phi
/// CHECK-NOT: BoundsCheck
/// CHECK: ArraySet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
- // Added blocks for deoptimization.
+ // Added blocks at end for deoptimization.
+ /// CHECK: Exit
/// CHECK: If
- /// CHECK: Goto
+ /// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
- /// CHECK: Phi
+ /// CHECK: Goto
/// CHECK: Goto
void foo3(int[] array, int end, boolean expectInterpreter) {
- // Two HDeoptimize will be added. One for end < array.length,
+ // Three HDeoptimize will be added. Two for the index
// and one for null check on array (to hoist null check
// and array.length out of loop).
for (int i = 3 ; i <= end; i++) {
@@ -770,18 +767,19 @@
/// CHECK: ArraySet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
- // Added blocks for deoptimization.
+ // Added blocks at end for deoptimization.
+ /// CHECK: Exit
/// CHECK: If
- /// CHECK: Goto
+ /// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
- /// CHECK: Phi
+ /// CHECK: Goto
/// CHECK: Goto
void foo4(int[] array, int end, boolean expectInterpreter) {
- // Two HDeoptimize will be added. One for end <= array.length,
+ // Three HDeoptimize will be added. Two for the index
// and one for null check on array (to hoist null check
// and array.length out of loop).
for (int i = end ; i > 0; i--) {
@@ -816,14 +814,18 @@
/// CHECK: ArrayGet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
- // Added blocks for deoptimization.
+ // Added blocks at end for deoptimization.
+ /// CHECK: Exit
/// CHECK: If
- /// CHECK: Goto
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
- // array.length is defined before the loop header so no phi is needed.
- /// CHECK-NOT: Phi
+ /// CHECK: Goto
/// CHECK: Goto
void foo5(int[] array, int end, boolean expectInterpreter) {
@@ -831,8 +833,8 @@
for (int i = array.length - 1 ; i >= 0; i--) {
array[i] = 1;
}
- // One HDeoptimize will be added.
- // It's for (end - 2 <= array.length - 2).
+ // Several HDeoptimize will be added. Two for each index.
+ // The null check is not necessary.
for (int i = end - 2 ; i > 0; i--) {
if (expectInterpreter) {
assertIsInterpreted();
@@ -859,7 +861,6 @@
/// CHECK: ArrayGet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArraySet
-
/// CHECK-START: void Main.foo6(int[], int, int, boolean) BCE (after)
/// CHECK: Phi
/// CHECK-NOT: BoundsCheck
@@ -874,23 +875,27 @@
/// CHECK: ArrayGet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArraySet
- // Added blocks for deoptimization.
+ // Added blocks at end for deoptimization.
+ /// CHECK: Exit
/// CHECK: If
- /// CHECK: Goto
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
- /// CHECK: Phi
/// CHECK: Goto
- /// CHECK-NOT: Deoptimize
+ /// CHECK: Goto
void foo6(int[] array, int start, int end, boolean expectInterpreter) {
- // Three HDeoptimize will be added. One for
- // start >= 2, one for end <= array.length - 3,
- // and one for null check on array (to hoist null
- // check and array.length out of loop).
+ // Several HDeoptimize will be added.
for (int i = end; i >= start; i--) {
if (expectInterpreter) {
assertIsInterpreted();
@@ -914,20 +919,19 @@
/// CHECK: ArrayGet
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
- // Added blocks for deoptimization.
+ // Added blocks at end for deoptimization.
+ /// CHECK: Exit
/// CHECK: If
- /// CHECK: Goto
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
- /// CHECK: Phi
+ /// CHECK: Goto
/// CHECK: Goto
void foo7(int[] array, int start, int end, boolean lowEnd) {
- // Three HDeoptimize will be added. One for
- // start >= 0, one for end <= array.length,
+ // Three HDeoptimize will be added. One for the index
// and one for null check on array (to hoist null
// check and array.length out of loop).
for (int i = start ; i < end; i++) {
@@ -955,26 +959,28 @@
/// CHECK: Phi
/// CHECK-NOT: BoundsCheck
/// CHECK: ArraySet
- // Added blocks for deoptimization.
+ // Added blocks at end for deoptimization.
+ /// CHECK: Exit
/// CHECK: If
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
/// CHECK: Goto
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
- /// CHECK: Deoptimize
+ /// CHECK: Goto
+ /// CHECK: Goto
+ /// CHECK: If
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Goto
- /// CHECK: Phi
+ /// CHECK: Goto
/// CHECK: Goto
void foo8(int[][] matrix, int start, int end) {
- // Three HDeoptimize will be added for the outer loop.
- // start >= 0, end <= matrix.length, and null check on matrix.
- // Three HDeoptimize will be added for the inner loop
- // start >= 0 (TODO: this may be optimized away),
- // end <= row.length, and null check on row.
+ // Three HDeoptimize will be added for the outer loop,
+ // two for the index, and null check on matrix. Same
+ // for the inner loop.
for (int i = start; i < end; i++) {
int[] row = matrix[i];
for (int j = start; j < end; j++) {
@@ -994,15 +1000,22 @@
// loop for loop body entry test.
/// CHECK: Deoptimize
/// CHECK: Deoptimize
+ /// CHECK: Deoptimize
/// CHECK-NOT: Deoptimize
/// CHECK: Phi
/// CHECK-NOT: NullCheck
/// CHECK-NOT: BoundsCheck
/// CHECK: ArrayGet
+ /// CHECK-START: void Main.foo9(int[], boolean) instruction_simplifier_after_bce (after)
+ // Simplification removes the redundant check
+ /// CHECK: Deoptimize
+ /// CHECK: Deoptimize
+ /// CHECK-NOT: Deoptimize
+
void foo9(int[] array, boolean expectInterpreter) {
- // Two HDeoptimize will be added. One for
- // 10 <= array.length, and one for null check on array.
+ // Two HDeoptimize will be added. Two for the index
+ // and one for null check on array.
for (int i = 0 ; i < 10; i++) {
if (expectInterpreter) {
assertIsInterpreted();
diff --git a/test/530-checker-loops/src/Main.java b/test/530-checker-loops/src/Main.java
index 58c92f1..4e0bf3c 100644
--- a/test/530-checker-loops/src/Main.java
+++ b/test/530-checker-loops/src/Main.java
@@ -29,6 +29,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linear(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linear(int[] x) {
int result = 0;
for (int i = 0; i < x.length; i++) {
@@ -41,6 +42,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearDown(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearDown(int[] x) {
int result = 0;
for (int i = x.length - 1; i >= 0; i--) {
@@ -53,6 +55,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearObscure(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearObscure(int[] x) {
int result = 0;
for (int i = x.length - 1; i >= 0; i--) {
@@ -66,6 +69,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearVeryObscure(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearVeryObscure(int[] x) {
int result = 0;
for (int i = 0; i < x.length; i++) {
@@ -79,6 +83,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWhile(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearWhile(int[] x) {
int i = 0;
int result = 0;
@@ -92,6 +97,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearThreeWayPhi(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearThreeWayPhi(int[] x) {
int result = 0;
for (int i = 0; i < x.length; ) {
@@ -108,6 +114,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearFourWayPhi(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearFourWayPhi(int[] x) {
int result = 0;
for (int i = 0; i < x.length; ) {
@@ -128,6 +135,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.wrapAroundThenLinear(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int wrapAroundThenLinear(int[] x) {
// Loop with wrap around (length - 1, 0, 1, 2, ..).
int w = x.length - 1;
@@ -143,6 +151,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.wrapAroundThenLinearThreeWayPhi(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int wrapAroundThenLinearThreeWayPhi(int[] x) {
// Loop with wrap around (length - 1, 0, 1, 2, ..).
int w = x.length - 1;
@@ -162,6 +171,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int[] Main.linearWithParameter(int) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int[] linearWithParameter(int n) {
int[] x = new int[n];
for (int i = 0; i < n; i++) {
@@ -174,6 +184,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int[] Main.linearCopy(int[]) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int[] linearCopy(int x[]) {
int n = x.length;
int y[] = new int[n];
@@ -183,10 +194,55 @@
return y;
}
+ /// CHECK-START: int Main.linearByTwo(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearByTwo(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ private static int linearByTwo(int x[]) {
+ int n = x.length / 2;
+ int result = 0;
+ for (int i = 0; i < n; i++) {
+ int ii = i << 1;
+ result += x[ii];
+ result += x[ii + 1];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearByTwoSkip1(int[]) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ private static int linearByTwoSkip1(int x[]) {
+ int result = 0;
+ for (int i = 0; i < x.length / 2; i++) {
+ result += x[2 * i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.linearByTwoSkip2(int[]) BCE (after)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ private static int linearByTwoSkip2(int x[]) {
+ int result = 0;
+ // This case is not optimized.
+ for (int i = 0; i < x.length; i+=2) {
+ result += x[i];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.linearWithCompoundStride() BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWithCompoundStride() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearWithCompoundStride() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
int result = 0;
@@ -202,6 +258,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWithLargePositiveStride() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearWithLargePositiveStride() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int result = 0;
@@ -218,6 +275,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWithVeryLargePositiveStride() BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearWithVeryLargePositiveStride() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int result = 0;
@@ -234,6 +292,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWithLargeNegativeStride() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearWithLargeNegativeStride() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int result = 0;
@@ -250,6 +309,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearWithVeryLargeNegativeStride() BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearWithVeryLargeNegativeStride() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
int result = 0;
@@ -266,6 +326,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearForNEUp() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearForNEUp() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -279,6 +340,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearForNEDown() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearForNEDown() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -292,6 +354,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearDoWhileUp() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearDoWhileUp() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -306,6 +369,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearDoWhileDown() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearDoWhileDown() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -320,6 +384,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.linearShort() BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int linearShort() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -330,10 +395,31 @@
return result;
}
+ /// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (before)
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.invariantFromPreLoop(int[], int) BCE (after)
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
+ private static int invariantFromPreLoop(int[] x, int y) {
+ int result = 0;
+ // Strange pre-loop that sets upper bound.
+ int hi;
+ while (true) {
+ y = y % 3;
+ hi = x.length;
+ if (y != 123) break;
+ }
+ for (int i = 0; i < hi; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
/// CHECK-START: int Main.periodicIdiom(int) BCE (before)
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.periodicIdiom(int) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int periodicIdiom(int tc) {
int[] x = { 1, 3 };
// Loop with periodic sequence (0, 1).
@@ -350,6 +436,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.periodicSequence2(int) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int periodicSequence2(int tc) {
int[] x = { 1, 3 };
// Loop with periodic sequence (0, 1).
@@ -372,6 +459,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.periodicSequence4(int) BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int periodicSequence4(int tc) {
int[] x = { 1, 3, 5, 7 };
// Loop with periodic sequence (0, 1, 2, 3).
@@ -395,6 +483,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.justRightUp1() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int justRightUp1() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -408,6 +497,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.justRightUp2() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int justRightUp2() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -421,6 +511,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.justRightUp3() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int justRightUp3() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -434,6 +525,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.justOOBUp() BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int justOOBUp() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -448,6 +540,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.justRightDown1() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int justRightDown1() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -461,6 +554,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.justRightDown2() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int justRightDown2() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -474,6 +568,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.justRightDown3() BCE (after)
/// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int justRightDown3() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -487,6 +582,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: int Main.justOOBDown() BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static int justOOBDown() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int result = 0;
@@ -501,6 +597,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: void Main.lowerOOB(int[]) BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static void lowerOOB(int[] x) {
for (int i = -1; i < x.length; i++) {
sResult += x[i];
@@ -511,6 +608,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: void Main.upperOOB(int[]) BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static void upperOOB(int[] x) {
for (int i = 0; i <= x.length; i++) {
sResult += x[i];
@@ -521,6 +619,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: void Main.doWhileUpOOB() BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static void doWhileUpOOB() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int i = 0;
@@ -533,6 +632,7 @@
/// CHECK-DAG: BoundsCheck
/// CHECK-START: void Main.doWhileDownOOB() BCE (after)
/// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: Deoptimize
private static void doWhileDownOOB() {
int[] x = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int i = x.length - 1;
@@ -541,6 +641,278 @@
} while (-1 <= i);
}
+ /// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (before)
+ /// CHECK-DAG: StaticFieldGet
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: StaticFieldSet
+ /// CHECK-START: int Main.linearDynamicBCE1(int[], int, int) BCE (after)
+ /// CHECK-DAG: StaticFieldGet
+ /// CHECK-NOT: NullCheck
+ /// CHECK-NOT: ArrayLength
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: StaticFieldSet
+ /// CHECK-DAG: Exit
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ private static int linearDynamicBCE1(int[] x, int lo, int hi) {
+ int result = 0;
+ for (int i = lo; i < hi; i++) {
+ sResult += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.linearDynamicBCE2(int[], int, int, int) BCE (before)
+ /// CHECK-DAG: StaticFieldGet
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: StaticFieldSet
+ /// CHECK-START: int Main.linearDynamicBCE2(int[], int, int, int) BCE (after)
+ /// CHECK-DAG: StaticFieldGet
+ /// CHECK-NOT: NullCheck
+ /// CHECK-NOT: ArrayLength
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: StaticFieldSet
+ /// CHECK-DAG: Exit
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ private static int linearDynamicBCE2(int[] x, int lo, int hi, int offset) {
+ int result = 0;
+ for (int i = lo; i < hi; i++) {
+ sResult += x[offset + i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.wrapAroundDynamicBCE(int[]) BCE (before)
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-START: int Main.wrapAroundDynamicBCE(int[]) BCE (after)
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-NOT: NullCheck
+ /// CHECK-NOT: ArrayLength
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ private static int wrapAroundDynamicBCE(int[] x) {
+ int w = 9;
+ int result = 0;
+ for (int i = 0; i < 10; i++) {
+ result += x[w];
+ w = i;
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.periodicDynamicBCE(int[]) BCE (before)
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-START: int Main.periodicDynamicBCE(int[]) BCE (after)
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-NOT: NullCheck
+ /// CHECK-NOT: ArrayLength
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ private static int periodicDynamicBCE(int[] x) {
+ int k = 0;
+ int result = 0;
+ for (int i = 0; i < 10; i++) {
+ result += x[k];
+ k = 1 - k;
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.dynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (before)
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-START: int Main.dynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after)
+ /// CHECK-NOT: NullCheck
+ /// CHECK-NOT: ArrayLength
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ static int dynamicBCEPossiblyInfiniteLoop(int[] x, int lo, int hi) {
+ // This loop could be infinite for hi = max int. Since i is also used
+ // as subscript, however, dynamic bce can proceed.
+ int result = 0;
+ for (int i = lo; i <= hi; i++) {
+ result += x[i];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.noDynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (before)
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-START: int Main.noDynamicBCEPossiblyInfiniteLoop(int[], int, int) BCE (after)
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ static int noDynamicBCEPossiblyInfiniteLoop(int[] x, int lo, int hi) {
+ // As above, but now the index is not used as subscript,
+ // and dynamic bce is not applied.
+ int result = 0;
+ for (int k = 0, i = lo; i <= hi; i++) {
+ result += x[k++];
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (before)
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: NotEqual
+ /// CHECK-DAG: If
+ /// CHECK-DAG: If
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: If
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-START: int Main.dynamicBCEAndConstantIndices(int[], int[][], int, int) BCE (after)
+ /// CHECK-DAG: NullCheck
+ /// CHECK-DAG: ArrayLength
+ /// CHECK-DAG: NotEqual
+ /// CHECK-DAG: If
+ /// CHECK-DAG: If
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: If
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: Exit
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-NOT: ArrayGet
+ static int dynamicBCEAndConstantIndices(int[] x, int[][] a, int lo, int hi) {
+ // Deliberately test array length on a before the loop so that only bounds checks
+ // on constant subscripts remain, making them a viable candidate for hoisting.
+ if (a.length == 0) {
+ return -1;
+ }
+ // Loop that allows BCE on x[i].
+ int result = 0;
+ for (int i = lo; i < hi; i++) {
+ result += x[i];
+ if ((i % 10) != 0) {
+ // None of the subscripts inside a conditional are removed by dynamic bce,
+ // making them a candidate for deoptimization based on constant indices.
+ // Compiler should ensure the array loads are not subsequently hoisted
+ // "above" the deoptimization "barrier" on the bounds.
+ a[0][i] = 1;
+ a[1][i] = 2;
+ a[99][i] = 3;
+ }
+ }
+ return result;
+ }
+
+ /// CHECK-START: int Main.dynamicBCEAndConstantIndicesAllTypes(int[], boolean[], byte[], char[], short[], int[], long[], float[], double[], java.lang.Integer[], int, int) BCE (before)
+ /// CHECK-DAG: If
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-START: int Main.dynamicBCEAndConstantIndicesAllTypes(int[], boolean[], byte[], char[], short[], int[], long[], float[], double[], java.lang.Integer[], int, int) BCE (after)
+ /// CHECK-DAG: If
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-NOT: BoundsCheck
+ /// CHECK-NOT: ArrayGet
+ /// CHECK-DAG: Exit
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: Deoptimize
+ /// CHECK-DAG: ArrayGet
+ static int dynamicBCEAndConstantIndicesAllTypes(int[] q,
+ boolean[] r,
+ byte[] s,
+ char[] t,
+ short[] u,
+ int[] v,
+ long[] w,
+ float[] x,
+ double[] y,
+ Integer[] z, int lo, int hi) {
+ int result = 0;
+ for (int i = lo; i < hi; i++) {
+ result += q[i] + (r[0] ? 1 : 0) + (int) s[0] + (int) t[0] + (int) u[0] + (int) v[0] +
+ (int) w[0] + (int) x[0] + (int) y[0] + (int) z[0];
+ }
+ return result;
+ }
+
//
// Verifier.
//
@@ -596,6 +968,9 @@
}
// Linear with non-unit strides.
+ expectEquals(55, linearByTwo(x));
+ expectEquals(25, linearByTwoSkip1(x));
+ expectEquals(25, linearByTwoSkip2(x));
expectEquals(56, linearWithCompoundStride());
expectEquals(66, linearWithLargePositiveStride());
expectEquals(66, linearWithVeryLargePositiveStride());
@@ -608,6 +983,7 @@
expectEquals(55, linearDoWhileUp());
expectEquals(55, linearDoWhileDown());
expectEquals(55, linearShort());
+ expectEquals(55, invariantFromPreLoop(x, 1));
// Periodic adds (1, 3), one at the time.
expectEquals(0, periodicIdiom(-1));
@@ -690,6 +1066,85 @@
sResult += 1000;
}
expectEquals(1055, sResult);
+
+ // Dynamic BCE.
+ sResult = 0;
+ try {
+ linearDynamicBCE1(x, -1, x.length);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult += 1000;
+ }
+ expectEquals(1000, sResult);
+ sResult = 0;
+ linearDynamicBCE1(x, 0, x.length);
+ expectEquals(55, sResult);
+ sResult = 0;
+ try {
+ linearDynamicBCE1(x, 0, x.length + 1);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult += 1000;
+ }
+ expectEquals(1055, sResult);
+
+ // Dynamic BCE with offset.
+ sResult = 0;
+ try {
+ linearDynamicBCE2(x, 0, x.length, -1);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult += 1000;
+ }
+ expectEquals(1000, sResult);
+ sResult = 0;
+ linearDynamicBCE2(x, 0, x.length, 0);
+ expectEquals(55, sResult);
+ sResult = 0;
+ try {
+ linearDynamicBCE2(x, 0, x.length, 1);
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult += 1000;
+ }
+ expectEquals(1054, sResult);
+
+ // Dynamic BCE candidates.
+ expectEquals(55, wrapAroundDynamicBCE(x));
+ expectEquals(15, periodicDynamicBCE(x));
+ expectEquals(55, dynamicBCEPossiblyInfiniteLoop(x, 0, 9));
+ expectEquals(55, noDynamicBCEPossiblyInfiniteLoop(x, 0, 9));
+
+ // Dynamic BCE combined with constant indices.
+ int[][] a;
+ a = new int[0][0];
+ expectEquals(-1, dynamicBCEAndConstantIndices(x, a, 0, 10));
+ a = new int[100][10];
+ expectEquals(55, dynamicBCEAndConstantIndices(x, a, 0, 10));
+ for (int i = 0; i < 10; i++) {
+ expectEquals((i % 10) != 0 ? 1 : 0, a[0][i]);
+ expectEquals((i % 10) != 0 ? 2 : 0, a[1][i]);
+ expectEquals((i % 10) != 0 ? 3 : 0, a[99][i]);
+ }
+ a = new int[2][10];
+ sResult = 0;
+ try {
+ expectEquals(55, dynamicBCEAndConstantIndices(x, a, 0, 10));
+ } catch (ArrayIndexOutOfBoundsException e) {
+ sResult = 1;
+ }
+ expectEquals(1, sResult);
+ expectEquals(a[0][1], 1);
+ expectEquals(a[1][1], 2);
+
+ // Dynamic BCE combined with constant indices of all types.
+ boolean[] x1 = { true };
+ byte[] x2 = { 2 };
+ char[] x3 = { 3 };
+ short[] x4 = { 4 };
+ int[] x5 = { 5 };
+ long[] x6 = { 6 };
+ float[] x7 = { 7 };
+ double[] x8 = { 8 };
+ Integer[] x9 = { 9 };
+ expectEquals(505,
+ dynamicBCEAndConstantIndicesAllTypes(x, x1, x2, x3, x4, x5, x6, x7, x8, x9, 0, 10));
}
private static void expectEquals(int expected, int result) {
