Implement LICM in optimizing compiler.
Change-Id: I9c8afb0a58ef45e568576015473cbfd5f011c242
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 83ab730..04ebc6c 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -100,8 +100,9 @@
optimizing/inliner.cc \
optimizing/instruction_simplifier.cc \
optimizing/intrinsics.cc \
- optimizing/intrinsics_x86_64.cc \
optimizing/intrinsics_arm64.cc \
+ optimizing/intrinsics_x86_64.cc \
+ optimizing/licm.cc \
optimizing/locations.cc \
optimizing/nodes.cc \
optimizing/optimization.cc \
diff --git a/compiler/optimizing/graph_visualizer.cc b/compiler/optimizing/graph_visualizer.cc
index ef461d9..22a3d12 100644
--- a/compiler/optimizing/graph_visualizer.cc
+++ b/compiler/optimizing/graph_visualizer.cc
@@ -18,6 +18,7 @@
#include "code_generator.h"
#include "nodes.h"
+#include "optimization.h"
#include "ssa_liveness_analysis.h"
namespace art {
@@ -216,6 +217,14 @@
}
}
output_ << " (liveness: " << instruction->GetLifetimePosition() << ")";
+ } else if (pass_name_ == kLoopInvariantCodeMotionPassName) {
+ output_ << " ( loop_header:";
+ HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
+ if (info == nullptr) {
+ output_ << "null )";
+ } else {
+ output_ << "B" << info->GetHeader()->GetBlockId() << " )";
+ }
}
}
diff --git a/compiler/optimizing/graph_visualizer.h b/compiler/optimizing/graph_visualizer.h
index b90d15e..8d6fe04 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -27,10 +27,6 @@
class DexCompilationUnit;
class HGraph;
-// TODO: Create an analysis/optimization abstraction.
-static const char* kLivenessPassName = "liveness";
-static const char* kRegisterAllocatorPassName = "register";
-
/**
* This class outputs the HGraph in the C1visualizer format.
* Note: Currently only works if the compiler is single threaded.
diff --git a/compiler/optimizing/licm.cc b/compiler/optimizing/licm.cc
new file mode 100644
index 0000000..10f24d8
--- /dev/null
+++ b/compiler/optimizing/licm.cc
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+#include "licm.h"
+#include "side_effects_analysis.h"
+
+namespace art {
+
+static bool IsPhiOf(HInstruction* instruction, HBasicBlock* block) {
+ return instruction->IsPhi() && instruction->GetBlock() == block;
+}
+
+/**
+ * Returns whether `instruction` has all its inputs and environment defined
+ * before the loop it is in.
+ */
+static bool InputsAreDefinedBeforeLoop(HInstruction* instruction) {
+ DCHECK(instruction->IsInLoop());
+ HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
+ for (HInputIterator it(instruction); !it.Done(); it.Advance()) {
+ HLoopInformation* input_loop = it.Current()->GetBlock()->GetLoopInformation();
+ // We only need to check whether the input is defined in the loop. If it is not
+ // it is defined before the loop.
+ if (input_loop != nullptr && input_loop->IsIn(*info)) {
+ return false;
+ }
+ }
+
+ if (instruction->HasEnvironment()) {
+ HEnvironment* environment = instruction->GetEnvironment();
+ for (size_t i = 0, e = environment->Size(); i < e; ++i) {
+ HInstruction* input = environment->GetInstructionAt(i);
+ if (input != nullptr) {
+ HLoopInformation* input_loop = input->GetBlock()->GetLoopInformation();
+ if (input_loop != nullptr && input_loop->IsIn(*info)) {
+ // We can move an instruction that takes a loop header phi in the environment:
+ // we will just replace that phi with its first input later in `UpdateLoopPhisIn`.
+ bool is_loop_header_phi = IsPhiOf(input, info->GetHeader());
+ if (!is_loop_header_phi) {
+ return false;
+ }
+ }
+ }
+ }
+ }
+ return true;
+}
+
+/**
+ * If `environment` has a loop header phi, we replace it with its first input.
+ */
+static void UpdateLoopPhisIn(HEnvironment* environment, HLoopInformation* info) {
+ for (size_t i = 0, e = environment->Size(); i < e; ++i) {
+ HInstruction* input = environment->GetInstructionAt(i);
+ if (input != nullptr && IsPhiOf(input, info->GetHeader())) {
+ HUseListNode<HEnvironment*>* env_use = environment->GetInstructionEnvUseAt(i);
+ input->RemoveEnvironmentUser(env_use);
+ HInstruction* incoming = input->InputAt(0);
+ environment->SetRawEnvAt(i, incoming);
+ incoming->AddEnvUseAt(environment, i);
+ }
+ }
+}
+
+void LICM::Run() {
+ DCHECK(side_effects_.HasRun());
+ // Only used during debug.
+ ArenaBitVector visited(graph_->GetArena(), graph_->GetBlocks().Size(), false);
+
+ // Post order visit to visit inner loops before outer loops.
+ for (HPostOrderIterator it(*graph_); !it.Done(); it.Advance()) {
+ HBasicBlock* block = it.Current();
+ if (!block->IsLoopHeader()) {
+ // Only visit the loop when we reach the header.
+ continue;
+ }
+
+ HLoopInformation* loop_info = block->GetLoopInformation();
+ SideEffects loop_effects = side_effects_.GetLoopEffects(block);
+ HBasicBlock* pre_header = loop_info->GetPreHeader();
+
+ for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
+ HBasicBlock* inner = it_loop.Current();
+ DCHECK(inner->IsInLoop());
+ if (inner->GetLoopInformation() != loop_info) {
+ // Thanks to post order visit, inner loops were already visited.
+ DCHECK(visited.IsBitSet(inner->GetBlockId()));
+ continue;
+ }
+ visited.SetBit(inner->GetBlockId());
+
+ // We can move an instruction that can throw only if it is the first
+ // throwing instruction in the loop. Note that the first potentially
+ // throwing instruction encountered that is not hoisted stops this
+ // optimization. Non-throwing instruction can still be hoisted.
+ bool found_first_non_hoisted_throwing_instruction_in_loop = !inner->IsLoopHeader();
+ for (HInstructionIterator inst_it(inner->GetInstructions());
+ !inst_it.Done();
+ inst_it.Advance()) {
+ HInstruction* instruction = inst_it.Current();
+ if (instruction->CanBeMoved()
+ && (!instruction->CanThrow() || !found_first_non_hoisted_throwing_instruction_in_loop)
+ && !instruction->GetSideEffects().DependsOn(loop_effects)
+ && InputsAreDefinedBeforeLoop(instruction)) {
+ // We need to update the environment if the instruction has a loop header
+ // phi in it.
+ if (instruction->NeedsEnvironment()) {
+ UpdateLoopPhisIn(instruction->GetEnvironment(), loop_info);
+ }
+ instruction->MoveBefore(pre_header->GetLastInstruction());
+ } else if (instruction->CanThrow()) {
+ // If `instruction` can throw, we cannot move further instructions
+ // that can throw as well.
+ found_first_non_hoisted_throwing_instruction_in_loop = true;
+ }
+ }
+ }
+ }
+}
+
+} // namespace art
diff --git a/compiler/optimizing/licm.h b/compiler/optimizing/licm.h
new file mode 100644
index 0000000..4812394
--- /dev/null
+++ b/compiler/optimizing/licm.h
@@ -0,0 +1,42 @@
+/*
+ * Copyright (C) 2015 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.
+ */
+
+#ifndef ART_COMPILER_OPTIMIZING_LICM_H_
+#define ART_COMPILER_OPTIMIZING_LICM_H_
+
+#include "nodes.h"
+#include "optimization.h"
+
+namespace art {
+
+class SideEffectsAnalysis;
+
+class LICM : public HOptimization {
+ public:
+ LICM(HGraph* graph, const SideEffectsAnalysis& side_effects)
+ : HOptimization(graph, true, kLoopInvariantCodeMotionPassName), side_effects_(side_effects) {}
+
+ void Run() OVERRIDE;
+
+ private:
+ const SideEffectsAnalysis& side_effects_;
+
+ DISALLOW_COPY_AND_ASSIGN(LICM);
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_OPTIMIZING_LICM_H_
diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index fe9ce74..5fd75f6 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -707,7 +707,7 @@
return os;
}
-void HInstruction::InsertBefore(HInstruction* cursor) {
+void HInstruction::MoveBefore(HInstruction* cursor) {
next_->previous_ = previous_;
if (previous_ != nullptr) {
previous_->next_ = next_;
@@ -715,6 +715,7 @@
if (block_->instructions_.first_instruction_ == this) {
block_->instructions_.first_instruction_ = next_;
}
+ DCHECK_NE(block_->instructions_.last_instruction_, this);
previous_ = cursor->previous_;
if (previous_ != nullptr) {
@@ -723,6 +724,10 @@
next_ = cursor;
cursor->previous_ = this;
block_ = cursor->block_;
+
+ if (block_->instructions_.first_instruction_ == cursor) {
+ block_->instructions_.first_instruction_ = this;
+ }
}
void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
@@ -737,7 +742,7 @@
for (HInstructionIterator it(entry_block_->GetInstructions()); !it.Done(); it.Advance()) {
HInstruction* current = it.Current();
if (current->IsConstant()) {
- current->InsertBefore(outer_graph->GetEntryBlock()->GetLastInstruction());
+ current->MoveBefore(outer_graph->GetEntryBlock()->GetLastInstruction());
} else if (current->IsParameterValue()) {
current->ReplaceWith(invoke->InputAt(parameter_index++));
} else {
diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 3e4028e..dfb03c3 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -899,8 +899,8 @@
void ReplaceWith(HInstruction* instruction);
void ReplaceInput(HInstruction* replacement, size_t index);
- // Insert `this` instruction in `cursor`'s graph, just before `cursor`.
- void InsertBefore(HInstruction* cursor);
+ // Move `this` instruction before `cursor`.
+ void MoveBefore(HInstruction* cursor);
#define INSTRUCTION_TYPE_CHECK(type, super) \
bool Is##type() const { return (As##type() != nullptr); } \
@@ -2562,6 +2562,12 @@
return MustGenerateClinitCheck() || !is_referrers_class_;
}
+ bool CanThrow() const OVERRIDE {
+ // May call runtime and and therefore can throw.
+ // TODO: finer grain decision.
+ return !is_referrers_class_;
+ }
+
DECLARE_INSTRUCTION(LoadClass);
private:
@@ -2726,12 +2732,14 @@
bool NeedsEnvironment() const OVERRIDE { return true; }
+ bool CanThrow() const OVERRIDE { return true; }
+
uint32_t GetDexPc() const { return dex_pc_; }
DECLARE_INSTRUCTION(Throw);
private:
- uint32_t dex_pc_;
+ const uint32_t dex_pc_;
DISALLOW_COPY_AND_ASSIGN(HThrow);
};
@@ -3063,6 +3071,39 @@
DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
};
+// Iterator over the blocks that art part of the loop. Includes blocks part
+// of an inner loop. The order in which the blocks are iterated is on their
+// block id.
+class HBlocksInLoopIterator : public ValueObject {
+ public:
+ explicit HBlocksInLoopIterator(const HLoopInformation& info)
+ : blocks_in_loop_(info.GetBlocks()),
+ blocks_(info.GetHeader()->GetGraph()->GetBlocks()),
+ index_(0) {
+ if (!blocks_in_loop_.IsBitSet(index_)) {
+ Advance();
+ }
+ }
+
+ bool Done() const { return index_ == blocks_.Size(); }
+ HBasicBlock* Current() const { return blocks_.Get(index_); }
+ void Advance() {
+ ++index_;
+ for (size_t e = blocks_.Size(); index_ < e; ++index_) {
+ if (blocks_in_loop_.IsBitSet(index_)) {
+ break;
+ }
+ }
+ }
+
+ private:
+ const BitVector& blocks_in_loop_;
+ const GrowableArray<HBasicBlock*>& blocks_;
+ size_t index_;
+
+ DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator);
+};
+
} // namespace art
#endif // ART_COMPILER_OPTIMIZING_NODES_H_
diff --git a/compiler/optimizing/optimization.h b/compiler/optimizing/optimization.h
index e36ef19..9315d89 100644
--- a/compiler/optimizing/optimization.h
+++ b/compiler/optimizing/optimization.h
@@ -21,6 +21,10 @@
namespace art {
+static const char* kLivenessPassName = "liveness";
+static const char* kRegisterAllocatorPassName = "register";
+static const char* kLoopInvariantCodeMotionPassName = "licm";
+
/**
* Abstraction to implement an optimization pass.
*/
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 705345b..50d7924 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -34,6 +34,7 @@
#include "inliner.h"
#include "instruction_simplifier.h"
#include "intrinsics.h"
+#include "licm.h"
#include "jni/quick/jni_compiler.h"
#include "mirror/art_method-inl.h"
#include "nodes.h"
@@ -225,6 +226,7 @@
HConstantFolding fold2(graph);
SideEffectsAnalysis side_effects(graph);
GVNOptimization gvn(graph, side_effects);
+ LICM licm(graph, side_effects);
BoundsCheckElimination bce(graph);
ReferenceTypePropagation type_propagation(graph);
InstructionSimplifier simplify2(graph, "instruction_simplifier_after_types");
@@ -242,6 +244,7 @@
&fold2,
&side_effects,
&gvn,
+ &licm,
&bce,
&type_propagation,
&simplify2
diff --git a/test/445-checker-licm/expected.txt b/test/445-checker-licm/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/445-checker-licm/expected.txt
diff --git a/test/445-checker-licm/info.txt b/test/445-checker-licm/info.txt
new file mode 100644
index 0000000..e09d958
--- /dev/null
+++ b/test/445-checker-licm/info.txt
@@ -0,0 +1 @@
+Checker test for testing loop invariant code motion.
diff --git a/test/445-checker-licm/src/Main.java b/test/445-checker-licm/src/Main.java
new file mode 100644
index 0000000..91ac2ed
--- /dev/null
+++ b/test/445-checker-licm/src/Main.java
@@ -0,0 +1,123 @@
+/*
+* Copyright (C) 2015 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.div() licm (before)
+ // CHECK-DAG: Div ( loop_header:{{B\d+}} )
+
+ // CHECK-START: int Main.div() licm (after)
+ // CHECK-NOT: Div ( loop_header:{{B\d+}} )
+
+ // CHECK-START: int Main.div() licm (after)
+ // CHECK-DAG: Div ( loop_header:null )
+
+ public static int div() {
+ int result = 0;
+ for (int i = 0; i < 10; ++i) {
+ result += staticField / 42;
+ }
+ return result;
+ }
+
+ // CHECK-START: int Main.innerDiv() licm (before)
+ // CHECK-DAG: Div ( loop_header:{{B\d+}} )
+
+ // CHECK-START: int Main.innerDiv() licm (after)
+ // CHECK-NOT: Div ( loop_header:{{B\d+}} )
+
+ // CHECK-START: int Main.innerDiv() licm (after)
+ // CHECK-DAG: Div ( loop_header:null )
+
+ public static int innerDiv() {
+ int result = 0;
+ for (int i = 0; i < 10; ++i) {
+ for (int j = 0; j < 10; ++j) {
+ result += staticField / 42;
+ }
+ }
+ return result;
+ }
+
+ // CHECK-START: int Main.innerDiv2() licm (before)
+ // CHECK-DAG: Mul ( loop_header:{{B4}} )
+
+ // CHECK-START: int Main.innerDiv2() licm (after)
+ // CHECK-DAG: Mul ( loop_header:{{B2}} )
+
+ public static int innerDiv2() {
+ int result = 0;
+ for (int i = 0; i < 10; ++i) {
+ for (int j = 0; j < 10; ++j) {
+ // The operation has been hoisted out of the inner loop.
+ // Note that we depend on the compiler's block numbering to
+ // check if it has been moved.
+ result += staticField * i;
+ }
+ }
+ return result;
+ }
+
+ // CHECK-START: int Main.innerDiv3(int, int) licm (before)
+ // CHECK-DAG: Div ( loop_header:{{B\d+}} )
+
+ // CHECK-START: int Main.innerDiv3(int, int) licm (after)
+ // CHECK-DAG: Div ( loop_header:{{B\d+}} )
+
+ public static int innerDiv3(int a, int b) {
+ int result = 0;
+ while (b < 5) {
+ // a might be null, so we can't hoist the operation.
+ result += staticField / a;
+ b++;
+ }
+ return result;
+ }
+
+ // CHECK-START: int Main.arrayLength(int[]) licm (before)
+ // CHECK-DAG: [[NullCheck:l\d+]] NullCheck ( loop_header:{{B\d+}} )
+ // CHECK-DAG: ArrayLength [ [[NullCheck]] ] ( loop_header:{{B\d+}} )
+
+ // CHECK-START: int Main.arrayLength(int[]) licm (after)
+ // CHECK-NOT: NullCheck ( loop_header:{{B\d+}} )
+ // CHECK-NOT: ArrayLength ( loop_header:{{B\d+}} )
+
+ // CHECK-START: int Main.arrayLength(int[]) licm (after)
+ // CHECK-DAG: [[NullCheck:l\d+]] NullCheck ( loop_header:null )
+ // CHECK-DAG: ArrayLength [ [[NullCheck]] ] ( loop_header:null )
+
+ public static int arrayLength(int[] array) {
+ int result = 0;
+ for (int i = 0; i < array.length; ++i) {
+ result += array[i];
+ }
+ return result;
+ }
+
+ public static int staticField = 42;
+
+ public static void assertEquals(int expected, int actual) {
+ if (expected != actual) {
+ throw new Error("Expected " + expected + ", got " + actual);
+ }
+ }
+
+ public static void main(String[] args) {
+ assertEquals(10, div());
+ assertEquals(100, innerDiv());
+ assertEquals(12, arrayLength(new int[] { 4, 8 }));
+ }
+}
