summaryrefslogtreecommitdiffstats
path: root/compiler
diff options
context:
space:
mode:
Diffstat (limited to 'compiler')
-rw-r--r--compiler/Android.mk3
-rw-r--r--compiler/optimizing/graph_visualizer.cc9
-rw-r--r--compiler/optimizing/graph_visualizer.h4
-rw-r--r--compiler/optimizing/licm.cc134
-rw-r--r--compiler/optimizing/licm.h42
-rw-r--r--compiler/optimizing/nodes.cc9
-rw-r--r--compiler/optimizing/nodes.h47
-rw-r--r--compiler/optimizing/optimization.h4
-rw-r--r--compiler/optimizing/optimizing_compiler.cc3
9 files changed, 245 insertions, 10 deletions
diff --git a/compiler/Android.mk b/compiler/Android.mk
index 83ab730ce9..04ebc6c6de 100644
--- a/compiler/Android.mk
+++ b/compiler/Android.mk
@@ -100,8 +100,9 @@ LIBART_COMPILER_SRC_FILES := \
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 ef461d9ac5..22a3d124f1 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 @@ class HGraphVisualizerPrinter : public HGraphVisitor {
}
}
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 b90d15e1ff..8d6fe04c2b 100644
--- a/compiler/optimizing/graph_visualizer.h
+++ b/compiler/optimizing/graph_visualizer.h
@@ -27,10 +27,6 @@ class CodeGenerator;
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 0000000000..10f24d8148
--- /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 0000000000..4812394a35
--- /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 fe9ce740da..5fd75f652d 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -707,7 +707,7 @@ std::ostream& operator<<(std::ostream& os, const HInstruction::InstructionKind&
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 @@ void HInstruction::InsertBefore(HInstruction* cursor) {
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 @@ void HInstruction::InsertBefore(HInstruction* cursor) {
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 @@ void HGraph::InlineInto(HGraph* outer_graph, HInvoke* invoke) {
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 3e4028ed7f..dfb03c31cc 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -899,8 +899,8 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
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 @@ class HLoadClass : public HExpression<0> {
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 @@ class HThrow : public HTemplateInstruction<1> {
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 @@ class HPostOrderIterator : public ValueObject {
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 e36ef198b6..9315d89a4a 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 705345b279..50d7924186 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 @@ static void RunOptimizations(HGraph* graph,
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 @@ static void RunOptimizations(HGraph* graph,
&fold2,
&side_effects,
&gvn,
+ &licm,
&bce,
&type_propagation,
&simplify2
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-19 09:10:49 +0000