Support all conditions in predicated vectorization

Support all condition types inside the condition when performing
diamond loop auto-vectorization. This allows diamond loop
auto-vectorization to be performed on a greater variety of loops.

To support this change, new vector condition nodes are added to
mirror the scalar condition nodes.

Also add a new gtest class to test whether predicated vectorization
can be performed on different combinations of condition types and
data types.

Authors: Chris Jones <christopher.jones@arm.com>,
         Konstantin Baladurin <konstantin.baladurin@arm.com>

Test: export ART_FORCE_TRY_PREDICATED_SIMD=true && \
      art/test.py --target --optimizing
Test: art/test.py --target --host --optimizing
Test: 661-checker-simd-cf-loops
Test: art/test.py --gtest art_compiler_tests
Change-Id: Ic9c925f1a58ada13d9031de3b445dcd4f77764b7

1 files changed, 186 insertions, 45 deletions

diff --git a/compiler/optimizing/loop_optimization_test.cc b/compiler/optimizing/loop_optimization_test.cc
index 81867beb4b..c60b66b6d7 100644
--- a/compiler/optimizing/loop_optimization_test.cc
+++ b/compiler/optimizing/loop_optimization_test.cc
@@ -14,29 +14,29 @@
  * 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 {
 
-/**
- * Fixture class for the loop optimization tests. These unit tests focus
- * constructing the loop hierarchy. Actual optimizations are tested
- * through the checker tests.
- */
-class LoopOptimizationTest : public OptimizingUnitTest {
+// Base class for loop optimization tests.
+class LoopOptimizationTestBase : public OptimizingUnitTest {
  protected:
   void SetUp() override {
     OptimizingUnitTest::SetUp();
 
-    graph_ = CreateGraph();
     BuildGraph();
     iva_  = new (GetAllocator()) HInductionVarAnalysis(graph_);
-    compiler_options_ = CommonCompilerTest::CreateCompilerOptions(kRuntimeISA, "default");
-    DCHECK(compiler_options_ != nullptr);
+    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(
@@ -51,24 +51,52 @@ class LoopOptimizationTest : public OptimizingUnitTest {
     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() {
+  void BuildGraph() override {
+    return_block_ = InitEntryMainExitGraph();
     graph_->SetNumberOfVRegs(1);
-    entry_block_ = new (GetAllocator()) HBasicBlock(graph_);
-    return_block_ = new (GetAllocator()) HBasicBlock(graph_);
-    exit_block_ = new (GetAllocator()) HBasicBlock(graph_);
-    graph_->AddBlock(entry_block_);
-    graph_->AddBlock(return_block_);
-    graph_->AddBlock(exit_block_);
-    graph_->SetEntryBlock(entry_block_);
-    graph_->SetExitBlock(exit_block_);
     parameter_ = MakeParam(DataType::Type::kInt32);
-    MakeReturnVoid(return_block_);
-    MakeExit(exit_block_);
-    entry_block_->AddSuccessor(return_block_);
-    return_block_->AddSuccessor(exit_block_);
   }
 
   /** Adds a loop nest at given position before successor. */
@@ -87,13 +115,6 @@ class LoopOptimizationTest : public OptimizingUnitTest {
     return header;
   }
 
-  /** Performs analysis. */
-  void PerformAnalysis() {
-    graph_->BuildDominatorTree();
-    iva_->Run();
-    loop_opt_->Run();
-  }
-
   /** Constructs string representation of computed loop hierarchy. */
   std::string LoopStructure() {
     return LoopStructureRecurse(loop_opt_->top_loop_);
@@ -109,34 +130,118 @@ class LoopOptimizationTest : public OptimizingUnitTest {
     }
     return s;
   }
+};
 
-  // General building fields.
-  HGraph* graph_;
+#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();
+  }
 
-  std::unique_ptr<CompilerOptions> compiler_options_;
-  std::unique_ptr<CodeGenerator> codegen_;
-  HInductionVarAnalysis* iva_;
-  HLoopOptimization* loop_opt_;
+  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);
 
-  HBasicBlock* entry_block_;
-  HBasicBlock* return_block_;
-  HBasicBlock* exit_block_;
+    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_);
+  }
 
-  HInstruction* 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();
+  PerformAnalysis(/*run_checker=*/ false);
   EXPECT_EQ("", LoopStructure());
 }
 
 TEST_F(LoopOptimizationTest, SingleLoop) {
   AddLoop(entry_block_, return_block_);
-  PerformAnalysis();
+  PerformAnalysis(/*run_checker=*/ false);
   EXPECT_EQ("[]", LoopStructure());
 }
 
@@ -147,7 +252,7 @@ TEST_F(LoopOptimizationTest, LoopNest10) {
     s = AddLoop(b, s);
     b = s->GetSuccessors()[0];
   }
-  PerformAnalysis();
+  PerformAnalysis(/*run_checker=*/ false);
   EXPECT_EQ("[[[[[[[[[[]]]]]]]]]]", LoopStructure());
 }
 
@@ -158,7 +263,7 @@ TEST_F(LoopOptimizationTest, LoopSequence10) {
     b = AddLoop(b, s);
     s = b->GetSuccessors()[1];
   }
-  PerformAnalysis();
+  PerformAnalysis(/*run_checker=*/ false);
   EXPECT_EQ("[][][][][][][][][][]", LoopStructure());
 }
 
@@ -175,7 +280,7 @@ TEST_F(LoopOptimizationTest, LoopSequenceOfNests) {
       bi = si->GetSuccessors()[0];
     }
   }
-  PerformAnalysis();
+  PerformAnalysis(/*run_checker=*/ false);
   EXPECT_EQ("[]"
             "[[]]"
             "[[[]]]"
@@ -202,7 +307,7 @@ TEST_F(LoopOptimizationTest, LoopNestWithSequence) {
     b = AddLoop(b, s);
     s = b->GetSuccessors()[1];
   }
-  PerformAnalysis();
+  PerformAnalysis(/*run_checker=*/ false);
   EXPECT_EQ("[[[[[[[[[[][][][][][][][][][]]]]]]]]]]", LoopStructure());
 }
 
@@ -326,4 +431,40 @@ TEST_F(LoopOptimizationTest, SimplifyLoopSinglePreheader) {
   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