diff options
Diffstat (limited to 'compiler/optimizing/nodes.cc')
| -rw-r--r-- | compiler/optimizing/nodes.cc | 625 |
1 files changed, 459 insertions, 166 deletions
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc index 4b9d4fc26b..47da9cc17c 100644 --- a/compiler/optimizing/nodes.cc +++ b/compiler/optimizing/nodes.cc @@ -16,7 +16,9 @@ #include "nodes.h" +#include "code_generator.h" #include "ssa_builder.h" +#include "base/bit_vector-inl.h" #include "utils/growable_array.h" #include "scoped_thread_state_change.h" @@ -37,8 +39,9 @@ static void RemoveAsUser(HInstruction* instruction) { instruction->RemoveAsUserOfInput(i); } - HEnvironment* environment = instruction->GetEnvironment(); - if (environment != nullptr) { + for (HEnvironment* environment = instruction->GetEnvironment(); + environment != nullptr; + environment = environment->GetParent()) { for (size_t i = 0, e = environment->Size(); i < e; ++i) { if (environment->GetInstructionAt(i) != nullptr) { environment->RemoveAsUserOfInput(i); @@ -191,24 +194,6 @@ void HGraph::SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor) { void HGraph::SimplifyLoop(HBasicBlock* header) { HLoopInformation* info = header->GetLoopInformation(); - // If there are more than one back edge, make them branch to the same block that - // will become the only back edge. This simplifies finding natural loops in the - // graph. - // Also, if the loop is a do/while (that is the back edge is an if), change the - // back edge to be a goto. This simplifies code generation of suspend cheks. - if (info->NumberOfBackEdges() > 1 || info->GetBackEdges().Get(0)->GetLastInstruction()->IsIf()) { - HBasicBlock* new_back_edge = new (arena_) HBasicBlock(this, header->GetDexPc()); - AddBlock(new_back_edge); - new_back_edge->AddInstruction(new (arena_) HGoto()); - for (size_t pred = 0, e = info->GetBackEdges().Size(); pred < e; ++pred) { - HBasicBlock* back_edge = info->GetBackEdges().Get(pred); - back_edge->ReplaceSuccessor(header, new_back_edge); - } - info->ClearBackEdges(); - info->AddBackEdge(new_back_edge); - new_back_edge->AddSuccessor(header); - } - // Make sure the loop has only one pre header. This simplifies SSA building by having // to just look at the pre header to know which locals are initialized at entry of the // loop. @@ -218,11 +203,9 @@ void HGraph::SimplifyLoop(HBasicBlock* header) { AddBlock(pre_header); pre_header->AddInstruction(new (arena_) HGoto()); - ArenaBitVector back_edges(arena_, GetBlocks().Size(), false); - HBasicBlock* back_edge = info->GetBackEdges().Get(0); for (size_t pred = 0; pred < header->GetPredecessors().Size(); ++pred) { HBasicBlock* predecessor = header->GetPredecessors().Get(pred); - if (predecessor != back_edge) { + if (!info->IsBackEdge(*predecessor)) { predecessor->ReplaceSuccessor(header, pre_header); pred--; } @@ -230,9 +213,17 @@ void HGraph::SimplifyLoop(HBasicBlock* header) { pre_header->AddSuccessor(header); } - // Make sure the second predecessor of a loop header is the back edge. - if (header->GetPredecessors().Get(1) != info->GetBackEdges().Get(0)) { - header->SwapPredecessors(); + // Make sure the first predecessor of a loop header is the incoming block. + if (info->IsBackEdge(*header->GetPredecessors().Get(0))) { + HBasicBlock* to_swap = header->GetPredecessors().Get(0); + for (size_t pred = 1, e = header->GetPredecessors().Size(); pred < e; ++pred) { + HBasicBlock* predecessor = header->GetPredecessors().Get(pred); + if (!info->IsBackEdge(*predecessor)) { + header->predecessors_.Put(pred, to_swap); + header->predecessors_.Put(0, predecessor); + break; + } + } } // Place the suspend check at the beginning of the header, so that live registers @@ -303,25 +294,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 +315,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()); } @@ -364,26 +348,60 @@ void HLoopInformation::PopulateRecursive(HBasicBlock* block) { } bool HLoopInformation::Populate() { - DCHECK_EQ(GetBackEdges().Size(), 1u); - HBasicBlock* back_edge = GetBackEdges().Get(0); - DCHECK(back_edge->GetDominator() != nullptr); - if (!header_->Dominates(back_edge)) { - // This loop is not natural. Do not bother going further. - return false; - } + DCHECK_EQ(blocks_.NumSetBits(), 0u) << "Loop information has already been populated"; + for (size_t i = 0, e = GetBackEdges().Size(); i < e; ++i) { + HBasicBlock* back_edge = GetBackEdges().Get(i); + DCHECK(back_edge->GetDominator() != nullptr); + if (!header_->Dominates(back_edge)) { + // This loop is not natural. Do not bother going further. + return false; + } - // Populate this loop: starting with the back edge, recursively add predecessors - // that are not already part of that loop. Set the header as part of the loop - // to end the recursion. - // This is a recursive implementation of the algorithm described in - // "Advanced Compiler Design & Implementation" (Muchnick) p192. - blocks_.SetBit(header_->GetBlockId()); - PopulateRecursive(back_edge); + // Populate this loop: starting with the back edge, recursively add predecessors + // that are not already part of that loop. Set the header as part of the loop + // to end the recursion. + // This is a recursive implementation of the algorithm described in + // "Advanced Compiler Design & Implementation" (Muchnick) p192. + blocks_.SetBit(header_->GetBlockId()); + PopulateRecursive(back_edge); + } return true; } +void HLoopInformation::Update() { + HGraph* graph = header_->GetGraph(); + for (uint32_t id : blocks_.Indexes()) { + HBasicBlock* block = graph->GetBlocks().Get(id); + // Reset loop information of non-header blocks inside the loop, except + // members of inner nested loops because those should already have been + // updated by their own LoopInformation. + if (block->GetLoopInformation() == this && block != header_) { + block->SetLoopInformation(nullptr); + } + } + blocks_.ClearAllBits(); + + if (back_edges_.IsEmpty()) { + // The loop has been dismantled, delete its suspend check and remove info + // from the header. + DCHECK(HasSuspendCheck()); + header_->RemoveInstruction(suspend_check_); + header_->SetLoopInformation(nullptr); + header_ = nullptr; + suspend_check_ = nullptr; + } else { + if (kIsDebugBuild) { + for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { + DCHECK(header_->Dominates(back_edges_.Get(i))); + } + } + // This loop still has reachable back edges. Repopulate the list of blocks. + bool populate_successful = Populate(); + DCHECK(populate_successful); + } +} + HBasicBlock* HLoopInformation::GetPreHeader() const { - DCHECK_EQ(header_->GetPredecessors().Size(), 2u); return header_->GetDominator(); } @@ -395,6 +413,14 @@ bool HLoopInformation::IsIn(const HLoopInformation& other) const { return other.blocks_.IsBitSet(header_->GetBlockId()); } +size_t HLoopInformation::GetLifetimeEnd() const { + size_t last_position = 0; + for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) { + last_position = std::max(back_edges_.Get(i)->GetLifetimeEnd(), last_position); + } + return last_position; +} + bool HBasicBlock::Dominates(HBasicBlock* other) const { // Walk up the dominator tree from `other`, to find out if `this` // is an ancestor. @@ -416,26 +442,6 @@ static void UpdateInputsUsers(HInstruction* instruction) { DCHECK(!instruction->HasEnvironment()); } -void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { - DCHECK(!cursor->IsPhi()); - DCHECK(!instruction->IsPhi()); - DCHECK_EQ(instruction->GetId(), -1); - DCHECK_NE(cursor->GetId(), -1); - DCHECK_EQ(cursor->GetBlock(), this); - DCHECK(!instruction->IsControlFlow()); - instruction->next_ = cursor; - instruction->previous_ = cursor->previous_; - cursor->previous_ = instruction; - if (GetFirstInstruction() == cursor) { - instructions_.first_instruction_ = instruction; - } else { - instruction->previous_->next_ = instruction; - } - instruction->SetBlock(this); - instruction->SetId(GetGraph()->GetNextInstructionId()); - UpdateInputsUsers(instruction); -} - void HBasicBlock::ReplaceAndRemoveInstructionWith(HInstruction* initial, HInstruction* replacement) { DCHECK(initial->GetBlock() == this); @@ -463,23 +469,41 @@ void HBasicBlock::AddPhi(HPhi* phi) { Add(&phis_, this, phi); } +void HBasicBlock::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { + DCHECK(!cursor->IsPhi()); + DCHECK(!instruction->IsPhi()); + DCHECK_EQ(instruction->GetId(), -1); + DCHECK_NE(cursor->GetId(), -1); + DCHECK_EQ(cursor->GetBlock(), this); + DCHECK(!instruction->IsControlFlow()); + instruction->SetBlock(this); + instruction->SetId(GetGraph()->GetNextInstructionId()); + UpdateInputsUsers(instruction); + instructions_.InsertInstructionBefore(instruction, cursor); +} + +void HBasicBlock::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { + DCHECK(!cursor->IsPhi()); + DCHECK(!instruction->IsPhi()); + DCHECK_EQ(instruction->GetId(), -1); + DCHECK_NE(cursor->GetId(), -1); + DCHECK_EQ(cursor->GetBlock(), this); + DCHECK(!instruction->IsControlFlow()); + DCHECK(!cursor->IsControlFlow()); + instruction->SetBlock(this); + instruction->SetId(GetGraph()->GetNextInstructionId()); + UpdateInputsUsers(instruction); + instructions_.InsertInstructionAfter(instruction, cursor); +} + void HBasicBlock::InsertPhiAfter(HPhi* phi, HPhi* cursor) { DCHECK_EQ(phi->GetId(), -1); DCHECK_NE(cursor->GetId(), -1); DCHECK_EQ(cursor->GetBlock(), this); - if (cursor->next_ == nullptr) { - cursor->next_ = phi; - phi->previous_ = cursor; - DCHECK(phi->next_ == nullptr); - } else { - phi->next_ = cursor->next_; - phi->previous_ = cursor; - cursor->next_ = phi; - phi->next_->previous_ = phi; - } phi->SetBlock(this); phi->SetId(GetGraph()->GetNextInstructionId()); UpdateInputsUsers(phi); + phis_.InsertInstructionAfter(phi, cursor); } static void Remove(HInstructionList* instruction_list, @@ -497,6 +521,7 @@ static void Remove(HInstructionList* instruction_list, } void HBasicBlock::RemoveInstruction(HInstruction* instruction, bool ensure_safety) { + DCHECK(!instruction->IsPhi()); Remove(&instructions_, this, instruction, ensure_safety); } @@ -504,6 +529,24 @@ 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(const GrowableArray<HInstruction*>& locals) { + for (size_t i = 0; i < locals.Size(); i++) { + HInstruction* instruction = locals.Get(i); + SetRawEnvAt(i, instruction); + if (instruction != nullptr) { + instruction->AddEnvUseAt(this, i); + } + } +} + void HEnvironment::CopyFrom(HEnvironment* env) { for (size_t i = 0; i < env->Size(); i++) { HInstruction* instruction = env->GetInstructionAt(i); @@ -514,6 +557,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()); @@ -546,6 +611,34 @@ void HInstructionList::AddInstruction(HInstruction* instruction) { } } +void HInstructionList::InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor) { + DCHECK(Contains(cursor)); + if (cursor == first_instruction_) { + cursor->previous_ = instruction; + instruction->next_ = cursor; + first_instruction_ = instruction; + } else { + instruction->previous_ = cursor->previous_; + instruction->next_ = cursor; + cursor->previous_ = instruction; + instruction->previous_->next_ = instruction; + } +} + +void HInstructionList::InsertInstructionAfter(HInstruction* instruction, HInstruction* cursor) { + DCHECK(Contains(cursor)); + if (cursor == last_instruction_) { + cursor->next_ = instruction; + instruction->previous_ = cursor; + last_instruction_ = instruction; + } else { + instruction->next_ = cursor->next_; + instruction->previous_ = cursor; + cursor->next_ = instruction; + instruction->next_->previous_ = instruction; + } +} + void HInstructionList::RemoveInstruction(HInstruction* instruction) { if (instruction->previous_ != nullptr) { instruction->previous_->next_ = instruction->next_; @@ -660,6 +753,14 @@ void HPhi::AddInput(HInstruction* input) { input->AddUseAt(this, inputs_.Size() - 1); } +void HPhi::RemoveInputAt(size_t index) { + RemoveAsUserOfInput(index); + inputs_.DeleteAt(index); + for (size_t i = index, e = InputCount(); i < e; ++i) { + InputRecordAt(i).GetUseNode()->SetIndex(i); + } +} + #define DEFINE_ACCEPT(name, super) \ void H##name::Accept(HGraphVisitor* visitor) { \ visitor->Visit##name(this); \ @@ -694,6 +795,84 @@ void HGraphVisitor::VisitBasicBlock(HBasicBlock* block) { } } +HConstant* HTypeConversion::TryStaticEvaluation() const { + HGraph* graph = GetBlock()->GetGraph(); + if (GetInput()->IsIntConstant()) { + int32_t value = GetInput()->AsIntConstant()->GetValue(); + switch (GetResultType()) { + case Primitive::kPrimLong: + return graph->GetLongConstant(static_cast<int64_t>(value)); + case Primitive::kPrimFloat: + return graph->GetFloatConstant(static_cast<float>(value)); + case Primitive::kPrimDouble: + return graph->GetDoubleConstant(static_cast<double>(value)); + default: + return nullptr; + } + } else if (GetInput()->IsLongConstant()) { + int64_t value = GetInput()->AsLongConstant()->GetValue(); + switch (GetResultType()) { + case Primitive::kPrimInt: + return graph->GetIntConstant(static_cast<int32_t>(value)); + case Primitive::kPrimFloat: + return graph->GetFloatConstant(static_cast<float>(value)); + case Primitive::kPrimDouble: + return graph->GetDoubleConstant(static_cast<double>(value)); + default: + return nullptr; + } + } else if (GetInput()->IsFloatConstant()) { + float value = GetInput()->AsFloatConstant()->GetValue(); + switch (GetResultType()) { + case Primitive::kPrimInt: + if (std::isnan(value)) + return graph->GetIntConstant(0); + if (value >= kPrimIntMax) + return graph->GetIntConstant(kPrimIntMax); + if (value <= kPrimIntMin) + return graph->GetIntConstant(kPrimIntMin); + return graph->GetIntConstant(static_cast<int32_t>(value)); + case Primitive::kPrimLong: + if (std::isnan(value)) + return graph->GetLongConstant(0); + if (value >= kPrimLongMax) + return graph->GetLongConstant(kPrimLongMax); + if (value <= kPrimLongMin) + return graph->GetLongConstant(kPrimLongMin); + return graph->GetLongConstant(static_cast<int64_t>(value)); + case Primitive::kPrimDouble: + return graph->GetDoubleConstant(static_cast<double>(value)); + default: + return nullptr; + } + } else if (GetInput()->IsDoubleConstant()) { + double value = GetInput()->AsDoubleConstant()->GetValue(); + switch (GetResultType()) { + case Primitive::kPrimInt: + if (std::isnan(value)) + return graph->GetIntConstant(0); + if (value >= kPrimIntMax) + return graph->GetIntConstant(kPrimIntMax); + if (value <= kPrimLongMin) + return graph->GetIntConstant(kPrimIntMin); + return graph->GetIntConstant(static_cast<int32_t>(value)); + case Primitive::kPrimLong: + if (std::isnan(value)) + return graph->GetLongConstant(0); + if (value >= kPrimLongMax) + return graph->GetLongConstant(kPrimLongMax); + if (value <= kPrimLongMin) + return graph->GetLongConstant(kPrimLongMin); + return graph->GetLongConstant(static_cast<int64_t>(value)); + case Primitive::kPrimFloat: + return graph->GetFloatConstant(static_cast<float>(value)); + default: + return nullptr; + } + } + return nullptr; +} + HConstant* HUnaryOperation::TryStaticEvaluation() const { if (GetInput()->IsIntConstant()) { int32_t value = Evaluate(GetInput()->AsIntConstant()->GetValue()); @@ -702,7 +881,7 @@ HConstant* HUnaryOperation::TryStaticEvaluation() const { // TODO: Implement static evaluation of long unary operations. // // Do not exit with a fatal condition here. Instead, simply - // return `nullptr' to notify the caller that this instruction + // return `null' to notify the caller that this instruction // cannot (yet) be statically evaluated. return nullptr; } @@ -738,7 +917,7 @@ HConstant* HBinaryOperation::GetConstantRight() const { } // If `GetConstantRight()` returns one of the input, this returns the other -// one. Otherwise it returns nullptr. +// one. Otherwise it returns null. HInstruction* HBinaryOperation::GetLeastConstantLeft() const { HInstruction* most_constant_right = GetConstantRight(); if (most_constant_right == nullptr) { @@ -855,6 +1034,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; @@ -886,40 +1074,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)) { + // If this was the last back edge of the loop, we deliberately leave 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->ReplaceBackEdge(other, 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); @@ -961,6 +1276,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. @@ -993,7 +1326,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) @@ -1082,11 +1415,9 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) { loop_it.Current()->Add(to); } if (info->IsBackEdge(*at)) { - // Only `at` can become a back edge, as the inlined blocks - // are predecessors of `at`. - DCHECK_EQ(1u, info->NumberOfBackEdges()); - info->ClearBackEdges(); - info->AddBackEdge(to); + // Only `to` can become a back edge, as the inlined blocks + // are predecessors of `to`. + info->ReplaceBackEdge(at, to); } } } @@ -1101,7 +1432,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()) { @@ -1110,10 +1441,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()); @@ -1125,53 +1465,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 << "[" |