Revert "Dynamic BCE (based on induction range analysis)"
This reverts commit 0b5849be045c5683d4a6b6b6c306abadba5f0fcc.
Change-Id: Id33f5da42bbdfb1aff7e2281417c8a7aa492df05
Rationale: so close :-( but bullhead-userdebug (linux) build in git_mnc-dr-dev-plus-aosp reported a breakage with a type inconsistency (long vs int in probably the codegen of dynamic bce); no time to investigate and fix this fully before my trip, so rolling back for now
diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc
index a448302..cca0baf 100644
--- a/compiler/optimizing/bounds_check_elimination.cc
+++ b/compiler/optimizing/bounds_check_elimination.cc
@@ -20,7 +20,6 @@
#include "base/arena_containers.h"
#include "induction_var_range.h"
-#include "side_effects_analysis.h"
#include "nodes.h"
namespace art {
@@ -176,24 +175,6 @@
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) {
@@ -271,6 +252,157 @@
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:
@@ -368,13 +500,18 @@
: 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();
@@ -382,6 +519,23 @@
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) {
@@ -473,9 +627,467 @@
}
}
+ // 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_.
@@ -499,9 +1111,7 @@
return block->GetBlockId() >= initial_block_size_;
}
- BCEVisitor(HGraph* graph,
- const SideEffectsAnalysis& side_effects,
- HInductionVarAnalysis* induction_analysis)
+ BCEVisitor(HGraph* graph, HInductionVarAnalysis* induction_analysis)
: HGraphVisitor(graph),
maps_(graph->GetBlocks().size(),
ArenaSafeMap<int, ValueRange*>(
@@ -511,17 +1121,8 @@
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 {
@@ -537,17 +1138,6 @@
}
}
- 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) {
@@ -576,6 +1166,25 @@
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,
@@ -721,6 +1330,17 @@
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);
@@ -744,6 +1364,17 @@
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
@@ -769,34 +1400,38 @@
}
}
- void VisitBoundsCheck(HBoundsCheck* bounds_check) OVERRIDE {
+ void VisitBoundsCheck(HBoundsCheck* bounds_check) {
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());
- bool try_dynamic_bce = true;
+
+ 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();
+ }
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 dominator-based analysis.
+ // Try range obtained by local analysis.
ValueRange* index_range = LookupValueRange(index, block);
if (index_range != nullptr && index_range->FitsIn(&array_range)) {
- ReplaceInstruction(bounds_check, index);
+ ReplaceBoundsCheck(bounds_check, index);
return;
}
// Try range obtained by induction variable analysis.
- // Disables dynamic bce if OOB is certain.
- if (InductionRangeFitsIn(&array_range, bounds_check, index, &try_dynamic_bce)) {
- ReplaceInstruction(bounds_check, index);
+ index_range = LookupInductionRange(bounds_check, index);
+ if (index_range != nullptr && index_range->FitsIn(&array_range)) {
+ ReplaceBoundsCheck(bounds_check, index);
return;
}
} else {
- // Constant subscript.
int32_t constant = index->AsIntConstant()->GetValue();
if (constant < 0) {
// Will always throw exception.
@@ -804,7 +1439,7 @@
}
if (array_length->IsIntConstant()) {
if (constant < array_length->AsIntConstant()->GetValue()) {
- ReplaceInstruction(bounds_check, index);
+ ReplaceBoundsCheck(bounds_check, index);
}
return;
}
@@ -815,7 +1450,7 @@
ValueBound lower = existing_range->GetLower();
DCHECK(lower.IsConstant());
if (constant < lower.GetConstant()) {
- ReplaceInstruction(bounds_check, index);
+ ReplaceBoundsCheck(bounds_check, index);
return;
} else {
// Existing range isn't strong enough to eliminate the bounds check.
@@ -850,11 +1485,11 @@
ValueRange(GetGraph()->GetArena(), lower, upper);
GetValueRangeMap(block)->Overwrite(array_length->GetId(), range);
}
+ }
- // If static analysis fails, and OOB is not certain, try dynamic elimination.
- if (try_dynamic_bce) {
- TryDynamicBCE(bounds_check);
- }
+ void ReplaceBoundsCheck(HInstruction* bounds_check, HInstruction* index) {
+ bounds_check->ReplaceWith(index);
+ bounds_check->GetBlock()->RemoveInstruction(bounds_check);
}
static bool HasSameInputAtBackEdges(HPhi* phi) {
@@ -873,7 +1508,7 @@
return true;
}
- void VisitPhi(HPhi* phi) OVERRIDE {
+ void VisitPhi(HPhi* phi) {
if (phi->IsLoopHeaderPhi()
&& (phi->GetType() == Primitive::kPrimInt)
&& HasSameInputAtBackEdges(phi)) {
@@ -920,7 +1555,7 @@
}
}
- void VisitIf(HIf* instruction) OVERRIDE {
+ void VisitIf(HIf* instruction) {
if (instruction->InputAt(0)->IsCondition()) {
HCondition* cond = instruction->InputAt(0)->AsCondition();
IfCondition cmp = cond->GetCondition();
@@ -929,11 +1564,42 @@
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) OVERRIDE {
+ void VisitAdd(HAdd* add) {
HInstruction* right = add->GetRight();
if (right->IsIntConstant()) {
ValueRange* left_range = LookupValueRange(add->GetLeft(), add->GetBlock());
@@ -947,7 +1613,7 @@
}
}
- void VisitSub(HSub* sub) OVERRIDE {
+ void VisitSub(HSub* sub) {
HInstruction* left = sub->GetLeft();
HInstruction* right = sub->GetRight();
if (right->IsIntConstant()) {
@@ -1049,19 +1715,19 @@
}
}
- void VisitDiv(HDiv* div) OVERRIDE {
+ void VisitDiv(HDiv* div) {
FindAndHandlePartialArrayLength(div);
}
- void VisitShr(HShr* shr) OVERRIDE {
+ void VisitShr(HShr* shr) {
FindAndHandlePartialArrayLength(shr);
}
- void VisitUShr(HUShr* ushr) OVERRIDE {
+ void VisitUShr(HUShr* ushr) {
FindAndHandlePartialArrayLength(ushr);
}
- void VisitAnd(HAnd* instruction) OVERRIDE {
+ void VisitAnd(HAnd* instruction) {
if (instruction->GetRight()->IsIntConstant()) {
int32_t constant = instruction->GetRight()->AsIntConstant()->GetValue();
if (constant > 0) {
@@ -1076,7 +1742,7 @@
}
}
- void VisitNewArray(HNewArray* new_array) OVERRIDE {
+ void VisitNewArray(HNewArray* new_array) {
HInstruction* len = new_array->InputAt(0);
if (!len->IsIntConstant()) {
HInstruction *left;
@@ -1100,12 +1766,9 @@
}
}
- 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.
+ void VisitDeoptimize(HDeoptimize* deoptimize) {
+ // Right now it's only HLessThanOrEqual.
+ DCHECK(deoptimize->InputAt(0)->IsLessThanOrEqual());
HLessThanOrEqual* less_than_or_equal = deoptimize->InputAt(0)->AsLessThanOrEqual();
HInstruction* instruction = less_than_or_equal->InputAt(0);
if (instruction->IsArrayLength()) {
@@ -1119,35 +1782,6 @@
}
}
- /**
- * 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) {
@@ -1169,9 +1803,6 @@
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) {
@@ -1215,425 +1846,21 @@
}
}
- /**
- * 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_;
@@ -1645,12 +1872,14 @@
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.
- BCEVisitor visitor(graph_, side_effects_, induction_analysis_);
+ //
+ // TODO: only visit blocks that dominate some array accesses.
HBasicBlock* last_visited_block = nullptr;
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* current = it.Current();
@@ -1667,9 +1896,6 @@
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 b9df686..cdff3ca 100644
--- a/compiler/optimizing/bounds_check_elimination.h
+++ b/compiler/optimizing/bounds_check_elimination.h
@@ -21,16 +21,12 @@
namespace art {
-class SideEffectsAnalysis;
class HInductionVarAnalysis;
class BoundsCheckElimination : public HOptimization {
public:
- BoundsCheckElimination(HGraph* graph,
- const SideEffectsAnalysis& side_effects,
- HInductionVarAnalysis* induction_analysis)
+ BoundsCheckElimination(HGraph* graph, HInductionVarAnalysis* induction_analysis)
: HOptimization(graph, kBoundsCheckEliminiationPassName),
- side_effects_(side_effects),
induction_analysis_(induction_analysis) {}
void Run() OVERRIDE;
@@ -38,7 +34,6 @@
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 dbeb1cc..c9afdf2 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_, side_effects, &induction).Run();
+ BoundsCheckElimination(graph_, &induction).Run();
}
ArenaPool pool_;
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index b3b09d2..5814d75 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -735,29 +735,26 @@
}
}
- // 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.",
+ // 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.",
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.",
- phi->GetId(),
- other_phi->GetId(),
- phi->GetRegNumber()));
- }
+ other_phi->GetId(),
+ phi->GetRegNumber()));
}
}
}
diff --git a/compiler/optimizing/induction_var_range.cc b/compiler/optimizing/induction_var_range.cc
index 433c8f8..b40ef5a 100644
--- a/compiler/optimizing/induction_var_range.cc
+++ b/compiler/optimizing/induction_var_range.cc
@@ -425,13 +425,9 @@
}
HInductionVarAnalysis::InductionInfo* trip =
induction_analysis_->LookupInfo(loop, header->GetLastInstruction());
- // 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).
+ // Determine what tests are needed.
*needs_finite_test = NeedsTripCount(info) && IsUnsafeTripCount(trip);
- *needs_taken_test = IsBodyTripCount(trip);
+ *needs_taken_test = NeedsTripCount(info) && 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) {
@@ -549,42 +545,29 @@
}
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);
+ // 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);
}
- *result = Insert(block, oper);
+ return true;
}
- 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 b76bce4..0a39ff3 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1890,7 +1890,7 @@
* |
* if_block
* / \
- * true_block false_block
+ * dummy_block deopt_block
* \ /
* new_pre_header
* |
@@ -1898,73 +1898,62 @@
*/
void HGraph::TransformLoopHeaderForBCE(HBasicBlock* header) {
DCHECK(header->IsLoopHeader());
- HBasicBlock* old_pre_header = header->GetDominator();
+ HBasicBlock* pre_header = header->GetDominator();
- // Need extra block to avoid critical edge.
+ // Need this to avoid critical edge.
HBasicBlock* if_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());
+ // 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* new_pre_header = new (arena_) HBasicBlock(this, header->GetDexPc());
AddBlock(if_block);
- AddBlock(true_block);
- AddBlock(false_block);
+ AddBlock(dummy_block);
+ AddBlock(deopt_block);
AddBlock(new_pre_header);
- header->ReplacePredecessor(old_pre_header, new_pre_header);
- old_pre_header->successors_.clear();
- old_pre_header->dominated_blocks_.clear();
+ header->ReplacePredecessor(pre_header, new_pre_header);
+ pre_header->successors_.clear();
+ pre_header->dominated_blocks_.clear();
- 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->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->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);
+ 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);
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++] = true_block;
- reverse_post_order_[index_of_header++] = false_block;
+ reverse_post_order_[index_of_header++] = dummy_block;
+ reverse_post_order_[index_of_header++] = deopt_block;
reverse_post_order_[index_of_header++] = new_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);
+ 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);
!loop_it.Done();
loop_it.Advance()) {
loop_it.Current()->Add(if_block);
- loop_it.Current()->Add(true_block);
- loop_it.Current()->Add(false_block);
+ loop_it.Current()->Add(dummy_block);
+ loop_it.Current()->Add(deopt_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 5194681..2204921 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -491,13 +491,12 @@
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, *side_effects, induction);
+ BoundsCheckElimination* bce = new (arena) BoundsCheckElimination(graph, induction);
ReferenceTypePropagation* type_propagation =
new (arena) ReferenceTypePropagation(graph, &handles);
HSharpening* sharpening = new (arena) HSharpening(graph, codegen, dex_compilation_unit, driver);
@@ -550,7 +549,6 @@
licm,
induction,
bce,
- fold3, // evaluates code generated by dynamic bce
simplify3,
lse,
dce2,