compiler/optimizing/loop_optimization_test.cc - platform/art - Git at Google


            
            /*

            
             * 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
	/*
	* 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