Enable support of VecLoad/VecStore in LSE
Changes:
- Enable VecLoad and VecStore support in LSE.
- This CL is based on Mingyao's CL: More general store elimination.
- The new gtest load_store_elimination_test is to test some corner cases
where ArrayGet/ArraySet/VecLoad/VecStore are mixed and overlap.
- The new java 530-checker-lse-simd.
Test: test.py --host --optimizing --jit --gtest
Test: test.py --target --optimizing --jit
Test: run-gtests.sh
Test: load_store_elimination_test
Test: 530-checker-lse-simd
Test: ./art/test/run-test --optimizing --64 --gcstress 667-checker-simd-alignment
Test: m -j80 art-check-testing-apex-gen
Change-Id: I2d2024ec75a2aaef56b527db98abb40c5f16be79
diff --git a/compiler/optimizing/load_store_elimination_test.cc b/compiler/optimizing/load_store_elimination_test.cc
new file mode 100644
index 0000000..7380378
--- /dev/null
+++ b/compiler/optimizing/load_store_elimination_test.cc
@@ -0,0 +1,893 @@
+/*
+ * Copyright (C) 2019 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 <tuple>
+
+#include "load_store_analysis.h"
+#include "load_store_elimination.h"
+#include "nodes.h"
+#include "optimizing_unit_test.h"
+#include "side_effects_analysis.h"
+
+#include "gtest/gtest.h"
+
+namespace art {
+
+class LoadStoreEliminationTest : public ImprovedOptimizingUnitTest {
+ public:
+ void PerformLSE() {
+ graph_->BuildDominatorTree();
+ SideEffectsAnalysis side_effects(graph_);
+ side_effects.Run();
+ LoadStoreAnalysis lsa(graph_);
+ lsa.Run();
+ LoadStoreElimination lse(graph_, side_effects, lsa, nullptr);
+ lse.Run();
+ EXPECT_TRUE(CheckGraphSkipRefTypeInfoChecks());
+ }
+
+ // Create instructions shared among tests.
+ void CreateEntryBlockInstructions() {
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c4 = graph_->GetIntConstant(4);
+ i_add1_ = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_, c1);
+ i_add4_ = new (GetAllocator()) HAdd(DataType::Type::kInt32, i_, c4);
+ entry_block_->AddInstruction(i_add1_);
+ entry_block_->AddInstruction(i_add4_);
+ entry_block_->AddInstruction(new (GetAllocator()) HGoto());
+ }
+
+ // Create the major CFG used by tests:
+ // entry
+ // |
+ // pre_header
+ // |
+ // loop[]
+ // |
+ // return
+ // |
+ // exit
+ void CreateTestControlFlowGraph() {
+ pre_header_ = new (GetAllocator()) HBasicBlock(graph_);
+ loop_ = new (GetAllocator()) HBasicBlock(graph_);
+
+ graph_->AddBlock(pre_header_);
+ graph_->AddBlock(loop_);
+
+ entry_block_->ReplaceSuccessor(return_block_, pre_header_);
+ pre_header_->AddSuccessor(loop_);
+ loop_->AddSuccessor(loop_);
+ loop_->AddSuccessor(return_block_);
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ CreateEntryBlockInstructions();
+
+ // pre_header block
+ // phi = 0;
+ phi_ = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
+ loop_->AddPhi(phi_);
+ pre_header_->AddInstruction(new (GetAllocator()) HGoto());
+ phi_->AddInput(c0);
+
+ // loop block:
+ // suspend_check
+ // phi++;
+ // if (phi >= 128)
+ suspend_check_ = new (GetAllocator()) HSuspendCheck();
+ HInstruction* inc_phi = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi_, c1);
+ HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(phi_, c128);
+ HInstruction* hif = new (GetAllocator()) HIf(cmp);
+ loop_->AddInstruction(suspend_check_);
+ loop_->AddInstruction(inc_phi);
+ loop_->AddInstruction(cmp);
+ loop_->AddInstruction(hif);
+ phi_->AddInput(inc_phi);
+
+ CreateEnvForSuspendCheck();
+ }
+
+ void CreateEnvForSuspendCheck() {
+ ArenaVector<HInstruction*> current_locals({array_, i_, j_},
+ GetAllocator()->Adapter(kArenaAllocInstruction));
+ ManuallyBuildEnvFor(suspend_check_, ¤t_locals);
+ }
+
+ // Create the diamond-shaped CFG:
+ // upper
+ // / \
+ // left right
+ // \ /
+ // down
+ //
+ // Return: the basic blocks forming the CFG in the following order {upper, left, right, down}.
+ std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateDiamondShapedCFG() {
+ CreateEntryBlockInstructions();
+
+ HBasicBlock* upper = new (GetAllocator()) HBasicBlock(graph_);
+ HBasicBlock* left = new (GetAllocator()) HBasicBlock(graph_);
+ HBasicBlock* right = new (GetAllocator()) HBasicBlock(graph_);
+
+ graph_->AddBlock(upper);
+ graph_->AddBlock(left);
+ graph_->AddBlock(right);
+
+ entry_block_->ReplaceSuccessor(return_block_, upper);
+ upper->AddSuccessor(left);
+ upper->AddSuccessor(right);
+ left->AddSuccessor(return_block_);
+ right->AddSuccessor(return_block_);
+
+ HInstruction* cmp = new (GetAllocator()) HGreaterThanOrEqual(i_, j_);
+ HInstruction* hif = new (GetAllocator()) HIf(cmp);
+ upper->AddInstruction(cmp);
+ upper->AddInstruction(hif);
+
+ left->AddInstruction(new (GetAllocator()) HGoto());
+ right->AddInstruction(new (GetAllocator()) HGoto());
+
+ return std::make_tuple(upper, left, right, return_block_);
+ }
+
+ // Add a HVecLoad instruction to the end of the provided basic block.
+ //
+ // Return: the created HVecLoad instruction.
+ HInstruction* AddVecLoad(HBasicBlock* block, HInstruction* array, HInstruction* index) {
+ DCHECK(block != nullptr);
+ DCHECK(array != nullptr);
+ DCHECK(index != nullptr);
+ HInstruction* vload = new (GetAllocator()) HVecLoad(
+ GetAllocator(),
+ array,
+ index,
+ DataType::Type::kInt32,
+ SideEffects::ArrayReadOfType(DataType::Type::kInt32),
+ 4,
+ /*is_string_char_at*/ false,
+ kNoDexPc);
+ block->InsertInstructionBefore(vload, block->GetLastInstruction());
+ return vload;
+ }
+
+ // Add a HVecStore instruction to the end of the provided basic block.
+ // If no vdata is specified, generate HVecStore: array[index] = [1,1,1,1].
+ //
+ // Return: the created HVecStore instruction.
+ HInstruction* AddVecStore(HBasicBlock* block,
+ HInstruction* array,
+ HInstruction* index,
+ HInstruction* vdata = nullptr) {
+ DCHECK(block != nullptr);
+ DCHECK(array != nullptr);
+ DCHECK(index != nullptr);
+ if (vdata == nullptr) {
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ vdata = new (GetAllocator()) HVecReplicateScalar(GetAllocator(),
+ c1,
+ DataType::Type::kInt32,
+ 4,
+ kNoDexPc);
+ block->InsertInstructionBefore(vdata, block->GetLastInstruction());
+ }
+ HInstruction* vstore = new (GetAllocator()) HVecStore(
+ GetAllocator(),
+ array,
+ index,
+ vdata,
+ DataType::Type::kInt32,
+ SideEffects::ArrayWriteOfType(DataType::Type::kInt32),
+ 4,
+ kNoDexPc);
+ block->InsertInstructionBefore(vstore, block->GetLastInstruction());
+ return vstore;
+ }
+
+ // Add a HArrayGet instruction to the end of the provided basic block.
+ //
+ // Return: the created HArrayGet instruction.
+ HInstruction* AddArrayGet(HBasicBlock* block, HInstruction* array, HInstruction* index) {
+ DCHECK(block != nullptr);
+ DCHECK(array != nullptr);
+ DCHECK(index != nullptr);
+ HInstruction* get = new (GetAllocator()) HArrayGet(array, index, DataType::Type::kInt32, 0);
+ block->InsertInstructionBefore(get, block->GetLastInstruction());
+ return get;
+ }
+
+ // Add a HArraySet instruction to the end of the provided basic block.
+ // If no data is specified, generate HArraySet: array[index] = 1.
+ //
+ // Return: the created HArraySet instruction.
+ HInstruction* AddArraySet(HBasicBlock* block,
+ HInstruction* array,
+ HInstruction* index,
+ HInstruction* data = nullptr) {
+ DCHECK(block != nullptr);
+ DCHECK(array != nullptr);
+ DCHECK(index != nullptr);
+ if (data == nullptr) {
+ data = graph_->GetIntConstant(1);
+ }
+ HInstruction* store = new (GetAllocator()) HArraySet(array,
+ index,
+ data,
+ DataType::Type::kInt32,
+ 0);
+ block->InsertInstructionBefore(store, block->GetLastInstruction());
+ return store;
+ }
+
+ void CreateParameters() override {
+ parameters_.push_back(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
+ dex::TypeIndex(0),
+ 0,
+ DataType::Type::kInt32));
+ array_ = parameters_.back();
+ parameters_.push_back(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
+ dex::TypeIndex(1),
+ 1,
+ DataType::Type::kInt32));
+ i_ = parameters_.back();
+ parameters_.push_back(new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
+ dex::TypeIndex(1),
+ 2,
+ DataType::Type::kInt32));
+ j_ = parameters_.back();
+ }
+
+ HBasicBlock* pre_header_;
+ HBasicBlock* loop_;
+
+ HInstruction* array_;
+ HInstruction* i_;
+ HInstruction* j_;
+ HInstruction* i_add1_;
+ HInstruction* i_add4_;
+ HInstruction* suspend_check_;
+
+ HPhi* phi_;
+};
+
+TEST_F(LoadStoreEliminationTest, ArrayGetSetElimination) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* c3 = graph_->GetIntConstant(3);
+
+ // array[1] = 1;
+ // x = array[1]; <--- Remove.
+ // y = array[2];
+ // array[1] = 1; <--- Remove, since it stores same value.
+ // array[i] = 3; <--- MAY alias.
+ // array[1] = 1; <--- Cannot remove, even if it stores the same value.
+ AddArraySet(entry_block_, array_, c1, c1);
+ HInstruction* load1 = AddArrayGet(entry_block_, array_, c1);
+ HInstruction* load2 = AddArrayGet(entry_block_, array_, c2);
+ HInstruction* store1 = AddArraySet(entry_block_, array_, c1, c1);
+ AddArraySet(entry_block_, array_, i_, c3);
+ HInstruction* store2 = AddArraySet(entry_block_, array_, c1, c1);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(load1));
+ ASSERT_FALSE(IsRemoved(load2));
+ ASSERT_TRUE(IsRemoved(store1));
+ ASSERT_FALSE(IsRemoved(store2));
+}
+
+TEST_F(LoadStoreEliminationTest, SameHeapValue1) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c1 = graph_->GetIntConstant(1);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+
+ // Test LSE handling same value stores on array.
+ // array[1] = 1;
+ // array[2] = 1;
+ // array[1] = 1; <--- Can remove.
+ // array[1] = 2; <--- Can NOT remove.
+ AddArraySet(entry_block_, array_, c1, c1);
+ AddArraySet(entry_block_, array_, c2, c1);
+ HInstruction* store1 = AddArraySet(entry_block_, array_, c1, c1);
+ HInstruction* store2 = AddArraySet(entry_block_, array_, c1, c2);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(store1));
+ ASSERT_FALSE(IsRemoved(store2));
+}
+
+TEST_F(LoadStoreEliminationTest, SameHeapValue2) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ // Test LSE handling same value stores on vector.
+ // vdata = [0x1, 0x2, 0x3, 0x4, ...]
+ // VecStore array[i...] = vdata;
+ // VecStore array[j...] = vdata; <--- MAY ALIAS.
+ // VecStore array[i...] = vdata; <--- Cannot Remove, even if it's same value.
+ AddVecStore(entry_block_, array_, i_);
+ AddVecStore(entry_block_, array_, j_);
+ HInstruction* vstore = AddVecStore(entry_block_, array_, i_);
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vstore));
+}
+
+TEST_F(LoadStoreEliminationTest, SameHeapValue3) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ // VecStore array[i...] = vdata;
+ // VecStore array[i+1...] = vdata; <--- MAY alias due to partial overlap.
+ // VecStore array[i...] = vdata; <--- Cannot remove, even if it's same value.
+ AddVecStore(entry_block_, array_, i_);
+ AddVecStore(entry_block_, array_, i_add1_);
+ HInstruction* vstore = AddVecStore(entry_block_, array_, i_);
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vstore));
+}
+
+TEST_F(LoadStoreEliminationTest, OverlappingLoadStore) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c1 = graph_->GetIntConstant(1);
+
+ // Test LSE handling array LSE when there is vector store in between.
+ // a[i] = 1;
+ // .. = a[i]; <-- Remove.
+ // a[i,i+1,i+2,i+3] = data; <-- PARTIAL OVERLAP !
+ // .. = a[i]; <-- Cannot remove.
+ AddArraySet(entry_block_, array_, i_, c1);
+ HInstruction* load1 = AddArrayGet(entry_block_, array_, i_);
+ AddVecStore(entry_block_, array_, i_);
+ HInstruction* load2 = AddArrayGet(entry_block_, array_, i_);
+
+ // Test LSE handling vector load/store partial overlap.
+ // a[i,i+1,i+2,i+3] = data;
+ // a[i+4,i+5,i+6,i+7] = data;
+ // .. = a[i,i+1,i+2,i+3];
+ // .. = a[i+4,i+5,i+6,i+7];
+ // a[i+1,i+2,i+3,i+4] = data; <-- PARTIAL OVERLAP !
+ // .. = a[i,i+1,i+2,i+3];
+ // .. = a[i+4,i+5,i+6,i+7];
+ AddVecStore(entry_block_, array_, i_);
+ AddVecStore(entry_block_, array_, i_add4_);
+ HInstruction* vload1 = AddVecLoad(entry_block_, array_, i_);
+ HInstruction* vload2 = AddVecLoad(entry_block_, array_, i_add4_);
+ AddVecStore(entry_block_, array_, i_add1_);
+ HInstruction* vload3 = AddVecLoad(entry_block_, array_, i_);
+ HInstruction* vload4 = AddVecLoad(entry_block_, array_, i_add4_);
+
+ // Test LSE handling vector LSE when there is array store in between.
+ // a[i,i+1,i+2,i+3] = data;
+ // a[i+1] = 1; <-- PARTIAL OVERLAP !
+ // .. = a[i,i+1,i+2,i+3];
+ AddVecStore(entry_block_, array_, i_);
+ AddArraySet(entry_block_, array_, i_, c1);
+ HInstruction* vload5 = AddVecLoad(entry_block_, array_, i_);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(load1));
+ ASSERT_FALSE(IsRemoved(load2));
+
+ ASSERT_TRUE(IsRemoved(vload1));
+ ASSERT_TRUE(IsRemoved(vload2));
+ ASSERT_FALSE(IsRemoved(vload3));
+ ASSERT_FALSE(IsRemoved(vload4));
+
+ ASSERT_FALSE(IsRemoved(vload5));
+}
+// function (int[] a, int j) {
+// a[j] = 1;
+// for (int i=0; i<128; i++) {
+// /* doesn't do any write */
+// }
+// a[j] = 1;
+TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithoutSideEffects) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c1 = graph_->GetIntConstant(1);
+
+ // a[j] = 1
+ AddArraySet(pre_header_, array_, j_, c1);
+
+ // LOOP BODY:
+ // .. = a[i,i+1,i+2,i+3];
+ AddVecLoad(loop_, array_, phi_);
+
+ // a[j] = 1;
+ HInstruction* array_set = AddArraySet(return_block_, array_, j_, c1);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(array_set));
+}
+
+// function (int[] a, int j) {
+// int[] b = new int[128];
+// a[j] = 0;
+// for (int phi=0; phi<128; phi++) {
+// a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
+// b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
+// }
+// a[j] = 0;
+// }
+TEST_F(LoadStoreEliminationTest, StoreAfterSIMDLoopWithSideEffects) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
+ array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // a[j] = 0;
+ AddArraySet(pre_header_, array_, j_, c0);
+
+ // LOOP BODY:
+ // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
+ // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
+ AddVecStore(loop_, array_, phi_);
+ HInstruction* vload = AddVecLoad(loop_, array_, phi_);
+ AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
+
+ // a[j] = 0;
+ HInstruction* a_set = AddArraySet(return_block_, array_, j_, c0);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(vload));
+ ASSERT_FALSE(IsRemoved(a_set)); // Cannot remove due to write side-effect in the loop.
+}
+
+// function (int[] a, int j) {
+// int[] b = new int[128];
+// a[j] = 0;
+// for (int phi=0; phi<128; phi++) {
+// a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
+// b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
+// }
+// x = a[j];
+// }
+TEST_F(LoadStoreEliminationTest, LoadAfterSIMDLoopWithSideEffects) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
+ array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // a[j] = 0;
+ AddArraySet(pre_header_, array_, j_, c0);
+
+ // LOOP BODY:
+ // a[phi,phi+1,phi+2,phi+3] = [1,1,1,1];
+ // b[phi,phi+1,phi+2,phi+3] = a[phi,phi+1,phi+2,phi+3];
+ AddVecStore(loop_, array_, phi_);
+ HInstruction* vload = AddVecLoad(loop_, array_, phi_);
+ AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
+
+ // x = a[j];
+ HInstruction* load = AddArrayGet(return_block_, array_, j_);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(vload));
+ ASSERT_FALSE(IsRemoved(load)); // Cannot remove due to write side-effect in the loop.
+}
+
+// Check that merging works correctly when there are VecStors in predecessors.
+//
+// vstore1: a[i,... i + 3] = [1,...1]
+// / \
+// / \
+// vstore2: a[i,... i + 3] = [1,...1] vstore3: a[i+1, ... i + 4] = [1, ... 1]
+// \ /
+// \ /
+// vstore4: a[i,... i + 3] = [1,...1]
+//
+// Expected:
+// 'vstore2' is removed.
+// 'vstore3' is not removed.
+// 'vstore4' is not removed. Such cases are not supported at the moment.
+TEST_F(LoadStoreEliminationTest, MergePredecessorVecStores) {
+ InitGraph();
+
+ HBasicBlock* upper;
+ HBasicBlock* left;
+ HBasicBlock* right;
+ HBasicBlock* down;
+ std::tie(upper, left, right, down) = CreateDiamondShapedCFG();
+
+ // upper: a[i,... i + 3] = [1,...1]
+ HInstruction* vstore1 = AddVecStore(upper, array_, i_);
+ HInstruction* vdata = vstore1->InputAt(2);
+
+ // left: a[i,... i + 3] = [1,...1]
+ HInstruction* vstore2 = AddVecStore(left, array_, i_, vdata);
+
+ // right: a[i+1, ... i + 4] = [1, ... 1]
+ HInstruction* vstore3 = AddVecStore(right, array_, i_add1_, vdata);
+
+ // down: a[i,... i + 3] = [1,...1]
+ HInstruction* vstore4 = AddVecStore(down, array_, i_, vdata);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(vstore2));
+ ASSERT_FALSE(IsRemoved(vstore3));
+ ASSERT_FALSE(IsRemoved(vstore4));
+}
+
+// Check that merging works correctly when there are ArraySets in predecessors.
+//
+// a[i] = 1
+// / \
+// / \
+// store1: a[i] = 1 store2: a[i+1] = 1
+// \ /
+// \ /
+// store3: a[i] = 1
+//
+// Expected:
+// 'store1' is removed.
+// 'store2' is not removed.
+// 'store3' is removed.
+TEST_F(LoadStoreEliminationTest, MergePredecessorStores) {
+ InitGraph();
+
+ HBasicBlock* upper;
+ HBasicBlock* left;
+ HBasicBlock* right;
+ HBasicBlock* down;
+ std::tie(upper, left, right, down) = CreateDiamondShapedCFG();
+
+ // upper: a[i,... i + 3] = [1,...1]
+ AddArraySet(upper, array_, i_);
+
+ // left: a[i,... i + 3] = [1,...1]
+ HInstruction* store1 = AddArraySet(left, array_, i_);
+
+ // right: a[i+1, ... i + 4] = [1, ... 1]
+ HInstruction* store2 = AddArraySet(right, array_, i_add1_);
+
+ // down: a[i,... i + 3] = [1,...1]
+ HInstruction* store3 = AddArraySet(down, array_, i_);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(store1));
+ ASSERT_FALSE(IsRemoved(store2));
+ ASSERT_TRUE(IsRemoved(store3));
+}
+
+// Check that redundant VStore/VLoad are removed from a SIMD loop.
+//
+// LOOP BODY
+// vstore1: a[i,... i + 3] = [1,...1]
+// vload: x = a[i,... i + 3]
+// vstore2: b[i,... i + 3] = x
+// vstore3: a[i,... i + 3] = [1,...1]
+//
+// Expected:
+// 'vstore1' is not removed.
+// 'vload' is removed.
+// 'vstore3' is removed.
+TEST_F(LoadStoreEliminationTest, RedundantVStoreVLoadInLoop) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
+ array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // LOOP BODY:
+ // a[i,... i + 3] = [1,...1]
+ // x = a[i,... i + 3]
+ // b[i,... i + 3] = x
+ // a[i,... i + 3] = [1,...1]
+ HInstruction* vstore1 = AddVecStore(loop_, array_a, phi_);
+ HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
+ AddVecStore(loop_, array_b, phi_, vload->AsVecLoad());
+ HInstruction* vstore3 = AddVecStore(loop_, array_a, phi_, vstore1->InputAt(2));
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vstore1));
+ ASSERT_TRUE(IsRemoved(vload));
+ ASSERT_TRUE(IsRemoved(vstore3));
+}
+
+// Loop write side effects invalidate all stores.
+// This causes stores after such loops not to be removed, even
+// their values are known.
+TEST_F(LoadStoreEliminationTest, StoreAfterLoopWithSideEffects) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c2 = graph_->GetIntConstant(2);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ // array[0] = 2;
+ // loop:
+ // b[i] = array[i]
+ // array[0] = 2
+ AddArraySet(entry_block_, array_, c0, c2);
+
+ HInstruction* array_b = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_b, pre_header_->GetLastInstruction());
+ array_b->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ HInstruction* load = AddArrayGet(loop_, array_, phi_);
+ AddArraySet(loop_, array_b, phi_, load);
+
+ HInstruction* store = AddArraySet(return_block_, array_, c0, c2);
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(store));
+}
+
+// As it is not allowed to use defaults for VecLoads, check if there is a new created array
+// a VecLoad used in a loop and after it is not replaced with a default.
+TEST_F(LoadStoreEliminationTest, VLoadDefaultValueInLoopWithoutWriteSideEffects) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // LOOP BODY:
+ // v = a[i,... i + 3]
+ // array[0,... 3] = v
+ HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
+ HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vload));
+ ASSERT_FALSE(IsRemoved(vstore));
+}
+
+// As it is not allowed to use defaults for VecLoads, check if there is a new created array
+// a VecLoad is not replaced with a default.
+TEST_F(LoadStoreEliminationTest, VLoadDefaultValue) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // v = a[0,... 3]
+ // array[0,... 3] = v
+ HInstruction* vload = AddVecLoad(pre_header_, array_a, c0);
+ HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vload));
+ ASSERT_FALSE(IsRemoved(vstore));
+}
+
+// As it is allowed to use defaults for ordinary loads, check if there is a new created array
+// a load used in a loop and after it is replaced with a default.
+TEST_F(LoadStoreEliminationTest, LoadDefaultValueInLoopWithoutWriteSideEffects) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // LOOP BODY:
+ // v = a[i]
+ // array[0] = v
+ HInstruction* load = AddArrayGet(loop_, array_a, phi_);
+ HInstruction* store = AddArraySet(return_block_, array_, c0, load);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(load));
+ ASSERT_FALSE(IsRemoved(store));
+}
+
+// As it is allowed to use defaults for ordinary loads, check if there is a new created array
+// a load is replaced with a default.
+TEST_F(LoadStoreEliminationTest, LoadDefaultValue) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // v = a[0]
+ // array[0] = v
+ HInstruction* load = AddArrayGet(pre_header_, array_a, c0);
+ HInstruction* store = AddArraySet(return_block_, array_, c0, load);
+
+ PerformLSE();
+
+ ASSERT_TRUE(IsRemoved(load));
+ ASSERT_FALSE(IsRemoved(store));
+}
+
+// As it is not allowed to use defaults for VecLoads but allowed for regular loads,
+// check if there is a new created array, a VecLoad and a load used in a loop and after it,
+// VecLoad is not replaced with a default but the load is.
+TEST_F(LoadStoreEliminationTest, VLoadAndLoadDefaultValueInLoopWithoutWriteSideEffects) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // LOOP BODY:
+ // v = a[i,... i + 3]
+ // v1 = a[i]
+ // array[0,... 3] = v
+ // array[0] = v1
+ HInstruction* vload = AddVecLoad(loop_, array_a, phi_);
+ HInstruction* load = AddArrayGet(loop_, array_a, phi_);
+ HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
+ HInstruction* store = AddArraySet(return_block_, array_, c0, load);
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vload));
+ ASSERT_TRUE(IsRemoved(load));
+ ASSERT_FALSE(IsRemoved(vstore));
+ ASSERT_FALSE(IsRemoved(store));
+}
+
+// As it is not allowed to use defaults for VecLoads but allowed for regular loads,
+// check if there is a new created array, a VecLoad and a load,
+// VecLoad is not replaced with a default but the load is.
+TEST_F(LoadStoreEliminationTest, VLoadAndLoadDefaultValue) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // v = a[0,... 3]
+ // v1 = a[0]
+ // array[0,... 3] = v
+ // array[0] = v1
+ HInstruction* vload = AddVecLoad(pre_header_, array_a, c0);
+ HInstruction* load = AddArrayGet(pre_header_, array_a, c0);
+ HInstruction* vstore = AddVecStore(return_block_, array_, c0, vload->AsVecLoad());
+ HInstruction* store = AddArraySet(return_block_, array_, c0, load);
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vload));
+ ASSERT_TRUE(IsRemoved(load));
+ ASSERT_FALSE(IsRemoved(vstore));
+ ASSERT_FALSE(IsRemoved(store));
+}
+
+// It is not allowed to use defaults for VecLoads. However it should not prevent from removing
+// loads getting the same value.
+// Check a load getting a known value is eliminated (a loop test case).
+TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoadInLoopWithoutWriteSideEffects) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // LOOP BODY:
+ // v = a[i,... i + 3]
+ // v1 = a[i,... i + 3]
+ // array[0,... 3] = v
+ // array[128,... 131] = v1
+ HInstruction* vload1 = AddVecLoad(loop_, array_a, phi_);
+ HInstruction* vload2 = AddVecLoad(loop_, array_a, phi_);
+ HInstruction* vstore1 = AddVecStore(return_block_, array_, c0, vload1->AsVecLoad());
+ HInstruction* vstore2 = AddVecStore(return_block_, array_, c128, vload2->AsVecLoad());
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vload1));
+ ASSERT_TRUE(IsRemoved(vload2));
+ ASSERT_FALSE(IsRemoved(vstore1));
+ ASSERT_FALSE(IsRemoved(vstore2));
+}
+
+// It is not allowed to use defaults for VecLoads. However it should not prevent from removing
+// loads getting the same value.
+// Check a load getting a known value is eliminated.
+TEST_F(LoadStoreEliminationTest, VLoadDefaultValueAndVLoad) {
+ InitGraph();
+ CreateTestControlFlowGraph();
+
+ HInstruction* c0 = graph_->GetIntConstant(0);
+ HInstruction* c128 = graph_->GetIntConstant(128);
+
+ HInstruction* array_a = new (GetAllocator()) HNewArray(c0, c128, 0, 0);
+ pre_header_->InsertInstructionBefore(array_a, pre_header_->GetLastInstruction());
+ array_a->CopyEnvironmentFrom(suspend_check_->GetEnvironment());
+
+ // v = a[0,... 3]
+ // v1 = a[0,... 3]
+ // array[0,... 3] = v
+ // array[128,... 131] = v1
+ HInstruction* vload1 = AddVecLoad(pre_header_, array_a, c0);
+ HInstruction* vload2 = AddVecLoad(pre_header_, array_a, c0);
+ HInstruction* vstore1 = AddVecStore(return_block_, array_, c0, vload1->AsVecLoad());
+ HInstruction* vstore2 = AddVecStore(return_block_, array_, c128, vload2->AsVecLoad());
+
+ PerformLSE();
+
+ ASSERT_FALSE(IsRemoved(vload1));
+ ASSERT_TRUE(IsRemoved(vload2));
+ ASSERT_FALSE(IsRemoved(vstore1));
+ ASSERT_FALSE(IsRemoved(vstore2));
+}
+
+} // namespace art