Inline methods with multiple blocks.
Change-Id: I3431af60e97fae230e0b6e98bcf0acc0ee9abf8c
diff --git a/compiler/optimizing/graph_checker.cc b/compiler/optimizing/graph_checker.cc
index 35c5269..4ebb136 100644
--- a/compiler/optimizing/graph_checker.cc
+++ b/compiler/optimizing/graph_checker.cc
@@ -153,8 +153,9 @@
? use->GetBlock()->GetPhis()
: use->GetBlock()->GetInstructions();
if (!list.Contains(use)) {
- AddError(StringPrintf("User %d of instruction %d is not defined "
+ AddError(StringPrintf("User %s:%d of instruction %d is not defined "
"in a basic block of the control-flow graph.",
+ use->DebugName(),
use->GetId(),
instruction->GetId()));
}
diff --git a/compiler/optimizing/inliner.cc b/compiler/optimizing/inliner.cc
index 513be7d..41e5164 100644
--- a/compiler/optimizing/inliner.cc
+++ b/compiler/optimizing/inliner.cc
@@ -35,7 +35,6 @@
namespace art {
static constexpr int kMaxInlineCodeUnits = 100;
-static constexpr int kMaxInlineNumberOfBlocks = 3;
static constexpr int kDepthLimit = 5;
void HInliner::Run() {
@@ -140,13 +139,6 @@
return false;
}
- if (callee_graph->GetBlocks().Size() > kMaxInlineNumberOfBlocks) {
- VLOG(compiler) << "Method " << PrettyMethod(method_index, outer_dex_file)
- << " has too many blocks to be inlined: "
- << callee_graph->GetBlocks().Size();
- return false;
- }
-
if (!RegisterAllocator::CanAllocateRegistersFor(*callee_graph,
compiler_driver_->GetInstructionSet())) {
VLOG(compiler) << "Method " << PrettyMethod(method_index, outer_dex_file)
@@ -200,6 +192,10 @@
!instr_it.Done();
instr_it.Advance()) {
HInstruction* current = instr_it.Current();
+ if (current->IsSuspendCheck()) {
+ continue;
+ }
+
if (current->CanThrow()) {
VLOG(compiler) << "Method " << PrettyMethod(method_index, outer_dex_file)
<< " could not be inlined because " << current->DebugName()
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 5fd75f6..f1868cb 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -292,6 +292,10 @@
return true;
}
+void HLoopInformation::Add(HBasicBlock* block) {
+ blocks_.SetBit(block->GetBlockId());
+}
+
void HLoopInformation::PopulateRecursive(HBasicBlock* block) {
if (blocks_.IsBitSet(block->GetBlockId())) {
return;
@@ -730,10 +734,121 @@
}
}
-void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
- // We currently only support graphs with one entry block, one body block, and one exit block.
- DCHECK_EQ(GetBlocks().Size(), 3u);
+HBasicBlock* HBasicBlock::SplitAfter(HInstruction* cursor) {
+ DCHECK(!cursor->IsControlFlow());
+ DCHECK_NE(instructions_.last_instruction_, cursor);
+ DCHECK_EQ(cursor->GetBlock(), this);
+ HBasicBlock* new_block = new (GetGraph()->GetArena()) HBasicBlock(GetGraph(), GetDexPc());
+ new_block->instructions_.first_instruction_ = cursor->GetNext();
+ new_block->instructions_.last_instruction_ = instructions_.last_instruction_;
+ cursor->next_->previous_ = nullptr;
+ cursor->next_ = nullptr;
+ instructions_.last_instruction_ = cursor;
+
+ new_block->instructions_.SetBlockOfInstructions(new_block);
+ for (size_t i = 0, e = GetSuccessors().Size(); i < e; ++i) {
+ HBasicBlock* successor = GetSuccessors().Get(i);
+ new_block->successors_.Add(successor);
+ successor->predecessors_.Put(successor->GetPredecessorIndexOf(this), new_block);
+ }
+ successors_.Reset();
+
+ for (size_t i = 0, e = GetDominatedBlocks().Size(); i < e; ++i) {
+ HBasicBlock* dominated = GetDominatedBlocks().Get(i);
+ dominated->dominator_ = new_block;
+ new_block->dominated_blocks_.Add(dominated);
+ }
+ dominated_blocks_.Reset();
+ return new_block;
+}
+
+void HInstructionList::SetBlockOfInstructions(HBasicBlock* block) const {
+ for (HInstruction* current = first_instruction_;
+ current != nullptr;
+ current = current->GetNext()) {
+ current->SetBlock(block);
+ }
+}
+
+void HInstructionList::AddAfter(HInstruction* cursor, const HInstructionList& instruction_list) {
+ DCHECK(Contains(cursor));
+ if (!instruction_list.IsEmpty()) {
+ if (cursor == last_instruction_) {
+ last_instruction_ = instruction_list.last_instruction_;
+ } else {
+ cursor->next_->previous_ = instruction_list.last_instruction_;
+ }
+ instruction_list.last_instruction_->next_ = cursor->next_;
+ cursor->next_ = instruction_list.first_instruction_;
+ instruction_list.first_instruction_->previous_ = cursor;
+ }
+}
+
+void HInstructionList::Add(const HInstructionList& instruction_list) {
+ DCHECK(!IsEmpty());
+ AddAfter(last_instruction_, instruction_list);
+}
+
+void HBasicBlock::MergeWith(HBasicBlock* other) {
+ DCHECK(successors_.IsEmpty()) << "Unimplemented block merge scenario";
+ DCHECK(dominated_blocks_.IsEmpty()) << "Unimplemented block merge scenario";
+ DCHECK(other->GetDominator()->IsEntryBlock() && other->GetGraph() != graph_)
+ << "Unimplemented block merge scenario";
+ DCHECK(other->GetPhis().IsEmpty());
+
+ successors_.Reset();
+ dominated_blocks_.Reset();
+ instructions_.Add(other->GetInstructions());
+ other->GetInstructions().SetBlockOfInstructions(this);
+
+ while (!other->GetSuccessors().IsEmpty()) {
+ HBasicBlock* successor = other->GetSuccessors().Get(0);
+ successor->ReplacePredecessor(other, this);
+ }
+
+ 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;
+ other->graph_ = nullptr;
+}
+
+void HBasicBlock::ReplaceWith(HBasicBlock* other) {
+ while (!GetPredecessors().IsEmpty()) {
+ HBasicBlock* predecessor = GetPredecessors().Get(0);
+ predecessor->ReplaceSuccessor(this, other);
+ }
+ while (!GetSuccessors().IsEmpty()) {
+ HBasicBlock* successor = GetSuccessors().Get(0);
+ successor->ReplacePredecessor(this, other);
+ }
+ for (size_t i = 0; i < dominated_blocks_.Size(); ++i) {
+ other->AddDominatedBlock(dominated_blocks_.Get(i));
+ }
+ GetDominator()->ReplaceDominatedBlock(this, other);
+ other->SetDominator(GetDominator());
+ dominator_ = nullptr;
+ graph_ = nullptr;
+}
+
+// Create space in `blocks` for adding `number_of_new_blocks` entries
+// starting at location `at`. Blocks after `at` are moved accordingly.
+static void MakeRoomFor(GrowableArray<HBasicBlock*>* blocks,
+ size_t number_of_new_blocks,
+ size_t at) {
+ size_t old_size = blocks->Size();
+ size_t new_size = old_size + number_of_new_blocks;
+ blocks->SetSize(new_size);
+ for (size_t i = old_size - 1, j = new_size - 1; i > at; --i, --j) {
+ blocks->Put(j, blocks->Get(i));
+ }
+}
+
+void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
// Walk over the entry block and:
// - Move constants from the entry block to the outer_graph's entry block,
// - Replace HParameterValue instructions with their real value.
@@ -751,41 +866,122 @@
}
}
- // Insert the body's instructions except the last, just after the `invoke`
- // instruction.
- HBasicBlock* body = GetBlocks().Get(1);
- DCHECK(!body->IsExitBlock());
- HInstruction* last = body->GetLastInstruction();
- HInstruction* first = body->GetFirstInstruction();
+ if (GetBlocks().Size() == 3) {
+ // Simple case: Put the first block's instruction into `invoke`'s block.
+ HBasicBlock* body = GetBlocks().Get(1);
+ DCHECK(!body->IsExitBlock());
+ HInstruction* last = body->GetLastInstruction();
- if (first != last) {
- HInstruction* antelast = last->GetPrevious();
+ invoke->GetBlock()->instructions_.AddAfter(invoke, body->GetInstructions());
+ body->GetInstructions().SetBlockOfInstructions(invoke->GetBlock());
- // Update the instruction list of the body to only contain the last
- // instruction.
- last->previous_ = nullptr;
- body->instructions_.first_instruction_ = last;
- body->instructions_.last_instruction_ = last;
-
- // Update the instruction list of the `invoke`'s block to now contain the
- // body's instructions.
- antelast->next_ = invoke->GetNext();
- antelast->next_->previous_ = antelast;
- first->previous_ = invoke;
- invoke->next_ = first;
-
- // Update the block pointer of all instructions.
- for (HInstruction* current = antelast; current != invoke; current = current->GetPrevious()) {
- current->SetBlock(invoke->GetBlock());
+ // Replace the invoke with the return value of the inlined graph.
+ if (last->IsReturn()) {
+ invoke->ReplaceWith(last->InputAt(0));
+ } else {
+ DCHECK(last->IsReturnVoid());
}
- }
- // Replace the invoke with the return value of the inlined graph.
- if (last->IsReturn()) {
- invoke->ReplaceWith(last->InputAt(0));
- body->RemoveInstruction(last);
+ invoke->GetBlock()->RemoveInstruction(last);
} else {
- DCHECK(last->IsReturnVoid());
+ // Need to inline multiple blocks. We split `invoke`'s block
+ // into two blocks, merge the first block of the inlined graph into
+ // the first half, and replace the exit block if the inlined graph
+ // with the second half.
+ ArenaAllocator* allocator = outer_graph->GetArena();
+ HBasicBlock* at = invoke->GetBlock();
+ HBasicBlock* to = at->SplitAfter(invoke);
+
+ HBasicBlock* first = entry_block_->GetSuccessors().Get(0);
+ DCHECK(!first->IsInLoop());
+ at->MergeWith(first);
+ exit_block_->ReplaceWith(to);
+
+ // Update all predecessors of the exit block (now the `to` block)
+ // to not `HReturn` but `HGoto` instead. Also collect the return
+ // values if any, and potentially make it a phi if there are multiple
+ // predecessors.
+ HInstruction* return_value = nullptr;
+ for (size_t i = 0, e = to->GetPredecessors().Size(); i < e; ++i) {
+ HBasicBlock* predecessor = to->GetPredecessors().Get(i);
+ HInstruction* last = predecessor->GetLastInstruction();
+ if (!last->IsReturnVoid()) {
+ if (return_value != nullptr) {
+ if (!return_value->IsPhi()) {
+ HPhi* phi = new (allocator) HPhi(
+ allocator, kNoRegNumber, to->GetPredecessors().Size(), invoke->GetType());
+ return_value->AsPhi()->AddInput(return_value);
+ to->AddPhi(phi);
+ return_value = phi;
+ }
+ return_value->AsPhi()->AddInput(last->InputAt(0));
+ } else {
+ return_value = last->InputAt(0);
+ }
+ }
+ predecessor->AddInstruction(new (allocator) HGoto());
+ predecessor->RemoveInstruction(last);
+ }
+
+ if (return_value != nullptr) {
+ invoke->ReplaceWith(return_value);
+ }
+
+ // Update the meta information surrounding blocks:
+ // (1) the graph they are now in,
+ // (2) the reverse post order of that graph,
+ // (3) the potential loop information they are now in.
+
+ // We don't add the entry block, the exit block, and the first block, which
+ // has been merged with `at`.
+ static constexpr int kNumberOfSkippedBlocksInCallee = 3;
+
+ // We add the `to` block.
+ static constexpr int kNumberOfNewBlocksInCaller = 1;
+ size_t blocks_added = (reverse_post_order_.Size() - kNumberOfSkippedBlocksInCallee)
+ + kNumberOfNewBlocksInCaller;
+
+ // Find the location of `at` in the outer graph's reverse post order. The new
+ // blocks will be added after it.
+ size_t index_of_at = 0;
+ while (outer_graph->reverse_post_order_.Get(index_of_at) != at) {
+ index_of_at++;
+ }
+ MakeRoomFor(&outer_graph->reverse_post_order_, blocks_added, index_of_at);
+
+ // Do a reverse post order of the blocks in the callee and do (1), (2),
+ // and (3) to the blocks that apply.
+ HLoopInformation* info = at->GetLoopInformation();
+ for (HReversePostOrderIterator it(*this); !it.Done(); it.Advance()) {
+ HBasicBlock* current = it.Current();
+ if (current != exit_block_ && current != entry_block_ && current != first) {
+ DCHECK(!current->IsInLoop());
+ DCHECK(current->GetGraph() == this);
+ current->SetGraph(outer_graph);
+ outer_graph->AddBlock(current);
+ outer_graph->reverse_post_order_.Put(++index_of_at, current);
+ if (info != nullptr) {
+ info->Add(current);
+ current->SetLoopInformation(info);
+ }
+ }
+ }
+
+ // Do (1), (2), and (3) to `to`.
+ to->SetGraph(outer_graph);
+ outer_graph->AddBlock(to);
+ outer_graph->reverse_post_order_.Put(++index_of_at, to);
+ if (info != nullptr) {
+ info->Add(to);
+ to->SetLoopInformation(info);
+ 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);
+ }
+ }
}
// Finally remove the invoke from the caller.
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 6f7bc0c..30d869d 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -73,6 +73,15 @@
bool FoundBefore(const HInstruction* instruction1,
const HInstruction* instruction2) const;
+ bool IsEmpty() const { return first_instruction_ == nullptr; }
+ void Clear() { first_instruction_ = last_instruction_ = nullptr; }
+
+ // Update the block of all instructions to be `block`.
+ void SetBlockOfInstructions(HBasicBlock* block) const;
+
+ void AddAfter(HInstruction* cursor, const HInstructionList& instruction_list);
+ void Add(const HInstructionList& instruction_list);
+
private:
HInstruction* first_instruction_;
HInstruction* last_instruction_;
@@ -241,6 +250,10 @@
return header_;
}
+ void SetHeader(HBasicBlock* block) {
+ header_ = block;
+ }
+
HSuspendCheck* GetSuspendCheck() const { return suspend_check_; }
void SetSuspendCheck(HSuspendCheck* check) { suspend_check_ = check; }
bool HasSuspendCheck() const { return suspend_check_ != nullptr; }
@@ -288,6 +301,8 @@
const ArenaBitVector& GetBlocks() const { return blocks_; }
+ void Add(HBasicBlock* block);
+
private:
// Internal recursive implementation of `Populate`.
void PopulateRecursive(HBasicBlock* block);
@@ -351,6 +366,7 @@
}
HGraph* GetGraph() const { return graph_; }
+ void SetGraph(HGraph* graph) { graph_ = graph; }
int GetBlockId() const { return block_id_; }
void SetBlockId(int id) { block_id_ = id; }
@@ -358,6 +374,16 @@
HBasicBlock* GetDominator() const { return dominator_; }
void SetDominator(HBasicBlock* dominator) { dominator_ = dominator; }
void AddDominatedBlock(HBasicBlock* block) { dominated_blocks_.Add(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) {
+ dominated_blocks_.Put(i, new_block);
+ return;
+ }
+ }
+ LOG(FATAL) << "Unreachable";
+ UNREACHABLE();
+ }
int NumberOfBackEdges() const {
return loop_information_ == nullptr
@@ -384,10 +410,22 @@
successors_.Put(successor_index, new_block);
}
+ void ReplacePredecessor(HBasicBlock* existing, HBasicBlock* new_block) {
+ size_t predecessor_index = GetPredecessorIndexOf(existing);
+ DCHECK_NE(predecessor_index, static_cast<size_t>(-1));
+ existing->RemoveSuccessor(this);
+ new_block->successors_.Add(this);
+ predecessors_.Put(predecessor_index, new_block);
+ }
+
void RemovePredecessor(HBasicBlock* block) {
predecessors_.Delete(block);
}
+ void RemoveSuccessor(HBasicBlock* block) {
+ successors_.Delete(block);
+ }
+
void ClearAllPredecessors() {
predecessors_.Reset();
}
@@ -422,6 +460,26 @@
return -1;
}
+ // Split the block into two blocks just after `cursor`. Returns the newly
+ // created block. Note that this method just updates raw block information,
+ // like predecessors, successors, dominators, and instruction list. It 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).
+ HBasicBlock* SplitAfter(HInstruction* cursor);
+
+ // Merge `other` at the end of `this`. Successors and dominated blocks of
+ // `other` are changed to be successors and dominated blocks of `this`. 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 MergeWith(HBasicBlock* other);
+
+ // Replace `this` with `other`. Predecessors, successors, and dominated blocks
+ // of `this` are moved to `other`.
+ // Note that this method does not update the graph, reverse post order, loop
+ // information, nor make sure the blocks are consistent (for example ending
+ void ReplaceWith(HBasicBlock* other);
+
void AddInstruction(HInstruction* instruction);
void RemoveInstruction(HInstruction* instruction);
void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
@@ -446,8 +504,9 @@
return loop_information_;
}
- // Set the loop_information_ on this block. This method overrides the current
+ // Set the loop_information_ on this block. Overrides the current
// loop_information if it is an outer loop of the passed loop information.
+ // Note that this method is called while creating the loop information.
void SetInLoop(HLoopInformation* info) {
if (IsLoopHeader()) {
// Nothing to do. This just means `info` is an outer loop.
@@ -465,6 +524,11 @@
}
}
+ // Raw update of the loop information.
+ void SetLoopInformation(HLoopInformation* info) {
+ loop_information_ = info;
+ }
+
bool IsInLoop() const { return loop_information_ != nullptr; }
// Returns wheter this block dominates the blocked passed as parameter.
@@ -482,7 +546,7 @@
void SetIsCatchBlock() { is_catch_block_ = true; }
private:
- HGraph* const graph_;
+ HGraph* graph_;
GrowableArray<HBasicBlock*> predecessors_;
GrowableArray<HBasicBlock*> successors_;
HInstructionList instructions_;
@@ -2180,6 +2244,8 @@
DISALLOW_COPY_AND_ASSIGN(HTypeConversion);
};
+static constexpr uint32_t kNoRegNumber = -1;
+
class HPhi : public HInstruction {
public:
HPhi(ArenaAllocator* arena, uint32_t reg_number, size_t number_of_inputs, Primitive::Type type)
diff --git a/compiler/optimizing/side_effects_analysis.cc b/compiler/optimizing/side_effects_analysis.cc
index 96e1c8f..ea1ca5a 100644
--- a/compiler/optimizing/side_effects_analysis.cc
+++ b/compiler/optimizing/side_effects_analysis.cc
@@ -19,6 +19,11 @@
namespace art {
void SideEffectsAnalysis::Run() {
+ // Inlining might have created more blocks, so we need to increase the size
+ // if needed.
+ block_effects_.SetSize(graph_->GetBlocks().Size());
+ loop_effects_.SetSize(graph_->GetBlocks().Size());
+
if (kIsDebugBuild) {
for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
HBasicBlock* block = it.Current();
diff --git a/test/447-checker-inliner3/expected.txt b/test/447-checker-inliner3/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/447-checker-inliner3/expected.txt
diff --git a/test/447-checker-inliner3/info.txt b/test/447-checker-inliner3/info.txt
new file mode 100644
index 0000000..66a3270
--- /dev/null
+++ b/test/447-checker-inliner3/info.txt
@@ -0,0 +1 @@
+Tests inlining in the optimizing compiler.
diff --git a/test/447-checker-inliner3/src/Main.java b/test/447-checker-inliner3/src/Main.java
new file mode 100644
index 0000000..db4b236
--- /dev/null
+++ b/test/447-checker-inliner3/src/Main.java
@@ -0,0 +1,77 @@
+/*
+* Copyright (C) 2014 The Android Open Source Project
+*
+* Licensed under the Apache License, Version 2.0 (the "License");
+* you may not use this file except in compliance with the License.
+* You may obtain a copy of the License at
+*
+* http://www.apache.org/licenses/LICENSE-2.0
+*
+* Unless required by applicable law or agreed to in writing, software
+* distributed under the License is distributed on an "AS IS" BASIS,
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+* See the License for the specific language governing permissions and
+* limitations under the License.
+*/
+
+public class Main {
+
+ // CHECK-START: int Main.inlineIfThenElse() inliner (before)
+ // CHECK-DAG: [[Invoke:i\d+]] InvokeStaticOrDirect
+ // CHECK-DAG: Return [ [[Invoke]] ]
+
+ // CHECK-START: int Main.inlineIfThenElse() inliner (after)
+ // CHECK-NOT: InvokeStaticOrDirect
+
+ public static int inlineIfThenElse() {
+ return foo(true);
+ }
+
+ private static int foo(boolean value) {
+ if (value) {
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+
+ // CHECK-START: int Main.inlineInLoop() inliner (before)
+ // CHECK-DAG: InvokeStaticOrDirect
+
+ // CHECK-START: int Main.inlineInLoop() inliner (after)
+ // CHECK-NOT: InvokeStaticOrDirect
+
+ public static int inlineInLoop() {
+ int result = 0;
+ for (int i = 0; i < 32; ++i) {
+ result += foo(i % 2 == 0);
+ }
+ return result;
+ }
+
+ // CHECK-START: int Main.inlineInLoopHeader() inliner (before)
+ // CHECK-DAG: InvokeStaticOrDirect
+
+ // CHECK-START: int Main.inlineInLoopHeader() inliner (after)
+ // CHECK-NOT: InvokeStaticOrDirect
+
+ public static int inlineInLoopHeader() {
+ int result = 0;
+ for (int i = 0; i < foo(i % 2 == 0); ++i) {
+ result += 42;
+ }
+ return result;
+ }
+
+ public static void main(String[] args) {
+ if (inlineIfThenElse() != 1) {
+ throw new Error("Expected 1");
+ }
+ if (inlineInLoop() != 16) {
+ throw new Error("Expected 16");
+ }
+ if (inlineInLoopHeader() != 42) {
+ throw new Error("Expected 16");
+ }
+ }
+}