path: root/compiler/optimizing/loop_optimization_test.cc

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