blob: c60b66b6d7b1f284f240ce04ac6afd8b1df5e7e2 [file] [log] [blame]
/*
* Copyright (C) 2016 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 "android-base/logging.h"
#include "base/macros.h"
#include "code_generator.h"
#include "driver/compiler_options.h"
#include "loop_optimization.h"
#include "optimizing/data_type.h"
#include "optimizing/nodes.h"
#include "optimizing_unit_test.h"
namespace art HIDDEN {
// Base class for loop optimization tests.
class LoopOptimizationTestBase : public OptimizingUnitTest {
protected:
void SetUp() override {
OptimizingUnitTest::SetUp();
BuildGraph();
iva_ = new (GetAllocator()) HInductionVarAnalysis(graph_);
if (compiler_options_ == nullptr) {
compiler_options_ = CommonCompilerTest::CreateCompilerOptions(kRuntimeISA, "default");
DCHECK(compiler_options_ != nullptr);
}
codegen_ = CodeGenerator::Create(graph_, *compiler_options_);
DCHECK(codegen_.get() != nullptr);
loop_opt_ = new (GetAllocator()) HLoopOptimization(
graph_, *codegen_.get(), iva_, /* stats= */ nullptr);
}
void TearDown() override {
codegen_.reset();
compiler_options_.reset();
graph_ = nullptr;
ResetPoolAndAllocator();
OptimizingUnitTest::TearDown();
}
virtual void BuildGraph() = 0;
// Run loop optimization and optionally check the graph.
void PerformAnalysis(bool run_checker) {
graph_->BuildDominatorTree();
// Check the graph is valid before loop optimization.
std::ostringstream oss;
if (run_checker) {
ASSERT_TRUE(CheckGraph(oss)) << oss.str();
}
iva_->Run();
loop_opt_->Run();
// Check the graph is valid after loop optimization.
if (run_checker) {
ASSERT_TRUE(CheckGraph(oss)) << oss.str();
}
}
// General building fields.
std::unique_ptr<CompilerOptions> compiler_options_;
std::unique_ptr<CodeGenerator> codegen_;
HInductionVarAnalysis* iva_;
HLoopOptimization* loop_opt_;
HBasicBlock* return_block_;
HInstruction* parameter_;
};
/**
* Fixture class for the loop optimization tests. These unit tests mostly focus
* on constructing the loop hierarchy. Checker tests are also used to test
* specific optimizations.
*/
class LoopOptimizationTest : public LoopOptimizationTestBase {
protected:
virtual ~LoopOptimizationTest() {}
/** Constructs bare minimum graph. */
void BuildGraph() override {
return_block_ = InitEntryMainExitGraph();
graph_->SetNumberOfVRegs(1);
parameter_ = MakeParam(DataType::Type::kInt32);
}
/** Adds a loop nest at given position before successor. */
HBasicBlock* AddLoop(HBasicBlock* position, HBasicBlock* successor) {
HBasicBlock* header = new (GetAllocator()) HBasicBlock(graph_);
HBasicBlock* body = new (GetAllocator()) HBasicBlock(graph_);
graph_->AddBlock(header);
graph_->AddBlock(body);
// Control flow.
position->ReplaceSuccessor(successor, header);
header->AddSuccessor(body);
header->AddSuccessor(successor);
MakeIf(header, parameter_);
body->AddSuccessor(header);
MakeGoto(body);
return header;
}
/** Constructs string representation of computed loop hierarchy. */
std::string LoopStructure() {
return LoopStructureRecurse(loop_opt_->top_loop_);
}
// Helper method
std::string LoopStructureRecurse(HLoopOptimization::LoopNode* node) {
std::string s;
for ( ; node != nullptr; node = node->next) {
s.append("[");
s.append(LoopStructureRecurse(node->inner));
s.append("]");
}
return s;
}
};
#ifdef ART_ENABLE_CODEGEN_arm64
// Unit tests for predicated vectorization.
class PredicatedSimdLoopOptimizationTest : public LoopOptimizationTestBase {
protected:
void SetUp() override {
// Predicated SIMD is only supported by SVE on Arm64.
compiler_options_ = CommonCompilerTest::CreateCompilerOptions(InstructionSet::kArm64,
"default",
"sve");
LoopOptimizationTestBase::SetUp();
}
virtual ~PredicatedSimdLoopOptimizationTest() {}
// Constructs a graph with a diamond loop which should be vectorizable with predicated
// vectorization. This graph includes a basic loop induction (consisting of Phi, Add, If and
// SuspendCheck instructions) to control the loop as well as an if comparison (consisting of
// Parameter, GreaterThanOrEqual and If instructions) to control the diamond loop.
//
// entry
// |
// preheader
// |
// return <------------ header <----------------+
// | | |
// exit diamond_top |
// / \ |
// diamond_true diamond_false |
// \ / |
// back_edge |
// | |
// +---------------------+
void BuildGraph() override {
return_block_ = InitEntryMainExitGraphWithReturnVoid();
HBasicBlock* back_edge;
std::tie(std::ignore, header_, back_edge) = CreateWhileLoop(return_block_);
std::tie(diamond_top_, diamond_true_, std::ignore) = CreateDiamondPattern(back_edge);
parameter_ = MakeParam(DataType::Type::kInt32);
std::tie(phi_, std::ignore) = MakeLinearLoopVar(header_, back_edge, 0, 1);
MakeSuspendCheck(header_);
HInstruction* trip = MakeCondition(header_,
kCondGE,
phi_,
graph_->GetIntConstant(kArm64DefaultSVEVectorLength));
MakeIf(header_, trip);
diamond_hif_ = MakeIf(diamond_top_, parameter_);
}
// Add an ArraySet to the loop which will be vectorized, thus setting the type of vector
// instructions in the graph to the given vector_type. This needs to be called to ensure the loop
// is not simplified by SimplifyInduction or SimplifyBlocks before vectorization.
void AddArraySetToLoop(DataType::Type vector_type) {
// Ensure the data type is a java type so it can be stored in a TypeField. The actual type does
// not matter as long as the size is the same so it can still be vectorized.
DataType::Type new_type = DataType::SignedIntegralTypeFromSize(DataType::Size(vector_type));
// Add an array set to prevent the loop from being optimized away before vectorization.
// Note: This uses an integer parameter and not an array reference to avoid the difficulties in
// allocating an array. The instruction is still treated as a valid ArraySet by loop
// optimization.
diamond_true_->AddInstruction(new (GetAllocator()) HArraySet(parameter_,
phi_,
graph_->GetIntConstant(1),
new_type,
/* dex_pc= */ 0));
}
// Replace the input of diamond_hif_ with a new condition of the given types.
void ReplaceIfCondition(DataType::Type l_type,
DataType::Type r_type,
HBasicBlock* condition_block,
IfCondition cond) {
AddArraySetToLoop(l_type);
HInstruction* l_param = MakeParam(l_type);
HInstruction* r_param = MakeParam(r_type);
HCondition* condition = MakeCondition(condition_block, cond, l_param, r_param);
diamond_hif_->ReplaceInput(condition, 0);
}
// Is loop optimization able to vectorize predicated code?
bool IsPredicatedVectorizationSupported() {
// Mirror the check guarding TryVectorizePredicated in TryOptimizeInnerLoopFinite.
return kForceTryPredicatedSIMD && loop_opt_->IsInPredicatedVectorizationMode();
}
HBasicBlock* header_;
HBasicBlock* diamond_top_;
HBasicBlock* diamond_true_;
HPhi* phi_;
HIf* diamond_hif_;
};
#endif // ART_ENABLE_CODEGEN_arm64
//
// The actual tests.
//
// Loop structure tests can't run the graph checker because they don't create valid graphs.
TEST_F(LoopOptimizationTest, NoLoops) {
PerformAnalysis(/*run_checker=*/ false);
EXPECT_EQ("", LoopStructure());
}
TEST_F(LoopOptimizationTest, SingleLoop) {
AddLoop(entry_block_, return_block_);
PerformAnalysis(/*run_checker=*/ false);
EXPECT_EQ("[]", LoopStructure());
}
TEST_F(LoopOptimizationTest, LoopNest10) {
HBasicBlock* b = entry_block_;
HBasicBlock* s = return_block_;
for (int i = 0; i < 10; i++) {
s = AddLoop(b, s);
b = s->GetSuccessors()[0];
}
PerformAnalysis(/*run_checker=*/ false);
EXPECT_EQ("[[[[[[[[[[]]]]]]]]]]", LoopStructure());
}
TEST_F(LoopOptimizationTest, LoopSequence10) {
HBasicBlock* b = entry_block_;
HBasicBlock* s = return_block_;
for (int i = 0; i < 10; i++) {
b = AddLoop(b, s);
s = b->GetSuccessors()[1];
}
PerformAnalysis(/*run_checker=*/ false);
EXPECT_EQ("[][][][][][][][][][]", LoopStructure());
}
TEST_F(LoopOptimizationTest, LoopSequenceOfNests) {
HBasicBlock* b = entry_block_;
HBasicBlock* s = return_block_;
for (int i = 0; i < 10; i++) {
b = AddLoop(b, s);
s = b->GetSuccessors()[1];
HBasicBlock* bi = b->GetSuccessors()[0];
HBasicBlock* si = b;
for (int j = 0; j < i; j++) {
si = AddLoop(bi, si);
bi = si->GetSuccessors()[0];
}
}
PerformAnalysis(/*run_checker=*/ false);
EXPECT_EQ("[]"
"[[]]"
"[[[]]]"
"[[[[]]]]"
"[[[[[]]]]]"
"[[[[[[]]]]]]"
"[[[[[[[]]]]]]]"
"[[[[[[[[]]]]]]]]"
"[[[[[[[[[]]]]]]]]]"
"[[[[[[[[[[]]]]]]]]]]",
LoopStructure());
}
TEST_F(LoopOptimizationTest, LoopNestWithSequence) {
HBasicBlock* b = entry_block_;
HBasicBlock* s = return_block_;
for (int i = 0; i < 10; i++) {
s = AddLoop(b, s);
b = s->GetSuccessors()[0];
}
b = s;
s = b->GetSuccessors()[1];
for (int i = 0; i < 9; i++) {
b = AddLoop(b, s);
s = b->GetSuccessors()[1];
}
PerformAnalysis(/*run_checker=*/ false);
EXPECT_EQ("[[[[[[[[[[][][][][][][][][][]]]]]]]]]]", LoopStructure());
}
// Check that SimplifyLoop() doesn't invalidate data flow when ordering loop headers'
// predecessors.
//
// This is a test for nodes.cc functionality - HGraph::SimplifyLoop.
TEST_F(LoopOptimizationTest, SimplifyLoopReoderPredecessors) {
// Can't use AddLoop as we want special order for blocks predecessors.
HBasicBlock* header = new (GetAllocator()) HBasicBlock(graph_);
HBasicBlock* body = new (GetAllocator()) HBasicBlock(graph_);
graph_->AddBlock(header);
graph_->AddBlock(body);
// Control flow: make a loop back edge first in the list of predecessors.
entry_block_->RemoveSuccessor(return_block_);
body->AddSuccessor(header);
entry_block_->AddSuccessor(header);
header->AddSuccessor(body);
header->AddSuccessor(return_block_);
DCHECK(header->GetSuccessors()[1] == return_block_);
// Data flow.
MakeIf(header, parameter_);
MakeGoto(body);
HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
header->AddPhi(phi);
HInstruction* add = MakeBinOp<HAdd>(body, DataType::Type::kInt32, phi, parameter_);
phi->AddInput(add);
phi->AddInput(parameter_);
graph_->ClearLoopInformation();
graph_->ClearDominanceInformation();
graph_->BuildDominatorTree();
// BuildDominatorTree inserts a block beetween loop header and entry block.
EXPECT_EQ(header->GetPredecessors()[0]->GetSinglePredecessor(), entry_block_);
// Check that after optimizations in BuildDominatorTree()/SimplifyCFG() phi inputs
// are still mapped correctly to the block predecessors.
for (size_t i = 0, e = phi->InputCount(); i < e; i++) {
HInstruction* input = phi->InputAt(i);
EXPECT_TRUE(input->GetBlock()->Dominates(header->GetPredecessors()[i]));
}
}
// Test that SimplifyLoop() processes the multiple-preheaders loops correctly.
//
// This is a test for nodes.cc functionality - HGraph::SimplifyLoop.
TEST_F(LoopOptimizationTest, SimplifyLoopSinglePreheader) {
HBasicBlock* header = AddLoop(entry_block_, return_block_);
header->InsertInstructionBefore(
new (GetAllocator()) HSuspendCheck(), header->GetLastInstruction());
// Insert an if construct before the loop so it will have two preheaders.
HBasicBlock* if_block = new (GetAllocator()) HBasicBlock(graph_);
HBasicBlock* preheader0 = new (GetAllocator()) HBasicBlock(graph_);
HBasicBlock* preheader1 = new (GetAllocator()) HBasicBlock(graph_);
graph_->AddBlock(if_block);
graph_->AddBlock(preheader0);
graph_->AddBlock(preheader1);
// Fix successors/predecessors.
entry_block_->ReplaceSuccessor(header, if_block);
if_block->AddSuccessor(preheader0);
if_block->AddSuccessor(preheader1);
preheader0->AddSuccessor(header);
preheader1->AddSuccessor(header);
MakeIf(if_block, parameter_);
MakeGoto(preheader0);
MakeGoto(preheader1);
HBasicBlock* body = header->GetSuccessors()[0];
DCHECK(body != return_block_);
// Add some data flow.
HIntConstant* const_0 = graph_->GetIntConstant(0);
HIntConstant* const_1 = graph_->GetIntConstant(1);
HIntConstant* const_2 = graph_->GetIntConstant(2);
HAdd* preheader0_add = MakeBinOp<HAdd>(preheader0, DataType::Type::kInt32, parameter_, const_0);
HAdd* preheader1_add = MakeBinOp<HAdd>(preheader1, DataType::Type::kInt32, parameter_, const_1);
HPhi* header_phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
header->AddPhi(header_phi);
HAdd* body_add = MakeBinOp<HAdd>(body, DataType::Type::kInt32, parameter_, const_2);
DCHECK(header->GetPredecessors()[0] == body);
DCHECK(header->GetPredecessors()[1] == preheader0);
DCHECK(header->GetPredecessors()[2] == preheader1);
header_phi->AddInput(body_add);
header_phi->AddInput(preheader0_add);
header_phi->AddInput(preheader1_add);
graph_->ClearLoopInformation();
graph_->ClearDominanceInformation();
graph_->BuildDominatorTree();
EXPECT_EQ(header->GetPredecessors().size(), 2u);
EXPECT_EQ(header->GetPredecessors()[1], body);
HBasicBlock* new_preheader = header->GetLoopInformation()->GetPreHeader();
EXPECT_EQ(preheader0->GetSingleSuccessor(), new_preheader);
EXPECT_EQ(preheader1->GetSingleSuccessor(), new_preheader);
EXPECT_EQ(new_preheader->GetPhis().CountSize(), 1u);
HPhi* new_preheader_phi = new_preheader->GetFirstPhi()->AsPhi();
EXPECT_EQ(new_preheader_phi->InputCount(), 2u);
EXPECT_EQ(new_preheader_phi->InputAt(0), preheader0_add);
EXPECT_EQ(new_preheader_phi->InputAt(1), preheader1_add);
EXPECT_EQ(header_phi->InputCount(), 2u);
EXPECT_EQ(header_phi->InputAt(0), new_preheader_phi);
EXPECT_EQ(header_phi->InputAt(1), body_add);
}
#ifdef ART_ENABLE_CODEGEN_arm64
#define FOR_EACH_CONDITION_INSTRUCTION(M, CondType) \
M(EQ, CondType) \
M(NE, CondType) \
M(LT, CondType) \
M(LE, CondType) \
M(GT, CondType) \
M(GE, CondType) \
M(B, CondType) \
M(BE, CondType) \
M(A, CondType) \
M(AE, CondType)
// Define tests ensuring that all types of conditions can be handled in predicated vectorization
// for diamond loops.
#define DEFINE_CONDITION_TESTS(Name, CondType) \
TEST_F(PredicatedSimdLoopOptimizationTest, VectorizeCondition##Name##CondType) { \
if (!IsPredicatedVectorizationSupported()) { \
GTEST_SKIP() << "Predicated SIMD is not enabled."; \
} \
ReplaceIfCondition(DataType::Type::k##CondType, \
DataType::Type::k##CondType, \
diamond_top_, \
kCond##Name); \
PerformAnalysis(/*run_checker=*/ true); \
EXPECT_TRUE(graph_->HasPredicatedSIMD()); \
}
FOR_EACH_CONDITION_INSTRUCTION(DEFINE_CONDITION_TESTS, Uint8)
FOR_EACH_CONDITION_INSTRUCTION(DEFINE_CONDITION_TESTS, Int8)
FOR_EACH_CONDITION_INSTRUCTION(DEFINE_CONDITION_TESTS, Uint16)
FOR_EACH_CONDITION_INSTRUCTION(DEFINE_CONDITION_TESTS, Int16)
FOR_EACH_CONDITION_INSTRUCTION(DEFINE_CONDITION_TESTS, Int32)
#undef DEFINE_CONDITION_TESTS
#undef FOR_EACH_CONDITION_INSTRUCTION
#endif // ART_ENABLE_CODEGEN_arm64
} // namespace art