diff options
Diffstat (limited to 'compiler/optimizing')
37 files changed, 1579 insertions, 464 deletions
diff --git a/compiler/optimizing/boolean_simplifier.cc b/compiler/optimizing/boolean_simplifier.cc index 6ebfb45074..8100a29f32 100644 --- a/compiler/optimizing/boolean_simplifier.cc +++ b/compiler/optimizing/boolean_simplifier.cc @@ -18,6 +18,26 @@ namespace art { +void HBooleanSimplifier::TryRemovingNegatedCondition(HBasicBlock* block) { + DCHECK(block->EndsWithIf()); + + // Check if the condition is a Boolean negation. + HIf* if_instruction = block->GetLastInstruction()->AsIf(); + HInstruction* boolean_not = if_instruction->InputAt(0); + if (!boolean_not->IsBooleanNot()) { + return; + } + + // Make BooleanNot's input the condition of the If and swap branches. + if_instruction->ReplaceInput(boolean_not->InputAt(0), 0); + block->SwapSuccessors(); + + // Remove the BooleanNot if it is now unused. + if (!boolean_not->HasUses()) { + boolean_not->GetBlock()->RemoveInstruction(boolean_not); + } +} + // Returns true if 'block1' and 'block2' are empty, merge into the same single // successor and the successor can only be reached from them. static bool BlocksDoMergeTogether(HBasicBlock* block1, HBasicBlock* block2) { @@ -78,55 +98,69 @@ static HInstruction* GetOppositeCondition(HInstruction* cond) { } } +void HBooleanSimplifier::TryRemovingBooleanSelection(HBasicBlock* block) { + DCHECK(block->EndsWithIf()); + + // Find elements of the pattern. + HIf* if_instruction = block->GetLastInstruction()->AsIf(); + HBasicBlock* true_block = if_instruction->IfTrueSuccessor(); + HBasicBlock* false_block = if_instruction->IfFalseSuccessor(); + if (!BlocksDoMergeTogether(true_block, false_block)) { + return; + } + HBasicBlock* merge_block = true_block->GetSuccessors().Get(0); + if (!merge_block->HasSinglePhi()) { + return; + } + HPhi* phi = merge_block->GetFirstPhi()->AsPhi(); + HInstruction* true_value = phi->InputAt(merge_block->GetPredecessorIndexOf(true_block)); + HInstruction* false_value = phi->InputAt(merge_block->GetPredecessorIndexOf(false_block)); + + // Check if the selection negates/preserves the value of the condition and + // if so, generate a suitable replacement instruction. + HInstruction* if_condition = if_instruction->InputAt(0); + HInstruction* replacement; + if (NegatesCondition(true_value, false_value)) { + replacement = GetOppositeCondition(if_condition); + if (replacement->GetBlock() == nullptr) { + block->InsertInstructionBefore(replacement, if_instruction); + } + } else if (PreservesCondition(true_value, false_value)) { + replacement = if_condition; + } else { + return; + } + + // Replace the selection outcome with the new instruction. + phi->ReplaceWith(replacement); + merge_block->RemovePhi(phi); + + // Delete the true branch and merge the resulting chain of blocks + // 'block->false_block->merge_block' into one. + true_block->DisconnectAndDelete(); + block->MergeWith(false_block); + block->MergeWith(merge_block); + + // Remove the original condition if it is now unused. + if (!if_condition->HasUses()) { + if_condition->GetBlock()->RemoveInstructionOrPhi(if_condition); + } +} + void HBooleanSimplifier::Run() { // Iterate in post order in the unlikely case that removing one occurrence of - // the pattern empties a branch block of another occurrence. Otherwise the - // order does not matter. + // the selection pattern empties a branch block of another occurrence. + // Otherwise the order does not matter. for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { HBasicBlock* block = it.Current(); if (!block->EndsWithIf()) continue; - // Find elements of the pattern. - HIf* if_instruction = block->GetLastInstruction()->AsIf(); - HBasicBlock* true_block = if_instruction->IfTrueSuccessor(); - HBasicBlock* false_block = if_instruction->IfFalseSuccessor(); - if (!BlocksDoMergeTogether(true_block, false_block)) { - continue; - } - HBasicBlock* merge_block = true_block->GetSuccessors().Get(0); - if (!merge_block->HasSinglePhi()) { - continue; - } - HPhi* phi = merge_block->GetFirstPhi()->AsPhi(); - HInstruction* true_value = phi->InputAt(merge_block->GetPredecessorIndexOf(true_block)); - HInstruction* false_value = phi->InputAt(merge_block->GetPredecessorIndexOf(false_block)); - - // Check if the selection negates/preserves the value of the condition and - // if so, generate a suitable replacement instruction. - HInstruction* if_condition = if_instruction->InputAt(0); - HInstruction* replacement; - if (NegatesCondition(true_value, false_value)) { - replacement = GetOppositeCondition(if_condition); - if (replacement->GetBlock() == nullptr) { - block->InsertInstructionBefore(replacement, if_instruction); - } - } else if (PreservesCondition(true_value, false_value)) { - replacement = if_condition; - } else { - continue; - } + // If condition is negated, remove the negation and swap the branches. + TryRemovingNegatedCondition(block); - // Replace the selection outcome with the new instruction. - phi->ReplaceWith(replacement); - merge_block->RemovePhi(phi); - - // Link the start/end blocks and remove empty branches. - graph_->MergeEmptyBranches(block, merge_block); - - // Remove the original condition if it is now unused. - if (!if_condition->HasUses()) { - if_condition->GetBlock()->RemoveInstruction(if_condition); - } + // If this is a boolean-selection diamond pattern, replace its result with + // the condition value (or its negation) and simplify the graph. + TryRemovingBooleanSelection(block); } } diff --git a/compiler/optimizing/boolean_simplifier.h b/compiler/optimizing/boolean_simplifier.h index a88733e1af..733ebaac2c 100644 --- a/compiler/optimizing/boolean_simplifier.h +++ b/compiler/optimizing/boolean_simplifier.h @@ -14,11 +14,15 @@ * limitations under the License. */ -// This optimization recognizes a common pattern where a boolean value is -// either cast to an integer or negated by selecting from zero/one integer -// constants with an If statement. Because boolean values are internally -// represented as zero/one, we can safely replace the pattern with a suitable -// condition instruction. +// This optimization recognizes two common patterns: +// (a) Boolean selection: Casting a boolean to an integer or negating it is +// carried out with an If statement selecting from zero/one integer +// constants. Because Boolean values are represented as zero/one, the +// pattern can be replaced with the condition instruction itself or its +// negation, depending on the layout. +// (b) Negated condition: Instruction simplifier may replace an If's condition +// with a boolean value. If this value is the result of a Boolean negation, +// the true/false branches can be swapped and negation removed. // Example: Negating a boolean value // B1: @@ -66,6 +70,9 @@ class HBooleanSimplifier : public HOptimization { static constexpr const char* kBooleanSimplifierPassName = "boolean_simplifier"; private: + void TryRemovingNegatedCondition(HBasicBlock* block); + void TryRemovingBooleanSelection(HBasicBlock* block); + DISALLOW_COPY_AND_ASSIGN(HBooleanSimplifier); }; diff --git a/compiler/optimizing/bounds_check_elimination.cc b/compiler/optimizing/bounds_check_elimination.cc index 6511120794..92fa6db507 100644 --- a/compiler/optimizing/bounds_check_elimination.cc +++ b/compiler/optimizing/bounds_check_elimination.cc @@ -246,6 +246,141 @@ class ValueBound : public ValueObject { 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_(INT_MAX), + offset_high_(INT_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; + } + const GrowableArray<HBasicBlock*> successors = block->GetSuccessors(); + for (size_t i = 0; i < successors.Size(); i++) { + if (!loop_info->Contains(*successors.Get(i))) { + // One of the successors exits the loop. + return true; + } + } + return false; + } + + void Run() { + HLoopInformation* loop_info = induction_variable_->GetBlock()->GetLoopInformation(); + // Must be simplified loop. + DCHECK_EQ(loop_info->GetBackEdges().Size(), 1U); + for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) { + HBasicBlock* block = it_loop.Current(); + DCHECK(block->IsInLoop()); + HBasicBlock* back_edge = loop_info->GetBackEdges().Get(0); + if (!block->Dominates(back_edge)) { + // 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. Otherwise, the loop induction variable is going to cover the full + // monotonic value range from initial_ to end_, and deoptimizations are added + // iff the loop will throw AIOOBE. + found_array_length_ = nullptr; + return; + } + for (HInstruction* instruction = block->GetFirstInstruction(); + instruction != nullptr; + instruction = instruction->GetNext()) { + if (!instruction->IsArrayGet() && !instruction->IsArraySet()) { + continue; + } + HInstruction* index = instruction->InputAt(1); + if (!index->IsBoundsCheck()) { + continue; + } + + HArrayLength* array_length = index->InputAt(1)->AsArrayLength(); + if (array_length == nullptr) { + DCHECK(index->InputAt(1)->IsIntConstant()); + // TODO: may optimize for constant case. + continue; + } + + 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; + } + + index = index->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. + 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: @@ -332,21 +467,31 @@ class ValueRange : public ArenaObject<kArenaAllocMisc> { class MonotonicValueRange : public ValueRange { public: MonotonicValueRange(ArenaAllocator* allocator, + HPhi* induction_variable, HInstruction* initial, int32_t increment, ValueBound bound) // To be conservative, give it full range [INT_MIN, INT_MAX] in case it's // used as a regular value range, due to possible overflow/underflow. : 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* GetLoopHead() const { + DCHECK(induction_variable_->GetBlock()->IsLoopHeader()); + return induction_variable_->GetBlock(); + } MonotonicValueRange* AsMonotonicValueRange() OVERRIDE { return this; } @@ -371,6 +516,10 @@ class MonotonicValueRange : public ValueRange { if (increment_ > 0) { // Monotonically increasing. ValueBound lower = ValueBound::NarrowLowerBound(bound_, range->GetLower()); + if (!lower.IsConstant() || lower.GetConstant() == INT_MIN) { + // Lower bound isn't useful. Leave it to deoptimization. + return this; + } // We currently conservatively assume max array length is INT_MAX. If we can // make assumptions about the max array length, e.g. due to the max heap size, @@ -417,6 +566,11 @@ class MonotonicValueRange : public ValueRange { DCHECK_NE(increment_, 0); // Monotonically decreasing. ValueBound upper = ValueBound::NarrowUpperBound(bound_, range->GetUpper()); + if ((!upper.IsConstant() || upper.GetConstant() == INT_MAX) && + !upper.IsRelatedToArrayLength()) { + // Upper bound isn't useful. Leave it to deoptimization. + return this; + } // Need to take care of underflow. Try to prove underflow won't happen // for common cases. @@ -432,10 +586,217 @@ class MonotonicValueRange : public ValueRange { } } + // 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; + // 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; + } + + // Adds a check that (value >= constant), and HDeoptimize otherwise. + void AddDeoptimizationConstant(HInstruction* value, + int32_t constant) { + HBasicBlock* block = induction_variable_->GetBlock(); + DCHECK(block->IsLoopHeader()); + HGraph* graph = block->GetGraph(); + HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); + HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck(); + 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()); + pre_header->InsertInstructionBefore(cond, pre_header->GetLastInstruction()); + pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction()); + deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( + suspend_check->GetEnvironment(), block); + } + + // 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; + 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* block = induction_variable_->GetBlock(); + DCHECK(block->IsLoopHeader()); + HGraph* graph = block->GetGraph(); + HBasicBlock* pre_header = block->GetLoopInformation()->GetPreHeader(); + HSuspendCheck* suspend_check = block->GetLoopInformation()->GetSuspendCheck(); + + // We may need to hoist null-check and array_length out of loop first. + if (!array_length->GetBlock()->Dominates(pre_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 array is defined before the loop when collecting + // array accesses for the loop. + DCHECK(array->GetBlock()->Dominates(pre_header)); + if (null_check != nullptr && !null_check->GetBlock()->Dominates(pre_header)) { + // 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()); + pre_header->InsertInstructionBefore(null_check_cond, pre_header->GetLastInstruction()); + pre_header->InsertInstructionBefore( + null_check_deoptimize, pre_header->GetLastInstruction()); + // Eliminate null check in the loop. + null_check->ReplaceWith(array); + null_check->GetBlock()->RemoveInstruction(null_check); + null_check_deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( + suspend_check->GetEnvironment(), block); + } + // Hoist array_length out of loop. + array_length->MoveBefore(pre_header->GetLastInstruction()); + } + + HIntConstant* offset_instr = graph->GetIntConstant(offset); + HAdd* add = new (graph->GetArena()) HAdd(Primitive::kPrimInt, array_length, offset_instr); + HCondition* cond = new (graph->GetArena()) HGreaterThan(value, add); + HDeoptimize* deoptimize = new (graph->GetArena()) + HDeoptimize(cond, suspend_check->GetDexPc()); + pre_header->InsertInstructionBefore(add, pre_header->GetLastInstruction()); + pre_header->InsertInstructionBefore(cond, pre_header->GetLastInstruction()); + pre_header->InsertInstructionBefore(deoptimize, pre_header->GetLastInstruction()); + deoptimize->CopyEnvironmentFromWithLoopPhiAdjustment( + suspend_check->GetEnvironment(), block); + } + + // Add 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; + } + + bool is_constant_proven, is_length_proven; + if (increment_ == 1) { + // Increasing from initial_ to end_. + int32_t offset = inclusive_ ? -offset_high - 1 : -offset_high; + if (CanAddDeoptimizationConstant(initial_, -offset_low, &is_constant_proven) && + CanAddDeoptimizationArrayLength(end_, array_length, offset, &is_length_proven)) { + if (!is_constant_proven) { + AddDeoptimizationConstant(initial_, -offset_low); + } + if (!is_length_proven) { + AddDeoptimizationArrayLength(end_, array_length, offset); + } + return true; + } + } else if (increment_ == -1) { + // Decreasing from initial_ to end_. + int32_t constant = inclusive_ ? -offset_low : -offset_low - 1; + if (CanAddDeoptimizationConstant(end_, constant, &is_constant_proven) && + CanAddDeoptimizationArrayLength( + initial_, array_length, -offset_high - 1, &is_length_proven)) { + if (!is_constant_proven) { + AddDeoptimizationConstant(end_, constant); + } + if (!is_length_proven) { + AddDeoptimizationArrayLength(initial_, array_length, -offset_high - 1); + } + return true; + } + } + return false; + } + + // Try to add HDeoptimize's in the loop pre-header first to narrow this range. + ValueRange* NarrowWithDeoptimization() { + if (increment_ != 1 && increment_ != -1) { + // TODO: possibly handle overflow/underflow issues with deoptimization. + return this; + } + + if (end_ == nullptr) { + // No full info to add deoptimization. + 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); + } + private: - HInstruction* const initial_; - const int32_t increment_; - ValueBound bound_; // Additional value bound info for initial_; + 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_. DISALLOW_COPY_AND_ASSIGN(MonotonicValueRange); }; @@ -598,6 +959,20 @@ class BCEVisitor : public HGraphVisitor { // There should be no critical edge at this point. DCHECK_EQ(false_successor->GetPredecessors().Size(), 1u); + ValueRange* left_range = LookupValueRange(left, block); + MonotonicValueRange* left_monotonic_range = nullptr; + if (left_range != nullptr) { + left_monotonic_range = left_range->AsMonotonicValueRange(); + if (left_monotonic_range != nullptr) { + HBasicBlock* loop_head = left_monotonic_range->GetLoopHead(); + if (instruction->GetBlock() != loop_head) { + // For monotonic value range, don't handle `instruction` + // if it's not defined in the loop header. + return; + } + } + } + bool found; ValueBound bound = ValueBound::DetectValueBoundFromValue(right, &found); // Each comparison can establish a lower bound and an upper bound @@ -610,7 +985,6 @@ class BCEVisitor : public HGraphVisitor { ValueRange* right_range = LookupValueRange(right, block); if (right_range != nullptr) { if (right_range->IsMonotonicValueRange()) { - ValueRange* left_range = LookupValueRange(left, block); if (left_range != nullptr && left_range->IsMonotonicValueRange()) { HandleIfBetweenTwoMonotonicValueRanges(instruction, left, right, cond, left_range->AsMonotonicValueRange(), @@ -628,6 +1002,17 @@ class BCEVisitor : public HGraphVisitor { 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->GetLoopHead() && + 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); @@ -651,6 +1036,17 @@ class BCEVisitor : public HGraphVisitor { 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->GetLoopHead() && + 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 @@ -790,6 +1186,7 @@ class BCEVisitor : public HGraphVisitor { } range = new (GetGraph()->GetArena()) MonotonicValueRange( GetGraph()->GetArena(), + phi, initial_value, increment, bound); @@ -809,6 +1206,36 @@ class BCEVisitor : public HGraphVisitor { 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()->GetLoopHead()) { + // The comparison is for an induction variable in the loop header. + DCHECK(left == left_range->AsMonotonicValueRange()->GetInductionVariable()); + HBasicBlock* loop_body_successor; + if (LIKELY(block->GetLoopInformation()-> + Contains(*instruction->IfFalseSuccessor()))) { + loop_body_successor = instruction->IfFalseSuccessor(); + } else { + loop_body_successor = instruction->IfTrueSuccessor(); + } + ValueRange* new_left_range = LookupValueRange(left, loop_body_successor); + if (new_left_range == left_range) { + // 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(instruction->IfFalseSuccessor())-> + Overwrite(left->GetId(), new_left_range); + } + } + } } } } @@ -1064,7 +1491,7 @@ class BCEVisitor : public HGraphVisitor { }; void BoundsCheckElimination::Run() { - if (!graph_->HasArrayAccesses()) { + if (!graph_->HasBoundsChecks()) { return; } diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc index 75cf1cf063..97be778dbd 100644 --- a/compiler/optimizing/bounds_check_elimination_test.cc +++ b/compiler/optimizing/bounds_check_elimination_test.cc @@ -43,7 +43,7 @@ TEST(BoundsCheckEliminationTest, NarrowingRangeArrayBoundsElimination) { ArenaAllocator allocator(&pool); HGraph* graph = new (&allocator) HGraph(&allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (&allocator) HBasicBlock(graph); graph->AddBlock(entry); @@ -148,7 +148,7 @@ TEST(BoundsCheckEliminationTest, OverflowArrayBoundsElimination) { ArenaAllocator allocator(&pool); HGraph* graph = new (&allocator) HGraph(&allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (&allocator) HBasicBlock(graph); graph->AddBlock(entry); @@ -220,7 +220,7 @@ TEST(BoundsCheckEliminationTest, UnderflowArrayBoundsElimination) { ArenaAllocator allocator(&pool); HGraph* graph = new (&allocator) HGraph(&allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (&allocator) HBasicBlock(graph); graph->AddBlock(entry); @@ -292,7 +292,7 @@ TEST(BoundsCheckEliminationTest, ConstantArrayBoundsElimination) { ArenaAllocator allocator(&pool); HGraph* graph = new (&allocator) HGraph(&allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (&allocator) HBasicBlock(graph); graph->AddBlock(entry); @@ -365,7 +365,7 @@ static HGraph* BuildSSAGraph1(ArenaAllocator* allocator, int increment, IfCondition cond = kCondGE) { HGraph* graph = new (allocator) HGraph(allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (allocator) HBasicBlock(graph); graph->AddBlock(entry); @@ -502,7 +502,7 @@ static HGraph* BuildSSAGraph2(ArenaAllocator* allocator, int increment = -1, IfCondition cond = kCondLE) { HGraph* graph = new (allocator) HGraph(allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (allocator) HBasicBlock(graph); graph->AddBlock(entry); @@ -633,7 +633,7 @@ static HGraph* BuildSSAGraph3(ArenaAllocator* allocator, int increment, IfCondition cond) { HGraph* graph = new (allocator) HGraph(allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (allocator) HBasicBlock(graph); graph->AddBlock(entry); @@ -744,7 +744,7 @@ static HGraph* BuildSSAGraph4(ArenaAllocator* allocator, int initial, IfCondition cond = kCondGE) { HGraph* graph = new (allocator) HGraph(allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (allocator) HBasicBlock(graph); graph->AddBlock(entry); @@ -869,7 +869,7 @@ TEST(BoundsCheckEliminationTest, BubbleSortArrayBoundsElimination) { ArenaAllocator allocator(&pool); HGraph* graph = new (&allocator) HGraph(&allocator); - graph->SetHasArrayAccesses(true); + graph->SetHasBoundsChecks(true); HBasicBlock* entry = new (&allocator) HBasicBlock(graph); graph->AddBlock(entry); diff --git a/compiler/optimizing/builder.cc b/compiler/optimizing/builder.cc index 818d671b5b..96e08fd24c 100644 --- a/compiler/optimizing/builder.cc +++ b/compiler/optimizing/builder.cc @@ -21,6 +21,7 @@ #include "class_linker.h" #include "dex_file-inl.h" #include "dex_instruction-inl.h" +#include "dex/verified_method.h" #include "driver/compiler_driver-inl.h" #include "driver/compiler_options.h" #include "mirror/class_loader.h" @@ -587,7 +588,7 @@ bool HGraphBuilder::BuildInvoke(const Instruction& instruction, const char* descriptor = dex_file_->StringDataByIdx(proto_id.shorty_idx_); Primitive::Type return_type = Primitive::GetType(descriptor[0]); bool is_instance_call = invoke_type != kStatic; - const size_t number_of_arguments = strlen(descriptor) - (is_instance_call ? 0 : 1); + size_t number_of_arguments = strlen(descriptor) - (is_instance_call ? 0 : 1); MethodReference target_method(dex_file_, method_idx); uintptr_t direct_code; @@ -605,7 +606,15 @@ bool HGraphBuilder::BuildInvoke(const Instruction& instruction, } DCHECK(optimized_invoke_type != kSuper); + // By default, consider that the called method implicitly requires + // an initialization check of its declaring method. + HInvokeStaticOrDirect::ClinitCheckRequirement clinit_check_requirement = + HInvokeStaticOrDirect::ClinitCheckRequirement::kImplicit; + // Potential class initialization check, in the case of a static method call. + HClinitCheck* clinit_check = nullptr; + HInvoke* invoke = nullptr; + if (optimized_invoke_type == kVirtual) { invoke = new (arena_) HInvokeVirtual( arena_, number_of_arguments, return_type, dex_pc, method_idx, table_index); @@ -620,9 +629,76 @@ bool HGraphBuilder::BuildInvoke(const Instruction& instruction, bool is_recursive = (target_method.dex_method_index == dex_compilation_unit_->GetDexMethodIndex()); DCHECK(!is_recursive || (target_method.dex_file == dex_compilation_unit_->GetDexFile())); + + if (optimized_invoke_type == kStatic) { + ScopedObjectAccess soa(Thread::Current()); + StackHandleScope<4> hs(soa.Self()); + Handle<mirror::DexCache> dex_cache(hs.NewHandle( + dex_compilation_unit_->GetClassLinker()->FindDexCache( + *dex_compilation_unit_->GetDexFile()))); + Handle<mirror::ClassLoader> class_loader(hs.NewHandle( + soa.Decode<mirror::ClassLoader*>(dex_compilation_unit_->GetClassLoader()))); + mirror::ArtMethod* resolved_method = compiler_driver_->ResolveMethod( + soa, dex_cache, class_loader, dex_compilation_unit_, method_idx, + optimized_invoke_type); + + if (resolved_method == nullptr) { + MaybeRecordStat(MethodCompilationStat::kNotCompiledUnresolvedMethod); + return false; + } + + const DexFile& outer_dex_file = *outer_compilation_unit_->GetDexFile(); + Handle<mirror::DexCache> outer_dex_cache(hs.NewHandle( + outer_compilation_unit_->GetClassLinker()->FindDexCache(outer_dex_file))); + Handle<mirror::Class> referrer_class(hs.NewHandle(GetOutermostCompilingClass())); + + // The index at which the method's class is stored in the DexCache's type array. + uint32_t storage_index = DexFile::kDexNoIndex; + bool is_referrer_class = (resolved_method->GetDeclaringClass() == referrer_class.Get()); + if (is_referrer_class) { + storage_index = referrer_class->GetDexTypeIndex(); + } else if (outer_dex_cache.Get() == dex_cache.Get()) { + // Get `storage_index` from IsClassOfStaticMethodAvailableToReferrer. + compiler_driver_->IsClassOfStaticMethodAvailableToReferrer(outer_dex_cache.Get(), + referrer_class.Get(), + resolved_method, + method_idx, + &storage_index); + } + + if (referrer_class.Get()->IsSubClass(resolved_method->GetDeclaringClass())) { + // If the referrer class is the declaring class or a subclass + // of the declaring class, no class initialization is needed + // before the static method call. + clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kNone; + } else if (storage_index != DexFile::kDexNoIndex) { + // If the method's class type index is available, check + // whether we should add an explicit class initialization + // check for its declaring class before the static method call. + + // TODO: find out why this check is needed. + bool is_in_dex_cache = compiler_driver_->CanAssumeTypeIsPresentInDexCache( + *outer_compilation_unit_->GetDexFile(), storage_index); + bool is_initialized = + resolved_method->GetDeclaringClass()->IsInitialized() && is_in_dex_cache; + + if (is_initialized) { + clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kNone; + } else { + clinit_check_requirement = HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit; + HLoadClass* load_class = + new (arena_) HLoadClass(storage_index, is_referrer_class, dex_pc); + current_block_->AddInstruction(load_class); + clinit_check = new (arena_) HClinitCheck(load_class, dex_pc); + current_block_->AddInstruction(clinit_check); + ++number_of_arguments; + } + } + } + invoke = new (arena_) HInvokeStaticOrDirect( arena_, number_of_arguments, return_type, dex_pc, target_method.dex_method_index, - is_recursive, invoke_type, optimized_invoke_type); + is_recursive, invoke_type, optimized_invoke_type, clinit_check_requirement); } size_t start_index = 0; @@ -655,6 +731,12 @@ bool HGraphBuilder::BuildInvoke(const Instruction& instruction, } } + if (clinit_check_requirement == HInvokeStaticOrDirect::ClinitCheckRequirement::kExplicit) { + // Add the class initialization check as last input of `invoke`. + DCHECK(clinit_check != nullptr); + invoke->SetArgumentAt(argument_index++, clinit_check); + } + DCHECK_EQ(argument_index, number_of_arguments); current_block_->AddInstruction(invoke); latest_result_ = invoke; @@ -732,7 +814,6 @@ bool HGraphBuilder::IsOutermostCompilingClass(uint16_t type_index) const { return compiling_class.Get() == cls.Get(); } - bool HGraphBuilder::BuildStaticFieldAccess(const Instruction& instruction, uint32_t dex_pc, bool is_put) { @@ -764,7 +845,7 @@ bool HGraphBuilder::BuildStaticFieldAccess(const Instruction& instruction, if (is_referrer_class) { storage_index = referrer_class->GetDexTypeIndex(); } else if (outer_dex_cache.Get() != dex_cache.Get()) { - // The compiler driver cannot currently understand multple dex caches involved. Just bailout. + // The compiler driver cannot currently understand multiple dex caches involved. Just bailout. return false; } else { std::pair<bool, bool> pair = compiler_driver_->IsFastStaticField( @@ -882,7 +963,7 @@ void HGraphBuilder::BuildArrayAccess(const Instruction& instruction, current_block_->AddInstruction(new (arena_) HArrayGet(object, index, anticipated_type)); UpdateLocal(source_or_dest_reg, current_block_->GetLastInstruction()); } - graph_->SetHasArrayAccesses(true); + graph_->SetHasBoundsChecks(true); } void HGraphBuilder::BuildFilledNewArray(uint32_t dex_pc, @@ -984,6 +1065,7 @@ void HGraphBuilder::BuildFillArrayData(const Instruction& instruction, uint32_t default: LOG(FATAL) << "Unknown element width for " << payload->element_width; } + graph_->SetHasBoundsChecks(true); } void HGraphBuilder::BuildFillWideArrayData(HInstruction* object, diff --git a/compiler/optimizing/code_generator.cc b/compiler/optimizing/code_generator.cc index b14b69ba39..5163395cac 100644 --- a/compiler/optimizing/code_generator.cc +++ b/compiler/optimizing/code_generator.cc @@ -612,7 +612,7 @@ void CodeGenerator::BuildVMapTable(std::vector<uint8_t>* data) const { } void CodeGenerator::BuildStackMaps(std::vector<uint8_t>* data) { - uint32_t size = stack_map_stream_.ComputeNeededSize(); + uint32_t size = stack_map_stream_.PrepareForFillIn(); data->resize(size); MemoryRegion region(data->data(), size); stack_map_stream_.FillIn(region); @@ -654,7 +654,8 @@ void CodeGenerator::RecordPcInfo(HInstruction* instruction, if (instruction == nullptr) { // For stack overflow checks. - stack_map_stream_.AddStackMapEntry(dex_pc, pc_info.native_pc, 0, 0, 0, inlining_depth); + stack_map_stream_.BeginStackMapEntry(dex_pc, pc_info.native_pc, 0, 0, 0, inlining_depth); + stack_map_stream_.EndStackMapEntry(); return; } LocationSummary* locations = instruction->GetLocations(); @@ -672,12 +673,12 @@ void CodeGenerator::RecordPcInfo(HInstruction* instruction, } // The register mask must be a subset of callee-save registers. DCHECK_EQ(register_mask & core_callee_save_mask_, register_mask); - stack_map_stream_.AddStackMapEntry(dex_pc, - pc_info.native_pc, - register_mask, - locations->GetStackMask(), - environment_size, - inlining_depth); + stack_map_stream_.BeginStackMapEntry(dex_pc, + pc_info.native_pc, + register_mask, + locations->GetStackMask(), + environment_size, + inlining_depth); // Walk over the environment, and record the location of dex registers. for (size_t i = 0; i < environment_size; ++i) { @@ -823,6 +824,7 @@ void CodeGenerator::RecordPcInfo(HInstruction* instruction, LOG(FATAL) << "Unexpected kind " << location.GetKind(); } } + stack_map_stream_.EndStackMapEntry(); } bool CodeGenerator::CanMoveNullCheckToUser(HNullCheck* null_check) { diff --git a/compiler/optimizing/code_generator_arm.cc b/compiler/optimizing/code_generator_arm.cc index ae1fb537bb..01748a9f5c 100644 --- a/compiler/optimizing/code_generator_arm.cc +++ b/compiler/optimizing/code_generator_arm.cc @@ -176,7 +176,6 @@ class LoadClassSlowPathARM : public SlowPathCodeARM { InvokeRuntimeCallingConvention calling_convention; __ LoadImmediate(calling_convention.GetRegisterAt(0), cls_->GetTypeIndex()); - arm_codegen->LoadCurrentMethod(calling_convention.GetRegisterAt(1)); int32_t entry_point_offset = do_clinit_ ? QUICK_ENTRY_POINT(pInitializeStaticStorage) : QUICK_ENTRY_POINT(pInitializeType); @@ -222,7 +221,6 @@ class LoadStringSlowPathARM : public SlowPathCodeARM { SaveLiveRegisters(codegen, locations); InvokeRuntimeCallingConvention calling_convention; - arm_codegen->LoadCurrentMethod(calling_convention.GetRegisterAt(1)); __ LoadImmediate(calling_convention.GetRegisterAt(0), instruction_->GetStringIndex()); arm_codegen->InvokeRuntime( QUICK_ENTRY_POINT(pResolveString), instruction_, instruction_->GetDexPc(), this); @@ -1243,6 +1241,14 @@ void InstructionCodeGeneratorARM::VisitReturn(HReturn* ret) { } void LocationsBuilderARM::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + // Explicit clinit checks triggered by static invokes must have been + // pruned by art::PrepareForRegisterAllocation, but this step is not + // run in baseline. So we remove them manually here if we find them. + // TODO: Instead of this local workaround, address this properly. + if (invoke->IsStaticWithExplicitClinitCheck()) { + invoke->RemoveClinitCheckOrLoadClassAsLastInput(); + } + IntrinsicLocationsBuilderARM intrinsic(GetGraph()->GetArena(), codegen_->GetInstructionSetFeatures()); if (intrinsic.TryDispatch(invoke)) { @@ -1267,6 +1273,10 @@ static bool TryGenerateIntrinsicCode(HInvoke* invoke, CodeGeneratorARM* codegen) } void InstructionCodeGeneratorARM::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + // Explicit clinit checks triggered by static invokes must have been + // pruned by art::PrepareForRegisterAllocation. + DCHECK(!invoke->IsStaticWithExplicitClinitCheck()); + if (TryGenerateIntrinsicCode(invoke, codegen_)) { return; } diff --git a/compiler/optimizing/code_generator_arm64.cc b/compiler/optimizing/code_generator_arm64.cc index 1c6debdded..dada4ce5bd 100644 --- a/compiler/optimizing/code_generator_arm64.cc +++ b/compiler/optimizing/code_generator_arm64.cc @@ -173,14 +173,13 @@ class LoadClassSlowPathARM64 : public SlowPathCodeARM64 { InvokeRuntimeCallingConvention calling_convention; __ Mov(calling_convention.GetRegisterAt(0).W(), cls_->GetTypeIndex()); - arm64_codegen->LoadCurrentMethod(calling_convention.GetRegisterAt(1).W()); int32_t entry_point_offset = do_clinit_ ? QUICK_ENTRY_POINT(pInitializeStaticStorage) : QUICK_ENTRY_POINT(pInitializeType); arm64_codegen->InvokeRuntime(entry_point_offset, at_, dex_pc_, this); if (do_clinit_) { - CheckEntrypointTypes<kQuickInitializeStaticStorage, void*, uint32_t, mirror::ArtMethod*>(); + CheckEntrypointTypes<kQuickInitializeStaticStorage, void*, uint32_t>(); } else { - CheckEntrypointTypes<kQuickInitializeType, void*, uint32_t, mirror::ArtMethod*>(); + CheckEntrypointTypes<kQuickInitializeType, void*, uint32_t>(); } // Move the class to the desired location. @@ -225,11 +224,10 @@ class LoadStringSlowPathARM64 : public SlowPathCodeARM64 { SaveLiveRegisters(codegen, locations); InvokeRuntimeCallingConvention calling_convention; - arm64_codegen->LoadCurrentMethod(calling_convention.GetRegisterAt(1).W()); __ Mov(calling_convention.GetRegisterAt(0).W(), instruction_->GetStringIndex()); arm64_codegen->InvokeRuntime( QUICK_ENTRY_POINT(pResolveString), instruction_, instruction_->GetDexPc(), this); - CheckEntrypointTypes<kQuickResolveString, void*, uint32_t, mirror::ArtMethod*>(); + CheckEntrypointTypes<kQuickResolveString, void*, uint32_t>(); Primitive::Type type = instruction_->GetType(); arm64_codegen->MoveLocation(locations->Out(), calling_convention.GetReturnLocation(type), type); @@ -1970,6 +1968,14 @@ void LocationsBuilderARM64::VisitInvokeVirtual(HInvokeVirtual* invoke) { } void LocationsBuilderARM64::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + // Explicit clinit checks triggered by static invokes must have been + // pruned by art::PrepareForRegisterAllocation, but this step is not + // run in baseline. So we remove them manually here if we find them. + // TODO: Instead of this local workaround, address this properly. + if (invoke->IsStaticWithExplicitClinitCheck()) { + invoke->RemoveClinitCheckOrLoadClassAsLastInput(); + } + IntrinsicLocationsBuilderARM64 intrinsic(GetGraph()->GetArena()); if (intrinsic.TryDispatch(invoke)) { return; @@ -2020,6 +2026,10 @@ void CodeGeneratorARM64::GenerateStaticOrDirectCall(HInvokeStaticOrDirect* invok } void InstructionCodeGeneratorARM64::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + // Explicit clinit checks triggered by static invokes must have been + // pruned by art::PrepareForRegisterAllocation. + DCHECK(!invoke->IsStaticWithExplicitClinitCheck()); + if (TryGenerateIntrinsicCode(invoke, codegen_)) { return; } diff --git a/compiler/optimizing/code_generator_x86.cc b/compiler/optimizing/code_generator_x86.cc index c604842d86..04999bedb0 100644 --- a/compiler/optimizing/code_generator_x86.cc +++ b/compiler/optimizing/code_generator_x86.cc @@ -174,7 +174,6 @@ class LoadStringSlowPathX86 : public SlowPathCodeX86 { SaveLiveRegisters(codegen, locations); InvokeRuntimeCallingConvention calling_convention; - x86_codegen->LoadCurrentMethod(calling_convention.GetRegisterAt(1)); __ movl(calling_convention.GetRegisterAt(0), Immediate(instruction_->GetStringIndex())); __ fs()->call(Address::Absolute(QUICK_ENTRYPOINT_OFFSET(kX86WordSize, pResolveString))); RecordPcInfo(codegen, instruction_, instruction_->GetDexPc()); @@ -208,7 +207,6 @@ class LoadClassSlowPathX86 : public SlowPathCodeX86 { InvokeRuntimeCallingConvention calling_convention; __ movl(calling_convention.GetRegisterAt(0), Immediate(cls_->GetTypeIndex())); - x86_codegen->LoadCurrentMethod(calling_convention.GetRegisterAt(1)); __ fs()->call(Address::Absolute(do_clinit_ ? QUICK_ENTRYPOINT_OFFSET(kX86WordSize, pInitializeStaticStorage) : QUICK_ENTRYPOINT_OFFSET(kX86WordSize, pInitializeType))); @@ -1196,6 +1194,14 @@ void InstructionCodeGeneratorX86::VisitReturn(HReturn* ret) { } void LocationsBuilderX86::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + // Explicit clinit checks triggered by static invokes must have been + // pruned by art::PrepareForRegisterAllocation, but this step is not + // run in baseline. So we remove them manually here if we find them. + // TODO: Instead of this local workaround, address this properly. + if (invoke->IsStaticWithExplicitClinitCheck()) { + invoke->RemoveClinitCheckOrLoadClassAsLastInput(); + } + IntrinsicLocationsBuilderX86 intrinsic(codegen_); if (intrinsic.TryDispatch(invoke)) { return; @@ -1214,6 +1220,10 @@ static bool TryGenerateIntrinsicCode(HInvoke* invoke, CodeGeneratorX86* codegen) } void InstructionCodeGeneratorX86::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + // Explicit clinit checks triggered by static invokes must have been + // pruned by art::PrepareForRegisterAllocation. + DCHECK(!invoke->IsStaticWithExplicitClinitCheck()); + if (TryGenerateIntrinsicCode(invoke, codegen_)) { return; } @@ -3809,7 +3819,7 @@ void LocationsBuilderX86::VisitBoundsCheck(HBoundsCheck* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); locations->SetInAt(0, Location::RegisterOrConstant(instruction->InputAt(0))); - locations->SetInAt(1, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1))); if (instruction->HasUses()) { locations->SetOut(Location::SameAsFirstInput()); } @@ -3821,16 +3831,38 @@ void InstructionCodeGeneratorX86::VisitBoundsCheck(HBoundsCheck* instruction) { Location length_loc = locations->InAt(1); SlowPathCodeX86* slow_path = new (GetGraph()->GetArena()) BoundsCheckSlowPathX86(instruction, index_loc, length_loc); - codegen_->AddSlowPath(slow_path); - Register length = length_loc.AsRegister<Register>(); - if (index_loc.IsConstant()) { - int32_t value = CodeGenerator::GetInt32ValueOf(index_loc.GetConstant()); - __ cmpl(length, Immediate(value)); + if (length_loc.IsConstant()) { + int32_t length = CodeGenerator::GetInt32ValueOf(length_loc.GetConstant()); + if (index_loc.IsConstant()) { + // BCE will remove the bounds check if we are guarenteed to pass. + int32_t index = CodeGenerator::GetInt32ValueOf(index_loc.GetConstant()); + if (index < 0 || index >= length) { + codegen_->AddSlowPath(slow_path); + __ jmp(slow_path->GetEntryLabel()); + } else { + // Some optimization after BCE may have generated this, and we should not + // generate a bounds check if it is a valid range. + } + return; + } + + // We have to reverse the jump condition because the length is the constant. + Register index_reg = index_loc.AsRegister<Register>(); + __ cmpl(index_reg, Immediate(length)); + codegen_->AddSlowPath(slow_path); + __ j(kAboveEqual, slow_path->GetEntryLabel()); } else { - __ cmpl(length, index_loc.AsRegister<Register>()); + Register length = length_loc.AsRegister<Register>(); + if (index_loc.IsConstant()) { + int32_t value = CodeGenerator::GetInt32ValueOf(index_loc.GetConstant()); + __ cmpl(length, Immediate(value)); + } else { + __ cmpl(length, index_loc.AsRegister<Register>()); + } + codegen_->AddSlowPath(slow_path); + __ j(kBelowEqual, slow_path->GetEntryLabel()); } - __ j(kBelowEqual, slow_path->GetEntryLabel()); } void LocationsBuilderX86::VisitTemporary(HTemporary* temp) { diff --git a/compiler/optimizing/code_generator_x86_64.cc b/compiler/optimizing/code_generator_x86_64.cc index 47425fb9ae..5ce932928b 100644 --- a/compiler/optimizing/code_generator_x86_64.cc +++ b/compiler/optimizing/code_generator_x86_64.cc @@ -197,7 +197,6 @@ class LoadClassSlowPathX86_64 : public SlowPathCodeX86_64 { InvokeRuntimeCallingConvention calling_convention; __ movl(CpuRegister(calling_convention.GetRegisterAt(0)), Immediate(cls_->GetTypeIndex())); - x64_codegen->LoadCurrentMethod(CpuRegister(calling_convention.GetRegisterAt(1))); __ gs()->call(Address::Absolute((do_clinit_ ? QUICK_ENTRYPOINT_OFFSET(kX86_64WordSize, pInitializeStaticStorage) : QUICK_ENTRYPOINT_OFFSET(kX86_64WordSize, pInitializeType)) , true)); @@ -244,7 +243,6 @@ class LoadStringSlowPathX86_64 : public SlowPathCodeX86_64 { SaveLiveRegisters(codegen, locations); InvokeRuntimeCallingConvention calling_convention; - x64_codegen->LoadCurrentMethod(CpuRegister(calling_convention.GetRegisterAt(1))); __ movl(CpuRegister(calling_convention.GetRegisterAt(0)), Immediate(instruction_->GetStringIndex())); __ gs()->call(Address::Absolute( @@ -1291,6 +1289,14 @@ Location InvokeDexCallingConventionVisitor::GetNextLocation(Primitive::Type type } void LocationsBuilderX86_64::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + // Explicit clinit checks triggered by static invokes must have been + // pruned by art::PrepareForRegisterAllocation, but this step is not + // run in baseline. So we remove them manually here if we find them. + // TODO: Instead of this local workaround, address this properly. + if (invoke->IsStaticWithExplicitClinitCheck()) { + invoke->RemoveClinitCheckOrLoadClassAsLastInput(); + } + IntrinsicLocationsBuilderX86_64 intrinsic(codegen_); if (intrinsic.TryDispatch(invoke)) { return; @@ -1309,6 +1315,10 @@ static bool TryGenerateIntrinsicCode(HInvoke* invoke, CodeGeneratorX86_64* codeg } void InstructionCodeGeneratorX86_64::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + // Explicit clinit checks triggered by static invokes must have been + // pruned by art::PrepareForRegisterAllocation. + DCHECK(!invoke->IsStaticWithExplicitClinitCheck()); + if (TryGenerateIntrinsicCode(invoke, codegen_)) { return; } @@ -3750,7 +3760,7 @@ void LocationsBuilderX86_64::VisitBoundsCheck(HBoundsCheck* instruction) { LocationSummary* locations = new (GetGraph()->GetArena()) LocationSummary(instruction, LocationSummary::kNoCall); locations->SetInAt(0, Location::RegisterOrConstant(instruction->InputAt(0))); - locations->SetInAt(1, Location::RequiresRegister()); + locations->SetInAt(1, Location::RegisterOrConstant(instruction->InputAt(1))); if (instruction->HasUses()) { locations->SetOut(Location::SameAsFirstInput()); } @@ -3762,16 +3772,38 @@ void InstructionCodeGeneratorX86_64::VisitBoundsCheck(HBoundsCheck* instruction) Location length_loc = locations->InAt(1); SlowPathCodeX86_64* slow_path = new (GetGraph()->GetArena()) BoundsCheckSlowPathX86_64(instruction, index_loc, length_loc); - codegen_->AddSlowPath(slow_path); - CpuRegister length = length_loc.AsRegister<CpuRegister>(); - if (index_loc.IsConstant()) { - int32_t value = CodeGenerator::GetInt32ValueOf(index_loc.GetConstant()); - __ cmpl(length, Immediate(value)); + if (length_loc.IsConstant()) { + int32_t length = CodeGenerator::GetInt32ValueOf(length_loc.GetConstant()); + if (index_loc.IsConstant()) { + // BCE will remove the bounds check if we are guarenteed to pass. + int32_t index = CodeGenerator::GetInt32ValueOf(index_loc.GetConstant()); + if (index < 0 || index >= length) { + codegen_->AddSlowPath(slow_path); + __ jmp(slow_path->GetEntryLabel()); + } else { + // Some optimization after BCE may have generated this, and we should not + // generate a bounds check if it is a valid range. + } + return; + } + + // We have to reverse the jump condition because the length is the constant. + CpuRegister index_reg = index_loc.AsRegister<CpuRegister>(); + __ cmpl(index_reg, Immediate(length)); + codegen_->AddSlowPath(slow_path); + __ j(kAboveEqual, slow_path->GetEntryLabel()); } else { - __ cmpl(length, index_loc.AsRegister<CpuRegister>()); + CpuRegister length = length_loc.AsRegister<CpuRegister>(); + if (index_loc.IsConstant()) { + int32_t value = CodeGenerator::GetInt32ValueOf(index_loc.GetConstant()); + __ cmpl(length, Immediate(value)); + } else { + __ cmpl(length, index_loc.AsRegister<CpuRegister>()); + } + codegen_->AddSlowPath(slow_path); + __ j(kBelowEqual, slow_path->GetEntryLabel()); } - __ j(kBelowEqual, slow_path->GetEntryLabel()); } void CodeGeneratorX86_64::MarkGCCard(CpuRegister temp, diff --git a/compiler/optimizing/constant_folding.h b/compiler/optimizing/constant_folding.h index ac00824e33..66ff57855e 100644 --- a/compiler/optimizing/constant_folding.h +++ b/compiler/optimizing/constant_folding.h @@ -32,8 +32,8 @@ namespace art { */ class HConstantFolding : public HOptimization { public: - explicit HConstantFolding(HGraph* graph) - : HOptimization(graph, true, kConstantFoldingPassName) {} + explicit HConstantFolding(HGraph* graph, const char* name = kConstantFoldingPassName) + : HOptimization(graph, true, name) {} void Run() OVERRIDE; diff --git a/compiler/optimizing/constant_folding_test.cc b/compiler/optimizing/constant_folding_test.cc index 02ad675dc3..422223f5e0 100644 --- a/compiler/optimizing/constant_folding_test.cc +++ b/compiler/optimizing/constant_folding_test.cc @@ -572,14 +572,19 @@ TEST(ConstantFolding, IntConstantFoldingAndJumps) { }; // Expected difference after dead code elimination. - diff_t expected_dce_diff = { - { " 3: IntConstant\n", removed }, - { " 13: IntConstant\n", removed }, - { " 18: IntConstant\n", removed }, - { " 24: IntConstant\n", removed }, - { " 34: IntConstant\n", removed }, - }; - std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff); + std::string expected_after_dce = + "BasicBlock 0, succ: 1\n" + " 5: IntConstant []\n" + " 30: SuspendCheck\n" + " 32: IntConstant []\n" + " 33: IntConstant []\n" + " 35: IntConstant [28]\n" + " 31: Goto 1\n" + "BasicBlock 1, pred: 0, succ: 5\n" + " 21: SuspendCheck\n" + " 28: Return(35)\n" + "BasicBlock 5, pred: 1\n" + " 29: Exit\n"; TestCode(data, expected_before, @@ -647,13 +652,15 @@ TEST(ConstantFolding, ConstantCondition) { ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1); }; - // Expected difference after dead code elimination. - diff_t expected_dce_diff = { - { " 3: IntConstant [9, 15, 22]\n", " 3: IntConstant [9, 22]\n" }, - { " 22: Phi(3, 5) [15]\n", " 22: Phi(3, 5)\n" }, - { " 15: Add(22, 3)\n", removed } - }; - std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff); + // Expected graph after dead code elimination. + std::string expected_after_dce = + "BasicBlock 0, succ: 1\n" + " 19: SuspendCheck\n" + " 20: Goto 1\n" + "BasicBlock 1, pred: 0, succ: 4\n" + " 17: ReturnVoid\n" + "BasicBlock 4, pred: 1\n" + " 18: Exit\n"; TestCode(data, expected_before, diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc index 8045cc5027..91cd60acce 100644 --- a/compiler/optimizing/dead_code_elimination.cc +++ b/compiler/optimizing/dead_code_elimination.cc @@ -20,10 +20,78 @@ namespace art { -void HDeadCodeElimination::Run() { +static void MarkReachableBlocks(HBasicBlock* block, ArenaBitVector* visited) { + int block_id = block->GetBlockId(); + if (visited->IsBitSet(block_id)) { + return; + } + visited->SetBit(block_id); + + HInstruction* last_instruction = block->GetLastInstruction(); + if (last_instruction->IsIf()) { + HIf* if_instruction = last_instruction->AsIf(); + HInstruction* condition = if_instruction->InputAt(0); + if (!condition->IsIntConstant()) { + MarkReachableBlocks(if_instruction->IfTrueSuccessor(), visited); + MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited); + } else if (condition->AsIntConstant()->IsOne()) { + MarkReachableBlocks(if_instruction->IfTrueSuccessor(), visited); + } else { + DCHECK(condition->AsIntConstant()->IsZero()); + MarkReachableBlocks(if_instruction->IfFalseSuccessor(), visited); + } + } else { + for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) { + MarkReachableBlocks(block->GetSuccessors().Get(i), visited); + } + } +} + +void HDeadCodeElimination::MaybeRecordDeadBlock(HBasicBlock* block) { + if (stats_ != nullptr) { + stats_->RecordStat(MethodCompilationStat::kRemovedDeadInstruction, + block->GetPhis().CountSize() + block->GetInstructions().CountSize()); + } +} + +void HDeadCodeElimination::RemoveDeadBlocks() { + // Classify blocks as reachable/unreachable. + ArenaAllocator* allocator = graph_->GetArena(); + ArenaBitVector live_blocks(allocator, graph_->GetBlocks().Size(), false); + MarkReachableBlocks(graph_->GetEntryBlock(), &live_blocks); + + // Remove all dead blocks. Process blocks in post-order, because removal needs + // the block's chain of dominators. + for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) { + HBasicBlock* block = it.Current(); + if (live_blocks.IsBitSet(block->GetBlockId())) { + continue; + } + MaybeRecordDeadBlock(block); + block->DisconnectAndDelete(); + } + + // Connect successive blocks created by dead branches. Order does not matter. + for (HReversePostOrderIterator it(*graph_); !it.Done();) { + HBasicBlock* block = it.Current(); + if (block->IsEntryBlock() || block->GetSuccessors().Size() != 1u) { + it.Advance(); + continue; + } + HBasicBlock* successor = block->GetSuccessors().Get(0); + if (successor->IsExitBlock() || successor->GetPredecessors().Size() != 1u) { + it.Advance(); + continue; + } + block->MergeWith(successor); + + // Reiterate on this block in case it can be merged with its new successor. + } +} + +void HDeadCodeElimination::RemoveDeadInstructions() { // Process basic blocks in post-order in the dominator tree, so that - // a dead instruction depending on another dead instruction is - // removed. + // a dead instruction depending on another dead instruction is removed. for (HPostOrderIterator b(*graph_); !b.Done(); b.Advance()) { HBasicBlock* block = b.Current(); // Traverse this block's instructions in backward order and remove @@ -47,4 +115,9 @@ void HDeadCodeElimination::Run() { } } +void HDeadCodeElimination::Run() { + RemoveDeadBlocks(); + RemoveDeadInstructions(); +} + } // namespace art diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h index cee9364c84..0bea0fc1c2 100644 --- a/compiler/optimizing/dead_code_elimination.h +++ b/compiler/optimizing/dead_code_elimination.h @@ -40,6 +40,10 @@ class HDeadCodeElimination : public HOptimization { "dead_code_elimination"; private: + void MaybeRecordDeadBlock(HBasicBlock* block); + void RemoveDeadBlocks(); + void RemoveDeadInstructions(); + DISALLOW_COPY_AND_ASSIGN(HDeadCodeElimination); }; diff --git a/compiler/optimizing/dead_code_elimination_test.cc b/compiler/optimizing/dead_code_elimination_test.cc index 98ae1ec5d3..3209d3eb18 100644 --- a/compiler/optimizing/dead_code_elimination_test.cc +++ b/compiler/optimizing/dead_code_elimination_test.cc @@ -169,20 +169,25 @@ TEST(DeadCodeElimination, AdditionsAndInconditionalJumps) { "BasicBlock 5, pred: 4\n" " 28: Exit\n"; - // Expected difference after dead code elimination. - diff_t expected_diff = { - { " 13: IntConstant [14]\n", removed }, - { " 24: IntConstant [25]\n", removed }, - { " 14: Add(19, 13) [25]\n", removed }, - // The SuspendCheck instruction following this Add instruction - // inserts the latter in an environment, thus making it "used" and - // therefore non removable. It ensues that some other Add and - // IntConstant instructions cannot be removed, as they are direct - // or indirect inputs of the initial Add instruction. - { " 19: Add(9, 18) [14]\n", " 19: Add(9, 18) []\n" }, - { " 25: Add(14, 24)\n", removed }, - }; - std::string expected_after = Patch(expected_before, expected_diff); + // The SuspendCheck instruction following this Add instruction + // inserts the latter in an environment, thus making it "used" and + // therefore non removable. It ensures that some other Add and + // IntConstant instructions cannot be removed, as they are direct + // or indirect inputs of the initial Add instruction. + std::string expected_after = + "BasicBlock 0, succ: 1\n" + " 3: IntConstant [9]\n" + " 5: IntConstant [9]\n" + " 18: IntConstant [19]\n" + " 29: SuspendCheck\n" + " 30: Goto 1\n" + "BasicBlock 1, pred: 0, succ: 5\n" + " 9: Add(3, 5) [19]\n" + " 19: Add(9, 18) []\n" + " 21: SuspendCheck\n" + " 27: ReturnVoid\n" + "BasicBlock 5, pred: 1\n" + " 28: Exit\n"; TestCode(data, expected_before, expected_after); } diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc index 8950635d6a..dc3124b35f 100644 --- a/compiler/optimizing/graph_checker.cc +++ b/compiler/optimizing/graph_checker.cc @@ -121,6 +121,18 @@ void GraphChecker::VisitBasicBlock(HBasicBlock* block) { } } +void GraphChecker::VisitBoundsCheck(HBoundsCheck* check) { + if (!GetGraph()->HasBoundsChecks()) { + AddError(StringPrintf("Instruction %s:%d is a HBoundsCheck, " + "but HasBoundsChecks() returns false", + check->DebugName(), + check->GetId())); + } + + // Perform the instruction base checks too. + VisitInstruction(check); +} + void GraphChecker::VisitInstruction(HInstruction* instruction) { if (seen_ids_.IsBitSet(instruction->GetId())) { AddError(StringPrintf("Instruction id %d is duplicate in graph.", @@ -191,6 +203,30 @@ void GraphChecker::VisitInstruction(HInstruction* instruction) { } } +void GraphChecker::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + VisitInstruction(invoke); + + if (invoke->IsStaticWithExplicitClinitCheck()) { + size_t last_input_index = invoke->InputCount() - 1; + HInstruction* last_input = invoke->InputAt(last_input_index); + if (last_input == nullptr) { + AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check " + "has a null pointer as last input.", + invoke->DebugName(), + invoke->GetId())); + } + if (!last_input->IsClinitCheck() && !last_input->IsLoadClass()) { + AddError(StringPrintf("Static invoke %s:%d marked as having an explicit clinit check " + "has a last instruction (%s:%d) which is neither a clinit check " + "nor a load class instruction.", + invoke->DebugName(), + invoke->GetId(), + last_input->DebugName(), + last_input->GetId())); + } + } +} + void SSAChecker::VisitBasicBlock(HBasicBlock* block) { super_type::VisitBasicBlock(block); @@ -264,6 +300,8 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) { } } + const ArenaBitVector& loop_blocks = loop_header->GetLoopInformation()->GetBlocks(); + // Ensure there is only one back edge per loop. size_t num_back_edges = loop_header->GetLoopInformation()->GetBackEdges().Size(); @@ -276,16 +314,27 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) { "Loop defined by header %d has several back edges: %zu.", id, num_back_edges)); + } else { + DCHECK_EQ(num_back_edges, 1u); + int back_edge_id = loop_header->GetLoopInformation()->GetBackEdges().Get(0)->GetBlockId(); + if (!loop_blocks.IsBitSet(back_edge_id)) { + AddError(StringPrintf( + "Loop defined by header %d has an invalid back edge %d.", + id, + back_edge_id)); + } } - // Ensure all blocks in the loop are dominated by the loop header. - const ArenaBitVector& loop_blocks = - loop_header->GetLoopInformation()->GetBlocks(); + // Ensure all blocks in the loop are live and dominated by the loop header. for (uint32_t i : loop_blocks.Indexes()) { HBasicBlock* loop_block = GetGraph()->GetBlocks().Get(i); - if (!loop_header->Dominates(loop_block)) { + if (loop_block == nullptr) { + AddError(StringPrintf("Loop defined by header %d contains a previously removed block %d.", + id, + i)); + } else if (!loop_header->Dominates(loop_block)) { AddError(StringPrintf("Loop block %d not dominated by loop header %d.", - loop_block->GetBlockId(), + i, id)); } } @@ -296,7 +345,7 @@ void SSAChecker::CheckLoop(HBasicBlock* loop_header) { if (!loop_blocks.IsSubsetOf(&outer_info->GetBlocks())) { AddError(StringPrintf("Blocks of loop defined by header %d are not a subset of blocks of " "an outer loop defined by header %d.", - loop_header->GetBlockId(), + id, outer_info->GetHeader()->GetBlockId())); } } @@ -483,7 +532,7 @@ void SSAChecker::VisitBinaryOperation(HBinaryOperation* op) { Primitive::PrettyDescriptor(op->InputAt(1)->GetType()))); } } else { - if (PrimitiveKind(op->InputAt(1)->GetType()) != PrimitiveKind(op->InputAt(0)->GetType())) { + if (PrimitiveKind(op->InputAt(0)->GetType()) != PrimitiveKind(op->InputAt(1)->GetType())) { AddError(StringPrintf( "Binary operation %s %d has inputs of different types: " "%s, and %s.", @@ -508,7 +557,7 @@ void SSAChecker::VisitBinaryOperation(HBinaryOperation* op) { "from its input type: %s vs %s.", op->DebugName(), op->GetId(), Primitive::PrettyDescriptor(op->GetType()), - Primitive::PrettyDescriptor(op->InputAt(1)->GetType()))); + Primitive::PrettyDescriptor(op->InputAt(0)->GetType()))); } } } diff --git a/compiler/optimizing/graph_checker.h b/compiler/optimizing/graph_checker.h index 24fee373f9..b4314da03b 100644 --- a/compiler/optimizing/graph_checker.h +++ b/compiler/optimizing/graph_checker.h @@ -42,6 +42,12 @@ class GraphChecker : public HGraphDelegateVisitor { // Check `instruction`. void VisitInstruction(HInstruction* instruction) OVERRIDE; + // Perform control-flow graph checks on instruction. + void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE; + + // Check that the HasBoundsChecks() flag is set for bounds checks. + void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE; + // Was the last visit of the graph valid? bool IsValid() const { return errors_.empty(); diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc index bffd639e83..ada32db047 100644 --- a/compiler/optimizing/inliner.cc +++ b/compiler/optimizing/inliner.cc @@ -130,6 +130,16 @@ bool HInliner::TryInline(HInvoke* invoke_instruction, return false; } + if (invoke_instruction->IsInvokeStaticOrDirect() && + invoke_instruction->AsInvokeStaticOrDirect()->IsStaticWithImplicitClinitCheck()) { + // Case of a static method that cannot be inlined because it implicitly + // requires an initialization check of its declaring class. + VLOG(compiler) << "Method " << PrettyMethod(method_index, caller_dex_file) + << " is not inlined because it is static and requires a clinit" + << " check that cannot be emitted due to Dex cache limitations"; + return false; + } + if (!TryBuildAndInline(resolved_method, invoke_instruction, method_index, can_use_dex_cache)) { resolved_method->SetShouldNotInline(); return false; @@ -258,8 +268,8 @@ bool HInliner::TryBuildAndInline(Handle<mirror::ArtMethod> resolved_method, callee_graph->InlineInto(graph_, invoke_instruction); - if (callee_graph->HasArrayAccesses()) { - graph_->SetHasArrayAccesses(true); + if (callee_graph->HasBoundsChecks()) { + graph_->SetHasBoundsChecks(true); } return true; diff --git a/compiler/optimizing/intrinsics_arm.cc b/compiler/optimizing/intrinsics_arm.cc index 932192e4fd..abdf04ebb1 100644 --- a/compiler/optimizing/intrinsics_arm.cc +++ b/compiler/optimizing/intrinsics_arm.cc @@ -79,6 +79,7 @@ static void MoveFromReturnRegister(Location trg, Primitive::Type type, CodeGener static void MoveArguments(HInvoke* invoke, ArenaAllocator* arena, CodeGeneratorARM* codegen) { if (invoke->InputCount() == 0) { + // No argument to move. return; } diff --git a/compiler/optimizing/intrinsics_arm64.cc b/compiler/optimizing/intrinsics_arm64.cc index 117d6a4279..7a753b2da9 100644 --- a/compiler/optimizing/intrinsics_arm64.cc +++ b/compiler/optimizing/intrinsics_arm64.cc @@ -88,6 +88,7 @@ static void MoveFromReturnRegister(Location trg, static void MoveArguments(HInvoke* invoke, ArenaAllocator* arena, CodeGeneratorARM64* codegen) { if (invoke->InputCount() == 0) { + // No argument to move. return; } diff --git a/compiler/optimizing/intrinsics_x86.cc b/compiler/optimizing/intrinsics_x86.cc index a8e2cdf1f6..7275edb695 100644 --- a/compiler/optimizing/intrinsics_x86.cc +++ b/compiler/optimizing/intrinsics_x86.cc @@ -113,6 +113,7 @@ static void MoveFromReturnRegister(Location target, static void MoveArguments(HInvoke* invoke, ArenaAllocator* arena, CodeGeneratorX86* codegen) { if (invoke->InputCount() == 0) { + // No argument to move. return; } @@ -1038,7 +1039,7 @@ static void CreateLongIntToVoidLocations(ArenaAllocator* arena, Primitive::Type LocationSummary::kNoCall, kIntrinsified); locations->SetInAt(0, Location::RequiresRegister()); - HInstruction *value = invoke->InputAt(1); + HInstruction* value = invoke->InputAt(1); if (size == Primitive::kPrimByte) { locations->SetInAt(1, Location::ByteRegisterOrConstant(EDX, value)); } else { diff --git a/compiler/optimizing/intrinsics_x86_64.cc b/compiler/optimizing/intrinsics_x86_64.cc index 5d24d1fbfb..35daaf60bb 100644 --- a/compiler/optimizing/intrinsics_x86_64.cc +++ b/compiler/optimizing/intrinsics_x86_64.cc @@ -105,6 +105,7 @@ static void MoveFromReturnRegister(Location trg, static void MoveArguments(HInvoke* invoke, ArenaAllocator* arena, CodeGeneratorX86_64* codegen) { if (invoke->InputCount() == 0) { + // No argument to move. return; } diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 6ab57b8e50..e2eb46aabb 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -303,25 +303,6 @@ HNullConstant* HGraph::GetNullConstant() { return cached_null_constant_; } -template <class InstructionType, typename ValueType> -InstructionType* HGraph::CreateConstant(ValueType value, - ArenaSafeMap<ValueType, InstructionType*>* cache) { - // Try to find an existing constant of the given value. - InstructionType* constant = nullptr; - auto cached_constant = cache->find(value); - if (cached_constant != cache->end()) { - constant = cached_constant->second; - } - - // If not found or previously deleted, create and cache a new instruction. - if (constant == nullptr || constant->GetBlock() == nullptr) { - constant = new (arena_) InstructionType(value); - cache->Overwrite(value, constant); - InsertConstant(constant); - } - return constant; -} - HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value) { switch (type) { case Primitive::Type::kPrimBoolean: @@ -343,6 +324,18 @@ HConstant* HGraph::GetConstant(Primitive::Type type, int64_t value) { } } +void HGraph::CacheFloatConstant(HFloatConstant* constant) { + int32_t value = bit_cast<int32_t, float>(constant->GetValue()); + DCHECK(cached_float_constants_.find(value) == cached_float_constants_.end()); + cached_float_constants_.Overwrite(value, constant); +} + +void HGraph::CacheDoubleConstant(HDoubleConstant* constant) { + int64_t value = bit_cast<int64_t, double>(constant->GetValue()); + DCHECK(cached_double_constants_.find(value) == cached_double_constants_.end()); + cached_double_constants_.Overwrite(value, constant); +} + void HLoopInformation::Add(HBasicBlock* block) { blocks_.SetBit(block->GetBlockId()); } @@ -481,6 +474,7 @@ static void Remove(HInstructionList* instruction_list, } void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) { + DCHECK(!instruction->IsPhi()); Remove(&instructions_, this, instruction, ensure_safety); } @@ -488,6 +482,14 @@ void HBasicBlock::RemovePhi(HPhi* phi, bool ensure_safety) { Remove(&phis_, this, phi, ensure_safety); } +void HBasicBlock::RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety) { + if (instruction->IsPhi()) { + RemovePhi(instruction->AsPhi(), ensure_safety); + } else { + RemoveInstruction(instruction, ensure_safety); + } +} + void HEnvironment::CopyFrom(HEnvironment* env) { for (size_t i = 0; i < env->Size(); i++) { HInstruction* instruction = env->GetInstructionAt(i); @@ -498,6 +500,28 @@ void HEnvironment::CopyFrom(HEnvironment* env) { } } +void HEnvironment::CopyFromWithLoopPhiAdjustment(HEnvironment* env, + HBasicBlock* loop_header) { + DCHECK(loop_header->IsLoopHeader()); + for (size_t i = 0; i < env->Size(); i++) { + HInstruction* instruction = env->GetInstructionAt(i); + SetRawEnvAt(i, instruction); + if (instruction == nullptr) { + continue; + } + if (instruction->IsLoopHeaderPhi() && (instruction->GetBlock() == loop_header)) { + // At the end of the loop pre-header, the corresponding value for instruction + // is the first input of the phi. + HInstruction* initial = instruction->AsPhi()->InputAt(0); + DCHECK(initial->GetBlock()->Dominates(loop_header)); + SetRawEnvAt(i, initial); + initial->AddEnvUseAt(this, i); + } else { + instruction->AddEnvUseAt(this, i); + } + } +} + void HEnvironment::RemoveAsUserOfInput(size_t index) const { const HUserRecord<HEnvironment*> user_record = vregs_.Get(index); user_record.GetInstruction()->RemoveEnvironmentUser(user_record.GetUseNode()); @@ -672,6 +696,11 @@ void HPhi::AddInput(HInstruction* input) { input->AddUseAt(this, inputs_.Size() - 1); } +void HPhi::RemoveInputAt(size_t index) { + RemoveAsUserOfInput(index); + inputs_.DeleteAt(index); +} + #define DEFINE_ACCEPT(name, super) \ void H##name::Accept(HGraphVisitor* visitor) { \ visitor->Visit##name(this); \ @@ -867,6 +896,15 @@ bool HBasicBlock::HasSinglePhi() const { return !GetPhis().IsEmpty() && GetFirstPhi()->GetNext() == nullptr; } +size_t HInstructionList::CountSize() const { + size_t size = 0; + HInstruction* current = first_instruction_; + for (; current != nullptr; current = current->GetNext()) { + size++; + } + return size; +} + void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const { for (HInstruction* current = first_instruction_; current != nullptr; @@ -898,40 +936,167 @@ void HInstructionList::Add(const HInstructionList& instruction_list) { } } -void HBasicBlock::DisconnectFromAll() { - DCHECK(dominated_blocks_.IsEmpty()) << "Unimplemented scenario"; +void HBasicBlock::DisconnectAndDelete() { + // Dominators must be removed after all the blocks they dominate. This way + // a loop header is removed last, a requirement for correct loop information + // iteration. + DCHECK(dominated_blocks_.IsEmpty()); + + // Remove the block from all loops it is included in. + for (HLoopInformationOutwardIterator it(*this); !it.Done(); it.Advance()) { + HLoopInformation* loop_info = it.Current(); + loop_info->Remove(this); + if (loop_info->IsBackEdge(*this)) { + // This deliberately leaves the loop in an inconsistent state and will + // fail SSAChecker unless the entire loop is removed during the pass. + loop_info->RemoveBackEdge(this); + } + } + // Disconnect the block from its predecessors and update their control-flow + // instructions. for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { - predecessors_.Get(i)->successors_.Delete(this); + HBasicBlock* predecessor = predecessors_.Get(i); + HInstruction* last_instruction = predecessor->GetLastInstruction(); + predecessor->RemoveInstruction(last_instruction); + predecessor->RemoveSuccessor(this); + if (predecessor->GetSuccessors().Size() == 1u) { + DCHECK(last_instruction->IsIf()); + predecessor->AddInstruction(new (graph_->GetArena()) HGoto()); + } else { + // The predecessor has no remaining successors and therefore must be dead. + // We deliberately leave it without a control-flow instruction so that the + // SSAChecker fails unless it is not removed during the pass too. + DCHECK_EQ(predecessor->GetSuccessors().Size(), 0u); + } } + predecessors_.Reset(); + + // Disconnect the block from its successors and update their dominators + // and phis. for (size_t i = 0, e = successors_.Size(); i < e; ++i) { - successors_.Get(i)->predecessors_.Delete(this); - } - dominator_->dominated_blocks_.Delete(this); + HBasicBlock* successor = successors_.Get(i); + // Delete this block from the list of predecessors. + size_t this_index = successor->GetPredecessorIndexOf(this); + successor->predecessors_.DeleteAt(this_index); + + // Check that `successor` has other predecessors, otherwise `this` is the + // dominator of `successor` which violates the order DCHECKed at the top. + DCHECK(!successor->predecessors_.IsEmpty()); + + // Recompute the successor's dominator. + HBasicBlock* old_dominator = successor->GetDominator(); + HBasicBlock* new_dominator = successor->predecessors_.Get(0); + for (size_t j = 1, f = successor->predecessors_.Size(); j < f; ++j) { + new_dominator = graph_->FindCommonDominator( + new_dominator, successor->predecessors_.Get(j)); + } + if (old_dominator != new_dominator) { + successor->SetDominator(new_dominator); + old_dominator->RemoveDominatedBlock(successor); + new_dominator->AddDominatedBlock(successor); + } - predecessors_.Reset(); + // Remove this block's entries in the successor's phis. + if (successor->predecessors_.Size() == 1u) { + // The successor has just one predecessor left. Replace phis with the only + // remaining input. + for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { + HPhi* phi = phi_it.Current()->AsPhi(); + phi->ReplaceWith(phi->InputAt(1 - this_index)); + successor->RemovePhi(phi); + } + } else { + for (HInstructionIterator phi_it(successor->GetPhis()); !phi_it.Done(); phi_it.Advance()) { + phi_it.Current()->AsPhi()->RemoveInputAt(this_index); + } + } + } successors_.Reset(); - dominator_ = nullptr; - graph_ = nullptr; + + // Disconnect from the dominator. + dominator_->RemoveDominatedBlock(this); + SetDominator(nullptr); + + // Delete from the graph. The function safely deletes remaining instructions + // and updates the reverse post order. + graph_->DeleteDeadBlock(this); + SetGraph(nullptr); } void HBasicBlock::MergeWith(HBasicBlock* other) { - DCHECK(successors_.IsEmpty()) << "Unimplemented block merge scenario"; - DCHECK(dominated_blocks_.IsEmpty() - || (dominated_blocks_.Size() == 1 && dominated_blocks_.Get(0) == other)) - << "Unimplemented block merge scenario"; + DCHECK_EQ(GetGraph(), other->GetGraph()); + DCHECK(GetDominatedBlocks().Contains(other)); + DCHECK_EQ(GetSuccessors().Size(), 1u); + DCHECK_EQ(GetSuccessors().Get(0), other); + DCHECK_EQ(other->GetPredecessors().Size(), 1u); + DCHECK_EQ(other->GetPredecessors().Get(0), this); DCHECK(other->GetPhis().IsEmpty()); + // Move instructions from `other` to `this`. + DCHECK(EndsWithControlFlowInstruction()); + RemoveInstruction(GetLastInstruction()); + instructions_.Add(other->GetInstructions()); + other->instructions_.SetBlockOfInstructions(this); + other->instructions_.Clear(); + + // Remove `other` from the loops it is included in. + for (HLoopInformationOutwardIterator it(*other); !it.Done(); it.Advance()) { + HLoopInformation* loop_info = it.Current(); + loop_info->Remove(other); + if (loop_info->IsBackEdge(*other)) { + loop_info->ClearBackEdges(); + loop_info->AddBackEdge(this); + } + } + + // Update links to the successors of `other`. successors_.Reset(); - dominated_blocks_.Reset(); + while (!other->successors_.IsEmpty()) { + HBasicBlock* successor = other->successors_.Get(0); + successor->ReplacePredecessor(other, this); + } + + // Update the dominator tree. + dominated_blocks_.Delete(other); + for (size_t i = 0, e = other->GetDominatedBlocks().Size(); i < e; ++i) { + HBasicBlock* dominated = other->GetDominatedBlocks().Get(i); + dominated_blocks_.Add(dominated); + dominated->SetDominator(this); + } + other->dominated_blocks_.Reset(); + other->dominator_ = nullptr; + + // Clear the list of predecessors of `other` in preparation of deleting it. + other->predecessors_.Reset(); + + // Delete `other` from the graph. The function updates reverse post order. + graph_->DeleteDeadBlock(other); + other->SetGraph(nullptr); +} + +void HBasicBlock::MergeWithInlined(HBasicBlock* other) { + DCHECK_NE(GetGraph(), other->GetGraph()); + DCHECK(GetDominatedBlocks().IsEmpty()); + DCHECK(GetSuccessors().IsEmpty()); + DCHECK(!EndsWithControlFlowInstruction()); + DCHECK_EQ(other->GetPredecessors().Size(), 1u); + DCHECK(other->GetPredecessors().Get(0)->IsEntryBlock()); + DCHECK(other->GetPhis().IsEmpty()); + DCHECK(!other->IsInLoop()); + + // Move instructions from `other` to `this`. instructions_.Add(other->GetInstructions()); - other->GetInstructions().SetBlockOfInstructions(this); + other->instructions_.SetBlockOfInstructions(this); - while (!other->GetSuccessors().IsEmpty()) { - HBasicBlock* successor = other->GetSuccessors().Get(0); + // Update links to the successors of `other`. + successors_.Reset(); + while (!other->successors_.IsEmpty()) { + HBasicBlock* successor = other->successors_.Get(0); successor->ReplacePredecessor(other, this); } + // Update the dominator tree. for (size_t i = 0, e = other->GetDominatedBlocks().Size(); i < e; ++i) { HBasicBlock* dominated = other->GetDominatedBlocks().Get(i); dominated_blocks_.Add(dominated); @@ -973,6 +1138,24 @@ static void MakeRoomFor(GrowableArray<HBasicBlock*>* blocks, } } +void HGraph::DeleteDeadBlock(HBasicBlock* block) { + DCHECK_EQ(block->GetGraph(), this); + DCHECK(block->GetSuccessors().IsEmpty()); + DCHECK(block->GetPredecessors().IsEmpty()); + DCHECK(block->GetDominatedBlocks().IsEmpty()); + DCHECK(block->GetDominator() == nullptr); + + for (HBackwardInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { + block->RemoveInstruction(it.Current()); + } + for (HBackwardInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) { + block->RemovePhi(it.Current()->AsPhi()); + } + + reverse_post_order_.Delete(block); + blocks_.Put(block->GetBlockId(), nullptr); +} + void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { if (GetBlocks().Size() == 3) { // Simple case of an entry block, a body block, and an exit block. @@ -1005,7 +1188,7 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { HBasicBlock* first = entry_block_->GetSuccessors().Get(0); DCHECK(!first->IsInLoop()); - at->MergeWith(first); + at->MergeWithInlined(first); exit_block_->ReplaceWith(to); // Update all predecessors of the exit block (now the `to` block) @@ -1113,7 +1296,7 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { // - Remove suspend checks, that hold an environment. // We must do this after the other blocks have been inlined, otherwise ids of // constants could overlap with the inner graph. - int parameter_index = 0; + size_t parameter_index = 0; for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) { HInstruction* current = it.Current(); if (current->IsNullConstant()) { @@ -1122,10 +1305,19 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { current->ReplaceWith(outer_graph->GetIntConstant(current->AsIntConstant()->GetValue())); } else if (current->IsLongConstant()) { current->ReplaceWith(outer_graph->GetLongConstant(current->AsLongConstant()->GetValue())); - } else if (current->IsFloatConstant() || current->IsDoubleConstant()) { - // TODO: Don't duplicate floating-point constants. - current->MoveBefore(outer_graph->GetEntryBlock()->GetLastInstruction()); + } else if (current->IsFloatConstant()) { + current->ReplaceWith(outer_graph->GetFloatConstant(current->AsFloatConstant()->GetValue())); + } else if (current->IsDoubleConstant()) { + current->ReplaceWith(outer_graph->GetDoubleConstant(current->AsDoubleConstant()->GetValue())); } else if (current->IsParameterValue()) { + if (kIsDebugBuild + && invoke->IsInvokeStaticOrDirect() + && invoke->AsInvokeStaticOrDirect()->IsStaticWithExplicitClinitCheck()) { + // Ensure we do not use the last input of `invoke`, as it + // contains a clinit check which is not an actual argument. + size_t last_input_index = invoke->InputCount() - 1; + DCHECK(parameter_index != last_input_index); + } current->ReplaceWith(invoke->InputAt(parameter_index++)); } else { DCHECK(current->IsGoto() || current->IsSuspendCheck()); @@ -1137,53 +1329,6 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { invoke->GetBlock()->RemoveInstruction(invoke); } -void HGraph::MergeEmptyBranches(HBasicBlock* start_block, HBasicBlock* end_block) { - // Find the two branches of an If. - DCHECK_EQ(start_block->GetSuccessors().Size(), 2u); - HBasicBlock* left_branch = start_block->GetSuccessors().Get(0); - HBasicBlock* right_branch = start_block->GetSuccessors().Get(1); - - // Make sure this is a diamond control-flow path. - DCHECK_EQ(left_branch->GetSuccessors().Get(0), end_block); - DCHECK_EQ(right_branch->GetSuccessors().Get(0), end_block); - DCHECK_EQ(end_block->GetPredecessors().Size(), 2u); - DCHECK_EQ(start_block, end_block->GetDominator()); - - // Disconnect the branches and merge the two blocks. This will move - // all instructions from 'end_block' to 'start_block'. - DCHECK(left_branch->IsSingleGoto()); - DCHECK(right_branch->IsSingleGoto()); - left_branch->DisconnectFromAll(); - right_branch->DisconnectFromAll(); - start_block->RemoveInstruction(start_block->GetLastInstruction()); - start_block->MergeWith(end_block); - - // Delete the now redundant blocks from the graph. - blocks_.Put(left_branch->GetBlockId(), nullptr); - blocks_.Put(right_branch->GetBlockId(), nullptr); - blocks_.Put(end_block->GetBlockId(), nullptr); - - // Update reverse post order. - reverse_post_order_.Delete(left_branch); - reverse_post_order_.Delete(right_branch); - reverse_post_order_.Delete(end_block); - - // Update loops which contain the code. - for (HLoopInformationOutwardIterator it(*start_block); !it.Done(); it.Advance()) { - HLoopInformation* loop_info = it.Current(); - DCHECK(loop_info->Contains(*left_branch)); - DCHECK(loop_info->Contains(*right_branch)); - DCHECK(loop_info->Contains(*end_block)); - loop_info->Remove(left_branch); - loop_info->Remove(right_branch); - loop_info->Remove(end_block); - if (loop_info->IsBackEdge(*end_block)) { - loop_info->RemoveBackEdge(end_block); - loop_info->AddBackEdge(start_block); - } - } -} - std::ostream& operator<<(std::ostream& os, const ReferenceTypeInfo& rhs) { ScopedObjectAccess soa(Thread::Current()); os << "[" diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h index b89487f4f6..0533bff0b3 100644 --- a/compiler/optimizing/nodes.h +++ b/compiler/optimizing/nodes.h @@ -97,6 +97,9 @@ class HInstructionList { void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list); void Add(const HInstructionList& instruction_list); + // Return the number of instructions in the list. This is an expensive operation. + size_t CountSize() const; + private: HInstruction* first_instruction_; HInstruction* last_instruction_; @@ -124,12 +127,14 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { number_of_vregs_(0), number_of_in_vregs_(0), temporaries_vreg_slots_(0), - has_array_accesses_(false), + has_bounds_checks_(false), debuggable_(debuggable), current_instruction_id_(start_instruction_id), cached_null_constant_(nullptr), cached_int_constants_(std::less<int32_t>(), arena->Adapter()), - cached_long_constants_(std::less<int64_t>(), arena->Adapter()) {} + cached_float_constants_(std::less<int32_t>(), arena->Adapter()), + cached_long_constants_(std::less<int64_t>(), arena->Adapter()), + cached_double_constants_(std::less<int64_t>(), arena->Adapter()) {} ArenaAllocator* GetArena() const { return arena_; } const GrowableArray<HBasicBlock*>& GetBlocks() const { return blocks_; } @@ -168,7 +173,8 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { // Inline this graph in `outer_graph`, replacing the given `invoke` instruction. void InlineInto(HGraph* outer_graph, HInvoke* invoke); - void MergeEmptyBranches(HBasicBlock* start_block, HBasicBlock* end_block); + // Removes `block` from the graph. + void DeleteDeadBlock(HBasicBlock* block); void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor); void SimplifyLoop(HBasicBlock* header); @@ -226,19 +232,19 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { return linear_order_; } - bool HasArrayAccesses() const { - return has_array_accesses_; + bool HasBoundsChecks() const { + return has_bounds_checks_; } - void SetHasArrayAccesses(bool value) { - has_array_accesses_ = value; + void SetHasBoundsChecks(bool value) { + has_bounds_checks_ = value; } bool IsDebuggable() const { return debuggable_; } // Returns a constant of the given type and value. If it does not exist - // already, it is created and inserted into the graph. Only integral types - // are currently supported. + // already, it is created and inserted into the graph. This method is only for + // integral types. HConstant* GetConstant(Primitive::Type type, int64_t value); HNullConstant* GetNullConstant(); HIntConstant* GetIntConstant(int32_t value) { @@ -247,9 +253,16 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { HLongConstant* GetLongConstant(int64_t value) { return CreateConstant(value, &cached_long_constants_); } + HFloatConstant* GetFloatConstant(float value) { + return CreateConstant(bit_cast<int32_t, float>(value), &cached_float_constants_); + } + HDoubleConstant* GetDoubleConstant(double value) { + return CreateConstant(bit_cast<int64_t, double>(value), &cached_double_constants_); + } - private: HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const; + + private: void VisitBlockForDominatorTree(HBasicBlock* block, HBasicBlock* predecessor, GrowableArray<size_t>* visits); @@ -260,10 +273,34 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const; void RemoveDeadBlocks(const ArenaBitVector& visited); - template <class InstType, typename ValueType> - InstType* CreateConstant(ValueType value, ArenaSafeMap<ValueType, InstType*>* cache); + template <class InstructionType, typename ValueType> + InstructionType* CreateConstant(ValueType value, + ArenaSafeMap<ValueType, InstructionType*>* cache) { + // Try to find an existing constant of the given value. + InstructionType* constant = nullptr; + auto cached_constant = cache->find(value); + if (cached_constant != cache->end()) { + constant = cached_constant->second; + } + + // If not found or previously deleted, create and cache a new instruction. + if (constant == nullptr || constant->GetBlock() == nullptr) { + constant = new (arena_) InstructionType(value); + cache->Overwrite(value, constant); + InsertConstant(constant); + } + return constant; + } + void InsertConstant(HConstant* instruction); + // Cache a float constant into the graph. This method should only be + // called by the SsaBuilder when creating "equivalent" instructions. + void CacheFloatConstant(HFloatConstant* constant); + + // See CacheFloatConstant comment. + void CacheDoubleConstant(HDoubleConstant* constant); + ArenaAllocator* const arena_; // List of blocks in insertion order. @@ -290,8 +327,8 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { // Number of vreg size slots that the temporaries use (used in baseline compiler). size_t temporaries_vreg_slots_; - // Has array accesses. We can totally skip BCE if it's false. - bool has_array_accesses_; + // Has bounds checks. We can totally skip BCE if it's false. + bool has_bounds_checks_; // Indicates whether the graph should be compiled in a way that // ensures full debuggability. If false, we can apply more @@ -301,11 +338,14 @@ class HGraph : public ArenaObject<kArenaAllocMisc> { // The current id to assign to a newly added instruction. See HInstruction.id_. int32_t current_instruction_id_; - // Cached common constants often needed by optimization passes. + // Cached constants. HNullConstant* cached_null_constant_; ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_; + ArenaSafeMap<int32_t, HFloatConstant*> cached_float_constants_; ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_; + ArenaSafeMap<int64_t, HDoubleConstant*> cached_double_constants_; + friend class SsaBuilder; // For caching constants. friend class SsaLivenessAnalysis; // For the linear order. ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1); DISALLOW_COPY_AND_ASSIGN(HGraph); @@ -451,6 +491,7 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { HBasicBlock* GetDominator() const { return dominator_; } void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; } void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(block); } + void RemoveDominatedBlock(HBasicBlock* block) { dominated_blocks_.Delete(block); } void ReplaceDominatedBlock(HBasicBlock* existing, HBasicBlock* new_block) { for (size_t i = 0, e = dominated_blocks_.Size(); i < e; ++i) { if (dominated_blocks_.Get(i) == existing) { @@ -520,6 +561,13 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { predecessors_.Put(1, temp); } + void SwapSuccessors() { + DCHECK_EQ(successors_.Size(), 2u); + HBasicBlock* temp = successors_.Get(0); + successors_.Put(0, successors_.Get(1)); + successors_.Put(1, temp); + } + size_t GetPredecessorIndexOf(HBasicBlock* predecessor) { for (size_t i = 0, e = predecessors_.Size(); i < e; ++i) { if (predecessors_.Get(i) == predecessor) { @@ -550,7 +598,7 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { // that this method does not update the graph, reverse post order, loop // information, nor make sure the blocks are consistent (for example ending // with a control flow instruction). - void MergeWith(HBasicBlock* other); + void MergeWithInlined(HBasicBlock* other); // Replace `this` with `other`. Predecessors, successors, and dominated blocks // of `this` are moved to `other`. @@ -559,12 +607,17 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { // with a control flow instruction). void ReplaceWith(HBasicBlock* other); - // Disconnects `this` from all its predecessors, successors and the dominator. - // It assumes that `this` does not dominate any blocks. - // Note that this method does not update the graph, reverse post order, loop - // information, nor make sure the blocks are consistent (for example ending - // with a control flow instruction). - void DisconnectFromAll(); + // Merge `other` at the end of `this`. This method updates loops, reverse post + // order, links to predecessors, successors, dominators and deletes the block + // from the graph. The two blocks must be successive, i.e. `this` the only + // predecessor of `other` and vice versa. + void MergeWith(HBasicBlock* other); + + // Disconnects `this` from all its predecessors, successors and dominator, + // removes it from all loops it is included in and eventually from the graph. + // The block must not dominate any other block. Predecessors and successors + // are safely updated. + void DisconnectAndDelete(); void AddInstruction(HInstruction* instruction); void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor); @@ -578,6 +631,7 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> { // instruction is not in use and removes it from the use lists of its inputs. void RemoveInstruction(HInstruction* instruction, bool ensure_safety = true); void RemovePhi(HPhi* phi, bool ensure_safety = true); + void RemoveInstructionOrPhi(HInstruction* instruction, bool ensure_safety = true); bool IsLoopHeader() const { return (loop_information_ != nullptr) && (loop_information_->GetHeader() == this); @@ -996,6 +1050,10 @@ class HEnvironment : public ArenaObject<kArenaAllocMisc> { } void CopyFrom(HEnvironment* env); + // Copy from `env`. If it's a loop phi for `loop_header`, copy the first + // input to the loop phi instead. This is for inserting instructions that + // require an environment (like HDeoptimization) in the loop pre-header. + void CopyFromWithLoopPhiAdjustment(HEnvironment* env, HBasicBlock* loop_header); void SetRawEnvAt(size_t index, HInstruction* instruction) { vregs_.Put(index, HUserRecord<HEnvironment*>(instruction)); @@ -1231,6 +1289,13 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> { environment_->CopyFrom(environment); } + void CopyEnvironmentFromWithLoopPhiAdjustment(HEnvironment* environment, + HBasicBlock* block) { + ArenaAllocator* allocator = GetBlock()->GetGraph()->GetArena(); + environment_ = new (allocator) HEnvironment(allocator, environment->Size()); + environment_->CopyFromWithLoopPhiAdjustment(environment, block); + } + // Returns the number of entries in the environment. Typically, that is the // number of dex registers in a method. It could be more in case of inlining. size_t EnvironmentSize() const; @@ -2023,13 +2088,14 @@ class HFloatConstant : public HConstant { private: explicit HFloatConstant(float value) : HConstant(Primitive::kPrimFloat), value_(value) {} + explicit HFloatConstant(int32_t value) + : HConstant(Primitive::kPrimFloat), value_(bit_cast<float, int32_t>(value)) {} const float value_; - // Only the SsaBuilder can currently create floating-point constants. If we - // ever need to create them later in the pipeline, we will have to handle them - // the same way as integral constants. + // Only the SsaBuilder and HGraph can create floating-point constants. friend class SsaBuilder; + friend class HGraph; DISALLOW_COPY_AND_ASSIGN(HFloatConstant); }; @@ -2060,13 +2126,14 @@ class HDoubleConstant : public HConstant { private: explicit HDoubleConstant(double value) : HConstant(Primitive::kPrimDouble), value_(value) {} + explicit HDoubleConstant(int64_t value) + : HConstant(Primitive::kPrimDouble), value_(bit_cast<double, int64_t>(value)) {} const double value_; - // Only the SsaBuilder can currently create floating-point constants. If we - // ever need to create them later in the pipeline, we will have to handle them - // the same way as integral constants. + // Only the SsaBuilder and HGraph can create floating-point constants. friend class SsaBuilder; + friend class HGraph; DISALLOW_COPY_AND_ASSIGN(HDoubleConstant); }; @@ -2211,6 +2278,14 @@ class HInvoke : public HInstruction { class HInvokeStaticOrDirect : public HInvoke { public: + // Requirements of this method call regarding the class + // initialization (clinit) check of its declaring class. + enum class ClinitCheckRequirement { + kNone, // Class already initialized. + kExplicit, // Static call having explicit clinit check as last input. + kImplicit, // Static call implicitly requiring a clinit check. + }; + HInvokeStaticOrDirect(ArenaAllocator* arena, uint32_t number_of_arguments, Primitive::Type return_type, @@ -2218,11 +2293,13 @@ class HInvokeStaticOrDirect : public HInvoke { uint32_t dex_method_index, bool is_recursive, InvokeType original_invoke_type, - InvokeType invoke_type) + InvokeType invoke_type, + ClinitCheckRequirement clinit_check_requirement) : HInvoke(arena, number_of_arguments, return_type, dex_pc, dex_method_index), original_invoke_type_(original_invoke_type), invoke_type_(invoke_type), - is_recursive_(is_recursive) {} + is_recursive_(is_recursive), + clinit_check_requirement_(clinit_check_requirement) {} bool CanDoImplicitNullCheckOn(HInstruction* obj) const OVERRIDE { UNUSED(obj); @@ -2236,12 +2313,60 @@ class HInvokeStaticOrDirect : public HInvoke { bool IsRecursive() const { return is_recursive_; } bool NeedsDexCache() const OVERRIDE { return !IsRecursive(); } + // Is this instruction a call to a static method? + bool IsStatic() const { + return GetInvokeType() == kStatic; + } + + // Remove the art::HClinitCheck or art::HLoadClass instruction as + // last input (only relevant for static calls with explicit clinit + // check). + void RemoveClinitCheckOrLoadClassAsLastInput() { + DCHECK(IsStaticWithExplicitClinitCheck()); + size_t last_input_index = InputCount() - 1; + HInstruction* last_input = InputAt(last_input_index); + DCHECK(last_input != nullptr); + DCHECK(last_input->IsClinitCheck() || last_input->IsLoadClass()) << last_input->DebugName(); + RemoveAsUserOfInput(last_input_index); + inputs_.DeleteAt(last_input_index); + clinit_check_requirement_ = ClinitCheckRequirement::kImplicit; + DCHECK(IsStaticWithImplicitClinitCheck()); + } + + // Is this a call to a static method whose declaring class has an + // explicit intialization check in the graph? + bool IsStaticWithExplicitClinitCheck() const { + return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kExplicit); + } + + // Is this a call to a static method whose declaring class has an + // implicit intialization check requirement? + bool IsStaticWithImplicitClinitCheck() const { + return IsStatic() && (clinit_check_requirement_ == ClinitCheckRequirement::kImplicit); + } + DECLARE_INSTRUCTION(InvokeStaticOrDirect); + protected: + const HUserRecord<HInstruction*> InputRecordAt(size_t i) const OVERRIDE { + const HUserRecord<HInstruction*> input_record = HInvoke::InputRecordAt(i); + if (kIsDebugBuild && IsStaticWithExplicitClinitCheck() && (i == InputCount() - 1)) { + HInstruction* input = input_record.GetInstruction(); + // `input` is the last input of a static invoke marked as having + // an explicit clinit check. It must either be: + // - an art::HClinitCheck instruction, set by art::HGraphBuilder; or + // - an art::HLoadClass instruction, set by art::PrepareForRegisterAllocation. + DCHECK(input != nullptr); + DCHECK(input->IsClinitCheck() || input->IsLoadClass()) << input->DebugName(); + } + return input_record; + } + private: const InvokeType original_invoke_type_; const InvokeType invoke_type_; const bool is_recursive_; + ClinitCheckRequirement clinit_check_requirement_; DISALLOW_COPY_AND_ASSIGN(HInvokeStaticOrDirect); }; @@ -2746,6 +2871,7 @@ class HPhi : public HInstruction { size_t InputCount() const OVERRIDE { return inputs_.Size(); } void AddInput(HInstruction* input); + void RemoveInputAt(size_t index); Primitive::Type GetType() const OVERRIDE { return type_; } void SetType(Primitive::Type type) { type_ = type; } @@ -3214,7 +3340,6 @@ class HLoadString : public HExpression<0> { DISALLOW_COPY_AND_ASSIGN(HLoadString); }; -// TODO: Pass this check to HInvokeStaticOrDirect nodes. /** * Performs an initialization check on its Class object input. */ diff --git a/compiler/optimizing/optimization.cc b/compiler/optimizing/optimization.cc index b13e07eb22..c46a21955c 100644 --- a/compiler/optimizing/optimization.cc +++ b/compiler/optimizing/optimization.cc @@ -21,9 +21,9 @@ namespace art { -void HOptimization::MaybeRecordStat(MethodCompilationStat compilation_stat) const { +void HOptimization::MaybeRecordStat(MethodCompilationStat compilation_stat, size_t count) const { if (stats_ != nullptr) { - stats_->RecordStat(compilation_stat); + stats_->RecordStat(compilation_stat, count); } } diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h index 8b2028177b..ccf8de9f6a 100644 --- a/compiler/optimizing/optimization.h +++ b/compiler/optimizing/optimization.h @@ -48,7 +48,7 @@ class HOptimization : public ValueObject { void Check(); protected: - void MaybeRecordStat(MethodCompilationStat compilation_stat) const; + void MaybeRecordStat(MethodCompilationStat compilation_stat, size_t count = 1) const; HGraph* const graph_; // Used to record stats about the optimization. diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc index d99d35998a..05451bcaa6 100644 --- a/compiler/optimizing/optimizing_compiler.cc +++ b/compiler/optimizing/optimizing_compiler.cc @@ -328,7 +328,7 @@ static void RunOptimizations(HGraph* graph, HInliner inliner(graph, dex_compilation_unit, dex_compilation_unit, driver, stats); - HConstantFolding fold2(graph); + HConstantFolding fold2(graph, "constant_folding_after_inlining"); SideEffectsAnalysis side_effects(graph); GVNOptimization gvn(graph, side_effects); LICM licm(graph, side_effects); diff --git a/compiler/optimizing/optimizing_compiler_stats.h b/compiler/optimizing/optimizing_compiler_stats.h index e6508c9851..65c84e6942 100644 --- a/compiler/optimizing/optimizing_compiler_stats.h +++ b/compiler/optimizing/optimizing_compiler_stats.h @@ -58,8 +58,8 @@ class OptimizingCompilerStats { public: OptimizingCompilerStats() {} - void RecordStat(MethodCompilationStat stat) { - compile_stats_[stat]++; + void RecordStat(MethodCompilationStat stat, size_t count = 1) { + compile_stats_[stat] += count; } void Log() const { diff --git a/compiler/optimizing/prepare_for_register_allocation.cc b/compiler/optimizing/prepare_for_register_allocation.cc index f5d8d82571..fa6b3c292c 100644 --- a/compiler/optimizing/prepare_for_register_allocation.cc +++ b/compiler/optimizing/prepare_for_register_allocation.cc @@ -79,4 +79,26 @@ void PrepareForRegisterAllocation::VisitCondition(HCondition* condition) { } } +void PrepareForRegisterAllocation::VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) { + if (invoke->IsStaticWithExplicitClinitCheck()) { + size_t last_input_index = invoke->InputCount() - 1; + HInstruction* last_input = invoke->InputAt(last_input_index); + DCHECK(last_input->IsLoadClass()) << last_input->DebugName(); + + // Remove a load class instruction as last input of a static + // invoke, which has been added (along with a clinit check, + // removed by PrepareForRegisterAllocation::VisitClinitCheck + // previously) by the graph builder during the creation of the + // static invoke instruction, but is no longer required at this + // stage (i.e., after inlining has been performed). + invoke->RemoveClinitCheckOrLoadClassAsLastInput(); + + // If the load class instruction is no longer used, remove it from + // the graph. + if (!last_input->HasUses()) { + last_input->GetBlock()->RemoveInstruction(last_input); + } + } +} + } // namespace art diff --git a/compiler/optimizing/prepare_for_register_allocation.h b/compiler/optimizing/prepare_for_register_allocation.h index c28507c925..d7f277fa0d 100644 --- a/compiler/optimizing/prepare_for_register_allocation.h +++ b/compiler/optimizing/prepare_for_register_allocation.h @@ -39,6 +39,7 @@ class PrepareForRegisterAllocation : public HGraphDelegateVisitor { void VisitBoundType(HBoundType* bound_type) OVERRIDE; void VisitClinitCheck(HClinitCheck* check) OVERRIDE; void VisitCondition(HCondition* condition) OVERRIDE; + void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE; DISALLOW_COPY_AND_ASSIGN(PrepareForRegisterAllocation); }; diff --git a/compiler/optimizing/register_allocator.cc b/compiler/optimizing/register_allocator.cc index 0fdf051957..a8d006f104 100644 --- a/compiler/optimizing/register_allocator.cc +++ b/compiler/optimizing/register_allocator.cc @@ -1455,6 +1455,7 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) { : Location::StackSlot(interval->GetParent()->GetSpillSlot())); } UsePosition* use = current->GetFirstUse(); + UsePosition* env_use = current->GetFirstEnvironmentUse(); // Walk over all siblings, updating locations of use positions, and // connecting them when they are adjacent. @@ -1466,32 +1467,39 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) { LiveRange* range = current->GetFirstRange(); while (range != nullptr) { - while (use != nullptr && use->GetPosition() < range->GetStart()) { - DCHECK(use->GetIsEnvironment()); - use = use->GetNext(); - } + DCHECK(use == nullptr || use->GetPosition() >= range->GetStart()); while (use != nullptr && use->GetPosition() <= range->GetEnd()) { + DCHECK(!use->GetIsEnvironment()); DCHECK(current->CoversSlow(use->GetPosition()) || (use->GetPosition() == range->GetEnd())); LocationSummary* locations = use->GetUser()->GetLocations(); - if (use->GetIsEnvironment()) { - locations->SetEnvironmentAt(use->GetInputIndex(), source); - } else { - Location expected_location = locations->InAt(use->GetInputIndex()); - // The expected (actual) location may be invalid in case the input is unused. Currently - // this only happens for intrinsics. - if (expected_location.IsValid()) { - if (expected_location.IsUnallocated()) { - locations->SetInAt(use->GetInputIndex(), source); - } else if (!expected_location.IsConstant()) { - AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location); - } - } else { - DCHECK(use->GetUser()->IsInvoke()); - DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone); + Location expected_location = locations->InAt(use->GetInputIndex()); + // The expected (actual) location may be invalid in case the input is unused. Currently + // this only happens for intrinsics. + if (expected_location.IsValid()) { + if (expected_location.IsUnallocated()) { + locations->SetInAt(use->GetInputIndex(), source); + } else if (!expected_location.IsConstant()) { + AddInputMoveFor(interval->GetDefinedBy(), use->GetUser(), source, expected_location); } + } else { + DCHECK(use->GetUser()->IsInvoke()); + DCHECK(use->GetUser()->AsInvoke()->GetIntrinsic() != Intrinsics::kNone); } use = use->GetNext(); } + + // Walk over the environment uses, and update their locations. + while (env_use != nullptr && env_use->GetPosition() < range->GetStart()) { + env_use = env_use->GetNext(); + } + + while (env_use != nullptr && env_use->GetPosition() <= range->GetEnd()) { + DCHECK(current->CoversSlow(env_use->GetPosition()) || (env_use->GetPosition() == range->GetEnd())); + LocationSummary* locations = env_use->GetUser()->GetLocations(); + locations->SetEnvironmentAt(env_use->GetInputIndex(), source); + env_use = env_use->GetNext(); + } + range = range->GetNext(); } @@ -1553,14 +1561,7 @@ void RegisterAllocator::ConnectSiblings(LiveInterval* interval) { current = next_sibling; } while (current != nullptr); - if (kIsDebugBuild) { - // Following uses can only be environment uses. The location for - // these environments will be none. - while (use != nullptr) { - DCHECK(use->GetIsEnvironment()); - use = use->GetNext(); - } - } + DCHECK(use == nullptr); } void RegisterAllocator::ConnectSplitSiblings(LiveInterval* interval, diff --git a/compiler/optimizing/ssa_builder.cc b/compiler/optimizing/ssa_builder.cc index 7a252af2ad..b66e655d2b 100644 --- a/compiler/optimizing/ssa_builder.cc +++ b/compiler/optimizing/ssa_builder.cc @@ -417,6 +417,7 @@ HFloatConstant* SsaBuilder::GetFloatEquivalent(HIntConstant* constant) { ArenaAllocator* allocator = graph->GetArena(); result = new (allocator) HFloatConstant(bit_cast<float, int32_t>(constant->GetValue())); constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); + graph->CacheFloatConstant(result); } else { // If there is already a constant with the expected type, we know it is // the floating point equivalent of this constant. @@ -439,6 +440,7 @@ HDoubleConstant* SsaBuilder::GetDoubleEquivalent(HLongConstant* constant) { ArenaAllocator* allocator = graph->GetArena(); result = new (allocator) HDoubleConstant(bit_cast<double, int64_t>(constant->GetValue())); constant->GetBlock()->InsertInstructionBefore(result, constant->GetNext()); + graph->CacheDoubleConstant(result); } else { // If there is already a constant with the expected type, we know it is // the floating point equivalent of this constant. diff --git a/compiler/optimizing/ssa_liveness_analysis.cc b/compiler/optimizing/ssa_liveness_analysis.cc index ea0e7c3712..b674f746b6 100644 --- a/compiler/optimizing/ssa_liveness_analysis.cc +++ b/compiler/optimizing/ssa_liveness_analysis.cc @@ -341,7 +341,7 @@ int LiveInterval::FindFirstRegisterHint(size_t* free_until) const { size_t end = GetEnd(); while (use != nullptr && use->GetPosition() <= end) { size_t use_position = use->GetPosition(); - if (use_position >= start && !use->GetIsEnvironment()) { + if (use_position >= start) { HInstruction* user = use->GetUser(); size_t input_index = use->GetInputIndex(); if (user->IsPhi()) { diff --git a/compiler/optimizing/ssa_liveness_analysis.h b/compiler/optimizing/ssa_liveness_analysis.h index 97254edb5e..b95276afd7 100644 --- a/compiler/optimizing/ssa_liveness_analysis.h +++ b/compiler/optimizing/ssa_liveness_analysis.h @@ -219,6 +219,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { void AddTempUse(HInstruction* instruction, size_t temp_index) { DCHECK(IsTemp()); DCHECK(first_use_ == nullptr) << "A temporary can only have one user"; + DCHECK(first_env_use_ == nullptr) << "A temporary cannot have environment user"; size_t position = instruction->GetLifetimePosition(); first_use_ = new (allocator_) UsePosition( instruction, temp_index, /* is_environment */ false, position, first_use_); @@ -265,8 +266,13 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { return; } - first_use_ = new (allocator_) UsePosition( - instruction, input_index, is_environment, position, first_use_); + if (is_environment) { + first_env_use_ = new (allocator_) UsePosition( + instruction, input_index, is_environment, position, first_env_use_); + } else { + first_use_ = new (allocator_) UsePosition( + instruction, input_index, is_environment, position, first_use_); + } if (is_environment && !keep_alive) { // If this environment use does not keep the instruction live, it does not @@ -477,7 +483,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { size_t end = GetEnd(); while (use != nullptr && use->GetPosition() <= end) { size_t use_position = use->GetPosition(); - if (use_position > position && !use->GetIsEnvironment()) { + if (use_position > position) { Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex()); if (location.IsUnallocated() && (location.GetPolicy() == Location::kRequiresRegister @@ -508,12 +514,10 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { UsePosition* use = first_use_; size_t end = GetEnd(); while (use != nullptr && use->GetPosition() <= end) { - if (!use->GetIsEnvironment()) { - Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex()); - size_t use_position = use->GetPosition(); - if (use_position > position && location.IsValid()) { - return use_position; - } + Location location = use->GetUser()->GetLocations()->InAt(use->GetInputIndex()); + size_t use_position = use->GetPosition(); + if (use_position > position && location.IsValid()) { + return use_position; } use = use->GetNext(); } @@ -524,6 +528,10 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { return first_use_; } + UsePosition* GetFirstEnvironmentUse() const { + return first_env_use_; + } + Primitive::Type GetType() const { return type_; } @@ -577,6 +585,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { new_interval->parent_ = parent_; new_interval->first_use_ = first_use_; + new_interval->first_env_use_ = first_env_use_; LiveRange* current = first_range_; LiveRange* previous = nullptr; // Iterate over the ranges, and either find a range that covers this position, or @@ -655,10 +664,18 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { stream << " "; } while ((use = use->GetNext()) != nullptr); } + stream << "}, {"; + use = first_env_use_; + if (use != nullptr) { + do { + use->Dump(stream); + stream << " "; + } while ((use = use->GetNext()) != nullptr); + } stream << "}"; stream << " is_fixed: " << is_fixed_ << ", is_split: " << IsSplit(); - stream << " is_high: " << IsHighInterval(); stream << " is_low: " << IsLowInterval(); + stream << " is_high: " << IsHighInterval(); } LiveInterval* GetNextSibling() const { return next_sibling_; } @@ -754,6 +771,10 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { if (first_use_ != nullptr) { high_or_low_interval_->first_use_ = first_use_->Dup(allocator_); } + + if (first_env_use_ != nullptr) { + high_or_low_interval_->first_env_use_ = first_env_use_->Dup(allocator_); + } } // Returns whether an interval, when it is non-split, is using @@ -851,6 +872,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { first_safepoint_(nullptr), last_safepoint_(nullptr), first_use_(nullptr), + first_env_use_(nullptr), type_(type), next_sibling_(nullptr), parent_(this), @@ -905,6 +927,7 @@ class LiveInterval : public ArenaObject<kArenaAllocMisc> { // Uses of this interval. Note that this linked list is shared amongst siblings. UsePosition* first_use_; + UsePosition* first_env_use_; // The instruction type this interval corresponds to. const Primitive::Type type_; diff --git a/compiler/optimizing/stack_map_stream.cc b/compiler/optimizing/stack_map_stream.cc index fcc86d5163..8344fc3237 100644 --- a/compiler/optimizing/stack_map_stream.cc +++ b/compiler/optimizing/stack_map_stream.cc @@ -18,29 +18,29 @@ namespace art { -void StackMapStream::AddStackMapEntry(uint32_t dex_pc, - uint32_t native_pc_offset, - uint32_t register_mask, - BitVector* sp_mask, - uint32_t num_dex_registers, - uint8_t inlining_depth) { - StackMapEntry entry; - entry.dex_pc = dex_pc; - entry.native_pc_offset = native_pc_offset; - entry.register_mask = register_mask; - entry.sp_mask = sp_mask; - entry.num_dex_registers = num_dex_registers; - entry.inlining_depth = inlining_depth; - entry.dex_register_locations_start_index = dex_register_locations_.Size(); - entry.inline_infos_start_index = inline_infos_.Size(); - entry.dex_register_map_hash = 0; +void StackMapStream::BeginStackMapEntry(uint32_t dex_pc, + uint32_t native_pc_offset, + uint32_t register_mask, + BitVector* sp_mask, + uint32_t num_dex_registers, + uint8_t inlining_depth) { + DCHECK_EQ(0u, current_entry_.dex_pc) << "EndStackMapEntry not called after BeginStackMapEntry"; + current_entry_.dex_pc = dex_pc; + current_entry_.native_pc_offset = native_pc_offset; + current_entry_.register_mask = register_mask; + current_entry_.sp_mask = sp_mask; + current_entry_.num_dex_registers = num_dex_registers; + current_entry_.inlining_depth = inlining_depth; + current_entry_.dex_register_locations_start_index = dex_register_locations_.Size(); + current_entry_.inline_infos_start_index = inline_infos_.Size(); + current_entry_.dex_register_map_hash = 0; + current_entry_.same_dex_register_map_as_ = kNoSameDexMapFound; if (num_dex_registers != 0) { - entry.live_dex_registers_mask = + current_entry_.live_dex_registers_mask = new (allocator_) ArenaBitVector(allocator_, num_dex_registers, true); } else { - entry.live_dex_registers_mask = nullptr; + current_entry_.live_dex_registers_mask = nullptr; } - stack_maps_.Add(entry); if (sp_mask != nullptr) { stack_mask_max_ = std::max(stack_mask_max_, sp_mask->GetHighestBitSet()); @@ -54,11 +54,16 @@ void StackMapStream::AddStackMapEntry(uint32_t dex_pc, register_mask_max_ = std::max(register_mask_max_, register_mask); } +void StackMapStream::EndStackMapEntry() { + current_entry_.same_dex_register_map_as_ = FindEntryWithTheSameDexMap(); + stack_maps_.Add(current_entry_); + current_entry_ = StackMapEntry(); +} + void StackMapStream::AddDexRegisterEntry(uint16_t dex_register, - DexRegisterLocation::Kind kind, - int32_t value) { - StackMapEntry entry = stack_maps_.Get(stack_maps_.Size() - 1); - DCHECK_LT(dex_register, entry.num_dex_registers); + DexRegisterLocation::Kind kind, + int32_t value) { + DCHECK_LT(dex_register, current_entry_.num_dex_registers); if (kind != DexRegisterLocation::Kind::kNone) { // Ensure we only use non-compressed location kind at this stage. @@ -82,12 +87,11 @@ void StackMapStream::AddDexRegisterEntry(uint16_t dex_register, location_catalog_entries_indices_.Insert(std::make_pair(location, index)); } - entry.live_dex_registers_mask->SetBit(dex_register); - entry.dex_register_map_hash += - (1 << (dex_register % (sizeof(entry.dex_register_map_hash) * kBitsPerByte))); - entry.dex_register_map_hash += static_cast<uint32_t>(value); - entry.dex_register_map_hash += static_cast<uint32_t>(kind); - stack_maps_.Put(stack_maps_.Size() - 1, entry); + current_entry_.live_dex_registers_mask->SetBit(dex_register); + current_entry_.dex_register_map_hash += + (1 << (dex_register % (sizeof(current_entry_.dex_register_map_hash) * kBitsPerByte))); + current_entry_.dex_register_map_hash += static_cast<uint32_t>(value); + current_entry_.dex_register_map_hash += static_cast<uint32_t>(kind); } } @@ -97,29 +101,33 @@ void StackMapStream::AddInlineInfoEntry(uint32_t method_index) { inline_infos_.Add(entry); } -size_t StackMapStream::ComputeNeededSize() { - size_t size = CodeInfo::kFixedSize - + ComputeDexRegisterLocationCatalogSize() - + ComputeStackMapsSize() - + ComputeDexRegisterMapsSize() - + ComputeInlineInfoSize(); - // Note: use RoundUp to word-size here if you want CodeInfo objects to be word aligned. - return size; -} +size_t StackMapStream::PrepareForFillIn() { + int stack_mask_number_of_bits = stack_mask_max_ + 1; // Need room for max element too. + stack_mask_size_ = RoundUp(stack_mask_number_of_bits, kBitsPerByte) / kBitsPerByte; + inline_info_size_ = ComputeInlineInfoSize(); + dex_register_maps_size_ = ComputeDexRegisterMapsSize(); + stack_maps_size_ = stack_maps_.Size() + * StackMap::ComputeStackMapSize(stack_mask_size_, + inline_info_size_, + dex_register_maps_size_, + dex_pc_max_, + native_pc_offset_max_, + register_mask_max_); + dex_register_location_catalog_size_ = ComputeDexRegisterLocationCatalogSize(); -size_t StackMapStream::ComputeStackMaskSize() const { - int number_of_bits = stack_mask_max_ + 1; // Need room for max element too. - return RoundUp(number_of_bits, kBitsPerByte) / kBitsPerByte; -} - -size_t StackMapStream::ComputeStackMapsSize() { - return stack_maps_.Size() * StackMap::ComputeStackMapSize( - ComputeStackMaskSize(), - ComputeInlineInfoSize(), - ComputeDexRegisterMapsSize(), - dex_pc_max_, - native_pc_offset_max_, - register_mask_max_); + // Note: use RoundUp to word-size here if you want CodeInfo objects to be word aligned. + needed_size_ = CodeInfo::kFixedSize + + dex_register_location_catalog_size_ + + stack_maps_size_ + + dex_register_maps_size_ + + inline_info_size_; + + dex_register_location_catalog_start_ = CodeInfo::kFixedSize; + stack_maps_start_ = dex_register_location_catalog_start_ + dex_register_location_catalog_size_; + dex_register_maps_start_ = stack_maps_start_ + stack_maps_size_; + inline_infos_start_ = dex_register_maps_start_ + dex_register_maps_size_; + + return needed_size_; } size_t StackMapStream::ComputeDexRegisterLocationCatalogSize() const { @@ -157,12 +165,13 @@ size_t StackMapStream::ComputeDexRegisterMapSize(const StackMapEntry& entry) con return size; } -size_t StackMapStream::ComputeDexRegisterMapsSize() { +size_t StackMapStream::ComputeDexRegisterMapsSize() const { size_t size = 0; for (size_t i = 0; i < stack_maps_.Size(); ++i) { - if (FindEntryWithTheSameDexMap(i) == kNoSameDexMapFound) { + StackMapEntry entry = stack_maps_.Get(i); + if (entry.same_dex_register_map_as_ == kNoSameDexMapFound) { // Entries with the same dex map will have the same offset. - size += ComputeDexRegisterMapSize(stack_maps_.Get(i)); + size += ComputeDexRegisterMapSize(entry); } } return size; @@ -174,55 +183,33 @@ size_t StackMapStream::ComputeInlineInfoSize() const { + (number_of_stack_maps_with_inline_info_ * InlineInfo::kFixedSize); } -size_t StackMapStream::ComputeDexRegisterLocationCatalogStart() const { - return CodeInfo::kFixedSize; -} - -size_t StackMapStream::ComputeStackMapsStart() const { - return ComputeDexRegisterLocationCatalogStart() + ComputeDexRegisterLocationCatalogSize(); -} - -size_t StackMapStream::ComputeDexRegisterMapsStart() { - return ComputeStackMapsStart() + ComputeStackMapsSize(); -} - -size_t StackMapStream::ComputeInlineInfoStart() { - return ComputeDexRegisterMapsStart() + ComputeDexRegisterMapsSize(); -} - void StackMapStream::FillIn(MemoryRegion region) { + DCHECK_EQ(0u, current_entry_.dex_pc) << "EndStackMapEntry not called after BeginStackMapEntry"; + DCHECK_NE(0u, needed_size_) << "PrepareForFillIn not called before FillIn"; + CodeInfo code_info(region); - DCHECK_EQ(region.size(), ComputeNeededSize()); + DCHECK_EQ(region.size(), needed_size_); code_info.SetOverallSize(region.size()); - size_t stack_mask_size = ComputeStackMaskSize(); - - size_t dex_register_map_size = ComputeDexRegisterMapsSize(); - size_t inline_info_size = ComputeInlineInfoSize(); - MemoryRegion dex_register_locations_region = region.Subregion( - ComputeDexRegisterMapsStart(), - dex_register_map_size); + dex_register_maps_start_, dex_register_maps_size_); MemoryRegion inline_infos_region = region.Subregion( - ComputeInlineInfoStart(), - inline_info_size); + inline_infos_start_, inline_info_size_); - code_info.SetEncoding(inline_info_size, - dex_register_map_size, + code_info.SetEncoding(inline_info_size_, + dex_register_maps_size_, dex_pc_max_, native_pc_offset_max_, register_mask_max_); code_info.SetNumberOfStackMaps(stack_maps_.Size()); - code_info.SetStackMaskSize(stack_mask_size); - DCHECK_EQ(code_info.GetStackMapsSize(), ComputeStackMapsSize()); + code_info.SetStackMaskSize(stack_mask_size_); + DCHECK_EQ(code_info.GetStackMapsSize(), stack_maps_size_); // Set the Dex register location catalog. - code_info.SetNumberOfDexRegisterLocationCatalogEntries( - location_catalog_entries_.Size()); + code_info.SetNumberOfDexRegisterLocationCatalogEntries(location_catalog_entries_.Size()); MemoryRegion dex_register_location_catalog_region = region.Subregion( - ComputeDexRegisterLocationCatalogStart(), - ComputeDexRegisterLocationCatalogSize()); + dex_register_location_catalog_start_, dex_register_location_catalog_size_); DexRegisterLocationCatalog dex_register_location_catalog(dex_register_location_catalog_region); // Offset in `dex_register_location_catalog` where to store the next // register location. @@ -253,11 +240,11 @@ void StackMapStream::FillIn(MemoryRegion region) { stack_map.SetDexRegisterMapOffset(code_info, StackMap::kNoDexRegisterMap); } else { // Search for an entry with the same dex map. - size_t entry_with_same_map = FindEntryWithTheSameDexMap(i); - if (entry_with_same_map != kNoSameDexMapFound) { + if (entry.same_dex_register_map_as_ != kNoSameDexMapFound) { // If we have a hit reuse the offset. stack_map.SetDexRegisterMapOffset(code_info, - code_info.GetStackMapAt(entry_with_same_map).GetDexRegisterMapOffset(code_info)); + code_info.GetStackMapAt(entry.same_dex_register_map_as_) + .GetDexRegisterMapOffset(code_info)); } else { // New dex registers maps should be added to the stack map. MemoryRegion register_region = @@ -309,49 +296,34 @@ void StackMapStream::FillIn(MemoryRegion region) { inline_info.SetMethodReferenceIndexAtDepth(j, inline_entry.method_index); } } else { - if (inline_info_size != 0) { + if (inline_info_size_ != 0) { stack_map.SetInlineDescriptorOffset(code_info, StackMap::kNoInlineInfo); } } } } -size_t StackMapStream::FindEntryWithTheSameDexMap(size_t entry_index) { - StackMapEntry entry = stack_maps_.Get(entry_index); - auto entries_it = dex_map_hash_to_stack_map_indices_.find(entry.dex_register_map_hash); +size_t StackMapStream::FindEntryWithTheSameDexMap() { + size_t current_entry_index = stack_maps_.Size(); + auto entries_it = dex_map_hash_to_stack_map_indices_.find(current_entry_.dex_register_map_hash); if (entries_it == dex_map_hash_to_stack_map_indices_.end()) { // We don't have a perfect hash functions so we need a list to collect all stack maps // which might have the same dex register map. GrowableArray<uint32_t> stack_map_indices(allocator_, 1); - stack_map_indices.Add(entry_index); - dex_map_hash_to_stack_map_indices_.Put(entry.dex_register_map_hash, stack_map_indices); + stack_map_indices.Add(current_entry_index); + dex_map_hash_to_stack_map_indices_.Put(current_entry_.dex_register_map_hash, stack_map_indices); return kNoSameDexMapFound; } - // TODO: We don't need to add ourselves to the map if we can guarantee that - // FindEntryWithTheSameDexMap is called just once per stack map entry. - // A good way to do this is to cache the offset in the stack map entry. This - // is easier to do if we add markers when the stack map constructions begins - // and when it ends. - - // We might have collisions, so we need to check whether or not we should - // add the entry to the map. `needs_to_be_added` keeps track of this. - bool needs_to_be_added = true; - size_t result = kNoSameDexMapFound; + // We might have collisions, so we need to check whether or not we really have a match. for (size_t i = 0; i < entries_it->second.Size(); i++) { size_t test_entry_index = entries_it->second.Get(i); - if (test_entry_index == entry_index) { - needs_to_be_added = false; - } else if (HaveTheSameDexMaps(stack_maps_.Get(test_entry_index), entry)) { - result = test_entry_index; - needs_to_be_added = false; - break; + if (HaveTheSameDexMaps(stack_maps_.Get(test_entry_index), current_entry_)) { + return test_entry_index; } } - if (needs_to_be_added) { - entries_it->second.Add(entry_index); - } - return result; + entries_it->second.Add(current_entry_index); + return kNoSameDexMapFound; } bool StackMapStream::HaveTheSameDexMaps(const StackMapEntry& a, const StackMapEntry& b) const { diff --git a/compiler/optimizing/stack_map_stream.h b/compiler/optimizing/stack_map_stream.h index 990e682216..0c626be89f 100644 --- a/compiler/optimizing/stack_map_stream.h +++ b/compiler/optimizing/stack_map_stream.h @@ -70,7 +70,18 @@ class StackMapStream : public ValueObject { native_pc_offset_max_(0), register_mask_max_(0), number_of_stack_maps_with_inline_info_(0), - dex_map_hash_to_stack_map_indices_(std::less<uint32_t>(), allocator->Adapter()) {} + dex_map_hash_to_stack_map_indices_(std::less<uint32_t>(), allocator->Adapter()), + current_entry_(), + stack_mask_size_(0), + inline_info_size_(0), + dex_register_maps_size_(0), + stack_maps_size_(0), + dex_register_location_catalog_size_(0), + dex_register_location_catalog_start_(0), + stack_maps_start_(0), + dex_register_maps_start_(0), + inline_infos_start_(0), + needed_size_(0) {} // See runtime/stack_map.h to know what these fields contain. struct StackMapEntry { @@ -84,18 +95,20 @@ class StackMapStream : public ValueObject { size_t inline_infos_start_index; BitVector* live_dex_registers_mask; uint32_t dex_register_map_hash; + size_t same_dex_register_map_as_; }; struct InlineInfoEntry { uint32_t method_index; }; - void AddStackMapEntry(uint32_t dex_pc, - uint32_t native_pc_offset, - uint32_t register_mask, - BitVector* sp_mask, - uint32_t num_dex_registers, - uint8_t inlining_depth); + void BeginStackMapEntry(uint32_t dex_pc, + uint32_t native_pc_offset, + uint32_t register_mask, + BitVector* sp_mask, + uint32_t num_dex_registers, + uint8_t inlining_depth); + void EndStackMapEntry(); void AddDexRegisterEntry(uint16_t dex_register, DexRegisterLocation::Kind kind, @@ -103,25 +116,20 @@ class StackMapStream : public ValueObject { void AddInlineInfoEntry(uint32_t method_index); - size_t ComputeNeededSize(); - size_t ComputeStackMaskSize() const; - size_t ComputeStackMapsSize(); + // Prepares the stream to fill in a memory region. Must be called before FillIn. + // Returns the size (in bytes) needed to store this stream. + size_t PrepareForFillIn(); + void FillIn(MemoryRegion region); + + private: size_t ComputeDexRegisterLocationCatalogSize() const; size_t ComputeDexRegisterMapSize(const StackMapEntry& entry) const; - size_t ComputeDexRegisterMapsSize(); + size_t ComputeDexRegisterMapsSize() const; size_t ComputeInlineInfoSize() const; - size_t ComputeDexRegisterLocationCatalogStart() const; - size_t ComputeStackMapsStart() const; - size_t ComputeDexRegisterMapsStart(); - size_t ComputeInlineInfoStart(); - - void FillIn(MemoryRegion region); - - private: - // Returns the index of an entry with the same dex register map + // Returns the index of an entry with the same dex register map as the current_entry, // or kNoSameDexMapFound if no such entry exists. - size_t FindEntryWithTheSameDexMap(size_t entry_index); + size_t FindEntryWithTheSameDexMap(); bool HaveTheSameDexMaps(const StackMapEntry& a, const StackMapEntry& b) const; ArenaAllocator* allocator_; @@ -146,6 +154,18 @@ class StackMapStream : public ValueObject { ArenaSafeMap<uint32_t, GrowableArray<uint32_t>> dex_map_hash_to_stack_map_indices_; + StackMapEntry current_entry_; + size_t stack_mask_size_; + size_t inline_info_size_; + size_t dex_register_maps_size_; + size_t stack_maps_size_; + size_t dex_register_location_catalog_size_; + size_t dex_register_location_catalog_start_; + size_t stack_maps_start_; + size_t dex_register_maps_start_; + size_t inline_infos_start_; + size_t needed_size_; + static constexpr uint32_t kNoSameDexMapFound = -1; DISALLOW_COPY_AND_ASSIGN(StackMapStream); diff --git a/compiler/optimizing/stack_map_test.cc b/compiler/optimizing/stack_map_test.cc index 8d160bc81e..3291a77021 100644 --- a/compiler/optimizing/stack_map_test.cc +++ b/compiler/optimizing/stack_map_test.cc @@ -40,11 +40,12 @@ TEST(StackMapTest, Test1) { ArenaBitVector sp_mask(&arena, 0, false); size_t number_of_dex_registers = 2; - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); stream.AddDexRegisterEntry(0, Kind::kInStack, 0); // Short location. stream.AddDexRegisterEntry(1, Kind::kConstant, -2); // Short location. + stream.EndStackMapEntry(); - size_t size = stream.ComputeNeededSize(); + size_t size = stream.PrepareForFillIn(); void* memory = arena.Alloc(size, kArenaAllocMisc); MemoryRegion region(memory, size); stream.FillIn(region); @@ -123,20 +124,22 @@ TEST(StackMapTest, Test2) { sp_mask1.SetBit(2); sp_mask1.SetBit(4); size_t number_of_dex_registers = 2; - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask1, number_of_dex_registers, 2); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask1, number_of_dex_registers, 2); stream.AddDexRegisterEntry(0, Kind::kInStack, 0); // Short location. stream.AddDexRegisterEntry(1, Kind::kConstant, -2); // Large location. stream.AddInlineInfoEntry(42); stream.AddInlineInfoEntry(82); + stream.EndStackMapEntry(); ArenaBitVector sp_mask2(&arena, 0, true); sp_mask2.SetBit(3); sp_mask1.SetBit(8); - stream.AddStackMapEntry(1, 128, 0xFF, &sp_mask2, number_of_dex_registers, 0); + stream.BeginStackMapEntry(1, 128, 0xFF, &sp_mask2, number_of_dex_registers, 0); stream.AddDexRegisterEntry(0, Kind::kInRegister, 18); // Short location. stream.AddDexRegisterEntry(1, Kind::kInFpuRegister, 3); // Short location. + stream.EndStackMapEntry(); - size_t size = stream.ComputeNeededSize(); + size_t size = stream.PrepareForFillIn(); void* memory = arena.Alloc(size, kArenaAllocMisc); MemoryRegion region(memory, size); stream.FillIn(region); @@ -273,11 +276,12 @@ TEST(StackMapTest, TestNonLiveDexRegisters) { ArenaBitVector sp_mask(&arena, 0, false); uint32_t number_of_dex_registers = 2; - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); stream.AddDexRegisterEntry(0, Kind::kNone, 0); // No location. stream.AddDexRegisterEntry(1, Kind::kConstant, -2); // Large location. + stream.EndStackMapEntry(); - size_t size = stream.ComputeNeededSize(); + size_t size = stream.PrepareForFillIn(); void* memory = arena.Alloc(size, kArenaAllocMisc); MemoryRegion region(memory, size); stream.FillIn(region); @@ -353,7 +357,7 @@ TEST(StackMapTest, DexRegisterMapOffsetOverflow) { ArenaBitVector sp_mask(&arena, 0, false); uint32_t number_of_dex_registers = 1024; // Create the first stack map (and its Dex register map). - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); uint32_t number_of_dex_live_registers_in_dex_register_map_0 = number_of_dex_registers - 8; for (uint32_t i = 0; i < number_of_dex_live_registers_in_dex_register_map_0; ++i) { // Use two different Dex register locations to populate this map, @@ -362,13 +366,15 @@ TEST(StackMapTest, DexRegisterMapOffsetOverflow) { // art::DexRegisterMap::SingleEntrySizeInBits). stream.AddDexRegisterEntry(i, Kind::kConstant, i % 2); // Short location. } + stream.EndStackMapEntry(); // Create the second stack map (and its Dex register map). - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); for (uint32_t i = 0; i < number_of_dex_registers; ++i) { stream.AddDexRegisterEntry(i, Kind::kConstant, 0); // Short location. } + stream.EndStackMapEntry(); - size_t size = stream.ComputeNeededSize(); + size_t size = stream.PrepareForFillIn(); void* memory = arena.Alloc(size, kArenaAllocMisc); MemoryRegion region(memory, size); stream.FillIn(region); @@ -413,19 +419,22 @@ TEST(StackMapTest, TestShareDexRegisterMap) { ArenaBitVector sp_mask(&arena, 0, false); uint32_t number_of_dex_registers = 2; // First stack map. - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); stream.AddDexRegisterEntry(0, Kind::kInRegister, 0); // Short location. stream.AddDexRegisterEntry(1, Kind::kConstant, -2); // Large location. + stream.EndStackMapEntry(); // Second stack map, which should share the same dex register map. - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); stream.AddDexRegisterEntry(0, Kind::kInRegister, 0); // Short location. stream.AddDexRegisterEntry(1, Kind::kConstant, -2); // Large location. + stream.EndStackMapEntry(); // Third stack map (doesn't share the dex register map). - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); stream.AddDexRegisterEntry(0, Kind::kInRegister, 2); // Short location. stream.AddDexRegisterEntry(1, Kind::kConstant, -2); // Large location. + stream.EndStackMapEntry(); - size_t size = stream.ComputeNeededSize(); + size_t size = stream.PrepareForFillIn(); void* memory = arena.Alloc(size, kArenaAllocMisc); MemoryRegion region(memory, size); stream.FillIn(region); @@ -462,9 +471,10 @@ TEST(StackMapTest, TestNoDexRegisterMap) { ArenaBitVector sp_mask(&arena, 0, false); uint32_t number_of_dex_registers = 0; - stream.AddStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.BeginStackMapEntry(0, 64, 0x3, &sp_mask, number_of_dex_registers, 0); + stream.EndStackMapEntry(); - size_t size = stream.ComputeNeededSize(); + size_t size = stream.PrepareForFillIn(); void* memory = arena.Alloc(size, kArenaAllocMisc); MemoryRegion region(memory, size); stream.FillIn(region); |